Redis 数据结构与内存办理战略(上)51CTO博客 - 娱乐之横扫全球

Redis 数据结构与内存办理战略(上)51CTO博客

2019年03月06日14时06分25秒 | 作者: 翠彤 | 标签: 数据,数据结构,咱们 | 浏览: 1042

Redis 数据结构与内存办理战略(上)

标签: Redis Redis数据结构 Redis内存办理战略 Redis数据类型 Redis类型映射


  • Redis 数据类型特色与运用场景
    • String、List、Hash、Set、Zset
    • 事例:沪江团购体系大促 hot-top 接口 cache 规划
  • Redis 内存数据结构与编码
    • OBJECT encoding key、DEBUG OBJECT key
    • 简略动态字符串(simple dynamic string)
    • 链表(linked list)
    • 字典(dict)
    • 跳表(skip list)
    • 整数调集(int set)
    • 紧缩表(zip list)
    • Redis Object 类型与映射
  • Redis 内存办理战略
    • 键 过期时刻、生计时刻
    • 过期键删去战略
    • AOF 、RDB 处理过期键战略
    • Redis LRU 算法
  • Redis 耐久化办法
    • AOF (Append-only file)
    • RDB (Redis DataBase)
Redis 数据类型特色与运用场景

redis 为咱们供给了 5 种数据类型,根本上咱们运用频率最高的就是 string ,而对其他四种数据类型运用的频次稍弱于 string 。

一方面是因为 string 运用起来比较简略,能够便利存储杂乱大方针,运用场景比较多。还有一个原因就是因为 redis expire time 只能设置在 key 上,像 list、hash、set、zset 归于调集类型,会办理一组 item,咱们无法在这些调集的 item 上设置过期时刻,所以运用 expire time 来处理调集的 cache 失效会变得略微杂乱些。可是 string 运用 expire time 来办理过期战略会比较简略,因为它包括的项少。这儿说的调集是广泛的相似调集。

导致咱们习惯性的运用 string 而忽视其他四种数据类型的另一个深层次原因,大多是因为咱们对别的四种数据类型的运用和原理不是太了解。这个时分往往会忽视在特定场景下运用某种数据类型或许会比 string 功用高出许多,比方运用 hash 结构来进步某个实体的某个项的修正等。

这儿咱们不计划罗列这 5 种数据类型的运用办法,这些资料网上有许多。咱们首要评论这 5 种数据类型的功用特色,这些特色别离合适用于处理哪些实际的事务场景,最重要的是咱们怎么组合性的运用这 5 种数据类型来处理杂乱的 cache 问题。

String、List、Hash、Set、Zset String

string 是 redis 供给的字符串类型。能够针对 string 类型独立设置 expire time 。一般用来存储长字符串数据,比方,某个方针的 json 字符串。

string 类型咱们在运用上最奇妙的是能够动态拼接 key。一般咱们能够将一组 id 放在 set 里,然后动态查找 string 仍是否存在,假如不存在阐明现已过期或许因为数据修正自动 delete 了,需求再做一次 cache 数据 load 。

尽管 set 无法设置 item 的过期时刻,可是咱们能够将 set item 与 string key 相关来到达相同的效果。

上图中的左面是一个 key 为 set:order:ids 的 set 调集,它或许是一个全量调集,也或许是某个查询条件获取出来的一个调集。

有时分杂乱点的场景需求多个 set 调集来支撑核算,在 redis 效劳器 里或许会有许多相似这样的调集。

这些调集咱们能够称为 功用数据,这些数据是用来辅佐 cache 核算的,当进行各种调集运算之后会得出当时查询需求回来的子集,终究咱们才会去获取某个订单真实的数据。

这些 string:order:{orderId} 字符串 key 并不一定是为了效劳一种场景,而是整个体系最底层的数据,各种场景终究都需求获取这些数据。那些 set 调集能够以为是查询条件数据,用来辅佐查询条件的核算。

redis 为咱们供给了 TYPE 指令来查看某个 key 的数据类型,如:string 类型:

SET string:order:100 order-100
TYPE string:order:100

