乐趣区

关于redis:万字长文38-图爆肝-Redis-基础

jiezi

00 前言

Redis 在互联网技术存储方面的应用能够说是十分宽泛了，只有是接触过 Java 开发的敌人就算你没用过，都会听过它。在面试也是十分高频的一个知识点。

最近，我的的小弟 小胖和老王 就对 Redis 十分感兴趣；我举荐它一本书《Redis 设计与实现》。谁知这货说看不下去，非要我来总结一波。所以本文算是给 小胖和老王 的学习材料，也是我本人的学习笔记。心愿对你有帮忙。

还是老规矩，先上张脑图。全文 13274 字，从下午 2 点爆肝到早晨 9 点，先上张思维导图镇楼：

0.1 往期精彩

1、小胖问我：select 语句是怎么执行的？

2、女朋友问我：MySQL 索引的原理是怎么的？

3、小胖问我：MySQL 日志到底有啥用？

4、老王问我：MySQL 事务与 MVCC 原理是怎么的？

5、女朋友问我：MySQL 的锁机制是怎么的？

01 什么是 Redis？

官网是这么形容的：

Redis（用 C 语言实现的）是一个开源的，基于内存的数据结构存储，可用作于数据库、缓存、消息中间件。

信息简洁明了，一下就晓得了三个点：基于内存、用作缓存、多种数据结构。

的了，那就从这三个方面开始钻研呗。

1.0 为什么要用 Redis 做缓存？

下面说了，用作缓存。有些小伙伴可能会问：有 MySQL 数据库就得了呗？干嘛还要缓存？而且为啥要用 Redis 做？Map 不行嘛？

  • 第一、二个问题，都晓得 MySQL 数据是存在磁盘的，而 CPU 拜访磁盘是十分慢的。如果遇到并发高的时候，所有线程每次都要拜访磁盘，预计得挂。

到底有多慢？请看链接：zhuanlan.zhihu.com/p/24726196

Redis 和 Map 做下比照，就晓得为啥不适合了。

  • Map 是本地缓存，如果在多台机器部署，必须每个机器都要复制一份，否则造成缓存不统一；Redis 是分布式缓存，部署在多台机器，也是用的同一份缓存，放弃了一致性，问题不大。
  • Map 做缓存，数据量大的话会导致 JVM 内存飙升，进而拖垮程序，并且 JVM 挂了，还会导致数据失落；Redis 能够用更大容量的内存（看你的配置，即几十 G 都没问题）做缓存，并且还能够长久化到磁盘。

02 Redis 的数据结构

你可能第一反馈不就 “String（字符串）、List（列表）、Hash（哈希）、Set（汇合）和 Sorted Set（有序汇合）么？”，太简略了，我都会。

老铁你错了，你说的是 Redis 的数据类型只有 5 种，也就是他的表现形式。而我说的数据结构是底层的，有 6 种，别离是简略动静字符串、双向链表、压缩列表、哈希表、跳表和整数数组，它们的对应关系如下：

由上图可知 String 类型的底层实现只有一种数据结构，而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现构造都是汇合。

看到这里，你可能又有疑难了。这些数据结构都是值的底层实现，键和值自身之间用什么构造组织？

2.0 键和值用什么构造组织？

实际上，Redis 应用了一个哈希表来保留所有键值对。它的存储是以 key-value 的模式的。key 肯定是字符串，value 能够是 string、list、hash、set、sortset 中的轻易一种。

一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。每个哈希桶中保留了键值对数据，哈希桶中的元素保留的并不是值自身，而是指向具体值的指针。这点从下图能够看出：

哈希桶中的 entry 元素中保留了 key 和 value 指针，别离指向了理论的键和值，这样一来，即便值是一个汇合，也能够通过 *value 指针被查找到。

redis 的键值都是 redisObject 对象，即在创立时会生成一个用于键名的 redisObject 对象和一个用于键值的 redisObject 对象。这点从源码也能够看进去：

typedef struct redisObject {
    // 类型
    unsigned type:4;
    
    // 编码
    unsigned encoding:4;
    
    // 指向数据的指针
    void *ptr;

    // 记录对象最初一次被程序拜访工夫，用于计算空转时长(以后工夫 -lru)
    unsigned lru:22; /* lru time (relative to server.lruclock) */
    
    // 援用计数，用于内存回收
    int refcount;
} robj;

也就是说上图 entry 中的健值指针就别离指向这样一个 redisObject。其中 type、encoding 和 ptr 是最重要的三个属性。type 记录了对象所保留的值的类型，它的值可能是以下常量的其中一个。

/*
 * 对象类型
 */
#define REDIS_STRING 0  // 字符串
#define REDIS_LIST 1    // 列表
#define REDIS_SET 2     // 汇合
#define REDIS_ZSET 3    // 有序集
#define REDIS_HASH 4    // 哈希表

encoding 记录了 对象所保留的值的编码，它的值可能是以下常量的其中一个.

/*
 * 对象编码
 */
#define REDIS_ENCODING_RAW 0            // 编码为字符串
#define REDIS_ENCODING_INT 1            // 编码为整数
#define REDIS_ENCODING_HT 2             // 编码为哈希表
#define REDIS_ENCODING_ZIPMAP 3         // 编码为 zipmap
#define REDIS_ENCODING_LINKEDLIST 4     // 编码为双端链表
#define REDIS_ENCODING_ZIPLIST 5        // 编码为压缩列表
#define REDIS_ENCODING_INTSET 6         // 编码为整数汇合
#define REDIS_ENCODING_SKIPLIST 7       // 编码为跳跃表

比方，咱们在 redis 外面 put (“ 狗哥 ”,666)，在 redisObject 实际上是这样寄存的：

2.1 SDS 简略动静字符串

简略动静字符串 (Simple dynamic string,SDS)

跟传统的 C 语言字符串不一样，Redis 应用了 SDS 来构建本人的字符串对象，源码如下：

struct sdshdr{

    // 字节数组，用于保留字符串
    char buf[];

    // 记录 buf 数组中已应用的字节数量，也是字符串的长度
    int len;

    // 记录 buf 数组未应用的字节数量
    int free;
}

图示：

buf 属性是一个 char 类型的数组，最初一个字节保留了空字符 ’\0’，不算入 len 长度。

2.1.0 为什么应用 SDS？

SDS 比 C 字符串好在哪？

  • 常数复杂度获取字符串长度：C 字符串不记录长度，统计长度只能一一遍历字符，复杂度是 O(N)；而 SDS 在 len 属性中记录了本身长度，复杂度仅为 O(1)。
  • 不会产生缓冲区溢出 ：SDS 不会产生溢出的问题，如果批改 SDS 时，空间有余。先会扩大空间，再批改！( 外部实现了动静扩大机制)。
  • SDS 能够 缩小内存调配的次数 (空间预调配 & 惰性空间开释)。在扩大空间时，除了调配批改时所必要的空间，还会调配额定的闲暇空间 (free 属性)。
  • SDS 是 二进制平安的，所有 SDS API 都会以解决二进制的形式来解决 SDS 寄存在 buf 数组里的数据。

2.2 链表

链表，大家都很相熟了吧？在 Java 中 LinkedList 的底层数据结构就是链表 + 数组实现的。那 Redis 中的链表是怎么的呢？

依照常规，上源码。它应用 listNode 构造（源码位于 adlist.h）示意链表的每个节点：

typedef strcut listNode{
    // 前置节点
    strcut listNode  *pre;

    // 后置节点
    strcut listNode  *pre;

    // 节点的值
    void  *value;
}listNode

多个 listNode 能够通过 prev 和 next 指针组成一个双向链表，像这样：

