- 1、redis和hash算法的关系
- 2、hash算法的演进
- 2.1 最初hash算法
- 2.2 一致性hash算法
- 2.3 redis的 hash slot算法
主要是redis cluster的时候，对于请求，我们不能说随机的打到一台机器上，这样要是第一次写到A机器，第二次读的时候，读的是B机器，那么就会发生读不到的情况，这样缓存不就失去意义了么？
所以redis中hash算法的可以简单理解为，想办法如何让同一个请求，每一次都打到同一个机器上，不同请求分布到不同的机器上。
简单来说，就是hash取模，假设有N台机器，那么通过：
index = hash(key) % N
计算出来的index就是机器的序号，这样做简单明了，但是也是有弊端的，那就N如果变化了，会发生一些意外情况。
假设现在有3台缓存机器，A,B,C,机器分别分布在上面，此时，C宕机了，那么所有值钱打到C上面的缓存都会找不到，假设我们发现的，手动把N调整了：
调整前：A: key：0，3，5B: key：1，4，7C: key：2，5，8调整后：A： key：0，2，4，6，8B： key：1，3，5，7，9
举个栗子，之前key为3是是写在A上面的，现在计算出来key的hash是在B上面，这样也会导致查不到，如果量很大的情况就会导致缓存雪崩。
如果添加一个D也是类似，需要很多映射都已经错乱了，需要重新映射，那么就存在大量的缓存重建了。
从上面我们可以知道，根本的原因就是N会变化，我们需要在N变化的时候，影响更少量的数据。
于是就有人想出了环的概念，一致性hash算法。
一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。
举个栗子，将hash值得范围设置为0-2^32,假设他们分布在一个圆环上，然后有三台服务器A,B,C,那么也均匀分布圆环上。会计算key的hash值，落在圆环上，然后顺时针找到第一个节点，落在上面。
这样一来，要是A节点挂了，怎么办？
A节点挂了，那么原来的落在A节点的部分，会找到C，落在C上面，也就只影响直线A节点的那部分，就是1/3.
如果是加入节点的话，那么新的服务器直接挂在圆环的一个位置上，只会影响新的服务器到圆环漆面那一台服务器的部分数据。
由此可以看出，一致性hash算法，不管增减节点，其实都是影响一部分数据，有较高的容错性和拓展性。
但是这样做，还会有一个问题，就是热点数据的数据倾斜问题，假设只有两台机器，但是大部分的数据hash之后都落在了A节点的区间。
那这样就只有少数的会落到B节点上面，这样数据就会有可能发生严重的倾斜，所以就引入了���,���虚拟节点的机制。
所谓虚拟节点，即对每一个节点计算多个hash，每个计算结果位置都放一个服务节点，但是是虚拟的，一般是服务器ip或者主机+编号实现。例如上面的A，B节点，增加虚拟节点，A1，A2，B1，B2：
这样一来，key hash之后落的位置不变，但是如果定位到A，A1，A2都会定位到A上面，多了从虚拟节点到实际节点的映射，这样可以解决数据节点少的时候数据倾斜的问题。一般情况下，我们的虚拟节点大小都是大于等于32.
memcached也是使用了一致性hash算法。
redis没有使用上面说的一致性hash算法，而是使用了自己的hash slot算法，也是为了在多个master节点的时候，数据如何分布到这些节点上去，解决这个问题。
redis中hash提出槽的概念，也就是把数据hash分成多个槽，先放着。每个节点呢，相当于一个槽，就可以分得一部分hash值，对应hash值的数据就存在上面。
在redis cluster架构下，每个redis要放开两个端口号，比如一个是6379，另外一个就是加10000的端口号，比如16379，16379端口号是用来进行节点间通信的，也就是cluster bus的东西，集群总线。cluster bus的通信，用来进行故障检测，配置更新，故障转移授权。
cluster bus用了另外一种二进制的协议，主要用于节点间进行高效的数据交换，占用更少的网络带宽和处理时间。
redis cluster有固定的16384个hash slot，对每个key计算CRC16值，然后对16384取模，可以获取key对应的hash slot。
redis cluster中每个master都会持有部分slot，比如有3个master，那么可能每个master持有5000多个hash slot
hash slot让node的增加和移除很简单，增加一个master，就将其他master的hash slot移动部分过去，减少一个master，就将它的hash slot移动到其他master上去。
移动hash slot的成本是非常低的，这个是可以自动移动的，不需要手动操作。
在客户端的api，可以对指定的数据，让他们走同一个hash slot，通过hash tag来实现。
此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~
技术之路不在一时，山高水长，纵使缓慢，驰而不息。