Sometimes "math/rand" Uses Weighted Dice
Tags: go, random, prng
Published: 2023-06-19 03:39:28

<!--
Titles:
- When Seeding "math/rand" Fails
- "math/rand" is Less Random Than You Think
- Don't start 100,000 Go Processes with "math/rand"
- Go's "math/rand" Can Act Like Weighted Dice

Audience:
Adam Ryman

Points to communicate:
- Seeding the "math/rand" Source or package with the same value generates the same number sequence.
- The "math/rand" seed method(s) truncate the input in a way that can cause repeating values unexpectedly frequently.
- Starting in Go 1.20, "math/rand" is automatically seeded at startup.
- About 2/100,000 seed values resolve to the same "math/rand" sequence

Recommendations:
- "math/rand" is great for most use cases, but sometimes you need an alternative, like "x/exp/rand" (others?)
- Use "x/exp/rand" (or others?)
- Don't depend on "math/rand" for globally-unique values

Sources:
- https://github.com/golang/go/issues/54880 - math/rand: seed global generator randomly
- https://github.com/golang/go/issues/36133 - math/rand: documentation on rng.go is lacking important context and information
- https://github.com/golang/go/issues/21835 - proposal: use PCG Source in math/rand for Go 2

Images:
- https://www.pexels.com/photo/closeup-photo-of-two-red-dices-showing-4-and-5-965875/
- https://www.pexels.com/photo/yelling-formal-man-watching-news-on-laptop-3760778/
-->

Go's [math/rand](https://pkg.go.dev/math/rand) package provides pseudo-random number generators, or PRNGs, that are used in a ton of Go software. I've personally used the `math/rand` package in the vast majority of Go projects I've worked on. It's great for generating IDs, shuffling lists, introducing jitter in timing, and lots of other things.

