• Document detailed experiment info like date/time, STO version used, and parameters
• Investigate the performance difference between boosting and STO in vacation
  • e.g. run time breakdown, abort rate, etc.
• Take a look at TGeneric
• More info on the "11%" number
  • without the full opacity check, vacation high contention at 16 threads takes 37.79 seconds to finish, compared to 32.37 seconds (a 14.34% improvement) with hard_check_opacity()
  • abort rate also went down from 21.65% to 16.26% (1869436 hco aborts out of a total of 3055493 hco calls, or 61.2%)

Looks like right now when we dereference an iterator, it gives us the value rather than a std::pair<K, T>?

std::map<int, int> m;
m[1] = 1;
auto it = m.end();
--it;
std::cout << it->first << ", " << it->second << std::endl;

will print 1,1...
So NULL pointer probably doesn't work... we need a sentinel node.

The way constructors/destructors of TestTransaction class works seems very problematic. I've changed the destructor to do nothing (instead of reverting to a "base" transaction) to avoid bugs in many of our unit tests.

Taking a new snapshot involves loading the current global _TID value, set the LSB, and write the resulting value to _GSC (global snapshot counter), all atomically. Since _TID and _GSC span different words, a 16-byte compare-and-swap is probably required. Would also need a struct to enclose _TID and _GSC to make sure they are adjacent to each other.

Can we delete List1? I mean obviously we can. :) So: What are the reasons to NOT delete List1?

I found a couple very serious bugs:

1. RBTreeInternal.hh: In find_any(), we are actually returning the grandparent of the absent key... Took me almost the entire afternoon to figure out why find_any() and insert() returned different parents...
2. RBTree.hh: We forgot to unlock before we abort in find_or_abort()

Fixed in 7944322 (on rbtree_bn)

TODOs:

• Node representation: {std::pair<const K key; T value>; version; rblinks;} (potentially using versioned values with the pair as the value) (@huangyihe)
• Absent reads (@tslilyai)
  • tree version has a special key, added to read set for absent reads
  • inserts/deletes change the tree version
• Add to read/write sets as follows:
  • Sto::item(this, ptr_node).add_read(node->version);
  • Sto::item(this, ptr_node).add_write(node->value);
  • values of read/write sets should be versions
• Garbage collection (rcu) for erases at commit time (@tslilyai)
  • abort upon seeing delete_bit set unless read_my_writes

Rather than a “Transaction&”, Transaction::get_transaction() should return a TransactionProxy, which aborts when out of scope.

A slight refinement on this would let us make nested transactions.

• Combine unlock() and cleanup() methods
  • We currently think this was a bad idea! It's hard to write a true cleanup() when you can't know whether some other part of the data structure has been locked.
• An abort() during the lock() phase doesn't leave the txn system borked
• Check equality of read_version()s when installing a new read version over an item that already has one; otherwise we risk issues if, e.g., a txn checks value equality for read values
  • This is not necessary for opaque reads
  • I think we can't ever check value equality; the predicate system is designed to fix this problem
• Should Sto::check_in_progress() be an assertion?
• New-style opacity check (GP7 or whatever?…)
• Try-lock?
• Vector uses conflictingly-typed keys (Vector* this vs. int), all keys should be same type
• predicate changes
  • check_predicate
• Call cleanup only if has_write

Final version

• Boosting comparison with hash tables—Nate
  • Boosting comparison with red-black trees—lower prio—Nate
  • Relationship between boosting and STM
• Fine-grained locking for red-black trees; red-black tree comparison vs. TL2—lower prio—Yihe
• Checking Silo/Masstree for bugs—Jeevana
• Predicate experiment—Jeevana
• Code cleanup—Eddie
• GV6/7 more scalable opacity check
• Try-lock for deadlock detection
• Avoid commit protocol for read-only transactions
• versioned_value_struct leaks memory
• Predicate recheck if opacity fails!!
• Get rid of code in check_reads()?

Transactional versions

• Opacity relationship with TransactionTid/TVersion
  • Suggest a TVersion type which encapsulates a version number
  • Suggest we override add_read(TVersion) to automatically handle opacity
• How does PriorityQueue::empty_key work? Is that actually a predicate?
• Hate comments like (list.hh) “check_item() is not const, but the way we’re using it is” :(
• Do we need both List and List1?
• GenericSTM is not correct wrt opacity
• Boosting + RBtree
• Terminology: “poisoned” objects (rather than “try-lock”)

Eric Koskinen

• Does boosting have fine-grained or coarse-grained locking?
• Really true that boosting has no STM?
• Boosting code
• Attach our paper
• Do you have a hash table?
• What'd they use for the list in STAMP vacation?
• How'd they boost k-means?

PLDI paper

• What'd they use for the list in STAMP vacation?

1. The concurrent writer check here (commit 116ea7b, RBTree.hh:144) doesn't seem sufficient. Checking Tids stored in versioned_value's themselves probably a better idea?
2. We need to lock around here (commit 116ea7b, RBTree.hh:213); RBTreeInternal::find_any() is not thread-safe. If we are returning a pointer like this then our erase method should never actually "erase" any node -- not even after the transaction commits. Let's do RCU garbage collection instead.

I may be overthinking this but I'm really worried about the following scenario:

txn1 updated key x, not committed yet
txn2 came in, deleted key x, and committed
txn3 came in, re-inserted key x, not committed yet
Back to txn1, read check passed, in install() turning the update to an "insert", only to find out key x already existed in the tree in a phantom state (with insert bit set because txn3 is not committed yet)

Now what should we do... Should we abort the txn1? We already passed read-check so we can't. Should we abort txn3? Ideally we don't want to since it's an insert-only transaction. So both transactions should commit. But how? txn1 cannot lock the node holding key x right now because it may deadlock...

Hi there, I really like this project and am trying to build something on top of it. In particular, I'm interested in the case where the workload has a lot of contention. To achieve this I ran the tpcc benchmark with only 1 warehouse on 24 cores. I found that an assert in the code is not passing. This issue is fully reproducible with the following command line, which is what I am using for compiling and running:

MODE=perf CXX=c++\ -std=gnu++0x make -j dbtest
out-perf.masstree/benchmarks/dbtest --runtime 30 --num-threads 24 --scale-factor 1 --bench tpcc -dmbta --retry-aborted-transactions --verbose

The failed assertion is in tpcc.cc:1838

ALWAYS_ASSERT(c_order_line.n >= 5 && c_order_line.n <= 15);

The same command line runs fine with the stock Silo. Thanks!

Things like this look like race conditions to me...