随机数在互联网业务中的应用
在互联网业务中，随机数被用到的场景很广泛。通常大家也认为使用随机数很简单，直接调用现成的函数库即可实现功能。但是想用好随机数还是有些难度的。需要熟悉其中的原理。本文会介绍一些在互联网业务中使用随机的方法。
在信息学中，随机的定义如下：
随机性：不存在统计学偏差，是完全杂乱的数列
不可预测性：不能从过去的数列推测出下一个出现的数
不可重现性：除非将数列本身保存下来，否则不能重现相同的数列
随机数可能在统计上呈现某种规律。
在工程上，用到随机也主要是用到两个特性：
- 不可预测性
- 均匀获取数字。（在大量随机统计时，每个数出现次数的期望相同）
在安全相关的场景，用到的是不可预测性。例如生成密钥，生成验证码等场景，让黑客不能从中找到生成的规律。
在抽奖实现、负载均衡等场景，主要用到随机数在统计时，每个随机数字出现的次数的期望都很接近，让结果是公平的。
0 随机数的生成方法
在计算机中，主要生成随机数有两种方法，线性同余算法，硬件设备随机数生成器。
一、线性同余算法
在C函数库中的rand()函数，用的就是线性同余算法，类似的实现代码如下
1 | static unsigned long next = 1; |
注：以上只是为了简单描述Glibc库实现的方法，实际代码不是这样写的。
利用srand函数设置初始随机种子，在每次需要随机数的时候调用rand生成随机数。
线性同余算法的特点是：只要种子相同，即使在两台不同的机器上，都能够产生相同的随机序列。利用这个特性，我们可以在应用层做很多事。
例如：
时间换空间：只要保存一个种子，就能够通过计算得到一个序列。可以利用这个序列来实现功能。
还原操作：在客户端根据随机序列构建地图，然后在服务器校验，只需要同步种子，就能实现相同场景。
线性同余算法计算速度快，实现简单，但是是伪随机，知道种子后能够预测随机序列，而且随机序列经过一段时间后会循环重复。
所以在安全使用的场景中，不会使用线性同余算法。
二、Linux系统的/dev/random
/dev/random在类UNIX系统中是一个特殊的设备文件，可以用作随机数发生器或伪随机数发生器。Linux内核允许程序访问来自设备驱动程序或其它来源的背景噪声。
发生器有一个容纳噪声数据的熵池，在读取时，/dev/random设备会返回小于熵池噪声总数的随机字节。/dev/random可生成高随机性的公钥或一次性密码本。
若熵池空了，对/dev/random的读操作将会被阻塞，直到收集到了足够的环境噪声为止。这样的设计使得/dev/random是真正的随机数发生器，提供了最大可能的随机数据熵，建议在需要生成高强度的密钥时使用。
为了解决阻塞的问题，还提供了一个设备/dev/urandom，即非阻塞版本。它会重复使用熵池中的数据以产生伪随机数据，输出的熵可能小于/dev/random的。它可以作为生成较低强度密码的伪随机数生成器。
安全使用随机数是比较专业的场景，一般都是使用特定的库或算法，直接调用即可，不要自己造算法。
1. 误用随机的场景
在日常的开发场景中，遇到过几种误用随机的场景，相信很多人还会掉到这些坑里。这里提出来供大家参考。
1.1 多次设置随机种子
线性同余算法，为了让每次程序启动时生成的随机数都是不同的，可以利用srand()函数设置不同的随机种子。一般是设置种子为当前时间，或者进程的进程号等。然后再调用rand()来生成随机数。**srand()只需要开始调用一次，rand()是每次需要随机数的时候调用一次。**
但是有的错误用法，会在常驻进程中使用随机数的时候，把srand和rand配套调用。起不到随机的效果，每一秒钟的随机数都是一样的，而且只取到的线性同余生成的第一个随机数，整体的均匀性也达不到。
1 | srand(time(NULL));//正确使用的方式 |
如果使用上面错误的方式，在一个常驻进程中，会让每秒钟生成的随机数都相同。假如这个随机数是用来给后端选择路由的，会造成同一秒钟的流量都访问到同一个节点，起不到负载均衡的作用。在大型互联网服务中，一秒钟的流量也是巨大的，可能会影响单一节点的服务质量。
1.2 生成范围随机数直接取模
假设一个随机函数rand21()，每次生成的随机数范围是[0, 21)，那么现在要生成[0, 10)的随机数，如何生成。
常见的错误实现方式是
1 | int rand10 = rand21() % 10; |
虽然这种方式得到的数字结果是在[0, 10)之间的。但这种实现方式是错的，因为生成的[0,10)区间的数字不均匀。生成0这两个数字的概率要超过其他9个数字的概率。
rand21产生的[0, 10), [10, 20)取模对应[0,10)是等概率的，会多出来[20, 21)这个区间。直接取模会让结果不均匀。
正确的做法应该是截断这段数值。
1 | int r = 0; |
上面的代码理论上会产生死循环，可能一直生成20这个随机数。在实际工程中可以做个上报，发现超过一定的数值次数，就主动跳出循环，返回失败或设置个默认值。但实际这种概率非常小。
从一种随机数范围的发生器，映射到另一个随机数范围的发生器过程中，不要简单的取模，可能会造成结果不是随机的。
注：除了截断操作，还有拼接的方法，拼出要随机新范围的倍数，再取模。本质和截断一样。
1.3 一定要用随机吗
有时，我们用随机的场景，不是真的为了随机，而是为了让结果更分散。这种场景用随机是一种实现方式。需要了解业务的目的，挑选出适合的实现方式，让方案更简单。
例如路由选择，只要保证节点分布是均匀的，是否可预测并不是必要条件。只要整体的统计分布是均匀即可。存储一个计数器，简单的轮询也是实现均匀分发。
1 | //随机实现路由 |
1 | //轮询实现 |
但是有些场景，用随机反而麻烦。
例如每100万号码存储在一个服务中，对前1000万个号码进行发送push消息操作。如果直接按顺序遍历这1000万个号码，会对这10个存储服务分别造成查询压力。导致修改操作冷热不均。一种方式是每次从号码区间中随机选择一个号码处理，但是要记录号码是否被选择过的状态，需要额外的存储空间。
还一种简单的方法是先按照号段轮询，再按照号码轮询，可以达到不需要存储的实现方式。
伪代码如下：
1 | for(int i = 0; i < 1000000; ++i) |
本质是用到的是映射，让结果均匀，虽然随机也能达到这个目的。
2. 项目中用到的随机场景
在项目中，用好随机可以帮我们提高用户体验，还可以帮我们用时间换空间。
2.1 让用户体验更好的随机
有时虽然程序员懂随机，但是和用户理解的随机不一样，这时程序员要适应用户的感观。
2.1.1 歌曲随机播放
在播放器中，随机播放是一种播放模式。如果简单的调用随机函数，会出现用户接受不了的情况。可能下一首播放的歌曲和当前歌曲是一样的，可能某个子序列会反复播放。
例如有ABCD四首歌。可能会出现AABB、ABABABAB这样的顺序播放。虽然在数学上是达到了随机，但是用户体验不佳。
播放器的「随机播放」实际上是一种打乱播放的意思，可以用的shuffle洗牌算法（可以使用Fisher–Yates shuffle算法）。把原本有序的序列，变成无需无规则的序列，就像洗扑克牌一样。
以下为Fisher–Yates shuffle算法的伪代码，也用到了随机函数。
1 | -- To shuffle an array a of n elements (indices 0..n-1): |
有时还需要考虑专辑、歌手、曲风等因素，可以多一些区分的维度，在每个维度再加上一些随机。可能有些歌曲用户比较爱听，随机到的权重也要高一点。
总之，歌曲的随机播放要根据用户对播放器的预期，来干涉生成序列，不能简单粗暴地直接使用随机来生成。
2.1.2 游戏抽奖
十连抽
在游戏中，为了激励玩家批量购买，会有「10连抽必中稀有物品」的玩法。用户如果一次性消耗10次中奖机会，就会至少中一次稀有物品。
由于已经承诺给用户必中，所以要干预连续10次抽中的情况，如果出现10次都没中大奖，就会给用户替换一个稀有物品。
对于10连抽的场景，要人工干预最后的奖励序列。不能一味的随机。
普通抽奖
在一些国家或地区，会要求软件开发者给出中奖概率。当玩家知道中奖概率后，针对玩家的抽奖就不能完全用随机函数，小于概率值就中，不小于就不中的方法。因为这种方法会让玩家体验不好，以为官方在作弊。
例如：一个装备，抽奖中奖的概率是10%。以普通玩家的想法，抽10次就会中一次，如果抽20次才中一次，玩家也勉强接受。但是如果抽100次，一次都不中，大多数玩家都接受不了的，一方面会质疑游戏的公平性，也会因为体验不好而离开。另外一边与运气不好的玩家相反，还有些运气好的玩家，可能抽10次，就中了5次，消耗了过多的奖品。
在一些大DAU的游戏中，运气好的玩家和运气不好的玩家，出现的概率还挺高的。
运气不好的玩家。每次抽中奖概率10%，抽100次都不中的概率是$(1-10%)^{100}=2.656*10^{-5}$大概万分之二。如果一天有1万个玩家抽了100次奖，平均有2个人是100次都不中。
运气好的玩家。10%中奖，抽10次中5次的概率是$C(10, 5) * 10%^5*90%^5 = 0.0014880348$，大概是万分之15左右，是运气不好的玩家概率的7、8倍。
为了让玩家感观上是随机并且公平，也采用洗牌算法，对每个玩家生成一个奖品等级的中奖序列。把序列打乱，按次序给玩家，每次根据奖品等级生成该等级的奖品发给玩家。
2.1.3 游戏武器暴击
在游戏中的武器装备也涉及到概率，例如一把屠龙刀，暴击概率提升到30%。玩家的感觉也是在10刀里，大概率会有3刀是暴击的，在100刀里要有30几刀的暴击。
暴击和抽奖遇到的问题类似，都是玩家对概率的理解和程序员理解不一致。因为按照独立事件的概率，可以连续100次都不暴击，也可以连续3-4刀每次都暴击。连续不暴击会伤害持有武器玩家的体验，连续暴击会伤害和持有武器对战玩家的体验。
暴击在游戏中的不确定性会增加游戏的乐趣性。和抽奖不同，偶尔多一两次，对于游戏来说玩家也是可以接受的，不会像抽奖如果密集中奖会影响体验。在暴击的随机，可以参考暴雪的随机公式（PRD）。
$$P(N) = C × N$$
P(N) 表示在第N次攻击之后某个动作发生得概率，N表示第N次修正概率后得攻击次数（最小值为1），C表示暴击发生的初始概率以及每次攻击之后概率的增量，是个简单地线性关系。当N足够多的时候，P（N）总会趋向于1。
在编写程序时，先设置好C，通过C来增加下一次效果触发的几率。C会作为初始概率，比效果说明中的概率要低。当效果没有触发时，会不停地积累N，让P(N)逐渐增加接近100%。一旦效果触发了效果，计数器N就会重置。
例如一把武器有25%暴击，把初始概率C设置为8.5%。那么第一次攻击，他实际上只有大约8.5%几率触发暴击，随后每一次失败的触发会增加大约8.5%触发几率，于是到了第二次攻击，几率就变成大约17%，第三次大约25.5%，以此类推，在一次暴击触发后，下一次攻击的触发几率又会重置到大约8.5%，那么经过一段时间之后，暴击几率的平均值就会接近25%。
采用PRD随机公式保证在有限次数能够实现暴击，并且整体期望和独立事件的期望接近。
2.2 时间换空间
2.2.1 游戏作弊校验
在一些消除类的单机游戏中，玩家游戏在客户端本机进行，结束后上传分数给服务器。服务器会根据玩家的分数进行排行，并给予一些奖励。为了让玩家能够有良好的体验，在游戏过程中，所有操作都在本地进行。为了防止作弊，在玩家上传分数后进行检测。
如何做到校验玩家游戏是否作弊呢？方法也比较简单，把游戏数据上传，在服务器重放玩家操作，根据行为判断是否作弊。但是这里有一个难点，游戏开始下发地图的时候，如果把游戏中所有的随机事件，例如机关的摆放，NPC的随机施法都生成好下发到客户端，会消耗很多流量，影响启动速度。
线性同余算法，不同机器相同种子，可以产生相同序列的特性，很好地支持了这个场景。在游戏开始时，通过加密通道，把随机种子下发给客户端，客户端按照随机种子生成地图和操作。结束游戏，客户端上传用户操作，服务器收到操作序列后，重新生成地图和地图上的机关操作，然后快速执行玩家操作。最终校验两种结果是否一致。通过种子的传递，只要算法一致，就能够重放，大大降低了带宽和同步数据的复杂度。
2.2.2 节约存储成本
在互联网早期的一些安全充值的场景中，为了验证充值卡的归属。用户充值时，需要输入充值卡背面的密保卡片中的一些数字，校验卡片归属。因为充值卡后面的密保矩阵是被覆盖的，如果刮开会影响销售，只有购买的人才能看到。一般是一个10*10的数字矩阵。
最直接设计方法是，可以给每个充值卡生成一个随机的100个数字序列，然后每次针对用户的输入进行匹配。如果矩阵每个数字用两个字节存储，1张卡要耗费200个字节。如果发行了1亿张卡，就要20G的存储空间。
但是如果每张卡只存一个种子值，当用户来校验时，根据种子生成100个数字来校验，效果是一样的。假设一个种子4个字节，1亿张卡只需要400M存储就可以了。可以都load到缓存中加快速度。
利用随机空间换时间，本质是存储元数据，利用算法的生成规律，保证能反复重放序列。可以达到减少同步信息，降低存储量的效果。虽然现在带宽和存储的成本越来越低，但是掌握了这种方法，在一些特殊场景中能够提供奇妙的解决方案。
3. 小结
随机在互联网应用的十分广泛，我们根据场景采用不同的使用方式。
在安全相关的专业算法领域，用已有的算法和工具，不要去造轮子。在Linux系统中使用/dev/random读取随机数。
在应用层，使用伪随机函数例如线性同余算法，快速生成随机数，满足大多数生成随机数的需求。
在游戏、歌曲等更高层应用的领域，用户对随机的理解和数学上的随机不太一致。要区分用户是要整体分布更均匀，还是让结果充满随机性增加乐趣。根据场景适时调整，修改随机数的分布，而不是默认采用独立事件生成随机数，往往能够达到更好的效果。
算法是固定的，在实现业务的时候，要从实际角度出发，选择最适合的实现方式，来满足业务需求。做到活学活用。