/Users/deen/code/yugabyte-db/src/yb/rocksdb/merge_operator.h
Line | Count | Source |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | |
21 | | #ifndef ROCKSDB_INCLUDE_ROCKSDB_MERGE_OPERATOR_H |
22 | | #define ROCKSDB_INCLUDE_ROCKSDB_MERGE_OPERATOR_H |
23 | | |
24 | | #include <deque> |
25 | | #include <memory> |
26 | | #include <string> |
27 | | |
28 | | #include "yb/util/slice.h" |
29 | | |
30 | | namespace rocksdb { |
31 | | |
32 | | class Logger; |
33 | | |
34 | | // The Merge Operator |
35 | | // |
36 | | // Essentially, a MergeOperator specifies the SEMANTICS of a merge, which only |
37 | | // client knows. It could be numeric addition, list append, string |
38 | | // concatenation, edit data structure, ... , anything. |
39 | | // The library, on the other hand, is concerned with the exercise of this |
40 | | // interface, at the right time (during get, iteration, compaction...) |
41 | | // |
42 | | // To use merge, the client needs to provide an object implementing one of |
43 | | // the following interfaces: |
44 | | // a) AssociativeMergeOperator - for most simple semantics (always take |
45 | | // two values, and merge them into one value, which is then put back |
46 | | // into rocksdb); numeric addition and string concatenation are examples; |
47 | | // |
48 | | // b) MergeOperator - the generic class for all the more abstract / complex |
49 | | // operations; one method (FullMerge) to merge a Put/Delete value with a |
50 | | // merge operand; and another method (PartialMerge) that merges multiple |
51 | | // operands together. this is especially useful if your key values have |
52 | | // complex structures but you would still like to support client-specific |
53 | | // incremental updates. |
54 | | // |
55 | | // AssociativeMergeOperator is simpler to implement. MergeOperator is simply |
56 | | // more powerful. |
57 | | // |
58 | | // Refer to rocksdb-merge wiki for more details and example implementations. |
59 | | // |
60 | | class MergeOperator { |
61 | | public: |
62 | 280 | virtual ~MergeOperator() {} |
63 | | |
64 | | // Gives the client a way to express the read -> modify -> write semantics |
65 | | // key: (IN) The key that's associated with this merge operation. |
66 | | // Client could multiplex the merge operator based on it |
67 | | // if the key space is partitioned and different subspaces |
68 | | // refer to different types of data which have different |
69 | | // merge operation semantics |
70 | | // existing: (IN) null indicates that the key does not exist before this op |
71 | | // operand_list:(IN) the sequence of merge operations to apply, front() first. |
72 | | // new_value:(OUT) Client is responsible for filling the merge result here. |
73 | | // The string that new_value is pointing to will be empty. |
74 | | // logger: (IN) Client could use this to log errors during merge. |
75 | | // |
76 | | // Return true on success. |
77 | | // All values passed in will be client-specific values. So if this method |
78 | | // returns false, it is because client specified bad data or there was |
79 | | // internal corruption. This will be treated as an error by the library. |
80 | | // |
81 | | // Also make use of the *logger for error messages. |
82 | | virtual bool FullMerge(const Slice& key, |
83 | | const Slice* existing_value, |
84 | | const std::deque<std::string>& operand_list, |
85 | | std::string* new_value, |
86 | | Logger* logger) const = 0; |
87 | | |
88 | | // This function performs merge(left_op, right_op) |
89 | | // when both the operands are themselves merge operation types |
90 | | // that you would have passed to a DB::Merge() call in the same order |
91 | | // (i.e.: DB::Merge(key,left_op), followed by DB::Merge(key,right_op)). |
92 | | // |
93 | | // PartialMerge should combine them into a single merge operation that is |
94 | | // saved into *new_value, and then it should return true. |
95 | | // *new_value should be constructed such that a call to |
96 | | // DB::Merge(key, *new_value) would yield the same result as a call |
97 | | // to DB::Merge(key, left_op) followed by DB::Merge(key, right_op). |
98 | | // |
99 | | // The string that new_value is pointing to will be empty. |
100 | | // |
101 | | // The default implementation of PartialMergeMulti will use this function |
102 | | // as a helper, for backward compatibility. Any successor class of |
103 | | // MergeOperator should either implement PartialMerge or PartialMergeMulti, |
104 | | // although implementing PartialMergeMulti is suggested as it is in general |
105 | | // more effective to merge multiple operands at a time instead of two |
106 | | // operands at a time. |
107 | | // |
108 | | // If it is impossible or infeasible to combine the two operations, |
109 | | // leave new_value unchanged and return false. The library will |
110 | | // internally keep track of the operations, and apply them in the |
111 | | // correct order once a base-value (a Put/Delete/End-of-Database) is seen. |
112 | | // |
113 | | // TODO: Presently there is no way to differentiate between error/corruption |
114 | | // and simply "return false". For now, the client should simply return |
115 | | // false in any case it cannot perform partial-merge, regardless of reason. |
116 | | // If there is corruption in the data, handle it in the FullMerge() function, |
117 | | // and return false there. The default implementation of PartialMerge will |
118 | | // always return false. |
119 | | virtual bool PartialMerge(const Slice& key, const Slice& left_operand, |
120 | | const Slice& right_operand, std::string* new_value, |
121 | 1.80k | Logger* logger) const { |
122 | 1.80k | return false; |
123 | 1.80k | } |
124 | | |
125 | | // This function performs merge when all the operands are themselves merge |
126 | | // operation types that you would have passed to a DB::Merge() call in the |
127 | | // same order (front() first) |
128 | | // (i.e. DB::Merge(key, operand_list[0]), followed by |
129 | | // DB::Merge(key, operand_list[1]), ...) |
130 | | // |
131 | | // PartialMergeMulti should combine them into a single merge operation that is |
132 | | // saved into *new_value, and then it should return true. *new_value should |
133 | | // be constructed such that a call to DB::Merge(key, *new_value) would yield |
134 | | // the same result as subquential individual calls to DB::Merge(key, operand) |
135 | | // for each operand in operand_list from front() to back(). |
136 | | // |
137 | | // The string that new_value is pointing to will be empty. |
138 | | // |
139 | | // The PartialMergeMulti function will be called only when the list of |
140 | | // operands are long enough. The minimum amount of operands that will be |
141 | | // passed to the function are specified by the "min_partial_merge_operands" |
142 | | // option. |
143 | | // |
144 | | // In the default implementation, PartialMergeMulti will invoke PartialMerge |
145 | | // multiple times, where each time it only merges two operands. Developers |
146 | | // should either implement PartialMergeMulti, or implement PartialMerge which |
147 | | // is served as the helper function of the default PartialMergeMulti. |
148 | | virtual bool PartialMergeMulti(const Slice& key, |
149 | | const std::deque<Slice>& operand_list, |
150 | | std::string* new_value, Logger* logger) const; |
151 | | |
152 | | // The name of the MergeOperator. Used to check for MergeOperator |
153 | | // mismatches (i.e., a DB created with one MergeOperator is |
154 | | // accessed using a different MergeOperator) |
155 | | // TODO: the name is currently not stored persistently and thus |
156 | | // no checking is enforced. Client is responsible for providing |
157 | | // consistent MergeOperator between DB opens. |
158 | | virtual const char* Name() const = 0; |
159 | | }; |
160 | | |
161 | | // The simpler, associative merge operator. |
162 | | class AssociativeMergeOperator : public MergeOperator { |
163 | | public: |
164 | 115 | virtual ~AssociativeMergeOperator() {} |
165 | | |
166 | | // Gives the client a way to express the read -> modify -> write semantics |
167 | | // key: (IN) The key that's associated with this merge operation. |
168 | | // existing_value:(IN) null indicates the key does not exist before this op |
169 | | // value: (IN) the value to update/merge the existing_value with |
170 | | // new_value: (OUT) Client is responsible for filling the merge result |
171 | | // here. The string that new_value is pointing to will be empty. |
172 | | // logger: (IN) Client could use this to log errors during merge. |
173 | | // |
174 | | // Return true on success. |
175 | | // All values passed in will be client-specific values. So if this method |
176 | | // returns false, it is because client specified bad data or there was |
177 | | // internal corruption. The client should assume that this will be treated |
178 | | // as an error by the library. |
179 | | virtual bool Merge(const Slice& key, |
180 | | const Slice* existing_value, |
181 | | const Slice& value, |
182 | | std::string* new_value, |
183 | | Logger* logger) const = 0; |
184 | | |
185 | | |
186 | | private: |
187 | | // Default implementations of the MergeOperator functions |
188 | | virtual bool FullMerge(const Slice& key, |
189 | | const Slice* existing_value, |
190 | | const std::deque<std::string>& operand_list, |
191 | | std::string* new_value, |
192 | | Logger* logger) const override; |
193 | | |
194 | | virtual bool PartialMerge(const Slice& key, |
195 | | const Slice& left_operand, |
196 | | const Slice& right_operand, |
197 | | std::string* new_value, |
198 | | Logger* logger) const override; |
199 | | }; |
200 | | |
201 | | } // namespace rocksdb |
202 | | |
203 | | #endif // ROCKSDB_INCLUDE_ROCKSDB_MERGE_OPERATOR_H |