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.
5 #ifndef STORAGE_LEVELDB_DB_FORMAT_H_
6 #define STORAGE_LEVELDB_DB_FORMAT_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"
19 // Grouping of constants. We may want to make some of these
20 // parameters set via options.
22 static const int kNumLevels = 7;
24 // Level-0 compaction is started when we hit this many files.
25 static const int kL0_CompactionTrigger = 4;
27 // Soft limit on number of level-0 files. We slow down writes at this point.
28 static const int kL0_SlowdownWritesTrigger = 8;
30 // Maximum number of level-0 files. We stop writes at this point.
31 static const int kL0_StopWritesTrigger = 12;
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;
45 // Value types encoded as the last component of internal keys.
46 // DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk
52 // kValueTypeForSeek defines the ValueType that should be passed when
53 // constructing a ParsedInternalKey object for seeking to a particular
54 // sequence number (since we sort sequence numbers in decreasing order
55 // and the value type is embedded as the low 8 bits in the sequence
56 // number in internal keys, we need to use the highest-numbered
57 // ValueType, not the lowest).
58 static const ValueType kValueTypeForSeek = kTypeValue;
60 typedef uint64_t SequenceNumber;
62 // We leave eight bits empty at the bottom so a type and sequence#
63 // can be packed together into 64-bits.
64 static const SequenceNumber kMaxSequenceNumber =
67 struct ParsedInternalKey {
69 SequenceNumber sequence;
72 ParsedInternalKey() { } // Intentionally left uninitialized (for speed)
73 ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
74 : user_key(u), sequence(seq), type(t) { }
75 std::string DebugString() const;
78 // Return the length of the encoding of "key".
79 inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) {
80 return key.user_key.size() + 8;
83 // Append the serialization of "key" to *result.
84 extern void AppendInternalKey(std::string* result,
85 const ParsedInternalKey& key);
87 // Attempt to parse an internal key from "internal_key". On success,
88 // stores the parsed data in "*result", and returns true.
90 // On error, returns false, leaves "*result" in an undefined state.
91 extern bool ParseInternalKey(const Slice& internal_key,
92 ParsedInternalKey* result);
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);
100 inline ValueType ExtractValueType(const Slice& internal_key) {
101 assert(internal_key.size() >= 8);
102 const size_t n = internal_key.size();
103 uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
104 unsigned char c = num & 0xff;
105 return static_cast<ValueType>(c);
108 // A comparator for internal keys that uses a specified comparator for
109 // the user key portion and breaks ties by decreasing sequence number.
110 class InternalKeyComparator : public Comparator {
112 const Comparator* user_comparator_;
114 explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { }
115 virtual const char* Name() const;
116 virtual int Compare(const Slice& a, const Slice& b) const;
117 virtual void FindShortestSeparator(
119 const Slice& limit) const;
120 virtual void FindShortSuccessor(std::string* key) const;
122 const Comparator* user_comparator() const { return user_comparator_; }
124 int Compare(const InternalKey& a, const InternalKey& b) const;
127 // Filter policy wrapper that converts from internal keys to user keys
128 class InternalFilterPolicy : public FilterPolicy {
130 const FilterPolicy* const user_policy_;
132 explicit InternalFilterPolicy(const FilterPolicy* p) : user_policy_(p) { }
133 virtual const char* Name() const;
134 virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const;
135 virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const;
138 // Modules in this directory should keep internal keys wrapped inside
139 // the following class instead of plain strings so that we do not
140 // incorrectly use string comparisons instead of an InternalKeyComparator.
145 InternalKey() { } // Leave rep_ as empty to indicate it is invalid
146 InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
147 AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
150 void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); }
151 Slice Encode() const {
152 assert(!rep_.empty());
156 Slice user_key() const { return ExtractUserKey(rep_); }
158 void SetFrom(const ParsedInternalKey& p) {
160 AppendInternalKey(&rep_, p);
163 void Clear() { rep_.clear(); }
165 std::string DebugString() const;
168 inline int InternalKeyComparator::Compare(
169 const InternalKey& a, const InternalKey& b) const {
170 return Compare(a.Encode(), b.Encode());
173 inline bool ParseInternalKey(const Slice& internal_key,
174 ParsedInternalKey* result) {
175 const size_t n = internal_key.size();
176 if (n < 8) return false;
177 uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
178 unsigned char c = num & 0xff;
179 result->sequence = num >> 8;
180 result->type = static_cast<ValueType>(c);
181 result->user_key = Slice(internal_key.data(), n - 8);
182 return (c <= static_cast<unsigned char>(kTypeValue));
185 // A helper class useful for DBImpl::Get()
188 // Initialize *this for looking up user_key at a snapshot with
189 // the specified sequence number.
190 LookupKey(const Slice& user_key, SequenceNumber sequence);
194 // Return a key suitable for lookup in a MemTable.
195 Slice memtable_key() const { return Slice(start_, end_ - start_); }
197 // Return an internal key (suitable for passing to an internal iterator)
198 Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
200 // Return the user key
201 Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
204 // We construct a char array of the form:
205 // klength varint32 <-- start_
206 // userkey char[klength] <-- kstart_
209 // The array is a suitable MemTable key.
210 // The suffix starting with "userkey" can be used as an InternalKey.
214 char space_[200]; // Avoid allocation for short keys
216 // No copying allowed
217 LookupKey(const LookupKey&);
218 void operator=(const LookupKey&);
221 inline LookupKey::~LookupKey() {
222 if (start_ != space_) delete[] start_;
225 } // namespace leveldb
227 #endif // STORAGE_LEVELDB_DB_FORMAT_H_