0. 前言
前面写了一篇关于跳表基本原理和特性的文章, 本次继续介绍跳表的概率平衡和工程实现, 跳表在 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 中的:
1 (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=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 的概率为 p^0(1-p).
节点层数恰好等于 2 的概率为 p^1(1-p).
节点层数恰好等于 3 的概率为 p^2(1-p).
节点层数恰好等于 4 的概率为 p^3(1-p).
依次递推节点层数恰好等于 K 的概率为 p^(k-1)(1-p)
因此如果我们要求节点的平均层数, 那么也就转换成了求概率分布的期望问题了, 灵魂画手大白再次上线:
表中 P 为概率, V 为对应取值, 给出了所有取值和概率的可能, 因此就可以求这个概率分布的期望了.
方括号里面的式子其实就是高一年级学的等比数列, 常用技巧错位相减求和, 从中可以看到结点层数的期望值与 1-p 成反比.
对于 Redis 而言, 当 p=0.25 时结点层数的期望是 1.33.
小结: 在 Redis 源码中有详尽的关于插入和删除调整跳表的过程, 本文就不再展开了, 代码并不算难懂, 都是纯 C 写的没有那么多炫技的特效, 放心大胆读起来.
4. 参考资料
https://juejin.im/post/5cb885a8f265da03973aa8a1
来源: https://www.cnblogs.com/backnullptr/p/12015242.html