java - 内存高效的分布式方法来确定唯一值？

Question

问题

我正在尝试对非常大的原始非规范化 CSV 表中的列进行规范化。列值是短字符串(10-100 字节)。我正在努力寻找比我目前的方法更快的解决方案。

示例

输入.csv

john,london
jean,paris
bill,london

转换为以下文件:

输入.标准化.csv

1,1
2,2
3,1

输入.col1.csv

1,john
2,jean
3,bill

输入.col2.csv

1,london
2,paris

我目前有两种方法来规范化这些数据集。

当前方法

在内存中单次传递

单一传递方法，将列 values -> normalized_id 值存储在关联数组中(在我的例子中是 Java HashMap)。这会在某个时候耗尽内存，但是当它可以将所有内容存储在内存中时速度很快。降低内存使用量的一种简单方法是每列执行一次。

多遍排序

基于排序的多 channel 方法。列值附加它们的行号，然后进行排序(以内存高效的合并排序方式)。例如，列值 london,paris,london 附有行号，然后进行排序:london;1,london;3,paris;2。

我现在可以拥有一个“唯一值计数器”，只需将每个值与之前的值进行比较(例如 London == London，因此不要增加唯一值计数器)。最后，我有一对 unique_id,linenum 对，我可以按行号排序以重建规范化列。然后可以一次合并列。

这种方法可以在非常有限的内存中完成，具体取决于所应用的排序算法的内存使用情况。好消息是这种方法很容易在 hadoop 之类的东西中实现，利用它的分布式排序步骤。

我的问题

与单遍方法(或每列单遍方法)相比，多遍方法慢得令人痛苦。所以我想知道优化该方法的最佳方法是什么，或者是否有人可以建议替代方法？

我想我正在寻找某种(分布式)键值存储，它的内存使用率尽可能低。

在我看来，使用 Trove 将是使用 Java HashMap 的一种很好、简单的替代方法，但我想要一些可以为我处理 key 分配的东西。

Redis 可能是一个不错的选择，但我对它的每个键值对的内存使用情况并不满意。

Answer 1

您知道输入列的大致数量级吗？如果是这样，您不需要保留原始输入文件顺序吗？然后您可以使用足够大的哈希函数来避免输入键的冲突。

如果您坚持要有一个密集的连续键空间，那么您已经涵盖了两个主要选择。您当然可以尝试使用 Redis，我已经看到它用于数以千万计的键值对，但它可能不会超出此范围。你也可以试试 memcached。它的内存开销可能比 Redis 略低，但我肯定会尝试两者，因为它们在这种特定用途上非常相似。您实际上不需要 Redis 的高级数据结构。

如果您需要的键值比单台机器内存中存储的更多，您可以回退到 BDB 或 Kyoto cabinet 之类的东西，但最终这一步将成为处理的瓶颈。另一个危险信号是，如果您可以在一台机器上的内存中容纳整个列，那么您为什么要使用 Hadoop？

老实说，依赖密集有序的主键是在 NoSQL 数据库中首先被抛弃的事情之一，因为它假设有一个协调的主控。如果您甚至可以允许一些间隙，那么您可以做类似于 vector 时钟的事情。

最后一个替代方案是使用 map-reduce 作业来按键收集所有重复值，然后使用一些外部事务数据库计数器分配一个唯一值。然而，map-reduce 作业本质上是一种多遍方法，因此它可能更糟。主要优点是您将获得一些 IO 并行性。 (虽然id赋值仍然是一个串行事务。)