我知我见之Redis数据结构

发表于 | 更新于 | 分类于 | 阅读次数：

VQguaq.jpg

主要参考文章Redis深度历险和Redis设计与实现

Redis底层数据结构

即redis的底层数据结构,包含其组成,扩展等原理
主要的几种数据结构为sds简单动态字符串,链表,字典,跳跃表,整数集合,压缩列表,对象等,此外还有hyperLoglog,bitMap位图等

sds

1
面试问题:https://juejin.im/post/5ca9d8ae6fb9a05e5c05c4e8?utm_source=gold_browser_extension

结构

sds是redis基于C语言的字符串进一步优化的

1
2
3
4
5
struct sdshdr {
	int len;// 已使用的字符串长度
	int free;// 未使用的字符串长度
	char buf[];// 字节数组，用于保存字符串本数据
};

VMsbFO.png
如上,redis的sds结构

与C字符串的对比

  1. 时间复杂度
    c字符串查询字符串长度的时间复杂度是O(N),需要对每个数进行计数
    sds的查询长度的时间复杂度是O(1),其维护了字段len来计算其长度
  2. 缓冲区溢出问题
    c语言不记录本身数据长度,在扩容时候,非常容易造成缓冲区溢出(即分配过多内存)
    而sds因为记录了本身的长度,在空间分配策略/扩容时能杜绝溢出的可能,在低于512M大小时,不会溢出(sds是先扩容,再修改)
  3. 修改的性能
    c语言在每次修改数据时(增删改),会从新分配内存,容易出现扩容内存溢出,截断内存泄漏等问题
    sds不需要反复的进行内存分配,因为sds采用的是空间预分配+懒性空间释放机制,(参见下方的扩容机制)

扩容机制

采用的是空间预分配和懒性空间释放策略

  1. 预分配
    在字符串长度小于1M的时候,其扩容是加倍扩容,即会保留100%的冗余空间
    在字符串长度超过1M之后,每次扩容只会多分配1M的冗余空间
  2. 懒性释放
    上述的冗余空间的意思是,不仅会分配新数据所需空间,还会分配free的空间备用
    而懒性空间释放,不是直接释放,而是将空出的空间记录在free上,以待后续使用

总结

VM6MDI.md.jpg

链表LinkedList

在redis中链表使用非常频繁,在其他数据结构也使用了链表,在基本数据类型中列表的本质就是链表,而非数组

结构

1
2
3
4
5
typedef struct listNode {
	struct listNode  *  prev; // 前置节点
	struct listNode  *  next; // 后置节点
	void  *  value;// 节点的值
}listNode;//链表节点
1
2
3
4
5
6
7
8
typedef struct list {
listNode  *  head;	// 表头节点
listNode  *  tail;	// 表尾节点
unsigned long len;	// 链表所包含的节点数量
void  * ( * dup)(void  * ptr);	// 节点值复制函数
void ( * free)(void  * ptr);	// 节点值释放函数
int ( * match)(void  * ptr,void  * key);// 节点值对比函数
} list;//链表

多个链表节点互联组成双向链表
VM6Qbt.jpg

特性

1.redis的链表特性,其一就是双端,如此获取前后节点的时间复杂度都是O(1)
2.无环,即表头或者表尾,总有一个prev或者next指向NULL,不会造成环状
3.链表自带计数器,其自带len属性,获取其长度的时间复杂度为O(1)

字典dirt

字段是redis使用最多的数据结构,字典的本质就是hash,结构类似于java的hashMap
全局所有的key,value也组成了一个字段,过期的key也组成了一个字典
zset的score和value的关系映射也用到了字典
字典的底层是由哈希表hash实现的,一个哈希表由多个哈希节点组成,一个哈希节点存放一个字典的键值对

结构

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;     // 哈希表数组
    unsigned long size;    // 哈希表大小
    unsigned long sizemask;//hash掩码
    unsigned long used;//已有节点数量
} dictht;//哈希表
1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
    void *key; // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;	// 值
    struct dictEntry *next;    // 指向下个哈希表节点，形成链表

} dictEntry;//哈希表节点
1
2
3
4
5
6
typedef struct dict {
    dictType *type;    // 类型特定函数
    void *privdata;    // 私有数据
    dictht ht[2];    // 哈希表(两个表,一个常用,一个rehash时使用)
    int rehashidx;     // rehash 索引(为-1时,不进行rehash)
} dict;//字典

如上
1.分别为哈希表,哈希节点和字典,可以看出字典对象的主体就是哈希表对象,此外还维护了一些诸如函数和rehash索引的数据
2.可以看出,字典的组成与java的hashmap组成基本一致,同属于数组+链表的结构
其中数组默认维护了两份哈希表,其一为常用存储,另外一个是在rehash的时候使用的

链表冲突

在多个键分配到同一数组的哈希表的同一索引上时,会发生冲突的,而哈希表对于这个冲突,采取的是链地址法来解决冲突的,没个哈希表节点维护了一个next指针,多个节点通过这个指针组成链表
VM6ZCD.jpg

渐进式rehash

redis中比较考究的一个知识点,就是渐进式rehash
在扩容/收缩的时候,需要重新计算hash值,并重新分配,非常耗时,所以redis便采取渐进式rehash策略
rehash使用到了字典的两个哈希表
redis的扩容条件:当hash中元素等于链表中元素时就会扩容
redis的缩容条件:只占有10%的时候

简单的过程如下:

1.在扩容时,会通过计算,得出新的需要的内存大小,并将此大小分配给h1表
2.然后将h0的已有键值对数据,同步到h1的表中去,此同步过程,需要重新计算hash值并分配位置
3.此时,释放h0表,然后将h1表置为h0表作为使用,并新开辟一个h1表做待用,如此完成渐进式rehash过程

VM6nvd.jpg
VM6mgH.jpg

上述是hash表的rehash过程,但需要知道的是,rehash过程,不是一蹴而就的,是分多次,渐进式的把数据同步过去的

具体的过程如下:

1.为字典的h1分配计算后的空间,让字典同时持有两块hash表
2.将字段持有的rehashidx标识置为0(默认为-1),标识rehash开始
3.在rehash的数据同步阶段,任何对h0表的在索引rehashidx上的键的修改,都会同步rehash到h1表中,并将rehashidx的值加1(rehashidx记录进度)
4.rehash过程中,任何查询/删除/修改,都会同时作用两张表去查询的,而新增会直接作用在h1表中,保证h0只减不增,随着rehash变成空表
5.rehash完成后,将rehashinx置为-1,标识rehash结束

VM6KKA.jpg

跳跃表

  • TODO