前言：
ꢀ
ꢀ红包是支付的方式, 也是社交的延伸。群红包在这两块领域串联得很好, 表现尤为的浓墨重
彩.
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ承接上两篇技术浅谈：
ꢀ1). 浅谈接龙红包的技术实现.
ꢀ2). 浅谈微信红包摇一摇的技术实现.
ꢀ这一次, 让我们谈谈群红包的技术实现. 一为是红包的分配算法, 二为竞抢的技术实现.
分配算法:
ꢀ最初玩群红包的时候, 并没有意识到分配算法的难度. 下意识的觉得, 不就是个随机算法
嘛? so easy! 后来在知乎上看到很多人在讨论, 才意识到该算法或许并不简单.
ꢀ好的东西, 往往让人觉得简单, 而其背后默默挨打的小怪兽(精细和缜密), 你是否可曾留意
过.
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ我们先来看看, 最自然的随机算法, 为何不合理?
ꢀ假设 T 为总金额, k 为红包个数, 每次获取先保底(每人至少得最小金额为 0.01), 然后取随
机剩余数
ꢀ
ꢀ则 Ai 的迭代公式为:
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. 这就是宏观
上的平等.
ꢀ
ꢀ
ꢀ
ꢀ有人就以平均值做突破口, 引入截尾正态分布, 达到了非常好的效果.
ꢀ
ꢀ详细见<<微信红包算法探讨>>这篇博文, 这边具体也不展开了.
工程的角度, 我们可以简化算法, 用拟合的算法来近似代替.
ꢀ概率函数为:
ꢀ
对于第 i 个玩家而言
随机生成(k-i)个 Bj (j=0,1,k-i-1), Bj 范围在[0, 100]之间.
则概率函数 P(i) = Bi / (B0 + B1 + ... + Bk-i-1)
对于 Ai, 则迭代公式为:
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 语句来实现.
begin transaction; ꢀꢀꢀꢀ // (1)开启事务
select ... for update; ꢀꢀꢀꢀꢀ// (2)锁定某行记录
update ... set ... where ...;ꢀꢀ// (3)进行记录更新
commit transaction; ꢀꢀꢀꢀꢀ// (4)事务提交ꢀ
这边重点讲讲乐观锁机制, 其不光能用于关系数据库,也能用于 NoSQL.
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ乐观锁的核心思想是, 基于版本号的更新, 前提是操作需保证原子性.
ꢀ设计简化的红包表:
ꢀ
ꢀ注释: total_money 为总金额, total_number 为红包数, left_money 为剩余金额数,
left_number 为剩余红包数
ꢀ
ꢀ
ꢀ当用户拆红包时, 触发如下流程
ꢀ(1) 查询群红包信息
SELECT left_money, left_number, version_id
FROM tb_hongbao
WHERE envelope_id = '?';
ꢀ
(2) 计算所分配的红包
通过上述的方法, 通过 left_money, left_number 计算出具体的红包: delta_money
(3) 更新群红包信息
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 服务).
