db/dbformat.h

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