Redis数据编码方式详解-白红宇

Redis数据编码方式详解

阅读量：4116 次

发布时间：2019-05-25

本文共 11205 字，大约阅读时间需要 37 分钟。

摘要： ## 引言 Redis是一个key-value存储系统。和Memcached类似，它支持存储的value类型相对更多，包括string(字符串)、list(链表)、set(集合)、zset(sorted set有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove以及取交集并集和差集及更丰富的操作，而且这些操作都是原子性的。本文将对Redis数据的

引言

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 512hash-max-ziplist-value 64list-max-ziplist-entries 512list-max-ziplist-value 64zset-max-ziplist-entries 128zset-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_TAILarea        |<------------------- 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

具体的算法在此就不详细赘述了，与一般的跳跃表实现相比，有序集合中的跳跃表有以下特点：

允许重复的 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;