LevelDB学习笔记 (2): 整体概览与读写实现细节
LevelDB学习笔记 (2): 整体概览与读写实现细节
1. leveldb整体介绍#
首先leveldb的数据是存储在磁盘上的。采用LSM-Tree实现,LSM-Tree把对于磁盘的随机写操作转换成了顺序写操作。这是得益于此leveldb的写操作非常快,为了做点这一点LSM-Tree的思路是将索引树结构拆成一大一小两棵树,较小的一颗常驻内存,较大的一个持久化到磁盘。而随着内存中的树逐渐增大就会发生树的合并和分裂,大概结构如下图所示。后面还会详细分析
下图是整个leveldb的结构概述图,首先我们会把数据写入memtable(位于内存中),当memtable满了之后。就会变成immutable memtable。也就是所谓的冷却状态,这个时候的memtable无法再被写入数据。在immutable memtable中的数据会准备写入SST(磁盘)中
2. leveldb的主要构成#
1、Log文件(位于磁盘)#
在我们把数据写Memtable前会先写Log文件,Log通过append的方式顺序写入。Log的存在使得机器宕机导致的内存数据丢失得以恢复。
2、 Memtable(位于内存)#
Leveldb主要的内存数据结构,采用跳表进行实现。新的数据会首先写入这里。
3、Immutable Memtable(位于内存)#
当Memtable内的数据设置的容量上限后,Memtable会变为Immutable为之后向SST文件的归并做准备。Immutable Mumtable不再接受用户写入,同时生成新的Memtable、log文件供新数据写入。
4、SST文件(位于磁盘)#
磁盘数据存储文件。SSTable(Sorted String Table)就是由内存中的数据不断导出并进行Compaction操作后形成的,而且SSTable的所有文件是一种层级结构,第一层为Level 0,第二层为Level 1,依次类推,层级逐渐增高,这也是为何称之为LevelDb的原因。除此之外,Compact动作会将多个SSTable合并成少量的几个SSTable,以剔除无效数据,保证数据访问效率并降低磁盘占用。
SSTABLE是由多个segement组成,这样可以减少碎片的产生。整体的结构如下图引用自
5、Manifest文件(位于磁盘)#
Manifest文件中记录SST文件在不同Level的分布,单个SST文件的最大最小key,以及其他一些LevelDB需要的元信息。
6、Current文件(位于磁盘)#
从上面的介绍可以看出,LevelDB启动时的首要任务就是找到当前的Manifest,而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名,从而让这个过程变得非常简单。
上述的整体结构就可以利用下图来描述
3. leveldb读写实现速看#
1. 写操作的实现#
首先我们通过之前写过的简单的put操作,利用断点跟踪一下整个put过程。
// Write data.status = db->Put(leveldb::WriteOptions(), "name", "zxl");
WriteOptions 控制着我们是否需要
sync
,也就是刷到磁盘上
根据断点执行,上述的put操作要先进入db/db_impl.cc
里面的Put函数。这里可以发现的key和value都是以Slice形式来存储,也就是切片来存储。因此在往下追溯之前我们先来看一下切片
// Convenience methodsStatus DBImpl::Put(const WriteOptions& o, const Slice& key, const Slice& val) { return DB::Put(o, key, val); }
切片的实现
切片的整体代码位于include/Slice.h
。整体由一个类组成。其中含有一个c字符串和一个大小变量
class LEVELDB_EXPORT Slice { // ...... private: const char* data_; size_t size_; }
整体关于Slice的构造函数有几种不同的重载,下面我们仔细来看一下
// Create an empty slice.Slice() : data_(""), size_(0) {}// Create a slice that refers to d[0,n-1].Slice(const char* d, size_t n) : data_(d), size_(n) {}// Create a slice that refers to the contents of "s"Slice(const std::string& s) : data_(s.data()), size_(s.size()) {}// Create a slice that refers to s[0,strlen(s)-1]Slice(const char* s) : data_(s), size_(strlen(s)) {}
上面四种分别对应了不同的情况
是对于空字符串的初始化
对于给定长度的c字符串的初始化
对于string的初始化
对于不给定长度的c字符串的初始化
对于拷贝构造和拷贝赋值则都采用了c++11的默认方法=default
来实现
关于c++11的默认拷贝构造与拷贝赋值
// Intentionally copyable.Slice(const Slice&) = default; // 默认浅拷贝Slice& operator=(const Slice&) = default;
同样关于切片还有一些特殊作用的函数,来分析一下
starts_with
函数用来判断x是不是当前Slice的一个前缀。这里用到了memcmp
这个c语言库函数。
int memcmp (const void *s1, const void *s2, size_t n); 用来比较s1 和s2 所指的内存区间前n 个字符。
如果返回值为0则表示相同,否则会返回差值,这里是按照ascll的顺序来进行比较的
// Return true iff "x" is a prefix of "*this" bool starts_with(const Slice& x) const { return ((size_ >= x.size_) && (memcmp(data_, x.data_, x.size_) == 0)); }
下面还有两个切片的比较函数
假如说我们调用a.compare(b)
那么比较的逻辑就是先看a和b谁比较长一点。
然后取较小的长度去进行比较
如果在较小的长度内a和b是相同的,那么就是谁长谁就更大
如果在较小的长度内a和b不是想同的,那么就以较小长度内的比较为准
inline int Slice::compare(const Slice& b) const { const size_t min_len = (size_ < b.size_) ? size_ : b.size_; int r = memcmp(data_, b.data_, min_len); if (r == 0) { if (size_ < b.size_) r = -1; else if (size_ > b.size_) r = +1; } return r; }
写一个测试代码
auto a = new leveldb::Slice("123"); leveldb::Slice b; b = leveldb::Slice("21"); std:: cout << "a 与 b 的比较结果" << a->compare(b) << std::endl;
上述代码会输出-1表示a < b这符合我们的预期
好了我们上面知道了key和value都是以切片的形式进行存储的。ok下面继续分析写操作
随后进入db/db_imp.cc
中的DB::Put函数
// Default implementations of convenience methods that subclasses of DB// can call if they wishStatus DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) { WriteBatch batch; batch.Put(key, value); return Write(opt, &batch); }
这里会定义一个writeBatch
来进行写入操作,它会调用batch.put
来实现原子写。
不过我们前面有说写操作会先写Log
来防止出现意外。而数据则会先写入memtable
中
Write Log操作
在调用write(opt, &batch)的时候
Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates) { Writer w(&mutex_); w.batch = updates; w.sync = options.sync; w.done = false; MutexLock l(&mutex_); writers_.push_back(&w); // 排队写入,直到我们在 front while (!w.done && &w != writers_.front()) { w.cv.Wait(); } if (w.done) { return w.status; }
{ mutex_.Unlock(); status = log_->AddRecord(WriteBatchInternal::Contents(write_batch));
上述操作就是写入log的操作。而下面的代码则是写入memTable
if (status.ok()) { status = WriteBatchInternal::InsertInto(write_batch, mem_); // 这里写入,mem_ 是 MemTable, }
关于log写入的具体分析后面会在log详解的时候分析
写入memtable
Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) { MemTableInserter inserter; inserter.sequence_ = WriteBatchInternal::Sequence(b); inserter.mem_ = memtable; return b->Iterate(&inserter); }
上面的代码最终会执行到。memtable.cc
中
void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key, const Slice& value) { // Format of an entry is concatenation of: // key_size : varint32 of internal_key.size() // key bytes : char[internal_key.size()] // value_size : varint32 of value.size() // value bytes : char[value.size()] size_t key_size = key.size(); size_t val_size = value.size(); size_t internal_key_size = key_size + 8; const size_t encoded_len = VarintLength(internal_key_size) + internal_key_size + VarintLength(val_size) + val_size; // 为要put的key value 创建空间 char* buf = arena_.Allocate(encoded_len); char* p = EncodeVarint32(buf, internal_key_size); // copy进去 std::memcpy(p, key.data(), key_size); p += key_size; EncodeFixed64(p, (s << 8) | type); p += 8; p = EncodeVarint32(p, val_size); std::memcpy(p, value.data(), val_size); assert(p + val_size == buf + encoded_len); // 将索引写入SkipList table_.Insert(buf); }
前面说过当memtable满了之后会写入磁盘也就是sstable。对应的代码在MakeRoomForWrite
后面再仔细分析了
Status status = MakeRoomForWrite(updates == nullptr);uint64_t last_sequence = versions_->LastSequence();
2. 读操作的实现#
同样的还是通过debug的方式追踪代码
代码位于
db_impl.cc:DBImpl::Get
// Unlock while reading from files and memtables{ mutex_.Unlock(); // First look in the memtable, then in the immutable memtable (if any). LookupKey lkey(key, snapshot); if (mem->Get(lkey, value, &s)) { // Done } else if (imm != nullptr && imm->Get(lkey, value, &s)) { // Done } else { s = current->Get(options, lkey, value, &stats); have_stat_update = true; } mutex_.Lock(); }if (have_stat_update && current->UpdateStats(stats)) { MaybeScheduleCompaction(); } mem->Unref();if (imm != nullptr) imm->Unref(); current->Unref();return s;
可以发现读操作会先根据key值做一个查找操作loocupKey
随后去memtable中查找。如果memtable没有则会去 immutable
中寻找
如果上面两个地方都查不到的话最后则要去sstable中查找。
4. 总结#
借鉴了很多大佬们的资料, 分析了一下leveldb的整体结构,以及读和写操作的简单实现,当然后面还会进一步分析。更详细的讲解读和写操作的实现。下一篇就分析一下memtable
的实现以及是如何写入memtable
和immutable
的。
5. 参考资料#
https://youjiali1995.github.io/rocksdb/io/
https://github.com/google/leveldb/tree/v1.20/doc
http://catkang.github.io/2017/01/07/leveldb-summary.html
https://www.zhihu.com/column/c_1327581534384230400
https://www.youtube.com/watch?v=PSna05F5fL4&list=PLBokfyNIQPIR2EOXnpemSqzXkkZylAmsD
http://blog.yanick.site/2020/11/08/algorithm/lsm-tree/
https://mp.weixin.qq.com/s/RmyBUUrNVUrmHBJ-7ujM3w
来源https://www.cnblogs.com/JayL-zxl/p/14969466.html