RFC: transactions! snapshots! merge operators!

[spacejam]

Here are some sketches for upcoming features I'd like to implement after the 0.15 release bakes in the reliability of the core system a bit more. If you have an opinion on the API for any of these, please comment! This is just a (not runnable, pseudocode) sketch I wrote up while thinking about these features. I will edit this as ideas solidify.

Transactions

enum TxResult {
  Ok,
  PredicateFailure,
  Abort,
}

impl Tx {
    // Predicates must all return true if a transaction is to succeed.
    fn predicate(&mut self, k: Key, f: F) where F: Fn(&Key, Option<&Value>) -> bool;

    // Retries the transaction in a loop until it succeeds or reaches PredicateFailure. 
    fn retry_on_abort(&mut self, bool);

    fn set(&mut self, k: Key, v: Value);
    fn del(&mut self, k: &Key);

    // runs the transaction
    fn execute(self) -> TxResult
}

let mut tx = tree.tx();
tx.predicate("cats", |k, v| v == Some(b"meow"));
tx.predicate("dogs", |k, v| v == Some(b"woof"));
tx.set("cats", "woof");
tx.set("dogs", "meow");

match tx.execute() {
  TxResult::Committed(reads) => assert!(reads.is_empty()),
  TxResult::PredicateFailure(reads) => println!("tx failed because either cats \
                                     is not meow, or dogs is not woof \
                                     in {:?}", reads),
  TxResult::Abort => println!("another transaction operated on state concurrently, \
                                                we may want to retry");
}

After the 0.15 release bakes in the stability of the pagecache, 0.16 will be the "feature release" which includes transactions, snapshots and merge operators! A goal is to implement these in a way that minimizes the performance impact to workloads that do not care about these features. Performance is not the primary goal of these features, however, and for long-running snapshot cleanup, we may encounter some latency hiccups, although these may be hidden by punting cleanup to a threadpool.

Basic idea behind transactions:

• all updates (set, del, cas, merge) include their original LSN
• when executing, we check into an epoch, then generate a timestamp, then bound all reads of the transaction by this timestamp
• any time an item is deleted, it uses the epoch-dropper mechanism to delay removal from shared state until all threads that checked in early enough to witness it have checked out of their epochs.
• mutations in transactions only become visible to others after their transactions commit
• transactions may cause each other to fail, resulting in conflicts. They first read all data items to be read or written, then set each data item into a pending state that refers to a transaction object, then they set the transaction object to the completed state, then clean up the pending state. Any reads that encounter a pending object try to set their transaction object to the failed state.

Snapshots

These use the same epoch & lsn-bounding technique as shown above to ensure old state doesn't get dropped out before a thread is done with it. Supports long-running scan operations, but they may hiccup when they complete due to cleaning up all of the garbage that has amassed since they began.

Merge Operators

type MergeOperator = Fn(key: &Key, last_value: Option<&Value>, new_merges: Vec<&Value>) -> Option<Value>;

fn concat_merge(key: &Key, existing_val: Option<&Value>, operands: Vec<&Value>)  -> Option<Value> {
    let mut result: Vec<u8> = Vec::with_capacity(operands.len());
    existing_val.map(|v| {
        result.extend_from_slice(&*v);
    });           
    for op in operands {    
        result.extend_from_slice(&*op); 
    } 
    // returning None deletes the value
    Some(result)
}

config.set_merge_operator(concat_merge);

let tree == config.tree();

tree.merge("cats", "m");
tree.merge("cats", "e");
tree.merge("cats", "o");
tree.merge("cats", "w");

assert_eq!(tree.get("cats"), Some("meow"));

// set and cas clear previous state
tree.set("cats", "woof");
assert_eq!(tree.get("cats"), Some("woof"));

[spacejam]

@rigelrozanski suggested enabling the builder pattern for describing transactions

[spacejam]

merge operators have been merged! present in sled 0.15.11 and up.

[spacejam]

to keep things simple, the initial transactional engine will only be optimistic and serializable.

[spacejam]

0.16 is going to be about performance instead of features, and it has a new zero-copy readpath. Transactions aren't done yet, so I'm putting them off until 0.17 so we can break the API with a release that adds major improvements asap.

[ferrouswheel]

Would it make sense to allow people to specify either a error message or label for predicates?

I can imagine that if multiple predicates exist, trying to debug which one failed could be difficult otherwise.

[spacejam]

@ferrouswheel Yeah, that might be a nice thing to know. In order to abort as quickly as possible, we will probably end a transaction immediately when a single predicate is found to not match, so just the first non-matching predicate can be returned. This is cheap now that zero-copy reads are possible, since we don't have to copy the failed value, and we can just take the key from the provided vec.

[spacejam]

moving to implementation in #382