日期：2025.9.6（凌晨)
个人总结：
perface
是这样的，本来是打算写完之后再整理的，但是感觉自己貌似会懒癌犯了，所以决定还是自己看了哪些内容就都发了吧。
如果自己真的会想整理的话，那就算之前写个过半成品应该也会有心去整理好好总结吧。
为了自己的数据库的水平可以再提高一些，所以准备阅读leveldb源码 （绝不是因为想看别的数据库源码，但是发现自己屁都看不懂
关于编译运行前的若干情况
clone下来后发现有可能编译不过，如果有这种情况，就在cmakelists里面加上一个set(CMAKE_CXX_STANDARD 17)就好了。
发现googletest的版本过低，请自行升级。（去clone一个最新版本的，然后替换掉thirdparty里面的gtest就好了。
前置声明：
由于本人的水平也并不高，对于源码的阅读是第一次，所以是有一些没有框架的逻辑在的，说人话就是自己是读到哪看到哪写到哪的。
并不专业，但是尽量会说出自己的理解，让个人听懂。
本人最后会把自己对于leveldb的中文注释放到仓库上去。
Slice
首先其实最先上来，去看有关db的文件了，然后发现有一个类出现的非常多，Slice。发现内容不长，所以先来拜读一下。
然后发现其内部主要是对const char * data 和 size_t size的一个封装，里面有一些有的比较多的函数，例如remove_prefix去除前n个字节。
看了看设计，发现这个主要是对资源获取他的指针，然后访问。我们不需要去一直传递资源从而浪费性能，直接传递Slice就好了，而且对他拷贝也并没有什么损耗，毕竟就一个指针和一个size_t。
值得注意的一点是，我们是需要确保资源没有被析构，否则会造成段错误。
//这个类并不需要得到资源，只是得到资源的指针用来方便访问而已。
// 所以也没有析构函数
class LEVELDB_EXPORT Slice {public:// 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)) {}// Intentionally copyable.Slice(const Slice&) = default;Slice& operator=(const Slice&) = default;// Return true iff the length of the referenced data is zerobool empty() const { return size_ == 0; }const char* begin() const { return data(); }const char* end() const { return data() + size(); }//....此处省略 // Drop the first "n" bytes from this slice.void remove_prefix(size_t n) {assert(n <= size());data_ += n;size_ -= n;}private:const char* data_;size_t size_;
};
WriteBatch
后来接着顺序，看到了
// Default implementations of convenience methods that subclasses of DB
// can call if they wish
Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) {WriteBatch batch;batch.Put(key, value);return Write(opt, &batch);
}
这是db的put操作，这里有一个没有接触的类是WriteBatch。
来翻看一下writebatch.h
/*
这就是一个写操作的集合，有点对标事务吧?*/
class LEVELDB_EXPORT WriteBatch {public://定义了一个基础操作类，有插入和删除两个操作class LEVELDB_EXPORT Handler {public:virtual ~Handler();virtual void Put(const Slice& key, const Slice& value) = 0;virtual void Delete(const Slice& key) = 0;};WriteBatch();// Intentionally copyable.WriteBatch(const WriteBatch&) = default;WriteBatch& operator=(const WriteBatch&) = default;~WriteBatch();void Put(const Slice& key, const Slice& value);void Delete(const Slice& key);void Clear();size_t ApproximateSize() const;void Append(const WriteBatch& source);Status Iterate(Handler* handler) const;private:friend class WriteBatchInternal;/*所以就现在来看，这个WriteBatch里的rep_里的前8个字节（uint64)代表返回这个写集合里的第一个队列的编号* 第8到第12字节（uint32)是代表count的个数，也就是目前存的个数。*/std::string rep_; // See comment in write_batch.cc for the format of rep_
};
首先先来讲解一下，这个其实是一个写操作的集合，在leveldb里面，每一个操作都会有一个队列编号，其实也可以理解成操作编号，（主要是在并发控制的时候派上用场)，然后这个操作会用WriteBatch维护起来，这个维护的具体方式是用一个字符串rep_去记录下来操作的内容。
首先是规定了rep_的前8个字节代表的是这个操作集合的第一个队列的编号，为什么说是第一个队列的编号，是因为leveldb对于这个writebatch有一个小优化，就是如果有很多的操作，如果我们对于每一个操作单独处理，空间上会有一些浪费，例如每一个writebatch都要开前12个字节去记录，还有一点就是落盘操作会慢一些，一次性批量的写入完会更快一些。所以优化就是会把很多个操作都放到同一个writebatch里面，在这里面他们的队列编号其实是单调递增且连续的。所以我们记录下来第一个队列的编号就好了。
对于第9到12个字节（uint32_t)，代表的是队列里面放的操作的个数。（这也是static const size_t kHeader = 12;的原因)后续就是存放具体的操作了。
然后我们来看一下writebatch的put操作：
// 这里就是，每一次put的时候，我们把key和value追加到rep_里面去。
// 首先是count个数要+1，然后放进去
// 关于rep的内容，首先是用一个char类型（也就是一个字节)去区分类型，如果是kTypeValue，那么就是Put操作。
// 然后就会进行两次长度+内容的解析，也就是先读取长度，然后读取对应长度的字节去转换过来。
// 这样就搞出来了key和value。
// 下面的delete也是这样的操作。
void WriteBatch::Put(const Slice& key, const Slice& value) {WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);rep_.push_back(static_cast<char>(kTypeValue));PutLengthPrefixedSlice(&rep_, key);PutLengthPrefixedSlice(&rep_, value);
}
对于每一个操作，我们会用一个字节去存放这个操作的类型，如果是kTypeValue就是put，也就是update或者insert操作，这里没有做更进一步的区分，因为其实无论如何都是insert，并不会有概念上的update操作，关于这里先暂且不详谈，等到将table的时候再说。
如果是kTypeValue就是put，那么我们再跟上key和value。这里的函数实现：
//追加了一个长度，然后还有对应长度的数据。
void PutLengthPrefixedSlice(std::string* dst, const Slice& value) {PutVarint32(dst, value.size());dst->append(value.data(), value.size());
}
我们肯定是要先存放key的长度，然后再放进去key。value我们也是这样的处理。 （PutVarint32这个内容我们以后会说到)
如果是删除操作，也是和put类似的内容。
void WriteBatch::Delete(const Slice& key) {WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);rep_.push_back(static_cast<char>(kTypeDeletion));PutLengthPrefixedSlice(&rep_, key);
}
这里的PutLengthPrefixedSlice函数，是关于coding.h的内容，我们等会会详说。先接着把WriteBatch的内容说完。
还有一个关于WriteBatch的稍微重要一些的内容：
就是其实我们并不会直接面向WriteBatch（大多数)，而是用WriteBatchInternal。
这个WriteBatchInternal其实是一个辅助我们，给我们提供了一些操作WriteBatch的一些接口。我们如果有一些想要对于WriteBatch实现的函数，那么就是在这个WriteBatchInternal里面先写好接口，然后在WriteBatch里面实现好具体的功能。
但以上的两个put和delete函数的内容，则主要是面向于对于一个WriteBatch初始化的时候我们做的内容，例如我们想要put一对{key，value}，我们会创建一个WriteBatch，然后调用put函数，之后的事情就交给WriteBatchInternal了，其实我觉得可以把最开始的put和delete操作也交给WriteBatchInternal来做，也不知道为什么把put和delete给单独交给WriteBatch来搞了。
这里直接贴上了WriteBatchInternal的类的代码了，附带中文注释。关于这些函数内容，我们接下来会谈到。
namespace leveldb {class MemTable;// WriteBatchInternal provides static methods for manipulating a
// WriteBatch that we don't want in the public WriteBatch interface.
class WriteBatchInternal {public:// Return the number of entries in the batch.static int Count(const WriteBatch* batch);// Set the count for the number of entries in the batch.static void SetCount(WriteBatch* batch, int n);// Return the sequence number for the start of this batch.// 获得队列编号static SequenceNumber Sequence(const WriteBatch* batch);// Store the specified number as the sequence number for the start of// this batch.//设置队列编号static void SetSequence(WriteBatch* batch, SequenceNumber seq);//返回一个Slice，用来访问内部数据的static Slice Contents(const WriteBatch* batch) { return Slice(batch->rep_); }//返回rep_里的具体的长度static size_t ByteSize(const WriteBatch* batch) { return batch->rep_.size(); }//赋值操作static void SetContents(WriteBatch* batch, const Slice& contents);//插入操作，把batch的内容写到memtable里面static Status InsertInto(const WriteBatch* batch, MemTable* memtable);//合并操作，直接把src合并到dst上去static void Append(WriteBatch* dst, const WriteBatch* src);
};} // namespace leveldb
关于前面的Count，SetCount等函数我们就不说了，就是简单的返回一个值的操作。
比较重要的有两个，一个是InsertInto函数，另一个是Append函数。
//虽然是InsertInto操作，但是这里确切将是开始执行写操作（包括插入删除)
Status WriteBatchInternal::InsertInto(const WriteBatch* b, MemTable* memtable) {MemTableInserter inserter;inserter.sequence_ = WriteBatchInternal::Sequence(b);inserter.mem_ = memtable;return b->Iterate(&inserter);
}
关于这个InsertInto函数，我们会声明一个插入器，把队列的编号和memtable给他，然后调用 b->Iterate(&inserter);，我们现不管这个，而是去考虑一个基础的操作类。
//定义了一个基础操作类，有插入和删除两个操作class LEVELDB_EXPORT Handler {public:virtual ~Handler();virtual void Put(const Slice& key, const Slice& value) = 0;virtual void Delete(const Slice& key) = 0;};
这个Handler定义了基础的put和delete操作，MemTableInserter就是基于这个来的。关于这些抽象的接口我们可以先不管，而是去看看Iterate函数。
这个内容其实比较简单，就是把我们存到WriteBatch里的操作给逐一解析出来，解析出来之后根据那个一个字节的type来选择调用put还是delete操作。
/*
这一段写的比较简单
就如把存起来的操作给依次实现出来，用一个handler去做Put，Delete操作等
*/
Status WriteBatch::Iterate(Handler* handler) const {Slice input(rep_);if (input.size() < kHeader) {return Status::Corruption("malformed WriteBatch (too small)");}//注意这里input的remove不是真的remove，只是指针前移了而已。//实际的内容在rep_里input.remove_prefix(kHeader);Slice key, value;int found = 0; //已经搞了的操作数while (!input.empty()) {found++; //操作数+1，然后开始解析这次的操作char tag = input[0]; //取出来标记符，看看是kTypeValue还是kTypeDeletioninput.remove_prefix(1);switch (tag) {case kTypeValue:if (GetLengthPrefixedSlice(&input, &key) &&GetLengthPrefixedSlice(&input, &value)) {handler->Put(key, value);} else {return Status::Corruption("bad WriteBatch Put");}break;case kTypeDeletion:if (GetLengthPrefixedSlice(&input, &key)) {handler->Delete(key);} else {return Status::Corruption("bad WriteBatch Delete");}break;default:return Status::Corruption("unknown WriteBatch tag");}}//最后的found应该和我们Count出来的结果一致if (found != WriteBatchInternal::Count(this)) {return Status::Corruption("WriteBatch has wrong count");} else {return Status::OK();}
}
这里中间有一个函数GetLengthPrefixedSlice，是用来把input开头存放的数字放到len里面，然后依据len来解析出来后续的key或者value，把内容放到result里面，input会去除开头的数字和内容。
//这里是把input开头解析的数字放到了result里面，input会去除result的部分。
// 按照这里的写法，Slice的开头存放的是长度。
// 如果返回的false，有种情况会是解析的数字过大，而Slice的实际长度却不够。
// 但是如果Slice设置的没有问题的情况下，应该不会发生这种问题。
// 成功了返回true，否则返回false
bool GetLengthPrefixedSlice(Slice* input, Slice* result) {uint32_t len;if (GetVarint32(input, &len) && input->size() >= len) {*result = Slice(input->data(), len);input->remove_prefix(len);return true;} else {return false;}
}
里面有个函数GetVarint32我们下一节会去讲它。
另外关于WriteBatchInternal的另一个函数Append，内容也比较简单，注释在里面了。
void WriteBatchInternal::Append(WriteBatch* dst, const WriteBatch* src) {SetCount(dst, Count(dst) + Count(src));assert(src->rep_.size() >= kHeader);// 这里就是直接把src的内容（去掉了header)给加了进来。上面的assert就是纯防止第二个参数搞成了负数罢了。dst->rep_.append(src->rep_.data() + kHeader, src->rep_.size() - kHeader);
}
关于WriteBatch的test
其实对于这一块部分，我初步的理解也算是一个写操作的集合，后来深入了解其实不是先看源码，而是先去看了test。
其实在做CMU的时候对于自己不太了解的内容除了问AI以外，看test是一个比较方便的东西，可以比较简洁直观的看出来在做什么。
TEST(WriteBatchTest, Multiple) {WriteBatch batch;batch.Put(Slice("foo"), Slice("bar"));batch.Delete(Slice("box"));batch.Put(Slice("baz"), Slice("boo"));WriteBatchInternal::SetSequence(&batch, 100);ASSERT_EQ(100, WriteBatchInternal::Sequence(&batch));ASSERT_EQ(3, WriteBatchInternal::Count(&batch));ASSERT_EQ("Put(baz, boo)@102""Delete(box)@101""Put(foo, bar)@100",PrintContents(&batch));
}
比如这一段，我们可以看到里面放了三个操作，然后利用WriteBatchInternal去搞了一些操作。
当然这里最开始的时候也没看懂（bushi，因为这里是从memtable用迭代器去读取，所以会有一个key的顺序从小到大，这都是后话了。
postscript
这里又开了新坑，之前的CMU没有在搞了，因为感觉之前打了数据库的比赛，做CMU可能对我的帮助没有那么大了，于是选择开始看源码了，先从一个简单的开始，但愿这次不会弃坑。
 其中 L log L = sqrt n)
