1  // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
  2  // Use of this source code is governed by a BSD-style license that can be
  3  // found in the LICENSE file. See the AUTHORS file for names of contributors.
  4  
  5  #ifndef STORAGE_LEVELDB_DB_DBFORMAT_H_
  6  #define STORAGE_LEVELDB_DB_DBFORMAT_H_
  7  
  8  #include <cstddef>
  9  #include <cstdint>
 10  #include <string>
 11  
 12  #include "leveldb/comparator.h"
 13  #include "leveldb/db.h"
 14  #include "leveldb/filter_policy.h"
 15  #include "leveldb/slice.h"
 16  #include "leveldb/table_builder.h"
 17  #include "util/coding.h"
 18  #include "util/logging.h"
 19  
 20  namespace leveldb {
 21  
 22  // Grouping of constants.  We may want to make some of these
 23  // parameters set via options.
 24  namespace config {
 25  static const int kNumLevels = 7;
 26  
 27  // Level-0 compaction is started when we hit this many files.
 28  static const int kL0_CompactionTrigger = 4;
 29  
 30  // Soft limit on number of level-0 files.  We slow down writes at this point.
 31  static const int kL0_SlowdownWritesTrigger = 8;
 32  
 33  // Maximum number of level-0 files.  We stop writes at this point.
 34  static const int kL0_StopWritesTrigger = 12;
 35  
 36  // Maximum level to which a new compacted memtable is pushed if it
 37  // does not create overlap.  We try to push to level 2 to avoid the
 38  // relatively expensive level 0=>1 compactions and to avoid some
 39  // expensive manifest file operations.  We do not push all the way to
 40  // the largest level since that can generate a lot of wasted disk
 41  // space if the same key space is being repeatedly overwritten.
 42  static const int kMaxMemCompactLevel = 2;
 43  
 44  // Approximate gap in bytes between samples of data read during iteration.
 45  static const int kReadBytesPeriod = 1048576;
 46  
 47  }  // namespace config
 48  
 49  class InternalKey;
 50  
 51  // Value types encoded as the last component of internal keys.
 52  // DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk
 53  // data structures.
 54  enum ValueType { kTypeDeletion = 0x0, kTypeValue = 0x1 };
 55  // kValueTypeForSeek defines the ValueType that should be passed when
 56  // constructing a ParsedInternalKey object for seeking to a particular
 57  // sequence number (since we sort sequence numbers in decreasing order
 58  // and the value type is embedded as the low 8 bits in the sequence
 59  // number in internal keys, we need to use the highest-numbered
 60  // ValueType, not the lowest).
 61  static const ValueType kValueTypeForSeek = kTypeValue;
 62  
 63  typedef uint64_t SequenceNumber;
 64  
 65  // We leave eight bits empty at the bottom so a type and sequence#
 66  // can be packed together into 64-bits.
 67  static const SequenceNumber kMaxSequenceNumber = ((0x1ull << 56) - 1);
 68  
 69  struct ParsedInternalKey {
 70    Slice user_key;
 71    SequenceNumber sequence;
 72    ValueType type;
 73  
 74    ParsedInternalKey() {}  // Intentionally left uninitialized (for speed)
 75    ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
 76        : user_key(u), sequence(seq), type(t) {}
 77    std::string DebugString() const;
 78  };
 79  
 80  // Return the length of the encoding of "key".
 81  inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) {
 82    return key.user_key.size() + 8;
 83  }
 84  
 85  // Append the serialization of "key" to *result.
 86  void AppendInternalKey(std::string* result, const ParsedInternalKey& key);
 87  
 88  // Attempt to parse an internal key from "internal_key".  On success,
 89  // stores the parsed data in "*result", and returns true.
 90  //
 91  // On error, returns false, leaves "*result" in an undefined state.
 92  bool ParseInternalKey(const Slice& internal_key, ParsedInternalKey* result);
 93  
 94  // Returns the user key portion of an internal key.
 95  inline Slice ExtractUserKey(const Slice& internal_key) {
 96    assert(internal_key.size() >= 8);
 97    return Slice(internal_key.data(), internal_key.size() - 8);
 98  }
 99  