节点示意进去了，整个链表又该怎么示意呢？Redis 应用 list 构造（源码位于 adlist.h）来构建链表，上源码：

typedef struct list{

    // 表头结点
    listNode  *head;

    // 表尾节点
    listNode  *tail;

    // 链表长度
    unsigned long len;

    // 节点值复制函数
    void *(*dup) (viod *ptr);

    // 节点值开释函数
    void  (*free) (viod *ptr);

    // 节点值比照函数
    int (*match) (void *ptr,void *key);

}list

2.2.0 Redis 链表的个性

  • 双端：有 prev 和 next 两个指针；能够前后挪动。
  • 无环：链表不闭环，prev 和 next 都指向 null，链表拜访以 null 为起点。
  • 获取带表头指针、表尾指针、节点数量的工夫复杂度均为 O (1)。
  • 链表应用 void * 指针来保留节点值，能够保留各种不同类型的值。

2.3 哈希表

哈希表，大家也都不生疏吧？在 Java 中哈希表的底层数据结构就是数组 + 链表实现的。那 Redis 中的哈希表是怎么实现的呢？

依照常规，上源码。哈希表应用 dictht 构造（源码位于 dict.h）示意哈希表，源码如下：

typedef struct dictht{
    // 哈希表数组
    dictEntry **table;  

    // 哈希表大小，也即 table 大小
    unsigned long size;    

    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size-1
    unsigned long sizemark;     

    // 哈希表已有节点数量
    unsigned long used;
}dictht

sizemark 和哈希值决定一个键应该被放到 table 数组的那个索引上。PS：就是 Java 中计算哈希值决定地位的办法。

图示一个大小为 4 的空哈希表（不蕴含任何键值）

哈希表节点应用 dictEntry 构造示意，每个 dictEntry 都保留着一个键值对。源码如下：

 typedef struct dictEntry {
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_tu64;
        int64_ts64;
    }v; 

    // 指向下个哈希节点，组成链表
    struct dictEntry *next;
}dictEntry;

key 解释得很分明了；说说 v 属性，它 保留着键值对中的值，能够是一个指针，或者是一个 uint64_t 整数，又或者是一个 int64_t 整数。

next 则是执行下一个哈希表节点的指针，能够将多个哈希值雷同的键值对连贯在一起作为一个链表，以此来解决键抵触（collision）的问题。PS：参考 Java 中 HashMap 是怎么解决抵触的。旧文：《HashMap 源码解读》有提过。

图示通过 next 指针把雷同索引值的键 k1 和 k0 连贯在一起。

为了更好实现 rehash（扩容）；Redis 又在哈希表之上封装了一层，称之为字典。由 dict 构造示意，源码如下：

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 公有数据
    void * privdata; 
    // 哈希表，代表两个哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 - 1 
    in trehashidx; /*rehashing not in pro gress if rehashidx==-1*/
}dict;

-------------------------------------------------------

typedef struct dictType{
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void * key);

    // 复制键的函数
    void *(*keyDup)(void *private, const void *key);

    // 复制值的函数
    void *(*valDup)(void *private, const void *obj);  

    // 比照键的函数
    int (*keyCompare)(void *privdata , const void *key1, const void *key2)

    // 销毁键的函数
    void (*keyDestructor)(void *private, void *key);

    // 销毁值的函数
    void (*valDestructor)(void *private, void *obj);  
}dictType

type 属性和 privdata 属性是针对不同类型的键值对，为创立多态字典而设置的。

  • type 是一个指向 dictType 的指针，每个 dictType 保留了一簇用于操作特定类型键值对的函数，Redis 为用处不同的字典设置不同的类型特定函数
  • 而 privdata 则保留了传给类型特定函数的可选参数
  • ht 是蕴含了两个哈希表的数组；ht[0] 寄存实在数据，ht[1] 在对 ht[0] 进行 rehash（扩容）时应用。

最终，你会发现其实所谓的字典就是两个哈希表组成的。图式构造如下：

