面试再被问到一致性 Hash 算法，这样回答面试官！

逃离我推掉我的手 2023-06-23 07:00 56阅读 0赞

公众号后台回复“**学习**”，免费获取精品学习资料

![format_png][]

扫描下方海报 **试听**

![format_png 1][]

本文来自会点代码的大叔的投稿

数据分片

✔︎ 先让我们看一个例子吧

我们经常会用 Redis 做缓存，把一些数据放在上面，以减少数据的压力。

当数据量少，访问压力不大的时候，通常一台Redis就能搞定，为了高可用，弄个主从也就足够了；

当数据量变大，并发量也增加的时候，把全部的缓存数据放在一台机器上就有些吃力了，毕竟一台机器的资源是有限的

通常我们会搭建集群环境，让数据尽量平均的放到每一台 Redis 中，比如我们的集群中有 4 台Redis。

那么如何把数据尽量平均地放到这 4 台Redis中呢？最简单的就是取模算法：

hash( key ) % N，N 为 Redis 的数量，在这里 N = 4 ;

![format_png 2][]

看起来非常得美好，因为依靠这样的方法，我们可以让数据平均存储到 4 台 Redis 中，当有新的请求过来的时候，我们也可以定位数据会在哪台 Redis 中，这样可以精确地查询到缓存数据。

数据分片会遇到的问题

但是 4 台 Redis 不够了，需要再增加 4 台 Redis ；那么这个求余算法就会变成：hash( key ) % 8 ；

![format_png 3][]

那么可以想象一下，当前大部分缓存的位置都会是错误的，极端情况下，就会造成 缓存雪崩。

一致性 Hash 算法

一致性 Hash 算法可以很好地解决这个问题，它的大概过程是这样的：

把 0 作为起点，2^32-1 作为终点，画一条直线，再把起点和终点重合，直线变成一个圆，方向是顺时针从小到大。0 的右侧第一个点是 1 ，然后是 2 ，以此类推。

对三台服务器的 IP 或其他关键字进行 hash 后对 2^32 取模，这样势必能落在这个圈上的某个位置，记为 Node1、Node2、Node3。

![format_png 4][]

然后对数据 key 进行相同的操作，势必也会落在圈上的某个位置；然后顺时针行走，可以找到某一个 Node，这就是这个 key 要储存的服务器。

![format_png 5][]

如果增加一台服务器或者删除一台服务器，只会影响 部分数据。

![format_png 6][]

但如果节点太少或分布不均匀的时候，容易造成 数据倾斜，也就是大部分数据会集中在某一台服务器上。

![format_png 7][]

为了解决数据倾斜问题，一致性 Hash 算法提出了【虚拟节点】，会对每一个服务节点计算多个哈希，然后放到圈上的不同位置。

![format_png 8][]

当然我们也可以发现，一致性 Hash 算法，也只是解决大部分数据的问题。

**END**

**如有收获，请划至底部，点击“在看”，谢****谢****！**

![format_png 9][]

欢迎长按下图关注公众号**石杉的架构笔记**

![format_png 10][]

**BAT架构经验倾囊相授**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy8xSjZJYkljUENMYUViNmliWmFtT2c1ZHlqTGZsb2tZQW95UW9pY282SDFmQ0l4RWVyUDg5OWRsTlg2Tm01d2lhN0VDZmlhMnNuaWJjalp0d3RCcmJKV2x3d0VBLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy8xSjZJYkljUENMWjhhN2s1RXNqV25KSlpyZG43SEpMa3lzZW1pYmRTVTZXWlJoS1FxZUNHZlZyaWEzM3NHVTFMYmQzWlVEUWgyZG04MG9acFZNeWZ2MmF3LzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Gam9EMnBOejhGRnJHY1FDbXBaenRIR0NFeEFubmMwbTRlc2lhaWJEZ1Q1ektsTHhYelYyQ2hEM091OWt2SHZENTM5M0swWUNEUTA3dGNIeWFvdXd3YlN3LzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Gam9EMnBOejhGRnJHY1FDbXBaenRIR0NFeEFubmMwbVcxQ2pTbjFQc1pZUTlBUVlIVlJqamtGb2t1cDJyZFVlYlZOaWMza2ljdmc0N3NrVWljMWR2RGpidy82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Gam9EMnBOejhGRnJHY1FDbXBaenRIR0NFeEFubmMwbTVURzBIRU9HYnc1VUZxU0J5NFpaMjBpYmh2ZWNhMGhYOUE0bjVzelhOckpwUFVQcWljM3FPaWF5dy82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Gam9EMnBOejhGRnJHY1FDbXBaenRIR0NFeEFubmMwbTZLeGZBZmYwZTdhMWljVzVpY3EzTmliTEdqaWEzeXZ4T2ljaFppYlpGMk9zNFNkSHpxVXMyNXZtTlh0QS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Gam9EMnBOejhGRnJHY1FDbXBaenRIR0NFeEFubmMwbUNyQ1FNbmhKWUVPZFZSSVk2czN2N0szbFhqaWFSUzFmaWJNbXV0c3p2ZlJFSHIyQ1M1RjFZNTFBLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Gam9EMnBOejhGRnJHY1FDbXBaenRIR0NFeEFubmMwbTA5cVdyQUFQRUNlNlRLVHNJOW02QmdXTG1VeW8wVjZPTG5oNjRCWWdpYkdBMVM4V05yaWJuc2pnLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9Gam9EMnBOejhGRnJHY1FDbXBaenRIR0NFeEFubmMwbVVqQndIeTV2aWNYbVhtTkhkN2liWjhwOUpzRkhmS3BZZmhrOTBwQWM1VmEzN3Q1aWIyT05mTENuQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy8xSjZJYkljUENMYW5HMm56alZab3YxVmlibVBYUjdsRGliRmpSZFR2SDFpYUR6OWljNEgzeFJaQ3o3Qk01NjNyRkZmdlJ1a3pYN3VoT3FYYzh5RGhFWnFpY0ZRLzY0MD93eF9mbXQ9cG5n?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy8xSjZJYkljUENMYkw1T2JpYlh4aWJzaWNPaWJ4bFZ6c05ZaWFLTmhCMEpVM29iUzdkWjFFSFU0VVhpY0ppY25LcGlhTHhyY01DblRreWJDOFh0NzZTWjhXR3JaRGVnLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png