一、从常用数据结构说起

上文说到Redis提供了丰富的数据结构，包括STRING（字符串）、LIST（列表）、SET（集合）、HASH（散列）和ZSET（有序集合）基本数据类型。

先来一波操作感受一下：

基本的数据类型的大概使用就到这里，接下来就分析一下它的内部结构是怎么实现的。

二、底层实现

Redis是KV类型的数据库，Key-Value我们一般会用什么数据结构存储？

哈希表！没错Redis的最外层确实也是通过hashtable实现的。在Redis里面每个键值对都是一个dictEntry，通过指针指向key的存储结构和value的存储结构，此外还有一个next存储里指向下一个键值对的指针。

typedef struct dictEntry {
    void *key; //key void*表示任意类型指针

    union {                   
       void      *val;//value定义
       uint64_t  u64;
       int64_t   s64;
       double   d;
    } v;
    struct dictEntry *next;   //next指针
} dictEntry;

看到这里大家会有疑惑，那过期时间放在哪里？

对，实际上在dicEntry的外面还有一层redisDB。

/* Redis数据库结构体 */
typedef struct redisDb {
    // 数据库键空间，存放着所有的键值对（键为key，值为相应的类型对象）
    dict *dict;                 
    // 键的过期时间
    dict *expires;              
    // 处于阻塞状态的键和相应的client（主要用于List类型的阻塞操作）
    dict *blocking_keys;       
    // 准备好数据可以解除阻塞状态的键和相应的client
    dict *ready_keys;           
    // 被watch命令监控的key和相应client
    dict *watched_keys;         
    // 数据库ID标识
    int id;
    // 数据库内所有键的平均TTL（生存时间）
    long long avg_ttl;         
} redisDb;

外层说完了，接下来就以set hello world为例，逐步分析一下。

首先key是字符串，Redis自己实现了一个字符串类型叫SDS，后面我们会细说，所以hello指向一个SDS的存储结构。value是world，也是一个字符串，是不是也用SDS存储呢？

这里就要重点介绍以下了，由前文我们知道Redis的key都是字符串类型，value的类型有多种。那Redis如何是适配这多种类型呢？于是就封装了一层redisObject。而我们所说的Redis数据类型的任何一种，都是通过redisObject存储的。

我们来看一下redisObject的结构：

typedef struct redisObject {
    //对象的数据类型，占4bits，共5种类型
    unsigned type:4;        
    //对象的编码类型，占4bits，共10种类型
    unsigned encoding:4;
    //least recently used
    //实用LRU算法计算相对server.lruclock的LRU时间
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
    //引用计数
    int refcount;
    //指向底层数据实现的指针
    void *ptr;
} robj;

到这里就能看出一些奇妙的地方了，type是数据类型，encoding是编码类型，且数量不等。有意思了，那我们接下来看看这个encoding究竟是些什么。

127.0.0.1:6379> set number 123

OK

127.0.0.1:6379> object encoding number

"int"

127.0.0.1:6379> set story "long long ago,and long long ago,other long long ago"

OK

127.0.0.1:6379> object encoding story

"raw"

127.0.0.1:6379> set msg "hello world"

OK

127.0.0.1:6379> object encoding msg

"embstr"

到此我们大概看出来一些端倪，Redis的数据类型背后根据存储的数据不同使用的不同的编码存储。为什么要这样做呢？

节约存储空间！

其实远远不止这些，我们后面会详细说到。接下来就看每种数据结构有哪些编码类型。

三、数据结构详解

1、String

上文我们已经分析出了，String底层有三种。

int：存储8个字节的长整形

embstr：代表embsds格式的SDS，存储小于44字节的字符串

raw：存储大于44字节的SDS

接下来问题来了，什么是SDS呢？SDS全称是Simple Dynamic String，即简单动态字符串。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 长度 */
    uint8_t alloc; /* 分配的内存大小 */
    unsigned char flags; /* 属性，标志不同种类的sds */
    char buf[];/* 内容 */
};