2.3.0 哈希抵触

当往哈希表写入大量数据时，不可避免的就呈现多个 key 计算出来的哈希值雷同。也就是多个不同的 key 须要放到同一个哈希桶，这就是所谓的 哈希抵触。

而 Redis 解决哈希抵触的伎俩很 Java 一样，都是链式哈希：同一个哈希桶中的多个元素用一个链表来保留，它们之间顺次用指针连贯。

如图，假如 entry1、entry2、entry3 的哈希值都是 3；那么他们将寄存在下标为 3 的哈希桶外面，并转换成链表。

PS：没懂哈希抵触的看旧文。旧文：《HashMap 源码解读》有具体例子解析。

当一直产生哈希抵触，链表越来越长，影响查问性能时，Redis 就须要 rehash。

2.3.1 rehash（扩容）

Redis 开始执行 rehash，这个过程分为三步：

  • 1、给哈希表 2 调配更大的空间，例如是以后哈希表 1 大小的两倍；
  • 2、把哈希表 1 中的数据从新映射并拷贝到哈希表 2 中；
  • 3、开释哈希表 1 的空间。

如此，就能够从哈希表 1 切换到哈希表 2，用增大的哈希表 2 保留更多数据，而原来的哈希表 1 留作下一次 rehash 扩容备用。

你必定认为这样就完满了？但还有坑，当哈希表 1 数据量很大，如果一次性复制就会造成线程阻塞，无奈服务其余申请 。Redis 不容许这种事产生，因而应用了 渐进式 rehash。

PS：没懂 rehash 的看旧文。旧文：《HashMap 源码解读》有具体例子解析。

2.3.2 渐进式 rehash

啥是渐进式 rehash？

在第二步拷贝数据时，Redis 依然失常解决客户端申请，每解决一个申请，顺带从哈希表 1 中的第一个索引地位开始，把这个地位上所有的 entry 复制到哈希表 2 中，下个申请就复制地位 2；直至全副复制实现。

过程如下图所示：

具体到代码，它的过程是这样的：

  • 1、在字典中维持一个索引计数器变量 rehashidx，并将设置为 0，示意 rehash 开始。
  • 2、在 rehash 期间，客户端每次对字典进行 CRUD 操作时，会将 ht [0] 中 rehashidx 索引上的值 rehash 到 ht [1]，操作实现后 rehashidx+1。
  • 3、字典操作一直执行，最终在某个工夫点，所有的键值对实现 rehash，这时将 rehashidx 设置为 – 1，示意 rehash 实现

说到这，你可能还有以下几点疑难？

只有在操作字典的时候才进行复制数据吗？如果客户端只操作一次字段是不是就完不成 rehash 了？

渐进式 rehash 执行时，除了依据针对字典的 CRUD 操作来进行数据迁徙，Redis 自身还会有一个定时工作在执行 rehash，如果没有针对字典的申请时，这个定时工作会周期性地（例如每 100ms 一次）搬移一些数据到新的哈希表。

渐进式 rehash，CRUD 到底在哪个哈希表操作呢？

在渐进式 rehash 过程中，字典会同时应用两个哈希表 ht [0] 和 ht [1]，所有的 CRUD 操作也会在两个哈希表进行。

比方要查找一个键时，服务器会优先查找 ht [0]，如果不存在，再查找 ht [1]。当执行 新增操作 时，新的键值对一律保留到 ht [1]，不再对 ht [0] 进行任何操作，以保障 ht [0] 的键值对数量只减不增，最初变为空表。

2.4 跳跃表

跳跃表在 Java 中很少接触到，大家对这个知识点也是挺生疏的。之前在学习数据结构是看到过小灰的一篇文章，写得通俗易懂，大家能够看下，倡议看完再往下看。

https://mp.weixin.qq.com/s/CO…

