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 // 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.
9 // Each Version keeps track of a set of Table files per level. The
10 // entire set of versions is maintained in a VersionSet.
12 // Version,VersionSet are thread-compatible, but require external
13 // synchronization on all accesses.
15 #ifndef STORAGE_LEVELDB_DB_VERSION_SET_H_
16 #define STORAGE_LEVELDB_DB_VERSION_SET_H_
21 #include "db/dbformat.h"
22 #include "db/version_edit.h"
23 #include "port/port.h"
24 #include "port/thread_annotations.h"
28 namespace log { class Writer; }
39 // Return the smallest index i such that files[i]->largest >= key.
40 // Return files.size() if there is no such file.
41 // REQUIRES: "files" contains a sorted list of non-overlapping files.
42 extern int FindFile(const InternalKeyComparator& icmp,
43 const std::vector<FileMetaData*>& files,
46 // Returns true iff some file in "files" overlaps the user key range
47 // [*smallest,*largest].
48 // smallest==NULL represents a key smaller than all keys in the DB.
49 // largest==NULL represents a key largest than all keys in the DB.
50 // REQUIRES: If disjoint_sorted_files, files[] contains disjoint ranges
52 extern bool SomeFileOverlapsRange(
53 const InternalKeyComparator& icmp,
54 bool disjoint_sorted_files,
55 const std::vector<FileMetaData*>& files,
56 const Slice* smallest_user_key,
57 const Slice* largest_user_key);
61 // Append to *iters a sequence of iterators that will
62 // yield the contents of this Version when merged together.
63 // REQUIRES: This version has been saved (see VersionSet::SaveTo)
64 void AddIterators(const ReadOptions&, std::vector<Iterator*>* iters);
66 // Lookup the value for key. If found, store it in *val and
67 // return OK. Else return a non-OK status. Fills *stats.
68 // REQUIRES: lock is not held
70 FileMetaData* seek_file;
73 Status Get(const ReadOptions&, const LookupKey& key, std::string* val,
76 // Adds "stats" into the current state. Returns true if a new
77 // compaction may need to be triggered, false otherwise.
78 // REQUIRES: lock is held
79 bool UpdateStats(const GetStats& stats);
81 // Reference count management (so Versions do not disappear out from
82 // under live iterators)
86 void GetOverlappingInputs(
88 const InternalKey* begin, // NULL means before all keys
89 const InternalKey* end, // NULL means after all keys
90 std::vector<FileMetaData*>* inputs);
92 // Returns true iff some file in the specified level overlaps
93 // some part of [*smallest_user_key,*largest_user_key].
94 // smallest_user_key==NULL represents a key smaller than all keys in the DB.
95 // largest_user_key==NULL represents a key largest than all keys in the DB.
96 bool OverlapInLevel(int level,
97 const Slice* smallest_user_key,
98 const Slice* largest_user_key);
100 // Return the level at which we should place a new memtable compaction
101 // result that covers the range [smallest_user_key,largest_user_key].
102 int PickLevelForMemTableOutput(const Slice& smallest_user_key,
103 const Slice& largest_user_key);
105 int NumFiles(int level) const { return files_[level].size(); }
107 // Return a human readable string that describes this version's contents.
108 std::string DebugString() const;
111 friend class Compaction;
112 friend class VersionSet;
114 class LevelFileNumIterator;
115 Iterator* NewConcatenatingIterator(const ReadOptions&, int level) const;
117 VersionSet* vset_; // VersionSet to which this Version belongs
118 Version* next_; // Next version in linked list
119 Version* prev_; // Previous version in linked list
120 int refs_; // Number of live refs to this version
122 // List of files per level
123 std::vector<FileMetaData*> files_[config::kNumLevels];
125 // Next file to compact based on seek stats.
126 FileMetaData* file_to_compact_;
127 int file_to_compact_level_;
129 // Level that should be compacted next and its compaction score.
130 // Score < 1 means compaction is not strictly needed. These fields
131 // are initialized by Finalize().
132 double compaction_score_;
133 int compaction_level_;
135 explicit Version(VersionSet* vset)
136 : vset_(vset), next_(this), prev_(this), refs_(0),
137 file_to_compact_(NULL),
138 file_to_compact_level_(-1),
139 compaction_score_(-1),
140 compaction_level_(-1) {
145 // No copying allowed
146 Version(const Version&);
147 void operator=(const Version&);
152 VersionSet(const std::string& dbname,
153 const Options* options,
154 TableCache* table_cache,
155 const InternalKeyComparator*);
158 // Apply *edit to the current version to form a new descriptor that
159 // is both saved to persistent state and installed as the new
160 // current version. Will release *mu while actually writing to the file.
161 // REQUIRES: *mu is held on entry.
162 // REQUIRES: no other thread concurrently calls LogAndApply()
163 Status LogAndApply(VersionEdit* edit, port::Mutex* mu)
164 EXCLUSIVE_LOCKS_REQUIRED(mu);
166 // Recover the last saved descriptor from persistent storage.
169 // Return the current version.
170 Version* current() const { return current_; }
172 // Return the current manifest file number
173 uint64_t ManifestFileNumber() const { return manifest_file_number_; }
175 // Allocate and return a new file number
176 uint64_t NewFileNumber() { return next_file_number_++; }
178 // Arrange to reuse "file_number" unless a newer file number has
179 // already been allocated.
180 // REQUIRES: "file_number" was returned by a call to NewFileNumber().
181 void ReuseFileNumber(uint64_t file_number) {
182 if (next_file_number_ == file_number + 1) {
183 next_file_number_ = file_number;
187 // Return the number of Table files at the specified level.
188 int NumLevelFiles(int level) const;
190 // Return the combined file size of all files at the specified level.
191 int64_t NumLevelBytes(int level) const;
193 // Return the last sequence number.
194 uint64_t LastSequence() const { return last_sequence_; }
196 // Set the last sequence number to s.
197 void SetLastSequence(uint64_t s) {
198 assert(s >= last_sequence_);
202 // Mark the specified file number as used.
203 void MarkFileNumberUsed(uint64_t number);
205 // Return the current log file number.
206 uint64_t LogNumber() const { return log_number_; }
208 // Return the log file number for the log file that is currently
209 // being compacted, or zero if there is no such log file.
210 uint64_t PrevLogNumber() const { return prev_log_number_; }
212 // Pick level and inputs for a new compaction.
213 // Returns NULL if there is no compaction to be done.
214 // Otherwise returns a pointer to a heap-allocated object that
215 // describes the compaction. Caller should delete the result.
216 Compaction* PickCompaction();
218 // Return a compaction object for compacting the range [begin,end] in
219 // the specified level. Returns NULL if there is nothing in that
220 // level that overlaps the specified range. Caller should delete
222 Compaction* CompactRange(
224 const InternalKey* begin,
225 const InternalKey* end);
227 // Return the maximum overlapping data (in bytes) at next level for any
228 // file at a level >= 1.
229 int64_t MaxNextLevelOverlappingBytes();
231 // Create an iterator that reads over the compaction inputs for "*c".
232 // The caller should delete the iterator when no longer needed.
233 Iterator* MakeInputIterator(Compaction* c);
235 // Returns true iff some level needs a compaction.
236 bool NeedsCompaction() const {
237 Version* v = current_;
238 return (v->compaction_score_ >= 1) || (v->file_to_compact_ != NULL);
241 // Add all files listed in any live version to *live.
242 // May also mutate some internal state.
243 void AddLiveFiles(std::set<uint64_t>* live);
245 // Return the approximate offset in the database of the data for
246 // "key" as of version "v".
247 uint64_t ApproximateOffsetOf(Version* v, const InternalKey& key);
249 // Return a human-readable short (single-line) summary of the number
250 // of files per level. Uses *scratch as backing store.
251 struct LevelSummaryStorage {
254 const char* LevelSummary(LevelSummaryStorage* scratch) const;
259 friend class Compaction;
260 friend class Version;
262 void Finalize(Version* v);
264 void GetRange(const std::vector<FileMetaData*>& inputs,
265 InternalKey* smallest,
266 InternalKey* largest);
268 void GetRange2(const std::vector<FileMetaData*>& inputs1,
269 const std::vector<FileMetaData*>& inputs2,
270 InternalKey* smallest,
271 InternalKey* largest);
273 void SetupOtherInputs(Compaction* c);
275 // Save current contents to *log
276 Status WriteSnapshot(log::Writer* log);
278 void AppendVersion(Version* v);
280 bool ManifestContains(const std::string& record) const;
283 const std::string dbname_;
284 const Options* const options_;
285 TableCache* const table_cache_;
286 const InternalKeyComparator icmp_;
287 uint64_t next_file_number_;
288 uint64_t manifest_file_number_;
289 uint64_t last_sequence_;
290 uint64_t log_number_;
291 uint64_t prev_log_number_; // 0 or backing store for memtable being compacted
294 WritableFile* descriptor_file_;
295 log::Writer* descriptor_log_;
296 Version dummy_versions_; // Head of circular doubly-linked list of versions.
297 Version* current_; // == dummy_versions_.prev_
299 // Per-level key at which the next compaction at that level should start.
300 // Either an empty string, or a valid InternalKey.
301 std::string compact_pointer_[config::kNumLevels];
303 // No copying allowed
304 VersionSet(const VersionSet&);
305 void operator=(const VersionSet&);
308 // A Compaction encapsulates information about a compaction.
313 // Return the level that is being compacted. Inputs from "level"
314 // and "level+1" will be merged to produce a set of "level+1" files.
315 int level() const { return level_; }
317 // Return the object that holds the edits to the descriptor done
318 // by this compaction.
319 VersionEdit* edit() { return &edit_; }
321 // "which" must be either 0 or 1
322 int num_input_files(int which) const { return inputs_[which].size(); }
324 // Return the ith input file at "level()+which" ("which" must be 0 or 1).
325 FileMetaData* input(int which, int i) const { return inputs_[which][i]; }
327 // Maximum size of files to build during this compaction.
328 uint64_t MaxOutputFileSize() const { return max_output_file_size_; }
330 // Is this a trivial compaction that can be implemented by just
331 // moving a single input file to the next level (no merging or splitting)
332 bool IsTrivialMove() const;
334 // Add all inputs to this compaction as delete operations to *edit.
335 void AddInputDeletions(VersionEdit* edit);
337 // Returns true if the information we have available guarantees that
338 // the compaction is producing data in "level+1" for which no data exists
339 // in levels greater than "level+1".
340 bool IsBaseLevelForKey(const Slice& user_key);
342 // Returns true iff we should stop building the current output
343 // before processing "internal_key".
344 bool ShouldStopBefore(const Slice& internal_key);
346 // Release the input version for the compaction, once the compaction
348 void ReleaseInputs();
351 friend class Version;
352 friend class VersionSet;
354 explicit Compaction(int level);
357 uint64_t max_output_file_size_;
358 Version* input_version_;
361 // Each compaction reads inputs from "level_" and "level_+1"
362 std::vector<FileMetaData*> inputs_[2]; // The two sets of inputs
364 // State used to check for number of of overlapping grandparent files
365 // (parent == level_ + 1, grandparent == level_ + 2)
366 std::vector<FileMetaData*> grandparents_;
367 size_t grandparent_index_; // Index in grandparent_starts_
368 bool seen_key_; // Some output key has been seen
369 int64_t overlapped_bytes_; // Bytes of overlap between current output
370 // and grandparent files
372 // State for implementing IsBaseLevelForKey
374 // level_ptrs_ holds indices into input_version_->levels_: our state
375 // is that we are positioned at one of the file ranges for each
376 // higher level than the ones involved in this compaction (i.e. for
377 // all L >= level_ + 2).
378 size_t level_ptrs_[config::kNumLevels];
381 } // namespace leveldb
383 #endif // STORAGE_LEVELDB_DB_VERSION_SET_H_