1、引言
這個(gè)系列文章已經(jīng)整理了10篇，但都沒有涉及到具體的紅包算法實(shí)現(xiàn)，主要有以下兩方面原因。
一方面是各社交/IM產(chǎn)品中的紅包功能同質(zhì)化嚴(yán)重，紅包算法的“可玩性”便是“核心競(jìng)爭(zhēng)力所在”，這是同質(zhì)化功能的差異化競(jìng)爭(zhēng)思路，不會(huì)隨便公開。
另一方面，市場(chǎng)上還存在各種搶紅包插件這類灰產(chǎn)存在，一旦公開這些算法，很可能又被這幫插件開發(fā)者們搞出什么幺蛾子。
所以，這樣的情況下，如果要做社交/IM產(chǎn)品中的紅包功能，紅包隨便算法該怎么實(shí)現(xiàn)，基本上只能自已琢磨，很難找到大廠算法直接套用。
本著即時(shí)通訊網(wǎng)一貫的im知識(shí)傳播精神，我收集整理并參考了大量的網(wǎng)上資料，綜合了比較靠譜的信息來源，便有了本文。本文根據(jù)有限的資料，分享了微信紅包隨機(jī)算法實(shí)現(xiàn)中的一些技術(shù)要點(diǎn)，并整理了兩種比較靠譜的紅包算法實(shí)現(xiàn)思路（含可運(yùn)行的實(shí)現(xiàn)代碼），希望能給你的紅包算法開發(fā)帶來啟發(fā)。
申明：本文資料整理自網(wǎng)絡(luò)，僅供學(xué)習(xí)研究之用，如有不妥，請(qǐng)通知Jack Jiang。
學(xué)習(xí)交流：
- 移動(dòng)端IM開發(fā)入門文章：《新手入門一篇就夠：從零開發(fā)移動(dòng)端IM》
- 開源IM框架源碼：
本文已同步發(fā)布于“即時(shí)通訊技術(shù)圈”公眾號(hào)。
2、系列文章
《社交軟件紅包技術(shù)解密(一)：全面解密QQ紅包技術(shù)方案——架構(gòu)、技術(shù)實(shí)現(xiàn)等》
《社交軟件紅包技術(shù)解密(二)：解密微信搖一搖紅包從0到1的技術(shù)演進(jìn)》
《社交軟件紅包技術(shù)解密(三)：微信搖一搖紅包雨背后的技術(shù)細(xì)節(jié)》
《社交軟件紅包技術(shù)解密(四)：微信紅包系統(tǒng)是如何應(yīng)對(duì)高并發(fā)的》
《社交軟件紅包技術(shù)解密(五)：微信紅包系統(tǒng)是如何實(shí)現(xiàn)高可用性的》
《社交軟件紅包技術(shù)解密(六)：微信紅包系統(tǒng)的存儲(chǔ)層架構(gòu)演進(jìn)實(shí)踐》
《社交軟件紅包技術(shù)解密(七)：支付寶紅包的海量高并發(fā)技術(shù)實(shí)踐》
《社交軟件紅包技術(shù)解密(八)：全面解密微博紅包技術(shù)方案》
《社交軟件紅包技術(shù)解密(九)：談?wù)勈諵春節(jié)紅包的設(shè)計(jì)、容災(zāi)、運(yùn)維、架構(gòu)等》
《社交軟件紅包技術(shù)解密(十)：手Q客戶端針對(duì)2020年春節(jié)紅包的技術(shù)實(shí)踐》
《社交軟件紅包技術(shù)解密(十一)：最全解密微信紅包隨機(jī)算法(含演示代碼)》（* 本文）
3、微信紅包算法要點(diǎn)匯總
這是目前能找到的僅有的一份，有微信團(tuán)隊(duì)人員參與的微信紅包算法技術(shù)要點(diǎn)的討論資料。分享于2015年，差不多是微信紅包剛火沒多久，大概是微信技術(shù)團(tuán)隊(duì)的人當(dāng)時(shí)沒有現(xiàn)在這些技術(shù)之外的顧慮，所以作了有限的分享，資料難得，本次重新整理了一下，可以作為參考資料使用。以下是資料正文。
資料來源：來自InfoQ的某架構(gòu)群的技術(shù)討論，由朱玉華整理（個(gè)人博客是：z（目前已無法訪問））。
資料背景：起因是有朋友在朋友圈咨詢微信紅包的架構(gòu)，于是在微信團(tuán)隊(duì)成員參與討論的情況下，我（指“朱玉華”）整理了這次討論的技術(shù)要點(diǎn)，也就是下面的內(nèi)容（內(nèi)容為問答形式）。
3.1、算法實(shí)現(xiàn)的技術(shù)要點(diǎn)
【1】問：微信的金額什么時(shí)候算？
答：微信金額是拆的時(shí)候?qū)崟r(shí)算出來，不是預(yù)先分配的，采用的是純內(nèi)存計(jì)算，不需要預(yù)算空間存儲(chǔ)。
為什么采取實(shí)時(shí)計(jì)算金額？原因是：實(shí)時(shí)效率更高，預(yù)算才效率低下。預(yù)算還要占額外存儲(chǔ)。因?yàn)榧t包只占一條記錄而且有效期就幾天，所以不需要多大空間。就算壓力大時(shí)，水平擴(kuò)展機(jī)器是。
【2】問：關(guān)于實(shí)時(shí)實(shí)時(shí)性，為什么明明搶到紅包，點(diǎn)開后發(fā)現(xiàn)沒有？
答：2014年的紅包一點(diǎn)開就知道金額，分兩次操作，先搶到金額，然后再轉(zhuǎn)賬。
2015年的紅包的拆和搶是分離的，需要點(diǎn)兩次，因此會(huì)出現(xiàn)搶到紅包了，但點(diǎn)開后告知紅包已經(jīng)被領(lǐng)完的狀況。進(jìn)入到第一個(gè)頁面不代表搶到，只表示當(dāng)時(shí)紅包還有。
【3】問：關(guān)于分配算法，紅包里的金額怎么算？為什么出現(xiàn)各個(gè)紅包金額相差很大？
答：隨機(jī)，額度在 0.01 和剩余平均值 2 之間。 例如：發(fā) 100 塊錢，總共 10 個(gè)紅包，那么平均值是 10 塊錢一個(gè)，那么發(fā)出來的紅包的額度在 0.01元～20元之間波動(dòng)。
當(dāng)前面 3 個(gè)紅包總共被領(lǐng)了 40 塊錢時(shí)，剩下 60 塊錢，總共 7 個(gè)紅包，那么這 7 個(gè)紅包的額度在：0.01～（60/7 * 2）=17.14之間。
注意：這里的算法是每被搶一個(gè)后，剩下的會(huì)再次執(zhí)行上面的這樣的算法（Tim老師也覺得上述算法太復(fù)雜，不知基于什么樣的考慮）。
這樣算下去，會(huì)超過最開始的全部金額，因此到了最后面如果不夠這么算，那么會(huì)采取如下算法：保證剩余用戶能拿到最低1分錢即可。
如果前面的人手氣不好，那么后面的余額越多，紅包額度也就越多，因此實(shí)際概率一樣的。
【4】問：紅包的設(shè)計(jì)
答：微信從財(cái)付通拉取金額數(shù)據(jù)過來，生成個(gè)數(shù)/紅包類型/金額放到redis集群里，app端將紅包ID的請(qǐng)求放入請(qǐng)求隊(duì)列中，如果發(fā)現(xiàn)超過紅包的個(gè)數(shù)，直接返回。根據(jù)紅包的邏輯處理成功得到令牌請(qǐng)求，則由財(cái)付通進(jìn)行一致性調(diào)用，通過像比特幣一樣，兩邊保存交易記錄，交易后交給第三方服務(wù)審計(jì)，如果交易過程中出現(xiàn)不一致就強(qiáng)制回歸。
【5】問：并發(fā)性處理：紅包如何計(jì)算被搶完？
答：cache會(huì)抵抗無效請(qǐng)求，將無效的請(qǐng)求過濾掉，實(shí)際進(jìn)入到后臺(tái)的量不大。cache記錄紅包個(gè)數(shù)，原子操作進(jìn)行個(gè)數(shù)遞減，到 0 表示被搶光。財(cái)付通按照 20萬筆每秒入賬準(zhǔn)備，但實(shí)際還不到 8萬每秒。
【6】問：通如何保持8w每秒的寫入？
答：多主sharding，水平擴(kuò)展機(jī)器。
【7】問：數(shù)據(jù)容量多少？
答：一個(gè)紅包只占一條記錄，有效期只有幾天，因此不需要太多空間。
【8】問：查詢紅包分配，壓力大不？
答：搶到紅包的人數(shù)和紅包都在一條cache記錄上，沒有太大的查詢壓力。
【9】問：一個(gè)紅包一個(gè)隊(duì)列？
答：沒有隊(duì)列，一個(gè)紅包一條數(shù)據(jù)，數(shù)據(jù)上有一個(gè)計(jì)數(shù)器字段。
【10】問：有沒有從數(shù)據(jù)上證明每個(gè)紅包的概率是不是均等？
答：不是絕對(duì)均等，就是一個(gè)簡(jiǎn)單的拍腦袋算法。
【11】問：拍腦袋算法，會(huì)不會(huì)出現(xiàn)兩個(gè)最佳？
答：會(huì)出現(xiàn)金額一樣的，但是手氣最佳只有一個(gè)，先搶到的那個(gè)最佳。
【12】問：每領(lǐng)一個(gè)紅包就更新數(shù)據(jù)么？
答：每搶到一個(gè)紅包，就cas更新剩余金額和紅包個(gè)數(shù)。
【13】問：紅包如何入庫入賬？
答：數(shù)據(jù)庫會(huì)累加已經(jīng)領(lǐng)取的個(gè)數(shù)與金額，插入一條領(lǐng)取記錄。入賬則是后臺(tái)異步操作。
【14】問：入帳出錯(cuò)怎么辦？比如紅包個(gè)數(shù)沒了，但余額還有？
答：最后會(huì)有一個(gè)take all操作。另外還有一個(gè)對(duì)賬來保障。
【15】問：既然在搶的時(shí)候有原子減了就不應(yīng)該出現(xiàn)搶到了拆開沒有的情況？
答：這里的原子減并不是真正意義上的原子操作，是Cache層提供的CAS，通過比較版本號(hào)不斷嘗試。
【16】問：cache和db掛了怎么辦？
答：主備 +對(duì)賬。
【17】問：為什么要分離搶和拆？
答：總思路是設(shè)置多層過濾網(wǎng)，層層篩選，層層減少流量和壓力。
這個(gè)設(shè)計(jì)最初是因?yàn)閾尣僮魇菢I(yè)務(wù)層，拆是入賬操作，一個(gè)操作太重了，而且中斷率高。 從接口層面看，第一個(gè)接口純緩存操作，搞壓能力強(qiáng)，一個(gè)簡(jiǎn)單查詢Cache擋住了絕大部分用戶，做了第一道篩選，所以大部分人會(huì)看到已經(jīng)搶完了的提示。
【18】問：搶到紅包后再發(fā)紅包或者提現(xiàn)，這里有什么策略嗎？
答：大額優(yōu)先入賬策略。
針對(duì)上面的技術(shù)要點(diǎn)，有人還畫了張?jiān)韴D（這是網(wǎng)上能找到的相對(duì)清晰的版本）：
3.2、微信搶紅包的過程模擬
針對(duì)上節(jié)中整理的資料，當(dāng)有人在微信群里發(fā)了一個(gè) N 人的紅包、總金額 M 元，后臺(tái)大概的技術(shù)邏輯如下。
3.2.1）發(fā)紅包后臺(tái)操作：
1）在數(shù)據(jù)庫中增加一條紅包記錄，存儲(chǔ)到CKV，設(shè)置過期時(shí)間；
2）在Cache（可能是騰訊內(nèi)部kv數(shù)據(jù)庫，基于內(nèi)存，有落地，有內(nèi)核態(tài)網(wǎng)絡(luò)處理模塊，以內(nèi)核模塊形式提供服務(wù)））中增加一條記錄，存儲(chǔ)搶紅包的人數(shù)N。
3.2.2）搶紅包后臺(tái)操作：
1）搶紅包分為搶和拆：搶操作在Cache層完成，通過原子減操作進(jìn)行紅包數(shù)遞減，到0就說明搶光了，最終實(shí)際進(jìn)入后臺(tái)拆操作的量不大，通過操作的分離將無效請(qǐng)求直接擋在Cache層外面。
這里的原子減操作并不是真正意義上的原子減操作，是其Cache層提供的CAS，通過比較版本號(hào)不斷嘗試，存在一定程度上的沖突，沖突的用戶會(huì)放行，讓其進(jìn)入下一步拆的操作，這也解釋了為啥有用戶搶到了拆開發(fā)現(xiàn)領(lǐng)完了的情況。
2）拆紅包在數(shù)據(jù)庫完成：通過數(shù)據(jù)庫的事務(wù)操作累加已經(jīng)領(lǐng)取的個(gè)數(shù)和金額，插入一條領(lǐng)取流水，入賬為異步操作，這也解釋了為啥在春節(jié)期間紅包領(lǐng)取后在余額中看不到。
拆的時(shí)候會(huì)實(shí)時(shí)計(jì)算金額，其金額為1分到剩余平均值2倍之間隨機(jī)數(shù)，一個(gè)總金額為M元的紅包，最大的紅包為 M * 2 /N（且不會(huì)超過M），當(dāng)拆了紅包后會(huì)更新剩余金額和個(gè)數(shù)。財(cái)付通按20萬筆每秒入賬準(zhǔn)備，實(shí)際只到8萬每秒。
4、微信紅包算法模擬實(shí)現(xiàn)1（含代碼）
根據(jù)上一節(jié)的微信紅包隨機(jī)算法技術(shù)要點(diǎn)資料，實(shí)現(xiàn)了一個(gè)算法，以下供參考。（注：本節(jié)內(nèi)容引用自《微信紅包隨機(jī)算法初探》一文）
4.1、算法約定
算法很簡(jiǎn)單，跟微信的算法一樣，不是提前算好，而是搶紅包時(shí)計(jì)算。
即：金額隨機(jī)，額度在0.01和剩余平均值*2之間。（參見上一節(jié)的 “關(guān)于分配算法，紅包里的金額怎么算？為什么出現(xiàn)各個(gè)紅包金額相差很大？” 內(nèi)容）
4.2、代碼實(shí)現(xiàn)
算法的邏輯主要是：
public static double getRandomMoney(RedPackage _redPackage) {
// remainSize 剩余的紅包數(shù)量
// remainMoney 剩余的錢
i == 1) {
_redPackage.remainSize--;
return (double) Ma * 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 = Ma(money * 100) / 100;
_redPackage.remainSize--;
_redPackage.remainMoney -= money;
return money;
}
LeftMoneyPackage數(shù)據(jù)結(jié)構(gòu)如下：
class RedPackage {
int remainSize;
double remainMoney;
}
測(cè)試時(shí)初始化相關(guān)數(shù)據(jù)是：
static void init() {
redPackage.remainSize = 30;
redPackage.remainMoney = 500;
}
附件是可以運(yùn)行的完整Java代碼文件：
（無法上傳附件，如有需要請(qǐng)從此鏈接處下載：）
4.3、測(cè)試結(jié)果
4.3.1 單次測(cè)試
按上述代碼中的初始化數(shù)據(jù)（30人搶500塊），執(zhí)行了兩次，結(jié)果如下：
//第一次
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
第一次隨機(jī)紅包數(shù)據(jù)圖表如下：
▲ x軸為搶的順序，y軸為搶到的金額
第二次隨機(jī)紅包數(shù)據(jù)圖表如下：
▲ x軸為搶的順序，y軸為搶到的金額
4.3.2 多次均值
重復(fù)執(zhí)行200次的均值：
▲ x軸為搶的順序，y軸為該次搶到金額的概率均值
重復(fù)執(zhí)行2000次的均值：
▲ x軸為搶的順序，y軸為該次搶到金額的概率均值
從以上兩張圖的均值結(jié)果可以看出，這個(gè)算法中每一次能搶到的金額幾率幾乎是均等的，從隨機(jī)性來說比較合理。
5、微信紅包算法模擬實(shí)現(xiàn)2（含代碼）
我對(duì)隨機(jī)算法很感興趣，正巧最近研究的方向有點(diǎn)偏隨機(jī)數(shù)這塊，所以也自己實(shí)現(xiàn)了一下微信的紅包分發(fā)算法（算法要點(diǎn)參考的是本文第三節(jié)內(nèi)容）。（注：本節(jié)內(nèi)容引用自《微信紅包算法的分析》一文）
5.1、代碼實(shí)現(xiàn)
從第三節(jié)中可以了解到，微信并不是一開始就預(yù)分配所有的紅包金額，而是在拆時(shí)進(jìn)行計(jì)算的。這樣做的好處是效率高，實(shí)時(shí)性。本次的代碼中，紅包具體是怎么計(jì)算的呢？請(qǐng)參見第4節(jié)中的“關(guān)于分配算法，紅包里的金額怎么算？為什么出現(xiàn)各個(gè)紅包金額相差很大？”。
那基于這個(gè)思想，可以寫出一個(gè)紅包分配算法：
/**
* 并不完美的紅包算法
*/
public static double rand(double money, int people, List<Double> l) {
if(people == 1) {
double red = Ma(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 = Ma(red * 100) / 100.0;
l.add(red);
double remain = Ma((money - red) * 100) / 100.0;
return remain;
}
算法整體思路很簡(jiǎn)單，就在在最后一個(gè)人的時(shí)候要注意，此時(shí)不進(jìn)行隨機(jī)數(shù)計(jì)算，而是直接將剩余金額作為紅包。
5.2、第一次分析
采用上述算法，可以對(duì)用戶的搶紅包行為做分析。這里的模仿行為是：30 元的紅包，10 人搶。操作 100 次。
可以得出如下結(jié)果：
▲ x軸為搶的順序，y軸為該次搶到金額
從上圖中可以很輕易的看出來，越后搶的人，風(fēng)險(xiǎn)越大，同時(shí)收益也越大，有較大幾率獲得“手氣最佳”。
那紅包面值的分布性如何呢？
▲ x軸為搶的順序，y軸為該次搶到金額重復(fù) 100 次后的平均值
從上圖可以看出，都是比較接近平均值(3 元)的。
那重復(fù) 1000 次呢？
▲ x軸為搶的順序，y軸為該次搶到金額重復(fù) 1000 次后的平均值
更接近了。。。
可以看出，這個(gè)算法可以讓大家搶到紅包面額在概率上是大致均等的。
5.3、不足之處
有人提出了這個(gè)問題：
他接下來放了好幾張他試驗(yàn)的截圖。我這里取了一張，如果有興趣，可以去知乎的問題里查看更多圖片。
而此時(shí)，我哥們?cè)诤臀业脑谟懻撝?，也告訴我，確實(shí)存在某個(gè)規(guī)律，可能讓最后一個(gè)搶的人占有某些微小的優(yōu)勢(shì)，比如，多 0.01 的之類。
例如發(fā) 6 個(gè)，總額 0.09 的包，最后一個(gè)搶的有極大概率是 0.03。
然而我之前的代碼卻沒辦法體現(xiàn)出這一點(diǎn)。
比如 10 人拆 0.11 元的包，我的結(jié)果是：
可見以上代碼還存在不足之處。
于是我就有一個(gè)猜測(cè)：
微信可能不是對(duì)全金額進(jìn)行隨機(jī)的，可能在派發(fā)紅包之前，已經(jīng)對(duì)金額做了處理，比如，事先減去(紅包個(gè)數(shù)*0.01)，之后在每個(gè)紅包的隨機(jī)值基礎(chǔ)上加 0.01，以此來保證每個(gè)紅包最小值都是 0.01。
這個(gè)猜測(cè)或許可以解開那位知友和我哥們這邊的疑惑。
5.4、完善算法
在原先的基礎(chǔ)上對(duì)代碼進(jìn)行簡(jiǎn)單的修正：
public static double rand(double money, int people, List<Double> l) {
if(people == 1) {
double red = Ma(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 = Ma(red * 100) / 100.0;
l.add(red+0.01);
double remain = Ma((money - red) * 100) / 100.0;
return remain;
}
這個(gè)算法，在第一次調(diào)用時(shí)傳入 money 的值是總金額減去紅包數(shù)*0.01，大概像這樣：
_money = _money - people * 0.01;
5.5、第二次分析
5.5.1 驗(yàn)證上次的不足之處
1）10 人搶 0.11 元的包：
2）2 人搶 0.03 元的包：
3）6 人搶 0.09 的包：
5.5.2 修改后的代碼會(huì)不會(huì)對(duì)已知結(jié)論造成影響？
30 元的紅包，10 人搶，操作 100 次。
▲ x軸為搶的順序，y軸為該次搶到金額
▲ x軸為搶的順序，y軸為該次搶到金額重復(fù) 100 次后的平均值
由上面兩圖可見，結(jié)論基本上沒有改變。
5.6、結(jié)論
經(jīng)過上述代碼實(shí)踐可知：
1）先搶后搶，金額期望都是相同的；
2）微信的紅包算法很可能是預(yù)先分配給每人 0.01 的“底額”；
3）后搶者風(fēng)險(xiǎn)高，收益大。
5.7、補(bǔ)充
上幾張后面測(cè)試的圖，補(bǔ)充一下之前的觀點(diǎn)，發(fā) n 個(gè)紅包，總金額是(n+1)*0.01，最后一個(gè)領(lǐng)的一定是手氣最佳。
大家也可以試試。
以上，大概可以證明，微信紅包是在分配前先給每個(gè)人 0.01 的最低金額的！
6、參考資料
[1] 微信紅包隨機(jī)算法初探
[2] 微信紅包算法的分析
[3] 微信紅包的架構(gòu)設(shè)計(jì)簡(jiǎn)介
[4] 微信紅包的隨機(jī)算法是怎樣實(shí)現(xiàn)的？
另外，知乎上對(duì)于微信紅包算法的討論問題很多人參與，有興趣可以上去看看，或許會(huì)有更多啟發(fā)：《微信紅包的隨機(jī)算法是怎樣實(shí)現(xiàn)的？》。
附錄：更多微信相關(guān)資源
《IM開發(fā)寶典：史上最全，微信各種功能參數(shù)和邏輯規(guī)則資料匯總》
《微信本地?cái)?shù)據(jù)庫破解版(含iOS、Android)，僅供學(xué)習(xí)研究 [附件下載]》
（本文同步發(fā)布于：）
1.《0.10紅包代表什么看這里!最全解密微信紅包隨機(jī)算法(含代碼實(shí)現(xiàn))》援引自互聯(lián)網(wǎng)，旨在傳遞更多網(wǎng)絡(luò)信息知識(shí)，僅代表作者本人觀點(diǎn)，與本網(wǎng)站無關(guān)，侵刪請(qǐng)聯(lián)系頁腳下方聯(lián)系方式。
2.《0.10紅包代表什么看這里!最全解密微信紅包隨機(jī)算法(含代碼實(shí)現(xiàn))》僅供讀者參考，本網(wǎng)站未對(duì)該內(nèi)容進(jìn)行證實(shí)，對(duì)其原創(chuàng)性、真實(shí)性、完整性、及時(shí)性不作任何保證。
3.文章轉(zhuǎn)載時(shí)請(qǐng)保留本站內(nèi)容來源地址，http://f99ss.com/gl/2170827.html
