引子

哈希的本质是从一个较大空间映射到一个较小的空间，因此在插入数据足够多之后，根据鸽巢原理，一定会存在位置冲突。常见的哈希表（Hash Table 或者字典，dictionary）会通过链表、开放地址探测等方式来处理冲突。单桶多函数的布谷鸟哈希，便是开放地址法处理冲突的一种哈希表，只不过有冲突后，不是通过线性寻找新的位置，而是通过额外哈希函数来寻找。

最近有兴致，想看点中国经济的书，受朋友推荐知道这本书。在微信读书上用差不多一周的时间赶着读完，虽然囫囵吞枣，倒也酣畅淋漓。以前看过吴晓波《激荡三十年》的一些章节，本书算是后传，风格一致，但是读起来会更有共鸣，因为这也正是初代九零后我们的人生中的黄金十年。作为“渐有意识”的亲历者，回放感很强。

概述

吴晓波很擅长宏大叙事和情绪铺垫，在本书中全景式的再现了 2008~2018 这十年间中国经济和企业的波澜起伏。书名“水大鱼大”乍一看很俗，看完后细想，倒也形象。市场和企业的关系，正是鱼和水的关系——水大容纳了鱼的成长厮杀，鱼大成就了水的鲜活壮阔。

这十年也是我从懵懂少年到步入青年的一个人生阶段。作为这段经济史的亲身经历者，对于其间的很多现象，有的没太留意，有的不得其解。作者以类似编年体的方式，以更高维的视角，紧扣时空二象，将各种线头有机的组织在一块，并带出了一些当时不广为人知的秘辛。通过这些冰山之下的暗线，让我们在重新审视这段历史时，隐隐然摸到了一些脉络。

西奥迪尼在影响力方面对我的影响，其他任何科学家都比不上…… 这本畅销书呈现了六至八种方法，让你古怪精灵的想法不会再阻碍你获得最佳利益。
——查理·芒格，巴菲特黄金搭档

人类都有一些思维定势或固有模式，一经触发会使我们就像被按下了播放键，之后的行为便可能不受我们控制。其实这些都是源于人类避免思考的趋势。避免思考在人类原始时期确实给人类带来了不少好处，比如它能节省时间，减轻犹豫不决带来的危及生命的后果。但现在，避免思考的本能也恰恰成了最容易被顺从专家们利用的地方。

其实，不管是那种顺从手法，其应对的核心方法都是一个——思考。首先要从情绪中脱离出来，其次要想清楚自己真正想要的是什么，把表象和实质区分开。

概述

Bw-tree 是 2013 年微软发表的相关论文提出的数据结构。考虑到多核机器和 SSD 日趋普及，结合两大存储引擎 B±tree 和 LSM-tree 特点，提出了一种 latch-free、delta update、log structured 的 B族树 —— Bw-tree。

由于上述论文在实现细节上语焉不详，cmu 几个作者在 2015 年时实现了一版基于内存的 Bw-tree，然后又发表了一篇论文，补充了一些实现上的细节，并将代码开源在了 github 上，称为 open bwtree。

例行地总结下（太长不看版），Bw tree 的主要特点有：

1. 总体分三层：bwtree 索引层，缓存控制层和 Flash 存储层。
2. bwtree 在整体上是一棵 B+ 树，同时借鉴了 B-link 树的思想，每个节点存在一个指向右兄弟的 side pointer。
3. bwtree 在单个树节点上表现为类似 LSM-tree 的 Log-Structure，每个逻辑节点由 a base node + a delta records chain 组成。
4. bwtree 实现 latch-free 的核心数据结构叫 Mapping Table，通过 CAS 进行 installing 操作，修改一个 mapping entry 可以同时完成多个逻辑指针的修改。
5. bwtree flash 层也使用 Log-Structure Store （append only）对逻辑页的物理存储（base page 和 delta record）进行管理。

在技术领域中，分布式系统越来越成为绕不过去的一个名词。原因在于，这个时代的数据尺度与单机存储、处理能力的不匹配。于是有两条路子：机器大型化和机器互联。前者成本高昂且不灵活，于是后者越来越受青睐。根据代价守恒定律，代价不会凭空消失，硬件成本降下来了，软件设计成本便会提升。而分布式系统理论，则是帮我们降低这个软件成本的钥匙。

是什么

分布式系统奠基者 Leslie Lamport [1] 在其最重要的论文之一 ”Time, Clocks, and the Ordering of Events in a Distributed System“ [2] 中提到：

A system is distributed if the message transmission delay is not negligible compared to the time between events in a single process.

Lamport 是用类似相对论的思想来阐释这个问题。我们考虑两个时间尺度：进程间消息传递延迟和进程内事件间隔，如果前者相对后者不可忽略，则这组进程就是一个分布式系统。

理解这个定义，需要理解几个重要的概念（形式化的定义总是这样，摊手）：进程（process）、消息（message）和事件（event）。为了避免套娃，这里不做过多展开，仅给出一个形象的理解：进程就是一个负责干活的劳工，其干的活可以分解为多个步骤，每个步骤就是一个事件，消息便是劳工交流的方式。

这也印证了维基百科中 distributed computing [3]（分布式系统又称分布式计算）给的定义：

1. There are several autonomous computational entities ( computers or nodes ), each of which has its own local memory.
2. The entities communicate with each other by message passing.

这里面涉及到了计算机系统中最重的几种资源：计算（computational），存储（memory），以及沟通他们的网络（network）。

总结下，我们可以从另一个角度来对分布式系统进行描述：

对外，分布式系统表现为一个整体，基于总体的存储和计算能力，提供特定功能。

对内，分布式系统表现为一组个体，基于网络消息进行通信，分工合作。

而分布式系统的设计目标是，最大化整体资源利用率的同时，处理局部错误、保持对外可用性。

概述

Facebook TAO[1] ，即 The Associations and Objects 的缩写，点（对象，Object）和边（联结，Associations）是”图“中最基本的抽象，用来做 Facebook 图存储名字倒是恰如其分。

概括来说，TAO 是 Facebook 为了解决社交场景下，超大数据的更新与关联读取问题，其核心特点如下：

1. 提供面向 Facebook 社交信息流场景特化的图 API ，比如点查、一度关联查询、按时间的范围查询。
2. 两层架构，MySQL 做存储层，MemeCache 做缓存层；缓存层又可细分为主从两层。
3. 可多机房扩展，高度面向读性能优化，只提供最终一致性保证。

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

北京

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

景山远眺故宫

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

每篇将以概述背景、架构模块、总结延伸来分别解析，本篇是第一篇：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 的实现思路，最后详述相关数据结构的实现细节。