system-design-notes传统哈希取模为什么不适合大规模集群节点增删的数据迁移困境【免费下载链接】system-design-notesNotes of the book System Desgin Interview - An Insiders Guide项目地址: https://gitcode.com/GitHub_Trending/sy/system-design-notes在分布式系统设计中如何把数据均匀分散到成百上千台服务器是水平扩展绕不开的核心问题。开源笔记项目 system-design-notes 第 5 章《Design Consistent Hashing》就深入剖析了这一点传统「哈希取模」方案在节点数量变化时会导致大规模集群中大部分数据被迫迁移而**一致性哈希Consistent Hashing**通过哈希环将迁移量降到最低。本文将带你理解这个数据迁移困境以及一致性哈希与虚拟节点给出的答案。一、哈希取模固定集群下的完美方案在服务器数量固定的场景下取模法简单又高效对 key 做哈希再对服务器数量 N 取模就能得到数据应落在哪台服务器上。上图展示了serverIndex hash % 4的分配效果8 个 key 被均匀地分散到 4 台服务器上。对于缓存、负载均衡等场景这种方式查找快、实现简单是教科书级的入门做法。但问题在于——它隐含了一个前提服务器数量 N 永远不变。而真实的生产集群恰恰相反扩容、缩容、机器宕机每天都在发生。二、数据迁移困境一个节点下线全局数据大搬家当集群中某台服务器下线时N 从 4 变成 3取模公式随之改变。灾难就发生了几乎所有 key 的取模结果都会改变它们全部被重新映射到新的服务器上。如上图serverIndex hash % 3server 1 下线后原本落在它身上的 key 无一幸免其余服务器上的大量 key 也被迫重新分配图中红色标记的 key0、key3、key4、key5、key7。带来的连锁反应是缓存大面积未命中数据还在但取模公式变了客户端按新规则找到的新家里却没有数据大量数据搬运迁移期间带宽被占满集群响应变慢节点瞬间过载迁移风暴可能压垮本已健康的节点 结论取模法中任何一个节点的增删都会牵动全局迁移成本与集群总数据量成正比——这就是大规模集群无法容忍的原因。三、一致性哈希把线性取模换成哈希环一致性哈希的核心思想很巧妙不再用hash(key) % N而是把哈希值的空间首尾相接构成一个哈希环。1. 服务器与 key 都映射到环上用同一个哈希函数把服务器 IP 映射到环上的一个位置key 的哈希值同样落在环上。2. 顺时针查找第一个服务器key 的归属规则只有一条从 key 的哈希位置出发沿环顺时针走遇到的第一台服务器就是它的数据存储节点。这个设计让节点变化的影响范围被天然限制住了每台服务器只负责环上自己到下一台服务器之间的那段弧区间。四、迁移量骤降增删节点只影响相邻区间新增节点新服务器 s4 加入环上后只需要从前驱节点 s3手中接管 s3 与 s4 之间的那一段 key其余数据纹丝不动。移除节点server 1 下线后它负责的 key 只会顺时针迁移给下一台服务器 s2其他节点上的 key 完全不受影响。对比取模法一个节点变化、全局数据搬家一致性哈希把迁移量从N-1 台服务器的全部数据压缩到1/N 左右的局部数据这正是它成为大规模分布式系统标配的原因。五、虚拟节点解决环上负载不均基础版一致性哈希还有一个隐患服务器在环上的位置是哈希随机决定的分区弧长天然参差不齐——运气差的服务器可能接手一大段环成为热点运气好的则闲着。解决方案是虚拟节点每台物理服务器在环上不再只占一个点而是用多个虚拟节点均匀占位。如上图server 0 和 server 1 各自以多个虚拟节点s0_0、s0_1…s1_2分散占位。虚拟节点越多key 的分布越接近理想均匀标准差随虚拟节点数增加而减小。此外虚拟节点数量还能按物理机容量配置天然支持异构集群——大内存机器分配更多虚拟节点自动承担更多数据。六、总结从取模到哈希环的演进逻辑方案节点增删的迁移范围负载均匀性适用场景哈希取模几乎全局重映射均匀服务器数量固定的小集群一致性哈希仅约 1/N 局部迁移依赖节点分布需要动态扩缩容的集群一致性哈希 虚拟节点仅约 1/N 局部迁移虚拟节点数越多越均匀生产级大规模分布式系统 一句话记住取模法让变化扩散到全局哈希环让变化停留在局部——这就是节点增删数据迁移困境的终极答案。一致性哈希也是 Amazon DynamoDB、Apache Cassandra、Discord、Akamai CDN 等真实系统的基础设施。想继续深入可以阅读本章完整的笔记与配套架构图一致性哈希章节全文05. Consistent Hashing/Readme.md下一章 Key-Value Store 中的环形数据分片实践06. Key-Value Store/Readme.md水平扩展的入门背景01. Scaling/Readme.md【免费下载链接】system-design-notesNotes of the book System Desgin Interview - An Insiders Guide项目地址: https://gitcode.com/GitHub_Trending/sy/system-design-notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
system-design-notes：传统哈希取模为什么不适合大规模集群？节点增删的数据迁移困境
system-design-notes传统哈希取模为什么不适合大规模集群节点增删的数据迁移困境【免费下载链接】system-design-notesNotes of the book System Desgin Interview - An Insiders Guide项目地址: https://gitcode.com/GitHub_Trending/sy/system-design-notes在分布式系统设计中如何把数据均匀分散到成百上千台服务器是水平扩展绕不开的核心问题。开源笔记项目 system-design-notes 第 5 章《Design Consistent Hashing》就深入剖析了这一点传统「哈希取模」方案在节点数量变化时会导致大规模集群中大部分数据被迫迁移而**一致性哈希Consistent Hashing**通过哈希环将迁移量降到最低。本文将带你理解这个数据迁移困境以及一致性哈希与虚拟节点给出的答案。一、哈希取模固定集群下的完美方案在服务器数量固定的场景下取模法简单又高效对 key 做哈希再对服务器数量 N 取模就能得到数据应落在哪台服务器上。上图展示了serverIndex hash % 4的分配效果8 个 key 被均匀地分散到 4 台服务器上。对于缓存、负载均衡等场景这种方式查找快、实现简单是教科书级的入门做法。但问题在于——它隐含了一个前提服务器数量 N 永远不变。而真实的生产集群恰恰相反扩容、缩容、机器宕机每天都在发生。二、数据迁移困境一个节点下线全局数据大搬家当集群中某台服务器下线时N 从 4 变成 3取模公式随之改变。灾难就发生了几乎所有 key 的取模结果都会改变它们全部被重新映射到新的服务器上。如上图serverIndex hash % 3server 1 下线后原本落在它身上的 key 无一幸免其余服务器上的大量 key 也被迫重新分配图中红色标记的 key0、key3、key4、key5、key7。带来的连锁反应是缓存大面积未命中数据还在但取模公式变了客户端按新规则找到的新家里却没有数据大量数据搬运迁移期间带宽被占满集群响应变慢节点瞬间过载迁移风暴可能压垮本已健康的节点 结论取模法中任何一个节点的增删都会牵动全局迁移成本与集群总数据量成正比——这就是大规模集群无法容忍的原因。三、一致性哈希把线性取模换成哈希环一致性哈希的核心思想很巧妙不再用hash(key) % N而是把哈希值的空间首尾相接构成一个哈希环。1. 服务器与 key 都映射到环上用同一个哈希函数把服务器 IP 映射到环上的一个位置key 的哈希值同样落在环上。2. 顺时针查找第一个服务器key 的归属规则只有一条从 key 的哈希位置出发沿环顺时针走遇到的第一台服务器就是它的数据存储节点。这个设计让节点变化的影响范围被天然限制住了每台服务器只负责环上自己到下一台服务器之间的那段弧区间。四、迁移量骤降增删节点只影响相邻区间新增节点新服务器 s4 加入环上后只需要从前驱节点 s3手中接管 s3 与 s4 之间的那一段 key其余数据纹丝不动。移除节点server 1 下线后它负责的 key 只会顺时针迁移给下一台服务器 s2其他节点上的 key 完全不受影响。对比取模法一个节点变化、全局数据搬家一致性哈希把迁移量从N-1 台服务器的全部数据压缩到1/N 左右的局部数据这正是它成为大规模分布式系统标配的原因。五、虚拟节点解决环上负载不均基础版一致性哈希还有一个隐患服务器在环上的位置是哈希随机决定的分区弧长天然参差不齐——运气差的服务器可能接手一大段环成为热点运气好的则闲着。解决方案是虚拟节点每台物理服务器在环上不再只占一个点而是用多个虚拟节点均匀占位。如上图server 0 和 server 1 各自以多个虚拟节点s0_0、s0_1…s1_2分散占位。虚拟节点越多key 的分布越接近理想均匀标准差随虚拟节点数增加而减小。此外虚拟节点数量还能按物理机容量配置天然支持异构集群——大内存机器分配更多虚拟节点自动承担更多数据。六、总结从取模到哈希环的演进逻辑方案节点增删的迁移范围负载均匀性适用场景哈希取模几乎全局重映射均匀服务器数量固定的小集群一致性哈希仅约 1/N 局部迁移依赖节点分布需要动态扩缩容的集群一致性哈希 虚拟节点仅约 1/N 局部迁移虚拟节点数越多越均匀生产级大规模分布式系统 一句话记住取模法让变化扩散到全局哈希环让变化停留在局部——这就是节点增删数据迁移困境的终极答案。一致性哈希也是 Amazon DynamoDB、Apache Cassandra、Discord、Akamai CDN 等真实系统的基础设施。想继续深入可以阅读本章完整的笔记与配套架构图一致性哈希章节全文05. Consistent Hashing/Readme.md下一章 Key-Value Store 中的环形数据分片实践06. Key-Value Store/Readme.md水平扩展的入门背景01. Scaling/Readme.md【免费下载链接】system-design-notesNotes of the book System Desgin Interview - An Insiders Guide项目地址: https://gitcode.com/GitHub_Trending/sy/system-design-notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考