接上篇：https://developer.aliyun.com/article/1225741?spm=a2c6h.13148508.setting.28.595d4f0eudDbz0
二、 关于随机
抽奖最需要保证的，其实是公平的产生抽奖结果，而这个公平，则来自于足够随机的抽奖算法，而抽奖算法不论怎么设计，常常依赖于计算机随机数的发生。不妨先来看一看万仞之基础——随机数是怎么产生的。
1. 伪随机数与其产生——线性同余
为了效率和成本计，现在常用的随机数的产生方式往往是伪随机数，最广为流行的就是线性同余产生器，其本质非常直白：
不难看出，其中的a、b、p的取值，就是是否能产出随机分布的数据根本所在。基本数论的常识告诉我们，这个同余式的取值必定在[0,p-1]的范围内封闭，并且拥有最大为p的周期，或者是多个较小但互不重合的周期构成，当其周期为p时，其式就成为了0到p-1的一个离散排列。
之所以这个看似简单的式子，能够成为随机数的生成方法，正是因为模数运算的良好特性，一来其在周期内绝不会出现重复结果，二来其分布也相对均匀。可以将f(x)/p视为[0,1)范围内的平均分布。
2. 参数取值
所以，我们的第一个问题，就必然是探索，在参数满足什么条件时，能将这个函数的周期尽可能的扩大，以更有效的利用其周期特性，挖掘这个式子产出的随机性。
我们先从模数p开始，不论其他，光凭数学直觉就会让人下意识的想取一个大素数，以此轻易攫取优越的分布特性和天然形成的宽周期。
但是，我们要注意到，伪随机数作为一个非常底层的方法，其存在本身就是为了效率的，取模操作虽然不算慢，但此时就会有一个更加优越的模数跃入眼帘，那就是2^n——不但可以直接将取模操作退化为移位和与操作，也可以很轻松的理解随机数的取值范围。当然，这个周期比起素周期也更方便均分以转化为其他范围的随机函数。
当然，模数不是素数的情况下，就对a、b的取值有了更大的约束。为了取得一个满周期序列的生成方法，The Art of Computer Programming中论证了其充要条件，也是现在大部分线性同余产生器的构造依据：
• b与p互质
• c=a-1是p所有素因子的倍数
• 若p是4的倍数，c也是4的倍数
我们可以看到，这其中对加数b的约束其实非常小，于是在gcc中，就比较随意的选择了个12345，java中干脆是个小素数11。而对于a的取值，在已知我们取模数为2^n时，就非常容易得知其约束条件：a-1是4的倍数。
3. 实现时的考量
现在我们满怀欢喜的得到一个满周期序列的生成方法，似乎只需要按照某些特性去选一些优秀的生成参数就可以跑起来成为一个经典库了。但事情还没有这么简单。
刚才我们的选择还遗留了一个问题，我们往往不是直接使用一个全模数范围的随机，而是由大周期的随机数取模转化为一个更小的周期来随机——只要大范围的随机函数能保证概率均等，取模后自然也是一个均匀分布的函数：
——但是以上方式有一个天然的缺陷，当我们的模数m与2的幂次相关时，其低位随机性并不是很好——低位周期的分布也会在这个小周期上呈现周期，形式化地说，就是：
也总是一个满周期序列，所以，无论怎么去改变参数分布，在模数非素的情况下，随机的分布都会呈现一个特别均匀的形式，当我们想取得范围特别小时，比如我们只需要0-1的整数，这个算法就会持续输出0、1、0、1、0、1、0、1。当然，它仍然是满周期的，但是呈现出的结果完全违背了我们对于“随机”这件事的直觉，可预测性太强了。
这个时候，我们重新回顾一下，就会发现，我们想要的其实不是满周期的随机性，当周期非常小的时候，我们更期待的是超越本周期的随机性分布，比如，给0-1的随机安排一个00101110这样的周期序列，这个要求在本周期的计算比较难达成的，但是既然这个小周期是由一个更大的周期序列摘取到的，我们就能够将大周期的随机性反映到小周期当中去。
很多平台的实现当中，是舍弃这些随机性不强的低比特位，换为截取高位比特位作为结果序列，这样当然会导致该序列一些很好的数列特性消失，但是从而也增强了其本身的随机性。
比如在java的实现中：
private final AtomicLong seed; private static final long multiplier = 0x5DEECE66DL; private static final long addend = 0xBL; private static final long mask = (1L << 48) - 1; protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; //这里有一把自旋锁，保证每次输出不相同 do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) & mask; } while (!seed.compareAndSet(oldseed, nextseed)); //这里截取的是高位比特值 return (int)(nextseed >>> (48 - bits)); }
4. 使用中的细节
其实到这里，随机数的生成问题我们基本上已经摸清楚了，既然我们知道了随机数的发生过程，其实就很容易抓住重点，那就是随机数种子才是最为重要的，随机数只是一种生成过程，甚至说理解为一种可持续的hash方式也无不可。随机数的随机性完全来自于你随机数种子的随机性。所以在习惯中，我们常常会使用当前毫秒时间作为种子，而在java里的默认种子生成如下：
public Random() { this(seedUniquifier() ^ System.nanoTime()); } private static long seedUniquifier() { // L'Ecuyer, "Tables of Linear Congruential Generators of // Different Sizes and Good Lattice Structure", 1999 for (;;) { long current = seedUniquifier.get(); long next = current * 181783497276652981L; if (seedUniquifier.compareAndSet(current, next)) return next; } } private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);
可以看到，为了避免不传种子的情况出现，java默认提供了一个种子，这里也有把自旋锁，加上随机数生成本身的那一把，可以看到随机数发生在多线程的情况是会导致竞争的（虽然损耗很低），所以在阿里巴巴开发规约中会推荐使用ThreadLocalRandom中的随机数来生成。
如果你还记得上面的内容，还可以看出，这个种子本身也是个线性同余发生器发出的随机数，只不过特殊一点，是b=0情况下的乘法发生器。这种发生器的周期必定无法满周期，但是对于生成“随机种子的因子”这种情况，够用。
有点黑色幽默的是，虽然这里堂而皇之的标明了这里的常数来源于Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure 这篇论文，但是实际上181783497276652981这个数并不存在于论文推荐的表现最佳的因子中，看上去这里是一个Typo——数字开头少打了个1，但是实际上大家也知道了，一个“不那么完美”的分布其实也没那么有所谓。
随机数的生成原理并不复杂，整体的实现也是非常简洁直白的，但这其中又包含了很多精巧的构思，最终达到了一种效率与结果的统一，技术的美感往往就分布在这些简单而不失优雅的实现当中。当然，任何算法都有自己的适用范围，伪随机数在密码学意义上并不足够安全，如果是对于随机性有着强需求的场景，我们应当使用其他的随机数生成方法。
接下篇：https://developer.aliyun.com/article/1225739?groupCode=idlefish
