走过很多路，待日子久远，记忆日渐模糊。幸有摄影，定格流连瞬间，勾起尘封情趣。今日午后有闲，辑录一二，漫步时光，略熨燥气。

北京

求学帝都，至今十余载，这是一个有太多回忆的地方，自然要单拎一辑。不过，照片基本成于近两年，不能表现京城美景什一。故宫的庄重，古籍馆的积淀，北海的闲趣，孔庙的肃穆，土城的热闹，长城的苍凉，海坨的开发，不可胜记。

景山远眺故宫

分布式系统有很多经典的套路，也即设计模式。每个设计模式可以解决经典的一类问题，积累的多了，便可以稍加变化，进行取舍，设计出贴合需求的架构组织。但似乎大家在这方面经验分享的不太多，因此之后打算总结一些工作和学习的经验，既是备忘，也希望对大家有些助益。篇幅所限、能力所囿，难以面面俱到，又或疏于精确。不当之处，欢迎指正。

每篇将以概述背景、架构模块、总结延伸来分别解析，本篇是第一篇：Master-Workers 架构。

概述

Master-Workers 架构（粗译为主从架构）是分布式系统中常见的一种组织方式，如 GFS 中的 Master、ChunkServers；MapReduce 中的 Master、Workers。面对分布式系统中一堆分离的机器资源，主从架构是一种最自然、直白的组织方式——就像一群人，有个说了算 leader 进行组织、协调，才能最大化这群人的对外输出能力。

这也是计算机系统中常见的一种分而治之思想的体现。即将一个复杂的系统，拆解成几个相对高内聚、低耦合的子模块，定义清楚其功能边界和交互接口，使得系统易于理解、维护和扩展。对于主从架构来说，主（Master） 通常会维护集群元信息、进而依靠这些元信息进行调度，从（Workers） 通常负责具体数据切片（存储系统）的读写或者作为子任务（计算系统）的执行单元。

引子

Paxos 是分布式系统中绕不过去的一个算法，但出了名的难以理解。因此我看到 Paxos 也是一直绕着走，但是绕的多了总感觉有些遗憾。于是过去一周闲暇时间搜集了很多资料，尝试了很多打开方式，总算初窥门径。便趁着新鲜，将脑中的理解赶到纸上，做个小结，以备后日不时之需。

Paxos 算法的发明人 Leslie Lamport 是分布式系统的奠基人之一，轶事颇多，从 Paxos 这个名字也能窥得一斑：Paxos 是 Lamport 为了引出分布式系统共识问题，所虚拟的一个古希腊城邦。在最初的相关论文 The Part-Time Parliament 发表于 1998 年后，很多人都表示理解不能。于是 Lamport 在 2001 年，又使用相对简练的语言和逻辑，将其主干思想重新阐述了一遍，便有了 Paxos made simple。

Lamport 在 Paxos made simple 论文的摘要只有一句话：

The Paxos algorithm, when presented in plain English, is very simple

然而，我却无法理解这种 simple。

Zookeeper

本篇要介绍 Patrick Hunt 等人在 2010 年发表的、至今仍然广泛使用的、定位于分布式系统协调组件的论文 —— ZooKeeper: Wait-free coordination for Internet-scale systems。我们在多线程、多进程编程时，免不了进行同步和互斥，常见手段有共享内存、消息队列、锁、信号量等等。而在分布式系统中，不同组件间必然也需要类似的协调手段，于是 Zookeeper 应运而生。配合客户端库，Zookeeper 可以提供动态参数配置（configuration metadata）、分布式锁、共享寄存器（shared register）、服务发现、集群关系（group membership）、多节点选主（leader election）等一系列分布式系统的协调服务。

总体来看，Zookeeper 有以下特点：

1. Zookeeper 是一个分布式协调内核，本身功能比较内聚，以保持 API 的简洁与高效。
2. Zookeeper 提供一组高性能的、保证 FIFO的、基于事件驱动的非阻塞 API。
3. Zookeeper 使用类似文件系统的目录树方式对数据进行组织，表达能力强大，方便客户端构建更复杂的协调源语。
4. Zookeeper 是一个自洽的容错系统，使用 Zab 原子广播（atomic broadcast）协议保证高可用和一致性。

本文依从论文顺序，简要介绍下 Zookeeper 的服务接口设计与模块粗略实现。更多细节请参考论文和开源项目主页。

引子

时下，随着通信技术的发展、移动互联网的普及、物联网车联网人工智能的兴起，每天所产生的数据呈爆炸性的增长。这种尺度的数据不是传统单机系统可以独立处理的，而只能借助于大规模的分布式系统，因而分布式系统渐渐的变成一门“显学”。而作为一个分布式系统初学者，面对网上未加归类、浩如烟海的学习资料，很容易两眼抓瞎。

但分布式系统有其基本研究内容和独特发展脉络，比如：

1. 一些基本研究问题：时序问题、一致性问题、容错技术、共识算法、并发控制等等。
2. 一些基本定理：CAP、PACELC、FLP
3. 渐次发展的工业系统：MapReduce、Spark、GFS、Dynamo、Cosmos

因此只需要在“时空”两个维度对分布式系统进行把握，就能提纲挈领，愈学愈明。“时”表示分布式系统的演进脉络，可以通过阅读不同时期、学术界工业界的一些论文来把握。“空”表示分布式系统中所研究的基本问题的拆解，可以通过阅读一些书籍建立分布式系统的知识体系。本文将我在学习分布式系统知识过程搜集到的一些资料，按类别简单汇总，以飨诸君。资料排名没有先后，请按需采用。

注：文中推荐的资料大多为英文，如果阅读有困难，推荐使用 Chrome 浏览器，并且给 Chrome 装一个 “google 翻译”的插件，可以点击一键“翻译此页面”。

早对 LevelDB 有所耳闻，这次心血来潮结合一些资料粗略过了遍代码，果然名不虚传。如果你对存储感兴趣、如果你想优雅使用 C++、如果你想学习如何架构项目，都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。
看过一遍如果不输出点什么，以我的记性，定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙，但又不想走寻常路：从架构概览说起，以模块分析做合。读代码的这些天，一直在盘算从哪下笔比较好。在将将读完之时，印象最深的反而是 LevelDB 的各种精妙的数据结构：贴合场景、从头构建、剪裁得当、代码精到。不妨， LevelDB 系列就从这些边边角角的小构件开始吧。
本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构，分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第三篇，LRUCache。

引子

LRU 是工程中多见的一个数据结构，常用于缓存场景。近年来，LRU 也是面试中一道炙手可热的考题，一来工程用的多，二来代码量较少，三来涉及的数据结构也很典型。LeetCode 中有一道相应的题目：lru-cache。相对实际场景，题目进行了简化：本质上要求维护一个按访问时间有序的 kv 集合，且 kv 皆是整数。经典解法是使用一个哈希表（unordered_map）和一个双向链表，哈希表解决索引问题，双向链表维护访问顺序。这是我当时的一个解法，特点是用了两个辅助函数，并且可以返回节点自身，以支持链式调用，从而简化了代码。

说回 LevelDB 源码，作为一个工业品，它使用 的 LRUCache 又做了哪些优化和变动呢？下面让我们一块来拆解下 LevelDB 中使用的 LRUCache，看看有什么不同。

本文首先明确 LRUCache 的使用方法，然后总览分析 LRUCache 的实现思路，最后详述相关数据结构的实现细节。

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

先来个对比

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

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

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

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

相关岗位

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

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. 并发架构（多核，分布式）

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