◆唐 真 周之敏

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

◆唐 真 周之敏

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

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

總金額動(dòng)態(tài)平衡；隨機(jī)立減；算法

1 算法背景分析

當(dāng)前市場(chǎng)上的隨機(jī)立減優(yōu)惠活動(dòng)，存在以下問(wèn)題：

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

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

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

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

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

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

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

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

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

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

圖1 算法總體流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

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

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