了解并发 HashMap 实现的缓存行失效和条带锁
Understanding Cache line invalidation and striped locks for Concurrent HashMap Implementation
If we put the striped locks very close to each other in memory for a concurrent hashmap, the cache line size can affect performance because we would have to invalidate caches unnecessarily. If you add padding to the array of striped locks, it will improve performance.
谁能解释一下？
先从非并发hashmap入手，基本原理是这样的：
- 为键和值建立索引结构（通常是一个数组或一组数组）。
- 获取密钥的哈希值。
- 将其缩小到数组的大小以内。 （Modulo 做这个很简单，所以如果哈希值是 123439281 并且有 31 个可用槽，那么我们使用
123439281 % 31 即 9 并将其用作我们的索引）。
- 查看那里是否有密钥，如果有，是否匹配（等于）。
- 存储密钥（如果是新密钥）和值。
可以使用相同的方法来查找给定键的值（或查找存在 none）。
当然，如果在同一个插槽中有一个键与您所关心的键不相等，那么上述方法就不起作用了，并且有不同的方法来处理这个问题，主要是继续寻找在不同的插槽中，直到一个空闲，或者让插槽实际上充当一个等索引对的链表。这个我就不细说了。
如果你正在寻找其他插槽，一旦你填充了数组它就不会工作（并且在那之前会很慢）并且如果你使用链表来处理冲突你会很慢如果您在同一索引处有许多键（随着情况变得更糟，您想要的 O(1) 变得越来越接近 O(n) ）。无论哪种方式，您都需要一种机制来在存储量太大时调整内部存储的大小。
好的。这是对哈希图的非常高级的描述。如果我们想让它成为线程安全的怎么办？
默认情况下它不是线程安全的，例如两个不同的线程写入不同的键，其哈希模向下为相同的值，那么一个线程可能会踩到另一个。
使 hashmap 线程安全的最简单方法是简单地拥有一个我们在所有操作上使用的锁。这意味着每个线程都会等待每个其他线程，因此它不会有很好的并发行为。通过一些巧妙的结构，我们可以拥有多个读取线程或一个写入线程（但不是两者）并不难，但这仍然不是很好。
可以创建安全并发的 hashmap 而根本不使用锁（参见 http://www.communicraft.com/blog/details/a-lock-free-dictionary for a description of one I wrote in C#, or http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable Cliff Click Java 中的一个，我在我的 C# 版本中使用了他的基本方法）。
但另一种方法是条带锁。
因为映射的基础是键值对数组（可能是哈希码的缓存副本）或它们的一组数组，并且因为让两个线程写入 and/or 一次读取数组的不同部分（有注意事项，但我暂时忽略它们）唯一的问题是当两个线程需要相同的插槽时，或者需要调整大小时。
因此不同的槽可以有不同的锁，然后只有在同一个槽上运行的线程才需要相互等待。
仍然存在调整大小的问题，但这不是无法克服的；如果您需要调整大小获取每个锁（按设定顺序，这样您就可以防止死锁发生）然后进行调整大小，首先检查没有其他线程在此期间进行相同的调整大小。
但是，如果您有一个包含 10,000 个槽的哈希图，这将意味着 10,000 个锁定对象。这会占用大量内存，而且调整大小意味着获得这 10,000 个锁中的每一个。
条带锁介于单锁方法和每个槽锁方法之间。有一定数量的锁数组，比如 16 作为一个很好的（二进制）轮数。当您需要对某个插槽进行操作时，获取锁号slotIndex % 16，然后进行您的操作。现在，虽然线程可能仍然会阻塞在对完全不同的插槽（插槽 5 和插槽 21 具有相同的锁）进行操作的线程上，但它们仍然可以同时执行许多其他操作，因此它是两个极端之间的中间地带。
这就是条带锁定在高层次上的工作方式。
现在，现代内存访问是不统一的，因为在 CPU.这种缓存有好有坏。
显然利大于弊，否则芯片制造商不会使用它。如果你访问一块内存，然后访问离它很近的一块内存，第二次访问很可能会非常快，因为它在第一次读取时已经加载到缓存中。写入也得到改善。
一段给定的代码很可能想要在彼此靠近的内存块上执行多个操作（例如，读取同一对象中的两个字段，或一个方法中的两个局部变量），这已经很自然了，这这就是为什么这种缓存首先起作用的原因。程序员进一步努力在设计代码时尽可能多地利用这一事实，哈希图等集合就是一个典型的例子。例如。我们可能在同一个数组中存储了密钥和存储的散列，这样读取一个就会将另一个带到缓存中以便快速读取，等等。
尽管有时此缓存会产生负面影响。特别是如果两个线程要同时处理彼此靠近的内存位。
这并不经常出现，因为线程最常处理它们自己的堆栈或它们自己的堆栈指向的堆内存位，并且只是偶尔处理其他线程可见的堆内存。这本身就是为什么 CPU 缓存通常是性能的一大胜利的重要原因。
但是，并发散列图的使用本质上是多个线程命中相邻内存块的情况。
CPU缓存在"cache lines"的基础上工作。这些是从 RAM 加载到缓存中，或作为一个单元从缓存写入 RAM 的代码块。 （同样，虽然我们即将讨论这是一件坏事的情况，但大多数时候这是一个有效的模型）。
现在，考虑具有 64 字节高速缓存行的 64 位处理器。每个指向对象的指针或引用都将占用 8 个字节。如果一段代码试图访问这样的引用，则意味着将 64 个字节加载到缓存中，然后由 CPU 处理其中的 8 个字节。如果 CPU 写入该内存，那么缓存中的这 8 个字节将被更改，并将缓存写回 RAM。如前所述，这通常很好，因为我们也希望对附近的其他 RAM 位执行相同操作的可能性很高，因此在同一缓存行中。
但是如果另一个线程想要访问同一个内存块怎么办？
如果 CPU0 去读取与 CPU1 刚刚写入的同一缓存行中的值，它将有一个已失效且必须读取的陈旧缓存行再次。如果 CPU0 试图写入它，它可能不仅需要再次读取它，而且还需要重做给它写入结果的操作。
现在，如果另一个线程想要访问 确切 相同的内存位，即使没有缓存也会发生冲突，所以事情并没有那么多比他们本来更糟（但他们更糟）。但是如果另一个线程要访问附近的内存，它仍然会受到影响。
这显然对我们并发映射的槽不利，但对它的条带锁来说更糟。我们说过我们可能有 16 把锁。使用 64 字节缓存行和 64 位引用，即所有锁的 2 个缓存行。锁与另一个线程想要的锁位于同一高速缓存行中的几率为 50%。对于 128 字节缓存行（Itanium 有）或 32 位引用（所有 32 位代码都使用它们），它是 100%。有很多线程，实际上 100% 您将要等待。如果还有另一个命中，则再次等待。等待。
我们试图阻止线程在同一个锁上等待的尝试变成了它们在同一个缓存行上等待。
更糟的是，使用锁的内核越多，情况就越糟。每个额外的核心都会大致以指数方式降低总吞吐量。 8 个内核的执行时间可能是 1 个内核的 200 多倍！
但是，如果我们用空白 space 填充条纹锁，使每个锁之间有 56 字节的间隙，那么这不会发生；锁都在不同的缓存行上，对相邻锁的操作不再影响它。这会消耗内存，并使正常的读写速度变慢（缓存的要点是它在大多数情况下都会使事情变得更快），但是在预期特别频繁的并发访问且我们不太可能这样做的情况下是合适的想打下一个锁（我们不是，除了调整大小操作）。 （另一个例子是条带化计数器；让不同的线程递增不同的整数，并在您想要计数时对它们求和）。
这个线程命中相邻内存块的问题（称为 "false-sharing" 因为它会对同一内存的共享访问造成性能影响，即使它们实际上访问的是相邻内存而不是同一内存）也会影响 hashmap 本身的内部存储，但影响不大，因为 map 本身可能更大，因此两次访问命中同一缓存行的几率较小。出于同样的原因，在这里使用填充也会更昂贵；更大的填充量可能会很大。
If we put the striped locks very close to each other in memory for a concurrent hashmap, the cache line size can affect performance because we would have to invalidate caches unnecessarily. If you add padding to the array of striped locks, it will improve performance.
谁能解释一下？
先从非并发hashmap入手，基本原理是这样的：
- 为键和值建立索引结构（通常是一个数组或一组数组）。
- 获取密钥的哈希值。
- 将其缩小到数组的大小以内。 （Modulo 做这个很简单，所以如果哈希值是 123439281 并且有 31 个可用槽，那么我们使用
123439281 % 31即9并将其用作我们的索引）。 - 查看那里是否有密钥，如果有，是否匹配（等于）。
- 存储密钥（如果是新密钥）和值。
可以使用相同的方法来查找给定键的值（或查找存在 none）。
当然，如果在同一个插槽中有一个键与您所关心的键不相等，那么上述方法就不起作用了，并且有不同的方法来处理这个问题，主要是继续寻找在不同的插槽中，直到一个空闲，或者让插槽实际上充当一个等索引对的链表。这个我就不细说了。
如果你正在寻找其他插槽，一旦你填充了数组它就不会工作（并且在那之前会很慢）并且如果你使用链表来处理冲突你会很慢如果您在同一索引处有许多键（随着情况变得更糟，您想要的 O(1) 变得越来越接近 O(n) ）。无论哪种方式，您都需要一种机制来在存储量太大时调整内部存储的大小。
好的。这是对哈希图的非常高级的描述。如果我们想让它成为线程安全的怎么办？
默认情况下它不是线程安全的，例如两个不同的线程写入不同的键，其哈希模向下为相同的值，那么一个线程可能会踩到另一个。
使 hashmap 线程安全的最简单方法是简单地拥有一个我们在所有操作上使用的锁。这意味着每个线程都会等待每个其他线程，因此它不会有很好的并发行为。通过一些巧妙的结构，我们可以拥有多个读取线程或一个写入线程（但不是两者）并不难，但这仍然不是很好。
可以创建安全并发的 hashmap 而根本不使用锁（参见 http://www.communicraft.com/blog/details/a-lock-free-dictionary for a description of one I wrote in C#, or http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable Cliff Click Java 中的一个，我在我的 C# 版本中使用了他的基本方法）。
但另一种方法是条带锁。
因为映射的基础是键值对数组（可能是哈希码的缓存副本）或它们的一组数组，并且因为让两个线程写入 and/or 一次读取数组的不同部分（有注意事项，但我暂时忽略它们）唯一的问题是当两个线程需要相同的插槽时，或者需要调整大小时。
因此不同的槽可以有不同的锁，然后只有在同一个槽上运行的线程才需要相互等待。
仍然存在调整大小的问题，但这不是无法克服的；如果您需要调整大小获取每个锁（按设定顺序，这样您就可以防止死锁发生）然后进行调整大小，首先检查没有其他线程在此期间进行相同的调整大小。
但是，如果您有一个包含 10,000 个槽的哈希图，这将意味着 10,000 个锁定对象。这会占用大量内存，而且调整大小意味着获得这 10,000 个锁中的每一个。
条带锁介于单锁方法和每个槽锁方法之间。有一定数量的锁数组，比如 16 作为一个很好的（二进制）轮数。当您需要对某个插槽进行操作时，获取锁号slotIndex % 16，然后进行您的操作。现在，虽然线程可能仍然会阻塞在对完全不同的插槽（插槽 5 和插槽 21 具有相同的锁）进行操作的线程上，但它们仍然可以同时执行许多其他操作，因此它是两个极端之间的中间地带。
这就是条带锁定在高层次上的工作方式。
现在，现代内存访问是不统一的，因为在 CPU.这种缓存有好有坏。
显然利大于弊，否则芯片制造商不会使用它。如果你访问一块内存，然后访问离它很近的一块内存，第二次访问很可能会非常快，因为它在第一次读取时已经加载到缓存中。写入也得到改善。
一段给定的代码很可能想要在彼此靠近的内存块上执行多个操作（例如，读取同一对象中的两个字段，或一个方法中的两个局部变量），这已经很自然了，这这就是为什么这种缓存首先起作用的原因。程序员进一步努力在设计代码时尽可能多地利用这一事实，哈希图等集合就是一个典型的例子。例如。我们可能在同一个数组中存储了密钥和存储的散列，这样读取一个就会将另一个带到缓存中以便快速读取，等等。
尽管有时此缓存会产生负面影响。特别是如果两个线程要同时处理彼此靠近的内存位。
这并不经常出现，因为线程最常处理它们自己的堆栈或它们自己的堆栈指向的堆内存位，并且只是偶尔处理其他线程可见的堆内存。这本身就是为什么 CPU 缓存通常是性能的一大胜利的重要原因。
但是，并发散列图的使用本质上是多个线程命中相邻内存块的情况。
CPU缓存在"cache lines"的基础上工作。这些是从 RAM 加载到缓存中，或作为一个单元从缓存写入 RAM 的代码块。 （同样，虽然我们即将讨论这是一件坏事的情况，但大多数时候这是一个有效的模型）。
现在，考虑具有 64 字节高速缓存行的 64 位处理器。每个指向对象的指针或引用都将占用 8 个字节。如果一段代码试图访问这样的引用，则意味着将 64 个字节加载到缓存中，然后由 CPU 处理其中的 8 个字节。如果 CPU 写入该内存，那么缓存中的这 8 个字节将被更改，并将缓存写回 RAM。如前所述，这通常很好，因为我们也希望对附近的其他 RAM 位执行相同操作的可能性很高，因此在同一缓存行中。
但是如果另一个线程想要访问同一个内存块怎么办？
如果 CPU0 去读取与 CPU1 刚刚写入的同一缓存行中的值，它将有一个已失效且必须读取的陈旧缓存行再次。如果 CPU0 试图写入它，它可能不仅需要再次读取它，而且还需要重做给它写入结果的操作。
现在，如果另一个线程想要访问 确切 相同的内存位，即使没有缓存也会发生冲突，所以事情并没有那么多比他们本来更糟（但他们更糟）。但是如果另一个线程要访问附近的内存，它仍然会受到影响。
这显然对我们并发映射的槽不利，但对它的条带锁来说更糟。我们说过我们可能有 16 把锁。使用 64 字节缓存行和 64 位引用，即所有锁的 2 个缓存行。锁与另一个线程想要的锁位于同一高速缓存行中的几率为 50%。对于 128 字节缓存行（Itanium 有）或 32 位引用（所有 32 位代码都使用它们），它是 100%。有很多线程，实际上 100% 您将要等待。如果还有另一个命中，则再次等待。等待。
我们试图阻止线程在同一个锁上等待的尝试变成了它们在同一个缓存行上等待。
更糟的是，使用锁的内核越多，情况就越糟。每个额外的核心都会大致以指数方式降低总吞吐量。 8 个内核的执行时间可能是 1 个内核的 200 多倍！
但是，如果我们用空白 space 填充条纹锁，使每个锁之间有 56 字节的间隙，那么这不会发生；锁都在不同的缓存行上，对相邻锁的操作不再影响它。这会消耗内存，并使正常的读写速度变慢（缓存的要点是它在大多数情况下都会使事情变得更快），但是在预期特别频繁的并发访问且我们不太可能这样做的情况下是合适的想打下一个锁（我们不是，除了调整大小操作）。 （另一个例子是条带化计数器；让不同的线程递增不同的整数，并在您想要计数时对它们求和）。
这个线程命中相邻内存块的问题（称为 "false-sharing" 因为它会对同一内存的共享访问造成性能影响，即使它们实际上访问的是相邻内存而不是同一内存）也会影响 hashmap 本身的内部存储，但影响不大，因为 map 本身可能更大，因此两次访问命中同一缓存行的几率较小。出于同样的原因，在这里使用填充也会更昂贵；更大的填充量可能会很大。