分布式算法真是吊炸天 – memcached - 第287篇

一、Memcached分布式是如何实现的

memcached本身是一个非常轻量级的服务，不支持主辅同步，也没有集群的概念。但为了可扩展性，memcached服务器端和 memcached 客户端结合起来可以构成一个分布式系统。

在memcached分布式系统中，各个 memcached 节点之间无须通信，所以扩展性非常好。

->Memcached的分布式特点：

•1>: 服务器端不关心分布式：服务端的各个Memcached都是独立部署，之间不相互通信，这样服务端部署多个Memcached就很简单。

•2>: 依靠客户端来实现分布式：最简单的方式就是客户端拥有服务端所有连接地址，客户端通过key的hash值获取到对应的Memcached。

二、分布式算法

当向memcached集群存入/取出key/value时，memcached客户端程序根据一定的算法计算存入哪台服务器，然后再把key/value值存到此服务器中。也就是说，存取数据分二步走，第一步，选择服务器，第二步存取数据。

常用的算法有两种: 余数计算分散法 和 一致性Hash算法。

2.1 余数计算分散法

标准的memcached分布式算法

CRC($key)%N

BTW：CRC是一循环冗余算法，N：memcached服务器个数。

客户端首先根据key来计算CRC , 然后结果对服务器取模得到memcached服务器节点。

       这种算法取余计算简单，分散效果好，但是缺点是如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有 (N-1) 的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有 (N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。

2.2 一致性hash算法

       将server的hash值分配至0~2^32的圆环上, 用同样的方法求出存储数值键的hash值并映射到圆上. 然后从数据映射到的位置开始顺时针查找, 将数据存放至找到的第一台服务器上。如果超过0~2^32还找不到, 则将数据存放至第一台服务器。

2.2.1 算法过程

（1）先构造一个长度为0~2^32（2的32次幂）个的整数环（又称：一致性Hash环），根据节点名称的Hash值将缓存服务器节点放置在这个Hash环中，如上图中的node1，node2等；

（2）根据需要缓存的数据的KEY值计算得到其Hash值，如上图中右半部分的“键”，计算其Hash值后顺时针离node2近；

（3）在Hash环上顺时针查找距离这个KEY的Hash值最近的缓存服务器节点，完成KEY到服务器的Hash映射查找，如上图中离右边这个键的Hash值最近的顺时针方向的服务器节点是node2，因此这个KEY会到node2中读取数据；

2.2.2 添加节点

当缓存服务器集群需要扩容的时候，只需要将新加入的节点名称（如node5）的Hash值放入一致性Hash环中，由于KEY总是顺时针查找距离其最近的节点，因此新加入的节点只影响整个环中的一部分。如下图中所示，添加node5后，只影响右边逆时针方向的三个Key/Value对数据，只占整个Hash环中的一小部分。

BTW：删节节点或者服务器down机，影响的也只是顺时针的下一个节点。

2.2.3 算法优缺点

优点：动态的增删节点，服务器down机，影响的只是顺时针的下一个节点

缺点：当服务器进行hash后值较为接近会导致在圆环上分布不均匀，进而导致key的分布、服务器的压力不均匀。若中间某一权重较大的serverdown机，命中率下降明显；

2.2.4 算法对比

我们可以与之前的普通余数Hash作对比：采用一致性Hash算法时，当3台服务器扩容到4台时，可以继续命中原有缓存数据的概率为75%，远高于普通余数Hash的25%，而且随着集群规模越大，继续命中原有缓存数据的概率也会随之增大。当100台服务器增加1台时，继续命中的概率是99%。虽然，仍有小部分数据缓存在服务器中无法被读取到，但是这个比例足够小，通过访问数据库也不会对数据库造成致命的负载压力。

2.3 优化一致性hash算法（虚拟节点）

服务器的映射地点的分布非常的不均匀, 导致数据访问倾斜, 大量的key被映射到同一台服务器上，这时候需要在一致性哈希算法的基础上引入虚拟节点：

引入虚拟节点的思想，解决一致性hash算法分布不均导致负载不均的问题。一个真实节点对应若干个虚拟节点，当key被映射到虚拟节点上时，则被认为映射到虚拟节点所对应的真实节点上。

BTW：引入虚拟节点的思想，每个物理节点对应圆环上若干个虚拟节点（比如200~300个），当key hash到虚拟节点，就会存储到实际的物理节点上，有效的实现了负载均衡。

三、悟纤小结

总结：

（1）Memcached的分布式实现原理：服务端之间互不通信，分布式的实现是通过客户端使用一致性Hash算法进行实现的。

（2）分布式算法：余数计算分散法和一致性hash算法。

（3）余数分散法存在的问题：当节点变动的时候，缓存数据需要重新计算，命中率就会受到很大影响。

（4）一致性hash算法存在问题：数据分布不均匀，负载不均衡。

（5）优化的一致hash算法原理：加入虚拟节点，物理节点映射到若干个虚拟节点上，从而使得数据分布均衡分布在虚拟节点上，以此来实现负载均衡。

购买完整视频，请前往：http://www.mark-to-win.com/TeacherV2.html?id=287