系统日知录

首先非常感谢你的订阅。本专栏是一个大规模数据系统从业者的絮絮叨叨，涵盖的主题包括存储、数据库、分布式系统、AI Infra 、计算机基础等庞杂的系统知识。由于主题零散、内容驳杂，以下是一些建议的本专栏的“打开姿势”。在一切开始之前，可以关注我的公众号：“木鸟杂记”，回复：“优惠券”，即可获取订阅本专栏的八折优惠券。 订阅了之后欢迎分享你喜欢的文章，如果你的朋友通过你分享的文章订阅后，你都可以拿到之后订阅费（会随着文章数的增多不断上调）的百分之二十！订阅后如果专栏内容不符合预期，二十四小时内可以随时退款。目录和索引我会定期更新所有文章目录到简介中，根据此目录，作为一个新读者，你可以快速通过标题找到你想要的文章。注：📘 代表该篇是论文解读🔥 表示该篇启发+留言人数较多也可以通过顶部的标签，来快速筛选想要看的某类文章：当然，也可以修改排序方式，来从老文章读起：最后，对于某些你感觉不错，以后想回看，或者想稍后阅读的文章，也可以点击收藏。启发和留言如果某一篇文章帮到了你，一定要不要吝啬点一个“有启发”，或者留言，根据这些反馈，我可以在未来调整写作方向，产出更多大家感兴趣的文章。让“赞”和“吐槽”都来的更猛烈些吧！读者社区我们有个相关的小论坛：https://distsys.cn/ ，我专门开了版面：https://distsys.cn/t/column，每次发文章后，会将摘要发到论坛上，如果你想进行公开讨论可以去该贴下回复，或者单开主题。我们有个读者群，但是由于我没有定期组织活动，所以群里长期也没有人发言。如果这样你还想进，那就扫下面二维码吧。这个群，以后我能想到的作用，也就是发了新文章之后，转到群里，如果大家有即时想法，可以直接在群里讨论了。

