0x00.前言

众所周知数据结构和算法是面试重点，我们持续发力是十分明智的，要不然最后肯定是要吃亏的，少打打游戏刷刷微博可以改变我们的生活水平哦。

不过本文不是要讲述数据结构和算法的，而是另外一个面试重点Redis，因为Redis也是跨语言的共同技术点，无论是Java还是C++都会问到，所以是个高频面试点。

笔者是2017年才开始接触Redis的，期间自己搭过单机版和集群版，不过现在公司大一些都完全是运维来实现的，我们使用者只需要在web页面进行相关申请即可，很多细节都被屏蔽了，这样当然很方便啦，不过我们还是要深入理解一下的。

在工作几年中笔者接触过Redis、类Redis的SSDB和Pika、谷歌的Key-Value存储引擎LevelDB、FackBook的Key-Value存储引擎RocksDB等NoSQL，其中Redis是基于标准C语言开发的，是工程中和学习上都非常优秀的开源项目。

之前笔者写过几篇左右Redis的文章，但是知识点都分散着不利于阅读，所以本次就把之前的文章进行汇总补充，来形成一个全一些的集合，希望对关注我的读者有所帮助就足够啦。

文中列出来的考点较多并且累计达3w+字 ，因此建议读者收藏，以备不时之需，通过本文你将了解到以下内容：

• Redis的作者和发展简史
• Redis常用数据结构及其实现
• Redis的SDS和C中字符串的原理和对比
• Redis有序集合ZSet的底层设计和实现
• Redis有序集合ZSet和跳跃链表问题
• Redis字典的实现及渐进式Rehash过程
• Redis单线程运行模式的基本原理和流程
• Redis反应堆模式的原理和设计实现
• Redis持久化方案及其基本原理
• 集群版Redis和Gossip协议
• Redis内存回收机制和基本原理
• Redis数据同步机制和基本原理

话不多说，时速400公里的大白号 开始加速！

笔者尽量详细地阐述每个问题，旨在深入理解避免囫囵吞枣的背诵，当然也会存在一些不足，如有问题可私信我。

0x01. 什么是Redis及其重要性？

Redis是一个使用ANSI C编写的开源、支持网络、基于内存、可选持久化的高性能键值对数据库。

Redis的之父是来自意大利的西西里岛的Salvatore Sanfilippo，Github网名antirez，笔者找了作者的一些简要信息并翻译了一下，如图：

从2009年第一个版本起Redis已经走过了10个年头，目前Redis依旧是最流行的key-value型内存数据库的之一。

优秀的开源项目离不开大公司的支持，在2013年5月之前，其开发由VMware赞助，而2013年5月至2015年6月期间，其开发由毕威拓赞助，从2015年6月开始，Redis的开发由Redis Labs赞助。

笔者也使用过一些其他的NoSQL，有的支持的value类型非常单一，因此很多操作都必须在客户端实现，比如value是一个结构化的数据，需要修改其中某个字段就需要整体读出来修改再整体写入，显得很笨重，但是Redis的value支持多种类型，实现了很多操作在服务端就可以完成了，这个对客户端而言非常方便。

当然Redis由于是内存型的数据库，数据量存储量有限而且分布式集群成本也会非常高，因此有很多公司开发了基于SSD的类Redis系统，比如360开发的SSDB、Pika等数据库，但是笔者认为从0到1的难度是大于从1到2的难度的，毋庸置疑Redis是NoSQL中浓墨重彩的一笔，值得我们去深入研究和使用。

Redis提供了Java、C/C++、C#、 PHP 、JavaScript、 Perl 、Object-C、Python、Ruby、Erlang、Golang等多种主流语言的客户端，因此无论使用者是什么语言栈总会找到属于自己的那款客户端，受众非常广。

笔者查了datanyze.com网站看了下Redis和MySQL的最新市场份额和排名对比以及全球Top站点的部署量对比(网站数据2019.12)：

可以看到Redis总体份额排名第9并且在全球Top100站点中部署数量与MySQL基本持平，所以Redis还是有一定的江湖地位的。

0x02. 简述Redis常用的数据结构及其如何实现的？

Redis支持的常用5种数据类型指的是value类型，分别为：字符串String、列表List、哈希Hash、集合Set、有序集合Zset，但是Redis后续又丰富了几种数据类型分别是Bitmaps、HyperLogLogs、GEO。

由于Redis是基于标准C写的，只有最基础的数据类型，因此Redis为了满足对外使用的5种数据类型，开发了属于自己独有的一套基础数据结构，使用这些数据结构来实现5种数据类型。

Redis底层的数据结构包括：简单动态数组SDS、链表、字典、跳跃链表、整数集合、压缩列表、对象。

Redis为了平衡空间和时间效率，针对value的具体类型在底层会采用不同的数据结构来实现，其中哈希表和压缩列表是复用比较多的数据结构，如下图展示了对外数据类型和底层数据结构之间的映射关系：

从图中可以看到ziplist压缩列表可以作为Zset、Set、List三种数据类型的底层实现，看来很强大，压缩列表是一种为了节约内存而开发的且经过特殊编码之后的连续内存块顺序型数据结构，底层结构还是比较复杂的。

0x03. Redis的SDS和C中字符串相比有什么优势？

在C语言中使用N+1长度的字符数组来表示字符串，尾部使用'\0'作为结尾标志，对于此种实现无法满足Redis对于安全性、效率、丰富的功能的要求，因此Redis单独封装了SDS简单动态字符串结构。

在理解SDS的优势之前需要先看下SDS的实现细节，找了github最新的src/sds.h的定义看下：

