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 "github.com/cockroachdb/pebble/internal/randvar"
8 :
9 : // OpType is an enum of possible operation types.
10 : type OpType int
11 :
12 : // These constants define the set of possible operation types performed by the
13 : // metamorphic test.
14 : const (
15 : OpBatchAbort OpType = iota
16 : OpBatchCommit
17 : OpDBCheckpoint
18 : OpDBClose
19 : OpDBCompact
20 : OpDBFlush
21 : OpDBRatchetFormatMajorVersion
22 : OpDBRestart
23 : OpIterClose
24 : OpIterFirst
25 : OpIterLast
26 : OpIterNext
27 : OpIterNextWithLimit
28 : OpIterNextPrefix
29 : OpIterCanSingleDelete
30 : OpIterPrev
31 : OpIterPrevWithLimit
32 : OpIterSeekGE
33 : OpIterSeekGEWithLimit
34 : OpIterSeekLT
35 : OpIterSeekLTWithLimit
36 : OpIterSeekPrefixGE
37 : OpIterSetBounds
38 : OpIterSetOptions
39 : OpNewBatch
40 : OpNewIndexedBatch
41 : OpNewIter
42 : OpNewIterUsingClone
43 : OpNewSnapshot
44 : OpNewExternalObj
45 : OpReaderGet
46 : OpReplicate
47 : OpSnapshotClose
48 : OpWriterApply
49 : OpWriterDelete
50 : OpWriterDeleteRange
51 : OpWriterIngest
52 : OpWriterIngestAndExcise
53 : OpWriterIngestExternalFiles
54 : OpWriterLogData
55 : OpWriterMerge
56 : OpWriterRangeKeyDelete
57 : OpWriterRangeKeySet
58 : OpWriterRangeKeyUnset
59 : OpWriterSet
60 : OpWriterSingleDelete
61 : NumOpTypes
62 : )
63 :
64 1 : func (o OpType) isDelete() bool {
65 1 : return o == OpWriterDelete || o == OpWriterDeleteRange || o == OpWriterSingleDelete
66 1 : }
67 :
68 : // OpConfig describes the distribution of operations and their attributes.
69 : type OpConfig struct {
70 : // Weights for the operation mix to generate. ops[i] corresponds to the
71 : // weight for opType(i).
72 : ops [NumOpTypes]int
73 :
74 : // newPrefix configures the probability that when generating a new user key,
75 : // the generated key uses a new key prefix rather than an existing prefix
76 : // with a suffix.
77 : newPrefix float64
78 : // writeSuffixDist defines the distribution of key suffixes during writing.
79 : // It's a dynamic randvar to roughly emulate workloads with MVCC timestamps,
80 : // skewing towards most recent timestamps.
81 : writeSuffixDist randvar.Dynamic
82 :
83 : // numInstances defines the number of pebble instances created for this
84 : // metamorphic test run.
85 : numInstances int
86 :
87 : // TODO(peter): unimplemented
88 : // keyDist randvar.Dynamic
89 : // keySizeDist randvar.Static
90 : // valueSizeDist randvar.Static
91 : // updateFrac float64
92 : // lowerBoundFrac float64
93 : // upperBoundFrac float64
94 : }
95 :
96 : // WithNewPrefixProbability returns a modified op configuration with the
97 : // probability of generating a new key prefix set to the provided value in
98 : // [0,1.0].
99 2 : func (c OpConfig) WithNewPrefixProbability(p float64) OpConfig {
100 2 : c.newPrefix = p
101 2 : return c
102 2 : }
103 :
104 : // WithOpWeight returns a modified op configuration with the weight of the
105 : // provided operation type overidden.
106 2 : func (c OpConfig) WithOpWeight(op OpType, weight int) OpConfig {
107 2 : c.ops[op] = weight
108 2 : return c
109 2 : }
110 :
111 : var presetConfigs = []OpConfig{
112 : DefaultOpConfig(),
113 : // Generate a configuration that helps exercise code paths dependent on many
114 : // versions of keys with the same prefixes. The default configuration does
115 : // not tend to generate many versions of the same key. Additionally, its
116 : // relatively high weight for deletion write operations makes it less likely
117 : // that we'll accumulate enough versions to exercise some code paths (eg,
118 : // see #2921 which requires >16 SETs for versions of the same prefix to
119 : // reside in a single block to exercise the code path).
120 : //
121 : // To encourage generation of many versions of the same keys, generate a new
122 : // prefix only 4% of the time when generating a new key. The remaining 96%
123 : // of new key generations will use an existing prefix. To keep the size of
124 : // the database growing, we also reduce the probability of delete write
125 : // operations significantly.
126 : DefaultOpConfig().
127 : WithNewPrefixProbability(0.04).
128 : WithOpWeight(OpWriterDeleteRange, 1).
129 : WithOpWeight(OpWriterDelete, 5).
130 : WithOpWeight(OpWriterSingleDelete, 5).
131 : WithOpWeight(OpWriterMerge, 0),
132 : }
133 :
134 : var multiInstancePresetConfig = multiInstanceConfig()
135 :
136 : // DefaultOpConfig returns the default distribution of operations.
137 2 : func DefaultOpConfig() OpConfig {
138 2 : return OpConfig{
139 2 : // dbClose is not in this list since it is deterministically generated once, at the end of the test.
140 2 : ops: [NumOpTypes]int{
141 2 : OpBatchAbort: 5,
142 2 : OpBatchCommit: 5,
143 2 : OpDBCheckpoint: 1,
144 2 : OpDBCompact: 1,
145 2 : OpDBFlush: 2,
146 2 : OpDBRatchetFormatMajorVersion: 1,
147 2 : OpDBRestart: 2,
148 2 : OpIterClose: 5,
149 2 : OpIterFirst: 100,
150 2 : OpIterLast: 100,
151 2 : OpIterNext: 100,
152 2 : OpIterNextWithLimit: 20,
153 2 : OpIterNextPrefix: 20,
154 2 : OpIterCanSingleDelete: 20,
155 2 : OpIterPrev: 100,
156 2 : OpIterPrevWithLimit: 20,
157 2 : OpIterSeekGE: 100,
158 2 : OpIterSeekGEWithLimit: 20,
159 2 : OpIterSeekLT: 100,
160 2 : OpIterSeekLTWithLimit: 20,
161 2 : OpIterSeekPrefixGE: 100,
162 2 : OpIterSetBounds: 100,
163 2 : OpIterSetOptions: 10,
164 2 : OpNewBatch: 5,
165 2 : OpNewIndexedBatch: 5,
166 2 : OpNewIter: 10,
167 2 : OpNewIterUsingClone: 5,
168 2 : OpNewSnapshot: 10,
169 2 : OpReaderGet: 100,
170 2 : OpReplicate: 0,
171 2 : OpSnapshotClose: 10,
172 2 : OpWriterApply: 10,
173 2 : OpWriterDelete: 100,
174 2 : OpWriterDeleteRange: 50,
175 2 : OpWriterIngest: 100,
176 2 : OpWriterIngestAndExcise: 0, // TODO(bilal): Enable this.
177 2 : OpWriterLogData: 10,
178 2 : OpWriterMerge: 100,
179 2 : OpWriterRangeKeySet: 10,
180 2 : OpWriterRangeKeyUnset: 10,
181 2 : OpWriterRangeKeyDelete: 5,
182 2 : OpWriterSet: 100,
183 2 : OpWriterSingleDelete: 50,
184 2 : OpNewExternalObj: 5,
185 2 : OpWriterIngestExternalFiles: 100,
186 2 : },
187 2 : // Use a new prefix 75% of the time (and 25% of the time use an existing
188 2 : // prefix with an alternative suffix).
189 2 : newPrefix: 0.75,
190 2 : // Use a skewed distribution of suffixes to mimic MVCC timestamps. The
191 2 : // range will be widened whenever a suffix is found to already be in use
192 2 : // for a particular prefix.
193 2 : writeSuffixDist: mustDynamic(randvar.NewSkewedLatest(0, 1, 0.99)),
194 2 : }
195 2 : }
196 :
197 : // ReadOpConfig builds an OpConfig that performs only read operations.
198 1 : func ReadOpConfig() OpConfig {
199 1 : return OpConfig{
200 1 : // dbClose is not in this list since it is deterministically generated once, at the end of the test.
201 1 : ops: [NumOpTypes]int{
202 1 : OpBatchAbort: 0,
203 1 : OpBatchCommit: 0,
204 1 : OpDBCheckpoint: 0,
205 1 : OpDBCompact: 0,
206 1 : OpDBFlush: 0,
207 1 : OpDBRatchetFormatMajorVersion: 0,
208 1 : OpDBRestart: 0,
209 1 : OpIterClose: 5,
210 1 : OpIterFirst: 100,
211 1 : OpIterLast: 100,
212 1 : OpIterNext: 100,
213 1 : OpIterNextWithLimit: 20,
214 1 : OpIterNextPrefix: 20,
215 1 : OpIterPrev: 100,
216 1 : OpIterPrevWithLimit: 20,
217 1 : OpIterSeekGE: 100,
218 1 : OpIterSeekGEWithLimit: 20,
219 1 : OpIterSeekLT: 100,
220 1 : OpIterSeekLTWithLimit: 20,
221 1 : OpIterSeekPrefixGE: 100,
222 1 : OpIterSetBounds: 100,
223 1 : OpIterSetOptions: 10,
224 1 : OpNewBatch: 0,
225 1 : OpNewIndexedBatch: 0,
226 1 : OpNewIter: 10,
227 1 : OpNewIterUsingClone: 5,
228 1 : OpNewSnapshot: 10,
229 1 : OpReaderGet: 100,
230 1 : OpSnapshotClose: 10,
231 1 : OpWriterApply: 0,
232 1 : OpWriterDelete: 0,
233 1 : OpWriterDeleteRange: 0,
234 1 : OpWriterIngest: 0,
235 1 : OpWriterLogData: 0,
236 1 : OpWriterMerge: 0,
237 1 : OpWriterRangeKeySet: 0,
238 1 : OpWriterRangeKeyUnset: 0,
239 1 : OpWriterRangeKeyDelete: 0,
240 1 : OpWriterSet: 0,
241 1 : OpWriterSingleDelete: 0,
242 1 : },
243 1 : // Use a new prefix 75% of the time (and 25% of the time use an existing
244 1 : // prefix with an alternative suffix).
245 1 : newPrefix: 0.75,
246 1 : // Use a skewed distribution of suffixes to mimic MVCC timestamps. The
247 1 : // range will be widened whenever a suffix is found to already be in use
248 1 : // for a particular prefix.
249 1 : writeSuffixDist: mustDynamic(randvar.NewSkewedLatest(0, 1, 0.99)),
250 1 : }
251 1 : }
252 :
253 : // WriteOpConfig builds an OpConfig suitable for generating a random test
254 : // database. It generates Writer operations and some meta database operations
255 : // like flushes and manual compactions, but it does not generate any reads.
256 1 : func WriteOpConfig() OpConfig {
257 1 : return OpConfig{
258 1 : // dbClose is not in this list since it is deterministically generated once, at the end of the test.
259 1 : ops: [NumOpTypes]int{
260 1 : OpBatchAbort: 0,
261 1 : OpBatchCommit: 5,
262 1 : OpDBCheckpoint: 0,
263 1 : OpDBCompact: 1,
264 1 : OpDBFlush: 2,
265 1 : OpDBRatchetFormatMajorVersion: 1,
266 1 : OpDBRestart: 2,
267 1 : OpIterClose: 0,
268 1 : OpIterFirst: 0,
269 1 : OpIterLast: 0,
270 1 : OpIterNext: 0,
271 1 : OpIterNextWithLimit: 0,
272 1 : OpIterNextPrefix: 0,
273 1 : OpIterPrev: 0,
274 1 : OpIterPrevWithLimit: 0,
275 1 : OpIterSeekGE: 0,
276 1 : OpIterSeekGEWithLimit: 0,
277 1 : OpIterSeekLT: 0,
278 1 : OpIterSeekLTWithLimit: 0,
279 1 : OpIterSeekPrefixGE: 0,
280 1 : OpIterSetBounds: 0,
281 1 : OpIterSetOptions: 0,
282 1 : OpNewBatch: 10,
283 1 : OpNewIndexedBatch: 0,
284 1 : OpNewIter: 0,
285 1 : OpNewIterUsingClone: 0,
286 1 : OpNewSnapshot: 10,
287 1 : OpReaderGet: 0,
288 1 : OpSnapshotClose: 10,
289 1 : OpWriterApply: 10,
290 1 : OpWriterDelete: 100,
291 1 : OpWriterDeleteRange: 20,
292 1 : OpWriterIngest: 100,
293 1 : OpWriterLogData: 10,
294 1 : OpWriterMerge: 100,
295 1 : OpWriterRangeKeySet: 10,
296 1 : OpWriterRangeKeyUnset: 10,
297 1 : OpWriterRangeKeyDelete: 5,
298 1 : OpWriterSet: 100,
299 1 : OpWriterSingleDelete: 50,
300 1 : },
301 1 : // Use a new prefix 75% of the time (and 25% of the time use an existing
302 1 : // prefix with an alternative suffix).
303 1 : newPrefix: 0.75,
304 1 : // Use a skewed distribution of suffixes to mimic MVCC timestamps. The
305 1 : // range will be widened whenever a suffix is found to already be in use
306 1 : // for a particular prefix.
307 1 : writeSuffixDist: mustDynamic(randvar.NewSkewedLatest(0, 1, 0.99)),
308 1 : }
309 1 : }
310 :
311 2 : func multiInstanceConfig() OpConfig {
312 2 : cfg := DefaultOpConfig()
313 2 : cfg.ops[OpReplicate] = 5
314 2 : cfg.ops[OpWriterIngestAndExcise] = 50
315 2 : // Single deletes and merges are disabled in multi-instance mode, as
316 2 : // replicateOp and ingestAndExciseOp don't support them.
317 2 : cfg.ops[OpWriterSingleDelete] = 0
318 2 : cfg.ops[OpWriterMerge] = 0
319 2 :
320 2 : // TODO(radu): external file ingest doesn't yet work with OpReplicate ("cannot
321 2 : // use skip-shared iteration due to non-shareable files in lower levels").
322 2 : cfg.ops[OpNewExternalObj] = 0
323 2 : cfg.ops[OpWriterIngestExternalFiles] = 0
324 2 : return cfg
325 2 : }
326 :
327 2 : func mustDynamic(dyn randvar.Dynamic, err error) randvar.Dynamic {
328 2 : if err != nil {
329 0 : panic(err)
330 : }
331 2 : return dyn
332 : }
|
