Redis 设计与实现：数据结构与对象
1 简单动态字符串（simple dynamic string，SDS）
Redis 的 简单动态字符串（Simple Dynamic String，SDS） 是 Redis 内部用于表示字符串的核心数据结构，替代了 C 语言原生的 char\* 字符串，解决了其一系列缺陷。SDS 是 Redis 中键和值最常见的数据表示方式，底层以一种结构体的形式封装。
Redis底层使用SDS作为字符串表示，与C字符串相比，SDS具有以下优点：
- 常数复杂度获取字符串长度
- 杜绝缓冲区移除
- 减少修改字符串长度时所需的内存分配次数
- 二进制安全
- 兼容部分C字符串库函数
/* src/sds.h */
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[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
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[];
};
2 链表
链表数据结构被广泛用于Redis的各种功能实现，如列表键、发布订阅、慢查询、监视器等。
Redis的链表实现特点：
-
每一个链表节点使用一个listNode结构表示
-
每个链表使用一个list结构表示
-
双端无环链表，prev和next
-
带表头和表尾指针，head和tail
-
带链表长度计数器，len
-
多态
/* src/adlist.h */
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
3 字典
字典是一种保存键值对的数据结构，Redis数据库使用字典作为底层实现，而Redis字典又是用哈希表作为其底层实现。
- 每个字典有两个哈希表，一个平时使用，一个仅在rehash时使用
- 哈希表使用链地址法解决键冲突，同一个索引上的键值对会连接成一个单向链表
- 当扩展或收缩哈希表时，程序会将现有哈希表的所有键值对rehash到新的哈希表，rehash是渐进式完成的
/* src/dict.h */
/* 哈希表节点 */
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; /* Next entry in the same hash bucket. */
void *metadata[]; /* An arbitrary number of bytes (starting at a
* pointer-aligned address) of size as returned
* by dictType's dictEntryMetadataBytes(). */
} dictEntry;
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(dict *d, const void *key);
void *(*valDup)(dict *d, const void *obj);
int (*keyCompare)(dict *d, const void *key1, const void *key2);
void (*keyDestructor)(dict *d, void *key);
void (*valDestructor)(dict *d, void *obj);
int (*expandAllowed)(size_t moreMem, double usedRatio);
/* Allow a dictEntry to carry extra caller-defined metadata. The
* extra memory is initialized to 0 when a dictEntry is allocated. */
size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;
struct dict {
dictType *type;
dictEntry **ht_table[2];
unsigned long ht_used[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
/* Keep small vars at end for optimal (minimal) struct padding */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
};
4 跳跃表
跳跃表是一种有序数据结构，其每个节点维持多个指向其他节点的指针，从而能够快速访问节点。跳跃表节点查找的平均效率为O(logN)，最坏为O(N)，可以和平衡树相比。Redis使用跳跃表作为有序集合的底层实现之一，此外，跳跃表还在Redis集群节点中用作内部数据结构。
- Redis跳跃表由
zskiplistNode和zskiplist实现，其中zskiplistNode表示跳跃表节点，zskiplist则保存跳跃表信息 - 每个跳跃表节点的层高都是1-32之间的随机数
- 跳跃表中的节点按照分值大小进行排序，分值相同时则按照节点对象的大小排序
/* src/server.h */
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
5 整数集合
整数集合是Redis集合的底层实现之一，而整数集合的底层实现是C数组，这个数组以有序、无重复的方式保存着集合元素。在向集合中添加一个新元素时，可能会导致整数集合升级（只能升级，不能降级），即底层数组的类型会改变，升级涉及以下步骤：
- 根据新元素类型，扩展整数集合底层数组的空间大小，同时也为新元素分配空间
- 将所有旧类型元素转换为新类型元素，并按照顺序放置到相应的位置
- 将新元素添加到底层数组中
/* src/intset.h */
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
6 压缩列表
压缩列表是一种为了节约内存而开发的顺序型数据结构，是Redis列表和哈希的底层实现之一，添加或者删除节点可能会涉及到连锁更新。
/* src/ziplist.c */
typedef struct zlentry {
unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
unsigned int prevrawlen; /* Previous entry len. */
unsigned int lensize; /* Bytes used to encode this entry type/len.
For example strings have a 1, 2 or 5 bytes
header. Integers always use a single byte.*/
unsigned int len; /* Bytes used to represent the actual entry.
For strings this is just the string length
while for integers it is 1, 2, 3, 4, 8 or
0 (for 4 bit immediate) depending on the
number range. */
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
the entry encoding. However for 4 bits
immediate integers this can assume a range
of values and must be range-checked. */
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
7 Redis 对象系统
经过以上介绍，了解了Redis所用到的主要数据结构：SDS、双端链表、字典、跳跃表、整数集合、压缩列表等。但Redis不是直接使用这些数据结构来实现键值对数据库，而是用这些构建了一个对象系统，这个系统包含了五种类型的对象：字符串对象、列表对象、哈希对象、集合对象、有序集合对象，每个对象都用到了至少一种前面介绍的数据结构。Redis中每个对象都由一个redisObject结构表示：
/* src/server.h */
struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
};
7.1 type
对于Redis保存的键值对来说，键总是一个字符串对象，值可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象之一。
/* src/server.h */
/* The actual Redis Object */
#define OBJ_STRING 0 /* String object. */
#define OBJ_LIST 1 /* List object. */
#define OBJ_SET 2 /* Set object. */
#define OBJ_ZSET 3 /* Sorted set object. */
#define OBJ_HASH 4 /* Hash object. */
7.2 encoding
redisObject对象的ptr指针指向对象的底层数据结构，而具体实现的数据结构由encoding决定，即决定这个对象使用了什么数据结构作为其底层实现。每种对象都可以使用多种底层数据结构实现，从而可以在不同场景下使用不同的底层数据结构实现，能够优化对象在不同场景下的效率。
/* src/server.h */
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object. */
#define OBJ_ENCODING_RAW 0 /* Raw representation */
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* No longer used: old hash encoding. */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
7.3 字符串对象
字符串对象的编码可以是：int、raw、embstr。
- 如果字符串对象保存的是long类型整数，编码则为int
- 如果字符串对象保存的是字符串且长度大于32字节，编码则为raw
- 如果字符串对象保存的是字符串且长度小于32字节，编码则为embstr。embstr是专门用于保存短字符串的一种优化编码方式
- int、embstr编码在一定条件下会转换成raw
/* src/server.h */
#define OBJ_ENCODING_RAW 0 /* Raw representation */
#define OBJ_ENCODING_INT 1 /* Encoded as integer */
#define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding */
7.4 列表对象
列表对象的编码可以是：ziplist(压缩列表)、linkedlist(双端链表)。Redis新版本中列表对象如今已不再使用这两种数据结构，当前 Redis 列表对象编码为 quicklist，每个节点是一个 listpack，整体是一个双向链表结构——支持快速的 lpush/rpush/lpop/rpop。
/* src/server.h */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
7.5 哈希对象
哈希对象的编码可以是：hashtable、ziplist。Redis新版本中哈希对象已不再使用ziplist。
/* src/server.h */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3 /* No longer used: old hash encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
7.6 集合对象
集合对象的编码可以是：intset、hashtable。当集合元素都是整数且集合元素不超过512个时使用intset，其他情况则使用hashtable。
/* src/server.h */
#define OBJ_ENCODING_HT 2 /* Encoded as hash table */
#define OBJ_ENCODING_INTSET 6 /* Encoded as intset */
7.7 有序集合对象
有序集合的编码可以是：skiplist(跳跃表)、ziplist(压缩列表)。Redis新版本中有序集合对象已不再使用ziplist。当编码为skiplist时，有序集合对象使用zset作为其底层实现，一个zset结构同时包含一个字典和一个跳跃表。
/* src/server.h */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
#define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
7.8 其它
Redis对象系统带有引用计数实现的内存回收机制，当一个对象的引用计数为0时，其对应内存将被回收。
对象会记录自己最后一次被访问的时间，可用于计算对象空转时长。
Redis会共享0-9999的字符串对象，从而节约内存和优化效率。