《redis设计与实现》1-数据结构与对象篇

kinnylee
3,678 阅读19分钟

前言

  • redis性能为什么这么出色？它与其他缓存中间件有什么区别？
  • redis底层使用了哪些数据结构支撑它如此高效的性能？
  • 内部丰富的数据类型底层为什么都使用至少两种数据结构实现？分别是什么？
  • 如果合理的使用redis才能发挥它最大的优势？

学习完《redis设计与实现》前面关于数据结构与对象的章节，以上问题都能得到解答。你也能了解到redis作者如此的煞费苦心设计了这么多丰富的数据结构，目的就是优化内存。学完这些内容，在使用redis的过程中，也会合理的使用以适应它内部的特点。当然新版本的redis支持了更多更丰富的特性，该书基于redis3版本，还没有涉及到那些内容。

《redis设计与实现》这本书非常浅显易懂，作者黄建宏老师，90后。另外还是《redis实战》的译者

另一篇可参考《redis设计与实现》2-数据库实现篇

概述

特点

  1. c语言开发，性能出色，纯内存操作，每秒可处理超过10w读写（QPS）
  2. 多种数据结构，单个最大限制可到1GB(memcached只支持字符串，最大1M)
  3. 受物理内存限制，不能作海量数据的读写。适用于较小数据量的高性能操作和运算上
  4. 支持事务，持久化
  5. 单线程模型（memcached是多线程）

支持的数据类型

  1. Sring
  2. List
  3. Set
  4. SortedSet
  5. hash
  6. Bitmap
  7. Hyperloglogs
  8. Geo
  9. pub/sub

redis为什么这么快

  1. 纯内存操作，没有磁盘io
  2. 单线程处理请求，没有线程切换开销和竞争条件，也不存在加锁问题
  3. 多路复用模型epoll，非阻塞io(多路：多个网络连接；复用：复用同一个线程) 多路复用技术可以让单个线程高效的处理多个连接请求
  4. 数据结构简单，对数据操作也简单。还做了自己的数据结构优化

redis为什么是单线程的

  1. 单线程已经很快了，减少多线程带来的网络开销，锁操作
  2. 后续的4.0版本在考虑多线程
  3. 单线程是指处理网络请求的时候只有一个线程，并不是redis-server只有一个线程在工作。持久化的时候，就是通过fork一个子线程来执行。
  4. 缺点：耗时的命令会导致并发的下降，比如keys *

redis的回收策略

  1. volatile-lru：从过期的数据集 server.db[i].expires中挑选最近最少使用的数据
  2. volatile-ttl：从过期的数据集 server.db[i].expires中挑选将要过期的数据淘汰
  3. volatile-random： server.db[i].expires中挑选任意数据淘汰
  4. allkeys-lru: 从数据集（server.db[i].dict）中挑选最近最少使用的数据淘汰
  5. allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰
  6. no-enviction（驱逐）：禁止驱逐数据

使用注意

  1. redis单线程无法发挥多核cpu性能，可以通过单机开多个redis实例来完善
  2. redis实现分布式锁：先用setnx（如果不存在才设置）争抢锁，抢到后，expire设置过期时间，防止忘记释放。
  3. redis实现一对多消息订阅：sub/pub数据结构
  4. redis实现延时消息队列：zadd时间戳作为score 消费的时候根据时间戳+延时时间做查询操作。

各大版本介绍

redis5版本新增功能：

  • zpopmax zpopmin以及阻塞变种：返回集合中给定分值最大最小的数据数量

reids4版本新增功能：

  • 模块功能，提供类似于插件的方式，自己开发一个.so模块，并加装 作者本人提供了一个神经网络的module。 可到redis-modules-hub上查看更多的module 模块功能使得用户可以将 Redis 用作基础设施， 并在上面构建更多功能， 这给 Redis 带来了无数新的可能性。
  • PSYNC：解决了旧版本的 Redis 在复制时的一些不够优化的地方
  • 缓存清理策略优化 新增last frequently used 对已有策略进行优化
  • 非阻塞DEL FLUSHDB FLUSHALL 解决了之前执行这些命令的时候导致阻塞的问题 Flushdb async, flushall async, unlink(替代del)
  • 添加了swapdb：交换数据库
  • 混合RDB-AOF的持久化格式
  • 添加内存使用情况命令：MEMORY

