10 | 一致哈希算法:如何分群,突破集群的“领导者”限制?
该思维导图由 AI 生成,仅供参考
- 深入了解
- 翻译
- 解释
- 总结
一致哈希算法是一种解决集群性能限制和数据迁移成本高问题的技术。传统哈希算法在集群数量变化时导致数据路由失败,需要大量数据迁移,而一致哈希算法通过引入虚拟节点和环形哈希空间,实现了节点动态扩缩容时数据迁移的最小化。文章详细介绍了一致哈希算法的原理和优势,以及如何通过虚拟节点解决数据访问分布不均匀的问题。通过实例分析,展示了一致哈希算法在节点增减时数据迁移量的显著减少,以及其在KV存储系统内部的简单路由寻址特点。总体而言,一致哈希算法具有较好的容错性和可扩展性,适用于简单的路由寻址场景。文章还提出了一个思考问题,即在多个Raft集群组成的KV系统中,如何设计一致哈希以实现整个系统在领导者节点故障后仍能稳定运行。这篇文章对一致哈希算法的原理和应用进行了深入浅出的介绍,对于读者快速了解一致哈希算法的概念和特点具有很高的参考价值。
《分布式协议与算法实战》,新⼈⾸单¥59
全部留言(44)
- 最新
- 精选
- 指尖以东置顶最近一直在看hash,老师可否讲讲虚拟节点的算法怎么做才能做到均衡,不然加的节点还是可能冷热不均衡的
作者回复: 加一颗星:这个主要是利用算法的随机性,在实际使用中,增加更多的节点,就会均衡了。为了帮助大家更直观的理解,我新增了一个演示程序(https://github.com/hanj4096/hash),来演示虚拟节点的均衡性的。具体效果如下: go run consistent-hash-vnode.go normal mode: node0 79.597960% , node1 87.818782% , node2 132.613261% vnode mode: node0 100.990099% , node1 98.679868% , node2 100.360036%
2020-05-0612 - Michael Tesla老师,我觉得课后题的答案是:数据要同时写入当前集群和下一个集群。某个Raft集群挂掉后,原本路由到这个集群的请求,现在都到下一个Raft集群去了。只要下一个Raft集群保存了上一个集群的数据,即使某个集群挂了,整个系统还能正常提供服务。
作者回复: 加一颗星:),相比“值到节点”的一级映射,可以做两级映射,“值到集群,集群到领导者节点”,通过Raft的节点故障容错能力,来避免数据迁移。在实际系统中,如果不采用具有节点故障容错能力的共识算法,一般不会直接将数据写入到下一个节点,而是会有个备份服务器,当节点故障,切换到备节点时,为了实现强一致性,能读取到最新数据,不仅要做一致性对比和数据迁移,还是实现双读,比较复杂。
2020-03-3020 - Purson老师,consistent-hash.go 和 hash.go 算法希望能分享一下。另外有个问题,虚拟节点还是映射了实际节点,比如一个节点有4个虚拟节点,如果1个实际节点挂了,是不是意味着另外3个相关的虚拟节点挂了,这样一致性hash算法还是会有很多不命中的情况。
作者回复: https://github.com/hanj4096/hash 是的,虚拟节点,是需要映射到实际节点的,实际节点挂了,虚拟节点就没有意义了。
2020-03-0417 - 星期一那TiDB 通过raft实现kv,region 来突破领导者单点问题,老师可以不可以串讲一下:TiDB、kafka、es 等常见分布式中间件 它们各自如何解决分布式的问题。
作者回复: 好,后续做个补充吧。
2020-03-04316 - Kvicii.Y4.当某一个节点故障了,该节点上的数据需要进行迁移吗??感觉只是影响了瞬间的读写,raft选举会很快进行吧,恢复了之后就有正常了,选举期间的读写访问顺延到下一节点这个才需要具体实现吧?
作者回复: 加一颗星:),是的,不需要,领导者选举很快的,在客户端超时重试间隔内,是能恢复的。
2020-03-247 - hello老师请教下,在环中加入节点以及去掉节点,那存储的数据是如何迁移到其它节点上的?
作者回复: 需要自己开发工具,在迁移过渡状态时,还要考虑多读,数据写入到新节点,但读,需要同时读2个节点,返回最新的数据。
2020-03-0437 - Sinclairs针对多个 Raft 集群, 需要有一个路由系统, 客户端通过这个路由系统来读写数据.. 1. 客户端写数据时, 根据哈希算法会得到一个值, 这个值可以落到集群A的哈希分片上, 假设集群B是集群A顺时针哈希分片后的下一个分片. 客户端写入数据时, 要保证集群A和集群B同时写入成功 2. 客户端读取数据时, 路由系统若检测到集群A不可用, 则去访问集群B, 也能获得数据. 集群A和相邻的集群B同时发生故障的概率是非常小的, 这样就能保证系统的稳定运行.
作者回复: 加一颗星:),考虑到Raft集群本身就有节点故障容错能力,当发生领导者选举后,映射到新的领导者,就可以了。
2020-03-0477 - 尿布为什么一个节点可以算出多个hash值?
作者回复: 加一颗星:),引入虚拟节点,比如,将包含主机名和虚拟节点编号的字符串,作为参数,来计算哈希值。
2020-03-126 - Theodore解开了我多年的疑惑。我说一致性hash怎么解决迁移带来的问题,还是靠运维啊
作者回复: 加一颗星:),扩容或缩容时,一般是通过运维工具来迁移的。
2020-04-204 - 沉淀的梦想当其中一个 Raft 集群领导者出现故障,读的时候还是可以从跟随者读,写的时候可以暂时先写到哈希环上的下一个集群中,等到重新选举领导者完成,再把数据捞回来。这么设计可以吗?
作者回复: 数据迁移,实际操作起来,还是有复杂度,需要流程化。其实,领导者选举是很快的,一般,写失败后,重试就可以了。
2020-03-0524