算法 - redis的zslRandomLevel函数的实现原理是什么？

Question

hi,all

最近在看redis的代码（huangz注释过的），是2.6版本的。在看到t_zset.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.
 *
 * 返回一个介于 1 和 ZSKIPLIST_MAXLEVEL 之间的随机值，作为节点的层数。
 *
 * 根据幂次定律(power law)，数值越大，函数生成它的几率就越小
 *
 * T = O(N)
 */
int zslRandomLevel(void) {
    int level = 1;
    // TODO 了解这个公式背后的数学原理
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

Answer 1

http://blog.csdn.net/kisimple/article/details/38706729
この説明は比較的明確です。スキップリストのペーパーも参照してください。