0

我们的 Hadoop 集群每天摄取数 TB 的 Web 日志。每条日志记录都包含用户 IP 地址、cookie ID 等信息。但是,不同的 IP 地址和 cookie ID 可以对应一个物理用户(家庭/工作计算机等)。我们设计了一个函数来计算任何一对记录的匹配分数,分数越高意味着两条记录对应一个物理用户的概率越高。

目标是使用评分功能将所有记录分成可能对应于一个物理用户的组,并通过唯一的组 ID(即物理用户 ID)标记组中的所有记录。使用 Hadoop/Mahout 实现此逻辑的最佳方法是什么?

4

1 回答 1

2

首先,我假设您知道如何链接 MapReduce 作业。如果没有,请参阅http://developer.yahoo.com/hadoop/tutorial/module4.html#chaining了解详细信息。

其次,我假设您有一个可用的分布式键/值存储,例如 Cassandra。

第三,你的评分功能对我来说没有意义。我不认为“这里的一张唱片,那里的一张唱片”会让你知道他们是同一个人。我可以相信“这里的记录与那里的记录相比=估计是否同一个人”。因此,与您的描述相反,我将假设这就是您的评分功能的实际工作方式。

现在,解决您的问题的理论上的好方法是什么?

  1. 处理日志,将唯一机器标识符(IP 地址 + cookie)+ 日期范围映射到所有记录事件的存储中。

  2. 提取所有唯一机器标识符的列表。也存储它。

  3. 执行 MapReduce,其中 map 采用机器标识符,获取所有其他机器标识符的列表,并发出所有不同机器标识符对,其中第一个小于第二个。reduce 查询每个记录的事件,计算分数,然后如果分数超过阈值,则发出较大机器标识符映射到较小机器标识符的数据点。

  4. 3 的输出通过管道传送到 map reduce,它的 map 什么都不做,它为每个机器标识符找到它映射到的最小机器标识符。

  5. 4 的输出通过管道传输到 map reduce,其 map 采用一对(机器标识符,规范机器标识符),从 #1 中的存储中获取事件,并将它们重新映射到(规范机器标识符,其余事件),其 reduce存储规范机器标识符(又名组 ID)、相关事件。(如果你愿意,可以按日期。)

好的,这是一个很好的理论。它哪里出错了?

问题是所有标识符对都太多了。该列表最终可能在 10 18的数量级上,您要为每个列表提取日志。除非您拥有真正出色的硬件,否则您将耗尽处理能力来计算它。因此,您需要找到启发式方法来减少它。

第一个也是最简单的,任何已识别的“这两个标识符映射到同一个标识符”都应该尽可能预先存储和重用。

其次,在完成一项大型初始工作后,您可能会逃避,“在所有最近创建的标识符中,它们映射到什么?” 这些是您不希望总是重新创建的规范映射的候选者。

第三,我相信你有“相似记录”的概念。所以将记录映射到某种记录组,然后在reduce中让所有“足够小”的组将所有对映射到“可能相同”。将这些对发送到一个 map reduce 中,该 map reduce 抓取“可能相同”的记录,然后创建一个查找映射机器标识符,以便所有“出现可能相同超过 X 次”。保存那个。现在重复上面的步骤,除了在第 2 步中,您将机器标识符发送给所有对自身,并带有“出现可能相同”的另一个。这个捷径会大大减少工作量。

这是一个需要大量工作的通用策略。祝你好运。

于 2013-07-18T23:40:53.693 回答