forked from cockroachdb/pebble
-
Notifications
You must be signed in to change notification settings - Fork 1
/
compaction_picker.go
293 lines (257 loc) · 9.37 KB
/
compaction_picker.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
// Copyright 2018 The LevelDB-Go and Pebble Authors. All rights reserved. Use
// of this source code is governed by a BSD-style license that can be found in
// the LICENSE file.
package pebble
import (
"math"
)
// compactionPicker holds the state and logic for picking a compaction. A
// compaction picker is associated with a single version. A new compaction
// picker is created and initialized every time a new version is installed.
type compactionPicker struct {
opts *Options
vers *version
// The level to target for L0 compactions. Levels L1 to baseLevel must be
// empty.
baseLevel int
// smoothedLevelMultiplier is the size ratio between one level and the next.
smoothedLevelMultiplier float64
// levelMaxBytes holds the dynamically adjusted max bytes setting for each
// level.
levelMaxBytes [numLevels]int64
// These fields are the level that should be compacted next and its
// compaction score. A score < 1 means that compaction is not strictly
// needed.
score float64
level int
file int
}
func newCompactionPicker(v *version, opts *Options) *compactionPicker {
p := &compactionPicker{
opts: opts,
vers: v,
}
p.initLevelMaxBytes(v, opts)
p.initTarget(v, opts)
return p
}
func (p *compactionPicker) compactionNeeded() bool {
if p == nil {
return false
}
return p.score >= 1
}
// estimatedCompactionDebt estimates the number of bytes which need to be
// compacted before the LSM tree becomes stable.
func (p *compactionPicker) estimatedCompactionDebt(l0ExtraSize uint64) uint64 {
if p == nil {
return 0
}
compactionDebt := totalSize(p.vers.files[0]) + l0ExtraSize
bytesAddedToNextLevel := compactionDebt
levelSize := totalSize(p.vers.files[p.baseLevel])
// estimatedL0CompactionSize is the estimated size of the L0 component in the
// current or next L0->LBase compaction. This is needed to estimate the number
// of L0->LBase compactions which will need to occur for the LSM tree to
// become stable.
estimatedL0CompactionSize := uint64(p.opts.L0CompactionThreshold * p.opts.MemTableSize)
// The ratio bytesAddedToNextLevel(L0 Size)/estimatedL0CompactionSize is the
// estimated number of L0->LBase compactions which will need to occur for the
// LSM tree to become stable. We multiply this by levelSize(LBase size) to
// estimate the compaction debt incurred by LBase in the L0->LBase compactions.
compactionDebt += (levelSize * bytesAddedToNextLevel) / estimatedL0CompactionSize
var nextLevelSize uint64
for level := p.baseLevel; level < numLevels - 1; level++ {
levelSize += bytesAddedToNextLevel
bytesAddedToNextLevel = 0
nextLevelSize = totalSize(p.vers.files[level + 1])
if levelSize > uint64(p.levelMaxBytes[level]) {
bytesAddedToNextLevel = levelSize - uint64(p.levelMaxBytes[level])
levelRatio := float64(nextLevelSize)/float64(levelSize)
compactionDebt += uint64(float64(bytesAddedToNextLevel) * (levelRatio + 1))
}
levelSize = nextLevelSize
}
return compactionDebt
}
// estimatedMaxWAmp estimates the maximum possible write amp per byte that is
// added to L0.
func (p *compactionPicker) estimatedMaxWAmp() float64 {
return float64(numLevels - p.baseLevel) * (p.smoothedLevelMultiplier + 1)
}
func (p *compactionPicker) initLevelMaxBytes(v *version, opts *Options) {
// Determine the first non-empty level and the maximum size of any level.
firstNonEmptyLevel := -1
var bottomLevelSize int64
for level := 1; level < numLevels; level++ {
levelSize := int64(totalSize(v.files[level]))
if levelSize > 0 {
if firstNonEmptyLevel == -1 {
firstNonEmptyLevel = level
}
bottomLevelSize = levelSize
}
}
// Initialize the max-bytes setting for each level to "infinity" which will
// disallow compaction for that level. We'll fill in the actual value below
// for levels we want to allow compactions from.
for level := 0; level < numLevels; level++ {
p.levelMaxBytes[level] = math.MaxInt64
}
if bottomLevelSize == 0 {
// No levels for L1 and up contain any data. Target L0 compactions for the
// last level.
p.baseLevel = numLevels - 1
return
}
levelMultiplier := 10.0
baseBytesMax := opts.LBaseMaxBytes
baseBytesMin := int64(float64(baseBytesMax) / levelMultiplier)
curLevelSize := bottomLevelSize
for level := numLevels - 2; level >= firstNonEmptyLevel; level-- {
curLevelSize = int64(float64(curLevelSize) / levelMultiplier)
}
if curLevelSize <= baseBytesMin {
// If we make target size of last level to be bottomLevelSize, target size of
// the first non-empty level would be smaller than baseBytesMin. We set it
// be baseBytesMin.
p.baseLevel = firstNonEmptyLevel
} else {
// Compute base level (where L0 data is compacted to).
p.baseLevel = firstNonEmptyLevel
for p.baseLevel > 1 && curLevelSize > baseBytesMax {
p.baseLevel--
curLevelSize = int64(float64(curLevelSize) / levelMultiplier)
}
}
if p.baseLevel < numLevels-1 {
p.smoothedLevelMultiplier = math.Pow(
float64(bottomLevelSize)/float64(baseBytesMax),
1.0/float64(numLevels-p.baseLevel-1))
} else {
p.smoothedLevelMultiplier = 1.0
}
levelSize := float64(baseBytesMax)
for level := p.baseLevel; level < numLevels; level++ {
if level > p.baseLevel && levelSize > 0 {
levelSize *= p.smoothedLevelMultiplier
}
// Round the result since test cases use small target level sizes, which
// can be impacted by floating-point imprecision + integer truncation.
roundedLevelSize := math.Round(levelSize)
if roundedLevelSize > float64(math.MaxInt64) {
p.levelMaxBytes[level] = math.MaxInt64
} else {
p.levelMaxBytes[level] = int64(roundedLevelSize)
}
}
}
// initTarget initializes the compaction score and level. If the compaction
// score indicates compaction is needed, a target table within the target level
// is selected for compaction.
func (p *compactionPicker) initTarget(v *version, opts *Options) {
// We treat level-0 specially by bounding the number of files instead of
// number of bytes for two reasons:
//
// (1) With larger write-buffer sizes, it is nice not to do too many
// level-0 compactions.
//
// (2) The files in level-0 are merged on every read and therefore we
// wish to avoid too many files when the individual file size is small
// (perhaps because of a small write-buffer setting, or very high
// compression ratios, or lots of overwrites/deletions).
p.score = float64(len(v.files[0])) / float64(opts.L0CompactionThreshold)
p.level = 0
for level := 1; level < numLevels-1; level++ {
score := float64(totalSize(v.files[level])) / float64(p.levelMaxBytes[level])
if p.score < score {
p.score = score
p.level = level
}
}
if p.score >= 1 {
// TODO(peter): Select the file within the level to compact. See the
// kMinOverlappingRatio heuristic in RocksDB which chooses the file with the
// minimum overlapping ratio with the next level. This minimizes write
// amplification. We also want to computed a "compensated size" which adjusts
// the size of a table based on the number of deletions it contains.
//
// We want to minimize write amplification, but also ensure that deletes
// are propagated to the bottom level in a timely fashion so as to reclaim
// disk space. A table's smallest sequence number provides a measure of its
// age. The ratio of overlapping-bytes / table-size gives an indication of
// write amplification (a smaller ratio is preferrable).
//
// Simulate various workloads:
// - Uniform random write
// - Uniform random write+delete
// - Skewed random write
// - Skewed random write+delete
// - Sequential write
// - Sequential write+delete (queue)
// The current heuristic matches the RocksDB kOldestSmallestSeqFirst
// heuristic.
smallestSeqNum := uint64(math.MaxUint64)
files := v.files[p.level]
for i := range files {
f := &files[i]
if smallestSeqNum > f.smallestSeqNum {
smallestSeqNum = f.smallestSeqNum
p.file = i
}
}
return
}
// No levels exceeded their size threshold. Check for forced compactions.
for level := 0; level < numLevels-1; level++ {
files := v.files[p.level]
for i := range files {
f := &files[i]
if f.markedForCompaction {
p.score = 1.0
p.level = level
p.file = i
return
}
}
}
// TODO(peter): When a snapshot is released, we may need to compact tables at
// the bottom level in order to free up entries that were pinned by the
// snapshot.
}
// pickAuto picks the best compaction, if any.
func (p *compactionPicker) pickAuto(opts *Options) (c *compaction) {
if !p.compactionNeeded() {
return nil
}
vers := p.vers
c = newCompaction(opts, vers, p.level, p.baseLevel)
c.inputs[0] = vers.files[c.startLevel][p.file : p.file+1]
// Files in level 0 may overlap each other, so pick up all overlapping ones.
if c.startLevel == 0 {
cmp := opts.Comparer.Compare
smallest, largest := ikeyRange(cmp, c.inputs[0], nil)
c.inputs[0] = vers.overlaps(0, cmp, smallest.UserKey, largest.UserKey)
if len(c.inputs) == 0 {
panic("pebble: empty compaction")
}
}
c.setupOtherInputs()
return c
}
func (p *compactionPicker) pickManual(opts *Options, manual *manualCompaction) (c *compaction) {
if p == nil {
return nil
}
// TODO(peter): The logic here is untested and possibly incomplete.
cur := p.vers
c = newCompaction(opts, cur, manual.level, p.baseLevel)
manual.outputLevel = c.outputLevel
cmp := opts.Comparer.Compare
c.inputs[0] = cur.overlaps(manual.level, cmp, manual.start.UserKey, manual.end.UserKey)
if len(c.inputs[0]) == 0 {
return nil
}
c.setupOtherInputs()
return c
}