一种高并发下最终一致性算法及实现

◆李岩 唐真

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

1 构想的来源

分布式系统为应答高并发请求的压力，需要保证高效性能的同时，也要具备一致性的特点。为了解决性能问题，目前大部分分布式系统采用了redis 等内存数据库存储数据，然而这也为系统的一致性带来了问题：

（1）分布式应用存在宕机可能，redis 作为分布式内存数据库，由于不存在严格的事务特性，应用宕机后，会出现数据状态不一致的可能。

（2）使用lua 脚本操作redis 保证了批量操作的原子性，然而一个lua 脚本无法对多个redis 实例同时操作，不能满足分布式应用的场景。

（3）使用了Mysql 等关系型数据库的应用可以利用数据库的事务特性，避免数据不一致的问题。对于redis 这种内存数据库，则需要自己编码实现回退步骤，但是这种回退方式只能适用于程序运行过程中出现预期异常或错误且被捕获的情况下。对于宕机这类问题，无法做到回退，而且回退过程中也可能出现失败风险，造成数据不一致。

2 最佳技术方案

本算法已应用到随机立减优惠活动中，一共包含三个部分，第一部分是对redis 优惠队列的初始化，第二部分是对redis 优惠队列的操作。第三个部分是通过定时任务执行回退操作。对redis 优惠队列初始化算法的具体过程如下：设本次优惠活动指定的优惠总金额为N，指定的优惠总名额为M，redis 的实例数量为R。

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

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

使用随机函数（如Java 中的Random.nextⅠnt（））生成一个大小范围在（1，100]区间内的数字A。

利用生成的随机数字A，为10 个区间分别生成两个随机优惠金额：（0，100]内的两个随机优惠金额大小为A，100-A；（100，200]内的两个随机优惠金额大小为A+100，200-A；（200，300]内的两个随机优惠金额大小为A+200，300-A；（300，400]内的两个随机优惠金额大小为A+300，400-A；（400，500]内的两个随机优惠金额大小为A+400，500-A；（500，600]内的两个随机优惠金额大小为A+500，600-A；（600，700]内的两个随机优惠金额大小为A+600，700-A；（700，800]内的两个随机优惠金额大小为A+700，800-A；（800，900]内的两个随机优惠金额大小为A+800，900-A；（900，1000]内的两个随机优惠金额大小为A+900，1000-A；

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

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

①从List1 中取出R1 个元素，从List3 中取出R3 个元素，将这些元素以随机的顺序放入redis 集群中的一个redis 实例的优惠队列List 中。

The aim of this study was to evaluate the compliance of the staff of an Academic Hospital with a CRC screening program using FIT.

②从List2 中取出R2 个元素，放入2.1 中刚放入的List 的尾部。List2 中的元素一定要在List1 和List3 元素的后面，这是为了尽可能防止一个用户享受X 次优惠后，X+1 次得到的优惠额度加上前X 次享受的总优惠额度超过用户可以享受的优惠额度上限。

③重复2.1 和2.2 中的步骤，直到每个redis 实例的优惠队列中都有优惠金额，redis 优惠队列初始化算法部分结束。

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

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

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

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

lua 脚本具有原子性以及保持系统一致性，将修改redis 的操作与记录这些修改操作的步骤放入到lua 脚本，可以保证即使应用宕机，也不会出现执行了操作而没有记录操作的情况。所以使用lua 脚本执行读取优惠队列和补偿队列的操作，步骤如下：（1）生成UUⅠD，以此为key 值存入到redis 中，value 设置为当前时间戳；（2）获取优惠金额与补偿金额；（3）判断是否获取到优惠金额。

（5）使用lua 脚本更新用户优惠信息，并记录更新信息到redis中。

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

（6）根据5 中累加后的优惠笔数金额结果，判断高位的笔数是否超出了优惠活动指定的笔数上限（transNumLimit），若超出：

①执行金额回退lua 脚本：回退4 中获取到的优惠金额和补偿金额。记录回退步骤，key 为UUⅠD+“returnMoney”，value 为优惠金额+“：”+补偿金额，金额回退lua 脚本执行结束。

②执行用户优惠信息回退lua 脚本：回退步骤5 中用户增加的金额笔数。记录回退步骤，key 为UUⅠD+“：”+“returnUser”+用户Ⅰd，value 为用户回退的优惠金额与笔数。更改UUⅠD 的value 为-1，表示所有流程结束，等待定时任务删除所有此次UUⅠD 开头的key，返回应答，结束。

（7）判断用户享受的优惠金额是否超出transAtLimit。

若未超出，更改UUⅠD的value为-1，表示所有流程结束，等待定时任务删除所有此次UUⅠD开头的key，返回应答，结束。

若超出，计算transAtLimit 与步骤5 中更新前的用户累计金额之间的差值transAtExtra，并按照以下场景做回退操作。

若transAtExtra>=从优惠队列中取出的金额，执行回退lua 脚本：

记录操作步骤，key 为UUⅠD+“returnCompensate”，value 为回退的补偿金额，大小为（优惠队列金额+补偿队列金额-transAtExtra），等待定时任务回退这笔补偿金额到补偿队列，脚本执行结束。

（8）对用户优惠信息的更新做回退，执行lua 脚本。

回退redis 中用户更新的优惠信息，因为回退补偿队列意味着将步骤5 中多增加的优惠金额减去，这里不需要减去优惠笔数，是因为用户占用了优惠名额，所以只对优惠金额进行更改，只需要减去步骤5 更新后的优惠金额与transAtlimit 的差值即可，保证用户最终享受到的总优惠金额不超过上限。

记录操作步骤，key 为key 为UUⅠD+“：”+“returnUser”+用户Ⅰd，value 为用户回退的金额。

更改UUⅠD 的value 为-1，表示所有流程结束，等待定时任务删除所有此次UUⅠD 开头的key，返回应答，结束。

定时任务处理流程主要是清理已经完成任务的key 和回退超时任务的key，保证数据的一致性。对于定时任务的执行间隔时间和任务超时时间，一般设置为5 秒，这是因为在高并发分布式系统中，用户对系统的响应要求是5 秒以内，但是系统的响应时间需要根据具体场景决定，所以根据不同的场景，用户可以自定义定时任务的执行间隔时间和任务超时时间。