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

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

引子

由于 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 fileIndex file 之外,增加了 journal file,专门用来记录被删除的 BLOB 条目。

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

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

阅读全文 »

概览

Haystack 的基本思想就是将索引信息放在内存中,避免额外的IO。为了做到这一点,主要进行了两方面的设计:

  1. 将小文件集合成大文件,减少文件数,从而减少了元信息的数目。
  2. 精简文件元信息,去掉一切在 Facebook 场景中不需要的 POSIX 语义中元信息。

这样就可以将数据元信息减小到一个内存可以放的下的量级,基本上每次每次数据访问同一个一次 IO 就可以完成,而非以前的好几次。

阅读全文 »

绪论

使用 Logging 前可以先捋一下我们常见的日志输出需求,俗话说,不管需求的设计就是耍流氓。

  1. 能够定位事件(Event)的产生位置(代码文件&行数)和生成时间,用于调试和跟踪。
  2. 一份日志可以同时送到多个目标输出
  3. 可以通过不同级别或者更精细条件筛选日志输出。
  4. 可以方便的控制第三方模块的日志输出。
  5. 实现上面的一切的前提下,配置/设置 尽量简单。

Python 的 Logging 模块通过神奇的模块化设计,形的方式组织完美的实现了以上五点。

阅读全文 »

引言

某次在用到 Python 的 socketserver 时,看到了 ForkingMixInThreadingMixIn。当时就对这种插件式语法糖感觉很神奇。最近自己写代码,也想写一些这种即插即用的插件代码,于是对 python 的 mix-in 机制探究了一番。

简单来说它是利用多继承的特性,通过插拔额外代码片段,对原类进行花样式增强的一种技术。

阅读全文 »