leveldb::Version Class Reference

#include <version_set.h>

Collaboration diagram for leveldb::Version:

Classes
struct	GetStats
class	LevelFileNumIterator

Public Member Functions
void	AddIterators (const ReadOptions &, std::vector< Iterator *> *iters)
Status	Get (const ReadOptions &, const LookupKey &key, std::string *val, GetStats *stats)
bool	UpdateStats (const GetStats &stats)
bool	RecordReadSample (Slice key)
void	Ref ()
void	Unref ()
void	GetOverlappingInputs (int level, const InternalKey *begin, const InternalKey *end, std::vector< FileMetaData *> *inputs)
bool	OverlapInLevel (int level, const Slice *smallest_user_key, const Slice *largest_user_key)
int	PickLevelForMemTableOutput (const Slice &smallest_user_key, const Slice &largest_user_key)
int	NumFiles (int level) const
std::string	DebugString () const

Private Member Functions
Iterator *	NewConcatenatingIterator (const ReadOptions &, int level) const
void	ForEachOverlapping (Slice user_key, Slice internal_key, void *arg, bool(*func)(void *, int, FileMetaData *))
	Version (VersionSet *vset)
	~Version ()
	Version (const Version &)
void	operator= (const Version &)

Private Attributes
VersionSet *	vset_
Version *	next_
Version *	prev_
int	refs_
std::vector< FileMetaData * >	files_ [config::kNumLevels]
FileMetaData *	file_to_compact_
int	file_to_compact_level_
double	compaction_score_
int	compaction_level_

Friends
class	Compaction
class	VersionSet

Detailed Description

Definition at line 59 of file version_set.h.

---

Class Documentation

leveldb::Version::GetStats

struct leveldb::Version::GetStats

Definition at line 69 of file version_set.h.

Collaboration diagram for leveldb::Version::GetStats:

Class Members
FileMetaData *	seek_file
int	seek_file_level

Constructor & Destructor Documentation

Version() [1/2]

leveldb::Version::Version ( VersionSet *  vset )

inlineexplicitprivate

Definition at line 150 of file version_set.h.

      : vset_(vset), next_(this), prev_(this), refs_(0),
        file_to_compact_(NULL),
        file_to_compact_level_(-1),
        compaction_score_(-1),
        compaction_level_(-1) {
  }

~Version()

leveldb::Version::~Version ( )

private

Definition at line 66 of file version_set.cc.

                  {
  assert(refs_ == 0);

  // Remove from linked list
  prev_->next_ = next_;
  next_->prev_ = prev_;

  // Drop references to files
  for (int level = 0; level < config::kNumLevels; level++) {
    for (size_t i = 0; i < files_[level].size(); i++) {
      FileMetaData* f = files_[level][i];
      assert(f->refs > 0);
      f->refs--;
      if (f->refs <= 0) {
        delete f;
      }
    }
  }
}

Version() [2/2]

leveldb::Version::Version ( const Version &  )

private

Member Function Documentation

AddIterators()

void leveldb::Version::AddIterators	(	const ReadOptions &	options,
		std::vector< Iterator *> *	iters
	)

