@yishuailuo 2019-03-06T15:10:35.000000Z 字数 16551 阅读 7708

一万六千字谈谈如何实现经典“四则运算”算法优化 Redis 集合运算

一万六千字谈谈如何实现经典“四则运算”算法优化 Redis 集合运算

一、本文概述

本文主要介绍为什么要使用 Lua 脚本在 Redis 环境中优化集合运算，以及如何使用 Lua 脚本在 Redis 环境中优化集合运算。在介绍这两部分内容中间，还会穿插着介绍 Redis 数据库和 Lua 语言的一些基础知识，以及经典“四则运算”算法的基础知识。

二、为什么要“优化” Redis 集合运算

2.1 Redis 集合运算简介

Redis 中有两种集合类型：set（无序集合）和 sorted set（有序集合），针对集合的单次运算（交，并，差）有原生的 Redis 命令支持。

2.1.1 无序集合 set 命令

sadd key member [member ...]
sinter key [key ...]
sinterstore destination key [key ...]
sunion key [key ...]
sunionstore destination key [key ...]
sdiff key [key ...]
sdiffstore destination key [key ...]
sismember key member
smembers key
...

更多 Redis 无序集合相关命令请参见：：Redis set

2.1.2 有序集合 sorted set 命令

zadd key [NX|XX] [CH] [INCR] score member [score member ...]
zinterstore destination numkeys key [key ...] [WEIGHTS weight [weight ...]] [AGGREGATE SUM|MIN|MAX]
zunionstore destination numkeys key [key ...] [WEIGHTS weight [weight ...]] [AGGREGATE SUM|MIN|MAX]
...

sorted set 没有 zinter、zunion，也没有 zdiffstore。其中，zdiffstore 的语义需要通过组合其他命令来实现。

更多Redis 有序集合相关命令请参见：Redis zset

2.1.3 集合运算示例

我们先简单地看一下 sadd、sunionstore 命令。setX（包含[a,b,c]）和 setY（包含[c,d]）是无序集合，通过求 setX 和 setY 的并集，并把结果存入集合 setZ。可以得知，在集合 setX 或者在 setY 中的元素有[a,b,c,d]。

图1：无序集合 set 的求并集示例

然后再看一下 zadd、zinterstore 命令。zsetX（包含[a:1,b:2,c:3]）和 zsetY（包含[c:3,d:6]）是有序集合，通过求 zsetX 和 zsetY 的交集，并把结果存入集合 zsetZ。可以得知，在集合 zsetX 并且在 zsetY 中的元素有[c:6]。

图2：有序集合 sorted set 的求交集示例

2.2 为什么要“优化”

假设有这样的需求场景

有表示性别为男性的无序集合 male，元素有 [张三，李四，王五]，
有表示年龄的有序集合 age，元素有 [张三:20，李四:35，王五:43，赵六:50]
有表示住址在上海的无序集合 sh，元素有 [李四，王五]。

现在需要找出“居住在上海并且年龄大于30岁的男性”。

2.2.1 普通原生集合命令实现

先找出年龄大于30岁的男性，临时结果存为有序集合 tempSet1，元素有 [李四:35，王五:43，赵六:50]；
接着将 tempSet1 和 male 作交集，临时结果存为有序集合 tempSet2，元素有 [李四:35，王五:43]；
然后将 tempSet2 和 sh 作交集，最终结果存为有序集合 resultSet，元素有 [李四:35，王五:43]；
所以“居住在上海并且年龄大于30岁的男性”有李四和王五。

如图所示：

图3：原生命令找出“居住在上海并且年龄大于30岁的男性”示例

从图中我们可以看出，要找出“居住在上海并且年龄大于30岁的男性”需要多次进行集合运算，过程中与服务器有多次交互，并且无法保证原子性。

2.2.2 普通原生集合命令+事务实现

当然，我们可以使用 Redis 事务来保证计算 tempSet1，tempSet2 和 resultSet的原子性，但是，仍旧没法避免客户端与服务端的多次交互。如图所示：

图4：原生命令+事务找出“居住在上海并且年龄大于30岁的男性”示例

2.2.3 集合个数不定、需求场景多变的集合运算

另外，我们再看一下另几种需求，找出“年龄大于40岁且不居住在上海的男性”，找出“年龄小于30岁居住在上海的男性”等等。其中，我们会发现，针对每一种需求，我们需要写多套 redis 原生命令的组合逻辑(或者再加上 redis 事务)；

再者，如果我们还有别的集合，比如表示性别为女性的无序集合 female，元素有[王丽，李红，张英]，表示芝麻信用分的有序集合 credit，元素有[王丽:550，李红:650，张英:730]；（注：信用分，年龄等有序集合表示的是用户的全集，实际上集合应为age:[王丽:18，李红:19，张英:19，张三:20，李四:35，王五:43，赵六:50]，credit:[王丽:550，李红:650，张三:675，李四:693，张英:730，赵六:740，王五:751]）等等。

