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