《大型分布式网站架构设计与实践》

• 读后感

逐字逐句看完《大型分布式网站架构设计与实践》第2章，意犹未尽！如标题所言，这是一本“真材实料的分布式资料”，它与我看过的分布式书籍（如《大型网站系统与Java中间件实践》）不同，本书重技术兼并理论，给了新人入手的方向。

我最最感动的是书中介绍了很多分布式的“干货”：分布式缓存可以用memcache、数据库水平/垂直拆分技术、分布式存储可以HBase/Redis等、消息通道可以用ActiveMQ、搜索引擎Lucene/Solr等。当然每一种技术都不是一本书能说完的，作者至少给了我们学习的方向，我很感动。

这只是第2章，后面还会有我很感兴趣的日志处理、数据仓库、负载均衡等，如果没有中奖，我也会去买一本学习。这是一本适合入门和进阶的书籍，有介绍分布式的理论，也同时介绍每种技术用到的具体实现方式，可以让我们少走弯路。

书中介绍了一致性hash算法(consistent hashing)，我个人也非常佩服这个经典算法，所以后面对它进行一些介绍总结。

• 一致性算法

背景：所谓分布式缓存不是说每台服务器都存储所有的缓存，而是让每台服务器均分存储缓存。要实现服务器的均分及更新就要注意两点：①用什么算法去均分才能快速找到指定缓存；②当缓存出现新增、删除时如何将变化的缓存同步到对应服务器也是一个关键。

传统算法：最传统的算法是通过“缓存总数/服务器数量”的形式来均分，每一个缓存都有其唯一的Hash值（数字），要找到指定缓存在哪台服务器上可通过hash(key)%N取余的形式判断，这样基本能达到平衡。

传统的算法查找缓存运行模式如下图所示，当客户端需要某个缓存的时候，首先会向缓存索引（菱形结构）发出请求，此时索引器通过算法（hash(key)%N）取余的形式找到余数对应的缓存服务器并取得该缓存返回。

这种算法能达到缓存的第一个条件“用什么算法去均分才能快速找到指定缓存”，但是却在第二个条件上碰了壁“当缓存出现新增、删除时如何将变化的缓存同步到对应服务器”。假设server1突然宕机，该服务器上的所有缓存失效，这时又得重新平均计算缓存并且平均放到剩余的几台服务器上。重置缓存是需要花费时间的，这时如果有用户请求则无法取到缓存，取而代之的是从数据源读数据，一大波数据请求不断冲击服务器，很可能造成系统崩溃，这也就是所谓的“雪崩效应”。

一致性哈希（consistent hashing）：一致性哈希算法在1997年由麻省理工学院提出，设计目标是为了解决因特网中的热点问题，目前在集群缓存应用中得到非常高的肯定。

下图所示为一致性哈希的理论原理。

>>首先要有一个首位相接的圆环，这个圆环大小是有科学依据的：一般一个缓存对象的hash值是32位的，那么理论上就可以存在2的32次方个（也就是从数字0~2的32次方-1）不同的哈希值，那么只需要将0和2的32次方-1首尾相连就成了一个数字圆环。

>>假设有9个缓存，这时将其进行hash计算成一个数字，再根据他们的哈希值放到圆环对应数字点位上，这样9个缓存就已经有自己位置（如下图粉色小圆点即是缓存哈希）。

>>假设有4台缓存服务器，我们也对服务器进行哈希计算生成32位数字，这时再将服务器放在圆环对应位置上（如下图淡蓝色圆圈）。这样就组成了缓存与缓存服务器的物理结构图。[顺便提一下服务器的hash计算，一般的方法可以使用机器的IP地址或者机器名作为hash输入。]

>>如何将缓存映射到对应服务器上呢？一致性哈希算法采用单向就近原则：在这个环形空间中，如果沿着顺时针方向从缓存哈希出发，直到遇见一个服务器Node，那么就将该对象存储在这个Node上，因为缓存哈希和服务器的hash值是固定的，因此这个缓存必然是唯一和确定的。这样就能很方便根据哈希值找到对应服务器下的缓存对象。

用这种方式只需要维护node的hash值即可找到对应缓存，非常快速方便。而且假设有一个node宕机，则只需要将它维护的缓存hash放入下一个Node中即可；假设有新缓存加入，则只需要根据其hash值找最近的Node即可，缓存变化影响非常小。这是模式满足了前面提到的分布式缓存第二点要求“当缓存出现新增、删除时如何将变化的缓存同步到对应服务器”。

当然，上面描绘的只是一种理想的情况，各个节点在环上分布得十分均匀。正常情况下，当节点数量较少时，节点的分布可能十分不均匀，从而导致数据访问的倾斜，大量的 key 被映射到同一台服务器上。为了避免这种情况的出现，可以引入虚拟节点机制，对每一个服务器节点都计算多个 Hash值，每一个Hash值都对应环上一个节点的位置，该节点称为虚拟节点，而key 的映射方式不变，只是多了一步从虚拟节点再映射到真实节点的过程。这样，如果虚拟节点的数量足够多，即使只有很少的实际节点，也能够使 key分布得相对均衡。 

<转：http://blessht.iteye.com/blog/2124630>