一種高并發下最終一致性算法及實現

◆李巖 唐真

（中國銀聯股份有限公司 上海 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 秒以內，但是系統的響應時間需要根據具體場景決定，所以根據不同的場景，用戶可以自定義定時任務的執行間隔時間和任務超時時間。