深入理解跳表在Redis中的应用

原创后端技术指南针后端研究所

前面写了一篇关于跳表基本原理和特性的文章，本次继续介绍跳表的概率平衡和工程实现，跳表在Redis、LevelDB、ES中都有应用，本文以Redis为工程蓝本，分析跳表在Redis中的工程实现。

通过本文你将了解到以下内容：

Redis基本的数据类型和底层数据结构
Redis的有序集合的实现方法
Redis的跳表实现细节

1.Redis的数据结构

Redis对外共有约五种类型的对象：

字符串（String）
列表（List）
哈希（Hash）
集合（Set）
有序集合（SortedSet）

redis源码文件src/server.h中对于5种结构的定义：

/* The actual Redis Object */#define OBJ_STRING 0    /* String object. */#define OBJ_LIST 1      /* List object. */#define OBJ_SET 2       /* Set object. */#define OBJ_ZSET 3      /* Sorted set object. */#define OBJ_HASH 4      /* Hash object. */

Redis对象由redisObject结构体表示，从src/server.h可以看到该结构的定义如下：

typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;        unsigned lru:LRU_BITS;     int refcount;    void *ptr;} robj;

redisObject明确了对象类型、对象编码方式、过期设置、引用计数、内存指针等，从而完整表示一个key-value键值对。

由于Redis是基于内存的，Antirez在实现这5种数据类型时在底层创建了多种数据结构，在对象底层选择采用哪种结构来实现，需要根据对象大小以及单个元素大小来进行确定，从而提高空间使用率和效率。

如图展示了Redis对外使用的数据类型和底层的数据结构：

有序集合对象的编码可以是ziplist或者skiplist，在元素小于128并且元素长度小于64Byte时才会选择压缩列表实现，一般使用skiplist跳表实现。

2.Redis的ZSet

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

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

ZSet中的字典和跳表布局：

注:图片源自网络

3.ZSet中跳表的实现细节

随机层数的实现原理

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

指定节点最大层数 MaxLevel，指定概率 p，默认层数 lvl 为1
生成一个0~1的随机数r，若r<p，且lvl<MaxLevel ，则lvl ++
重复第 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;}