Skip to content

Instantly share code, notes, and snippets.

Created March 16, 2010 05:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save anonymous/333664 to your computer and use it in GitHub Desktop.
Save anonymous/333664 to your computer and use it in GitHub Desktop.
Here's a first pass at some kind of spec. These aren't meant to be final - just posting for discussion. I anticipate that after we (developers) come to some kind of conclusion here we will want to run this by the user list to see if we're missing use cases, etc.
h1. Definitions
For the sake of common vocabulary, we define the following terms:
*ATOMICITY*: an operation is atomic if it either completes entirely or not at all
*CONSISTENCY*: all actions cause the table to transition from one valid state directly to another (eg a row will not disappear during an update,e tc)
*ISOLATION*: an operation is isolated if it appears to complete independently of any other concurrent transaction
*DURABILITY*: any update that reports "successful" to the client will not be lost
*VISIBILITY*: an update is considered visible if any subsequent read will see the update as having been committed
h1. APIs to consider
* Read APIs
** get
** scan
* Write APIs
** put
** delete
* Combination (read-modify-write) APIs
** incrementColumnValue
** compareAndSet
h1. Guarantees Provided
h2. Atomicity
# All mutations are atomic within a row. Any put will either wholely succeed or wholely fail.
## An operation that returns a "success" code has completely succeeded.
## An operation that returns a "failure" code has completely failed.
## An operation that times out may have succeeded and may have failed. However, it will not have partially succeeded or failed.
# This is true even if the mutation crosses multiple column families within a row.
# APIs that mutate several rows will _not_ be atomic across the multiple rows. For example, a multiput that operates on rows 'a','b', and 'c' may return having mutated some but not all of the rows. XXX: will they return failure or success or some mixed response here?
# The compareAndSet API happens atomically as is typically understood by this operation.
h2. Consistency and Isolation
# All rows returned via any access API will consist of a complete row that existed at some point in the table's history.
# This is true across column families - i.e a get of a full row that occurs concurrent with some mutations 1,2,3,4,5 will return a complete row that existed at some point in time between mutation i and i+1 for some i between 1 and 5.
h3. Consistency of Scans
A scan is *not* a consistent view of a table. Scans do *not* exhibit _snapshot isolation_.
Rather, scans have the following properties:
# Any row returned by the scan will be a consistent view (i.e. that version of the complete row existed at some point in time)
# A scan will always reflect a version _at least as new as_ the beginning of the scan. This satisfies the visibility guarantees enumerated below.
## For example, if client A writes data X and then communicates via a side channel to client B, any scans started by client B will contain data at least as new as X.
## Scans may include data that is _newer_ than the start of the scan.
## Another way of stating this is that a scan must reflect all mutations committed prior to the construction of the scanner, and _may_ reflect some mutations committed subsequent to the construction of the scanner.
Those familiar with relational databases will recognize this isolation level as "read committed".
XXX: Ryan has mentioned the model of "scans will always get the most up-to-date version of a row when beginning a new row". Do we want to guarantee this or just leave it at "some version of the row at least as new as what existed at scan start"?
h2. Visibility
# When a client receives a "success" response for any mutation, that mutation is immediately visible to both that client and any client with whom it later communicates through side channels.
# A row will never exhibit so-called "time-travel" properties. That is to say, if a series of mutations moves a row sequentially through a series of states, any sequence of concurrent reads will return a subsequence of those states.
## For example, if a row's cells are mutated using the "incrementColumnValue" API, a client will never see the value of any cell decrease.
## This is true regardless of which read API is used to read back the mutation.
# Any version of a cell that has been returned to a read operation is guaranteed to be durably stored.
h2. Durability
# All visible data is also durable data. That is to say, a read will never return data that is not durably on disk.
# Any operation that returns a "success" code (eg does not throw an exception) will be made durable.
# Any operation that returns a "failure" code will not be made durable (subject to the Atomicity guarantees above)
# All reasonable failure scenarios will not affect any of the guarantees of this document.
XXX: should expand this to include the concept of tunable durability windows (this also impacts visibility since you can experience time travel during failure if some updates arent durable)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment