redis数据结构与原理

发表于 | 分类于

一、缓存

1.1，缓存的概念

缓存的概念很广泛，依据用途不同可以分为：

  1. 操作系统磁盘的缓存：减少磁盘操作
  2. 数据库缓存：减少磁盘IO
  3. 应用程序缓存：减少数据库访问
  4. Web服务器缓存：减少服务器访问
  5. 客户端浏览器缓存：减少网页访问

由此我们可以简单认为缓存实际上就是为了减少交互而存在的功能或者组件。

1.2，缓存的意义

由以上缓存的用途我们可以知道，缓存意义重大，用于减少互相之间的交互提升效率，本质上是热点数据或者临时数据有了一个就近或者效率高的备份。这就引出了一个问题：备份数据和源数据的数据一致性问题。因为你访问数据时是首先访问备份数据（效率原因），数据不存在或者失效再访问源数据。即使缓存存在不止这一个问题，但是由于它的存在带来服务质量以及运作效率的提升，是非常重要不可或缺的。

1.3，关于redis

我们常见的缓存大致可以分为应用内缓存和组件缓存。应用内缓存有java中的Map，组件缓存包含我们常用的redis和MemCache。接下来，我们将从数据类型入手，讲解redis的基本用法和原理分析。

二、redis的数据类型与用法

2.1，redis的五种数据类型

redis分为五种数据类型：

  1. string（字符串）
  2. list（链表）
  3. hash（hash）
  4. set（集合）
  5. sorted-set（有序集合）

redis-datatype

2.2，数据类型的基本用法

2.2.1 string

string 是 redis 最基本的类型，你可以理解成与 Memcached 一模一样的类型，一个 key 对应一个 value。string 类型是二进制安全的。意思是 redis 的 string 可以包含任何数据。比如jpg图片或者序列化的对象。string 类型是 Redis 最基本的数据类型，string 类型的值最大能存储 512MB。

redis-string

2.2.2 list

Redis 列表是简单的字符串列表，按照插入顺序排序，你可以添加一个元素到列表的头部（左边）或者尾部（右边）。

redis-list

2.2.3 hash

Redis hash 是一个键值(key=>value)对集合；是一个 string 类型的 field 和 value 的映射表，hash 特别适合用于存储对象。

redis-hash

2.2.4 set

Redis的Set是string类型的无序集合。和列表一样，在执行插入和删除和判断是否存在某元素时，效率是很高的。集合最大的优势在于可以进行交集并集差集操作。集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是O(1)。

redis-set

2.2.5 sorted-set

Redis zset 和 set 一样也是string类型元素的集合,且不允许重复的成员。不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。zset的成员是唯一的,但分数(score)却可以重复。sorted-set是插入有序的，即自动排序。

redis-sorted-set

三、redis数据结构原理

3.1，简单动态字符串（SDS）

3.1.1，结构定义

redis中的字符串是最基本数据类型，所有的字符串（各类数据类型的key值、最基本字符串元素值等）内部都是通过SDS（简单动态字符串）来保存的。下面是SDS在redis中的结构定义：

1
struct sdshdr {
2
  int len;			//记录buf数组中已使用字节的数量，等于SDS所保存字符串的长度
3
  int free;			//记录buf数组中未使用字节的数量
4
  char buf[];		//字节数组，用于保存字符串
5
}

通过代码定义我们可以知道，redis中sds通过len、free、buf来表示一个字符串。其中len记录为字符串长度，free记录未使用字节长度，字节数组buf来记录当前实际存储的值。通过图示我们可以看到字符串“redis”在sds中的表示：

redis-sdshdr

sds中使用buf字节数组存放字符串”redis”，由于”redis”本身占用5个字节，所以字符串长度len为5，没有剩余空间free为0。buf字节数组中我们可以看到，和标准C字符串以空字符结尾一样’\0’。下面展示了另外一个sds示例，与刚才这个sds保存的数据一致，区别在于下面这个sds分配了未使用的空间：

redis-sdshdr

3.1.2，优点

通过上述sds结构定义和示例我们可以对比出redis的sds相对于C语言中普通字符串优点：

  1. O(1)复杂度获取字符串长度。由于sds结构内定义了len字段，可以直接获取当前字符串长度。
  2. 杜绝缓冲区溢出。sds api在对字符串进行操作（添加等需要字节空间）时，会先检查剩余空间（free字段）是否符合操作需求，如果不符合，则先对字符串进行扩容操作。
  3. 减少修改字符串带来的内存重分配次数。
    1. 空间预分配。当对sds的字符串进行修改并且需要进行扩容时，程序不仅会分配修改所需要的空间，还会为sds分配额外未使用的空间。通过空间预分配，减少连续执行字符串增长操作所需内存重分配次数。
    2. 惰性空间释放。当sds需要缩短保存的字符串时，空闲出来的字节数量不立马释放，而是先用free记录起来，并等待将来使用。同时也提供了相应的api让我们可以真正释放sds的未使用空间。
  4. 二进制安全。sds的api处理字符串时，都是以二进制形式来处理，并不会像C语言一样遇到空字符就认为是字符串的结束。数据写入是什么样的，读出来就是什么样的。redis并不是单纯使用sds保存字符，而是保存二进制数据。

