README.md

LevelDB analysis

Introduction (PPT)

1. Analysis Tools
2. Where to start?
3. Source Code
4. Important Functions
5. Code Flow
6. Watermark
7. Draw figure with PPT

Topics

Topic	User API	Internal Operation	Contents	Source Code	PPT
WAL/Manifest	Put	Open Flush Compaction	Version Control Log Format Manifest Format	log_.h version_.h db_impl.h repair.cc	Week5 Week6 Week8 Week9
Memtable	Put Get Iterator	Flush	Skiplist Arena Batch Write	wirte_batch_internal.h skiplist.h memtable.h db_impl.h arena.h	Week5 Week6 Week8 Week9
Compaction	Put	Compaction	Compaction Policy Merge Iterator	db_impl.h merger.h version_set.h	Week5 Week6 Week8 Week9
SSTable	Get Iterator	Flush Compaction	SST Format Block Format	table/ builder.h	Week5 Week6 Week8 Week9
Bloom filter	Put Get	Flush Compaction	Meta Index Block Filter Block Bloom Filter	bloom.cc filter_block.cc filter_policy.h	Week5 Week6 Week8 Week9
Cache	Get Iterator		Replacement Policy Sharding, Lock Hash Index/Data Block	cache.h table.cc table_cache.h hash.h db_impl.h	Week5 Week6 Week8 Week9

Functions

WAL/Manifest

Memtable

leveldb::log::Writer::AddRecord leveldb::_GLOBAL__N_1::PosixWritableFile::Append leveldb::log::Writer::EmitPhysicalRecord leveldb::VersionSet::PickCompaction leveldb::VersionSet::LogAndApply leveldb::VersionSet::AppendVersion leveldb::VersionSet::NeedsCompaction leveldb::VersionEdit::VersionEdit leveldb::Version::OverlapInLevel leveldb::DBImpl::MaybeScheduleCompaction leveldb::DBImpl::InstallCompactionResults leveldb::_GLOBAL__N_1::PosixWritableFile::SyncFd leveldb::_GLOBAL__N_1::PosixEnv::RemoveFile

leveldb::Version::PickLevelForMemTableOutput leveldb::DBImpl::CompactMemTable leveldb::DBImpl::WriteLevel0Table leveldb::SkipList::RandomHeight leveldb::SkipList::NewNode leveldb::SkipList::Equal leveldb::SkipList::Node::SetNext leveldb::SkipList::Iterator leveldb::Arena::MemoryUsage leveldb::Arena::AllocateNewBlock leveldb::Arena::~Arena

Compaction	SSTable
leveldb::DBImpl::BGWork leveldb::DBImpl::DoCompactionWork leveldb::DBImpl::FinishCompactionOutputFile leveldb::DBImpl::InstallCompactionResults leveldb::DBImpl::CleanupCompaction leveldb::NewTwoLevelIterator leveldb::NewMergingIterator leveldb::_GLOBAL__N_1::MergingIterator::SeekToFirst leveldb::_GLOBAL__N_1::MergingIterator::key	leveldb::ReadBlock leveldb::TableBuilder::Add leveldb::TableBuilder::Flush leveldb::TableBuilder::WriteBlock leveldb::port::Snappy_Compress leveldb::_GLOBAL__N_1::HandleTable::Lookup leveldb::_GLOBAL__N_1::PosixMmapReadableFile::Read leveldb::_GLOBAL__N_1::TwoLevelIterator::InitDataBlock leveldb::_GLOBAL__N_1::PosixWritableFile::Append leveldb::_GLOBAL__N_1::PosixWritableFile::Sync

Bloom Filter

Cache

leveldb::Table::ReadFilter leveldb::FilterBlockBuilder::Finish leveldb::FilterBlockBuilder::StartBlock leveldb::FilterBlockBuilder::GenerateFilter leveldb::FilterBlockBuilder::FilterBlockBuilder leveldb::FilterBlockBuilder::AddKey leveldb::FilterBlockReader::KeyMayMatch leveldb::_GLOBAL__N_1::BloomFilterPolicy::KeyMayMatch leveldb::FilterBlockReader::FilterBlockReader leveldb::_GLOBAL__N_1::BloomHash leveldb::_GLOBAL__N_1::BloomFilterPolicy::CreateFilter leveldb::_GLOBAL__N_1::BloomFilterPolicy::Name

leveldb::TableCache::FindTable leveldb::DeleteCachedBlock leveldb::_GLOBAL__N_1::LRUCache::Release leveldb::_GLOBAL__N_1::LRUCache::LRU_Remove leveldb::_GLOBAL__N_1::LRUCache::LRU_Append leveldb::_GLOBAL__N_1::LRUCache::FinishErase leveldb::_GLOBAL__N_1::LRUCache::Unref leveldb::_GLOBAL__N_1::ShardedLRUCache::Shard leveldb::_GLOBAL__N_1::ShardedLRUCache::Lookup leveldb::_GLOBAL__N_1::ShardedLRUCache::Insert leveldb::_GLOBAL__N_1::PosixMmapReadableFile::Read

Notice

• Upload your presentation file through pull reqeust.

  • Pull request until every Tuesday, 11AM.
  • Title: [analysis]topic_week0.pdf
  • presentation.ppt

• Upload your analysis document at DKU-StarLab/leveldb-wiki repository through pull reqeust.

  • Pull request until every Tuesday, 11AM.

• Check previous study presentation files.

  • https://github.com/DKU-StarLab/RocksDB_Festival