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 (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_ |
225 | |