侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

Redis的基本数据结构及原理

林贤钦
2021-04-12 / 0 评论 / 0 点赞 / 600 阅读 / 10,007 字
温馨提示:
本文最后更新于 2021-05-25,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Redis有5种基本数据结构,分别为:string(字符串)、list(列表)、hash(字典)、set(集合)和zset(有序集合)

本文针对Redis的5种数据结构源码级的分析,包括跳表,压缩表,快速列表,rehash等。

1 string(字符串)

字符串string是Redis最简单的数据结构,在内存中它是以字节数组的形式存在的。Redis的字符串叫"SDS",也就是simple Dynamic String。它的结构是一个带长度的字节数组。

struct SDS<T> {
	T capacity;//数组容量,也就是所分配的数组长度,与内存分配相关
	T len;//数组实际长度
	byte flags;//特殊标志位,不用理
	byte[] content;//数组内容
}

如代码所示,content里面存储了真正的字符串内容,而capacity和len就类型java的ArrayList结构

因为字符串是可以修改的字符串,它要支持append操作,如果数组没有冗余空间,那么追加操作必然涉及分配新数组,然后将旧内容复制过来,再append新内容,如果字符串过长,内存的分配和复制开销就会非常大。

上面的SDS结构使用了泛型T。为什么不直接使用int?因为当字符串比较短时,len和capacity可以使用byte和short来表示,Redis为了对内存做到极致的优化,不同的字符串使用了不同的结构体来表示。

embstr&raw

Redis的字符串有两种存储方式,在长度特别短时,使用embstr形式存储,当长度超过44字节时,会使用raw形式存储。

两种类型有什么区别呢?为什么分界线是44字节呢?

首先我们先研究一下Redis对象头结构,所有的Redis对象都有下面这个对象头结构

struct RedisObject{
	int4 type;   //4bits   ----- 对象的类型 如zset、set、hash等
	int4 encoding;   //4bits ----- 对象编码 如ziplist、intset、skiplist等
	int24 lru;   //24bits   ----- 对象的热度
	int32 refcount; //4bytes ----- 引用计数
	void *ptr;    //8bytes,64-bit system ----- 对象的body
}robj;

可以算出任何一个redis的对象头都需要占用4bits+4bits+24bits+4bytes+8bytes=16个字节的存储空间。

接着我们看SDS的结构体大小,在字符串比较小的时候,SDS对象头结构的大小是capacity+3.

struct SDS{
	int8 capacity; //1byte
	int8 len; //1byte
	int8 flags; //1byte
	byte[] content; //内联数组,长度为capacity
}

意味着分配一个字符串的最小空间占用19字节。

embstr存储形式是这样的一种存储形式,它将RedisObject对象头结构和SDS对象连续存在一起,使用malloc方法一次分配,而raw的存储形式不太一样,它需要使用两次malloc方法,两个对象头在内存地址上一般是不连续的。
而内存分配器jemalloc、tcmalloc等分配内存大小单位都是2/4/8/16/32/64字节,而一个字符串最小的固定长度需要占用19字节+一个字节NULL结尾,所以jemalloc最少会分配32个字节,如果字符串稍微大一点,就分配64字节的空间。而如果字符串总体(固定结构+NULL+数组)大小超过64位,Redis会认为这是一个大字符串,不再使用embstr形式存储,而该使用raw形式。

这也就是为什么是44个字节了,一个字符串加上NULL结尾最少占用20个字节,而Jemalloc最多分配64字节

而raw的存储则不是连续的

raw存储结构

作用
常见的用户就是缓存用户信息,将用户的信息使用JSON序列化成字符串,取数据的时候反序列化,还有就是能做全局计数器,统计一些信息,不过它的范围是long的最大值和最小值之间,超过这个范围,Redis会报错。

2 list(链表)

Redis的链表相当于java的LinkedList,注意它是链表而不是数组。这意味着list的插入和删除操作非常快,时间复杂度为O(1),但索引定位很慢,时间复杂度为O(n).

Redis早期版本存储list列表数据结构使用的是压缩列表ziplist和普通的双向列表linkedlist,也就是说当元素少的时候用ziplist,当元素多的时候用linkedlist。

//链表的节点
struct listNode<T>{
	listNode *prev;
	listNode *next;
	T value;
}
//链表
struct list{
	listNode *head;
	listNode *tail;
	long length;
}

