Inside Bitcoin

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// The representation of a DBImpl consists of a set of Versions.  The
6// newest version is called "current".  Older versions may be kept
7// around to provide a consistent view to live iterators.
8//
9// Each Version keeps track of a set of Table files per level.  The
10// entire set of versions is maintained in a VersionSet.
11//
12// Version,VersionSet are thread-compatible, but require external
13// synchronization on all accesses.
14
15#ifndef STORAGE_LEVELDB_DB_VERSION_SET_H_
16#define STORAGE_LEVELDB_DB_VERSION_SET_H_
17
18#include <map>
19#include <set>
20#include <vector>
21
22#include "db/dbformat.h"
23#include "db/version_edit.h"
24#include "port/port.h"
25#include "port/thread_annotations.h"
26
27namespace leveldb {
28
29namespace log {
30class Writer;
31}
32
33class Compaction;
34class Iterator;
35class MemTable;
36class TableBuilder;
37class TableCache;
38class Version;
39class VersionSet;
40class WritableFile;
41
42// Return the smallest index i such that files[i]->largest >= key.
43// Return files.size() if there is no such file.
44// REQUIRES: "files" contains a sorted list of non-overlapping files.
45int FindFile(const InternalKeyComparator& icmp,
46             const std::vector<FileMetaData*>& files, const Slice& key);
47
48// Returns true iff some file in "files" overlaps the user key range
49// [*smallest,*largest].
50// smallest==nullptr represents a key smaller than all keys in the DB.
51// largest==nullptr represents a key largest than all keys in the DB.
52// REQUIRES: If disjoint_sorted_files, files[] contains disjoint ranges
53//           in sorted order.
54bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
55                           bool disjoint_sorted_files,
56                           const std::vector<FileMetaData*>& files,
57                           const Slice* smallest_user_key,
58                           const Slice* largest_user_key);
59
60class Version {
61 public:
62  // Lookup the value for key.  If found, store it in *val and
63  // return OK.  Else return a non-OK status.  Fills *stats.
64  // REQUIRES: lock is not held
65  struct GetStats {
66    FileMetaData* seek_file;
67    int seek_file_level;
68  };
69
70  // Append to *iters a sequence of iterators that will
71  // yield the contents of this Version when merged together.
72  // REQUIRES: This version has been saved (see VersionSet::SaveTo)
73  void AddIterators(const ReadOptions&, std::vector<Iterator*>* iters);
74
75  Status Get(const ReadOptions&, const LookupKey& key, std::string* val,
76             GetStats* stats);
77
78  // Adds "stats" into the current state.  Returns true if a new
79  // compaction may need to be triggered, false otherwise.
80  // REQUIRES: lock is held
81  bool UpdateStats(const GetStats& stats);
82
83  // Record a sample of bytes read at the specified internal key.
84  // Samples are taken approximately once every config::kReadBytesPeriod
85  // bytes.  Returns true if a new compaction may need to be triggered.
86  // REQUIRES: lock is held
87  bool RecordReadSample(Slice key);
88
89  // Reference count management (so Versions do not disappear out from
90  // under live iterators)
91  void Ref();
92  void Unref();
93
94  void GetOverlappingInputs(
95      int level,
96      const InternalKey* begin,  // nullptr means before all keys
97      const InternalKey* end,    // nullptr means after all keys
98      std::vector<FileMetaData*>* inputs);
99
100  // Returns true iff some file in the specified level overlaps
101  // some part of [*smallest_user_key,*largest_user_key].
102  // smallest_user_key==nullptr represents a key smaller than all the DB's keys.
103  // largest_user_key==nullptr represents a key largest than all the DB's keys.
104  bool OverlapInLevel(int level, const Slice* smallest_user_key,
105                      const Slice* largest_user_key);
106
107  // Return the level at which we should place a new memtable compaction
108  // result that covers the range [smallest_user_key,largest_user_key].
109  int PickLevelForMemTableOutput(const Slice& smallest_user_key,
110                                 const Slice& largest_user_key);
111
112  int NumFiles(int level) const { return files_[level].size(); }
113
114  // Return a human readable string that describes this version's contents.
115  std::string DebugString() const;
116
117 private:
118  friend class Compaction;
119  friend class VersionSet;
120
121  class LevelFileNumIterator;
122
123  explicit Version(VersionSet* vset)
124      : vset_(vset),
125        next_(this),
126        prev_(this),
127        refs_(0),
128        file_to_compact_(nullptr),
129        file_to_compact_level_(-1),
130        compaction_score_(-1),
131        compaction_level_(-1) {}
132
133  Version(const Version&) = delete;
134  Version& operator=(const Version&) = delete;
135
136  ~Version();
137
138  Iterator* NewConcatenatingIterator(const ReadOptions&, int level) const;
139
140  // Call func(arg, level, f) for every file that overlaps user_key in
141  // order from newest to oldest.  If an invocation of func returns
142  // false, makes no more calls.
143  //
144  // REQUIRES: user portion of internal_key == user_key.
145  void ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
146                          bool (*func)(void*, int, FileMetaData*));
147
148  VersionSet* vset_;  // VersionSet to which this Version belongs
149  Version* next_;     // Next version in linked list
150  Version* prev_;     // Previous version in linked list
151  int refs_;          // Number of live refs to this version
152
153  // List of files per level
154  std::vector<FileMetaData*> files_[config::kNumLevels];
155
156  // Next file to compact based on seek stats.
157  FileMetaData* file_to_compact_;
158  int file_to_compact_level_;
159
160  // Level that should be compacted next and its compaction score.
161  // Score < 1 means compaction is not strictly needed.  These fields
162  // are initialized by Finalize().
163  double compaction_score_;
164  int compaction_level_;
165};
166
167class VersionSet {
168 public:
169  VersionSet(const std::string& dbname, const Options* options,
170             TableCache* table_cache, const InternalKeyComparator*);
171  VersionSet(const VersionSet&) = delete;
172  VersionSet& operator=(const VersionSet&) = delete;
173
174  ~VersionSet();
175
176  // Apply *edit to the current version to form a new descriptor that
177  // is both saved to persistent state and installed as the new
178  // current version.  Will release *mu while actually writing to the file.
179  // REQUIRES: *mu is held on entry.
180  // REQUIRES: no other thread concurrently calls LogAndApply()
181  Status LogAndApply(VersionEdit* edit, port::Mutex* mu)
182      EXCLUSIVE_LOCKS_REQUIRED(mu);
183
184  // Recover the last saved descriptor from persistent storage.
185  Status Recover(bool* save_manifest);
186
187  // Return the current version.
188  Version* current() const { return current_; }
189
190  // Return the current manifest file number
191  uint64_t ManifestFileNumber() const { return manifest_file_number_; }
192
193  // Allocate and return a new file number
194  uint64_t NewFileNumber() { return next_file_number_++; }
195
196  // Arrange to reuse "file_number" unless a newer file number has
197  // already been allocated.
198  // REQUIRES: "file_number" was returned by a call to NewFileNumber().
199  void ReuseFileNumber(uint64_t file_number) {
200    if (next_file_number_ == file_number + 1) {
201      next_file_number_ = file_number;
202    }
203  }
204
205  // Return the number of Table files at the specified level.
206  int NumLevelFiles(int level) const;
207
208  // Return the combined file size of all files at the specified level.
209  int64_t NumLevelBytes(int level) const;
210
211  // Return the last sequence number.
212  uint64_t LastSequence() const { return last_sequence_; }
213
214  // Set the last sequence number to s.
215  void SetLastSequence(uint64_t s) {
216    assert(s >= last_sequence_);
217    last_sequence_ = s;
218  }
219
220  // Mark the specified file number as used.
221  void MarkFileNumberUsed(uint64_t number);
222
223  // Return the current log file number.
224  uint64_t LogNumber() const { return log_number_; }
225
226  // Return the log file number for the log file that is currently
227  // being compacted, or zero if there is no such log file.
228  uint64_t PrevLogNumber() const { return prev_log_number_; }
229
230  // Pick level and inputs for a new compaction.
231  // Returns nullptr if there is no compaction to be done.
232  // Otherwise returns a pointer to a heap-allocated object that
233  // describes the compaction.  Caller should delete the result.
234  Compaction* PickCompaction();
235
236  // Return a compaction object for compacting the range [begin,end] in
237  // the specified level.  Returns nullptr if there is nothing in that
238  // level that overlaps the specified range.  Caller should delete
239  // the result.
240  Compaction* CompactRange(int level, const InternalKey* begin,
241                           const InternalKey* end);
242
243  // Return the maximum overlapping data (in bytes) at next level for any
244  // file at a level >= 1.
245  int64_t MaxNextLevelOverlappingBytes();
246
247  // Create an iterator that reads over the compaction inputs for "*c".
248  // The caller should delete the iterator when no longer needed.
249  Iterator* MakeInputIterator(Compaction* c);
250