]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | ||
10 | #pragma once | |
11 | ||
12 | #include <memory> | |
13 | #include <set> | |
14 | #include <string> | |
15 | #include <unordered_set> | |
16 | #include <vector> | |
17 | ||
f67539c2 | 18 | #include "db/compaction/compaction.h" |
7c673cae FG |
19 | #include "db/version_set.h" |
20 | #include "options/cf_options.h" | |
21 | #include "rocksdb/env.h" | |
22 | #include "rocksdb/options.h" | |
23 | #include "rocksdb/status.h" | |
24 | ||
f67539c2 TL |
25 | namespace ROCKSDB_NAMESPACE { |
26 | ||
27 | // The file contains an abstract class CompactionPicker, and its two | |
28 | // sub-classes LevelCompactionPicker and NullCompactionPicker, as | |
29 | // well as some helper functions used by them. | |
7c673cae FG |
30 | |
31 | class LogBuffer; | |
32 | class Compaction; | |
33 | class VersionStorageInfo; | |
34 | struct CompactionInputFiles; | |
35 | ||
f67539c2 TL |
36 | // An abstract class to pick compactions from an existing LSM-tree. |
37 | // | |
38 | // Each compaction style inherits the class and implement the | |
39 | // interface to form automatic compactions. If NeedCompaction() is true, | |
40 | // then call PickCompaction() to find what files need to be compacted | |
41 | // and where to put the output files. | |
42 | // | |
43 | // Non-virtual functions CompactRange() and CompactFiles() are used to | |
44 | // pick files to compact based on users' DB::CompactRange() and | |
45 | // DB::CompactFiles() requests, respectively. There is little | |
46 | // compaction style specific logic for them. | |
7c673cae FG |
47 | class CompactionPicker { |
48 | public: | |
49 | CompactionPicker(const ImmutableCFOptions& ioptions, | |
50 | const InternalKeyComparator* icmp); | |
51 | virtual ~CompactionPicker(); | |
52 | ||
53 | // Pick level and inputs for a new compaction. | |
54 | // Returns nullptr if there is no compaction to be done. | |
55 | // Otherwise returns a pointer to a heap-allocated object that | |
56 | // describes the compaction. Caller should delete the result. | |
f67539c2 TL |
57 | virtual Compaction* PickCompaction( |
58 | const std::string& cf_name, const MutableCFOptions& mutable_cf_options, | |
20effc67 TL |
59 | const MutableDBOptions& mutable_db_options, VersionStorageInfo* vstorage, |
60 | LogBuffer* log_buffer, | |
f67539c2 | 61 | SequenceNumber earliest_memtable_seqno = kMaxSequenceNumber) = 0; |
7c673cae FG |
62 | |
63 | // Return a compaction object for compacting the range [begin,end] in | |
64 | // the specified level. Returns nullptr if there is nothing in that | |
65 | // level that overlaps the specified range. Caller should delete | |
66 | // the result. | |
67 | // | |
68 | // The returned Compaction might not include the whole requested range. | |
69 | // In that case, compaction_end will be set to the next key that needs | |
70 | // compacting. In case the compaction will compact the whole range, | |
71 | // compaction_end will be set to nullptr. | |
72 | // Client is responsible for compaction_end storage -- when called, | |
73 | // *compaction_end should point to valid InternalKey! | |
74 | virtual Compaction* CompactRange( | |
75 | const std::string& cf_name, const MutableCFOptions& mutable_cf_options, | |
20effc67 TL |
76 | const MutableDBOptions& mutable_db_options, VersionStorageInfo* vstorage, |
77 | int input_level, int output_level, | |
f67539c2 | 78 | const CompactRangeOptions& compact_range_options, |
11fdf7f2 | 79 | const InternalKey* begin, const InternalKey* end, |
f67539c2 TL |
80 | InternalKey** compaction_end, bool* manual_conflict, |
81 | uint64_t max_file_num_to_ignore); | |
7c673cae FG |
82 | |
83 | // The maximum allowed output level. Default value is NumberLevels() - 1. | |
84 | virtual int MaxOutputLevel() const { return NumberLevels() - 1; } | |
85 | ||
86 | virtual bool NeedsCompaction(const VersionStorageInfo* vstorage) const = 0; | |
87 | ||
88 | // Sanitize the input set of compaction input files. | |
89 | // When the input parameters do not describe a valid compaction, the | |
90 | // function will try to fix the input_files by adding necessary | |
91 | // files. If it's not possible to conver an invalid input_files | |
92 | // into a valid one by adding more files, the function will return a | |
93 | // non-ok status with specific reason. | |
94 | #ifndef ROCKSDB_LITE | |
95 | Status SanitizeCompactionInputFiles(std::unordered_set<uint64_t>* input_files, | |
96 | const ColumnFamilyMetaData& cf_meta, | |
97 | const int output_level) const; | |
98 | #endif // ROCKSDB_LITE | |
99 | ||
100 | // Free up the files that participated in a compaction | |
101 | // | |
102 | // Requirement: DB mutex held | |
103 | void ReleaseCompactionFiles(Compaction* c, Status status); | |
104 | ||
105 | // Returns true if any one of the specified files are being compacted | |
106 | bool AreFilesInCompaction(const std::vector<FileMetaData*>& files); | |
107 | ||
108 | // Takes a list of CompactionInputFiles and returns a (manual) Compaction | |
109 | // object. | |
11fdf7f2 TL |
110 | // |
111 | // Caller must provide a set of input files that has been passed through | |
112 | // `SanitizeCompactionInputFiles` earlier. The lock should not be released | |
113 | // between that call and this one. | |
7c673cae FG |
114 | Compaction* CompactFiles(const CompactionOptions& compact_options, |
115 | const std::vector<CompactionInputFiles>& input_files, | |
116 | int output_level, VersionStorageInfo* vstorage, | |
117 | const MutableCFOptions& mutable_cf_options, | |
20effc67 | 118 | const MutableDBOptions& mutable_db_options, |
7c673cae FG |
119 | uint32_t output_path_id); |
120 | ||
121 | // Converts a set of compaction input file numbers into | |
122 | // a list of CompactionInputFiles. | |
123 | Status GetCompactionInputsFromFileNumbers( | |
124 | std::vector<CompactionInputFiles>* input_files, | |
125 | std::unordered_set<uint64_t>* input_set, | |
126 | const VersionStorageInfo* vstorage, | |
127 | const CompactionOptions& compact_options) const; | |
128 | ||
129 | // Is there currently a compaction involving level 0 taking place | |
130 | bool IsLevel0CompactionInProgress() const { | |
131 | return !level0_compactions_in_progress_.empty(); | |
132 | } | |
133 | ||
134 | // Return true if the passed key range overlap with a compaction output | |
135 | // that is currently running. | |
136 | bool RangeOverlapWithCompaction(const Slice& smallest_user_key, | |
137 | const Slice& largest_user_key, | |
138 | int level) const; | |
139 | ||
140 | // Stores the minimal range that covers all entries in inputs in | |
141 | // *smallest, *largest. | |
142 | // REQUIRES: inputs is not empty | |
143 | void GetRange(const CompactionInputFiles& inputs, InternalKey* smallest, | |
144 | InternalKey* largest) const; | |
145 | ||
146 | // Stores the minimal range that covers all entries in inputs1 and inputs2 | |
147 | // in *smallest, *largest. | |
148 | // REQUIRES: inputs is not empty | |
149 | void GetRange(const CompactionInputFiles& inputs1, | |
150 | const CompactionInputFiles& inputs2, InternalKey* smallest, | |
151 | InternalKey* largest) const; | |
152 | ||
153 | // Stores the minimal range that covers all entries in inputs | |
154 | // in *smallest, *largest. | |
155 | // REQUIRES: inputs is not empty (at least on entry have one file) | |
156 | void GetRange(const std::vector<CompactionInputFiles>& inputs, | |
157 | InternalKey* smallest, InternalKey* largest) const; | |
158 | ||
159 | int NumberLevels() const { return ioptions_.num_levels; } | |
160 | ||
161 | // Add more files to the inputs on "level" to make sure that | |
162 | // no newer version of a key is compacted to "level+1" while leaving an older | |
163 | // version in a "level". Otherwise, any Get() will search "level" first, | |
164 | // and will likely return an old/stale value for the key, since it always | |
165 | // searches in increasing order of level to find the value. This could | |
166 | // also scramble the order of merge operands. This function should be | |
167 | // called any time a new Compaction is created, and its inputs_[0] are | |
168 | // populated. | |
169 | // | |
170 | // Will return false if it is impossible to apply this compaction. | |
171 | bool ExpandInputsToCleanCut(const std::string& cf_name, | |
172 | VersionStorageInfo* vstorage, | |
11fdf7f2 TL |
173 | CompactionInputFiles* inputs, |
174 | InternalKey** next_smallest = nullptr); | |
7c673cae FG |
175 | |
176 | // Returns true if any one of the parent files are being compacted | |
177 | bool IsRangeInCompaction(VersionStorageInfo* vstorage, | |
178 | const InternalKey* smallest, | |
179 | const InternalKey* largest, int level, int* index); | |
180 | ||
181 | // Returns true if the key range that `inputs` files cover overlap with the | |
182 | // key range of a currently running compaction. | |
183 | bool FilesRangeOverlapWithCompaction( | |
184 | const std::vector<CompactionInputFiles>& inputs, int level) const; | |
185 | ||
186 | bool SetupOtherInputs(const std::string& cf_name, | |
187 | const MutableCFOptions& mutable_cf_options, | |
188 | VersionStorageInfo* vstorage, | |
189 | CompactionInputFiles* inputs, | |
190 | CompactionInputFiles* output_level_inputs, | |
191 | int* parent_index, int base_index); | |
192 | ||
193 | void GetGrandparents(VersionStorageInfo* vstorage, | |
194 | const CompactionInputFiles& inputs, | |
195 | const CompactionInputFiles& output_level_inputs, | |
196 | std::vector<FileMetaData*>* grandparents); | |
197 | ||
11fdf7f2 TL |
198 | void PickFilesMarkedForCompaction(const std::string& cf_name, |
199 | VersionStorageInfo* vstorage, | |
200 | int* start_level, int* output_level, | |
201 | CompactionInputFiles* start_level_inputs); | |
202 | ||
203 | bool GetOverlappingL0Files(VersionStorageInfo* vstorage, | |
204 | CompactionInputFiles* start_level_inputs, | |
205 | int output_level, int* parent_index); | |
206 | ||
7c673cae FG |
207 | // Register this compaction in the set of running compactions |
208 | void RegisterCompaction(Compaction* c); | |
209 | ||
210 | // Remove this compaction from the set of running compactions | |
211 | void UnregisterCompaction(Compaction* c); | |
212 | ||
213 | std::set<Compaction*>* level0_compactions_in_progress() { | |
214 | return &level0_compactions_in_progress_; | |
215 | } | |
216 | std::unordered_set<Compaction*>* compactions_in_progress() { | |
217 | return &compactions_in_progress_; | |
218 | } | |
219 | ||
220 | protected: | |
221 | const ImmutableCFOptions& ioptions_; | |
222 | ||
223 | // A helper function to SanitizeCompactionInputFiles() that | |
224 | // sanitizes "input_files" by adding necessary files. | |
225 | #ifndef ROCKSDB_LITE | |
226 | virtual Status SanitizeCompactionInputFilesForAllLevels( | |
227 | std::unordered_set<uint64_t>* input_files, | |
228 | const ColumnFamilyMetaData& cf_meta, const int output_level) const; | |
229 | #endif // ROCKSDB_LITE | |
230 | ||
231 | // Keeps track of all compactions that are running on Level0. | |
232 | // Protected by DB mutex | |
233 | std::set<Compaction*> level0_compactions_in_progress_; | |
234 | ||
235 | // Keeps track of all compactions that are running. | |
236 | // Protected by DB mutex | |
237 | std::unordered_set<Compaction*> compactions_in_progress_; | |
238 | ||
239 | const InternalKeyComparator* const icmp_; | |
240 | }; | |
241 | ||
7c673cae | 242 | #ifndef ROCKSDB_LITE |
f67539c2 TL |
243 | // A dummy compaction that never triggers any automatic |
244 | // compaction. | |
7c673cae FG |
245 | class NullCompactionPicker : public CompactionPicker { |
246 | public: | |
247 | NullCompactionPicker(const ImmutableCFOptions& ioptions, | |
248 | const InternalKeyComparator* icmp) | |
249 | : CompactionPicker(ioptions, icmp) {} | |
250 | virtual ~NullCompactionPicker() {} | |
251 | ||
252 | // Always return "nullptr" | |
f67539c2 TL |
253 | Compaction* PickCompaction( |
254 | const std::string& /*cf_name*/, | |
255 | const MutableCFOptions& /*mutable_cf_options*/, | |
20effc67 | 256 | const MutableDBOptions& /*mutable_db_options*/, |
f67539c2 TL |
257 | VersionStorageInfo* /*vstorage*/, LogBuffer* /* log_buffer */, |
258 | SequenceNumber /* earliest_memtable_seqno */) override { | |
7c673cae FG |
259 | return nullptr; |
260 | } | |
261 | ||
262 | // Always return "nullptr" | |
11fdf7f2 TL |
263 | Compaction* CompactRange(const std::string& /*cf_name*/, |
264 | const MutableCFOptions& /*mutable_cf_options*/, | |
20effc67 | 265 | const MutableDBOptions& /*mutable_db_options*/, |
11fdf7f2 TL |
266 | VersionStorageInfo* /*vstorage*/, |
267 | int /*input_level*/, int /*output_level*/, | |
f67539c2 | 268 | const CompactRangeOptions& /*compact_range_options*/, |
11fdf7f2 TL |
269 | const InternalKey* /*begin*/, |
270 | const InternalKey* /*end*/, | |
271 | InternalKey** /*compaction_end*/, | |
f67539c2 TL |
272 | bool* /*manual_conflict*/, |
273 | uint64_t /*max_file_num_to_ignore*/) override { | |
7c673cae FG |
274 | return nullptr; |
275 | } | |
276 | ||
277 | // Always returns false. | |
278 | virtual bool NeedsCompaction( | |
11fdf7f2 | 279 | const VersionStorageInfo* /*vstorage*/) const override { |
7c673cae FG |
280 | return false; |
281 | } | |
282 | }; | |
283 | #endif // !ROCKSDB_LITE | |
284 | ||
f67539c2 TL |
285 | // Attempts to find an intra L0 compaction conforming to the given parameters. |
286 | // | |
287 | // @param level_files Metadata for L0 files. | |
288 | // @param min_files_to_compact Minimum number of files required to | |
289 | // do the compaction. | |
290 | // @param max_compact_bytes_per_del_file Maximum average size in bytes per | |
291 | // file that is going to get deleted by | |
292 | // the compaction. | |
293 | // @param max_compaction_bytes Maximum total size in bytes (in terms | |
294 | // of compensated file size) for files | |
295 | // to be compacted. | |
296 | // @param [out] comp_inputs If a compaction was found, will be | |
297 | // initialized with corresponding input | |
298 | // files. Cannot be nullptr. | |
299 | // | |
300 | // @return true iff compaction was found. | |
301 | bool FindIntraL0Compaction( | |
302 | const std::vector<FileMetaData*>& level_files, size_t min_files_to_compact, | |
303 | uint64_t max_compact_bytes_per_del_file, uint64_t max_compaction_bytes, | |
304 | CompactionInputFiles* comp_inputs, | |
305 | SequenceNumber earliest_mem_seqno = kMaxSequenceNumber); | |
494da23a | 306 | |
7c673cae FG |
307 | CompressionType GetCompressionType(const ImmutableCFOptions& ioptions, |
308 | const VersionStorageInfo* vstorage, | |
309 | const MutableCFOptions& mutable_cf_options, | |
310 | int level, int base_level, | |
311 | const bool enable_compression = true); | |
312 | ||
20effc67 TL |
313 | CompressionOptions GetCompressionOptions( |
314 | const MutableCFOptions& mutable_cf_options, | |
315 | const VersionStorageInfo* vstorage, int level, | |
316 | const bool enable_compression = true); | |
11fdf7f2 | 317 | |
f67539c2 | 318 | } // namespace ROCKSDB_NAMESPACE |