压缩列表

压缩列表是一块连续的内存空间,元素之间紧挨着存储,没有任何冗余空隙。

struct ziplist<T> {
	int32 zlbytes; //整个压缩列表占用的字节数
    int32 zltail_offset;//最后一个元素距离压缩列表起始位置的偏移量,用于快速定位到最后一个位置的元素
    int16 zllength;//元素个数
    T[] entries; // 元素内容列表,一次紧凑存储
    int8 zlend; //标志压缩列表结束,值恒为 0xFF
}

list是支持双向遍历的,所有才有ztail_offset这个字段,来快速定位到最后一个元素,然后倒着遍历。

entry块随着容纳的元素类型不同,也会有不一样的结构。

struct entry{
    int<var> prevlen; // 前一个entry的字节长度
    int<var> encoding; //元素类型编码
    optional byte[] content; //元素内容
}

当压缩列表倒着遍历时,需要通过prevlen这个字段快速定位下一个元素的位置,当字符串长度小于254时,使用一个字节表示,如果达到或超过254,就用5个字节表示。

增加元素
因为ziplist都是紧凑存储的,没有冗余空间,这意味着插入一个新的元素就需要调用realloc扩展内存。取决于内存分配器算法和当前ziplist内存大小,realloc可能会重新分配新的内存空间,并将之前内容一次性拷贝到新的地址,也可能在原有的地址上进行扩展,这时就不需要进行旧内容的内存拷贝。

如果ziplist占据内存太大,重新分配内存和拷贝内存就会有很大的消耗,所有ziplist不适合存储大型字符串,存储的元素也不宜过多。

级联更新

每个entry都会有一个prevlen字段存储前一个entry的长度,如果内容小于254字节,prevlen就会用一个字节存储,否则就用5字节存储。如果某个entry经过修改,从253变成了254,那么它下一个entry的prevlen字段就需要更新,那么如果下一个entry本来的长度也是250-253,经过修改也变成大于254了,这样后面的entry就需要修改了,以此类推,就是级联更新了。

快速链表

考虑到链表的附加空间太高了,prev和next指针就需要占16字节,另外每个节点的内存都是单独分配的,会加剧内存的碎片化,影响内存管理效率。后来Redis新版对列表的数据结构进行改造,使用quicklist代替ziplist和linkedlist。

quicklist是ziplist和linkedlist的混合体,它将linkedlist按段切分,每一段用ziplist让存储紧凑,多个ziplist之间使用双向指针串接起来。

struct quicklistNode{
    quicklistNode *prev;
    quicklistNode *next;
    ziplist* zl; //指向压缩列表
    int32 size; //ziplist的字节总数
    int16 count; //ziplist中的元素数量
    int2 encoding; //存储形式,原数组还是LZF压缩存储
}
struct quicklist{
    quicklistNode* head;
    quicklistNode* tail;
    long count; //元素总数
    int nodes; //ziplist节点的个数
    int compressDepth;//LZF算法压缩深度
    ...
}

为了进一步节约空间,Redis还会对ziplist进行压缩存储,使用LZF算法压缩,可以选择压缩深度。

每个ziplist存了多少元素?

quicklist内部默认单个ziplist长度为8KB,超过这个字节数,就会另起一个ziplist。ziplist的长度由配置参数list-max-ziplist-size决定。

压缩深度
quicklist默认的压缩深度为0,也就是不压缩,压缩的实际深度由配置参数list-compress-depth决定,为了支持快速的push/pop操作,quicklist的首位两个ziplist不压缩,此时压缩深度为1.如果压缩深度为2,就表示quicklist的收尾第一个ziplist以及首尾第二个ziplist都不压缩。

压缩深度为1的情况如图:

压缩深度为2的情况如图:

紧凑列表

Redis5.0版本又引入一个新的数据结构listpack,它是对ziplist结构的改进版,在存储空间上会更加节省,而且结构上也比ziplist更加精简。listpack的整体形式和ziplist比较相近。

struct listpack<T>{
    int32 total_bytes; //占用的总字节数
    int16 size;   // 元素个数
    T[] entries;  //紧凑列表的元素列表
    int8 end;     //同zlend一样,恒为0xFF
}

