微信紅包實現原理猜想

以下內容來自QCon某高可用架構群聊天記錄整理背景：有某個朋友諮詢微信紅包的架構，在官方或非官方同學的解釋和討論中得出以下討論內容，在此期間有多個同學發紅包做現網演算法測試。

搶紅包過程

當有人在群組裡發了一個N人的紅包，總金額M元，後台大概發生的事情如下：

一、發紅包後台操作：

在數據庫中增加一條紅包記錄，儲存到CKV，設定過期時間；

在Cache（可能是騰訊內部kv資料庫，基於內存，有落地，有內核態網絡處理模組，以內核模組形式提供服務））中增加一條記錄，存儲搶紅包的人數N

二、搶紅包後台操作：

搶紅包分為搶和拆，搶操作在Cache層完成，透過原子減操作進行紅包數遞減，到0 就表示搶光了，最終實際進入後台拆操作的量不大，透過操作的分離將無效請求直接擋在Cache層外面。這裡的原子減操作並不是真正意義上的原子減操作，是 其Cache層提供的CAS，透過比較版本號不斷嘗試，存在一定程度上的衝突，衝突的用戶會放行，讓其進入下一步拆的操作，這也解釋了為啥有用戶搶到了拆     開發現領完了的狀況。

拆紅包在資料庫完成，透過資料庫的事務操作累加已經領取的數量和金額，插入一條領取     流水，入帳為非同步操作，這也解釋了為啥在春節期間紅包領取後在餘額中看不到。拆的時候會即時計算金額，其金額為1分到剩餘平均值2倍之間隨機數，一個總金     額為M元的紅包，最大的紅包為 M * 2 /N（且不會超過M），拆了紅包後會更新剩餘金額和個數。財付通以20萬筆每秒入帳準備，實際只到8萬每秒。

FAQ

既然在搶的時候有原子減了就不應該出現搶到了拆開沒有的情況？
    這裡的原子減並不是真正意義上的原子操作，是Cache層提供的CAS，透過比較版本號不斷嘗試。

cache和db掛了怎麼辦？
    主備 +對帳

有沒有紅包個數沒了，但餘額還有狀況？
    沒有，程式最後會有一個take all操作以及一個非同步對帳保障。

為什麼要分離搶和拆？

總思路是設定多層過濾網，層層篩選，層層減少流量和壓力。這個設計最初是因為搶操作是業務層，拆是入帳操作，一個操作太重了，中斷率高。     從介面層面看，第一個介面純快取操作，搞壓能力強，一個簡單查詢Cache擋住了絕大部分用戶，做了第一道篩選，所以大部分人會看到已經搶完了的提示。

搶到紅包後再發紅包或是提現，這裡有什麼策略嗎？
    大額優先入帳策略

有沒有從數據上證明每個紅包的機率是不是均等？
    不是絕對均等，就是一個簡單的拍腦袋演算法。

拍腦袋演算法，會不會出現兩個最佳？
    會出現金額一樣的，但是手氣最佳只有一個，先搶到的那個最佳。

發紅包人的錢會不會凍結？
    是直接即時扣掉，不是凍結。

採用即時算出金額是出於什麼考慮？
    即時效率更高，預算才效率低。預算還要佔額外儲存。因為紅包只佔一筆記錄而且有效期限就幾天，所以不需要太多空間。就算壓力大時，水平擴展機器是。

測試二：知乎使用者「馬景銠」的實驗：

這裡給出一份100樣本的調查抽樣樣本數據，並提出自己的猜測。

1. 錢包錢數滿足截尾常態隨機數分佈。大致為在截尾常態分佈中取隨機數，並用其求和數除以總價值，得到修正因子，再用修正因子乘上所有的隨機數，得到紅包價值。

這種分佈意味著：低於平均值的紅包多，但是離平均值不遠；高於平均值的紅包少，但是遠大於平均值的紅包偏多。

圖1. 錢包價值與其頻率分佈直方圖及其正態擬合

但看分佈直方圖並不能推出它符合正態分佈，但是考慮到程序的簡潔性和隨機數的合理性，這是最合乎情理的一種猜測。

2. 越是後面的錢包，價值普遍更高

圖2. 錢包序列數與其價值關係曲線

從圖2的線性擬合紅線可以看到，錢包價值的整體變化趨勢是在慢慢增大，其變化範圍大約是一個綠色虛線上下界劃出的「通道」。 (曲線可以被圍在這麼一個正合乎常規的「通道」中，也從側面反映了規律1的合理性，說明了並不是均勻分佈的隨機數)

從另一個平均數的圖中也可以看出這一規律。

圖3. 平均數隨序列數的變化曲線

在樣本中，1000價值的錢包被分成100份，均值為10。然而在圖3我們可以看到在最後一個錢包之前，平均數一直低於10，這就說明了一開始的錢包價值偏低，一直被後期的錢包價值拉著往上走，後期的錢包價值更高。

3. 當然平均數的圖還可以透露出另一個規律，那就是最後的那一個人往往容易走運抽得比較多。因為最後那一個人是錢包剩下多少就拿多少的，而之前所有人的平均數都低於10，所以至少保證了最後一個人會高於平均值。在本樣本中，98號錢包抽到35，最後一份錢包抽到46。

綜上，根據樣本猜測：

1. 抽到的錢大多時候跟別人一樣少，但一旦一多，就容易多很多。

2. 越是抽後面的錢包，錢越容易多。

3. 最後一個人往往容易撞大運。