3.2，链表

3.2.1，结构定义

链表提供了高效的节点重排能力，以及顺序性节点访问方式。作为一种常用的数据结构，redis自己构建了链表的实现。

使用listNode作为链表节点的定义：

1
typedef struct listNode {
2
    struct listNode *prev;		//指向前一个节点的指针
3
    struct listNode *next;		//指向后一个节点的指针
4
    void *value;							//节点的值
5
} listNode;

多个listNode组成双端链表，如下所示：

redis-listNode

在此基础上，redis利用list将链表整个结构表现出来，list定义：

1
typedef struct list {
2
    listNode *head;													//指向表头节点
3
    listNode *tail;													//指向表尾巴节点
4
    void *(*dup)(void *ptr);								//节点值复制函数
5
    void (*free)(void *ptr);								//节点值释放函数
6
    int (*match)(void *ptr, void *key);			//节点值对比函数
7
    unsigned long len;											//链表所包含节点数量
8
} list;

由一个list和多个listNode组成的图示如下，通过list结构，可以发现对链表操作更加方便

redis-list-struct

3.2.2，优点

  1. 双端。链表节点有prev和next指针，获取某个节点的前置节点和后置节点复杂度都是O(1)。
  2. 无环。表头节点的prev和表尾节点的next指向NULL，顺序访问节点通过NULL结束。
  3. list结构带表头head和表尾tail指针。可以迅速访问表头节点和表尾节点。
  4. O(1)时间复杂度获取链表节点长度。

3.3，字典

3.3.1 结构定义

字典是一个映射（map），一种用于保存键值对的抽象数据结构。在字典中，一个键key和一个值value进行关联，称之为键值对。字典中每个键都是独一无二的，不允许重复。redis构建了自己的字典实现，使用哈希表作为底层实现。一个哈希表里面可以有多个哈希表节点，每个哈希表节点就保存了字典中的一个键值对。

hash表节点定义如下：

1
typedef struct dictEntry {
2
    void *key;								//键值对的键
3
    void *val;								//键值对的值
4
    struct dictEntry *next;		//指向下一个键值对的指针
5
} dictEntry;

dictEntry定义了键值对的键和值，同时还包含有指向下一个键值对dictEntry的指针。为什么会有下一个键值对的指针呢？是因为当计算出的hash值出现冲突的时候，字典通过链地址法解决冲突。

hash表定义如下：

1
typedef struct dictht {
2
    dictEntry **table;			//存储dictEntry节点的数组
3
    unsigned long size;			//hash表大小
4
    unsigned long sizemask;	//hash表大小掩码，用于计算索引值
5
    unsigned long used;			//已经存在的节点数量
6
} dictht;

table是一个数组，数组中的每个元素都是指向dictEntry的指针。size记录了hash表的大小。sizemask作为掩码用于计算每个dictEntry的下标值，大小等于hash表大小size-1。used代表hash表上节点的数量。下图展示了一个大小为4的空hash表：

redis-dict-empty

有两个元素且两个元素冲突的hash表图示：

redis-dict-used

redis中字典定义如下：

1
typedef struct dict {
2
    dictType *type;		//类型特定函数
3
    void *privdata;		//私有数据
4
    dictht ht[2];			//哈希表数组
5
    long rehashidx;		//rehash索引，索引不再进行时rehashidx=-1
6
    unsigned long iterators;
7
} dict;

下面图示为有两个键值对节点的字典：

redis-dict

3.3.2，优点

  1. 哈希算法。使用字典设置的哈希函数计算键key的hash值，然后根据hash值计算下标索引值。

    hash=dict->type->hashFunction(key)

    index=hash&dict->ht[x].sizemask

  2. 解决键冲突。当计算出来的index值和当前hash表中的键冲突时，通过链地址法来解决冲突。即将新节点添加到链表的表头位置，排在其他已有节点的前面。

  3. rehash。

    1. 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量(ht[0].used)：
      1. 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[1].used*2的2n(2的n次方幂)
      2. 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2n。
    2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
    3. 当ht[0]包含的所有键值对都迁移到了ht[1]之后，ht[0]这时已经是一个空表，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]上新创建一个空白哈希表，为下次rehash作准备。

  4. 渐进式hash。为了避免rehash对服务器性能造成的影响，服务器并不是一次性将ht[0]里面所有的键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1]。渐进式哈希餐区分而治之的策略，将rehash键值对所需的计算工作均摊到对字典每个添加、删除、查找和更新的操作上，从而避免了集中式rehash而带来的庞大计算量。在执行rehash期间，rehashidx记录当前已经执行了rehash的原table下标。