string
List

list 在进步 throughput 的场景中十分适用,因为它特有的 LPUSH、RPUSH、LPOP、RPOP 功用能够无缝的支撑生产者、顾客架构形式。

这十分合适完结相似 Java Concurrency Fork/Join 结构中的 work-stealing 算法 (作业盗取) 。

java fork/join 结构运用并行来进步功用,可是会带来因为并发 take task 带来的 race condition (竞态条件) 问题,所以选用 work-stealing 算法 来处理因为竞赛问题带来的功用损耗。

上图中模拟了一个典型的付出 callback 峰值场景。在峰值呈现的当地一般咱们都会运用加 buffer 的办法来加速恳求处理速度,这样才干进步并发处理才干,进步 throughput 。

付出 gateway 收到 callback 之后不做任何处理直接交给 分发器 。分发器 是一个无状况的 cluster ,每个 node 经过向 注册中心 pull handler queue list ,也就是获取下流处理器注册到注册中心里的音讯通道。

每一个分发器 node 会保护一个本地 queue list ,然后次序推送音讯到这些 queue list 即可。这儿会有点小问题,就是 付出 gateway 调用分发器的时分是怎么做 load balance ,假如不是均匀负载或许会有某个 queue list 高出其他 queue list 。

而分发器不需求做 soft load balance ,因为哪怕某个 queue list 比其他 queue list 多也无所谓,因为下流 message handler 会依据 work-stealing 算法来盗取其他消费慢的 queue list 。

redis list 的 LPUSH、RPUSH、LPOP、RPOP 特性的确能够在许多场景下进步这种横向扩展核算才干。

Hash

hash 数据类型很明显是依据 hash 算法的,关于项的查找时刻杂乱度是 O(1) 的,在极点状况下或许呈现项 hash 抵触问题,redis 内部是运用链表加 key 判别来处理的。详细 redis 内部的数据结构咱们在后面有介绍,这儿就不打开了。

hash 数据类型的特色一般能够用来处理带有映射联系,一起又需求对某些项进行更新或许删去等操作。假如不是某个项需求保护,那么一般能够经过运用 string 来处理。

假如有需求对某个字段进行修正,运用 string 很明显是会多出许多开支,需求读取出来反序列化成方针然后操作,然后再序列化写回 redis ,这中心或许还有并发问题。

那咱们能够运用 redis hash 供给的实体特色 hash 存储特性,咱们能够以为 hash value 是一个 hash table ,实体的每一个特色都是经过 hash 得到特色的终究数据索引。

上图运用 hash 数据类型来记载页面的 a/b metrics ,左面的是主页 index 的各个区域的核算,右边是营销 marketing 的各个区域核算。

在程序里咱们能够很便利的运用 redis 的 atomic 特性对 hash 某个项进行累加操作。

HMSET hash:mall:page:ab:metrics:index topbanner 10 leftbanner 5 rightbanner 8 bottombanner 20 productmore 10 topshopping 8
OK
HGETALL hash:mall:page:ab:metrics:index
 1) "topbanner"
 2) "10"
 3) "leftbanner"
 4) "5"
 5) "rightbanner"
 6) "8"
 7) "bottombanner"
 8) "20"
 9) "productmore"
10) "10"
11) "topshopping"
12) "8"
HINCRBY hash:mall:page:ab:metrics:index topbanner 1
(integer) 11

运用 redis hash increment 进行原子添加操作。HINCRBY 指令能够原子添加任何给定的整数,也能够经过 HINCRBYFLOAT 来原子添加浮点类型数据。

Set

set 调集数据类型能够支撑调集运算,不能存储重复数据。

set 最大的特色就是调集的核算才干,inter 交集union 并集diff 差集,这些特色能够用来做高功用的穿插核算或许除掉数据。

set 调集在运用场景上仍是比较多和自在的。举个简略的比方,在运用体系中比较常见的就是产品、活动类场景。用一个 set 缓存有用产品调集,再用一个 set 缓存活动产品调集。假如产品呈现上下架操作只需求保护有用产品 set ,每次获取活动产品的时分需求过滤下是否有下架产品,假如有就需求从活动产品中除掉。