现在总的集合信息如下：

male: [张三，李四，王五]
female: [王丽，李红，张英]
sh: [李四，王五]。
age: [王丽:18，李红:19，张英:19，张三:20，李四:35，王五:43，赵六:50]
credit: [王丽:550，李红:650，张三:675，李四:693，张英:730，赵六:740，王五:751]

那么如果现在需要找出，“能看白领日记且居住在上海的男性”，那么先找到男性，再找到居住在上海的，然后找到芝麻信用分大于750的（注：只有分数大于等于750才能看白领日记，校园日记等），用 Redis 原生命令加事务与服务端多次交互，几个集合作运算后我们一下子就知道只有隔壁老王——王五能看"白领日记"。

从此可以看出，当我们的集合个数不定，需求场景多变的情况下，用原生集合命令或者事务需要客户端多套编写复杂的逻辑。（这些都是我实际开发中遇到的需求问题。）

2.2.4 总结需要“优化”的原因

那么我们大致可以得出结论，为什么需要“优化” Redis 集合运算。

原生集合命令不支持多次交并差集合混合运算；
使用原生集合命令多次集合运算不能保证原子性；
使用原生集合命令多次与服务端交互非常耗时；
使用 Redis 事务同样无法避免与服务端多次交互；
使用原生集合命令或者事务需要客户端编写复杂逻辑。

既然知道了为什么要“优化”，不优化没法保证一次交互作多次集合混合运算，不优化没法保证多次集合运算原子性，不优化没法减少交互传输的耗时，不优化需要客户端编写多套复杂逻辑，那么我们如何去做优化呢？这时候就该 "Lua 脚本"以及经典"四则运算"算法登场了。Lua 脚本是解决一次交互，耗时以及原子性问题的，而经典"四则运算"算法则解决集合个数不定，业务场景多变的问题的。

2.2.4 lua 脚本的简单示例

下面的章节会重点介绍 "Lua 脚本"以及经典"四则运算"算法。这里先来看一个简单的例子，还是刚才的需求场景，找出“居住在上海并且年龄大于30岁的男性”。

图5：lua 脚本组合命令找出“居住在上海并且年龄大于30岁的男性”示例

图6：找出“居住在上海并且年龄大于30岁的男性”的简单lua 脚本

使用 lua 脚本组合了多条 redis 命令，在客户端调用的时候，只需要与服务端交互一次，把脚本传到服务端，这里只有一次传输，服务端接受到脚本后，原子性地执行 lua 脚本里的多条 redis 命令。

这里如果把集合的交并差以及大于小于等比较符映射成符号 &&，II，^，>，< 等，那么找出“居住在上海并且年龄大于30岁的男性”的集合运算表达式就可以表示为age:score>30 && male && sh，找出“能看白领日记且居住在上海的男性”的集合运算表达式就可以表示为credit:score>=750 && male && sh；其他需求场景与此类似，都可以抽象成一个这样的集合运算表达式。

图7：lua 脚本处理集合个数不定，业务需求多变的情况

那么，只要脚本封装好了无序集合和有序集合的交并差等命令，接收上述那样的集合运算表达式，并且有算法逻辑处理交并差等集合运算的先后顺序，那么就能支持多个集合运算以及满足不同的需求场景了，这里算法就是经典的“四则运算”算法，只不过为了满足具体的需求，我们稍微做了一下算法的变形，稍后会详细介绍。

三、Redis 及 Lua 基础知识

在介绍用 lua 脚本实现经典四则运算算法“优化”集合运算之前，我们先来了解一下 Redis 以及 Lua 相关的基础知识，以便后续深入介绍具体的脚本与算法。

3.1 Redis 客户端与服务端交互

3.1.1 客户端与服务端交互

Redis 服务器是一对多服务器程序，一个服务器可以与多个客户端建立网络连接，这里的客户端指的是普通客户端；Redis 还有伪客户端，它处理的命令请求来自服务端的 lua 脚本（执行 Redis 命令）或者 AOF 文件（还原数据库状态），无需通过网络连接，直接在服务端执行。其中，这两个伪客户端又稍有不同：

Lua 伪客户端
- 服务器运行的整个生命周期会一直存在
- 服务器关闭时关闭
AOF 伪客户端
- 载入 AOF 文件还原数据库时存在
- 载入完成后关闭

另外，Redis 服务器使用单线程单进程方式处理命令请求的，同时处理多个客户端命令请求需要排队等待。

图8：普通客户端，伪客户端与服务端交互

3.1.2 客户端缓冲区以及软硬性限制

每个 Redis 客户端与服务端连接时，服务端会为每个客户端的连接创建相应的 redisClient 结构（客户端状态），它保存着客户端的当前状态信息（比较通用的属性）以及执行相关功能需要用到的数据结构（和特定功能相关的属性）。

