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/slice.h"
12
#include "leveldb/table_builder.h"
13
#include "util/coding.h"
14
#include "util/logging.h"
18
// Grouping of constants. We may want to make some of these
19
// parameters set via options.
21
static const int kNumLevels = 7;
23
// Level-0 compaction is started when we hit this many files.
24
static const int kL0_CompactionTrigger = 4;
26
// Soft limit on number of level-0 files. We slow down writes at this point.
27
static const int kL0_SlowdownWritesTrigger = 8;
29
// Maximum number of level-0 files. We stop writes at this point.
30
static const int kL0_StopWritesTrigger = 12;
32
// Maximum level to which a new compacted memtable is pushed if it
33
// does not create overlap. We try to push to level 2 to avoid the
34
// relatively expensive level 0=>1 compactions and to avoid some
35
// expensive manifest file operations. We do not push all the way to
36
// the largest level since that can generate a lot of wasted disk
37
// space if the same key space is being repeatedly overwritten.
38
static const int kMaxMemCompactLevel = 2;
44
// Value types encoded as the last component of internal keys.
45
// DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk
51
// kValueTypeForSeek defines the ValueType that should be passed when
52
// constructing a ParsedInternalKey object for seeking to a particular
53
// sequence number (since we sort sequence numbers in decreasing order
54
// and the value type is embedded as the low 8 bits in the sequence
55
// number in internal keys, we need to use the highest-numbered
56
// ValueType, not the lowest).
57
static const ValueType kValueTypeForSeek = kTypeValue;
59
typedef uint64_t SequenceNumber;
61
// We leave eight bits empty at the bottom so a type and sequence#
62
// can be packed together into 64-bits.
63
static const SequenceNumber kMaxSequenceNumber =
66
struct ParsedInternalKey {
68
SequenceNumber sequence;
71
ParsedInternalKey() { } // Intentionally left uninitialized (for speed)
72
ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
73
: user_key(u), sequence(seq), type(t) { }
74
std::string DebugString() const;
77
// Return the length of the encoding of "key".
78
inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) {
79
return key.user_key.size() + 8;
82
// Append the serialization of "key" to *result.
83
extern void AppendInternalKey(std::string* result,
84
const ParsedInternalKey& key);
86
// Attempt to parse an internal key from "internal_key". On success,
87
// stores the parsed data in "*result", and returns true.
89
// On error, returns false, leaves "*result" in an undefined state.
90
extern bool ParseInternalKey(const Slice& internal_key,
91
ParsedInternalKey* result);
93
// Returns the user key portion of an internal key.
94
inline Slice ExtractUserKey(const Slice& internal_key) {
95
assert(internal_key.size() >= 8);
96
return Slice(internal_key.data(), internal_key.size() - 8);
99
inline ValueType ExtractValueType(const Slice& internal_key) {
100
assert(internal_key.size() >= 8);
101
const size_t n = internal_key.size();
102
uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
103
unsigned char c = num & 0xff;
104
return static_cast<ValueType>(c);
107
// A comparator for internal keys that uses a specified comparator for
108
// the user key portion and breaks ties by decreasing sequence number.
109
class InternalKeyComparator : public Comparator {
111
const Comparator* user_comparator_;
113
explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { }
114
virtual const char* Name() const;
115
virtual int Compare(const Slice& a, const Slice& b) const;
116
virtual void FindShortestSeparator(
118
const Slice& limit) const;
119
virtual void FindShortSuccessor(std::string* key) const;
121
const Comparator* user_comparator() const { return user_comparator_; }
123
int Compare(const InternalKey& a, const InternalKey& b) const;
126
// Modules in this directory should keep internal keys wrapped inside
127
// the following class instead of plain strings so that we do not
128
// incorrectly use string comparisons instead of an InternalKeyComparator.
133
InternalKey() { } // Leave rep_ as empty to indicate it is invalid
134
InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
135
AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
138
void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); }
139
Slice Encode() const {
140
assert(!rep_.empty());
144
Slice user_key() const { return ExtractUserKey(rep_); }
146
void SetFrom(const ParsedInternalKey& p) {
148
AppendInternalKey(&rep_, p);
151
void Clear() { rep_.clear(); }
153
std::string DebugString() const;
156
inline int InternalKeyComparator::Compare(
157
const InternalKey& a, const InternalKey& b) const {
158
return Compare(a.Encode(), b.Encode());
161
inline bool ParseInternalKey(const Slice& internal_key,
162
ParsedInternalKey* result) {
163
const size_t n = internal_key.size();
164
if (n < 8) return false;
165
uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
166
unsigned char c = num & 0xff;
167
result->sequence = num >> 8;
168
result->type = static_cast<ValueType>(c);
169
result->user_key = Slice(internal_key.data(), n - 8);
170
return (c <= static_cast<unsigned char>(kTypeValue));
173
// A helper class useful for DBImpl::Get()
176
// Initialize *this for looking up user_key at a snapshot with
177
// the specified sequence number.
178
LookupKey(const Slice& user_key, SequenceNumber sequence);
182
// Return a key suitable for lookup in a MemTable.
183
Slice memtable_key() const { return Slice(start_, end_ - start_); }
185
// Return an internal key (suitable for passing to an internal iterator)
186
Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
188
// Return the user key
189
Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
192
// We construct a char array of the form:
193
// klength varint32 <-- start_
194
// userkey char[klength] <-- kstart_
197
// The array is a suitable MemTable key.
198
// The suffix starting with "userkey" can be used as an InternalKey.
202
char space_[200]; // Avoid allocation for short keys
204
// No copying allowed
205
LookupKey(const LookupKey&);
206
void operator=(const LookupKey&);
209
inline LookupKey::~LookupKey() {
210
if (start_ != space_) delete[] start_;
213
} // namespace leveldb
215
#endif // STORAGE_LEVELDB_DB_FORMAT_H_
added
removed
src/leveldb/db/dbformat.h
