概要
1）Redis中的字符串-sds
2）Redis中的HashMap-dict
3）dict的渐进式rehash
4）Redis的5种对象底层剖析

2.1 Redis中的字符串-sds

众所周知，Redis是使用C语言实现的，C语言底层存放string是使用char数组，并且在最后会加上'\0'作为string的结束标志。

C语言存放"Vander" - 》 char[] str = "Vander\0"（此时字符串的length为6byte，但是占据7byte的空间，‘\0’不算在字符串长度里）

问题一：为什么Redis不直接跟C语言一样存放string？

答：因为如果我想存放'Vander\0Jason'就会产生误判，提前结束，这样只会读取到“Vander”，后面的“Jason”就被截取掉了。

由于Redis的Key都是字符串，所以先查看Redis底层的数据结构sds

问题二：如何减少C语言中的string修改字符串时带来的内存重分配

C字符串的内存重分配.png

由于C字符串不记录长度，所以每次增减字符都要对保存的C字符串的数组进行内存重分配。

Redis为了解决增加字符数，频繁重分配的问题，会进行内存预分配，来减少由于再次增加字符而导致的内存重分配的问题。即，假设原有sds存放char[] = 'V','a','n','d','e','r','\0'，需要存放"Vander&Jason"，由于此字符串占12byte，所以会预分配25byte(12*2+1,'\0'占1byte)。但是在大于1MB之后，每次新增不会按照两倍扩展了，只能会再分配多1MB。

惰性空间释放.png

为了解决缩少字符数，导致的内存泄漏的问题，通过调整free来释放惰性空间，通过free来说明当前数组还有剩余空间可以使用。

从Redis设计的sds来看，有三个特点：
1）二进制安全的数据结构（不直接用'\0'作为判断结束的标志，而是加上len的标识）
2）提供内存预分配机制，避免了频繁的内存分配
3）兼容C语言的函数库（数组结尾还是使用'\0'兼容原有的C语言规范）

2.2 Redis中的HashMap-dict

由于C语言中没有实现字典类型的数据结构，所以Redis提供了它的实现，字典可以理解成Java中的HashMap，功能与之类似。当一个hash类型的key包含的键值对较多，或者键值对中的元素都是较长字符串时，底层就会使用字典来作为底层实现

127.0.0.1:6379> hset user:001 bigvalue ababababaabababaababbababaabbaababababababababababababababababababababbabaabababababababababaababababababaababababababaab
(integer) 1
127.0.0.1:6379> object encoding user:001
"hashtable"

dictht(dict.h)-哈希表

typedef struct dictht {// 为了实现渐进式的rehash
    dictEntry **table;// 存放key value的entry
    unsigned long size; // hashtable的容量
    unsigned long sizemask; // size - 1，用于取模运算相当于2^(size - 1)
    unsigned long used;// hashtable的元素个数
} dictht;

负载因子：use/size

Hash冲突及解决：与JDK的实现类似，刚开始申请的数组不够用，需要进行扩容，就需要重新申请一块内存区域，然后将数据搬移到新的内存区域上，在出现Hash冲突时，会将冲突的元素用链表链起来，这种方式叫“链地址法”

举例说明，假设存储的是<key1, value1>,<key2, value2>, <key3, value3>，默认情况下hashtable的初始大小为4，所以用长度为4的数组来存放，上图橙色方块为slot(哈希槽)，hash(key2) %4 =2且hash(key3) %4 =2，都会放入槽位2中，这种情况就是Hash碰撞，在JDK的HashMap中在碰撞较少时会使用链表存放，此处也是类似的，采用链表将碰撞的key连起来，当碰撞到一定长度后会进行重新扩容，这里扩容比较粗暴直接*2即可，所以翻阅源码会看到dict里会有两个dictht(dict hash table的意思)的结构体，就是为了扩容做准备的。假设当前的槽位是4个，扩容时会向操作系统申请8个槽位的内存空间，再将另一个dictht的指针指向这块区域，然后将原有的dictht逐渐迁移到新的dictht

注意：取模运算的优化：num % 2^n = num & (2^n - 1)

2.2.1 Hash碰撞问题

hash碰撞.png

为了让链表不要太长，所以负载因子需要维持在一个合理的范围内，

