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