【Redis】有序集合内部分享

去年技术分享，分享了我对redis有序集合的理解，目录包括有序集合的用法、适用场景、底层原理。分享结束后同事们也进行了提问，收获颇多。

zset介绍

● 有序集合(sorted set)是排序的集合(set)。
● 集合是 string 类型元素的集合，且元素不允许重复。
● 有序集合每个元素会关联一个 double 类型的分值 score，通过 score 将集合成员从小到大排序。

使用场景

• 排行榜。有序集合经典场景，例如答主答题排行、答主作答时效排行。
• 带权重队列。如延迟队列、时间队列。

实现原理

zset底层是跳表实现的，原理在 http://杨硕.网址/archives/62/

问题探讨

• 问题1：查询集合和删除元素的原子性如何保证

  • 具体场景为：未查看答案的push，在查询完集合后某个元素因为用户看了答案而被删了，导致多发push。
  • 解决方案：遍历集合时先判断该元素是否存在，不存在则不发push。

• 问题2：zinterstore方法的局限性

  • zinterstore命令是对多个集合求交集，涉及多个key。单机情况下没问题，但是集群模式下，多个key可能被分布在不同的节点，这时zinterstore将失效。
  • 解决方案：hash_tag
  • 具体实现：确保多个key有公共的字符串，用"{"、"}"将公共字符串扩上，这样能确保这些key分布到同一节点。

• 问题3：交集、并集的时间复杂度是多少，性能如何？

  • 交集：时间复杂度O(m+n+..)m、n为集合数量。空间复杂度O(1)
  • 并集：时间复杂度O(m+n)
• 问题4：幂次定律的实现中最高level的判断为什么不放在循环中？

int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

最新版代码：

/* 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) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
#define RAND_MAX Ox7FFF 其值最小为32767,最大为2147483647