typedef struct redisClient {
    // ...
    int fd;       // 描述符：-1-伪客户端，大于-1的整数-普通客户端
    robj *name;   // 名字
    int flag;     // 标志位，表示客户端角色状态等：REDIS_SLAVE-从服务器，REDIS_MULTI-正执行事务
    sds querybuf; // 输入缓冲，空间根据输入动态伸缩，最大为1G，超出客户端会被关闭
    /**
    * 以下两个为固定大小输出缓冲区两个属性，REDIS_REPLY_CHUNK_BYTES = 16*1024 即 16 KB
    */
    char buf[REDIS_REPLY_CHUNK_BYTES]; // 固定大小缓冲区字节数组
    int bufpos;   // 固定大小缓冲区已使用字节数
    list *reply;  // 可变大小缓冲区，链表构成，理论上可变大小缓冲区可无限大，实际上不能超过硬性限制
    robj **argv;  // 命令参数，如 "set age 18"
    int argc;     // 命令参数个数，如上述命令则为 3，set 本身也是命令参数
    struct redisCommand *cmd;  // 命令的实现函数
    int authenticated;         // 身份验证：0-未通过，1-通过
    time_t ctime;  // 客户端创建时间
    time_t lastinteration;     // 客户端与服务端最后一次互动时间
    time_t obuf_soft_limit_reached_time; // 输出缓冲区第一次到达软性限制的时间
    // ...
} redisClient

这里着重讲讲，输入缓冲区，输出缓冲区（包括硬性限制与软性限制）。

输入缓冲区
- 客户端状态结构 redis-cli 保存的输入缓冲区保存客户端发送的命令请求。缓冲区的大小根据输入内容动态地缩小后者扩大，最大不能超过 1G。
- 如果客户端发送的命令请求大小超过了输入缓冲区的限制大小（默认为1GB），那么这个客户端将会被服务器关闭。
输出缓冲区
- 固定大小缓冲区——字节数组
  - 保存长度较小的回复
    - 比如'OK'
    - 比如简短的字符串值
    - 比如整数值
    - 比如错误回复等
- 可变大小的缓冲区——reply链表
  - 保存长度较大的回复
    - 比如一个非常长的字符串值
    - 比如一个有很多项组成的列表
    - 比如包含了很多元素的集合等等
- 如果发送给客户端的命令回复大小超过了输出缓冲区的大小，那么这个客户端将会被服务器关闭。服务端使用两种模式来限制客户端输出缓冲区的大小
  - 硬性限制
    - 如果输出缓冲区大小超过了硬性限制设置的大小，那么服务端立即关闭客户端。
  - 软性限制
    - 如果输出缓冲区大小超过了软性限制设置的大小，还没超过硬性限制，那么服务端讲使用客户端状态结构的 obuf_soft_limit_reached_time 属性记下客户端到达软性限制的起始时间；
    - 之后服务端会继续监控客户端，如果输出缓冲区大小一直超过软性限制，并且持续时间超过服务器设定的时长，那么服务端讲关闭客户端；
    - 相反地，如果输出缓冲区大小在指定时间内不再超出软性限制，那么客户端就不会被关闭，并且 obuf_soft_limit_reached_time 属性值也会被清零。
    - 使用 client-output-buffer-limit 选项可为普通客户端，从服务器客户端，执行发布与订阅的客户端分别设置不同的软性限制和硬性限制，格式如下：
      - client-output-buffer-limit < class > < hard limit > < soft limit > < soft seconds >
        
        client-output-buffer-limit normal 0 0 0 —— 0 指不限制
        
        client-output-buffer-limit slave 256mb 64mb 60
        
        client-output-buffer-limit pubsub 32mb 8mb 60

当然，通过 client list 命令可查看 redis 客户端结构的部分当前状态，如下：

图9：通过 client list 命令查客户端当前状态

3.2 Redis 中 Lua 环境

3.2.1 我对 Lua 语言的理解

Lua 语言是一门嵌入式脚本语言。这里有两个关键字：嵌入式 和脚本。“脚本”在这里是指无需编译，按行执行，它的语言风格跟 python 和 perl 语言较为类似；“嵌入式”在这里是指它通过嵌入某个环境，再结合宿主语言某些特性（例如在 Redis 环境中可调用 C 函数）来发挥它本身作为语言的作用。

这里对于“嵌入式”的理解，如果以 Lua 语言嵌入到 Redis 环境来举例的话，意思是 Redis 服务端中有 Lua 环境，通过在 Redis 服务端执行 lua 脚本，能够实现有复杂逻辑的多个 redis 命令的原子执行。

3.2.2 客户端使用 Lua 脚本与 Redis 交互的简单示例

Redis 从 2.6 版本开始引入对 Lua 脚本的支持，通过在服务器中嵌入 Lua 环境，Redis 客户端可以使用 Lua 脚本，直接在服务器原子地执行多个命令。

3.2.2.1 lua 脚本输出 Hello World 的例子

先来看个简单的例子：

图10：lua 脚本输出 hello world