typedef char *sds;/*这个用不到 忽略即可*/struct __attribute__ ((__packed__)) sdshdr5 {    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */    char buf[];};/*不同长度的header 8 16 32 64共4种 都给出了四个成员len：当前使用的空间大小；alloc去掉header和结尾空字符的最大空间大小flags:8位的标记 下面关于SDS_TYPE_x的宏定义只有5种 3bit足够了 5bit没有用buf:这个跟C语言中的字符数组是一样的，从typedef char* sds可以知道就是这样的。buf的最大长度是2^n 其中n为sdshdr的类型，如当选择sdshdr16，buf_max=2^16。*/struct __attribute__ ((__packed__)) sdshdr8 {    uint8_t len; /* used */    uint8_t alloc; /* excluding the header and null terminator */    unsigned char flags; /* 3 lsb of type, 5 unused bits */    char buf[];};struct __attribute__ ((__packed__)) sdshdr16 {    uint16_t len; /* used */    uint16_t alloc; /* excluding the header and null terminator */    unsigned char flags; /* 3 lsb of type, 5 unused bits */    char buf[];};struct __attribute__ ((__packed__)) sdshdr32 {    uint32_t len; /* used */    uint32_t alloc; /* excluding the header and null terminator */    unsigned char flags; /* 3 lsb of type, 5 unused bits */    char buf[];};struct __attribute__ ((__packed__)) sdshdr64 {    uint64_t len; /* used */    uint64_t alloc; /* excluding the header and null terminator */    unsigned char flags; /* 3 lsb of type, 5 unused bits */    char buf[];};#define SDS_TYPE_5  0#define SDS_TYPE_8  1#define SDS_TYPE_16 2#define SDS_TYPE_32 3#define SDS_TYPE_64 4#define SDS_TYPE_MASK 7#define SDS_TYPE_BITS 3

看了前面的定义，笔者画了个图：

从图中可以知道sds本质分为三部分：header、buf、null结尾符，其中header可以认为是整个sds的指引部分，给定了使用的空间大小、最大分配大小等信息，再用一张网上的图来清晰看下sdshdr8的实例：

在sds.h/sds.c源码中可清楚地看到sds完整的实现细节，本文就不展开了要不然篇幅就过长了，快速进入主题说下sds的优势：

• O(1)获取长度: C字符串需要遍历而sds中有len可以直接获得；
• 防止缓冲区溢出bufferoverflow: 当sds需要对字符串进行修改时，首先借助于len和alloc检查空间是否满足修改所需的要求，如果空间不够的话，SDS会自动扩展空间，避免了像C字符串操作中的覆盖情况；
• 有效降低内存分配次数：C字符串在涉及增加或者清除操作时会改变底层数组的大小造成重新分配、sds使用了空间预分配和惰性空间释放机制，说白了就是每次在扩展时是成倍的多分配的，在缩容是也是先留着并不正式归还给OS，这两个机制也是比较好理解的；
• 二进制安全：C语言字符串只能保存ascii码，对于图片、音频等信息无法保存，sds是二进制安全的，写入什么读取就是什么，不做任何过滤和限制；

老规矩上一张黄健宏大神总结好的图：

0x04. Redis的字典是如何实现的？简述渐进式rehash过程

字典算是Redis中常用数据类型中的明星成员了，前面说过字典可以基于ziplist和hashtable来实现，我们只讨论基于hashtable实现的原理。

字典是个层次非常明显的数据类型，如图：

有了个大概的概念，我们看下最新的src/dict.h源码定义：

//哈希节点结构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;/* This is our hash table structure. Every dictionary has two of this as we * implement incremental rehashing, for the old to the new table. *///哈希表结构 该部分是理解字典的关键typedef struct dictht {    dictEntry **table;    unsigned long size;    unsigned long sizemask;    unsigned long used;} dictht;//字典结构typedef struct dict {    dictType *type;    void *privdata;    dictht ht[2];    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    unsigned long iterators; /* number of iterators currently running */} dict;

C语言的好处在于定义必须是由最底层向外的，因此我们可以看到一个明显的层次变化，于是笔者又画一图来展现具体的层次概念：

• 关于dictEntry

dictEntry是哈希表节点，也就是我们存储数据地方，其保护的成员有：key,v,next指针。key保存着键值对中的键，v保存着键值对中的值，值可以是一个指针或者是uint64_t或者是int64_t。next是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决哈希冲突的问题。

如图为两个冲突的哈希节点的连接关系：

• 关于dictht

从源码看哈希表包括的成员有table、size、used、sizemask。table是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针， 每个dictEntry结构保存着一个键值对；size 属性记录了哈希表table的大小，而used属性则记录了哈希表目前已有节点的数量。sizemask等于size-1和哈希值计算一个键在table数组的索引，也就是计算index时用到的。

如上图展示了一个大小为4的table中的哈希节点情况，其中k1和k0在index=2发生了哈希冲突，进行开链表存在，本质上是先存储的k0，k1放置是发生冲突为了保证效率直接放在冲突链表的最前面，因为该链表没有尾指针。

• 关于dict

从源码中看到dict结构体就是字典的定义，包含的成员有type，privdata、ht、rehashidx。其中dictType指针类型的type指向了操作字典的api，理解为函数指针即可，ht是包含2个dictht的数组，也就是字典包含了2个哈希表，rehashidx进行rehash时使用的变量，privdata配合dictType指向的函数作为参数使用，这样就对字典的几个成员有了初步的认识。

字典的哈希算法

//伪码：使用哈希函数，计算键key的哈希值hash = dict->type->hashFunction(key);//伪码：使用哈希表的sizemask和哈希值，计算出在ht[0]或许ht[1]的索引值index = hash & dict->ht[x].sizemask;//源码定义#define dictHashKey(d, key) (d)->type->hashFunction(key)

redis使用MurmurHash算法计算哈希值，该算法最初由Austin Appleby在2008年发明，MurmurHash算法的无论数据输入情况如何都可以给出随机分布性较好的哈希值并且计算速度非常快，目前有MurmurHash2和MurmurHash3等版本。

• 普通Rehash重新散列

哈希表保存的键值对数量是动态变化的，为了让哈希表的负载因子维持在一个合理的范围之内，就需要对哈希表进行扩缩容。

扩缩容是通过执行rehash重新散列来完成，对字典的哈希表执行普通rehash的基本步骤为分配空间->逐个迁移->交换哈希表，详细过程如下：

1. 为字典的ht[1]哈希表分配空间，分配的空间大小取决于要执行的操作以及ht[0]当前包含的键值对数量：
   扩展操作时ht[1]的大小为第一个大于等于ht[0].used*2的2^n；
   收缩操作时ht[1]的大小为第一个大于等于ht[0].used的2^n ；扩展时比如h[0].used=200，那么需要选择大于400的第一个2的幂，也就是2^9=512。
2. 将保存在ht[0]中的所有键值对重新计算键的哈希值和索引值rehash到ht[1]上；
3. 重复rehash直到ht[0]包含的所有键值对全部迁移到了ht[1]之后释放 ht[0]， 将ht[1]设置为 ht[0]，并在ht[1]新创建一个空白哈希表， 为下一次rehash做准备。

