'unstable value' in reference to time % 12345

8/23/2018

In this reflector package it mentions an unstable value being used as a name suffix. It's the number of nanoseconds modulo 12345. Is this meaningful or is it just a synonym for pseudo random so humans don't interpret it?

// reflectorDisambiguator is used to disambiguate started reflectors.
// initialized to an unstable value to ensure meaning isn't attributed to the suffix.
var reflectorDisambiguator = int64(time.Now().UnixNano() % 12345)

The word unstable is what is specifically making me unsure. What does it mean in this context?

Is there an advantage of doing this over another method of getting a random number under 12345?

-- Brian
go
kubernetes

1 Answer

8/23/2018

The meaning seems clear:

Kubernetes-commit: 1da4f4a745bf536c34e377321a252b4774d1a7e0

tools/cache/reflector.go

// reflectorDisambiguator is used to disambiguate started reflectors.
// initialized to an unstable value to ensure meaning isn't attributed to the suffix.

The suffix behavior should not be deterministic because you should not rely on a particular implementation behavior.


For example, a similar situation occured for Go maps:

The Go Programming Language Specification

For statements with range clause

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.

Go 1 Release Notes

Iterating in maps

The old language specification did not define the order of iteration for maps, and in practice it differed across hardware platforms. This caused tests that iterated over maps to be fragile and non-portable, with the unpleasant property that a test might always pass on one machine but break on another.

In Go 1, the order in which elements are visited when iterating over a map using a for range statement is defined to be unpredictable, even if the same loop is run multiple times with the same map. Code should not assume that the elements are visited in any particular order.

This change means that code that depends on iteration order is very likely to break early and be fixed long before it becomes a problem. Just as important, it allows the map implementation to ensure better map balancing even when programs are using range loops to select an element from a map.

Go 1.3 Release Notes

Map iteration

Iterations over small maps no longer happen in a consistent order. Go 1 defines that “The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.” To keep code from depending on map iteration order, Go 1.0 started each map iteration at a random index in the map. A new map implementation introduced in Go 1.1 neglected to randomize iteration for maps with eight or fewer entries, although the iteration order can still vary from system to system. This has allowed people to write Go 1.1 and Go 1.2 programs that depend on small map iteration order and therefore only work reliably on certain systems. Go 1.3 reintroduces random iteration for small maps in order to flush out these bugs.

Updating: If code assumes a fixed iteration order for small maps, it will break and must be rewritten not to make that assumption. Because only small maps are affected, the problem arises most often in tests.


Similar concerns lead to a proposal, that wasn't implemented, to ensure that the order for unstable sorts was unstable:

proposal: sort: return equal values in non-deterministic order#13884

Crazy idea, but what if sort.Sort randomly permuted its input a bit before starting?

Go 1.6 has a different sort.Sort than Go 1.5 and I've seen at least a dozen test failures at Google that were implicitly depending on the old algorithm. The usual scenario is that you sort a slice of structs by one field in the struct. If there are entries with that field equal but others unequal and you expect a specific order for the structs at the end, you are depending on sort.Sort's algorithm. A later sort.Sort might make a different choice and produce a different order. This makes programs not portable from one version of Go to another, much like map hash differences used to make programs not portable from one architecture to another. We solved maps by randomizing the iteration order a bit. In the map case it's not a full permutation, but just enough variation to make tests obviously flaky.

I wonder if we should do the same for sort.Sort. It would only take N swaps to shuffle things quite well, and we already use Nlog(N) swaps, so N(log(N)+1) is not likely to be noticed. That would also protect a bit against malicious inputs.

It would surprise people, especially people who think sort.Sort == sort.Stable. But the rationale is that it's better to surprise them the first time they run the code instead of however many Go releases later.


Here are benchmarks comparing time.Now() to rand.Intn():

package main

import "testing"

import (
    rand "math/rand"
    "time"
)

// https://github.com/kubernetes/client-go/blob/79cb21f5b3b1dd8f8b23bd3f79925b4fda4e2562/tools/cache/reflector.go#L100
var reflectorDisambiguator = int64(time.Now().UnixNano() % 12345)

func BenchmarkTimeNow(b *testing.B) {
    for N := 0; N < b.N; N++ {
        reflectorDisambiguator = int64(time.Now().UnixNano() % 12345)
    }
}

// rand.Intn()
func init() {
    rand.Seed(time.Now().UnixNano())
    reflectorDisambiguator = int64(rand.Intn(12345))
}

func BenchmarkRandIntn(b *testing.B) {
    for N := 0; N < b.N; N++ {
        rand.Seed(time.Now().UnixNano())
        reflectorDisambiguator = int64(rand.Intn(12345))
    }
}

Output:

$ go test disambiguator_test.go -bench=.
goos: linux
goarch: amd64
BenchmarkTimeNow-4      20000000            67.5 ns/op
BenchmarkRandIntn-4       100000         11941 ns/op
$
-- peterSO
Source: StackOverflow