Redis数据结构

通常我们都说Redis快，都是说它是基于内存的数据库。但是仅仅是这样吗？

实际上Redis快的原因除了它本身是基于内存的数据库之外，实际上还有一个重要因素那就是它实现的数据结构。注意：【这里说到的数据结构并不是指Redis的数据类型（String、List、Hash、Set、Zset），而是这些数据类型底层依赖的数据结构。】

Redis的五个基本数据类型和底层数据结构的关系

Redis经过多个版本的迭代更新，底层数据结构也发生了变化。

在Redis3.0的时候，5个基本数据类型对应的底层数据结构分别是：

String Set List Sorted Set Hash
sds（动态字符串） hashTable（哈希表） quickList（双端链表） skipList（跳表） hashTable（哈希表）
intSet（整数数组） zipList（压缩列表）

在数据结构发生变化之后：

String Set List Sorted Set Hash
sds（动态字符串） hashTable（哈希表） quickList（双端链表） skipList（跳表） hashTable（哈希表）
intSet（整数数组） listPack（紧凑列表）

可以看到，有很多底层使用了两种数据结构，比如Set在元素较少，且都是数字的情况下会使用整数列表，数据增加会变成哈希表。

Redis的键值对数据库是怎么实现的

在Redis中key就是字符串对象，但是value可以是字符串对象，也可以是集合数据类型的对象，比如List对象、Hash对象、Set对象和Zset对象。比如这里新增几个key然后使用type命令即可查看value的类型，可以发现这些类型分别是string、hash以及list。

127.0.0.1:6379> SET k1 v1
OK
127.0.0.1:6379> HSET student name jack age 13
(integer) 2
127.0.0.1:6379> RPUSH list v1 v2 v3 v4
(integer) 4
127.0.0.1:6379> type k1
string
127.0.0.1:6379> type student
hash
127.0.0.1:6379> type list
list

全局哈希表

Redis中key是如何保存的呢？

在Redis中，其实是使用了一个哈希表保存所有键值对，每一个key经过Redis内部的hash算法之后都会计算出一个地址，这个地址就对应一个哈希桶了，使用哈希表的最大的好处就是查找的时间复杂度只有O(1)。哈希表其实就是一个数组，数组中的元素叫做哈希桶。

#+--------+--------+--------+--------+--------+--------+--------+--------+--------+
#|  Hash  |  Hash  |  Hash  |  Hash  |  Hash  |  Hash  |  Hash  |  Hash  |  Hash  |
#| Bucket | Bucket | Bucket | Bucket | Bucket | Bucket | Bucket | Bucket | Bucket |
#+--------+--------+--------+--------+--------+--------+--------+--------+--------+

但是说到hash算法必然有哈希冲突存在，那怎么解决呢？Redis使用了链表来解决这个问题（有点类似Java中的HashMap）。

#   +------------+
#   | HashBucket |
#   +------------+         +------------+         +------------+
#   | HashBucket |-------->|  KeyValue  |-------->|   ......   |
#   +------------+         +------------+         +------------+
#   | HashBucket |
#   +------------+
#   | HashBucket |
#   +------------+         +------------+         +------------+         +------------+
#   | HashBucket |-------->|  KeyValue  |-------->|  KeyValue  |-------->|   ......   |
#   +------------+         +------------+         +------------+         +------------+
#   | HashBucket |
#   +------------+
#   | HashBucket |
#   +------------+
#   | HashBucket |
#   +------------+

当这个链表中的元素越来越多之后，一个哈希桶所对应的链表会越来越长，一个链表上的遍历时间复杂度是O(n)，会严重影响性能。Redis为了处理这个问题会有一个rehash操作。大概就是会在内部重新建一个长度为原始长度2倍的空哈希表，然后原哈希表上的元素重新rehash到新的哈希表中去，然后我们使用新的哈希表即可。但是Redis大部分操作还是单线程的，这个过程可能会阻塞其他操作，如果是在数据量很大的时候，那可能会花很长时间来完成。所以Redis采用了渐进式rehash操作，简单说就是在每次操作的时候顺便copy到新的哈希表，而且Redis本身也有定时任务来处理。

哈希桶又是如何保存key的呢？

哈希桶存放的是指向键值对数据的指针（dictEntry），这样通过指针就能找到键值对数据，然后因为键值对的值可以保存字符串对象和集合数据类型的对象，所以键值对的数据结构中并不是直接保存值本身，而是保存了*key和*val指针，分别指向了实际的key对象和value对象，这样一来，即使值是集合数据，也可以通过*val指针找到。dictEntry源码结构如下：

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* 哈希桶里面的下一个entry */
    void *metadata[];                                           
};

RedisObject

上面说到了dictEntry，dictEntry中的*key和*val指针指向的是Redis对象（redisObject），Redis中key和value对象都是redisObject。

struct redisObject {
    unsigned type:4;        /* 对象的类型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET等*/
    unsigned encoding:4;    /* 具体对应的数据结构*/
    unsigned lru:LRU_BITS;  /* 淘汰策略LRU和LFU会用到*/
    int refcount;           /* 引用计数，当refcount为0的时候，表示该对象已经不被任何对象引用，可以被淘汰了*/
    void *ptr;              /* 指向对象实际的数据结构的指针*/
};

为了便于操作，Redis采用redisObject结构来统一五种不同的数据类型，这样所有的数据类型就都可以以相同的形式在函数间传递而不用使用特定的类型结构。同时，为了识别不同的数据类型，redisObject中定义了type和encoding两个字段来对不同的数据类型加以区分。

RedisObject中每个字段的含义：

  1. type表示具体的数据类型

  2. encoding表示该类型的物理编码方式，同一种数据类型可能会有不同的编码方式（比如String类型就有三种编码方式，分别有：int、embstr、raw）。

    /* 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 */

  3. lru则是用于淘汰策略的字段，具体可以看这里。

  4. refcount则表示对象的引用计数。

  5. ptr则是指向对象实际的数据结构的指针。

DEBUG OBEJECT

上面我们说到了同一种数据类型可能会有不同的编码方式。那怎么确定使用的是哪种编码方式呢？

Redis提供了DEBUG OBEJECT命令，DEBUG OBEJECT是一个调试命令，可以查看key的详细信息，其不应该在客户端使用。直接使用会返回error。

127.0.0.1:6379> DEBUG OBJECT key
(error) ERR DEBUG command not allowed. If the enable-debug-command option is set to "local", you can run it from a local connection, otherwise you need to set this option in the configuration file, and then restart the server.

这里根据报错信息可以看到，想要使用这个命令还需要修改一个配置enable-debug-command为local，修改需重启Redis。

然后开始测试，首先创建两个key分别使用命令：

127.0.0.1:6379> SET k1 v1
OK
127.0.0.1:6379> SET COUNT 100
OK
127.0.0.1:6379> type k1
string
127.0.0.1:6379> type COUNT
string

可以看到这里个key的类型都是String，然后我们再使用DEBUG OBEJECT查看key的详细信息：

127.0.0.1:6379> DEBUG OBJECT k1
Value at:0xffff87135d38 refcount:1 encoding:embstr serializedlength:3 lru:2460675 lru_seconds_idle:113
127.0.0.1:6379> DEBUG OBJECT COUNT
Value at:0xffff871147b0 refcount:2147483647 encoding:int serializedlength:2 lru:2460514 lru_seconds_idle:279

可以这两个key的类型虽然都是String，但是它们的编码方式却是不同的，分别是int和embstr。

Redis数据结构解析

更多关于Redis的底层的数据结构解析可以看这里：