关于redis:Redis-定长队列的探索和实践

vivo 互联网服务器团队 – Wang Zhi

一、业务背景

从技术的角度来说，技术计划的选型都是受限于理论的业务场景，都以解决理论业务场景为指标。

在咱们的理论业务场景中，须要以游戏的维度收集和上报行为数据，思考数据的量级，执行尽最大致力交付且容许数据的局部抛弃。

数据上报反对游戏的维度的批量上报，反对同一款游戏 128 个行为进行批量上报。

数据上报须要时效管制，上报的数据必须是上报时刻的前 3 分钟的数据。

整体数据的业务状态如下图所示：

二、技术选型

从业务的角度来说蕴含数据的收集和数据的上报，咱们把数据的收集比作生产者，数据的上报比作消费者，是一个典型的生产生产模型。

生产生产模型在 JVM 过程外部通过队列 + 锁或者无锁的 Disruptor 来实现，在跨过程场景下通过 MQ（RocketMQ/kafka）进行处了解耦。

然而细化到具体业务场景来看，音讯的生产有诸多限度，包含：游戏维度的批量行为上报，行为上报的时效限度，细化到各个技术计划选型进行比照。

计划一

应用 RocketMQ 或者 Kafaka 等音讯队列来存储上报的音讯，然而生产侧须要思考在业务过程中依照游戏维度进行聚合，其中技术细节波及依照游戏维度进行拆分，在满足音讯时效性和批量性的前提下触发上报。在这种计划下消息中间件表演的角色实质上音讯的中转站，没有解决任何业务场景中提及的游戏维度拆分、批量性和时效性。

计划二

在计划一的根底上，寻求一种技术计划来解决游戏维度的音讯分组、批量生产、时效性。通过 Redis 的 list 构造来实现队列（进一步要求实现定长队列）来解决游戏维度的音讯分组；通过 Redis 的 list 反对的 Lrange 来实现批量生产；通过业务侧的多线程来解决时效问题，针对高频的游戏应用独自的线程池进行解决，上述两个伎俩可能保障生产速度大于生产速度。

计划比照

比照两种计划后决定应用 Redis 的实现了一个伪消息中间件：

1. 通过 List 对象实现定长队列来保留游戏维度的行为音讯（以游戏作为 key 的 List 对象来保留用户行为）；
2. 通过 List 来保留所有的存在行为数据的游戏列表；
3. 通过 Set 来进行去重判断来保障 2 中的 List 对象的唯一性。

整体的技术计划如下图所示：

生产过程

步骤一：游戏维度的某行为数据 PUSH 到游戏维度的队列当中。

步骤二：判断游戏是否在游戏的汇合 Set 中，如果在就间接返回，如果不在进行步骤三。

步骤三：往游戏列表中 PUSH 游戏。

生产过程

步骤一：从游戏对象的列表中循环取出一款游戏。

步骤二：通过步骤一获取的游戏对象去该游戏对象的行为数据队列中批量获取数据处理。

三、技术原理

在 Redis 的反对命令中，在 List 和 Set 的根底命令，联合 Lua 脚本来实现整个技术计划。

音讯数据层面，通过独自的 List 循环保护待生产的游戏维度的数据，每个游戏维度应用定长的 List 来保留音讯。

音讯生产过程中，通过联合 List 的 llen+lpop+rpush 来实现游戏维度的定长队列，保障队列的长度可控。

音讯生产过程中，通过联合 List 的 lrange+ltrim 来实现游戏维度的音讯的批量生产。

在整个执行的复杂度层面，须要保障工夫复杂度在 0(N)常量维度，保障工夫可控。

3.1 Lua 脚本

EVAL script numkeys key [key ...] arg [arg ...]
    工夫复杂度：取决于脚本自身的执行的工夫复杂度。> eval "return {KEYS[1],KEYS[2],ARGV[1],ARGV[2]}" 2 key1 key2 first second
1) "key1"
2) "key2"
3) "first"
4) "second"
 
Redis uses the same Lua interpreter to run all the commands.
Also Redis guarantees that a script is executed in an atomic way:
no other script or Redis command will be executed while a script is being executed.
This semantic is similar to the one of MULTI / EXEC.
From the point of view of all the other clients the effects of a script are either still not visible or already completed.

Redis 采纳雷同的 Lua 解释器去运行所有命令，咱们能够保障，脚本的执行是原子性的。作用就相似于加了 MULTI/EXEC。

• Lua 脚本内多个命令以原子性的形式执行，保障了命令执行的线程平安。
• Lua 脚本联合 List 命令实现定长队列，实现批量生产。
• Lua 脚本仅反对单个 key 的操作，不反对多 key 的操作。

3.2 List 对象

LLEN key
    计算 List 的长度
    工夫复杂度：O(1)。LPOP key [count]
    从 List 的左侧移除元素
    工夫复杂度：O(N)，N 为移除元素的个数。RPUSH key element [element ...]
    从 List 的右侧保留元素
    工夫复杂度：O(N)，N 为保留元素的个数。

• List 的根底命令包含计算 List 的长度，移除数据，增加数据，整体命令的复杂度都在 O(N)的常量工夫。
• 整合上述三个命令，咱们能保障实现固定长度的队列，通过判断队列长度是否达到定长联合新增队列元素和移除队列元素来实现。

