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

背景

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

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

树形结构的常见场景

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

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

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

树形结构的解决方案

邻接表

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

“邻接表”的优点：

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

“邻接表”的缺点：

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

路径枚举

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

“路径枚举”的优点：

• 查询节点的所有父节点高效：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。示例如下：

业务逻辑：

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

需要注意的是：

• 更新Redis时采用批量更新提升性能，HMSET key field value [field value …]
• 实际生产中，我们采用的是二级缓存，方案更复杂，此处不展开

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脚本命令简述

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]获取传入的参数

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，则不能使用此方式了

127.0.0.1:6379> SCRIPT LOAD "return 1"
"e0e1f9fabfc9d4800c877a703b823ac0578ff8db"

// 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 …]后的均为附加参数，个数不固定
• 返回值：脚本执行结果

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：脚本不存在

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命令无差别攻击，不能清除指定的脚本

127.0.0.1:6379> SCRIPT FLUSH
OK

SCRIPT KILL

• 参数：SCRIPT KILL
• 功能：杀死正在执行的没有写操作的Lua脚本
• 可用版本：2.6.0
• 时间复杂度：O(1)
• 参数说明：无参数
• 备注：KILL命令无差别攻击，不能杀死指定的脚本

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
• 备注：没有方式可以查看当前的脚本调试模式

// 指定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()，当下一行有断点时暂停

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

[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, 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 )。

-- 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 NOSAVE和SHUTDOWN的区别在于SHUTDOWN NOSAVE不会进行持久化操作，也就是说在上一次快照后的数据修改都将丢失

// 此脚本可被 SCRIPT KILL 杀死

eval 'while(true) do print("1") end' 0

// 此脚本 不可被 SCRIPT KILL 杀死

eval "redis.call('set','公众号','appblog') while true do end" 0

// 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

// 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脚本注意事项：

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即可正常运行

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，但数据量过大时，极易造成数据倾斜，从而影响系统的稳定性。所以使用前请充分分析评估数据，按需灵活处理

// 集群模式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://redis.io/commands/eval
• https://redis.io/topics/ldb

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