数据结构

  • redis里面每个键值对都是由对象组成的
  • 键总是一个字符串对象，
  • 值则可以是以下对象的一种：
    • 字符串对象
    • 列表对象
    • 哈希对象
    • 集合对象
    • 有序结合对象

简单动态字符串SDS

数据结构

struct sdshdr {
    uint8_t len; /* used，使用的字节数 */
    uint8_t alloc; /* excluding the header and null terminator，预分配总字节数，不包括结束符\0的长度 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[]; /*c风格的字符，包括结束符\0*/
};
  • 位于sds.h文件
  • SDS遵循C字符串以\0结尾的惯例，存储在buf中（不同于nginx的底层实现，nginx实现时不保存最后一个\0）
  • 但是不计算最后一个字符的长度到len中
  • 保留c风格buf的好处是可以重用一部分c函数库的函数

分配和释放策略

空间预分配

  • 用于优化SDS字符串增长操作，以减少连续执行增长操作所需的内存重分配次数
  • 扩展SDS空间时，先检查未使用的空间是否足够，如果足够直接使用，如果不够，不仅分配够用，还预分配一些空间
  • 预分配策略：
    • 修改后的SDS长度（len的值）< 1MB，预分配同样len大小的空间
    • 修改后的SDS长度（len的值）>= 1MB，预分配1MB大小的空间

惰性空间释放

  • 用于优化SDS字符缩短操作
  • 缩短SDS空间时，并不立即进行内存重分配释放空间，而是记录free的字节数
  • SDS提供相应api，有需要时真正释放空间

比C字符串的优势

  • 获取字符串的长度时间复杂度由O(N)降到O(1)
  • 避免缓冲区溢出
  • 减少修改字符串时带来的内存重分配次数。内存分配会涉及复杂算法，且可能需要系统调用，非常耗时。
  • 二进制安全：c语言的结束符限制了它只能保存文本数据，不能保存图片，音频等二进制数据

链表

数据结构

位于adlist.h文件

typedef struct listNode {
    struct listNode *prev; // 前置节点
    struct listNode *next; // 后置节点
    void *value;//节点值
} listNode;

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;

特点

  • 双端队列，可以获取某个节点前置节点和后置节点,复杂度为O(1)
  • 无环
  • 获取表头和表尾复杂度为O(1)
  • 带长度，获取链表长度复杂度为O(1)
  • 多态：使用void*保存节点值，可保存不同类型的值

字典

数据结构

位于dict.h文件

哈希表

// 哈希表
typedef struct dictht {
    dictEntry **table; // 一个数组，数组中每个元素都是指向dictEntry结构的指针
    unsigned long size; // table数组的大小
    unsigned long sizemask; // 值总数size-1
    unsigned long used; // 哈希表目前已有节点（键值对）的数量
} dictht;

哈希节点

// 每个dictEntry都保存着一个键值对，表示哈希表节点
typedef struct dictEntry {
    void *key; // 键值对的键
    // 键值对的值，可以是指针，整形，浮点型
    union { 
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 哈希表节点指针，用于解决键冲突问题
} dictEntry;

字典类型

每个字典类型保存一簇用于操作特定类型键值对的函数

typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*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;

字典

// 字典
typedef struct dict {
    dictType *type; // 不同键值对类型对应的操作函数
    void *privdata; // 需要传递给对应函数的参数
    dictht ht[2]; // ht[0]用于存放数据，ht[1]在进行rehash时使用
    long rehashidx; /* rehashing not in progress if rehashidx == -1，目前rehash的进度*/
    unsigned long iterators; /* number of iterators currently running */
} dict;

哈希算法

  • redis使用MurmurHash2算法计算键的hash值
  • 哈希值与sizemask取或，得到哈希索引
  • 哈希冲突（两个或以上数量键被分配到哈希表数组同一个索引上）：链地址法解决冲突

rehash

  • 对哈希表进行扩展或收缩，以使哈希表的负载因子维持在一个合理范围之内
  • 负载因子 = 保存的节点数（used）/ 哈希表大小（size）

rehash步骤包括

  • 为字典的ht[1]哈希表分配空间，大小取决于要执行的操作以及ht[0]当前包含的键值对数量
    • 扩展操作：ht[1]大小为第一个大于等于ht[0].used乘以2的2的n次幂
    • 收缩操作：ht[1]大小为第一个大于等于ht[0].used的2的n次幂
  • 将保存在ht[0]的所有键值对rehash到ht[1]上面：重新计算键的哈希值和索引值
  • 当所有ht[0]的键值对都迁移到ht[1]之后，释放ht[0]，将ht[1]置为ht[0],并新建一个恐怖hash作为ht[1]

自动扩展的条件

  • 服务器没有执行BGSave命令或GBRewriteAOF命令，并且哈希表的负载因子 >= 1
  • 服务器正在执行BGSave命令或GBRewriteAOF命令，并且哈希表的负载因子 >= 5
  • BGSave命令或GBRewriteAOF命令时，服务器需要创建当前服务器进程的子进程，会耗费内存，提高负载因子避免写入，节约内存

自动收缩的条件

  • 哈希表负载因子小于0.1时，自动收缩

渐进式rehash

  • ht[0]数据重新索引到ht[1]不是一次性集中完成的，而是多次渐进式完成（避免hash表过大时导致性能问题）

渐进式rehash详细步骤

  • 为ht[1]分配空间，让自动同时持有两个哈希表
  • 字典中rehashidx置为0，表示开始执行rehash（默认值为-1）
  • rehash期间，每次对字典执行操作时，顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]
  • 全部rehash完毕时，rehashidx设为-1

