◆唐 真 周之敏

一種高效的總金額動態(tài)平衡的隨機立減算法及實現(xiàn)

◆唐 真 周之敏

（中國銀聯(lián)股份有限公司 上海 201201）

本文就總金額動態(tài)平衡下的隨機立減算法以及其實現(xiàn)進行分析，希望能夠?qū)ζ渌惴ê蛯崿F(xiàn)途徑有一個整體性的認識。

總金額動態(tài)平衡；隨機立減；算法

1 算法背景分析

當前市場上的隨機立減優(yōu)惠活動，存在以下問題：

（1）優(yōu)惠金額隨機性太差，優(yōu)惠金額區(qū)間分布不均勻，即用戶的優(yōu)惠金額方差太小，優(yōu)惠金額太過集中于某些區(qū)間段，比如集中到1分到1元的小額優(yōu)惠區(qū)間段或集中到9元到10元的大額優(yōu)惠區(qū)間段。

（2）對優(yōu)惠預算的控制不能滿足預期。由于對每個參與活動的用戶有著累計優(yōu)惠次數(shù)和累計優(yōu)惠金額的限制，以及優(yōu)惠金額充滿隨機不確定性的特點，不好的隨機立減算法將會導致活動結(jié)束時活動經(jīng)費剩余過多或者大量超出預算。

（3）現(xiàn)有的隨機立減算法不夠高效、快速、存儲空間利用率低、操作冗余。為了存儲用戶的歷史優(yōu)惠信息，現(xiàn)有的算法大部分使用了Redis中的2個鍵值對分別存儲用戶的累計優(yōu)惠筆數(shù)和累計優(yōu)惠金額，這就造成了存儲和更新用戶信息操作至少需要操作兩次鍵值，降低了效率，浪費了存儲空間。優(yōu)惠活動的體驗度取決于隨機立減算法的高效性，若隨機立減算法效率過低，將會影響用戶對優(yōu)惠活動的體驗。

因此筆者針對隨機立減優(yōu)惠活動，提出一種高效的總金額動態(tài)平衡的隨機立減算法解決以上問題。

2 最佳技術(shù)方案（實施舉例）

本算法一共包含兩個部分，第一部分是對redis優(yōu)惠隊列的初始化，第二部分是對redis優(yōu)惠隊列的操作。算法總體流程如圖1。

接收用戶請求前，在redis中初始化優(yōu)惠隊列、補償隊列、用戶隊列，初始化完成后，優(yōu)惠隊列中的優(yōu)惠金額生成完畢，補償隊列與用戶隊列為空。

隊列初始化完成后，開始接收用戶請求，并根據(jù)用戶的交易金額和歷史優(yōu)惠信息，獲取優(yōu)惠金額與補償金額并更新用戶的累積優(yōu)惠信息，最終返回請求應答。

2.1 對redis優(yōu)惠隊列初始化算法的具體過程

設(shè)本次優(yōu)惠活動指定的優(yōu)惠總金額為N，指定的優(yōu)惠總名額為M，redis的實例數(shù)量為R。

圖1 算法總體流程圖

（1）在本地應用中初始化3個存儲優(yōu)惠金額的優(yōu)惠列表List1，List2，List3，后續(xù)會將3個列表中的優(yōu)惠數(shù)據(jù)放入到redis中去。3個列表的總優(yōu)惠總名額為M，優(yōu)惠總額度為N。列表生成步驟如下：

首先，初始化優(yōu)惠列表List1。List1存儲了大量的優(yōu)惠金額數(shù)據(jù)，其優(yōu)惠名額至少占據(jù)了優(yōu)惠活動的50%或優(yōu)惠額度占據(jù)了優(yōu)惠活動的5/6，并且這些優(yōu)惠額度是均勻地落在每個優(yōu)惠區(qū)間。用以解決了優(yōu)惠金額隨機性較差的問題。

其次，初始化優(yōu)惠列表List2。List2中存儲了少量的優(yōu)惠金額全為1的優(yōu)惠金額序列，該列表大小<=M/10并且列表總金額<=N/3000。生成List2的目的主要是為了防止一個用戶享受X次優(yōu)惠后，X+1次得到的優(yōu)惠額度加上前X次享受的總優(yōu)惠額度超過用戶可以享受的優(yōu)惠額度上限，這樣可以很好的控制預算趨近于優(yōu)惠活動指定的預算。

最后，初始化優(yōu)惠列表List3。List3列表主要是為了補齊List1，List2生成后剩余的優(yōu)惠金額與名額，同時為了保證隨機性，規(guī)定List3中存儲的隨機優(yōu)惠金額隨機生成，且總額大小為（N-List1總金額-List2總金額），總名額大小為（M-List1總名額-List2總名額）。

（2）根據(jù)redis實例數(shù)量R，將List1，List2，List3中的本地優(yōu)惠列表，放入每個redis實例的優(yōu)惠隊列中。令R1=（List1名額大小/R），R2=（List2名額大小/R），R3=（List3名額大小/R），R1，R2，R3分別表示每個redis實例的優(yōu)惠隊列要從List1、List2、List3中獲取并存儲的元素個數(shù)。

2.2 對redis優(yōu)惠隊列的操作算法步驟

