As a case study, we focus on Memcached [19], a popular in-memory caching layer, and show how our toolbox of techniques can improve Memcached’s performance by 3× and reduce its memory use by 30%.

Most keys are smaller than 32 bytes and most values no more than a few hundred bytes. In particular, there is one common type of request that almost exclusively uses 16 or 21 Byte keys and 2 Byte values.

Our hash table is 4-way set-associative. Without set-associativity, basic cuckoo hashing allows only 50% of the table entries to be occupied before unresolvable collisions occur. It is possible to improve the space utilization to over 90% by using a 4-way (or higher) set associative hash table. 

After checking all 8 candidate slots, a negative Lookup makes 8 × 0.39% = 0.03 pointer deref- erences on average. Because each bucket fits in a CPU cacheline (usually 64-Byte), on average each Lookup makes only 2 parallel cacheline-sized reads for checking the two buckets plus either 0.03 pointer dereferences if the Lookup misses or 1.03 if it hits.

b1 = HASH(x) // based on the entire key
b2 = b1 ⊕ HASH(tag) //based on b1 and tag of x

 more importantly b1 can be computed by the same formula from b2 and tag. This property ensures that to displace a key originally in bucket b—no matter if b is b1 or b2— it is possible to calculate its alternate bucket b′ from bucket index b and the tag stored in bucket b by 
 	b′ = b ⊕ HASH(tag)

To avoid writer/writer deadlocks, it allows only one writer at a time — a tradeoff we accept as our target workloads are read-heavy.

Optimizing for the common case, our approach takes advantage of having a single writer to synchronize Insert and Lookups with low overhead. Instead of locking on buckets, it assigns a version counter for each key, updates its version when displacing this key on Insert, and looks for a version change during Lookup to detect any concurrent displacement.

P1: Avoid unnecessary or unintentional access to common data.  这个基本不用说了，最基本的套路.
P2: Minimize the size and execution time of critical sections. 同上.
P3: Optimize the concurrency control mechanism. 这里的名堂就多了去了。这里还讨论了使用HTM的优化。

This optimization is key to reducing the size of the critical section: While the total number of slots examined is still M, this is work that can be performed without a lock held. With BFS, however, at most five buckets must be examined and modified with the lock actually held, reducing both the duration of the critical section and the number of cache lines dirtied while doing so.

Here we favor spinlocks using compare-and-swap over more general purpose mutexes. A spinlock wastes CPU cycles spinning on the lock while other writers are active, but has low overhead, particularly for uncontended access. Because the operations that our hash tables support are all very short and have low contention, very simple spinlocks are often the best choice.

1. Data conflicts on transactionally accessed addresses;
2. Limited resources for transactional stores;
3. Use of TSX-unfriendly instructions or system calls. such as brk, futex, or mmap. 

void elided_lock_wrapper(lock) {
  xbegin_retry = 0; abort_retry = 0;
  while (xbegin_retry < _MAX_XBEGIN_RETRY) {
    // Start transaction
    if (status=_xbegin() == _XBEGIN_STARTED) {
      // Check lock and put into read-set
      if (lock is free)
        return; //Execute in transaction
      // Abort transaction as lock is busy
      _xabort (_ABORT_LOCK_BUSY);
    }
    // Transaction may not succeed on a retry
    if (!(status & _ABORT_RETRY)) {
      // There is no chance for a retry
      if (abort_retry >= _MAX_ABORT_RETRY)
        break;
      abort_retry ++ ;
    }
    xbegin_retry ++;
  }
  take fallback lock;
}

void elided_unlock_wrapper(lock) {
  if (lock is free)
     _xend(); // Commit transaction 
  else
    unlock lock;
}