Kyoto Cabinet/Berkeley DB:哈希表的大小限制

Question

我很难在我的SSD上存储数亿个16/32字节的键/值对和一个哈希数组.

京都内阁:当它工作正常时,它以70000记录/秒的速度插入.一旦下降,它就会下降到10-500记录/秒.使用默认设置,在大约一百万条记录之后发生丢弃.查看文档,这是数组中默认的桶数,因此它是有意义的.我将这个数字增加到了2500万,事实上,它可以正常工作,直到大约2500万条记录.问题是,只要我将桶数推到3000万或以上,插入速率就会从一开始就降低到10-500条记录/秒.Kyoto Cabinet不是为了在创建数据库后增加存储桶数量而设计的,因此我无法插入超过2500万条记录.

1/一旦铲斗数超过25M,为什么KC的插入率会变得非常低？

使用Berkeley DB:我得到的最佳速度略低于KC,接近50000记录/秒,但仍然可以.使用默认设置,就像KC一样,在大约一百万条记录之后,速度会突然下降.我知道BDB旨在逐步扩展其桶数.无论如何,它试图增加初始数量,与HashNumElements和FillFactor一起玩,但是这些尝试都使情况变得更糟.所以我仍然无法使用DBD插入超过1-2百万条记录.我尝试激活非同步事务,尝试不同速率的检查点,增加缓存.什么都没有改善下降.

2/在1-2百万次插入后,什么可能导致BDB的插入率下降？

注意:我正在使用java,当速度下降时,CPU使用率降低到0-30%,而在正常速度下工作时,CPU使用率降低到100%.
注意:停止进程并恢复插入不会改变任何内容.所以我认为这与内存限制或垃圾收集无关.

谢谢.

Answer 1

下面是我如何在 KC 遇到写入限制的情况下设法存储数十亿条记录。

\n\n

经过我的努力，仍然没有解决京都内阁和伯克利数据库的问题。然而，我使用京都橱柜想出了一个有趣的解决方法。

\n\n

我注意到我不能在一个 KC 文件上写入超过 25M 的记录，但是读取没有这样的限制 \xe2\x88\x92 它总是很快，无论数据库的大小如何。我找到的解决方案是为每25M新记录创建一个新的KC文件（新数据库）。这样，读取发生在许多 KC 文件上并且仍然很快，并且写入仅发生在最后创建的文件上并且也很快。唯一剩下的问题是允许更新/删除先前文件中的记录。为此，我复制了 SSTables 方法，即：

\n\n

\n
• 0到N-1文件都是只读的，文件N是读+写的。
\n
• 任何插入/更新/删除都写入文件N中。
\n
• 读取查找文件 N 到 0，并返回最先看到/最后写入的插入/更新/删除。
\n
• 每个文件都附加了布隆过滤器，以避免访问没有所需记录的文件。
\n
• 一旦文件 N 达到 25M 记录，它就会变为只读，并创建文件 N+1。
\n

\n\n

注意事项：

\n\n

\n
• 就像 SSTables 一样，如果执行大量更新/删除，我们可能需要执行压缩。然而与 SSTables 不同的是，这里的压缩不需要重写文件。过时的记录只是从 KC 文件中删除，如果 KC 文件变得非常小，可以删除 \xe2\x88\x92 将记录重新插入文件 N\xe2\x88\x92 中，或者重新打开以进行新插入 \xe2\x88 \x92 假设接下来的文件是紧凑的。
\n
• 删除不会删除记录，而是写入一个特殊值来标识该记录已删除。在压缩过程中，删除的记录会被真正删除。
\n
• 检查记录是否存在通常需要查看数据库。多亏了布隆过滤器，大多数否定答案都可以在没有任何磁盘访问的情况下给出。
\n

\n