当然,下架的时分能够直接删去缓存的活动产品,可是活动是从 marketing 体系中 load 出来的,就算我将 cache 里的活动产品删去,当下次再从 marketing 体系中 load 活动产品时分仍是会有下架产品。当然这仅仅举例,一个场景有不同的完结办法。

上图中左右两头是两个不同的调集,左面是营销域中的可用产品ids调集,右边是营销域中活动产品ids调集,中心核算出两个调集的交集。

SADD set:marketing:product:available:ids 1000100 1000120 1000130 1000140 1000150 1000160
SMEMBERS set:marketing:product:available:ids
1) "1000100"
2) "1000120"
3) "1000130"
4) "1000140"
5) "1000150"
6) "1000160"
SADD set:marketing:activity:product:ids 1000100 1000120 1000130 1000140 1000200 1000300
SMEMBERS set:marketing:activity:product:ids
1) "1000100"
2) "1000120"
3) "1000130"
4) "1000140"
5) "1000200"
6) "1000300"
SINTER set:marketing:product:available:ids set:marketing:activity:product:ids
1) "1000100"
2) "1000120"
3) "1000130"
4) "1000140"

在一些杂乱的场景中,也能够运用 SINTERSTORE 指令将交集核算后的成果存储在一个方针调集中。 这在运用 pipeline 指令管道中特别有用,将 SINTERSTORE 指令包裹在 pipeline 指令串中能够重复运用核算出来的成果集。

因为 redis 是 Signle-Thread 单线程模型 ,依据这个特性咱们就能够运用 redis 供给的 pipeline 管道 来提交一连串带有逻辑的指令调集,这些指令在处理期间不会被其他客户端的指令搅扰。

Zset

zset 排序调集与 set 调集相似,可是 zset 供给了排序的功用。在介绍 set 调集的时分咱们知道 set 调集中的成员是无序的,zset 填补了调集能够排序的空地。

zset 最强壮的功用就是能够依据某个 score 比分值 进行排序,这在许多事务场景中十分急需。比方,在促销活动里依据产品的出售数量来排序产品,在旅行景区里依据流入人数来排序抢手景点等。

根本上人们在做任何事情都需求依据某些条件进行排序。

其实 zset 在咱们运用体系中能用到当地处处都是,这儿咱们举一个简略的比方,在团购体系中咱们一般需求依据参团人数来排序成团列表,咱们都期望参与那些行将成团的团。

上图是一个依据团购code创立的zset,score 分值 就是参团人数累加和。

ZADD zset:marketing:groupon:group:codes 5 G_PXYJY9QQFA 8 G_4EXMT6NZJQ 20 G_W7BMF5QC2P 10 G_429DHBTGZX 8 G_KHZGH9U4PP
ZREVRANGEBYSCORE zset:marketing:groupon:group:codes 1000 0
1) "G_W7BMF5QC2P"
2) "G_ZMZ69HJUCB"
3) "G_429DHBTGZX"
4) "G_KHZGH9U4PP"
5) "G_4EXMT6NZJQ"
6) "G_PXYJY9QQFA"
ZREVRANGEBYSCORE zset:marketing:groupon:group:codes 1000 0 withscores
 1) "G_W7BMF5QC2P"
 2) "20"
 3) "G_ZMZ69HJUCB"
 4) "10"
 5) "G_429DHBTGZX"
 6) "10"
 7) "G_KHZGH9U4PP"
 8) "8"
 9) "G_4EXMT6NZJQ"
10) "8"
11) "G_PXYJY9QQFA"
12) "5"

zset 自身供给了许多办法用来进行调集的排序,假如需求 score 分值能够运用 withscore 字句带出每一项的分值。

在一些比较特别的场合或许需求组合排序,或许有多个 zset 别离用来对同一个实体在不同维度的排序,按时刻排序、按人数排序等。这个时分就能够组合运用 zset 带来的快捷性,运用 pipeline 再结合多个 zset 终究得出组合排序调集。

