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 ExtractUserKey(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