使用非常大的字典进行垃圾收集

Question

我有一个非常大的不可变的密钥集，不适合存储在内存中，还有一个更大的引用列表，必须只扫描一次。如何在RAM中完成标记阶段？我确实有一个可能的解决方案，稍后我会写下来作为答案（不想破坏它），但也许还有其他我没有想到的解决方案。

我将试图重申这个问题，使其更“真实”：

你在Facebook工作，你的任务是找出哪些用户从未创建过带有表情符号的帖子。你所拥有的只是活动用户名列表（大约20亿），以及帖子列表（用户名/文本），你必须扫描它们，但只扫描一次。它只包含活动用户（您不需要验证他们）。

此外，您还有一台电脑，内存为2GB（1GB可获得额外积分）。因此，它必须全部在RAM中完成（无需外部排序或按排序顺序读取）。两天之内。

你能做到吗？怎样提示：您可能需要使用一个哈希表，用户名作为键，一位作为值。但是用户名列表不适合存储，所以这不起作用。对于用户ID，它可能会起作用，但你只知道名称。你可以扫描用户名列表几次（可能是40次，但不能更多）。

Answer 1

创建一个最小的完美哈希函数（MPHF）。在每个键1.8位左右（使用RecSplit算法），它使用了大约429 MB。（这里，1 MB是2^20字节，1 GB是2^30字节。）对于每个用户，分配一位作为标记，大约238 MB。所以内存使用量大约是667 MB。然后读取帖子，为每个用户计算哈希，如果需要，设置相关的位。再次读取用户表，计算哈希，检查是否设置了位。

生成MPHF有点棘手，不是因为速度慢（这可能需要大约30分钟的CPU时间），而是因为内存使用。对于1GB或RAM，它需要分段完成。假设我们使用32个大小大致相同的片段，如下所示：

• 循环段ID从0到31

上面的算法读取用户列表32次。如果使用更多的段（例如一百万个），并且每一步读取内存中的尽可能多的段，这个数字可以减少到大约10次。对于较小的段，每个键需要更少的比特来降低一个段内重复的概率。

Answer 2

对键进行散列，对散列进行排序，并以压缩形式存储排序后的散列。

TL； DR

我提出的算法可以看作是类似（更简单）问题解决方案的扩展。

1. 对每个键：应用一个散列函数，将键映射到范围[0... h]内的整数。从h=2*number_of_keys开始似乎相当好。
2. 用这些散列填充所有可用内存。
3. 排序散列。
4. 如果哈希值是唯一的，将其写入唯一哈希列表；否则删除它的所有副本并将其写入重复列表。这两个列表都应该保持压缩形式：作为相邻值之间的差异，用最佳熵编码器（如算术编码器、范围编码器或ANS编码器）进行压缩。如果唯一哈希列表不是空的，将其与排序哈希合并；合并时可能会发现其他重复。如果重复列表不是空的，将新的重复合并到其中。
5. 当有任何未处理的密钥时，重复步骤1...4。
6. 在执行步骤1...5时，多读几次键。但是忽略所有不在前一遍重复列表中的键。对于每一遍，使用不同的哈希函数（除了与前一遍重复列表匹配之外，这意味着对于两个不同的哈希函数，我们需要对哈希进行两次排序）。
7. 再次读取键，将剩余的重复哈希列表转换为普通键列表。排序。
8. 分配20亿位的数组。
9. 使用所有未占用的内存为每个散列压缩列表构建一个索引。这可以是一个trie或一个排序列表。索引的每个条目应该包含熵解码器的“状态”，允许从一开始就避免解码压缩流。
10. 处理帖子列表并更新20亿位的数组。
11. 再次读取密钥，将散列转换回密钥。

虽然使用值h=2*number_的_键似乎相当不错，但我们可以尝试改变它以优化空间需求。（设置太高会降低压缩比，设置太低会导致重复太多）。

这种方法不能保证结果：有可能发明10个坏的哈希函数，这样每个键在每一次传递中都会被复制。但是很有可能它会成功，并且很可能需要大约1GB的内存（因为大多数压缩的整数值都在[1...8]的范围内，所以每个键在压缩流中会产生大约2...3位）。

为了精确估计空间需求，我们可能需要（复杂？）数学证明或算法的完整实现（也相当复杂）。但是要获得粗略的估计，我们可以使用步骤1...4的部分实现。在Ideone上看到它。它使用了名为FSE的ANS编码器的变体（摘自这里：https://github.com/Cyan4973/FiniteStateEntropy）和简单的哈希函数实现（摘自这里：https://gist.github.com/badboy/6267743）。以下是结果：

Key list loads allowed:     10           20
Optimal h/n:                 2.1          1.2
Bits per key:                2.98         2.62
Compressed MB:             710.851      625.096
Uncompressed MB:            40.474        3.325
Bitmap MB:                 238.419      238.419
MB used:                   989.744      866.839
Index entries:           1'122'520    5'149'840
Indexed fragment size:    1781.71       388.361

由于最初的操作限制为10个键扫描，散列范围的最佳值仅略高于我的猜测（2.1），这个参数非常方便，因为它允许使用32位散列（而不是64位散列）。所需的内存略小于1GB，这允许使用相当大的索引（因此第10步不会很慢）。这里有一个小问题：这些结果显示了最终消耗了多少内存，但是在这个特定的情况下（10个键扫描），我们在执行第二次扫描时暂时需要超过1GB的内存。如果我们删除第一次通过的结果（唯一哈希）并在稍后与步骤7一起重新计算，这可能是固定的。

由于没有20个键扫描的严格限制，散列范围的最佳值为1.2，这意味着算法需要更少的内存，并为索引留出更多空间（因此步骤10将几乎快5倍）。

放宽对40键扫描的限制不会带来任何进一步的改进。

Answer 3

听起来像是我10年前解决的问题。

第一阶段：沟渠GC。小对象（几个字节）的GC开销可能超过100%。

第二阶段：设计一个合适的用户名压缩方案。英语每个字符大约有3位。即使允许更多字符，平均比特数也不会快速增加。

第三阶段：在内存中创建用户名词典。使用每个用户名的16位前缀来选择正确的子字典。读入所有用户名，最初仅按此前缀对它们进行排序。然后依次对每本字典进行排序。如问题中所述，为“used emoji”结果为每个用户名分配一个额外的位。

现在的问题是I/O受限的，因为计算是令人尴尬的并行。最长的阶段将是阅读所有帖子（这将是很多TB）。

请注意，在这个设置中，您没有使用像String这样的奇特数据类型。字典是连续的内存块。

不过，如果最后期限是两天，我会放弃一些这种幻想。用于读取文本的I/O限制非常严重，用户数据库的创建可能会超过16GB。是的，可以换成磁盘。一次性的大不了。