事例:沪江团购体系大促 hot-top 接口 cache 规划

咱们总结了 redis 供给的 5 种数据类型的各自特色和一般的运用场景。可是咱们不仅仅能够分隔运用这些数据类型,咱们完全能够归纳运用这些数据类型来完结杂乱的 cache 场景。

下面咱们共享一个运用多个 zset 、string 来优化 团购体系 前台接口的比方。因为篇幅和时刻约束,这儿只介绍跟本次事例相关的信息。

hot-top 接口是指热门、排名接口的意思,表明它的浏览量、并发量比较高,一般大促的时分都会有几个这种功用要求比较高的接口。

咱们先来剖析一个查询接口所包括的惯例信息。

首要一个查询接口肯定是有 query condition 查询条件 ,然后是 sort 排序信息 、终究是 page 分页信息 。这是一般接口所承当的根本责任,当然,特别场景下还需求支撑 master/slave replication 时关于数据 session 一致性 的要求,需求供给盯梢符号来回 master 查询数据,这儿就不打开了。

咱们能够笼统出这几个维度的信息:

query condition
查询条件,companyid=100,sellerid=1010101 诸如此类。
sort
排序信息,一般是默许一个列排序,可是在杂乱的场景下会有或许让接口运用者定制排序字段,比方一些租户信息列。
page
分页信息,简略了解就是数据记载排完序之后的第几行到第几行。

因为这儿咱们朴实用 redis 来进步 cache 才干,不涉及到有关于任何查找的才干,所以这儿疏忽其他杂乱查询的状况。其实咱们在杂乱的当地运用了 elastcsearch 来进步查找才干。

上述咱们剖析总结出了一个查询接口的根本信息,这儿还有一个有关于高并发接口的规划准则就是将 hot-top 接口和一般 search 接口分脱离,因为只要分而治之才干别离依据特色选用不同的技能。假如咱们不分责任将一切的查询场景封装在一个接口里,那么在后面优化接口功用的时分根本就很麻烦了,有些场景是无法或许很难用 cache 来处理的,因为接口里耦合了各种场景逻辑,就算牵强能完结功用也不会高。

前面做这些衬托是为了能在介绍事例的时分达到一个根本的一致。现在咱们来看下这个团购体系的 hot-top 接口的详细逻辑。

在大促的时分需求展示团购列表,这个接口的拜访量是十分大的,团购活动需求依据参团人数倒序排序,并且分页回来指定数量的团列表。

咱们假定这个接口名为 getTopGroups(getTopGroupsRequest request)

query condition 查询条件问题

咱们来仔细剖析下,首要不同的查询条件从 DB 里查询出来的数据是不一样的,也就是说查询出来的团列表是不一样的,或许有 company 公司channel 途径 等过滤条件。因为一个团购活动下不会有太多团,顶多上百个是极限了,所以一个查询条件出来的团列表也顶多几十个,并且依据场景剖析热门查询条件不会超越十个,所以咱们挑选将 查询条件 hash 出一个 code 来缓存本次查询条件的全量团列表调集,可是这些成果集是没有任何排序的。

sort 排序问题

再看依据参团人数排序问题,咱们马上就能够想到运用 zset 来处理团排序问题,因为只要一个排序维度,所以一个 zset 就够了。咱们运用一个 zset来缓存一切团的参团人数调集,它是一个全量的团排序调集。

那么咱们怎么将用户的查询条件出来的团列表依据参团人数排序尼,刚好能够运用 zset 的交集运算直接核算出当时这个调集的 zset 子集。

page 分页问题

经过对现已排序之后的团列表 zset 运用 zrange 来获取出分页调集。

咱们来看下完好的流程,怎么处理查询、排序、分页的。

上图从 query condition 核算 hash code ,然后经过 DB 查询出当时条件全量团列表。
zset:marketing:groupon:hottop:available:group key 表明全量团的参团人数,用一个 zset 来缓存。接着将这两个 zset 核算交集,就能够得出当时查询所需求的带有参团人数的 zset ,终究在运用 zrevrange 获取分页区间。

