使用大数据计算共同组成员的算法

Question

使用大数据计算共同组成员的算法

6

我需要编写一个程序，计算两个用户在同一组中出现的次数。用户通过用户名给出，组通过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工作内存中运行时内存消耗过大（首先是堆空间，优化后我得到了罕见的“GC超限”错误）。从Java连续写入数据库也太慢了（即使使用批量查询进行优化）。越来越绝望，我尝试了一些更奇特的方法，比如将所有对写入数组，然后排序（O（n log（n））），然后逐渐计数。但仍然需要存储太多数据在内存中。

有没有关于如何解决这个问题的算法？或者说这是不可能的？

- dottorep

1

你那里的用户名是用 text 而不是像 user_id 一样的 integer 类型吗？另外，(grp, usr) 是唯一的吗？还有，你使用的是哪个版本的Postgres？ - Erwin Brandstetter

我认为有三个选项。1）给您的计算机增加更多内存。2）将数据分成几部分。3）使用并行计算，让多台计算机计算数据的一部分。 - WereWolfBoy

是的，我有用户名作为文本。我已经使（grp，usr）唯一。Postgres版本为8.4.0。获取user_id需要与另一个表合并，这将耗费太多时间。但是我已经成功地将所有共组对非唯一地写入了一个文本文件中。它有50 GB大小。我目前正在使用Linux sort命令进行排序。我想从这里开始，我可以编写一个程序，逐步读取文本文件，计算每个昵称组合的出现次数，并将它们保存到另一个文件中，而不会在内存中存储太多数据。你看到任何明显的缺陷吗？ - dottorep

顺便提一下，不清楚结果是否应按任何特定顺序排序。对于大量行来说，这会产生很大的影响... - Erwin Brandstetter

感谢大家提供的出色答案！我之前做的那个烂解决方案最终居然产生了我想要的结果，经过几天的处理。生成的文件有15亿行，大约40GB。正如@ErwinBrandstetter预测的那样，这很难处理，我可能最终会使用提供的查询来制作一个较小的版本。（这是我的第一个问题 - 我必须说我对所有伟大的回复感到非常惊讶！谢谢！） - dottorep

3个回答

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

你现在已经有了文件名和数量对（使用一元计数法，因此你真正需要的是文件大小，以字节为单位）。

几乎所有这些都可以并行完成，尽管阶段1必须在阶段2开始之前完成。要提高速度，可以增加核心或购买更快的磁盘。没有内存限制，只有磁盘。

添加内容：我刚刚使用一个线程对这个算法进行了一些模拟测试。

1800个组，300个用户和15000个成员（全部随机生成），大约需要2.5分钟。 900个组，150个用户和7500个成员，只需要54秒钟。

- OldCurmudgeon

+1 为提供测试用例结果点赞。非常有用！（不是为了解决问题提出的路线）。你用哪个软件进行了测试？ - Erwin Brandstetter

我也喜欢 shell hacks，但是我不认为这个非常好的解决方案可以在这样的规模上工作。我们正在查看一个可能有数百万个文件的目录。每个文件都会使用至少1个磁盘块（加上元数据！），而你需要随机地写入它们。对于原始数据集，它很可能会遭受严重损坏。要使第一阶段并行化，您需要使用锁。否则，同时打开和追加到同一文件的进程将彼此覆盖。 - jop

@jop - 我们可以缓解FileSystem的过载问题。我们可以将文件放置在子目录中等，这不是问题。文件锁定也不应该是问题，因为写入应该被很好地分布，并且锁争用应该相对较少。这可能不是“最佳”解决方案，但它将在任何地方工作，并且（在足够的并行化情况下）将以类似于MapReduce解决方案的时间终止。 - OldCurmudgeon

@jop - 我的实验表明，相对于第二阶段，第一阶段相对较短 - 这正如我所预期的。我们正在对第一阶段生成的每个文件进行 O（（n / 2）^ 2）处理。这种方法的好处是它将使用一致和可预测的运行时间，并且仅在磁盘变满时才会失败。 - OldCurmudgeon

有趣的解决方案！并且带有一点点黑客的感觉，这是我一直喜欢的。但是我认为在文件系统中生成15亿个文件与数据库解决方案相比可能不太实用。而且我也不确定我的服务器系统管理员会批准这种做法。 - dottorep

显示剩余2条评论

1

无论采用什么解决方案，复杂度取决于生成的配对数量，而不一定是组或人数。对于不同的团体大小：

一个有10个成员的团体会产生 C(10,2) = 45 对配对
100个成员的团体会产生 C(100,2) = 4950 对配对
1000个成员的团体，会产生 499500 对配对...
有10000个成员的单个团体将产生接近5000万对配对！因此，单个团体的计算量可能会超过其余计算的总和。

因此，我的第一个建议是从数据集中清除非常大的团体。如果您无法省略大型团体，并且发现它不能适应内存，或者需要花费很长时间才能通过单个线程完成计算，则可以使用Map-Reduce自动并行化计算，如下所示。如果您从团体成员开始，例如：

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

你可以使用map步骤来生成所有的配对：

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

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

- jop

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Erwin Brandstetter · Accepted Answer

关系型数据库管理系统(RDBMS)专门用于排序等操作。在数据库外进行这些操作的性能几乎无法与其相媲美。请使用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;

根据您有多少重叠，这可能会产生大量的行，正如您所说的那样。因此，这永远不会很快。

引出问题：生成数百万个无法处理的行的目的是什么？您确定操作从一开始就有意义吗？

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

升级！PostgreSQL 8.4现在已经相当过时。特别是，PostgreSQL 9.2以大数据为重点。您可以期望在这样的工作中获得更好的性能。
而且没有人应该运行8.4.0。仅出于安全原因，但您也会错过很多错误修复。当前的点发布版是8.4.17。我引用链接的网站:

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

使用整数作为用户的代理键，这样你在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 必须排在第一位。为什么这很重要？

    CREATE INDEX usr_grp_gu_idx ON usr_grp(grp_id, usr_id);

在您的计算机上增加大量RAM，并增加work_mem和shared_buffers的设置。

测试用例

我采用了@OldCurmudgeon报告的数字，并在PostgreSQL中创建了一个可比较的测试用例。

-> SQLfiddle演示。

在此公共测试数据库中约为250毫秒。
结果未排序（没有ORDER BY），因为这未被指定。
与下面报道的相比，2.5分钟。因素为600。