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

Question

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

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

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

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

问题当然是这样的映射不适合内存。所以我正在寻找一种方法，通过混合磁盘和内存处理来高效地完成这项工作。

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

带有更新插入 (ON CONFLICT UPDATE) 的 postgresql table。结果证明这太慢了。
python 中的内存字典混合体，当它们变得太大时写入 RocksDB or LMDB 键值存储。尽管这些数据库对于此类任务比 postgresql 快得多，但完成时间仍然在几个月左右。

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

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

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

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

Answer 1

正如 Frank Yellin 所观察到的，有一种 one-round MapReduce 算法。映射器使用键 key1,key2 和值 val 生成 key-value 对。 MapReduce 框架通过键（洗牌）对这些对进行分组。 reducer 对值求和。

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

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

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

如果您可以告诉我们输入是如何产生的，以及您打算如何处理输出，我们或许可以为您提供更好的建议。

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

Accumulate the grouped sum of values across trillions of values

python

algorithm

memory

mapreduce

bigdata