累积数万亿个值的分组总和

Question

我有一个数据缩减问题，事实证明该问题很难解决。

本质上，我有一个程序，可以从总共约 6000 万个键的集合中计算键对的增量值（浮点）。该程序将“相对”快速地生成约 53万亿对的值（简单地迭代这些值将需要大约三天的时间）。并不是每对键都会出现，很多对会出现很多次。没有合理的方法可以让这些对按特定顺序出现。我需要的是一种找到为每对键生成的值之和的方法。

对于适合内存的数据来说，这是一个非常简单的问题。在 python 中，它看起来像这样：

from collections import Counter
res = Counter()
for key1,key2,val in data_generator():
    res[(key1,key2)] += val

当然，问题在于这样的映射不适合内存。因此，我正在寻找一种结合磁盘和内存处理来有效地完成此操作的方法。

到目前为止我已经尝试过：

1. 带有 upserts ( ) 的 postgresql 表ON CONFLICT UPDATE。事实证明，这实在是太慢了。
2. Python 内存中字典的混合体，当它们变得太大时写入RocksDB或LMDB键值存储。尽管对于此类任务，这些数据库比 postgresql 快得多，但完成时间仍约为几个月。

在这一点上，我希望有人有更好的方法可供我尝试。有没有办法把这个问题分解成更小的部分？是否有解决此类问题的标准 MapReduce 方法？

任何提示或指示将不胜感激。谢谢！

编辑： 我使用的计算机有 64GB RAM、96 个内核（我的大部分工作都非常可并行）和 TB 级 HDD（以及一些 SSD）存储。

很难估计缩减结果中的密钥对总数，但肯定至少有数千亿。

Answer 1

正如 Frank Yellin 所观察到的，存在一种单轮 MapReduce 算法。key1,key2映射器生成带有 key和 value的键值对val。MapReduce 框架按键（shuffle）对这些对进行分组。减速器对值进行求和。

为了控制内存使用，MapReduce将中间数据写入磁盘。传统上有n文件，所有带有密钥的对都key1,key2转到 file hash((key1,key2)) mod n。这里有一个张力：n应该足够大，以便每个文件都可以由内存中的映射处理，但如果n太大，则文件系统会崩溃。粗略计算表明，n对于您来说，该值可能介于 1e4 和 1e5 之间。希望操作系统将使用 RAM 来缓冲文件写入，但请确保最大化磁盘吞吐量，否则您可能必须自己实现缓冲。（也可能有合适的框架，但您不必为单台机器编写太多代码。）

我同意 user3386109 的观点，您将需要一个非常大的磁盘。如果您可以多次重新生成输入，则可以通过进行 k 次传递（每次仅保存文件的 1/k 部分）来用时间换取空间。

我担心这个 MapReduce 的运行时间相对于平均故障间隔时间来说太大。MapReduce 传统上是为了容错和并行而分布式的。

如果您可以告诉我们有关输入如何产生以及您计划如何处理输出的信息，我们也许可以为您提供更好的建议。