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