最全解密微信紅包隨機(jī)算法(含代碼實(shí)現(xiàn))
1、引言
一方面是各社交/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。
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)匯總
資料來源：來自InfoQ的某架構(gòu)群的技術(shù)討論，由朱玉華整理（個(gè)人博客是：zhuyuhua.com（目前已無法訪問））。
資料背景：起因是有朋友在朋友圈咨詢微信紅包的架構(gòu)，于是在微信團(tuán)隊(duì)成員參與討論的情況下，我（指“朱玉華”）整理了這次討論的技術(shù)要點(diǎn)，也就是下面的內(nèi)容（內(nèi)容為問答形式）。
3.1、算法實(shí)現(xiàn)的技術(shù)要點(diǎn)
問：微信的金額什么時(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ī)器是。
問：關(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í)紅包還有。
問：關(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/72）=17.14之間。
注意：這里的算法是每被搶一個(gè)后，剩下的會(huì)再次執(zhí)行上面的這樣的算法（Tim老師也覺得上述算法太復(fù)雜，不知基于什么樣的考慮）。
如果前面的人手氣不好，那么后面的余額越多，紅包額度也就越多，因此實(shí)際概率一樣的。
問：紅包的設(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)制回歸。
問：并發(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萬每秒。
問：通如何保持8w每秒的寫入？
答：多主sharding，水平擴(kuò)展機(jī)器。
問：數(shù)據(jù)容量多少？
答：一個(gè)紅包只占一條記錄，有效期只有幾天，因此不需要太多空間。
問：查詢紅包分配，壓力大不？
答：搶到紅包的人數(shù)和紅包都在一條cache記錄上，沒有太大的查詢壓力。
問：一個(gè)紅包一個(gè)隊(duì)列？
答：沒有隊(duì)列，一個(gè)紅包一條數(shù)據(jù)，數(shù)據(jù)上有一個(gè)計(jì)數(shù)器字段。
問：有沒有從數(shù)據(jù)上證明每個(gè)紅包的概率是不是均等？
答：不是絕對(duì)均等，就是一個(gè)簡(jiǎn)單的拍腦袋算法。
問：拍腦袋算法，會(huì)不會(huì)出現(xiàn)兩個(gè)最佳？
答：會(huì)出現(xiàn)金額一樣的，但是手氣最佳只有一個(gè)，先搶到的那個(gè)最佳。
問：每領(lǐng)一個(gè)紅包就更新數(shù)據(jù)么？
答：每搶到一個(gè)紅包，就cas更新剩余金額和紅包個(gè)數(shù)。
問：紅包如何入庫入賬？
答：數(shù)據(jù)庫會(huì)累加已經(jīng)領(lǐng)取的個(gè)數(shù)與金額，插入一條領(lǐng)取記錄。入賬則是后臺(tái)異步操作。
問：入帳出錯(cuò)怎么辦？比如紅包個(gè)數(shù)沒了，但余額還有？
答：最后會(huì)有一個(gè)take all操作。另外還有一個(gè)對(duì)賬來保障。
問：既然在搶的時(shí)候有原子減了就不應(yīng)該出現(xiàn)搶到了拆開沒有的情況？
答：這里的原子減并不是真正意義上的原子操作，是Cache層提供的CAS，通過比較版本號(hào)不斷嘗試。
問：cache和db掛了怎么辦？
答：主備 +對(duì)賬。
問：為什么要分離搶和拆？
答：總思路是設(shè)置多層過濾網(wǎng)，層層篩選，層層減少流量和壓力。
這個(gè)設(shè)計(jì)最初是因?yàn)閾尣僮魇菢I(yè)務(wù)層，拆是入賬操作，一個(gè)操作太重了，而且中斷率高。從接口層面看，第一個(gè)接口純緩存操作，搞壓能力強(qiáng)，一個(gè)簡(jiǎn)單查詢Cache擋住了絕大部分用戶，做了第一道篩選，所以大部分人會(huì)看到已經(jīng)搶完了的提示。
問：搶到紅包后再發(fā)紅包或者提現(xiàn)，這里有什么策略嗎？
答：大額優(yōu)先入賬策略。
針對(duì)上面的技術(shù)要點(diǎn)，有人還畫了張?jiān)韴D（這是網(wǎng)上能找到的相對(duì)清晰的版本）：
3.2、微信搶紅包的過程模擬
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（含代碼）
4.1、算法約定
即：金額隨機(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 剩余的錢if (_redPackage.remainSize == 1) {_redPackage.remainSize--;return (double) Math.round(_redPackage.remainMoney * 100) / 100;}Random r = new Random();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;}
class RedPackage {int remainSize;double remainMoney;}
static void init() {redPackage.remainSize = 30;redPackage.remainMoney = 500;}
（附件下載：http://www.52im.net/thread-3125-1-1.html）
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ù)圖表如下：
?4.3.2多次均值
重復(fù)執(zhí)行200次的均值：
▲?x軸為搶的順序，y軸為該次搶到金額的概率均值
重復(fù)執(zhí)行2000次的均值：
▲?x軸為搶的順序，y軸為該次搶到金額的概率均值
從以上兩張圖的均值結(jié)果可以看出，這個(gè)算法中每一次能搶到的金額幾率幾乎是均等的，從隨機(jī)性來說比較合理。
5、微信紅包算法模擬實(shí)現(xiàn)2（含代碼）
5.1、代碼實(shí)現(xiàn)
那基于這個(gè)思想，可以寫出一個(gè)紅包分配算法：
/*** 并不完美的紅包算法*/public static double rand(double money, int people, Listl) { if (people == 1) {double red = Math.round(money * 100) / 100.0;l.add(red);return 0;}Random random = new Random();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、第一次分析
可以得出如下結(jié)果：
?從上圖中可以很輕易的看出來，越后搶的人，風(fēng)險(xiǎn)越大，同時(shí)收益也越大，有較大幾率獲得“手氣最佳”。
那紅包面值的分布性如何呢？
?從上圖可以看出，都是比較接近平均值(3 元)的。
那重復(fù) 1000 次呢？
?更接近了。。。
可以看出，這個(gè)算法可以讓大家搶到紅包面額在概率上是大致均等的。
5.3、不足之處
?他接下來放了好幾張他試驗(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è)：
這個(gè)猜測(cè)或許可以解開那位知友和我哥們這邊的疑惑。
5.4、完善算法
public static double rand(double money, int people, Listl) { if (people == 1) {double red = Math.round(money * 100) / 100.0;l.add(red+0.01);return 0;}Random random = new Random();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 = _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 次。
?
?由上面兩圖可見，結(jié)論基本上沒有改變。
5.6、結(jié)論
1）先搶后搶，金額期望都是相同的； 2）微信的紅包算法很可能是預(yù)先分配給每人 0.01 的“底額”； 3）后搶者風(fēng)險(xiǎn)高，收益大。
5.7、補(bǔ)充
?
?大家也可以試試。
以上，大概可以證明，微信紅包是在分配前先給每個(gè)人 0.01 的最低金額的！
6、參考資料
[2]?微信紅包算法的分析
[3]?微信紅包的架構(gòu)設(shè)計(jì)簡(jiǎn)介
[4]?微信紅包的隨機(jī)算法是怎樣實(shí)現(xiàn)的？
另外，知乎上對(duì)于微信紅包算法的討論問題很多人參與，有興趣可以上去看看，或許會(huì)有更多啟發(fā)：《微信紅包的隨機(jī)算法是怎樣實(shí)現(xiàn)的？》。
——————END——————
歡迎關(guān)注“Java引導(dǎo)者”，我們分享最有價(jià)值的Java的干貨文章，助力您成為有思想的Java開發(fā)工程師！
贊+在看,小生感恩??
評(píng)論
圖片
表情