• 渐进Rehash过程

Redis的rehash动作并不是一次性完成的，而是分多次、渐进式地完成的，原因在于当哈希表里保存的键值对数量很大时， 一次性将这些键值对全部rehash到ht[1]可能会导致服务器在一段时间内停止服务，这个是无法接受的。

针对这种情况Redis采用了渐进式rehash，过程的详细步骤：

1. 为ht[1]分配空间，这个过程和普通Rehash没有区别；
2. 将rehashidx设置为0，表示rehash工作正式开始，同时这个rehashidx是递增的，从0开始表示从数组第一个元素开始rehash。
3. 在rehash进行期间，每次对字典执行增删改查操作时，顺带将ht[0]哈希表在rehashidx索引上的键值对rehash到 ht[1]，完成后将rehashidx加1，指向下一个需要rehash的键值对。
4. 随着字典操作的不断执行，最终ht[0]的所有键值对都会被rehash至ht[1]，再将rehashidx属性的值设为-1来表示 rehash操作已完成。

渐进式 rehash的思想在于将rehash键值对所需的计算工作分散到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的阻塞问题。

看到这里不禁去想这种捎带脚式的rehash会不会导致整个过程非常漫长？如果某个value一直没有操作那么需要扩容时由于一直不用所以影响不大，需要缩容时如果一直不处理可能造成内存浪费，具体的还没来得及研究，先埋个问题吧！

0x05. 讲讲4.0之前版本的Redis的单线程运行模式

本质上Redis并不是单纯的单线程服务模型，一些辅助工作比如持久化刷盘、惰性删除等任务是由BIO线程来完成的，这里说的单线程主要是说与客户端交互完成命令请求和回复的工作线程。

至于Antirez大佬当时是怎么想的设计为单线程不得而知，只能从几个角度来分析，来确定单线程模型的选择原因。

5.1 单线程模式的考量

CPU并非瓶颈：多线程模型主要是为了充分利用多核CPU，让线程在IO阻塞时被挂起让出CPU使用权交给其他线程，充分提高CPU的使用率，但是这个场景在Redis并不明显，因为CPU并不是Redis的瓶颈，Redis的所有操作都是基于内存的，处理事件极快，因此使用多线程来切换线程提高CPU利用率的需求并不强烈；

内存才是瓶颈：单个Redis实例对单核的利用已经很好了，但是Redis的瓶颈在于内存，设想64核的机器假如内存只有16GB，那么多线程Redis有什么用武之地？

复杂的Value类型：Redis有丰富的数据结构，并不是简单的Key-Value型的NoSQL，这也是Redis备受欢迎的原因，其中常用的Hash、Zset、List等结构在value很大时，CURD的操作会很复杂，如果采用多线程模式在进行相同key操作时就需要加锁来进行同步，这样就可能造成死锁问题。

这时候你会问：将key做hash分配给相同的线程来处理就可以解决呀，确实是这样的，这样的话就需要在Redis中增加key的hash处理以及多线程负载均衡的处理，从而Redis的实现就成为多线程模式了，好像确实也没有什么问题，但是Antirez并没有这么做，大神这么做肯定是有原因的，果不其然，我们见到了集群化的Redis；

集群化扩展：目前的机器都是多核的，但是内存一般128GB/64GB算是比较普遍了，但是Redis在使用内存60%以上稳定性就不如50%的性能了(至少笔者在使用集群化Redis时超过70%时，集群failover的频率会更高)，因此在数据较大时，当Redis作为主存，就必须使用多台机器构建集群化的Redis数据库系统，这样以来Redis的单线程模式又被集群化的处理所扩展了；

软件工程角度：单线程无论从开发和维护都比多线程要容易非常多，并且也能提高服务的稳定性，无锁化处理让单线程的Redis在开发和维护上都具备相当大的优势；

类Redis系统：Redis的设计秉承实用第一和工程化，虽然有很多理论上优秀的设计模式，但是并不一定适用自己，软件设计过程就是权衡的过程。业内也有许多类Redis的NoSQL，比如360基础架构组开发的Pika系统，基于SSD和Rocks存储引擎，上层封装一层协议转换，来实现Redis所有功能的模拟，感兴趣的可以研究和使用。

5.2 Redis的文件事件和时间事件

Redis作为单线程服务要处理的工作一点也不少，Redis是事件驱动的服务器，主要的事件类型就是：文件事件类型和时间事件类型，其中时间事件是理解单线程逻辑模型的关键。

• 时间事件

Redis的时间事件分为两类：

1. 定时事件：任务在等待指定大小的等待时间之后就执行，执行完成就不再执行，只触发一次；
2. 周期事件：任务每隔一定时间就执行，执行完成之后等待下一次执行，会周期性的触发；

• 周期性时间事件

Redis中大部分是周期事件，周期事件主要是服务器定期对自身运行情况进行检测和调整，从而保证稳定性，这项工作主要是ServerCron函数来完成的，周期事件的内容主要包括：

1. 删除数据库的key
2. 触发RDB和AOF持久化
3. 主从同步
4. 集群化保护
5. 关闭清理死客户端链接
6. 统计更新服务器的内存、key数量等信息

可见 Redis的周期性事件虽然主要处理辅助任务，但是对整个服务的稳定运行，起到至关重要的作用。

• 时间事件的无序链表

Redis的每个时间事件分为三个部分：

1. 事件ID 全局唯一 依次递增
2. 触发时间戳 ms级精度
3. 事件处理函数 事件回调函数

时间事件Time_Event结构：

Redis的时间事件是存储在链表中的，并且是按照ID存储的，新事件在头部旧事件在尾部，但是并不是按照即将被执行的顺序存储的。

也就是第一个元素50ms后执行，但是第三个可能30ms后执行，这样的话Redis每次从链表中获取最近要执行的事件时，都需要进行O(N)遍历，显然性能不是最好的，最好的情况肯定是类似于最小栈MinStack的思路，然而Antirez大佬却选择了无序链表的方式。

选择无序链表也是适合Redis场景的，因为Redis中的时间事件数量并不多，即使进行O(N)遍历性能损失也微乎其微，也就不必每次插入新事件时进行链表重排。

Redis存储时间事件的无序链表如图：

5.3 单线程模式中事件调度和执行

Redis服务中因为包含了时间事件和文件事件，事情也就变得复杂了，服务器要决定何时处理文件事件、何时处理时间事件、并且还要明确知道处理时间的时间长度，因此事件的执行和调度就成为重点。

Redis服务器会轮流处理文件事件和时间事件，这两种事件的处理都是同步、有序、原子地执行的，服务器也不会终止正在执行的事件，也不会对事件进行抢占。

• 事件执行调度规则

文件事件是随机出现的，如果处理完成一次文件事件后，依旧没有其他文件事件到来，服务器将继续等待，在文件事件的不断执行中，时间会逐渐向最早的时间事件所设置的到达时间逼近并最终来到到达时间，这时服务器就可以开始处理到达的时间事件了。

由于时间事件在文件事件之后执行，并且事件之间不会出现抢占，所以时间事件的实际处理时间一般会比设定的时间稍晚一些。

• 事件执行调度的代码实现

Redis源码ae.c中对事件调度和执行的详细过程在aeProcessEvents中实现的，具体的代码如下：

int aeProcessEvents(aeEventLoop *eventLoop, int flags){  int processed = 0, numevents;  if (!(flags & AE_TIME_EVENTS) && !(flags & AE_FILE_EVENTS))    return 0;  if (eventLoop->maxfd != -1 ||    ((flags & AE_TIME_EVENTS) && !(flags & AE_DONT_WAIT))) {    int j;    aeTimeEvent *shortest = NULL;    struct timeval tv, *tvp;    if (flags & AE_TIME_EVENTS && !(flags & AE_DONT_WAIT))      shortest = aeSearchNearestTimer(eventLoop);    if (shortest) {      long now_sec, now_ms;      aeGetTime(&now_sec, &now_ms);      tvp = &tv;      long long ms =        (shortest->when_sec - now_sec)*1000 +        shortest->when_ms - now_ms;      if (ms > 0) {        tvp->tv_sec = ms/1000;        tvp->tv_usec = (ms % 1000)*1000;      } else {        tvp->tv_sec = 0;        tvp->tv_usec = 0;      }    } else {      if (flags & AE_DONT_WAIT) {        tv.tv_sec = tv.tv_usec = 0;        tvp = &tv;      } else {        tvp = NULL; /* wait forever */      }    }    numevents = aeApiPoll(eventLoop, tvp);    if (eventLoop->aftersleep != NULL && flags & AE_CALL_AFTER_SLEEP)      eventLoop->aftersleep(eventLoop);    for (j = 0; j < numevents; j++) {      aeFileEvent *fe = &eventLoop->events[eventLoop->fired[j].fd];      int mask = eventLoop->fired[j].mask;      int fd = eventLoop->fired[j].fd;      int fired = 0;      int invert = fe->mask & AE_BARRIER;      if (!invert && fe->mask & mask & AE_READABLE) {        fe->rfileProc(eventLoop,fd,fe->clientData,mask);        fired++;      }      if (fe->mask & mask & AE_WRITABLE) {        if (!fired || fe->wfileProc != fe->rfileProc) {          fe->wfileProc(eventLoop,fd,fe->clientData,mask);          fired++;        }      }      if (invert && fe->mask & mask & AE_READABLE) {        if (!fired || fe->wfileProc != fe->rfileProc) {          fe->rfileProc(eventLoop,fd,fe->clientData,mask);          fired++;        }      }      processed++;    }  }  /* Check time events */  if (flags & AE_TIME_EVENTS)    processed += processTimeEvents(eventLoop);  return processed;}

• 事件执行和调度的伪码

上面的源码可能读起来并不直观，在《Redis设计与实现》书中给出了伪代码实现：

def aeProcessEvents()  #获取当前最近的待执行的时间事件  time_event = aeGetNearestTimer()  #计算最近执行事件与当前时间的差值  remain_gap_time = time_event.when - uinx_time_now()  #判断时间事件是否已经到期 则重置 马上执行  if remain_gap_time < 0:    remain_gap_time = 0  #阻塞等待文件事件 具体的阻塞等待时间由remain_gap_time决定  #如果remain_gap_time为0 那么不阻塞立刻返回  aeApiPoll(remain_gap_time)  #处理所有文件事件  ProcessAllFileEvent()  #处理所有时间事件  ProcessAllTimeEvent()

可以看到Redis服务器是边阻塞边执行的，具体的阻塞事件由最近待执行时间事件的等待时间决定的，在阻塞该最小等待时间返回之后，开始处理事件任务，并且先执行文件事件、再执行时间事件，所有即使时间事件要即刻执行，也需要等待文件事件完成之后再执行时间事件，所以比预期的稍晚。

• 事件调度和执行流程

0x06. 谈谈对Redis的反应堆模式的认识

Redis基于Reactor模式(反应堆模式)开发了自己的网络模型，形成了一个完备的基于IO复用的事件驱动服务器，但是不由得浮现几个问题:

1. 为什么要使用Reactor模式呢？
2. Redis如何实现自己的Reactor模式？

6.1 Reactor模式

单纯的epoll/kqueue可以单机支持数万并发，单纯从性能的角度而言毫无问题，但是技术实现和软件设计依旧存在一些差异。

设想这样一种场景:

• epoll/kqueue将收集到的可读写事件全部放入队列中等待业务线程的处理，此时线程池的工作线程拿到任务进行处理，实际场景中可能有很多种请求类型，工作线程每拿到一种任务就进行相应的处理，处理完成之后继续处理其他类型的任务
• 工作线程需要关注各种不同类型的请求，对于不同的请求选择不同的处理方法，因此请求类型的增加会让工作线程复杂度增加，维护起来也变得越来越困难

上面的场景其实和高并发网络模型很相似，如果我们在epoll/kqueue的基础上进行业务区分，并且对每一种业务设置相应的处理函数，每次来任务之后对任务进行识别和分发，每种处理函数只处理一种业务，这种模型更加符合OO的设计理念，这也是Reactor反应堆模式的设计思路。

反应堆模式是一种对象行为的设计模式，主要同于同步IO，异步IO有Proactor模式，这里不详细讲述Proactor模式，二者的主要区别就是Reactor是同步IO,Proactor是异步IO，理论上Proactor效率更高，但是Proactor模式需要操作系统在内核层面对异步IO进行支持，Linux的Boost.asio就是Proactor模式的代表，Windows有IOCP。

网上比较经典的一张Reactor模式的类图:

图中给出了5个部件分别为：

1. handle 可以理解为读写事件 可以注册到Reactor进行监控
2. Sync event demultiplexer 可以理解为epoll/kqueue/select等作为IO事件的采集器
3. Dispatcher 提供注册/删除事件并进行分发，作为事件分发器
4. Event Handler 事件处理器 完成具体事件的回调 供Dispatcher调用
5. Concrete Event Handler 具体请求处理函数

更简洁的流程如下：

循环前先将待监控的事件进行注册，当监控中的Socket读写事件到来时，事件采集器epoll等IO复用工具检测到并且将事件返回给事件分发器Dispatcher，分发器根据读、写、异常等情况进行分发给事件处理器，事件处理器进而根据事件具体类型来调度相应的实现函数来完成任务。

6.2 Reactor模式在Redis中的实现

Redis处理客户端业务(文件事件)的基本流程：

Redis的IO复用的选择

#ifdef HAVE_EVPORT#include "ae_evport.c"#else    #ifdef HAVE_EPOLL    #include "ae_epoll.c"    #else        #ifdef HAVE_KQUEUE        #include "ae_kqueue.c"        #else        #include "ae_select.c"        #endif    #endif#endif

Redis中支持多种IO复用，源码中使用相应的宏定义进行选择，编译时就可以获取当前系统支持的最优的IO复用函数来使用，从而实现了Redis的优秀的可移植特性。

• Redis的任务事件队列

由于Redis的是单线程处理业务的，因此IO复用程序将读写事件同步的逐一放入队列中，如果当前队列已经满了，那么只能出一个入一个，但是由于Redis正常情况下处理得很快，不太会出现队列满迟迟无法放任务的情况，但是当执行某些阻塞操作时将导致长时间的阻塞，无法处理新任务。

• Redis事件分派器

事件的可读写是从服务器角度看的，分派看到的事件类型包括：

1. AE_READABLE 客户端写数据、关闭连接、新连接到达
2. AE_WRITEABLE 客户端读数据

特别地，当一个套接字连接同时可读可写时，服务器会优先处理读事件再处理写事件，也就是读优先。

• Redis事件处理器

Redis将文件事件进行归类，编写了多个事件处理器函数，其中包括：

1. 连接应答处理器：实现新连接的建立
2. 命令请求处理器：处理客户端的新命令
3. 命令回复处理器：返回客户端的请求结果
4. 复制处理器：实现主从服务器的数据复制

• Redis C/S一次完整的交互

Redis服务器的主线程处于循环中，此时Client向Redis服务器发起连接请求，假如是6379端口，监听端口在IO复用工具下检测到AE_READABLE事件，并将该事件放入TaskQueue中，等待被处理，事件分派器获取这个读事件，进一步确定是新连接请求，就将该事件交给连接应答处理器建立连接；

建立连接后Client向服务器发送了一个get命令，依旧被IO复用检测处理放入队列，被事件分派器处理指派给命令请求处理器，调用相应程序进行执行；

服务器将套接字的AE_WRITEABLE事件与命令回复处理器相关联，当客户端尝试读取结果时产生可写事件，此时服务器端触发命令回复响应，并将数据结果写入套接字，完成之后服务端接触该套接字与命令回复处理器之间的关联；

x07. Redis是如何做持久化的及其基本原理

通俗讲持久化就是将内存中的数据写入非易失介质中，比如机械磁盘和SSD。

在服务器发生宕机时，作为内存数据库Redis里的所有数据将会丢失，因此Redis提供了持久化两大利器：RDB和AOF

1. RDB 将数据库快照以二进制的方式保存到磁盘中。
2. AOF 以协议文本方式，将所有对数据库进行过写入的命令和参数记录到 AOF 文件，从而记录数据库状态。

• 查看RDB配置

[redis@abc]$ cat /abc/redis/conf/redis.conf   save 900 1  save 300 10  save 60 10000  dbfilename "dump.rdb" dir "/data/dbs/redis/rdbstro" 

前三行都是对触发RDB的一个条件， 如第一行表示每900秒钟有一条数据被修改则触发RDB，依次类推；只要一条满足就会进行RDB持久化；

第四行dbfilename指定了把内存里的数据库写入本地文件的名称，该文件是进行压缩后的二进制文件；

第五行dir指定了RDB二进制文件存放目录 ；

• 修改RDB配置

在命令行里进行配置,服务器重启才会生效:

[redis@abc]$ bin/redis-cli127.0.0.1:6379> CONFIG GET save 1) "save"2) "900 1 300 10 60 10000"127.0.0.1:6379> CONFIG SET save "21600 1000" OK

7.1 RDB的SAVE和BGSAVE

RDB文件适合数据的容灾备份与恢复，通过RDB文件恢复数据库耗时较短，可以快速恢复数据。

RDB持久化只会周期性的保存数据，在未触发下一次存储时服务宕机，就会丢失增量数据。当数据量较大的情况下，fork子进程这个操作很消耗cpu，可能会发生长达秒级别的阻塞情况。

SAVE是阻塞式持久化，执行命令时Redis主进程把内存数据写入到RDB文件中直到创建完毕，期间Redis不能处理任何命令。

BGSAVE属于非阻塞式持久化，创建一个子进程把内存中数据写入RDB文件里同时主进程处理命令请求。

如图展示了bgsave的简单流程：

• BGSAVE实现细节

RDB方式的持久化是通过快照实现的，符合条件时Redis会自动将内存数据进行快照并存储在硬盘上，以BGSAVE为例，一次完整数据快照的过程：

1. Redis使用fork函数创建子进程；
2. 父进程继续接收并处理命令请求，子进程将内存数据写入临时文件；
3. 子进程写入所有数据后会用临时文件替换旧RDB文件；

执行fork的时OS会使用写时拷贝策略，对子进程进行快照过程优化。

Redis在进行快照过程中不会修改RDB文件，只有快照结束后才会将旧的文件替换成新的，也就是任何时候RDB文件都是完整的。

我们可以通过定时备份RDB文件来实现Redis数据库备份，RDB文件是经过压缩的，占用的空间会小于内存中的数据大小。

除了自动快照还可以手动发送SAVE或BGSAVE命令让Redis执行快照。通过RDB方式实现持久化，由于RDB保存频率的限制，如果数据很重要则考虑使用AOF方式进行持久化。

7.2 AOF详解

在使用AOF持久化方式时，Redis会将每一个收到的写命令都通过Write函数追加到文件中类似于MySQL的binlog。换言之AOF是通过保存对redis服务端的写命令来记录数据库状态的。

AOF文件有自己的存储协议格式：

[redis@abc]$ more appendonly.aof *2     # 2个参数$6     # 第一个参数长度为 6SELECT     # 第一个参数$1     # 第二参数长度为 18     # 第二参数*3     # 3个参数$3     # 第一个参数长度为 4SET     # 第一个参数$4     # 第二参数长度为 4name     # 第二个参数$4     # 第三个参数长度为 4Jhon     # 第二参数长度为 4

AOF配置：

[redis@abc]$ more ~/redis/conf/redis.confdir "/data/dbs/redis/abcd"           #AOF文件存放目录appendonly yes                       #开启AOF持久化，默认关闭appendfilename "appendonly.aof"      #AOF文件名称（默认）appendfsync no                       #AOF持久化策略auto-aof-rewrite-percentage 100      #触发AOF文件重写的条件（默认）auto-aof-rewrite-min-size 64mb       #触发AOF文件重写的条件（默认）

当开启AOF后，服务端每执行一次写操作就会把该条命令追加到一个单独的AOF缓冲区的末尾，然后把AOF缓冲区的内容写入AOF文件里，由于磁盘缓冲区的存在写入AOF文件之后，并不代表数据已经落盘了，而何时进行文件同步则是根据配置的appendfsync来进行配置：

appendfsync选项：always、everysec和no：

• always：服务器在每执行一个事件就把AOF缓冲区的内容强制性的写入硬盘上的AOF文件里，保证了数据持久化的完整性，效率是最慢的但最安全的；
• everysec：服务端每隔一秒才会进行一次文件同步把内存缓冲区里的AOF缓存数据真正写入AOF文件里，兼顾了效率和完整性，极端情况服务器宕机只会丢失一秒内对Redis数据库的写操作；
• no：表示默认系统的缓存区写入磁盘的机制，不做程序强制，数据安全性和完整性差一些。

AOF比RDB文件更大，并且在存储命令的过程中增长更快，为了压缩AOF的持久化文件，Redis提供了重写机制以此来实现控制AOF文件的增长。

AOF重写实现的理论基础是这样的：

1. 执行set hello world 50次
2. 最后执行一次 set hello china
3. 最终对于AOF文件而言前面50次都是无意义的，AOF重写就是将key只保存最后的状态。
4. 重写期间的数据一致性问题

子进程在进行 AOF 重写期间， 主进程还需要继续处理命令， 而新的命令可能对现有的数据进行修改， 会出现数据库的数据和重写后的 AOF 文件中的数据不一致。

因此Redis 增加了一个 AOF 重写缓存， 这个缓存在 fork 出子进程之后开始启用， Redis 主进程在接到新的写命令之后， 除了会将这个写命令的协议内容追加到现有的 AOF 文件之外， 还会追加到这个缓存中。

当子进程完成 AOF 重写之后向父进程发送一个完成信号， 父进程在接到完成信号之后会调用信号处理函数，完成以下工作：

1. 将 AOF 重写缓存中的内容全部写入到新 AOF 文件中
2. 对新的 AOF 文件进行改名，覆盖原有的 AOF 文件
3. AOF重写的阻塞性

整个 AOF 后台重写过程中只有最后写入缓存和改名操作会造成主进程阻塞， 在其他时候AOF 后台重写都不会对主进程造成阻塞， 将 AOF 重写对性能造成的影响降到了最低。

AOF 重写可以由用户通过调用 BGREWRITEAOF 手动触发。

服务器在 AOF 功能开启的情况下，会维持以下三个变量：

1. 当前 AOF 文件大小
2. 最后一次 重写之后， AOF 文件大小的变量
3. AOF文件大小增长百分比

每次当 serverCron 函数执行时， 它都会检查以下条件是否全部满足， 如果是的话， 就会触发自动的 AOF 重写：

1. 没有 BGSAVE 命令在进行 防止与RDB的冲突
2. 没有 BGREWRITEAOF 在进行 防止和手动AOF冲突
3. 当前 AOF 文件大小至少大于设定值 基本要求 太小没意义
4. 当前 AOF 文件大小和最后一次 AOF 重写后的大小之间的比率大于等于指定的增长百分比

7.3 Redis的数据恢复

Redis的数据恢复优先级

1. 如果只配置 AOF ，重启时加载 AOF 文件恢复数据；
2. 如果同时配置了 RDB 和 AOF ，启动只加载 AOF 文件恢复数据；
3. 如果只配置 RDB，启动将加载 dump 文件恢复数据。

拷贝 AOF 文件到 Redis 的数据目录，启动 redis-server AOF 的数据恢复过程:Redis 虚拟一个客户端，读取AOF文件恢复 Redis 命令和参数，然后执行命令从而恢复数据，这些过程主要在loadAppendOnlyFile() 中实现。

拷贝 RDB 文件到 Redis 的数据目录，启动 redis-server即可，因为RDB文件和重启前保存的是真实数据而不是命令状态和参数。

新型的混合型持久化

RDB和AOF都有各自的缺点：

1. RDB是每隔一段时间持久化一次, 故障时就会丢失宕机时刻与上一次持久化之间的数据，无法保证数据完整性
2. AOF存储的是指令序列, 恢复重放时要花费很长时间并且文件更大

Redis 4.0 提供了更好的混合持久化选项： 创建出一个同时包含 RDB 数据和 AOF 数据的 AOF 文件， 其中 RDB 数据位于 AOF 文件的开头， 它们储存了服务器开始执行重写操作时的数据库状态，至于那些在重写操作执行之后执行的 Redis 命令， 则会继续以 AOF 格式追加到 AOF 文件的末尾， 也即是 RDB 数据之后。

持久化实战

在实际使用中需要根据Redis作为主存还是缓存、数据完整性和缺失性的要求、CPU和内存情况等诸多因素来确定适合自己的持久化方案，一般来说稳妥的做法包括：

1. 最安全的做法是RDB与AOF同时使用，即使AOF损坏无法修复，还可以用RDB来恢复数据，当然在持久化时对性能也会有影响。
2. Redis当简单缓存，没有缓存也不会造成缓存雪崩只使用RDB即可。
3. 不推荐单独使用AOF，因为AOF对于数据的恢复载入比RDB慢，所以使用AOF的时候，最好还是有RDB作为备份。
4. 采用新版本Redis 4.0的持久化新方案。

