分布式系统,程序语言,算法设计

cmu15445 是一门关于数据库管理系统(DBMS)设计与实现的经典公开课。该课程以 Database System Concepts 为教材,提供随堂讲义、笔记和视频,精心准备了几个互相勾连的小实验。该课程十分注重系统设计和编程实现,用主讲教授 Andy Pavlo 的话说,这是一门可以写在简历上、并且能帮你拿到好 offer 的课程。

这个假期得空,翻出这门课程,即被其翔实的内容、精当的组织所折服。无奈时间有限,只能以实验为主线,辅以讲义笔记,简单跟一跟。如果再有时间,就去扫下教材视频。从实验一开始,每个实验 autograder 跑过之后,出一篇笔记,聊以备忘。 Andy Pavlo 教授建议不要公开实验代码仓库,因此文章尽量少贴代码,多写思路。

本篇是实验一,管理文件系统的页在内存中的缓存 —— buffer pool manager。

概览

实验的目标系统 BusTub 是一个面向磁盘的 DBMS,但磁盘上的数据不支持字节粒度的访问。这就需要一个管理页的中间层,但 Andy Pavlo 教授坚持不使用 mmap 将页管理权力让渡给操作系统,因此实验一 的目标便在于主动管理磁盘中的页(page)在内存中的缓存,从而,最小化磁盘访问次数(时间上)、最大化相关数据连续(空间上)。

该实验可以分解为相对独立的两个子任务:

  1. 维护替换策略的: LRU replacement policy
  2. 管理缓冲池的: buffer pool manager

两个组件都要求线程安全。

本文首先从基本概念、核心数据流总体分析下实验内容,然后分别对两个子任务进行梳理。

阅读全文 »

概述

Golang 中 slice 极似其他语言中数组,但又有诸多不同,因此容易使初学者产生一些误解,并在使用时不易察觉地掉进各种坑中。本篇小文,首先从 Go 语言官方博客出发,铺陈官方给出的 slice 的相关语法;其次以图示的方式给出一种理解 slice 的模型;最后再总结分析一些特殊的使用情况,以期在多个角度对 slice 都有个更清晰侧写。

如不愿看繁琐叙述过程,可直接跳到最后小结看总结。

go-slice-view-derive.png

阅读全文 »

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+ 树来说,分支节点用于查找,叶子节点存数据。

  1. 顶层 B+ 树,比较特殊,称为 root bucket,其所有叶子节点保存的都是子 bucket B+ 树根的 page id 。
  2. 其他 B+ 树,不妨称之为 data bucket,其叶子节点可能是正常用户数据,也可能是子 bucket B+ 树根的 page id。

boltdb-buckets-organised.png

相比普通 B+ 树,boltdb 的 B+ 树有几点特殊之处:

  1. 节点的分支个数不是一个固定范围,而是依据其所存元素大小之和来限制的,这个上限即为页大小。
  2. 其分支节点(branch node)所存分支的 key,是其所指向分支的最小 key。
  3. 所有叶子节点并没有通过链表首尾相接起来。
  4. 没有保证所有的叶子节点都在同一层。

在代码组织上,boltdb 索引相关的源文件如下:

  1. bucket.go:对 bucket 操作的高层封装。包括kv 的增删改查、子bucket 的增删改查以及 B+ 树拆分和合并。
  2. node.go:对 node 所存元素和 node 间关系的相关操作。节点内所存元素的增删、加载和落盘,访问孩子兄弟元素、拆分与合并的详细逻辑。
  3. cursor.go:实现了类似迭代器的功能,可以在 B+ 树上的叶子节点上进行随意游走。

本文主要分三部分,由局部到整体来一步步揭示 BoltDB 是如何进行索引设计的。首先会拆解树的基本单元,其次剖析 bucket 的遍历实现,最后分析树的生长和平衡过程。

阅读全文 »

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 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传。如果你对存储感兴趣、如果你想优雅使用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.png

