本文內容編寫時，參考了網上的資料，詳見“參考資料”部分，感謝分享者。
1、引言
這個系列文章已經整理了10篇，但都沒有涉及到具體的紅包算法實現，主要有以下兩方面原因。
一方面是各社交/IM產品中的紅包功能同質化嚴重，紅包算法的“可玩性”便是“核心競爭力所在”，這是同質化功能的差異化競爭思路，不會隨便公開。
另一方面，市場上還存在各種搶紅包插件這類灰產存在，一旦公開這些算法，很可能又被這幫插件開發者們搞出什么幺蛾子。
所以，這樣的情況下，如果要做社交/IM產品中的紅包功能，紅包隨便算法該怎么實現，基本上只能自已琢磨，很難找到大廠算法直接套用。
本著即時通訊網一貫的im知識傳播精神，我收集整理并參考了大量的網上資料，綜合了比較靠譜的信息來源，便有了本文。本文根據有限的資料，分享了微信紅包隨機算法實現中的一些技術要點，并整理了兩種比較靠譜的紅包算法實現思路（含可運行的實現代碼），希望能給你的紅包算法開發帶來啟發。
申明：本文資料整理自網絡，僅供學習研究之用，如有不妥，請通知Jack Jiang。
學習交流：
- 移動端IM開發入門文章：《新手入門一篇就夠：從零開發移動端IM》
- 開源IM框架源碼：https://github.com/JackJiang2011/MobileIMSDK
本文已同步發布于“即時通訊技術圈”公眾號。
2、系列文章
《社交軟件紅包技術解密(一)：全面解密QQ紅包技術方案——架構、技術實現等》
《社交軟件紅包技術解密(二)：解密微信搖一搖紅包從0到1的技術演進》
《社交軟件紅包技術解密(三)：微信搖一搖紅包雨背后的技術細節》
《社交軟件紅包技術解密(四)：微信紅包系統是如何應對高并發的》
《社交軟件紅包技術解密(五)：微信紅包系統是如何實現高可用性的》
《社交軟件紅包技術解密(六)：微信紅包系統的存儲層架構演進實踐》
《社交軟件紅包技術解密(七)：支付寶紅包的海量高并發技術實踐》
《社交軟件紅包技術解密(八)：全面解密微博紅包技術方案》
《社交軟件紅包技術解密(九)：談談手Q春節紅包的設計、容災、運維、架構等》
《社交軟件紅包技術解密(十)：手Q客戶端針對2020年春節紅包的技術實踐》
《社交軟件紅包技術解密(十一)：最全解密微信紅包隨機算法(含演示代碼)》（* 本文）
3、微信紅包算法要點匯總
這是目前能找到的僅有的一份，有微信團隊人員參與的微信紅包算法技術要點的討論資料。分享于2015年，差不多是微信紅包剛火沒多久，大概是微信技術團隊的人當時沒有現在這些技術之外的顧慮，所以作了有限的分享，資料難得，本次重新整理了一下，可以作為參考資料使用。以下是資料正文。
資料來源：來自InfoQ的某架構群的技術討論，由朱玉華整理（個人博客是：zhuyuhua.com（目前已無法訪問））。
資料背景：起因是有朋友在朋友圈咨詢微信紅包的架構，于是在微信團隊成員參與討論的情況下，我（指“朱玉華”）整理了這次討論的技術要點，也就是下面的內容（內容為問答形式）。
3.1、算法實現的技術要點
【1】問：微信的金額什么時候算？
答：微信金額是拆的時候實時算出來，不是預先分配的，采用的是純內存計算，不需要預算空間存儲。
為什么采取實時計算金額？原因是：實時效率更高，預算才效率低下。預算還要占額外存儲。因為紅包只占一條記錄而且有效期就幾天，所以不需要多大空間。就算壓力大時，水平擴展機器是。
【2】問：關于實時實時性，為什么明明搶到紅包，點開后發現沒有？
答：2014年的紅包一點開就知道金額，分兩次操作，先搶到金額，然后再轉賬。
2015年的紅包的拆和搶是分離的，需要點兩次，因此會出現搶到紅包了，但點開后告知紅包已經被領完的狀況。進入到第一個頁面不代表搶到，只表示當時紅包還有。
【3】問：關于分配算法，紅包里的金額怎么算？為什么出現各個紅包金額相差很大？
答：隨機，額度在 0.01 和剩余平均值 2 之間。 例如：發 100 塊錢，總共 10 個紅包，那么平均值是 10 塊錢一個，那么發出來的紅包的額度在 0.01元～20元之間波動。
當前面 3 個紅包總共被領了 40 塊錢時，剩下 60 塊錢，總共 7 個紅包，那么這 7 個紅包的額度在：0.01～（60/7 * 2）=17.14之間。
注意：這里的算法是每被搶一個后，剩下的會再次執行上面的這樣的算法（Tim老師也覺得上述算法太復雜，不知基于什么樣的考慮）。
這樣算下去，會超過最開始的全部金額，因此到了最后面如果不夠這么算，那么會采取如下算法：保證剩余用戶能拿到最低1分錢即可。
如果前面的人手氣不好，那么后面的余額越多，紅包額度也就越多，因此實際概率一樣的。
【4】問：紅包的設計
答：微信從財付通拉取金額數據過來，生成個數/紅包類型/金額放到redis集群里，App端將紅包ID的請求放入請求隊列中，如果發現超過紅包的個數，直接返回。根據紅包的邏輯處理成功得到令牌請求，則由財付通進行一致性調用，通過像比特幣一樣，兩邊保存交易記錄，交易后交給第三方服務審計，如果交易過程中出現不一致就強制回歸。
【5】問：并發性處理：紅包如何計算被搶完？
答：cache會抵抗無效請求，將無效的請求過濾掉，實際進入到后臺的量不大。cache記錄紅包個數，原子操作進行個數遞減，到 0 表示被搶光。財付通按照 20萬筆每秒入賬準備，但實際還不到 8萬每秒。
【6】問：通如何保持8w每秒的寫入？
答：多主sharding，水平擴展機器。
【7】問：數據容量多少？
答：一個紅包只占一條記錄，有效期只有幾天，因此不需要太多空間。
【8】問：查詢紅包分配，壓力大不？
答：搶到紅包的人數和紅包都在一條cache記錄上，沒有太大的查詢壓力。
【9】問：一個紅包一個隊列？
答：沒有隊列，一個紅包一條數據，數據上有一個計數器字段。
【10】問：有沒有從數據上證明每個紅包的概率是不是均等？
答：不是絕對均等，就是一個簡單的拍腦袋算法。
【11】問：拍腦袋算法，會不會出現兩個最佳？
答：會出現金額一樣的，但是手氣最佳只有一個，先搶到的那個最佳。
【12】問：每領一個紅包就更新數據么？
答：每搶到一個紅包，就cas更新剩余金額和紅包個數。
【13】問：紅包如何入庫入賬？
答：數據庫會累加已經領取的個數與金額，插入一條領取記錄。入賬則是后臺異步操作。
【14】問：入帳出錯怎么辦？比如紅包個數沒了，但余額還有？
答：最后會有一個take all操作。另外還有一個對賬來保障。
【15】問：既然在搶的時候有原子減了就不應該出現搶到了拆開沒有的情況？
答：這里的原子減并不是真正意義上的原子操作，是Cache層提供的CAS，通過比較版本號不斷嘗試。
【16】問：cache和db掛了怎么辦？
答：主備 +對賬。
【17】問：為什么要分離搶和拆？
答：總思路是設置多層過濾網，層層篩選，層層減少流量和壓力。
這個設計最初是因為搶操作是業務層，拆是入賬操作，一個操作太重了，而且中斷率高。 從接口層面看，第一個接口純緩存操作，搞壓能力強，一個簡單查詢Cache擋住了絕大部分用戶，做了第一道篩選，所以大部分人會看到已經搶完了的提示。
【18】問：搶到紅包后再發紅包或者提現，這里有什么策略嗎？
答：大額優先入賬策略。
針對上面的技術要點，有人還畫了張原理圖（這是網上能找到的相對清晰的版本）：
3.2、微信搶紅包的過程模擬
針對上節中整理的資料，當有人在微信群里發了一個 N 人的紅包、總金額 M 元，后臺大概的技術邏輯如下。
3.2.1）發紅包后臺操作：
1）在數據庫中增加一條紅包記錄，存儲到CKV，設置過期時間；
2）在Cache（可能是騰訊內部kv數據庫，基于內存，有落地，有內核態網絡處理模塊，以內核模塊形式提供服務））中增加一條記錄，存儲搶紅包的人數N。
3.2.2）搶紅包后臺操作：
1）搶紅包分為搶和拆：搶操作在Cache層完成，通過原子減操作進行紅包數遞減，到0就說明搶光了，最終實際進入后臺拆操作的量不大，通過操作的分離將無效請求直接擋在Cache層外面。
這里的原子減操作并不是真正意義上的原子減操作，是其Cache層提供的CAS，通過比較版本號不斷嘗試，存在一定程度上的沖突，沖突的用戶會放行，讓其進入下一步拆的操作，這也解釋了為啥有用戶搶到了拆開發現領完了的情況。
2）拆紅包在數據庫完成：通過數據庫的事務操作累加已經領取的個數和金額，插入一條領取流水，入賬為異步操作，這也解釋了為啥在春節期間紅包領取后在余額中看不到。
拆的時候會實時計算金額，其金額為1分到剩余平均值2倍之間隨機數，一個總金額為M元的紅包，最大的紅包為 M * 2 /N（且不會超過M），當拆了紅包后會更新剩余金額和個數。財付通按20萬筆每秒入賬準備，實際只到8萬每秒。
4、微信紅包算法模擬實現1（含代碼）
根據上一節的微信紅包隨機算法技術要點資料，實現了一個算法，以下供參考。（注：本節內容引用自《微信紅包隨機算法初探》一文）
4.1、算法約定
算法很簡單，跟微信的算法一樣，不是提前算好，而是搶紅包時計算。
即：金額隨機，額度在0.01和剩余平均值*2之間。（參見上一節的 “關于分配算法，紅包里的金額怎么算？為什么出現各個紅包金額相差很大？” 內容）
4.2、代碼實現
算法的邏輯主要是：
public static double getRandomMoney(RedPackage _redPackage) {
// remainSize 剩余的紅包數量
// remainMoney 剩余的錢
if(_redPackage.remainSize == 1) {
_redPackage.remainSize--;
return (double) Math.round(_redPackage.remainMoney * 100) / 100;
}
Random r = newRandom();
double min = 0.01; //
double max = _redPackage.remainMoney / _redPackage.remainSize * 2;
double money = r.nextDouble() * max;
money = money <= min ? 0.01: money;
money = Math.floor(money * 100) / 100;
_redPackage.remainSize--;
_redPackage.remainMoney -= money;
return money;
}
LeftMoneyPackage數據結構如下：
class RedPackage {
int remainSize;
double remainMoney;
}
測試時初始化相關數據是：
static void init() {
redPackage.remainSize = 30;
redPackage.remainMoney = 500;
}
附件是可以運行的完整JAVA代碼文件：
（無法上傳附件，如有需要請從此鏈接處下載：http://www.52im.net/thread-3125-1-1.html）
4.3、測試結果
4.3.1 單次測試
按上述代碼中的初始化數據（30人搶500塊），執行了兩次，結果如下：
//第一次
15.69 21.18 24.11 30.85 0.74 20.85 2.96 13.43 11.12 24.87 1.86 19.62 5.97 29.33 3.05 26.94 18.69 34.47 9.4 29.83 5.17 24.67 17.09 29.96 6.77 5.79 0.34 23.89 40.44 0.92
//第二次
10.44 18.01 17.01 21.07 11.87 4.78 30.14 32.05 16.68 20.34 12.94 27.98 9.31 17.97 12.93 28.75 12.1 12.77 7.54 10.87 4.16 25.36 26.89 5.73 11.59 23.91 17.77 15.85 23.42 9.77
第一次隨機紅包數據圖表如下：
▲ x軸為搶的順序，y軸為搶到的金額
第二次隨機紅包數據圖表如下：
▲ x軸為搶的順序，y軸為搶到的金額
4.3.2 多次均值
重復執行200次的均值：
▲ x軸為搶的順序，y軸為該次搶到金額的概率均值
重復執行2000次的均值：
▲ x軸為搶的順序，y軸為該次搶到金額的概率均值
從以上兩張圖的均值結果可以看出，這個算法中每一次能搶到的金額幾率幾乎是均等的，從隨機性來說比較合理。
5、微信紅包算法模擬實現2（含代碼）
我對隨機算法很感興趣，正巧最近研究的方向有點偏隨機數這塊，所以也自己實現了一下微信的紅包分發算法（算法要點參考的是本文第三節內容）。（注：本節內容引用自《微信紅包算法的分析》一文）
5.1、代碼實現
從第三節中可以了解到，微信并不是一開始就預分配所有的紅包金額，而是在拆時進行計算的。這樣做的好處是效率高，實時性。本次的代碼中，紅包具體是怎么計算的呢？請參見第4節中的“關于分配算法，紅包里的金額怎么算？為什么出現各個紅包金額相差很大？”。
那基于這個思想，可以寫出一個紅包分配算法：
/**
* 并不完美的紅包算法
*/
public static double rand(double money, int people, List<Double> l) {
if(people == 1) {
double red = Math.round(money * 100) / 100.0;
l.add(red);
return0;
}
Random random = newRandom();
double min = 0.01;
double max = money / people * 2.0;
double red = random.nextDouble() * max;
red = red <= min ? min : red;
red = Math.floor(red * 100) / 100.0;
l.add(red);
double remain = Math.round((money - red) * 100) / 100.0;
return remain;
}
算法整體思路很簡單，就在在最后一個人的時候要注意，此時不進行隨機數計算，而是直接將剩余金額作為紅包。
5.2、第一次分析
采用上述算法，可以對用戶的搶紅包行為做分析。這里的模仿行為是：30 元的紅包，10 人搶。操作 100 次。
可以得出如下結果：
▲ x軸為搶的順序，y軸為該次搶到金額
從上圖中可以很輕易的看出來，越后搶的人，風險越大，同時收益也越大，有較大幾率獲得“手氣最佳”。
那紅包面值的分布性如何呢？
▲ x軸為搶的順序，y軸為該次搶到金額重復 100 次后的平均值
從上圖可以看出，都是比較接近平均值(3 元)的。
那重復 1000 次呢？
▲ x軸為搶的順序，y軸為該次搶到金額重復 1000 次后的平均值
更接近了。。。
可以看出，這個算法可以讓大家搶到紅包面額在概率上是大致均等的。
5.3、不足之處
有人提出了這個問題：
他接下來放了好幾張他試驗的截圖。我這里取了一張，如果有興趣，可以去知乎的問題里查看更多圖片。
而此時，我哥們在和我的在討論中，也告訴我，確實存在某個規律，可能讓最后一個搶的人占有某些微小的優勢，比如，多 0.01 的之類。
例如發 6 個，總額 0.09 的包，最后一個搶的有極大概率是 0.03。
然而我之前的代碼卻沒辦法體現出這一點。
比如 10 人拆 0.11 元的包，我的結果是：
可見以上代碼還存在不足之處。
于是我就有一個猜測：
微信可能不是對全金額進行隨機的，可能在派發紅包之前，已經對金額做了處理，比如，事先減去(紅包個數*0.01)，之后在每個紅包的隨機值基礎上加 0.01，以此來保證每個紅包最小值都是 0.01。
這個猜測或許可以解開那位知友和我哥們這邊的疑惑。
5.4、完善算法
在原先的基礎上對代碼進行簡單的修正：
public static double rand(double money, int people, List<Double> l) {
if(people == 1) {
double red = Math.round(money * 100) / 100.0;
l.add(red+0.01);
return 0;
}
Random random = newRandom();
double min = 0;
double max = money / people * 2.0;
double red = random.nextDouble() * max;
red = red <= min ? min : red;
red = Math.floor(red * 100) / 100.0;
l.add(red+0.01);
double remain = Math.round((money - red) * 100) / 100.0;
return remain;
}
這個算法，在第一次調用時傳入 money 的值是總金額減去紅包數*0.01，大概像這樣：
_money = _money - people * 0.01;
5.5、第二次分析
5.5.1 驗證上次的不足之處
1）10 人搶 0.11 元的包：
2）2 人搶 0.03 元的包：
3）6 人搶 0.09 的包：
5.5.2 修改后的代碼會不會對已知結論造成影響？
30 元的紅包，10 人搶，操作 100 次。
▲ x軸為搶的順序，y軸為該次搶到金額
▲ x軸為搶的順序，y軸為該次搶到金額重復 100 次后的平均值
由上面兩圖可見，結論基本上沒有改變。
5.6、結論
經過上述代碼實踐可知：
1）先搶后搶，金額期望都是相同的；
2）微信的紅包算法很可能是預先分配給每人 0.01 的“底額”；
3）后搶者風險高，收益大。
5.7、補充
上幾張后面測試的圖，補充一下之前的觀點，發 n 個紅包，總金額是(n+1)*0.01，最后一個領的一定是手氣最佳。
大家也可以試試。
以上，大概可以證明，微信紅包是在分配前先給每個人 0.01 的最低金額的！
6、參考資料
[1] 微信紅包隨機算法初探
[2] 微信紅包算法的分析
[3] 微信紅包的架構設計簡介
[4] 微信紅包的隨機算法是怎樣實現的？
另外，知乎上對于微信紅包算法的討論問題很多人參與，有興趣可以上去看看，或許會有更多啟發：《微信紅包的隨機算法是怎樣實現的？》。
附錄：更多微信相關資源
《IM開發寶典：史上最全，微信各種功能參數和邏輯規則資料匯總》
《微信本地數據庫破解版(含IOS、Android)，僅供學習研究 [附件下載]》
（本文同步發布于：http://www.52im.net/thread-3125-1-1.html）
