常见系统设计题系列-抽奖系统

不得不说的随机

拿音乐播放器的随机播放举一个例子，一般音乐播放器的随机播放分两种：

播放当前歌曲时才随机生成下一首，即完全随机（称为Random算法）
将当前的list打乱顺序，然后依次播放，也就是大家所说的伪随机（称为Shuffle算法）

对我们的Shuffle算法进行下抽象：

一个从1到n的序列，随机打乱，保证每个数出现在任意一个位置的概率相同。

// 得到一个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        // 从 i 到最后随机选一个元素
        int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}

按照权重生成随机数

方法1: 如果随机选的话，在一个list中出现的次数多被选中的概率就会大。所以可以按照权重组合一个list，在这个list中A有50个，B有10个，C有100个，等等。有了list之后，从中随机选一个。这样选取的时间负责度是O(1)。但是如果数字很多，权重又很大的话，那么空间复杂度会很高。

方法2: 对每个元素的权重进行加和记为sum，在1到sum之间随机选一个数。之后遍历整个集合，统计遍历到的项的权重之和，如果大于sum，则选择这个数。该方法需要遍历集合，时间复杂度为O(n)

方案3: 上面方法最坏的情况是遍历完所有的元素，但是如果权重大的元素能够先被遍历的话可以减少遍历次数。基于此，可以先对元素按照权重排序。但是这样排序的话也会比较花时间。可以计算一个前项和序列，记录到每一项时的权重是多少。然后随机生成一个数，可以用二分查找找这个数对应的索引，也就可以找到对应的元素。

跟nginx的WRR有什么区别呢？

红包系统设计

有以下几个要点：

预留足够的金额以确保每一个红包至少有钱（预留金额：0.01 * N)
对剩余金额进行分配，使分配结果符合某种需要的分布：截尾正态分布、纯随机分布等
考虑拆的时候实时算出来，而不预先分配的，采用的是纯内存计算，不需要预算空间存储。采取实时计算金额的考虑：预算需要占存储，实时效率很高，预先计算存起来才效率低。
数据库会累加已经领取的个数与金额，插入一条领取记录。入账则是后台异步操作。
二倍均值法，剩余红包金额为M，剩余人数为N，那么有如下公式：每次抢到的金额 = 随机区间?（0， M / N X 2）

微信红包架构

方案一，使用内存操作替代实时的 DB 事务操作。
并发性能好，但是有可能丢失数据
方案二，使用乐观锁替代悲观锁。
并发请求抢锁问题解决，但是用户体验不好

正确姿势：

系统垂直 SET 化，分而治之。
1. 按照红包ID来hash分流
逻辑 Server 层将请求排队，解决 DB 并发问题。
1. 首先，将同一个红包 ID 的所有请求 stick 到同一台 Server。
2. 其次，设计单机请求排队方案。
3. 最后，增加 memcached 控制并发。
双维度库表设计，保障系统性能稳定
1. 按照db_{红包IDhash}.table_{红包日期1～31}

蓄水池算法

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。

考虑参加抽奖的用户基数很大且未知，也可以说是这个基数可能会动态地增加，那么在这种情况下，固定选取k个人中奖，如何保证实时参加抽奖的n个用户中每个人中奖的概率为k/n呢？（为何不在最终结果n出来时再来随机抽取k个样本，保证概率为k/n呢？其实这种想法有些时候是不可行的，数据是动态增长的，可能缓存系统存储不了所有的样本信息，但却足够存储k个样本的信息，即空间复杂度可以从O(n)降到O(k)，k相对n来说是非常小的。所以储水池算法还是很有应用价值的）

Neo's Blog