跳跃表 (shiplist) 是实现 sortset (有序汇合) 的底层数据结构之一；除此以外，在集群节点中也有用到它。

Redis 的跳跃表由 zskiplistNode 和 zskiplist 两个构造定义，源码位于 redis.h 文件中。其中前者是跳跃表的构造；后者的作用是保留跳跃表的节点数量与头、尾节点的指针等信息。

typeof struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 后退指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];} zskiplistNode;

如下图所示，展现了不同层高的跳跃表节点

typeof struct zskiplist {
    // 表头节点，表尾节点
    struct skiplistNode *header,*tail;
    // 表中节点数量
    unsigned long length;
    // 表中最大层数
    int level;
} zskiplist;

下图展现了一个跳跃示意例：

图片最右边的是 zskiplist 构造，蕴含：

  • header：指向跳跃表的表头节点。
  • tail：指向跳跃表的表尾节点。
  • level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
  • length：记录跳跃表的长度，也即是，跳跃表目前蕴含节点的数量（表头节点不计算在内）。

zskiplist 构造右方的是四个 zskiplistNode 构造，蕴含：

  • 层：比方节点中的 L1、L2、L3 等，包含后退指针和跨度
  • 后退指针：用于拜访位于表尾方向的其余节点
  • 跨度：记录了后退指针所指向节点和以后节点的间隔
  • 后退指针：指向以后节点的前一个节点，从表尾向表头遍历
  • 分值：节点按各自分值从小到大排列
  • 成员对象：节点所保留的成员对象

PS：跳跃表这块的内容比拟多，比拟难说分明实现细节。具体的看下面的链接，以及《Redis 设计与实现》这本书（说得很好，微信读书网页版就有）

2.5 整数汇合

整数汇合是 Set（汇合）的底层数据结构之一。当 Set 只蕴含整数值元素，并且这个 Set 的元素数量不多时，Redis 就会应用整数汇合作为 Set 的底层实现。

Redis 应用了 intset 用于保留整数值汇合，它保障了有序以及不反复。源码如下：

typeof struct intset {
    // 编码方式
    unit32_t encoding;
    // 汇合蕴含的元素数量
    unit32_t lenght;
    // 保留元素的数组
    int8_t contents[];} intset;

一个保留了 5 个整数的汇合如下所示：

length 就不说了，次要说下 contents 和 encoding 的关系；contents 的真正类型取决于 encoding 的值：

  • INTSET_ENC_INT16
  • INTSET_ENC_INT32
  • INTSET_ENC_INT64

这三个值别离对应 16、32、64 编码对应能寄存的数字范畴是不一样的。16 最小（-32768~32767），32 在两头（-2147483648~2147483647）64 最大（-9223372036854775808~9223372036854775807）。

如下图所示为 INTSET_ENC_INT16 类型汇合寄存 5 位整数占用的空间：16 * 5

2.5.0 降级操作

如果 contents 原本保留 1、3、5 三个整数值，前面加一个 2147483647456。

那么只有 2147483647456 是真正须要 int64_t 类型来保留的，而其余的 1、3、5 都能够用 int16_t 类型来保留；这时是整体降级，所有元素都会被降级为 int64_t 类型。

也就是说原本是 int16_t 类型的汇合，要放入大于自身的整数。就须要降级，步骤如下：

  • 1、依据新元素类型拓展整数汇合底层数组的空间并为新元素调配空间。
  • 2、将底层数组现有的所有元素都转换成与新元素雷同的类型，并将类型转换后的元素放到正确的位上，须要维持底层数组的有序性质不变。
  • 3、将新元素增加到底层数组。

举个栗子：

1、原来是数组是 INTSET_ENC_INT16 类型 3 位，占用 48 位空间；

2、插入整数 65535，超出 INTSET_ENC_INT16 范畴；降级为 INTSET_ENC_INT32。须要的空间也从 48 加到 128 位。如下所示：新调配空间 = 128 – 48 = 80

