玩转Redis-Lua脚本入门到实战-树形结构存储及查询

背景

在toB公司负责中台业务,众多企业的部门关系是树形结构,前段时间有业务诉求是“在大数据量下高效查询指定部门的所有上级部门,企业的部门树形关系可能随时变更”。在MySQL的基础上遂想到了利用Redis缓存树形结构并实现高效查询。

树形结构的常见场景及解决方案

树形结构的常见场景

生活中我们有很多树形结构的数据场景,比如:

  • 国家行政区域编码
  • 企业组织架构

国家行政区域编码

企业组织架构

树形结构数据的特征是 有明显的所属关系,比如 “行政区域编码”示例中“朝阳区”属于“北京市”,“组织架构”示例中“社交产品部”属于“产品中心”。

树形结构的解决方案

邻接表

业界最常使用的方案恐怕就是“邻接表”了,简而言之,“邻接表”的每条数据都存储了“上级数据ID”。

数据ID 数据名称 上级数据ID
zhangsan 产品中心 总公司ID
lisi 社交产品部 zhangsan
wangwu 办公产品部 zhangsan
zhaoliu 办公产品一组 wangwu
zhouqi 办公产品二组 wangwu

“邻接表”的优点:

  • 添加数据高效
  • 修改数据的上级高效
  • 删除叶子节点数据高效

“邻接表”的缺点:

  • 删除中间节点需移动其子节点
  • 查询节点的所有叶子节点、所有父节点复杂(这里指MySQL,Oracle是支持递归查询的)

路径枚举

另一个比较常用的方案就是“路径枚举”了,其核心思想是,每条数据都有字段存储了其所有的上级信息。

数据ID 数据名称 路径
1 中国 1
11 北京市 1,11
110105 朝阳区 1,11,110105
51 四川省 1,51
5101 成都市 1,51,5101
510104 锦江区 1,51,5101,510104

“路径枚举”的优点:

  • 查询节点的所有父节点高效:select 路径 where 数据ID = '节点ID';
  • 查询节点的所有子节点高效:select 数据ID where 路径 like '1,51%';

“路径枚举”的缺点:

  • 依赖复杂逻辑维护路径
  • 路径长度可能失控
  • 非叶子节点删除或变更上级节点时,所有子节点都将变动

除了“邻接表”、“路径枚举”,还有存储子孙节点范围的“嵌套集”、维护独立数据表存储所有子孙节点关系的“闭包表”等方案用于存储树形结构数据。由于不是本文重点,此处不再赘述。

在实际的生产方案中,我们也不用拘泥于以上某个方案,适当的将方案整合使用,往往事半功倍。比如我们的生产系统,就有将“邻接表”、“路径枚举”方案混合使用的场景,综合性能也相当出色。

不管黑猫白猫,抓到耗子就是好猫。

Redis下树形结构的存储

在阐述存储方案前,我们先详细梳理下现有的业务场景,技术都是为业务服务的。

toB系统,系统中有众多企业(company1 ~ company666),每个企业都有自己的部门树。示例:某公司 A0 下有 B1 ~ B50 这 50 个一级部门;每个一级部门下又有若干个二级部门(比如 B1 下有 CB1-1 ~ CB1-30 这 30 个二级部门,B3 下有 CB3-1 ~ CB3-40 这 40 个二级部门);同理,每个二级部门下又有若干个三级部门。对于大企业而言,部门达到几千上万。此外需要注意的是,企业的部门信息是可能随时变动的。而现在我们的诉求是:查询第N级某个部门的所有上级部门信息。

树形结构的存储

在MySQL场景下,我们可以“邻接表”或者“路径枚举”方案,甚至于像上面提及的需要做方案混合。对于诉求“查询节点的所有父节点”,通过先前的方案分析,“路径枚举”是较优的方案。但如果当QPS很高,需要进一步提升性能呢,除了提升DB的性能响应外,我们是否还有其他的出路?

高性能的Redis进入了我们的视野,那么如何使用Redis完成树型结构的存储呢?

此处我们使用的Redis数据结构是 Hash,Redis的key为企业ID(depttree:企业ID),field 为 部门ID,field 对应的value是 该部门ID对应的上级部门ID。示例如下:

Hash实现树型结构存储

