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