Redis 数据结构

Redis 数据结构

字符串

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte flags; // 特殊标识位,不理睬它
  byte[] content; // 数组内容
}

字典

struct RedisDb {
    dict* dict; // all keys  key=>value
    dict* expires; // all expired keys key=>long(timestamp)
    ...
}

struct zset {
    dict *dict; // all values  value=>score
    zskiplist *zsl;
}

dict 结构内部包含两个 hashtable,通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时,需要分配新的 hashtable,然后进行渐进式搬迁,这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后,旧的 hashtable 被删除,新的 hashtable 取而代之。

struct dict {
    ...
    dictht ht[2];
}

渐进式 rehash

大字典的扩容是比较耗时间的,需要重新申请新的数组,然后将旧字典所有链表中的元素重新挂接到新的数组下面,这是一个O(n)级别的操作,作为单线程的Redis表示很难承受这样耗时的过程。步子迈大了会扯着蛋,所以Redis使用渐进式rehash小步搬迁。虽然慢一点,但是肯定可以搬完。

搬迁操作埋伏在当前字典的后续指令中(来自客户端的hset/hdel指令等),但是有可能客户端闲下来了,没有了后续指令来触发这个搬迁,那么Redis就置之不理了么?当然不会,优雅的Redis怎么可能设计的这样潦草。Redis还会在定时任务中对字典进行主动搬迁。

扩容条件

正常情况下,当 hash 表中元素的个数等于第一维数组的长度时,就会开始扩容,扩容的新数组是原数组大小的 2 倍。不过如果 Redis 正在做 bgsave,为了减少内存页的过多分离 (Copy On Write),Redis 尽量不去扩容 (dict_can_resize),但是如果 hash 表已经非常满了,元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio),说明 hash 表已经过于拥挤了,这个时候就会强制扩容。

压缩列表

Redis 为了节约内存空间使用,zsethash 容器对象在元素个数较少的时候,采用压缩列表 (ziplist) 进行存储。压缩列表是一块连续的内存空间,元素之间紧挨着存储,没有任何冗余空隙。

Redis 的 zset 是一个复合结构,一方面它需要一个 hash 结构来存储 value 和 score 的对应关系,另一方面需要提供按照 score 来排序的功能,还需要能够指定 score 的范围来获取 value 列表的功能,这就需要另外一个结构「跳跃列表」。

zset 的内部实现是一个 hash 字典加一个跳跃列表 (skiplist)。

跳跃列表

如果数据存储在链表中,就真的没法用二分查找算法了吗?只需要对链表稍加改造,就可以支持类似“二分”的查找算法。这种链表加多级索引的结构,就是跳表。

Redis 中的有序集合支持的核心操作主要有下面这几个:

  • 插入一个数据;
  • 删除一个数据;
  • 查找一个数据;
  • 按照区间查找数据(比如查找值在[100, 356]之间的数据);
  • 迭代输出有序序列。

插入、删除、查找以及迭代输出有序序列这几个操作,红黑树也可以完成,时间复杂度跟跳表是一样的。但是,按照区间来查找数据这个操作,红黑树的效率没有跳表高

对于按照区间查找数据这个操作,跳表可以做到 O(logn) 的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。

对于每一个新插入的节点,都需要调用一个随机算法给它分配一个合理的层数。直观上期望的目标是 50% 的 Level1,25% 的 Level2,12.5% 的 Level3,一直到最顶层2^-63,因为这里每一层的晋升概率是 50%

/* 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;
}

位图

在我们平时开发过程中,会有一些 bool 型数据需要存取,比如用户一年的签到记录,签了是 1,没签是 0,要记录 365 天。如果使用普通的 key/value,每个用户要记录 365 个,当用户上亿的时候,需要的存储空间是惊人的。

为了解决这个问题,Redis 提供了位图数据结构,这样每天的签到记录只占据一个位,365 天就是 365 个位,46 个字节 (一个稍长一点的字符串) 就可以完全容纳下,这就大大节约了存储空间。

Redis 的位数组是自动扩展,如果设置了某个偏移位置超出了现有的内容范围,就会自动将位数组进行零扩充。

HyperLogLog

统计网站的 UV (同一个用户一天之内的多次访问请求只能计数一次,这就要求每一个网页请求都需要带上用户的 ID,无论是登陆用户还是未登陆用户都需要一个唯一 ID 来标识),如果使用 Set 会占据太多空间,Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。HyperLogLog 提供不精确的去重计数方案,虽然不精确但是也不是非常不精确,标准误差是 0.81%,这样的精确度已经可以满足上面的 UV 统计需求了。

127.0.0.1:6379> pfadd codehole user1
127.0.0.1:6379> pfadd codehole user2
127.0.0.1:6379> pfcount codehole
(integer) 2

Redis 4.0 布隆过滤器

新闻客户端推荐系统如何实现推送去重的?当用户量很大,每个用户看过的新闻又很多的情况下,从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录,推荐系统的去重工作在性能上跟的上么?

当布隆过滤器说某个值存在时,这个值可能不存在;当它说不存在时,那就肯定不存在。

127.0.0.1:6379> bf.add codehole user1
127.0.0.1:6379> bf.add codehole user2
127.0.0.1:6379> bf.exists codehole user1
1

Redis 4.0 redis-cell 漏斗限流模块

> cl.throttle zk:reply 15 30 60 1
                ▲     ▲  ▲  ▲  ▲
                |     |  |  |  └───── need 1 quota (可选参数,默认值也是1)
                |     |  └──┴─────── 30 operations / 60 seconds 这是漏水速率
                |     └───────────── 15 capacity 这是漏斗容量
                └─────────────────── key

Redis 3.2 GeoHash 地理位置

如何快速查询附近的人 ?

业界比较通用的地理位置距离排序算法是 GeoHash 算法,Redis 也使用 GeoHash 算法。GeoHash 算法将二维的经纬度数据映射到一维的整数,这样所有的元素都将在挂载到一条线上,距离靠近的二维坐标映射到一维后的点之间距离也会很接近。当我们想要计算「附近的人时」,首先将目标位置映射到这条线上,然后在这个一维的线上获取附近的点就行了。