注意点

  • rehash的所有操作会在两个哈希表进行
  • 新增加的值一律放入ht[1]，保证数据只会减少不会增加

跳跃表

  • 跳跃表是一种有序数据结构，通过在每个节点维持多个指向其他节点的指针，达到快速访问节点的目的
  • 时间复杂度：最坏O(N)，平均O(logN)
  • 大部分情况下，效率可与平衡树媲美，不过比平衡树实现简单
  • 有序集合的底层实现之一

数据结构

位于server.h文件中

// 跳跃表节点
typedef struct zskiplistNode {
    sds ele; // 成员对象
    double score; // 分值，从小到大排序
    struct zskiplistNode *backward; // 后退指针，从表尾向表头遍历时使用
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span; // 跨度，记录两个节点之间的距离
    } level[]; // 层，是一个数组
} zskiplistNode;

// 跳跃表相关信息
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表头和表尾
    unsigned long length; // 跳跃表长度（包含节点的数量）
    int level; // 跳跃表内层数最大那个节点的层数（不包括表头节点层数）
} zskiplist;

  • level数组的大小在每次新建跳跃表的时候，随机生成，大小介于1-32直接
  • 遍历操作只使用前进指针，跨度用来计算排位（rank），沿途访问的所有层跨度加起来就是节点的排位
  • 多个节点可以包含相同的分支，但每个节点成员对象是唯一的

整数集合

  • intset是集合键的底层实现之一
  • 当一个集合只包含整数值原素，且数量不多时，会使用整数集合作为底层实现

数据结构

位于intset.h文件

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; // 长度
    int8_t contents[]; // 内容,数组内容类型取决于encoding属性，并不是int8_t。按照大小排序，没有重复
} intset;

升级

  • 当我们要将一个新元素添加到整数集合里，并且新元素的类型比整数集合现有所有的元素类型都要长时，集合要先进行升级才能添加新数据
  • 升级步骤包括三步：
    • 根据类型，扩展大小，分配空间
    • 将底层数组数据都转换成新的类型，并反倒正确位置
    • 新元素添加到底层数组里面
  • 添加元素可能导致升级，所以添加新元素的世界复杂度为O(N)
  • 不支持降级，升级后将一直保持新的数据类型

升级的好处

  • 提高灵活性
  • 节约内存

压缩列表

  • ziplist是列表键和哈希键的底层实现之一
  • redis为了节约内存而开发的顺序型数据结构
  • 当列表键只包含少量列表项，且每个列表项要么是小整数，要么是短字符串，就使用ziplist作为列表键底层实现
  • 压缩列表遍历时，从表位向表头回溯遍历
  • ziplist没有专门的struct来表示

压缩列表的构成

属性 类型 长度 用途
zlbytes uint32_t 4字节 整个压缩列表占用的内存字节数
zltail uint32_t 4字节 表尾节点距离压缩列表起始地址有多少字节，无需遍历就可得到表尾节点
zllen uint16_t 2字节 节点数量，小于65535时是实际值，超过时需要遍历才能算出
entryN 列表节点 不定 包含的各个节点
zlend uint8_t 1字节 特殊值0xFF,末端标记

