Lock striping

这是一种细粒度锁的技巧。

在实现并发哈希表的时候，我们可以有两种方式实现并发：

  1. 整个哈希表使用一个大锁，这种 粗粒度的同步方式（coarse-grained synchronization）使得对哈希表的更新是串行的，但其锁的使用几乎没有内存空间上的开销。
  2. 哈希表中的每一个桶各自使用一个锁，这样的细粒度的同步方式又会占用大量内存。

Lock striping 是上面两种方法的中间态，其可以把哈希表中的桶分成N个区域，每个区域用一把锁，区域与区域之间用不同的锁，这样子能够达成这样的目的：

  1. 相对于粗粒度的同步方式，该方式的并行度从1提升至N
  2. 相对于每个桶一个锁的做法，这种方式将内存开销缩小到原来的 1/N

提到具体的实现方式，可以使用key的哈希值进行分区

一些文献

MemC3 [1] 用了这种技巧

参考资料

  1. https://www.baeldung.com/java-lock-stripping
  2. https://www.geeksforgeeks.org/what-is-lock-striping-in-java-concurrency/
  3. https://stackoverflow.com/questions/16151606/need-simple-explanation-how-lock-striping-works-with-concurrenthashmap
  4. M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008.
[1]
B. Fan, D. G. Andersen, and M. Kaminsky, “MemC3: compact and concurrent MemCache with dumber caching and smarter hashing,” in Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation, USA, 2013, pp. 371–384.

提到本笔记的相关内容