随机数与并发

首先给出结论:

• 如果对随机数的数值本身敏感，那么应该在每次程序启动时，使用时间戳初始化随机数
• 在高并发环境下，无脑用随机数，性能很差

伪随机数

随机数分为伪随机数与真随机数，在很多情况下，考虑到性能问题，我们实际上使用的都是伪随机数

对于伪随机数算法而言，我们期望的就是输入一个数，而后返回一个近似随机的结果。这里的近似随机指 “输出的结果在不知道算法本身的情况下难以预测”

由于计算机中数字本身是有限的，因此实际上是要求相当于: 将一个数输入到算法中，将输出再次送入算法，最终可以得到所有的数，并且每个数只出现一次。同时在任意区间内，每个数位是 11 或 00 的概率都应该是 5050%。这也是 “线性反馈移位寄存器” 的要求（实际上，是生成除去 00 之外的所有数）

以通过时间作为种子为例，尽管短时间内可能时间相差不大，但只要确保时间不同，由于伪随机数具有“均匀”的特点，那么实际上即使两个输入相差不大，但是输出仍然会有很大的差异，这样就实现了“随机”。

从这里可以很自然发现一个问题，如果种子相同，那么生成的随机数序列是固定的。这很容易验证

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	fmt.Println(rand.Int())
	for i := 0; i < 3; i++ {
		func(i int) {
			rng := rand.New(rand.NewSource(1))
			fmt.Println(i, rng.Int())
			fmt.Println(i, rng.Int())
			fmt.Println(i, rng.Int())
		}(i)
	}
}

5577006791947779410
0 5577006791947779410
0 8674665223082153551
0 6129484611666145821
1 5577006791947779410
1 8674665223082153551
1 6129484611666145821
2 5577006791947779410
2 8674665223082153551
2 6129484611666145821

无论如何验证，程序的输出都不会变化。这是因为 Go 默认的种子就是 11。

因此，通常我们需要使用当前的时间戳来初始化随机数种子，确保程序每次取得的结果都是不一致的（特殊情况下，这种固定顺序的算法也会属于一个 feature，比如要进行验证码校验，传递随机数种子后，只需要保证生成和校验过程中计算顺序一致，就可以得到一个确定的结果，同时用户很难去“破解”验证码）

对于用户而言，这些伪随机数充斥着魔法数字——虽然能用，但是无法直观地理解。不过实际上都是移位寄存器的设计思想

#include <stdint.h>

struct xorshift32_state {
  uint32_t a;
};

/* The state word must be initialized to non-zero */
uint32_t xorshift32(struct xorshift32_state *state)
{
	/* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
	uint32_t x = state->a;
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return state->a = x;
}

struct xorshift64_state {
  uint64_t a;
};

uint64_t xorshift64(struct xorshift64_state *state)
{
	uint64_t x = state->a;
	x ^= x << 13;
	x ^= x >> 7;
	x ^= x << 17;
	return state->a = x;
}

struct xorshift128_state {
  uint32_t a, b, c, d;
};

/* The state array must be initialized to not be all zero */
uint32_t xorshift128(struct xorshift128_state *state)
{
	/* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
	uint32_t t = state->d;

	uint32_t const s = state->a;
	state->d = state->c;
	state->c = state->b;
	state->b = s;

	t ^= t << 11;
	t ^= t >> 8;
	return state->a = t ^ s ^ (s >> 19);
}

Go 随机数实现思路

Go 的 math/rand 包实现了一套伪随机算法，其思路如下

伪随机数生成器

带锁伪随机数生成器

Go 随机数对象

Go 全局随机数对象

随机int

随机float

...

首先是底层的伪随机数生成器，维护上一个生成结果作为输入，每次生成新值并更新数据。伪随机数会被封装成为带锁伪随机数生成器，作为并发场景下的保护。
为了方便使用，使用 Go 随机数对象封装了各种特定格式的随机数输出函数，同时默认创建了一个全局的伪随机数，方便直接调用。

在这里就引入了一个问题: 随机数是带锁的

很容易明白，如果没有锁，在高并发情况下，可能会导致这样的问题，短时间内多个线程请求伪随机数生成新随机数，由于种子还未更新，因此这段时间内生成的随机数完全相同！同时由于每次都需要更新，无论是读写锁还是信号量，都无法很好地解决这个问题。

这也就导致了一个问题: 在高并发场景下，进行随机数计算，可能会花费大量的时间等待锁

高性能随机数

在高并发场景下，要实现高性能随机数可以使用 valyala/fastrand。这个库的原理是使用 sync.Pool 来维护随机数池。每个随机数生成器都使用初始化时的时间作为种子，确保各不相同。每次需要获取随机数时，从池子中认领一个随机数生成器，生成随机数后再还回随机数池。

得益于 sync.Pool 本身的高效实现，这里获取随机数性能很高。

当然，同样的思路，我们也可以将 Go 原本的随机数生成器使用 sync.Pool 维护。

使用 benchmark 可以得到如下结果，从上到下分别是 Go 原生 random、原生 random + pool、fastrand 包分别并发获取 1e6 个随机数的结果。

goos: linux
goarch: amd64
pkg: temp
cpu: Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz
BenchmarkRandom-4                      4         348095650 ns/op
BenchmarkRandomPool-4                  4         303406350 ns/op
BenchmarkFastRand-4                    4         256881850 ns/op
PASS
ok      temp    7.931s

参考资料

• valyala/fastrand
• Go: 谨慎使用 math/rand 包中的默认随机数函数 - Huang Huang 的博客 (mozillazg.com)
• Golang随机数生成和原理 | JWang的博客 (wangbjun.site)
• Xorshift - Wikipedia
• A fast alternative to the modulo reduction – Daniel Lemire's blog