“工业流水线”的鼻祖，福特 T 型汽车的电机装配，将组装过程拆成 29 道工序，将装备时间由平均二十分钟降到五分钟，效率提升四倍 ，下图图源。这种流水线的思想在数据处理过程中也随处可见。其核心概念是：标准化的数据集合：对应待组装对象，是对数据处理中各个环节输入输出的一种一致性抽象。所谓一致，就是一个任意处理环节的输出，都可以作为任意处理环节的输入。可组合的数据变换：对应单道组装工序，定义了对数据进行变换的一个原子操作。通过组合各种原子操作，可以具有强大的表达力。则，数据处理的本质是：针对不同需求，读取并标准化数据集后，施加不同的变换组合。Unix 管道Unix 管道是一项非常伟大的发明，体现了 Unix 的一贯哲学：程序应该只关注一个目标，并尽可能把它做好。让程序能够互相协同工作。应该让程序处理文本数据流，因为这是一个通用的接口。— Unix Pipe 机制发明者 Malcolm Douglas McIlroy上述三句话哲学正体现了我们提到的两点，标准化的数据集合——来自标准输入输出的文本数据流，可组合的数据变换——能够协同工作的程序（如像 sort, head, tail 这种 Unix 自带的工具，和用户自己编写的符合管道要求的程序）。让我们来看一个使用 Unix tools 和管道来解决实际问题的例子。假设我们有一些关于服务访问的日志文件（var/log/nginx/access.log ，例子来自 DDIA 第十章），日志的每一行格式如下：// $remote_addr - $remote_user [$time_local] "$request" // $status $body_bytes_sent "$http_referer" "$http_user_agent" 216.58.210.78 - - [27/Feb/2015:17:55:11 +0000] "GET /css/typography.css HTTP/1.1" 200 3377 "<http://martin.kleppmann.com/>" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_9_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/40.0.2214.115 Safari/537.36" 我们的需求是，统计出日志文件中最受欢迎的五个网页。使用 Unix Shell ，我们会写出类似的命令：cat /var/log/nginx/access.log | # 读取文件，打入标准输出 awk '{print $7}' | # 取出每行按空格分割的第七个字段 sort | # 对每行按字面值进行排序 uniq -c | # 归并重复行，并给出重复次数 sort -r -n | # 按重复次数降序进行排序 head -n 5 # 输出前五行 可以看出上述 Shell 命令有以下几个特点：每个命令实现的功能都很简单（高内聚）所有命令通过管道进行组合（低耦合），当然这也要求可组合的程序只面向标准输入、标准输出进行编程，无其他副作用（比如输出到文件）输入输出面向文本而非二进制此外，Unix 的管道的另一大优点是——流式的处理数据。也即所有程序中间结果并非都计算完成之后，才送入下一个命令，而是边算边送，从而达到多个程序并行执行的效果，这就是流水线的精髓了。当然，管道也有缺点——只能进行线性的流水线排布，这也限制了他的表达能力。GFS 和 MapReduceMapReduce 是谷歌 2004 年的论文 MapReduce: Simplified Data Processing on Large Clusters 提出的，用以解决大规模集群、并行数据处理的一种算法。GFS 是与 MapReduce 配套使用的基于磁盘的分布式文件系统。MapReduce 算法主要分为三个阶段：Map：在不同机器上并行的对每个数据分区执行用户定义的 map() → List<Key, Value> 函数。Shuffle：将 map 的输出结果（KV 对）按 key 进行重新分区，按 key 聚集送到不同机器上， Key→ List<Value>。Reduce：在不同机器上并行地对 map 输出的每个 key 对应的List<Value> 调用 reduce 函数。（下图源 DDIA 第十章）每个 MapReduce 程序就是对存储在 GFS 上的数据集（标准化的数据集）的一次变换。理论上，我们可以通过组合多个 MapReduce 程序（可组合的变换），来满足任意复杂的数据处理需求。但与管道不同的是，每次 MapReduce 的输出都要进行“物化”，即完全落到分布式文件系统 GFS 上，才会执行下一个 MapReduce 程序。好处是可以进行任意的、非线性的 MapReduce 程序排布。坏处是代价非常高，尤其考虑到 GFS 上的文件是多机多副本的数据集，这意味着大量的跨机器数据传输、额外的数据拷贝开销。但要考虑到历史上开创式的创新，纵然一开始缺点多多，但会随着时间迭代而慢慢克服。GFS + MapReduce 正是这样一种在工业界开创了在大规模集群尺度上处理海量数据的先河。SparkSpark 便是为了解决 MapReduce 中每次数据集都要落盘的一种演进。首先，Spark 提出了标准的数据集抽象——RDD，这是一种通过分片的形式分散在多机上、基于内存的数据集。基于内存可以使得每次处理结果不用落盘，从而处理延迟更低。基于分片可以使得在机器宕机时，只用恢复少量分片，而非整个数据集。逻辑上，我们可以将其当做一个整体来进行变换，物理上，我们使用多机内存承载其每个分片。其次，基于 RDD，Spark 提供了多种可灵活组合的算子集，这相当于对一些常用的变换逻辑进行“构件化”，可以让用户开箱即用。（下面图源 RDD 论文）基于此，用户可以进行任意复杂数据处理，在物理上多个数据集（点）和算子（边）会构成一个复杂的 DAG （有向无环图）执行拓扑：关系型数据库关系型数据库是数据处理系统的集大成者。一方面，它对外提供强大的声明式查询语言——SQL，兼顾了灵活性和易用性。另一方面，他对内使用紧凑、索引友好的存储方式，可以支撑高效的数据查询需求。关系型数据库系统同时集计算和存储于一身，又会充分利用硬盘，甚至网络（分布式数据库）特点，是对计算机各种资源全方位使用的一个典范。本文不去过分展开关系型数据库实现的各个环节，而是聚焦本文重点——标准的数据集和可组合的算子。关系型数据库对用户提供的数据基本组织单位是——关系，或者说表。在 SQL 模型中，这是一种由行列组成的、强模式的二维表。所谓强模式，可以在逻辑上理解为表格中每个单元所存储的数据必须要符合该列“表头”的类型定义。针对这种标准的二维表，用户可以施加各种关系代数算子（选择、投影、笛卡尔乘积）。一条 SQL 语句，在进入 RDBMS 之后，经过解析、校验、优化，最后转化成算子树进行执行。对应的 RDBMS 中的逻辑单元，我们通常称之为——执行引擎，Facebook Velox 就是专门针对该生态位的一个 C++ 库。传统的执行引擎多使用火山模型，一种属于拉（ pull-based ）流派的执行方式。其基本概念就是以树形的方式组织算子，并从根节点开始，自上而下的进行递归调用，算子间自下而上的以行（row）或者批（batch）的粒度返回数据。近些年来，基于推（push-based）的流派渐渐火起来了，DuckDB、Velox 都属于此流派。类似于将递归转化为迭代，自下而上，从叶子节点进行计算，然后推给父亲节点，直到根节点。每个算子树都可以拆解为多个可以并行执行的算子流水线（下图源，Facebook Velox 文档）我们把上图顺时针旋转九十度，可以发现他和 Spark 的执行方式如出一辙，更多关于 velox 机制的解析，可以参考我写的这篇文章。但无论推还是拉，其对数据集和算子的抽象都符合本文一开始提出的理论。小结考察完上述四种系统之后，可以看出，数据处理在某种角度上是大一统的——首先抽象出归一化的数据集，然后提供施加于该数据集之上的运算集，最终通过组合的形式表达用户的各种数据处理需求。