LevelDB 将数据分为两大部分,分别存放在内存和文件系统中。主要数据模块包括 WAL log,memtable,immutable memtable,sstable。按照数据流向依次如下:

  1. 当 LevelDB 收到一个写入请求 put(k, v) ,会首先将其操作日志追加到日志文件(WAL)中,以备节点意外宕机恢复。
  2. 写完 WAL 后,LevelDB 将该条 kv 插入内存中的查找结构:memtable。
  3. 在 memtable 积累到一定程度后,会 rotate 为一个只读 memtable,即 immutable memtable;同时生成一个新的 memtable 以供写入。
  4. 当内存有压力后,会将 immutable memtable 顺序写入文件系统,生成一个 level0 层的 sstable(sorted strings table) 文件。该过程称为一次 minor compaction。
  5. 由于查询操作需要按层次遍历 memtable、immutable 和 sstable。当 sstable 文件生成的越来越多之后,查询性能必然越来越差,因此需要将不同的 sstable 进行归并,称为 major compaction。

LevelDB 层次组织

所有在文件系统中的 sstable 文件,被 LevelDB 在逻辑上组织成多个层次(一般是 7层),并且满足以下性质:

  1. 层次越大说明其数据写入越早,即先往上层进行“放”(minor compaction),上层“满”(达到容量限制)之后“溢”(major compaction)到下层进行合并。
  2. 每层文件总大小都有一定限制,并且成指数级增长。比如 level0 层文件总大小上限为10MB,level1 层为100MB,依次类推,最高层(level6层)没有限制。
  3. 由于 level0 每个 sstable 文件都是直接由 memtable 落盘而来, 因此多个 sstable 文件的 key 范围可能会有交叠。而其他层的多个 sstable 文件则通过一些规则保证没有交叠。

对于 LevelDB 的一次读取操作,需要首先去 memtable、immutable memtable 查找,然后依次去文件系统中各层查找。可以看出,相比写入操作,读取操作实在有点效率低下。我们这种客户端进行一次读请求,进入系统后被变成多次读请求的现象为读放大

为了减小读放大,LevelDB 采取了几方面措施:

  1. 通过 major compaction 尽量减少 sstable 文件
  2. 使用快速筛选的办法,快速判断 key 是否在某个 sstable 文件中

而快速判断某个 key 是否在某个 key 集合中,LevelDB 用的正是布隆过滤器。当然,布隆过滤器只能快速判断 key 一定不在某个 sstable 中,从而在层层查找时跳过某些 sstable 。之后会详述原因,此处按下不表。

阅读全文 »

go-context-tree-construction.png

概述

Context 是 Go 中一个比较独特而常用的概念,用好了往往能事半功倍。但如果不知其然而滥用,则往往变成 “为赋新词强说愁”,轻则影响代码结构,重则埋下许多bug。

Golang 使用树形派生的方式构造 Context,通过在不同过程 [1] 中传递 deadline 和 cancel 信号,来管理处理某个任务所涉及到的一组 goroutine 的生命周期,防止 goroutine 泄露。并且可以通过附加在 Context 上的 Value 来传递/共享一些跨越整个请求间的数据。

Context 最常用来追踪 RPC/HTTP 等耗时的、跨进程的 IO 请求的生命周期,从而让外层调用者可以主动地或者自动地取消该请求,进而告诉子过程回收用到的所有 goroutine 和相关资源。

Context 本质上是一种在 API 间树形嵌套调用时传递信号的机制。本文将从接口、派生、源码分析、使用等几个方面来逐一解析 Context。

阅读全文 »

早对 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 ,进而将三个接口简化为两个。砍完这一刀后,剩下的就是在 PutGet 间进行性能取舍,LevelDB 的选择是:牺牲部分 Get 性能,换取强悍 Put 性能,再极力优化 Get

我们知道,在存储层次体系(Memory hierarchy)中,内存访问远快于磁盘,因此 LevelDB 为了达到目标做了以下设计:

  1. 写入(Put):让所有写入都发生在内存中,然后达到一定尺寸后将其批量刷磁盘
  2. 读取(Get):随着时间推移,数据不断写入,内存中会有一小部分数据,磁盘中有剩余大部分数据。读取时,如果在内存中没命中,就需要去磁盘查找。

