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_FORMAT_H_ 6 #define STORAGE_LEVELDB_DB_FORMAT_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 } // namespace config 42 43 class InternalKey; 44 45 // Value types encoded as the last component of internal keys. 46 // DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk 47 // data structures. 48 enum ValueType { 49 kTypeDeletion = 0x0, 50 kTypeValue = 0x1 51 }; 52 // kValueTypeForSeek defines the ValueType that should be passed when 53 // constructing a ParsedInternalKey object for seeking to a particular 54 // sequence number (since we sort sequence numbers in decreasing order 55 // and the value type is embedded as the low 8 bits in the sequence 56 // number in internal keys, we need to use the highest-numbered 57 // ValueType, not the lowest). 58 static const ValueType kValueTypeForSeek = kTypeValue; 59 60 typedef uint64_t SequenceNumber; 61 62 // We leave eight bits empty at the bottom so a type and sequence# 63 // can be packed together into 64-bits. 64 static const SequenceNumber kMaxSequenceNumber = 65 ((0x1ull << 56) - 1); 66 67 struct ParsedInternalKey { 68 Slice user_key; 69 SequenceNumber sequence; 70 ValueType type; 71 72 ParsedInternalKey() { } // Intentionally left uninitialized (for speed) 73 ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t) 74 : user_key(u), sequence(seq), type(t) { } 75 std::string DebugString() const; 76 }; 77 78 // Return the length of the encoding of "key". 79 inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) { 80 return key.user_key.size() + 8; 81 } 82 83 // Append the serialization of "key" to *result. 84 extern void AppendInternalKey(std::string* result, 85 const ParsedInternalKey& key); 86 87 // Attempt to parse an internal key from "internal_key". On success, 88 // stores the parsed data in "*result", and returns true. 89 // 90 // On error, returns false, leaves "*result" in an undefined state. 91 extern bool ParseInternalKey(const Slice& internal_key, 92 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 inline ValueType ExtractValueType(const Slice& internal_key) { 101 assert(internal_key.size() >= 8); 102 const size_t n = internal_key.size(); 103 uint64_t num = DecodeFixed64(internal_key.data() + n - 8); 104 unsigned char c = num & 0xff; 105 return static_cast<ValueType>(c); 106 } 107 108 // A comparator for internal keys that uses a specified comparator for 109 // the user key portion and breaks ties by decreasing sequence number. 110 class InternalKeyComparator : public Comparator { 111 private: 112 const Comparator* user_comparator_; 113 public: 114 explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { } 115 virtual const char* Name() const; 116 virtual int Compare(const Slice& a, const Slice& b) const; 117 virtual void FindShortestSeparator( 118 std::string* start, 119 const Slice& limit) const; 120 virtual void FindShortSuccessor(std::string* key) const; 121 122 const Comparator* user_comparator() const { return user_comparator_; } 123 124 int Compare(const InternalKey& a, const InternalKey& b) const; 125 }; 126 127 // Filter policy wrapper that converts from internal keys to user keys 128 class InternalFilterPolicy : public FilterPolicy { 129 private: 130 const FilterPolicy* const user_policy_; 131 public: 132 explicit InternalFilterPolicy(const FilterPolicy* p) : user_policy_(p) { } 133 virtual const char* Name() const; 134 virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const; 135 virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const; 136 }; 137 138 // Modules in this directory should keep internal keys wrapped inside 139 // the following class instead of plain strings so that we do not 140 // incorrectly use string comparisons instead of an InternalKeyComparator. 141 class InternalKey { 142 private: 143 std::string rep_; 144 public: 145 InternalKey() { } // Leave rep_ as empty to indicate it is invalid 146 InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) { 147 AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t)); 148 } 149 150 void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); } 151 Slice Encode() const { 152 assert(!rep_.empty()); 153 return rep_; 154 } 155 156 Slice user_key() const { return ExtractUserKey(rep_); } 157 158 void SetFrom(const ParsedInternalKey& p) { 159 rep_.clear(); 160 AppendInternalKey(&rep_, p); 161 } 162 163 void Clear() { rep_.clear(); } 164 165 std::string DebugString() const; 166 }; 167 168 inline int InternalKeyComparator::Compare( 169 const InternalKey& a, const InternalKey& b) const { 170 return Compare(a.Encode(), b.Encode()); 171 } 172 173 inline bool ParseInternalKey(const Slice& internal_key, 174 ParsedInternalKey* result) { 175 const size_t n = internal_key.size(); 176 if (n < 8) return false; 177 uint64_t num = DecodeFixed64(internal_key.data() + n - 8); 178 unsigned char c = num & 0xff; 179 result->sequence = num >> 8; 180 result->type = static_cast<ValueType>(c); 181 result->user_key = Slice(internal_key.data(), n - 8); 182 return (c <= static_cast<unsigned char>(kTypeValue)); 183 } 184 185 // A helper class useful for DBImpl::Get() 186 class LookupKey { 187 public: 188 // Initialize *this for looking up user_key at a snapshot with 189 // the specified sequence number. 190 LookupKey(const Slice& user_key, SequenceNumber sequence); 191 192 ~LookupKey(); 193 194 // Return a key suitable for lookup in a MemTable. 195 Slice memtable_key() const { return Slice(start_, end_ - start_); } 196 197 // Return an internal key (suitable for passing to an internal iterator) 198 Slice internal_key() const { return Slice(kstart_, end_ - kstart_); } 199 200 // Return the user key 201 Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); } 202 203 private: 204 // We construct a char array of the form: 205 // klength varint32 <-- start_ 206 // userkey char[klength] <-- kstart_ 207 // tag uint64 208 // <-- end_ 209 // The array is a suitable MemTable key. 210 // The suffix starting with "userkey" can be used as an InternalKey. 211 const char* start_; 212 const char* kstart_; 213 const char* end_; 214 char space_[200]; // Avoid allocation for short keys 215 216 // No copying allowed 217 LookupKey(const LookupKey&); 218 void operator=(const LookupKey&); 219 }; 220 221 inline LookupKey::~LookupKey() { 222 if (start_ != space_) delete[] start_; 223 } 224 225 } // namespace leveldb 226 227 #endif // STORAGE_LEVELDB_DB_FORMAT_H_ 228