当前位置：首页 > article >正文

深入理解Redis

article 2024/12/24 17:59:41

1.数据结构类型

数据结构-SDS-简单动态字符串

Redis构建了一种新字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。 Redis未直接使用C语言的字符串，如：char* s = "hello"，本质是字符数组： {'h', 'e', 'l', 'l', 'o', '\0'}。因为C语言字符串存在很多问题：a. 获取字符串长度的需要通过运算; b. 非二进制安全; c. 不可修改;

而使用SDS存在以下优点： a. 获取字符串长度的时间复杂度为O(1); b. 支持动态扩容; c. 减少内存分配次数; d. 二进制安全;

数据结构-IntSet-整数集合

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

具备如下特点： a. Redis会确保Intset中的元素唯一、有序 b. 具备类型升级机制，可以节省内存空间; c. 底层采用二分查找方式来查询;

HT-哈希表/字典-结构

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict），类似java的HashTable，底层是数组加链表来解决哈希冲突。

ict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次操作键值对时都会检查负载因子（LoadFactor = used/size），满足以下两种情况时会触发哈希表扩容：

哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
哈希表的 LoadFactor > 5 ；
扩容大小为第一个大于等于used + 1的2^n;（比如used的是8，则扩容为8+1=9的最近的2的n次方16）

Dict每次删除元素时，也会对负载因子做检查，满足以下情况时会触发哈希表缩容：

当LoadFactor < 0.1 时，会做哈希表收缩：
收缩大小为第一个大于等于used 的2^n（比如used的是7，则缩容为7的最近的2的n次方8，但是如果used为8呢？刚好8那岂不是又要扩容？还是说不会出现）

Dict的rehash：

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。

因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。

Dict的渐进式rehash: Dict的rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。

渐进式rehash过程是这样的：

a. 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n

如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

b. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1];

c. 设置dict.rehashidx = 0，标示开始rehash;

d. 每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++(注意下一步没有展示)。直至dict.ht[0]的所有数据都rehash到dict.ht[1];

e. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存;

f. 将rehashidx赋值为-1，代表rehash结束;

注意：在rehash过程中，新增操作则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可确保ht[0]的数据只减不增，随rehash最终为空；

渐进式哈希过程

ZipList

ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

特征：

a. 列表节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低;

b. 如果列表数据过多，导致链表过长，可能影响查询性能;

c. 增或删较大数据时有可能发生连锁更新问题连锁更新：假设我们有N个连续长度为250~253字节之间的entry，因此entry的previous_entry_length属性用1个字节。如果新增一个entry长度超过253，则后续previous_entry_length需变为5个字节来存储，ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。