真材实料的分布式资料-试读《大型分布式网站架构设计与实践》有感

dananhai 2014-10-05

  • 读后感

逐字逐句看完《大型分布式网站架构设计与实践》第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分布得相对均衡。 

这就是一致性哈希算法的原理,理论非常合理,所以才会受到这么广泛的应用,希望能给大家有所帮助。