|
| 1 | +//go:build xfail |
| 2 | + |
| 3 | +package networkdb |
| 4 | + |
| 5 | +import ( |
| 6 | + "maps" |
| 7 | + "math" |
| 8 | + "math/bits" |
| 9 | + "slices" |
| 10 | + "strings" |
| 11 | + "testing" |
| 12 | + |
| 13 | + "github.com/montanaflynn/stats" |
| 14 | + "gotest.tools/v3/assert" |
| 15 | + is "gotest.tools/v3/assert/cmp" |
| 16 | + "pgregory.net/rapid" |
| 17 | +) |
| 18 | + |
| 19 | +func TestMRandomNodes(t *testing.T) { |
| 20 | + cfg := DefaultConfig() |
| 21 | + // The easiest way to ensure that we don't accidentally generate node |
| 22 | + // IDs that match the local one is to include runes that the generator |
| 23 | + // will never emit. |
| 24 | + cfg.NodeID = "_thisnode" |
| 25 | + uut := newNetworkDB(cfg) |
| 26 | + |
| 27 | + t.Run("EmptySlice", func(t *testing.T) { |
| 28 | + sample := uut.mRandomNodes(3, nil) |
| 29 | + assert.Check(t, is.Len(sample, 0)) |
| 30 | + }) |
| 31 | + |
| 32 | + t.Run("OnlyLocalNode", func(t *testing.T) { |
| 33 | + sample := uut.mRandomNodes(3, []string{cfg.NodeID}) |
| 34 | + assert.Check(t, is.Len(sample, 0)) |
| 35 | + }) |
| 36 | + |
| 37 | + gen := rapid.Custom(func(t *rapid.T) []string { |
| 38 | + s := rapid.SliceOfNDistinct(rapid.StringMatching(`[a-z]{10}`), 0, 100, rapid.ID).Draw(t, "node-names") |
| 39 | + insertPoint := rapid.IntRange(0, len(s)).Draw(t, "insertPoint") |
| 40 | + return slices.Insert(s, insertPoint, cfg.NodeID) |
| 41 | + }) |
| 42 | + |
| 43 | + rapid.Check(t, func(t *rapid.T) { |
| 44 | + nodes := gen.Draw(t, "nodes") |
| 45 | + m := rapid.IntRange(0, len(nodes)).Draw(t, "m") |
| 46 | + |
| 47 | + takeSample := func() []string { |
| 48 | + sample := uut.mRandomNodes(m, nodes) |
| 49 | + assert.Check(t, is.Len(sample, min(m, len(nodes)-1))) |
| 50 | + assert.Check(t, is.Equal(slices.Index(sample, cfg.NodeID), -1), "sample contains local node ID\n%v", sample) |
| 51 | + assertUniqueElements(t, sample) |
| 52 | + return sample |
| 53 | + } |
| 54 | + |
| 55 | + p := kpermutations(uint64(len(nodes)-1), uint64(m)) |
| 56 | + switch { |
| 57 | + case p <= 1: |
| 58 | + // Only one permutation is possible, so cannot test randomness. |
| 59 | + // Assert the other properties by taking a few samples. |
| 60 | + for range 100 { |
| 61 | + _ = takeSample() |
| 62 | + } |
| 63 | + return |
| 64 | + case p <= 10: |
| 65 | + // With a small number of possible k-permutations, we |
| 66 | + // can feasibly test how many samples it takes to get |
| 67 | + // all of them. |
| 68 | + seen := make(map[string]bool) |
| 69 | + var i int |
| 70 | + for i = range 10000 { |
| 71 | + sample := takeSample() |
| 72 | + seen[strings.Join(sample, ",")] = true |
| 73 | + if len(seen) == int(p) { |
| 74 | + break |
| 75 | + } |
| 76 | + } |
| 77 | + assert.Check(t, is.Len(seen, int(p)), "did not see all %d permutations after %d trials", p, i+1) |
| 78 | + t.Logf("saw all %d permutations after %d samples", p, i+1) |
| 79 | + default: |
| 80 | + uniques := 0 |
| 81 | + sample1 := takeSample() |
| 82 | + for range 10 { |
| 83 | + sample2 := takeSample() |
| 84 | + if !slices.Equal(sample1, sample2) { |
| 85 | + uniques++ |
| 86 | + } |
| 87 | + } |
| 88 | + assert.Check(t, uniques > 0, "mRandomNodes returned the same sample multiple times") |
| 89 | + } |
| 90 | + |
| 91 | + // We are testing randomness so statistical outliers are |
| 92 | + // occasionally expected even when the probability |
| 93 | + // distribution is uniform. Run multiple trials to make |
| 94 | + // test flakes unlikely in practice. |
| 95 | + extremes := 0 |
| 96 | + for range 10 { |
| 97 | + counts := make(map[string]int) |
| 98 | + for _, n := range nodes { |
| 99 | + if n != cfg.NodeID { |
| 100 | + counts[n] = 0 |
| 101 | + } |
| 102 | + } |
| 103 | + const samples = 10000 |
| 104 | + for range samples { |
| 105 | + for _, n := range uut.mRandomNodes(m, nodes) { |
| 106 | + counts[n]++ |
| 107 | + } |
| 108 | + } |
| 109 | + // Adding multiple samples together should yield a normal distribution |
| 110 | + // if the samples are unbiased. |
| 111 | + countsf := stats.LoadRawData(slices.Collect(maps.Values(counts))) |
| 112 | + nf := stats.NormFit(countsf) |
| 113 | + mean, stdev := nf[0], nf[1] |
| 114 | + minv, _ := countsf.Min() |
| 115 | + maxv, _ := countsf.Max() |
| 116 | + if minv < mean-4*stdev || maxv > mean+4*stdev { |
| 117 | + extremes++ |
| 118 | + t.Logf("Mean: %f, StdDev: %f, Min: %f, Max: %f", mean, stdev, minv, maxv) |
| 119 | + } |
| 120 | + } |
| 121 | + assert.Check(t, extremes <= 2, "outliers in distribution: %d/10 trials, expected <2/10", extremes) |
| 122 | + }) |
| 123 | +} |
| 124 | + |
| 125 | +func assertUniqueElements[S ~[]E, E comparable](t rapid.TB, s S) { |
| 126 | + t.Helper() |
| 127 | + counts := make(map[E]int) |
| 128 | + for _, e := range s { |
| 129 | + counts[e]++ |
| 130 | + } |
| 131 | + for e, c := range counts { |
| 132 | + assert.Equal(t, c, 1, "element %v appears more than once in the slice", e) |
| 133 | + } |
| 134 | +} |
| 135 | + |
| 136 | +// kpermutations returns P(n,k), the number of permutations of k elements chosen |
| 137 | +// from a set of size n. The calculation is saturating: if the result is larger than |
| 138 | +// can be represented by a uint64, math.MaxUint64 is returned. |
| 139 | +func kpermutations(n, k uint64) uint64 { |
| 140 | + if k > n { |
| 141 | + return 0 |
| 142 | + } |
| 143 | + if k == 0 || n == 0 { |
| 144 | + return 1 |
| 145 | + } |
| 146 | + p := uint64(1) |
| 147 | + for i := range k { |
| 148 | + var hi uint64 |
| 149 | + hi, p = bits.Mul64(p, n-i) |
| 150 | + if hi != 0 { |
| 151 | + return math.MaxUint64 |
| 152 | + } |
| 153 | + } |
| 154 | + return p |
| 155 | +} |
0 commit comments