确定性抽奖

今天在微信中无意点开一个链接, 说的是微信花费抽奖活动, 在上千万个抽奖机会中抽取 3 个代步车、300万张话费券、600万张车票券以及500万张电影票代金券. 一时间想到万妖谷的抽卡功能就做过这种确定性抽奖功能. 确定性抽奖需要保证的就是次数严格相等, 比如 1% 的概率抽取 100 次就必须保证只有一次抽中. 如果按照纯概率随机就有可能抽出多个来. 解决方法其实不难, 只需要事先生成好抽取表就好了, 每次就从中随机一个元素, 随机一个减去一个, 以此来保证确定性. 随之而来会遇到的问题是, 如果抽取表都被抽光了怎么办? 可以像微信一样生成一张巨大的表, 保证在这个活动期间内绝不会抽完. 但是也有万一抽完的情况, 这个时候就会排除掉一些项目再重新生成一个抽取表, 3 个代步车就很可能会被删除, 其它的项目就可以按照比例再分配. 这是由于事先确定了数目决定的. 在万妖谷中事先只确定了概率, 方法是类似的, 取一个大的整数, 按照概率大小分配每个类别的数量, 抽取完了就再重复生成一遍.

随之而来的第二个问题是, 如此巨大的表应该如何保存, 我们给出的方案很简单, 只保存类别和数量, 不具体保存元素. 这样 4 个类别就只有非常小的 8 个整型值. 为了从中抽取, 万妖谷的方法是将类别概率排序, 小概率在前, 但其数量保存的不在是当前类别的数量, 而是一直到该类别所有前面的数量和. 随机一个数字落在哪个范围就是哪种类别. 抽完之后还得将从抽中的类别之后的所有的数量都减一. 这样做的好处在于总数在最后一个元素, 很容易知道. 抽取的方法只需要简单再这个总数内随机一个整数然后查找范围就可以了. 今天我自己想到另外一种方法, 当做是补充吧, 将所有类别当前的数量与总数的比作为本次抽取的概率, 随后按照这个最新的概率随机一个类别, 对相应的类别减一. 当某个类别减至数量为 0 自然就不再参与下一次抽取了. 这个方法需要每次重新计算概率, 但是数据结构相对会简单一点, 至少不在需要排序列表.

说到这里再讨论多一点. 我们在做万妖谷的时候是多线程进行抽奖的, 而生成好的抽取表是以 json 字符串的形式保存在 Redis 中. 整个抽取的过程必须保证是原子操作, 也就是说从读取抽取表到再次写入抽取表必须保证期间其它线程没有改变此数据.

Redis 为开发者提供了 5 个命令来实现事务操作. WATCH 命令监视若干键, MULTI 开启事务, 其后直到 EXEC 命令之间的所有操作都会暂存起来而不提交, EXEC 仅在 WATCH 住的键没有改变的情况下才会以原子的方式将上面的操作都持久化到 Redis 中. 还有 DISCARD 和 UNWATCH 取消事务. 在此必须说明一下, EXEC、DISCARD、UNWATCH 都具有将 MULTI 后面的暂存命令清除和使 WATCH 失效的能力, 并且解除事务. 也就是说一旦调用这 3 命令中的任何一个, 连接状态就变成了正常状态. 这正是我们所需要的. 另外一点就是 MULTI 和 EXEC 可以单独使用, 不必与 WATCH 配合. 这为一次性提交多个操作提供了可能性.

在我们的抽卡过程中, 首先会 WATCH 住这个抽取表, 并在 MULTI 命令下获取抽取表, 执行抽取, 再次写入抽取表, 最后调用 EXEC 提交本次操作. 如果提交时发现抽取表已经被别的线程更改了, 就再重复执行直到最大重试次数. 这就是我们所谓的乐观锁. 之所以获取抽取表也放在 WATCH 之后, 是因为有可能如果放在之前的话, 在获取抽取表之后, WATCH 之前那段时间其它线程更改了抽取表, 而无法察觉.

虽然 Redis 能够监视整个键, 却无法监视 hash 里边的一个 field. 为了防止多用户同时修改一个 hash 里边的同一个 field 但是又要允许可以同时修改不同的 field, 利用 Redis 的 HSET HINCRBY 是原子操作的性质搞了个类似于自旋锁的方案. 具体地说就是另外开辟了一个键作为锁键, 调用 HINCRBY 对锁键中相应的 field 进行增加 1 的操作, 如果增加完之后发现新值不是 1 表示加锁不成功不能操作原键中对应 field 数据, 并再次重试增加 1 , 把新值与 1 进行比较, 直到成功或达到最大次数. 而新值为 1 的表示加锁成功, 将操作原键中对应 field 数据. 并在操作完之后调用 HSET 将锁键中的 field 设置为 0, 表示解锁. 现在想来这种方法有点重, 若是用 WeakHashMap 配以原子对象的 compareAndSet 方法的方式直接在内存中搞会轻量一点.