◆李巖 唐真

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

1 構(gòu)想的來源

分布式系統(tǒng)為應(yīng)答高并發(fā)請求的壓力，需要保證高效性能的同時，也要具備一致性的特點(diǎn)。為了解決性能問題，目前大部分分布式系統(tǒng)采用了redis 等內(nèi)存數(shù)據(jù)庫存儲數(shù)據(jù)，然而這也為系統(tǒng)的一致性帶來了問題：

（1）分布式應(yīng)用存在宕機(jī)可能，redis 作為分布式內(nèi)存數(shù)據(jù)庫，由于不存在嚴(yán)格的事務(wù)特性，應(yīng)用宕機(jī)后，會出現(xiàn)數(shù)據(jù)狀態(tài)不一致的可能。

（2）使用lua 腳本操作redis 保證了批量操作的原子性，然而一個lua 腳本無法對多個redis 實(shí)例同時操作，不能滿足分布式應(yīng)用的場景。

（3）使用了Mysql 等關(guān)系型數(shù)據(jù)庫的應(yīng)用可以利用數(shù)據(jù)庫的事務(wù)特性，避免數(shù)據(jù)不一致的問題。對于redis 這種內(nèi)存數(shù)據(jù)庫，則需要自己編碼實(shí)現(xiàn)回退步驟，但是這種回退方式只能適用于程序運(yùn)行過程中出現(xiàn)預(yù)期異?；蝈e誤且被捕獲的情況下。對于宕機(jī)這類問題，無法做到回退，而且回退過程中也可能出現(xiàn)失敗風(fēng)險(xiǎn)，造成數(shù)據(jù)不一致。

2 最佳技術(shù)方案

本算法已應(yīng)用到隨機(jī)立減優(yōu)惠活動中，一共包含三個部分，第一部分是對redis 優(yōu)惠隊(duì)列的初始化，第二部分是對redis 優(yōu)惠隊(duì)列的操作。第三個部分是通過定時任務(wù)執(zhí)行回退操作。對redis 優(yōu)惠隊(duì)列初始化算法的具體過程如下：設(shè)本次優(yōu)惠活動指定的優(yōu)惠總金額為N，指定的優(yōu)惠總名額為M，redis 的實(shí)例數(shù)量為R。

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

①初始化優(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)惠金額隨機(jī)性較差的問題。其生成步驟如下：

使用隨機(jī)函數(shù)（如Java 中的Random.nextⅠnt（））生成一個大小范圍在（1，100]區(qū)間內(nèi)的數(shù)字A。

利用生成的隨機(jī)數(shù)字A，為10 個區(qū)間分別生成兩個隨機(jī)優(yōu)惠金額：（0，100]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A，100-A；（100，200]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+100，200-A；（200，300]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+200，300-A；（300，400]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+300，400-A；（400，500]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+400，500-A；（500，600]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+500，600-A；（600，700]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+600，700-A；（700，800]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+700，800-A；（800，900]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+800，900-A；（900，1000]內(nèi)的兩個隨機(jī)優(yōu)惠金額大小為A+900，1000-A；

②初始化優(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ù)算趨近于優(yōu)惠活動指定的預(yù)算。

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

①從List1 中取出R1 個元素，從List3 中取出R3 個元素，將這些元素以隨機(jī)的順序放入redis 集群中的一個redis 實(shí)例的優(yōu)惠隊(duì)列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 次優(yōu)惠后，X+1 次得到的優(yōu)惠額度加上前X 次享受的總優(yōu)惠額度超過用戶可以享受的優(yōu)惠額度上限。

③重復(fù)2.1 和2.2 中的步驟，直到每個redis 實(shí)例的優(yōu)惠隊(duì)列中都有優(yōu)惠金額，redis 優(yōu)惠隊(duì)列初始化算法部分結(jié)束。

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

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

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

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

lua 腳本具有原子性以及保持系統(tǒng)一致性，將修改redis 的操作與記錄這些修改操作的步驟放入到lua 腳本，可以保證即使應(yīng)用宕機(jī)，也不會出現(xiàn)執(zhí)行了操作而沒有記錄操作的情況。所以使用lua 腳本執(zhí)行讀取優(yōu)惠隊(duì)列和補(bǔ)償隊(duì)列的操作，步驟如下：（1）生成UUⅠD，以此為key 值存入到redis 中，value 設(shè)置為當(dāng)前時間戳；（2）獲取優(yōu)惠金額與補(bǔ)償金額；（3）判斷是否獲取到優(yōu)惠金額。

（5）使用lua 腳本更新用戶優(yōu)惠信息，并記錄更新信息到redis中。

