注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小葫芦君(汉斯的博客)

博客迁移到新博客:https://blog.ssxingshou.com

 
 
 

日志

 
 
关于我

小小葫芦商城,为您提供高品质的商品,一流的产品,一流的包装服务,一流的物流服务,放心购买

网易考拉推荐

memcached分布式算法 哈希分布 一致性哈希  

2012-06-04 12:12:39|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

        分布式缓存系统里哈希算法承担着系统架构上的关键点。使用分布更合理的算法可以使得多个服务节点间的负载相对均衡,可以最大程度的避免资源的浪费以及服务器过载。使用一致性哈希算法,可以最大程度的降低服务硬件环境变化带来的数据迁移代价和风险。使用更合理的配置策略和算法可以使分布式缓存系统更加高效稳定的为我们整体的应用服务。

关键点思考
        一致性哈希算法在1997年由麻省理工学院提出,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。一致性哈希的 算法/策略来源于p2p网络,基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息, 并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中。所有这一切使得一致性哈希成为第一个实用的DHT算法。 其实纵观p2p网络应用的场景,在许多地方与我们的应用有很多相似的地方,可以学习借鉴。

 

memcached是缓存,所以数据不会永久保存在服务器上,而是保存在服务器内存。它不会释放已经分配的内存,当记录超时后客户端即无法命中该记录,其存储空间即可被重复使用,优先使用过期的记录空间,当空间不足时Least Recently Used(LRU),即“最近很少使用”机制来分配空间。memcached内部不会监视记录是否过期,而是在Get时查看时间戳,这种技术叫“Lazy expiration”,因此它不会在过期监视上花费CPU时间。memcached分布式算法由客户端API程序决定和实现的,(api根据存储用的key以及已知的服务器列表,根据key的hash计算将指定的key存储到对应的服务器列表上),这种分布式是memcached的最大特点.

起初算法根据余数计算分散
机制:键值HashCode / 服务器节点数目 =(求余) 服务器位置。【哈希原理: 两个集合间的映射关系函数,在我们通常的应用中基本上可以理解为 在集合A(任意字母数字等组合,此处为存储用的key)里的一条记录去查找集合B(如0-2^32)中的对应记录。(题外话:md5的碰撞或者说冲突其实 就是发生在这里,也就是说多个A的记录映射到了同一个B的记录)】当选择的服务器无法连接时,则将连接次数添加到键值后,再计算哈希值并再次尝试 (Rehash)连接选择的服务器。

这种方法很好,但是当增删服务器时,缓存的命中率的确很失败,大概降低到23%。web应用中,增删缓存服务器瞬间,缓存效率会急剧下降,负载会突然集中到数据库服务器。于是,新的事物诞生了。

优化后的算法一致性哈希(Consistent Hashing)

  1. 首先求出每个服务节点的hash,并将其配置到一个0~2^32的圆环(continuum)区间上。
  2. 其次使用同样的方法求出你所需要存储的key的hash,也将其配置到这个圆环(continuum)上。
  3. 然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务节点上。如果超过2^32仍然找不到服务节点,就会保存到第一个memcached服务节点上。

首先求出memcached服务器节点的哈希值,并将其配置到0~2的32次方的环上,然后用同样的方法求出数据键值的哈希值并映射到环上,然后从数据被映射到环的位置开始顺时针查找服务器位置,将数据保存在第一个找到的服务器上。如果没有找到则保持在第一个服务器上。
memcached分布式算法 哈希分布 一致性哈希 - hans(汉斯) - 汉斯的博客

在这种算法下,增加服务器只会影响该节点位置逆时针方向的第一台服务器上的键。为了解决服务器节点位置的映射不均问题,并进一步减小增减服务器带来的缓存重分布,引入了“虚拟机点”的思想,即,每个物理节点上分配几百个点。
由服务器台数n,和增加的服务器台数m,计算增加服务器后的命中率计算公式:(1-n/(n+m)) * 100

memcached 默认情况下采用了名为Slab Allocator的机制分配、管理内存。在之前的版本中,Memcached存储会导致很多内存碎片,从而加重了操作系统对内存管理的负担。Slab Allocator的基本原理是按照预先规定的大小,将分配的内存分割成特定长度的块, 以完全解决内存碎片问题。

  借用一张图说明一下:

memcached分布式算法 哈希分布 一致性哈希 - hans(汉斯) - 汉斯的博客

  Slab Allocation 将分配的内存分割成各种尺寸的chunk (块),并把大小相同尺寸的chunk分为一组,就如上图一样:分割了 88b,112b,144b等尺寸。其实Slab Allocation还有重复利用内存的功能,也就是说分配的内存不会释放,而是重复利用。

  当存储数据的时候,它会自动去查找最为匹配的chunk,然后将数据存储到其中。比如我存储数据的大小为110B,那么它会存储到112B的chunk中。

  上面的问题来了,我存储只需要110B,但是我存储到112B的chunk中。如下图(借用):
memcached分布式算法 哈希分布 一致性哈希 - hans(汉斯) - 汉斯的博客

  那么在110b的存储中会浪费2B的内存空间
     至于如何完全解决这个内存空间浪费的问题,还没有很好的方案,不过Memcached的 增长因子(Growth Factor)能够适当解决此问题。目前Memcached的默认增长因子 是1.25,也就是说会以原有的最大值基础上乘以1.25 来分配空间。

  评论这张
 
阅读(2586)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017