淺談群紅包的實(shí)現(xiàn)
前言：
紅包是支付的方式, 也是社交的延伸。群紅包在這兩塊領(lǐng)域串聯(lián)得很好, 表現(xiàn)尤為的濃墨重彩.
承接上兩篇技術(shù)淺談:
1). 淺談接龍紅包的技術(shù)實(shí)現(xiàn).
2). 淺談微信紅包搖一搖的技術(shù)實(shí)現(xiàn).
這一次, 讓我們談?wù)勅杭t包的技術(shù)實(shí)現(xiàn). 一為是紅包的分配算法, 二為競(jìng)搶的技術(shù)實(shí)現(xiàn).
分配算法:
最初玩群紅包的時(shí)候, 并沒有意識(shí)到分配算法的難度. 下意識(shí)的覺得, 不就是個(gè)隨機(jī)算法嘛? so easy! 后來在知乎上看到很多人在討論, 才意識(shí)到該算法或許并不簡(jiǎn)單.
好的東西, 往往讓人覺得簡(jiǎn)單, 而其背后默默挨打的小怪獸(精細(xì)和縝密), 你是否可曾留意過.
我們先來看看, 最自然的隨機(jī)算法, 為何不合理?
假設(shè)T為總金額, k為紅包個(gè)數(shù), 每次獲取先保底(每人至少得最小金額為0.01), 然后取隨機(jī)剩余數(shù)
則Ai的迭代公式為:
|
1
2
|
Ai = random(0.01, T - 0.01 * (k - i) - A0 - … - Ai-1) (0 <= i < k - 1)
Ak-1 = T - A0 - … - Ak-2 (最后玩家所得)
|
貌似簡(jiǎn)單合理, 殊不知頭重腳輕, 統(tǒng)計(jì)概率上, 排前面的值往往大于排后面的值, 當(dāng)k很大, 最后幾位往往會(huì)被收斂為0.01.
顯然不合理, 這篇<<微信紅包的算法實(shí)現(xiàn)探討>>博文也證述了該現(xiàn)象.
結(jié)合上面的例子, 一個(gè)好的分配算法, 必須具備以下幾個(gè)條件:
1). 每個(gè)玩家都能領(lǐng)到紅包
2). 所有玩家的紅包錢數(shù)和等于總數(shù)
3). 無論哪個(gè)順序位, 在紅包分配上的概率是平等公平的
對(duì)了條件(3)的解讀, 可以這么理解, 每個(gè)順序位的預(yù)期紅包分配數(shù)為N/k (N為紅包總素,k為用戶數(shù)). 一次分配差異大, 但統(tǒng)計(jì)重復(fù)M次, M越大, 預(yù)期平均值越接近N/k. 這就是宏觀上的平等.
有人就以平均值做突破口, 引入截尾正態(tài)分布, 達(dá)到了非常好的效果.
詳細(xì)見<<微信紅包算法探討>>這篇博文, 這邊具體也不展開了.
工程的角度, 我們可以簡(jiǎn)化算法, 用擬合的算法來近似代替.
概率函數(shù)為:
|
1
2
3
|
對(duì)于第i個(gè)玩家而言
隨機(jī)生成(k-i)個(gè) Bj (j=0,1,k-i-1), Bj范圍在[0, 100]之間.
則概率函數(shù)P(i) = Bi / (B0 + B1 + ... + Bk-i-1)
|
對(duì)于Ai, 則迭代公式為:
|
1
2
|
Ti = T - 0.01 * (k - i) - A0 - … - Ai-1
則Ai = Ti * P(i) + 0.01 = Ti * Bi / (B0 + B1 + ... + Bk-i-1) + 0.01
|
因?yàn)槭褂?strong>加減乘除, 比用高級(jí)概率分布的sin/cos/log函數(shù)計(jì)算效率要高.
競(jìng)搶技術(shù):
群紅包的"搶奪", 最重要的還是數(shù)據(jù)安全問題.說白了就是競(jìng)態(tài)條件下, 如何保證數(shù)據(jù)完整性和一致性
業(yè)內(nèi)對(duì)該類問題, 有大致三種主流的做法:
1). 悲觀鎖思路
2). FIFO隊(duì)列思路
3). 樂觀鎖思路
悲觀鎖思路, 常見的是借用mysql的SELECT ... FOR UPDATE語(yǔ)句來實(shí)現(xiàn).
|
1
2
3
4
|
begin transaction; // (1)開啟事務(wù)
select ... for update; // (2)鎖定某行記錄
update ... set ... where ...; // (3)進(jìn)行記錄更新
commit transaction; // (4)事務(wù)提交
|
這邊重點(diǎn)講講樂觀鎖機(jī)制, 其不光能用于關(guān)系數(shù)據(jù)庫(kù),也能用于NoSQL.
樂觀鎖的核心思想是, 基于版本號(hào)的更新, 前提是操作需保證原子性.
設(shè)計(jì)簡(jiǎn)化的紅包表:
注釋: total_money為總金額, total_number為紅包數(shù), left_money為剩余金額數(shù), left_number為剩余紅包數(shù)
當(dāng)用戶拆紅包時(shí), 觸發(fā)如下流程
(1) 查詢?nèi)杭t包信息
|
1
2
3
|
SELECT left_money, left_number, version_id
FROM tb_hongbao
WHERE envelope_id = '?';
|
(2) 計(jì)算所分配的紅包
通過上述的方法, 通過left_money, left_number計(jì)算出具體的紅包: delta_money
(3) 更新群紅包信息
|
1
2
3
4
5
6
7
|
UPDATE tb_hongbao
SET
left_money = left_money - delta_money,
left_number = left_number - 1,
version_id = version_id + 1
WHERE
envelope_id = '?' AND version_id = 'old_version_id'
|
SQL是能保證原子性的, 帶著上次查詢回來的version_id去更新, 若version_id一致, 則更新成功, 版本號(hào)遞增, 若不一致, 則需要重復(fù)1~3步, 直至成功或放棄.
這邊講述的利用mysql來實(shí)現(xiàn)的, 事實(shí)上有些Nosql系統(tǒng)也支持(大淘寶的Tair服務(wù)).
寫在最后：
如果你覺得這篇文章對(duì)你有幫助, 請(qǐng)小小打賞下. 其實(shí)我想試試, 看看寫博客能否給自己帶來一點(diǎn)小小的收益. 無論多少, 都是對(duì)樓主一種由衷的肯定.
轉(zhuǎn)自: http://www.cnblogs.com/mumuxinfei/p/4305979.html