ceph/src/rocksdb/db/compaction_picker.h

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