← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 7274.g · 生成模型:Hy3

一致性散列减迁移

理解等级:中级

普通散列按“对象ID散列 % 节点数”定位节点,一旦增删节点,几乎所有对象的映射都失效,需大规模迁移、阻塞服务。一致性散列是对它的改进:把散列值排成一个首尾相连的环,节点均匀落在环上,对象按散列值找环上顺时针最近的节点。

效果:增加节点时,仅其逆时针相邻节点的一部分对象迁过来;删除节点时,仅其对象逆时针迁给下一节点,其余对象映射不变,迁移量大幅下降。为在增删后维持负载均衡,再引入虚拟节点——每个物理节点拆成多个虚拟节点均匀散布环上,使负载尽量分摊。

用途:Swift 等对象存储用它做数据分布,兼顾可扩展性与负载均衡。区别:相比静态取模,它把“全量重映射”变成“局部邻域迁移”。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《数据存储架构与技术(第2版)》第8章《8.4.1 典型分布式对象存储系统》(源文件:extracted/数据存储架构与技术(第2版)/_epub-src/converter-master/example/312279/155.html) - 结论依据:原文对比普通散列在增删节点时引入巨大开销,从而引出一致性散列作为改进,支撑其减迁移作用。 - 原始内容:一致性散列算法是对普通散列算法的改进。普通散列算法对对象ID做散列运算并将散列结果对存储节点数取模,以此作为该对象的存储节点编号。普通散列算法在节点增加或节点删除时会给系统引入巨大的开销。