当人们谈论规模的时候，他们往往是在谈论可扩展的分布式系统。如果你想知道自己在某些地方的认知全是错误的，那么深入分布式吧。不管怎样，关于分布式，你首先要学习的事情就是通过机器有效的进行数据分发或者通过服务器进行有效的负载均衡。我将在这篇文字中讨论前者。像往常一样，我们将从现实的例子开始，然后解决它。让我们开始吧。
比如说，你老板给你一个文件，这个文件包含很多行，每行有一个IP地址和一个时间戳。IP地址代表客户端地址，时间戳代表对应的客户访问你们网站的时间。这个文件包含10万个这样的组合。时间戳是按升序排列，这意味着倒数第二个记录的时间戳小于倒数第一个的时间戳。下面是个样本格式：
111.111.111.111 2014:02:01:12.0400
222.222.222.222 2014:02:01:13.0410
333.333.333.333 2014:02:01:14.0500
111.111.111.111 2014:02:01:15.0200
你老板希望你能写个算法，这个算法能计算出特定客户IP地址最后访问你们网站的时间。你想到了键值对数据集能够解决它。因为需要重复查找指定的键，能够提供O(1)查找时间的hashmap非常合适解决这个问题。你的老板正看着你，你在心里对使用hashmap的这个想法做了个评估，最后告诉他这样很容易完成这个任务。这是该算法的粗略轮廓：
你将会用一个O(n)时间的线性扫描来将这些键值对放到一个map中。由于时间戳是升序的，所以假如遇到了重复的key，就直接用新的时间戳替换key的value。只要这个map准备好，该算法就能够在O(1)时间提供给客户它最近的访问时间。你自豪感爆棚。
你的老板问了你一个很贴切的问题“你是把数据一直放在内存里吗？”。你肯定的回复他说：由于数据不大，所以放内存里是没有问题的，这样做的结果是几乎能立即查询出结果。他皱了皱眉头然后跟你说：“内存当前还不是问题，但不能假设他永远不会出问题”。你思索了一下他说的话，然后明白了他的意思。他指的是公司快速发展的网站以后会产生越来越多的数据，如果你把所有的客户IP都放在内存里，迟早会压垮服务器。你同意他的观点。可扩展性意识悄悄出现。你征求说需要一点时间来考虑这个问题，他点头答应然后消失了。和平！！
现在你开始思考这个问题，基于你的数据结构的知识，你认为你给出了这个时间复杂度为O(1)的解决方案是最好的，然而不幸的是这个方案存在明显的问题。你想象有一个1亿行的文件，然后你的头开始旋转。你考虑LRU缓存机制，然后又否定它，因为出现一个缓存命中失败就会很麻烦（需要记住1亿记录在一个单独的机器中），并且我们希望有一个非常快的查询。但是呢，你是问题解决者。你觉得将数据放入hash-map的方法是不错的，但是内存是个问题。为什么不把数据放到多个机器上呢？每个机器保持一部分有限的数据就可以非常快速的访问。这是个不错的策略并且看起来可行。
但是首要的问题是找到数据分发到这些机器的规则。你手头有10台机器可以使用。你又想象有1亿的数据，然后每台机器就能处理1000万条数据。你还认为拥有相同IP的数据应该分发到同一台机器。你想到哈希，你最好的朋友。IP地址串能够哈希成一个数字，随后被映射到对应的机器。由于你有10台机器，为了避免过载，你需要对这个关键字对机器数进行取模。你得到了你的哈希算法：
IP地址 => 哈希数字 => 哈希数字%机器数 => 关键字对应的机器编号
例如，111.111.111.111 => 994968954 => 994968954%10 => 4。所以111.111.111.111应该分发到第一台机器。
非常棒！你全力去实现这个算法。你用sockets写了一个小的后台服务，并在每台机器上运行。你同样写了一个轻量的服务接口，这个服务接受一个key，使用上面的算法计算出这个key，将key对应的数据分发到对应的服务器，然后与提取数据的服务器建立通信通道。为了写入一个新行，程序同样要调用类似的服务接口，传入关键字(该行中的IP地址)和需要负载的数据(这个例子中就是该行中的时间戳)，随后附加到目标机器的文件尾。由于每台机器存储的浏览记录相对来说比较少，你在返回数据时用LRU缓存[固定大小]来缓存它。这样即使出现缓存命中失败也不会碍事。非常好！！一切都搞定了，然后你想你老板展示了你的解决方案。
他很高兴，并问了你几个关于机器失效的问题。你没能回答，然后他让你专注于可扩展性和效率，先不管故障处理和数据复制，至少目前应该这样。你勉强同意。
你完成了该方案，并部署在10台生产环境的机器上。数据根据key分发过来并保留在对于的机器上，一切运行良好。由于每台机器上的数据减到之前的10分之一，速度令人惊叹。
自从代码部署到了生产环境，各种事情的发生就像你以前预见一样。你老板找到你并告诉你在各台机器上的数据增长非常快，你需要添加更多机器，否则每台机器将会由于数据集太大而变得非常慢。你同意他的观点。他建议你添加更多机器。你看了看你的算法，现在数据将分发到20台机器，你可能需要将模10改成模20。你老板怀疑地问了一个问题：“那么现有的数据集怎么办？”。
你看到了问题所在，现在这些关键字将映射到新的数字，而且读取操作将被发送到新的机器，新机器上的数据可能不正确。你很忧虑。现在最好的解决方案就是将这10台机器上的数据重新分发到20台机器上。你老板问道，这样重新分发需要多少时间？你回答他：“小于一个小时，但是网站在这段时间将不能访问”。你老板皱起眉头。
你被困在一个难堪的局面。你征求说需要一点时间来考虑这个问题，他点头答应然后消失了。和平！！
你认为如果网站继续按目前的速度增长的话，这样的问题可能每个月都会发生。同样我们还没有考虑故障接管。你向你工作在一个客户快速增长的公司的朋友请教。他直言不讳地说：“你的哈希函数很烂，如果你想横向扩展你的系统的话，你应该看看一致性哈希”。你问他：“什么是一致性哈希？”。他开始解释：
“一致性哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对K/n个关键字重新映射，其中K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。”。 Wikipedia
在实战中你已经遇见了上面句子中最后那部分描述的情况。
为了更好的理解，这里进行更多的解释。假设说你有15个数字(关键字),[1,8,3,7,5,6,4,2,11,15,12,13,14]和3台机器。在这个例子里，你知道关键字的范围是1-15。你分配固定的ID给你的机器，分别为0、5、10。现在的算法就是将关键字对应的数据放到ID小于或等于关键字的机器上（现实中数字范围会很大，这里为了简单起见，我们假设固定在1-15）。所以：
机器0 -> 1, 2, 3, 4
机器5 -> 5, 6, 7, 8
机器10 -> 11, 12, 13, 14, 15
如果新的关键字到达，例如9，它将放到机器5上面，因为5小于9：
机器5 -> 5, 6, 7, 8, 9
现在考虑这个问题：你现在得到一台机器并想把它添加到集群中。你分配任何一个1-15之间的数字作为该机器的ID。这里假设是7。现在你有4台机器在机器中，然后数据需要重新分发。但细想一下，机器0和10中的数据不受影响，只有机器5中的数据受影响。机器5中只有大于等于7的数据需要重新分发。结果如下：
机器0 -> 1, 2, 3, 4
机器5 -> 5, 6
机器7 -> 7, 8, 9
机器10 -> 11, 12, 13, 14, 15
这可以很好的可视化成一个圆。下面是一个一致性哈希环：
恭喜！！你刚刚已经实现了一致性哈希。所以现在，如果你想添加一个新的机器，只需要对环上的某些关键字从之前的机器上重新分发到新机器上。我们已经走过了漫长的道路。
你向你老板展示了这个新算法，算法令他印象深刻。但是向往常一样，他问了你另一个问题：“能添加节点是很好的，但是如果一个包含数据集的节点发生故障那将会发生什么？”。你思考了一下，看着你的一致性哈希环，很快有了个方案。但是就像往常一下，你征求说需要一点时间来考虑这个问题，他点头答应然后消失了。和平！！
在这个一致性哈希环中，即使一个机器出故障了，它前面的那个机器将能够很好的处理发送到它的关键字，是不是？例如，7号机器出了故障，哪个机器将会服务关键字8？机器5，对不对？因为当7号机器不在的时候，机器5在环山的关键字8前面。所以，你想啊，为啥不在前一个机器上保存当前机上关键字的一个副本？假如当前机器出现故障，那前一个机器就会救了我们。使用专业术语来说，就是我们设定重复因子为1，这样万一故障出现，我们至少会有1个节点拥有备份的数据。这非常简单。所以画了个新图（看起来有点乱，请忍受一下）。正如你所看到的，现在0号机器保存了一份机器5关键字的副本。所以每次关键字发生到机器5，都会被复制到机器0。其他机器也做类似处理。
现在你有串联方式工作的机集群。关键字被分布在机器中，即使其中一个出现故障时，它前面的机器将接替它工作。因此，集群不仅支持负载均衡，还支持切换。这太棒了！！
有了这个惊人的算法，支持负载均衡和故障转移，你自豪的去找你的经理。他给一个微笑：“很赞的工作”。
一致性哈希拯救了你。你欣赏的不仅是这个算法容易实现，而且是它有可扩展性和处理失败这种巨大的能力。
你上面实现的小算法其实在NoSQL数据库里使用。还有，为了显而易见我在这里已经排除很多东西，但基本思想是一样的。这是学习分布式系统是如何工作的第一步，并且你跨过了这一步。太棒了！
注意：在文章中我们很多次提及用来计算哈希关键字的固定机器ID，这个ID本身是由哈希函数来计算的。如果机器间隔的比较远，那这种技术有时会导致负载不均衡，这意味着一个机器实际上得到负载会大于其他的机器。这实际上可能发生，即使在环上静态分配机器标识。这通常通过引入虚拟节点机制来解决。在这个机制中，我们在环上加入很多虚拟节点，这些虚拟点世界上也是对应那些真实的机器。所以技术上来说，一个机器可以负责环上的多个区间。在种技术在The Apache Cassandra Project和Riak-Basho Technologies中有使用。这里借了一个图来展示。下图看起来很复杂但实际上不是。它仅仅是说这里有4台机器，但是负责32个我们上面提到的那种分区。每段绿色的由机器0处理，橘色的由机器1处理，以此类推。。。
哈希快乐…一致性哈希！！！