木鸟杂记

小引

最近在写 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 是一款谷歌开源的非常优秀的构建系统。它的定位，用官方的话来说是：

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 中生成器是什么？答曰：有 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

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

小引

二叉树（Binary Tree）是数据结构中很好玩的一种，可以把玩的地方非常之多。而二叉搜索树（Binary Serach Tree，下面简称 BST，当然也有叫二叉查找树、查找二叉树等等）又是其中常用的一种，它有很多有趣的性质：

1. 左皆小，右皆大。
2. 中序遍历有序。
3. 投影升序。

当然，加上平衡会引入更多的特性，这里先按下不表。今天先从个小题入手把玩一番。

季秋时节，各种果子纷至沓来。山楂，我们那叫山里红，北京好像称红果。老北京一道有名的菜便是“炒红果”。这天去菜市场，发现今年的个大成色好，便赶紧买了些来。

在使用 github pages + hexo + next 搭建了 Hexo 博客 并用了一段时间后，想对博客进一步进行定制和美化，记录在这里。过程中发现英文文档要比中文文档详细很多，基本上 thems/next/_config.yaml 中所涉及到的所有设置都有讲解，所以如果英文不错，还是看英文文档吧：https://theme-next.org/docs/ 。

此外，每次修改后记得及时用 hexo s 在本地http://localhost:4000/部署查看效果，看是否达到了自己的预期。

上一篇讲了待调度任务的组织形式，这一篇来继续挑软骨头啃：节点资源抽象和调度策略。

引子

由于 Ray 支持对任务进行显式的资源约束，因此需要对所有节点的资源进行硬件无关的抽象，将所有资源归一化管理，以在逻辑层面对资源进行增删。当有节点加入，需要感知其资源总量大小；当有任务调度，需要寻找满足约束节点；当任务调度成功，可以获取剩余可用资源等等。

Ray 除了对标准资源如 CPU，GPU 的支持，还支持对用户自定义 label 的资源的调度。用户在启动节点（ray start --resources <resources>）指定该节点具有某种类别的资源（比如说 memory，bandwidth，某种型号的 GPU 等等）的总量，在定义 remote 函数时指定任务使用多少该类别的资源，Ray 的调度器在调度该任务时，就会按照用户自定义的资源需求将其调度到特定的机器上去。这是一种用户代码和调度器交互的一种有趣设计。

对于调度策略，由于 Ray 是去中心化的调度，很容易存在不一致状态。最简单的在实践中反而是统计最优的——对于每个任务找到符合资源约束的节点，随机选择一个，将任务调度过去。

之前文章写了 Ray 的论文翻译。后来我花了些时间读了读 Ray 的源码，为了学习和记忆，后续预计会出一系列的源码解析文章。为了做到能持续更新，尽量将模块拆碎些，以保持较短篇幅。另外，阅历所限，源码理解不免有偏颇指出，欢迎大家一块讨论。

小引

GFS 是谷歌为其业务定制开发的，支持弹性伸缩，为海量数据而生的分布式大文件存储系统。它运行于通用廉价商用服务器集群上，具有自动容错功能，支持大量客户端的并发访问。

GFS 是为大文件而生的，针对读多于写的场景。虽然支持对文件修改，但只对追加做了优化。同时不支持 POSIX 语义，但是实现了类似的文件操作的API。它是谷歌在 MapReduce 同时期，为了解决大规模索引等数据存储所实现的具有开创性的工业级的大规模存储系统。

引子

MapReduce 是谷歌 2004 年（Google 内部是从03年写出第一个版本）发表的论文里提出的一个概念。虽然已经过去15 年了，但现在回顾这个大数据时代始祖级别概念的背景、原理和实现，仍能获得对分布式系统的很多直觉性的启发，所谓温故而知新。

在Google 的语境里，MapReduce 既是一种编程模型，也是支持该模型的一种分布式系统实现。它的提出，让没有分布式系统背景的开发者，也能较轻松的利用大规模集群以高吞吐量的方式来处理海量数据。其解决问题思路很值得借鉴：找到需求的痛点（如海量索引如何维护，更新和排名），对处理关键流程进行高阶抽象（分片Map，按需Reduce），以进行高效的系统实现（所谓量体裁衣）。这其中，如何找到一个合适的计算抽象，是最难的部分，既要对需求有直觉般的了解，又要具有极高的计算机科学素养。当然，并且可能更为接近现实的是，该抽象是在根据需求不断试错后进化出的海水之上的冰山一角。