我们在工程实践中，有些构建代码的小技巧，其背后所体现的思想，生活中也常常可见。本系列便是这样一组跨越生活和工程的奇怪联想。这是第一篇：多轮次拆解，也即，很多我们习惯一遍完成的事情，有时候拆成多个轮次完成，会简单、高效很多。我在进行 code review 时，有时会看到一些新手同学在一个 for 循环中干太多事情。这常会造成多层嵌套，或者 for 循环内容巨大无比。此时，如果不损失太多性能，我通常建议同学将要干的事情拆成多少个步骤，每个步骤一个 for 循环。甚至，可以每个步骤一个函数。当然，这些全是从维护角度着眼的。因为人一下总是记不了太多事情，一步步来，而不是揉在一块来，会让每个步骤逻辑清晰很多。后者，我通常称之为”摊大饼“式代码，这种代码的特点是写时很自然，但是维护起来很费劲——细节揉在一起总会让复杂度爆炸。软件工程中的最小可用原型，也是类似的理念。这种理念，其实在”函数式“编程中也随处可见，即对一个数据集操作时，我们会链式的应用一系列变换函数，从而让数据流清晰的展示出来。在大数据处理中，这种范式就更常见了，比如 spark 论文中提到的：errors.filter(_.contains("HDFS")) .map(_.split(’\\t’)(3)) .collect() SQL 查询引擎在实现时也是用的类似机制，即将一个查询语句，转换成对一个行列组成的二维数据集，施加多轮次的算子变换。如下图所示。图源：CMU15445，查询引擎讲义。我高中时学过一点点素描，虽然没有入门，但其多轮次的做图技法给我印象很深：先勾轮廓，再逐层完善。打线的时候也是一层层的打，而非一个地方画完再画另一个地方。我最近常常翻译文章，开始时，我总是务求一遍翻译好。但结果就是非常慢，且很容易放弃。后面开始使用多轮次、逐层打磨法。一开始用 ChatGPT 帮忙翻译一遍，然后自己再对照原文订正语义，最后扫一遍调换语序理顺词句等等。常言道，好文章是改出来的，应该也是这个道理。滑铁卢大学教授 Srinivasan Keshav 在其 ”How to Read a Paper“ 中阐述了经典的”三遍（three-pas approach）读论文“方法，也是类似的思想：The first pass：鸟瞰式略读，抓摘要、章节标题、结论等重点内容。The second pass：稍微细一些，但不要陷入细节。The third pass：细读，完全理解。其中任何一步都可以及时停止：这可能不是你需要的论文。但我之前读论文就长陷入一个误区，我愿称之为”地毯式读法“——逐字句过每一个细节。包括我刚开始进行 code review 时，也常常陷入这个误区。一次性的、按顺序把事情做完，是大部分人的天性，但这种天性往往是低效的，我们要通过不断地训练来克服。说起来，我出去点菜的时候，也常用两遍法——第一遍把想吃的都加上，第二遍考虑各种约束（偏好强弱、价格高低、吃过与否等等）来将菜品去到一个合理的范围内。我想背后的原因是：人的注意力是有限的，因此只擅长一次专注的做好一件事情。人的认知也是一个由浅入深的过程，一层层细化便是利用了这个特点。

