一种高效的总金额动态平衡的随机立减算法及实现

◆唐 真 周之敏

一种高效的总金额动态平衡的随机立减算法及实现

◆唐 真 周之敏

（中国银联股份有限公司 上海 201201）

本文就总金额动态平衡下的随机立减算法以及其实现进行分析，希望能够对其算法和实现途径有一个整体性的认识。

总金额动态平衡；随机立减；算法

1 算法背景分析

当前市场上的随机立减优惠活动，存在以下问题：

（1）优惠金额随机性太差，优惠金额区间分布不均匀，即用户的优惠金额方差太小，优惠金额太过集中于某些区间段，比如集中到1分到1元的小额优惠区间段或集中到9元到10元的大额优惠区间段。

（2）对优惠预算的控制不能满足预期。由于对每个参与活动的用户有着累计优惠次数和累计优惠金额的限制，以及优惠金额充满随机不确定性的特点，不好的随机立减算法将会导致活动结束时活动经费剩余过多或者大量超出预算。

（3）现有的随机立减算法不够高效、快速、存储空间利用率低、操作冗余。为了存储用户的历史优惠信息，现有的算法大部分使用了Redis中的2个键值对分别存储用户的累计优惠笔数和累计优惠金额，这就造成了存储和更新用户信息操作至少需要操作两次键值，降低了效率，浪费了存储空间。优惠活动的体验度取决于随机立减算法的高效性，若随机立减算法效率过低，将会影响用户对优惠活动的体验。

因此笔者针对随机立减优惠活动，提出一种高效的总金额动态平衡的随机立减算法解决以上问题。

2 最佳技术方案（实施举例）

本算法一共包含两个部分，第一部分是对redis优惠队列的初始化，第二部分是对redis优惠队列的操作。算法总体流程如图1。

接收用户请求前，在redis中初始化优惠队列、补偿队列、用户队列，初始化完成后，优惠队列中的优惠金额生成完毕，补偿队列与用户队列为空。

队列初始化完成后，开始接收用户请求，并根据用户的交易金额和历史优惠信息，获取优惠金额与补偿金额并更新用户的累积优惠信息，最终返回请求应答。

2.1 对redis优惠队列初始化算法的具体过程

设本次优惠活动指定的优惠总金额为N，指定的优惠总名额为M，redis的实例数量为R。

图1 算法总体流程图

（1）在本地应用中初始化3个存储优惠金额的优惠列表List1，List2，List3，后续会将3个列表中的优惠数据放入到redis中去。3个列表的总优惠总名额为M，优惠总额度为N。列表生成步骤如下：

首先，初始化优惠列表List1。List1存储了大量的优惠金额数据，其优惠名额至少占据了优惠活动的50%或优惠额度占据了优惠活动的5/6，并且这些优惠额度是均匀地落在每个优惠区间。用以解决了优惠金额随机性较差的问题。

其次，初始化优惠列表List2。List2中存储了少量的优惠金额全为1的优惠金额序列，该列表大小<=M/10并且列表总金额<=N/3000。生成List2的目的主要是为了防止一个用户享受X次优惠后，X+1次得到的优惠额度加上前X次享受的总优惠额度超过用户可以享受的优惠额度上限，这样可以很好的控制预算趋近于优惠活动指定的预算。

最后，初始化优惠列表List3。List3列表主要是为了补齐List1，List2生成后剩余的优惠金额与名额，同时为了保证随机性，规定List3中存储的随机优惠金额随机生成，且总额大小为（N-List1总金额-List2总金额），总名额大小为（M-List1总名额-List2总名额）。

（2）根据redis实例数量R，将List1，List2，List3中的本地优惠列表，放入每个redis实例的优惠队列中。令R1=（List1名额大小/R），R2=（List2名额大小/R），R3=（List3名额大小/R），R1，R2，R3分别表示每个redis实例的优惠队列要从List1、List2、List3中获取并存储的元素个数。

2.2 对redis优惠队列的操作算法步骤

