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             : }