preface

一致性hash最早提出, 是为了解决缓存服务器高热、节点增删导致缓存数据大量变动的问题, 减少大型web应用中的部分系统失败的影响.

在缓存服务中, 如果使用 hash(key) % n 的方式, 那么, 机器节点的增删 都会导致 所有节点重新映射到新的位置, 使用了一致性hash之后, 节点的添加/删除 只影响到部分的key.

theory

  1. 先看下一致性hash的实现

    • 将机器/bucket 映射到 circle/环 的多个伪随机分布的point/点, 也就是说 bucket对应着ciricle上的多个point
    • 将请求的key映射到hash 环的一个位置, 顺序遍历找到最近的一个有bucket的point
    • 当机器节点删除的时候: 机器节点在circle/环上响应的point也会删除, 那么, 之前在 point上的数据会迁移到原来point下一个有bucket的point
    • 当机器节点增加的时候: 机器节点/bucket在circle/环上添加映射的point/点, 将这个point 和 上一个smaller point上的资源迁移到这个point上. 因为是一个point是负责 (smaller_point, point] range的point的资源, 所以, 当在smaller_point和point中间插入一个point的时候, 就会产生分裂.

  2. 在衡量一致性算法的质量方面, 提出了四个特性:

    • Balance/: 对象均衡的分布在bucket里面。
    • Monotonicity/单调性: 缩扩容bucket情况下, key要么在原来的bucket的位置, 要么映射到新的bucket, 而不能在原来的bucket集合内迁移, 保证均匀分布
    • Spread/分散性: 同一个key被分散到不同bucket的严重程度, 因为client端看到的视图是不一致的, 所以, 同一个key, 在不同的client会被映射到不同的bucket
    • Load/负载： 是分散性在bucket的视角.

    好的一致性算法, 应该满足 高balance、monotonicity、低spread、低load.

problem

  1. 当节点太少的时候, 存在负载不均衡的现象, 也就是说, 大量数据/请求在同一台机器上, 这样, 高负载的机器crash的话, 大量缓存数据就丢失了, 为了解决这个问题, 可以引入虚拟节点的概念, 避免这个问题的产生.

apply

  1. 适合路由层/缓存层/域名服务器场景, hash并没有很好的数据迁移的亲和性, 所以 不适合存储层.
  2. redis tweproxy 一致性hash算法实现
  3. mapReduce运算的负载均衡
  4. 去中心化的DHT文件系统
  5. Dynamo系统

impl

  1. Ketama: 一致性hash的标准实现
  2. jump consistent hash, 实现简单, 但是没有实现节点挂掉不移除节点的场景,需要进行改造, 当选择的节点不可用的情况, 需要在进行hash, 并设置hash的上限

improve

  1. 负载有界的一致性哈希算法: 通过计算 每个服务器的平均负载*tension(压力百分比)=threshold(阈值), 当key hash 到环上找到指定的server, 需要判断server的当前load是否 超过 threshold, 超过了就找下一个. 通过这种方式, 避免了服务过载的情况. google使用这种方式节省了缓存带宽近8倍. 相关论文参考Reference.7, 实现可以参考

alternative

  1. Rendezvous hash: 也叫最高随机权重hash(hrw hashing): 存储的时候, 去除候选的bucket集合, 计算每个候选bucket的值, 选择最大的进行存储; 耗时较长, 如果优化的话, rebalance的效果较差. github glb就使用了 hrw hashing.

reference

  1. 一致性hash的论文
  2. 基于贪心算法的一致性哈希负载均衡优化
  3. vpch(virtual partition consistent hashing)
  4. 鸟窝blog
  5. jump consistent hash
  6. github load balancer
  7. google 负载游街一致性hash算法
  8. google 负载一致性hash blog
  9. Rendezvous hashing
  10. 不错的ppt