第一步，將R個Redis實例與R個支付交易系統(tǒng)實例一一對應，按照1臺機器1個redis實例+1個交易支付系統(tǒng)實例的方式部署應用與redis，每個支付系統(tǒng)實例初始時只訪問本地的redis實例，盡可能減少網(wǎng)絡(luò)開銷，達到優(yōu)惠活動的高效性。

第二步，用戶使用瀏覽器、客戶端APP（如云閃付APP，微信、支付寶）對交易進行支付。瀏覽器、客戶端APP將帶有用戶標識的支付交易信息發(fā)送到交易支付系統(tǒng)。交易支付系統(tǒng)根據(jù)本次交易信息的金額，以及發(fā)起該交易的用戶在此次活動中已經(jīng)享受過的優(yōu)惠金額和筆數(shù)判斷用戶是否具備優(yōu)惠條件：交易金額大小是否達到優(yōu)惠條件閾值transAtThreshold；用戶享受的優(yōu)惠累計次數(shù)是否已經(jīng)超出優(yōu)惠活動指定的優(yōu)惠次數(shù)transNumLimit；用戶享受的優(yōu)惠累計金額是否已經(jīng)達到優(yōu)惠活動指定的優(yōu)惠金額上限transAtLimit。

若交易金額transNumLimit或優(yōu)惠累計金額>transAtLimit，則返回應答，流程結(jié)束

第三步，從本地應用中獲取優(yōu)惠活動標志變量stopped，判斷優(yōu)惠活動是否結(jié)束。初始時該標志置為false，表示優(yōu)惠活動未結(jié)束，當且僅當所有redis實例中的優(yōu)惠隊列為空時，優(yōu)惠活動結(jié)束，stopped置為true。若stopped為true，則返回應答，流程結(jié)束。

第四步，讀取當前支付系統(tǒng)應用所連接的redis實例優(yōu)惠隊列中的優(yōu)惠金額及補償隊列中的優(yōu)惠金額。

這里的優(yōu)惠隊列指的是redis初始化時的優(yōu)惠隊列。初始時為了防止過多的跨網(wǎng)開銷，應用讀取本機redis實例上的優(yōu)惠隊列。

補償隊列存儲了超出用戶限定優(yōu)惠金額的差額部分，即用戶從優(yōu)惠隊列取得的優(yōu)惠金額與累計享受的優(yōu)惠金額之和減去優(yōu)惠活動限定的每個用戶的最大享受優(yōu)惠金額的差額部分。使用補償隊列，可以將這些超出的優(yōu)惠上限部分用于下一個用戶享受優(yōu)惠時使用，很好地將預算控制到優(yōu)惠活動指定的總金額，補償隊列初始時為空。

若從優(yōu)惠隊列取出的優(yōu)惠金額不為空，跳轉(zhuǎn)至步驟5，否則表示該redis中已經(jīng)不存在優(yōu)惠名額，標記該redis實例不存在優(yōu)惠名額，遍歷redis集群，尋找其他優(yōu)惠隊列非空的redis實例。

第五步，為了記錄用戶在優(yōu)惠活動中的累計消費金額和累計消費筆數(shù)，redis實例除了存儲優(yōu)惠隊列和補償隊列信息，同時也存儲了用戶累計優(yōu)惠筆數(shù)和累計優(yōu)惠金額。在高并發(fā)情況下，同一用戶的請求不能保證每次達到同一臺機器上，因此需要對用戶的標識做hash，一個用戶的信息有且只能有一個redis實例存儲。此算法中采用了對redis實例數(shù)取模的方法，將用戶的累計優(yōu)惠信息路由到指定的redis實例中存儲。

相比于其他存儲用戶累計優(yōu)惠信息的算法，此算法中不再使用兩個鍵值來分別存儲用戶的累計優(yōu)惠筆數(shù)和金額，而只使用一個key存儲了這兩個信息。其中key表示用戶的id，value為“用戶累計筆數(shù)”+“用戶累計金額”的組合字符串，即value的前幾位存儲的是用戶累計筆數(shù)，而后幾位存儲的是用戶累計金額。redis提供的hincrby函數(shù)，可以用來計算用戶的累計金額和累計筆數(shù)，該函數(shù)保證原子性的同時，還可以直接對字符串類型的數(shù)值進行操作。

第六步，根據(jù)5中累加后的優(yōu)惠筆數(shù)金額結(jié)果，判斷高位的筆數(shù)是否超出了優(yōu)惠活動指定的筆數(shù)上限（transNumLimit）。若超出，則回退4中獲取到的優(yōu)惠金額和補償金額，同時將步驟5中用戶增加的金額筆數(shù)減去，返回應答流程，結(jié)束[2]。

第七步，判斷用戶享受的優(yōu)惠金額是否超出transAtLimit。

3 結(jié)語

本文對一種高效的總金額動態(tài)平衡的隨機立減算法及實現(xiàn)進行了探討，對隨機立減算法分析有一定的借鑒意義。

[1]張志雄，張靜之，趙春鋒.微信紅包隨機金額生成算法模擬及應用[J].教育教學論壇，2019（10）：51-53.

[2]孟開文，方珂瑋.隨機回報的3階矩模型研究[J].重慶師范大學學報（自然科學版），2018（06）：70-74.