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 1 : func (c OpConfig) WithNewPrefixProbability(p float64) OpConfig {
101 1 : c.newPrefix = p
102 1 : return c
103 1 : }
104 :
105 : // WithOpWeight returns a modified op configuration with the weight of the
106 : // provided operation type overidden.
107 1 : func (c OpConfig) WithOpWeight(op OpType, weight int) OpConfig {
108 1 : c.ops[op] = weight
109 1 : return c
110 1 : }
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 1 : func DefaultOpConfig() OpConfig {
139 1 : return OpConfig{
140 1 : // dbClose is not in this list since it is deterministically generated once, at the end of the test.
141 1 : ops: [NumOpTypes]int{
142 1 : OpBatchAbort: 5,
143 1 : OpBatchCommit: 5,
144 1 : OpDBCheckpoint: 1,
145 1 : OpDBCompact: 1,
146 1 : OpDBDownload: 1,
147 1 : OpDBFlush: 2,
148 1 : OpDBRatchetFormatMajorVersion: 1,
149 1 : OpDBRestart: 2,
150 1 : OpIterClose: 5,
151 1 : OpIterFirst: 100,
152 1 : OpIterLast: 100,
153 1 : OpIterNext: 100,
154 1 : OpIterNextWithLimit: 20,
155 1 : OpIterNextPrefix: 20,
156 1 : OpIterCanSingleDelete: 20,
157 1 : OpIterPrev: 100,
158 1 : OpIterPrevWithLimit: 20,
159 1 : OpIterSeekGE: 100,
160 1 : OpIterSeekGEWithLimit: 20,
161 1 : OpIterSeekLT: 100,
162 1 : OpIterSeekLTWithLimit: 20,
163 1 : OpIterSeekPrefixGE: 100,
164 1 : OpIterSetBounds: 100,
165 1 : OpIterSetOptions: 10,
166 1 : OpNewBatch: 5,
167 1 : OpNewIndexedBatch: 5,
168 1 : OpNewIter: 10,
169 1 : OpNewIterUsingClone: 5,
170 1 : OpNewSnapshot: 10,
171 1 : OpReaderGet: 100,
172 1 : OpReplicate: 0,
173 1 : OpSnapshotClose: 10,
174 1 : OpWriterApply: 10,
175 1 : OpWriterDelete: 100,
176 1 : OpWriterDeleteRange: 50,
177 1 : OpWriterIngest: 100,
178 1 : OpWriterIngestAndExcise: 50,
179 1 : OpWriterLogData: 10,
180 1 : OpWriterMerge: 100,
181 1 : OpWriterRangeKeySet: 10,
182 1 : OpWriterRangeKeyUnset: 10,
183 1 : OpWriterRangeKeyDelete: 5,
184 1 : OpWriterSet: 100,
185 1 : OpWriterSingleDelete: 50,
186 1 : OpNewExternalObj: 5,
187 1 : OpWriterIngestExternalFiles: 100,
188 1 : },
189 1 : // Use a new prefix 75% of the time (and 25% of the time use an existing
190 1 : // prefix with an alternative suffix).
191 1 : newPrefix: 0.75,
192 1 : // Use a skewed distribution of suffixes to mimic MVCC timestamps. The
193 1 : // range will be widened whenever a suffix is found to already be in use
194 1 : // for a particular prefix.
195 1 : writeSuffixDist: mustDynamic(randvar.NewSkewedLatest(0, 1, 0.99)),
196 1 : }
197 1 : }
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 1 : func multiInstanceConfig() OpConfig {
314 1 : cfg := DefaultOpConfig()
315 1 : cfg.ops[OpReplicate] = 5
316 1 : // Single deletes and merges are disabled in multi-instance mode, as
317 1 : // replicateOp doesn't support them.
318 1 : cfg.ops[OpWriterSingleDelete] = 0
319 1 : cfg.ops[OpWriterMerge] = 0
320 1 :
321 1 : // TODO(radu): external file ingest doesn't yet work with OpReplicate ("cannot
322 1 : // use skip-shared iteration due to non-shareable files in lower levels").
323 1 : cfg.ops[OpNewExternalObj] = 0
324 1 : cfg.ops[OpWriterIngestExternalFiles] = 0
325 1 : return cfg
326 1 : }
327 :
328 1 : func mustDynamic(dyn randvar.Dynamic, err error) randvar.Dynamic {
329 1 : if err != nil {
330 0 : panic(err)
331 : }
332 1 : return dyn
333 : }
|