相比于其他存儲用戶累計(jì)優(yōu)惠信息的算法，此算法中不再使用兩個鍵值來分別存儲用戶的累計(jì)優(yōu)惠筆數(shù)和金額，而只使用一個key存儲了這兩個信息。其中key 表示用戶的id，value 為“用戶累計(jì)筆數(shù)”+“用戶累計(jì)金額”的組合字符串，即value 的前幾位存儲的是用戶累計(jì)筆數(shù)，而后幾位存儲的是用戶累計(jì)金額。redis 提供的hincrby 函數(shù)，可以用來計(jì)算用戶的累計(jì)金額和累計(jì)筆數(shù)，該函數(shù)保證原子性的同時，還可以直接對字符串類型的數(shù)值進(jìn)行操作。所以根據(jù)步驟4中所讀取到的優(yōu)惠金額和補(bǔ)償金額，執(zhí)行更新用戶優(yōu)惠信息lua腳本。

（6）根據(jù)5 中累加后的優(yōu)惠筆數(shù)金額結(jié)果，判斷高位的筆數(shù)是否超出了優(yōu)惠活動指定的筆數(shù)上限（transNumLimit），若超出：

①執(zhí)行金額回退lua 腳本：回退4 中獲取到的優(yōu)惠金額和補(bǔ)償金額。記錄回退步驟，key 為UUⅠD+“returnMoney”，value 為優(yōu)惠金額+“：”+補(bǔ)償金額，金額回退lua 腳本執(zhí)行結(jié)束。

②執(zhí)行用戶優(yōu)惠信息回退lua 腳本：回退步驟5 中用戶增加的金額筆數(shù)。記錄回退步驟，key 為UUⅠD+“：”+“returnUser”+用戶Ⅰd，value 為用戶回退的優(yōu)惠金額與筆數(shù)。更改UUⅠD 的value 為-1，表示所有流程結(jié)束，等待定時任務(wù)刪除所有此次UUⅠD 開頭的key，返回應(yīng)答，結(jié)束。

（7）判斷用戶享受的優(yōu)惠金額是否超出transAtLimit。

若未超出，更改UUⅠD的value為-1，表示所有流程結(jié)束，等待定時任務(wù)刪除所有此次UUⅠD開頭的key，返回應(yīng)答，結(jié)束。

若超出，計(jì)算transAtLimit 與步驟5 中更新前的用戶累計(jì)金額之間的差值transAtExtra，并按照以下場景做回退操作。

若transAtExtra>=從優(yōu)惠隊(duì)列中取出的金額，執(zhí)行回退lua 腳本：

記錄操作步驟，key 為UUⅠD+“returnCompensate”，value 為回退的補(bǔ)償金額，大小為（優(yōu)惠隊(duì)列金額+補(bǔ)償隊(duì)列金額-transAtExtra），等待定時任務(wù)回退這筆補(bǔ)償金額到補(bǔ)償隊(duì)列，腳本執(zhí)行結(jié)束。

（8）對用戶優(yōu)惠信息的更新做回退，執(zhí)行l(wèi)ua 腳本。

回退redis 中用戶更新的優(yōu)惠信息，因?yàn)榛赝搜a(bǔ)償隊(duì)列意味著將步驟5 中多增加的優(yōu)惠金額減去，這里不需要減去優(yōu)惠筆數(shù)，是因?yàn)橛脩粽加昧藘?yōu)惠名額，所以只對優(yōu)惠金額進(jìn)行更改，只需要減去步驟5 更新后的優(yōu)惠金額與transAtlimit 的差值即可，保證用戶最終享受到的總優(yōu)惠金額不超過上限。

記錄操作步驟，key 為key 為UUⅠD+“：”+“returnUser”+用戶Ⅰd，value 為用戶回退的金額。

更改UUⅠD 的value 為-1，表示所有流程結(jié)束，等待定時任務(wù)刪除所有此次UUⅠD 開頭的key，返回應(yīng)答，結(jié)束。

定時任務(wù)處理流程主要是清理已經(jīng)完成任務(wù)的key 和回退超時任務(wù)的key，保證數(shù)據(jù)的一致性。對于定時任務(wù)的執(zhí)行間隔時間和任務(wù)超時時間，一般設(shè)置為5 秒，這是因?yàn)樵诟卟l(fā)分布式系統(tǒng)中，用戶對系統(tǒng)的響應(yīng)要求是5 秒以內(nèi)，但是系統(tǒng)的響應(yīng)時間需要根據(jù)具體場景決定，所以根據(jù)不同的場景，用戶可以自定義定時任務(wù)的執(zhí)行間隔時間和任務(wù)超時時間。