从上图可知，当服务端开启的状态下，redis 客户端通过 eval 命令执行了 lua 脚本，脚本内容为 return 'Hello World'，脚本传入参数中 KEY 的个数为 0 个；我们看到客户端打印了脚本里返回的字符串 Hello World。

3.2.2.2 lua 脚本与 Redis 交互的例子

再看一个 lua 脚本与 Redis 交互的例子：

图11：lua 脚本与 redis 交互，set hello world 和 get hello

从上图可知，第一次交互中，redis 客户端通过 eval 命令执行了 lua 脚本，脚本内容为 return redis.pcall('set', KEYS[1], ARGV[1])，脚本传入参数中 KEY 的个数为 1，这个KEY是指接在 1 后面的 'hello'，这个'hello'等 KEY 被脚本里的 KEY[] 数组接收，KEY[1] 表示第一个 KEY ，即 'hello' ，然后 'hello' 紧接着是参数 'world'，这个 'world' 等 ARGV 被脚本里的 ARGV[] 数组接收，ARGV[1] 表示第一个 ARGV，即 'world' ，脚本里 redis.pcall() 调用 set 命令；我们看到客户端打印了脚本里执行 set 命令返回的 ok，如同直接用 redis-cli 写 set 命令得到的返回一样。

第二次交互中，redis 客户端同样通过 eval 命令执行了 lua 脚本，脚本内容为 return redis.pcall('get', KEYS[1])，脚本传入参数中 KEY 的个数为 1，这个 KEY 是指接在 1 后面的 'hello'，与第一次执行 set 命令的交互一样，这个 'hello' 就是 KEYS[1]，这里没有参数 ARGV[]，脚本里 redis.pcall() 调用 get 命令；我们看到客户端打印了脚本里执行 get 命令返回的 'world'，如同直接用 redis-cli 写 get 命令得到的返回一样。

从以上两个例子可以看到，redis 客户端通过 eval 命令把 lua 脚本传送到 redis 服务端执行，并且可以使用 redis.pcall() 函数调用 redis 的命令。

那么这个过程是怎么样的呢？接下来一小节做个大概的阐述。

3.2.3 Lua 语言如何 "嵌入" Redis 环境

在介绍 eval 命令从发送脚本到服务端到服务端执行脚本之前，我们先看一下执行 lua 脚本前 Redis 的一些准备工作。

3.2.3.1 lua 环境准备工作——伪客户端

如之前所述，服务端是通过创造一个伪客户端来专门执行 lua 脚本的。服务器内嵌一个 Lua 环境，并对这个环境进行一系列修改，从而确保这个 Lua 环境可以满足 Redis 服务器的需要（就我个人的理解，这个环境可以类比 Java语言中的 JVM）。

图12：lua 伪客户端

Redis 服务器创建和修改 Lua 环境的整个过程包括以下步骤：

图13：创建和修改 Lua 环境过程

从上图得知，Redis 创建和修改 Lua 环境经过了八个步骤，可以分为 创建 -> 修改 -> 添加三大过程；主要的过程可以概述为：创建基本的 lua 环境，为环境载入函数库，基于 Redis 环境对 lua 脚本原有的函数做调整并且禁止部分 lua 脚本的功能以保护 Redis 中 lua 的全局环境，然后把经过这个修改后的 lua 环境添加到服务器状态结构中。

好了，那么多个客户端都调用了 lua 脚本，那需要多少个环境呢？

刚才我们已经了解过了 Redis 使用串行化（单线程）方式执行 Redis 命令的，所以答案是，在特定时间内，最多只有一个脚本能放在 lua 环境中，那么整个 Redis 服务器只需要创建一个 Lua 环境即可。

那么我们来看一下，脚本调用方、lua 环境、伪客户端与服务端（其实是指命令执行器）之间的交互关系。

图14：脚本调用方、lua 环境、伪客户端与服务端（其实是指命令执行器）交互关系

服务端准备好 Lua 环境后，Jedis 或者 redis-cli 等调用方通过 eval 命令把 Lua 脚本发送到服务端，服务端载入脚本到 lua 环境，lua 环境把 redis.call() 函数要执行的 redis 命令发送到 lua 伪客户端，伪客户端就和普通客户端一样地与命令执行器交互————发送命令与获取命令结果。其中，redis.call() 函数可能是在 lua 脚本中多次被调用的，所以会有多次的与 redis 命令执行器的交互。

3.2.3.2 lua 环境之脚本字典

在 Lua 环境与服务端的交互的过程中，除了伪客户端这个组件，还有另一个组件是脚本字典（lua_sripts）。这个字典的键是某个 Lua 脚本的 SHA1 校验和，字典的值是这个脚本，那么字典就可以维护多个 lua 脚本。

图15：通过 script load 命令加载 lua 脚本的 SHA1 值

图16：redisServer 结构中的 lua_scripts

3.2.4 eval 命令格式及其执行过程

3.2.4.1 eval 命令格式

