微信红包的架构设计

https://www.zybuluo.com/yulin718/note/93148

概况：2014年微信红包使用数据库硬抗整个流量，2015年使用cache抗流量。

1. 微信的金额什么时候算？
   答：微信金额是拆的时候实时算出来，不是预先分配的，采用的是纯内存计算，不需要预算空间存储。。
   采取实时计算金额的考虑：预算需要占存储，实时效率很高，预算才效率低。
2. 实时性：为什么明明抢到红包，点开后发现没有？
   答：2014年的红包一点开就知道金额，分两次操作，先抢到金额，然后再转账。
   2015年的红包的拆和抢是分离的，需要点两次，因此会出现抢到红包了，但点开后告知红包已经被领完的状况。进入到第一个页面不代表抢到，只表示当时红包还有。
3. 分配：红包里的金额怎么算？为什么出现各个红包金额相差很大？
   答：随机，额度在0.01和剩余平均值*2之间。
   例如：发100块钱，总共10个红包，那么平均值是10块钱一个，那么发出来的红包的额度在0.01元～20元之间波动。
   当前面3个红包总共被领了40块钱时，剩下60块钱，总共7个红包，那么这7个红包的额度在：0.01～（60/7*2）=17.14之间。
   注意：这里的算法是每被抢一个后，剩下的会再次执行上面的这样的算法（Tim老师也觉得上述算法太复杂，不知基于什么样的考虑）。
   这样算下去，会超过最开始的全部金额，因此到了最后面如果不够这么算，那么会采取如下算法：保证剩余用户能拿到最低1分钱即可。
   如果前面的人手气不好，那么后面的余额越多，红包额度也就越多，因此实际概率一样的。
4. 红包的设计
   答：微信从财付通拉取金额数据郭莱，生成个数/红包类型/金额放到redis集群里，app端将红包ID的请求放入请求队列中，如果发现超过红包的个数，直接返回。根据红包的裸祭处理成功得到令牌请求，则由财付通进行一致性调用，通过像比特币一样，两边保存交易记录，交易后交给第三方服务审计，如果交易过程中出现不一致就强制回归。
5. 发性处理：红包如何计算被抢完？
   答：cache会抵抗无效请求，将无效的请求过滤掉，实际进入到后台的量不大。cache记录红包个数，原子操作进行个数递减，到0表示被抢光。财付通按照20万笔每秒入账准备，但实际还不到8万每秒。
6. 通如何保持8w每秒的写入？
   答：多主sharding，水平扩展机器。
7. 据容量多少？
   答：一个红包只占一条记录，有效期只有几天，因此不需要太多空间。
8. 询红包分配，压力大不？
   答：抢到红包的人数和红包都在一条cache记录上，没有太大的查询压力。
9. 一个红包一个队列？
   答：没有队列，一个红包一条数据，数据上有一个计数器字段。
10. 有没有从数据上证明每个红包的概率是不是均等？
    答：不是绝对均等，就是一个简单的拍脑袋算法。
11. 拍脑袋算法，会不会出现两个最佳？
    答：会出现金额一样的，但是手气最佳只有一个，先抢到的那个最佳。
12. 每领一个红包就更新数据么？
    答：每抢到一个红包，就cas更新剩余金额和红包个数。
13. 红包如何入库入账？
    数据库会累加已经领取的个数与金额，插入一条领取记录。入账则是后台异步操作。
14. 入帐出错怎么办？比如红包个数没了，但余额还有？
    答：最后会有一个take all操作。另外还有一个对账来保障。

http://timyang.net/architecture/wechat-red-packet/

为了保证每次操作的原子性，拆包过程中使用了CAS，确保每次只有一个并发用户拆包成功。拆包CAS失败的用户可以由系统自动进行重试。但也有可能在重试过程中被别的用户抢得先机而空手而归，因此严格意义拆包的调用也未能保证用户先到先得。

基于上面的原因，当时在群中提到这种算法有些复杂，微信红包为了减少存储，每次进行了一个理解稍复杂的实时计算。对比大部分架构师想到的预分配金额的做法，预先分配金额需要将金额保存在一个内存队列中，如果红包的份额较多，则需要较大的存储空间。而微信红包仅保存 count:balance 这样2个数字。count指还剩几个人可以抢，balance只还剩下的金额。

但是预分配金额也并不是非得需要额外存储。比如利用随机算法，在种子相同的情况下，随机数实际上返回的随机序列也是固定的。如以下Python代码，对于给定的seed 1024，每次执行返回的结果都是相同的。

因此预分配金额也只需要额外存储一个种子，或利用一些红包id做加密变换做seed达到零存储。而在发放红包时候，无需进行CAS操作，而只需要对剩余红包count做一个DECR操作。当count<0时，表示红包被拆包抢完。由于DECR是原子操作，无需加锁，用简单的方法达到了先拆包先得，原理上不存在早拆包但由于并发冲突失败而抢不到红包的情况。

每个人分配的金额是：total * random(n) / random_total，不需要重复计算。
random(1)..random(n)不需要保存，因为对于给定的seed，random(1)到random(n)返回是固定的。

http://www.phppan.com/2015/04/weixin-hongbao/

当有人在群里发了一个N人的红包，总金额M元，后台大概发生的事情如下：

一、发红包后台操作：

