DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 和所有文字稿在这里。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。

事务型还是分析型

术语 OL（Online）主要是指交互式的查询。

术语事务（ transaction ）由来有一些历史原因。早期的数据库使用方多为商业交易（commercial ），比如买卖、发工资等等。但是随着数据库应用不断扩大，交易\事务作为名词保留了下来。

事务不一定具有 ACID 特性，事务型处理多是随机的以较低的延迟进行读写，与之相反，分析型处理多为定期的批处理，延迟较高。

DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 和所有文字稿在这里。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。

第二章讲了上层抽象：数据模型和查询语言。
本章下沉一些，聚焦数据库底层如何处理查询和存储。这其中，有个逻辑链条：

使用场景→ 查询类型 → 存储格式。

DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 和所有文字稿在这里。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。

概要

本节围绕两个主要概念来展开。

如何分析一个数据模型：

1. 基本考察点：数据基本元素，和元素之间的对应关系（一对多，多对多）
2. 利用几种常用模型来比较：（最为流行的）关系模型，（树状的）文档模型，（极大自由度的）图模型。
3. schema 模式：强 Schema（写时约束）；弱 Schema（读时解析）

如何考量查询语言：

1. 如何与数据模型关联、匹配
2. 声明式（declarative）和命令式（imperative）

计算下推其实是常见的思想：将计算推到数据旁。由于在数据库中，逻辑上，计算常在存储层之上，因此将一部分算子推到存储层去做，称为计算下推。其在分布式数据库中尤为重要。

下面是 CockroachDB 和 TiDB 的解决方案，内容来自于文档和博客，因此可能和最新代码的逻辑并不一致。

CockroachDB

基本概念

CockroachDB 中相应的模块叫 DistSQL，其思想来源于Sawzall，有点类似 MapReduce。支持的算子叫做 aggregator，本质上是对 SQL 聚合算子的一种泛化。

DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 和所有文字稿在这里。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。

第一章是很容易被跳过的一章，因为概念较多，容易泛泛而谈。但其给出的三个概念，确实是构建系统避不开的三个重点方向。

ps. 开源中文版本有些地方翻译的不是很地道，读起来可能会有些难受，不过这是所有翻译难免的。

（贾）岛初赴举京师，一日驴上得句云：“鸟宿池边树，僧敲月下门”。始欲着“推”字，又欲着“敲”字，练之未定，遂于驴上吟哦，时时引手作推敲之势。

—— 宋·胡仔《苕溪渔隐丛话》卷十九引《刘公嘉话》

命名，是编码中最为紧要的事情，其之于程序，便如脸面之于少女。好的命名，能清晰的传达代码的意图，甚而，有一种韵律的美感。而懒散随意的起名，则令人如堕云雾，不忍卒读，会一遍遍地消耗维护者的精气神儿。此外，混乱的命名体系，能轻巧的掩藏 BUG，贻祸千里。

因此，我们在写代码时，有必要花一点时间，对关键命名进行推敲，与人方便，与己方便。对于生命周期越长的项目，其益处便越明显。那么该如何推敲呢？结合自己写代码、看代码、Review 代码的一些经验，聊聊我的一些体会。

最近写 golang 多一点，因此例子用的都是 golang ，但都是伪代码，有些例子并不不严格遵从语法。此外，例子大多出于现造，因此可能并不是特别贴合。

引子

哈希的本质是从一个较大空间映射到一个较小的空间，因此在插入数据足够多之后，根据鸽巢原理，一定会存在位置冲突。常见的哈希表（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. 可多机房扩展，高度面向读性能优化，只提供最终一致性保证。