1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

//  txn algo:
//      read
//          get ts + id for each write with single fetch_add
//          version search
//              early abort if r.wts > t.ts
//      validation
//          if recent aborts
//              sort write set by contention
//              precheck version consistency
//          install pending versions
//              create tx pointing to writeset
//              add delta to index
//          update read ts
//          check version consistency
//      write phase
//          persist
//              for (Wts, Version) in !ts:
//                  @k <- (Wts, Version)
//              delete !ts from sled
//          commit in mem chain
//      maintenance
//          schedule gc
//              put (@k, wts, version) for last good version into epoch dropper
//
//      recovery algo:
//          bump stored ts by TS_SAFETY_BUFFER
//          for (ts, writeset) in ts range:
//              for Wts, Version in writeset:
//                  filter @k, remove (Wts, Version)
//              delete ts from sled
//
//      phantom handling
//          inserts
//              install pending has old version point to None
//          deletes
//              install pending has new version point to None
extern crate serde;
extern crate bincode;
extern crate sled;

use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering::SeqCst;

use bincode::{Infinite, deserialize, serialize};

mod tx;
mod db;
mod mvcc;

pub use tx::{Error, Tx, TxResult};
pub use db::Db;
use mvcc::{Chain, MemRecord, Mvcc, Status};

type Version = u64;
type Ts = u64;
type Key = Vec<u8>;
type Value = Vec<u8>;
type Delta = Vec<u8>;

// a pending ptr (prefixed by !) points to keys in-flight
type WriteSet = Vec<Key>;

// a key (prefixed by @) points to versions
type Versions = Vec<(Ts, Version)>;

#[derive(Debug, PartialEq)]
pub enum TxRet {
    Committed,
    Conflict,
    PredicateFailure,
}

fn bytes_to_ts(bytes: &[u8]) -> Ts {
    let mut ts_arr = [0; 8];
    ts_arr.copy_from_slice(&bytes[0..8]);
    unsafe { std::mem::transmute(ts_arr) }
}

fn ts_to_bytes(ts: Ts) -> Vec<u8> {
    let bytes: [u8; 8] = unsafe { std::mem::transmute(ts) };
    bytes.to_vec()
}

fn key_safety_pad(key: &Key) -> Key {
    let mut new = Vec::with_capacity(key.len() + 1);
    unsafe {
        new.set_len(key.len() + 1);
    }
    new[0] = b'@';
    (new[1..1 + key.len()]).copy_from_slice(&*key);
    new
}

#[test]
fn it_works() {
    let conf = sled::ConfigBuilder::new().temporary(true).build();
    let db = Db::start(conf).unwrap();

    let mut tx = db.tx();
    tx.set(b"cats".to_vec(), Some(b"meow".to_vec()));
    tx.set(b"dogs".to_vec(), Some(b"woof".to_vec()));
    assert_eq!(tx.execute(), Ok(()));

    let mut tx = db.tx();
    tx.predicate(b"cats".to_vec(), |_k, v| *v == Some(b"meow".to_vec()));
    tx.predicate(b"dogs".to_vec(), |_k, v| *v == Some(b"woof".to_vec()));
    tx.set(b"cats".to_vec(), Some(b"woof".to_vec()));
    tx.set(b"dogs".to_vec(), Some(b"meow".to_vec()));
    //tx.get(b"dogs".to_vec());
    assert_eq!(tx.execute(), Ok(()));

    let mut tx = db.tx();
    tx.predicate(b"cats".to_vec(), |_k, v| *v == Some(b"meow".to_vec()));
    assert_eq!(tx.execute(), Err(Error::PredicateFailure));
}