100  // A comparator for internal keys that uses a specified comparator for
101  // the user key portion and breaks ties by decreasing sequence number.
102  class InternalKeyComparator : public Comparator {
103   private:
104    const Comparator* user_comparator_;
105  
106   public:
107    explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) {}
108    const char* Name() const override;
109    int Compare(const Slice& a, const Slice& b) const override;
110    void FindShortestSeparator(std::string* start,
111                               const Slice& limit) const override;
112    void FindShortSuccessor(std::string* key) const override;
113  
114    const Comparator* user_comparator() const { return user_comparator_; }
115  
116    int Compare(const InternalKey& a, const InternalKey& b) const;
117  };
118  
119  // Filter policy wrapper that converts from internal keys to user keys
120  class InternalFilterPolicy : public FilterPolicy {
121   private:
122    const FilterPolicy* const user_policy_;
123  
124   public:
125    explicit InternalFilterPolicy(const FilterPolicy* p) : user_policy_(p) {}
126    const char* Name() const override;
127    void CreateFilter(const Slice* keys, int n, std::string* dst) const override;
128    bool KeyMayMatch(const Slice& key, const Slice& filter) const override;
129  };
130  
131  // Modules in this directory should keep internal keys wrapped inside
132  // the following class instead of plain strings so that we do not
133  // incorrectly use string comparisons instead of an InternalKeyComparator.
134  class InternalKey {
135   private:
136    std::string rep_;
137  
138   public:
139    InternalKey() {}  // Leave rep_ as empty to indicate it is invalid
140    InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
141      AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
142    }
143  
144    bool DecodeFrom(const Slice& s) {
145      rep_.assign(s.data(), s.size());
146      return !rep_.empty();
147    }
148  
149    Slice Encode() const {
150      assert(!rep_.empty());
151      return rep_;
152    }
153  
154    Slice user_key() const { return ExtractUserKey(rep_); }
155  
156    void SetFrom(const ParsedInternalKey& p) {
157      rep_.clear();
158      AppendInternalKey(&rep_, p);
159    }
160  
161    void Clear() { rep_.clear(); }
162  
163    std::string DebugString() const;
164  };
165  
166  inline int InternalKeyComparator::Compare(const InternalKey& a,
167                                            const InternalKey& b) const {
168    return Compare(a.Encode(), b.Encode());
169  }
170  
171  inline bool ParseInternalKey(const Slice& internal_key,
172                               ParsedInternalKey* result) {
173    const size_t n = internal_key.size();
174    if (n < 8) return false;
175    uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
176    uint8_t c = num & 0xff;
177    result->sequence = num >> 8;
178    result->type = static_cast<ValueType>(c);
179    result->user_key = Slice(internal_key.data(), n - 8);
180    return (c <= static_cast<uint8_t>(kTypeValue));
181  }
182  
183  // A helper class useful for DBImpl::Get()
184  class LookupKey {
185   public:
186    // Initialize *this for looking up user_key at a snapshot with
187    // the specified sequence number.
188    LookupKey(const Slice& user_key, SequenceNumber sequence);
189  
190    LookupKey(const LookupKey&) = delete;
191    LookupKey& operator=(const LookupKey&) = delete;
192  
193    ~LookupKey();
194  
195    // Return a key suitable for lookup in a MemTable.
196    Slice memtable_key() const { return Slice(start_, end_ - start_); }
197  
198    // Return an internal key (suitable for passing to an internal iterator)
199    Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
200  
201    // Return the user key
202    Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
203  
204   private:
205    // We construct a char array of the form:
206    //    klength  varint32               <-- start_
207    //    userkey  char[klength]          <-- kstart_
208    //    tag      uint64
209    //                                    <-- end_
210    // The array is a suitable MemTable key.
211    // The suffix starting with "userkey" can be used as an InternalKey.
212    const char* start_;
213    const char* kstart_;
214    const char* end_;
215    char space_[200];  // Avoid allocation for short keys
216  };
217  
218  inline LookupKey::~LookupKey() {
219    if (start_ != space_) delete[] start_;
220  }
221  
222  }  // namespace leveldb
223  
224  #endif  // STORAGE_LEVELDB_DB_DBFORMAT_H_