Lock striping | My Note

Lock striping

Updated: Oct 26th, 2023

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

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

  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.

Instead of authenticating the giscus application, you can also comment directly on GitHub.

Notes mentioning this note

There are no notes linking to this note.