微信紅包實現原理猜想

阿神
發布: 2017-02-10 14:31:16
原創
2056 人瀏覽過

以下內容來自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. 最後一個人往往容易撞大運。

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板