一种基于大数据的常见群组成员统计算法

Question

我需要编写一个程序来计算两个用户在同一组中的次数。用户按用户名提供，组按id提供。例如，对于输入(存储在文本文件中)：

john 32
john 21
jim 21
jim 32
bob 32

我想要结果：

john-jim 2 
john-bob 1
jim-bob 1

这听起来微不足道。但问题是:我有180万个组和30万用户。以及大量的会员资格(我预计每个用户平均至少有50个会员，可能更多)。这意味着需要大量的数据和处理。

我已经写了5个不同的程序来做这件事，没有一个能够减少数据量:作为一个PostgreSQL查询，它太慢了。在Java工作内存中的Map中运行时消耗太多内存(第一个堆空间，在优化后，我得到了罕见的“超出GC开销限制”)。从Java连续写入数据库太慢了(即使使用批处理查询进行了优化)。变得越来越绝望，我尝试了一些更奇特的方法，比如将所有对写入一个数组，然后对它们进行排序(O(n log (N)，然后对它们进行计数。但它仍然有太多的数据存储在内存中。

有没有什么算法可以做到这一点？或者这是不可能的？

Answer 1

RDBMS专门处理排序之类的操作。在DB之外做这件事几乎不会在性能上接近。使用SQL来实现！

这将完成这项工作(在更新中简化)：

SELECT t1.usr || '-' || t2.usr, count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
WHERE  t2.usr > t1.usr   -- prevent dupes and get sorted pair
GROUP  BY t1.usr, t2.usr;

正如您所说的，这可能会产生大量的行，这取决于您有多少重叠。所以这永远不会是快的。

这就引出了一个问题:生成数百万行没有人能处理的行的目的是什么？你确定，这个操作一开始就有意义吗？

为了让它更快，你可以..

• Upgrade! PostgreSQL 8.4 is rather outdated by now.特别是，PostgreSQL 9.2的重点是大数据。你可以期待这样的工作有更好的表现。

没有人应该运行8.4.0。仅出于安全方面的原因，但您也错过了许多bug修复。当前的point-release是8.4.17。我引用链接的网站：

我们始终建议所有用户针对正在使用的任何主要版本运行最新的可用次要版本。

• 使用integer作为用户的代理键，因此只能在usr_grp中处理整数。使表和索引更小，处理速度更快。如果n:m表(usr_grp)的基数比表usr大得多，那么这应该会更快，即使这意味着更多的连接。

​

​

SELECT u1.usr  || '-' || u2.usr, count(*) AS ct
FROM   usr_grp t1
JOIN   usr_grp t2 USING (grp_id) 
JOIN   usr u1 ON t1.usr_id = u1.usr_id
JOIN   usr u2 ON t2.usr_id = u2.usr_id
WHERE  t2.usr_id > t1.usr_id
GROUP  BY u1.usr_id, u2.usr_id;

• 创建一个多列索引(如果您还没有)。

grp_id必须放在第一位。Why does this matter?

​

​

    CREATE INDEX usr_grp_gu_idx ON usr_grp(grp_id, usr_id);

• 会在您的计算机中添加大量的内存，并增加work_mem和shared_buffers.

的设置

测试用例

我用数字@OldCurmudgeon reported作为他的测试用例，并用PostgreSQL创建了一个类似的测试用例。

-> demo.

此公共测试数据库中的~ 250 ms。

结果不是有序的(没有ORDER BY)，因为还没有指定。

与2.5分钟相比，reported below。因数600。

Answer 2

不如让你的文件系统来做吧。

对于每个条目-打开一个以组ID命名的文件，并附加新用户名。最终，每个组都会有一个文件。

您现在拥有-例如：

Group-21.txt
 jim
 john

Group-32.txt
 bob
 jim
 john

现在遍历所有文件，生成其中的每个用户名对(我将对名称进行排序并对其执行标准组合过程)。对于每一对，将"1“附加到具有特定名称的文件。

您现在拥有-例如：

User-jim-john.txt
 11

User-bob-jim.txt
 1

User-bob-john.txt
 1

现在，您有了文件名中的对和文件中的计数(一元，所以您真正需要的是以字节为单位的文件大小)。

尽管第一阶段必须在第二阶段开始之前完成，但几乎所有这些都可以并行完成。为了提高速度-添加内核-购买更快的磁盘。没有内存限制，只有磁盘限制。

补充道：，我刚刚用一个线程对这个算法进行了一些模拟测试

1800个组，300个用户和15000个成员资格都是随机生成的，大约需要2.5分钟。900个组，150个用户和7500个成员花了54秒。

Answer 3

无论解决方案是什么，复杂性都取决于生成的对的数量，而不一定取决于组或人员的数量。对于不同的组大小：

• 有10个成员的组产生C(10,2) = 45对
• 有100个成员的组产生C(100,2) = 4950对
• 有1,000个成员的组，499500对...
• 有10000个成员，单个组将产生近5,000万对！因此，一个单独的组就可以超过其余计算的全部成本。

因此，我的第一个建议是在数据集中剔除非常大的组。如果您不能省略大的组，并且发现它不能放入内存中，或者使用单个线程遍历它将需要很长时间，您可以使用Map-Reduce自动并行化计算，如下所示。如果您从组成员身份开始，例如：

32 -> john, jim, bob
21 -> john, jim

您可以使用map步骤来生成所有对：

john-jim -> 32, john-bob -> 32, jim-bob -> 32
john-jim -> 21

这些将按名称对进行聚合。然后在reduce中，只计算每个键的出现次数。这假设您有足够的磁盘来存储所有对。