以下情况会进行hash表的扩展（即上述橙色格子加多一倍的数量，并对数据重新rehash放入新的数组中）
1）服务端没有在执行BGSAVE或BGREWRITEAOF命令，并且负载因子大于等于1
2）服务器正在执行BGSAVE或BGREWRITEAOF命令，并且负载因子大于等于5

以下情况会进行hash表的收缩
1）负载因子小于0.1

2.2.2 渐进式rehash

这里还需要特别说明地是，为了避免rehash对服务性能造成影响，Redis服务端不是一次性将ht[0]的所有键值对全部rehash到ht[1]，而是分多次、渐进式的进行迁移数据，每次对字典执行增删改查时执行对应的key会顺带做迁移，当然在Redis空闲时也会有一个事件轮询的机制进行数据迁移，顺带一提的是，在进行查找的时候，会对这两个dictht的map都进行搜索，直到搬迁完毕，搬迁的过程实在主线程中执行的，用后台线程就要考虑边搬迁边有数据写入，由于是渐进式的所以搬迁数据速度也非常快，所以不会阻塞太长

2.3 Redis的5种对象底层剖析

在Redis中不管是Key还是Value都是用realObject来表示的

typedef struct redisObject {// string/list/set/hash/zset...
    unsigned type:4; // 通过type标识value的类型，这个type就可以限定不同的redisObject只能执行相对应的指令 通过type key进行查看 占4bit
    unsigned encoding:4; // 通过object encoding key进行查看，类型有：raw,embstr,int,ziplist... 占4bit
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or 占3byte(24bit)
                            * LFU data (least significant 8 bits  内存淘汰策略相关frequency
                            * and most significant 16 bits access time). */ 
    int refcount; // 4byte 使用引用计数管理内存 
    void *ptr;    // 8byte 指向底层实现的数据结构的指针
} robj; // 共占16byte

2.3.1 string

Redis中的string，key是sds类型，而value类型也是sds类型（所以通过type查看都是string），但sds底层实现（通过命令encoding object [key]）查看)则有int、raw、embstr，表示的是Redis底层的真实数据结构，在Redis中称为encoding

redisObject对应ptr.png

1）int

试想一下存储整型的数字，而redisObject中的指针就占了8byte，但是long类型在64bit OS中也是占用8byte，若存储整型还要向内存开辟多8byte的空间，然后再用redisObject的ptr来指向是不是一种浪费，又要申请内存，还要CPU多操作去寻址找到对应存储long类型的区域。

Redis基于以上的原因对可以用8byte存储的长整型做了优化，直接使用ptr存放长整型，在计算机中64bit的空间能存放的长整形的范围为(-2^63)~(263)*即-9,223,372,036,854,775,808~9,223,372,036,854,775,807

所以当字符串小于等于20byte时，Redis会尝试转成长整型来存储，若可以，直接用ptr指针来存储此长整型，这样存储能减少一次CPU IO也减少了另外开辟空间，时间空间上都能节省

# 存入64bit长整型的右边界
127.0.0.1:6379:0>set strInt 9223372036854775807
"OK"
# 观察到确实是int
127.0.0.1:6379:0>debug object strInt 
"Value at:00007FCD875B56A0 refcount:1 encoding:int serializedlength:20 lru:5249254 lru_seconds_idle:2"
# 存入64bit长整型的右边界+1
127.0.0.1:6379:0>set strInt 9223372036854775808
"OK"
# 观察到已经转换成了embstr
127.0.0.1:6379:0>debug object strInt 
"Value at:00007FCD875B5640 refcount:1 encoding:embstr serializedlength:20 lru:5249266 lru_seconds_idle:2"
# 同理左边界
127.0.0.1:6379:0>set strInt -9223372036854775808
"OK"
127.0.0.1:6379:0>object encoding strInt
"int"

2）embstr

redisObject结构体总共占16byte（type:4bit, encoding:4bit, lru:3byte, refcount:4byte, *ptr:8byte）

