Line data Source code
1 : // Copyright 2021 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 rangekey 6 : 7 : import ( 8 : "math" 9 : "sort" 10 : 11 : "github.com/cockroachdb/pebble/internal/base" 12 : "github.com/cockroachdb/pebble/internal/invariants" 13 : "github.com/cockroachdb/pebble/internal/keyspan" 14 : ) 15 : 16 : // Coalesce imposes range key semantics and coalesces range keys with the same 17 : // bounds. Coalesce drops any keys shadowed by more recent sets, unsets or 18 : // deletes. Coalesce modifies the provided span's Keys slice, reslicing the 19 : // slice to remove dropped keys. 20 : // 21 : // Coalescence has subtle behavior with respect to sequence numbers. Coalesce 22 : // depends on a keyspan.Span's Keys being sorted in sequence number descending 23 : // order. The first key has the largest sequence number. The returned coalesced 24 : // span includes only the largest sequence number. All other sequence numbers 25 : // are forgotten. When a compaction constructs output range keys from a 26 : // coalesced span, it produces at most one RANGEKEYSET, one RANGEKEYUNSET and 27 : // one RANGEKEYDEL. Each one of these keys adopt the largest sequence number. 28 : // 29 : // This has the potentially surprising effect of 'promoting' a key to a higher 30 : // sequence number. This is okay, because: 31 : // - There are no other overlapping keys within the coalesced span of 32 : // sequence numbers (otherwise they would be in the compaction, due to 33 : // the LSM invariant). 34 : // - Range key sequence numbers are never compared to point key sequence 35 : // numbers. Range keys and point keys have parallel existences. 36 : // - Compactions only coalesce within snapshot stripes. 37 : // 38 : // Additionally, internal range keys at the same sequence number have subtle 39 : // mechanics: 40 : // - RANGEKEYSETs shadow RANGEKEYUNSETs of the same suffix. 41 : // - RANGEKEYDELs only apply to keys at lower sequence numbers. 42 : // 43 : // This is required for ingestion. Ingested sstables are assigned a single 44 : // sequence number for the file, at which all of the file's keys are visible. 45 : // The RANGEKEYSET, RANGEKEYUNSET and RANGEKEYDEL key kinds are ordered such 46 : // that among keys with equal sequence numbers (thus ordered by their kinds) the 47 : // keys do not affect one another. Ingested sstables are expected to be 48 : // consistent with respect to the set/unset suffixes: A given suffix should be 49 : // set or unset but not both. 50 : // 51 : // The resulting dst Keys slice is sorted by Trailer. 52 2 : func Coalesce(cmp base.Compare, eq base.Equal, keys []keyspan.Key, dst *[]keyspan.Key) { 53 2 : // TODO(jackson): Currently, Coalesce doesn't actually perform the sequence 54 2 : // number promotion described in the comment above. 55 2 : keysBySuffix := keyspan.KeysBySuffix{ 56 2 : Cmp: cmp, 57 2 : Keys: (*dst)[:0], 58 2 : } 59 2 : CoalesceIntoKeysBySuffix(eq, &keysBySuffix, math.MaxUint64, keys) 60 2 : // Update the span with the (potentially reduced) keys slice. coalesce left 61 2 : // the keys in *dst sorted by suffix. Re-sort them by trailer. 62 2 : *dst = keysBySuffix.Keys 63 2 : keyspan.SortKeysByTrailer(dst) 64 2 : } 65 : 66 : // CoalesceIntoKeysBySuffix is a variant of Coalesce which outputs the results into 67 : // keyspan.KeysBySuffix without sorting them. 68 : func CoalesceIntoKeysBySuffix( 69 : equal base.Equal, keysBySuffix *keyspan.KeysBySuffix, snapshot uint64, keys []keyspan.Key, 70 2 : ) { 71 2 : // First, enforce visibility and RangeKeyDelete mechanics. We only need to 72 2 : // consider the prefix of keys before and including the first 73 2 : // RangeKeyDelete. We also must skip any keys that aren't visible at the 74 2 : // provided snapshot sequence number. 75 2 : // 76 2 : // NB: Within a given sequence number, keys are ordered as: 77 2 : // RangeKeySet > RangeKeyUnset > RangeKeyDelete 78 2 : // This is significant, because this ensures that a Set or Unset sharing a 79 2 : // sequence number with a Delete do not shadow each other. 80 2 : deleteIdx := -1 81 2 : for i := range keys { 82 2 : if invariants.Enabled && i > 0 && keys[i].Trailer > keys[i-1].Trailer { 83 0 : panic("pebble: invariant violation: span keys unordered") 84 : } 85 2 : if !keys[i].VisibleAt(snapshot) { 86 2 : continue 87 : } 88 : // Once a RangeKeyDelete is observed, we know it shadows all subsequent 89 : // keys and we can break early. We don't add the RangeKeyDelete key to 90 : // keysBySuffix.keys yet, because we don't want a suffix-less key 91 : // that appeared earlier in the slice to elide it. It'll be added back 92 : // in at the end. 93 2 : if keys[i].Kind() == base.InternalKeyKindRangeKeyDelete { 94 2 : deleteIdx = i 95 2 : break 96 : } 97 2 : keysBySuffix.Keys = append(keysBySuffix.Keys, keys[i]) 98 : } 99 : 100 : // Sort the accumulated keys by suffix. There may be duplicates within a 101 : // suffix, in which case the one with a larger trailer survives. 102 : // 103 : // We use a stable sort so that the first key with a given suffix is the one 104 : // that with the highest Trailer (because the input `keys` was sorted by 105 : // trailer descending). 106 2 : sort.Stable(keysBySuffix) 107 2 : 108 2 : // Grab a handle of the full sorted slice, before reslicing 109 2 : // keysBySuffix.keys to accumulate the final coalesced keys. 110 2 : sorted := keysBySuffix.Keys 111 2 : keysBySuffix.Keys = keysBySuffix.Keys[:0] 112 2 : 113 2 : var ( 114 2 : // prevSuffix is updated on each iteration of the below loop, and 115 2 : // compared by the subsequent iteration to determine whether adjacent 116 2 : // keys are defined at the same suffix. 117 2 : prevSuffix []byte 118 2 : // shadowing is set to true once any Key is shadowed by another key. 119 2 : // When it's set to true—or after the loop if no keys are shadowed—the 120 2 : // keysBySuffix.keys slice is resliced to contain the prefix of 121 2 : // unshadowed keys. This avoids copying them incrementally in the common 122 2 : // case of no shadowing. 123 2 : shadowing bool 124 2 : ) 125 2 : for i := range sorted { 126 2 : if i > 0 && equal(prevSuffix, sorted[i].Suffix) { 127 2 : // Skip; this key is shadowed by the predecessor that had a larger 128 2 : // Trailer. If this is the first shadowed key, set shadowing=true 129 2 : // and reslice keysBySuffix.keys to hold the entire unshadowed 130 2 : // prefix. 131 2 : if !shadowing { 132 2 : keysBySuffix.Keys = keysBySuffix.Keys[:i] 133 2 : shadowing = true 134 2 : } 135 2 : continue 136 : } 137 2 : prevSuffix = sorted[i].Suffix 138 2 : if shadowing { 139 2 : keysBySuffix.Keys = append(keysBySuffix.Keys, sorted[i]) 140 2 : } 141 : } 142 : // If there was no shadowing, keysBySuffix.keys is untouched. We can simply 143 : // set it to the existing `sorted` slice (also backed by keysBySuffix.keys). 144 2 : if !shadowing { 145 2 : keysBySuffix.Keys = sorted 146 2 : } 147 : // If the original input `keys` slice contained a RangeKeyDelete, add it. 148 2 : if deleteIdx >= 0 { 149 2 : keysBySuffix.Keys = append(keysBySuffix.Keys, keys[deleteIdx]) 150 2 : } 151 : } 152 : 153 : // ForeignSSTTransformer implements a keyspan.Transformer for range keys in 154 : // shared ingested sstables. It is largely similar to the Transform function 155 : // implemented in UserIteratorConfig in that it calls coalesce to remove range 156 : // keys shadowed by other range keys, but also retains the range key that does 157 : // the shadowing. In addition, it elides RangeKey unsets/dels in L6 as they are 158 : // inapplicable when reading from a different Pebble instance. Finally, it 159 : // returns keys sorted in trailer order, not suffix order, as that's what the 160 : // rest of the iterator stack expects. 161 : type ForeignSSTTransformer struct { 162 : Equal base.Equal 163 : SeqNum uint64 164 : sortBuf keyspan.KeysBySuffix 165 : } 166 : 167 : // Transform implements the Transformer interface. 168 : func (f *ForeignSSTTransformer) Transform( 169 : cmp base.Compare, s keyspan.Span, dst *keyspan.Span, 170 2 : ) error { 171 2 : // Apply shadowing of keys. 172 2 : dst.Start = s.Start 173 2 : dst.End = s.End 174 2 : f.sortBuf = keyspan.KeysBySuffix{ 175 2 : Cmp: cmp, 176 2 : Keys: f.sortBuf.Keys[:0], 177 2 : } 178 2 : CoalesceIntoKeysBySuffix(f.Equal, &f.sortBuf, math.MaxUint64, s.Keys) 179 2 : keys := f.sortBuf.Keys 180 2 : dst.Keys = dst.Keys[:0] 181 2 : for i := range keys { 182 2 : switch keys[i].Kind() { 183 2 : case base.InternalKeyKindRangeKeySet: 184 2 : if invariants.Enabled && len(dst.Keys) > 0 && cmp(dst.Keys[len(dst.Keys)-1].Suffix, keys[i].Suffix) > 0 { 185 0 : panic("pebble: keys unexpectedly not in ascending suffix order") 186 : } 187 1 : case base.InternalKeyKindRangeKeyUnset: 188 1 : if invariants.Enabled && len(dst.Keys) > 0 && cmp(dst.Keys[len(dst.Keys)-1].Suffix, keys[i].Suffix) > 0 { 189 0 : panic("pebble: keys unexpectedly not in ascending suffix order") 190 : } 191 2 : case base.InternalKeyKindRangeKeyDelete: 192 : // Nothing to do. 193 0 : default: 194 0 : return base.CorruptionErrorf("pebble: unrecognized range key kind %s", keys[i].Kind()) 195 : } 196 2 : dst.Keys = append(dst.Keys, keyspan.Key{ 197 2 : Trailer: base.MakeTrailer(f.SeqNum, keys[i].Kind()), 198 2 : Suffix: keys[i].Suffix, 199 2 : Value: keys[i].Value, 200 2 : }) 201 : } 202 : // coalesce results in dst.Keys being sorted by Suffix. Change it back to 203 : // ByTrailerDesc, as that's what the iterator stack will expect. 204 2 : keyspan.SortKeysByTrailer(&dst.Keys) 205 2 : dst.KeysOrder = keyspan.ByTrailerDesc 206 2 : return nil 207 : }