Skip to content


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



  1. MemSQL 用 Lock Free Skip List 做索引:The Story Behind MemSQL’s Skiplist Indexes
  2. SQL SERVER 内存存储引擎 Hekaton 用 Lock Free Bw-Tree 做索引:
  3. HyPer 的并行查询引擎大量的应用了 Lock Free 数据结构,如使用 Lock Free 的 Hash Table 实现 Hash Join:
  4. DB2 BLU 的并行查询引擎:
  5. OceanBase 也大量的使用 Lock Free

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