Branch data Line data Source code
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 [ # # ]: 77746 : ParsedInternalKey() {} // Intentionally left uninitialized (for speed)
75 : 1007 : ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
76 : 1007 : : 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 : 257949275 : inline Slice ExtractUserKey(const Slice& internal_key) {
96 [ - + ]: 257949275 : assert(internal_key.size() >= 8);
97 : 257949275 : 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 [ - + # # : 3160 : class InternalKeyComparator : public Comparator {
# # ][ + -
+ - + - ]
103 : : private:
104 : : const Comparator* user_comparator_;
105 : :
106 : : public:
107 [ + - ]: 489 : 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 [ + - + - : 13808646 : 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 : 489 : class InternalFilterPolicy : public FilterPolicy {
121 : : private:
122 : : const FilterPolicy* const user_policy_;
123 : :
124 : : public:
125 [ + - ]: 489 : 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 [ - - - - : 2522 : class InternalKey {
- - - - +
- - - - -
- - - + +
- ][ - + +
- # # ][ #
# # # # #
# # # # #
# # # # #
# # # # ]
[ - - - -
- - + - +
- + - ]
135 : : private:
136 : : std::string rep_;
137 : :
138 : : public:
139 [ + - + - : 892 : InternalKey() {} // Leave rep_ as empty to indicate it is invalid
- - + - +
- - + -
- ][ # # #
# # # ][ +
- - + - -
+ - + - #
# # # ]
140 [ + - ]: 96 : InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
141 [ + - ]: 96 : AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
142 : 96 : }
143 : :
144 : 28758 : bool DecodeFrom(const Slice& s) {
145 : 28758 : rep_.assign(s.data(), s.size());
146 : 28758 : return !rep_.empty();
147 : : }
148 : :
149 : 1289434 : Slice Encode() const {
150 [ - + ]: 1289434 : assert(!rep_.empty());
151 [ - + ]: 1289434 : return rep_;
152 : : }
153 : :
154 [ - - - - : 1297562 : Slice user_key() const { return ExtractUserKey(rep_); }
- - - - -
+ - + - +
- + - + -
+ - + - -
- - ][ - +
- + # # #
# # # # #
# # # # #
# # # # #
# # # # ]
155 : :
156 : : void SetFrom(const ParsedInternalKey& p) {
157 : : rep_.clear();
158 : : AppendInternalKey(&rep_, p);
159 : : }
160 : :
161 [ + - ]: 48 : void Clear() { rep_.clear(); }
162 : :
163 : : std::string DebugString() const;
164 : : };
165 : :
166 : 717 : inline int InternalKeyComparator::Compare(const InternalKey& a,
167 : : const InternalKey& b) const {
168 : 717 : return Compare(a.Encode(), b.Encode());
169 : : }
170 : :
171 : 79350 : inline bool ParseInternalKey(const Slice& internal_key,
172 : : ParsedInternalKey* result) {
173 [ + - ]: 79350 : const size_t n = internal_key.size();
174 [ + - ]: 79350 : if (n < 8) return false;
175 : 79350 : uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
176 : 79350 : uint8_t c = num & 0xff;
177 : 79350 : result->sequence = num >> 8;
178 : 79350 : result->type = static_cast<ValueType>(c);
179 : 79350 : result->user_key = Slice(internal_key.data(), n - 8);
180 : 79350 : 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 : 4726623 : Slice memtable_key() const { return Slice(start_, end_ - start_); }
197 : :
198 : : // Return an internal key (suitable for passing to an internal iterator)
199 [ + - ]: 4556699 : Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
200 : :
201 : : // Return the user key
202 [ + - ]: 9247739 : 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 : 4722718 : inline LookupKey::~LookupKey() {
219 [ - + - - ]: 4722718 : if (start_ != space_) delete[] start_;
220 : 4722718 : }
221 : :
222 : : } // namespace leveldb
223 : :
224 : : #endif // STORAGE_LEVELDB_DB_DBFORMAT_H_
|