本质上就是一个char数组！

那么既然是一个char数组，为什么要通过SDS实现呢？

SDS

很简单，因为C语言中没有字符串类型，只有char数组。但是使用char数组会有一些问题，什么问题呢，大家可以想一下。

1、必须分配足够的空间，否则可能会溢出

2、如果要获取长度，需要遍历数组，时间复杂度是O(n)

3、如果长度变更，需要重新内存分配

4、字符串规则是遇到第一个'/0'即为结束，因此不能存放二进制的内容

好了，既然有了这些问题，SDS是如何解决的呢？

1、SDS实现了动态扩容，无需担心溢出的问题

2、定义了len属性，获取长度时间复杂度是O(1)

3、通过空间预分配和惰性空间释放，放置了重新分配内存

4、判断结束标志示len属性，避免了二进制不安全

哇，到这里是不是感觉到Redis的编码格式设计的很巧妙。别着急，慢慢来，还有。

embstr和raw，为什么要设计两个编码格式呢？就是为了长度不同吗？SDS也已经满足了呀？

实际原因是embstr的使用，只分配了一次内存，redisObject和SDS是一起分配的，二raw是分配了两次内存

那这三种类型之间是怎么转换的呢？

1、int 不在时整形，转成raw

2、int大小超过long的范围，转成embstr

3、embstr超过44字节，转成raw

注意：不可回转！！！

到此，String的数据结构就介绍完毕了。最后大家都思考一下String的使用场景有哪些？

1、缓存：热点数据，提升检索效率；

2、数据共享：session共享多个服务器共用；

3、分布式锁：setNx方法，判断是否添加成功；

4、全局唯一ID：INT类型的incrby；

5、计数器：INT类型

6、限流：INT类型

哈哈，是不是感觉String好强大，不需要其他数据类型了？那么问题来了，如果我要存一个对象怎么办？举个例子，存一个学生信息，包括姓名、年龄、学号等信息。大家可能会说，String存储一个json就行了，没错可以实现。但是我如果只想获取学生的年龄呢？

接下来介绍的Hash类型，就是解决这个问题的。

2、Hash

Hash类型是指Redis键值对中的值本身又是一个键值对结构，形如value=[{field1，value1}，...{fieldN，valueN}]，hash的value只能是字符串，不能嵌套其他类型。同样是存储字符串，Hash和String有什么区别呢？如下图所示:

从上图可以明显看出：

1、把所有相关的值聚集到一个key中，节省内存空间

2、只使用一个key，可以有效减少key冲突

3、当需要批量获取值的时候，只需要使用一个命令，减少内存/IO/CPU

那么它的底层编码是如何实现的呢？是不是使用dicEntry实现的呢？我们先来操作一波：

127.0.0.1:6379> hset user1 name aaaaaaaaaaaaaaaaaaa

(integer) 1

127.0.0.1:6379> hset user2 name aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

(integer) 1

127.0.0.1:6379> object encoding user1

"ziplist"

127.0.0.1:6379> object encoding user2

"hashtable"

可以看到，哈希类型的内部编码有两种：ziplist(压缩列表),hashtable(哈希表)。又有两个陌生的结构，不要慌张，我们下文会逐个分析。

ziplist

ziplist是一个经过特殊编码的，由连续的内存块组成的双向链表。它不存储指向上一个节点和下一个节点的指针，而是存储上一个节点的长度和当前节点的长度。这让数据在内存中更为紧凑，所以叫做zip，同时可以轻易地得到前驱后驱数据项的位置。

<zlbytes><zltail><zllen><entry>...<entry><zlend>

接下来我们具体看下实际元素里，究竟是怎么存储的。

