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