较真抽奖服务里的随机性

作者：cancanjin，腾讯PCG后台开发工程师

| 导语抽奖是一个非常常见的业务场景，抽奖的公平性是用户普遍都关心的问题。而抽奖一般有人抽奖品（有抽奖资格的用户主动抽奖品）和奖品选人（类似年会抽奖）两类。redis提供的srandmember方法和后者的业务场景非常贴合，但是深入了解了该方法的底层实现后，可以发现很多之前难以发现的小问题。本文讨论的就是基于redis里srandmember方法做抽奖服务的随机性问题。

一、背景

体育业务中有一类互动活动是每场赛事提前配置好固定数目不同档位的奖品，针对参加活动的用户随机选取用户中奖。

由于比赛热度的不同，参与用户的量级从0到几十万不等。

我们的抽奖方案也很简单，满足条件（过滤了黑产）的用户uid存储在redis的set结构中。抽奖时调用srandmember方法选取n个人依次中一等奖、二等奖等。

本文不考虑随机数生成的伪随机性问题，假设随机数算法足够随机的情况下，业务侧还可能遇到什么问题。

二、随机性分析2.1 问题一、总是uid小的人中大奖？

内测阶段很容易发现一个问题，中了一等奖的人总是中一等奖，这个问题真是足够严重了。查看中奖名单uid列表，名单顺序完全是uid顺序。

分析：redis的set存储类型有两种。当元素可以转为整数，且元素数小于一定值（配置文件中set-max-intset-entries变量)时是intset类型，类似数组，按照整数从小到大排列，如下图所示。

否则就是hashtable类型。

redis里所有的value都封装成了redisObject，可以查看元素类型、编码方式等。

typedef struct redisObject { // 刚刚好32 bits // 对象的类型，字符串/列表/集合/哈希表 unsigned type:4; // 未使用的两个位 unsigned notused:2; /* Not used */ // 编码的方式，Redis 为了节省空间，提供多种方式来保存一个数据 // 譬如：“123456789” 会被存储为整数123456789 unsigned encoding:4; // 当内存紧张，淘汰数据的时候用到 unsigned lru:22; /* lru time (relative to server.lruclock) */ // 引用计数 int refcount; // 数据指针 void *ptr;} robj;

使用redis Object命令查看set的编码类型：

查看或者修改set-max-intset-entries的大小可以在腾讯云控制台参数配置页操作。

内测阶段用户参与量很小，小于512，所以返回的用户列表是顺序排列的。当然如果我们选取不同档位奖品的时候，是多次spop的方式，也不会有问题。

解决：对srandmember返回的数据随机打乱，再分配奖品。

2.2 问题二、延伸考虑，如果参与人数不会小于512，还会有上面的问题吗？

2.2.1 存储顺序的稳定性

redis里set的特征是无序、去重。无序和随机其实是完全不一样的概念，无序只是说元素的存储顺序不按照加入顺序，但是相同的添加顺序得到的元素顺序是一样的。看一下set元素的添加过程就能确认了(https://github.com/redis/redis/blob/4.0/src/t_set.c)：

dict结构的定义在dict.h文件中：https://github.com/redis/redis/blob/4.0/src/dict.h

如上图所示，dict里的ht就是一个hashtable，hashtable里包含哈希表的大小，用于定位元素应该放在table下什么索引的掩码和已经使用的节点数量。redis往set添加元素的过程简单总结就是：

1. 计算元素对应的哈希值和索引值（hash值和掩码按位与就是索引）
2. 将元素放在哈希表具体的数组索引位置上，同时更新used大小+1。
3. 随着元素增加，当操作时发现某个哈希表保存的键值对过多或过少时，redis会出发rehash逻辑。
4. rehash的步骤就是首先根据要ht[0]中used大小，在ht[1]中分配空间；然后将ht[0]中所有元素再次计算哈希值（和之前的哈希值结果肯定一样）和索引值（size不同，掩码也不同，得到的索引不同），放入ht[1]中。所有元素迁移完以后释放ht[0]，ht[1]变为ht[0]，等待下一次rehash。

redis采用的hash算法是siphash。无论哪个hash算法，哈希方法都有两个特征：稳定、分布均匀。可以看到整个元素添加的过程中，不会引入任何随机策略，按照同样顺序添加元素，得到的元素顺序是一样的。

也就是如果用户每次加入set的顺序不变，得到的set存储顺序也不变。尤其是当set个数较少时，元素碰撞的概率变低，set的存储顺序更加稳定。

2.2.2、挑选过程的随机性：

就算每次抽奖都用同一个set，只要选取用户的时候是随机的，也可以保证抽奖的随机性。那srandmember方法是怎么实现随机挑选元素的呢？

简单总结就是：

1、count为负数时返回元素可重复的count个元素

2、挑选元素数count 大于等于总数时，直接返回整个set

3、除了上面的边界情况，redis会新申请一个set，如果count小于某个临界值，就随机选择count个元素。如果count大于某个临界值，就把全部元素拷贝到新set里，然后随机删除n-count个元素。

在614行定义了SRANDMEMBER_SUB_STRATEGY_MUL为3。也就是当挑选的元素个数大于总数目1/3时返回元素的顺序基本是元素的存储顺序。在抽奖业务场景下，如果参与用户不多，奖品数目较多，接近100%中奖时，选择的用户名单的顺序也是稳定的。

最后，redis官方文档https://redis.io/commands/srandmember/的说明也验证了这一点：

返回结果的顺序不是真正随机的，客户端需要自己shuffle一下。其原因就是上面2.1和2.2部分分析过的。

2.3 问题三、元素挑选过程的随机性问题

前面分别讨论了使用srandmember方法，intset类型返回的元素顺序按整数排列。hashtable类型在选取的元素个数逼近set总数时返回的元素顺序也是稳定的。

那么只要我们对返回结果打散，还会有其他随机性的问题吗？

有的！这个发生在一开始挑选元素的过程中，也就是选取谁中奖的问题。

redis文档里最后提到了redis6以下（我们在meepo平台上申请的redis目前是5.0版本）随机挑选的算法不是完美的随机算法：

1. 先找到一个不为空的桶。
2. 桶里随机选择元素删除。

这意味着如果set元素比较少，某个桶里如果只有一个元素，这个元素被挑选到的概率将远远大于其他桶。

2.3.1 这个对于实际业务会带来什么问题呢？

如果用户的参与顺序大致稳定，或者每次抽奖使用同一个set。当用户量级较少（碰撞概率低）时，会发生某一类uid的用户中奖概率高于其他用户。

如果对抽奖概率不是那么较真的，或者认为用户的参与顺序足够随机也可以忽略这个问题，但是严格意义上并不符合我们的预期。比如我们的业务场景就是通过push下发触达的用户，为了抗并发，可能会按用户群体做削峰处理，（先推某一类uid的用户，再推送某一类uid的用户；或者区分地域推送）会导致用户接收到参与提醒的时机是有序的，那么用户的参与时机也会大致有序。所以通过依赖参与顺序的随机性来保证抽奖结果的随机性是不稳定的，很容易被忽略。

2.3.2 那么抽奖逻辑可以如何解决这个问题呢？

这里我想了三种解决方案，方案的优缺点欢迎一起研究讨论下。

方案1、在set小于一定临界值时，全量拉取用户，随机打乱，截取前n用户中奖。反之就信赖srandmember的结果（阅读redis源码，可以发现redis很多地方都是这个思想，量变带来质变）

方案2、思考以后，想到一种去除uid稳定性的方案（更倾向本方案）。上面所有的随机性问题的产生都是由于哈希方法是稳定的，用户的uid也是稳定的。思路转变成只要保证算法的不均匀不涉及到uid就可以了。

如果在计算哈希的时候，加入随机盐：hash(uid+nounce)，只要保证每场抽奖使用不同的nounce，nounce随机，对于业务来说就没有问题了。

这个方案的成本转换为每场比赛选取一个随机盐。

方案3、如果业务不追求奖品100%发到真实用户，可以在每个参与用户set下，随机加入一些dump用户。新用户的加入会导致set不断触发rehash，变动存储顺序。这样就解决了稳定用户群体的中奖随机性问题。

这个方案会导致奖品可能不会发到真实用户，有业务局限性。

三、总结

为了更好理解，举一个通俗点的例子来解释。就像我们在商店买东西，货架上的商品顺序是在放入的时候决定的。每次买东西，随机选择count个商品，选择好以后导购员按照这几样商品货架上的顺序取下来。商品a如果在商品b的前面，不管买几次，选择的count是多少，a都永远在b的前面。如果有新商品的加入，货架上的商品位置可能会发生小范围挪动。

综上所述，其实一共分析了两个问题，
一是srandmember返回的数据顺序可能是稳定的，表现为挑选元素个数不变时，返回结果里a在b的前面就永远在b的前面，执行多少次都是。

二是桶里元素比较少时，srandmember挑选元素的概率不均问题。

针对问题一，做法就是对srandmember方法返回的结果打散。

针对问题二、在2.3.2部分提出了三种解决思路。

使用srandmember做抽奖时，必须要做的就是重排返回结果的顺序。做了这一步，抽奖的随机性就基本得到了保证。但是如果对随机性要求更高的业务场景，比如年会抽奖..摇号..，就需要我们方案选型时，多考虑下底层实现的部分。

如果摒弃srandmember方法做抽奖，自己实现抽奖，也需要我们的业务考虑其他的问题，比如百万级或者千万级用户，中奖名单在万级时，如何加载数据，如何扫描用户，如何去重等。业务开发没有“银弹”，适合自己业务场景的才是最好的。