木鸟杂记

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

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

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

北京

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

景山远眺故宫

阅读全文 »