CAP

CAP Theorem described: http://en.wikipedia.org/wiki/CAP_theorem
Brewer's Conjecture in detail: http://lpd.epfl.ch/sgilbert/pubs/BrewersConjecture-SigAct.pdf

Disclaimer This page is currently in very rough "brain dump form." If something doesn't make sense, you are probably more correct in your understanding than I.

Consistency

The default usage of the O1 graph database will favor consistency over availability and partition tolerance. Correctness is the default highest priority. It is a design goal to offer a configurable option to relax absolute consistency to improve partition tolerance (via eventual consistency).

An implementation of Paxos is the most likely approach to ensure all writes are eventually consistent in the face of failure. Cells will require a version number to participate in consensus based reconciliation.

Transaction consistency and concurrency will follow a typical in-memory transaction approach where:
  • Optimistic concurrency is assumed
  • Write-write conflict will cause a transaction to fail
  • The read-committed isolation level is the default behavior
  • Cells will be versioned, and when a modification happens, the transaction ID will represent the version of the cell.

Availability

The design of the O1 graph database will support high availability via read only replication of RAM Trunk data, but prefer consistency. This preference is expressed via an active RAM Trunk and offline replica on another node. The number of replicas is expected to be configurable.

Performance of write operations will depend on the level of consistency desired and the number of trunk replicas to support high availability. This is the primary trade-off; eventual consistency will provide unblocked asynchronous writes, but risk inconsistency with message loss.

If absolute consistency is required, the system will be unavailable for as long as it takes to ensure a replica is in a consistent state. Additionally, write operations may fail if they cannot be committed across all replicas, if high consistency is required.

Partition Tolerance

Graphs are not very partition tolerant by nature; the entire graph must be available to correctly answer a graph query. The desired level of consistency and availability will determine the degree to which the system can tolerate a network partition. Read-only graph queries can be processed as long as all trunks are known to be available. Write operations may not be allowed until consensus is reached regarding if every RAM Trunk is deemed in a writable state and considered Active on reachable nodes.
This behavior requires:
  • all trunks must be known in a highly available manner
  • nodes must heartbeat on a regular basis in a manner that enables consensus on which nodes own write-able RAM Trunks

raw design notes
Storage
Global Shared Constructs
Cell Format
Query Processing

Last edited Sep 28, 2014 at 11:52 PM by bkjuice, version 6