知识卡片
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
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。