1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. 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). 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 18 #include "db/compaction/compaction.h" 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 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. 30 31 class LogBuffer; 32 class Compaction; 33 class VersionStorageInfo; 34 struct CompactionInputFiles; 35 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. 47 class CompactionPicker { 48 public: 49 CompactionPicker(const ImmutableOptions& 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. 57 virtual Compaction* PickCompaction( 58 const std::string& cf_name, const MutableCFOptions& mutable_cf_options, 59 const MutableDBOptions& mutable_db_options, VersionStorageInfo* vstorage, 60 LogBuffer* log_buffer, 61 SequenceNumber earliest_memtable_seqno = kMaxSequenceNumber) = 0; 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, 76 const MutableDBOptions& mutable_db_options, VersionStorageInfo* vstorage, 77 int input_level, int output_level, 78 const CompactRangeOptions& compact_range_options, 79 const InternalKey* begin, const InternalKey* end, 80 InternalKey** compaction_end, bool* manual_conflict, 81 uint64_t max_file_num_to_ignore); 82 83 // The maximum allowed output level. Default value is NumberLevels() - 1. MaxOutputLevel()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. 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. 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, 118 const MutableDBOptions& mutable_db_options, 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 IsLevel0CompactionInProgress()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 NumberLevels()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, 173 CompactionInputFiles* inputs, 174 InternalKey** next_smallest = nullptr); 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 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 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 level0_compactions_in_progress()213 std::set<Compaction*>* level0_compactions_in_progress() { 214 return &level0_compactions_in_progress_; 215 } compactions_in_progress()216 std::unordered_set<Compaction*>* compactions_in_progress() { 217 return &compactions_in_progress_; 218 } 219 220 protected: 221 const ImmutableOptions& 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 242 #ifndef ROCKSDB_LITE 243 // A dummy compaction that never triggers any automatic 244 // compaction. 245 class NullCompactionPicker : public CompactionPicker { 246 public: NullCompactionPicker(const ImmutableOptions & ioptions,const InternalKeyComparator * icmp)247 NullCompactionPicker(const ImmutableOptions& ioptions, 248 const InternalKeyComparator* icmp) 249 : CompactionPicker(ioptions, icmp) {} ~NullCompactionPicker()250 virtual ~NullCompactionPicker() {} 251 252 // Always return "nullptr" PickCompaction(const std::string &,const MutableCFOptions &,const MutableDBOptions &,VersionStorageInfo *,LogBuffer *,SequenceNumber)253 Compaction* PickCompaction( 254 const std::string& /*cf_name*/, 255 const MutableCFOptions& /*mutable_cf_options*/, 256 const MutableDBOptions& /*mutable_db_options*/, 257 VersionStorageInfo* /*vstorage*/, LogBuffer* /* log_buffer */, 258 SequenceNumber /* earliest_memtable_seqno */) override { 259 return nullptr; 260 } 261 262 // Always return "nullptr" CompactRange(const std::string &,const MutableCFOptions &,const MutableDBOptions &,VersionStorageInfo *,int,int,const CompactRangeOptions &,const InternalKey *,const InternalKey *,InternalKey **,bool *,uint64_t)263 Compaction* CompactRange(const std::string& /*cf_name*/, 264 const MutableCFOptions& /*mutable_cf_options*/, 265 const MutableDBOptions& /*mutable_db_options*/, 266 VersionStorageInfo* /*vstorage*/, 267 int /*input_level*/, int /*output_level*/, 268 const CompactRangeOptions& /*compact_range_options*/, 269 const InternalKey* /*begin*/, 270 const InternalKey* /*end*/, 271 InternalKey** /*compaction_end*/, 272 bool* /*manual_conflict*/, 273 uint64_t /*max_file_num_to_ignore*/) override { 274 return nullptr; 275 } 276 277 // Always returns false. NeedsCompaction(const VersionStorageInfo *)278 virtual bool NeedsCompaction( 279 const VersionStorageInfo* /*vstorage*/) const override { 280 return false; 281 } 282 }; 283 #endif // !ROCKSDB_LITE 284 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); 306 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 313 CompressionOptions GetCompressionOptions( 314 const MutableCFOptions& mutable_cf_options, 315 const VersionStorageInfo* vstorage, int level, 316 const bool enable_compression = true); 317 318 } // namespace ROCKSDB_NAMESPACE 319