ZSKIPLIST_MAXLEVEL(64) 够2^64个元素吗？
Is ZSKIPLIST_MAXLEVEL(64) enough for 2^64 elements？
我最近从跳表：平衡树的概率替代中了解了跳表。我认为 p=0.25 的 64 个级别应该有 4^64 个元素（如果 p = 1/2，使用 MaxLevel = 16 适用于最多包含 2^16 个元素的数据结构。--引用自平衡树的概率替代方案） .但是当我检查 Redis server.h 时，我看到
define ZSKIPLIST_MAXLEVEL 64 /* 应该足够 2^64 个元素 */
define ZSKIPLIST_P 0.25 /* 跳表 P = 1/4 */.
是我错了还是配置错了？
You are right. It is fair to say that server.h defines a MAXLEVEL higher than necessary.
The probability that a particular element reaches a level at least k is p^k, and the probability that any of the n elements reaches a level at least k is n·p^k.
Redis uses the skip list for sorted sets, and it uses it in conjunction with a hash map. The hash map (dict) has a capacity of 2^64-1 elements (ready for, not ever tested in practice). Hence the comment on ZSKIPLIST_MAXLEVEL.
It follows that if we use N = 2^64 as an upper bound on the number of elements in the skip list, Redis could have used ZSKIPLIST_MAXLEVEL = 32.
The nodes allocate memory up the level they actually got when rolling the dice. Only the first, null node uses the ZSKIPLIST_MAXLEVEL. The impact: 512 bytes of extra memory per sorted list (of 129 entries or more - before, it uses a ziplist, see zset-max-ziplist-entries config setting).
The other side effect is the chance a node would get an unnecessarily high level, but the odds get really low really fast as we go up beyond the 32nds level.
I think it is worth fixing IMO, for those 512 bytes.
我最近从跳表：平衡树的概率替代中了解了跳表。我认为 p=0.25 的 64 个级别应该有 4^64 个元素（如果 p = 1/2，使用 MaxLevel = 16 适用于最多包含 2^16 个元素的数据结构。--引用自平衡树的概率替代方案） .但是当我检查 Redis server.h 时，我看到
define ZSKIPLIST_MAXLEVEL 64 /* 应该足够 2^64 个元素 */
define ZSKIPLIST_P 0.25 /* 跳表 P = 1/4 */.
是我错了还是配置错了？
You are right. It is fair to say that server.h defines a MAXLEVEL higher than necessary.
The probability that a particular element reaches a level at least k is p^k, and the probability that any of the n elements reaches a level at least k is n·p^k.
Redis uses the skip list for sorted sets, and it uses it in conjunction with a hash map. The hash map (dict) has a capacity of 2^64-1 elements (ready for, not ever tested in practice). Hence the comment on ZSKIPLIST_MAXLEVEL.
It follows that if we use N = 2^64 as an upper bound on the number of elements in the skip list, Redis could have used ZSKIPLIST_MAXLEVEL = 32.
The nodes allocate memory up the level they actually got when rolling the dice. Only the first, null node uses the ZSKIPLIST_MAXLEVEL. The impact: 512 bytes of extra memory per sorted list (of 129 entries or more - before, it uses a ziplist, see zset-max-ziplist-entries config setting).
The other side effect is the chance a node would get an unnecessarily high level, but the odds get really low really fast as we go up beyond the 32nds level.
I think it is worth fixing IMO, for those 512 bytes.