Definition at line 234 of file version_set.cc.

                                                        {
  // Merge all level zero files together since they may overlap
  for (size_t i = 0; i < files_[0].size(); i++) {
    iters->push_back(
        vset_->table_cache_->NewIterator(
            options, files_[0][i]->number, files_[0][i]->file_size));
  }

  // For levels > 0, we can use a concatenating iterator that sequentially
  // walks through the non-overlapping files in the level, opening them
  // lazily.
  for (int level = 1; level < config::kNumLevels; level++) {
    if (!files_[level].empty()) {
      iters->push_back(NewConcatenatingIterator(options, level));
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

DebugString()

std::string leveldb::Version::DebugString

(

)

const

Definition at line 574 of file version_set.cc.

                                     {
  std::string r;
  for (int level = 0; level < config::kNumLevels; level++) {
    // E.g.,
    //   --- level 1 ---
    //   17:123['a' .. 'd']
    //   20:43['e' .. 'g']
    r.append("--- level ");
    AppendNumberTo(&r, level);
    r.append(" ---\n");
    const std::vector<FileMetaData*>& files = files_[level];
    for (size_t i = 0; i < files.size(); i++) {
      r.push_back(' ');
      AppendNumberTo(&r, files[i]->number);
      r.push_back(':');
      AppendNumberTo(&r, files[i]->file_size);
      r.append("[");
      r.append(files[i]->smallest.DebugString());
      r.append(" .. ");
      r.append(files[i]->largest.DebugString());
      r.append("]\n");
    }
  }
  return r;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ForEachOverlapping()

void leveldb::Version::ForEachOverlapping ( Slice  user_key, Slice  internal_key, void *  arg, bool(*)(void *, int, FileMetaData *)  func  )

private

Definition at line 287 of file version_set.cc.

                                                                          {
  // TODO(sanjay): Change Version::Get() to use this function.
  const Comparator* ucmp = vset_->icmp_.user_comparator();

  // Search level-0 in order from newest to oldest.
  std::vector<FileMetaData*> tmp;
  tmp.reserve(files_[0].size());
  for (uint32_t i = 0; i < files_[0].size(); i++) {
    FileMetaData* f = files_[0][i];
    if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
        ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
      tmp.push_back(f);
    }
  }
  if (!tmp.empty()) {
    std::sort(tmp.begin(), tmp.end(), NewestFirst);
    for (uint32_t i = 0; i < tmp.size(); i++) {
      if (!(*func)(arg, 0, tmp[i])) {
        return;
      }
    }
  }

  // Search other levels.
  for (int level = 1; level < config::kNumLevels; level++) {
    size_t num_files = files_[level].size();
    if (num_files == 0) continue;

    // Binary search to find earliest index whose largest key >= internal_key.
    uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
    if (index < num_files) {
      FileMetaData* f = files_[level][index];
      if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {
        // All of "f" is past any data for user_key
      } else {
        if (!(*func)(arg, level, f)) {
          return;
        }
      }
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Get()

Status leveldb::Version::Get	(	const ReadOptions &	options,
		const LookupKey &	key,
		std::string *	val,
		GetStats *	stats
	)

Definition at line 332 of file version_set.cc.

                                     {
  Slice ikey = k.internal_key();
  Slice user_key = k.user_key();
  const Comparator* ucmp = vset_->icmp_.user_comparator();
  Status s;

  stats->seek_file = NULL;
  stats->seek_file_level = -1;
  FileMetaData* last_file_read = NULL;
  int last_file_read_level = -1;

  // We can search level-by-level since entries never hop across
  // levels.  Therefore we are guaranteed that if we find data
  // in an smaller level, later levels are irrelevant.
  std::vector<FileMetaData*> tmp;
  FileMetaData* tmp2;
  for (int level = 0; level < config::kNumLevels; level++) {
    size_t num_files = files_[level].size();
    if (num_files == 0) continue;

    // Get the list of files to search in this level
    FileMetaData* const* files = &files_[level][0];
    if (level == 0) {
      // Level-0 files may overlap each other.  Find all files that
      // overlap user_key and process them in order from newest to oldest.
      tmp.reserve(num_files);
      for (uint32_t i = 0; i < num_files; i++) {
        FileMetaData* f = files[i];
        if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
            ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
          tmp.push_back(f);
        }
      }
      if (tmp.empty()) continue;

      std::sort(tmp.begin(), tmp.end(), NewestFirst);
      files = &tmp[0];
      num_files = tmp.size();
    } else {
      // Binary search to find earliest index whose largest key >= ikey.
      uint32_t index = FindFile(vset_->icmp_, files_[level], ikey);
      if (index >= num_files) {
        files = NULL;
        num_files = 0;
      } else {
        tmp2 = files[index];
        if (ucmp->Compare(user_key, tmp2->smallest.user_key()) < 0) {
          // All of "tmp2" is past any data for user_key
          files = NULL;
          num_files = 0;
        } else {
          files = &tmp2;
          num_files = 1;
        }
      }
    }

    for (uint32_t i = 0; i < num_files; ++i) {
      if (last_file_read != NULL && stats->seek_file == NULL) {
        // We have had more than one seek for this read.  Charge the 1st file.
        stats->seek_file = last_file_read;
        stats->seek_file_level = last_file_read_level;
      }

      FileMetaData* f = files[i];
      last_file_read = f;
      last_file_read_level = level;

      Saver saver;
      saver.state = kNotFound;
      saver.ucmp = ucmp;
      saver.user_key = user_key;
      saver.value = value;
      s = vset_->table_cache_->Get(options, f->number, f->file_size,
                                   ikey, &saver, SaveValue);
      if (!s.ok()) {
        return s;
      }
      switch (saver.state) {
        case kNotFound:
          break;      // Keep searching in other files
        case kFound:
          return s;
        case kDeleted:
          s = Status::NotFound(Slice());  // Use empty error message for speed
          return s;
        case kCorrupt:
          s = Status::Corruption("corrupted key for ", user_key);
          return s;
      }
    }
  }

  return Status::NotFound(Slice());  // Use an empty error message for speed
}

Here is the call graph for this function:

Here is the caller graph for this function:

GetOverlappingInputs()

void leveldb::Version::GetOverlappingInputs	(	int	level,
		const InternalKey *	begin,
		const InternalKey *	end,
		std::vector< FileMetaData *> *	inputs
	)

Definition at line 531 of file version_set.cc.

                                      {
  assert(level >= 0);
  assert(level < config::kNumLevels);
  inputs->clear();
  Slice user_begin, user_end;
  if (begin != NULL) {
    user_begin = begin->user_key();
  }
  if (end != NULL) {
    user_end = end->user_key();
  }
  const Comparator* user_cmp = vset_->icmp_.user_comparator();
  for (size_t i = 0; i < files_[level].size(); ) {
    FileMetaData* f = files_[level][i++];
    const Slice file_start = f->smallest.user_key();
    const Slice file_limit = f->largest.user_key();
    if (begin != NULL && user_cmp->Compare(file_limit, user_begin) < 0) {
      // "f" is completely before specified range; skip it
    } else if (end != NULL && user_cmp->Compare(file_start, user_end) > 0) {
      // "f" is completely after specified range; skip it
    } else {
      inputs->push_back(f);
      if (level == 0) {
        // Level-0 files may overlap each other.  So check if the newly
        // added file has expanded the range.  If so, restart search.
        if (begin != NULL && user_cmp->Compare(file_start, user_begin) < 0) {
          user_begin = file_start;
          inputs->clear();
          i = 0;
        } else if (end != NULL && user_cmp->Compare(file_limit, user_end) > 0) {
          user_end = file_limit;
          inputs->clear();
          i = 0;
        }
      }
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

NewConcatenatingIterator()

Iterator * leveldb::Version::NewConcatenatingIterator ( const ReadOptions &  options, int  level  ) const

private

Definition at line 227 of file version_set.cc.

                                                             {
  return NewTwoLevelIterator(
      new LevelFileNumIterator(vset_->icmp_, &files_[level]),
      &GetFileIterator, vset_->table_cache_, options);
}

Here is the call graph for this function:

Here is the caller graph for this function:

NumFiles()

int leveldb::Version::NumFiles ( int  level ) const

inline

Definition at line 111 of file version_set.h.

{ return files_[level].size(); }

operator=()

void leveldb::Version::operator= ( const Version &  )

private

OverlapInLevel()

bool leveldb::Version::OverlapInLevel	(	int	level,
		const Slice *	smallest_user_key,
		const Slice *	largest_user_key
	)

Definition at line 495 of file version_set.cc.

                                                            {
  return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level],
                               smallest_user_key, largest_user_key);
}

Here is the call graph for this function:

Here is the caller graph for this function:

PickLevelForMemTableOutput()

int leveldb::Version::PickLevelForMemTableOutput	(	const Slice &	smallest_user_key,
		const Slice &	largest_user_key
	)

Definition at line 502 of file version_set.cc.

                                   {
  int level = 0;
  if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) {
    // Push to next level if there is no overlap in next level,
    // and the #bytes overlapping in the level after that are limited.
    InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
    InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
    std::vector<FileMetaData*> overlaps;
    while (level < config::kMaxMemCompactLevel) {
      if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
        break;
      }
      if (level + 2 < config::kNumLevels) {
        // Check that file does not overlap too many grandparent bytes.
        GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
        const int64_t sum = TotalFileSize(overlaps);
        if (sum > MaxGrandParentOverlapBytes(vset_->options_)) {
          break;
        }
      }
      level++;
    }
  }
  return level;
}

Here is the call graph for this function:

Here is the caller graph for this function:

RecordReadSample()

bool leveldb::Version::RecordReadSample

(

Slice

key

)

Definition at line 444 of file version_set.cc.

                                                 {
  ParsedInternalKey ikey;
  if (!ParseInternalKey(internal_key, &ikey)) {
    return false;
  }

  struct State {
    GetStats stats;  // Holds first matching file
    int matches;

    static bool Match(void* arg, int level, FileMetaData* f) {
      State* state = reinterpret_cast<State*>(arg);
      state->matches++;
      if (state->matches == 1) {
        // Remember first match.
        state->stats.seek_file = f;
        state->stats.seek_file_level = level;
      }
      // We can stop iterating once we have a second match.
      return state->matches < 2;
    }
  };

  State state;
  state.matches = 0;
  ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match);

  // Must have at least two matches since we want to merge across
  // files. But what if we have a single file that contains many
  // overwrites and deletions?  Should we have another mechanism for
  // finding such files?
  if (state.matches >= 2) {
    // 1MB cost is about 1 seek (see comment in Builder::Apply).
    return UpdateStats(state.stats);
  }
  return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Ref()

void leveldb::Version::Ref

(

)

Definition at line 482 of file version_set.cc.

                  {
  ++refs_;
}

Here is the caller graph for this function:

Unref()

void leveldb::Version::Unref

(

)

Definition at line 486 of file version_set.cc.

                    {
  assert(this != &vset_->dummy_versions_);
  assert(refs_ >= 1);
  --refs_;
  if (refs_ == 0) {
    delete this;
  }
}

Here is the caller graph for this function:

UpdateStats()

bool leveldb::Version::UpdateStats

(

const GetStats &

stats

)

Definition at line 431 of file version_set.cc.

                                               {
  FileMetaData* f = stats.seek_file;
  if (f != NULL) {
    f->allowed_seeks--;
    if (f->allowed_seeks <= 0 && file_to_compact_ == NULL) {
      file_to_compact_ = f;
      file_to_compact_level_ = stats.seek_file_level;
      return true;
    }
  }
  return false;
}

Here is the caller graph for this function:

Friends And Related Function Documentation

Compaction

friend class Compaction

friend

Definition at line 117 of file version_set.h.

VersionSet

friend class VersionSet

friend

Definition at line 118 of file version_set.h.

Member Data Documentation

compaction_level_

int leveldb::Version::compaction_level_

private

Definition at line 148 of file version_set.h.

compaction_score_

double leveldb::Version::compaction_score_

private

Definition at line 147 of file version_set.h.

file_to_compact_

FileMetaData* leveldb::Version::file_to_compact_

private

Definition at line 141 of file version_set.h.

file_to_compact_level_

int leveldb::Version::file_to_compact_level_

private

Definition at line 142 of file version_set.h.

files_

std::vector<FileMetaData*> leveldb::Version::files_[config::kNumLevels]

private

Definition at line 138 of file version_set.h.

next_

Version* leveldb::Version::next_

private

Definition at line 133 of file version_set.h.

prev_

Version* leveldb::Version::prev_

private

Definition at line 134 of file version_set.h.

refs_

int leveldb::Version::refs_

private

Definition at line 135 of file version_set.h.

vset_

VersionSet* leveldb::Version::vset_

private

Definition at line 132 of file version_set.h.

---

The documentation for this class was generated from the following files:

• db/version_set.h
• db/version_set.cc