本文整理自OSDI 2020 Virtual Consensus in Delos 论文演讲,探讨了分布式系统中控制面的存储系统,提出了一种基于分层抽象思想的分布式架构。其核心在于提出了一种逻辑协议层,使得物理层可以按需进行实现和移植,有点类似于单机系统中虚拟内存之于物理内存的味道。
Cmu15445 课程介绍
小引
大学时,数据库学的不是很深,现在有印象的也就 SQL、ER 图、范式、事务等使用上的寥寥概念。对于其实现上一直没有过系统性的了解,但既然走上了存储这条路,数据库知识肯定要补一下。先前,知乎上很多地方看到大家推荐 cmu15445 这门课,也早就将课程主页收藏到了文件夹,但一直没得空来看。念念不忘,必有回响,到这个假期,恰逢换工作,才有点大块的时间开个头。
大纲
简单介绍下 cmu15445 的教学大纲,该课以 Database System Concepts 为辅助教材, 讲述了数据库管理系统(DBMS)设计和实现的方方面面,包括:
- 数据模型(关系型,文档型,键值型)
- 存储模型(n-ary,decomposition,可以理解为行式、列式)
- 查询语言(sql,存储过程 stored procedures)
- 存储结构(heaps,基于日志 log-structured)
- 索引设计(排序树,哈希表)
- 事务处理(ACID,并发控制)
- 数据恢复(日志、快照)
- 执行引擎(joins,排序,聚集,优化)
- 并发架构(多核,分布式)
可以看出,内容十分翔实,课程使用一个开源的商业数据库作为案例进行讲解,以深入探讨数据库设计时,在上述各个方面进行取舍的过程。本课程十分重视编程实践,设计了一系列前后勾连但又足够简洁的代码实验。
Cmu15445 数据库系统实验一:Buffer Pool Manager
cmu15445 是一门关于数据库管理系统(DBMS)设计与实现的经典公开课。该课程以 Database System Concepts 为教材,提供随堂讲义、笔记和视频,精心准备了几个互相勾连的小实验。该课程十分注重系统设计和编程实现,用主讲教授 Andy Pavlo 的话说,这是一门可以写在简历上、并且能帮你拿到好 offer 的课程。
这个假期得空,翻出这门课程,即被其翔实的内容、精当的组织所折服。无奈时间有限,只能以实验为主线,辅以讲义和笔记,简单跟一跟。如果再有时间,就去扫下教材和视频。从实验一开始,每个实验 autograder 跑过之后,出一篇笔记,聊以备忘。 Andy Pavlo 教授建议不要公开实验代码仓库,因此文章尽量少贴代码,多写思路。
本篇是实验一,管理文件系统的页在内存中的缓存 —— buffer pool manager。
概览
实验的目标系统 BusTub 是一个面向磁盘的 DBMS,但磁盘上的数据不支持字节粒度的访问。这就需要一个管理页的中间层,但 Andy Pavlo 教授坚持不使用 mmap 将页管理权力让渡给操作系统,因此实验一 的目标便在于主动管理磁盘中的页(page)在内存中的缓存,从而,最小化磁盘访问次数(时间上)、最大化相关数据连续(空间上)。
该实验可以分解为相对独立的两个子任务:
- 维护替换策略的: LRU replacement policy
- 管理缓冲池的: buffer pool manager
两个组件都要求线程安全。
本文首先从基本概念、核心数据流总体分析下实验内容,然后分别对两个子任务进行梳理。
Golang 笔记(三):一种理解 Slice 的模型
Boltdb 源码导读(二):Boltdb 索引设计
boltdb 是市面上为数不多的纯 go 语言开发的、单机 KV 库。boltdb 基于 Howard Chu’s LMDB 项目 ,实现的比较清爽,去掉单元测试和适配代码,核心代码大概四千多行。简单的 API、简约的实现,也是作者的意图所在。由于作者精力所限,原 boltdb 已经封版,不再更新。若想改进,提交新的 pr,建议去 etcd 维护的 fork 版本 bbolt。
为了方便,本系列导读文章仍以不再变动的原 repo 为基础。该项目麻雀虽小,五脏俱全,仅仅四千多行代码,就实现了一个基于 B+ 树索引、支持一写多读事务的单机 KV 引擎。代码本身简约朴实、注释得当,如果你是 go 语言爱好者、如果对 KV 库感兴趣,那 boltdb 绝对是不可错过的一个 repo。
本系列计划分成三篇文章,依次围绕数据组织、索引设计、事务实现等三个主要方面对 boltdb 源码进行剖析。由于三个方面不是完全正交解耦的,因此叙述时会不可避免的产生交织,读不懂时,暂时略过即可,待有全貌,再回来梳理。本文是第一篇, boltdb 数据组织。
概览
数据库中常用的索引设计有两种,一个是 B+ 树,一个是 LSM-tree。B+ 树比较经典,比如说传统单机数据库 mysql 就是 B+ 树索引,它对快速读取和范围查询(range query)比较友好。 LSM-tree 是近年来比较流行的索引结构,Bigtable、LevelDB、RocksDB 都有它的影子;前面文章也有提到,LSM-tree 使用 WAL 和多级数据组织以牺牲部分读性能,换来强悍的随机写性能。因此,这也是一个经典的取舍问题。
BoltDB 在逻辑上以桶来组织数据,一个桶可以看做一个命名空间,是一组 KV 对的集合,和对象存储的桶概念类似。每个桶对应一棵 B+ 树,命名空间是可以嵌套的,因此 BoltDB 的 Bucket 间也是允许嵌套的。在实现上来说,子 bucket 的 root node 的 page id 保存在父 bucket 叶子节点上实现嵌套。
每个 db 文件,是一组树形组织的 B+ 树。我们知道对于 B+ 树来说,分支节点用于查找,叶子节点存数据。
- 顶层 B+ 树,比较特殊,称为 root bucket,其所有叶子节点保存的都是子 bucket B+ 树根的 page id 。
- 其他 B+ 树,不妨称之为 data bucket,其叶子节点可能是正常用户数据,也可能是子 bucket B+ 树根的 page id。
相比普通 B+ 树,boltdb 的 B+ 树有几点特殊之处:
- 节点的分支个数不是一个固定范围,而是依据其所存元素大小之和来限制的,这个上限即为页大小。
- 其分支节点(branch node)所存分支的 key,是其所指向分支的最小 key。
- 所有叶子节点并没有通过链表首尾相接起来。
- 没有保证所有的叶子节点都在同一层。
在代码组织上,boltdb 索引相关的源文件如下:
- bucket.go:对 bucket 操作的高层封装。包括kv 的增删改查、子bucket 的增删改查以及 B+ 树拆分和合并。
- node.go:对 node 所存元素和 node 间关系的相关操作。节点内所存元素的增删、加载和落盘,访问孩子兄弟元素、拆分与合并的详细逻辑。
- cursor.go:实现了类似迭代器的功能,可以在 B+ 树上的叶子节点上进行随意游走。
本文主要分三部分,由局部到整体来一步步揭示 BoltDB 是如何进行索引设计的。首先会拆解树的基本单元,其次剖析 bucket 的遍历实现,最后分析树的生长和平衡过程。
Boltdb 源码导读(一):Boltdb 数据组织
boltdb 是市面上为数不多的纯 go 语言开发的、单机 KV 库。boltdb 基于 Howard Chu’s LMDB 项目 ,实现的比较清爽,去掉单元测试和适配代码,核心代码大概四千多行。简单的 API、简约的实现,也是作者的意图所在。由于作者精力所限,原 boltdb 已经封版,不再更新。若想改进,提交新的 pr,建议去 etcd 维护的 fork 版本 bbolt。
为了方便,本系列导读文章仍以不再变动的原 repo 为基础。该项目麻雀虽小,五脏俱全,仅仅四千多行代码,就实现了一个基于 B+ 树索引、支持一写多读事务的单机 KV 引擎。代码本身简约朴实、注释得当,如果你是 go 语言爱好者、如果对 KV 库感兴趣,那 boltdb 绝对是不可错过的一个 repo。
本系列计划分成三篇文章,依次围绕数据组织、索引设计、事务实现等三个主要方面对 boltdb 源码进行剖析。由于三个方面不是完全正交解耦的,因此叙述时会不可避免的产生交织,读不懂时,暂时略过即可,待有全貌,再回来梳理。本文是第一篇, boltdb 数据组织。
引子
一个存储引擎最底层的构成,就是处理数据在各种物理介质(比如在磁盘上、在内存里)上的组织。而这些数据组织也体现了该存储引擎在设计上的取舍哲学。
在文件系统上,boltdb 采用页(page)的组织方式,将一切数据都对齐到页;在内存中,boltdb 按 B+ 树组织数据,其基本单元是节点(node),一个内存中的树节点对应文件系统上一个或者多个连续的页。boltdb 就在数据组织上就只有这两种核心抽象,可谓设计简洁。当然,这种简洁必然是有代价的,后面文章会进行详细分析。
本文首先对节点和页的关系进行总体说明,然后逐一分析四种页的格式及其载入内存后的表示,最后按照 db 的生命周期串一下 db 文件的增长过程以及载入内存的策略。
漫谈 LevelDB 数据结构(二):布隆过滤器(Bloom Filter)
早对 LevelDB 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传。如果你对存储感兴趣、如果你想优雅使用C++、如果你想学习如何架构项目,都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。
看过一遍如果不输出点什么,以我的记性,定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙,但又不想走寻常路:从架构概览说起,以模块分析做合。读代码的这些天,一直在盘算从哪下笔比较好。在将将读完之时,印象最深的反而是 LevelDB 的各种精妙的数据结构:贴合场景、从头构建、剪裁得当、代码精到。不妨, LevelDB 系列就从这些边边角角的小构件开始吧。
本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构,分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第二篇,Bloom Filter。
引子
LevelDB 是一个单机的 KV 存储引擎,但没有使用传统的平衡查找树以平衡读写性能,而是使用了 LSM-tree 结构来组织数据,牺牲部分读性能来换取较高的写吞吐。下面来对照一张图来介绍 LSM-tree 在不同存储介质上的组织方式。
LevelDB 将数据分为两大部分,分别存放在内存和文件系统中。主要数据模块包括 WAL log,memtable,immutable memtable,sstable。按照数据流向依次如下:
- 当 LevelDB 收到一个写入请求
put(k, v)
,会首先将其操作日志追加到日志文件(WAL)中,以备节点意外宕机恢复。 - 写完 WAL 后,LevelDB 将该条 kv 插入内存中的查找结构:memtable。
- 在 memtable 积累到一定程度后,会 rotate 为一个只读 memtable,即 immutable memtable;同时生成一个新的 memtable 以供写入。
- 当内存有压力后,会将 immutable memtable 顺序写入文件系统,生成一个 level0 层的 sstable(sorted strings table) 文件。该过程称为一次 minor compaction。
- 由于查询操作需要按层次遍历 memtable、immutable 和 sstable。当 sstable 文件生成的越来越多之后,查询性能必然越来越差,因此需要将不同的 sstable 进行归并,称为 major compaction。
LevelDB 层次组织
所有在文件系统中的 sstable 文件,被 LevelDB 在逻辑上组织成多个层次(一般是 7层),并且满足以下性质:
- 层次越大说明其数据写入越早,即先往上层进行“放”(minor compaction),上层“满”(达到容量限制)之后“溢”(major compaction)到下层进行合并。
- 每层文件总大小都有一定限制,并且成指数级增长。比如 level0 层文件总大小上限为10MB,level1 层为100MB,依次类推,最高层(level6层)没有限制。
- 由于 level0 每个 sstable 文件都是直接由 memtable 落盘而来, 因此多个 sstable 文件的 key 范围可能会有交叠。而其他层的多个 sstable 文件则通过一些规则保证没有交叠。
对于 LevelDB 的一次读取操作,需要首先去 memtable、immutable memtable 查找,然后依次去文件系统中各层查找。可以看出,相比写入操作,读取操作实在有点效率低下。我们这种客户端进行一次读请求,进入系统后被变成多次读请求的现象为读放大。
为了减小读放大,LevelDB 采取了几方面措施:
- 通过 major compaction 尽量减少 sstable 文件
- 使用快速筛选的办法,快速判断 key 是否在某个 sstable 文件中
而快速判断某个 key 是否在某个 key 集合中,LevelDB 用的正是布隆过滤器。当然,布隆过滤器只能快速判断 key 一定不在某个 sstable 中,从而在层层查找时跳过某些 sstable 。之后会详述原因,此处按下不表。
Golang 笔记(二):Context 源码剖析
概述
Context 是 Go 中一个比较独特而常用的概念,用好了往往能事半功倍。但如果不知其然而滥用,则往往变成 “为赋新词强说愁”,轻则影响代码结构,重则埋下许多bug。
Golang 使用树形派生的方式构造 Context,通过在不同过程 [1] 中传递 deadline 和 cancel 信号,来管理处理某个任务所涉及到的一组 goroutine 的生命周期,防止 goroutine 泄露。并且可以通过附加在 Context 上的 Value 来传递/共享一些跨越整个请求间的数据。
Context 最常用来追踪 RPC/HTTP 等耗时的、跨进程的 IO 请求的生命周期,从而让外层调用者可以主动地或者自动地取消该请求,进而告诉子过程回收用到的所有 goroutine 和相关资源。
Context 本质上是一种在 API 间树形嵌套调用时传递信号的机制。本文将从接口、派生、源码分析、使用等几个方面来逐一解析 Context。
漫谈 LevelDB 数据结构(一):跳表(Skip List)
早对 LevelDB 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传。如果你对存储感兴趣、如果你想优雅使用C++、如果你想学习如何架构项目,都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。
看过一遍如果不输出点什么,以我的记性,定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙,但又不想走寻常路,从架构概览说起,以模块分析做合。读代码的这些天,一直在盘算从哪下笔比较好。在将将读完之时,印象最深的反而是 LevelDB 的各种精妙的数据结构:贴合场景、从头构建、剪裁得当、代码精到。不妨, LevelDB 系列就从这些边边角角的小构件开始吧。
本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构,分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第一篇,Skip List。
需求
LevelDB 是一个单机的 KV 存储引擎。KV 引擎在本质上可认为只提供对数据条目(key,val) Put(key, val), Get(key) val, Delete(key)
操作的三个接口。而在实现上,LevelDB 在收到删除请求时不会真正删除数据,而是为该 Key 写一个特殊标记,以备读取时发现该 Key 不存在,从而将 Delete
转为 Put
,进而将三个接口简化为两个。砍完这一刀后,剩下的就是在 Put
和 Get
间进行性能取舍,LevelDB 的选择是:**牺牲部分 Get
性能,换取强悍 Put
性能,再极力优化 Get
**。
我们知道,在存储层次体系(Memory hierarchy)中,内存访问远快于磁盘,因此 LevelDB 为了达到目标做了以下设计:
- 写入(Put):让所有写入都发生在内存中,然后达到一定尺寸后将其批量刷磁盘。
- 读取(Get):随着时间推移,数据不断写入,内存中会有一小部分数据,磁盘中有剩余大部分数据。读取时,如果在内存中没命中,就需要去磁盘查找。
为了保证写入性能,同时优化读取性能,需要内存中的存储结构能够同时支持高效的插入和查找。
之前听说 LevelDB 时,最自然的想法,以为该内存结构(memtable)为是平衡树,比如红黑树、AVL 树等,可以保证插入和查找的时间复杂度都是 lg(n),看源码才知道用了跳表。相比平衡树,跳表优势在于,在保证读写性能的同时,大大简化了实现。
此外,为了将数据定期 dump 到磁盘,还需要该数据结构支持高效的顺序遍历。总结一下 LevelDB 内存数据结构(memtable)需求点:
- 高效查找
- 高效插入
- 高效顺序遍历
Amazon 针对小对象的分布式键值存储——Dynamo
概览
Dynamo 是一个高可用的 KV 存储系统。为了保证高可用和高性能,Dynamo 采用了最终一致性模型,它对开发人员提供一种新型 API,使用了版本机制,并通过用户侧辅助解决冲突。Dynamo 目标是提供不间断的服务,同时保证性能和可扩展性。由于亚马逊大量采用了去中心化、高度解耦微服务架构,因此对微服务状态的存储系统的可用性要求尤其高。
S3 (Simple Storage Service)是 Amazon 另一款有名的存储服务,虽然也可以理解为 KV 存储,但它和 Dynamo 的目标场景并不一致。S3 是面向大文件的对象存储服务,主要存储二进制文件,不提供跨对象的事务。而 Dynamo 是一款面向小文件的文档存储服务,主要存储结构化数据(如 json),并且可以对数据设置索引,且支持跨数据条目的事务。
相对于传统的关系型数据库,Dynamo 可以认为是只提供主键索引,从而获取更高的性能和更好的扩展性。
为了实现可扩展性和高可用性,并保证最终一致性,Dynamo 综合使用了以下技术:
- 使用一致性哈希对数据进行分片(partition)和备份(replicate)。
- 使用版本号机制(Vector Clock)处理数据一致性问题。
- 使用多数票(Quorum)和去中心化同步协议来维持副本间的一致性(Merkle Tree)。
- 基于 Gossip Protocol 进行失败检测和副本维持。
实现上来说,Dynamo 有以下特点:
- 完全去中心化,没有中心节点,所有节点关系对等。
- 采用最终一致性,使用版本号解决冲突,甚至要求用户参与解决冲突。
- 使用哈希值进行数据分片,组织数据分布,均衡数据负载。
让我们荡起双桨
儿时初学“让我们荡起双桨”,只感觉旋律朗朗;年岁稍长,偶尔哼起,三言两语,味出千万意境;后来,求学帝都,游北海,正是“湖面倒映着美丽的白塔,四周环绕着绿树红墙”,光阴荏苒,不变的是文字的生命力。
歌词为乔羽先生所做,很多脍炙人口的名作皆出自其手:《我的祖国》、《难忘今宵》、《爱我中华》。词分三段,层层递进。第一段写划船之景,寥寥几句,首尾勾连、推近及远、勾勒出四合景象。第二段写欢快之情,童真昂扬,心情轻快,描绘出饱满的童趣。第三段继而升华,设问如此美景、如此生活、如此时代,如何得来?尔后戛然而止,语已尽而意无穷。