2

我正在 hadoop 集群上构建字典，需要为每个令牌生成一个数字id。我该怎么做？

4

3 回答 3

2

你有两个问题。首先，您要确保为每个令牌准确分配一个 id。为此，您应该按标记对记录进行排序和分组，并在减速器中进行分配。一旦你确定对每个标记只调用一次 reducer 方法，你就可以使用上下文中的分区号和 reducer 维护的唯一数字 id（每个分区一个实例） - 只需使用初始化为 1 的实例变量在 setup 方法中并在 reduce 方法中递增。

于 2012-07-31T12:13:47.813 回答
0

为了避免不属于您的业务逻辑的同步、排序和分组，您可以使用一些技巧，这样会更快。

最简单的一种是在 Reducer 中生成 UUID，每个键一个UUID UUID.randomUUID()，但这些不是数字。

如果您想要连续的数字 id 序列并且您的输出足够小以供一个减速器处理，那么通过 org.apache.hadoop.mapreduce.Job.setNumReduceTasks(int tasks) 强制使用一个减速器来完成作业，因此所有键都将被定向到单个 Reducer。

如果 Mapper 的输出对于单个 Reducer 来说仍然太大，并且您不关心 id 的序列连续性或者您的字典可以被分区，那么您可以使用 Partitioner 的一些技巧（请参阅参考资料）。这个想法是您可以在逻辑上将键划分为 N 个已知长度的范围（例如，范围 1 可以有 1 百万个以 1 开头的键，范围 4 可以有 500 个以 3500000 开头的 id，等等）。逻辑：

  1. 将 Reducer 的数量设置为 N (JobConf.setNumReduceTasks(N))；
  2. 实现将 key 与其 range 匹配的 Partitioner，它将把同一 range 中的所有 key 定向到同一个 Reducer；
  3. 在 Reducer 中有一个以范围的第一个 id 开头的计数器（在第一次调用 reduce 时，使用与 partitioner 中相同的逻辑来识别哪个范围是 Reducer）

如果您对范围没有任何业务知识，则可以花一些时间对键进行区分并计算范围及其长度。有了这个，您可以在结果集中获得连续的 id 序列。

如果您不想花时间在不同的键上，那么目标是为每个 Reducer 使用不同的数字开始 id（Reducer 1 生成仅以 1 开头的 id（1、10、124523、1341243），Reducer 2 与 2 （2、23、234234532）等）。为此，计算密钥第一个字节的 mod 10，并强制 10 个 Reducer，将零指向与 1 相同的分区（主要原因是没有以 0 开头的 2 位整数，它可能会导致与 ids 冲突来自其他分区），因此分区 0 的输出为空。比在 reducer 端追加（连接 2 个字符串！！！）计数器到（密钥 mod 10 的第一个字节），其中 0 更改为 1。每个 reducer 都有一个从 1 到无穷大的计数器，可以从包含用于该分区的最后一个 id 的文件。

前任。

key = "abc", ascii of 'a' is 97, 97 % 10 = 7 and id for that key is '7' + '1' = '71', 
for "asd" it will be '7' + '244' = '7244', 
for "bbv" is '8' + '1' = '81', 
for "bgh" is '8' + '2' = '82', 
for "ddv", 'd' is ascii 100, 100 % 100 = 0 , convert to 1, '1' + '1' = '11', 
for "edv" is 101 % 100 = 1, '1' + '2234' = '12234'.

因为所有的键都以不同的数字开头，所以它们从不重叠，因此不需要在多个 Reducer 之间进行同步。它由 mod 结果和计数器的字符串连接保证，因此不会溢出到下一个前缀/前导数字。另一个优点是您不需要进行任何预排序，这不是您业务逻辑的一部分。当 Reducer 关闭时，它可以将在 id 生成中使用的最后一个计数器写入文件，该计数器可以在下一次运行中使用，并通过字典的分区提供 id 的连续性。

要将分区数量从 10 增加到 100，请使用 mod 100 并将单个数字结果与 2 数字结果合并（我们再次浪费了 10 个 reducer 的输出）。Ex 10 % 100 = 10, 1 % 100 = 1 转换为 10, 102 % 100 = 2 通过添加 '0' 作为字符串或乘以 10 转换为 20。目标是使所有前缀具有相同的位数，在这种情况下为 2。

通过巧妙的逻辑，我们可以避免浪费跳过的分区（在 mod 100 的情况下为 0、1、2、9）。

警告：此逻辑容易受到数据倾斜的影响。

我希望它有所帮助，干杯。

于 2012-07-31T20:42:18.193 回答
0

我们使用的另一个选项是将 ID 块分配给任务，为此您需要一种机制来管理事务。我们使用 AWS 的SimpleDB来跟踪交易和已使用或未使用的 ID。

在作业开始时，我们将整个 ID 块集锁定在 Simple DB 上（只有一个属性更改为“locked”），然后每个任务调用 simple db 来“签出”它使用的 ID 块。

如果任务失败，它永远不会“解锁”块并且永远不会更新最后使用的 ID，因此这些 ID 不会被失败的任务消耗。最后，当我们解锁整个 ID 块集时，我们会解锁任何由失败任务持有的块。

我们将通过从简单数据库导入/导出 ID 块来改进此过程，因此我们不必更新外部资源。相反，我们可以从与数据一起存储的文件中读取可用的 ID，将它们写入 simple db，使用 simple DB 来协调将块分配给各个任务（映射器、reducer），然后将它们写回并返回成功的结果。

一旦我们做出改进，我们可能会公开代码，所以如果有人对这种方法感兴趣，请随时与我联系，如果我们完成了，我会用代码更新这篇文章。

于 2013-01-25T02:16:49.177 回答