Leveldb

1 levelDB读写形象在levelDB中，读写能力是通过Env提供的。Env是一个接口类，其提供创立读写代理文件类（是我本人非凡的叫法，因为这些类，实质上是对特定环境下的文件读写的代理。当然Env除了形象了文件读写之外，还形象了一部分工作执行或者说叫CPU能力，然而这块实现上还是比拟急简略），这些句柄类依据不同的内核有不同的实现，在levelDB中次要是posix语义的实现以及windows语义的文件句柄类。 在实现上，Env并不保有任何的代理文件对象，而是通过几个接口，创立对应的代理文件对象。几个抽象类的关系如下 Posix语义的实体类关系如下所示 2 细读PosixEnv

理清leveldb的recover流程对于了解leveldb如何保证数据正确性和一致性（即便在节点解体的状况下）是十分有帮忙的。首先从Open函数开始，结构一个DBImpl实例，而后调用了其Recover办法。 Status DB::Open(const Options& options, const std::string& dbname, DB** dbptr) { *dbptr = NULL; DBImpl* impl = new DBImpl(options, dbname); impl->mutex_.Lock(); VersionEdit edit; // Recover handles create_if_missing, error_if_exists bool save_manifest = false; Status s = impl->Recover(&edit, &save_manifest); if (s.ok() && impl->mem_ == NULL) { // Create new log and a corresponding memtable. uint64_t new_log_number = impl->versions_->NewFileNumber(); WritableFile* lfile; s = options.env->NewWritableFile(LogFileName(dbname, new_log_number), &lfile); if (s.ok()) { edit.SetLogNumber(new_log_number); impl->logfile_ = lfile; impl->logfile_number_ = new_log_number; impl->log_ = new log::Writer(lfile); impl->mem_ = new MemTable(impl->internal_comparator_); impl->mem_->Ref(); } } if (s.ok() && save_manifest) { edit.SetPrevLogNumber(0); // No older logs needed after recovery. edit.SetLogNumber(impl->logfile_number_); s = impl->versions_->LogAndApply(&edit, &impl->mutex_); } if (s.ok()) { impl->DeleteObsoleteFiles(); impl->MaybeScheduleCompaction(); } impl->mutex_.Unlock(); if (s.ok()) { assert(impl->mem_ != NULL); *dbptr = impl; } else { delete impl; } return s;}Status DBImpl::Recover(VersionEdit* edit, bool *save_manifest) { mutex_.AssertHeld(); // Ignore error from CreateDir since the creation of the DB is // committed only when the descriptor is created, and this directory // may already exist from a previous failed creation attempt. env_->CreateDir(dbname_); assert(db_lock_ == NULL); Status s = env_->LockFile(LockFileName(dbname_), &db_lock_); if (!s.ok()) { return s; } if (!env_->FileExists(CurrentFileName(dbname_))) { if (options_.create_if_missing) { s = NewDB(); if (!s.ok()) { return s; } } else { return Status::InvalidArgument( dbname_, "does not exist (create_if_missing is false)"); } } else { if (options_.error_if_exists) { return Status::InvalidArgument( dbname_, "exists (error_if_exists is true)"); } } // 这里调用了versions_->Recover函数 s = versions_->Recover(save_manifest); if (!s.ok()) { return s; } SequenceNumber max_sequence(0); // Recover from all newer log files than the ones named in the // descriptor (new log files may have been added by the previous // incarnation without registering them in the descriptor). // // Note that PrevLogNumber() is no longer used, but we pay // attention to it in case we are recovering a database // produced by an older version of leveldb. // 以下是复原在descriptor中记录的最初一个log file之后的所有日志文件 const uint64_t min_log = versions_->LogNumber(); const uint64_t prev_log = versions_->PrevLogNumber(); std::vector<std::string> filenames; s = env_->GetChildren(dbname_, &filenames); if (!s.ok()) { return s; } std::set<uint64_t> expected; versions_->AddLiveFiles(&expected); uint64_t number; FileType type; std::vector<uint64_t> logs; for (size_t i = 0; i < filenames.size(); i++) { if (ParseFileName(filenames[i], &number, &type)) { expected.erase(number); // 对于日志文件而言，所有文件编号大于等于versions_->LogNumber()的日志文件都没有来得及被写入以后版本，此时须要回放。 if (type == kLogFile && ((number >= min_log) || (number == prev_log))) logs.push_back(number); } } if (!expected.empty()) { char buf[50]; snprintf(buf, sizeof(buf), "%d missing files; e.g.", static_cast<int>(expected.size())); return Status::Corruption(buf, TableFileName(dbname_, *(expected.begin()))); } // Recover in the order in which the logs were generated std::sort(logs.begin(), logs.end()); for (size_t i = 0; i < logs.size(); i++) { s = RecoverLogFile(logs[i], (i == logs.size() - 1), save_manifest, edit, &max_sequence); if (!s.ok()) { return s; } // The previous incarnation may not have written any MANIFEST // records after allocating this log number. So we manually // update the file number allocation counter in VersionSet. versions_->MarkFileNumberUsed(logs[i]); } if (versions_->LastSequence() < max_sequence) { versions_->SetLastSequence(max_sequence); } return Status::OK();}上面关注下versions_->Recover()函数 ...

最近练手的项目里用到了LevelDB, 具有很优秀的存储效率，DDIA中有介绍它底层是LSM-tree实现的，今天决定看看LSM-tree,给看到的文章做总结，也给自己想要动手写了好久的技术博客开个头吧。 特点总的来说就是通过将大量的随机写转换为顺序写，从而极大地提升了数据写入的性能，虽然与此同时牺牲了部分读的性能。只适合存储 key 值有序且写入大于读取的数据，或者读取操作通常是 key 值连续的数据。这里有一篇比较B树，B+树，以及lsm树的文章。 存储模型WALWAL（write ahead log）也称预写log，包括mysql的Binlog等,在设计数据库的时候经常被使用，当插入一条数据时，数据先顺序写入 WAL 文件中，之后插入到内存中的 MemTable 中。这样就保证了数据的持久化，不会丢失数据，并且都是顺序写，速度很快。当程序挂掉重启时，可以从 WAL 文件中重新恢复内存中的 MemTable。 MemTableMemTable 对应的就是 WAL 文件，是该文件内容在内存中的存储结构，通常用 SkipList 来实现。MemTable 提供了 k-v 数据的写入、删除以及读取的操作接口。其内部将 k-v 对按照 key 值有序存储，这样方便之后快速序列化到 SSTable 文件中，仍然保持数据的有序性。 Immutable Memtable顾名思义，Immutable Memtable 就是在内存中只读的 MemTable，由于内存是有限的，通常我们会设置一个阀值，当 MemTable 占用的内存达到阀值后就自动转换为 Immutable Memtable，Immutable Memtable 和 MemTable 的区别就是它是只读的，系统此时会生成新的 MemTable 供写操作继续写入。之所以要使用 Immutable Memtable，就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。 SSTableSSTable 就是 MemTable 中的数据在磁盘上的有序存储，其内部数据是根据 key 从小到大排列的。通常为了加快查找的速度，需要在 SSTable 中加入数据索引，可以快读定位到指定的 k-v 数据。 SSTable 通常采用的分级的结构，例如 LevelDB 中就是如此。MemTable 中的数据达到指定阀值后会在 Level 0 层创建一个新的 SSTable。当某个 Level 下的文件数超过一定值后，就会将这个 Level 下的一个 SSTable 文件和更高一级的 SSTable 文件合并，由于 SSTable 中的 k-v 数据都是有序的，相当于是一个多路归并排序，所以合并操作相当快速，最终生成一个新的 SSTable 文件，将旧的文件删除，这样就完成了一次合并过程。 ...

单机基于SSTable。适用于与SSD一起使用。整体https://segmentfault.com/a/11...。mysql写入千条/s，读万应该没问题。redis 写入 万条/s 7M/s(k+v 700bytes，双核)读是写入的1.4倍 mem 3gb 2核。这两个网上搜的，不保证正确，就看个大概吧。SSD上 rocksdb随机和顺序的性能差不多，写要比读性能稍好。随机读写1.7万条/s 14M/s （32核）。batch_write/read下SSD单线程会耗8倍。普通write只快1.2倍。没有再一个机器上的对比。rocksdb在用SSD和batch-write/read下的读写性能还是可以的。 第一章 levelDb架构图 读取过程数据的读取是按照 MemTable、Immutable MemTable 以及不同层级的 SSTable 的顺序进行的，前两者都是在内存中，后面不同层级的 SSTable 都是以 *.ldb 文件的形式持久存储在磁盘上 写入过程1.调用 MakeRoomForWrite 方法为即将进行的写入提供足够的空间；在这个过程中，由于 memtable 中空间的不足可能会冻结当前的 memtable，发生 Minor Compaction 并创建一个新的 MemTable 对象；不可变imm去minor C,新的memtable继续接收写在某些条件满足时，也可能发生 Major Compaction，对数据库中的 SSTable 进行压缩；2.通过 AddRecord 方法向日志中追加一条写操作的记录；3.再向日志成功写入记录后，我们使用 InsertInto 直接插入 memtable 中，内存格式为跳表，完成整个写操作的流程； writebatch并发控制全局的sequence(memcache中记录)。读写事务都申请writebatch。这里即使是并发，也是选择leader(cas+memory_order)将多个writebatch合并一起写入WAL，再依次写入memtable再提交。 ACID版本控制 内存中在每次读的时候用userkey+sequence生成。这个sequence面膜人呢使用当前最新的sequnce。保证整个读过程都读到当前版本的，在写入时，写入成功后才更新sequnce保证最新写入的sequnce+1的内存不会被旧的读取读到。Compaction过程中被引用的version不会删除。被version引用的file也不会删除每次获取current versionn的内容。更新后才会更改current的位置 memtable频繁插入查询，没有删除。需要无写状态下的遍历（dump过程）=》跳表日志文件4M后变sstable.memtable是日志的副本 sstablesstable（默认7个）【上层0，下层7】filemetadata: refs文件被不同version引用次数,allowed_Seeks允许查找次数,number文件序号,file_size，smallest,largest除了level0是内存满直接落盘key范围会有重叠，下层都是经过合并的，没重叠，可以直接通过filemetadata定位在一个文件后二分查找。level0会查找多个文件。上层倒到容量后触发向下一层归并，每一层数据量是比其上一层成倍增长 sstable=>blocks=>entrys DataBlock Key := UserKey + SequenceNum + TypeType := kDelete or kValueMeta Block：比较特殊的Block，用来存储元信息，目前LevelDB使用的仅有对布隆过滤器的存储。写入Data Block的数据会同时更新对应Meta Block中的过滤器。读取数据时也会首先经过布隆过滤器过滤.bloom过滤器：key散列到hash%过滤器容量，1代表有0代表无，判断key在容量范围内是否存在。因为hash冲突有一定存在但并不存在的错误率哈希函数的个数k；=>double-hashing i从0-k, gi(x) = h1(x) + ih2(x) + i^2 mod m,布隆过滤器位数组的容量m;布隆过滤器插入的数据数量n;datablock: ...