引用nwsm · 2020-09
“The key paper (Consistent Hashing with Bounded Loads) referenced in the video: [0].”
称它是视频里提到的关键论文
在一致性哈希上加负载上限,兼顾均衡与最少迁移
动态场景下把客户端均衡分配给服务器,既要分布均匀,又要在增删服务器或客户端时尽量少迁移。普通一致性哈希的均衡性不比随机分配好,n 个客户端 n 台服务器时会有服务器负载达到 Θ(log n / log log n)。这篇论文给出带用户指定均衡参数 c=1+ε 的算法,保证任何服务器负载不超过 ⌈cm/n⌉,而每次更新期望迁移的球数只比无容量约束的一般下界多一个 O(1/ε²) 的乘性因子(ε≤1),ε≥1 时只多 1+O(log c / c) 倍;n 个客户端 n 台服务器时可保证最大负载为 2,每次更新期望只迁移常数个客户端。
有人在技术讲解视频和系统设计讨论中把它称为关键论文,用来说明如何避免热点节点,例如搭配 rendezvous hashing 做有界负载的节点选择。
“The key paper (Consistent Hashing with Bounded Loads) referenced in the video: [0].”
“clients use rendezvous hashing for picking a node, with bounded load”