3、元素 3 排名第三，挪动到 contents 索引 2 地位；其余相似，元素 2 挪动到索引 1 地位；元素 1 挪动到索引 0 地位

4、最初增加新元素 65535 即可实现降级。

留神点：整数汇合只反对降级、不反对降级。

2.6 压缩列表

压缩列表是 list 和 hash 的底层实现之一，当 list 只蕴含大量元素，并且每个元素都是小整数值，或者是比拟短的字符串，压缩列表会作为 list 的底层实现。

压缩列表（ziplist）是 Redis 为 节约内存 而开发，它的理念是 多大元素用多大内存。

如下图，依据每个节点的理论存储的内容决定内存的大小，第一个节点占用 5 字节，第二个节点占用 5 字节，第三个节点占用 1 字节，第四个节点占用 4 字节，第五个节点占用 3 字节。

图示为 ziplist 的构造：它相似于一个数组，不同的是它在表头有三个字段 zlbytes、zltail 和 zllen；别离示意列表长度、列表尾的偏移量和元素的个数；表尾有 zlend，列表完结的标识。

2.6.0 节点形成

图示一个压缩列表中一个节点的形成：

  • previous_entry_length：记录前一个节点的长度
  • encoding：编码，管制 content 的类型和长度；分为字节数组编码和整数编码
  • content：保留节点值，能够是一个字节数组或整数

2.6.1 压缩列表的查找

如果查找的是第一个元素或最初一个元素，可通过表头三个字段的长度间接定位，复杂度是 O (1)。而查找其余元素时，只能一一查找，复杂度是 O (N)。

倒序遍历：首先指针通过 zltail 偏移量指向表尾节点，而后通过指向 节点记录的前一个节点的长度顺次向前遍历拜访整个压缩列表。

03 数据类型与数据结构

还记得文章结尾那张数据类型与底层数据结构的对应关系图吗？长这样：

Redis 这种对应关系实际上是由 redisObject 的 type（类型）和 encoding（编码）独特决定的，具体对应关系如下：

上面来具体介绍下，什么条件下应用那种类型实现对应的对象。比方：String 什么状况下用 int 编码实现？什么状况下用 embstr 编码实现？什么状况下用 raw 编码实现呢？

3.0 字符串（String）对象

从上图得悉，String 有 int、raw、embst 三种编码格局：

  • int：整数值，能够用 long 类型示意，应用整数值保留对象
  • raw：字符串值且长度 > 32 字节，应用 SDS 保留对象
  • embstr：字符串值且长度 < 32 字节，应用 embstr 编码的 SDS 保留对象

PS：对于浮点数（long double 类型示意的），Redis 会将浮点数转换成字符串值；最终视长度决定用那种编码（embstr 或 raw）保留。取出时，再将其转成浮点值。

3.0.0 embstr 和 raw 有啥区别？

  • raw 分配内存和开释内存的次数是 两次，embstr 是一次
  • embstr 编码的数据保留在一块 间断的内存 外面

3.0.1 编码的转换

  • int 类型的字符串，当保留的不再是 整数值，将转换成 raw 类型
  • embstr 类型的字符串是 只读的，批改时会转换成 raw 类型。起因：Redis 没有为 embstr 提供批改程序，所以它是只读的；要批改只能先转成 raw。

3.1 列表（list）对象

还是从上图得悉，列表的编码能够是 ziplist 或 linkedlist：

  • ziplist：所有元素长度都小于 64 字节且元素数量少于 512 个

    • 以上两个条件的上限值能够通过配置文件的 list-max-ziplist-value和 list-max-ziplist-entries 批改
  • linkedlist：不满足上述条件时，将从 ziplist 转换成 linkedlist

3.1.0 区别

执行 RPUSH 命令将创立一个列表对象，比方：

redis> RPUSH numbers 1 "three" 5
(integer) 3

如果 numbers 应用 ziplist 编码，对象构造如下：