Redis 通过 eval 命令执行 lua 脚本，eval 命令格式为：EVAL script numkeys key [key ...] arg [arg ...]

命令第一个参数 scipts 是脚本，第二个参数 numkeys 是键名 key 的个数，后面跟着键 key，接着是脚本所需参数 arg。比如：

> eval "return {KEYS[1],KEYS[2],ARGV[1]}" 2 key1 key2 first
1) "key1"
2) "key2"
3) "first"

这里 numkeys 为2表示有 key1 key2 两个键，key1 key2 传入到脚本中，被 KEYS[] 数组接收，first 脚本参数被 ARGV[] 数组接收。详请请参考：Redis eval command

Redis 建议所有用到的 key (指redis的key)，都需要传到 KEYS[] 数组，而不是传到 ARGV[] 数组，这个应该是基于 Redis 集群的考虑。

注意：lua 脚本和事务其中有命令出错，都会继续往下执行，并没有回滚。
为了保证原子性，用scan，zscan 或者 sscan 等命令会“阻塞”服务端，这里的“阻塞”是指对 redis 数据库的写操作无法生效。

3.2.4.2 eval 命令执行过程

好了，现在再来回答前面说，eval 命令发送脚本到服务端到服务端执行脚本这个过程是怎么样的那个问题。

eval 命令执行过程可以分为以下三个步骤：

图17：eval 命令执行过程

根据客户端给定的 Lua 脚本，在 Lua 环境中定义一个 Lua 函数。
- 计算脚本的 SHA1 校验和
- 函数名为 f_SHA1校验和，函数体为脚本本身
- 例如：对于命令 eval "return 'hello world'" 0，脚本为 return 'hello world'，计算它的 SHA1 校验和为 “5332031c6b470dc5a0dd9b4bf2030dea6d65de91”，那么函数名为 f_5332031c6b470dc5a0dd9b4bf2030dea6d65de91，函数体为 return 'hello world'。
- 使用函数保存存入脚本好处是：
  - 执行脚本很简单，调用与脚本相应的函数即可。
  - 通过函数的局部性让 Lua 环境保持清洁，减少垃圾回收的工作量，并且避免使用全局变量。
  - 如果脚本对应的函数被定义过，那么只要记住这个脚本的 SHA1 校验和，就可以在不知道脚本的情况下，直接通过调用 lua 函数执行函数。这也是 eval 命令的实现原理。
    - 上图中，当得知脚本的 SHA1 校验和，直接通过 evelsha 命令可以直接调用 SHA1 校验和对应的脚本，即上面的 return 'hello world'
将客户端给定的 Lua 脚本保存到 lua_scripts 字典，等待将来进一步使用。
- 脚本的 SHA1 校验和作为 key，脚本本身作为 value 值存入 lua_scripts 字典。
执行刚刚在 Lua 环境中定义的函数，以此来执行客户端给定的 Lua 脚本。
- 准备和执行脚本过程如下：
  - 将 eval 命令传入的键名参数和脚本参数分别存到 KEYS 数组和 ARGV 数组，作为全局变量传到 Lua 环境里面。
  - 将 Lua 环境装载超时处理钩子，在脚本出现超时情况下，客户端可通过 script kill 命令停止脚本或者 shutdown nosave 命令直接关闭服务器
    - 脚本有最大执行时间，默认为 5 秒，保存在配置文件的 lua-time-limit 配置项里。
  - 执行脚本函数
    - 脚本只可传参和修改 Redis 数据，不可访问外部系统（访问文件系统和系统调用）
  - 移除超时钩子
  - 将执行函数所得结果保存到输出缓冲区，等到服务器将结果返回给客户端
  - 对 Lua 环境执行垃圾回收操作

四、“四则运算”算法基础知识

数学意义上，加减乘除运算被称为“四则运算”，如1+2*3-4，“四则运算”算法主要分两步：第一步是中缀表达式转后缀表达式，第二步是计算后缀表达式得到结果。

4.1 基本概念介绍

4.1.1 中缀表达式与后缀表达式

一般情况下，四则运算的表达式为中缀表达式，比如表达式 A+(B-C/D)*E，该表达式的中缀表达式与后缀表达式如下：

中缀表达式：A+(B-C/D)*E
后缀表达式：ABCD/-E*+

中缀表达式将操作符置于两个操作数中；后缀表达式将操作符置于两个操作数之后；另外，后缀表达式已经去除括号，并且定义了运算的先后顺序，稍后我们来分析。

4.1.2 操作符与操作数

中后缀表达式中的字符有操作数和操作符之分：

操作符：表达式中的 +-*/()（稍后运算用到的#符号也是）
操作数：表达式中的 ABCDE

也就是说，我们将加(+)、减(-)、乘(*)、除(/)、和括号("()")称作操作符，将运算的字符A、B、C、D、E称作操作数。

4.1.3 栈、队列与操作符优先级

将中缀表达式转为后缀表达式，需要

