Concurrency

Lock-free data structures

• Key idea: use primitive atomic operation instead of lock
• Data structures:
  • Stack
    • Example: Push = node→next = head; head = node
      • Key: CAS
        • Try to first update the node→next as current head
        • If head is still same as node→next (compare), update head to point to node
  • Linked list
    • NOTE: it is a better example, since locking the entire list during traversal is expensive, while locking all nodes individually are too much overhead
    • https://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf

Applications

内存数据库领域用的很多

1. MemSQL 用 Lock Free Skip List 做索引：The Story Behind MemSQL’s Skiplist Indexes
2. SQL SERVER 内存存储引擎 Hekaton 用 Lock Free Bw-Tree 做索引：https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/bw-tree-icde2013-final.pdf...
3. HyPer 的并行查询引擎大量的应用了 Lock Free 数据结构，如使用 Lock Free 的 Hash Table 实现 Hash Join：http://db.in.tum.de/~leis/papers/morsels.pdf...
4. DB2 BLU 的并行查询引擎：http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p773-barber.pdf...
5. OceanBase 也大量的使用 Lock Free

为什么传统数据库不用呢？因为瓶颈在磁盘，Lock Free 增加的性能几乎可以忽略不计，但是在内存数据库中是可以大幅度提高性能的。