> ⚠️ `math/rand` should not be used for security-sensitive purposes. For that, use [crypto/rand](https://pkg.go.dev/crypto/rand) instead.

<!-- TODO: Remove?
Pseudo-random number generators, or PRNGs, are great. You can use them to generate random strings, pick from a list of options, procedurally generate game levels, and lots of other applications. (Something about security?)
-->

As with any PRNG, the number sequence appears random but is actually deterministic and depends on the [seed](https://en.wikipedia.org/wiki/Random_seed) value. As a result, it's possible to get `math/rand` to generate the exact same number sequence by giving it the same seed value.

Let's look at an example:

```go
rand.Seed(1)
fmt.Println(rand.Int63(), rand.Int63())
// Output: 5577006791947779410 8674665223082153551

rand.Seed(1)
fmt.Println(rand.Int63(), rand.Int63())
// Output: 5577006791947779410 8674665223082153551
```
{% cta https://go.dev/play/p/r6OLyKo6hv7 %} Go Playground {% endcta %}

We used the same seed and got the same random numbers each time, just like we expected! Now let's try using different seed values:

```go
rand.Seed(1)
fmt.Println(rand.Int63(), rand.Int63())
// Output: 5577006791947779410 8674665223082153551

rand.Seed(2)
fmt.Println(rand.Int63(), rand.Int63())
// Output: 1543039099823358511 2444694468985893231
```
{% cta https://go.dev/play/p/4_2Ki3FC-td %} Go Playground {% endcta %}

Great, we got different numbers! Let's try two more seed values:

```go
rand.Seed(243697394791045426)
fmt.Println(rand.Int63(), rand.Int63())
// Output: 5463449640670714849 6224151428804650039

rand.Seed(-6474076765971414729)
fmt.Println(rand.Int63(), rand.Int63())
// Output: 5463449640670714849 6224151428804650039
```
{% cta https://go.dev/play/p/UT7U9dXtI8i %} Go Playground {% endcta %}

Oops, that's not right. We gave it totally different seed values, but the sequences are the same. What happened?

It turns out that `math/rand` will sometimes generate the same number sequence for different seed values. The [rand.Seed](https://pkg.go.dev/math/rand#Seed) function docs describe the unexpected behavior:

> Seed values that have the same remainder when divided by 2<sup>31</sup>-1 generate the same pseudo-random sequence.

That's not great, that means `math/rand` might generate the same number sequence even if our seed values don't repeat.

![Yelling formal man watching news on laptop](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z8h1gbeokfsemjsjfxvm.jpg)
> Why'd you do that `math/rand`?! You're supposed to be (pseudo) random!

## Automatic Seeds in Go 1.20

If you've looked at the [rand.Seed](https://pkg.go.dev/math/rand#Seed) documentation recently, you may have noticed that the function is deprecated. In fact, starting with Go 1.20, the package-global `math/rand` PRNG is automatically initialized with a random seed value. Great, so we can ignore this seed nonsense and just live our lives, right?

Mostly yes. However, it's still possible to run into problems with the new `math/rand` automatic seed values. I found that if you start about 100,000 processes that generate numbers with `math/rand` using the automatic seed values, two of those processes will probably generate the same sequence.

{% details Why 100,000? (click for details) %}
This is an example of the [birthday paradox](https://en.wikipedia.org/wiki/Birthday_problem), which is the counterintuitive fact that you're likely to get a repeating value in a series of random numbers much sooner than you might expect. In this case, `rand.Seed` basically truncates the `int64` input into 31 bits of entropy. Based on that, we can calculate that we have about a 90% chance of getting a repeating value after generating 100,000 random 31-bit numbers.
{% enddetails %}

Granted, most use cases don't require starting 100,000 processes. However, it could cause problems if, for example, you deploy an agent to every container in a very large server fleet and you need those agents to generate different number sequences.

## Some Possible Fixes

If that is a problem for us, is there anything we can do about it? Yes!

### Use a different PRNG library.

One solution is to use a different PRNG that doesn't suffer from the same unexpected behavior as `math/rand`. [Go issue #36133](https://github.com/golang/go/issues/36133) suggests a possible alternative is the [golang.org/x/exp/rand](https://pkg.go.dev/golang.org/x/exp/rand) module, which implements a different type of PRNG. Importantly, the `x/exp/rand` module does not truncate seed values, so is less likely to cause collisions between seeds. However, it is not automatically seeded like `math/rand`, so you must provide a seed value yourself!

### Use `crypto/rand` instead.

Another option is to use the [crypto/rand](https://pkg.go.dev/crypto/rand) package instead, which uses the operating system's or runtime's cryptographically-secure randomness source. Cryptographically-secure RNGs are typically slower than PRNGs, but if you don't need to generating a ton of values, then using `crypto/rand` can be a simple option.

### Partition the PRNG values.

A more complex solution is to "partition" the `math/rand` output with a value that is different for each process. For example, consider the following code that generates hexadecimal strings to use as request IDs. It reads a random value from `crypto/rand` at startup and appends that to all values read from `math/rand`, reducing the probability of collisions between processes:
```go
var partition uint32

func init() {
	err := binary.Read(cryptorand.Reader, binary.LittleEndian, &partition)
	if err != nil {
		panic(err)
	}
}

func newRequestID() string {
	return fmt.Sprintf("%016x%08x", rand.Uint64(), partition)
}
```
{% cta https://go.dev/play/p/hMm1SgsXWT- %} Go Playground {% endcta %}

> ⚠️ Adding partitions to pseudo-random values can change the distribution of values, so it's extremely important to understand how it affects your use case. For example, a new distribution of values might introduce "hotspots" in a database index that wasn't a problem without the partition.

## Additional Reading
* [Go issue #54880](https://github.com/golang/go/issues/54880) - math/rand: seed global generator randomly
* [Go issue #21835](https://github.com/golang/go/issues/21835) - proposal: use PCG Source in math/rand for Go 2

<sup>
Cover photo is [Closeup Photo of Two Red Dices Showing 4 and 5](https://www.pexels.com/photo/closeup-photo-of-two-red-dices-showing-4-and-5-965875/) by [Jonathan Petersson](https://www.pexels.com/@grizzlybear/)
Body photo is [Yelling formal man watching news on laptop
](https://www.pexels.com/photo/yelling-formal-man-watching-news-on-laptop-3760778/) by [Andrea Piacquadio
](https://www.pexels.com/@olly/)
</sup>