typedef struct redisObject {// string/list/set/hash/zset...
    unsigned type:4; // 通过type标识value的类型 占4bit
    unsigned encoding:4; // 通过object encoding key进行查看，类型有：raw,embstr,int,ziplist... 占4bit
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or 占3byte(24bit)
                            * LFU data (least significant 8 bits  内存淘汰策略相关frequency
                            * and most significant 16 bits access time). */ 
    int refcount; // 4byte 使用引用计数管理内存 
    void *ptr;    // 8byte 指向sds
} robj; // 共占16byte

CPU通过内存地址获取数据通过cpu cache line（一次取64byte）来取数据，由于取RedisObject的时候会获取64byte，Redis将redisObject后的48byte利用起来，而sdshdr8占3byte，字符结束符'\0'占1byte，所以只剩下44byte能够放数据

embstr存储优化.png

# 44位的str
127.0.0.1:6379:0>set strInt 12345678901234567890123456789012345678901234
"OK"
127.0.0.1:6379:0>object encoding strInt
"embstr"
# 45位的str
127.0.0.1:6379:0>set strInt 123456789012345678901234567890123456789012345
"OK"
127.0.0.1:6379:0>object encoding strInt
"raw"

3）raw

当总体超过64byte，Redis认为是大字符串，则直接使用raw形式

string类型的应用：亿级用户日活统计BitMap实战

假设当前有一个场景需要统计上亿级别的用户的上线情况，如近三天的上线用户个数，或者是连续三天上线的用户个数，可以使用BitMap进行实现，BitMap类型实际上是sds，底层存储方式是以char[]实现的

bitmap场景-1.png

上图表示用bitmap的offset作为用户id，第2列表示用户0上过线，第3列表示用户1未上过线，第4列表示用户2上过线

bitmap场景-2.png

上图表示第2列表示20200520这天用户0上线了，20200521这天用户0也上线了，20200522这天用户0未上线

# 设置用户0在20200520当天有上线
127.0.0.1:6379> setbit login_20200520 0 1
(integer) 0
127.0.0.1:6379> setbit login_20200520 5 1
(integer) 0
# 0x84 -> 1000 0100
127.0.0.1:6379> get login_20200520
"\x84"
127.0.0.1:6379> setbit login_20200521 0 1
(integer) 0
127.0.0.1:6379> setbit login_20200521 2 1
(integer) 0
127.0.0.1:6379> setbit login_20200521 5 1
(integer) 0
127.0.0.1:6379> setbit login_20200522 3 1
(integer) 0
# 设置用户5在20200522当天有上线
127.0.0.1:6379> setbit login_20200522 5 1
(integer) 0
# 由于是5bit，所以只用1byte就能存储起来
127.0.0.1:6379> strlen login_20200520
(integer) 1
# 统计20200520的用户上线人数
127.0.0.1:6379> bitcount login_20200520
(integer) 2
# 指定20200521，id从3-5的用户上线人数
127.0.0.1:6379> bitcount login_20200521 3 5
(integer) 0

##连续三天都登录的用户个数
127.0.0.1:6379> bitop and login_20200520-20200522 login_20200520 login_20200521 login_20200522
(integer) 1
# 说明只有一个用户连续三天都登录了
127.0.0.1:6379> bitcount login_20200520-20200522
(integer) 1

##近三天有登录过的用户个数（bitop中的或运算）
127.0.0.1:6379> bitop or active_20200520-20200522 login_20200520 login_20200521 login_20200522
(integer) 1
127.0.0.1:6379> get active_20200520-20200522
"\xb4"
127.0.0.1:6379> get active_20200520-20200522
"\xb4"
127.0.0.1:6379> bitcount active_20200520-20200522
(integer) 4

说明：bitmap最多能存储 2^32-1 bit（即512M）,BitCount的计算速度快是由于用了“汉明重量”的算法

2.3.2 list

在翻阅源码前，想自己思考一下，list会如何实现？

由于操作时有lpush rpush lpop rpop，一般人都会想着通过双向链表实现。

使用双向链表的实现会出现以下问题，

问题1：pre、next两个指针，一个指针要占用8byte，两个即16byte，但是可能存放的数据就小于8byte，这种情况就叫胖指针。意思是指针占据了绝大多数空间而不是被数据占据。

问题2：链表创建可能会产生大量的内存碎片