listpack和ziplist的结构几乎一模一样,只是少了zltail_offset字段,ziplist通过这个字段定位出最后一个元素的位置,用于逆序遍历,但是listpack可以通过其他方式定位出最后一个元素的位置,所以zltail_offset字段就被省略了。

struct lpentry{
    int<var> encoding; //当前元素的编码
    optional byte[] content; //当前元素的内容
    int<var> length;//当前元素的长度
}

listpack通过total_bytes字段和最后一个元素的长度字段可以计算出最后一个元素的位置,所以不用zltail_offset字段。

元素的编码长度

listpack的长度字段使用varint进行编码,不同于skiplist长度的编码只能1个字节或者5个字节,listpack元素长度的编码可以是1~5个字节中的任一长度。

同UTF8编码一样,它通过字节的最高位是否为1来决定编码的长度

级联更新

在ziplist中,会存在级联更新行为,但listpack不存在级联更新行为,元素与元素之间完全独立,不会因为一个元素的长度变长导致后续的元素内容收到影响。

取代ziplist还需要时日

listpack的设计目的是用来取代ziplist,不过当前还没有做好替换ziplist的准备,因为有很多兼容性的问题需要考虑。ziplist在Redis的数据结构使用太广泛了。替换起来复杂度会非常高。listpack目前只用在新增加的Stream数据结构中。

list作用

右进左出:队列

队列是先进先出的数据结构,常用于消息排队和异步的逻辑处理,它会确保元素的访问顺序。

右进右出:栈

栈是先进后出的数据结构,跟队列相反。拿Redis的list链表来做栈的业务场景并不多见。

3 hash(字典)

Redis的字典相当于Java语言里面的HashMap,它是无序字典,内部存储了很多键值对。实现结构上与Java的HashMap也是一样的,都是“数组+链表”二维结构。

第一维数组位置发生碰撞时,就会将发生碰撞的元素使用链表串接起来

不同的是,Redis的字典的值只能是字符串,另外他们rehash的方式也不太一样,因为Java的HashMap在字典很大的时候,rehash是一个耗时的操作,需要一次性全部rehash,Redis为了追求高性能,又不能阻塞服务,所以采用了rehash策略。

rehash

字典结构内部包含两个hashtable,通常情况下只有一个hashtable是有值的,但是在字典扩容缩容时,需要分配新的hashtable,然后进行渐进式搬迁,这时候两个hashtable存储分别是旧的hashtable和新的hashtable。等搬迁完成后,旧的hashtable被删除,新的hashtable取而代之。

字典数据结构的精华就落在了hashtable结构上了

struct dictEntry{
    void* key;
    void* val;
    dictEntry* next;//链接下一个entry
}
struct dictht{
    dictEntry** table;//二维
    long size; //第一维数组的长度
    long used; //hash表中的元素个数
}

渐进式rehash

大字典的扩容是比较耗时的,需要申请新的数组,然后将旧字典所有链表中的元素重新挂接到新的数组下面,这是一个o(n)级别的操作,作为单线程的Redis很难承受这样一个耗时的过程,所以Redis使用渐进式rehash小步搬迁。

dict *dictAddRaw(dict *d,void *key,dictEntry **existing){
    long index;
    dictEntry *entry;
    dictht * ht;
    //这里进行小步搬迁
    if(dictIsRehashing(d)) _dictRehashStep(d);
    if((index = _dictKeyIndex(d,key,dicthashKey(d,key),exising))==-1)return NULL;
    //如果字典处于搬迁过程中,要将新的元素挂接到新的数组下面
    ht =dictIsRehashing(d)? &d->ht[1] : &d->ht[0];
    entry -> next = ht->hable[index];
    ht->table[index]=entry;
    ht->used++;
    dictSetKey(d,entry,key);
    return entry;
}

搬迁操作埋伏在当前字典的后续指令中,有可能客户端闲下来了,没有后续指令来触发这个搬迁,这时候Redis是会有定时任务来进行主动搬迁的。

既然是两个hashtable,那么在查找的过程中,是如何定位的?

当key在ht[0]不存在且不在rehashing状态时,可以速度返回空。如果在rehashing状态,当在ht[0]没值的时候,还需要在ht[1]里查找。

dictAdd的时候,如果状态是rehashing,则把值插入到ht[1],否则ht[0].

func get(key) {
	let index = hash_func(key)% size;
	let entry = table[index];
	while(entry != NULL){
		if enry.key ==target {
			return entry.value;
		}
		entry =entry.next;
	}
}

