木鸟杂记

分布式系统,数据库,存储

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

下面是 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. 可多机房扩展,高度面向读性能优化,只提供最终一致性保证。
阅读全文 »

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

北京

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

景山远眺故宫

阅读全文 »

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

每篇将以概述背景、架构模块、总结延伸来分别解析,本篇是第一篇: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。

阅读全文 »