为了解决胖指针的问题，在Redis 3.2之前是使用ziplist和linkedlist来进行存储的，压缩列表相对于双向链表更节省内存，所以在创建list时，会先考虑压缩列表，并在一定条件下才转化为双向链表，在说明转化条件之前，我们先了解一下什么是压缩列表。

1）ziplist

ziplist&demo.png

压缩列表是Redis为了节省内存而设计的，是由连续内存空间组成的顺序型数据，每个entry可以是字节数组或整数值

ziplist节省内存的原因

因为节点的prerawlen属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的初始地址来计算出前一个节点的起始地址。例如，假设当前指向entry2的指针为p_entry2，则 p_entry1=p_entry2-prerawlen，通过这样的计算方式就能不保留前一个节点的指针从而节约了内存。

创建新列表时 redis 默认使用 redis_encoding_ziplist 编码， 当以下任意一个条件被满足时， 列表会被转换成 redis_encoding_linkedlist 编码：

• 试图往列表新添加一个字符串值，且这个字符串的长度超过 server.list_max_ziplist_value （默认值为 64 ）。
• ziplist 包含的节点超过 server.list_max_ziplist_entries （默认值为 512 ）。

注意：这两个条件是可以修改的，在 redis.conf 中：

list-max-ziplist-value 64 
list-max-ziplist-entries 512 

ziplist连锁更新问题

因为在ziplist中，每个zlentry都存储着前一个节点所占的字节数，而这个数值又是变长编码的。假设存在一个压缩列表，其包含e1、e2、e3、e4…..，e1节点的大小为253字节，那么e2.prevrawlen的大小为1字节，如果此时在e2与e1之间插入了一个新节点e_new，e_new编码后的整体长度（包含e1的长度）为254字节，此时e2.prevrawlen就需要扩充为5字节；如果e2的整体长度变化又引起了e3.prevrawlen的存储长度变化，那么e3也需要扩…….如此递归直到表尾节点或者某一个节点的prevrawlen本身长度可以容纳前一个节点的变化。其中每一次扩充都需要进行空间再分配操作。删除节点亦是如此，只要引起了操作节点之后的节点的prevrawlen的变化，都可能引起连锁更新。

连锁更新在最坏情况下需要进行N次空间再分配，而每次空间再分配的最坏时间复杂度为O(N)，因此连锁更新的总体时间复杂度是O(N^2)。
即使涉及连锁更新的时间复杂度这么高，但它能引起的性能问题的概率是极低的：需要列表中存在大量的节点长度接近254个entry。

所以Redis3.2后为了解决这个问题有引入了quicklist

2）quicklist

可以认为quickList，是ziplist和linkedlist二者的结合；quickList将二者的优点结合起来。

quicklist数据结构.png

quickList就是一个标准的双向链表的配置，有head 有tail;
每一个节点是一个quicklistNode，包含prev和next指针。
每一个quicklistNode 包含 一个ziplist，*zp 压缩链表里存储键值。
所以quicklist是对ziplist进行一次封装，使用小块的ziplist来既保证了少使用内存，也保证了性能。

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
# 设置单个ziplist节点最大存储8kb,超过则进行分裂,将数据存储到新的ziplist节点
list-max-ziplist-size -2
# 0代表所有节点，都不进行压缩,1代表前面两个和尾部两个不进行压缩,其它均压缩,2,3,4...以此类推
list-compress-depth 1

2.3.3 hash

1）ziplist

Hash对象的编码可以是ziplist或者hashtable，当数据量比较小，或单个元素较小时，底层用ziplist存储。数据大小和元素数量阈值可以通过以下参数进行设置

# ziplist元素个数超过512，将改为hashtable编码
hash-max-ziplist-entries 512
# 单个元素大小超过64byte，将改为hashtable编码
hash-max-ziplist-value 64

## 测试hash的object encoding
127.0.0.1:6379> hmset user:001 name Vander age 18
OK
127.0.0.1:6379> type user:001
hash
127.0.0.1:6379> object encoding user:001
"ziplist"
#写入超过64byte的value，会转换成hashtable
127.0.0.1:6379> hset user:001 bigvalue ababababaabababaababbababaabbaababababababababababababababababababababbabaabababababababababaababababababaababababababaab
(integer) 1
127.0.0.1:6379> object encoding user:001
"hashtable"