hash_func会将key映射为一个整数,不同的key会被映射成分布比较均匀散乱的整数。

扩容条件

正常情况下,当hash表中元素的个数等于第一维数组的长度时,就会开始扩容,扩容的新数组是原数组大小的2倍。不过如果Redis正在做bgsave时,为了减少内存页的过多分离,Redis尽量不去扩容,但是如果hash表已经非常满了,元素的个数已经达到第一维数组长度的5倍,说明hash表已经过于拥挤了,这时候就会强制扩容。

缩容条件

当hash表因为元素逐渐被删除变得越来越稀疏时,Redis会对hash表进行缩容来减少hash表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的10%。缩容不会考虑Redis的bgsave。

bgsave:在后台异步保存当前内存的数据到磁盘文件中。

4 set(集合)

Redis的集合相当于Java的HashSet,它内部的键值对是无序的,唯一的,所有的value都是NULL。

作用

set结构可以用来存储某活动中中间的用户id,有去重功能,可以保证一个用户不会中间两次。

5 zset(有序列表)

zset可能是Redis提高最有特色的数据结构,它类似Java的SortedSet和HashMap的结合体,一方面它是一个set,保证内部value的唯一性,另一方面,它可以给每个value赋予score,代表每个value的排序权重,它的内部实现用的是一种叫做“跳跃表”的数据结构。

这就是跳跃表的示意图,图中只花了几层。Redis的跳跃表共有64层,可以容纳2 64个元素。每个kv块都对应如下面的代码块中的zslnode结构,kv header也是这个结构,只不过value字段是NULL值,无效的,score是Double.MIN_VALUE,用来垫底的。

struct zslnode{
    string value;
    double score;
    zslnode*[] forwards; //多层连接指针
    zslnode* backward; // 回溯指针
}
struct zsl{
    zslnode* header;   //跳跃列表的头指针
    int maxLevel;		// 跳跃列表当前的最高层
    map<String,zslnode*> ht;	//hash结构的所有键值对
}

kv之间使用指针穿起来形成了双链表结构,他们是有序排序的,从小到大,不同的kv曾高可能不太一样,层数越高kv越少,同一层的kv会使用指针串起来。每一个层的遍历都是从kv header触发。

查找过程

如图所示,我们需要定位到蓝色的kv,需要从header的最高层开始遍历找到第一个比“我”小的节点, 然后从这个节点开始降一层遍历找到第二个节点,以此类推降到最底层找到期望节点。

随机层数

对于每一个新插入的节点,都需要调用一个随机算法给他分配一个合理的层数,直观上期望目标是50%的概率分配到Level_1,25%的概率被分配到level_2,12.5%的概率被分配到level_3,以此类推,2-63的概率被分配到顶层,因为每一层的晋升率是50%。

int zslRandomLevel(void){
    int level =1;
    while((random()&0xFFFF)<(ZSKIPLIST*0xFFFF))level +=1;
    return level<ZSLKIPLIST_MAXLEVEL ? level : ZSKIPLIST_MAXLEVEL;
}

一般层数不会很高,所以遍历的时候从底层开始往下遍历会非常浪费,跳跃表会记录当前的最高层数maxLevel,遍历的时候从这个maxLevel开始遍历。

插入过程

首先我们在搜索合适的插入点过程中将“搜索路径”找出来,然后就可以开始创建新节点。创建的时候需要给这个节点分配一个层数,再将搜索路径的节点和这个新节点通过前后指针串起来。如果分配的新节点的高度高于当前跳跃列表的最大高度,就需要更新一下跳跃列表的最大高度。

更新过程

很简单,如果value不存在,那就是插入过程,如果这个value已经存在,需要修改score值,那就先删除,再插入。

如果score值都一样呢?

在一个极端情况下,zset的所有score值都一样,zset的查找效率会降到o(n)吗?Redis当然也考虑了这个问题,zset排序的时候不止看score,还会根据value排序。

元素排名是怎么算出来的

Redis在skiplist的forward指针进行了优化,给每个forward指针都增加了一个span属性,表示“跨度”的意思,表示从当前层的当前节点沿着forward指针跳到下一个节点的中间会跳过多少个节点。Redis在插入和删除操作都会小心翼翼的维护更新这个span值的大小

0

评论区