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

本文缘起于Lu Pan 的个人博客文章:https://blog.the-pans.com/cap/ ,是他经过 Martin Kleppmann 授权并且翻译的博文”Please stop calling databases CP or AP”中文版本。但译文中不少句子读来颇为古怪,我对照英文原文,按照自己理解,逐句校验、重译了一遍。这篇文章探讨了为什么不应该滥用 CAP定理 这个概念,旁征博引,入木三分,值得一读。更值得称道的是,Martin 文中所有关键观点都给出了来源,并在最后推荐了一些学习资料,都是不错的阅读材料。以下是正文。

在 Jeff Hodges 的精彩博文给年轻人关于分布式系统的笔记 中,他建议我们用CAP定理来评判系统。不少人听从了这个建议,将他们的系统称为”CP” (提供一致性但在网络分区时不可用),“AP”(高可用但是在网络分区时不一致) 或者干脆 “CA” (说明还没有读过Coda的五年前的文章)。

我同意 Jeff 的所有其他观点,但其关于 CAP 定理的使用建议,我不能表示赞同。CAP 定理本身太过简化而且存在广泛的误解,以至于在界定系统时不能有效的起到作用。因此我请求大家不要再引用CAP定理, 不要再讨论CAP定理。取而代之,我们应该用更精确的术语来表述我们对系统的取舍。

(当然,讽刺的是我不希望别人再讨论这个话题,自己却正在写一篇关于这个话题的文章。不过至少以后别人问我为什么不喜欢讨论CAP定理的时候,我可以把这篇文章的链接给他。还有,抱歉这篇文章会有些吐槽,但是至少这些吐槽给出了文献引用)

阅读全文 »

cap-consistency-example.png

小引

曾经在一个面试中让谈谈对 CAP 的理解,当时凭着准备面试时谷歌到的N手资料,类似于小学生背书一样,生挤出只言片语。面试官无奈的笑笑,简练的概括出他想要听到的要点,听的我心下惭愧。面试自然是挂了,后来工作时偶尔接触到这个词汇,初不得要领,后通过不同资料的多侧面理解、印证,渐渐拼凑出了一个轮廓,在这里梳理下,将影子撵到纸上,以供日后索引。

面试官大约是这么概括的:在分布式系统中,失败必然的,分区容错(P)是一定需要的,因此设计系统时需要在可用性(A)和一致性(C)间进行权衡。当时被教育印象很深,现在看来,这句概括是点出了小荷才露尖尖角的那个角。

阅读全文 »

初冬一个晴朗的午后,从地坛出发,经交道口三条,过圆恩寺胡同,一路走到什刹海。当天天气出奇的好,在太阳的透照下,整个胡同片区懒洋洋的,心里也不由的很轻快。

阅读全文 »

研究生毕业时,去网易游戏实习攒了点钱,便想入手垂涎了好久的程序员生产力工具—— MacBook Pro。适逢新版发售,等到 2016 年底,新版甫一上市,便从官网下单了一台 pro 入门版:13 寸两口不带 bar 。不过哪怕是入门版,也要一万多大洋,还两个口,还不带 bar。

mac-buy-info.png

不带 bar 尚可接受,毕竟 vim 党还是喜欢能按的下去的 Esc 。但两个口——于是默默了去京东下单了几个扩展口,彼时 tpye c 尚不流行,选择无几。

到货后满心欢喜打开,惊艳异常,是醉人的新配色——深空灰、是史无前例的轻薄、是类 Unix 系统加上舒服的 UI。于是将之前的小嘀咕抛诸脑后,嗯,真香。

阅读全文 »

引子

18年的时候做过一些 6.824,旧文在此,无奈做到 Part 2C,无论如何也跑不过测试,便一直搁置起来。但在后来的日子,却时时念起此门神课,心下伤感。拖到今日,终于可以来还愿了。

这次能跑过所有测试,原因有三:一来,之前做过一次,很多原理还留有印象;二来,这一年多在工作上有了很多分布式系统的实践;三来,golang 的驾驭上也精进了一些。但是在做的过程中,仍然遇到了大量令人纠结的细节,为了方便日后回顾,将这些细节梳理一下,记在此处。若能好巧对其他做此门课的人有些微启发,则又是快事一件了。

6.824 与 Raft

6.824 是一门关于分布式系统的非常棒的公开课,做课程实验的过程中时时惊叹于其构思之精巧、材料准备之翔实。MIT 的大师们能将这样精华的课程开放出来,实乃名校和大师们的气度,更是我们计算机人的幸事。

