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 1 : ) RangeDelSpanCompactor {
28 1 : c := RangeDelSpanCompactor{
29 1 : cmp: cmp,
30 1 : equal: equal,
31 1 : snapshots: snapshots,
32 1 : }
33 1 : c.elider.Init(cmp, elision)
34 1 : return c
35 1 : }
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 1 : func (c *RangeDelSpanCompactor) Compact(span, output *keyspan.Span) {
49 1 : if invariants.Enabled && span.KeysOrder != keyspan.ByTrailerDesc {
50 0 : panic("pebble: span's keys unexpectedly not in trailer order")
51 : }
52 1 : output.Reset()
53 1 : // Apply the snapshot stripe rules, keeping only the latest tombstone for
54 1 : // each snapshot stripe.
55 1 : currentIdx := -1
56 1 : for _, k := range span.Keys {
57 1 : idx := c.snapshots.Index(k.SeqNum())
58 1 : if currentIdx == idx {
59 1 : continue
60 : }
61 1 : if idx == 0 && c.elider.ShouldElide(span.Start, span.End) {
62 1 : // This is the last snapshot stripe and the range tombstone
63 1 : // can be elided.
64 1 : break
65 : }
66 :
67 1 : output.Keys = append(output.Keys, k)
68 1 : if idx == 0 {
69 1 : // This is the last snapshot stripe.
70 1 : break
71 : }
72 1 : currentIdx = idx
73 : }
74 1 : if len(output.Keys) > 0 {
75 1 : output.Start = append(output.Start, span.Start...)
76 1 : output.End = append(output.End, span.End...)
77 1 : output.KeysOrder = span.KeysOrder
78 1 : }
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 1 : ) RangeKeySpanCompactor {
95 1 : c := RangeKeySpanCompactor{
96 1 : cmp: cmp,
97 1 : equal: equal,
98 1 : snapshots: snapshots,
99 1 : }
100 1 : c.elider.Init(cmp, elision)
101 1 : return c
102 1 : }
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 1 : func (c *RangeKeySpanCompactor) Compact(span, output *keyspan.Span) {
117 1 : 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 1 : output.Reset()
124 1 : x, y := len(c.snapshots)-1, 0
125 1 : usedLen := 0
126 1 : for x >= 0 {
127 1 : start := y
128 1 : for y < len(span.Keys) && !base.Visible(span.Keys[y].SeqNum(), c.snapshots[x], base.InternalKeySeqNumMax) {
129 1 : // Include y in current partition.
130 1 : y++
131 1 : }
132 1 : if y > start {
133 1 : keysDst := output.Keys[usedLen:cap(output.Keys)]
134 1 : rangekey.Coalesce(c.cmp, c.equal, span.Keys[start:y], &keysDst)
135 1 : if y == len(span.Keys) {
136 1 : // This is the last snapshot stripe. Unsets and deletes can be elided.
137 1 : keysDst = c.elideInLastStripe(span.Start, span.End, keysDst)
138 1 : }
139 1 : usedLen += len(keysDst)
140 1 : output.Keys = append(output.Keys, keysDst...)
141 : }
142 1 : x--
143 : }
144 1 : if y < len(span.Keys) {
145 1 : keysDst := output.Keys[usedLen:cap(output.Keys)]
146 1 : rangekey.Coalesce(c.cmp, c.equal, span.Keys[y:], &keysDst)
147 1 : keysDst = c.elideInLastStripe(span.Start, span.End, keysDst)
148 1 : usedLen += len(keysDst)
149 1 : output.Keys = append(output.Keys, keysDst...)
150 1 : }
151 1 : if len(output.Keys) > 0 {
152 1 : output.Start = append(output.Start, span.Start...)
153 1 : output.End = append(output.End, span.End...)
154 1 : output.KeysOrder = span.KeysOrder
155 1 : }
156 : }
157 :
158 : func (c *RangeKeySpanCompactor) elideInLastStripe(
159 : start, end []byte, keys []keyspan.Key,
160 1 : ) []keyspan.Key {
161 1 : // Unsets and deletes in the last snapshot stripe can be elided.
162 1 : k := 0
163 1 : for j := range keys {
164 1 : if (keys[j].Kind() == base.InternalKeyKindRangeKeyUnset || keys[j].Kind() == base.InternalKeyKindRangeKeyDelete) &&
165 1 : c.elider.ShouldElide(start, end) {
166 1 : continue
167 : }
168 1 : keys[k] = keys[j]
169 1 : k++
170 : }
171 1 : 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 1 : ) error {
187 1 : if span.Empty() {
188 1 : return nil
189 1 : }
190 :
191 1 : if upToKey == nil || cmp(span.End, upToKey) <= 0 {
192 1 : if err := tw.EncodeSpan(span); err != nil {
193 0 : return err
194 0 : }
195 1 : span.Reset()
196 1 : return nil
197 : }
198 :
199 1 : 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 1 : splitSpan := keyspan.Span{
206 1 : Start: span.Start,
207 1 : End: upToKey,
208 1 : Keys: span.Keys,
209 1 : }
210 1 : if err := tw.EncodeSpan(&splitSpan); err != nil {
211 0 : return err
212 0 : }
213 1 : span.Start = append(span.Start[:0], upToKey...)
214 1 : return nil
215 : }
|
