木鸟杂记

分布式系统,程序语言,算法设计

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

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

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

阅读全文 »

概述

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 的实现思路,最后详述相关数据结构的实现细节。

阅读全文 »

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

先来个对比

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

对比图-调色前.jpg

对比图-调色后.jpg

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

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

阅读全文 »

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

相关岗位

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

  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 的超融合。

阅读全文 »