这篇文章写在飞机晚点严重的一天，晚了10个小时，无力吐槽。到了早上的时候，人越来越多，候机厅比较吵，想起还有个类似问题，值得写一篇文章，于是开搞，很快完成了。奇妙的是，感觉时间过得很快，周围也没有那么吵了，哈哈。
最近遇到要写一个红包程序，这个问题其实有很多可以考虑的地方，是个有意思的问题，我就慢慢说来。
首先，我们最先想到和可能接触最多的是微信的拼手气红包，不管怎么抢，最后都能抢完，而且每个人得到的也基本是分布均匀的；这个其实是一类，还有一类，当时产品要求给单个红包设置限额，比如最少1个额度，最多10个额度，而且有总的红包额度。这种情况下，就会出现比较复杂的情况，用微信的方法是不能满足的要求的。下面分开各自说明下。
红包问题几个实现的关键点：平均分布或基本平均，额度随机，能够分配完，每个都能分到，总额固定不会超出。
举几个例子：限定单个上限的话，前面分配完成了，最后剩余很多，不可取。或者前面分配完了，后面分配不到。又或者单个获得红包额和人数的和，超过了总金额，这种情况可能是并发或者分配策略不当造成。
问题提出来，再去解决问题，首先看看微信是怎么做的。
概况来说，微信有个固定的算法，实时计算获得的红包金额，每次用剩余的额度除以剩余人数的一半作为最大随机边界，即保证能分配完，又能随机，每个人都分配到。以下是核心代码简单逻辑，只需要最开始初始化就可以。
public int randomPacket() {
if (remainSize ==0 || !checkConfig()) {
return -1;
}
if (remainSize ==1) {
remainSize--;
return remainCoin;
}
int max =remainCoin /remainSize *2;
int t = RandomUtils.nextInt(1, max);
remainSize--;
remainCoin -= t;
return t;
}
下面我们再看看限定上界的方案。当时想的是生成对应的槽位，比如n个人，就有n个槽位，首先用1填充，可以默认为1，然后剩下的槽位随机多次遍历，用1到上限的随机数填充，达最大，跳过找下一个，直到所有的额度分配完成，相当于预先生成红包，然后每次就从预生成的中取就可以。但是有几个问题。1、生成过程中多次随机，会很慢，某些概率下会造成假死，一直找不到合适的位置；2、预生成无疑增加了存储的成本；3、多了存储，相应的交互也多了起来，实现会繁重和复杂。下面是个简单的实现例子：
private int totalCoin;
private int maxCoin;
private int minCoin;
private int size;
private final AtomicInteger current = new AtomicInteger(0);
private Map<Integer, Integer> packets;
public PacketPrepare(int maxCoin, int minCoin, int totalCoin, int size) {
this.maxCoin = maxCoin;
this.minCoin = minCoin;
this.totalCoin = totalCoin;
this.size = size;
this.packets = randomPackets();
}
private Map<Integer, Integer> randomPackets() {
Map<Integer, Integer> packets = Maps.newHashMap();
if (!checkConfig()) {
return packets;
}
int remain = totalCoin;
Integer t;
int rand;
int round = 0;
while (remain > 0) {
for (int i = 0; i < size; i++) {
if (round == 0) {
packets.put(i, 1);
remain--;
continue;
}
rand = RandomUtils.nextInt(minCoin - 1, maxCoin);
if (remain - rand <= 0) {
t = packets.get(i);
packets.put(i, remain + t);
return packets;
}
remain -= rand;
t = packets.get(i);
if (t == null) {
t = 1;
}
t += rand;
packets.put(i, t);
}
round++;
}
return packets;
}
private boolean checkConfig() {
if (maxCoin <= 0 || minCoin <= 0 || totalCoin <= 0 || size <= 0) {
return false;
}
if (totalCoin < size) {
return false;
}
if (maxCoin >= totalCoin) {
return false;
}
return true;
}
最后做个总结。鉴于预先生成的方案有各种弊端，最后说服产品统一使用微信的方案，比较业界大头。这里还有个问题要补充，线上服务一般都是多机器部署的，红包肯定不能用内存存储，这里想到了用Redis做记录，一个唯一key，只对应总人数和总额度。内存计算红包后，对人数和额度做减少，而且Redis增减是原子的。当然也可以用MySQL等update set n = n - x ，但这种方式对锁不是很友好，而且也比较繁琐。除了Redis，额外的用MySQL记录些红包基本信息和领取记录，整个就实现完成了。功能还有很多可以改进的点，期待以后更多接触对之进行优化。
网友评论