hash算法与一致性hash
source link: https://segmentfault.com/a/1190000040396960
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
hash算法与一致性hash
hash算法的应用很广泛，如安全加密、数据校验、唯一标识、散列函数、负载均衡、数据分片、分布式存储。这里简单聊一下hash算法在分布式下的数据存储，假如我们有三台redis集群节点A、B、C：
1，普通hash+取模算法
我在对数据进行查询的时候，会进行这样的运算:hash(key)%3来找到对应的机器。不过当我们数据量变大需要增加一台机器的时候，那这里相应会调整为:hash(key)%4，这样的话会将之前三个节点上所存储的数据与机器的对应关系都会影响到，同样某个节点出了故障进行了下线也会有同样的问题，这就会给后面的数据库造成很大的压力。显然这种路由算法在机器常常增减的场景下是不能接受的。我们接着看应对策略：
2，一致性hash算法
具体过程是这样的：先使用2的32次方构造一个虚拟环，然后将机器节点分布在这个环上:hash(节点ip)%2^32,这里是对2^32进行取模而不是对机器节点个数进行取模，当进行数据查找时进行hash(key)运算然后顺时针找到第一个遇到的机器节点。同样当我们增加一台机器时，也只会影响到1/3节点的数据而不至于像第一种方式影响到的有节点数据。解决了动态增减节点造成的影响但还是会存在数据分布不均匀的情况，可能会出现80%的数据都集中在其中一台机器上而另两台机器上的数据很少，这个时候的策略：
3，一致性hash+虚拟节点思想
在第2种思想的基础上，我们再对所有节点进行多次hash运算生成多个虚拟节点，只要hash运算的次数合适，那么每个真实节点对应的虚拟节点会交织分布的很均匀，如此一来数据在节点上的分布也会很均匀。这里的过程就是数据再定位到虚拟节点、虚拟节点再对应真实节点。
最后再提一下redis的 hash slot算法
redis定位key的过程是：CRC16(key)%16384找到对应的slot，而每个slot有相关的node,每个node会记录自身所属的slot也会记录其它node所属的slot，如果key就在自身node上则返回对应的value,如果不在则返回MOVED并返回这个key所在的node。也就是CRC16(key)%16384 -> slot -> node
Recommend
-
11
一致性hash算法 | 梦回故里一致性hash算法 我们都知道单机应用很简单，但是一旦涉及到多机应用，涉及到分布式，那么事情就会变得复杂，而一致性hash算法就是为了解决分布式中添加节点不造成大量节点数据重新分配的算法。 1997年，Karger...
-
14
v2-3244e076d29c02565e07a29be205e91a_1440w.jpg 讲一致性hash算法前，先简述一下求余hash算法：
-
14
本文已被Github仓库收录 https://github.com/silently9527/JavaCore 微信公众号：贝塔学Java 前言 在之前写了两篇关于缓存的文章《...
-
8
一致性 Hash 常用于缓解分布式缓存系统扩缩容节点时造成的缓存大量失效的问题。一致性 Hash 与其说是一种 Hash 算法，其实更像是一种负载均衡策略。 GroupCache 是 golang 官方提供的一个分布式缓存库，其中包含了一个简单的一致性 Hash...
-
3
如果在大型高并发系统需要数据的分布式存储 希望数据均匀分布可扩展性强那么一致性hash算法就可以完美解决这个问题 一致性hash算法的应用再很多领域 缓存 hadoop ES 分布式数据库 一致性Hash算法原理 一致性Hash算法是使用取...
-
4
Mr.Feng BlogNLP、深度学习、机器学习、Python、Go一致性hash算法及其实现简单讲述一致性hash算法。 大数据时代，单机数据库再也无法满足存储、访问需求...
-
5
作者 | kylinkzhang，腾讯 CSIG 后台开发工程师一致性 Hash 算法背景考虑这么一种...
-
6
聊聊一致性Hash算法代码实现 作者：顽石九变 2022-11-10 07:49:09 一致性hash算法常用于分布式缓存服务，把所有的服务节点进行hash，得到hash环上的位置。添加进服务的数据用同样的算法进行hash，然后从hash环上取...
-
9
1、场景描述 1.1 需求 假设，我们有三台缓存服务器，有3万张图片需要缓存，希望这些图片被均匀的缓存到这3台服务器上，以便它们能够分摊缓存的压力，即我们希望每台服务器能够缓存1万张左右图...
-
7
一致性hash算法原理及实践 大家好，我...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK