Golang随机数生成和原理

发表于 | 更新于 | 分类于 | 浏览数
| 字数统计 3.1k

说到随机数不得不提一下真随机和伪随机，一般来说，真随机是指通过物理现象产生的，比如掷骰子、双色球摇奖（前提是机器没问题）、同位素衰变等等，其特征是不可预测、不可重现。而伪随机数一般是通过软件算法产生，看上去是随机的，但是无论是什么算法函数，都会有输入和输出，如果你能得到其输入，自然也可以预测其输出。

实际应用中，伪随机在计算机软件中十分常见，大部分编程语言的函数库里面都有类似 random() 这样的内置函数，可以快速的产生随机数。而真随机数主要应用于安全要求特别高的加密应用中，一般都会有专门的设备用于产生随机数，而本篇文章是给大家介绍一下Golang里面如何生成随机数。

1.math/rand伪随机

这个库是Golang里面用于产生伪随机数的包，我们首先看一下其注释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Package rand implements pseudo-random number generators.
//
// Random numbers are generated by a Source. Top-level functions, such as
// Float64 and Int, use a default shared Source that produces a deterministic
// sequence of values each time a program is run. Use the Seed function to
// initialize the default Source if different behavior is required for each run.
// The default Source is safe for concurrent use by multiple goroutines, but
// Sources created by NewSource are not.
//
// Mathematical interval notation such as [0, n) is used throughout the
// documentation for this package.
//
// For random numbers suitable for security-sensitive work, see the crypto/rand
// package.

这里我简单翻译解读一下：这是一个伪随机数生成器，对于高阶函数比如Float64或者Int，每次运行的时候它使用一个默认共享源来产生一个随机数。

如果你需要每次运行产生的结果不一样，那么就需要使用Seed函数初始化默认源。默认的源是协程并发安全的，但是使用NewSource函数产生的并不是。

最后，对于安全十分敏感的工作，推荐使用crypto/rand包。（注：因为这个包可以产生真随机数）

这个包内置的公开函数特别多，乍一看，有Int63、Int31、Int、Int63n、Int31n…等等，这名字看上去有点凌乱！下面咱们来细说一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func main() {
    // 下面这些高阶函数都是使用的全局源
    fmt.Printf("%v\n", rand.Int63()) // 产生一个0到2的63次方之间的正整数,类型是int64
    fmt.Printf("%v\n", rand.Int63n(100)) // 产生一个0到n之间的正整数,n不能大于2的63次方，类型是int64
    fmt.Printf("%v\n", rand.Int31()) // 这个和前面的区别就产生的是int32类型的整数
    fmt.Printf("%v\n", rand.Int31n(100)) // 同上

    // 这个比较有意思了，它至少产生一个32位的正整数，因为int类型在64位机器上等于int64，在32位机器上就是int32
    fmt.Printf("%v\n", rand.Int())
    fmt.Printf("%v\n", rand.Intn(100)) // 同上

    fmt.Printf("%v\n", rand.Float32()) // 产生一个0到1.0的浮点数，float32类型
    fmt.Printf("%v\n", rand.Float64()) // 产生一个0到1.0的浮点数，float64类型
}

总结一下：Int63和Int31的区别就是位数，一个是32位类型，一个是64为类型，带n的就是产生一个0-n之间的该类型的数，看上去还是挺简单的，但如果你多次运行这段代码，你会发现结果却一直没变，一直都是固定的，不是说好的随机吗？

1
2
3
4
5
6
7
8
5577006791947779410
51
1427131847
59
3916589616287113937
18
0.06563702
0.15651925473279124

这个可能就不是你想要的结果了。。。原因正如上面所说的是因为它们默认使用全局的源，而这个源的默认种子是固定的1

1
var globalRand = New(&lockedSource{src: NewSource(1).(*rngSource)})

为了每次运行产生不同的结果，我们需要使用一个随机数当种子来初始化源，最常见的做法就是使用当前时间戳：

1
rand.Seed(time.Now().UnixNano())

如果你真的要追求极致性能的话，你可能需要自己New一个rand，因为默认的Source为了实现并发安全使用了一个全局的排它锁，必然会带来性能损耗，如果确实特别在意这点性能消耗的话，可以通过定义一个你的包共享的或者结构体实例共享的 Rand 实例来优化锁的性能消耗（最小化锁的粒度，不跟其他包/代码竞争这个锁）。

1
2
3
4
5
6
7
8
func randNew() {
    r:= rand.New(rand.NewSource(time.Now().UnixNano()))
    fmt.Printf("%v\n", r.Intn(100))
    fmt.Printf("%v\n", r.Intn(100))
    fmt.Printf("%v\n", r.Intn(100))
    fmt.Printf("%v\n", r.Intn(100))
    fmt.Printf("%v\n", r.Intn(100))
}

但是请注意这个rand并不是并发安全的，如果在并发环境下使用，需要自行加锁！

2.源码分析

下面咱以一个最常用的Intn函数为例分析其实现过程：

1
2
3
4
// Intn returns, as an int, a non-negative pseudo-random number in [0,n)
// from the default Source.
// It panics if n <= 0.
func Intn(n int) int { return globalRand.Intn(n) }

(1)初始化全局源

首先，这个函数调用了一个包全局变量globalRand的Intn函数，这个变量之前提到过：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var globalRand = New(&lockedSource{src: NewSource(1).(*rngSource)})

type lockedSource struct {
    lk  sync.Mutex
    src *rngSource
}

type rngSource struct {
	tap  int           // index into vec
	feed int           // index into vec
	vec  [rngLen]int64 // current feedback register
}

const rngLen = 607

func NewSource(seed int64) Source {
    var rng rngSource
    rng.Seed(seed)
    return &rng
}

其中lockedSource包含一个排它锁和一个rngSource，这个rngSource有2个int成员和一个固定大小为607的int64类型的数组，具体啥用俺也不清楚，但其中这个Seed函数非常关键：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Seed uses the provided seed value to initialize the generator to a deterministic state.
func (rng *rngSource) Seed(seed int64) {
    rng.tap = 0
    rng.feed = rngLen - rngTap

    seed = seed % int32max
    if seed < 0 {
        seed += int32max
    }
    if seed == 0 {
        seed = 89482311
    }

    x := int32(seed)
    for i := -20; i < rngLen; i++ {
        x = seedrand(x)
        if i >= 0 {
            var u int64
            u = int64(x) << 40
            x = seedrand(x)
            u ^= int64(x) << 20
            x = seedrand(x)
            u ^= int64(x)
            u ^= rngCooked[i]
            rng.vec[i] = u
        }
    }
}

// seed rng x[n+1] = 48271 * x[n] mod (2**31 - 1)
func seedrand(x int32) int32 {
    const (
        A = 48271
        Q = 44488
        R = 3399
    )

    hi := x / Q
    lo := x % Q
    x = A*lo - R*hi
    if x < 0 {
        x += int32max
    }
    return x
}

这里有很多固定的常量，比如rngTap是273，rngLen是607，还有一个rngCooked是一个大小为607的int64数组，里面是固定写死的数值，内容看上去分布很均匀，可能是作者精心挑选的一些整数，我也不知道有没有什么讲究…

虽然看不出这个算法有什么精妙的地方，但是我们可以看出来经过一顿操作，其最终目的就是把rngSource里面的vec填充满随机的整数。同时也可以得出一个结论，如果Seed的参数是固定的，其得到结果也是固定的，这也就是为什么默认源多次运行结果都一样。

(2)产生随机数

当我们初始化了这个源之后，调用 Intn() 函数之后过程如下：

1
2
3
4
5
6
7
8
9
10
11
// Intn returns, as an int, a non-negative pseudo-random number in [0,n).
// It panics if n <= 0.
func (r *Rand) Intn(n int) int {
    if n <= 0 {
        panic("invalid argument to Intn")
    }
    if n <= 1<<31-1 {
        return int(r.Int31n(int32(n)))
    }
    return int(r.Int63n(int64(n)))
}

首先，其转手做了一道判断，如果小于int32的范围则调用Int31n，否则调用Int63n，十分机智！接下来咱们以Int31n为例继续分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Int31n returns, as an int32, a non-negative pseudo-random number in [0,n).
// It panics if n <= 0.
func (r *Rand) Int31n(n int32) int32 {
    if n <= 0 {
        panic("invalid argument to Int31n")
    }
    if n&(n-1) == 0 { // n is power of two, can mask
        return r.Int31() & (n - 1)
    }
    max := int32((1 << 31) - 1 - (1<<31)%uint32(n))
    v := r.Int31()
    for v > max {
        v = r.Int31()
    }
    return v % n
}

这里我有一点不明白，为什么 n <= 0 你就直接pannic了呢？？？这一点有点伤，按理说返回一个error比较友好！

接下来就是一个按位与操作，如果 n&(n-1) == 0，意思就是说n是2的幂次方，也就是说是2、4、8、16…等数，那么就返回 r.Int31() & (n-1)，这是啥意思呢？

