一、redis的存储结构
1.1 存储结构
1.2 存储转换
二、字典(dict)实现
redis 数据库通过 dict 实现映射关系。key 的固定类型是 string,value 的类型有多种。
redis 中 KV 组织是通过字典来实现的;hash 结构当节点超过512 个或者单个字符串长度大于 64 时,hash 结构采用字典实现。
2.1 数据结构
dict 由哈希表 dictht + 哈希节点 dictEntry 组成。哈希表有两个,通常 ht[0] 使用,ht[1] 不使用;rehash 时,ht[0] 存储 rehash 之前的数据,ht[1] 存储新数据和 ht[0] 迁移来的数据。
// dict相当于C++的类的封装
typedef struct dict {
dictType *type; // dict 类型,封装成员函数
void *privdata; // 私有数据,连接的上下文
dictht ht[2]; // 散列表,一个存储当前数据,另一个 rehash 时使用。
long rehashidx; // 指示rehash到哪个位置了,它是从0开始的,如果rehashidx == -1,则rehash未进行。
unsigned long iterators; /* number of iterators currently running */
} dict;
// 哈希表
typedef struct dictht {
dictEntry **table; // entry 指针数组,保存 entry 的指针
unsigned long size; // 哈希表大小,2的n次幂
unsigned long sizemask; // 哈希表掩码 size-1,hash 取余运算优化成位运算
unsigned long used; // 实际存储元素 entry 的个数
} dictht;
// 哈希节点
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
1)字符串经过 hash 函数运算得到 64 位整数;
2)相同字符串多次通过 hash 函数得到相同的64位整数;
3)整数对 取余可以转化为位运算;sizemask是size-1,属于对字典的优化。因为散列表的存储是通过hash(key)%size=index
确定索引,sizemask是对取余长度的优化,将hash(key)%size
变成hash(key) &sizemask
,把除法优化为二进制的运算,从而提高执行速度,这种优化的前提是 数组的长度必须是2的n次幂(
2
n
2^n
2n)。
2.2 哈希冲突
哈希冲突指的是不同的键在哈希表中计算得到相同的哈希值,但它们的实际存放位置并不相同。在哈希表中,每个键通过哈希函数映射到一个桶(bucket)或槽(slot),存储在对应的位置上。
由于哈希表的大小是有限的,而键的数量可能是无限的,所以哈希冲突是不可避免的。
我们通过负载因子 LoadFactor = used / size
来衡量哈希冲突的程度, used 是数组存储元素的个数,size 是数组的长度;
负载因子越小,冲突越小;负载因子越大,冲突越大;redis 的负载因子是 1 .
2.3 扩容
- 如果负载因子 > 1 ,则会发生扩容;扩容的规则是翻倍;
- 如果正在 fork (在 rdb、aof 复写以及 rdb-aof 混用情况下)时,会阻止扩容;
- 但是此时若负载因子 > 5 ,索引效率大大降低, 则马上扩容;这里涉及到写时复制原理;
在写时复制中,当需要修改一个数据副本时,不会立即进行实际的复制操作,而是在修改发生时创建该数据的新副本。这样可以避免对原始数据进行修改,从而保持数据的一致性和完整性。
写时复制核心思想:只有在不得不复制数据内容时才去复制数据内容;
2.4 缩容
如果负载因子 < 0.1 ,则会发生缩容;缩容的规则是恰好包含used 的
2
n
2^n
2n;
恰好的理解:假如此时数组存储元素个数为 9,恰好包含该元素的就是 ,也就是 16;
为什么缩容的负载因子不是小于1?
因为缩容的负载因子是小于1的话会造成频繁的扩缩容,扩缩容都有分配内存的操作,内存操作变得频繁就会造成IO密集。
2.5 渐进式rehash
扩容和缩容都会导致rehash,因为映射算法发生了改变。
当 hashtable 中的元素过多的时候,因为redis是一个数据库,里面存储的数据非常多,不能一次性 rehash 到ht[1];这样会长期占用 redis,其他命令得不到响应;所以需要使用渐进式 rehash。
rehash步骤:
将 ht[0] 中的元素重新经过 hash 函数生成 64 位整数,再对ht[1] 长度进行取余,从而映射到 ht[1]。
渐进式规则:
1) 分治的思想,将 rehash 分到之后的每步增删改查的操作当中。
2)在定时器中,最大执行一毫秒 rehash ;每次步长 100 个数组槽位。
3)处理渐进式 rehash 的过程中,不会发生扩容和缩容。
2.6 scan 命令
SCAN命令的引入是为了解决,在某些情况下,需要对Redis数据库中的所有键进行遍历,以便进行某些操作或统计。然而,如果直接使用KEYS命令获取所有键,会对性能产生严重影响,因为KEYS命令会阻塞其他操作,并且在数据集较大时,返回所有键也会消耗大量内存。SCAN命令通过迭代方式,分批次逐步返回匹配的键,避免了一次性返回所有键的问题,从而减少了长时间阻塞的情况。
scan cursor [MATCH pattern] [COUNT count] [TYPE type]
redis在遍历数据期间,如果发生扩容或者缩容,造成映射算法发生改变,键的槽位可能会发生改变。那么继续遍历会发生错误。
因此 scan 采用高位进位加法的遍历顺序,这样 rehash 后的槽位在遍历顺序上是相邻的,对 sacn 那刻起已经存在的元素遍历不会出现重复和遗漏。例外:在scan过程当中,发生两次缩容的时候,会发生数据重复。
2.7 expire机制
redis的EXPIRE机制用于设置键的过期时间,即在指定时间后自动删除键。它是基于每个键的时间戳实现的。
1)EXPIRE key seconds
:设置键 key 的过期时间为 seconds 秒。当键到达过期时间后,Redis会自动删除该键。
2)PEXPIRE key milliseconds
:设置键 key 的过期时间为 milliseconds 毫秒。与 EXPIRE 命令类似,但时间单位为毫秒。
3)TTL key
:获取键 key 的剩余过期时间(以秒为单位)。如果键不存在或键没有设置过期时间,返回 -1。如果键已过期,返回 -2。
4)PTTL key
:获取键 key 的剩余过期时间(以毫秒为单位)。如果键不存在或键没有设置过期时间,返回 -1。如果键已过期,返回 -2。
redis有两种删除方式:
1)惰性删除:分布在每一个命令操作时检查 key 是否过期;若过期删除 key,再进行命令操作。
2)定时删除:在定时器中检查库中指定个数(25)个 key。
需要注意的对大对象(大key)的删除:
在 redis 实例中形成了很大的对象,比如一个很大的 hash 或很大的 zset,这样的对象在扩容的时候,会一次性申请更大的一块内存,这会导致卡顿;如果这个大 key 被删除,内存会一次性回收,卡顿现象会再次产生。
如果观察到 redis 的内存大起大落,极有可能因为大 key 导致的。
# 每隔0.1秒 执行100条scan命令
redis-cli -h 127.0.0.1 --bigkeys -i 0.1
三、跳表(skiplist)实现
跳表的特点
- 多层级有序链表
- 最底层包含所有的元素
- 支持二分查找,快速定位边界,然后在最底层找到范围内所有元素(区别红黑树)。
- 增删改查的时间复杂度都是 O(log2n)。
3.1 理想跳表
理想跳表是多层级有序链表,采取空间换时间的方法,每隔一个节点生成一个层级节点,模拟二叉树结构,最底层包含所有的元素。
但是如果对理想跳表结构进行增删操作,很可能改变跳表结构。若重构链表,代价极大。考虑用概率的方法来优化。每次增加节点的时候,1/2 的概率增加一个层级,1/4 的概率增加两个层级,以此类推。经过证明,当数据量足够大(256)时,通过概率构造的跳表趋向于理想跳表,并且此时如果删除节点,无需重构跳表结构,此时依然趋向于理想跳表。时间复杂度为 ( 1 − 1 n c ) × O ( l o g 2 n ) (1-\frac{1}{n^c} )\times O(log_2 n) (1−nc1)×O(log2n)
3.2 redis跳表
从节约内存角度出发,redis 考虑牺牲一些时间性能让跳表结构变得更加扁平。以循环双向链表结构实现,每次增加节点时,1/4 的概率增加一个层级,跳表的最高层级为 32。当节点数量大于 128 或者有一个字符串长度大于 64,则使用跳表结构。文章来源:https://www.toymoban.com/news/detail-620457.html
比如插入17,先比较第 4 层:(6, nil), 从 6 节点往下跳。比较第 3 层:(6, 25),从 6 节点往下跳。比较第 2 层:(9, 25),从 9 节点往下跳。比较第1层:(12, 19),在 12 节点后插入 节点17。
文章来源地址https://www.toymoban.com/news/detail-620457.html
#define ZSKIPLIST_MAXLEVEL 32 // 跳表的层级,
#define ZSKIPLIST_P 0.25 // 每个节点增加层级的概率
typedef struct zskiplistNode {
sds ele; // 节点存储的数据
double score; // 节点分数,排序使用
struct zskiplistNode *backward; // 前一个节点指针
struct zskiplistLevel { // 多级索引数组
struct zskiplistNode *forward; // 下一个节点指针
unsigned long span; // 索引跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头尾节点指针
unsigned long length; // 节点数量
int level; // 最大的索引层,默认是1
} zskiplist;
到了这里,关于redis 存储原理与数据模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!