LRANGE key start end
    工夫复杂度：O(S+N)，S 为偏移量 start，N 为指定区间内元素的数量。下标 (index) 参数 start 和 stop 都以 0 为底，也就是说，以 0 示意列表的第一个元素，以 1 示意列表的第二个元素，以此类推。你也能够应用正数下标，以 -1 示意列表的最初一个元素，-2 示意列表的倒数第二个元素，以此类推。LTRIM key start stop
    工夫复杂度：O(N) where N is the number of elements to be removed by the operation.
 
    修剪 (trim) 一个已存在的 list，这样 list 就会只蕴含指定范畴的指定元素。

• List 的根底命令包含批量返回数据和裁剪数据，整体命令的复杂度都在 O(N)的常量工夫。
• 整合上述两个命令，咱们可能批量生产数据并移除队列数据，通过 LRANGE 批量返回数据并通过 LTRIM 保留残余数据。

3.3 Set 对象

SADD key member [member ...]
    往 Set 汇合增加数据。工夫复杂度：O(1)。SISMEMBER key member
    判断 Set 汇合是否存在元素。工夫复杂度：O(1)。

四、技术利用

4.1 生产音讯

定义 LUA 脚本   
    CACHE_NPPA_EVENT_LUA =
        "local retVal = 0" +
        "local key = KEYS[1]" +
        "local num = tonumber(ARGV[1])" +
        "local val = ARGV[2]" +
        "local expire = tonumber(ARGV[3])" +
        "if (redis.call('llen', key) < num) then redis.call('rpush', key, val)" +
        "else redis.call('lpop', key) redis.call('rpush', key, val) retVal = 1 end" +
        "redis.call('expire', key, expire) return retVal";
 
 
执行 LUA 脚本
    String data = JSON.toJSONString(nppaBehavior);
    Long retVal = (Long)jedisClusterTemplate.eval(CACHE_NPPA_EVENT_LUA, 1, NPPA_PREFIX + nppaBehavior.getGamePackage(), String.valueOf(MAX_GAME_EVENT_PER_GAME), data, String.valueOf(NPPA_TTL_MINUTE * 60));
 
执行成果
    实现固长队列的数据存储并设置过期工夫

• 通过整合 llen+rpush+lpop 三个命令实现定长队列。
• 通过 lua 脚本保障上述命令的原子性执行。

• 整体的执行流程如上图所示，核心理念通过 lua 脚本的原子性保障了队列长度计算（llen）、队列数据移除（lpop）、队列数据保留（rpush)的原子性执行。

4.2 生产音讯

定义 LUA 脚本
    QUERY_NPPA_EVENT_LUA =
        "local data = {}" +
        "local key = KEYS[1]" +
        "local num = tonumber(ARGV[1])" +
        "data = redis.call('lrange', key, 0, num) redis.call('ltrim', key, num+1, -1) return data";
 
执行 LUA 脚本
    Integer batchSize = NppaConfigUtils.getInteger("nppa.report.batch.size", 1);
    Object result = jedisClusterTemplate.eval(QUERY_NPPA_EVENT_LUA, 1,NPPA_PREFIX + gamePackage, String.valueOf(batchSize));
 
执行成果
    取固定数量的对象，而后保留队列的残余的音讯对象。

• 通过整合 lrange+ltrim 两个命令实现音讯的批量生产。
• 通过 lua 脚本保障上述命令的原子性执行。

• 整体的执行流程如上图所示，核心理念通过 lua 脚本的原子性保障了数据获取（Lrange）和数据裁剪（Ltrim)的原子性执行。
• 整体的生产流程抉择 pull 模式，通过多线程循环轮询可生产的队列进行生产。与借助于 redis 的 pub/sub 的告诉机制实现生产流程的 push 模式相比，pull 模式老本更低成果更佳。

4.3 注意事项

• Redis 集群模式下，执行 Lua 脚本倡议传单 key，多 key 会报重定向谬误。
• 在不同的 Redis 版本下，Lua 脚本针对 null 的返回值解决不同，参考官网文档。
• 消费者的生产过程中通过循环遍历游戏列表，而后依据游戏去获取对应的音讯对象，然而不同的游戏对应的热度不同，所以在生产端咱们通过配置的形式为热门游戏独自开启生产线程进行生产，相当于针对不同游戏配置不同优先级的消费者。

五、线上成果

• 生产和生产的 QPS 约为 1w qps 左右，整体上报 QPS 通过批量上报后会远低于生产的音讯生产和生产的 QPS。
• 整体数据的应用游戏包名作为 key 进行存储，性能上不存在热点的问题。

六、实用场景

在形容完计划的原理和实现细节之后，进一步对实用的业务场景进行下总结。整体计划是基于 redis 的根本数据结构构建一个伪音讯队列，用以解决音讯的单个生产批量生产的场景，通过多 key 模式实现音讯队列的多 Topic 模式，重要的是可能借助于 redis 的原生能力在 O(N)的工夫复杂度实现批量生产。另外该计划也能够降级作为实现先进先出定长的日志队列。

七、总结

本文次要摸索在特定业务场景下通过 Redis 的原生命令实现类 MQ 的性能，翻新式的通过 Lua 脚本组合 Redis 的 List 的根底命令，实现了音讯的分组，音讯的定长队列，音讯的批量生产性能；整体解决方案在线上环境落地并安稳运行，为特定场景提供了一种通用的解决方案。