ceph/src/rocksdb/db/compaction_picker.h

   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.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 {
  26
  27 class LogBuffer;
  28 class Compaction;
  29 class VersionStorageInfo;
  30 struct CompactionInputFiles;
  31
  32 class CompactionPicker {
  33  public:
  34   CompactionPicker(const ImmutableCFOptions& ioptions,
  35                    const InternalKeyComparator* icmp);
  36   virtual ~CompactionPicker();
  37
  38   // Pick level and inputs for a new compaction.
  39   // Returns nullptr if there is no compaction to be done.
  40   // Otherwise returns a pointer to a heap-allocated object that
  41   // describes the compaction.  Caller should delete the result.
  42   virtual Compaction* PickCompaction(const std::string& cf_name,
  43                                      const MutableCFOptions& mutable_cf_options,
  44                                      VersionStorageInfo* vstorage,
  45                                      LogBuffer* log_buffer) = 0;
  46
  47   // Return a compaction object for compacting the range [begin,end] in
  48   // the specified level.  Returns nullptr if there is nothing in that
  49   // level that overlaps the specified range.  Caller should delete
  50   // the result.
  51   //
  52   // The returned Compaction might not include the whole requested range.
  53   // In that case, compaction_end will be set to the next key that needs
  54   // compacting. In case the compaction will compact the whole range,
  55   // compaction_end will be set to nullptr.
  56   // Client is responsible for compaction_end storage -- when called,
  57   // *compaction_end should point to valid InternalKey!
  58   virtual Compaction* CompactRange(
  59       const std::string& cf_name, const MutableCFOptions& mutable_cf_options,
  60       VersionStorageInfo* vstorage, int input_level, int output_level,
  61       uint32_t output_path_id, uint32_t max_subcompactions,
  62       const InternalKey* begin, const InternalKey* end,
  63       InternalKey** compaction_end, bool* manual_conflict);
  64
  65   // The maximum allowed output level.  Default value is NumberLevels() - 1.
  66   virtual int MaxOutputLevel() const { return NumberLevels() - 1; }
  67
  68   virtual bool NeedsCompaction(const VersionStorageInfo* vstorage) const = 0;
  69
  70 // Sanitize the input set of compaction input files.
  71 // When the input parameters do not describe a valid compaction, the
  72 // function will try to fix the input_files by adding necessary
  73 // files.  If it's not possible to conver an invalid input_files
  74 // into a valid one by adding more files, the function will return a
  75 // non-ok status with specific reason.
  76 #ifndef ROCKSDB_LITE
  77   Status SanitizeCompactionInputFiles(std::unordered_set<uint64_t>* input_files,
  78                                       const ColumnFamilyMetaData& cf_meta,
  79                                       const int output_level) const;
  80 #endif  // ROCKSDB_LITE
  81
  82   // Free up the files that participated in a compaction
  83   //
  84   // Requirement: DB mutex held
  85   void ReleaseCompactionFiles(Compaction* c, Status status);
  86
  87   // Returns true if any one of the specified files are being compacted
  88   bool AreFilesInCompaction(const std::vector<FileMetaData*>& files);
  89
  90   // Takes a list of CompactionInputFiles and returns a (manual) Compaction
  91   // object.
  92   //
  93   // Caller must provide a set of input files that has been passed through
  94   // `SanitizeCompactionInputFiles` earlier. The lock should not be released
  95   // between that call and this one.
  96   Compaction* CompactFiles(const CompactionOptions& compact_options,
  97                            const std::vector<CompactionInputFiles>& input_files,
  98                            int output_level, VersionStorageInfo* vstorage,
  99                            const MutableCFOptions& mutable_cf_options,
 100                            uint32_t output_path_id);
 101
 102   // Converts a set of compaction input file numbers into
 103   // a list of CompactionInputFiles.
 104   Status GetCompactionInputsFromFileNumbers(
 105       std::vector<CompactionInputFiles>* input_files,
 106       std::unordered_set<uint64_t>* input_set,
 107       const VersionStorageInfo* vstorage,
 108       const CompactionOptions& compact_options) const;
 109
 110   // Is there currently a compaction involving level 0 taking place
 111   bool IsLevel0CompactionInProgress() const {
 112     return !level0_compactions_in_progress_.empty();
 113   }
 114
 115   // Return true if the passed key range overlap with a compaction output
 116   // that is currently running.
 117   bool RangeOverlapWithCompaction(const Slice& smallest_user_key,
 118                                   const Slice& largest_user_key,
 119                                   int level) const;
 120
 121   // Stores the minimal range that covers all entries in inputs in
 122   // *smallest, *largest.
 123   // REQUIRES: inputs is not empty
 124   void GetRange(const CompactionInputFiles& inputs, InternalKey* smallest,
 125                 InternalKey* largest) const;
 126
 127   // Stores the minimal range that covers all entries in inputs1 and inputs2
 128   // in *smallest, *largest.
 129   // REQUIRES: inputs is not empty
 130   void GetRange(const CompactionInputFiles& inputs1,
 131                 const CompactionInputFiles& inputs2, InternalKey* smallest,
 132                 InternalKey* largest) const;
 133
 134   // Stores the minimal range that covers all entries in inputs
 135   // in *smallest, *largest.
 136   // REQUIRES: inputs is not empty (at least on entry have one file)
 137   void GetRange(const std::vector<CompactionInputFiles>& inputs,
 138                 InternalKey* smallest, InternalKey* largest) const;
 139
 140   int NumberLevels() const { return ioptions_.num_levels; }
 141
 142   // Add more files to the inputs on "level" to make sure that
 143   // no newer version of a key is compacted to "level+1" while leaving an older
 144   // version in a "level". Otherwise, any Get() will search "level" first,
 145   // and will likely return an old/stale value for the key, since it always
 146   // searches in increasing order of level to find the value. This could
 147   // also scramble the order of merge operands. This function should be
 148   // called any time a new Compaction is created, and its inputs_[0] are
 149   // populated.
 150   //
 151   // Will return false if it is impossible to apply this compaction.
 152   bool ExpandInputsToCleanCut(const std::string& cf_name,
 153                               VersionStorageInfo* vstorage,
 154                               CompactionInputFiles* inputs,
 155                               InternalKey** next_smallest = nullptr);
 156
 157   // Returns true if any one of the parent files are being compacted
 158   bool IsRangeInCompaction(VersionStorageInfo* vstorage,
 159                            const InternalKey* smallest,
 160                            const InternalKey* largest, int level, int* index);
 161
 162   // Returns true if the key range that `inputs` files cover overlap with the
 163   // key range of a currently running compaction.
 164   bool FilesRangeOverlapWithCompaction(
 165       const std::vector<CompactionInputFiles>& inputs, int level) const;
 166
 167   bool SetupOtherInputs(const std::string& cf_name,
 168                         const MutableCFOptions& mutable_cf_options,
 169                         VersionStorageInfo* vstorage,
 170                         CompactionInputFiles* inputs,
 171                         CompactionInputFiles* output_level_inputs,
 172                         int* parent_index, int base_index);
 173
 174   void GetGrandparents(VersionStorageInfo* vstorage,
 175                        const CompactionInputFiles& inputs,
 176                        const CompactionInputFiles& output_level_inputs,
 177                        std::vector<FileMetaData*>* grandparents);
 178
 179   void PickFilesMarkedForCompaction(const std::string& cf_name,
 180                                     VersionStorageInfo* vstorage,
 181                                     int* start_level, int* output_level,
 182                                     CompactionInputFiles* start_level_inputs);
 183
 184   bool GetOverlappingL0Files(VersionStorageInfo* vstorage,
 185                              CompactionInputFiles* start_level_inputs,
 186                              int output_level, int* parent_index);
 187
 188   // Register this compaction in the set of running compactions
 189   void RegisterCompaction(Compaction* c);
 190
 191   // Remove this compaction from the set of running compactions
 192   void UnregisterCompaction(Compaction* c);
 193
 194   std::set<Compaction*>* level0_compactions_in_progress() {
 195     return &level0_compactions_in_progress_;
 196   }
 197   std::unordered_set<Compaction*>* compactions_in_progress() {
 198     return &compactions_in_progress_;
 199   }
 200
 201  protected:
 202   const ImmutableCFOptions& ioptions_;
 203
 204 // A helper function to SanitizeCompactionInputFiles() that
 205 // sanitizes "input_files" by adding necessary files.
 206 #ifndef ROCKSDB_LITE
 207   virtual Status SanitizeCompactionInputFilesForAllLevels(
 208       std::unordered_set<uint64_t>* input_files,
 209       const ColumnFamilyMetaData& cf_meta, const int output_level) const;
 210 #endif  // ROCKSDB_LITE
 211
 212   // Keeps track of all compactions that are running on Level0.
 213   // Protected by DB mutex
 214   std::set<Compaction*> level0_compactions_in_progress_;
 215
 216   // Keeps track of all compactions that are running.
 217   // Protected by DB mutex
 218   std::unordered_set<Compaction*> compactions_in_progress_;
 219
 220   const InternalKeyComparator* const icmp_;
 221 };
 222
 223 class LevelCompactionPicker : public CompactionPicker {
 224  public:
 225   LevelCompactionPicker(const ImmutableCFOptions& ioptions,
 226                         const InternalKeyComparator* icmp)
 227       : CompactionPicker(ioptions, icmp) {}
 228   virtual Compaction* PickCompaction(const std::string& cf_name,
 229                                      const MutableCFOptions& mutable_cf_options,
 230                                      VersionStorageInfo* vstorage,
 231                                      LogBuffer* log_buffer) override;
 232
 233   virtual bool NeedsCompaction(
 234       const VersionStorageInfo* vstorage) const override;
 235 };
 236
 237 #ifndef ROCKSDB_LITE
 238 class NullCompactionPicker : public CompactionPicker {
 239  public:
 240   NullCompactionPicker(const ImmutableCFOptions& ioptions,
 241                        const InternalKeyComparator* icmp)
 242       : CompactionPicker(ioptions, icmp) {}
 243   virtual ~NullCompactionPicker() {}
 244
 245   // Always return "nullptr"
 246   Compaction* PickCompaction(const std::string& /*cf_name*/,
 247                              const MutableCFOptions& /*mutable_cf_options*/,
 248                              VersionStorageInfo* /*vstorage*/,
 249                              LogBuffer* /*log_buffer*/) override {
 250     return nullptr;
 251   }
 252
 253   // Always return "nullptr"
 254   Compaction* CompactRange(const std::string& /*cf_name*/,
 255                            const MutableCFOptions& /*mutable_cf_options*/,
 256                            VersionStorageInfo* /*vstorage*/,
 257                            int /*input_level*/, int /*output_level*/,
 258                            uint32_t /*output_path_id*/,
 259                            uint32_t /*max_subcompactions*/,
 260                            const InternalKey* /*begin*/,
 261                            const InternalKey* /*end*/,
 262                            InternalKey** /*compaction_end*/,
 263                            bool* /*manual_conflict*/) override {
 264     return nullptr;
 265   }
 266
 267   // Always returns false.
 268   virtual bool NeedsCompaction(
 269       const VersionStorageInfo* /*vstorage*/) const override {
 270     return false;
 271   }
 272 };
 273 #endif  // !ROCKSDB_LITE
 274
 275 bool FindIntraL0Compaction(const std::vector<FileMetaData*>& level_files,
 276                            size_t min_files_to_compact,
 277                            uint64_t max_compact_bytes_per_del_file,
 278                            CompactionInputFiles* comp_inputs);
 279
 280 CompressionType GetCompressionType(const ImmutableCFOptions& ioptions,
 281                                    const VersionStorageInfo* vstorage,
 282                                    const MutableCFOptions& mutable_cf_options,
 283                                    int level, int base_level,
 284                                    const bool enable_compression = true);
 285
 286 CompressionOptions GetCompressionOptions(const ImmutableCFOptions& ioptions,
 287                                          const VersionStorageInfo* vstorage,
 288                                          int level,
 289                                          const bool enable_compression = true);
 290
 291 }  // namespace rocksdb