否则应用 linkedlist，就是双端链表作为底层实现。构造如下：

3.2 哈希（hash）对象

又是从上图得悉，哈希的编码能够是 ziplist 或 hashtable：

  • ziplist：哈希对象保留的所有键值对的键和值的字符串长度都小于 64 字节且键值对数量小于 512

    • 以上两个条件的上限值能够通过配置文件的 hash-max-ziplist-value和 hash-max-ziplist-entries 批改
  • hashtable：不能满足上述条件，将从 ziplist 转成 hashtable

3.2.0 区别

执行 HSET 命令，能够创立一个 hash 对象并保留数据：

redis> HSET profile name "Tom"
(integer) 1
redis> HSET profile age 25
(integer) 1
redis> HSET profile career "Programmer"
(integer) 1

ziplist 保留的 hash 对象：

hashtable 保留的 hash 对象：

  • 字典中每个键都是一个字符串对像，对象中保留键值对的键
  • 字典中每个值都是一个字符串对像，对象中保留键值对的值

架构如下：

3.3 汇合（set）对象

又又是从上图得悉，哈希的编码能够是 intset 或 hashtable：

  • intset：汇合对象保留的所有元素都是整数值且元素数量小于 512 个

    • 以上两个条件的上限值能够通过配置文件的 set-max-intset-entries批改
  • hashtable：不能满足上述条件，将从 intset 转成 hashtable

3.3.0 区别

应用 SADD 命令 可构建一个 intset 编码的 set 对象并保留数据：

redis> SADD numbers 1 3 5
(integer) 3

intset 编码的汇合对象构造如下：

应用 SADD 命令 可构建一个 hashtable 编码的 set 对象并保留数据：

redis> SADD fruits "apple" "banana" "cherry"
(integer) 3

hashtable 编码的 set 应用字典作为底层实现，每个键都是字符串对象，每个对象蕴含一个汇合元素，字典值全副置为 null。

hashtable 编码的汇合对象构造如下：

3.4 有序汇合（Sorted Set）对象

又又又是从上图得悉，有序汇合的编码能够是 ziplist 或 skiplist：

  • ziplist：保留的元素数量小于 128 个且所有元素长度都小于 64 字节

    • 以上两个条件的上限值能够通过配置文件的 zset-max-ziplist-entries和 zset-max-ziplist-value 批改
  • skiplist：不能同时满足上述条件，将从 ziplist 转成 skiplist

3.4.0 区别

应用 ZADD 命令能够构建一个 Sorted Set 对象并保留数据：

redis> ZADD price 8.5 apple 5.0 banana 6.0 cherry
(integer) 3

ziplist 编码实现的 Sorted Set 对象，每个汇合元素应用两个相邻的节点保留，第一个节点是 元素成员 ，第二个节点是 元素分值 。按分值 从小到大 进行排序，构造如下：

skiplist 编码实现的 Sorted Set 应用 zset 作为底层实现，它蕴含 跳跃表 和字典，源码如下：

typedef struct zset {
    zskpilist *zsl;
    dict *dict;
}zset;

大体构造如下：

  • 跳跃表 zsl 按分值从小到大保留所有汇合元素；每个节点保留一个汇合元素；object 属性保留元素成员、score 属性保留元素分值。目标：实现疾速的范畴查问操作。
  • 字典 dict 创立一个从成员到分值的 key-value；字典中每个键值对都保留一个汇合元素；键保留元素成员、值保留元素分值。目标：用 O(1) 复杂度 get 元素分值。

最初，具体的构造如下所示：

听到这里有人可能有疑难：zset 构造同时应用 跳跃表和字典 来保留有序汇合元素，不会反复吗？

不会，因为二者会通过 指针 来共享同一个元素，并不会产生反复。

为什么 skiplist 编码实现的有序汇合要同时用跳跃表和字典实现？轻易用一个行吗？

