compaction.go raw
1 /*
2 * SPDX-FileCopyrightText: © Hypermode Inc. <hello@hypermode.com>
3 * SPDX-License-Identifier: Apache-2.0
4 */
5
6 package badger
7
8 import (
9 "bytes"
10 "fmt"
11 "log"
12 "math"
13 "sync"
14
15 "github.com/dgraph-io/badger/v4/table"
16 "github.com/dgraph-io/badger/v4/y"
17 )
18
19 type keyRange struct {
20 left []byte
21 right []byte
22 inf bool
23 size int64 // size is used for Key splits.
24 }
25
26 func (r keyRange) isEmpty() bool {
27 return len(r.left) == 0 && len(r.right) == 0 && !r.inf
28 }
29
30 var infRange = keyRange{inf: true}
31
32 func (r keyRange) String() string {
33 return fmt.Sprintf("[left=%x, right=%x, inf=%v]", r.left, r.right, r.inf)
34 }
35
36 func (r keyRange) equals(dst keyRange) bool {
37 return bytes.Equal(r.left, dst.left) &&
38 bytes.Equal(r.right, dst.right) &&
39 r.inf == dst.inf
40 }
41
42 func (r *keyRange) extend(kr keyRange) {
43 // TODO(ibrahim): Is this needed?
44 if kr.isEmpty() {
45 return
46 }
47 if r.isEmpty() {
48 *r = kr
49 }
50 if len(r.left) == 0 || y.CompareKeys(kr.left, r.left) < 0 {
51 r.left = kr.left
52 }
53 if len(r.right) == 0 || y.CompareKeys(kr.right, r.right) > 0 {
54 r.right = kr.right
55 }
56 if kr.inf {
57 r.inf = true
58 }
59 }
60
61 func (r keyRange) overlapsWith(dst keyRange) bool {
62 // Empty keyRange always overlaps.
63 if r.isEmpty() {
64 return true
65 }
66 // TODO(ibrahim): Do you need this?
67 // Empty dst doesn't overlap with anything.
68 if dst.isEmpty() {
69 return false
70 }
71 if r.inf || dst.inf {
72 return true
73 }
74
75 // [dst.left, dst.right] ... [r.left, r.right]
76 // If my left is greater than dst right, we have no overlap.
77 if y.CompareKeys(r.left, dst.right) > 0 {
78 return false
79 }
80 // [r.left, r.right] ... [dst.left, dst.right]
81 // If my right is less than dst left, we have no overlap.
82 if y.CompareKeys(r.right, dst.left) < 0 {
83 return false
84 }
85 // We have overlap.
86 return true
87 }
88
89 // getKeyRange returns the smallest and the biggest in the list of tables.
90 // TODO(naman): Write a test for this. The smallest and the biggest should
91 // be the smallest of the leftmost table and the biggest of the right most table.
92 func getKeyRange(tables ...*table.Table) keyRange {
93 if len(tables) == 0 {
94 return keyRange{}
95 }
96 smallest := tables[0].Smallest()
97 biggest := tables[0].Biggest()
98 for i := 1; i < len(tables); i++ {
99 if y.CompareKeys(tables[i].Smallest(), smallest) < 0 {
100 smallest = tables[i].Smallest()
101 }
102 if y.CompareKeys(tables[i].Biggest(), biggest) > 0 {
103 biggest = tables[i].Biggest()
104 }
105 }
106
107 // We pick all the versions of the smallest and the biggest key. Note that version zero would
108 // be the rightmost key, considering versions are default sorted in descending order.
109 return keyRange{
110 left: y.KeyWithTs(y.ParseKey(smallest), math.MaxUint64),
111 right: y.KeyWithTs(y.ParseKey(biggest), 0),
112 }
113 }
114
115 type levelCompactStatus struct {
116 ranges []keyRange
117 delSize int64
118 }
119
120 func (lcs *levelCompactStatus) debug() string {
121 var b bytes.Buffer
122 for _, r := range lcs.ranges {
123 b.WriteString(r.String())
124 }
125 return b.String()
126 }
127
128 func (lcs *levelCompactStatus) overlapsWith(dst keyRange) bool {
129 for _, r := range lcs.ranges {
130 if r.overlapsWith(dst) {
131 return true
132 }
133 }
134 return false
135 }
136
137 func (lcs *levelCompactStatus) remove(dst keyRange) bool {
138 final := lcs.ranges[:0]
139 var found bool
140 for _, r := range lcs.ranges {
141 if !r.equals(dst) {
142 final = append(final, r)
143 } else {
144 found = true
145 }
146 }
147 lcs.ranges = final
148 return found
149 }
150
151 type compactStatus struct {
152 sync.RWMutex
153 levels []*levelCompactStatus
154 tables map[uint64]struct{}
155 }
156
157 func (cs *compactStatus) overlapsWith(level int, this keyRange) bool {
158 cs.RLock()
159 defer cs.RUnlock()
160
161 thisLevel := cs.levels[level]
162 return thisLevel.overlapsWith(this)
163 }
164
165 func (cs *compactStatus) delSize(l int) int64 {
166 cs.RLock()
167 defer cs.RUnlock()
168 return cs.levels[l].delSize
169 }
170
171 type thisAndNextLevelRLocked struct{}
172
173 // compareAndAdd will check whether we can run this compactDef. That it doesn't overlap with any
174 // other running compaction. If it can be run, it would store this run in the compactStatus state.
175 func (cs *compactStatus) compareAndAdd(_ thisAndNextLevelRLocked, cd compactDef) bool {
176 cs.Lock()
177 defer cs.Unlock()
178
179 tl := cd.thisLevel.level
180 y.AssertTruef(tl < len(cs.levels), "Got level %d. Max levels: %d", tl, len(cs.levels))
181 thisLevel := cs.levels[cd.thisLevel.level]
182 nextLevel := cs.levels[cd.nextLevel.level]
183
184 if thisLevel.overlapsWith(cd.thisRange) {
185 return false
186 }
187 if nextLevel.overlapsWith(cd.nextRange) {
188 return false
189 }
190 // Check whether this level really needs compaction or not. Otherwise, we'll end up
191 // running parallel compactions for the same level.
192 // Update: We should not be checking size here. Compaction priority already did the size checks.
193 // Here we should just be executing the wish of others.
194
195 thisLevel.ranges = append(thisLevel.ranges, cd.thisRange)
196 nextLevel.ranges = append(nextLevel.ranges, cd.nextRange)
197 thisLevel.delSize += cd.thisSize
198 for _, t := range append(cd.top, cd.bot...) {
199 cs.tables[t.ID()] = struct{}{}
200 }
201 return true
202 }
203
204 func (cs *compactStatus) delete(cd compactDef) {
205 cs.Lock()
206 defer cs.Unlock()
207
208 tl := cd.thisLevel.level
209 y.AssertTruef(tl < len(cs.levels), "Got level %d. Max levels: %d", tl, len(cs.levels))
210
211 thisLevel := cs.levels[cd.thisLevel.level]
212 nextLevel := cs.levels[cd.nextLevel.level]
213
214 thisLevel.delSize -= cd.thisSize
215 found := thisLevel.remove(cd.thisRange)
216 // The following check makes sense only if we're compacting more than one
217 // table. In case of the max level, we might rewrite a single table to
218 // remove stale data.
219 if cd.thisLevel != cd.nextLevel && !cd.nextRange.isEmpty() {
220 found = nextLevel.remove(cd.nextRange) && found
221 }
222
223 if !found {
224 this := cd.thisRange
225 next := cd.nextRange
226 fmt.Printf("Looking for: %s in this level %d.\n", this, tl)
227 fmt.Printf("This Level:\n%s\n", thisLevel.debug())
228 fmt.Println()
229 fmt.Printf("Looking for: %s in next level %d.\n", next, cd.nextLevel.level)
230 fmt.Printf("Next Level:\n%s\n", nextLevel.debug())
231 log.Fatal("keyRange not found")
232 }
233 for _, t := range append(cd.top, cd.bot...) {
234 _, ok := cs.tables[t.ID()]
235 y.AssertTrue(ok)
236 delete(cs.tables, t.ID())
237 }
238 }
239