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