AberSheeran
Aber Sheeran

如何索引十亿哈希数据

起笔自
所属文集: 杂记
共计 1318 个字符
落笔于

入职安天的当天,屁股刚坐稳就给了我一个需求。索引、压缩一个预计会达到十亿数据量的哈希-病毒名的数据对。这个数据对以文本形式存储会达到 50 GB,而给我的限制是要求在 11GB 之内,并且要求能快速查询到指定哈希值对应的病毒名,内存要尽可能的小。并且有更新的需求,单次更新的数据量可能会有几百万。

一开始我是懵逼的,因为我从来没做过存储。在经历了几天的搜索、学习相关资料和了解业务场景之后,我才明白其实这个需求并没有那么复杂。

过滤

业务中存在大量的无效查询,只有很少的数据会存在于数据集合里。在这一层,可以考虑使用布隆过滤器来处理。根据布隆过滤器的错误率公式,可以通过数据量与错误率来计算出布隆过滤器的最优大小和最优哈希函数数量。以下是一个不依赖第三方库的 Python 实现。

索引

对于单次查询,程序动用的磁盘 IO 次数越少越好,并且由于操作系统的页设计,单次 IO 操作控制在 4K 是最赚的。那么为了减少内存的使用,我们需要把全量的数据索引丢进磁盘,将索引的索引放在内存,这样内存占用大约会多出微不足道的几个MB,通过控制每个全量数据索引块的大小在 4K 内,可以得到最后的分割。

接下来我将记录两种全量索引模式,前者是另一个同事的实现,后者是我的实现。

前缀分割

使用前两个十六进制数字作为目录,使用其后的四个十六进制数字对数据进行分割,记录每个分割点的第一个数据在整个文件中的偏移量,这样一来,一次查询只需要读取一次索引,再通过索引得到文件偏移量直接读取指定部分的全部数据到内存里查找即可。

这里利用了哈希值的稀疏性,单次读取数据大概率不会超过 4K。但缺点是更新困难,因为任何一条新数据进来都会导致其后所有的数据的偏移量失效。同事给出的想法是不更新原始文件,而是合并更新数据作为额外的小文件存在。

跳表查询

把全量的有序数据分割到多个文件,每个文件头部使用 4096 个字节记录其文件内所包含的哈希值的跳表,每两条跳表数据之间的数据大小控制在 4K 之内,由于单条数据长度是固定的,所以在这里可以算出 4K 大小之内最大可包含的数据,实际使用时不需要在跳表里记录偏移量,可以通过查询到的数据在跳表中的位置计算出偏移量。在一次查询里,只需要读取一次文件头部的跳表,通过二分搜索可以直接算出数据偏移量,再次读取数据。

这个思路和前面一种思路的区别不大。但由于文件的切割,带来的好处是更新数据的成本较低,每次只需要更改一个几个MB的小文件即可。坏处是在数据较大时小文件较多,比其单一文件存储,会更多的消耗磁盘空间。

事后

最后我花了两个星期的方案还是没用上……原因是之前的方案已经有了实现并且投入到了生产线,而我的方案没有较大的提升,修改现有代码得不偿失。

而我从这事也吸取了一个教训——Python 不适合需要共享一个大数据的服务。因为最终的布隆过滤器要包含十亿数据,占据较大的内存空间。为了充分利用服务器 CPU,Python 这边只能启动多个进程,而Python给的进程之间共享数据的方案使用了大量的进程锁,完全无法充分利用 CPU。真密集型 CPU 计算可以上 C 拓展,但是这种情况,Python 真就没办法。

如果你觉得本文值得,不妨赏杯茶
Django 禁止用户多客户端登录
四行代码实现 Python 管道