知识卡片

结构图卡

Redis三种路由算法的对比:Hash、一致性哈希、分槽算法

理解等级:未标注

分布式缓存要做水平扩容,核心问题是”一个key该路由到哪个节点”,三种路由算法在这个问题上给出了不同答案,理解它们的关键在于比较”节点数量变化时,历史数据的迁移成本有多大”。Hash算法:hash(routekey)后对节点数取余得到目标节点,简单易懂,但一旦需要扩容(比如从32个库扩到64个库),路由目标会随之整体变化,几乎所有历史数据都需要全量迁移才能被正确命中,迁移成本极高。一致性哈希算法:把节点通过hash(节点)映射到一个0~2³²的圆环上,路由时对key做hash(routekey)后顺时针查找圆上最近的节点;扩容时只有新增节点逆时针方向的第一个节点上的数据会受影响,大部分历史数据依然可以正常命中,无须全量迁移,影响面远小于普通Hash算法——但一致性哈希存在数据倾斜问题:如果圆上节点太少、分布不均,可能导致大量数据集中命中同一个节点,高并发下这个节点容易因负载过大宕机,解决办法是引入虚拟节点(对同一个物理节点计算多次hash,映射到圆上多个位置,如192.168.1.1-01、192.168.1.1-02等),让数据分布更均匀。分槽算法:介于前两者之间的折中方案,以固定数量的Slot(Redis Cluster中是16384个)作为路由的中间层,节点伸缩需要迁移数据时,只需要移动相关的Slot本身即可、无须关心具体数据内容,且Slot数量从一开始就固定不会因节点伸缩而变化——同一个key从一开始就被路由到确定的Slot上,永远只会被路由到这个Slot;具体实现上,key先做CRC16运算再对16384取模得到具体Slot,再通过映射关系路由到目标节点的Slot上。三者的演进逻辑清晰:Hash算法牺牲了扩容灵活性换取实现简单,一致性哈希用更复杂的实现换取扩容时的局部影响,分槽算法则进一步把”迁移的对象”从数据本身抽象为固定数量的Slot,把数据管理成本降到最低。

结构图:

flowchart LR
    A[Hash算法<br/>简单,扩容需全量迁移历史数据]
    B[一致性哈希算法<br/>圆环映射,扩容仅影响局部节点<br/>需虚拟节点避免数据倾斜]
    C[分槽算法<br/>固定数量Slot为中间层<br/>伸缩只需迁移Slot,不关心具体数据]
    A -.复杂度递增,迁移成本递减.-> B
    B -.-> C
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《超大流量分布式系统架构解决方案:人人都是架构师2.0》第4章《大促抢购核心技术难题——读/写优化方案》"4.2.2 基于RedisCluster模式实现Sharding"节(源文件:OEBPS/Text/0009.xhtml) - 结论依据:原文说明Hash算法"节点产生的任何变动,几乎都需要对所有的历史数据进行全量迁移",一致性哈希"只有在圆上增加节点的地点逆时针方向的第一个节点上的相关数据会受到影响……无须全量迁移,影响面相对较小"但存在数据倾斜问题需引入虚拟节点,分槽算法"仅仅只需要移动相关的 Slot 即可,无须关心具体的数据……Slot 的数量从一开始就是固定的,不会因为节点的伸缩而变化",直接支撑本卡片结构。 - 原始内容:假设从原先的32个库水平扩容到64个库后,路由目标肯定也会随之发生变化……几乎都需要对所有的历史数据进行全量迁移……只有在圆上增加节点的地点逆时针方向的第一个节点上的相关数据会受到影响……分槽算法是以 Slot 为维度的,当节点伸缩需要对历史数据进行迁移时,仅仅只需要移动相关的 Slot 即可。