Raft 是一个面向理解的分布式共识(consensus)协议。分布式共识算法是分布式领域非常非常经典的问题,同时也是分布式系统中非常难的一块,直观的说,就如同流沙上打下分布式系统大楼的地基。不可靠的网络、易故障的主机,造成的状态变化之复杂,实在不是一般人能在脑中模拟得了的。本人愚钝,只能是感性把握加细节堆叠,堪堪有些认识。说回 Raft,有同领域 Paxos 珠玉在前,何以 Raft 仍能脱颖而出?应该是抓住了以下两点:

  1. 易于理解。Paxos 是出了名的难以理解,因此也就难以飞入寻常百姓家。而 Raft 通过解耦出多个模块,将算法复杂度进行降维,大大降低了一般人的理解难度。此外,Raft 还有很多精巧的设计,以尽可能避免引入复杂度,从而进一步减轻大家的心智负担。
  2. 易于实现。易于理解客观上会导致利于实现,但不等同于就能据此产出优秀系统。如果理解流于感性,则实现成空中楼阁。Raft 论文的厉害之处就在于既有感性把握又有细节组织,几乎就是一个系统的设计文档,还是详细设计文档。

要想做好该实验,需要涉猎大量的材料,我把实验中提到的和我看到的汇总在文末。当然,还有英文劝退。虽然我最后测试用例都过了,但仍有很多没实现好的点以及不理解之处。

阅读全文 »

小引

最近在写 Go 代码时需要给某个 struct 定制一个字符串转换方法

1
func (ms MyStruct) String() string

但是在实现是考虑选用 value methods 还是 pointer methods 方式时纠结了起来。

Go 的语法糖使得这两种方式在调用上是一致的,这让我一时难以抉择孰优孰劣,于是决定深入探究一下其背后原理以便之后能写出更地道(idiomatic)的 Go 代码。

阅读全文 »

概览

Kafka (该论文发表于2011年6月[1])是日志处理和消息队列系统的集大成者。较低的延迟、极高的容量和吞吐,使其可以应用于在线服务和离线业务。为了兼顾性能和可扩展性,Kafka 做了一些看起来反直觉但是却很实用的设计。例行总结一下其设计特点:

  1. 面向存储的消息队列:意味在近实时的情况下能够将传统消息队列的存储增加几个数量级。实现原理是充分利用了磁盘的顺序写和操作系统自身的缓存;此外为了提高访盘、传输效率,使用了文件分段、段首索引、零拷贝和批量拉取等技术。

  2. 灵活的生产消费方式:总体而言是基于主题粒度的发布订阅式架构,并且既支持组内多消费者互斥消费,也支持不同消费者组间的重复消费。这里面涉及到消息队列的两个核心设计选择:pull 式消费以及客户端侧存储消费进度。拉式消费可能会导致空轮询以及稍微的延迟,好处在于灵活;客户端存储消费进度可以使的 broker 无状态,以进行灵活伸缩和容错。为了简化实现,消费时,每个分区最多为一个消费者所消费。

  3. Zookeeper 存储元信息:利用分布式一致性组件 Zookeeper 以注册表的形式存储系统元信息,包括 broker 和消费者的存活信息、消费者和分区间的对应关系、每个分区的消费进度等等。Zookeeper 作为一个前缀树形式组织 KV、支持发布订阅的高可用组件,可以满足 Kafka 进行消费协调和进度保存的协作需求。

  4. 分区级别的多副本设计:这一点在论文中还没实现,应该是后来系统开源演进时加上的。利用该条可以实现对 broker 的容错。

  5. 简洁强大的消费接口:Kafka 的客户端一般提供两层接口抽象。包括无需关注分区偏移量信息的高层(high-level)简单读写接口,以及可以灵活控制分区组织和消费进度的低层(low-level)接口。论文中只提到了前者,以表现其简洁。

阅读全文 »

bazel-golang.png

引子

Bazel 是一款谷歌开源的非常优秀的构建系统。它的定位,用官方的话来说是:

a fast, scalable, multi-language and extensible build system

大意为:

一款速度极快可伸缩跨语言并且可扩展的构建系统

使用 Bazel 构建 golang 项目,除了 Bazel 本身特性外,还需要了解针对 golang 的扩展包 rules_go。另外,可以使用 bazel gazelle 来进行一些自动生成的工作。

阅读全文 »

概述

RDD,学名可伸缩的分布式数据集(Resilient Distributed Dataset)。是一种对数据集形态的抽象,基于此抽象,使用者可以在集群中执行一系列计算,而不用将中间结果落盘。而这正是之前 MR 抽象的一个重要痛点,每一个步骤都需要落盘,使得不必要的开销很高。

对于分布式系统,容错支持是必不可少的。为了支持容错,RDD 只支持粗粒度的变换。即,输入数据集是 immutable (或者说只读)的,每次运算会产生新的输出。不支持对一个数据集中细粒度的更新操作。这种约束,大大简化了容错支持,并且能满足很大一类的计算需求。

阅读全文 »

python-generator.png

引子

某次面试问候选人:Python 中生成器是什么?答曰:有 yield 关键字的函数。而在我印象中此种函数返回的值是生成器,而函数本身不是。如下:

1
2
3
4
5
6
7
8
9
10
11
In [1]: def get_nums(n): 
...: for i in range(n):
...: yield i
...:
In [2]: type(get_nums)
Out[2]: function

In [3]: nums = get_nums(10)

In [4]: type(nums)
Out[4]: generator

但看候选人那么笃定,隐隐然感觉哪里不对,于是有了以下探究。

阅读全文 »