Repository navigation
Expand file tree
/
Copy pathsession_compaction.go
More file actions
253 lines (225 loc) · 7.77 KB
/
Copy pathsession_compaction.go
File metadata and controls
253 lines (225 loc) · 7.77 KB
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
package granite
import (
"sort"
"github.com/DecarbonizedGlucose/granite/iterator"
mt "github.com/DecarbonizedGlucose/granite/memtable"
)
func compactionLevelSize(level int) int64 {
size := int64(compactionLevelBaseBytes)
for i := 0; i < level; i++ {
size *= compactionLevelSizeMultiplier
}
return size
}
// compaction represents a compaction state.
type compaction struct {
session *session
version *version
level int
sourceTables tableFiles
targetTables tableFiles
grandparentTables tableFiles
grandparentIndex int
seenInputKey bool
grandparentOverlapSize int64
smallestKey internalKey
largestKey internalKey
deeperLevelIndexes []int
}
// expandInputs includes every table needed to compact a complete key range.
// The caller serializes version changes with DB.compactionMu.
func (c *compaction) expandInputs() {
limit := int64(compactionExpandBytes)
allSourceTables := c.version.levels[c.level]
var allTargetTables tableFiles
if targetLevel := c.level + 1; targetLevel < len(c.version.levels) {
allTargetTables = c.version.levels[targetLevel]
}
sourceTables := c.sourceTables
targetTables := c.targetTables
smallestKey, largestKey := sourceTables.getRange(c.session.ikc)
// L0 table ranges may overlap. Include the complete overlap closure so a
// user key cannot remain split between compacted and uncompacted tables.
if c.level == 0 {
sourceTables = allSourceTables.getOverlaps(
sourceTables, c.session.ikc, smallestKey.ukey(), largestKey.ukey(), true,
)
if len(sourceTables) != len(c.sourceTables) {
smallestKey, largestKey = sourceTables.getRange(c.session.ikc)
}
}
targetTables = allTargetTables.getOverlaps(
targetTables, c.session.ikc, smallestKey.ukey(), largestKey.ukey(), false,
)
compactionSmallest, compactionLargest := append(sourceTables, targetTables...).getRange(c.session.ikc)
// Add more source tables when doing so stays below the input limit and
// does not pull in another target table.
if len(targetTables) > 0 {
expandedSource := allSourceTables.getOverlaps(
nil, c.session.ikc, compactionSmallest.ukey(), compactionLargest.ukey(), c.level == 0,
)
if len(expandedSource) > len(sourceTables) && targetTables.size()+expandedSource.size() < limit {
expandedSmallest, expandedLargest := expandedSource.getRange(c.session.ikc)
expandedTarget := allTargetTables.getOverlaps(
nil, c.session.ikc, expandedSmallest.ukey(), expandedLargest.ukey(), false,
)
if len(expandedTarget) == len(targetTables) {
smallestKey, largestKey = expandedSmallest, expandedLargest
sourceTables, targetTables = expandedSource, expandedTarget
compactionSmallest, compactionLargest = append(sourceTables, targetTables...).getRange(c.session.ikc)
}
}
}
// Track overlapping tables two levels below the source. Output tables are
// split when too much of that level would overlap one output file.
if grandparentLevel := c.level + 2; grandparentLevel < len(c.version.levels) {
c.grandparentTables = c.version.levels[grandparentLevel].getOverlaps(
c.grandparentTables,
c.session.ikc,
compactionSmallest.ukey(),
compactionLargest.ukey(),
false,
)
}
c.sourceTables = sourceTables
c.targetTables = targetTables
c.smallestKey = smallestKey
c.largestKey = largestKey
}
func (c *compaction) isTrivialMove() bool {
return len(c.sourceTables) == 1 &&
len(c.targetTables) == 0 &&
c.grandparentTables.size() <= compactionGrandparentBytes
}
// keyAbsentFromDeeperLevels reports whether levels below the compaction target
// contain no older value for userKey. Only then may compaction drop a tombstone.
func (c *compaction) keyAbsentFromDeeperLevels(userKey []byte) bool {
for level := c.level + 2; level < len(c.version.levels); level++ {
tables := c.version.levels[level]
for c.deeperLevelIndexes[level] < len(tables) {
table := tables[c.deeperLevelIndexes[level]]
if c.session.ikc.CompareUser(userKey, table.imax.ukey()) <= 0 {
if c.session.ikc.CompareUser(userKey, table.imin.ukey()) >= 0 {
return false
}
break
}
c.deeperLevelIndexes[level]++
}
}
return true
}
// shouldSplitOutputBefore advances the overlap accounting to key and reports
// whether the current output table should end before that key.
func (c *compaction) shouldSplitOutputBefore(key internalKey) bool {
for ; c.grandparentIndex < len(c.grandparentTables); c.grandparentIndex++ {
grandparent := c.grandparentTables[c.grandparentIndex]
if c.session.ikc.Compare(key, grandparent.imax) <= 0 {
break
}
if c.seenInputKey {
c.grandparentOverlapSize += grandparent.size
}
}
c.seenInputKey = true
if c.grandparentOverlapSize > compactionGrandparentBytes {
c.grandparentOverlapSize = 0
return true
}
return false
}
func (c *compaction) newInputIterator() iterator.InternalIterator {
var inputs []iterator.InternalIterator
readOptions := &ReadOptions{DontFillCache: true}
for offset, tables := range [...]tableFiles{c.sourceTables, c.targetTables} {
if len(tables) == 0 {
continue
}
if c.level+offset == 0 {
// L0 tables overlap, so they are independent merge inputs.
for _, table := range tables {
inputs = append(inputs, c.session.tops.newIterator(table, nil, readOptions))
}
} else {
// Higher levels are sorted and non-overlapping. Open one table at
// a time instead of pinning every compaction input at once.
inputs = append(inputs, newTableSequenceIterator(c.session.tops, tables, readOptions))
}
}
return iterator.NewMergedIterator(inputs, c.session.ikc)
}
func newCompaction(s *session, v *version, level int, sourceTables tableFiles) *compaction {
c := &compaction{
session: s,
version: v,
level: level,
sourceTables: sourceTables,
deeperLevelIndexes: make([]int, len(v.levels)),
}
c.expandInputs()
return c
}
// compactionForRange builds a compaction containing tables that overlap the
// user-key range. The caller serializes version changes with DB.compactionMu.
func (s *session) compactionForRange(level int, smallest, largest []byte, noLimit bool) *compaction {
v := s.version()
if level >= len(v.levels) {
return nil
}
sourceTables := v.levels[level].getOverlaps(nil, s.ikc, smallest, largest, level == 0)
if len(sourceTables) == 0 {
return nil
}
// Avoid compacting too much in one shot when the range is large. L0 is
// exempt because all overlapping L0 tables must move together.
if !noLimit && level > 0 {
limit := int64(compactionSourceBytes)
total := int64(0)
for i, table := range sourceTables {
total += table.size
if total >= limit {
sourceTables = sourceTables[:i+1]
break
}
}
}
return newCompaction(s, v, level, sourceTables)
}
// flushMemTable writes one immutable memtable to a new L0 table.
func (s *session) flushMemTable(rec *manifestRecord, mem *mt.MemTable) error {
iter := mem.NewMTIter(nil, nil)
defer iter.Close()
table, _, err := s.tops.createFrom(iter)
if err != nil {
return err
}
rec.addTableFile(0, table)
return nil
}
// nextCompaction chooses one compaction from the current size scores. The
// caller serializes version changes with DB.compactionMu.
func (s *session) nextCompaction() *compaction {
v := s.version()
var level int
var sourceTables tableFiles
if v.compactionScore >= 1 {
level = v.compactionLevel
pointer := s.compactionPointer(level)
tables := v.levels[level]
if pointer != nil && level > 0 {
n := len(tables)
if i := sort.Search(n, func(i int) bool {
return s.ikc.Compare(tables[i].imax, pointer) > 0
}); i < n {
sourceTables = append(sourceTables, tables[i])
}
}
if len(sourceTables) == 0 {
sourceTables = append(sourceTables, tables[0])
}
} else {
// Seek-compaction has been removed; only size-score triggers compaction.
return nil
}
return newCompaction(s, v, level, sourceTables)
}