每周学点大数据 | No.43 相似连接的可扩展性

No.43期

相似连接的可扩展性

小可：那么具体是怎么做的呢？

Mr. 王：我们先来看看求单元函数值是如何在 MapReduce 上实现的吧。

图中有三个集合 M1、 M2、 M3。键值为集合名称，值为每种元素的个数。在经过 Mapper的过程中， key 依然不变，但 value 部分我们保存两种 value ：第一种用 0 标记，用来统计这个Mapper 收到的来自某一个集合的元组个数。

比如第一个 Mapper 收到了 M1 两个、 M2 两个；第二种我们用 1 以上的数来做标志位，表示这个 Mapper 收到了多少种来自这一集合的元素，比如第一个 Mapper 收到了来自 M1 的一种元素（标志位记为 1），其后面的部分记录各种元素的数量（<a,2>），和之前一样。

这里包含了一个思想，就是合理设计 value 值的结构，让 value值可以有多种不同的类型，比如这里设计了一个标志位来区分不同类型的 value 值。

同时这个value 里面有一个次级键的思想，value 里面的第一个值就是一条记录的次级键，在洗牌的过程中，可以实现利用次级键进行二次排序。

接下来数据经过洗牌之后被送到了 Reducer 中，从图中可以看出， Reducer 对数据进行了整理，生成的键值对的第一个 value 属性就是每一个集合的计数，也就是单元函数值。

小可：那求合取函数值又是怎么做的呢？我觉得如果 HDFS 上可以存储前面的输出结果的话，那么求合取函数值时是不是可以对这个结果加以利用呢？

Mr. 王：对。之所以我们在求单元函数值的过程中保留着对各种元素的计数，就是要进一步应用这个结果。

在求合取函数值的过程中， Mapper 做的一件事情叫作交换键值。我们将元素反提出来，将集合名称放进 value 中，变成一种有利于做合取的形态。

接下来在 Reducer 中，每一个 Reducer整理一种元素，比如某一个 Reducer 整理 a，这个 Reducer 将其整理成key=<M1,M3,5,4>、value=<2,1> 这种形式。

它的意思是， M1 和 M3 中分别含有 5 个和 4 个元素，其中 a 的个数分别为 2 和 1。

小可：我想做到这一步，合取函数值已经求出来了吧？

Mr. 王：没错，做到这里，合取函数值已经可以通过这一步的结果知道了。我们进一步做下去，再用一轮 MapReduce 将相似度彻底求出来。

Mr. 王：下一轮的这个 Mapper，会把中间结果发送出去，而 Reducer 会收到这些结果，我们就能求出其根据三种不同计算方法的相似度。

这里有一点点小思考，我们可以对求单元函数值部分做出改进，让它的求解变得更快速一些。

首先还是要对表进行随机分割，但是在 Mapper 运行之后，我们尝试对 Mapper 生成的数据进行压缩。我们在 Mapper 中只统计元素的个数，而忽略它们具体是什么；在 Reducer 里面做一个求和就可以了。

小可：这样在求单元函数值时的确可以更加节省资源，但是后面的合取求解怎么做呢？

Mr. 王：当我们已经求出了每个集合中有多少个元素这张表保存在每一个 Mapper 中。

只要每个 Mapper 中都有这样的一个表，求解相应的占比也就容易得多了。但是对于 Mapper 来说，这样的表也是对内存的一种消耗。好在这个表不会太大，消耗的内存也不会太多。

内容来源：灯塔大数据