1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/version_set.h" 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <algorithm> 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <stdio.h> 9179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/filename.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/log_reader.h" 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/log_writer.h" 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/memtable.h" 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/table_cache.h" 14fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/env.h" 15fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/table_builder.h" 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/merger.h" 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/two_level_iterator.h" 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/coding.h" 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/logging.h" 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 2307f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.orgstatic const int kTargetFileSize = 2 * 1048576; 2407f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org 2507f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org// Maximum bytes of overlaps in grandparent (i.e., level+2) before we 26b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org// stop building a single file in a level->level+1 compaction. 2707f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.orgstatic const int64_t kMaxGrandParentOverlapBytes = 10 * kTargetFileSize; 28b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 2956addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com// Maximum number of bytes in all compacted files. We avoid expanding 3056addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com// the lower level file set of a compaction if it would make the 3156addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com// total compaction cover more than this many bytes. 3256addd362f70667d374aaa686f90eeae5c23d486sanjay@google.comstatic const int64_t kExpandedCompactionByteSizeLimit = 25 * kTargetFileSize; 3356addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic double MaxBytesForLevel(int level) { 3595e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // Note: the result for level zero is not really used since we set 3695e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // the level-0 compaction threshold based on number of files. 3795e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org double result = 10 * 1048576.0; // Result for both level-0 and level-1 3895e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org while (level > 1) { 3995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org result *= 10; 4095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org level--; 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 4295e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org return result; 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic uint64_t MaxFileSizeForLevel(int level) { 4607f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org return kTargetFileSize; // We could vary per level to reduce number of files? 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 495fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.comstatic int64_t TotalFileSize(const std::vector<FileMetaData*>& files) { 505fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com int64_t sum = 0; 515fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com for (size_t i = 0; i < files.size(); i++) { 525fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com sum += files[i]->file_size; 535fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 545fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return sum; 555fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com} 565fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgVersion::~Version() { 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(refs_ == 0); 59a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 60a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Remove from linked list 61a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org prev_->next_ = next_; 62a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org next_->prev_ = prev_; 63a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 64a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Drop references to files 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 661511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < files_[level].size(); i++) { 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FileMetaData* f = files_[level][i]; 68a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(f->refs > 0); 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org f->refs--; 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (f->refs <= 0) { 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete f; 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 778cd4ab8303620197cf24282ae8639060efbb326egabor@google.comint FindFile(const InternalKeyComparator& icmp, 788cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const std::vector<FileMetaData*>& files, 798cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const Slice& key) { 808cd4ab8303620197cf24282ae8639060efbb326egabor@google.com uint32_t left = 0; 818cd4ab8303620197cf24282ae8639060efbb326egabor@google.com uint32_t right = files.size(); 828cd4ab8303620197cf24282ae8639060efbb326egabor@google.com while (left < right) { 838cd4ab8303620197cf24282ae8639060efbb326egabor@google.com uint32_t mid = (left + right) / 2; 848cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const FileMetaData* f = files[mid]; 858cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (icmp.InternalKeyComparator::Compare(f->largest.Encode(), key) < 0) { 868cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Key at "mid.largest" is < "target". Therefore all 878cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // files at or before "mid" are uninteresting. 888cd4ab8303620197cf24282ae8639060efbb326egabor@google.com left = mid + 1; 898cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } else { 908cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Key at "mid.largest" is >= "target". Therefore all files 918cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // after "mid" are uninteresting. 928cd4ab8303620197cf24282ae8639060efbb326egabor@google.com right = mid; 938cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 948cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 958cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return right; 968cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 978cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 985fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.comstatic bool AfterFile(const Comparator* ucmp, 995fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice* user_key, const FileMetaData* f) { 1005fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // NULL user_key occurs before all keys and is therefore never after *f 1015fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return (user_key != NULL && 1025fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com ucmp->Compare(*user_key, f->largest.user_key()) > 0); 1035fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com} 1045fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 1055fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.comstatic bool BeforeFile(const Comparator* ucmp, 1065fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice* user_key, const FileMetaData* f) { 1075fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // NULL user_key occurs after all keys and is therefore never before *f 1085fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return (user_key != NULL && 1095fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com ucmp->Compare(*user_key, f->smallest.user_key()) < 0); 1105fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com} 1115fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 1128cd4ab8303620197cf24282ae8639060efbb326egabor@google.combool SomeFileOverlapsRange( 1138cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const InternalKeyComparator& icmp, 1145fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com bool disjoint_sorted_files, 1158cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const std::vector<FileMetaData*>& files, 1165fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice* smallest_user_key, 1175fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice* largest_user_key) { 1185fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Comparator* ucmp = icmp.user_comparator(); 1195fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (!disjoint_sorted_files) { 1205fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // Need to check against all files 121158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.com for (size_t i = 0; i < files.size(); i++) { 1225fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const FileMetaData* f = files[i]; 1235fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (AfterFile(ucmp, smallest_user_key, f) || 1245fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com BeforeFile(ucmp, largest_user_key, f)) { 1255fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // No overlap 1265fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } else { 1275fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return true; // Overlap 1285fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 1295fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 1305fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return false; 1315fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 1325fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 1335fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // Binary search over file list 1345fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com uint32_t index = 0; 1355fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (smallest_user_key != NULL) { 1365fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // Find the earliest possible internal key for smallest_user_key 1375fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com InternalKey small(*smallest_user_key, kMaxSequenceNumber,kValueTypeForSeek); 1385fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com index = FindFile(icmp, files, small.Encode()); 1395fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 1405fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 1415fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (index >= files.size()) { 1425fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // beginning of range is after all files, so no overlap. 1435fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return false; 1445fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 1455fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 1465fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return !BeforeFile(ucmp, largest_user_key, files[index]); 1478cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 1488cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 149179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// An internal iterator. For a given version/level pair, yields 150179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// information about the files in the level. For a given entry, key() 151179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// is the largest key that occurs in the file, and value() is an 152f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org// 16-byte value containing the file number and file size, both 153f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org// encoded using EncodeFixed64. 154179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass Version::LevelFileNumIterator : public Iterator { 155179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 156a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org LevelFileNumIterator(const InternalKeyComparator& icmp, 157179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>* flist) 158a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org : icmp_(icmp), 159179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org flist_(flist), 160179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org index_(flist->size()) { // Marks as invalid 161179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 162179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual bool Valid() const { 163179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return index_ < flist_->size(); 164179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 165179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Seek(const Slice& target) { 1668cd4ab8303620197cf24282ae8639060efbb326egabor@google.com index_ = FindFile(icmp_, *flist_, target); 167179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 168179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void SeekToFirst() { index_ = 0; } 169179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void SeekToLast() { 170179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org index_ = flist_->empty() ? 0 : flist_->size() - 1; 171179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 172179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Next() { 173179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org index_++; 175179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 176179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Prev() { 177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (index_ == 0) { 179179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org index_ = flist_->size(); // Marks as invalid 180179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 181179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org index_--; 182179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 183179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 184179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice key() const { 185179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return (*flist_)[index_]->largest.Encode(); 187179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 188179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice value() const { 189179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Valid()); 190179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org EncodeFixed64(value_buf_, (*flist_)[index_]->number); 191f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org EncodeFixed64(value_buf_+8, (*flist_)[index_]->file_size); 192179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Slice(value_buf_, sizeof(value_buf_)); 193179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 194179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status status() const { return Status::OK(); } 195179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 196179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const InternalKeyComparator icmp_; 197179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>* const flist_; 1981511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org uint32_t index_; 199179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 200f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org // Backing store for value(). Holds the file number and size. 201f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org mutable char value_buf_[16]; 202179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 203179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 204179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic Iterator* GetFileIterator(void* arg, 205179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const ReadOptions& options, 206179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& file_value) { 207179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TableCache* cache = reinterpret_cast<TableCache*>(arg); 208f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org if (file_value.size() != 16) { 209179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return NewErrorIterator( 210179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status::Corruption("FileReader invoked with unexpected value")); 211179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 212f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org return cache->NewIterator(options, 213f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org DecodeFixed64(file_value.data()), 214f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org DecodeFixed64(file_value.data() + 8)); 215179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 216179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 217179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 218179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgIterator* Version::NewConcatenatingIterator(const ReadOptions& options, 219179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int level) const { 220179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return NewTwoLevelIterator( 221a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org new LevelFileNumIterator(vset_->icmp_, &files_[level]), 222179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org &GetFileIterator, vset_->table_cache_, options); 223179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 224179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 225179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid Version::AddIterators(const ReadOptions& options, 226179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<Iterator*>* iters) { 227179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Merge all level zero files together since they may overlap 2281511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < files_[0].size(); i++) { 229179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iters->push_back( 230f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org vset_->table_cache_->NewIterator( 231f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org options, files_[0][i]->number, files_[0][i]->file_size)); 232179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 233179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 234179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // For levels > 0, we can use a concatenating iterator that sequentially 235179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // walks through the non-overlapping files in the level, opening them 236179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // lazily. 237179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 1; level < config::kNumLevels; level++) { 238179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!files_[level].empty()) { 239179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iters->push_back(NewConcatenatingIterator(options, level)); 240179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 241179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 242179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 243179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 24499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// Callback from TableCache::Get() 24599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comnamespace { 24699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comenum SaverState { 24799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com kNotFound, 24899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com kFound, 24999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com kDeleted, 25099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com kCorrupt, 25199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com}; 25299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comstruct Saver { 25399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com SaverState state; 25499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const Comparator* ucmp; 25599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Slice user_key; 25699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::string* value; 25799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com}; 25899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 25999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comstatic void SaveValue(void* arg, const Slice& ikey, const Slice& v) { 26099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Saver* s = reinterpret_cast<Saver*>(arg); 2618cd4ab8303620197cf24282ae8639060efbb326egabor@google.com ParsedInternalKey parsed_key; 26299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (!ParseInternalKey(ikey, &parsed_key)) { 26399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s->state = kCorrupt; 26499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } else { 26599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (s->ucmp->Compare(parsed_key.user_key, s->user_key) == 0) { 26699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s->state = (parsed_key.type == kTypeValue) ? kFound : kDeleted; 26799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (s->state == kFound) { 26899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s->value->assign(v.data(), v.size()); 26999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 2708cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 2718cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 2728cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 2738cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 2748cd4ab8303620197cf24282ae8639060efbb326egabor@google.comstatic bool NewestFirst(FileMetaData* a, FileMetaData* b) { 2758cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return a->number > b->number; 2768cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 2778cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 27808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.orgvoid Version::ForEachOverlapping(Slice user_key, Slice internal_key, 27908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org void* arg, 28008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org bool (*func)(void*, int, FileMetaData*)) { 28108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // TODO(sanjay): Change Version::Get() to use this function. 28208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org const Comparator* ucmp = vset_->icmp_.user_comparator(); 28308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 28408595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // Search level-0 in order from newest to oldest. 28508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org std::vector<FileMetaData*> tmp; 28608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org tmp.reserve(files_[0].size()); 28708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org for (uint32_t i = 0; i < files_[0].size(); i++) { 28808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org FileMetaData* f = files_[0][i]; 28908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 && 29008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org ucmp->Compare(user_key, f->largest.user_key()) <= 0) { 29108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org tmp.push_back(f); 29208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 29308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 29408595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (!tmp.empty()) { 29508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org std::sort(tmp.begin(), tmp.end(), NewestFirst); 29608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org for (uint32_t i = 0; i < tmp.size(); i++) { 29708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (!(*func)(arg, 0, tmp[i])) { 29808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org return; 29908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 30008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 30108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 30208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 30308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // Search other levels. 30408595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org for (int level = 1; level < config::kNumLevels; level++) { 30508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org size_t num_files = files_[level].size(); 30608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (num_files == 0) continue; 30708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 30808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // Binary search to find earliest index whose largest key >= internal_key. 30908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key); 31008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (index < num_files) { 31108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org FileMetaData* f = files_[level][index]; 31208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) { 31308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // All of "f" is past any data for user_key 31408595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } else { 31508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (!(*func)(arg, level, f)) { 31608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org return; 31708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 31808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 31908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 32008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 32108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org} 32208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 3238cd4ab8303620197cf24282ae8639060efbb326egabor@google.comStatus Version::Get(const ReadOptions& options, 3248cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const LookupKey& k, 3258cd4ab8303620197cf24282ae8639060efbb326egabor@google.com std::string* value, 3268cd4ab8303620197cf24282ae8639060efbb326egabor@google.com GetStats* stats) { 3278cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Slice ikey = k.internal_key(); 3288cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Slice user_key = k.user_key(); 3298cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const Comparator* ucmp = vset_->icmp_.user_comparator(); 3308cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Status s; 3318cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 3328cd4ab8303620197cf24282ae8639060efbb326egabor@google.com stats->seek_file = NULL; 3338cd4ab8303620197cf24282ae8639060efbb326egabor@google.com stats->seek_file_level = -1; 3348cd4ab8303620197cf24282ae8639060efbb326egabor@google.com FileMetaData* last_file_read = NULL; 335394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com int last_file_read_level = -1; 3368cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 3378cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // We can search level-by-level since entries never hop across 3388cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // levels. Therefore we are guaranteed that if we find data 3398cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // in an smaller level, later levels are irrelevant. 3408cd4ab8303620197cf24282ae8639060efbb326egabor@google.com std::vector<FileMetaData*> tmp; 3418cd4ab8303620197cf24282ae8639060efbb326egabor@google.com FileMetaData* tmp2; 3428cd4ab8303620197cf24282ae8639060efbb326egabor@google.com for (int level = 0; level < config::kNumLevels; level++) { 3438cd4ab8303620197cf24282ae8639060efbb326egabor@google.com size_t num_files = files_[level].size(); 3448cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (num_files == 0) continue; 3458cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 3468cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Get the list of files to search in this level 3478cd4ab8303620197cf24282ae8639060efbb326egabor@google.com FileMetaData* const* files = &files_[level][0]; 3488cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (level == 0) { 3498cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Level-0 files may overlap each other. Find all files that 3508cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // overlap user_key and process them in order from newest to oldest. 3518cd4ab8303620197cf24282ae8639060efbb326egabor@google.com tmp.reserve(num_files); 352fbe4e3af3f4e368e0779b6d75cd6005d67469aa2dgrogan@chromium.org for (uint32_t i = 0; i < num_files; i++) { 3538cd4ab8303620197cf24282ae8639060efbb326egabor@google.com FileMetaData* f = files[i]; 3548cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 && 3558cd4ab8303620197cf24282ae8639060efbb326egabor@google.com ucmp->Compare(user_key, f->largest.user_key()) <= 0) { 3568cd4ab8303620197cf24282ae8639060efbb326egabor@google.com tmp.push_back(f); 3578cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 3588cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 3598cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (tmp.empty()) continue; 3608cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 3618cd4ab8303620197cf24282ae8639060efbb326egabor@google.com std::sort(tmp.begin(), tmp.end(), NewestFirst); 3628cd4ab8303620197cf24282ae8639060efbb326egabor@google.com files = &tmp[0]; 3638cd4ab8303620197cf24282ae8639060efbb326egabor@google.com num_files = tmp.size(); 3648cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } else { 3658cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Binary search to find earliest index whose largest key >= ikey. 3668cd4ab8303620197cf24282ae8639060efbb326egabor@google.com uint32_t index = FindFile(vset_->icmp_, files_[level], ikey); 3678cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (index >= num_files) { 3688cd4ab8303620197cf24282ae8639060efbb326egabor@google.com files = NULL; 3698cd4ab8303620197cf24282ae8639060efbb326egabor@google.com num_files = 0; 3708cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } else { 3718cd4ab8303620197cf24282ae8639060efbb326egabor@google.com tmp2 = files[index]; 3728cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (ucmp->Compare(user_key, tmp2->smallest.user_key()) < 0) { 3738cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // All of "tmp2" is past any data for user_key 3748cd4ab8303620197cf24282ae8639060efbb326egabor@google.com files = NULL; 3758cd4ab8303620197cf24282ae8639060efbb326egabor@google.com num_files = 0; 3768cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } else { 3778cd4ab8303620197cf24282ae8639060efbb326egabor@google.com files = &tmp2; 3788cd4ab8303620197cf24282ae8639060efbb326egabor@google.com num_files = 1; 3798cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 3808cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 3818cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 3828cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 383fbe4e3af3f4e368e0779b6d75cd6005d67469aa2dgrogan@chromium.org for (uint32_t i = 0; i < num_files; ++i) { 3848cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (last_file_read != NULL && stats->seek_file == NULL) { 3858cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // We have had more than one seek for this read. Charge the 1st file. 3868cd4ab8303620197cf24282ae8639060efbb326egabor@google.com stats->seek_file = last_file_read; 387394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com stats->seek_file_level = last_file_read_level; 3888cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 3898cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 3908cd4ab8303620197cf24282ae8639060efbb326egabor@google.com FileMetaData* f = files[i]; 3918cd4ab8303620197cf24282ae8639060efbb326egabor@google.com last_file_read = f; 392394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com last_file_read_level = level; 3938cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 39499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Saver saver; 39599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com saver.state = kNotFound; 39699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com saver.ucmp = ucmp; 39799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com saver.user_key = user_key; 39899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com saver.value = value; 39999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = vset_->table_cache_->Get(options, f->number, f->file_size, 40099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com ikey, &saver, SaveValue); 40199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (!s.ok()) { 4028cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return s; 40399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 40499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com switch (saver.state) { 40599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com case kNotFound: 40699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com break; // Keep searching in other files 40799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com case kFound: 40899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return s; 40999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com case kDeleted: 41099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = Status::NotFound(Slice()); // Use empty error message for speed 41199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return s; 41299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com case kCorrupt: 41399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = Status::Corruption("corrupted key for ", user_key); 4148cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return s; 4158cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 4168cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 4178cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 4188cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 4198cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return Status::NotFound(Slice()); // Use an empty error message for speed 4208cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 4218cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 4228cd4ab8303620197cf24282ae8639060efbb326egabor@google.combool Version::UpdateStats(const GetStats& stats) { 4238cd4ab8303620197cf24282ae8639060efbb326egabor@google.com FileMetaData* f = stats.seek_file; 4248cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (f != NULL) { 4258cd4ab8303620197cf24282ae8639060efbb326egabor@google.com f->allowed_seeks--; 4268cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (f->allowed_seeks <= 0 && file_to_compact_ == NULL) { 4278cd4ab8303620197cf24282ae8639060efbb326egabor@google.com file_to_compact_ = f; 4288cd4ab8303620197cf24282ae8639060efbb326egabor@google.com file_to_compact_level_ = stats.seek_file_level; 4298cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return true; 4308cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 4318cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 4328cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return false; 4338cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 4348cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 43508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.orgbool Version::RecordReadSample(Slice internal_key) { 43608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org ParsedInternalKey ikey; 43708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (!ParseInternalKey(internal_key, &ikey)) { 43808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org return false; 43908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 44008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 44108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org struct State { 44208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org GetStats stats; // Holds first matching file 44308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org int matches; 44408595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 44508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org static bool Match(void* arg, int level, FileMetaData* f) { 44608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org State* state = reinterpret_cast<State*>(arg); 44708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org state->matches++; 44808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (state->matches == 1) { 44908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // Remember first match. 45008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org state->stats.seek_file = f; 45108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org state->stats.seek_file_level = level; 45208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 45308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // We can stop iterating once we have a second match. 45408595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org return state->matches < 2; 45508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 45608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org }; 45708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 45808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org State state; 45908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org state.matches = 0; 46008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match); 46108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 46208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // Must have at least two matches since we want to merge across 46308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // files. But what if we have a single file that contains many 46408595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // overwrites and deletions? Should we have another mechanism for 46508595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // finding such files? 46608595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (state.matches >= 2) { 46708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // 1MB cost is about 1 seek (see comment in Builder::Apply). 46808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org return UpdateStats(state.stats); 46908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 47008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org return false; 47108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org} 47208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org 473179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid Version::Ref() { 474179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++refs_; 475179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 476179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 477179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid Version::Unref() { 478a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(this != &vset_->dummy_versions_); 479179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(refs_ >= 1); 480179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org --refs_; 481179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (refs_ == 0) { 482a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org delete this; 483179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 484179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 485179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 4868cd4ab8303620197cf24282ae8639060efbb326egabor@google.combool Version::OverlapInLevel(int level, 4875fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice* smallest_user_key, 4885fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice* largest_user_key) { 4895fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level], 4905fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com smallest_user_key, largest_user_key); 4915fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com} 4925fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 4935fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.comint Version::PickLevelForMemTableOutput( 4945fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice& smallest_user_key, 4955fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Slice& largest_user_key) { 4965fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com int level = 0; 4975fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) { 4985fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // Push to next level if there is no overlap in next level, 4995fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // and the #bytes overlapping in the level after that are limited. 5005fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek); 5015fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0)); 5025fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com std::vector<FileMetaData*> overlaps; 5035fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com while (level < config::kMaxMemCompactLevel) { 5045fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) { 5055fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com break; 5065fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 50708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (level + 2 < config::kNumLevels) { 50808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org // Check that file does not overlap too many grandparent bytes. 50908595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org GetOverlappingInputs(level + 2, &start, &limit, &overlaps); 51008595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org const int64_t sum = TotalFileSize(overlaps); 51108595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org if (sum > kMaxGrandParentOverlapBytes) { 51208595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org break; 51308595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org } 5145fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 5155fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com level++; 5165fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 5175fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 5185fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com return level; 5195fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com} 5205fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 5215fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com// Store in "*inputs" all files in "level" that overlap [begin,end] 5225fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.comvoid Version::GetOverlappingInputs( 5235fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com int level, 5245fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const InternalKey* begin, 5255fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const InternalKey* end, 5265fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com std::vector<FileMetaData*>* inputs) { 52708595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org assert(level >= 0); 52808595b9e51ded54851b7664bd38affad63a67838dgrogan@chromium.org assert(level < config::kNumLevels); 5295fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com inputs->clear(); 5305fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com Slice user_begin, user_end; 5315fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (begin != NULL) { 5325fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com user_begin = begin->user_key(); 5335fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 5345fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com if (end != NULL) { 5355fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com user_end = end->user_key(); 5365fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 5375fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const Comparator* user_cmp = vset_->icmp_.user_comparator(); 53845b9940be332834440bd5299419f396e38085ebehans@chromium.org for (size_t i = 0; i < files_[level].size(); ) { 53945b9940be332834440bd5299419f396e38085ebehans@chromium.org FileMetaData* f = files_[level][i++]; 54045b9940be332834440bd5299419f396e38085ebehans@chromium.org const Slice file_start = f->smallest.user_key(); 54145b9940be332834440bd5299419f396e38085ebehans@chromium.org const Slice file_limit = f->largest.user_key(); 54245b9940be332834440bd5299419f396e38085ebehans@chromium.org if (begin != NULL && user_cmp->Compare(file_limit, user_begin) < 0) { 5435fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // "f" is completely before specified range; skip it 54445b9940be332834440bd5299419f396e38085ebehans@chromium.org } else if (end != NULL && user_cmp->Compare(file_start, user_end) > 0) { 5455fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // "f" is completely after specified range; skip it 5465fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } else { 5475fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com inputs->push_back(f); 54845b9940be332834440bd5299419f396e38085ebehans@chromium.org if (level == 0) { 54945b9940be332834440bd5299419f396e38085ebehans@chromium.org // Level-0 files may overlap each other. So check if the newly 55045b9940be332834440bd5299419f396e38085ebehans@chromium.org // added file has expanded the range. If so, restart search. 55145b9940be332834440bd5299419f396e38085ebehans@chromium.org if (begin != NULL && user_cmp->Compare(file_start, user_begin) < 0) { 55245b9940be332834440bd5299419f396e38085ebehans@chromium.org user_begin = file_start; 55345b9940be332834440bd5299419f396e38085ebehans@chromium.org inputs->clear(); 55445b9940be332834440bd5299419f396e38085ebehans@chromium.org i = 0; 55545b9940be332834440bd5299419f396e38085ebehans@chromium.org } else if (end != NULL && user_cmp->Compare(file_limit, user_end) > 0) { 55645b9940be332834440bd5299419f396e38085ebehans@chromium.org user_end = file_limit; 55745b9940be332834440bd5299419f396e38085ebehans@chromium.org inputs->clear(); 55845b9940be332834440bd5299419f396e38085ebehans@chromium.org i = 0; 55945b9940be332834440bd5299419f396e38085ebehans@chromium.org } 56045b9940be332834440bd5299419f396e38085ebehans@chromium.org } 5615fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 5625fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 5638cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 5648cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 565179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstd::string Version::DebugString() const { 566179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string r; 567179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 5688cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // E.g., 5698cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // --- level 1 --- 5708cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // 17:123['a' .. 'd'] 5718cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // 20:43['e' .. 'g'] 5728cd4ab8303620197cf24282ae8639060efbb326egabor@google.com r.append("--- level "); 573179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org AppendNumberTo(&r, level); 5748cd4ab8303620197cf24282ae8639060efbb326egabor@google.com r.append(" ---\n"); 575179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>& files = files_[level]; 5761511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < files.size(); i++) { 577179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org r.push_back(' '); 578179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org AppendNumberTo(&r, files[i]->number); 579179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org r.push_back(':'); 580179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org AppendNumberTo(&r, files[i]->file_size); 5815fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com r.append("["); 5825fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com r.append(files[i]->smallest.DebugString()); 5835fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com r.append(" .. "); 5845fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com r.append(files[i]->largest.DebugString()); 5855fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com r.append("]\n"); 586179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 587179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 588179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return r; 589179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 590179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 591179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// A helper class so we can efficiently apply a whole sequence 592179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// of edits to a particular state without creating intermediate 593179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Versions that contain full copies of the intermediate state. 594179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass VersionSet::Builder { 595179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 596a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Helper to sort by v->files_[file_number].smallest 597a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org struct BySmallestKey { 598a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org const InternalKeyComparator* internal_comparator; 599a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 600a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org bool operator()(FileMetaData* f1, FileMetaData* f2) const { 601a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int r = internal_comparator->Compare(f1->smallest, f2->smallest); 602a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (r != 0) { 603a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org return (r < 0); 604a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } else { 605a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Break ties by file number 606a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org return (f1->number < f2->number); 607a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 608a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 609a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org }; 610a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 611a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org typedef std::set<FileMetaData*, BySmallestKey> FileSet; 612a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org struct LevelState { 613a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org std::set<uint64_t> deleted_files; 614a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org FileSet* added_files; 615a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org }; 616a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 617179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org VersionSet* vset_; 618a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org Version* base_; 619a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org LevelState levels_[config::kNumLevels]; 620179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 621179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 622179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Initialize a builder with the files from *base and other info from *vset 623179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Builder(VersionSet* vset, Version* base) 624a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org : vset_(vset), 625a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org base_(base) { 626a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org base_->Ref(); 627a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org BySmallestKey cmp; 628a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org cmp.internal_comparator = &vset_->icmp_; 629179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 630a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org levels_[level].added_files = new FileSet(cmp); 631179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 632179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 633179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 634179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~Builder() { 635179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 63651f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com const FileSet* added = levels_[level].added_files; 63751f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com std::vector<FileMetaData*> to_unref; 63851f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com to_unref.reserve(added->size()); 63951f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com for (FileSet::const_iterator it = added->begin(); 64051f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com it != added->end(); ++it) { 64151f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com to_unref.push_back(*it); 64251f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com } 64351f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com delete added; 644fbe4e3af3f4e368e0779b6d75cd6005d67469aa2dgrogan@chromium.org for (uint32_t i = 0; i < to_unref.size(); i++) { 645a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org FileMetaData* f = to_unref[i]; 646179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org f->refs--; 647179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (f->refs <= 0) { 648179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete f; 649179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 650179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 651179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 652a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org base_->Unref(); 653179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 654179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 655179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Apply all of the edits in *edit to the current state. 656179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void Apply(VersionEdit* edit) { 657179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Update compaction pointers 6581511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < edit->compact_pointers_.size(); i++) { 659179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const int level = edit->compact_pointers_[i].first; 660179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org vset_->compact_pointer_[level] = 661179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit->compact_pointers_[i].second.Encode().ToString(); 662179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 663179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 664179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Delete files 665179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const VersionEdit::DeletedFileSet& del = edit->deleted_files_; 666179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (VersionEdit::DeletedFileSet::const_iterator iter = del.begin(); 667179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter != del.end(); 668179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ++iter) { 669179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const int level = iter->first; 670179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const uint64_t number = iter->second; 671a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org levels_[level].deleted_files.insert(number); 672179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 673179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 674179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Add new files 6751511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < edit->new_files_.size(); i++) { 676179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const int level = edit->new_files_[i].first; 677179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FileMetaData* f = new FileMetaData(edit->new_files_[i].second); 678179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org f->refs = 1; 6798cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 6808cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // We arrange to automatically compact this file after 6818cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // a certain number of seeks. Let's assume: 6828cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // (1) One seek costs 10ms 6838cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // (2) Writing or reading 1MB costs 10ms (100MB/s) 6848cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // (3) A compaction of 1MB does 25MB of IO: 6858cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // 1MB read from this level 6868cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // 10-12MB read from next level (boundaries may be misaligned) 6878cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // 10-12MB written to next level 6888cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // This implies that 25 seeks cost the same as the compaction 6898cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // of 1MB of data. I.e., one seek costs approximately the 6908cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // same as the compaction of 40KB of data. We are a little 6918cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // conservative and allow approximately one seek for every 16KB 6928cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // of data before triggering a compaction. 6938cd4ab8303620197cf24282ae8639060efbb326egabor@google.com f->allowed_seeks = (f->file_size / 16384); 6948cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (f->allowed_seeks < 100) f->allowed_seeks = 100; 6958cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 696a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org levels_[level].deleted_files.erase(f->number); 697a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org levels_[level].added_files->insert(f); 698179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 699179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 700179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 701179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Save the current state in *v. 702179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void SaveTo(Version* v) { 703a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org BySmallestKey cmp; 704a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org cmp.internal_comparator = &vset_->icmp_; 705179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 706a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Merge the set of added files with the set of pre-existing files. 707a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Drop any deleted files. Store the result in *v. 708a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org const std::vector<FileMetaData*>& base_files = base_->files_[level]; 709a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin(); 710a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org std::vector<FileMetaData*>::const_iterator base_end = base_files.end(); 711a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org const FileSet* added = levels_[level].added_files; 712a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v->files_[level].reserve(base_files.size() + added->size()); 713a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org for (FileSet::const_iterator added_iter = added->begin(); 714a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org added_iter != added->end(); 715a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org ++added_iter) { 716a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Add all smaller files listed in base_ 717a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org for (std::vector<FileMetaData*>::const_iterator bpos 718a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org = std::upper_bound(base_iter, base_end, *added_iter, cmp); 719a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org base_iter != bpos; 720a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org ++base_iter) { 721a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org MaybeAddFile(v, level, *base_iter); 722a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 723a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 724a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org MaybeAddFile(v, level, *added_iter); 725a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 726a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 727a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Add remaining base files 728a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org for (; base_iter != base_end; ++base_iter) { 729a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org MaybeAddFile(v, level, *base_iter); 730179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 731a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 732a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org#ifndef NDEBUG 733a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Make sure there is no overlap in levels > 0 734a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (level > 0) { 735fbe4e3af3f4e368e0779b6d75cd6005d67469aa2dgrogan@chromium.org for (uint32_t i = 1; i < v->files_[level].size(); i++) { 736a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org const InternalKey& prev_end = v->files_[level][i-1]->largest; 737a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org const InternalKey& this_begin = v->files_[level][i]->smallest; 738a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (vset_->icmp_.Compare(prev_end, this_begin) >= 0) { 739a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org fprintf(stderr, "overlapping ranges in same level %s vs. %s\n", 7405fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com prev_end.DebugString().c_str(), 7415fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com this_begin.DebugString().c_str()); 742a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org abort(); 743a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 744a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 745a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 746a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org#endif 747a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 748a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 749a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 750a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org void MaybeAddFile(Version* v, int level, FileMetaData* f) { 751a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (levels_[level].deleted_files.count(f->number) > 0) { 752a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // File is deleted: do nothing 753a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } else { 7548cd4ab8303620197cf24282ae8639060efbb326egabor@google.com std::vector<FileMetaData*>* files = &v->files_[level]; 7558cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (level > 0 && !files->empty()) { 7568cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Must not overlap 7578cd4ab8303620197cf24282ae8639060efbb326egabor@google.com assert(vset_->icmp_.Compare((*files)[files->size()-1]->largest, 7588cd4ab8303620197cf24282ae8639060efbb326egabor@google.com f->smallest) < 0); 7598cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 760a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org f->refs++; 7618cd4ab8303620197cf24282ae8639060efbb326egabor@google.com files->push_back(f); 762179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 763179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 764179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 765179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 766179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgVersionSet::VersionSet(const std::string& dbname, 767179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Options* options, 768179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org TableCache* table_cache, 769179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const InternalKeyComparator* cmp) 770179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : env_(options->env), 771179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org dbname_(dbname), 772179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options_(options), 773179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org table_cache_(table_cache), 774179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org icmp_(*cmp), 775179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org next_file_number_(2), 776179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org manifest_file_number_(0), // Filled by Recover() 77795e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org last_sequence_(0), 77895e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org log_number_(0), 77995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org prev_log_number_(0), 780179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org descriptor_file_(NULL), 781179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org descriptor_log_(NULL), 782a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org dummy_versions_(this), 783a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org current_(NULL) { 784a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org AppendVersion(new Version(this)); 785179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 786179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 787179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgVersionSet::~VersionSet() { 788a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org current_->Unref(); 789a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(dummy_versions_.next_ == &dummy_versions_); // List must be empty 790179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete descriptor_log_; 791179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete descriptor_file_; 792179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 793179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 794a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.orgvoid VersionSet::AppendVersion(Version* v) { 795a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Make "v" current 796a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(v->refs_ == 0); 797a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(v != current_); 798a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (current_ != NULL) { 799a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org current_->Unref(); 800a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org } 801a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org current_ = v; 802a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v->Ref(); 803a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 804a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Append to linked list 805a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v->prev_ = dummy_versions_.prev_; 806a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v->next_ = &dummy_versions_; 807a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v->prev_->next_ = v; 808a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v->next_->prev_ = v; 809a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org} 810a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 811394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.comStatus VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) { 81295e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org if (edit->has_log_number_) { 81395e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org assert(edit->log_number_ >= log_number_); 81495e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org assert(edit->log_number_ < next_file_number_); 81595e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org } else { 81695e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org edit->SetLogNumber(log_number_); 81795e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org } 81895e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org 81995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org if (!edit->has_prev_log_number_) { 82095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org edit->SetPrevLogNumber(prev_log_number_); 82195e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org } 82295e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org 823179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit->SetNextFile(next_file_number_); 82495e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org edit->SetLastSequence(last_sequence_); 825179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 826179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Version* v = new Version(this); 827179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { 828179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Builder builder(this, current_); 829179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org builder.Apply(edit); 830179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org builder.SaveTo(v); 831179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 832a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org Finalize(v); 833179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 834179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Initialize new descriptor log file if necessary by creating 835179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // a temporary file that contains a snapshot of the current version. 836a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org std::string new_manifest_file; 837a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org Status s; 838a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (descriptor_log_ == NULL) { 839394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com // No reason to unlock *mu here since we only hit this path in the 840394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com // first call to LogAndApply (when opening the database). 841a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(descriptor_file_ == NULL); 842a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_); 843a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org edit->SetNextFile(next_file_number_); 844a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org s = env_->NewWritableFile(new_manifest_file, &descriptor_file_); 845a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org if (s.ok()) { 846a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org descriptor_log_ = new log::Writer(descriptor_file_); 847a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org s = WriteSnapshot(descriptor_log_); 848179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 849179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 850179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 851394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com // Unlock during expensive MANIFEST log write 852394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com { 853394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com mu->Unlock(); 854394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com 855394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com // Write new record to MANIFEST log 856179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 857394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com std::string record; 858394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com edit->EncodeTo(&record); 859394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com s = descriptor_log_->AddRecord(record); 860394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com if (s.ok()) { 861394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com s = descriptor_file_->Sync(); 862394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com } 86385e27d04530c0323957f28c3f47a7d9f6efeceb0dgrogan@chromium.org if (!s.ok()) { 86485e27d04530c0323957f28c3f47a7d9f6efeceb0dgrogan@chromium.org Log(options_->info_log, "MANIFEST write: %s\n", s.ToString().c_str()); 86585e27d04530c0323957f28c3f47a7d9f6efeceb0dgrogan@chromium.org } 866179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 867179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 868394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com // If we just created a new descriptor file, install it by writing a 869394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com // new CURRENT file that points to it. 870394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com if (s.ok() && !new_manifest_file.empty()) { 871394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com s = SetCurrentFile(env_, dbname_, manifest_file_number_); 872394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com } 873394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com 874394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com mu->Lock(); 875179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 876179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 877179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Install the new version 878179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 879a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org AppendVersion(v); 88095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org log_number_ = edit->log_number_; 88195e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org prev_log_number_ = edit->prev_log_number_; 882179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 883179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete v; 884179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!new_manifest_file.empty()) { 885179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete descriptor_log_; 886179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete descriptor_file_; 887179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org descriptor_log_ = NULL; 888179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org descriptor_file_ = NULL; 889179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org env_->DeleteFile(new_manifest_file); 890179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 891179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 892179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 893179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return s; 894179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 895179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 89695e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.orgStatus VersionSet::Recover() { 897179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org struct LogReporter : public log::Reader::Reporter { 898179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status* status; 899179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void Corruption(size_t bytes, const Status& s) { 900179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (this->status->ok()) *this->status = s; 901179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 902179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org }; 903179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 904179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Read "CURRENT" file, which contains a pointer to the current manifest file 905179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string current; 906179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status s = ReadFileToString(env_, CurrentFileName(dbname_), ¤t); 907179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!s.ok()) { 908179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return s; 909179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 910179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (current.empty() || current[current.size()-1] != '\n') { 911179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::Corruption("CURRENT file does not end with newline"); 912179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 913179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org current.resize(current.size() - 1); 914179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 915179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string dscname = dbname_ + "/" + current; 916179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org SequentialFile* file; 917179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org s = env_->NewSequentialFile(dscname, &file); 918179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!s.ok()) { 919179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return s; 920179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 921179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 922179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool have_log_number = false; 92395e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org bool have_prev_log_number = false; 924179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool have_next_file = false; 925179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org bool have_last_sequence = false; 926179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t next_file = 0; 92795e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org uint64_t last_sequence = 0; 92895e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org uint64_t log_number = 0; 92995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org uint64_t prev_log_number = 0; 930179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Builder builder(this, current_); 931179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 932179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org { 933179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org LogReporter reporter; 934179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org reporter.status = &s; 935a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org log::Reader reader(file, &reporter, true/*checksum*/, 0/*initial_offset*/); 936179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice record; 937179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string scratch; 938179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (reader.ReadRecord(&record, &scratch) && s.ok()) { 939179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org VersionEdit edit; 940179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org s = edit.DecodeFrom(record); 941179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 942179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (edit.has_comparator_ && 943179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit.comparator_ != icmp_.user_comparator()->Name()) { 944179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org s = Status::InvalidArgument( 94529c68f16466b1704dc7a663cf51bf9c5579830c3dgrogan@chromium.org edit.comparator_ + " does not match existing comparator ", 946179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org icmp_.user_comparator()->Name()); 947179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 948179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 949179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 950179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 951179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org builder.Apply(&edit); 952179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 953179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 954179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (edit.has_log_number_) { 95595e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org log_number = edit.log_number_; 956179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org have_log_number = true; 957179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 958179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 95995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org if (edit.has_prev_log_number_) { 96095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org prev_log_number = edit.prev_log_number_; 96195e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org have_prev_log_number = true; 96295e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org } 96395e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org 964179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (edit.has_next_file_number_) { 965179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org next_file = edit.next_file_number_; 966179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org have_next_file = true; 967179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 968179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 969179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (edit.has_last_sequence_) { 97095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org last_sequence = edit.last_sequence_; 971179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org have_last_sequence = true; 972179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 973179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 974179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 975179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete file; 976179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org file = NULL; 977179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 978179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 979179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!have_next_file) { 980179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org s = Status::Corruption("no meta-nextfile entry in descriptor"); 981179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else if (!have_log_number) { 982179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org s = Status::Corruption("no meta-lognumber entry in descriptor"); 983179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else if (!have_last_sequence) { 984179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org s = Status::Corruption("no last-sequence-number entry in descriptor"); 985179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 98695e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org 98795e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org if (!have_prev_log_number) { 98895e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org prev_log_number = 0; 98995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org } 990394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com 991394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com MarkFileNumberUsed(prev_log_number); 992394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com MarkFileNumberUsed(log_number); 993179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 994179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 995179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 996179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Version* v = new Version(this); 997179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org builder.SaveTo(v); 998a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Install recovered version 999a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org Finalize(v); 1000a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org AppendVersion(v); 1001a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org manifest_file_number_ = next_file; 1002a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org next_file_number_ = next_file + 1; 1003a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org last_sequence_ = last_sequence; 1004a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org log_number_ = log_number; 1005a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org prev_log_number_ = prev_log_number; 1006179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1007179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1008179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return s; 1009179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1010179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1011394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.comvoid VersionSet::MarkFileNumberUsed(uint64_t number) { 1012394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com if (next_file_number_ <= number) { 1013394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com next_file_number_ = number + 1; 1014394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com } 1015394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com} 1016394a4b425a6a8aca3244fc26ec77c101a11a632cgabor@google.com 1017a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.orgvoid VersionSet::Finalize(Version* v) { 1018179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Precomputed best level for next compaction 1019179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int best_level = -1; 1020179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org double best_score = -1; 1021179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1022a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org for (int level = 0; level < config::kNumLevels-1; level++) { 102395e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org double score; 1024179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (level == 0) { 102595e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // We treat level-0 specially by bounding the number of files 102695e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // instead of number of bytes for two reasons: 102795e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // 102895e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // (1) With larger write-buffer sizes, it is nice not to do too 102995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // many level-0 compactions. 103095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // 103195e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // (2) The files in level-0 are merged on every read and 103295e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // therefore we wish to avoid too many files when the individual 103395e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // file size is small (perhaps because of a small write-buffer 103495e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // setting, or very high compression ratios, or lots of 103595e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // overwrites/deletions). 1036a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org score = v->files_[level].size() / 1037a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org static_cast<double>(config::kL0_CompactionTrigger); 103895e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org } else { 103995e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org // Compute the ratio of current size to size limit. 104095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org const uint64_t level_bytes = TotalFileSize(v->files_[level]); 104195e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org score = static_cast<double>(level_bytes) / MaxBytesForLevel(level); 1042179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1043179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1044179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (score > best_score) { 1045179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org best_level = level; 1046179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org best_score = score; 1047179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1048179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1049179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1050179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org v->compaction_level_ = best_level; 1051179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org v->compaction_score_ = best_score; 1052179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1053179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1054179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgStatus VersionSet::WriteSnapshot(log::Writer* log) { 1055179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // TODO: Break up into multiple records to reduce memory usage on recovery? 1056179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1057179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Save metadata 1058179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org VersionEdit edit; 1059179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit.SetComparatorName(icmp_.user_comparator()->Name()); 1060179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1061179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Save compaction pointers 1062179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 1063179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!compact_pointer_[level].empty()) { 1064179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKey key; 1065179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org key.DecodeFrom(compact_pointer_[level]); 1066179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit.SetCompactPointer(level, key); 1067179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1068179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1069179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1070179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Save files 1071179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 1072179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>& files = current_->files_[level]; 10731511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < files.size(); i++) { 1074179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const FileMetaData* f = files[i]; 1075179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit.AddFile(level, f->number, f->file_size, f->smallest, f->largest); 1076179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1077179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1078179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1079179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string record; 1080179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit.EncodeTo(&record); 1081179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return log->AddRecord(record); 1082179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1083179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1084179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgint VersionSet::NumLevelFiles(int level) const { 1085179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(level >= 0); 1086179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(level < config::kNumLevels); 1087179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return current_->files_[level].size(); 1088179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1089179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1090a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.orgconst char* VersionSet::LevelSummary(LevelSummaryStorage* scratch) const { 1091a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org // Update code if kNumLevels changes 1092a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(config::kNumLevels == 7); 1093a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org snprintf(scratch->buffer, sizeof(scratch->buffer), 1094a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org "files[ %d %d %d %d %d %d %d ]", 1095a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int(current_->files_[0].size()), 1096a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int(current_->files_[1].size()), 1097a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int(current_->files_[2].size()), 1098a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int(current_->files_[3].size()), 1099a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int(current_->files_[4].size()), 1100a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int(current_->files_[5].size()), 1101a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org int(current_->files_[6].size())); 1102a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org return scratch->buffer; 1103a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org} 1104a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org 1105179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orguint64_t VersionSet::ApproximateOffsetOf(Version* v, const InternalKey& ikey) { 1106179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t result = 0; 1107179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 1108179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>& files = v->files_[level]; 11091511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < files.size(); i++) { 1110179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (icmp_.Compare(files[i]->largest, ikey) <= 0) { 1111179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Entire file is before "ikey", so just add the file size 1112179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org result += files[i]->file_size; 1113179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else if (icmp_.Compare(files[i]->smallest, ikey) > 0) { 1114179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Entire file is after "ikey", so ignore 1115179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (level > 0) { 1116179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Files other than level 0 are sorted by meta->smallest, so 1117179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // no further files in this level will contain data for 1118179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // "ikey". 1119179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 1120179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1121179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 1122179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // "ikey" falls in the range for this table. Add the 1123179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // approximate offset of "ikey" within the table. 1124179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Table* tableptr; 1125179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* iter = table_cache_->NewIterator( 1126f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org ReadOptions(), files[i]->number, files[i]->file_size, &tableptr); 1127179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (tableptr != NULL) { 1128179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org result += tableptr->ApproximateOffsetOf(ikey.Encode()); 1129179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1130179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete iter; 1131179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1132179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1133179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1134179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 1135179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1136179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1137179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid VersionSet::AddLiveFiles(std::set<uint64_t>* live) { 1138a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org for (Version* v = dummy_versions_.next_; 1139a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v != &dummy_versions_; 1140a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org v = v->next_) { 1141179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int level = 0; level < config::kNumLevels; level++) { 1142179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>& files = v->files_[level]; 11431511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < files.size(); i++) { 1144179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org live->insert(files[i]->number); 1145179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1146179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1147179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1148179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1149179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 115095e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.orgint64_t VersionSet::NumLevelBytes(int level) const { 115195e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org assert(level >= 0); 115295e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org assert(level < config::kNumLevels); 115395e21f32367748825123e382172ecbfd492ddb23dgrogan@chromium.org return TotalFileSize(current_->files_[level]); 115407f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org} 115507f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org 115607f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.orgint64_t VersionSet::MaxNextLevelOverlappingBytes() { 115707f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org int64_t result = 0; 1158b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org std::vector<FileMetaData*> overlaps; 11598cd4ab8303620197cf24282ae8639060efbb326egabor@google.com for (int level = 1; level < config::kNumLevels - 1; level++) { 11601511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < current_->files_[level].size(); i++) { 1161b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org const FileMetaData* f = current_->files_[level][i]; 11625fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com current_->GetOverlappingInputs(level+1, &f->smallest, &f->largest, 11635fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com &overlaps); 116407f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org const int64_t sum = TotalFileSize(overlaps); 1165b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org if (sum > result) { 1166b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org result = sum; 1167b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org } 1168b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org } 1169b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org } 1170b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org return result; 1171b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org} 1172b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1173179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Stores the minimal range that covers all entries in inputs in 1174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// *smallest, *largest. 1175179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// REQUIRES: inputs is not empty 1176179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid VersionSet::GetRange(const std::vector<FileMetaData*>& inputs, 1177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKey* smallest, 1178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKey* largest) { 1179179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(!inputs.empty()); 1180179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org smallest->Clear(); 1181179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org largest->Clear(); 11821511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < inputs.size(); i++) { 1183179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FileMetaData* f = inputs[i]; 1184179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (i == 0) { 1185179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *smallest = f->smallest; 1186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *largest = f->largest; 1187179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 1188179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (icmp_.Compare(f->smallest, *smallest) < 0) { 1189179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *smallest = f->smallest; 1190179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1191179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (icmp_.Compare(f->largest, *largest) > 0) { 1192179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *largest = f->largest; 1193179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1194179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1195179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1196179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1197179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1198b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org// Stores the minimal range that covers all entries in inputs1 and inputs2 1199b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org// in *smallest, *largest. 1200b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org// REQUIRES: inputs is not empty 1201b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.orgvoid VersionSet::GetRange2(const std::vector<FileMetaData*>& inputs1, 1202b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org const std::vector<FileMetaData*>& inputs2, 1203b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org InternalKey* smallest, 1204b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org InternalKey* largest) { 1205b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org std::vector<FileMetaData*> all = inputs1; 1206b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org all.insert(all.end(), inputs2.begin(), inputs2.end()); 1207b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org GetRange(all, smallest, largest); 1208b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org} 1209b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1210179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgIterator* VersionSet::MakeInputIterator(Compaction* c) { 1211179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ReadOptions options; 1212179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.verify_checksums = options_->paranoid_checks; 1213179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org options.fill_cache = false; 1214179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1215179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Level-0 files have to be merged together. For other levels, 1216179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // we will make a concatenating iterator per level. 1217179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // TODO(opt): use concatenating iterator for level-0 if there is no overlap 1218179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const int space = (c->level() == 0 ? c->inputs_[0].size() + 1 : 2); 1219179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator** list = new Iterator*[space]; 1220179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int num = 0; 1221179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int which = 0; which < 2; which++) { 1222179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!c->inputs_[which].empty()) { 1223179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (c->level() + which == 0) { 1224179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>& files = c->inputs_[which]; 12251511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < files.size(); i++) { 1226f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org list[num++] = table_cache_->NewIterator( 1227f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org options, files[i]->number, files[i]->file_size); 1228179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1229179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 1230179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Create concatenating iterator for the files from this level 1231179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org list[num++] = NewTwoLevelIterator( 1232a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]), 1233179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org &GetFileIterator, table_cache_, options); 1234179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1235179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1236179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1237179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(num <= space); 1238179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* result = NewMergingIterator(&icmp_, list, num); 1239179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete[] list; 1240179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 1241179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1242179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1243179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgCompaction* VersionSet::PickCompaction() { 12448cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Compaction* c; 12458cd4ab8303620197cf24282ae8639060efbb326egabor@google.com int level; 12468cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 12478cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // We prefer compactions triggered by too much data in a level over 12488cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // the compactions triggered by seeks. 12498cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const bool size_compaction = (current_->compaction_score_ >= 1); 12508cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const bool seek_compaction = (current_->file_to_compact_ != NULL); 12518cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (size_compaction) { 12528cd4ab8303620197cf24282ae8639060efbb326egabor@google.com level = current_->compaction_level_; 12538cd4ab8303620197cf24282ae8639060efbb326egabor@google.com assert(level >= 0); 12548cd4ab8303620197cf24282ae8639060efbb326egabor@google.com assert(level+1 < config::kNumLevels); 12558cd4ab8303620197cf24282ae8639060efbb326egabor@google.com c = new Compaction(level); 12568cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 12578cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Pick the first file that comes after compact_pointer_[level] 12588cd4ab8303620197cf24282ae8639060efbb326egabor@google.com for (size_t i = 0; i < current_->files_[level].size(); i++) { 12598cd4ab8303620197cf24282ae8639060efbb326egabor@google.com FileMetaData* f = current_->files_[level][i]; 12608cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (compact_pointer_[level].empty() || 12618cd4ab8303620197cf24282ae8639060efbb326egabor@google.com icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) { 12628cd4ab8303620197cf24282ae8639060efbb326egabor@google.com c->inputs_[0].push_back(f); 12638cd4ab8303620197cf24282ae8639060efbb326egabor@google.com break; 12648cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 12658cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 12668cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (c->inputs_[0].empty()) { 12678cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Wrap-around to the beginning of the key space 12688cd4ab8303620197cf24282ae8639060efbb326egabor@google.com c->inputs_[0].push_back(current_->files_[level][0]); 12698cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 12708cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } else if (seek_compaction) { 12718cd4ab8303620197cf24282ae8639060efbb326egabor@google.com level = current_->file_to_compact_level_; 12728cd4ab8303620197cf24282ae8639060efbb326egabor@google.com c = new Compaction(level); 12738cd4ab8303620197cf24282ae8639060efbb326egabor@google.com c->inputs_[0].push_back(current_->file_to_compact_); 12748cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } else { 1275179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return NULL; 1276179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1277179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1278179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->input_version_ = current_; 1279179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->input_version_->Ref(); 1280179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1281179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Files in level 0 may overlap each other, so pick up all overlapping ones 1282179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (level == 0) { 1283b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org InternalKey smallest, largest; 1284b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org GetRange(c->inputs_[0], &smallest, &largest); 1285179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Note that the next call will discard the file we placed in 1286179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // c->inputs_[0] earlier and replace it with an overlapping set 1287179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // which will include the picked file. 12885fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]); 1289179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(!c->inputs_[0].empty()); 1290179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1291179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1292b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org SetupOtherInputs(c); 1293b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1294b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org return c; 1295b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org} 1296b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1297b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.orgvoid VersionSet::SetupOtherInputs(Compaction* c) { 1298b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org const int level = c->level(); 1299b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org InternalKey smallest, largest; 1300b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org GetRange(c->inputs_[0], &smallest, &largest); 1301b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 13025fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com current_->GetOverlappingInputs(level+1, &smallest, &largest, &c->inputs_[1]); 1303179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1304b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org // Get entire range covered by compaction 1305b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org InternalKey all_start, all_limit; 1306b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit); 1307b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1308179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // See if we can grow the number of inputs in "level" without 1309179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // changing the number of "level+1" files we pick up. 1310179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!c->inputs_[1].empty()) { 1311179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<FileMetaData*> expanded0; 13125fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0); 131356addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com const int64_t inputs0_size = TotalFileSize(c->inputs_[0]); 131456addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com const int64_t inputs1_size = TotalFileSize(c->inputs_[1]); 131556addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com const int64_t expanded0_size = TotalFileSize(expanded0); 131656addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com if (expanded0.size() > c->inputs_[0].size() && 131756addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com inputs1_size + expanded0_size < kExpandedCompactionByteSizeLimit) { 1318179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org InternalKey new_start, new_limit; 1319179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org GetRange(expanded0, &new_start, &new_limit); 1320179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<FileMetaData*> expanded1; 13215fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com current_->GetOverlappingInputs(level+1, &new_start, &new_limit, 13225fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com &expanded1); 1323179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (expanded1.size() == c->inputs_[1].size()) { 1324f65a55c8d0744b95be29a65d06b59b22b012f37bgabor@google.com Log(options_->info_log, 132556addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com "Expanding@%d %d+%d (%ld+%ld bytes) to %d+%d (%ld+%ld bytes)\n", 1326179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org level, 1327179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int(c->inputs_[0].size()), 1328179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int(c->inputs_[1].size()), 132956addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com long(inputs0_size), long(inputs1_size), 1330179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int(expanded0.size()), 133156addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com int(expanded1.size()), 133256addd362f70667d374aaa686f90eeae5c23d486sanjay@google.com long(expanded0_size), long(inputs1_size)); 1333179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org smallest = new_start; 1334179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org largest = new_limit; 1335179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->inputs_[0] = expanded0; 1336179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->inputs_[1] = expanded1; 1337b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit); 1338179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1339179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1340179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1341179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1342b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org // Compute the set of grandparent files that overlap this compaction 1343b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org // (parent == level+1; grandparent == level+2) 1344b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org if (level + 2 < config::kNumLevels) { 13455fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com current_->GetOverlappingInputs(level + 2, &all_start, &all_limit, 13465fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com &c->grandparents_); 1347b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org } 1348b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1349179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (false) { 1350f65a55c8d0744b95be29a65d06b59b22b012f37bgabor@google.com Log(options_->info_log, "Compacting %d '%s' .. '%s'", 1351179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org level, 13525fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com smallest.DebugString().c_str(), 13535fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com largest.DebugString().c_str()); 1354179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1355179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1356179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Update the place where we will do the next compaction for this level. 1357179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // We update this immediately instead of waiting for the VersionEdit 1358179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // to be applied so that if the compaction fails, we will try a different 1359179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // key range next time. 1360179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org compact_pointer_[level] = largest.Encode().ToString(); 1361179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->edit_.SetCompactPointer(level, largest); 1362179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1363179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1364179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgCompaction* VersionSet::CompactRange( 1365179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org int level, 13665fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const InternalKey* begin, 13675fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com const InternalKey* end) { 1368179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::vector<FileMetaData*> inputs; 13695fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com current_->GetOverlappingInputs(level, begin, end, &inputs); 1370179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (inputs.empty()) { 1371179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return NULL; 1372179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1373179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 13745fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com // Avoid compacting too much in one shot in case the range is large. 137511042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org // But we cannot do this for level-0 since level-0 files can overlap 137611042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org // and we must not pick one file and drop another older file if the 137711042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org // two files overlap. 137811042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org if (level > 0) { 137911042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org const uint64_t limit = MaxFileSizeForLevel(level); 138011042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org uint64_t total = 0; 138111042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org for (size_t i = 0; i < inputs.size(); i++) { 138211042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org uint64_t s = inputs[i]->file_size; 138311042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org total += s; 138411042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org if (total >= limit) { 138511042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org inputs.resize(i + 1); 138611042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org break; 138711042098fe3e5a16ad70c388bb5914a907ae3faedgrogan@chromium.org } 13885fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 13895fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com } 13905fb21ed7ac9e91010d473ac77e132ae68f348d6agabor@google.com 1391179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Compaction* c = new Compaction(level); 1392179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->input_version_ = current_; 1393179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->input_version_->Ref(); 1394179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org c->inputs_[0] = inputs; 1395b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org SetupOtherInputs(c); 1396179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return c; 1397179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1398179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1399179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgCompaction::Compaction(int level) 1400179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : level_(level), 1401179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org max_output_file_size_(MaxFileSizeForLevel(level)), 1402b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org input_version_(NULL), 1403b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org grandparent_index_(0), 140407f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org seen_key_(false), 140507f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org overlapped_bytes_(0) { 1406179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int i = 0; i < config::kNumLevels; i++) { 1407179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org level_ptrs_[i] = 0; 1408179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1409179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1410179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1411179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgCompaction::~Compaction() { 1412179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (input_version_ != NULL) { 1413179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org input_version_->Unref(); 1414179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1415179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1416179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1417b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.orgbool Compaction::IsTrivialMove() const { 141807f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org // Avoid a move if there is lots of overlapping grandparent data. 1419b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org // Otherwise, the move could create a parent file that will require 1420b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org // a very expensive merge later on. 142107f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org return (num_input_files(0) == 1 && 142207f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org num_input_files(1) == 0 && 142307f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org TotalFileSize(grandparents_) <= kMaxGrandParentOverlapBytes); 1424b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org} 1425b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1426179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid Compaction::AddInputDeletions(VersionEdit* edit) { 1427179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int which = 0; which < 2; which++) { 14281511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < inputs_[which].size(); i++) { 1429179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org edit->DeleteFile(level_ + which, inputs_[which][i]->number); 1430179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1431179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1432179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1433179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1434179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgbool Compaction::IsBaseLevelForKey(const Slice& user_key) { 1435179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Maybe use binary search to find right entry instead of linear search? 1436179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Comparator* user_cmp = input_version_->vset_->icmp_.user_comparator(); 1437179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (int lvl = level_ + 2; lvl < config::kNumLevels; lvl++) { 1438179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const std::vector<FileMetaData*>& files = input_version_->files_[lvl]; 1439179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org for (; level_ptrs_[lvl] < files.size(); ) { 1440179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org FileMetaData* f = files[level_ptrs_[lvl]]; 1441179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (user_cmp->Compare(user_key, f->largest.user_key()) <= 0) { 1442179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // We've advanced far enough 1443179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (user_cmp->Compare(user_key, f->smallest.user_key()) >= 0) { 1444179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Key falls in this file's range, so definitely not base level 1445179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return false; 1446179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1447179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 1448179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1449179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org level_ptrs_[lvl]++; 1450179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1451179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1452179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return true; 1453179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1454179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1455a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.orgbool Compaction::ShouldStopBefore(const Slice& internal_key) { 1456b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org // Scan to find earliest grandparent file that contains key. 1457b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org const InternalKeyComparator* icmp = &input_version_->vset_->icmp_; 1458b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org while (grandparent_index_ < grandparents_.size() && 1459a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org icmp->Compare(internal_key, 1460a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org grandparents_[grandparent_index_]->largest.Encode()) > 0) { 146107f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org if (seen_key_) { 146207f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org overlapped_bytes_ += grandparents_[grandparent_index_]->file_size; 146307f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org } 1464b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org grandparent_index_++; 1465b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org } 146607f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org seen_key_ = true; 1467b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 146807f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org if (overlapped_bytes_ > kMaxGrandParentOverlapBytes) { 146907f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org // Too much overlap for current output; start new output 147007f3bcfb9764be2a339cc02cf0a0d6edb151defbjorlow@chromium.org overlapped_bytes_ = 0; 1471b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org return true; 1472b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org } else { 1473b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org return false; 1474b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org } 1475b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org} 1476b887f640bae906abfb77fdf418be63350b4c5e1fjorlow@chromium.org 1477179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid Compaction::ReleaseInputs() { 1478179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (input_version_ != NULL) { 1479179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org input_version_->Unref(); 1480179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org input_version_ = NULL; 1481179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 1482179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 1483179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 148445b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 1485