3.4，跳跃表

3.4.1，结构定义

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。支持平均O(logN)、最坏O(N)复杂度的节点查找，效率可以和平衡树相媲美，并且实现起来比红黑树更为简单。

redis中跳跃表中节点的定义如下：

1
typedef struct zskiplistNode {
2
    double score; 										//节点保存的分值
3
    struct zskiplistNode *backward;		//后退指针
4
    struct zskiplistLevel {
5
        struct zskiplistNode *forward;	//前进指针
6
        unsigned long span;							//跨度
7
    } level[];													//层
8
} zskiplistNode;

跳跃表使用zskiplistNode作为有序表中的一个节点。节点中有保存的分值，指向上一个节点的后退指针，以及整个节点的层。每层保存了指向下一个节点的指针以及跨度。

跳跃表节点定义如下：

1
typedef struct zskiplist {
2
    struct zskiplistNode *header, *tail;	//头节点、尾巴节点
3
    unsigned long length;									//表中节点的数量
4
    int level;														//表中层数最大的节点的层数
5
} zskiplist;

zskiplist持有了整个跳跃表的头节点和尾节点的指针，同时还保存了跳跃表中节点的数量和层数最大节点的层数。下图展示了有3个跳跃表节点且最高层数为5的跳跃表：

redis-dict

3.4.2，优点

  1. 通过zskiplist持有头尾节点，可以快速到达头尾节点，且能够获取节点的个数。
  2. 节点存储了值，且节点是按照值的大小顺序链表存贮。
  3. 每个节点层数随机生成。每层持有下一跳或者下几跳的节点和跨度，可以迅速跳到对应节点。
  4. 查找平均O(logN)、最坏O(N)时间复杂度，媲美红黑树且比红黑树实现起来简单。

3.5，整数集合

3.5.1，结构定义

1
typedef struct intset {
2
    uint32_t encoding;			// 编码类型
3
    uint32_t length;				// 集合包含元素的数量
4
    int8_t contents[];			// 保存元素的数组
5
} intset;

从intset的结构定义中我们可以知道，包含了一个编码类型，编码类型指定了contents数组里面保存元素的编码；同时intset还持有了集合包含元素数量的length。

整数集合intset是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，redis就会使用整数集合作为集合键的底层实现。图示如下：

redis-intset

inset记录了元素的编码值，当目前的编码值不允许存放更大的元素，占用位数更多的元素要进行插入时，根据新元素的类型，扩展整数集合底层数组空间大小；将contents里面每个元素转化成与新元素相同的类；将新元素插入到底层数组。

3.5.2，重点回顾

  1. 整数集合是集合键的底层实现之一。
  2. 整数集合底层实现为数组，这个数组以有序、无重复的方式保存集合元素，再有需要时，程序会根据新添加元素的类型改变数组的类型。
  3. 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
  4. 整数集合只支持升级操作，不支持降级操作。

3.6，压缩列表

3.6.1，结构定义

压缩列表是列表键和哈希键的底层实现之一。当一个列表键包含少量列表项，并且每个列表项要么是小整数值，要么是比较短的字符串，那么redis就会使用压缩列表来做列表键的底层实现。下面看一下压缩列表的定义：

1
unsigned char *ziplistNew(void) {
2
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
3
    unsigned char *zl = zmalloc(bytes);
4
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
5
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
6
    ZIPLIST_LENGTH(zl) = 0;
7
    zl[bytes-1] = ZIP_END;
8
    return zl;
9
}

redis中的压缩列表没有明确的定义，通过ziplistNew创建一个新的ziplist，我们可以大致画出它的内存结构：

redis-ziplist

各个字段代表的含义如下：

  1. zlbytes：记录整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配或者计算zlend位置时使用。
  2. zltail：记录压缩列表尾节点距离压缩列表起始地址有多少字节，通过这个字段可以计算出尾节点的位置。
  3. zlen：记录了压缩列表包含的节点数量。
  4. entryX：压缩列表的节点，真正保存数据。
  5. zlend：特殊值0xFF，用于标记压缩列表的末端。

节点entry构成如下图：

redis-ziplist-entry

各个字段代表含义如下：

  1. previous_entry_length：记录了上一个节点的长度，字节为单位。
  2. encoding：记录了当前节点content保存的数据的类型（整数类型或者字节类型）以及长度。
  3. content：保存节点的值，可以是一个字节数组或者整数。类型和长度通过encoding决定。

3.6.2，重点回顾

  1. 压缩列表是一种顺序型的数据结构，为了节约内存。
  2. 压缩列表用作列表list和哈希hash的底层实现之一。
  3. 压缩列表可以包含多个节点，每个节点可以保存一个字节数组护着整数值。
坚持原创分享