从Hadoop看普通算法在一个系统中的应用

jacky4955

　　之前看了一些简单的算法题目，感觉很有意思，而在自己做的工程项目开发过程中，却又感觉很少用到，大约是所做的工程太过于简单的缘故吧。最近在读《Hadoop权威指南》那本书，从中看到了不少算法的应用，举两个简单的例子来说。

      1.寻找最近的备份数据。
      在Hadoop中，用户可以指定要数据的备份数目，比如默认default的备份数目是3。那么在读取数据时，如果发现某个结点的数据已经损坏，则需要从另外的备份中进行读取。这样，从哪一个备份数据进行读取就是一个需要解决的问题。在Hadoop的实现中，程序会自动选择一个“最近”的备份节点上的数据进行读取。
      问题来了，“最近”是什么意思呢？
      鉴于带宽（bandwidth）是分布式系统中的一个稀缺资源，使用两个节点之间的带宽来描述距离看上去是一种合理的选择，然而，在实际应用中这却很难实现。
      Hadoop使用了一种简单的实现方法，它将网络描述为一个树形结构，然后用两个节点距离最近公共祖先的距离之和来描述这两个节点之间的距离！从下面的图1可以更加清楚地看出在Hadoop中节点之间的距离概念。其中d1和d2可能是两个数据中心，r1和r2可以是一个数据中心里的两台服务器。这样，就可以用这种抽象描述带宽距离了。

　　这个问题恰巧是我前几天刚刚和朋友讨论过的问题，而说起它的原因是在面试笔试中经常遇到。具体的解决方法有很多，比如使用DFS进行树的遍历，然后求出到两个节点的路径，再进行对比。也有更为巧妙的算法，可以通过网络查找，在此就不进行赘述了。

      2. 数据压缩
      由于在HDFS（Hadoop所使用的分布式文件系统）上要进行大量的文件存储，所以文件压缩就是一种需要考虑的时间/空间折中方法。压缩解压过程消耗时间，但是压缩可以节省很多硬盘空间。Hadoop支持了包括ZIP等在内的多种压缩算法，而且像ZIP、bzip2这种Splittable的压缩算法尤其适用于MapReduce程序，因为就像字面上说的那样，压缩之后的文件可以拆分，程序可以seek到任意位置进行读取。
      我之前也用过一些压缩工具，但是对于压缩算法的具体实现第一次产生了好奇心。压缩在底层是怎样的实现机制？又应用了哪些算法？
      在压缩算法中我看到了一些常用的字符串匹配算法和赫夫曼编码的应用。通常的文本压缩算法思想是用较短的串代替那些经常出现的较长的字符串，对位置长度等进行标记。压缩算法有很多种，实现机制也各不相同，在这里我也不摘抄别人的总结了。

      总之，本文通过两个例子看到从课本上学习的以及在面试笔试中经常遇到的基础算法的应用所在。只有真的看到了应用，才能有更多的好奇心去学习和掌握。