我正在尝试使用hadoop构建维基百科共同编辑页面的图形。原始数据包含编辑列表,即每个编辑有一行告诉谁编辑了什么:
# revisionId pageId userId
1 1 10
2 1 11
3 2 10
4 3 10
5 4 11
我想提取一个图表,其中每个节点都是一个页面,如果至少一个编辑器编辑了两个页面(同一个编辑器),两个页面之间有一个链接。对于上面的示例,输出将是:
# edges: pageId1,pageId2
1,2
1,3
1,4
2,3
我远不是Map/Reduce的专家,但我认为这必须在两项工作中完成:
第一个作业提取每个用户的已编辑页面列表。
# userId pageId1,pageId2,... 10 1,2,3 11 1,4
第二个作业采用上面的输出,并简单地生成每个用户编辑的所有页面对(因此这些页面已由同一用户编辑,因此将在图形中链接)。作为奖励,我们实际上可以计算出有多少用户共同编辑了每个页面,以获得每个边缘的权重。
# pageId1,pageID2 weight 1,2 1 1,3 1 1,4 1 2,3 1
我使用Hadoop实现了这一点,它可以工作。问题是第二个作业的映射阶段真的很慢(实际上,前 30% 没问题,但后来减慢了很多)。我想出的原因是,因为一些用户编辑了许多页面,映射器必须生成很多这样的对作为输出。因此,Hadoop必须溢出到磁盘,使整个事情变得非常缓慢。
因此,我的问题如下:
- 对于那些比我更有经验的Hadoop的人:我做错了吗?有没有更简单的方法来提取此图?
- 磁盘溢出可能是第二个作业的映射阶段非常缓慢的原因吗?我怎样才能避免这种情况?
作为侧节点,这在一小部分编辑样本中运行良好。只有 GB 的数据才会变慢。
显然,这是一个常见的问题,称为组合/互相关/共现,有两种模式可以使用 Map/Reduce、Pair 或 Stripes 来解决它:
- Map Reduce Design Patterns:- Pair & Stripes
- MapReduce模式,算法和用例(交叉相关部分)
- 成对和条纹
我在问题中提出的方法是配对方法,它通常会生成更多的数据。条纹方法从组合器中受益更多,并且在我的情况下提供了更好的结果。