引言
Redis是一个key-value存储系统。和Memcached类似，它支持存储的value类型相对更多，包括string(字符串)、list(链表)、set(集合)、zset(sorted set有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove以及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。
本文将对Redis数据的编码方式和底层数据结构进行分析和介绍，帮助读者更好的了解和使用它们。
数据类型和编码方式
Redis中数据对象的定义如下：
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount;
void *ptr;
} robj;其中type对应了Redis中的五种基本数据类型：
\#define OBJ_STRING 0
\#define OBJ_LIST 1
\#define OBJ_SET 2
\#define OBJ_ZSET 3
\#define OBJ_HASH 4
encoding则对应了 Redis 中的十种编码方式:
/* 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 /* Encoded as zipmap */ // 已废弃
\#define OBJ_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
\#define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
\#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 ziplists */type和encoding的对应关系如下图：
OBJ_ENCODING_RAW
RAW编码方式使用简单动态字符串来保存字符串对象，其具体定义为：
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};从len字段可以判断并不不依赖于'0'，故可以用与保存二进制对象。
从free字段可以判断其空间分配是采用预分配的方式，避免字符串修改时频繁分配释放内存。具体分配算法为:
sds sdsMakeRoomFor(sds s，size_t addlen) {
...
if (sdsavail(s) >= addlen) return s;
newlen = sdslen(s)+addlen;
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
sh = (void*) (s-(sizeof(struct sdshdr)));
newsh = zrealloc(sh，sizeof(struct sdshdr)+newlen+1);
if (newsh == NULL) return NULL;
newsh->free = newlen - len;
return newsh->buf;
}OBJ_ENCODING_INT
INT编码方式以整数保存字符串数据，仅限能用long类型值表达的字符串。
当robj中的LRU值没有意义的时候(实例没有设置maxmemory限制或者maxmemory-policy设置的淘汰算法中不计算LRU值时)， 0-10000之间的OBJ_ENCODING_INT编码的字符串对象将进行共享。
具体算法如下：
len = sdslen(s);
if (len <= 21 && string2l(s,len,&value)) {
/* 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_VOLATILE_LRU &&
server.maxmemory_policy != MAXMEMORY_ALLKEYS_LRU)) &&
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;
o->ptr = (void*) value;
return o;
}
}OBJ_ENCODING_EMBSTR
从Redis 3.0版本开始字符串引入了EMBSTR编码方式，长度小于OBJ_ENCODING_EMBSTR_SIZE_LIMIT的字符串将以EMBSTR方式存储。
EMBSTR方式的意思是 embedded string ，字符串的空间将会和redisObject对象的空间一起分配，两者在同一个内存块中。
Redis中内存分配使用的是jemalloc，jemalloc分配内存的时候是按照8,16,32,64作为chunk的单位进行分配的。为了保证采用这种编码方式的字符串能被jemalloc分配在同一个chunk中，该字符串长度不能超过64，故字符串长度限制OBJ_ENCODING_EMBSTR_SIZE_LIMIT = 64 - sizeof('0') - sizeof(robj)为16 - sizeof(struct sdshdr)为8 = 39。
采用这个方式可以减少内存分配的次数，提高内存分配的效率，降低内存碎片率。
robj *createStringObject(const char *ptr，size_t len) {
if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
return createEmbeddedStringObject(ptr,len);
else
return createRawStringObject(ptr,len);
}
robj *createEmbeddedStringObject(const char *ptr，size_t len) {
robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr)+len+1);
o->type = OBJ_STRING;
o->encoding = OBJ_ENCODING_EMBSTR;
...
if (ptr) {
memcpy(sh->buf,ptr,len);
sh->buf[len] = '\0';
} else {
memset(sh->buf,0,len+1);
}
return o;
}OBJ_ENCODING_ZIPLIST
链表(List),哈希(Hash),有序集合(Sorted Set)在成员较少，成员值较小的时候都会采用压缩列表(ZIPLIST)编码方式进行存储。
这里成员"较少"，成员值"较小"的标准可以通过配置项进行配置:
hash-max-ziplist-entries 512
hash-max-ziplist-value 64
list-max-ziplist-entries 512
list-max-ziplist-value 64
zset-max-ziplist-entries 128
zset-max-ziplist-value 64压缩列表简单来说就是一系列连续的内存数据块，其内存利用率很高，但增删改查效率较低，所以只会在成员较少，值较小的情况下使用。
其典型结构如下：
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
area |<------------------- entry -------------------->|
+------------------+----------+--------+---------+
component | pre_entry_length | encoding | length | content |
+------------------+----------+--------+---------+
OBJ_ENCODING_LINKDEDLIST / OBJ_ENCODING_QUICKLIST
在Redis 3.2版本之前，一般的链表使用LINKDEDLIST编码。
在Redis 3.2版本开始，所有的链表都是用QUICKLIST编码。
两者都是使用基本的双端链表数据结构，区别是QUICKLIST每个节点的值都是使用ZIPLIST进行存储的。
// 3.2版本之前
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;
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
// 3.2版本
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* total count of all entries in all ziplists */
unsigned int len; /* number of quicklistNodes */
int fill : 16; /* fill factor for individual nodes */
unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;
unsigned int sz; /* ziplist size in bytes */
unsigned int count : 16; /* count of items in ziplist */
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;OBJ_ENCODING_INTSET
整数集合(intset)是集合键的底层实现之一：
当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。
robj *setTypeCreate(robj *value) {
if (isObjectRepresentableAsLongLong(value,NULL) == REDIS_OK)
return createIntsetObject();
return createSetObject();
}
int setTypeAdd(robj *subject，robj *value) {
...
if (subject->encoding == REDIS_ENCODING_INTSET) {
if (isObjectRepresentableAsLongLong(value,&llval) == REDIS_OK) {
...
} else {
// 当往INTSET里面插入非整数值时，会将集合转成普通的HT编码方式
setTypeConvert(subject,REDIS_ENCODING_HT);
...
}
...
}
...
}OBJ_ENCODING_HT
字典是Redis中存在最广泛的一种数据结构不仅在哈希对象，集合对象和有序结合对象中都有使用，而且Redis所有的Key,Value都是存在db->dict这张字典中的。
Redis 的字典使用哈希表作为底层实现。
一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
哈希表的定义如下：
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// Redis 的哈希表使用链地址法(separate chaining)来解决键冲突：
// 每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表，
// 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。
struct dictEntry *next;
} dictEntry;
/* This is our hash table structure. */
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dictType {
// 用于计算Hash的函数指针
unsigned int (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata，const void *key);
void *(*valDup)(void *privdata，const void *obj);
int (*keyCompare)(void *privdata，const void *key1，const void *key2);
void (*keyDestructor)(void *privdata，void *key);
void (*valDestructor)(void *privdata，void *obj);
} dictType;Redis计算Hash值和索引的方式为:
hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask;一个字典里面保存了两个hash表结构，用于哈希表的扩展收缩操作(Rehash)。
/* Every dictionary has two of this as we
* implement incremental rehashing，for the old to the new table.
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载(used/size)维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
具体算法为:
- 为字典的 ht[1] 哈希表分配空间,这个哈希表的空间大小为:
第一个大于等于(扩展时)或者小于等于(收缩时) ht[0].used * 2 的 2^n(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 做准备。
一次性完成 rehash 过程时间可能很长，Redis采用渐进式 rehash 的方式完成整个过程。
- 每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 并将 rehashidx 的值增一;
- 直到整个 ht[0] 全部完成 rehash 后，rehashindex设为-1，释放 ht[0] , ht[1]置为 ht[0], 在 ht[1] 创建一个新的空白表。
OBJ_ENCODING_SKIPLIST
跳跃表(SKIPLIST)编码方式为有序集合对象专用，有序集合对象采用了字典+跳跃表的方式实现。其定义如下：
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;其中字典里面保存了有序集合中member与score的键值对，跳跃表则用于实现按score排序的功能。
跳跃表以有序的方式在层次化的链表中保存元素，在一般情况下情况下效率和平衡树媲美， 比起平衡树来说，跳跃表的实现要简单直观得多。
一般的跳跃表结构如下图所示：
跳跃表的基本原理是每一个节点创建的时候层数为随机值，层数越高的几率越小，Redis中每升高一层的概率为1/4。也就是说，一个跳跃表里，一般情况下，每一层的节点数为下一次的 1/4，相当于是一个“随机化”的平衡树。
\#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */ macro
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}具体的算法在此就不详细赘述了，与一般的跳跃表实现相比，有序集合中的跳跃表有以下特点：
- 允许重复的 score 值：多个不同的 member 的 score 值可以相同。
- 进行对比操作时，不仅要检查 score 值，还要检查 member：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。
- 每个节点都带有一个高度为1层的后退指针，用于从表尾方向向表头方向迭代：当执行 ZREVRANGE 或ZREVRANGEBYSCORE这类以逆序处理有序集的命令时，就会用到这个属性。
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
robj *obj;
double score;
// 后退指针，方便 zrev 系列的逆序操作
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header，*tail;
unsigned long length;
int level;
} zskiplist;结束
知其然，更要知其所以然。
只有深入了解了Redis数据的编码方式和底层数据结构，我们才能更好的了解使用它。在做疑难问题分析和业务优化时，才能更加有的放矢。
云数据库Redis版（ApsaraDB for Redis）是一种稳定可靠、性能卓越、可弹性伸缩的数据库服务。基于飞天分布式系统和全SSD盘高性能存储，支持主备版和集群版两套高可用架构。提供了全套的容灾切换、故障迁移、在线扩容、性能优化的数据库解决方案。欢迎各位购买使用:云数据库 Redis 版