业务逻辑

  • 查询所有父部门时,先从缓存中查询,缓存缺失时从DB查询并更新到Redis
  • 部门关系变更时,则删除Redis缓存
  • 部门删除时,则删除Redis缓存
  • Redis中的数据存储采用的是“邻接表”的方式
  • 由于任意部门的父部门都可能变动,Redis中的数据存储不采用“路径枚举”方案

需要注意的是:

  • 更新Redis时采用批量更新提升性能,HMSET key field value [field value …]
  • 实际生产中,我们采用的是二级缓存,方案更复杂,此处不展开
1
HMSET depttree:企业001 B1 A0 B2 A0 B3 A0 CB1-1 B1

Redis中如何使用Lua脚本

在上一节中部门关系数据已经存到Redis了,从hash的结构看,无法一次性查询指定部门的所有上级部门,所以我们需要使用到 Lua 脚本。正式实战之前,我们先学习下Redis中如何使用 Lua 脚本。

Redis 2.6.0 版本开始支持 Lua 脚本。Redis中使用 Lua 脚本应直接提供程序体,不需要也不能定义一个函数。下面我们来开始Redis Lua脚本的入门吧。

Redis支持的Lua脚本命令简述

命令 功能 参数
EVAL 执行Lua脚本 EVAL script numkeys key [key …] arg [arg …]
SCRIPT LOAD 将脚本内容导入Redis的脚本缓存 SCRIPT LOAD script
EVALSHA 通过导入脚本的SHA1摘要值执行脚本 EVALSHA sha1 numkeys key [key …] arg [arg …]
SCRIPT EXISTS 判断指定SHA1摘要值的脚本是否存在 SCRIPT EXISTS sha1 [sha1 …]
SCRIPT FLUSH 清空所有的Lua脚本缓存 SCRIPT FLUSH
SCRIPT KILL 杀死正在执行的没有写操作的Lua脚本 SCRIPT KILL
SCRIPT DEBUG 设置Lua脚本debug模式 `SCRIPT DEBUG YES

Redis支持的Lua脚本命令详解

EVAL

  • 参数:EVAL script numkeys key [key …] arg [arg …]
  • 功能:执行Lua脚本
  • 可用版本:2.6.0
  • 时间复杂度:取决于执行的脚本
  • 参数说明:
    • script:脚本内容
    • numkeys:key的个数
    • [key …]:key值,个数必须和numkeys匹配
    • [arg …]:附加参数,[key …]后的均为附加参数,个数不固定
  • 返回值:脚本执行结果
  • 备注:Lua 脚本中通过KEYS[1]KEYS[2]ARGV[1]获取传入的参数
1
2
3
4
5
127.0.0.1:6379> eval "return redis.call('set','公众号','appblog.cn')" 0
OK

127.0.0.1:6379> eval "return redis.call('set',KEYS[1],'bar')" 1 foo
OK

SCRIPT LOAD

  • 参数:SCRIPT LOAD script
  • 功能:将脚本内容导入Redis的脚本缓存
  • 可用版本:2.6.0
  • 时间复杂度:O(N),N取决于脚本字节长度
  • 参数说明:
    • script:脚本内容
  • 返回值:导入脚本的SHA1摘要值
  • 备注
    • 同一个脚本连续导入返回的SHA1摘要值相同
    • 导入的脚本将用于存放在Redis的脚本缓存里,除非使用 FLUSH 命令删除
    • 使用redis-cli交互时,我们可以使用$(cat ./luascript/xxx.lua)的方式导入指定路径下的lua脚本
    • 如果已经进入Redis交互shell,则不能使用此方式了
1
2
127.0.0.1:6379> SCRIPT LOAD "return 1"
"e0e1f9fabfc9d4800c877a703b823ac0578ff8db"
1
2
3
4
5
// redis-cli 导入指定路径下的lua脚本,公众号 zxiaofan

./redis-cli -a password -p 6379 script load "$(cat ./luascript/xxx.lua)"
Warning: Using a password with '-a' or '-u' option on the command line interface may not be safe.
"8144f1139110991cf3f085b70f807a4ef261b727"

EVALSHA

  • 参数:EVALSHA sha1 numkeys key [key …] arg [arg …]
  • 功能:通过导入脚本的SHA1摘要值执行脚本
  • 可用版本:2.6.0
  • 时间复杂度:取决于执行的脚本
  • 参数说明:
    • sha1:导入脚本的 sha1 摘要值
    • numkeys:key的个数
    • [key …]:key值,个数必须和numkeys匹配
    • [arg …]:附加参数,[key …]后的均为附加参数,个数不固定
  • 返回值:脚本执行结果
1
2
127.0.0.1:6379> evalsha e0e1f9fabfc9d4800c877a703b823ac0578ff8db 0
"1"

SCRIPT EXISTS

  • 参数:SCRIPT EXISTS sha1 [sha1 …]
  • 功能:判断指定 SHA1 摘要值的脚本是否存在
  • 可用版本:2.6.0
  • 时间复杂度:O(N),N取决于 SHA1 摘要值数量,单个判断的时间复杂度是O(1)
  • 参数说明:
    • [sha1 …]:SHA1 摘要值列表
  • 返回值
    • 1:脚本存在
    • 0:脚本不存在
1
2
3
127.0.0.1:6379> SCRIPT EXISTS e0e1f9fabfc9d4800c877a703b823ac0578ff8db e0e1f9fabfc9d4800c877a703b823ac0578ff8db2
1) (integer) 1
2) (integer) 0

SCRIPT FLUSH

  • 参数:SCRIPT FLUSH
  • 功能:清空所有的Lua脚本缓存
  • 可用版本:2.6.0
  • 时间复杂度:O(N),N是Redis 脚本缓存中脚本的个数
  • 参数说明:无参数
  • 返回值:OK:清除成功
  • 备注:FLUSH命令无差别攻击,不能清除指定的脚本
1
2
127.0.0.1:6379> SCRIPT FLUSH
OK

SCRIPT KILL

  • 参数:SCRIPT KILL
  • 功能:杀死正在执行的没有写操作的Lua脚本
  • 可用版本:2.6.0
  • 时间复杂度:O(1)
  • 参数说明:无参数
  • 备注:KILL命令无差别攻击,不能杀死指定的脚本
1
2
127.0.0.1:6379> SCRIPT KILL
(error) NOTBUSY No scripts in execution right now.

SCRIPT DEBUG

  • 参数:SCRIPT DEBUG YES|SYNC|NO
  • 功能:设置Lua脚本debug模式
  • 可用版本:3.2.0
  • 时间复杂度:O(1)
  • 参数说明
    • YES:设置debug模式为异步模式,调试脚本不阻塞,所有的改变在对话关闭后将回滚
    • SYNC:设置debug模式为同步模式,调试脚本将阻塞,所有的改变将保存到Redis
    • NO:禁用脚本调试模式
  • 返回值:OK
  • 备注:没有方式可以查看当前的脚本调试模式
1
2
3
// 指定debug模式调试脚本;

./redis-cli --ldb-sync-mode --eval /tmp/script.lua

Redis如何调试Lua脚本

Redis中包含一个完整的 Lua调试器(Lua debugger),代号 LDB

  • 调试命令 s:单步执行
  • 调试命令 p:打印所有变量值
  • Lua 脚本中加入redis.debug()用于调试时打印信息到控制台
  • Lua 脚本加入redis.breakpoint(),当下一行有断点时暂停

其他详细调试命令说明见下文的注释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
[redis@redis redis]$./redis-cli --ldb --eval /tmp/script.lua mykey key1 arg1 arg2

Lua debugging session started, please use:
quit -- End the session.
restart -- Restart the script in debug mode again.
help -- Show Lua script debugging commands.

// 输入 help 可 查看调试命令,用的最多的应该是 s(单步执行)

lua debugger> help
Redis Lua debugger help:
[h]elp Show this help.
[s]tep Run current line and stop again. 单步执行;
[n]ext Alias for step. 单步执行,同s;
[c]continue Run till next breakpoint. 执行到下一个断点;
[l]list List source code around current line. 展示当前行源码;
[l]list [line] List source code around [line].
line = 0 means: current position.展示指定行源码;
[l]list [line] [ctx] In this form [ctx] specifies how many lines
to show before/after [line]. 从第[line]行开始,展示[ctx]行源码;
[w]hole List all source code. Alias for 'list 1 1000000'. 展示所有源码;
[p]rint Show all the local variables.打印所有变量值;
[p]rint <var> Show the value of the specified variable.
Can also show global vars KEYS and ARGV.打印指定变量值;
[b]reak Show all breakpoints.展示所有断点;
[b]reak <line> Add a breakpoint to the specified line.在指定行添加一个断点;
[b]reak -<line> Remove breakpoint from the specified line.移除指定行断点;
[b]reak 0 Remove all breakpoints.移除所有断点;
[t]race Show a backtrace.查看当前执行栈;
[e]eval <code> Execute some Lua code (in a different callframe). 独立的栈中执行Lua代码;
[r]edis <cmd> Execute a Redis command.执行一个Redis指令;
[m]axlen [len] Trim logged Redis replies and Lua var dumps to len.
Specifying zero as <len> means unlimited.
[a]bort Stop the execution of the script. In sync
mode dataset changes will be retained. 终止脚本执行,sync模式下写入的数据将被保留;

Debugger functions you can call from Lua scripts:
redis.debug() Produce logs in the debugger console.
redis.breakpoint() Stop execution like if there was a breakpoint in the
next line of code.

Lua脚本实战Redis树形结构

前文“Redis下树形结构的存储”已讲述Redis下树形结果数据的存储,此处主要讲解 如何通过 Lua 脚本 快速查询指定节点的所有上级节点

脚本入参总共有4个:

  • rediskey :Redis的key,key的数据结构是Hash
  • currentDeptNo :待查询的指定部门
  • utilDeptNo :查询上级部门的终止节点,查到此部门为止
  • maxGetTimes:迭代查询最大次数,避免脏数据形成死循环
    • 最大值 100,若传入的 maxGetTimes 超过 100 将强制赋值为 100
    • 因为实际的部门层级没有超过100的
1
2
3
4
5
6
7
8
9
10
// 数据初始化,1 的上级是 2, 2 的上级是 3, 3 的上级是 4

127.0.0.1:6378> HMSET depttree:001 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
OK

// 执行脚本
// 查找 节点1 的所有上级,直到查到节点 3 为止,最多查询 66 次。

[redis@redis redis]$ ./openredis.sh 6378 "--eval luascript/lua_getAllSupDept.lua depttree:001 1 3 66"
"1,2,3"

lua_getAllSupDept.lua 脚本已在github开源,持续完善更新:https://github.com/zxiaofan/OpenSource_Study/blob/master/redis_scripts/lua_getAllSupDept.lua

在Lua脚本中,Redis 返回的结果为 (nil) 时,其真实的数据类型为 boolean,所以数据不存在 的判断方式是if (tempDept == false )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
-- Redis Lua脚本:查询指定部门的所有上级部门
-- 脚本保存为 lua_getAllSupDept.lua;

--[[
luaScriptName: getAllSupDept;
function: get all Super Dept of currentDeptNo;
param:
rediskey: the key of redis, the data structures is Hashes;
currentDeptNo: the current DeptNo;
utilDeptNo: query super dept until the utilDeptNo;
maxGetTimes: the max times of query to prevent dead loop.
result:
a. the whole super detp data;
b. the super detp data but not until specified dept(utilDeptNo);
c. return currentDeptNo when no data;
d. return error "error: the times of query exceeded the maxGetTimes!";
--]]

local rediskey = KEYS[1];
local currentDeptNo = KEYS[2];
local utilDeptNo = KEYS[3];
local maxGetTimes = tonumber(KEYS[4]);

-- redis.debug("rediskey: %q",rediskey);
-- redis.debug("currentDeptNo: %q",currentDeptNo);
-- redis.debug("utilDeptNo: %q",utilDeptNo);
-- redis.debug("maxGetTimes: %q",maxGetTimes);


if(currentDeptNo == utilDeptNo) then
return currentDeptNo;
end

if(maxGetTimes > 100) then
maxGetTimes = 100;
end

local time = 1;

local result = currentDeptNo;
local tempDept = currentDeptNo;

while(tempDept ~= utilDeptNo)
do
if(time > maxGetTimes) then
return "error: the times of query exceeded the maxGetTimes!";
end

tempDept = redis.call('hget',rediskey , tempDept);
-- redis.debug("tempDept: %q",tempDept);

if(tempDept == false or tempDept == "NULL") then
return result;
end

result = result .. "," .. tempDept;
time = time + 1 ;
end

return result;

Redis中使用Lua脚本的注意事项

(1)脚本是一个程序体,不能定义函数

(2)脚本执行是原子性的,脚本执行时不会有其他脚本或Redis命令执行

  • 避免使用 Lua 慢脚本

(3)Lua脚本中的变量必须是 局部变量

(4)Lua脚本可通过 redis.conf 中的lua-time-limit设置最大运行时间

  • lua-time-limit:默认5000,即5秒
  • 脚本运行超过时间限制后,Redis 将接收其他指令,但由于要保证脚本的原子性,脚本不会被终止,其他指令将返回“BUSY”错误
  • 可通过SCRIPT KILL杀掉正在运行的 Lua脚本
  • SCRIPT KILL不能杀死正在运行的包含修改操作的脚本,此时需要执行SHUTDOWN NOSAVE命令来强行终止 Redis

(5)Lua脚本执行完毕后,命令才追加写入到AOF中

(6)脚本内容提前导入Redis中,再利用EVALSHA sha1执行 Lua 脚本可提升性能,如果脚本较大,还可以节省带宽

SHUTDOWN NOSAVESHUTDOWN的区别在于SHUTDOWN NOSAVE不会进行持久化操作,也就是说在上一次快照后的数据修改都将丢失

1
2
3
// 此脚本可被 SCRIPT KILL 杀死

eval 'while(true) do print("1") end' 0
1
2
3
// 此脚本 不可被 SCRIPT KILL 杀死

eval "redis.call('set','公众号','appblog') while true do end" 0
1
2
3
// Lua脚本执行超时后,日志里将有警告

Lua slow script detected: still in execution after 5000 milliseconds. You can try killing the script using the SCRIPT KILL command. Script SHA1 is: 3245e4edc1a1e2a9bac3c52e99466f9ccabf65c0
1
2
3
// jedis 提示 Lua 脚本超时信息;

redis.clients.jedis.exceptions.JedisDataException: BUSY Redis is busy running a script. You can only call SCRIPT KILL or SHUTDOWN NOSAVE.

Redis集群模式下Lua脚本注意事项

1
2
127.0.0.1:6379> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 key1 key2 公众号 appblog
(error) CROSSSLOT Keys in request don't hash to the same slot

Redis Cluster 操作多key时,要求命令中的所有key都属于一个slot,否则会抛出异常CROSSSLOT Keys in request don't hash to the same slot

通过查看jedis的getSlot源码,我们可以发现,如果 key 包含{},则会使用第一个{}中的字符串作为 hash key,所以集群模式下我们可以将 Redis key 的相同内容使用{}包装起来。

所以将上面报错的语句的 key1 key2 修改为{key}1 {key}2即可正常运行

1
2
3
4
5
127.0.0.1:6379> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 {key}1 {key}2 公众号 appblog
1) "{key}1"
2) "{key}2"
3) "公众号"
4) "appblog"

需要注意的是,{}模式虽然能将不同的 key hash 到相同solt,但数据量过大时,极易造成数据倾斜,从而影响系统的稳定性。所以使用前请充分分析评估数据,按需灵活处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 集群模式getSlot操作
// 源码来自:https://github.com/redis/jedis/blob/6ed1441ca4c5de7e66648edfeafa16854707482c/src/main/java/redis/clients/jedis/util/JedisClusterCRC16.java

public static int getSlot(byte[] key) {
if (key == null) {
throw new JedisClusterOperationException("Slot calculation of null is impossible");
}

int s = -1;
int e = -1;
boolean sFound = false;
for (int i = 0; i < key.length; i++) {
if (key[i] == '{' && !sFound) {
s = i;
sFound = true;
}
if (key[i] == '}' && sFound) {
e = i;
break;
}
}
if (s > -1 && e > -1 && e != s + 1) {
return getCRC16(key, s + 1, e) & (16384 - 1);
}
return getCRC16(key) & (16384 - 1);
}

后记

Lua 脚本法力无边,但也需慎之又慎,避免超时阻塞,避免数据倾斜

生产环境使用 Lua 脚本时,必须有严格的检查评审机制

参考文档:

转载至:https://zxiaofan.blog.csdn.net/article/details/111146879