附录D.1 优化后的重分区框架
Hadoop社区连接包需要将每个键的所有值都读取到内存中。如何才能在reduce端的连接减少内存开销呢？本文提供的优化中，只需要缓存较小的数据集，然后在连接中遍历较大数据集中的数据。这个方法中还包括针对map的输出数据的次排序，那么reducer先接收到较小的数据集，然后接收到较大的数据集。图D.1是这个过程的流程图。
图D.2是实现的类图。类图中包含两个部分，一个通用框架和一些类的实现样例。
连接框架
我们以和Hadoop社区连接包的近似的风格编写连接的代码。目标是创建可以处理任意数据集的通用重分区机制。为简洁起见，我们重点说明主要部分。
首先是OptimizedDataJoinMapperBase类。这个类的作用是辨认出较小的数据集，并生成输出键和输出值。Configure方法在mapper创建时被调用。Configure方法的作用之一是标识每一个数据集，让reducer可以区分数据的源数据集。另一个作用是辨认当前的输入数据是否是较小的数据集。
protected abstract Text generateInputTag(String inputFile);
protected abstract boolean isInputSmaller(String inputFile);
public void configure(JobConf job) {
this.inputFile = job.get("map.input.file");
this.inputTag = generateInputTag(this.inputFile);
if(isInputSmaller(this.inputFile)) {
smaller = new BooleanWritable(true);
outputKey.setOrder(0);
} else {
smaller = new BooleanWritable(false);
outputKey.setOrder(1);
}
}
Map方法首先调用自定义的方法 (generateTaggedMapOutput) 来生成OutputValue对象。这个对象包含了在连接中需要使用的值（也可能包含了最终输出的值），和一个标识较大或较小数据集的布尔值。如果map方法可以调用自定义的方法 (generateGroupKey) 来得到可以在连接中使用的键，那么这个键就作为map的输出键。
protected abstract OptimizedTaggedMapOutput generateTaggedMapOutput(Object value); protected abstract String generateGroupKey(Object key, OptimizedTaggedMapOutput aRecord); public void map(Object key, Object value, OutputCollector output, Reporter reporter)
throws IOException { OptimizedTaggedMapOutput aRecord = generateTaggedMapOutput(value); if (aRecord == null) {
return;
} aRecord.setSmaller(smaller);
String groupKey = generateGroupKey(aRecord); if (groupKey == null) {
return;
} outputKey.setKey(groupKey);
output.collect(outputKey, aRecord);
}
图D.3 说明了map输出的组合键（composite 可以）和组合值。次排序将会根据连接键（join key）进行分区，并用整个组合键来进行排序。组合键包括一个标识源数据集（较大或较小）的整形值，因此可以根据这个整形值来保证较小源数据集的值先于较大源数据的值被reduce接收。
下一步是深入reduce。此前已经可以保证较小源数据集的值将会先于较大源数据集的值被接收。这里就可以将所有的较小源数据集的值放到缓存中。在开始接收较大源数据集的值的时候，就开始和缓存中的值做连接操作。
public void reduce(Object key, Iterator values, OutputCollector output, Reporter reporter)
throws IOException { CompositeKey k = (CompositeKey) key;
List<OptimizedTaggedMapOutput> smaller = new ArrayList<OptimizedTaggedMapOutput>(); while (values.hasNext()) {
Object value = values.next();
OptimizedTaggedMapOutput cloned =((OptimizedTaggedMapOutput) value).clone(job); if (cloned.isSmaller().get()) {
smaller.add(cloned);
} else {
joinAndCollect(k, smaller, cloned, output, reporter);
}
}
}
方法joinAndCollect包含了两个数据集的值，并输出它们。
protected abstract OptimizedTaggedMapOutput combine(
String key,
OptimizedTaggedMapOutput value1,
OptimizedTaggedMapOutput value2); private void joinAndCollect(CompositeKey key,
List<OptimizedTaggedMapOutput> smaller,
OptimizedTaggedMapOutput value,
OutputCollector output,
Reporter reporter)
throws IOException { if (smaller.size() < 1) {
OptimizedTaggedMapOutput combined = combine(key.getKey(), null, value);
collect(key, combined, output, reporter);
} else {
for (OptimizedTaggedMapOutput small : smaller) {
OptimizedTaggedMapOutput combined = combine(key.getKey(), small, value);
collect(key, combined, output, reporter);
}
}
}
这些就是这个框架的主要内容。第4章介绍能如何使用这个框架。