its*_*dok 5 on-disk data-structures
我有大约5亿个128位整数,每年增加大约1亿个.什么都没有删除.这些数字的分布均匀,按比例和时间分布.
基本上,我只需要一个添加操作,它也会返回DB中是否已存在该数字.此外,我不想为这个系统使用太多RAM,所以只是将所有内容存储在内存中并不是我想要的.
到目前为止,我们一直在MySQL上使用几个MyISAM表,使用两个bigint作为主键.这给了我们好的表现,但我怀疑它不适合这项工作.在拆分表之前我们遇到了一些性能问题,而且我们在停电时已经损坏了.此外,DB为我们提供了许多我们不需要的功能.
我在Linux上使用Python,但我愿意接受建议.
更新:马塞洛的评论提到布卢姆过滤器,这似乎对我很有希望.由于我正在使用哈希,我已经放弃了完全准确性,所以这可能是一个很好的精度/性能折衷.
将每个整数插入通过计算整数的n位哈希值选择的 2 n个SQLite 数据库池之一（2 8可能是一个不错的数字）。将一个表的一列设置为主键，这样尝试插入现有数字就会失败。
假设整数已经足够随机，您可能可以选择最低有效字节作为“散列”。
编辑：我已经做了一些测试。我在大约两个小时内插入了 2500 万个条目，但在此过程中它占用了超过 1 GB 的空间。这是通过生成随机数并将其分配给 32 个子进程来完成的，每个子进程控制一个 SQLite 数据库，并每 100,000 次插入提交一次。目前插入的速度约为 1350 Hz，远远超出了您的问题所需的 3 Hz，但整个数据库仍然适合缓存（我有 8 GB RAM）。除非接近您当前的数据库大小，否则我不会知道稳态性能。到那时，每次插入都会引起至少四次磁盘头移动（读写索引和表，可能更多是为了深入到 B+ 树），然后你就会知道你到底有多痛苦。
我开始认为这是一个真正有趣的问题，可以通过定制的解决方案更有效地解决。然而，我怀疑需要付出一定的努力才能显着优于数据库引擎。