LevelDB阅读笔记-Compaction流程
Compaction是所有LSM-Tree存储引擎必要的操作，Compaction会持续性地将当前的数据库中的SST文件按照一定规则进行合并，来回收一些无效的数据空间(例如对同一个key的多次更新操作，只需要保留最近的一次结果即可)；同时compaction操作对于读性能也有一定的提升，尤其是在LSM-Tree的布局采用tiering的数据放置策略时，一个读操作可能需要在多个sorted run中进行查找，导致较高的读放大；此时compaction会将多个sorted run合并为一个，减少额外的写操作。Compaction也是LSM-Tree中影响性能的一个重要因素，因此有许多针对Compaction的优化策略。这里我们只着眼于LevelDB的compaction实现，因为它足够简单直接。
数据库元数据VersionSet在正式介绍LevelDB的Compaction流程之前，有必要先介绍一下整个DB与元数据管理相关的数据结构VersionSet。 无论是进行Compaction还是对Level0的SST进行刷盘，这些操作都涉及到文件的创建和删除。VersionSet的作用就是记录这 ...
LevelDB阅读笔记-SSTable
为了保证数据的持久化, LevelDB最终会将memtable中的数据写入到底层文件中。写入的文件被称为SSTable文件，即Sorted String Table文件。这类文件包含了多个经过序列化的key-value条目，以及index block，filter block等元数据用于快速定位指定的键值对。SSTable文件需要同时支持顺序写入以及随即读写的能力。本文将介绍LevelDB中的SST文件，包括文件的格式以及文件是怎样被创建和使用的。
SSTable File Format关于LevelDB的SSTable文件的数据布局，网上有很多介绍的文章了，这里用一幅示意图来解释：
整个SSTable文件被划分为了多个block，而不同的Block有不同的作用。主要的Block类型如下：
Data Block: 用于存储多条经过序列化的key-value数据。
Filter Block: 用于存储该SSTable中所有key-value数据的过滤器，可以快速判断一个key是否在该SST中
MetaIndex Block: 存储了Filter Block的位置，是一个BlockHa ...
Transactional Information Systems: Syntax and Semantics of Transaction
OverviewThis article is all about the fomulation of an important concept arising in computer science, the Transaction. Transaction is usually considered to be a set of operations that maintain the ACID properties, which is an useful abtraction for programmers to write reasonable and effective code. In the past a few decades, various transactional algorithms were invented for achiving efficiency. However, it’s hard to reason about the correctness of a transactional algorithm because of the compl ...
TinyKV Course: RaftStore执行流程
Overview在前一节我们描述了raftstore的结构，一个raftstore可以将其看作是由ticker module, storage module, raft module等几个部分构成。在之前我们已经解析了其中的ticker module和storage module的代码，接下来我们将关注raft module这一核心部分，重点关注整个raft store结构体是怎样在外部消息的驱动下执行起来的。
首先我们回顾一下整个raftstore的结构示意图：
我们可以看到raftmodule的核心组成部分是router, peer, raftworker等几个结构体。其中peer代表了运行在该节点上的一个raft instance，它是对raft算法模块的RawNode的一层封装。RaftWorker是驱动整个系统状态前进的核心，可以将其理解为一个永远执行下去的线程。
Raft Encapsulation: raft peerpeer是对一个raft对象的封装，multi-raft中一个物理节点需要运行多个raft instance，而这些raft instance的状态必须 ...
TinyKV Course: RaftStore源码解析
TinyKV RaftStore源码解析TinyKV Course的Lab2B要求我们基于Raft Module实现一个key-value存储服务，在涉及到的模块中最重要的就是raftstore。 因此我们先对其相关的代码进行阅读，本文是代码阅读的总结，可能会随着后面阅读的深入继续更新。
Overviewraftstore是TinyKV中Raft存储的核心部分，它将raft::RawNode， storage, Transport等部分拼接在了一起。并且由于TiKV采用的是Multi-Raft, 一台服务机器上可能会运行多个raft peer, 这些不同region的raft peer都被同一个raftstore所管理。
上图展示了raftstore大概的结构，这里并没有展示一个raftstore结构体中的所有数据成员，而是选择了一些较为关键的部分。包括如下部分：
router: 由于一个raftstore中可能运行着多个raft peer,所以raftstore需要对收到的message按照region id进行分发，每个raft peer独立地处理自己这个raft region ...
SICP Chapter3: Assignment and local state
Assignment and State在之前的讨论中，我们并没有引入赋值这种在命令式语言中被广泛使用的语句，这是因为赋值会使得Lisp中的代换模型(Substitution Model)失效。在代换模型中，Lisp实现的是存粹的数学上的函数，也就是：给定相同的输入，保证会有相同的输出。这使得一个表达式可以通过将其中的函数调用替换为函数体，来求得最后的结果，这种代换并不会改变程序的语义，因为无论在何时对函数求值，得到的都是相同的结果。这种将表达式替换为值而不修改程序语义的特性，被称为reference transparency.
引入赋值的原因是我们想用编程世界来模拟现实世界，而不仅仅只是利用计算机来计算数学上的函数：数学上的函数，代表的是客观存在的真理，例如$since(\pi/2)=1$，因此它们可以很方便地利用代换模型计算；而现实世界的事物，增加了时间这一维度：一个函数在不同时刻的返回值可能会有所不同，因此只用代换模型模拟现实世界是不大可能的。
面向对象编程就是模拟现实世界的一种编程范式：现实世界的一个对象对应于编程世界中的一个“对象”。与之对应的是，我们也想模拟对象随时间的变 ...
Percolator: Google's transactional system
Percolator: Google’s transactional systemOverview本文介绍Google的上一代分布式事务系统：Percolator。Percolator首次出现在Google于2010年OSDI发表的论文：Large-scale Incremental Processing Using Distributed Transactions and Notifications 中。Google基于BigTable提供的单行事务语义实现了一个跨行，跨表的事务系统，称为Percolator，该系统基于2PC，支持Snapshot Isolation的隔离级别。TiDB在事务方面的实现也是基于Percolator模型，但是进行了一些优化，例如增加了悲观锁和Async commit。
Background & Motivation在21世纪的第一个十年，Google陆续发表了GFS, BigTable, MapReduce, Spanner等系统用以支持各种大数据应用。Percolator也是在这样的背景下诞生的，正如论文原文的描述：
Within Goog ...
XRP: In-Kernel Storage Functions with eBPF阅读笔记
XRP: In-Kernel Storage Functions with eBPF阅读笔记Introduction本文将介绍一篇OSDI2022年的论文： XRP: In-Kernel Storage Functions with eBPF,在这篇论文中，作者利用Linux Kernel提供的BPF(Berkeley Packet Filter)机制将用户态程序的部分逻辑移动到Device Driver层次，从而减轻了传统的Linux Storage软件栈的开销，提升了一些存储系统在Linux系统上的性能表现。
Background & MotivationLinux系统的存储软件栈Linux系统的存储软件栈自上而下包括了：用户态程序，文件系统层（又分为虚拟文件系统与硬件文件系统），块设备层(BIO Layer), 设备驱动层(Device Driver Layer)以及最后的存储设备层(Device Layer)。上述层次中，除了设备层之外的层次都由软件代码构成，为上层提供一定的抽象接口。例如文件系统向用户程序提供了文件这一抽象概念；块设备为文件系统提供了统一的硬件线性地 ...
最短路径算法基础
最短路径算法基础本文介绍四种最短路径算法以及其对应的模板。最短路径算法是十分基础的算法，一方面，一些题目直接需要我们求图中两点的最短路径；另一方面，一些题目也可以通过先建模成图，然后再调用最短路径算法解决。
本文要介绍的最短路径算法包括以下几种：
算法
限制
复杂度
Dijkstra算法
图中无负权边,单源
$O(n^2)$
Bellman-Ford算法
无限制，单源
$O(mn)$
SPFA算法
无限制，单源
一般$O(m)$ 最坏$O(mn)$
Floyd算法
多源
$O(n^3)$
Dijkstra算法Dijkstra算法采用了一种贪心的算法，它维护一个当前已经求的最短路的集合，然后不断向其中添加点，直到所有点都被添加进去。而每次添加点的方式就是选择当前距离源点最近的点（贪心），而当一个点被加入了之后，就用这个点来更新其他与该点相连的点到源点的距离。
在代码实现上如下所示，我们使用二维矩阵g[N][N]来代表一个图，g[i][j]表示有向图中点i到点j的距离, 一共有n个点。
void dijkstra() {
std::mems ...
LevelDB阅读笔记-Env
LevelDB与操作系统交互接口：EnvLevelDB中的Env类是一个上层逻辑与操作系统进行交互的接口，由于LevelDB以文件方式对数据进行持久化，并且需要读取文件来完成一次Get操作，上述过程都涉及到对文件的操作。但不同操作系统的文件系统调用接口不同，因此LevelDB定义了Env类来屏蔽上述操作系统的实现差异，向上层的LevelDB逻辑提供统一的接口。
上图表示了Env在整个系统架构中位置，包括了以下几部分：
定义了SequentialFile等几类具有不同读写行为的文件接口。
提供了和文件系统交互的其他接口，例如对文件重命名，创建文件夹等，上图未收录这部分。
提供了和线程控制相关的接口，例如Schedule用于向后台线程传递一个执行的函数。
抽象基类EnvEnv是一个抽象基类，它屏蔽了操作系统之间的实现差异，并向上层的leveldb逻辑提供统一的操作接口。总体上看，其接口可分为两类：文件系统相关与线程调度相关。
文件系统相关接口文件抽象LevelDB定义了三类不同的文件类型，即三种文件抽象基类，用于表示具有不同功能的文件抽象。
RandomAccessFile, ...
LevelDB阅读笔记-Memtable
LevelDB中的MemTable在LevelDB中，MemTable是一个内存数据结构，它被用于暂存写操作，并在合适的时候转换为immutable的memtable，最后转为SSTable文件写入磁盘。MemTable实际上只是一个提供了读写操作的接口，它负责将外界的key-value数据封装，实际的数据存储和查询都是由内部的SkipList索引来完成的，因此我们将着重分析SkipList的源码。
MemTableMemTable类包含了以下数据成员和接口：
class MemTable {
Iterator* NewIterator();
void Add(SequenceNumber seq, ValueType type, const Slice& key,
const Slice& value);
bool Get(const LookupKey& key, std::string* value, Status* s);
private:
struct KeyComparator {
...