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

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

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

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

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

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

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

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

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

官网是这么形容的：

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

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

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

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

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

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

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

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

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

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

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

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

实际上，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 实际上是这样寄存的：

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

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

struct sdshdr{

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

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

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

图示：

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

SDS 比 C 字符串好在哪？

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

链表，大家都很相熟了吧？在 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

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

哈希表，大家也都不生疏吧？在 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（扩容）时应用。

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

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

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

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

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

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

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

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

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

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

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

啥是渐进式 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] 的键值对数量只减不增，最初变为空表。

跳跃表在 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 设计与实现》这本书（说得很好，微信读书网页版就有）

整数汇合是 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

如果 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 即可实现降级。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ziplist：所有元素长度都小于 64 字节且元素数量少于 512 个
- 以上两个条件的上限值能够通过配置文件的 list-max-ziplist-value和 list-max-ziplist-entries 批改
linkedlist：不满足上述条件时，将从 ziplist 转换成 linkedlist

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

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

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

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

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

ziplist：哈希对象保留的所有键值对的键和值的字符串长度都小于 64 字节且键值对数量小于 512
- 以上两个条件的上限值能够通过配置文件的 hash-max-ziplist-value和 hash-max-ziplist-entries 批改
hashtable：不能满足上述条件，将从 ziplist 转成 hashtable

执行 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 对象：

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

架构如下：

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

intset：汇合对象保留的所有元素都是整数值且元素数量小于 512 个
- 以上两个条件的上限值能够通过配置文件的 set-max-intset-entries批改
hashtable：不能满足上述条件，将从 intset 转成 hashtable

应用 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 编码的汇合对象构造如下：

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

ziplist：保留的元素数量小于 128 个且所有元素长度都小于 64 字节
- 以上两个条件的上限值能够通过配置文件的 zset-max-ziplist-entries和 zset-max-ziplist-value 批改
skiplist：不能同时满足上述条件，将从 ziplist 转成 skiplist

应用 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 为了把两者有点联合起来，采纳了通过 指针共享 的形式，应用两种数据结构实现。

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

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

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

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

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

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

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

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

《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

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

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

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

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

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

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

00 前言

0.1 往期精彩

01 什么是 Redis？

1.0 为什么要用 Redis 做缓存？

02 Redis 的数据结构

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

2.1 SDS 简略动静字符串

2.1.0 为什么应用 SDS？

2.2 链表

2.2.0 Redis 链表的个性

2.3 哈希表

2.3.0 哈希抵触

2.3.1 rehash（扩容）

2.3.2 渐进式 rehash

2.4 跳跃表

2.5 整数汇合

2.5.0 降级操作

2.6 压缩列表

2.6.0 节点形成

2.6.1 压缩列表的查找

03 数据类型与数据结构

3.0 字符串（String）对象

3.0.0 embstr 和 raw 有啥区别？

3.0.1 编码的转换

3.1 列表（list）对象

3.1.0 区别

3.2 哈希（hash）对象

3.2.0 区别

3.3 汇合（set）对象

3.3.0 区别

3.4 有序汇合（Sorted Set）对象

3.4.0 区别

04 一些留神的点

4.0 Redis 如何执行命令

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

4.2 lru 属性的作用

05 伟人的肩膀

06 总结

07 送点面试题 & 电子书

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）