压缩列表节点的构成

  • previos_entry_length：前一个节点的长度，用于从表尾向表头回溯用
    • 如果前面节点长度小于254字节，preivos_entry_length用1字节表示
    • 如果前面节点长度小于254字节，preivos_entry_length用5字节表示，第1个字节为0xFE（254），后面四个字节表示实际长度
  • encoding：记录content的类型以及长度，encoding分为两部分，高两位和余下的位数，最高两位的取值有以下情况：
    最高两位取值 表示是数据类型 encoding字节数 余下的bit数 最大范围
    00 字符数组 一个字节 6bit 63位
    01 字符数组 两个字节 14bit 2^14-1
    10 字符数组 五个字节 4*8，第一个字节余下的6bit留空 2^32-1位
    11 整数 1个字节 000000 int16_t类型整数
    11 整数 1个字节 010000 int32_t类型整数
    11 整数 1个字节 100000 int64_t类型整数
    11 整数 1个字节 110000 24位有符号整数
    11 整数 1个字节 111110 8位有符号整数
    11 整数 1个字节 xxxxxx 没有content，xxxx本身就表示了0-12的整数
  • content：保存节点的值

连锁更新

  • 连续多个节点大小介于254左右的节点，因扩展导致连续内存分配的情况。不过在时间情况下，这种情况比较少。

对象

概述

  • redis并没有直接使用前面的数据结构来实现键值对的数据库，而是基于数据结构创建了一个对象系统，每种对象都用到前面至少一种数据结构
  • 每个对象都由一个redisObject结构来表示
//server.h
typedef struct redisObject {
   unsigned type:4; //类型
   unsigned encoding:4; // 编码
   // 对象最后一个被命令程序访问的时间
   unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                           * LFU data (least significant 8 bits frequency
                           * and most significant 16 bits access time). */
   int refcount; // 引用计数
   void *ptr; // 指向底层的数据结构指针
} robj;

使用对象的好处

  • 在执行命令之前，根据对象类型判断一个对象是否可以执行给定的命令
  • 针对不同厂家，Wie对象设置多种不同的数据结构实现，从而优化效率
  • 实现了基于引用计数的内存回收机制，不再使用的对象，内存会自动释放
  • 引用计数实现对象共享机制，多个数据库共享同一个对象以节约内存
  • 对象带有时间时间积累信息，用于计算空转时间

redis中的对象

  • 字符串对象
  • 列表对象
  • 哈希对象
  • 集合对象
  • 有序结合对象

对象的类型与编码

对象的类型

对象 对象type属性 type命令的输出
字符串对象 REDIS_STRING string
列表对象 REDIS_LIST list
哈希对象 REDIS_HASH hash
集合对象 REDIS_SET set
有序集合对象 REDIS_ZSET zset

对象的编码

  • 编码决定了ptr指向的数据类型，表明使用什么数据类型作为底层实现
  • 每种类型对象至少使用两种不同的编码
  • 通过编码，redis可以根据不同场景设定不同编码，极大提高灵活性和效率
编码常量 对应的数据结构 OBJECT ENCODING命令输出
REDIS_ENCODING_INT long类型的整数 “int”
REDIS_ENCODING_EMBSTR embstr编码的简单动态字符串 “embstr”
REDIS_ENCODING_RAW 简单动态字符串 “raw”
REDIS_ENCODING_HT 字典 “hashtable”
REDIS_ENCODING_LINKEDLIST 双端链表 “linkedlist”
REDIS_ENCODING_ZIPLIST 压缩列表 “ziplist”
REDIS_ENCODING_INTSET 整数集合 “intset”
REDIS_ENCODING_SKIPLIST 跳跃表和字典 “skiplist”

字符串对象

  • 字符串对象的编码可以是
    • int
    • raw
    • embstr
  • 浮点数在redis中也是作为字符串对象保存，涉及计算时，先转回浮点数。
字符串对象内容 长度 编码类型
整数值 - int
字符串值 小于32字节 embstr
字符串值 大于32字节 raw