当有新的键值对要加入到hash对象时，程序会先将保存了键的压缩列表节点推入到压缩列表尾部，然后再将保存了值的压缩列表节点推入到压缩列表尾部，如下图所示，hset name Vander在ziplist中是这么存储的：

hash-ziplist.png

使用这种方式保存时，并不需要申请多余的内存空间，而且每个Key都要存储一些关联的系统信息（如过期时间、LRU等），因此和String类型的Key/Value相比，Hash类型极大的减少了Key的数量(大部分的Key都以Hash字段的形式表示并存储了)，从而进一步优化了存储空间的使用效率。

在这篇 redis memory optimization 官方文章中，作者强烈推荐使用hash存储数据

hash vs string

若存放user对象，string会这么存储，而hash会这么存储

hash vs string.png

2）hashtable

hashtable 编码的哈希对象使用字典作为底层实现， 哈希对象中的每个键值对都使用一个字典键值对来保存：

• 字典的每个键都是一个字符串对象， 对象中保存了键值对的键；
• 字典的每个值都是一个字符串对象， 对象中保存了键值对的值。

hash-hashtable.png

具体使用哪种数据结构，其实是需要看你要存储的数据以及使用场景。

如果存储的都是比较结构化的数据，比如用户数据缓存，或者经常需要操作数据的一个或者几个，特别是如果一个数据中如果filed比较多，但是每次只需要使用其中的一个或者少数的几个，使用hash是一个好的选择，因为它提供了hget 和 hmget，而无需取出所有数据再在代码中处理。

反之，如果数据差异较大，操作时常常需要把所有数据都读取出来再处理，使用string 是一个好的选择。

还有一种场景：如果一个hash中有大量的field（成千上万个），需要考虑是不是使用string来分开存储是不是更好的选择。

2.3.4 set

Set为无序的，自动去重的集合数据类型，Set的encoding可以是intset或者是value为null的hashtable，当数据可以用整型表示时，set集合将被编码为intset数据结构

当满足以下两个条件时，set将用hashtable存储数据：
1）元素个数大于set-max-intset-entries
2）元素无法用整型表示

# intset能存储的最大元素个数，超过则用hashtable编码
set-max-intset-entries 512

## 测试set类型的object encoding
127.0.0.1:6379> sadd group_nums 1 2 3 5 4 0
(integer) 6
# 当元素量少，且可用整型表示时，会用intset，并且排好序，方便查找
127.0.0.1:6379> smembers group_nums
1) "0"
2) "1"
3) "2"
4) "3"
5) "4"
6) "5"
127.0.0.1:6379> type group_nums
set
127.0.0.1:6379> object encoding group_nums
"intset"
# 当添加了非整型类型后，转成hashtable
127.0.0.1:6379> sadd group_nums a
(integer) 1
127.0.0.1:6379> object encoding group_nums
"hashtable"

1）intset

整数集合是一个有序的，存储整型数据的结构。整型集合在Redis中可以保存int16_t,int32_t,int64_t类型的整型数据，并且可以保证集合中不会出现重复数据

typedef struct intset {
    uint32_t  encoding;// 编码类型 可以是INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64
    uint32_t  length;  // 元素个数
    int8_t    contents[]; // 存储元素的数组，可以是int16_t,int32_t,int64_t
} intset; 
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

升级

每当将新元素添加到集合，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要进行升级，然后才能将新元素添加到整数集合中，并且升级之后不会进行降级

分三步进行：
1）根据新元素的类型，扩展整数集合底层数组的空间大小并为新元素分配空间
2）将底层数组现有的所有元素都转换成新元素相同的类型，并将类型转换后的元素放在正确的位置（即要排好序放）
3）将新元素放入

2）hashtable

set-hashtable.png

2.3.5 zset

有序集合的encoding可以是ziplist或者skiplist

1）ziplist

压缩列表内的集合元素按score从小到大进行排序，分值较小的元素被放置在靠近表头的位置，分值较大的则放置在靠近表尾的位置

以下是“zadd accomplishment 100 math"，表示存储数学成绩100分

zset-ziplist.png

2）dict+skiplist

