Debian Codegraph @

raft/quorum/datadriven_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 "fmt"
19 "strings"
20 "testing"
21
22 "github.com/cockroachdb/datadriven"
23 )
24
25 // TestDataDriven parses and executes the test cases in ./testdata/*. An entry
26 // in such a file specifies the command, which is either of "committed" to check
27 // CommittedIndex or "vote" to verify a VoteResult. The underlying configuration
28 // and inputs are specified via the arguments 'cfg' and 'cfgj' (for the majority
29 // config and, optionally, majority config joint to the first one) and 'idx'
30 // (for CommittedIndex) and 'votes' (for VoteResult).
31 //
32 // Internally, the harness runs some additional checks on each test case for
33 // which it is known that the result shouldn't change. For example,
34 // interchanging the majority configurations of a joint quorum must not
35 // influence the result; if it does, this is noted in the test's output.
36 func TestDataDriven(t *testing.T) {
37 datadriven.Walk(t, "testdata", func(t *testing.T, path string) {
38 datadriven.RunTest(t, path, func(t *testing.T, d *datadriven.TestData) string {
39 // Two majority configs. The first one is always used (though it may
40 // be empty) and the second one is used iff joint is true.
41 var joint bool
42 var ids, idsj []uint64
43 // The committed indexes for the nodes in the config in the order in
44 // which they appear in (ids,idsj), without repetition. An underscore
45 // denotes an omission (i.e. no information for this voter); this is
46 // different from 0. For example,
47 //
48 // cfg=(1,2) cfgj=(2,3,4) idxs=(_,5,_,7) initializes the idx for voter 2
49 // to 5 and that for voter 4 to 7 (and no others).
50 //
51 // cfgj=zero is specified to instruct the test harness to treat cfgj
52 // as zero instead of not specified (i.e. it will trigger a joint
53 // quorum test instead of a majority quorum test for cfg only).
54 var idxs []Index
55 // Votes. These are initialized similar to idxs except the only values
56 // used are 1 (voted against) and 2 (voted for). This looks awkward,
57 // but is convenient because it allows sharing code between the two.
58 var votes []Index
59
60 // Parse the args.
61 for _, arg := range d.CmdArgs {
62 for i := range arg.Vals {
63 switch arg.Key {
64 case "cfg":
65 var n uint64
66 arg.Scan(t, i, &n)
67 ids = append(ids, n)
68 case "cfgj":
69 joint = true
70 if arg.Vals[i] == "zero" {
71 if len(arg.Vals) != 1 {
72 t.Fatalf("cannot mix 'zero' into configuration")
73 }
74 } else {
75 var n uint64
76 arg.Scan(t, i, &n)
77 idsj = append(idsj, n)
78 }
79 case "idx":
80 var n uint64
81 // Register placeholders as zeroes.
82 if arg.Vals[i] != "_" {
83 arg.Scan(t, i, &n)
84 if n == 0 {
85 // This is a restriction caused by the above
86 // special-casing for _.
87 t.Fatalf("cannot use 0 as idx")
88 }
89 }
90 idxs = append(idxs, Index(n))
91 case "votes":
92 var s string
93 arg.Scan(t, i, &s)
94 switch s {
95 case "y":
96 votes = append(votes, 2)
97 case "n":
98 votes = append(votes, 1)
99 case "_":
100 votes = append(votes, 0)
101 default:
102 t.Fatalf("unknown vote: %s", s)
103 }
104 default:
105 t.Fatalf("unknown arg %s", arg.Key)
106 }
107 }
108 }
109
110 // Build the two majority configs.
111 c := MajorityConfig{}
112 for _, id := range ids {
113 c[id] = struct{}{}
114 }
115 cj := MajorityConfig{}
116 for _, id := range idsj {
117 cj[id] = struct{}{}
118 }
119
120 // Helper that returns an AckedIndexer which has the specified indexes
121 // mapped to the right IDs.
122 makeLookuper := func(idxs []Index, ids, idsj []uint64) mapAckIndexer {
123 l := mapAckIndexer{}
124 var p int // next to consume from idxs
125 for _, id := range append(append([]uint64(nil), ids...), idsj...) {
126 if _, ok := l[id]; ok {
127 continue
128 }
129 if p < len(idxs) {
130 // NB: this creates zero entries for placeholders that we remove later.
131 // The upshot of doing it that way is to avoid having to specify place-
132 // holders multiple times when omitting voters present in both halves of
133 // a joint config.
134 l[id] = idxs[p]
135 p++
136 }
137 }
138
139 for id := range l {
140 // Zero entries are created by _ placeholders; we don't want
141 // them in the lookuper because "no entry" is different from
142 // "zero entry". Note that we prevent tests from specifying
143 // zero commit indexes, so that there's no confusion between
144 // the two concepts.
145 if l[id] == 0 {
146 delete(l, id)
147 }
148 }
149 return l
150 }
151
152 {
153 input := idxs
154 if d.Cmd == "vote" {
155 input = votes
156 }
157 if voters := JointConfig([2]MajorityConfig{c, cj}).IDs(); len(voters) != len(input) {
158 return fmt.Sprintf("error: mismatched input (explicit or _) for voters %v: %v",
159 voters, input)
160 }
161 }
162
163 var buf strings.Builder
164 switch d.Cmd {
165 case "committed":
166 l := makeLookuper(idxs, ids, idsj)
167
168 // Branch based on whether this is a majority or joint quorum
169 // test case.
170 if !joint {
171 idx := c.CommittedIndex(l)
172 fmt.Fprint(&buf, c.Describe(l))
173 // These alternative computations should return the same
174 // result. If not, print to the output.
175 if aIdx := alternativeMajorityCommittedIndex(c, l); aIdx != idx {
176 fmt.Fprintf(&buf, "%s <-- via alternative computation\n", aIdx)
177 }
178 // Joining a majority with the empty majority should give same result.
179 if aIdx := JointConfig([2]MajorityConfig{c, {}}).CommittedIndex(l); aIdx != idx {
180 fmt.Fprintf(&buf, "%s <-- via zero-joint quorum\n", aIdx)
181 }
182 // Joining a majority with itself should give same result.
183 if aIdx := JointConfig([2]MajorityConfig{c, c}).CommittedIndex(l); aIdx != idx {
184 fmt.Fprintf(&buf, "%s <-- via self-joint quorum\n", aIdx)
185 }
186 overlay := func(c MajorityConfig, l AckedIndexer, id uint64, idx Index) AckedIndexer {
187 ll := mapAckIndexer{}
188 for iid := range c {
189 if iid == id {
190 ll[iid] = idx
191 } else if idx, ok := l.AckedIndex(iid); ok {
192 ll[iid] = idx
193 }
194 }
195 return ll
196 }
197 for id := range c {
198 iidx, _ := l.AckedIndex(id)
199 if idx > iidx && iidx > 0 {
200 // If the committed index was definitely above the currently
201 // inspected idx, the result shouldn't change if we lower it
202 // further.
203 lo := overlay(c, l, id, iidx-1)
204 if aIdx := c.CommittedIndex(lo); aIdx != idx {
205 fmt.Fprintf(&buf, "%s <-- overlaying %d->%d", aIdx, id, iidx)
206 }
207 lo = overlay(c, l, id, 0)
208 if aIdx := c.CommittedIndex(lo); aIdx != idx {
209 fmt.Fprintf(&buf, "%s <-- overlaying %d->0", aIdx, id)
210 }
211 }
212 }
213 fmt.Fprintf(&buf, "%s\n", idx)
214 } else {
215 cc := JointConfig([2]MajorityConfig{c, cj})
216 fmt.Fprint(&buf, cc.Describe(l))
217 idx := cc.CommittedIndex(l)
218 // Interchanging the majorities shouldn't make a difference. If it does, print.
219 if aIdx := JointConfig([2]MajorityConfig{cj, c}).CommittedIndex(l); aIdx != idx {
220 fmt.Fprintf(&buf, "%s <-- via symmetry\n", aIdx)
221 }
222 fmt.Fprintf(&buf, "%s\n", idx)
223 }
224 case "vote":
225 ll := makeLookuper(votes, ids, idsj)
226 l := map[uint64]bool{}
227 for id, v := range ll {
228 l[id] = v != 1 // NB: 1 == false, 2 == true
229 }
230
231 if !joint {
232 // Test a majority quorum.
233 r := c.VoteResult(l)
234 fmt.Fprintf(&buf, "%v\n", r)
235 } else {
236 // Run a joint quorum test case.
237 r := JointConfig([2]MajorityConfig{c, cj}).VoteResult(l)
238 // Interchanging the majorities shouldn't make a difference. If it does, print.
239 if ar := JointConfig([2]MajorityConfig{cj, c}).VoteResult(l); ar != r {
240 fmt.Fprintf(&buf, "%v <-- via symmetry\n", ar)
241 }
242 fmt.Fprintf(&buf, "%v\n", r)
243 }
244 default:
245 t.Fatalf("unknown command: %s", d.Cmd)
246 }
247 return buf.String()
248 })
249 })
250 }