潘子浩

摘要：分布式存储系统中为了实现高可用、高性能和高扩展性，系统内数据布局和负载均衡是关键的技术问题。一致性哈希算法是解决此类问题行之有效的方法。将对比研究几种一致性哈希算法，包括基本和带虚拟节点的一致性哈希，微信存储系统中应用的一致性哈希和谷歌跳跃一致性哈希。对微信存储应用的一致性哈希进行了改进。

关键词：一致性哈希;虚拟节点;跳跃一致性哈希

Abstract： In order to achieve high availability， high performance， and high scalability in distributed storage systems， data layout and load balancing in the system are key technical issues. The consistent hashing algorithm is an effective way to solve such problems. Several consistent hashing algorithms will be studied and compared， including basic consistent hashing， consistent hashing with virtual nodes， consistent hashing used in WeChat storage systems and Google jump consistent hashing. The consistent hashing used in WeChat is improved.

Keywords： Consistent hashing; Virtual node; Jump consistent hashing

分布式存储系统发展过程中，遇到了多个方面的挑战，其一是数据分散存储在系统中，当系统面对海量读写请求时，如何保障系统的负载均衡避免出现数据倾斜。第二为应对系统流量的增长和萎缩，集群系统需要能够动态添加和删除节点，在保持负载均衡的同时实现数据的最小化迁移。一致性哈希算法因为具有良好的均衡性和一致性，在分布式存储系统中受到广泛的应用。

基本一致性哈希算法在Kager于1997年论文[1]中提出并其后应用于Danamo和Switf等系统后，衍生了多种优化改进的算法，包括带虚拟节点的一致性哈希，微信核心业务存储系统使用的一致性哈希，谷歌跳跃一致性哈希，maglev一致性哈希，负载有界一致性哈希，以及其他改进的一致性哈希算法等。对上述的部分一致性哈希算法，论文将从均衡性和一致性两个方面进行对比研究，并对微信存储系统使用的一致性哈希进行了优化。其中均衡性是指数据经过哈希后能尽可能分散到所有服务器节点中，每个服务器处理的数据相当，均衡的算法能最大化系统利用率。……