排序

时间复杂度、稳定性等

由源代码到可执行文件

简介

C或者C++的代码变为一个可执行文件主要需要经过以下几个阶段，1)预编译，2)编译，3)汇编，4)链接。接下来我会分别介绍一下这几个阶段所完成的工作。

Raft

Intro

共识算法让一组共同协作的计算机在其中一部分失效后也能继续工作下去，因此共识算法被应用于大规模的可靠软件系统中。在之前该领域使用的大都是Paxos，或者是在Paxos的影响之下设计出来的，但是Paxos较为难理解，因而更难实现，因而有人提出了Raft。正如其论文标题所述，该算法的一个首要目标就是容易理解。

接下来先简要介绍一下这个共识算法，该算法的主要流程可以分为两个部分，第一个部分就是领导人的选举，第二部分就是让leader负责接受用户请求并将自己的日志发送给所有的follower，让follower的日志与自己保持一致，同时当某个日志已经被复制到大多数机器上时，leader会负责通知所有follower。

LevelDB源码分析

Intro

前两篇博客主要注重于LevelDB内部结构及Compaction的机制的分析，该篇博客主要介绍LevelDB对外提供的数个接口，及这些接口的实现，包括这些接口是如何与前述截至相互作用的。

DBImpl::Put

DBImpl::Put直接使用了DB::Put的默认实现，即直接构建一个仅有一个Put操作的WriteBatch，然后利用Write来完成操作。

DBImpl::Delete

DBImpl::Delete的实现与DBImpl::Put类似，直接构建一个仅有一个删除操作的WriteBatch，然后让Write完成其余工作。

LevelDB源代码分析

Intro

这一篇主要介绍LevelDB的Compaction的过程。在上一篇我们看到LevelDB在打开数据库时会调用MaybeScheduleCompaction这个函数，该函数可能会在单独的线程调度Compaction。接下来我们首先介绍一下有哪些操作可以触发LevelDB的Compaction之后在介绍Compaction的流程。

在LevelDB中Compaction的触发可以大致分为两类，第一类是用户调用LevelDB的CompactRange接口来进行底层数据的压缩，第二类是用户调用Get/Write等操作时，随着LevelDB中某一个Level的文件大小或数量或者文件查找次数超过一定阈值来触发Compaction。当Compaction被触发后会统一调用MaybeScheduleCompaction，接下来逐行分析该函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void DBImpl::MaybeScheduleCompaction() {
    mutex_.AssertHeld();
    if (background_compaction_scheduled_) {
        // 已有线程正在进行Compaction
    } else if (shutting_down_.Acquire_Load()) {
        // 正在删除数据库
    } else if (!bg_error_.ok()) {
        // 过去Compaction的过程存在错误
    } else if (imm_ == nullptr && manual_compaction_ == nullptr &&
            !versions_->NeedsCompaction()) {
        // 现在不需要进行Compaction
    } else {
        background_compaction_scheduled_ = true;
        // 进行Compaction，最终调用的是BackgroundCall
        env_->Schedule(&DBImpl::BGWork, this);
    }
}

LevelDB源码分析

Intro

我们从LevelDB给定的示例入手对LevelDB的源代码进行分析，本篇仅分析其中的Open函数，该函数用于打开一个数据库。

1
2
3
4
5
6
7
8
9

leveldb::DB* db;  
leveldb::Options options;  
options.create_if_missing = true;  
leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);  
std::string value;  
leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);  
if (s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value);  
if (s.ok()) s = db->Delete(leveldb::WriteOptions(), key1);  
delete db;

Hi~