几种必须了解的分布式算法--一致性Hash算法

一致性Hash算法
1)问题描述
分布式常常用Hash算法来分布数据,当数据节点不变化时是非常好的,但当数据节点有增加或减少时,由于需要调整Hash算法里的模,导致所有数据得重新按照新的模分布到各个节点中去。如果数据量庞大,这样的工作常常是很难完成的。一致性Hash算法是基于Hash算法的优化,通过一些映射规则解决以上问题
2)算法本身
对于一致性Hash算法本身我也不做完整的阐述,有篇blog《一致性hash算法 - consistent hashing》 描述这个算法非常到位,我就不重复造轮子了。
实际上,在其他设计和开发领域我们也可以借鉴一致性Hash的思路,当一个映射或规则导致有难以维护的问题时,可以考虑更一步抽象这些映射或规则,通过规则的变化使得最终数据的不变。一致性hash实际就是把以前点映射改为区段映射,使得数据节点变更后其他数据节点变动尽可能小。这个思路在操作系统对于存储问题上体现很多,比如操作系统为了更优化地利用存储空间,区分了段、页等不同纬度,加了很多映射规则,目的就是要通过灵活的规则避免物理变动的代价
3)算法实现
一致性Hash算法本身比较简单,不过可以根据实际情况有很多改进的版本,其目的无非是两点:
节点变动后其他节点受影响尽可能小
节点变动后数据重新分配尽可能均衡
实现这个算法就技术本身来说没多少难度和工作量,需要做的是建立起你所设计的映射关系,无需借助什么框架或工具,sourceforge上倒是有个项目libconhash ,可以参考一下
以上两个算法在我看来就算从不涉及算法的开发人员也需要了解的,算法其实就是一个策略,而在分布式环境常常需要我们设计一个策略来解决很多无法通过单纯的技术搞定的难题,学习这些算法可以提供我们一些思路。

0 个评论

要回复文章请先登录注册