0x08.谈谈Redis的ZIPLIST的底层设计和实现

先不看Redis的对ziplist的具体实现，我们先来想一下如果我们来设计这个数据结构需要做哪些方面的考虑呢？思考式的学习收获更大呦！

• 考虑点1：连续内存的双面性

连续型内存减少了内存碎片，但是连续大内存又不容易满足。这个非常好理解，你和好基友三人去做地铁，你们三个挨着坐肯定不浪费空间，但是地铁里很多人都是单独出行的，大家都不愿意紧挨着，就这样有2个的位置有1个的位置，可是3个连续的确实不好找呀，来张图：

• 考虑点2: 压缩列表承载元素的多样性

待设计结构和数组不一样，数组是已经强制约定了类型，所以我们可以根据元素类型和个数来确定索引的偏移量，但是压缩列表对元素的类型没有约束，也就是说不知道是什么数据类型和长度，这个有点像TCP粘包拆包的做法了，需要我们指定结尾符或者指定单个存储的元素的长度，要不然数据都粘在一起了。

• 考虑点3：属性的常数级耗时获取

就是说我们解决了前面两点考虑，但是作为一个整体，压缩列表需要常数级消耗提供一些总体信息，比如总长度、已存储元素数量、尾节点位置(实现尾部的快速插入和删除)等，这样对于操作压缩列表意义很大。

• 考虑点4：数据结构对增删的支持

理论上我们设计的数据结构要很好地支持增删操作，当然凡事必有权衡，没有什么数据结构是完美的，我们边设计边调整吧。

• 考虑点5：如何节约内存

我们要节约内存就需要特殊情况特殊处理，所谓变长设计，也就是不像双向链表一样固定使用两个pre和next指针来实现，这样空间消耗更大，因此可能需要使用变长编码。

ziplist总体结构

大概想了这么多，我们来看看Redis是如何考虑的，笔者又画了一张总览简图：

从图中我们基本上可以看到几个主要部分：zlbytes、zltail、zllen、zlentry、zlend。

来解释一下各个属性的含义，借鉴网上一张非常好的图，其中红线验证了我们的考虑点2、绿线验证了我们的考虑点3：

来看下ziplist.c中对ziplist的申请和扩容操作，加深对上面几个属性的理解：

/* Create a new empty ziplist. */unsigned char *ziplistNew(void) {    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;    unsigned char *zl = zmalloc(bytes);    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);    ZIPLIST_LENGTH(zl) = 0;    zl[bytes-1] = ZIP_END;    return zl;}/* Resize the ziplist. */unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {    zl = zrealloc(zl,len);    ZIPLIST_BYTES(zl) = intrev32ifbe(len);    zl[len-1] = ZIP_END;    return zl;}

zlentry的实现

• encoding编码和content存储

我们再来看看zlentry的实现，encoding的具体内容取决于content的类型和长度，其中当content是字符串时encoding的首字节的高2bit表示字符串类型，当content是整数时，encoding的首字节高2bit固定为11，从Redis源码的注释中可以看的比较清楚，笔者对再做一层汉语版的注释：

 /* ###########字符串存储详解############### #### encoding部分分为三种类型：1字节、2字节、5字节 #### #### 最高2bit表示是哪种长度的字符串 分别是00 01 10 各自对应1字节 2字节 5字节 #### #### 当最高2bit=00时 表示encoding=1字节 剩余6bit 2^6=64 可表示范围0~63#### #### 当最高2bit=01时 表示encoding=2字节 剩余14bit 2^14=16384 可表示范围0~16383#### #### 当最高2bit=11时 表示encoding=5字节 比较特殊 用后4字节 剩余32bit 2^32=42亿多#### * |00pppppp| - 1 byte *      String value with length less than or equal to 63 bytes (6 bits). *      "pppppp" represents the unsigned 6 bit length. * |01pppppp|qqqqqqqq| - 2 bytes *      String value with length less than or equal to 16383 bytes (14 bits). *      IMPORTANT: The 14 bit number is stored in big endian. * |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes *      String value with length greater than or equal to 16384 bytes. *      Only the 4 bytes following the first byte represents the length *      up to 32^2-1. The 6 lower bits of the first byte are not used and *      are set to zero. *      IMPORTANT: The 32 bit number is stored in big endian. *########################字符串存储和整数存储的分界线####################* *#### 高2bit固定为11 其后2bit 分别为00 01 10 11 表示存储的整数类型 * |11000000| - 3 bytes *      Integer encoded as int16_t (2 bytes). * |11010000| - 5 bytes *      Integer encoded as int32_t (4 bytes). * |11100000| - 9 bytes *      Integer encoded as int64_t (8 bytes). * |11110000| - 4 bytes *      Integer encoded as 24 bit signed (3 bytes). * |11111110| - 2 bytes *      Integer encoded as 8 bit signed (1 byte). * |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer. *      Unsigned integer from 0 to 12. The encoded value is actually from *      1 to 13 because 0000 and 1111 can not be used, so 1 should be *      subtracted from the encoded 4 bit value to obtain the right value. * |11111111| - End of ziplist special entry.*/

content保存节点内容，其内容可以是字节数组和各种类型的整数，它的类型和长度决定了encoding的编码，对照上面的注释来看两个例子吧：

保存字节数组：编码的最高两位00表示节点保存的是一个字节数组，编码的后六位001011记录了字节数组的长度11，content 属性保存着节点的值 "hello world"。

保存整数：编码为11000000表示节点保存的是一个int16_t类型的整数值，content属性保存着节点的值10086。

• prevlen属性

最后来说一下prevlen这个属性，该属性也比较关键，前面一直在说压缩列表是为了节约内存设计的，然而prevlen属性就恰好起到了这个作用，回想一下链表要想获取前面的节点需要使用指针实现，压缩列表由于元素的多样性也无法像数组一样来实现，所以使用prevlen属性记录前一个节点的大小来进行指向。

prevlen属性以字节为单位，记录了压缩列表中前一个节点的长度，其长度可以是 1 字节或者 5 字节：

1. 如果前一节点的长度小于254字节，那么prevlen属性的长度为1字节， 前一节点的长度就保存在这一个字节里面。
2. 如果前一节点的长度大于等于254字节，那么prevlen属性的长度为5字节,第一字节会被设置为0xFE，之后的四个字节则用于保存前一节点的长度。