ZADD zset:marketing:groupon:hottop:condition:2986080 0 G4ZD5732YZQ 0 G5VW3YF42UC 0 GF773FEJ7CC 0 GFW8DUEND8S 0 GKPKKW8XEY9 0 GL324DGWMZM
(integer) 6
ZADD zset:marketing:groupon:hottop:available:group 5 GN7KQH36ZWK 10 GS7VB22AWD4 15 GF773FEJ7CC 17 G5VW3YF42UC 18 G4ZD5732YZQ 32 GTYJKCEJBRR 40 GKPKKW8XEY9 45 GL324DGWMZM 50 GFW8DUEND8S 60 GYTKY4ACWLT
(integer) 10
ZINTERSTORE zset:marketing:groupon:hottop:condition:interstore 2 zset:marketing:groupon:hottop:condition:2986080 zset:marketing:groupon:hottop:available:group
(integer) 6
ZRANGE zset:marketing:groupon:hottop:condition:interstore 0 -1 withscores
 1) "GF773FEJ7CC"
 2) "15"
 3) "G5VW3YF42UC"
 4) "17"
 5) "G4ZD5732YZQ"
 6) "18"
 7) "GKPKKW8XEY9"
 8) "40"
 9) "GL324DGWMZM"
10) "45"
11) "GFW8DUEND8S"
12) "50"
ZREVRANGE zset:marketing:groupon:hottop:condition:interstore 2 4 withscores
1) "GKPKKW8XEY9"
2) "40"
3) "G4ZD5732YZQ"
4) "18"
5) "G5VW3YF42UC"
6) "17"

有了回来的团 code 调集之后就能够经过 mget 来批量获取 string 类型的团概况信息,这儿就不贴出代码了。

因为篇幅和时刻联系,这儿就不打开太多的事务场景介绍了。这其间还涉及到核算 cache 过期时刻的问题,这也跟促销活动的运营规矩有联系,还涉及到有或许 query condition hash 抵触问题等,可是这些现已不与咱们本节主题相关。

Redis 内存数据结构与编码

咱们现已了解了 redis 供给的 5 种数据类型,那么 redis 内部到底是怎么支撑这 5 种数据类型的,也就是说 redis 到底是运用什么样的数据结构来存储、查找咱们设置在内存中的数据。

尽管咱们运用 5 种数据类型来缓存数据,可是 redis 会依据咱们存储数据的不同而选用不同的数据结构和编码。

咱们日常运用的是 redis 供给的 5 种数据类型,可是这 5 种数据类型在内存中的数据结构和编码有许多种。跟着咱们存储的数据类型的不同、数据量的巨细不同都会引起内存数据结构的动态调整。

本节仅仅做数据结构和编码的一般性介绍,不做过多细节评论,一方面是关于 redis 源码剖析的资料网上有许多,还有一个原因就是 redis 每一个版别的完结有很大差异,一旦打开细节评论每一个点每一个数据结构都会很杂乱,所以咱们这儿就不打开评论这些,仅仅起到抛砖引玉效果。

OBJECT encoding key、DEBUG OBJECT key

咱们知道运用 type 指令能够查看某个 key 是否是 5 种数据类型之一,可是当咱们想查看某个 key 底层是运用哪种数据结构和编码来存储的时分能够运用 OBJECT encoding 指令。

SET string:orderid:10101010 10101010
OK
OBJECT encoding string:orderid:10101010
"int"
SET string:orderid:10101010 "orderid:10101010"
OK
OBJECT encoding string:orderid:10101010
"embstr"

相同一个 key ,可是因为咱们设置的值不同而 redis 选用了不同的内存数据结构和编码。尽管 redis 供给的 string 数据类型,可是 redis 会自动识别咱们 cache 的数据类型是 int 仍是 string 。

假如咱们设置的是字符串,且这个字符串长度不大于 39 字节那么将运用 embstr 来编码,假如大于 39 字节将运用 raw 来编码。redis 4.0 将这个阀值扩展了 45 个字节。

