Big InMemory B+Index 中的并发访问
Concurrent Access within a Big InMemory B+Index
我目前正在围绕大内存索引结构（几千兆字节）进行设计。索引实际上是一个 RTree，其中 leafes 是 BTree（不要问）。它支持特殊查询并将其推到逻辑极限。
由于这些节点是唯一的搜索节点，我问自己如何最好地使其并行。
到目前为止我知道了六种解决方案：
计划写入时阻止读取。树完全阻塞，直到最后一次读取完成，然后执行写入，写入后树可以再次用于多次读取。 （读取不需要锁定）。
克隆节点以更改和重用现有节点（包括叶节点）并通过简单地再次停止读取切换并完成在两者之间切换。由于必须更改叶指针，因此叶指针也可能成为它们自己的 collection，从而可以切换修改 atomar，并且可以将更改重做到第二个版本，以避免在每次插入时复制指针。
像双缓冲一样使用索引的独立副本。更新索引的一个副本，切换它。一旦没有人读取旧索引，以相同的方式更改此索引。这样可以在不阻塞现有读取的情况下完成更改。如果另一个插入在合理的时间内命中树，也可以完成这些更改。
使用串行无共享架构，因此每个搜索线程都有自己的副本。由于线程只能在执行一次读取后更改其树，因此这也是无锁且简单的。由于每个工作线程（绑定到某个核心）的读取均匀分布，吞吐量不会受到损害。
为每个即将写入的节点使用写/读锁，并且在写入期间只阻塞一个子树。这将涉及对树的额外操作，因为拆分和合并会向上传播，因此需要重新插入（因为向上扩展锁（parentwise）会引入死锁的机会）。由于如果您的页面大小较大，拆分和合并不会那么频繁，这也是一个好方法。实际上，目前我的 BTree 实现目前使用类似的机制，通过拆分节点并重新插入值，除非不需要拆分（这不是最佳的但更简单）。
为每个节点使用双缓冲区，如数据库的影子缓存，其中每个页面在两个版本之间切换。因此，每次修改一个节点时，都会修改一个副本，一旦发出读取，就会使用旧版本或新版本。每个节点都有一个版本号，并且选择更接近活动版本（最新更改）的版本。要在版本之间切换，只需要对根信息进行原子更改。这样就可以更改和使用树。每次都可以进行此切换，但必须确保在覆盖新版本时没有读取使用旧版本。此方法有可能不干扰缓存局部性以便 link 叶子等。但它也需要两倍的内存量，因为必须存在后台缓冲区，但可以节省分配时间，并且可能有利于高频更改。
考虑到所有这些想法，什么是最好的？我知道这取决于但在野外做了什么？如果有 10 个读取线程（或更多）并且被单个写入操作阻塞，我想这不是我真正想要的。
另外，L3、L2、L1 缓存以及多 CPU 的场景如何？有什么问题吗？双缓冲的美妙之处在于，那些命中旧版本的读取仍有可能使用正确的缓存版本。
创建节点的新副本的版本非常不吸引人。那么，当今数据库环境的野外相遇是什么？
[更新]
通过重读 post，我想知道使用写锁进行拆分和合并是否更适合创建替换节点，因为对于拆分和合并我需要复制大约一半的元素，这些操作非常罕见，因此实际上完全复制一个节点可以通过在 parent 节点中替换该节点来实现，这是一个简单而快速的操作。这样，实际读取的块将非常有限，并且由于我们无论如何都会创建副本，因此只有在替换新节点时才会发生阻塞。由于在这些访问期间叶子可能不会被改变，所以它并不重要，因为信息密度没有改变。但这同样需要对节点的每次访问增加和减少读锁并检查预期的写锁。这一切都是开销，这一切都阻碍了进一步的阅读。
[更新2]
方案七（当前收藏）
目前我们倾向于为内部 (non-leaf) 节点使用双缓冲区，并使用类似于行锁定的东西。
我们的逻辑 table 我们试图使用这些索引结构（这是所有索引所做的）进行组合会导致在这些信息上使用集合代数。我注意到这个集合代数是线性的（O(m+n) 用于交集和并集）并且让我们有机会锁定每个条目作为此类操作的一部分。
通过对内部节点进行双缓冲（这不难实现，成本也不高（大约 <1% 的内存开销）），我们可以在不阻塞过多读取操作的情况下解决问题。
由于我们以某种方式批量修改，因此很少看到给定列被更新，但一旦更新，则需要更多时间，因为对于这个单个条目，这些修改可能会达到数千个。
因此，我们的目标是改变用于简单地与当前正在修改的那些列相交的集合代数。由于一次只修改一列，因此此类操作只会阻塞一次。对于当前阅读它的每个人来说，写操作必须等待。你猜怎么着，一旦写操作等待，它通常会让另一个不忙的列的另一个写操作发生。我们计算出这样一个块的概率非常非常低。所以我们不需要关心。
锁定机制是通过检查写入、检查写入意图、添加读取、再次检查写入并处理读取来完成的。所以没有明确的 object 锁定。我们访问固定的字节区域，如果结构清晰，所有关键的东西都计划转移到 c++ 版本中以使其更快（我们猜是 2 倍，这只需要一个人一到两周的时间来完成，特别是如果你使用 Java 到 C++ 翻译器）。
现在唯一重要的影响可能是缓存问题，因为它会使 L1 缓存失效，也可能使 L2 缓存失效。因此，我们计划在 1 分钟或更多分钟分时内收集对此类 table / 索引的所有修改，以安排到 运行，但要均匀分布，以免使系统出现性能问题。
如果您知道任何对我们有帮助的事情，请继续。
由于没有人回复，我想总结一下我们（我）最终做了什么。该结构现已分离。我们有一个 RTree，它的叶子实际上是表。那些 table 甚至可以是远程的，所以我们有一种分发方式，由于 RMI 和代理，它几乎是透明的。
剩下的就简单了。 RTree 有办法建议 table 分裂，这个分裂又是 table。这种拆分是在一台机器上完成的，如果必须远程则转移到另一台机器上。 Merge 差不多。
此远程也适用于绑定到不同 CPU 的线程以避免缓存问题。
关于内存的修改，我已经说过了。我们复制内部节点并将 table 旋转 90° 并调整代数集算法以有效处理锁定的列。单个 table 的测试很简单，与每列 1000 个条目相比毕竟不是性能问题。死锁也是不可能的，因为一次使用一列，所以每个线程只有一个锁。我们尝试并行处理列，这会增加响应时间。我们还考虑将列绑定到给定的虚拟核心，这样就不会再次锁定，因为列是隔离的，而且修改可以再次序列化。
这样一来，每个 CPU 就可以利用 20 个或更多的内核，还可以避免缓存未命中。
我目前正在围绕大内存索引结构（几千兆字节）进行设计。索引实际上是一个 RTree，其中 leafes 是 BTree（不要问）。它支持特殊查询并将其推到逻辑极限。
由于这些节点是唯一的搜索节点，我问自己如何最好地使其并行。
到目前为止我知道了六种解决方案：
计划写入时阻止读取。树完全阻塞，直到最后一次读取完成，然后执行写入，写入后树可以再次用于多次读取。 （读取不需要锁定）。
克隆节点以更改和重用现有节点（包括叶节点）并通过简单地再次停止读取切换并完成在两者之间切换。由于必须更改叶指针，因此叶指针也可能成为它们自己的 collection，从而可以切换修改 atomar，并且可以将更改重做到第二个版本，以避免在每次插入时复制指针。
像双缓冲一样使用索引的独立副本。更新索引的一个副本，切换它。一旦没有人读取旧索引，以相同的方式更改此索引。这样可以在不阻塞现有读取的情况下完成更改。如果另一个插入在合理的时间内命中树，也可以完成这些更改。
使用串行无共享架构，因此每个搜索线程都有自己的副本。由于线程只能在执行一次读取后更改其树，因此这也是无锁且简单的。由于每个工作线程（绑定到某个核心）的读取均匀分布，吞吐量不会受到损害。
为每个即将写入的节点使用写/读锁，并且在写入期间只阻塞一个子树。这将涉及对树的额外操作，因为拆分和合并会向上传播，因此需要重新插入（因为向上扩展锁（parentwise）会引入死锁的机会）。由于如果您的页面大小较大，拆分和合并不会那么频繁，这也是一个好方法。实际上，目前我的 BTree 实现目前使用类似的机制，通过拆分节点并重新插入值，除非不需要拆分（这不是最佳的但更简单）。
为每个节点使用双缓冲区，如数据库的影子缓存，其中每个页面在两个版本之间切换。因此，每次修改一个节点时，都会修改一个副本，一旦发出读取，就会使用旧版本或新版本。每个节点都有一个版本号，并且选择更接近活动版本（最新更改）的版本。要在版本之间切换，只需要对根信息进行原子更改。这样就可以更改和使用树。每次都可以进行此切换，但必须确保在覆盖新版本时没有读取使用旧版本。此方法有可能不干扰缓存局部性以便 link 叶子等。但它也需要两倍的内存量，因为必须存在后台缓冲区，但可以节省分配时间，并且可能有利于高频更改。
考虑到所有这些想法，什么是最好的？我知道这取决于但在野外做了什么？如果有 10 个读取线程（或更多）并且被单个写入操作阻塞，我想这不是我真正想要的。
另外，L3、L2、L1 缓存以及多 CPU 的场景如何？有什么问题吗？双缓冲的美妙之处在于，那些命中旧版本的读取仍有可能使用正确的缓存版本。
创建节点的新副本的版本非常不吸引人。那么，当今数据库环境的野外相遇是什么？
[更新]
通过重读 post，我想知道使用写锁进行拆分和合并是否更适合创建替换节点，因为对于拆分和合并我需要复制大约一半的元素，这些操作非常罕见，因此实际上完全复制一个节点可以通过在 parent 节点中替换该节点来实现，这是一个简单而快速的操作。这样，实际读取的块将非常有限，并且由于我们无论如何都会创建副本，因此只有在替换新节点时才会发生阻塞。由于在这些访问期间叶子可能不会被改变，所以它并不重要，因为信息密度没有改变。但这同样需要对节点的每次访问增加和减少读锁并检查预期的写锁。这一切都是开销，这一切都阻碍了进一步的阅读。
[更新2]
方案七（当前收藏）
目前我们倾向于为内部 (non-leaf) 节点使用双缓冲区，并使用类似于行锁定的东西。
我们的逻辑 table 我们试图使用这些索引结构（这是所有索引所做的）进行组合会导致在这些信息上使用集合代数。我注意到这个集合代数是线性的（O(m+n) 用于交集和并集）并且让我们有机会锁定每个条目作为此类操作的一部分。
通过对内部节点进行双缓冲（这不难实现，成本也不高（大约 <1% 的内存开销）），我们可以在不阻塞过多读取操作的情况下解决问题。
由于我们以某种方式批量修改，因此很少看到给定列被更新，但一旦更新，则需要更多时间，因为对于这个单个条目，这些修改可能会达到数千个。
因此，我们的目标是改变用于简单地与当前正在修改的那些列相交的集合代数。由于一次只修改一列，因此此类操作只会阻塞一次。对于当前阅读它的每个人来说，写操作必须等待。你猜怎么着，一旦写操作等待，它通常会让另一个不忙的列的另一个写操作发生。我们计算出这样一个块的概率非常非常低。所以我们不需要关心。
锁定机制是通过检查写入、检查写入意图、添加读取、再次检查写入并处理读取来完成的。所以没有明确的 object 锁定。我们访问固定的字节区域，如果结构清晰，所有关键的东西都计划转移到 c++ 版本中以使其更快（我们猜是 2 倍，这只需要一个人一到两周的时间来完成，特别是如果你使用 Java 到 C++ 翻译器）。
现在唯一重要的影响可能是缓存问题，因为它会使 L1 缓存失效，也可能使 L2 缓存失效。因此，我们计划在 1 分钟或更多分钟分时内收集对此类 table / 索引的所有修改，以安排到 运行，但要均匀分布，以免使系统出现性能问题。
如果您知道任何对我们有帮助的事情，请继续。
由于没有人回复，我想总结一下我们（我）最终做了什么。该结构现已分离。我们有一个 RTree，它的叶子实际上是表。那些 table 甚至可以是远程的，所以我们有一种分发方式，由于 RMI 和代理，它几乎是透明的。
剩下的就简单了。 RTree 有办法建议 table 分裂，这个分裂又是 table。这种拆分是在一台机器上完成的，如果必须远程则转移到另一台机器上。 Merge 差不多。
此远程也适用于绑定到不同 CPU 的线程以避免缓存问题。
关于内存的修改，我已经说过了。我们复制内部节点并将 table 旋转 90° 并调整代数集算法以有效处理锁定的列。单个 table 的测试很简单，与每列 1000 个条目相比毕竟不是性能问题。死锁也是不可能的，因为一次使用一列，所以每个线程只有一个锁。我们尝试并行处理列，这会增加响应时间。我们还考虑将列绑定到给定的虚拟核心，这样就不会再次锁定，因为列是隔离的，而且修改可以再次序列化。
这样一来，每个 CPU 就可以利用 20 个或更多的内核，还可以避免缓存未命中。