冰解的破-Redis

Redis

Redis 是一个 Key-Value 存储系统。和 Memcached 类似，它支持存储的 value 类型相对更多，包括 string(字符串)、 list(链表)、 set(集合)和 zset(有序集合)。这些数据类型都支持 push/pop、add/remove 及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。在此基础上，Redis 支持各种不同方式的排序。与 memcached 一样，为了保证效率，数据都是缓存在内存中。区别的是 Redis 会周期性的把更新的数据写入磁盘或者把修改操作写入追加的记录文件，并且在此基础上实现了 master-slave(主从)同步。

学习整理：

redis中hash slot是什么？

hash slot 是redis分布式部署，节点分配的一种方法
redis分布式部署其结构如下：

redis-cluster

Redis 集群采用每个节点拥有 1（主服务自身）到 N 个副本（N-1 个附加的从服务器）的主从模型，cluster内部master和slave之间的数据是异步复制的（提高性能，主要是在性能和一致性间的一个平衡）。
一个redis cluster有固定的16384个hash slot，slot被均匀的分配到cluster中的master节点上，而一个key具体的存储在哪个slot上，则是通过key的CRC16编码对16384取模得出的。

再讲讲hash slot的基本原理:

hash-slot

记录和物理机之间引入了虚拟桶层，记录通过hash函数映射到虚拟桶，记录和虚拟桶是多对一的关系；第二层是虚拟桶和物理机之间的映射，同样也是多对一的关系，即一个物理机对应多个虚拟桶，这个层关系是通过内存表实现的。

Redis 集群没有并使用传统的一致性哈希来分配数据，而是采用另外一种叫做哈希槽 (hash slot)的方式来分配的。redis cluster 默认分配了 16384 个slot，当我们set一个key 时，会用CRC16算法来取模得到所属的slot，然后将这个key 分到哈希槽区间的节点上，具体算法就是：CRC16(key) % 16384。

如果用户将新节点 D 添加到集群中，那么集群只需要将节点 A 、B 、 C 中的某些槽移动到节点 D 就可以了。
比如我想新增一个节点D，redis cluster的这种做法是从各个节点的前面各拿取一部分slot到D上。

与此类似，如果用户要从集群中移除节点 A ，那么集群只需要将节点 A 中的所有哈希槽移动到节点 B 和节点 C ，然后再移除空白（不包含任何哈希槽）的节点 A 就可以了。

因为将一个哈希槽从一个节点移动到另一个节点不会造成节点阻塞，所以无论是添加新节点还是移除已存在节点，又或者改变某个节点包含的哈希槽数量，都不会造成集群下线。

最后补充一个跟hash槽类似但应用更广的一个叫一致性hash的东东：

环形Hash空间
按照常用的hash算法来将对应的key哈希到一个具有2^{32次方个桶的空间中，即0~(2}32)-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。如下图

环形空间

把数据通过一定的hash算法处理后映射到环上

映射数据

将机器通过hash算法映射到环上

映射机器

对象与机器处于同一哈希空间中，这样按顺时针转动object1存储到了NODE1中，object3存储到了NODE2中，object2、object4存储到了NODE3中。

机器的删除与添加

节点（机器）的删除

删除节点

节点（机器）的添加

添加节点

通过按顺时针迁移的规则，那么object2被迁移到了NODE4中，其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析，一致性哈希算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说是非常合适的，避免了大量数据迁移，减小了服务器的的压力。

一致性哈希算法中，为了尽可能的满足平衡性，其引入了虚拟节点。

“虚拟节点”（ virtual node ）是实际节点（机器）在 hash 空间的复制（ replica ），一个节点（机器）对应了若干个“虚拟节点”，这个对应个数也称为“复制个数”，“虚拟节点”在 hash 空间中以hash值排列。

虚拟节点

映射关系：object1->NODE1-1，object2->NODE1-2，object3->NODE3-2，object4->NODE3-1。通过虚拟节点的引入，对象的分布就比较均衡了。那么在实际操作中，对象从hash到虚拟节点到实际节点的转换如下图：

时间转换

“虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设NODE1的IP地址为192.168.1.100。引入“虚拟节点”前，计算 cache A 的 hash 值：
Hash(“192.168.1.100”);

引入“虚拟节点”后，计算“虚拟节”点NODE1-1和NODE1-2的hash值：
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2