微信紅包金額分配的算法
雖然春節已經過去一段時間，但不少微信群里面依舊樂此不疲的在玩發紅包活動，用戶自發的將最初的一個春節拜年的場景功能慢慢演化成一個長尾功能。
用戶在微信中搶紅包時分成搶包和拆包兩個操作。搶包決定紅包是否還有剩余金額，但如果行動不夠迅速，在拆包階段可能紅包已經被其他用戶搶走的情況。
紅包的金額是在什么時候算？ 據某架構群騰訊財付通專家反饋，紅包的金額是拆的時候實時計算，而不是預先分配，實時計算基于內存，不需要額外存儲空間，并且實時計算效率也很高。每次拆紅包時，系統取0.01到剩余平均值*2之間作為紅包的金額。
為了保證每次操作的原子性，拆包過程中使用了CAS，確保每次只有一個并發用戶拆包成功。拆包CAS失敗的用戶可以由系統自動進行重試。但也有可能在重試過程中被別的用戶搶得先機而空手而歸，因此嚴格意義拆包的調用也未能保證用戶先到先得。
基于上面的原因，當時在群中提到這種算法有些復雜，微信紅包為了減少存儲，每次進行了一個理解稍復雜的實時計算。對比大部分架構師想到的預分配金額 的做法，預先分配金額需要將金額保存在一個內存隊列中，如果紅包的份額較多，則需要較大的存儲空間。而微信紅包僅保存 count:balance 這樣2個數字。count指還剩幾個人可以搶，balance只還剩下的金額。
但是預分配金額也并不是非得需要額外存儲。比如利用隨機算法，在種子相同的情況下，隨機數實際上返回的隨機序列也是固定的。如以下Python代碼，對于給定的seed 1024，每次執行返回的結果都是相同的。
>>> import random
>>> random.seed(1024)
>>> random.randint(1,100)
80
>>> random.randint(1,100)
49
>>> random.randint(1,100)
39
>>> random.randint(1,100)
83
>>> random.randint(1,100)
88
因此預分配金額也只需要額外存儲一個種子，或利用一些紅包id做加密變換做seed達到零存儲。而在發放紅包時候，無需進行CAS操作，而只需要對剩余紅包count做一個DECR操作。當count
每個人分配的金額是：total * random(n) / random_total，不需要重復計算。
random(1)..random(n)不需要保存，因為對于給定的seed，random(1)到random(n)返回是固定的。
以上算法評論與對比，與Tim所在雇主的紅包算法無關，特此聲明。
部分細節下面列表已做說明，未做詳細闡述。
Reference:
1、微信紅包的架構設計簡介
2、網友周航老師基于聊天記錄整理的微信紅包架構圖（點擊查看大圖）
3、微信紅包實現原理
對于上文中提到的架構群感興趣的朋友可以關注Tim公眾號“TimYang_net”后回復“arch”獲取進群方式。
Similar Posts: