Redis之数据结构底层实现
目录
redis底层数据结构实现
redis是（REmote DIctionary Service）作为NoSQL数据库，以key-value的字典方式来存储数据，其中的value主要支持五种数据类型。
本文主要讲解redis的五种常用数据类型（string、list、hash、set、zset）的底层数据结构实现。
Redis数据结构
Redis采用key-value的方式来存储数据，每个键值对都会有一个dictEntry，里面有指向key,value的指针，还有指向下一个键值对的next指针
typedef struct dictEntry {
void *key; /* key 关键字定义*/
union {
void *val;
uint64_t u64; /* value 定义*/
int64_t s64;
double d;
} v;
struct dictEntry *next; /* 指向下一个键值对节点*/
} dictEntry;这里的key 是字符串，使用了Redis自己定义的SDS数据结构来存储,而value 是存储在redisObject 中的。
typedef struct redisObject {
unsigned type:4; /* 对象的类型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET*/
unsigned encoding:4; /* 底层存储的具体数据结构*/
unsigned lru:LRU_BITS; /* 24 位，对象最后一次被访问的时间，与内存淘汰机制有关*/
int refcount; /* 引用计数。当其为0的时候，表示该对象已经不被任何对象引用，可以进行垃圾回收*/
void *ptr; /* 指向对象实际的数据结构*/
} robj;String字符串
redis中并没有使用C语言的 字符串表示(以空字符结尾的字符数组)，而是自己定义了一个SDS(Simple Dynamic String,简单动态字符串)作为字符串的默认实现
常用命令
| 1 | SET key value 设值 |
| 2 | GET key 取值。 |
| 3 | MGET key1 [key2..] 获取所有(一个或多个)给定 key 的值。 |
| 4 | SETEX key seconds value 设值，并将 key 的过期时间设为 seconds (以秒为单位) (原子性)。 |
| 5 | SETNX key value 只有在 key 不存在的时候才可以成功设置(可以根据这个特性来创建分布式锁) |
| 6 | MGET key1 [key2..] 获取所有(一个或多个)给定 key 的值。 |
| 7 | MSET key value [key value ...] 同时设置一个或多个 key-value 对(批量操作，原子性)。 |
| 8 | INCR/DECR key 将 key 中储存的数字值增一/减一。 |
| 9 | APPEND key value 向key对应的value值后追加新的value到其末尾 |
对于字符串,其内部的encoding有三种: 根本原因还是为了减少内存消耗
- int 存储8字节的长整型(最大存储2^63-1)
- embstr 代表embstr格式的SDS(Simple Dynamic String),字符串大小<44字节
- raw 存储大于44字节的字符串
Embstr和raw的区别? 区别在于分配内存的次数
Embstr在使用的时候只需要分配一次内存空间(RedisObject和SDS是连续的),而raw需要分配两次。如果字符串的长度增加导致需要重新分配内存空间，embstr类型的RedisObject和SDS都需要重新分配,因此 Redis中的embstr表现为只读(对embstr进行修改就会转化为raw编码)
SDS的定义
redis中的SDS有各种结构，sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，用于存储不同的长度的字符串(节省内存空间)，分别代表2^5=32byte， 2^8=256byte，2^16=65536byte=64KB，2^32byte=4GB
/* sds.h */
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 当前字符数组的长度*/
uint8_t alloc; /*当前字符数组总共分配的内存大小*/
unsigned char flags; /* 当前字符数组的属性,用来标识是sdshdr8 还是sdshdr16 等*/
char buf[]; /* 字符串真正的值,最后一个字符保存了空字符 '\0' */
};比方说一个字符串"Redis",给它分配了32个字节的空间，目前只保存了5个字符
SDS的好处
1.在声明的时候提前预留了空间，并且会在内存不够的时候进行扩容
2.在SDS定义了字符串的长度len,获取其长度的时间复杂度为O(1)
3.通过事先分配空间（空间预分配）和惰性空间释放，较少内存重新分配的次数，大大提高存储效率
4.以从开始的第len个字符表示字符串的结束，不用担心存储二进制数据的时候由于’\0’而导致无法完整获取数据，是二进制安全的
5.同样以'\0'结尾是因为这样就可以使用C语言中函数库操作字符串的函数了
应用场景
缓存热点数据,可以提升热点数据的访问速度
在分布式下共享数据 eg.分布式session
分布式锁 (setnx)
计数器:页面访问流量统计(incr)
List列表
用于存储有序的字符串,可以从头和尾添加或者获取元素(Left/Right)，列表里的元素可以重复,能够充当队列和栈的角色
常用命令
| 1 | BLPOP key1 [key2 ] timeout 从左侧移出并获取列表的第一个元素， 如果列表没有元素会阻塞直到超时或发现可弹出元素为止。 |
| 2 | BRPOP key1 [key2 ] timeout 从右侧并获取列表的最后一个元素， 如果列表没有元素会阻塞直到超时或发现可弹出元素为止。 |
| 3 | LPUSH key value1 [value2] 将一个或多个值插入到列表头部(左侧) |
| 4 | RPUSH key value1 [value2] 向列表尾部添加一个或多个值(右侧) |
先来说一下redis里的压缩列表的数据结构
压缩列表ziplist
压缩列表(ziplist),顾名思义，在条件允许的情形下对保存的列表数据尽可能的进行压缩，是Redis 为了节约内存而开发的， 一个经过特殊编码的连续内存块组成的双向链表。它不像普通的链表存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能，来换取高效的内存空间利用率。只适合用在字段个数少，字段值小的场景里面。
typedef struct zlentry {
unsigned int prevrawlensize; /* 上一个链表节点占用的长度*/
unsigned int prevrawlen; /* 存储上一个链表节点的长度数值所需要的字节数*/
unsigned int lensize; /* 存储当前链表节点长度数值所需要的字节数*/
unsigned int len; /* 当前链表节点占用的长度*/
unsigned int headersize; /* 当前链表节点的头部大小（prevrawlensize + lensize），即非数据域 的大小*/
unsigned char encoding; /* 编码方式*/
unsigned char *p; /* 压缩链表以字符串的形式保存，该指针指向当前节点起始位置*/
} zlentry;其存储结构如下图:
早期版本里，redis的列表是通过ziplist或者linkedlist的结构实现,数据量较小的时候会使用ziplist来保存数据，较大的时候会使用linkedlist(双向链表的结构)来存储，类似于下图，就不再赘述了
quicklist
3.2版本之后，统一用quicklist来存储。quicklist存储了一个双向链表，每个节点都是一个ziplist。
typedef struct quicklist {
quicklistNode *head; /* 指向双向列表的表头 */
quicklistNode *tail; /* 指向双向列表的表尾 */
unsigned long count; /* 所有的 ziplist 中一共存了多少个元素 */
unsigned long len; /* 双向链表的长度，node 的数量 */
int fill : 16; /* fill factor for individual nodes */
unsigned int compress : 16; /* 压缩深度，0：不压缩； */
} quicklist;
typedef struct quicklistNode {
struct quicklistNode *prev; /* 前一个节点 */
struct quicklistNode *next; /* 后一个节点 */
unsigned char *zl; /* 指向实际的 ziplist */
unsigned int sz; /* 当前 ziplist 占用多少字节 */
unsigned int count : 16; /* 当前 ziplist 中存储了多少个元素，占 16bit（下同），最大 65536 个 */ unsigned int encoding : 2; /* 是否采用了 LZF 压缩算法压缩节点，1：RAW 2：LZF */
unsigned int container : 2; /* 2：ziplist，未来可能支持其他结构存储 */
unsigned int recompress : 1; /* 当前 ziplist 是不是已经被解压出来作临时使用 */
unsigned int attempted_compress : 1; /* 测试用 */
unsigned int extra : 10; /* 预留给未来使用 */
} quicklistNode;
应用场景
消息队列: List提供了两个带阻塞功能的pop操作：BLPOP/BRPOP，可以实现简单的类似消息队列的功能
队列：先进先出：rpush blpop
栈：先进后出：rpush brpop
Hash哈希
存储包含键值对的无序散列表,其value只能是字符串，不能嵌套其他类型
常用命令
| 1 | HDEL key field1 [field2] 删除一个或多个哈希表字段 |
| 2 | HEXISTS key field 查看哈希表中，是否存在指定的field |
| 3 | HGET key field 获取存储在哈希表中指定field对应的value。 |
| 4 | HGETALL key 获取在哈希表中指定 key 的所有字段和值 |
| 5 | HKEYS key 获取key对应的哈希表中所有的字段 |
| 6 | HMSET key field1 value1 [field2 value2 ] 同时将多个 field-value (键值对)设置到哈希表 key 中。 |
| 7 | HSET key field value 将哈希表 key 中的字段 field 的值设为 value 。 |
前面说到redis本身就是一个K-V键值对的字典数据库，对于Hash结构，相当于将Redis的Value也使用field-value的方式来进行存储。其存储方式有两种:ziplist和hashtable
当hash对象同时满足以下两个条件的时候，会使用ziplist编码：
1）所有的键值对的健和值的字符串长度都小于等于64byte；
2）哈希对象保存的键值对数量小于512个。
压缩列表在前面就介绍过了，这里就介绍下hashtable\
hashtable
哈希表的节点使用dictEntry来表示,每个 dictEntry 结构都保存着一个键值对：
typedef struct dictEntry {
void *key; /* key 关键字定义*/
union {
void *val;
uint64_t u64; /* value 定义*/
int64_t s64;
double d;
} v;
struct dictEntry *next; /* 指向下一个键值对节点*/
} dictEntry;而dictEntry存储在一个dictht里(一个hashtable),
/*Thisisourhashtablestructure.Everydictionaryhastwoofthisaswe
*implementincrementalrehashing,fortheoldtothenewtable.*/
typedef struct dictht{
dictEntry **table;/* 哈希表数组 每一个元素是一个dictEntry*/
unsigned long size;/* 哈希表大小 */
unsigned long sizemask;/* 掩码大小，用于计算索引值。总是等于 size-1*/
unsigned long used;/* 已有节点数 */
} dictht;
而上述哈希表又保存到了dict里
typedef struct dict{
dictType *type;/* 字典类型 */
void *privdata;/* 私有数据 */
dictht ht[2];/* 一个字典有两个哈希表 */
long rehashidx;/*rehash 索引 */
unsigned long iterators;/* 当前正在使用的迭代器数量 */
} dict;
从外层到底层是这样的一个包含关系
dict-->dictht-->dictEntry
在普通情形下，一个哈希的字典的存储结构如下图:
其存储的方式类似于hashMap,如果发生hash冲突，那么就会将对应下标的最后一个元素的next指针指向新的dictEntry
这里定义了两个hashtable，主要是为了在发生大量哈希碰撞的时候进行扩容使用
一般情形下,dict里使用hashtable的时候，默认使用的是ht[0],ht[1]不会进行初始化和分配空间。哈希表使用链地址法来解决hash碰撞，如果碰撞剧烈，导致ht[0]的链很长，就会影响到redis的查询速度。故hashtable的查询性能取决于其table大小和保存的节点数量之间的比值。当上述比值较大的时候,也就是说hash碰撞发生比较剧烈的时候会对其进行扩容
此时需满足两个条件:
1)允许扩容 dict_can_resize=1
2)table里保存的节点数/table的大小大于dict_force_resize_ratio
扩容时，会对ht[1]进行初始化，并且分配空间，新的hashtable的大小为当前hashtable保存的节点数*2，然后将ht[0]里的dictEntry迁移到ht[1],重新计算哈希值和索引，存放到新的索引下。迁移完成后，将ht[1]设置为ht[0]表,然后把原来的ht[0]清空回收内存，将其设置为ht[1]以供下次rehash使用
应用场景
字符串数据结构可以做的事情，Hash也都能实现
存储对象类型的数据，以field为属性，value为对应的属性值，便于管理
Set集合
string类型的无序集合
常用命令
| 1 | SADD key member1 [member2] 向集合添加一个或多个成员 |
| 2 | SCARD key 获取集合的成员数 |
| 3 | SDIFF key1 [key2] 返回给定所有集合的差集 |
| 4 | SDIFFSTORE destination key1 [key2] 返回给定所有集合的差集并存储在 destination 中 |
| 5 | SINTER key1 [key2] 返回给定所有集合的交集 |
| 6 | SINTERSTORE destination key1 [key2] 返回给定所有集合的交集并存储在 destination 中 |
| 7 | SISMEMBER key member 判断 member 元素是否是集合 key 的成员 |
| 8 | SPOP key 移除并返回集合中的一个随机元素 |
| 9 | SRANDMEMBER key [count] 返回集合中一个或多个随机数 |
| 10 | SREM key member1 [member2] 移除集合中一个或多个成员 |
| 11 | SUNION key1 [key2] 返回所有给定集合的并集 |
| 12 | SUNIONSTORE destination key1 [key2] 所有给定集合的并集存储在 destination 集合中 |
Redis采用用intset或hashtable来存储set。如果元素都是整数类型，使用inset存储。
如果不全是整数类型，就用hashtable（数组+链表的结构来存储）,目的还是为了节省存储空间
inset整型集合
typedef struct intset {
// 编码方式 : INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组 不同的encoding,其数组的元素大小也不一样
int8_t contents[];
} intset;
使用hashtable来存储set的时候，dictEntry里的key对应于set里的成员，value为null
应用场景
抽奖 : 随机获取一个成员
签到 , 点赞，打卡
商品标签
商品筛选 ： 通过交集，差集，并集等做商品筛选
ZSet有序集合
有序的集合，每个元素都会有对应的score,根据score来排序；score相同时，按照key的ASCII码排序。
| 1 | ZADD key score1 member1 [score2 member2] 向有序集合添加一个或多个成员，或者更新已存在成员的分数 |
| 3 | ZCOUNT key min max 计算score在指定区间的有序集合的成员数 |
| 4 | ZINCRBY key increment member 有序集合中对指定成员的分数加上增量 increment |
| 5 | ZRANGE key start stop [WITHSCORES] 通过索引区间返回有序集合指定区间内的成员 |
| 6 | ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT] 通过分数返回有序集合指定区间内的成员 |
| 7 | ZRANK key member 返回有序集合中指定成员的索引 |
| 8 | ZREM key member [member ...] 移除有序集合中的一个或多个成员 |
| 9 | ZREVRANGE key start stop [WITHSCORES] 返回有序集中指定区间内的成员，通过索引，分数从高到低 |
| 10 | ZREVRANGEBYSCORE key max min [WITHSCORES] 返回有序集中指定分数区间内的成员，分数从高到低排序 |
| 11 | ZREVRANK key member 返回有序集合中指定成员的排名，有序集成员按分数值递减(从大到小)排序 |
| 12 | ZSCORE key member 返回有序集中，成员的分数值 |
存储原理
有序集合底层采用ziplist或者skiplist的方式进行存储
当 元素数量小于128个且所有member的长度都小于64字节的时候会使用ziplist存储有序集合,在压缩列表内部，按照score递增的顺序来进行存储，故而每次插入或者删除的时候要移动之后的数据
当大于这个阈值时，会使用跳跃表(skiplist)来存储
skiplist
大家都知道，对于链表，插入和删除的效率比较高，但是查询的效率会很低，因为需要从head节点开始遍历，直到找到对应的元素或者遍历完整个链表，其时间复杂度时O(n).同理，在有序链表里插入数据的时候也需要先查询一遍才可以确定插入的位置
对于有序数组我们可以使用二分查找法来优化查询的速度，对于有序链表，可以使用跳跃表
假如我们每相邻的两个节点间增加一个指针，形成一个新的Level(实际情形不一定是相邻2个节点形成一个level,但是Level越大，该层上的节点数就越少)，让其上的指针指向下一个节点。这样新的Level也是一个链表，但它包含的节点个数只有原来的一半(实际一定比原来少，具体多少不一定)（图中的8, 19, 41）。
如下图:
当想新增一个节点数据的时候，会根据幂次定律 （power law，越大的数出现的概率越小） 随机生成一个介于 1 和 32 之间的值作为level数组的大小， 这个大小就是层的“高度” (redis t_zset.c 中的zslRandomLevel方法)。
当我们想查询数据V的时候，可以先沿着这个新链表(最顶层Level)进行查找。当碰到比V大的节点或者下一个节为null时，下落到下一层进行查找(因为之后的节点只可能更大或者到头)，下落到较小的level节点之后，比较节点值和V的大小，如果V较大，则继续向前查找，如果V较小，则 通过后退指针"后退"查找，不断继续这个过程，直到找到对应的节点，或者V位于level1相邻两节点之间。
在查找过程中，由于新增加的层级包含更少的节点，故不再需要与链表中每个节点逐个进行比较才能找到对应的位置了，这就是跳跃表。
Redis中skiplist的定义
typedef struct zskiplist{
struct zskiplistNode *header,*tail;/* 指向跳跃表的头结点和尾节点 */
unsigned long length; /* 跳跃表内所有的节点数 */
int level;/* 跳跃表内，层数最大的那个节点的层数 */
}zskiplisttypedef struct zskiplistNode{
sds ele;/*zset 的元素 */
double score;/* 分值 */
struct zskiplistNode *backward;/* 后退指针 */
struct zskiplistLevel
{
struct zskiplistNode *forward;/* 前进指针，对应 level 的下一个节点 */
unsigned long span;/* 从当前节点到下一个节点的跨度（跨越的节点数） */
}
level[];/* 层 */
} zskiplistNode;
随机获取层数的函数
int zslRandomLevel(void){
int level=1;
while((random()&0xFFFF)<(ZSKIPLIST_P*0xFFFF))
level+=1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
应用场景
排行榜 点击数前几的新闻等
参考链接
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
6
0- 0
已为社区贡献2条内容
所有评论(0)