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 4encoding则对应了 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的对应关系如下图：
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; }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; } }从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; }链表(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 | +------------------+----------+--------+---------+在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;整数集合(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); ... } ... } ... }字典是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] 创建一个新的空白表。跳跃表(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 版
