我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:白小姐 > 分布式算法 >

php的memcached分布式hash算法如何解决分布不均?crc32这个算法

归档日期:07-28       文本归类:分布式算法      文章编辑:爱尚语录

  php的memcached分布式hash算法,如何解决分布不均?crc32这个算法没办法把key值均匀的分布出去

  php的memcached分布式hash算法,如何解决分布不均?crc32这个算法没办法把key值均匀的分布出去

  有木有更妥当的方法?让分布式更均匀例如找到可以替代crc32的内置算法,(ps:计算成数字的)...

  例如找到可以替代crc32的内置算法,(ps:计算成数字的)展开我来答

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  当前很多大型的web系统为了减轻数据库服务器负载,会采用memchached作为缓存系统以提高响应速度。

  其实思想还是比较简单的,实现包括server端(memcached开源项目一般只单指server端)和client端两部分:

  client端是一个library,负责处理memcached protocol的网络通信细节,与memcached server通信,针对各种语言的不同实现分装了易用的API实现了与不同语言平台的集成。

  memcached的分布式主要体现在client端,对于server端,仅仅是部署多个memcached server组成集群,每个server独自维护自己的数据(互相之间没有任何通信),通过daemon监听端口等待client端的请求。

  而在client端,通过一致的hash算法,将要存储的数据分布到某个特定的server上进行存储,后续读取查询使用同样的hash算法即可定位。

  直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。

  但是问题也很明显,server总数不能轻易变化。因为如果增加/减少memcached server的数量,对原先存储的所有key的后续查询都将定位到别的server上,导致所有的cache都不能被命中而失效。

  为了解决这个问题,需要采用一致性hash算法(consistent hash)

  相对于取模的算法,一致性hash算法除了计算key的hash值外,还会计算每个server对应的hash值,然后将这些hash值映射到一个有限的值域上(比如0~2^32)。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到,则直接把具有最小hash值的server作为目标server。

  如果现在有一个写入cache的请求,首先计算x=hash(key),映射到环中,然后从x顺时针查找,把找到的第一个server作为目标server来存储cache,如果超过了2^32仍然找不到,则命中第一个server。比如x的值介于A~B之间,那么命中的server节点应该是B节点

  可以看到,通过这种算法,对于同一个key,存储和后续的查询都会定位到同一个memcached server上。

  此时,cache不能命中的问题仍然存在,但是只存在于B~F之间的位置(由C变成了F),其他位置(包括F~C)的cache的命中不受影响(删除server的情况类似)。尽管仍然有cache不能命中的存在,但是相对于取模的方式已经大幅减少了不能命中的cache数量。

  但是,这种算法相对于取模方式也有一个缺陷:当server数量很少时,很可能他们在环中的分布不是特别均匀,进而导致cache不能均匀分布到所有的server上。

  如图,一共有3台server – 1,2,4。命中4的几率远远高于1和2。

  为解决这个问题,需要使用虚拟节点的思想:为每个物理节点(server)在环上分配100~200个点,这样环上的节点较多,就能抑制分布不均匀。

  当为cache定位目标server时,如果定位到虚拟节点上,就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。

  另外,如果每个实际server的负载能力不同,可以赋予不同的权重,根据权重分配不同数量的虚拟节点。

  余数计算的方法简单,数据的分散性也相当优秀,但也有其缺点。 那就是当添加或移除服务器时,缓存重组的代价相当巨大。 添加服务器后,余数就会产生巨变,这样就无法获取与保存时相同的服务器, 从而影响缓存的命中率。

  后面提到使用Consistent Hashing来最大限度地减小服务器增减时的缓存重新分布。

本文链接:http://frankstella.net/fenbushisuanfa/958.html