为了保证写入性能,同时优化读取性能,需要内存中的存储结构能够同时支持高效的插入查找

之前听说 LevelDB 时,最自然的想法,以为该内存结构(memtable)为是平衡树,比如红黑树AVL 树等,可以保证插入和查找的时间复杂度都是 lg(n),看源码才知道用了跳表。相比平衡树,跳表优势在于,在保证读写性能的同时,大大简化了实现。

此外,为了将数据定期 dump 到磁盘,还需要该数据结构支持高效的顺序遍历。总结一下 LevelDB 内存数据结构(memtable)需求点:

  1. 高效查找
  2. 高效插入
  3. 高效顺序遍历
阅读全文 »

概览

Dynamo 是一个高可用的 KV 存储系统。为了保证高可用和高性能,Dynamo 采用了最终一致性模型,它对开发人员提供一种新型 API,使用了版本机制,并通过用户侧辅助解决冲突。Dynamo 目标是提供不间断的服务,同时保证性能和可扩展性。由于亚马逊大量采用了去中心化、高度解耦微服务架构,因此对微服务状态的存储系统的可用性要求尤其高。

S3 (Simple Storage Service)是 Amazon 另一款有名的存储服务,虽然也可以理解为 KV 存储,但它和 Dynamo 的目标场景并不一致。S3 是面向大文件的对象存储服务,主要存储二进制文件,不提供跨对象的事务。而 Dynamo 是一款面向小文件的文档存储服务,主要存储结构化数据(如 json),并且可以对数据设置索引,且支持跨数据条目的事务。

相对于传统的关系型数据库,Dynamo 可以认为是只提供主键索引,从而获取更高的性能和更好的扩展性。

为了实现可扩展性和高可用性,并保证最终一致性,Dynamo 综合使用了以下技术:

  1. 使用一致性哈希对数据进行分片(partition)和备份(replicate)。
  2. 使用版本号机制(Vector Clock)处理数据一致性问题。
  3. 使用多数票(Quorum)和去中心化同步协议来维持副本间的一致性(Merkle Tree)。
  4. 基于 Gossip Protocol 进行失败检测和副本维持。

实现上来说,Dynamo 有以下特点:

  1. 完全去中心化,没有中心节点,所有节点关系对等。
  2. 采用最终一致性,使用版本号解决冲突,甚至要求用户参与解决冲突。
  3. 使用哈希值进行数据分片,组织数据分布,均衡数据负载。
阅读全文 »

1591539058644.jpg

儿时初学“让我们荡起双桨”,只感觉旋律朗朗;年岁稍长,偶尔哼起,三言两语,味出千万意境;后来,求学帝都,游北海,正是“湖面倒映着美丽的白塔,四周环绕着绿树红墙”,光阴荏苒,不变的是文字的生命力。

歌词为乔羽先生所做,很多脍炙人口的名作皆出自其手:《我的祖国》、《难忘今宵》、《爱我中华》。词分三段,层层递进。第一段写划船之景,寥寥几句,首尾勾连、推近及远、勾勒出四合景象。第二段写欢快之情,童真昂扬,心情轻快,描绘出饱满的童趣。第三段继而升华,设问如此美景、如此生活、如此时代,如何得来?尔后戛然而止,语已尽而意无穷。

阅读全文 »

6.824-schedule.png

MIT 今年终于主动在 Youtube 上放出了随堂视频资料,之前跟过一半这门课,今年打算刷一下视频,写写随堂笔记。该课程以分布式基础理论:容错、备份、一致性为脉络,以精选的工业级系统论文为主线,再填充上翔实的阅读材料和精到的课程实验,贯通学术理论和工业实践,实在是一门不可多得的分布式系统佳课。课程视频: YoutubeB站。课程资料:6.824主页。本篇是第六节课笔记,是 Raft 论文讲解的第一部分,主要总结了容错的几种类型以及 Raft 中的 Leader 选举相关内容。

阅读全文 »