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

小引

二叉树（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），以进行高效的系统实现（所谓量体裁衣）。这其中，如何找到一个合适的计算抽象，是最难的部分，既要对需求有直觉般的了解，又要具有极高的计算机科学素养。当然，并且可能更为接近现实的是，该抽象是在根据需求不断试错后进化出的海水之上的冰山一角。

导读

继 Spark 之后，UC Berkeley AMP 实验室又推出一重磅高性能AI计算引擎——Ray，号称支持每秒数百万次任务调度。那么它是怎么做到的呢？在试用之后，简单总结一下：

1. 极简 Python API 接口：在函数或者类定义时加上 ray.remote 的装饰器并做一些微小改变，就能将单机代码变为分布式代码。这意味着不仅可以远程执行纯函数，还可以远程注册一个类（Actor模型），在其中维护大量context（成员变量），并远程调用其成员方法来改变这些上下文。
2. 高效数据存储和传输：每个节点上通过共享内存（多进程访问无需拷贝）维护了一块局部的对象存储，然后利用专门优化过的 Apache Arrow格式来进行不同节点间的数据交换。
3. 动态图计算模型：这一点得益于前两点，将远程调用返回的 future 句柄传给其他的远程函数或者角色方法，即通过远程函数的嵌套调用构建复杂的计算拓扑，并基于对象存储的发布订阅模式来进行动态触发执行。
4. 全局状态维护：将全局的控制状态（而非数据）利用 Redis 分片来维护，使得其他组件可以方便的进行平滑扩展和错误恢复。当然，每个 redis 分片通过 chain-replica 来避免单点。
5. 两层调度架构：分本地调度器和全局调度器；任务请求首先被提交到本地调度器，本地调度器会尽量在本地执行任务，以减少网络开销。在资源约束、数据依赖或者负载状况不符合期望时，会转给全局调度器来进行全局调度。

当然，还有一些需要优化的地方，比如 Job 级别的封装（以进行多租户资源配给），待优化的垃圾回收算法（针对对象存储，现在只是粗暴的 LRU），多语言支持（最近支持了Java，但不知道好不好用）等等。但是瑕不掩瑜，其架构设计和实现思路还是有很多可以借鉴的地方。

引子

栽在 Python 的默认参数的“坑”中几次之后打算专门弄一篇博客来说一下这个事情。但是最近看到一篇很好地英文文章（Default Parameter Values in Python，Fredrik Lundh | July 17, 2008 | based on a comp.lang.python post），鞭辟入里。珠玉在前，就不舞文弄墨了。当然，也算是偷个懒，在这里简单翻译一下，希望更多的人能看到。

以下是翻译，意译，加了一些私货，不严格跟原文保持一致，语法特性以 Python3 为准。

概览

首先说下 BLOB 的意思， 英文全称是 Binary Large OBjects，可以理解为任意二进制格式的大对象；在 Facebook 的语境下，也就是用户在账户里上传的的图片，视频以及文档等数据，这些数据具有一次创建，多次读取，不会修改，偶尔删除 的特点。

之前简单翻译了 Facebook 的前驱之作 —— Haystack，随着业务量发展，数据量进一步增大，过去玩法又不转了，如果所有 BLOG 都用 Haystack 存，由于其三备份的实现，在这个量级下，性价比很低。但是完全用网络挂载+传统磁盘+Unix-like（POSIX）文件系统等冷存储，读取跟不上。于是计算机科学中最常用的分而治之的思想登场了。

他们首先统计了 BLOBs 的访问频次与创建时间的关系，然后提出了随着时间推移 BLOB 访问出现的冷热分布概念（和长尾效应差不多）。并据此提出了热、温分开的访问策略：用 HayStack 当做热存储去应对那些频繁访问的流量，然后用 F4 去响应剩下的不那么频繁访问的 BLOB流量，在此假设（F4只存储那些基本不怎么变动，访问量相对不大的数据）前提下，可以大大简化 F4 的设计。当然有个专门的路由层于两者之上进行了屏蔽，并进行决策和路由。

对于 Haystack 来说，从其论文出来时，已经过去了七年（07~14）。相对于当时，做了少许更新，比如说去掉了 Flag 位，在 data file，Index file 之外，增加了 journal file，专门用来记录被删除的 BLOB 条目。

对于 F4 来说，主要设计目的在于保证容错的前提下尽可能的减小有效冗余倍数（effective-replication-factor），以应对日益增长的温数据 存取需求。此外更加模块化，可扩展性更好，即能以加机器方式平滑扩展应对数据的不断增长。

我总结一下，本论文主要高光点就是温热分开，冗余编码，异地取或。