Line data Source code
1 : // Copyright 2019 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package metamorphic
6 :
7 : import (
8 : "bytes"
9 : "fmt"
10 : "sort"
11 :
12 : "github.com/cockroachdb/pebble"
13 : "github.com/cockroachdb/pebble/internal/randvar"
14 : "github.com/cockroachdb/pebble/internal/testkeys"
15 : "golang.org/x/exp/rand"
16 : )
17 :
18 : const maxValueSize = 20
19 :
20 : type iterOpts struct {
21 : lower []byte
22 : upper []byte
23 : keyTypes uint32 // pebble.IterKeyType
24 : // maskSuffix may be set if keyTypes is IterKeyTypePointsAndRanges to
25 : // configure IterOptions.RangeKeyMasking.Suffix.
26 : maskSuffix []byte
27 :
28 : // If filterMax is >0, this iterator will filter out any keys that have
29 : // suffixes that don't fall within the range [filterMin,filterMax).
30 : // Additionally, the iterator will be constructed with a block-property
31 : // filter that filters out blocks accordingly. Not all OPTIONS hook up the
32 : // corresponding block property collector, so block-filtering may still be
33 : // effectively disabled in some runs. The iterator operations themselves
34 : // however will always skip past any points that should be filtered to
35 : // ensure determinism.
36 : filterMin uint64
37 : filterMax uint64
38 :
39 : // see IterOptions.UseL6Filters.
40 : useL6Filters bool
41 :
42 : // NB: If adding or removing fields, ensure IsZero is in sync.
43 : }
44 :
45 0 : func (o iterOpts) IsZero() bool {
46 0 : return o.lower == nil && o.upper == nil && o.keyTypes == 0 &&
47 0 : o.maskSuffix == nil && o.filterMin == 0 && o.filterMax == 0 && !o.useL6Filters
48 0 : }
49 :
50 : type generator struct {
51 : cfg config
52 : rng *rand.Rand
53 :
54 : init *initOp
55 : ops []op
56 :
57 : // keyManager tracks the state of keys a operation generation time.
58 : keyManager *keyManager
59 : // Unordered sets of object IDs for live objects. Used to randomly select on
60 : // object when generating an operation. There are 4 concrete objects: the DB
61 : // (of which there is exactly 1), batches, iterators, and snapshots.
62 : //
63 : // liveBatches contains the live indexed and write-only batches.
64 : liveBatches objIDSlice
65 : // liveIters contains the live iterators.
66 : liveIters objIDSlice
67 : itersLastOpts map[objID]iterOpts
68 : // liveReaders contains the DB, and any live indexed batches and snapshots. The DB is always
69 : // at index 0.
70 : liveReaders objIDSlice
71 : // liveSnapshots contains the live snapshots.
72 : liveSnapshots objIDSlice
73 : // liveWriters contains the DB, and any live batches. The DB is always at index 0.
74 : liveWriters objIDSlice
75 :
76 : // Maps used to find associated objects during generation. These maps are not
77 : // needed during test execution.
78 : //
79 : // batchID -> batch iters: used to keep track of the open iterators on an
80 : // indexed batch. The iter set value will also be indexed by the readers map.
81 : batches map[objID]objIDSet
82 : // iterID -> reader iters: used to keep track of all of the open
83 : // iterators. The iter set value will also be indexed by either the batches
84 : // or snapshots maps.
85 : iters map[objID]objIDSet
86 : // readerID -> reader iters: used to keep track of the open iterators on a
87 : // reader. The iter set value will also be indexed by either the batches or
88 : // snapshots maps. This map is the union of batches and snapshots maps.
89 : readers map[objID]objIDSet
90 : // snapshotID -> snapshot iters: used to keep track of the open iterators on
91 : // a snapshot. The iter set value will also be indexed by the readers map.
92 : snapshots map[objID]objIDSet
93 : // snapshotID -> bounds of the snapshot: only populated for snapshots that
94 : // are constrained by bounds.
95 : snapshotBounds map[objID][]pebble.KeyRange
96 : // iterSequenceNumber is the metaTimestamp at which the iter was created.
97 : iterCreationTimestamp map[objID]int
98 : // iterReaderID is a map from an iterID to a readerID.
99 : iterReaderID map[objID]objID
100 : }
101 :
102 1 : func newGenerator(rng *rand.Rand, cfg config, km *keyManager) *generator {
103 1 : g := &generator{
104 1 : cfg: cfg,
105 1 : rng: rng,
106 1 : init: &initOp{},
107 1 : keyManager: km,
108 1 : liveReaders: objIDSlice{makeObjID(dbTag, 0)},
109 1 : liveWriters: objIDSlice{makeObjID(dbTag, 0)},
110 1 : batches: make(map[objID]objIDSet),
111 1 : iters: make(map[objID]objIDSet),
112 1 : readers: make(map[objID]objIDSet),
113 1 : snapshots: make(map[objID]objIDSet),
114 1 : snapshotBounds: make(map[objID][]pebble.KeyRange),
115 1 : itersLastOpts: make(map[objID]iterOpts),
116 1 : iterCreationTimestamp: make(map[objID]int),
117 1 : iterReaderID: make(map[objID]objID),
118 1 : }
119 1 : // Note that the initOp fields are populated during generation.
120 1 : g.ops = append(g.ops, g.init)
121 1 : return g
122 1 : }
123 :
124 1 : func generate(rng *rand.Rand, count uint64, cfg config, km *keyManager) []op {
125 1 : g := newGenerator(rng, cfg, km)
126 1 :
127 1 : generators := []func(){
128 1 : batchAbort: g.batchAbort,
129 1 : batchCommit: g.batchCommit,
130 1 : dbCheckpoint: g.dbCheckpoint,
131 1 : dbCompact: g.dbCompact,
132 1 : dbFlush: g.dbFlush,
133 1 : dbRatchetFormatMajorVersion: g.dbRatchetFormatMajorVersion,
134 1 : dbRestart: g.dbRestart,
135 1 : iterClose: g.randIter(g.iterClose),
136 1 : iterFirst: g.randIter(g.iterFirst),
137 1 : iterLast: g.randIter(g.iterLast),
138 1 : iterNext: g.randIter(g.iterNext),
139 1 : iterNextWithLimit: g.randIter(g.iterNextWithLimit),
140 1 : iterNextPrefix: g.randIter(g.iterNextPrefix),
141 1 : iterPrev: g.randIter(g.iterPrev),
142 1 : iterPrevWithLimit: g.randIter(g.iterPrevWithLimit),
143 1 : iterSeekGE: g.randIter(g.iterSeekGE),
144 1 : iterSeekGEWithLimit: g.randIter(g.iterSeekGEWithLimit),
145 1 : iterSeekLT: g.randIter(g.iterSeekLT),
146 1 : iterSeekLTWithLimit: g.randIter(g.iterSeekLTWithLimit),
147 1 : iterSeekPrefixGE: g.randIter(g.iterSeekPrefixGE),
148 1 : iterSetBounds: g.randIter(g.iterSetBounds),
149 1 : iterSetOptions: g.randIter(g.iterSetOptions),
150 1 : newBatch: g.newBatch,
151 1 : newIndexedBatch: g.newIndexedBatch,
152 1 : newIter: g.newIter,
153 1 : newIterUsingClone: g.newIterUsingClone,
154 1 : newSnapshot: g.newSnapshot,
155 1 : readerGet: g.readerGet,
156 1 : snapshotClose: g.snapshotClose,
157 1 : writerApply: g.writerApply,
158 1 : writerDelete: g.writerDelete,
159 1 : writerDeleteRange: g.writerDeleteRange,
160 1 : writerIngest: g.writerIngest,
161 1 : writerMerge: g.writerMerge,
162 1 : writerRangeKeyDelete: g.writerRangeKeyDelete,
163 1 : writerRangeKeySet: g.writerRangeKeySet,
164 1 : writerRangeKeyUnset: g.writerRangeKeyUnset,
165 1 : writerSet: g.writerSet,
166 1 : writerSingleDelete: g.writerSingleDelete,
167 1 : }
168 1 :
169 1 : // TPCC-style deck of cards randomization. Every time the end of the deck is
170 1 : // reached, we shuffle the deck.
171 1 : deck := randvar.NewDeck(g.rng, cfg.ops...)
172 1 : for i := uint64(0); i < count; i++ {
173 1 : generators[deck.Int()]()
174 1 : }
175 :
176 1 : g.dbClose()
177 1 : return g.ops
178 : }
179 :
180 1 : func (g *generator) add(op op) {
181 1 : g.ops = append(g.ops, op)
182 1 : g.keyManager.update(op)
183 1 : }
184 :
185 : // randKeyToWrite returns a key for any write other than SingleDelete.
186 : //
187 : // TODO(peter): make the size and distribution of keys configurable. See
188 : // keyDist and keySizeDist in config.go.
189 1 : func (g *generator) randKeyToWrite(newKey float64) []byte {
190 1 : return g.randKeyHelper(g.keyManager.eligibleWriteKeys(), newKey, nil)
191 1 : }
192 :
193 : // prefixKeyRange generates a [start, end) pair consisting of two prefix keys.
194 1 : func (g *generator) prefixKeyRange() ([]byte, []byte) {
195 1 : start := g.randPrefixToWrite(0.001)
196 1 : end := g.randPrefixToWrite(0.001)
197 1 : for g.cmp(start, end) == 0 {
198 1 : end = g.randPrefixToWrite(0.05)
199 1 : }
200 1 : if g.cmp(start, end) > 0 {
201 1 : start, end = end, start
202 1 : }
203 1 : return start, end
204 : }
205 :
206 : // randPrefixToWrite returns a prefix key (a key with no suffix) for a range key
207 : // write operation.
208 1 : func (g *generator) randPrefixToWrite(newPrefix float64) []byte {
209 1 : prefixes := g.keyManager.prefixes()
210 1 : if len(prefixes) > 0 && g.rng.Float64() > newPrefix {
211 1 : // Use an existing prefix.
212 1 : p := g.rng.Intn(len(prefixes))
213 1 : return prefixes[p]
214 1 : }
215 :
216 : // Use a new prefix.
217 1 : var prefix []byte
218 1 : for {
219 1 : prefix = g.randKeyHelperSuffix(nil, 4, 12, 0)
220 1 : if !g.keyManager.prefixExists(prefix) {
221 1 : if !g.keyManager.addNewKey(prefix) {
222 0 : panic("key must not exist if prefix doesn't exist")
223 : }
224 1 : return prefix
225 : }
226 : }
227 : }
228 :
229 : // randSuffixToWrite generates a random suffix according to the configuration's suffix
230 : // distribution. It takes a probability 0 ≤ p ≤ 1.0 indicating the probability
231 : // with which the generator should increase the max suffix generated by the
232 : // generator.
233 : //
234 : // randSuffixToWrite may return a nil suffix, with the probability the
235 : // configuration's suffix distribution assigns to the zero suffix.
236 1 : func (g *generator) randSuffixToWrite(incMaxProb float64) []byte {
237 1 : if g.rng.Float64() < incMaxProb {
238 1 : g.cfg.writeSuffixDist.IncMax(1)
239 1 : }
240 1 : return suffixFromInt(int64(g.cfg.writeSuffixDist.Uint64(g.rng)))
241 : }
242 :
243 : // randSuffixToRead generates a random suffix used during reads. The suffixes
244 : // generated by this function are within the same range as suffixes generated by
245 : // randSuffixToWrite, however randSuffixToRead pulls from a uniform
246 : // distribution.
247 1 : func (g *generator) randSuffixToRead() []byte {
248 1 : // When reading, don't apply the recency skewing in order to better exercise
249 1 : // a reading a mix of older and newer keys.
250 1 : max := g.cfg.writeSuffixDist.Max()
251 1 : return suffixFromInt(g.rng.Int63n(int64(max)))
252 1 : }
253 :
254 1 : func suffixFromInt(suffix int64) []byte {
255 1 : // Treat the zero as no suffix to match the behavior during point key
256 1 : // generation in randKeyHelper.
257 1 : if suffix == 0 {
258 1 : return nil
259 1 : }
260 1 : return testkeys.Suffix(suffix)
261 : }
262 :
263 1 : func (g *generator) randKeyToSingleDelete(id objID) []byte {
264 1 : keys := g.keyManager.eligibleSingleDeleteKeys(id)
265 1 : length := len(keys)
266 1 : if length == 0 {
267 1 : return nil
268 1 : }
269 1 : return keys[g.rng.Intn(length)]
270 : }
271 :
272 : // randKeyToRead returns a key for read operations.
273 1 : func (g *generator) randKeyToRead(newKey float64) []byte {
274 1 : return g.randKeyHelper(g.keyManager.eligibleReadKeys(), newKey, nil)
275 1 : }
276 :
277 : // randKeyToReadInRange returns a key for read operations within the provided
278 : // key range. The bounds of the provided key range must span a prefix boundary.
279 1 : func (g *generator) randKeyToReadInRange(newKey float64, kr pebble.KeyRange) []byte {
280 1 : return g.randKeyHelper(g.keyManager.eligibleReadKeysInRange(kr), newKey, &kr)
281 1 : }
282 :
283 : func (g *generator) randKeyHelper(
284 : keys [][]byte, newKey float64, newKeyBounds *pebble.KeyRange,
285 1 : ) []byte {
286 1 : switch {
287 1 : case len(keys) > 0 && g.rng.Float64() > newKey:
288 1 : // Use an existing user key.
289 1 : return keys[g.rng.Intn(len(keys))]
290 :
291 1 : case len(keys) > 0 && g.rng.Float64() > g.cfg.newPrefix:
292 1 : // Use an existing prefix but a new suffix, producing a new user key.
293 1 : prefixes := g.keyManager.prefixes()
294 1 :
295 1 : // If we're constrained to a key range, find which existing prefixes
296 1 : // fall within that key range.
297 1 : if newKeyBounds != nil {
298 1 : s := sort.Search(len(prefixes), func(i int) bool {
299 1 : return g.cmp(prefixes[i], newKeyBounds.Start) >= 0
300 1 : })
301 1 : e := sort.Search(len(prefixes), func(i int) bool {
302 1 : return g.cmp(prefixes[i], newKeyBounds.End) >= 0
303 1 : })
304 1 : prefixes = prefixes[s:e]
305 : }
306 :
307 1 : if len(prefixes) > 0 {
308 1 : for {
309 1 : // Pick a prefix on each iteration in case most or all suffixes are
310 1 : // already in use for any individual prefix.
311 1 : p := g.rng.Intn(len(prefixes))
312 1 : suffix := int64(g.cfg.writeSuffixDist.Uint64(g.rng))
313 1 :
314 1 : var key []byte
315 1 : if suffix > 0 {
316 1 : key = resizeBuffer(key, len(prefixes[p]), testkeys.SuffixLen(suffix))
317 1 : n := copy(key, prefixes[p])
318 1 : testkeys.WriteSuffix(key[n:], suffix)
319 1 : } else {
320 1 : key = resizeBuffer(key, len(prefixes[p]), 0)
321 1 : copy(key, prefixes[p])
322 1 : }
323 :
324 1 : if (newKeyBounds == nil || (g.cmp(key, newKeyBounds.Start) >= 0 && g.cmp(key, newKeyBounds.End) < 0)) &&
325 1 : g.keyManager.addNewKey(key) {
326 1 : return key
327 1 : }
328 :
329 : // If the generated key already existed, or the generated key
330 : // fell outside the provided bounds, increase the suffix
331 : // distribution and loop.
332 1 : g.cfg.writeSuffixDist.IncMax(1)
333 : }
334 : }
335 : // Otherwise fall through to generating a new prefix.
336 0 : fallthrough
337 :
338 1 : default:
339 1 : // Use a new prefix, producing a new user key.
340 1 :
341 1 : var key []byte
342 1 :
343 1 : suffix := int64(g.cfg.writeSuffixDist.Uint64(g.rng))
344 1 :
345 1 : // If we have bounds in which we need to generate the key, use
346 1 : // testkeys.RandomSeparator to generate a key between the bounds.
347 1 : if newKeyBounds != nil {
348 1 : targetLength := 4 + g.rng.Intn(8)
349 1 : key = testkeys.RandomSeparator(nil, g.prefix(newKeyBounds.Start), g.prefix(newKeyBounds.End),
350 1 : suffix, targetLength, g.rng)
351 1 : } else {
352 1 : for {
353 1 : key = g.randKeyHelperSuffix(nil, 4, 12, suffix)
354 1 : if !g.keyManager.prefixExists(key[:testkeys.Comparer.Split(key)]) {
355 1 : if !g.keyManager.addNewKey(key) {
356 0 : panic("key must not exist if prefix doesn't exist")
357 : }
358 1 : break
359 : }
360 : }
361 : }
362 1 : return key
363 : }
364 : }
365 :
366 : // randKeyHelperSuffix is a helper function for randKeyHelper, and should not be
367 : // invoked directly.
368 : func (g *generator) randKeyHelperSuffix(
369 : dst []byte, minPrefixLen, maxPrefixLen int, suffix int64,
370 1 : ) []byte {
371 1 : n := minPrefixLen
372 1 : if maxPrefixLen > minPrefixLen {
373 1 : n += g.rng.Intn(maxPrefixLen - minPrefixLen)
374 1 : }
375 : // In order to test a mix of suffixed and unsuffixed keys, omit the zero
376 : // suffix.
377 1 : if suffix == 0 {
378 1 : dst = resizeBuffer(dst, n, 0)
379 1 : g.fillRand(dst)
380 1 : return dst
381 1 : }
382 1 : suffixLen := testkeys.SuffixLen(suffix)
383 1 : dst = resizeBuffer(dst, n, suffixLen)
384 1 : g.fillRand(dst[:n])
385 1 : testkeys.WriteSuffix(dst[n:], suffix)
386 1 : return dst
387 : }
388 :
389 1 : func resizeBuffer(buf []byte, prefixLen, suffixLen int) []byte {
390 1 : if cap(buf) >= prefixLen+suffixLen {
391 0 : return buf[:prefixLen+suffixLen]
392 0 : }
393 1 : return make([]byte, prefixLen+suffixLen)
394 : }
395 :
396 : // TODO(peter): make the value size configurable. See valueSizeDist in
397 : // config.go.
398 1 : func (g *generator) randValue(min, max int) []byte {
399 1 : n := min
400 1 : if max > min {
401 1 : n += g.rng.Intn(max - min)
402 1 : }
403 1 : buf := make([]byte, n)
404 1 : g.fillRand(buf)
405 1 : return buf
406 : }
407 :
408 1 : func (g *generator) fillRand(buf []byte) {
409 1 : // NB: The actual random values are not particularly important. We only use
410 1 : // lowercase letters because that makes visual determination of ordering
411 1 : // easier, rather than having to remember the lexicographic ordering of
412 1 : // uppercase vs lowercase, or letters vs numbers vs punctuation.
413 1 : const letters = "abcdefghijklmnopqrstuvwxyz"
414 1 : const lettersLen = uint64(len(letters))
415 1 : const lettersCharsPerRand = 12 // floor(log(math.MaxUint64)/log(lettersLen))
416 1 :
417 1 : var r uint64
418 1 : var q int
419 1 : for i := 0; i < len(buf); i++ {
420 1 : if q == 0 {
421 1 : r = g.rng.Uint64()
422 1 : q = lettersCharsPerRand
423 1 : }
424 1 : buf[i] = letters[r%lettersLen]
425 1 : r = r / lettersLen
426 1 : q--
427 : }
428 : }
429 :
430 1 : func (g *generator) newBatch() {
431 1 : batchID := makeObjID(batchTag, g.init.batchSlots)
432 1 : g.init.batchSlots++
433 1 : g.liveBatches = append(g.liveBatches, batchID)
434 1 : g.liveWriters = append(g.liveWriters, batchID)
435 1 :
436 1 : g.add(&newBatchOp{
437 1 : batchID: batchID,
438 1 : })
439 1 : }
440 :
441 1 : func (g *generator) newIndexedBatch() {
442 1 : batchID := makeObjID(batchTag, g.init.batchSlots)
443 1 : g.init.batchSlots++
444 1 : g.liveBatches = append(g.liveBatches, batchID)
445 1 : g.liveReaders = append(g.liveReaders, batchID)
446 1 : g.liveWriters = append(g.liveWriters, batchID)
447 1 :
448 1 : iters := make(objIDSet)
449 1 : g.batches[batchID] = iters
450 1 : g.readers[batchID] = iters
451 1 :
452 1 : g.add(&newIndexedBatchOp{
453 1 : batchID: batchID,
454 1 : })
455 1 : }
456 :
457 : // removeFromBatchGenerator will not generate a closeOp for the target batch as
458 : // not every batch that is removed from the generator should be closed. For
459 : // example, running a closeOp before an ingestOp that contains the closed batch
460 : // will cause an error.
461 1 : func (g *generator) removeBatchFromGenerator(batchID objID) {
462 1 : g.liveBatches.remove(batchID)
463 1 : iters := g.batches[batchID]
464 1 : delete(g.batches, batchID)
465 1 :
466 1 : if iters != nil {
467 1 : g.liveReaders.remove(batchID)
468 1 : delete(g.readers, batchID)
469 1 : }
470 1 : g.liveWriters.remove(batchID)
471 1 : for _, id := range iters.sorted() {
472 1 : g.liveIters.remove(id)
473 1 : delete(g.iters, id)
474 1 : g.add(&closeOp{objID: id})
475 1 : }
476 : }
477 :
478 1 : func (g *generator) batchAbort() {
479 1 : if len(g.liveBatches) == 0 {
480 1 : return
481 1 : }
482 :
483 1 : batchID := g.liveBatches.rand(g.rng)
484 1 : g.removeBatchFromGenerator(batchID)
485 1 :
486 1 : g.add(&closeOp{objID: batchID})
487 : }
488 :
489 1 : func (g *generator) batchCommit() {
490 1 : if len(g.liveBatches) == 0 {
491 1 : return
492 1 : }
493 :
494 1 : batchID := g.liveBatches.rand(g.rng)
495 1 : g.removeBatchFromGenerator(batchID)
496 1 : g.add(&batchCommitOp{
497 1 : batchID: batchID,
498 1 : })
499 1 : g.add(&closeOp{objID: batchID})
500 :
501 : }
502 :
503 1 : func (g *generator) dbClose() {
504 1 : // Close any live iterators and snapshots, so that we can close the DB
505 1 : // cleanly.
506 1 : for len(g.liveIters) > 0 {
507 1 : g.randIter(g.iterClose)()
508 1 : }
509 1 : for len(g.liveSnapshots) > 0 {
510 1 : g.snapshotClose()
511 1 : }
512 1 : for len(g.liveBatches) > 0 {
513 1 : batchID := g.liveBatches[0]
514 1 : g.removeBatchFromGenerator(batchID)
515 1 : g.add(&closeOp{objID: batchID})
516 1 : }
517 1 : g.add(&closeOp{objID: makeObjID(dbTag, 0)})
518 : }
519 :
520 1 : func (g *generator) dbCheckpoint() {
521 1 : // 1/2 of the time we don't restrict the checkpoint;
522 1 : // 1/4 of the time we restrict to 1 span;
523 1 : // 1/8 of the time we restrict to 2 spans; etc.
524 1 : numSpans := 0
525 1 : for g.rng.Intn(2) == 0 {
526 1 : numSpans++
527 1 : }
528 1 : spans := make([]pebble.CheckpointSpan, numSpans)
529 1 : for i := range spans {
530 1 : start := g.randKeyToRead(0.01)
531 1 : end := g.randKeyToRead(0.01)
532 1 : if g.cmp(start, end) > 0 {
533 1 : start, end = end, start
534 1 : }
535 1 : spans[i].Start = start
536 1 : spans[i].End = end
537 : }
538 1 : g.add(&checkpointOp{
539 1 : spans: spans,
540 1 : })
541 : }
542 :
543 1 : func (g *generator) dbCompact() {
544 1 : // Generate new key(s) with a 1% probability.
545 1 : start := g.randKeyToRead(0.01)
546 1 : end := g.randKeyToRead(0.01)
547 1 : if g.cmp(start, end) > 0 {
548 1 : start, end = end, start
549 1 : }
550 1 : g.add(&compactOp{
551 1 : start: start,
552 1 : end: end,
553 1 : parallelize: g.rng.Float64() < 0.5,
554 1 : })
555 : }
556 :
557 1 : func (g *generator) dbFlush() {
558 1 : g.add(&flushOp{})
559 1 : }
560 :
561 1 : func (g *generator) dbRatchetFormatMajorVersion() {
562 1 : // Ratchet to a random format major version between the minimum the
563 1 : // metamorphic tests support and the newest. At runtime, the generated
564 1 : // version may be behind the database's format major version, in which case
565 1 : // RatchetFormatMajorVersion should deterministically error.
566 1 :
567 1 : // TODO(jackson): When the latest format major versions ares stabilized,
568 1 : // return this to just using `FormatNewest`.
569 1 : n := int(newestFormatMajorVersionTODO - minimumFormatMajorVersion)
570 1 : vers := pebble.FormatMajorVersion(g.rng.Intn(n+1)) + minimumFormatMajorVersion
571 1 : g.add(&dbRatchetFormatMajorVersionOp{vers: vers})
572 1 : }
573 :
574 1 : func (g *generator) dbRestart() {
575 1 : // Close any live iterators and snapshots, so that we can close the DB
576 1 : // cleanly.
577 1 : for len(g.liveIters) > 0 {
578 1 : g.randIter(g.iterClose)()
579 1 : }
580 1 : for len(g.liveSnapshots) > 0 {
581 1 : g.snapshotClose()
582 1 : }
583 : // Close the batches.
584 1 : for len(g.liveBatches) > 0 {
585 1 : batchID := g.liveBatches[0]
586 1 : g.removeBatchFromGenerator(batchID)
587 1 : g.add(&closeOp{objID: batchID})
588 1 : }
589 1 : if len(g.liveReaders) != 1 || len(g.liveWriters) != 1 {
590 0 : panic(fmt.Sprintf("unexpected counts: liveReaders %d, liveWriters: %d",
591 0 : len(g.liveReaders), len(g.liveWriters)))
592 : }
593 1 : g.add(&dbRestartOp{})
594 : }
595 :
596 : // maybeSetSnapshotIterBounds must be called whenever creating a new iterator or
597 : // modifying the bounds of an iterator. If the iterator is backed by a snapshot
598 : // that only guarantees consistency within a limited set of key spans, then the
599 : // iterator must set bounds within one of the snapshot's consistent keyspans. It
600 : // returns true if the provided readerID is a bounded snapshot and bounds were
601 : // set.
602 1 : func (g *generator) maybeSetSnapshotIterBounds(readerID objID, opts *iterOpts) bool {
603 1 : snapBounds, isBoundedSnapshot := g.snapshotBounds[readerID]
604 1 : if !isBoundedSnapshot {
605 1 : return false
606 1 : }
607 : // Pick a random keyrange within one of the snapshot's key ranges.
608 1 : parentBounds := snapBounds[g.rng.Intn(len(snapBounds))]
609 1 : // With 10% probability, use the parent start bound as-is.
610 1 : if g.rng.Float64() <= 0.1 {
611 1 : opts.lower = parentBounds.Start
612 1 : } else {
613 1 : opts.lower = testkeys.RandomSeparator(
614 1 : nil, /* dst */
615 1 : parentBounds.Start,
616 1 : parentBounds.End,
617 1 : 0, /* suffix */
618 1 : 4+g.rng.Intn(8),
619 1 : g.rng,
620 1 : )
621 1 : }
622 : // With 10% probability, use the parent end bound as-is.
623 1 : if g.rng.Float64() <= 0.1 {
624 1 : opts.upper = parentBounds.End
625 1 : } else {
626 1 : opts.upper = testkeys.RandomSeparator(
627 1 : nil, /* dst */
628 1 : opts.lower,
629 1 : parentBounds.End,
630 1 : 0, /* suffix */
631 1 : 4+g.rng.Intn(8),
632 1 : g.rng,
633 1 : )
634 1 : }
635 1 : return true
636 : }
637 :
638 1 : func (g *generator) newIter() {
639 1 : iterID := makeObjID(iterTag, g.init.iterSlots)
640 1 : g.init.iterSlots++
641 1 : g.liveIters = append(g.liveIters, iterID)
642 1 :
643 1 : readerID := g.liveReaders.rand(g.rng)
644 1 : if iters := g.readers[readerID]; iters != nil {
645 1 : iters[iterID] = struct{}{}
646 1 : g.iters[iterID] = iters
647 1 : //lint:ignore SA9003 - readability
648 1 : } else {
649 1 : // NB: the DB object does not track its open iterators because it never
650 1 : // closes.
651 1 : }
652 1 : g.iterReaderID[iterID] = readerID
653 1 :
654 1 : var opts iterOpts
655 1 : if !g.maybeSetSnapshotIterBounds(readerID, &opts) {
656 1 : // Generate lower/upper bounds with a 10% probability.
657 1 : if g.rng.Float64() <= 0.1 {
658 1 : // Generate a new key with a .1% probability.
659 1 : opts.lower = g.randKeyToRead(0.001)
660 1 : }
661 1 : if g.rng.Float64() <= 0.1 {
662 1 : // Generate a new key with a .1% probability.
663 1 : opts.upper = g.randKeyToRead(0.001)
664 1 : }
665 1 : if g.cmp(opts.lower, opts.upper) > 0 {
666 1 : opts.lower, opts.upper = opts.upper, opts.lower
667 1 : }
668 : }
669 1 : opts.keyTypes, opts.maskSuffix = g.randKeyTypesAndMask()
670 1 :
671 1 : // With 10% probability, enable automatic filtering of keys with suffixes
672 1 : // not in the provided range. This filtering occurs both through
673 1 : // block-property filtering and explicitly within the iterator operations to
674 1 : // ensure determinism.
675 1 : if g.rng.Float64() <= 0.1 {
676 1 : max := g.cfg.writeSuffixDist.Max()
677 1 : opts.filterMin, opts.filterMax = g.rng.Uint64n(max)+1, g.rng.Uint64n(max)+1
678 1 : if opts.filterMin > opts.filterMax {
679 1 : opts.filterMin, opts.filterMax = opts.filterMax, opts.filterMin
680 1 : } else if opts.filterMin == opts.filterMax {
681 1 : opts.filterMax = opts.filterMin + 1
682 1 : }
683 : }
684 :
685 : // Enable L6 filters with a 10% probability.
686 1 : if g.rng.Float64() <= 0.1 {
687 1 : opts.useL6Filters = true
688 1 : }
689 :
690 1 : g.itersLastOpts[iterID] = opts
691 1 : g.iterCreationTimestamp[iterID] = g.keyManager.nextMetaTimestamp()
692 1 : g.iterReaderID[iterID] = readerID
693 1 : g.add(&newIterOp{
694 1 : readerID: readerID,
695 1 : iterID: iterID,
696 1 : iterOpts: opts,
697 1 : })
698 : }
699 :
700 1 : func (g *generator) randKeyTypesAndMask() (keyTypes uint32, maskSuffix []byte) {
701 1 : // Iterate over different key types.
702 1 : p := g.rng.Float64()
703 1 : switch {
704 1 : case p < 0.2: // 20% probability
705 1 : keyTypes = uint32(pebble.IterKeyTypePointsOnly)
706 1 : case p < 0.8: // 60% probability
707 1 : keyTypes = uint32(pebble.IterKeyTypePointsAndRanges)
708 1 : // With 50% probability, enable masking.
709 1 : if g.rng.Intn(2) == 1 {
710 1 : maskSuffix = g.randSuffixToRead()
711 1 : }
712 1 : default: // 20% probability
713 1 : keyTypes = uint32(pebble.IterKeyTypeRangesOnly)
714 : }
715 1 : return keyTypes, maskSuffix
716 : }
717 :
718 1 : func (g *generator) newIterUsingClone() {
719 1 : if len(g.liveIters) == 0 {
720 1 : return
721 1 : }
722 1 : existingIterID := g.liveIters.rand(g.rng)
723 1 : iterID := makeObjID(iterTag, g.init.iterSlots)
724 1 : g.init.iterSlots++
725 1 : g.liveIters = append(g.liveIters, iterID)
726 1 : if iters := g.iters[existingIterID]; iters != nil {
727 1 : iters[iterID] = struct{}{}
728 1 : g.iters[iterID] = iters
729 1 : //lint:ignore SA9003 - readability
730 1 : } else {
731 1 : // NB: the DB object does not track its open iterators because it never
732 1 : // closes.
733 1 : }
734 1 : readerID := g.iterReaderID[existingIterID]
735 1 : g.iterReaderID[iterID] = readerID
736 1 :
737 1 : var refreshBatch bool
738 1 : if readerID.tag() == batchTag {
739 0 : refreshBatch = g.rng.Intn(2) == 1
740 0 : }
741 :
742 1 : var opts iterOpts
743 1 : if g.rng.Intn(2) == 1 {
744 1 : g.maybeMutateOptions(readerID, &opts)
745 1 : g.itersLastOpts[iterID] = opts
746 1 : } else {
747 1 : g.itersLastOpts[iterID] = g.itersLastOpts[existingIterID]
748 1 : }
749 :
750 1 : g.iterCreationTimestamp[iterID] = g.keyManager.nextMetaTimestamp()
751 1 : g.iterReaderID[iterID] = g.iterReaderID[existingIterID]
752 1 : g.add(&newIterUsingCloneOp{
753 1 : existingIterID: existingIterID,
754 1 : iterID: iterID,
755 1 : refreshBatch: refreshBatch,
756 1 : iterOpts: opts,
757 1 : derivedReaderID: readerID,
758 1 : })
759 : }
760 :
761 1 : func (g *generator) iterClose(iterID objID) {
762 1 : g.liveIters.remove(iterID)
763 1 : if readerIters, ok := g.iters[iterID]; ok {
764 1 : delete(g.iters, iterID)
765 1 : delete(readerIters, iterID)
766 1 : //lint:ignore SA9003 - readability
767 1 : } else {
768 1 : // NB: the DB object does not track its open iterators because it never
769 1 : // closes.
770 1 : }
771 :
772 1 : g.add(&closeOp{objID: iterID})
773 : }
774 :
775 1 : func (g *generator) iterSetBounds(iterID objID) {
776 1 : iterLastOpts := g.itersLastOpts[iterID]
777 1 : newOpts := iterLastOpts
778 1 : // TODO(jackson): The logic to increase the probability of advancing bounds
779 1 : // monotonically only applies if the snapshot is not bounded. Refactor to
780 1 : // allow bounded snapshots to benefit too, when possible.
781 1 : if !g.maybeSetSnapshotIterBounds(g.iterReaderID[iterID], &newOpts) {
782 1 : var lower, upper []byte
783 1 : genLower := g.rng.Float64() <= 0.9
784 1 : genUpper := g.rng.Float64() <= 0.9
785 1 : // When one of ensureLowerGE, ensureUpperLE is true, the new bounds
786 1 : // don't overlap with the previous bounds.
787 1 : var ensureLowerGE, ensureUpperLE bool
788 1 : if genLower && iterLastOpts.upper != nil && g.rng.Float64() <= 0.9 {
789 1 : ensureLowerGE = true
790 1 : }
791 1 : if (!ensureLowerGE || g.rng.Float64() < 0.5) && genUpper && iterLastOpts.lower != nil {
792 1 : ensureUpperLE = true
793 1 : ensureLowerGE = false
794 1 : }
795 1 : attempts := 0
796 1 : for {
797 1 : attempts++
798 1 : if genLower {
799 1 : // Generate a new key with a .1% probability.
800 1 : lower = g.randKeyToRead(0.001)
801 1 : }
802 1 : if genUpper {
803 1 : // Generate a new key with a .1% probability.
804 1 : upper = g.randKeyToRead(0.001)
805 1 : }
806 1 : if g.cmp(lower, upper) > 0 {
807 1 : lower, upper = upper, lower
808 1 : }
809 1 : if ensureLowerGE && g.cmp(iterLastOpts.upper, lower) > 0 {
810 1 : if attempts < 25 {
811 1 : continue
812 : }
813 1 : lower = iterLastOpts.upper
814 1 : upper = lower
815 1 : break
816 : }
817 1 : if ensureUpperLE && g.cmp(upper, iterLastOpts.lower) > 0 {
818 1 : if attempts < 25 {
819 1 : continue
820 : }
821 1 : upper = iterLastOpts.lower
822 1 : lower = upper
823 1 : break
824 : }
825 1 : break
826 : }
827 1 : newOpts.lower = lower
828 1 : newOpts.upper = upper
829 : }
830 1 : g.itersLastOpts[iterID] = newOpts
831 1 : g.add(&iterSetBoundsOp{
832 1 : iterID: iterID,
833 1 : lower: newOpts.lower,
834 1 : upper: newOpts.upper,
835 1 : })
836 1 : // Additionally seek the iterator in a manner consistent with the bounds,
837 1 : // and do some steps (Next/Prev). The seeking exercises typical
838 1 : // CockroachDB behavior when using iterators and the steps are trying to
839 1 : // stress the region near the bounds. Ideally, we should not do this as
840 1 : // part of generating a single op, but this is easier than trying to
841 1 : // control future op generation via generator state.
842 1 : doSeekLT := newOpts.upper != nil && g.rng.Float64() < 0.5
843 1 : doSeekGE := newOpts.lower != nil && g.rng.Float64() < 0.5
844 1 : if doSeekLT && doSeekGE {
845 1 : // Pick the seek.
846 1 : if g.rng.Float64() < 0.5 {
847 1 : doSeekGE = false
848 1 : } else {
849 1 : doSeekLT = false
850 1 : }
851 : }
852 1 : if doSeekLT {
853 1 : g.add(&iterSeekLTOp{
854 1 : iterID: iterID,
855 1 : key: newOpts.upper,
856 1 : derivedReaderID: g.iterReaderID[iterID],
857 1 : })
858 1 : if g.rng.Float64() < 0.5 {
859 1 : g.iterNext(iterID)
860 1 : }
861 1 : if g.rng.Float64() < 0.5 {
862 1 : g.iterNext(iterID)
863 1 : }
864 1 : if g.rng.Float64() < 0.5 {
865 1 : g.iterPrev(iterID)
866 1 : }
867 1 : } else if doSeekGE {
868 1 : g.add(&iterSeekGEOp{
869 1 : iterID: iterID,
870 1 : key: newOpts.lower,
871 1 : derivedReaderID: g.iterReaderID[iterID],
872 1 : })
873 1 : if g.rng.Float64() < 0.5 {
874 1 : g.iterPrev(iterID)
875 1 : }
876 1 : if g.rng.Float64() < 0.5 {
877 1 : g.iterPrev(iterID)
878 1 : }
879 1 : if g.rng.Float64() < 0.5 {
880 1 : g.iterNext(iterID)
881 1 : }
882 : }
883 : }
884 :
885 1 : func (g *generator) iterSetOptions(iterID objID) {
886 1 : opts := g.itersLastOpts[iterID]
887 1 : g.maybeMutateOptions(g.iterReaderID[iterID], &opts)
888 1 : g.itersLastOpts[iterID] = opts
889 1 : g.add(&iterSetOptionsOp{
890 1 : iterID: iterID,
891 1 : iterOpts: opts,
892 1 : derivedReaderID: g.iterReaderID[iterID],
893 1 : })
894 1 :
895 1 : // Additionally, perform a random absolute positioning operation. The
896 1 : // SetOptions contract requires one before the next relative positioning
897 1 : // operation. Ideally, we should not do this as part of generating a single
898 1 : // op, but this is easier than trying to control future op generation via
899 1 : // generator state.
900 1 : g.pickOneUniform(
901 1 : g.iterFirst,
902 1 : g.iterLast,
903 1 : g.iterSeekGE,
904 1 : g.iterSeekGEWithLimit,
905 1 : g.iterSeekPrefixGE,
906 1 : g.iterSeekLT,
907 1 : g.iterSeekLTWithLimit,
908 1 : )(iterID)
909 1 : }
910 :
911 1 : func (g *generator) iterSeekGE(iterID objID) {
912 1 : g.add(&iterSeekGEOp{
913 1 : iterID: iterID,
914 1 : key: g.randKeyToRead(0.001), // 0.1% new keys
915 1 : derivedReaderID: g.iterReaderID[iterID],
916 1 : })
917 1 : }
918 :
919 1 : func (g *generator) iterSeekGEWithLimit(iterID objID) {
920 1 : // 0.1% new keys
921 1 : key, limit := g.randKeyToRead(0.001), g.randKeyToRead(0.001)
922 1 : if g.cmp(key, limit) > 0 {
923 1 : key, limit = limit, key
924 1 : }
925 1 : g.add(&iterSeekGEOp{
926 1 : iterID: iterID,
927 1 : key: key,
928 1 : limit: limit,
929 1 : derivedReaderID: g.iterReaderID[iterID],
930 1 : })
931 : }
932 :
933 1 : func (g *generator) randKeyToReadWithinBounds(lower, upper []byte, readerID objID) []*keyMeta {
934 1 : var inRangeKeys []*keyMeta
935 1 : for _, keyMeta := range g.keyManager.byObj[readerID] {
936 1 : posKey := keyMeta.key
937 1 : if g.cmp(posKey, lower) < 0 || g.cmp(posKey, upper) >= 0 {
938 1 : continue
939 : }
940 1 : inRangeKeys = append(inRangeKeys, keyMeta)
941 : }
942 1 : return inRangeKeys
943 : }
944 :
945 1 : func (g *generator) iterSeekPrefixGE(iterID objID) {
946 1 : lower := g.itersLastOpts[iterID].lower
947 1 : upper := g.itersLastOpts[iterID].upper
948 1 : iterCreationTimestamp := g.iterCreationTimestamp[iterID]
949 1 : var key []byte
950 1 :
951 1 : // We try to make sure that the SeekPrefixGE key is within the iter bounds,
952 1 : // and that the iter can read the key. If the key was created on a batch
953 1 : // which deleted the key, then the key will still be considered visible
954 1 : // by the current logic. We're also not accounting for keys written to
955 1 : // batches which haven't been presisted to the DB. But we're only picking
956 1 : // keys in a best effort manner, and the logic is better than picking a
957 1 : // random key.
958 1 : if g.rng.Intn(10) >= 1 {
959 1 : possibleKeys := make([][]byte, 0, 100)
960 1 : inRangeKeys := g.randKeyToReadWithinBounds(lower, upper, dbObjID)
961 1 : for _, keyMeta := range inRangeKeys {
962 1 : posKey := keyMeta.key
963 1 : var foundWriteWithoutDelete bool
964 1 : for _, update := range keyMeta.updateOps {
965 1 : if update.metaTimestamp > iterCreationTimestamp {
966 1 : break
967 : }
968 :
969 1 : if update.deleted {
970 1 : foundWriteWithoutDelete = false
971 1 : } else {
972 1 : foundWriteWithoutDelete = true
973 1 : }
974 : }
975 1 : if foundWriteWithoutDelete {
976 1 : possibleKeys = append(possibleKeys, posKey)
977 1 : }
978 : }
979 :
980 1 : if len(possibleKeys) > 0 {
981 1 : key = []byte(possibleKeys[g.rng.Int31n(int32(len(possibleKeys)))])
982 1 : }
983 : }
984 :
985 1 : if key == nil {
986 1 : // TODO(bananabrick): We should try and use keys within the bounds,
987 1 : // even if we couldn't find any keys visible to the iterator. However,
988 1 : // doing this in experiments didn't really increase the valid
989 1 : // SeekPrefixGE calls by much.
990 1 : key = g.randKeyToRead(0) // 0% new keys
991 1 : }
992 :
993 1 : g.add(&iterSeekPrefixGEOp{
994 1 : iterID: iterID,
995 1 : key: key,
996 1 : derivedReaderID: g.iterReaderID[iterID],
997 1 : })
998 : }
999 :
1000 1 : func (g *generator) iterSeekLT(iterID objID) {
1001 1 : g.add(&iterSeekLTOp{
1002 1 : iterID: iterID,
1003 1 : key: g.randKeyToRead(0.001), // 0.1% new keys
1004 1 : derivedReaderID: g.iterReaderID[iterID],
1005 1 : })
1006 1 : }
1007 :
1008 1 : func (g *generator) iterSeekLTWithLimit(iterID objID) {
1009 1 : // 0.1% new keys
1010 1 : key, limit := g.randKeyToRead(0.001), g.randKeyToRead(0.001)
1011 1 : if g.cmp(limit, key) > 0 {
1012 1 : key, limit = limit, key
1013 1 : }
1014 1 : g.add(&iterSeekLTOp{
1015 1 : iterID: iterID,
1016 1 : key: key,
1017 1 : limit: limit,
1018 1 : derivedReaderID: g.iterReaderID[iterID],
1019 1 : })
1020 : }
1021 :
1022 : // randIter performs partial func application ("currying"), returning a new
1023 : // function that supplies the given func with a random iterator.
1024 1 : func (g *generator) randIter(gen func(objID)) func() {
1025 1 : return func() {
1026 1 : if len(g.liveIters) == 0 {
1027 1 : return
1028 1 : }
1029 1 : gen(g.liveIters.rand(g.rng))
1030 : }
1031 : }
1032 :
1033 1 : func (g *generator) iterFirst(iterID objID) {
1034 1 : g.add(&iterFirstOp{
1035 1 : iterID: iterID,
1036 1 : derivedReaderID: g.iterReaderID[iterID],
1037 1 : })
1038 1 : }
1039 :
1040 1 : func (g *generator) iterLast(iterID objID) {
1041 1 : g.add(&iterLastOp{
1042 1 : iterID: iterID,
1043 1 : derivedReaderID: g.iterReaderID[iterID],
1044 1 : })
1045 1 : }
1046 :
1047 1 : func (g *generator) iterNext(iterID objID) {
1048 1 : g.add(&iterNextOp{
1049 1 : iterID: iterID,
1050 1 : derivedReaderID: g.iterReaderID[iterID],
1051 1 : })
1052 1 : }
1053 :
1054 1 : func (g *generator) iterPrev(iterID objID) {
1055 1 : g.add(&iterPrevOp{
1056 1 : iterID: iterID,
1057 1 : derivedReaderID: g.iterReaderID[iterID],
1058 1 : })
1059 1 : }
1060 :
1061 1 : func (g *generator) iterNextWithLimit(iterID objID) {
1062 1 : g.add(&iterNextOp{
1063 1 : iterID: iterID,
1064 1 : limit: g.randKeyToRead(0.001), // 0.1% new keys
1065 1 : derivedReaderID: g.iterReaderID[iterID],
1066 1 : })
1067 1 : }
1068 :
1069 1 : func (g *generator) iterNextPrefix(iterID objID) {
1070 1 : g.add(&iterNextPrefixOp{
1071 1 : iterID: iterID,
1072 1 : derivedReaderID: g.iterReaderID[iterID],
1073 1 : })
1074 1 : }
1075 :
1076 1 : func (g *generator) iterPrevWithLimit(iterID objID) {
1077 1 : g.add(&iterPrevOp{
1078 1 : iterID: iterID,
1079 1 : limit: g.randKeyToRead(0.001), // 0.1% new keys
1080 1 : derivedReaderID: g.iterReaderID[iterID],
1081 1 : })
1082 1 : }
1083 :
1084 1 : func (g *generator) readerGet() {
1085 1 : if len(g.liveReaders) == 0 {
1086 0 : return
1087 0 : }
1088 :
1089 1 : readerID := g.liveReaders.rand(g.rng)
1090 1 :
1091 1 : // If the chosen reader is a snapshot created with user-specified key
1092 1 : // ranges, restrict the read to fall within one of the provided key ranges.
1093 1 : var key []byte
1094 1 : if bounds := g.snapshotBounds[readerID]; len(bounds) > 0 {
1095 1 : kr := bounds[g.rng.Intn(len(bounds))]
1096 1 : key = g.randKeyToReadInRange(0.001, kr) // 0.1% new keys
1097 1 : } else {
1098 1 : key = g.randKeyToRead(0.001) // 0.1% new keys
1099 1 : }
1100 1 : g.add(&getOp{readerID: readerID, key: key})
1101 : }
1102 :
1103 : // generateDisjointKeyRanges generates n disjoint key ranges.
1104 1 : func (g *generator) generateDisjointKeyRanges(n int) []pebble.KeyRange {
1105 1 : bounds := make([][]byte, 2*n)
1106 1 : used := map[string]bool{}
1107 1 : for i := 0; i < len(bounds); i++ {
1108 1 : k := g.prefix(g.randKeyToRead(0.1))
1109 1 : for used[string(k)] {
1110 1 : k = g.prefix(g.randKeyToRead(0.1))
1111 1 : }
1112 1 : bounds[i] = k
1113 1 : used[string(k)] = true
1114 : }
1115 1 : sort.Slice(bounds, func(i, j int) bool {
1116 1 : return g.cmp(bounds[i], bounds[j]) < 0
1117 1 : })
1118 1 : keyRanges := make([]pebble.KeyRange, n)
1119 1 : for i := range keyRanges {
1120 1 : keyRanges[i] = pebble.KeyRange{
1121 1 : Start: bounds[i*2],
1122 1 : End: bounds[i*2+1],
1123 1 : }
1124 1 : }
1125 1 : return keyRanges
1126 : }
1127 :
1128 1 : func (g *generator) newSnapshot() {
1129 1 : snapID := makeObjID(snapTag, g.init.snapshotSlots)
1130 1 : g.init.snapshotSlots++
1131 1 : g.liveSnapshots = append(g.liveSnapshots, snapID)
1132 1 : g.liveReaders = append(g.liveReaders, snapID)
1133 1 :
1134 1 : iters := make(objIDSet)
1135 1 : g.snapshots[snapID] = iters
1136 1 : g.readers[snapID] = iters
1137 1 :
1138 1 : s := &newSnapshotOp{
1139 1 : snapID: snapID,
1140 1 : }
1141 1 :
1142 1 : // With 75% probability, impose bounds on the keys that may be read with the
1143 1 : // snapshot. Setting bounds allows some runs of the metamorphic test to use
1144 1 : // a EventuallyFileOnlySnapshot instead of a Snapshot, testing equivalence
1145 1 : // between the two for reads within those bounds.
1146 1 : if g.rng.Float64() < 0.75 {
1147 1 : s.bounds = g.generateDisjointKeyRanges(
1148 1 : g.rng.Intn(5) + 1, /* between 1-5 */
1149 1 : )
1150 1 : g.snapshotBounds[snapID] = s.bounds
1151 1 : }
1152 1 : g.add(s)
1153 : }
1154 :
1155 1 : func (g *generator) snapshotClose() {
1156 1 : if len(g.liveSnapshots) == 0 {
1157 1 : return
1158 1 : }
1159 :
1160 1 : snapID := g.liveSnapshots.rand(g.rng)
1161 1 : g.liveSnapshots.remove(snapID)
1162 1 : iters := g.snapshots[snapID]
1163 1 : delete(g.snapshots, snapID)
1164 1 : g.liveReaders.remove(snapID)
1165 1 : delete(g.readers, snapID)
1166 1 :
1167 1 : for _, id := range iters.sorted() {
1168 1 : g.liveIters.remove(id)
1169 1 : delete(g.iters, id)
1170 1 : g.add(&closeOp{objID: id})
1171 1 : }
1172 :
1173 1 : g.add(&closeOp{objID: snapID})
1174 : }
1175 :
1176 1 : func (g *generator) writerApply() {
1177 1 : if len(g.liveBatches) == 0 {
1178 1 : return
1179 1 : }
1180 1 : if len(g.liveWriters) < 2 {
1181 0 : panic(fmt.Sprintf("insufficient liveWriters (%d) to apply batch", len(g.liveWriters)))
1182 : }
1183 :
1184 1 : batchID := g.liveBatches.rand(g.rng)
1185 1 :
1186 1 : var writerID objID
1187 1 : for {
1188 1 : writerID = g.liveWriters.rand(g.rng)
1189 1 : if writerID != batchID {
1190 1 : break
1191 : }
1192 : }
1193 :
1194 1 : g.removeBatchFromGenerator(batchID)
1195 1 :
1196 1 : g.add(&applyOp{
1197 1 : writerID: writerID,
1198 1 : batchID: batchID,
1199 1 : })
1200 1 : g.add(&closeOp{
1201 1 : batchID,
1202 1 : })
1203 : }
1204 :
1205 1 : func (g *generator) writerDelete() {
1206 1 : if len(g.liveWriters) == 0 {
1207 0 : return
1208 0 : }
1209 :
1210 1 : writerID := g.liveWriters.rand(g.rng)
1211 1 : g.add(&deleteOp{
1212 1 : writerID: writerID,
1213 1 : key: g.randKeyToWrite(0.001), // 0.1% new keys
1214 1 : })
1215 : }
1216 :
1217 1 : func (g *generator) writerDeleteRange() {
1218 1 : if len(g.liveWriters) == 0 {
1219 0 : return
1220 0 : }
1221 :
1222 1 : start := g.randKeyToWrite(0.001)
1223 1 : end := g.randKeyToWrite(0.001)
1224 1 : if g.cmp(start, end) > 0 {
1225 1 : start, end = end, start
1226 1 : }
1227 :
1228 1 : writerID := g.liveWriters.rand(g.rng)
1229 1 : g.add(&deleteRangeOp{
1230 1 : writerID: writerID,
1231 1 : start: start,
1232 1 : end: end,
1233 1 : })
1234 : }
1235 :
1236 1 : func (g *generator) writerRangeKeyDelete() {
1237 1 : if len(g.liveWriters) == 0 {
1238 0 : return
1239 0 : }
1240 1 : start, end := g.prefixKeyRange()
1241 1 :
1242 1 : writerID := g.liveWriters.rand(g.rng)
1243 1 : g.add(&rangeKeyDeleteOp{
1244 1 : writerID: writerID,
1245 1 : start: start,
1246 1 : end: end,
1247 1 : })
1248 : }
1249 :
1250 1 : func (g *generator) writerRangeKeySet() {
1251 1 : if len(g.liveWriters) == 0 {
1252 0 : return
1253 0 : }
1254 1 : start, end := g.prefixKeyRange()
1255 1 :
1256 1 : // 90% of the time, set a suffix.
1257 1 : var suffix []byte
1258 1 : if g.rng.Float64() < 0.90 {
1259 1 : // Increase the max suffix 5% of the time.
1260 1 : suffix = g.randSuffixToWrite(0.05)
1261 1 : }
1262 :
1263 1 : writerID := g.liveWriters.rand(g.rng)
1264 1 : g.add(&rangeKeySetOp{
1265 1 : writerID: writerID,
1266 1 : start: start,
1267 1 : end: end,
1268 1 : suffix: suffix,
1269 1 : value: g.randValue(0, maxValueSize),
1270 1 : })
1271 : }
1272 :
1273 1 : func (g *generator) writerRangeKeyUnset() {
1274 1 : if len(g.liveWriters) == 0 {
1275 0 : return
1276 0 : }
1277 1 : start, end := g.prefixKeyRange()
1278 1 :
1279 1 : // 90% of the time, set a suffix.
1280 1 : var suffix []byte
1281 1 : if g.rng.Float64() < 0.90 {
1282 1 : // Increase the max suffix 5% of the time.
1283 1 : suffix = g.randSuffixToWrite(0.05)
1284 1 : }
1285 :
1286 : // TODO(jackson): Increase probability of effective unsets? Purely random
1287 : // unsets are unlikely to remove an active range key.
1288 :
1289 1 : writerID := g.liveWriters.rand(g.rng)
1290 1 : g.add(&rangeKeyUnsetOp{
1291 1 : writerID: writerID,
1292 1 : start: start,
1293 1 : end: end,
1294 1 : suffix: suffix,
1295 1 : })
1296 : }
1297 :
1298 1 : func (g *generator) writerIngest() {
1299 1 : if len(g.liveBatches) == 0 {
1300 1 : return
1301 1 : }
1302 :
1303 : // TODO(nicktrav): this is resulting in too many single batch ingests.
1304 : // Consider alternatives. One possibility would be to pass through whether
1305 : // we can tolerate failure or not, and if the ingestOp encounters a
1306 : // failure, it would retry after splitting into single batch ingests.
1307 :
1308 : // Ingest between 1 and 3 batches.
1309 1 : batchIDs := make([]objID, 0, 1+g.rng.Intn(3))
1310 1 : canFail := cap(batchIDs) > 1
1311 1 : for i := 0; i < cap(batchIDs); i++ {
1312 1 : batchID := g.liveBatches.rand(g.rng)
1313 1 : if canFail && !g.keyManager.canTolerateApplyFailure(batchID) {
1314 1 : continue
1315 : }
1316 : // After the ingest runs, it either succeeds and the keys are in the
1317 : // DB, or it fails and these keys never make it to the DB.
1318 1 : g.removeBatchFromGenerator(batchID)
1319 1 : batchIDs = append(batchIDs, batchID)
1320 1 : if len(g.liveBatches) == 0 {
1321 1 : break
1322 : }
1323 : }
1324 1 : if len(batchIDs) == 0 && len(g.liveBatches) > 0 {
1325 1 : // Unable to find multiple batches because of the
1326 1 : // canTolerateApplyFailure call above, so just pick one batch.
1327 1 : batchID := g.liveBatches.rand(g.rng)
1328 1 : g.removeBatchFromGenerator(batchID)
1329 1 : batchIDs = append(batchIDs, batchID)
1330 1 : }
1331 1 : g.add(&ingestOp{
1332 1 : batchIDs: batchIDs,
1333 1 : })
1334 : }
1335 :
1336 1 : func (g *generator) writerMerge() {
1337 1 : if len(g.liveWriters) == 0 {
1338 0 : return
1339 0 : }
1340 :
1341 1 : writerID := g.liveWriters.rand(g.rng)
1342 1 : g.add(&mergeOp{
1343 1 : writerID: writerID,
1344 1 : // 20% new keys.
1345 1 : key: g.randKeyToWrite(0.2),
1346 1 : value: g.randValue(0, maxValueSize),
1347 1 : })
1348 : }
1349 :
1350 1 : func (g *generator) writerSet() {
1351 1 : if len(g.liveWriters) == 0 {
1352 0 : return
1353 0 : }
1354 :
1355 1 : writerID := g.liveWriters.rand(g.rng)
1356 1 : g.add(&setOp{
1357 1 : writerID: writerID,
1358 1 : // 50% new keys.
1359 1 : key: g.randKeyToWrite(0.5),
1360 1 : value: g.randValue(0, maxValueSize),
1361 1 : })
1362 : }
1363 :
1364 1 : func (g *generator) writerSingleDelete() {
1365 1 : if len(g.liveWriters) == 0 {
1366 0 : return
1367 0 : }
1368 :
1369 1 : writerID := g.liveWriters.rand(g.rng)
1370 1 : key := g.randKeyToSingleDelete(writerID)
1371 1 : if key == nil {
1372 1 : return
1373 1 : }
1374 1 : g.add(&singleDeleteOp{
1375 1 : writerID: writerID,
1376 1 : key: key,
1377 1 : // Keys eligible for single deletes can be removed with a regular
1378 1 : // delete. Mutate a percentage of SINGLEDEL ops into DELETEs. Note that
1379 1 : // here we are only determining whether the replacement *could* happen.
1380 1 : // At test runtime, the `replaceSingleDelete` test option must also be
1381 1 : // set to true for the single delete to be replaced.
1382 1 : maybeReplaceDelete: g.rng.Float64() < 0.25,
1383 1 : })
1384 : }
1385 :
1386 1 : func (g *generator) maybeMutateOptions(readerID objID, opts *iterOpts) {
1387 1 : // With 95% probability, allow changes to any options at all. This ensures
1388 1 : // that in 5% of cases there are no changes, and SetOptions hits its fast
1389 1 : // path.
1390 1 : if g.rng.Intn(100) >= 5 {
1391 1 : if !g.maybeSetSnapshotIterBounds(readerID, opts) {
1392 1 : // With 1/3 probability, clear existing bounds.
1393 1 : if opts.lower != nil && g.rng.Intn(3) == 0 {
1394 1 : opts.lower = nil
1395 1 : }
1396 1 : if opts.upper != nil && g.rng.Intn(3) == 0 {
1397 1 : opts.upper = nil
1398 1 : }
1399 : // With 1/3 probability, update the bounds.
1400 1 : if g.rng.Intn(3) == 0 {
1401 1 : // Generate a new key with a .1% probability.
1402 1 : opts.lower = g.randKeyToRead(0.001)
1403 1 : }
1404 1 : if g.rng.Intn(3) == 0 {
1405 1 : // Generate a new key with a .1% probability.
1406 1 : opts.upper = g.randKeyToRead(0.001)
1407 1 : }
1408 1 : if g.cmp(opts.lower, opts.upper) > 0 {
1409 1 : opts.lower, opts.upper = opts.upper, opts.lower
1410 1 : }
1411 : }
1412 :
1413 : // With 1/3 probability, update the key-types/mask.
1414 1 : if g.rng.Intn(3) == 0 {
1415 1 : opts.keyTypes, opts.maskSuffix = g.randKeyTypesAndMask()
1416 1 : }
1417 :
1418 : // With 1/3 probability, clear existing filter.
1419 1 : if opts.filterMax > 0 && g.rng.Intn(3) == 0 {
1420 1 : opts.filterMax, opts.filterMin = 0, 0
1421 1 : }
1422 : // With 10% probability, set a filter range.
1423 1 : if g.rng.Intn(10) == 1 {
1424 1 : max := g.cfg.writeSuffixDist.Max()
1425 1 : opts.filterMin, opts.filterMax = g.rng.Uint64n(max)+1, g.rng.Uint64n(max)+1
1426 1 : if opts.filterMin > opts.filterMax {
1427 1 : opts.filterMin, opts.filterMax = opts.filterMax, opts.filterMin
1428 1 : } else if opts.filterMin == opts.filterMax {
1429 1 : opts.filterMax = opts.filterMin + 1
1430 1 : }
1431 : }
1432 : // With 10% probability, flip enablement of L6 filters.
1433 1 : if g.rng.Float64() <= 0.1 {
1434 1 : opts.useL6Filters = !opts.useL6Filters
1435 1 : }
1436 : }
1437 : }
1438 :
1439 1 : func (g *generator) pickOneUniform(options ...func(objID)) func(objID) {
1440 1 : i := g.rng.Intn(len(options))
1441 1 : return options[i]
1442 1 : }
1443 :
1444 1 : func (g *generator) cmp(a, b []byte) int {
1445 1 : return g.keyManager.comparer.Compare(a, b)
1446 1 : }
1447 :
1448 1 : func (g *generator) equal(a, b []byte) bool {
1449 1 : return g.keyManager.comparer.Equal(a, b)
1450 1 : }
1451 :
1452 1 : func (g *generator) split(a []byte) int {
1453 1 : return g.keyManager.comparer.Split(a)
1454 1 : }
1455 :
1456 1 : func (g *generator) prefix(a []byte) []byte {
1457 1 : return a[:g.split(a)]
1458 1 : }
1459 :
1460 0 : func (g *generator) String() string {
1461 0 : var buf bytes.Buffer
1462 0 : for _, op := range g.ops {
1463 0 : fmt.Fprintf(&buf, "%s\n", op)
1464 0 : }
1465 0 : return buf.String()
1466 : }
|