1. 在数据库中增加一条红包记录，存储到CKV，设置过期时间；
2. 在Cache（可能是腾讯内部kv数据库，基于内存，有落地，有内核态网络处理模块，以内核模块形式提供服务））中增加一条记录，存储抢红包的人数N

二、抢红包后台操作：

1. 抢红包分为抢和拆，抢操作在Cache层完成，通过原子减操作进行红包数递减，到0就说明抢光了，最终实际进入后台拆操作的量不大，通过操作的分离将无效请求直接挡在Cache层外面。这里的原子减操作并不是真正意义上的原子减操作，是其Cache层提供的CAS，通过比较版本号不断尝试，存在一定程度上的冲突，冲突的用户会放行，让其进入下一步拆的操作，这也解释了为啥有用户抢到了拆开发现领完了的情况。
2. 拆红包在数据库完成，通过数据库的事务操作累加已经领取的个数和金额，插入一条领取流水，入账为异步操作，这也解释了为啥在春节期间红包领取后在余额中看不到。拆的时候会实时计算金额，其金额为1分到剩余平均值2倍之间随机数，一个总金额为M元的红包，最大的红包为 M * 2 /N（且不会超过M），当拆了红包后会更新剩余金额和个数。财付通按20万笔每秒入账准备，实际只到8万每秒。

FAQ

1. 既然在抢的时候有原子减了就不应该出现抢到了拆开没有的情况？
   这里的原子减并不是真正意义上的原子操作，是Cache层提供的CAS，通过比较版本号不断尝试。
2. cache和db挂了怎么办？
   主备 +对账
3. 有没有红包个数没了，但余额还有情况？
   没有，程序最后会有一个take all操作以及一个异步对账保障。
4. 为什么要分离抢和拆？
   总思路是设置多层过滤网，层层筛选，层层减少流量和压力。这个设计最初是因为抢操作是业务层，拆是入账操作，一个操作太重了，而且中断率高。 从接口层面看，第一个接口纯缓存操作，搞压能力强，一个简单查询Cache挡住了绝大部分用户，做了第一道筛选，所以大部分人会看到已经抢完了的提示。
5. 抢到红包后再发红包或者提现，这里有什么策略吗？
   大额优先入账策略
6. 有没有从数据上证明每个红包的概率是不是均等？
   不是绝对均等，就是一个简单的拍脑袋算法。
7. 拍脑袋算法，会不会出现两个最佳？
   会出现金额一样的，但是手气最佳只有一个，先抢到的那个最佳。
8. 发红包人的钱会不会冻结？
   是直接实时扣掉，不是冻结。
9. 采用实时算出金额是出于什么考虑？
   实时效率更高，预算才效率低下。预算还要占额外存储。因为红包只占一条记录而且有效期就几天，所以不需要多大空间。就算压力大时，水平扩展机器是。

http://finalshares.com/read-549?jike-503

红包领了不少，据观察红包主要有以下几个限制条件： 

• 所有人都能分到红包，也就是不会出现红包数值为 0 的情况
• 所有人的红包数值加起来等于支付的金额
• 红包波动范围比较大，约 5%~8% 的红包数值在平均值的两倍以上，同时数额 0.01 出现的概率比较高
• 红包的数值是随机的，并且数值的分布近似于正态分布

其中，前两条是最基本的限制条件，如果要求不是特别高，可以完全只考虑前两个限制条件即可。

def weixin_divide_hongbao(money, n):     divide_table = [random.randint(1, 10000) for x in xrange(0, n)]     sum_ = sum(divide_table)     return [x*money/sum_ for x in divide_table]

3.2、相关问题

如使用该方式，需要自己去添加相关代码逻辑去处理如下问题

• 浮点数精度问题
• 边界值的处理

from decimal import Decimal, InvalidOperation

                  

import random

                  

                  

def money_val(min, max):

    return min if min > max else Decimal(str(random.randint(min, max)))

                  

                  

def money_random(total, num, min=0.01):

    """

    :param total=10; # 红包总额 10 元

    :param num=8; # 分成 8 个红包，支持 8 人随机领取

    :param min=0.01; # 每个人最少能收到 0.01 元

    """

    money_list = []

                  

    try:

        total = Decimal(str(total))

    except InvalidOperation as e:

        return money_list, e.message

                  

    try:

        if isinstance(num, float) and int(num) != num:

            raise ValueError(u'Invalid value for Num: \'{0}\''.format(num))

        num = Decimal(str(int(num)))

    except ValueError as e:

        return money_list, e.message

                  

    try:

        min = Decimal(str(min))

    except InvalidOperation as e:

        return money_list, e.message

                  

    if total < num * min:

        return money_list, u'Invalid value for Total-{0}, Num-{1}, Min-{2}'.format(total, num, min)

                  

    for i in xrange(1, num):

        safe_total = (total - (num - i) * min) / (num - i)  # 随机安全上限

        money = money_val(min * 100, int(safe_total * 100)) / 100

        total -= money

        money_list.append(money)

    money_list.append(total)

                  

    random.shuffle(money_list)  # 随机打乱

                  

    return money_list, u'Success'

                  

                  

if __name__ == '__main__':

    print money_random(1, 10)

    print money_random(0.1, 10)

    print money_random(0.11, 10)

    print money_random(0.12, 10)