国内很多大学的计算机专业，比较偏重基础和理论的“灌输”（就我当时的体验，现在可能会好一些），对于代码能力，虽然也有一些课程实验，但往往不太够用。于是，在进入正式工作前，很多同学就会对自己代码水平不太自信。下面我就根据我自身的写代码经历提供一些建议。一些经历我是 2010 年上的北邮，当时也是很迷糊的就进了计算机专业。自然的，在大学一开始也谈不上什么学习规划。只能是沿用着高中的学习方法，懵懂地跟着老师走——上课就听课，课余就自习做作业。结果便是，学习效率很低，上课听不太懂、题目做不通透。但总归，上完计算机导论后，编程作业都是自己啃出来的，跌跌撞撞的完成之后，慢慢地竟感受到了编程的乐趣。我们当时大作业最多的几门课，C++ 程序设计、算法和数据结构、操作系统、计算机网络、微机原理等，现在想来，大部分都都跟玩具一样。后来做了国外一些知名大学公开课的实验才知道，要打造好一个实验项目，是非常难的事情：首先，得适配学生的水平，准备详尽的实验材料。其次，得搭好代码框架，在合适的地方“留白”，给学生“填空”。最后，还得构建足够好的自动化测试平台，进行打分。如果从头开发，这里面涉及到的复杂度、需要花的心思，并不比发一篇顶会论文简单。那作为教授来说，有这些时间，我为什么不去发一篇论文呢？毕竟国内高校都是科研第一、教学老末。因此，我在本科课内，代码水平也并没有打下太好的基础。后面在读研和工作中，不断摸索。回头来看，对我代码能力提升比较快的有这几个 “Code”：LeetCode、Writing/Review Code Loop、Clean Code。LeetCode在说 LeetCode 前，想先说说工作后，见到的一类神奇的人——打过算法比赛（通称 ACM，其实是 ICPC 和 CCPC）的同学的印象。这类同学的一大突出特点，用最简练的语言来形容，就是：出活快。几年的竞赛经历，让他们只要在脑袋中对需求（题目）理解之后，就能在最短的时间内转化为代码。由于太过懵懂，我自然是没有打过竞赛，等反应过来竞赛的诸般好处时，已经大三下了。当时，校队也不会招这么“大龄”的队员了，就算招，门槛也非常高。也是大学诸多憾事中的一件了。后来读了研，在找工作前一年时，LeetCode 已经相当流行了，便也和同学组队，互相激励着刷了起来。当时题目还不是特别多，到研二暑假找实习时，大概把前两百多道刷了两遍。一开始，会不断思考题目是什么意思，该用什么算法解，有时半天想不出来，便去看高票答案。很多高票解真的是精妙而简练，这大概也是当时 LeetCode 最吸引人的地方之一。慢慢的对各种类型题目有些感觉之后，就开始练速度和通过率。也就是上文说的，在理解题目后，能够迅速转变为 bug free 的代码。因此，虽然没有打过比赛，但是通过 LeetCode 的训练，确实也有了类似竞赛的收获。但自然，在深度、广度和速度上都远不及那些“身经百赛”的同学。不过我已经是受益匪浅：对常见数据结构和算法掌握纯熟。比如现在说起六种排序，特点、使用场景、背后原理，可以做到如数家珍；比如说起树的各种递归非递归遍历，脑动模拟递归执行过程，也是信手拈来；再比如链表、队列、图等特点，也能在脑中边模拟，边换成代码。学到了很多精巧的代码片段“构件”。比如如何二分、如何迭代、如何处理链表头尾节点、如何设计基本数据结构的接口等等。这些偏“原子”的构件，是我后来工作中写代码的血肉来源。但只有这些，是远远不够的，一到大项目里，写出的代码就很容易——“有佳句无佳章”。Writing/Review Code Loop遇到上述窘境，便是因为缺少中大型项目的磨练。表现在空间上，不知道如何组织上万行的代码，如何划分功能模块、构建层次体系；体现在在时间上，没有经过项目“起高楼、宴宾客、楼塌了”的构建-腐烂-重构循环。工程中在理解代码和组织代码时有个矛盾：可理解性。作为维护人员，我们学习代码时，多喜欢顺着数据流和控制流来理解，所谓根据某个头，一路追查到底，是为纵向。可维护性。但作为架构人员，我们组织代码时，为了容易维护，多是按照围绕模块来组织代码——把关联紧密的代码聚合到一块，是为横向。所以我们在拿到一个大工程时，如果立即按模块、地毯式的看代码，肯定会昏昏欲睡、事倍功半。不幸的是，由于多年读书养成的强大习惯，这个毛病跟了我很多年。正确的打开方式是，要像对待团在一起的多条线一样，找到“线头”，然后慢慢往外揪。在项目中，这些线头是：service 的 main 函数、各种单测入口。但我们在构建一个大工程时，又得反着来：先搭建一个揉在一起的主流程，然后逐渐迭代。就像盘古开天辟地一样，随着时间而演化，让天慢慢的升高、地慢慢下降，让整体化为地上四极、山川河流、太阳月亮。如是迭代，将一个混沌的流程，慢慢地模块化。比如常用的工具模块（utils）、业务相关基础模块（common）、控制模块（controller、manager）、RPC HTTP 等回调处理模块（processor）等等。但当然，如果你已经有了构建某种类型系统的经验，则并不需要在构建初期经历这个漫长过程，可以直接按经验分出一些模块。更有甚者，你已经形成了自己的一个代码库，比如时钟、网络、多线程、流控等等，在构建新的工程时可以直接拿来就用。剩下的问题就是对于细节的微调：1. 我们在进行分层时，边界处的功能，是往上升，还是往下沉；2. 某个较完整的结构，是拍平到使用类里，还是单独拎出来；这些形形色色的决策，都没有一个定则，更多的还是根据场景的需求、工期的长短等诸多实际情况，便宜行事。而这种背后的决策，则是在长时间对中大型项目的学习、对别人修改的 Review、自己上手搭架子和修修补补中，一点点形成的直觉和偏好。就像股票市场有周期一样，工程代码也是有其周期。不经历一个股市牛熊周期，我们不敢轻言空多；不经历过一个工程构建-成熟-腐烂的周期，我们也不敢轻言取舍。即，没有这些经验，我们就没办法在工程构建初期，预见到其最常用的打开方式，进而面向主要场景设计，牺牲次要场景的便利性。单元测试的重要性，怎么强调都不为过。一方面，能不能写出的单元测试，意味着你代码的模块边界是否清楚；另一方面，通过设计好的输入和输出，测试能够保证某种“不变性”，之后无论你怎么微调、重构，只要能跑过之前的测试，那就可以放心一半。另一半，就要靠自己和别人不断 Review 、测试集群线上集群不断地迭代了。所以，这个过程是一个无休止的 loop，不断的磨，尔后不断地提升。Clean Code最后说说对代码的品味。小节标题是：Clean Code，是因为我对代码的品味，最初是从 Clean Code: A Handbook of Agile Software Craftsmanship 这本书建立起来的。其第二章对命名——这个工程中“最难”的事情——的阐述，给我印象很深。工作中，我们常说，某某某对代码有“洁癖”。我也多少有一些，但我不以为是洁癖，而是一种对美的欣赏和追求。代码的美体现在哪里呢？我这里稍微抛个砖（当然，我之前也写文章就代码命名问题啰嗦过，感兴趣的可以点这里可以去看看）：一致性。比如具有相同含义的实体，使用相同的命名；而需要区分的实体，则要通过命名域（namespace）、前缀来进行甄别。从而给读者造成最小的心智负担。体系性。是指我们在做一组相关接口时，要考虑其体系性。比如增删改查，比如生产消费，比如预处理、处理、处理后，比如读取写入等等。体系性又包括对称性和逻辑性，让人在拿到一组接口时，就能最小成本地理解其是如何相互联系、又是如何具有区别的。没有赘肉。写代码，不要啰嗦，不要啰嗦，不要啰嗦。如果不小心啰嗦了，说明你可能没有想清楚所解决问题的本质。复杂的表象，在不断地剥离杂质后，往往有很简单的关窍。抓住这些关窍，再往其上附着骨肉，同时理清楚一对多、多对多等依赖关系，往往能化简为繁。在审美之外，还要说说建模（在某种程度上和隐喻是相通的）。毕竟，我们在说工程的“构建”时，本身就是借助的建筑学中的隐喻。软件工程中，类似的隐喻随处可见。我们大脑在认知新事物时，多建立在对旧的模型套用（好一点叫化用）上。因此，如果在处理模块时，如果能从经典的模型库中，找到一个相对合适的抽象，往往能够极大降低用户理解门槛。比如经典的生产者消费者模型、树形组织模型、路由器模型、线程调度模型、内存模型等等。此外，也可以使用某种常见意像、隐喻来命名项目，往往也能在易理解性上收获奇效。比如监控系统，可以叫“鹰眼”；比如各种流水线管控，可以叫“富士康”（手动斜眼）；再比如更常见一些的数据采集，我们都知道他叫——“爬虫”。最后，世间的事情往往是多方印证、互相补足的——如果你想写好代码，就不能只写代码，你得去读读历史、学学美术、写写文字，建立一套你自己的审美偏好，然后将其理念平移到写代码里来，才能写出符合直觉、具有美感的好代码。

