Line data Source code
1 : // Copyright 2024 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 compact
6 :
7 : import (
8 : "github.com/cockroachdb/pebble/internal/base"
9 : "github.com/cockroachdb/pebble/internal/invariants"
10 : "github.com/cockroachdb/pebble/internal/keyspan"
11 : "github.com/cockroachdb/pebble/internal/rangekey"
12 : "github.com/cockroachdb/pebble/sstable"
13 : )
14 :
15 : // RangeDelSpanCompactor coalesces RANGEDELs within snapshot stripes and elides
16 : // RANGEDELs in the last stripe if possible.
17 : type RangeDelSpanCompactor struct {
18 : cmp base.Compare
19 : equal base.Equal
20 : snapshots Snapshots
21 : elider rangeTombstoneElider
22 : }
23 :
24 : // MakeRangeDelSpanCompactor creates a new compactor for RANGEDEL spans.
25 : func MakeRangeDelSpanCompactor(
26 : cmp base.Compare, equal base.Equal, snapshots Snapshots, elision TombstoneElision,
27 2 : ) RangeDelSpanCompactor {
28 2 : c := RangeDelSpanCompactor{
29 2 : cmp: cmp,
30 2 : equal: equal,
31 2 : snapshots: snapshots,
32 2 : }
33 2 : c.elider.Init(cmp, elision)
34 2 : return c
35 2 : }
36 :
37 : // Compact compacts the given range del span and stores the results in the
38 : // given output span, reusing its slices.
39 : //
40 : // Compaction of a span entails coalescing RANGEDELs keys within snapshot
41 : // stripes, and eliding RANGEDELs in the last stripe if possible.
42 : //
43 : // It is possible for the output span to be empty after the call (if all
44 : // RANGEDELs in the span are elided).
45 : //
46 : // The spans that are passed to Compact calls must be ordered and
47 : // non-overlapping.
48 2 : func (c *RangeDelSpanCompactor) Compact(span, output *keyspan.Span) {
49 2 : if invariants.Enabled && span.KeysOrder != keyspan.ByTrailerDesc {
50 0 : panic("pebble: span's keys unexpectedly not in trailer order")
51 : }
52 2 : output.Reset()
53 2 : // Apply the snapshot stripe rules, keeping only the latest tombstone for
54 2 : // each snapshot stripe.
55 2 : currentIdx := -1
56 2 : for _, k := range span.Keys {
57 2 : idx := c.snapshots.Index(k.SeqNum())
58 2 : if currentIdx == idx {
59 2 : continue
60 : }
61 2 : if idx == 0 && c.elider.ShouldElide(span.Start, span.End) {
62 2 : // This is the last snapshot stripe and the range tombstone
63 2 : // can be elided.
64 2 : break
65 : }
66 :
67 2 : output.Keys = append(output.Keys, k)
68 2 : if idx == 0 {
69 2 : // This is the last snapshot stripe.
70 2 : break
71 : }
72 2 : currentIdx = idx
73 : }
74 2 : if len(output.Keys) > 0 {
75 2 : output.Start = append(output.Start, span.Start...)
76 2 : output.End = append(output.End, span.End...)
77 2 : output.KeysOrder = span.KeysOrder
78 2 : }
79 : }
80 :
81 : // RangeKeySpanCompactor coalesces range keys within snapshot stripes and elides
82 : // RangeKeyDelete and RangeKeyUnsets when possible. It is used as a container
83 : // for at most one "compacted" span.
84 : type RangeKeySpanCompactor struct {
85 : cmp base.Compare
86 : equal base.Equal
87 : snapshots Snapshots
88 : elider rangeTombstoneElider
89 : }
90 :
91 : // MakeRangeKeySpanCompactor creates a new compactor for range key spans.
92 : func MakeRangeKeySpanCompactor(
93 : cmp base.Compare, equal base.Equal, snapshots Snapshots, elision TombstoneElision,
94 2 : ) RangeKeySpanCompactor {
95 2 : c := RangeKeySpanCompactor{
96 2 : cmp: cmp,
97 2 : equal: equal,
98 2 : snapshots: snapshots,
99 2 : }
100 2 : c.elider.Init(cmp, elision)
101 2 : return c
102 2 : }
103 :
104 : // Compact compacts the given range key span and stores the results in the
105 : // given output span, reusing its slices.
106 : //
107 : // Compaction of a span entails coalescing range keys within snapshot
108 : // stripes, and eliding RangeKeyUnset/RangeKeyDelete in the last stripe if
109 : // possible.
110 : //
111 : // It is possible for the output span to be empty after the call (if all range
112 : // keys in the span are elided).
113 : //
114 : // The spans that are passed to Compact calls must be ordered and
115 : // non-overlapping.
116 2 : func (c *RangeKeySpanCompactor) Compact(span, output *keyspan.Span) {
117 2 : if invariants.Enabled && span.KeysOrder != keyspan.ByTrailerDesc {
118 0 : panic("pebble: span's keys unexpectedly not in trailer order")
119 : }
120 : // snapshots are in ascending order, while s.keys are in descending seqnum
121 : // order. Partition s.keys by snapshot stripes, and call rangekey.Coalesce
122 : // on each partition.
123 2 : output.Reset()
124 2 : x, y := len(c.snapshots)-1, 0
125 2 : usedLen := 0
126 2 : for x >= 0 {
127 2 : start := y
128 2 : for y < len(span.Keys) && !base.Visible(span.Keys[y].SeqNum(), c.snapshots[x], base.InternalKeySeqNumMax) {
129 2 : // Include y in current partition.
130 2 : y++
131 2 : }
132 2 : if y > start {
133 2 : keysDst := output.Keys[usedLen:cap(output.Keys)]
134 2 : rangekey.Coalesce(c.cmp, c.equal, span.Keys[start:y], &keysDst)
135 2 : if y == len(span.Keys) {
136 2 : // This is the last snapshot stripe. Unsets and deletes can be elided.
137 2 : keysDst = c.elideInLastStripe(span.Start, span.End, keysDst)
138 2 : }
139 2 : usedLen += len(keysDst)
140 2 : output.Keys = append(output.Keys, keysDst...)
141 : }
142 2 : x--
143 : }
144 2 : if y < len(span.Keys) {
145 2 : keysDst := output.Keys[usedLen:cap(output.Keys)]
146 2 : rangekey.Coalesce(c.cmp, c.equal, span.Keys[y:], &keysDst)
147 2 : keysDst = c.elideInLastStripe(span.Start, span.End, keysDst)
148 2 : usedLen += len(keysDst)
149 2 : output.Keys = append(output.Keys, keysDst...)
150 2 : }
151 2 : if len(output.Keys) > 0 {
152 2 : output.Start = append(output.Start, span.Start...)
153 2 : output.End = append(output.End, span.End...)
154 2 : output.KeysOrder = span.KeysOrder
155 2 : }
156 : }
157 :
158 : func (c *RangeKeySpanCompactor) elideInLastStripe(
159 : start, end []byte, keys []keyspan.Key,
160 2 : ) []keyspan.Key {
161 2 : // Unsets and deletes in the last snapshot stripe can be elided.
162 2 : k := 0
163 2 : for j := range keys {
164 2 : if (keys[j].Kind() == base.InternalKeyKindRangeKeyUnset || keys[j].Kind() == base.InternalKeyKindRangeKeyDelete) &&
165 2 : c.elider.ShouldElide(start, end) {
166 2 : continue
167 : }
168 2 : keys[k] = keys[j]
169 2 : k++
170 : }
171 2 : return keys[:k]
172 : }
173 :
174 : // SplitAndEncodeSpan splits a span at upToKey and encodes the first part into
175 : // the table writer, and updates the span to store the remaining part.
176 : //
177 : // If upToKey is nil or the span ends before upToKey, we encode the entire span
178 : // and reset it to the empty span.
179 : //
180 : // Note that the span.Start slice will be reused (it will be replaced with a
181 : // copy of upToKey, if appropriate).
182 : //
183 : // The span can contain either only RANGEDEL keys or only range keys.
184 : func SplitAndEncodeSpan(
185 : cmp base.Compare, span *keyspan.Span, upToKey []byte, tw *sstable.Writer,
186 2 : ) error {
187 2 : if span.Empty() {
188 2 : return nil
189 2 : }
190 :
191 2 : if upToKey == nil || cmp(span.End, upToKey) <= 0 {
192 2 : if err := tw.EncodeSpan(span); err != nil {
193 0 : return err
194 0 : }
195 2 : span.Reset()
196 2 : return nil
197 : }
198 :
199 2 : if cmp(span.Start, upToKey) >= 0 {
200 1 : // The span starts at/after upToKey; nothing to encode.
201 1 : return nil
202 1 : }
203 :
204 : // Split the span at upToKey and encode the first part.
205 2 : splitSpan := keyspan.Span{
206 2 : Start: span.Start,
207 2 : End: upToKey,
208 2 : Keys: span.Keys,
209 2 : }
210 2 : if err := tw.EncodeSpan(&splitSpan); err != nil {
211 0 : return err
212 0 : }
213 2 : span.Start = append(span.Start[:0], upToKey...)
214 2 : return nil
215 : }
|
