中间件|Redis 的底层数据结构中间件|redis

Redis 的底层数据结构一、redis快速的原因：1、在内存中进行操作 2、高效的数据结构底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示：

文章图片

1.Redis使用一个哈希表保存所有键值对，2.哈希桶中的元素保存的不是值的本身，而是指向具体元素的指针
具体元素都是RedisObject

文章图片

哈希冲突解决
a：Redis的hash表是全局的，所以当写入大量的key时，将会带来哈希冲突，已经rehash可能带来的操作阻塞
b：Redis解决hash冲突的方式，是链式哈希：同一个哈希桶中的多个元素用一个链表来保存
c：当哈希冲突链过长时，Redis会对hash表进行rehash操作。rehash就是增加现有的hash桶数量，分散entry元素。

【中间件|Redis 的底层数据结构】

文章图片

但是，这里依然存在一个问题，哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。
rehash机制
a：为了使rehash操作更高效，Redis默认使用了两个全局哈希表：哈希表1和哈希表2，起始时hash2没有分配空间
b：随着数据增多，Redis执行分三步执行rehash;
1，给hash2分配更大的内存空间，如是hash1的两倍
2，把hash1中的数据重新映射并拷贝到哈希表2中
3，释放hash1的空间
但是第二步涉及大量的数据拷贝（非常耗时，会阻塞redis）
为了解决这个问题Redis 采用了渐进式 rehash:集中迁移数据，改成每处理一个请求时，就从hash1中的第一个索引位置，顺带将这个索引位置上的所有entries拷贝到hash2中。
如下图所示：

文章图片

rehash 有两个hash table 分别是ht[0]和ht[1],默认使用ht[0],当ht[0]的桶个数超过某个值的时候，会把ht{1]初始化到ht[0]的2倍，
rehash的主要过程就是遍历ht[0]，取得key，然后将该key按ht[1]的桶的大小重新rehash，并在rehash完后将ht[0]指向ht[1],然后将ht[0]清空。在这个过程中rehashidx非常重要，它表示上次rehash时在ht[0]的下标位置。
rehashidx是下一个需要rehash的项在ht[0]中的索引，不需要rehash时置为-1。也就是说-1时，表示不进行rehash。

怎么复制到ht{1]

1.懒迁移:在每次对dict进行操作的时候执行一个slot的rehash
2定时迁移：每100ms里面使用1ms时间进行rehash。

怎么访问

需要对两张dict表做查询。唯一的优化判断是，当key在ht[0]不存在且不在rehashing状态时，可以速度返回空。如果在rehashing状态，当在ht[0]没值的时候，还需要在ht[1]里查找。
dictAdd的时候，如果状态是rehashing，则把值插入到ht[1]，否则ht[0]

压缩列表和跳表

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

文章图片

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。
跳表：
有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：

文章图片

redisCluster的数据分布结构体
每个节点都会维护一个 clusterState 结构，表示当前集群的整体状态，它的定义如下所示。

typedef struct clusterState { clusterNode *myself; /* 当前节点的clusterNode信息 */ .... dict *nodes; /* name到clusterNode的字典 */ .... clusterNode *slots[CLUSTER_SLOTS]; /* slot 和节点的对应关系*/ .... } clusterState;

它有三个比较关键的字段，具体示意图如下所示：

myself 字段，是一个 clusterNode 结构，用来记录自己的状态；
nodes 字典，记录一个 name 到 clusterNode 结构的映射，以此来记录其他节点的状态；
slot 数组，记录slot 对应的节点 clusterNode结构。

文章图片

clusterNode 结构保存了一个节点的当前状态，比如节点的创建时间、节点的名字、节点当前的配置纪元、节点的IP地址和端口号等等。除此之外，clusterNode结构的 link 属性是一个clusterLink结构，该结构保存了连接节点所需的有关信息**，比如**套接字描述符，输入缓冲区和输出缓冲区。clusterNode 还有一个 fail_report 的列表，用来记录疑似下线报告。具体定义如下所示。
clusterNode的信息

typedef struct clusterNode { mstime_t ctime; /* 创建节点的时间 */ char name[CLUSTER_NAMELEN]; /* 节点的名字 */ int flags; /* 节点标识，标记节点角色或者状态，比如主节点从节点或者在线和下线 */ uint64_t configEpoch; /* 当前节点已知的集群统一epoch */ unsigned char slots[CLUSTER_SLOTS/8]; /* slots handled by this node */ int numslots; /* Number of slots handled by this node */ int numslaves; /* Number of slave nodes, if this is a master */ struct clusterNode **slaves; /* pointers to slave nodes */ struct clusterNode *slaveof; /* pointer to the master node. Note that it may be NULL even if the node is a slave if we don't have the master node in our tables. */ mstime_t ping_sent; /* 当前节点最后一次向该节点发送 PING 消息的时间 */ mstime_t pong_received; /* 当前节点最后一次收到该节点 PONG 消息的时间 */ mstime_t fail_time; /* FAIL 标志位被设置的时间 */ mstime_t voted_time; /* Last time we voted for a slave of this master */ mstime_t repl_offset_time; /* Unix time we received offset for this node */ mstime_t orphaned_time; /* Starting time of orphaned master condition */ long long repl_offset; /* 当前节点的repl便宜 */ char ip[NET_IP_STR_LEN]; /* 节点的IP 地址 */ int port; /* 端口 */ int cport; /* 通信端口，一般是端口+1000 */ clusterLink *link; /* 和该节点的 tcp 连接 */ list *fail_reports; /* 下线记录列表 */ } clusterNode;

结束！
更多精彩分享请移步：IT学习道场
更多分享关注公众号【IT学习道场】