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 : 209470 : ParsedInternalKey() {} // Intentionally left uninitialized (for speed)
# 75 : : ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)
# 76 : 2950 : : user_key(u), sequence(seq), type(t) {}
# 77 : : std::string DebugString() const;
# 78 : : };
# 79 : :
# 80 : : // Return the length of the encoding of "key".
# 81 : 0 : inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) {
# 82 : 0 : return key.user_key.size() + 8;
# 83 : 0 : }
# 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 : 523197191 : inline Slice ExtractUserKey(const Slice& internal_key) {
# 96 : 523197191 : assert(internal_key.size() >= 8);
# 97 : 0 : return Slice(internal_key.data(), internal_key.size() - 8);
# 98 : 523197191 : }
# 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 : 2193 : 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 : 28666788 : 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 : 2193 : 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 : 16833 : InternalKey() {} // Leave rep_ as empty to indicate it is invalid
# 140 : 66 : InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {
# 141 : 66 : AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));
# 142 : 66 : }
# 143 : :
# 144 : 200425 : bool DecodeFrom(const Slice& s) {
# 145 : 200425 : rep_.assign(s.data(), s.size());
# 146 : 200425 : return !rep_.empty();
# 147 : 200425 : }
# 148 : :
# 149 : 3260268 : Slice Encode() const {
# 150 : 3260268 : assert(!rep_.empty());
# 151 : 0 : return rep_;
# 152 : 3260268 : }
# 153 : :
# 154 : 3535638 : Slice user_key() const { return ExtractUserKey(rep_); }
# 155 : :
# 156 : 0 : void SetFrom(const ParsedInternalKey& p) {
# 157 : 0 : rep_.clear();
# 158 : 0 : AppendInternalKey(&rep_, p);
# 159 : 0 : }
# 160 : :
# 161 : 864 : void Clear() { rep_.clear(); }
# 162 : :
# 163 : : std::string DebugString() const;
# 164 : : };
# 165 : :
# 166 : : inline int InternalKeyComparator::Compare(const InternalKey& a,
# 167 : 3869 : const InternalKey& b) const {
# 168 : 3869 : return Compare(a.Encode(), b.Encode());
# 169 : 3869 : }
# 170 : :
# 171 : : inline bool ParseInternalKey(const Slice& internal_key,
# 172 : 244712 : ParsedInternalKey* result) {
# 173 : 244712 : const size_t n = internal_key.size();
# 174 [ - + ]: 244712 : if (n < 8) return false;
# 175 : 244712 : uint64_t num = DecodeFixed64(internal_key.data() + n - 8);
# 176 : 244712 : uint8_t c = num & 0xff;
# 177 : 244712 : result->sequence = num >> 8;
# 178 : 244712 : result->type = static_cast<ValueType>(c);
# 179 : 244712 : result->user_key = Slice(internal_key.data(), n - 8);
# 180 : 244712 : return (c <= static_cast<uint8_t>(kTypeValue));
# 181 : 244712 : }
# 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 : 10091933 : Slice memtable_key() const { return Slice(start_, end_ - start_); }
# 197 : :
# 198 : : // Return an internal key (suitable for passing to an internal iterator)
# 199 : 9723156 : Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }
# 200 : :
# 201 : : // Return the user key
# 202 : 18898386 : 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 : 10083933 : inline LookupKey::~LookupKey() {
# 219 [ - + ]: 10083933 : if (start_ != space_) delete[] start_;
# 220 : 10083933 : }
# 221 : :
# 222 : : } // namespace leveldb
# 223 : :
# 224 : : #endif // STORAGE_LEVELDB_DB_DBFORMAT_H_
|