思考：注意一下这里的第一字节设置的是0xFE而不是0xFF，想下这是为什么呢？

没错！前面提到了zlend是个特殊值设置为0xFF表示压缩列表的结束，因此这里不可以设置为0xFF，关于这个问题在redis有个issue，有人提出来antirez的ziplist中的注释写的不对，最终antirez发现注释写错了，然后愉快地修改了，哈哈！

再思考一个问题，为什么prevlen的长度要么是1字节要么是5字节呢？为啥没有2字节、3字节、4字节这些中间态的长度呢？要解答这个问题就引出了今天的一个关键问题：连锁更新问题。

连锁更新问题

试想这样一种增加节点的场景：

如果在压缩列表的头部增加一个新节点，并且长度大于254字节，所以其后面节点的prevlen必须是5字节，然而在增加新节点之前其prevlen是1字节，必须进行扩展，极端情况下如果一直都需要扩展那么将产生连锁反应：

试想另外一种删除节点的场景：

如果需要删除的节点时小节点，该节点前面的节点是大节点，这样当把小节点删除时，其后面的节点就要保持其前面大节点的长度，面临着扩展的问题：

理解了连锁更新问题，再来看看为什么要么1字节要么5字节的问题吧，如果是2-4字节那么可能产生连锁反应的概率就更大了，相反直接给到最大5字节会大大降低连锁更新的概率，所以笔者也认为这种内存的小小浪费也是值得的。

从ziplist的设计来看，压缩列表并不擅长修改操作，这样会导致内存拷贝问题，并且当压缩列表存储的数据量超过某个阈值之后查找指定元素带来的遍历损耗也会增加。

0x09.谈谈Redis的Zset和跳跃链表问题

ZSet结构同时包含一个字典和一个跳跃表，跳跃表按score从小到大保存所有集合元素。字典保存着从member到score的映射。两种结构通过指针共享相同元素的member和score，不浪费额外内存。

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

ZSet中的字典和跳表布局：

9.1 ZSet中跳跃链表的实现细节

• 随机层数的实现原理

跳表是一个概率型的数据结构，元素的插入层数是随机指定的。Willam Pugh在论文中描述了它的计算过程如下：

1. 指定节点最大层数 MaxLevel，指定概率 p， 默认层数 lvl 为1
2. 生成一个0~1的随机数r，若r<p，且lvl<MaxLevel ，则lvl ++
3. 重复第 2 步，直至生成的r >p 为止，此时的 lvl 就是要插入的层数。

论文中生成随机层数的伪码：

在Redis中对跳表的实现基本上也是遵循这个思想的，只不过有微小差异，看下Redis关于跳表层数的随机源码src/z_set.c：

/* Returns a random level for the new skiplist node we are going to create. * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL * (both inclusive), with a powerlaw-alike distribution where higher * levels are less likely to be returned. */int zslRandomLevel(void) {    int level = 1;    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))        level += 1;    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;}

其中两个宏的定义在redis.h中：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

可以看到while中的：

(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)

第一眼看到这个公式，因为涉及位运算有些诧异，需要研究一下Antirez为什么使用位运算来这么写？

最开始的猜测是random()返回的是浮点数[0-1]，于是乎在线找了个浮点数转二进制的工具，输入0.25看了下结果：

可以看到0.25的32bit转换16进制结果为0x3e800000，如果与0xFFFF做与运算结果是0，好像也符合预期，再试一个0.5:

可以看到0.5的32bit转换16进制结果为0x3f000000，如果与0xFFFF做与运算结果还是0，不符合预期。

我印象中C语言的math库好像并没有直接random函数，所以就去Redis源码中找找看，于是下载了3.2版本代码，也并没有找到random()的实现，不过找到了其他几个地方的应用：

random()在dict.c中的使用

random()在cluster.c中的使用

看到这里的取模运算，后知后觉地发现原以为random()是个[0-1]的浮点数，但是现在看来是uint32才对，这样Antirez的式子就好理解了。

ZSKIPLIST_P*0xFFFF

由于ZSKIPLIST_P=0.25，所以相当于0xFFFF右移2位变为0x3FFF，假设random()比较均匀，在进行0xFFFF高16位清零之后，低16位取值就落在0x0000-0xFFFF之间，这样while为真的概率只有1/4。更一般地说为真的概率为1/ZSKIPLIST_P。

对于随机层数的实现并不统一，重要的是随机数生成，LevelDB中对跳表层数的生成代码：

template <typename Key, typename Value>int SkipList<Key, Value>::randomLevel() {  static const unsigned int kBranching = 4;  int height = 1;  while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {    height++;  }  assert(height > 0);  assert(height <= kMaxLevel);  return height;}uint32_t Next( uint32_t& seed) {  seed = seed & 0x7fffffffu;  if (seed == 0 || seed == 2147483647L) {     seed = 1;  }  static const uint32_t M = 2147483647L;  static const uint64_t A = 16807;  uint64_t product = seed * A;  seed = static_cast<uint32_t>((product >> 31) + (product & M));  if (seed > M) {    seed -= M;  }  return seed;}

可以看到leveldb使用随机数与kBranching取模，如果值为0就增加一层，这样虽然没有使用浮点数，但是也实现了概率平衡。

• 跳表结点的平均层数

我们很容易看出，产生越高的节点层数出现概率越低，无论如何层数总是满足幂次定律越大的数出现的概率越小。

如果某件事的发生频率和它的某个属性成幂关系，那么这个频率就可以称之为符合幂次定律。幂次定律的表现是少数几个事件的发生频率占了整个发生频率的大部分， 而其余的大多数事件只占整个发生频率的一个小部分。

幂次定律应用到跳表的随机层数来说就是大部分的节点层数都是黄色部分，只有少数是绿色部分，并且概率很低。

定量的分析如下：

1. 节点层数至少为1，大于1的节点层数满足一个概率分布。
2. 节点层数恰好等于1的概率为p^0(1-p)。
3. 节点层数恰好等于2的概率为p^1(1-p)。
4. 节点层数恰好等于3的概率为p^2(1-p)。
5. 节点层数恰好等于4的概率为p^3(1-p)。
6. 依次递推节点层数恰好等于K的概率为p^(k-1)(1-p)

如果要求节点的平均层数，那么也就转换成了求概率分布的期望问题了，灵魂画手大白再次上线：

路过

雷人

握手

鲜花

鸡蛋