图数据模型是一种对数据进行建模的方式。当下图数据模型中用的最多的建模方式是：属性图（Property Graph）。本文会探讨下属性图模型的基本概念和所面临的一些挑战。属性图主要包括三种元素：点（Node），边（Edge），和属性（Properties），其联系是：用点和边表达拓扑关系。在点和边上附着属性来存储数据。当下最流行的图查询语言是 Cypher，Cypher 和图模型的概念关系，就如如 SQL 和关系模型间的关系。在点边之外，Cypher 引入了对点和边的标记（Label）。下面，从学术角度，重新梳理一遍这几个元素的关系，并继续给出一些图中需要、但主流图查询语言还没有的元素。基本模型Basic Graph Data Model基本的图数据模型：从上图可以看出其基本特点是：有向（directed）图点（nodes）和边（edge）都是实体（entities）实体可以有标记（label）Property Graph Data Model属性图数据模型：其基本特点是：有向（directed）图点（nodes）和边（edge）都是实体（entities）实体可以包含标记（label）属性名、属性值对（ pairs）属性图的一些挑战市面上现有的图模型基本都是属性图，但在处理图问题上，存在一些挑战。挑战一：没有可组合性属性图不是可组合的（composable），所谓可组合性是指，经过查询语句处理返回的数据不再是图。以关系模型对照来看就很容易理解，在关系模型中，一切基于表（也就是关系）：存储数据是按表存，经过查询处理后，返回的结果仍然是表。但在属性图模型中，存储的是图，查询之后返回的却是属性表，或者点边列表。如果不满足可组合性，有很多缺点：不支持视图（子图）和嵌套查询（Sub-queries）。查询结果失去了原图的表达能力（毕竟不是图了）。挑战二：不支持原生路径也即，在属性图模型中，路径（Paths）不是一等公民。就跟传统面向对象的语言中，函数不是第一等公民一样（如：不能作为参数传递）。由于路径是二等公民，因此没有办法直接返回一个路径，而只能返回以某种形式表达的、组成路径的点集和边集。由于路径在图模型中非常基础，有大量基于路径查询的需求，如果不原生支持路径，会极大限制图查询语言的表达能力。挑战三：易处理性差属性图模型很难处理：对路径进行迭代返回没有还的路径（即简单路径）支持针对路径的任意过滤条件可选的模式匹配为此 LDBC GraphQL 工作组提出了 G-Core 模型，是一种路径属性图模型。Path Property Graph Data Model其特点是：有向（directed）图路径（paths）、点（nodes）和边（edge）都是实体（entities）实体可以包含标记（label）属性名、属性值对（ pairs）路径是图中连续边组成的序列。小结以后有人问你，属性图模型是什么？你就可以说，点边搭架子、属性附其上。如果他们再问，属性图模型有什么缺点？你可以继续说，没有组合性、不原生支持路径。这是一个新开的图数据库系列，还有什么想知道的，还有什么想了解的，欢迎留言讨论。参考资料A Survey Of Current Property Graph Query Languages：https://homepages.cwi.nl/~boncz/gql-survey.pdf