EC2介绍（三）

    首先我们来看一下EC2是怎么解决数据均衡分布的问题的。

一、数据均衡问题

    我们知道，在分布式环境下，数据是分布在不同的节点上的，这些节点可能是物理节点，也有可能是虚拟节点。但是不管怎么样，总是有一个问题，我怎么保证每个节点上比较均衡地分布数据的问题。在中心式的环境下，这个问题的处理比较容易理解，只要用一台中心服务器管理元数据好了。这样我自然就可以解决数据均衡的问题（不过这种办法有自己的麻烦，比如当数据量非常非常大的时候，元数据的规模也会很大，另外还有单点失效的问题）。但如前所述，EC2的设计是去中心化的，这意味着并没有一个这样的中心服务器来管理元数据，那他怎么解决数据均衡问题呢？

二、DHT

    答案是DHT。DHT是Distributed Hash Table的缩写，中文可以称为分布式哈希表。虽然听起来有点陌生又有点高深，但其实这种技术可能很多人都在不知不觉中用了很多年了。电驴和BT这类下载软件相信大家不会陌生，这类被称作P2P的下载软件区别于传统的客户端--服务器的下载模式，它们就是基于DHT实现的。这里还涉及到另外一个概念：一致性哈希（Consistent Hash）。目前主流的DHT的实现都是基于他的。两者的概念定义参见附录，他们之间的关系如下图：

 
    如图所以，DHT这个概念最大，它里面包含Consistent Hash。而Consistent Hash中包含着具体的算法，比方说电驴就是采用Kademlia算法实现的。

三、一致性哈希

    下面就来讲讲一致性哈希的核心思想。

    总的来讲，既然是哈希，那么必然有key和value，因此基于这种方式实现的存储系统，也要求数据有key和value两部分，这也带来了一些弊端，比如模糊搜索就做不了。普通的Hash是仅仅对key做Hash运算，因为Hash运算必然涉及一个模的问题，这个模当然就取节点的数目了。假定有5个节点，那么hash运算一番之后，key所代表的哈希值被分为了五个区间，分别代表五个节点，然后将数据往五个节点上放就行了。

    这里有几个问题，如果节点数目发生变化，那么由于模发生了变化，必然导致绝大部分key的映射关系都发生了改变，这就意味着绝大部分数据需要搬迁，这非常不合理。

    一致性哈希首先要解决这个问题，它通过对key和node都进行hash运算的方式来避免这个问题。如下图所示：

 

    如果有一个写入缓存的请求，其中Key值为K，计算器hash值Hash(K)， Hash(K) 对应于图环中的某一个点，如果该点对应没有映射到具体的某一个机器节点，那么顺时针查找，直到第一次找到有映射机器的节点，该节点就是确定的目标节点，如果超过了2^32仍然找不到节点，则命中第一个机器节点。比如 Hash(K) 的值介于n1~n2之间，那么命中的机器节点应该是n2节点。

    如果这个时候有一个新节点加入怎么办？看下图：

 
    显然，受影响的数据之局限于新加入那个节点的相邻两个节点，这就避免了大量数据搬迁带来的一系列问题。有节点撤出的情况也相似。

    另外，还有一个问题需要考虑，比如节点个数很少的时候，容易导致分布不均衡的情况发生，而Dynamo引入虚节点的概念，可以有效地缓解分布不均的问题。如下图所示，左边是引入虚节点之前分布不均的情况，右边是引入虚节点后，导致节点数大大增加，因而可以较好地解决数据均衡分布的问题。

 

说明如下：

1、在节点少的情况下，hash函数的随机性可能导致某几个节点上负载过多，节点越少，这种情况越明显。

2、在节点少的情况下，一个节点离开或者加入，引起的数据震荡较大。

3、不同物理节点的硬件配置与实际处理能力往往不一样，他们承载能力也不一样。

引入虚节点可以较好地解决这些问题。

据统计数据表明，当节点个数达到上百个的时候，各个节点间负载比较均衡。

 

    但上面这个模型其实有很多问题没考虑，比如路由表的问题。如果当前的节点只保存下一个节点的位置，那么每次查找都要遍历很多节点，不现实；如果所有的节点保存所有其他节点的位置，那么数据量很大，也不太现实。不过Dynamo采用的是第二种方式，他怎么处理路由表过大的问题就不得而知了。

    

（未完待续）