embstr编码是专门用于保存短字符串的一种优化编码方式。这种编码和raw编码一样，都使用redisObject结构和sdshdr结构来表示对象。区别在于：

  • raw编码调用两次内存分配函数来分别创建redisObject和sdrhdr结构
  • embstr则调用一次内存分配函数来创建一块连续空间，里面包括redisObject和sdrhdr

编码转换

int编码和embstr编码的对象满足条件时会自动转换为raw编码的字符串对象

  • int编码对象，执行命令导致对象不再是整数时，会转换为raw对象
  • embstr编码没有相应执行函数，是只读编码。涉及修改时，会转换为raw对象

字符串命令

redis中所有键都是字符串对象，所以所有对于键的命令都是针对字符串键来构建的

  • set
  • get
  • append
  • incrbyfloat
  • incrby
  • decrby
  • strlen
  • strrange
  • getrange

列表对象

  • 列表对象的编码可以是
    • ziplist
    • linkedlist

编码转换

使用ziplist编码的两个条件如下，不满足的都用linkedlist编码（这两个条件可以在配置文件中修改）:

  • 保存的所有字符串元素的长度都小于64字节
  • 列表的元素数量小于512个

列表命令

  • lpush
  • rpush
  • lpop
  • rpop
  • lindex
  • llen
  • linsert
  • lrem
  • ltrim
  • lset

哈希对象

哈希对象的编码可以是

  • ziplist
  • hashtable

编码转换

  • 使用ziplist需要满足两个条件，不满足则都使用hashtable（这两个条件可以在配置文件中修改）
    • 所有键值对的键和值的字符串长度都小于64字节
    • 键值对数量小于512个

哈希命令

  • hset
  • hget
  • hexists
  • hdel
  • hlen
  • hgetall

集合对象

集合对象的编码可以是：

  • intset：所有元素保存在整数集合里
  • hashtale：字典的值为null

编码转换

集合使用intset需要满足两个条件，不满足时使用hashtable（参数可通过配置文件修改）

  • 保存的所有元素都是整数值
  • 元素数量不超过512个

集合命令

  • sadd
  • scard
  • sismember
  • smembers
  • srandmember
  • spop
  • srem

有序结合对象

有序集合的编码可以是

  • ziplist：每个元素使用两个紧挨在一起的节点表示，第一个表示成员，第二个表示分值。分值小的靠近表头，分值大的靠近表尾
  • skiplist：使用zset作为底层实现，zset结构同时包含了字典和跳跃表，分别用于根据key查找score和分值排序或范围查询
// 两种数据结构通过指针共享元素成员和分值，不会浪费内存
typedef struct zset {
    zskplist *zsl; //跳跃表，方便zrank，zrange
    dict *dict; //字典，方便zscore
}zset;

编码转换

当满足以下两个条件时，使用ziplist编码，否则使用skiplist（可通过配置文件修改）

  • 保存的元素数量少于128个
  • 成员长度小于64字节

有序集合命令

  • zadd
  • zcard
  • zcount
  • zrange
  • zrevrange
  • zrem
  • zscore

类型检查和命令多态

redis的命令可以分为两大类：

  • 可以对任意类型的键执行，如
    • del
    • expire
    • rename
    • type
    • object
  • 只能对特定类型的键执行，比如前面各种对象的命令。是通过redisObject的type属性实现的

内存回收

redis通过对象的refcount属性记录对象引用计数信息，适当的时候自动释放对象进行内存回收

对象共享

  • 包含同样数值的对象，键的值指向同一个对象，以节约内存。
  • redis在初始化时，创建一万个字符串对象，包含从0-9999的所有整数值，当需要用到这些值时，服务器会共享这些对象，而不是新建对象
  • 数量可通过配置文件修改
  • 目前不包含字符串的对象共享，因为要比对字符串是否相同本身就会造成性能问题

对象空转时长

  • 空转时长=现在时间-redisObject.lru，lru记录对象最后一次被访问的时间
  • 当redis配置了最大内存（maxmemory）时，回收算法判断内存超过该值时，空转时长高的会优先被释放以回收内存

参考命令

# 设置字符串
set msg "hello world"
rpush numbers 1 2 3 4 5
llen numbers
lrange numbers 0 5
# 获取键值使用的底层数据结构
object encoding numbers
# 查看对象的引用计数值
object refcount numbers
# 对象空转时长: value=now-object.lru
object idletime numbers

参考文献

  • 《redis设计与实现》
avatar
文章
阅读
粉丝