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 27 namespace leveldb {
28 29 namespace log {
30 class Writer;
31 }
32 33 class Compaction;
34 class Iterator;
35 class MemTable;
36 class TableBuilder;
37 class TableCache;
38 class Version;
39 class VersionSet;
40 class 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.
45 int 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.
54 bool 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 60 class 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 167 class 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 251 // Returns true iff some level needs a compaction.
252 bool NeedsCompaction() const {
253 Version* v = current_;
254 return (v->compaction_score_ >= 1) || (v->file_to_compact_ != nullptr);
255 }
256 257 // Add all files listed in any live version to *live.
258 // May also mutate some internal state.
259 void AddLiveFiles(std::set<uint64_t>* live);
260 261 // Return the approximate offset in the database of the data for
262 // "key" as of version "v".
263 uint64_t ApproximateOffsetOf(Version* v, const InternalKey& key);
264 265 // Return a human-readable short (single-line) summary of the number
266 // of files per level. Uses *scratch as backing store.
267 struct LevelSummaryStorage {
268 char buffer[100];
269 };
270 const char* LevelSummary(LevelSummaryStorage* scratch) const;
271 272 private:
273 class Builder;
274 275 friend class Compaction;
276 friend class Version;
277 278 bool ReuseManifest(const std::string& dscname, const std::string& dscbase);
279 280 void Finalize(Version* v);
281 282 void GetRange(const std::vector<FileMetaData*>& inputs, InternalKey* smallest,
283 InternalKey* largest);
284 285 void GetRange2(const std::vector<FileMetaData*>& inputs1,
286 const std::vector<FileMetaData*>& inputs2,
287 InternalKey* smallest, InternalKey* largest);
288 289 void SetupOtherInputs(Compaction* c);
290 291 // Save current contents to *log
292 Status WriteSnapshot(log::Writer* log);
293 294 void AppendVersion(Version* v);
295 296 Env* const env_;
297 const std::string dbname_;
298 const Options* const options_;
299 TableCache* const table_cache_;
300 const InternalKeyComparator icmp_;
301 uint64_t next_file_number_;
302 uint64_t manifest_file_number_;
303 uint64_t last_sequence_;
304 uint64_t log_number_;
305 uint64_t prev_log_number_; // 0 or backing store for memtable being compacted
306 307 // Opened lazily
308 WritableFile* descriptor_file_;
309 log::Writer* descriptor_log_;
310 Version dummy_versions_; // Head of circular doubly-linked list of versions.
311 Version* current_; // == dummy_versions_.prev_
312 313 // Per-level key at which the next compaction at that level should start.
314 // Either an empty string, or a valid InternalKey.
315 std::string compact_pointer_[config::kNumLevels];
316 };
317 318 // A Compaction encapsulates information about a compaction.
319 class Compaction {
320 public:
321 ~Compaction();
322 323 // Return the level that is being compacted. Inputs from "level"
324 // and "level+1" will be merged to produce a set of "level+1" files.
325 int level() const { return level_; }
326 327 // Return the object that holds the edits to the descriptor done
328 // by this compaction.
329 VersionEdit* edit() { return &edit_; }
330 331 // "which" must be either 0 or 1
332 int num_input_files(int which) const { return inputs_[which].size(); }
333 334 // Return the ith input file at "level()+which" ("which" must be 0 or 1).
335 FileMetaData* input(int which, int i) const { return inputs_[which][i]; }
336 337 // Maximum size of files to build during this compaction.
338 uint64_t MaxOutputFileSize() const { return max_output_file_size_; }
339 340 // Is this a trivial compaction that can be implemented by just
341 // moving a single input file to the next level (no merging or splitting)
342 bool IsTrivialMove() const;
343 344 // Add all inputs to this compaction as delete operations to *edit.
345 void AddInputDeletions(VersionEdit* edit);
346 347 // Returns true if the information we have available guarantees that
348 // the compaction is producing data in "level+1" for which no data exists
349 // in levels greater than "level+1".
350 bool IsBaseLevelForKey(const Slice& user_key);
351 352 // Returns true iff we should stop building the current output
353 // before processing "internal_key".
354 bool ShouldStopBefore(const Slice& internal_key);
355 356 // Release the input version for the compaction, once the compaction
357 // is successful.
358 void ReleaseInputs();
359 360 private:
361 friend class Version;
362 friend class VersionSet;
363 364 Compaction(const Options* options, int level);
365 366 int level_;
367 uint64_t max_output_file_size_;
368 Version* input_version_;
369 VersionEdit edit_;
370 371 // Each compaction reads inputs from "level_" and "level_+1"
372 std::vector<FileMetaData*> inputs_[2]; // The two sets of inputs
373 374 // State used to check for number of overlapping grandparent files
375 // (parent == level_ + 1, grandparent == level_ + 2)
376 std::vector<FileMetaData*> grandparents_;
377 size_t grandparent_index_; // Index in grandparent_starts_
378 bool seen_key_; // Some output key has been seen
379 int64_t overlapped_bytes_; // Bytes of overlap between current output
380 // and grandparent files
381 382 // State for implementing IsBaseLevelForKey
383 384 // level_ptrs_ holds indices into input_version_->levels_: our state
385 // is that we are positioned at one of the file ranges for each
386 // higher level than the ones involved in this compaction (i.e. for
387 // all L >= level_ + 2).
388 size_t level_ptrs_[config::kNumLevels];
389 };
390 391 } // namespace leveldb
392 393 #endif // STORAGE_LEVELDB_DB_VERSION_SET_H_
394