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 : "math/rand/v2"
9 :
10 : "github.com/cockroachdb/pebble"
11 : "github.com/cockroachdb/pebble/internal/base"
12 : "github.com/cockroachdb/pebble/internal/randvar"
13 : "github.com/cockroachdb/pebble/sstable"
14 : )
15 :
16 : // OpType is an enum of possible operation types.
17 : type OpType int
18 :
19 : // These constants define the set of possible operation types performed by the
20 : // metamorphic test.
21 : const (
22 : OpBatchAbort OpType = iota
23 : OpBatchCommit
24 : OpDBCheckpoint
25 : OpDBClose
26 : OpDBCompact
27 : OpDBDownload
28 : OpDBFlush
29 : OpDBRatchetFormatMajorVersion
30 : OpDBRestart
31 : OpIterClose
32 : OpIterFirst
33 : OpIterLast
34 : OpIterNext
35 : OpIterNextWithLimit
36 : OpIterNextPrefix
37 : OpIterCanSingleDelete
38 : OpIterPrev
39 : OpIterPrevWithLimit
40 : OpIterSeekGE
41 : OpIterSeekGEWithLimit
42 : OpIterSeekLT
43 : OpIterSeekLTWithLimit
44 : OpIterSeekPrefixGE
45 : OpIterSetBounds
46 : OpIterSetOptions
47 : OpNewBatch
48 : OpNewIndexedBatch
49 : OpNewIter
50 : OpNewIterUsingClone
51 : OpNewSnapshot
52 : OpNewExternalObj
53 : OpReaderGet
54 : OpReplicate
55 : OpSnapshotClose
56 : OpWriterApply
57 : OpWriterDelete
58 : OpWriterDeleteRange
59 : OpWriterIngest
60 : OpWriterIngestAndExcise
61 : OpWriterIngestExternalFiles
62 : OpWriterLogData
63 : OpWriterMerge
64 : OpWriterRangeKeyDelete
65 : OpWriterRangeKeySet
66 : OpWriterRangeKeyUnset
67 : OpWriterSet
68 : OpWriterSingleDelete
69 : NumOpTypes
70 : )
71 :
72 0 : func (o OpType) isDelete() bool {
73 0 : return o == OpWriterDelete || o == OpWriterDeleteRange || o == OpWriterSingleDelete
74 0 : }
75 :
76 : // OpConfig describes the distribution of operations and their attributes.
77 : type OpConfig struct {
78 : // Weights for the operation mix to generate. ops[i] corresponds to the
79 : // weight for opType(i).
80 : ops [NumOpTypes]int
81 :
82 : // newPrefix configures the probability that when generating a new user key,
83 : // the generated key uses a new key prefix rather than an existing prefix
84 : // with a suffix.
85 : newPrefix float64
86 : // writeSuffixDist defines the distribution of key suffixes during writing.
87 : // It's a dynamic randvar to roughly emulate workloads with MVCC timestamps,
88 : // skewing towards most recent timestamps.
89 : writeSuffixDist randvar.Dynamic
90 :
91 : // numInstances defines the number of pebble instances created for this
92 : // metamorphic test run.
93 : numInstances int
94 :
95 : // TODO(peter): unimplemented
96 : // keyDist randvar.Dynamic
97 : // keySizeDist randvar.Static
98 : // valueSizeDist randvar.Static
99 : // updateFrac float64
100 : // lowerBoundFrac float64
101 : // upperBoundFrac float64
102 : }
103 :
104 : // WithNewPrefixProbability returns a modified op configuration with the
105 : // probability of generating a new key prefix set to the provided value in
106 : // [0,1.0].
107 1 : func (c OpConfig) WithNewPrefixProbability(p float64) OpConfig {
108 1 : c.newPrefix = p
109 1 : return c
110 1 : }
111 :
112 : // WithOpWeight returns a modified op configuration with the weight of the
113 : // provided operation type overidden.
114 1 : func (c OpConfig) WithOpWeight(op OpType, weight int) OpConfig {
115 1 : c.ops[op] = weight
116 1 : return c
117 1 : }
118 :
119 : var presetConfigs = []OpConfig{
120 : DefaultOpConfig(),
121 : // Generate a configuration that helps exercise code paths dependent on many
122 : // versions of keys with the same prefixes. The default configuration does
123 : // not tend to generate many versions of the same key. Additionally, its
124 : // relatively high weight for deletion write operations makes it less likely
125 : // that we'll accumulate enough versions to exercise some code paths (eg,
126 : // see #2921 which requires >16 SETs for versions of the same prefix to
127 : // reside in a single block to exercise the code path).
128 : //
129 : // To encourage generation of many versions of the same keys, generate a new
130 : // prefix only 4% of the time when generating a new key. The remaining 96%
131 : // of new key generations will use an existing prefix. To keep the size of
132 : // the database growing, we also reduce the probability of delete write
133 : // operations significantly.
134 : DefaultOpConfig().
135 : WithNewPrefixProbability(0.04).
136 : WithOpWeight(OpWriterDeleteRange, 1).
137 : WithOpWeight(OpWriterDelete, 5).
138 : WithOpWeight(OpWriterSingleDelete, 5).
139 : WithOpWeight(OpWriterMerge, 0),
140 : }
141 :
142 : var multiInstancePresetConfig = multiInstanceConfig()
143 :
144 : // DefaultOpConfig returns the default distribution of operations.
145 1 : func DefaultOpConfig() OpConfig {
146 1 : return OpConfig{
147 1 : // dbClose is not in this list since it is deterministically generated once, at the end of the test.
148 1 : ops: [NumOpTypes]int{
149 1 : OpBatchAbort: 5,
150 1 : OpBatchCommit: 5,
151 1 : OpDBCheckpoint: 1,
152 1 : OpDBCompact: 1,
153 1 : OpDBDownload: 1,
154 1 : OpDBFlush: 2,
155 1 : OpDBRatchetFormatMajorVersion: 1,
156 1 : OpDBRestart: 2,
157 1 : OpIterClose: 5,
158 1 : OpIterFirst: 100,
159 1 : OpIterLast: 100,
160 1 : OpIterNext: 100,
161 1 : OpIterNextWithLimit: 20,
162 1 : OpIterNextPrefix: 20,
163 1 : OpIterCanSingleDelete: 20,
164 1 : OpIterPrev: 100,
165 1 : OpIterPrevWithLimit: 20,
166 1 : OpIterSeekGE: 100,
167 1 : OpIterSeekGEWithLimit: 20,
168 1 : OpIterSeekLT: 100,
169 1 : OpIterSeekLTWithLimit: 20,
170 1 : OpIterSeekPrefixGE: 100,
171 1 : OpIterSetBounds: 100,
172 1 : OpIterSetOptions: 10,
173 1 : OpNewBatch: 5,
174 1 : OpNewIndexedBatch: 5,
175 1 : OpNewIter: 10,
176 1 : OpNewIterUsingClone: 5,
177 1 : OpNewSnapshot: 10,
178 1 : OpReaderGet: 100,
179 1 : OpReplicate: 0,
180 1 : OpSnapshotClose: 10,
181 1 : OpWriterApply: 10,
182 1 : OpWriterDelete: 100,
183 1 : OpWriterDeleteRange: 50,
184 1 : OpWriterIngest: 100,
185 1 : OpWriterIngestAndExcise: 50,
186 1 : OpWriterLogData: 10,
187 1 : OpWriterMerge: 100,
188 1 : OpWriterRangeKeySet: 10,
189 1 : OpWriterRangeKeyUnset: 10,
190 1 : OpWriterRangeKeyDelete: 5,
191 1 : OpWriterSet: 100,
192 1 : OpWriterSingleDelete: 50,
193 1 : OpNewExternalObj: 5,
194 1 : OpWriterIngestExternalFiles: 100,
195 1 : },
196 1 : // Use a new prefix 75% of the time (and 25% of the time use an existing
197 1 : // prefix with an alternative suffix).
198 1 : newPrefix: 0.75,
199 1 : // Use a skewed distribution of suffixes to mimic MVCC timestamps. The
200 1 : // range will be widened whenever a suffix is found to already be in use
201 1 : // for a particular prefix.
202 1 : writeSuffixDist: mustDynamic(randvar.NewSkewedLatest(0, 1, 0.99)),
203 1 : }
204 1 : }
205 :
206 : // ReadOpConfig builds an OpConfig that performs only read operations.
207 0 : func ReadOpConfig() OpConfig {
208 0 : return OpConfig{
209 0 : // dbClose is not in this list since it is deterministically generated once, at the end of the test.
210 0 : ops: [NumOpTypes]int{
211 0 : OpBatchAbort: 0,
212 0 : OpBatchCommit: 0,
213 0 : OpDBCheckpoint: 0,
214 0 : OpDBCompact: 0,
215 0 : OpDBFlush: 0,
216 0 : OpDBRatchetFormatMajorVersion: 0,
217 0 : OpDBRestart: 0,
218 0 : OpIterClose: 5,
219 0 : OpIterFirst: 100,
220 0 : OpIterLast: 100,
221 0 : OpIterNext: 100,
222 0 : OpIterNextWithLimit: 20,
223 0 : OpIterNextPrefix: 20,
224 0 : OpIterPrev: 100,
225 0 : OpIterPrevWithLimit: 20,
226 0 : OpIterSeekGE: 100,
227 0 : OpIterSeekGEWithLimit: 20,
228 0 : OpIterSeekLT: 100,
229 0 : OpIterSeekLTWithLimit: 20,
230 0 : OpIterSeekPrefixGE: 100,
231 0 : OpIterSetBounds: 100,
232 0 : OpIterSetOptions: 10,
233 0 : OpNewBatch: 0,
234 0 : OpNewIndexedBatch: 0,
235 0 : OpNewIter: 10,
236 0 : OpNewIterUsingClone: 5,
237 0 : OpNewSnapshot: 10,
238 0 : OpReaderGet: 100,
239 0 : OpSnapshotClose: 10,
240 0 : OpWriterApply: 0,
241 0 : OpWriterDelete: 0,
242 0 : OpWriterDeleteRange: 0,
243 0 : OpWriterIngest: 0,
244 0 : OpWriterLogData: 0,
245 0 : OpWriterMerge: 0,
246 0 : OpWriterRangeKeySet: 0,
247 0 : OpWriterRangeKeyUnset: 0,
248 0 : OpWriterRangeKeyDelete: 0,
249 0 : OpWriterSet: 0,
250 0 : OpWriterSingleDelete: 0,
251 0 : },
252 0 : // Use a new prefix 75% of the time (and 25% of the time use an existing
253 0 : // prefix with an alternative suffix).
254 0 : newPrefix: 0.75,
255 0 : // Use a skewed distribution of suffixes to mimic MVCC timestamps. The
256 0 : // range will be widened whenever a suffix is found to already be in use
257 0 : // for a particular prefix.
258 0 : writeSuffixDist: mustDynamic(randvar.NewSkewedLatest(0, 1, 0.99)),
259 0 : }
260 0 : }
261 :
262 : // WriteOpConfig builds an OpConfig suitable for generating a random test
263 : // database. It generates Writer operations and some meta database operations
264 : // like flushes and manual compactions, but it does not generate any reads.
265 0 : func WriteOpConfig() OpConfig {
266 0 : return OpConfig{
267 0 : // dbClose is not in this list since it is deterministically generated once, at the end of the test.
268 0 : ops: [NumOpTypes]int{
269 0 : OpBatchAbort: 0,
270 0 : OpBatchCommit: 5,
271 0 : OpDBCheckpoint: 0,
272 0 : OpDBCompact: 1,
273 0 : OpDBFlush: 2,
274 0 : OpDBRatchetFormatMajorVersion: 1,
275 0 : OpDBRestart: 2,
276 0 : OpIterClose: 0,
277 0 : OpIterFirst: 0,
278 0 : OpIterLast: 0,
279 0 : OpIterNext: 0,
280 0 : OpIterNextWithLimit: 0,
281 0 : OpIterNextPrefix: 0,
282 0 : OpIterPrev: 0,
283 0 : OpIterPrevWithLimit: 0,
284 0 : OpIterSeekGE: 0,
285 0 : OpIterSeekGEWithLimit: 0,
286 0 : OpIterSeekLT: 0,
287 0 : OpIterSeekLTWithLimit: 0,
288 0 : OpIterSeekPrefixGE: 0,
289 0 : OpIterSetBounds: 0,
290 0 : OpIterSetOptions: 0,
291 0 : OpNewBatch: 10,
292 0 : OpNewIndexedBatch: 0,
293 0 : OpNewIter: 0,
294 0 : OpNewIterUsingClone: 0,
295 0 : OpNewSnapshot: 10,
296 0 : OpReaderGet: 0,
297 0 : OpSnapshotClose: 10,
298 0 : OpWriterApply: 10,
299 0 : OpWriterDelete: 100,
300 0 : OpWriterDeleteRange: 20,
301 0 : OpWriterIngest: 100,
302 0 : OpWriterLogData: 10,
303 0 : OpWriterMerge: 100,
304 0 : OpWriterRangeKeySet: 10,
305 0 : OpWriterRangeKeyUnset: 10,
306 0 : OpWriterRangeKeyDelete: 5,
307 0 : OpWriterSet: 100,
308 0 : OpWriterSingleDelete: 50,
309 0 : },
310 0 : // Use a new prefix 75% of the time (and 25% of the time use an existing
311 0 : // prefix with an alternative suffix).
312 0 : newPrefix: 0.75,
313 0 : // Use a skewed distribution of suffixes to mimic MVCC timestamps. The
314 0 : // range will be widened whenever a suffix is found to already be in use
315 0 : // for a particular prefix.
316 0 : writeSuffixDist: mustDynamic(randvar.NewSkewedLatest(0, 1, 0.99)),
317 0 : }
318 0 : }
319 :
320 1 : func multiInstanceConfig() OpConfig {
321 1 : cfg := DefaultOpConfig()
322 1 : cfg.ops[OpReplicate] = 5
323 1 : // Single deletes and merges are disabled in multi-instance mode, as
324 1 : // replicateOp doesn't support them.
325 1 : cfg.ops[OpWriterSingleDelete] = 0
326 1 : cfg.ops[OpWriterMerge] = 0
327 1 :
328 1 : // TODO(radu): external file ingest doesn't yet work with OpReplicate ("cannot
329 1 : // use skip-shared iteration due to non-shareable files in lower levels").
330 1 : cfg.ops[OpNewExternalObj] = 0
331 1 : cfg.ops[OpWriterIngestExternalFiles] = 0
332 1 : return cfg
333 1 : }
334 :
335 1 : func mustDynamic(dyn randvar.Dynamic, err error) randvar.Dynamic {
336 1 : if err != nil {
337 0 : panic(err)
338 : }
339 1 : return dyn
340 : }
341 :
342 : var knownKeyFormats = []KeyFormat{
343 : TestkeysKeyFormat,
344 : }
345 :
346 1 : var keyFormatsByName = func() map[string]KeyFormat {
347 1 : m := make(map[string]KeyFormat)
348 1 : for _, kf := range knownKeyFormats {
349 1 : m[kf.Name] = kf
350 1 : }
351 1 : return m
352 : }()
353 :
354 : // A KeyFormat dictates the format of key-value pairs uses by the metamorphic
355 : // test.
356 : type KeyFormat struct {
357 : Name string
358 : Comparer *base.Comparer
359 : KeySchema *pebble.KeySchema
360 : FormatKey func(UserKey) string
361 : FormatKeySuffix func(UserKeySuffix) string
362 : ParseFormattedKey func(string) (UserKey, error)
363 : ParseFormattedKeySuffix func(string) (UserKeySuffix, error)
364 : NewGenerator func(*keyManager, *rand.Rand, OpConfig) KeyGenerator
365 : NewSuffixFilterMask func() pebble.BlockPropertyFilterMask
366 : NewSuffixBlockPropertyFilter func(min []byte, max []byte) sstable.BlockPropertyFilter
367 : }
368 :
369 : // KeyGenerator is an interface for generating keys, prefixes and suffixes.
370 : type KeyGenerator interface {
371 : // IncMaxSuffix increases the max suffix range and returns the new maximum
372 : // suffix (which is guaranteed to be larger than any previously generated
373 : // suffix).
374 : IncMaxSuffix() []byte
375 : // RandKey returns a random key (either a previously known key, or a new
376 : // key). The provided probability determines the likelihood of generating a
377 : // new key.
378 : RandKey(newKeyProbability float64) []byte
379 : // RandKeyInRange returns a random key (either a previously known key, or a
380 : // new key) in the given key range.
381 : RandKeyInRange(newKeyProbability float64, kr pebble.KeyRange) []byte
382 : // RandPrefix returns a random prefix key (a key with no suffix). The
383 : // provided probability determines the likelihood of generating a new
384 : // prefix.
385 : RandPrefix(newPrefix float64) []byte
386 : // SkewedSuffix generates a random suffix according to the configuration's
387 : // suffix distribution. It takes a probability 0 ≤ p ≤ 1.0 indicating the
388 : // probability with which the generator should increase the max suffix
389 : // generated by the generator.
390 : //
391 : // May return a nil suffix, with the probability the configuration's suffix
392 : // distribution assigns to the zero suffix.
393 : SkewedSuffix(incMaxProb float64) []byte
394 : // SuffixRange generates a new uniformly random range of suffixes [low,
395 : // high) such that high is guaranteed to be strictly greater than low.
396 : SuffixRange() (low, high []byte)
397 : // UniformSuffix returns a suffix in the same range as SkewedSuffix but with
398 : // a uniform distribution. This is used during reads to better exercise
399 : // reading a mix of older and newer keys. The suffix can be empty.
400 : //
401 : // May return a nil suffix.
402 : UniformSuffix() []byte
403 : // UniqueKeys takes a key-generating function and uses it to generate n
404 : // unique keys, returning them in sorted order.
405 : UniqueKeys(n int, genFn func() []byte) [][]byte
406 : }
|