答案是：不好。咱们来看看两种状况：

  • 只用 dict，能够保留以 O(1) 复杂度 get 成员分值；但 字典是无序的 ，所以 每次进行范畴操作都要对所有元素排序；显然这是性能更低的。
  • 只用跳跃表，疾速范畴操作得以保留；然而没了字典，get 成员分值的复杂度将进步至 O(logN)，这也影响性能。

所以，Redis 为了把两者有点联合起来，采纳了通过 指针共享 的形式，应用两种数据结构实现。

04 一些留神的点

4.0 Redis 如何执行命令

Redis 执行命令前，会先查看 值对象类型 ，判断 键是否能执行该命令 ；再查看 值对象的编码方式 抉择适合的命令执行。

举个例子：列表对象有 ziplist 和 linkedlist 两种编码格局可用；前者通过 ziplist 的 API 执行命令、后者通过 linkedlist 的 API 执行命令。

如果咱们执行 LLEN 命令，Redis 第一步判断执行的命令是不是针对列表的 ？是的话，第二步判断 值的编码格局 ，如果是 ziplist，应用 ziplistLen 函数 操作；如果是 linkedlist 则应用 listLength 函数 操作。

4.1 Redis 内存回收机制与共享对象

Redis 为每个对象构建一个 援用计数 属性，通过它可实现 内存回收机制（当一个对象的援用计数为 0 时，将会开释所占用内存）。

Redis 会共享值为 0 到 9999 的字符串对象（这个值可能通过批改 redis.h 文件的 REDIS_SHARDED_INTEGER 常量批改）

Redis 只共享字符串对象自身，为什么不共享蕴含字符串的对象？

能共享的前提是 指标对象和共享对象完全相同 。要共享就须要验证两者是否雷同？因为 蕴含字符串的对象复杂度更高，验证耗费的 CPU 工夫也更多，而性能将会降落。

4.2 lru 属性的作用

redisObject 的 lru 属性 记录对象最初一次被拜访的工夫 ，这个工夫能够用于计算对象的空转工夫（ 公式：以后工夫 – lru 工夫）。

05 伟人的肩膀

  • 《Redis 设计与实现》
  • redis 源码：github.com/antirez/redis
  • redis 源码中文正文版：github.com/huangz1990/redis-3.0-annotated
  • cnblogs.com/Java3y/p/9870829.html
  • time.geekbang.org/column/article/268253
  • http://www.fidding.me/article…
  • segmentfault.com/a/1190000019980165
  • cnblogs.com/chenchen0618/p/13260202.html

06 总结

本文从罕用的缓存技术讲起，深刻 Redis 的数据类型与底层数据结构。第一大节从 Redis 和缓存聊起；第二节站在源码角度跟你剖析 Redis 的 6 种数据结构：SDS、链表、哈希表、跳跃表、整数汇合以及压缩列表的个性；第三节着重和你分享 5 种数据类型和 6 中底层构造的对应关系；第四节则是画龙点睛地和你分享了 Redis 是怎么执行命令的？怎么开释内存等问题。

全文将近 13330 字，38 张图，心愿能帮到你。好啦，以上就是狗哥对于 MySQL 锁的总结。感激各技术社区大佬们的付出，尤其是极客工夫，真的牛逼。如果说我看得更远，那是因为我站在你们的肩膀上。心愿这篇文章对你有帮忙，咱们下篇文章见~

07 送点面试题 & 电子书

如果看到这里，喜爱这篇文章的话，请帮点个 难看。

初次见面，也不晓得送你们啥。罗唆就送 几百本电子书 和2021 最新面试材料 吧。微信搜寻 一个优良的废人 回复 电子书 送你 1000+ 本编程电子书；回复 面试 送点面试题；回复 1024 送你一套残缺的 java 视频教程。

面试题都是有答案的，如下所示：有须要的就来拿吧，相对收费，无套路获取。

退出移动版