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