Debian Codegraph @

raft/quorum/quick_test.go

raw
1 // Copyright 2019 The etcd Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 package quorum
16
17 import (
18 "math"
19 "math/rand"
20 "reflect"
21 "testing"
22 "testing/quick"
23 )
24
25 // TestQuick uses quickcheck to heuristically assert that the main
26 // implementation of (MajorityConfig).CommittedIndex agrees with a "dumb"
27 // alternative version.
28 func TestQuick(t *testing.T) {
29 cfg := &quick.Config{
30 MaxCount: 50000,
31 }
32
33 t.Run("majority_commit", func(t *testing.T) {
34 fn1 := func(c memberMap, l idxMap) uint64 {
35 return uint64(MajorityConfig(c).CommittedIndex(mapAckIndexer(l)))
36 }
37 fn2 := func(c memberMap, l idxMap) uint64 {
38 return uint64(alternativeMajorityCommittedIndex(MajorityConfig(c), mapAckIndexer(l)))
39 }
40 if err := quick.CheckEqual(fn1, fn2, cfg); err != nil {
41 t.Fatal(err)
42 }
43 })
44 }
45
46 // smallRandIdxMap returns a reasonably sized map of ids to commit indexes.
47 func smallRandIdxMap(rand *rand.Rand, _ int) map[uint64]Index {
48 // Hard-code a reasonably small size here (quick will hard-code 50, which
49 // is not useful here).
50 size := 10
51
52 n := rand.Intn(size)
53 ids := rand.Perm(2 * n)[:n]
54 idxs := make([]int, len(ids))
55 for i := range idxs {
56 idxs[i] = rand.Intn(n)
57 }
58
59 m := map[uint64]Index{}
60 for i := range ids {
61 m[uint64(ids[i])] = Index(idxs[i])
62 }
63 return m
64 }
65
66 type idxMap map[uint64]Index
67
68 func (idxMap) Generate(rand *rand.Rand, size int) reflect.Value {
69 m := smallRandIdxMap(rand, size)
70 return reflect.ValueOf(m)
71 }
72
73 type memberMap map[uint64]struct{}
74
75 func (memberMap) Generate(rand *rand.Rand, size int) reflect.Value {
76 m := smallRandIdxMap(rand, size)
77 mm := map[uint64]struct{}{}
78 for id := range m {
79 mm[id] = struct{}{}
80 }
81 return reflect.ValueOf(mm)
82 }
83
84 // This is an alternative implementation of (MajorityConfig).CommittedIndex(l).
85 func alternativeMajorityCommittedIndex(c MajorityConfig, l AckedIndexer) Index {
86 if len(c) == 0 {
87 return math.MaxUint64
88 }
89
90 idToIdx := map[uint64]Index{}
91 for id := range c {
92 if idx, ok := l.AckedIndex(id); ok {
93 idToIdx[id] = idx
94 }
95 }
96
97 // Build a map from index to voters who have acked that or any higher index.
98 idxToVotes := map[Index]int{}
99 for _, idx := range idToIdx {
100 idxToVotes[idx] = 0
101 }
102
103 for _, idx := range idToIdx {
104 for idy := range idxToVotes {
105 if idy > idx {
106 continue
107 }
108 idxToVotes[idy]++
109 }
110 }
111
112 // Find the maximum index that has achieved quorum.
113 q := len(c)/2 + 1
114 var maxQuorumIdx Index
115 for idx, n := range idxToVotes {
116 if n >= q && idx > maxQuorumIdx {
117 maxQuorumIdx = idx
118 }
119 }
120
121 return maxQuorumIdx
122 }