一个操作符栈 —— 后进先出 LIFO

一个字符队列 —— 先进先出 FIFO

定义操作符优先级

其中，操作符栈 存储操作符，并对操作符进行入栈出栈操作；字符队列存储转换前后的表达式；操作符优先级定义了栈内以及栈外各个操作符的优先级。

操作符优先级规则如下：

* / 优先级相同，+ - 优先级相同

优先级： * / > + -；

同一优先级(比如 + - )：先进栈 < 后进栈；

井号 # 优先级最低

在栈外，左括号 ( 优先级最高；在栈内，( 优先级除井号 # 外最低

总的来说，在栈外 ( > * / > + - > ) > '#'；在栈内 * / > + - > ) > ( > #

计算后缀表达式，需要

一个操作数栈 —— 后进先出 LIFO

一个字符队列 —— 先进先出 FIFO

4.2 中缀表达式转后缀表达式的过程

4.2.1 转换过程流程图

图18：中缀表达式转后缀表达式过程

主要的过程为：

循环读取表达式字符队列的字符
- 如果是操作数
  - 直接入队列
- 如果是操作符
  - 如果是 ")" 操作符
    - 栈顶元素出栈，入队列，直到遇到第一个 “(”
    - 如果还没读取到 ”(“，就已经读到了 "#"，说明表达式左括号和右括号不匹配
  - 否则，如果是 “(” 操作符
    - 直接入栈
  - 否则，比较指针读取的当前操作符，与栈顶操作符的优先级
    - 如果当前元素 <= 栈顶元素
      - 栈顶元素出栈，入队列
      - 直到遇到优先级 > 当前元素的栈顶单词，或者遇到“#”，当前元素入栈
    - 否则，（当前元素优先级 > 栈顶元素）当前元素入栈
- 当队列读取到末尾，栈中所有元素依次出栈，并入队列（#也入队列）

4.2.2 转换过程详细示例

表达式 A+(B-C/D)*E 中缀转后缀流程参见如下 PPT 演示：中缀转后缀流程

4.3 计算后缀表达式过程

4.3.1 计算过程流程图

图19：计算过程流程图

主要的过程为：

循环读取表达式字符队列的字符
- 如果是操作数（不是操作符）
  - 直接入栈
- 否则是操作符
  - 栈顶弹出两个操作符，做四则运算，结果重新入栈
- 如果遇到队列尾，结束

4.3.2 计算过程示例

表达式 ABCD/-E*+ 计算后缀表达式流程参见如下 PPT 演示：计算后缀表达式流程

4.4 简单示例

下面演示一个简单的示例，演示通过中缀表达式转后缀表达式，并计算后缀表达式来计算 1+(3-4/2)*5 的过程：

表达式 1+(3-4/2)*5 中缀转后缀流程参见如下 PPT 演示：中缀转后缀示例

表达式 1342/-5*+ 计算后缀表达式流程参见如下 PPT 演示：计算后缀表达式示例

五、Lua 脚本实现 “四则运算”算法“优化”集合运算

5.1 从理论到 lua 脚本实战概述

既然已经找到了 Redis 与 Lua 的基础知识，也知道“四则运算”算法的基础知识，那么接下来我们看看如何用 Lua 脚本来实现，并且过程中需要做哪些落地实战的改造。

再看一下之前的 Lua 脚本处理集合个数不定，业务需求多变的情况的图。

图20：lua 脚本处理集合个数不定，业务需求多变的情况

从图的左边一栏我们可以看到，每一栏位都是一个表达式，我们可以对其中的表达式做拆分，以符合“四则运算”算法中“字符”的定义，这里我们以示例来讲解，credit:score >= 50 && male 可以拆分为 credit:score、>=、50、&& 和 male 五部分，其中：

操作符：>= &&
操作数：credit:score、50、male

我们把操作符和操作数作为最基本的单元，相当于经典“四则运算”算法的“字符”，这里我们称作“单词”，即以“单词”做最基本单元作运算。

我们可以想到，如果把经典“四则运算”算法的操作符 + - * / 换成 && || ^ >= > <= < = != 等操作符，把经典“四则运算”算法的操作数 A B C D E，替换为 Redis 集合交并差运算需要的male、age、和credit:score等操作数，那么我们就可以实现这个 Lua 脚本满足集合的交并差等混合运算。

5.2 lua 脚本实战

5.2.1 简单演示

还是第一节举例的例子：

图21：准备无序集合 male，sh，有序集合 age

图22：使用 lua 脚本运算 sh && male && age:score >40示例

图23：跑 shell 脚本调用 lua 脚本

图24：查看 lua 脚本运算得到的有序集合 result

从以上几个图可以看到，运算sh && male && age:score >40 意思是找出居住在上海且年龄大于40岁的男性，从结果可知，就是王五，其年龄为45岁。从这个简单的示例我们可以推测，只要有相应的集合，当写好表达式，都能一次性地与服务端交互，算出想要的表达式结果。

接下来我们从设计和代码层面来实现这个脚本。

5.2.2 设计层面

我们需要：

两种数据结构：
- 栈
- 队列
主要的两个流程：
- 中缀表达式转后缀表达式
- 计算后缀表达式得到结果
辅助的一个流程：
- 字符序列转单词序列
操作符优先级

5.2.3 代码层面

5.2.3.1 栈定义

--[[
    栈定义 
        格式示例：{ stack_table={"A","B","C"} }
        函数：
            新建并初始化栈：new(o) -- o为基础栈，可为 nil
            入栈：push(element)
            出栈：pop()
            获取栈顶元素：top()
            判断是否空栈：isEmpty()
            栈大小：size()
            清空栈：clear()
            打印栈元素：printElement()
--]]

5.2.3.2 队列定义

--[[
    队列定义 
        格式示例：{ queue_table={"A","B","C"}, capacity = 10000, size_ = 3, head = 0, rear = 0}
        函数：
            新建并初始化队列：new(o) -- o为基础队列，可为 nil
            入队列：enQueue(element)
            出队列：deQueue()
            判断是否空队列：isEmpty()
            队列大小：size()
            清空队列：clear()
            打印队列元素：printElement()
--]]

5.2.3.3 逻辑表达式类定义

--[[
    逻辑表达式计算器定义 （利用闭包的方式模拟面向对象编程的类）
        私有成员属性：
            logic_expr：逻辑表达式
            key_final_set：最终结果集的key
            is_sorted_set_calc：是否是有序集合的运算
        私有成员函数：
            判断是否为操作符：isOperator(key)
            判断表达式是否有保留字'#'：hasNoSharpInExpr()
            校验表达式括号是否成对出现：isBracketsMatch()
            str 表达式转 queue_table：strToQueueTable(str_expr)
            中缀表达式转后缀：infix2Suffix(expr_queue)
            从单词中获取key：getKeyFromWord(word)
            判断单词是否为数字：is_operand_a_num(operand)
            计算后缀逻辑表达式：calcInRedis()
        公有成员函数：
            计算逻辑表达式主流程：calc()
--]]

5.2.3.4 操作符优先级定义

-- 栈外优先级 
local opr_priority_out_table = { ["("] = 4,  [">"] = 3, ["<"] = 3, [">="] = 3, ["<="] = 3, ["="] = 3, ["!="] = 3, ["||"] = 2, ["&&"] = 2, ["^"] = 2, [")"] = 1, ["#"] = -1 }
-- 栈内优先级
local opr_priority_in_table = { ["("] = 0, [">"] = 3, ["<"] = 3, [">="] = 3, ["<="] = 3, ["="] = 3, ["!="] = 3,  ["||"] = 2, ["&&"] = 2, ["^"] = 2, [")"] = 1, ["#"] = -1 }
-- 优先级存放在 table 中，相当于一个 hashmap，key 有操作符，value 为优先级，数字越大，优先级越高（即 4 > 3 > 2 > 1 > 0 > -1）

5.2.3.5 主流程实现

-- 计算逻辑表达式主流程
local calc = function ()
    -- str 表达式转 queue_table
    local status, queue_table_ = pcall(strToQueueTable)
    if not status then
        return {-1, queue_table_}
    end
    -- 初始化表达式队列
    local origin_queue = {queue_table = queue_table_}
    local expr_queue = Queue:new(origin_queue)
    -- 中缀表达式转后缀
    local status, suffix_queue = pcall(infix2Suffix, expr_queue)
    if not status then
        return {-1, suffix_queue}
    end
    --计算后缀表达式，得到结果集的元素个数
    local status, num_final_set = pcall(calcInRedis, suffix_queue)
    if not status then
        return {-1, num_final_set}
    end
    return num_final_set
    -- return {1, "success"}
end

5.2.3.6 脚本执行入口

--[[
    脚本执行入口
        KEYS[1] 最终结果集的key  
        ARGV[1] 逻辑表达式
        calc_result 最终结果
--]]
-- local key_final_set = "result"
-- local logic_expr = "sh&&male&&age:score>40"
-- local is_sorted_set_calc = true
-- 接收调用脚本传入的KEY与参数
local key_final_set = KEYS[1]
local logic_expr = ARGV[1]
local is_sorted_set_calc = ARGV[2]
local calc_result = {-1, "logic_expr or key_final_set is nil."}
if key_final_set ~= nil and logic_expr ~= nil then
    -- 初始化逻辑表达式计算器
    local logicExprCalculator = LogicExprCalculator(key_final_set, logic_expr, is_sorted_set_calc)
    -- 开始计算
    calc_result = logicExprCalculator.calc()
end
return calc_result

以上代码是整个 lua 脚本的部分代码片段，脚本入口 是 eval 命令传参数和接收参数的入口，脚本从这里开始调用主流程；主流程包含几大步骤（以 sh&&male&&age:score>40 举例）：

str 表达式转 queue_table
1.1. queue_table = {sh,male,&&,age:score,>,40,#}
初始化表达式队列
2.1. expr_queue = queue_table = {sh,male,&&,age:score,>,40,#}
中缀表达式转后缀
3.1. suffix_queue = {sh,male,&&,age:score,40,>,&&,#}
计算后缀表达式，得到结果集的元素个数
4.1. 先算 sh && male 得到 result1（即 sinterstore result1 ），再算 age:score > 40 得到 result2，最后算 result1 && result2 得到 result。
返回结果。
5.1. 返回 result 的个数

Lua 脚本完整代码请参考：lua 脚本“优化” Redis 集合运算完整代码

5.2.4 回顾 Lua 脚本能够“优化”的地方

5.2.4.1 五个优化点

Redis 集合运算需要“优化”的原因有一下几个：

原生集合命令不支持多次交并差集合混合运算；
使用原生集合命令多次集合运算不能保证原子性；
使用原生集合命令多次与服务端交互非常耗时；
使用 Redis 事务同样无法避免与服务端多次交互；
使用原生集合命令或者事务需要客户端编写复杂逻辑。

那么现在来看看实现了经典“四则运算”算法的 Lua 脚本能够“优化”哪些点。

Lua 脚本能支持 &&、||、^、>=、>、<=、<、=、!= 等操作符的混合使用（比如 (male && sh && age:score<40||credit:score>=750）。
- 解决上述的第 1 点：不支持多次交并差集合混合运算；
Lua 脚本传送到服务端后，服务端是原子性地执行整个 Lua 脚本，执行脚本过程中其他到达的命令将被阻塞。
- 解决上述第2点：不能保证原子性；
Lua 脚本一次性传输到服务端，调用方使用客户端只与服务端做一次交互，并且在调用过脚本之后，服务端有脚本对应的 SHA1 校验和可供客户端直接使用 evalsha 命令传入 SHA1 校验和 直接调用脚本，过程中一次交互，且不需要再传输脚本，减少了网络传输的耗时。这个稍后有详细介绍。
- 解决了上述的第3点：非常耗时
Lua 脚本一次性传输到服务端，调用方使用客户端只与服务端做一次交互。
- 解决上述的第4点：无法避免与服务端多次交互
Lua 脚本传送到服务端后，脚本就常驻在服务端（如果没有被 script flush 的话），客户端只需要传入简单的表达式，而不用编写复杂的逻辑。
- 解决上述的第5点：客户端编写复杂逻辑

5.2.4.2 Lua 解决耗时问题

接下来仔细介绍一下 Lua 脚本“优化”的第3点，现在有3个集合如下：

图25：准备无序集合 male，sh，有序集合 age

现在运行 sh 脚本分别查看使用 Lua 脚本以及不使用 Lua 脚本找出居住在上海且年龄大于40岁的男性，分别的耗时。

图26：使用和不使用 lua 脚本运算 sh && male && age:score >40示例

图27：跑 shell 脚本调用 lua 脚本并查看耗时。

图28：查看结果

从图24可以看出，使用 Lua 脚本做集合运算，的确减少了耗时。当然这只是一次的运算结果显示，我们可以不断地变换表达式，去做使用 Lua 脚本以及不使用 Lua 脚本耗时的对比。

另外，随着表达式涉及运算的集合个数的增加，不使用 Lua 脚本要做的交互次数增多，网络耗时将会随之增多，如果是使用 Lua 脚本，那么只有一次的交互将非常节省时间。

逻辑运算完整的 Lua 脚本
 计算耗时 sh 脚本

5.2.5 脚本实战的几个注意点

Lua "一切" 都是 table，这里的"一切"主要是指 array、hashmap、list 等集合类型。
Redis 不支持 Lua 脚本模块化，不能通过 import 引用模块，所以整个脚本都是在一个文件中。
栈的实现比较简单，就是对数组的增删改；队列的实现复杂一点，但也是对数组的增删改，设计到一定的算法，可以详看代码。
表达式字符串转字符队列时，注意分词（比如怎么把sh&&male&&age:score>40 分出sh、&&、male、age:score、>=、40来）。
在计算后缀表达式时，注意与 redis 交互的时候，如果没有原生命令直接支持，如何通过组合命令来实现（比如zdiffstore,, 有序集合的 >=，>，!= 等，这里不想说，脚本里有详细的注释说明）。
在计算后缀表达式时，注意与 redis 交互的时候，会有很多临时结果集的产生，需要清理掉临时结果集，才能保证与不使用 lua 脚本的效果是一样的。

最后插播个广告 —— 我们公司（上海数禾）招数据工程师，详情请点拉勾招聘链接

更多阅读：

两万字谈谈如何使用 Scrum 框架进行敏捷开发

与其临渊羡鱼不如退而结网 | 与其诅咒黑暗不如燃亮灯火 | 与其哀叹路遥不如上下求索