encoding为skiplist的zset对象使用zset结构体作为底层实现，一个zset的结构体同时有字典和跳表

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

先简单展示一下，跳表查找72的过程

跳表的简单演示.png

红色箭头为查找路径，通过索引层可以实现类似于二分查找的结果，所以跳表的查找时间复杂度为log(n)

Redis中的跳表谁能成为索引，是由随机函数随机决定的，越底层的元素能成为索引的可能性越大

下面展示"zadd accomplishment 100 math 99 chinese 95 English"

zset-skiplist.png

从上图可以看出skiplist主要是用于通过score来给内容进行排序，若只是需要单独取出某个内容的score，可以直接查询dict结构，这种方式使用了空间换取了时间，但是占得并不多，以上重复展示了个元素的成员和分值，其实字典和跳表是会共享元素的成员和分值，不会造成数据重复存储的。（注意上述只是为了举例，实际上上述指令encoding并不是skiplist，因为元素数量和元素长度都不满足条件，所以上述图示实际上是用ziplist存储的）

当同时满足以下两个条件时，对象使用ziplist编码：
1）有序集合保存的元素数量小于128个
2）有序集合保存的所有元素成员的长度都小于64byte

127.0.0.1:6379> zadd accomplishment 100 math 99 chinese 95 English
(integer) 3
127.0.0.1:6379> object encoding accomplishment
"ziplist"
127.0.0.1:6379> zadd accomplishment 50 abcdaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer) 1
127.0.0.1:6379> object encoding accomplishment
"skiplist"
127.0.0.1:6379>

注意：GEO类型是GeoHash算法+zset来实现的。

扩展知识

Redis 3.2前后sds的结构

Redis 3.2后sds的定义（sds.h）

struct sdshdr {
    int len;// 字符串的长度，不会计算'\0'
    int free;
    char buf[];
}

Redis 3.2后sts的定义（sds.h）

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];// 末尾的结束符'\0'会占用一个字节
};// 所以这个结构占用了4byte
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* 2byte used */
    uint16_t alloc; /* 2byte excluding the header and null terminator */
    unsigned char flags; /* 1byte 3 lsb of type, 5 unused bits */
    char buf[];// 1byte
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 已用长度 used */
    uint64_t alloc; /* 申请内存空间大小 excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[]; /* 真正存放数据的地方 char类型在C语言中占用1byte */ 
};

可以看出Redis的sts类型存放字符串也是通过char数组，其中还有len标记这个字符串的长度，还有alloc表示申请的总空间的大小

Redis 3.2之后对底层的sts类型进行了优化，当len小于5bit时，即存放的数据范围为0~(2^{5-1)时，直接使用sdshdr5进行存储即可。当存放的数据范围超过2}5-1，后面的5bit就会闲置无用。

sdshdr5-flags示意图.png

在64位系统c语言int占用4byte(32 bit)，能表示20位字符的长度(由于2^{32次方是42亿)，则使用sdshdr5，若数组长度为2}32~2^64，则使用sdshdr64，以此类推。

Redis的数据结构关联关系

redis的数据结构.png

Redis中db类型：redisDb(server.h)

typedef struct redisDb {
    dict *dict;                 /* 存放<k, value> The keyspace for this DB */
    dict *expires;              /* 存放<key timeout>Timeout of keys with a timeout set */
    dict *blocking_keys;        /* 阻塞队列的处理 Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* 客户端维护 Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* 数据库id Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

dict(dict.h)

typedef struct dict {
    dictType *type; // 类型
    void *privdata; //
    dictht ht[2];// 需要有两个dictht 为了实现渐进式的rehash,在没有进行rehash的阶段h[1]=null
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

dictht(dict.h)-哈希表

typedef struct dictht {// 为了实现渐进式的rehash
    dictEntry **table;// 存放key value的entry
    unsigned long size; // hashtable的容量
    unsigned long sizemask; // size - 1，用于取模运算相当于2^(size - 1)
    unsigned long used;// hashtable的元素个数
} dictht;

dictEntry(dict.h)

typedef struct dictEntry {
    void *key; // 实际上就是sds的结构体，由于key都是用string存储的
    union {
        void *val;// value的类型则比较多样，string/list/hash等，对应的结构体是redisObject
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 当hash冲突时，指向下个entry
} dictEntry;

dictEntry中的value是通过redisObject来进行存放的(server.h)

typedef struct redisObject {// string/list/set/hash/zset...
    unsigned type:4; // 通过type标识value的类型，这个type就可以限定不同的redisObject只能执行相对应的指令 通过type key进行查看 占4bit
    unsigned encoding:4; // 通过object encoding key进行查看，类型有：raw,embstr,int,ziplist... 占4bit
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or 占3byte(24bit)
                            * LFU data (least significant 8 bits  内存淘汰策略相关frequency
                            * and most significant 16 bits access time). */ 
    int refcount; // 4byte 使用引用计数管理内存 
    void *ptr;    // 8byte 指向sds
} robj; // 共占16byte

