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

强行凑出来的五一小长假即将结束,一年一度的朋友圈晒图大赛又将起航。虽然手机自带的图片自动润色功能越来越强大,但毕竟不能满足我们程序员想掌控一切的精细化调整需求。下面就我一些浅薄的调色经验,以我在长沙游天心阁玩拍的一张图片的调色过程为例,教你一套李鬼变李逵的风景调色屠龙技。最后会给一个简单的修图原理的总结,一探图片调色背后的本质。

先来个对比

为了说明图片调色确实有奇效,先上一个对比图给大家直观感受下:

对比图-调色前.jpg

对比图-调色后.jpg

此图摄于老长沙制高点——天心阁。是日乌云密布,暴雨将至,从天心阁二层远眺,黄瓦蓝天,车水马龙,一动一静,似有雷霆之势。

下面分步骤讲解下调色过程和原理,尽量简洁一点,并且附上参考资料,留给有兴趣深挖的同学。

阅读全文 »

前一段时间由于一些原因工作变动,面了一些分布式存储的相关岗位,感觉市面上相关经验分享较少,因此拿出来和大家分享一下。由于公司隐私政策问题,不会按公司对题目进行罗列,仅仅就一些面试的方向和内容进行简单梳理。水平经验所限,谬误之处,可以留言交流指正。

相关岗位

分布式存储方向的岗位涵盖甚广,一般可以按照方向分为:

  1. 分布式文件存储
  2. 对象存储
  3. 分布式 KV or 缓存
  4. 分布式数据库(new sql)
  5. 表格存储
  6. 块存储

其定位方向也稍有不同:

分布式文件存储。支持 POSIX 语义或者裁剪 POSIX。可以作为存储和计算分离的存储基座,也可以直接为应用所用,比如说深度学习的一些训练,大数据处理的一些中间存储。常见产品有盘古文件系统、Polarfs、JuiceFS 等。

对象存储。一般是存储图片和视频之类的非结构化数据,通常兼容亚马逊的 S3 接口。常见产品如 Amazon S3、阿里云 OSS、腾讯云 COS。

分布式 KV or 缓存。通常兼容 redis 接口,或者更简化 KV 接口。一般求快,基于内存或者SSD,甚至可持久化内存等新硬件。用于低延迟需求的业务缓存或者存储计算分离系统的底座。产品如字节的 ABase、阿里云的 Tair、PingCAP 的 TiKV。

分布式数据库(or new sql)。通常提供 SQL 接口以及无限水平扩展能力。常见产品有 PingCAP 的 TiDB、阿里云的 PolarDB、腾讯云的 TDSQL。

表格存储。经典的接口可以参考按列存储的 HBase,大数据领域应用比较多。产品如 HBase,字节的 ByteTable。

块存储。提供块设备接口,一般用于云主机的系统盘。产品如 smartX 的超融合。

阅读全文 »

boltdb 是市面上为数不多的纯 go 语言开发的、单机 KV 库。boltdb 基于 Howard Chu’s LMDB 项目 ,实现的比较清爽,去掉单元测试和适配代码,核心代码大概四千多行。简单的 API、简约的实现,也是作者的意图所在。由于作者精力所限,原 boltdb 已经封版,不再更新。若想改进,提交新的 pr,建议去 etcd 维护的 fork 版本 bbolt。

为了方便,本系列导读文章仍以不再变动的原 repo 为基础。该项目麻雀虽小,五脏俱全,仅仅四千多行代码,就实现了一个基于 B+ 树索引、支持一写多读事务的单机 KV 引擎。代码本身简约朴实、注释得当,如果你是 go 语言爱好者、如果对 KV 库感兴趣,那 boltdb 绝对是不可错过的一个 repo。

本系列计划分成三篇文章,依次围绕数据组织索引设计事务实现等三个主要方面对 boltdb 源码进行剖析。由于三个方面不是完全正交解耦的,因此叙述时会不可避免的产生交织,读不懂时,暂时略过即可,待有全貌,再回来梳理。本文是第三篇, boltdb 事务实现。

引子

在分析 boltd 的事务之前,我们有必要对事务概念做一个界定,以此来明确我们的讨论范围。数据库事务(简称:事务)是数据库管理系统执行过程中的一个逻辑单位,由一个有限的数据库操作序列构成^1。wiki 上的定义有点拗口,理解时只需抓住几个关键点即可:

  1. 执行:计算层面
  2. 逻辑单位:意味着不可分割
  3. 操作序列有限:一般粒度不会太大

那为什么要有事务呢?事务出现于上世纪七十年代,是为了解放数据库用户的心智而出现的:事务帮助用户组织一组操作、并在出错时自动进行扫尾。后来,NoSQL 和一些分布式存储为了高性能而舍弃了完整事务的支持。然而,历史是螺旋上升的,事务的便利性让 NewSQL 等新一代分布式数据库又将其重新请回。

提起事务,最脍炙人口的便是 ACID 四大特性。 其实 ACID 更像一种易于记忆的口号而非严格的描述,因为他们在概念上并不怎么对称,而且依赖于一些上下文阐释。本文仍然会按照这四个方面对 boltdb 对事务的支持进行剖析,但在每个小结开始,会先参考 Martin Kleppmann 的演讲[^2],试着从不同角度先阐释其内涵;然后在再分析 boltdb 对其实现。

阅读全文 »

北京周边的山上山桃特别多,像物种入侵一样密密麻麻的散落在山坡上、龟缩在山谷中。其他时节徒步时对此没有特别的感觉,但唯独春天,大为惊喜。远处望去,像团团粉色的烟雾般缥缈。然而疫情初定的帝都春日,雾霾又起。亲眼看着漫山的山桃,却只能凭空想象通透天空下的丽景。

山桃虽艳 抵不过老霾

阅读全文 »

本文整理自OSDI 2020 Virtual Consensus in Delos 论文演讲,探讨了分布式系统中控制面的存储系统,提出了一种基于分层抽象思想的分布式架构。其核心在于提出了一种逻辑协议层,使得物理层可以按需进行实现和移植,有点类似于单机系统中虚拟内存之于物理内存的味道。

阅读全文 »

小引

大学时,数据库学的不是很深,现在有印象的也就 SQL、ER 图、范式、事务等使用上的寥寥概念。对于其实现上一直没有过系统性的了解,但既然走上了存储这条路,数据库知识肯定要补一下。先前,知乎上很多地方看到大家推荐 cmu15445 这门课,也早就将课程主页收藏到了文件夹,但一直没得空来看。念念不忘,必有回响,到这个假期,恰逢换工作,才有点大块的时间开个头。

大纲

简单介绍下 cmu15445教学大纲,该课以 Database System Concepts 为辅助教材, 讲述了数据库管理系统(DBMS)设计和实现的方方面面,包括:

  1. 数据模型(关系型,文档型,键值型)
  2. 存储模型(n-ary,decomposition,可以理解为行式、列式)
  3. 查询语言(sql,存储过程 stored procedures)
  4. 存储结构(heaps,基于日志 log-structured)
  5. 索引设计(排序树,哈希表)
  6. 事务处理(ACID,并发控制)
  7. 数据恢复(日志、快照)
  8. 执行引擎(joins,排序,聚集,优化)
  9. 并发架构(多核,分布式)

可以看出,内容十分翔实,课程使用一个开源的商业数据库作为案例进行讲解,以深入探讨数据库设计时,在上述各个方面进行取舍的过程。本课程十分重视编程实践,设计了一系列前后勾连但又足够简洁的代码实验

阅读全文 »

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 文件的增长过程以及载入内存的策略。

阅读全文 »