typedef struct zlentry {
    //prevrawlen 前驱节点的长度
    //prevrawlensize 编码前驱节点的长度prevrawlen所需要的字节大小
    unsigned int prevrawlensize, prevrawlen;
    //len 当前节点值长度
    //lensize 编码当前节点长度len所需的字节数
    unsigned int lensize, len;
    //当前节点header的大小 = lensize + prevrawlensize
    unsigned int headersize;
    //当前节点的编码格式
    unsigned char encoding;
    //指向当前节点的指针，以char *类型保存
    unsigned char *p;
} zlentry;                 

那么什么时候使用ziplist呢？

hash对象保存的键值对数量<512所有键值对字符串长度小于54字节

如果任何一个条件不满足，存储结构就会转成hashtable。接下来介绍hashtable

hashtable

前面我们知道了，Redis的KV结构是通过dictEntry来实现的。在hashtable中，又对dictEntry进行了多层封装。

typedef struct dictht {
    // 两个哈希表
    dictEntry **table;
    // 哈希表的大小
    unsigned long size;
    // 哈希表大小掩码
    unsigned long sizemask;
    // 哈希表中数据项数量
    unsigned long used;
} dictht;

dictEntry放在了dictht(hashtable)里面了

typedef struct dict {
    // 哈希表的类型，包括哈希函数，比较函数，键值的内存释放函数
    dictType *type;
    // 存储一些额外的数据
    void *privdata;
    // 两个哈希表
    dictht ht[2];
    // 哈希表重置下标，指定的是哈希数组的数组下标
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 绑定到哈希表的迭代器个数
    int iterators; /* number of iterators currently running */
} dict;

dictht放在了dict里面了。

从源码可以看出，它是一个数组+链表的结构。如图：

我们发现dictht后面是个null，说明第二个hashtable没有数据。那么为什么要定义两个hashtable，其中一个不用呢？

答案是为了扩展哈希表！ht默认使用ht[0],ht[1]不初始化。hash表有一个普遍存在的问题就是hash冲突，如果冲突过多都会放置在上图的dicEntry数组里。这样hash的读性能就退化称数组的遍历，效率降低。解决hash冲突的有效手段就是对hash进行扩容，让数据足够分散。这个过程会进行一次rehash，这个过程中就会使用到ht[1]。首先是初始化ht[1]的大小为ht[0]的最小n次幂。然后将ht[0]的数据写入ht[1]，然后再将ht[0]释放。怎么样这个设计过程是不是很巧妙？

使用场景：

1、和String一样！毕竟hash存储的也是String。

2、存储对象类型的数据：比string节省key。

3、购物车：key：用户id，filed：商品id，value：数量。增加、减少、删除等都可以操作。

3. List

List主要用来存储有序数据，数据可重复。

先来操作一波：

127.0.0.1:6379> lpush queue a (integer) 1 127.0.0.1:6379> lpush queue b c (integer) 3 127.0.0.1:6379> object encoding queue "quicklist"

可以看到list的底层结构是quicklist来实现的。接下来就介绍一下quicklist。

quicklist

quicklist 实际上是 ziplist 和 linkedlist 的混合体，它将 linkedList 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。

typedef struct quicklist {
    quicklistNode *head;//指向第一个quicklistNode
    quicklistNode *tail;//指向最后一个quicklistNode
    unsigned long count; //在所有ziplist中entry的个数总和
    unsigned int len;//quicklistNode的个数
    int fill : 16; //ziplist大小限定，由server.list_max_ziplist_size给定
    unsigned int compress : 16; //节点压缩深度设置，由server.list-compress-depth给定，0表示关闭压缩
} quicklist;

看到里面用到了一个quicklistNode存储数据。

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    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;

ziplist上文已经介绍了，就不多说了。总的来说，quicklist就是ziplist 和 linkedlist 的混合体。

应用场景：

1、列表：文章列表、热门排行榜之类的

2、队列／栈：list有两个阻塞操作：BLPOP/BRPOP

4、set

set存储String类型的无序集合，最大存储2^32-1。

先操作一波：

127.0.0.1:6379> sadd myset a b c

(integer) 3

127.0.0.1:6379> object encoding myset

"hashtable"

