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 {
...