Line data Source code
1 : // Copyright 2018 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 base 6 : 7 : import "io" 8 : 9 : // Merge creates a ValueMerger for the specified key initialized with the value 10 : // of one merge operand. 11 : type Merge func(key, value []byte) (ValueMerger, error) 12 : 13 : // ValueMerger receives merge operands one by one. The operand received is either 14 : // newer or older than all operands received so far as indicated by the function 15 : // names, `MergeNewer()` and `MergeOlder()`. Once all operands have been received, 16 : // the client will invoke `Finish()` to obtain the final result. The order of 17 : // a merge is not changed after the first call to `MergeNewer()` or 18 : // `MergeOlder()`, i.e. the same method is used to submit all operands. 19 : // 20 : // The implementation may choose to merge values into the result immediately upon 21 : // receiving each operand, or buffer operands until Finish() is called. For example, 22 : // buffering may be useful to avoid (de)serializing partial merge results. 23 : // 24 : // The merge operation must be associative. That is, for the values A, B, C: 25 : // 26 : // Merge(A).MergeOlder(B).MergeOlder(C) == Merge(C).MergeNewer(B).MergeNewer(A) 27 : // 28 : // Examples of merge operators are integer addition, list append, and string 29 : // concatenation. 30 : type ValueMerger interface { 31 : // MergeNewer adds an operand that is newer than all existing operands. 32 : // The caller retains ownership of value. 33 : // 34 : // If an error is returned the merge is aborted and no other methods must 35 : // be called. 36 : MergeNewer(value []byte) error 37 : 38 : // MergeOlder adds an operand that is older than all existing operands. 39 : // The caller retains ownership of value. 40 : // 41 : // If an error is returned the merge is aborted and no other methods must 42 : // be called. 43 : MergeOlder(value []byte) error 44 : 45 : // Finish does any final processing of the added operands and returns a 46 : // result. The caller can assume the returned byte slice will not be mutated. 47 : // 48 : // Finish must be the last function called on the ValueMerger. The caller 49 : // must not call any other ValueMerger functions after calling Finish. 50 : // 51 : // If `includesBase` is true, the oldest merge operand was part of the 52 : // merge. This will always be the true during normal iteration, but may be 53 : // false during compaction when only a subset of operands may be 54 : // available. Note that `includesBase` is set to true conservatively: a false 55 : // value means that we could not definitely determine that the base merge 56 : // operand was included. 57 : // 58 : // If a Closer is returned, the returned slice will remain valid until it is 59 : // closed. The caller must arrange for the closer to be eventually closed. 60 : Finish(includesBase bool) ([]byte, io.Closer, error) 61 : } 62 : 63 : // DeletableValueMerger is an extension to ValueMerger which allows indicating that the 64 : // result of a merge operation is non-existent. Such non-existent entries will eventually 65 : // be deleted during compaction. Note that during compaction, non-existence of the result 66 : // of a merge means that the merge operands will not result in any record being output. 67 : // This is not the same as transforming the merge operands into a deletion tombstone, as 68 : // older merge operands will still be visible during iteration. Deletion of the merge operands 69 : // in this way is akin to the way a SingleDelete+Set combine into non-existence while leaving 70 : // older records for the same key unaffected. 71 : type DeletableValueMerger interface { 72 : ValueMerger 73 : 74 : // DeletableFinish enables a value merger to indicate that the result of a merge operation 75 : // is non-existent. See Finish for a description of includesBase. 76 : DeletableFinish(includesBase bool) (value []byte, delete bool, closer io.Closer, err error) 77 : } 78 : 79 : // Merger defines an associative merge operation. The merge operation merges 80 : // two or more values for a single key. A merge operation is requested by 81 : // writing a value using {Batch,DB}.Merge(). The value at that key is merged 82 : // with any existing value. It is valid to Set a value at a key and then Merge 83 : // a new value. Similar to non-merged values, a merged value can be deleted by 84 : // either Delete or DeleteRange. 85 : // 86 : // The merge operation is invoked when a merge value is encountered during a 87 : // read, either during a compaction or during iteration. 88 : type Merger struct { 89 : Merge Merge 90 : 91 : // Name is the name of the merger. 92 : // 93 : // Pebble stores the merger name on disk, and opening a database with a 94 : // different merger from the one it was created with will result in an error. 95 : Name string 96 : } 97 : 98 : // AppendValueMerger concatenates merge operands in order from oldest to newest. 99 : type AppendValueMerger struct { 100 : buf []byte 101 : } 102 : 103 : // MergeNewer appends value to the result. 104 2 : func (a *AppendValueMerger) MergeNewer(value []byte) error { 105 2 : a.buf = append(a.buf, value...) 106 2 : return nil 107 2 : } 108 : 109 : // MergeOlder prepends value to the result, which involves allocating a new buffer. 110 2 : func (a *AppendValueMerger) MergeOlder(value []byte) error { 111 2 : buf := make([]byte, len(a.buf)+len(value)) 112 2 : copy(buf, value) 113 2 : copy(buf[len(value):], a.buf) 114 2 : a.buf = buf 115 2 : return nil 116 2 : } 117 : 118 : // Finish returns the buffer that was constructed on-demand in `Merge{OlderNewer}()` calls. 119 2 : func (a *AppendValueMerger) Finish(includesBase bool) ([]byte, io.Closer, error) { 120 2 : return a.buf, nil, nil 121 2 : } 122 : 123 : // DefaultMerger is the default implementation of the Merger interface. It 124 : // concatenates the two values to merge. 125 : var DefaultMerger = &Merger{ 126 2 : Merge: func(key, value []byte) (ValueMerger, error) { 127 2 : res := &AppendValueMerger{} 128 2 : res.buf = append(res.buf, value...) 129 2 : return res, nil 130 2 : }, 131 : 132 : Name: "pebble.concatenate", 133 : }