除了运用 OBJECT encoding 指令外,咱们还能够运用 DEBUG OBJECT 指令来查看更多详细信息。

DEBUG OBJECT string:orderid:10101010
Value at:0x7fd190500210 refcount:1 encoding:int serializedlength:5 lru:6468044 lru_seconds_idle:8
DEBUG OBJECT string:orderid:10101010
Value at:0x7fd19043be60 refcount:1 encoding:embstr serializedlength:17 lru:6465804 lru_seconds_idle:1942

DEBUG OBJECT 能看到这个方针的 refcount 引证计数serializedlength 长度 、_lru_secondsidle 时刻 ,这些信息决议了这个 key 缓存铲除战略。

简略动态字符串(simple dynamic string)

简略动态字符串简称 SDS ,在 redis 中一切涉及到字符串的当地都是运用 SDS 完结,当然这儿不包括字面量。 SDS 与传统 C 字符串的差异就是 SDS 是结构化的,它能够高效的处理分配、收回、长度核算等问题。

struct sdshdr {
  unsigned int len;
  unsigned int free;
  char buf[];
};

这是 redis 3.0 版别的 sds.h 头文件界说,3.0.0 之后改变比较大。len 表明字符串长度,free 表明空间长度,buf 数组表明字符串。

SDS 有许多长处,比方,获取长度的时刻杂乱度 O(1) ,不需求遍历一切 char buf[] 组数,直接回来 len 值。

static inline size_t sdslen(const sds s) {
  struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
  return sh->len;
}

当然还有空间分配查看、空间预分配、空间慵懒开释等,这些都是 SDS 结构化字符串带来的强壮的扩展才干。

链表(linked list)

链表数据结构咱们是比较了解的,最大的特色就是节点的增、删十分灵敏。redis List 数据类型底层就是依据链表来完结。这是 redis 3.0 完结。

typedef struct list {
  listNode *head;
  listNode *tail;
  void *(*dup)(void *ptr);
  void (*free)(void *ptr);
  int (*match)(void *ptr, void *key);
  unsigned long len;
} list;
typedef struct listNode {
  struct listNode *prev;
  struct listNode *next;
  void *value;
} listNode;

在 redis 3.2.0 版别的时分引入了 quicklist 链表结构,结合了 linkedlist 和 ziplist 的优势。

typedef struct quicklist {
  quicklistNode *head;
  quicklistNode *tail;
  unsigned long count;  /* total count of all entries in all ziplists */
  unsigned int len;   /* number of quicklistNodes */
  int fill : 16;  /* fill factor for individual nodes */
  unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;
typedef struct quicklistNode {
  struct quicklistNode *prev;
  struct quicklistNode *next;
  unsigned char *zl;
  unsigned int sz;   /* ziplist size in bytes */
  unsigned int count : 16; /* count of items in ziplist */
  unsigned int encoding : 2; /* RAW1 or LZF2 */
  unsigned int container : 2;  /* NONE1 or ZIPLIST2 */
  unsigned int recompress : 1; /* was this node previous compressed? */
  unsigned int attempted_compress : 1; /* node cant compress; too small */
  unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quicklist 供给了灵敏性一起也统筹了 ziplist 的紧缩才干,quicklist->encoding 指定了两种紧缩算法。 quicklist->compress 表明咱们能够进行 quicklist node 的深度紧缩才干。redis 供给了两个有关于紧缩的装备。

list-max-ziplist-size:ziplist长度操控
list-compress-depth:操控链表两头节点的紧缩个数,越是接近两头的节点被拜访的机率越大,所以能够将拜访机率大的节点不紧缩,其他节点进行紧缩

比照 redis 3.2 的 quicklist 与 redis 3.0 ,很明显 quicklist 供给了愈加丰厚的紧缩功用。redis 3.0 的版别是每个 listnode 直接缓存值,而 quicklistnode 还有强壮的有关于紧缩才干。

LPUSH list:products:mall 100 200 300
(integer) 3
OBJECT encoding list:products:mall
"quicklist"
版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表娱乐之横扫全球立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章