https://developer.aliyun.com/article/1629452
Highest Random Weight hashing它和 Rendezvous Hashing 指的是同一个家族算法
| 算法 | 发表时间 | 核心思路 | 查询复杂度 | 是否支持权重 | 权重均衡情况 | 是否需要维护额外状态 | 内存占用 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|---|---|---|---|---|---|
| Consistent Hashing Ring | 1997 | 将节点和 key 一起映射到哈希环上，key 归属顺时针遇到的第一个节点 | 通常 O(log N) |
支持，但通常依赖虚拟节点实现 | 中等，强依赖虚拟节点数量和分布设计 | 需要维护 ring、虚拟节点、排序结构 | 中到高，取决于虚拟节点数量 | 增删节点时迁移量小；去中心化；工程实现成熟；生态广 | 不加大量虚拟节点时负载容易不均；需要维护 ring 元数据；权重支持不够自然 | 传统缓存集群、分布式存储、已有 ring 体系的系统 |
| Rendezvous / HRW | 1996 | 对每个 key-node 组合计算分数，选得分最高的节点 |
朴素实现 O(N) |
支持，较自然 | 高，通常能较自然逼近权重比例 | 只需维护节点列表 | 低，只需节点列表和少量临时计算状态 | 不需要环；实现直观；天然支持 top-k；最小扰动性质好；加权相对自然 |
节点很多时 CPU 成本偏高；查询时通常需要遍历全部节点 | 中小规模节点集群、副本选择、需要 top-k 的场景 |
| Jump | 2014 | 通过跳跃式伪随机过程，直接将 key 映射到桶编号 | O(log N)，常数很小 |
原始版本不直接支持 | 不适用，原始版本没有原生加权能力 | 基本不需要，接近无状态 | 极低，几乎只依赖常量级状态 | 速度快；内存占用几乎为零；实现极简；分布较均匀；扩容时迁移量低 | 要求桶编号连续；不适合频繁删除形成空洞的节点集合；原始形式不擅长权重和复杂成员管理 | 分片路由、对象存储分桶、数据库 shard 映射 |
| Multi-probe | 2015 | 在 ring 上不依赖大量虚拟节点，而是对同一个 key 做多次 probe 决定归属 | 约为 O(K log N)，K 为 probe 次数 |
支持，通常仍结合虚拟节点/副本权重 | 中到高，通常优于传统 ring，但仍依赖参数调优 | 需要维护 ring 和 probe 策略 | 中，通常低于传统大量虚拟节点 ring | 比传统 ring 更省内存；兼顾 ring 思路和更好均衡性；probe 数可调 | 查询需要多次 hash；probe 太少时均衡性下降；仍需维护 ring 结构；实现复杂度高于 Jump | 想保留 ring 方案、但希望减少虚拟节点和内存占用的系统 |
| Maglev | 2016 | 为每个后端生成置换序列并构造全局查找表，转发时直接查表 | 查表 O(1) |
可支持，但一般需通过表构造策略表达 | 中等，取决于表构造方式和表大小 | 需要维护较大的 lookup table | 高，主要消耗在全局查找表 | 查找可做到 O(1)；负载均衡效果好；非常适合高吞吐转发路径；稳定性强 |
需要维护较大的 lookup table；成员变更时通常要重建表；实现偏工程化 | 四层负载均衡、服务网关、高性能数据面 |
| Anchor | 2020 | 通过 anchor/bucket 结构在保持一致性的同时降低更新和内存成本 | 接近 O(1) |
支持扩展到加权版本 | 高，加权扩展后通常也能保持较好均衡 | 需要维护 anchor 状态和 bucket 元数据 | 低到中，明显优于大表或大规模虚拟节点方案 | 一致性强；内存开销低；更新效率高；适合大规模节点池；扩缩容代价小 | 实现和状态管理较复杂；理解成本高于 Jump/HRW；工程落地门槛更高 | 大规模负载均衡、连接亲和、云网络和基础设施场景 |
| Dx | 2021 | 基于伪随机序列与数据结构优化，兼顾一致性、均衡性和更新性能 | 接近 O(1) |
支持，包括加权扩展 | 高，设计目标之一就是兼顾加权后的均衡性 | 需要维护少量辅助状态 | 低到中，在吞吐和状态规模间做折中 | 在负载均衡、扰动控制、吞吐和内存之间做了较好折中；支持大规模和加权扩展 | 相对较新，生态和工程成熟度不如 Jump/HRW/Maglev；行业验证较少 | 大规模云服务、异构节点、需要加权和快速更新的场景 |
| 算法 | Memory usage | Lookup time | Init time | Resize time |
|---|---|---|---|---|
| Ring | Θ(VW) | O(log2(VW)) | O(VW log2(VW)) | O(V log2(VW)) |
| Rendezvous | Θ(W) | Θ(W) | Θ(W) | Θ(1) |
| Jump | Θ(1) | O(ln(W)) | Θ(1) | Θ(1) |
| Multi-probe | Θ(W) | O(P log2(W)) | O(W log2(W)) | O(log2(W)) |
| Maglev | Θ(MW) | Θ(1) | Θ(MW) | Θ(MW) |
| Anchor | Θ(A) | O((ln(A / W))2) | Θ(A) | Θ(1) |
| Dx | Θ(A) | O(A / V) | Θ(A) | Θ(1) |
V: ring 中每个物理节点对应的虚拟节点个数W: 集群中的 working 节点数目P: Multi-probe 中的探针（哈希）个数M: Maglev 中每个节点在查询表中的位置数A: 集群中的所有节点数（包括 working 和非 working 的节点）
负载均衡相关算法中，除了 Maglev 之外，还有一类常见思路是 Consistent Hashing with Bounded Loads：
-
Bounded Loads：主要思路是，根据当前负载情况对所有节点限制一个最大负载，在一致性哈希中对 hash 环进行查找时将跳过达到最大负载限制的节点，通过把过载的请求转移到其他节点上来解决热点和不均衡问题：
R: 当前所有节点的总负载（正在处理的总请求数）T: 节点总个数L: 当前所有节点的平均负载，L = R / Tε: 一个参数，用于表示在平均负载基础上允许承受的额外负载上限，可以按实际需求设置。根据 Vimeo 分享的 经验，这个值通常推荐设置为0.25 ~ 1M: 节点的最大负载上限，M = L * (1 + ε) = R * (1 + ε) / T
一致性哈希在进行节点查找时，会额外检查命中节点的当前负载（正在处理的请求数）是否达到上限
M。如果达到上限，则跳过当前节点并继续向后查找。这种算法存在级联溢出，即在放置一个 key 时可能会连续跳过多个满载节点。Revisiting Consistent Hashing with Bounded Loads 一文中通过随机跳跃的方式缓解了这个问题。
权重问题 上面的方法没有区分节点权重。如果要支持加权节点，可以把容量上限改成按权重比例分配：
R: 当前所有节点的总负载（正在处理的总请求数）T: 所有节点的权重总和L: 当前所有节点的平均负载（基于权重的平均负载），L = R / TW: 当前节点的权重值ε: 一个参数，用于表示在平均负载基础上允许承受的额外负载上限M: 当前节点的最大负载上限，M = W * L * (1 + ε) = W * R * (1 + ε) / T
一致性哈希在进行节点查找时，会额外检查命中节点的当前负载（正在处理的请求数）是否达到上限
M。如果达到上限，则跳过当前节点并继续向后查找。 -
deterministic subsetting：有点像jump hash，该算法要求给所有服务分配连续ID。