set key value源码解析

源码说明当redisObject的字节长度小于等于20时，会尝试使用长整型进行存储

setCommand(t_string.c)

void setCommand(client *c) {
    robj *expire = NULL;
    int unit = UNIT_SECONDS;
    int flags = OBJ_NO_FLAGS;

    if (parseExtendedStringArgumentsOrReply(c,&flags,&unit,&expire,COMMAND_SET) != C_OK) {
        return;
    }

    c->argv[2] = tryObjectEncoding(c->argv[2]);// 完成编码
    setGenericCommand(c,flags,c->argv[1],c->argv[2],expire,unit,NULL,NULL);
}

tryObjectEncoding(object.c)

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;

    /* Make sure this is a string object, the only type we encode
     * in this function. Other types use encoded memory efficient
     * representations but are handled by the commands implementing
     * the type. */
    serverAssertWithInfo(NULL,o,o->type == OBJ_STRING);

    /* We try some specialized encoding only for objects that are
     * RAW or EMBSTR encoded, in other words objects that are still
     * in represented by an actually array of chars. */
    if (!sdsEncodedObject(o)) return o;

    /* It's not safe to encode shared objects: shared objects can be shared
     * everywhere in the "object space" of Redis and may end in places where
     * they are not handled. We handle them only as values in the keyspace. */
     if (o->refcount > 1) return o;

    /* Check if we can represent this string as a long integer.
     * Note that we are sure that a string larger than 20 chars is not
     * representable as a 32 nor 64 bit integer. */
    len = sdslen(s);// 获取字符串的字节长度
    if (len <= 20 && string2l(s,len,&value)) {// 字符串长度小于等于20byte 尝试转成长整形存储
        /* This object is encodable as a long. Try to use a shared object.
         * Note that we avoid using shared integers when maxmemory is used
         * because every object needs to have a private LRU field for the LRU
         * algorithm to work well. */
        if ((server.maxmemory == 0 ||
            !(server.maxmemory_policy & MAXMEMORY_FLAG_NO_SHARED_INTEGERS)) &&
            value >= 0 &&
            value < OBJ_SHARED_INTEGERS)
        {
            decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {
            if (o->encoding == OBJ_ENCODING_RAW) {
                sdsfree(o->ptr);
                o->encoding = OBJ_ENCODING_INT;// encoding为int
                o->ptr = (void*) value;// 使用长整型存储
                return o;
            } else if (o->encoding == OBJ_ENCODING_EMBSTR) {
                decrRefCount(o);
                return createStringObjectFromLongLongForValue(value);
            }
        }
    }

    /* If the string is small and is still RAW encoded,
     * try the EMBSTR encoding which is more efficient.
     * In this representation the object and the SDS string are allocated
     * in the same chunk of memory to save space and cache misses. */
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;

        if (o->encoding == OBJ_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }

    /* We can't encode the object...
     *
     * Do the last try, and at least optimize the SDS string inside
     * the string object to require little space, in case there
     * is more than 10% of free space at the end of the SDS string.
     *
     * We do that only for relatively large strings as this branch
     * is only entered if the length of the string is greater than
     * OBJ_ENCODING_EMBSTR_SIZE_LIMIT. */
    trimStringObjectIfNeeded(o);

    /* Return the original object. */
    return o;
}

Redis 6.0新特性

1）多线程
2）服务端协助的客户端缓存（仅支持单机，lettuce 6.0版本已经支持）
3）权限管理（进行更加细致的权限管理）