1.SDS
struct sdshdr {
//记录buf数组中已使用字节的数量
//等于SDS所保存字符串的长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组，用于保存字符串
char buf[];
};
-
SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小。
-
通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。
-
空间预分配：惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。
- 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。
- 如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。
-
惰性空间释放：惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。
-
1）常数复杂度获取字符串长度。
2）杜绝缓冲区溢出。
3）减少修改字符串长度时所需的内存重分配次数。
4）二进制安全。
5）兼容部分C字符串函数。
2.链表
//==================链表节点=============
typedef struct listNode {
// 前置节点
struct listNode * prev;
// 后置节点
struct listNode * next;
//节点的值
void * value;
}listNode;
//==================链表=============
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;
3.字典
//==================哈希表节点=============
typedef struct dictEntry {
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
} v;
//指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
//==================哈希表=============
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
//总是等于size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;
//==================字典=============
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];
// rehash索引
//当rehash不在进行时，值为-1
in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
- ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
rehashidx记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。- Redis的哈希表使用链地址法（separate chaining）来解决键冲突，为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为O（1）），排在其他已有节点的前面。
3.1 rehash
为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
Redis对字典的哈希表执行rehash的步骤如下：
-
为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）：
- 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2 n（2的n次方幂）
- 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2 n。
-
将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
-
当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
- 服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
- 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
3.2 渐进式rehash
redis的rehash动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。这样做的原因在于，如果ht[0]里的键值对非常大，那么要一次性将这些键值对全部rehash到ht[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。
以下是哈希表渐进式rehash的详细步骤：
为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。
当ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。
- 在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找。
- 在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作。
4.跳跃表
typedef struct zskiplistNode {
//层
struct zskiplistLevel {
//前进指针
struct zskiplistNode *forward;
//跨度，用于记录两个节点之间的距离
unsigned int span;
} level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
} zskiplistNode;
typedef struct zskiplist {
//表头节点和表尾节点
structz skiplistNode *header, *tail;
//表中节点的数量
unsigned long length;
//表中层数最大的节点的层数
int level;
} zskiplist;
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。- 跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。
- Redis使用跳跃表作为
有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构
- level：每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。header默认层高32。
- 每个层都有一个指向表尾方向的前进指针（level[i].forward属性），用于从表头向表尾方向访问节点。
- 跨度（level[i].span）：用于记录两个节点之间的距离。在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
5.整数集合
typedef struct intset {
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
- 整数集合是集合键的底层实现之一。
- 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
6.压缩列表
压缩列表（ziplist）是列表键和哈希键的底层实现之一，是Redis为了节约内存而开发的。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。
| 属性 | 类型 | 长度 | 作用 |
|---|---|---|---|
| zlbytes | uint32_t | 4 | 压缩列表占用的内存字节数 |
| zltail | uint32_t | 4 | 表尾节点距离列表起始地址的字节数，因此可通过起始字节直接计算得到表尾地址 |
| zllen | uint16_t | 2 | 节点数量。小于65535时，值就是节点数量；大于时，需要遍历列表才能计算得出节点数量。 |
| entry_X | 列表的节点 | 即保存的节点。长度由各自节点内容决定 | |
| zlend | uint8_t | 1 | 特殊值0xFF(255)，标记压缩列表末端 |
previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。
压缩列表的从表尾向表头遍历操作就是使用这一原理实现的，只要我们拥有了一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的previous_entry_length属性，程序就可以一直向前一个节点回溯，最终到达压缩列表的表头节点。
encoding属性记录了节点的content属性所保存数据的类型以及长度
content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。
6.1 连锁更新
每个节点的previous_entry_length属性都记录了前一个节点的长度：
-
如果前一节点的长度小于254字节，那么previous_entry_length属性需要用1字节长的空间来保存这个长度值。
-
如果前一节点的长度大于等于254字节，那么previous_entry_length属性需要用5字节长的空间来保存这个长度值。
如果 原有的节点都小于 254 字节, 突然间插入一个大于等于 254 字节,原有节点的previous_entry_length的1个字节已经不满足需求，需要扩展至5字节， 压缩列表将会发生空间重分配(连锁更新);
删除节点, 也会发生导致连锁更新。
但是因为进行连锁更新，要求列表由连续多个长度在250到253字节的节点，这种情况并不多见，所以基本不用担心它的性能问题。
6.2快速链表 quicklist
redis 3.2以后，
quicklist作为列表键的实现底层实现之一，代替了压缩列表
typedef struct quicklist {
//指向头部(最左边)quicklist节点的指针
quicklistNode *head;
//指向尾部(最右边)quicklist节点的指针
quicklistNode *tail;
//ziplist中的entry节点计数器
unsigned long count;
//quicklist的quicklistNode节点计数器
unsigned int len;
//保存ziplist的大小，配置文件设定，占16bits
int fill : 16;
//保存压缩程度值，配置文件设定，占16bits，0表示不压缩
unsigned int compress : 16;
} quicklist;
typedef struct quicklistNode {
struct quicklistNode *prev; //前驱节点指针
struct quicklistNode *next; //后继节点指针
//不设置压缩数据参数recompress时指向一个ziplist结构
//设置压缩数据参数recompress指向quicklistLZF结构
unsigned char *zl;
//压缩列表ziplist的总长度
unsigned int sz;
//ziplist中包的节点数，占16 bits长度
unsigned int count : 16;
//表示是否采用了LZF压缩算法压缩quicklist节点，1表示压缩过，2表示没压缩，占2 bits长度
unsigned int encoding : 2;
//表示一个quicklistNode节点是否采用ziplist结构保存数据，2表示压缩了，1表示没压缩，默认是2，占2bits长度
unsigned int container : 2;
//标记quicklist节点的ziplist之前是否被解压缩过，占1bit长度
//如果recompress为1，则等待被再次压缩
unsigned int recompress : 1;
//测试时使用
unsigned int attempted_compress : 1;
//额外扩展位，占10bits长度
unsigned int extra : 10;
} quicklistNode;
7.对象
Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。
前面介绍的动态字符串（SDS）、双端链表、字典、压缩列表、整数集合等等，Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种我们前面所介绍的数据结构。
这样做的好处：
- 我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
- Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放。
- Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。
typedef struct redisObject {
//类型
//键：总是字符串对象
//值：符串对象、列表对象、哈希对象、集合对象和有序集合对象
unsigned type:4;
//编码
unsigned encoding:4;
//指向底层实现数据结构的指针
void *ptr;
//引用计数
int refcount;
//记录对象最后一次被命令程序访问的时间
unsigned lru:22;
// ...
} robj;
| 类型 | 编码 | 对象 |
|---|---|---|
| REDIS_STRING | REDIS_ENCODING_INT | 使用整数值实现的字符串对象 |
| REDIS_STRING | REDIS_ENCODING_EMBSTR | 这货redis3.0引入的，不管 |
| REDIS_STRING | REDIS_ENCODING_RAW | sds实现的字符串对象 |
| REDIS_LIST | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的列表对象 |
| REDIS_LIST | REDIS_ENCODING_LINKEDLIST | 使用双向链表实现的列表对象 |
| REDIS_HASH | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的哈希对象 |
| REDIS_HASH | REDIS_ENCODING_HT | 使用字典实现的哈希对象 |
| REDIS_SET | REDIS_ENCODING_INTSET | 使用整数集合实现的集合对象 |
| REDIS_SET | REDIS_ENCODING_HT | 使用字典实现的集合对象 |
| REDIS_ZSET | REDIS_ENCODING_ZIPLIST | 使用压缩列表实现的有序集合对象 |
| REDIS_ZSET | REDIS_ENCODING_SKIPLIST | 使用跳跃表想和字典实现的有序集合对象 |
7.1 字符串对象
字符串对象的编码可以是int、raw或者embstr。
- 如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码设置为int。
- 字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值，并将对象的编码设置为raw。
- 字符串对象保存的是一个字符串值，并且这个字符串值的长度小于等于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值。
embstr的创建只需分配一次内存，而raw为两次，分别创建redisObject结构和sdshdr结构。相对地，embstr释放内存的次数也由两次变为一次。embstr的objet和sds放在一起，更好地利用缓存带来的优势。redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。
字符串对象是Redis五种类型的对象中唯一一种会被其他四种对象嵌套的对象。
embstr例图：
7.2 列表对象
列表对象的编码可以是ziplist或者linkedlist。
-
使用
ziplist（redis 3.2以后，quicklist作为列表键的实现底层实现之一，代替了压缩列表）：- 列表对象保存的所有字符串元素的长度都小于64字节。
- 列表对象保存的元素数量小于512个。
-
使用
linklist：
7.3 哈希对象
哈希对象编码可以是ziplist或hashtable
-
使用
ziplist- 键和值的字符串长度小于64字节；
- 键值对数量少于512个；
-
使用
hashtable
7.4 集合对象
集合对象的编码可以是intset或hashtable
-
使用
inset- 所有元素为整数值；
- 保存的元素不超过512个；
-
使用
hashtable：字典的每个键都是一个字符串对象，每个字符串对象包含了一个集合元素，而字典的值则全部被设置为NULL。
7.5 有序集合对象
有序集合的编码可以是ziplist或skiplist，压缩列表内的集合元素按分值从小到大排列
-
使用
ziplist：每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。
-
使用
ziplist-
元素数量少于128个；
-
元素长度小于64字节；
- skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表：
typedef struct zset { zskiplist *zsl; dict *dict; } zset; 思考：为什么额外添加一个字典？ zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O（1）复杂度查找给定成员的分值，ZSCORE命令就是根据这一特性实现的。 如果我们只使用跳跃表来实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有了字典，所以根据成员查找分值这一操作的复杂度将从O（1）上升为O（logN）。因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。 - 跳跃表和字典使用指针来共享相同的元素和分值，因此不会产生重复，也不会造成内存浪费
-
7.6 内存回收
Redis构建一个引用计数计数实现内存回收机制；引用计数由redisObject结构的refcount属性记录：
typedef struct redisObject{
//...
//引用计数
int refcount;
//...
}
- 创建新对象时，
refcount被初始化为1； - 对象被新程序使用时，
refcount++； - 对象不被一个程序使用时，
refcount--； - 对象计数值为0时，对象占用的内存会被释放；
7.7 对象共享
- 对象的计数属性带有对象共享的作用；
- 当n个键保存同一个值时，这些键的值指针指向同一个值对象，值对象的
refcount为n； - Redis在初始化服务器时，会创建一万个字符串对象（0~9999的字符串对象），当服务器需要用到这些值对象时，服务器会使用这些共享对象，而不是创建新对象；
- Redis只对包含整数值的字符串对象进行共享，验证数字的时间复杂度为O(1)；
7.8 对象的空转时长
redisObject结构里有个lru属性，记录对象最后一次被命令程序访问的时间；
typedef struct redisObject{
//...
unsigned lru:22;
//...
}
-
使用命令
OBJECT IDLETIME可以显示对象的空转时间，不会改变对象的空转时间； -
如果服务器打开maxmemory选项，并且回收内存的算法为
volatile-lru或allkeys-lru，那么当服务器占用的内存数超过maxmemory选项设置的上限值是，空转时间较高的键会优先被服务器释放，回收内存；