第一步，将R个Redis实例与R个支付交易系统实例一一对应，按照1台机器1个redis实例+1个交易支付系统实例的方式部署应用与redis，每个支付系统实例初始时只访问本地的redis实例，尽可能减少网络开销，达到优惠活动的高效性。

第二步，用户使用浏览器、客户端APP（如云闪付APP，微信、支付宝）对交易进行支付。浏览器、客户端APP将带有用户标识的支付交易信息发送到交易支付系统。交易支付系统根据本次交易信息的金额，以及发起该交易的用户在此次活动中已经享受过的优惠金额和笔数判断用户是否具备优惠条件：交易金额大小是否达到优惠条件阈值transAtThreshold；用户享受的优惠累计次数是否已经超出优惠活动指定的优惠次数transNumLimit；用户享受的优惠累计金额是否已经达到优惠活动指定的优惠金额上限transAtLimit。

若交易金额transNumLimit或优惠累计金额>transAtLimit，则返回应答，流程结束

第三步，从本地应用中获取优惠活动标志变量stopped，判断优惠活动是否结束。初始时该标志置为false，表示优惠活动未结束，当且仅当所有redis实例中的优惠队列为空时，优惠活动结束，stopped置为true。若stopped为true，则返回应答，流程结束。

第四步，读取当前支付系统应用所连接的redis实例优惠队列中的优惠金额及补偿队列中的优惠金额。

这里的优惠队列指的是redis初始化时的优惠队列。初始时为了防止过多的跨网开销，应用读取本机redis实例上的优惠队列。

补偿队列存储了超出用户限定优惠金额的差额部分，即用户从优惠队列取得的优惠金额与累计享受的优惠金额之和减去优惠活动限定的每个用户的最大享受优惠金额的差额部分。使用补偿队列，可以将这些超出的优惠上限部分用于下一个用户享受优惠时使用，很好地将预算控制到优惠活动指定的总金额，补偿队列初始时为空。

若从优惠队列取出的优惠金额不为空，跳转至步骤5，否则表示该redis中已经不存在优惠名额，标记该redis实例不存在优惠名额，遍历redis集群，寻找其他优惠队列非空的redis实例。

第五步，为了记录用户在优惠活动中的累计消费金额和累计消费笔数，redis实例除了存储优惠队列和补偿队列信息，同时也存储了用户累计优惠笔数和累计优惠金额。在高并发情况下，同一用户的请求不能保证每次达到同一台机器上，因此需要对用户的标识做hash，一个用户的信息有且只能有一个redis实例存储。此算法中采用了对redis实例数取模的方法，将用户的累计优惠信息路由到指定的redis实例中存储。

相比于其他存储用户累计优惠信息的算法，此算法中不再使用两个键值来分别存储用户的累计优惠笔数和金额，而只使用一个key存储了这两个信息。其中key表示用户的id，value为“用户累计笔数”+“用户累计金额”的组合字符串，即value的前几位存储的是用户累计笔数，而后几位存储的是用户累计金额。redis提供的hincrby函数，可以用来计算用户的累计金额和累计笔数，该函数保证原子性的同时，还可以直接对字符串类型的数值进行操作。

第六步，根据5中累加后的优惠笔数金额结果，判断高位的笔数是否超出了优惠活动指定的笔数上限（transNumLimit）。若超出，则回退4中获取到的优惠金额和补偿金额，同时将步骤5中用户增加的金额笔数减去，返回应答流程，结束[2]。

第七步，判断用户享受的优惠金额是否超出transAtLimit。

3 结语

本文对一种高效的总金额动态平衡的随机立减算法及实现进行了探讨，对随机立减算法分析有一定的借鉴意义。

[1]张志雄，张静之，赵春锋.微信红包随机金额生成算法模拟及应用[J].教育教学论坛，2019（10）：51-53.

[2]孟开文，方珂玮.随机回报的3阶矩模型研究[J].重庆师范大学学报（自然科学版），2018（06）：70-74.