概述

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

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

阅读全文 »

引子

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

1
2
3
4
5
6
7
8
9
10
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. 投影升序。

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

入题

给定一个二叉搜索树 t (树中没有相同值的节点)以及其中的一个节点的值 val*,请以 *val 为界,将 t 拆为两棵新的二叉树 sl,要求:

阅读全文 »

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

馅老满的炒红果吃过两次,初吃很爽口,多吃几颗便发腻。于是早就想着自己也做点吃,自然要少糖!少糖!少糖!去年做过一次,但是山楂小且成色差,去籽手法也不好,做出来的差强人意。

近两年还和山楂还有过几次缘分。一次是在微软时,茶水间的阿姨有时候会熬一点山楂汤,有时候是雪梨汤。但印象最深的还是山楂汤:酸口、微甜,汤汁粘稠,如缎子一般,每次我会偷偷喝好几杯。一次是在哈尔滨在坐飞机,在去登机口路过的小店里,见识了不下几十种山楂制品,是在有点开眼,忍不住买了几样。不过,我是个老想不起吃零食的人,最后都在角落里落了灰。

阅读全文 »

在使用 github pages + hexo + next 搭建了 Hexo 博客 并用了一段时间后,想对博客进一步进行定制和美化,记录在这里。

添加“关于”标签

由于我使用的是 next 主题,两步就够了:

  1. 通过 hexo 引擎新建索引页:hexo new page "about"

  2. 菜单显示 about 链接,在主题的 _configy.yml 设置中将 menuabout 前面的注释去掉即可。

    1
    2
    3
    4
    5
    menu:
    home: /
    archives: /archives
    tags: /tags
    about: /about
阅读全文 »

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

引子

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

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

阅读全文 »

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

概述

Ray 核心的设计之一就是基于资源定制的细粒度、高吞吐的任务调度。为了实现这一点,Ray 将所有输入和输出存在基于共享内存的 Plasma 中;将所有状态存在基于 Redis 的 GCS 中,然后基于此进行去中心化的调度。即每个节点都可以拿到全局信息来进行局部调度决策,不过这也是不好做复杂调度策略的原因之一。

阅读全文 »

小引

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

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

其主要设计细节如下:

  • 简化系统元信息:Master 中维持了两个重要的映射,分别是文件路径到逻辑数据块,逻辑块与其多副本之间的关系。
  • 较大的数据块:选择了当时看来相当大的 64M 作为数据存储的基本单位,以此来减少元信息。
  • 放宽的一致性:允许多副本间内容不一致来简化实现、提高性能,通过读校验来保证损坏数据对用户不可见。
  • 高效副本同步:在多副本同步时分离控制流和数据流,利用网络拓扑提高同步效率。
  • 租约分散压力:Master 通过租约将部分权力下放给某个 Chunkserver ,负责某个块的多副本间的读写控制。
  • 追加并发优化:多客户端对同一文件进行并发追加,保证数据原子性及At Least Once的语义。
  • 快速备份支持:使用 COW 策略实现快照操作,并通过块的引用计数来进行写时拷贝。
  • 逐节点锁控制:对于每个操作,需要沿着文件路径逐节点获取读锁,叶子节点获取读锁或者写锁,当然文件路径会进行前缀压缩。
  • 异步垃圾回收:将数据删除与其他一些主节点的维护操作(损坏块清除,过期数据块移除)统一起来,成为一个定期过程。
  • 版本号标记:帮助客户端识别过期数据。
  • 数据块校验和:针对每 64KB 的小块打上 32 bit 的校验和。
阅读全文 »

引子

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. 两层调度架构:分本地调度器和全局调度器;任务请求首先被提交到本地调度器,本地调度器会尽量在本地执行任务,以减少网络开销。在资源约束、数据依赖或者负载状况不符合期望时,会转给全局调度器来进行全局调度。
阅读全文 »