src/leveldb/db/db_iter.cc

   1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4
   5 #include "db/db_iter.h"
   6
   7 #include "db/filename.h"
   8 #include "db/db_impl.h"
   9 #include "db/dbformat.h"
  10 #include "leveldb/env.h"
  11 #include "leveldb/iterator.h"
  12 #include "port/port.h"
  13 #include "util/logging.h"
  14 #include "util/mutexlock.h"
  15 #include "util/random.h"
  16
  17 #ifdef _MSC_VER
  18 #include <BaseTsd.h>
  19 typedef SSIZE_T ssize_t;
  20 #endif
  21
  22 namespace leveldb {
  23
  24 #if 0
  25 static void DumpInternalIter(Iterator* iter) {
  26   for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
  27     ParsedInternalKey k;
  28     if (!ParseInternalKey(iter->key(), &k)) {
  29       fprintf(stderr, "Corrupt '%s'\n", EscapeString(iter->key()).c_str());
  30     } else {
  31       fprintf(stderr, "@ '%s'\n", k.DebugString().c_str());
  32     }
  33   }
  34 }
  35 #endif
  36
  37 namespace {
  38
  39 // Memtables and sstables that make the DB representation contain
  40 // (userkey,seq,type) => uservalue entries.  DBIter
  41 // combines multiple entries for the same userkey found in the DB
  42 // representation into a single entry while accounting for sequence
  43 // numbers, deletion markers, overwrites, etc.
  44 class DBIter: public Iterator {
  45  public:
  46   // Which direction is the iterator currently moving?
  47   // (1) When moving forward, the internal iterator is positioned at
  48   //     the exact entry that yields this->key(), this->value()
  49   // (2) When moving backwards, the internal iterator is positioned
  50   //     just before all entries whose user key == this->key().
  51   enum Direction {
  52     kForward,
  53     kReverse
  54   };
  55
  56   DBIter(DBImpl* db, const Comparator* cmp, Iterator* iter, SequenceNumber s,
  57          uint32_t seed)
  58       : db_(db),
  59         user_comparator_(cmp),
  60         iter_(iter),
  61         sequence_(s),
  62         direction_(kForward),
  63         valid_(false),
  64         rnd_(seed),
  65         bytes_counter_(RandomPeriod()) {
  66   }
  67   virtual ~DBIter() {
  68     delete iter_;
  69   }
  70   virtual bool Valid() const { return valid_; }
  71   virtual Slice key() const {
  72     assert(valid_);
  73     return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
  74   }
  75   virtual Slice value() const {
  76     assert(valid_);
  77     return (direction_ == kForward) ? iter_->value() : saved_value_;
  78   }
  79   virtual Status status() const {
  80     if (status_.ok()) {
  81       return iter_->status();
  82     } else {
  83       return status_;
  84     }
  85   }
  86
  87   virtual void Next();
  88   virtual void Prev();
  89   virtual void Seek(const Slice& target);
  90   virtual void SeekToFirst();
  91   virtual void SeekToLast();
  92
  93  private:
  94   void FindNextUserEntry(bool skipping, std::string* skip);
  95   void FindPrevUserEntry();
  96   bool ParseKey(ParsedInternalKey* key);
  97
  98   inline void SaveKey(const Slice& k, std::string* dst) {
  99     dst->assign(k.data(), k.size());
 100   }
 101
 102   inline void ClearSavedValue() {
 103     if (saved_value_.capacity() > 1048576) {
 104       std::string empty;
 105       swap(empty, saved_value_);
 106     } else {
 107       saved_value_.clear();
 108     }
 109   }
 110
 111   // Pick next gap with average value of config::kReadBytesPeriod.
 112   ssize_t RandomPeriod() {
 113     return rnd_.Uniform(2*config::kReadBytesPeriod);
 114   }
 115
 116   DBImpl* db_;
 117   const Comparator* const user_comparator_;
 118   Iterator* const iter_;
 119   SequenceNumber const sequence_;
 120
 121   Status status_;
 122   std::string saved_key_;     // == current key when direction_==kReverse
 123   std::string saved_value_;   // == current raw value when direction_==kReverse
 124   Direction direction_;
 125   bool valid_;
 126
 127   Random rnd_;
 128   ssize_t bytes_counter_;
 129
 130   // No copying allowed
 131   DBIter(const DBIter&);
 132   void operator=(const DBIter&);
 133 };
 134
 135 inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
 136   Slice k = iter_->key();
 137   ssize_t n = k.size() + iter_->value().size();
 138   bytes_counter_ -= n;
 139   while (bytes_counter_ < 0) {
 140     bytes_counter_ += RandomPeriod();
 141     db_->RecordReadSample(k);
 142   }
 143   if (!ParseInternalKey(k, ikey)) {
 144     status_ = Status::Corruption("corrupted internal key in DBIter");
 145     return false;
 146   } else {
 147     return true;
 148   }
 149 }
 150
 151 void DBIter::Next() {
 152   assert(valid_);
 153
 154   if (direction_ == kReverse) {  // Switch directions?
 155     direction_ = kForward;
 156     // iter_ is pointing just before the entries for this->key(),
 157     // so advance into the range of entries for this->key() and then
 158     // use the normal skipping code below.
 159     if (!iter_->Valid()) {
 160       iter_->SeekToFirst();
 161     } else {
 162       iter_->Next();
 163     }
 164     if (!iter_->Valid()) {
 165       valid_ = false;
 166       saved_key_.clear();
 167       return;
 168     }
 169     // saved_key_ already contains the key to skip past.
 170   } else {
 171     // Store in saved_key_ the current key so we skip it below.
 172     SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
 173   }
 174
 175   FindNextUserEntry(true, &saved_key_);
 176 }
 177
 178 void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
 179   // Loop until we hit an acceptable entry to yield
 180   assert(iter_->Valid());
 181   assert(direction_ == kForward);
 182   do {
 183     ParsedInternalKey ikey;
 184     if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
 185       switch (ikey.type) {
 186         case kTypeDeletion:
 187           // Arrange to skip all upcoming entries for this key since
 188           // they are hidden by this deletion.
 189           SaveKey(ikey.user_key, skip);
 190           skipping = true;
 191           break;
 192         case kTypeValue:
 193           if (skipping &&
 194               user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
 195             // Entry hidden
 196           } else {
 197             valid_ = true;
 198             saved_key_.clear();
 199             return;
 200           }
 201           break;
 202       }
 203     }
 204     iter_->Next();
 205   } while (iter_->Valid());
 206   saved_key_.clear();
 207   valid_ = false;
 208 }
 209
 210 void DBIter::Prev() {
 211   assert(valid_);
 212
 213   if (direction_ == kForward) {  // Switch directions?
 214     // iter_ is pointing at the current entry.  Scan backwards until
 215     // the key changes so we can use the normal reverse scanning code.
 216     assert(iter_->Valid());  // Otherwise valid_ would have been false
 217     SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
 218     while (true) {
 219       iter_->Prev();
 220       if (!iter_->Valid()) {
 221         valid_ = false;
 222         saved_key_.clear();
 223         ClearSavedValue();
 224         return;
 225       }
 226       if (user_comparator_->Compare(ExtractUserKey(iter_->key()),
 227                                     saved_key_) < 0) {
 228         break;
 229       }
 230     }
 231     direction_ = kReverse;
 232   }
 233
 234   FindPrevUserEntry();
 235 }
 236
 237 void DBIter::FindPrevUserEntry() {
 238   assert(direction_ == kReverse);
 239
 240   ValueType value_type = kTypeDeletion;
 241   if (iter_->Valid()) {
 242     do {
 243       ParsedInternalKey ikey;
 244       if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
 245         if ((value_type != kTypeDeletion) &&
 246             user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {
 247           // We encountered a non-deleted value in entries for previous keys,
 248           break;
 249         }
 250         value_type = ikey.type;
 251         if (value_type == kTypeDeletion) {
 252           saved_key_.clear();
 253           ClearSavedValue();
 254         } else {
 255           Slice raw_value = iter_->value();
 256           if (saved_value_.capacity() > raw_value.size() + 1048576) {
 257             std::string empty;
 258             swap(empty, saved_value_);
 259           }
 260           SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
 261           saved_value_.assign(raw_value.data(), raw_value.size());
 262         }
 263       }
 264       iter_->Prev();
 265     } while (iter_->Valid());
 266   }
 267
 268   if (value_type == kTypeDeletion) {
 269     // End
 270     valid_ = false;
 271     saved_key_.clear();
 272     ClearSavedValue();
 273     direction_ = kForward;
 274   } else {
 275     valid_ = true;
 276   }
 277 }
 278
 279 void DBIter::Seek(const Slice& target) {
 280   direction_ = kForward;
 281   ClearSavedValue();
 282   saved_key_.clear();
 283   AppendInternalKey(
 284       &saved_key_, ParsedInternalKey(target, sequence_, kValueTypeForSeek));
 285   iter_->Seek(saved_key_);
 286   if (iter_->Valid()) {
 287     FindNextUserEntry(false, &saved_key_ /* temporary storage */);
 288   } else {
 289     valid_ = false;
 290   }
 291 }
 292
 293 void DBIter::SeekToFirst() {
 294   direction_ = kForward;
 295   ClearSavedValue();
 296   iter_->SeekToFirst();
 297   if (iter_->Valid()) {
 298     FindNextUserEntry(false, &saved_key_ /* temporary storage */);
 299   } else {
 300     valid_ = false;
 301   }
 302 }
 303
 304 void DBIter::SeekToLast() {
 305   direction_ = kReverse;
 306   ClearSavedValue();
 307   iter_->SeekToLast();
 308   FindPrevUserEntry();
 309 }
 310
 311 }  // anonymous namespace
 312
 313 Iterator* NewDBIterator(
 314     DBImpl* db,
 315     const Comparator* user_key_comparator,
 316     Iterator* internal_iter,
 317     SequenceNumber sequence,
 318     uint32_t seed) {
 319   return new DBIter(db, user_key_comparator, internal_iter, sequence, seed);
 320 }
 321
 322 }  // namespace leveldb