1
2
3
4
5
1  的二进制是 1
3  的二进制是 11
7  的二进制是 111
15 的二进制是 1111
...

当n是2的幂次方的时候，n-1的二进制全部是1，这时候任何一个数 &(n-1) 得到的结果必然小于n。为什么呢？大家回忆一下与预算符的功能： 只有2个位都为1，结果才是1。举个例子，假设Int31返回一个数 54328 & 15的运算过程如下：

1
2
3
4
5
1101010000111000（十进制54328）
&
0000000000001111（十进制15）
=
0000000000001000（十进制8）

这一步确实非常巧妙，继续往下看Int31这个函数，经过多次代码追踪发现Int31是调用了Int63位移转换得来。

1
2
// Int31 returns a non-negative pseudo-random 31-bit integer as an int32.
func (r *Rand) Int31() int32 { return int32(r.Int63() >> 32) }

而Int63最终是调用了Uint64函数，这个函数的作用就是从之前初始化的Source里面的 vec 数组里面取出对应 tap 和 feed 索引的值加在一起返回，同时还会更新tap和feed。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Uint64 returns a non-negative pseudo-random 64-bit integer as an uint64.
func (rng *rngSource) Uint64() uint64 {
    rng.tap--
    if rng.tap < 0 {
        rng.tap += rngLen
    }

    rng.feed--
    if rng.feed < 0 {
        rng.feed += rngLen
    }

    x := rng.vec[rng.feed] + rng.vec[rng.tap]
    rng.vec[rng.feed] = x
    return uint64(x)
}

从我个人测试的结果来看，其随机的结果分配还是比较均匀的，但是由于其算法局限性，重复率还是比较高的，经过我测试随机0-1000，重复1000次，在这1000次结果里面大概有300次结果是和之前一样的，也就是重复出现多次。

3.crypto/rand真随机

为什么说这个包是真随机呢？因为其是读取了硬件信息而来，根据这个包的注释可知，对于不同平台其来源也不一样，但官方的说法是加密安全的随机数生成器，即使不是严格意义上的真随机数，但其安全性非常高。

1
2
3
4
5
6
7
8
// Reader is a global, shared instance of a cryptographically
// secure random number generator.
//
// On Linux and FreeBSD, Reader uses getrandom(2) if available, /dev/urandom otherwise.
// On OpenBSD, Reader uses getentropy(2).
// On other Unix-like systems, Reader reads from /dev/urandom.
// On Windows systems, Reader uses the CryptGenRandom API.
// On Wasm, Reader uses the Web Crypto API.

这个包提供的函数功能十分有限，根据其注释可得知，在Linux平台下，当使用 getrandom() syscall，在int32位的机器上面上每次最多可以获取2^25-1个字节的数据。

下面这段代码演示的就是读取32个字节的数据，然后以base64编码的形式打印出来，其实就是一个UUID。

1
2
3
4
5
6
7
8
9
func main() {
    b := make([]byte, 32)
    _, err := rand.Read(b)
    if err != nil {
        panic(err)
    }
    fmt.Printf("%s\n", base64.StdEncoding.EncodeToString(b))
}
// o7yNCdWvxqsaD8JaeF2wCrR+Gp0HsFxvd9Pasb4ecK8=

但是如果你想要的是一个[0,n)的整数可以采用下面这种写法：

1
2
3
4
5
n, err := rand.Int(rand.Reader, big.NewInt(100))
if err != nil {
    panic(err)
}
fmt.Printf("%d\n", n)

4.真伪随机数性能

在实际编程开发中，大部分时候我们用的都是伪随机数，主要因为速度快，真随机数由于涉及物理硬件，生成速度慢很多，有多慢呢？咱们可以来个测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

import (
    crand "crypto/rand"
    "math/big"
    "math/rand"
    "testing"
)

func BenchmarkRand1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        rand.Intn(1000)
    }
}

func BenchmarkRand2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        crand.Int(crand.Reader, big.NewInt(1000))
    }
}

结果如下，可以看到差距不是一般大，是上百倍的差距：

1
2
3
4
5
BenchmarkRand1
BenchmarkRand1-12    	79847034	        14.8 ns/op
BenchmarkRand2
BenchmarkRand2-12    	  595071	      1985 ns/op
PASS

所以在一些对安全和效率要求都非常高的场景下，人们会采用一种专用的随机数生成硬件，里面有专门针对随机数生成优化的设计芯片，这样可以大大提高随机数生成效率。