127.0.0.1:6379> sadd newset 1 2 3

(integer) 3

127.0.0.1:6379> object encoding newset

"intset"

可以看到set的编码格式有两种intset和hashtable。如果第一个原始是一个整数，就会初始化为intset，如果intset保存的值的数量大于512(set_max_intset_entries默认值)个，会转化称hashtable。

typedef struct intset {
    uint32_t encoding;//数组中的值的编码方式
    uint32_t length;//数组长度
    int8_t contents[];//数组，记录每个值
} intset;

使用场景：

1、抽奖：spop

2、点赞、打卡：数据集无序，sadd添加，srem取消，sismember是否操作，smembers所有，scard总数

3、标签：sadd添加 sinter筛选

5、zset

sorted set存储的是有序的集合元素。它是为每个元素添加了一个score，按照score的大小排序。

操作一波：

127.0.0.1:6379> zadd myzset 1 java 2 redis 3 mysql

(integer) 3

127.0.0.1:6379> object encoding myzset

"ziplist"

127.0.0.1:6379> zadd myzsetnew 4 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

(integer) 1

127.0.0.1:6379> object encoding myzsetnew

"skiplist"

可以看到，有序集合是由 ziplist (压缩列表) 或 skiplist (跳跃表)组成的。

当数据比较少时(<128)，且所有元素长度都小于64字节，有序集合使用的是 ziplist 存储的，否则使用skiplist结构存储。

ziplist我们已经很熟悉了，那么问题来了，什么是skiplist？

skiplist

skiplist是一个特殊的链表，相比一般的链表，有更高的查找效率，其效率可比拟于二叉查找树。

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾指针 
    unsigned long length;   // skiplist的长度  
    int level;  // 最高多少级链表 
} zskiplist;

zskiplist的定义，没啥内容，就头尾指针、长度和级数，重点还是在zskiplistNode中。

typedef struct zskiplistNode {
    sds ele;   // 节点存储的具体值 
    double score;   // 节点对应的分值 
    struct zskiplistNode *backward; // 前向指针
    struct zskiplistLevel {
    	struct zskiplistNode *forward; // 每一层的后向指针 
    	unsigned long span;  // 到下一个节点的跨度 
    } level[];
} zskiplistNode;

通过上面的源码，我们可以简单画一下大概的结构图。

很明显查询我们需要遍历整个链表，效率低。我们想要提高其查找效率，可以考虑在链表上建索引的方式。每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引。这就是skiplist的实现方式。

在图中，需要寻找 68，在给出的查找过程中，利用跳表数据结构优势，只比较了 3次。由此可见，跳表预先间隔地保存了有序链表中的节点，从而在查找过程中能达到类似于二分搜索的效果，而二分搜索思想就是通过比较中点数据放弃另一半的查找，从而节省一半的查找时间。

应用场景：顺序会动态变化的场景。

1、热榜、热搜：incrby进行加1，zrevrange获取排序

到这里常用的数据类型就介绍完毕了，简单总结一下。

其他数据结构

bitmap

通过一个bit位来表示某个元素对应的值或者状态,其中的key就是对应元素本身。bitmap本身会极大的节省储存空间。

Redis从2.2.0版本开始新增了setbit,getbit,bitcount等几个bitmap相关命令。虽然是新命令，但是并没有新增新的数据类型，因为setbit等命令只不过是在set上的扩展。

使用场景：

1、在线用户统计

2、每日用户访问统计

hyperloglogs

HyperLogLog是用来做基数统计的算法，它的优点是在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。什么是基数呢？举个例子：比如数据集 {1, 3, 5, 7, 5, 7, 8}， 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。 基数估计就是在误差可接受的范围内，快速计算基数。

使用场景：统计网站的UV，日活。

geo

顾名思义，是用来地理位置计算的。

使用场景：附近的人

Stream

5.0之后新出的数据类型，支持广播的可持久化消息队列，类似于kafka。

使用场景：消息队列