文章归档

系统相关领域的一些学习材料

原文:架构相关领域的一些学习材料 by 林仕鼎

对于工程师来说,到一定阶段后往往会遇到成长瓶颈。要突破此瓶颈,需要在所属技术领域更深入学习,了解本领域的问题本质、方法论与设计理念、发展历 史等。以下提供一些架构相关领域的学习材料,附上简单点评,供有兴趣的工程师参考。希望大家能通过对这些领域的了解和学习,掌握更多system design principles,在自己的工作中得心应手,步入自由王国。

1. Operating Systems

Mach [Intro: http://www-2.cs.cmu.edu/afs/cs/project/mach/public/www/mach.html, Paper: http://www-2.cs.cmu.edu/afs/cs/project/mach/public/www/doc/publications.html]

传 统的kernel实现中,对中断的响应是在一个“大函数”里实现的。称为大函数的原因是从中断的入口到出口都是同一个控制流,当有中断重入发生的时候,实 现逻辑将变得非常复杂。大多数的OS,如UNIX,都采用这种monolithic kernel architecture。1985年开始的Mach项目,提出了一种全新的microkernel结构,使得由于70年代UNIX的发展到了极致而觉得后续无枝可依的学术界顿时找到了兴奋点,也开始了沸沸扬扬的monokernel与microkernel的争论。插播一个花絮:Mach的主导者Richard Rashid,彼时是CMU的教授,受Bill Gates之托去游说Jim Gray加盟MS。结果把自己也被绕了进来,组建了Microsoft Research。他到中国来做过几次21 Century Computing的keynotes。

Exokernel [Intro: http://pdos.csail.mit.edu/exo/,Paper: http://pdos.csail.mit.edu/PDOS-papers.html#Exokernels]

虽 然microkernel的结构很好,但实际中并没有广泛应用,因为performance太差,而且大家逐渐发现OS的问题并不在于实现的复杂性,而更 多在于如何提高application使用资源的灵活性。这也就是在kernel extension(例如loadable module in Linux)出现后,有关OS kernel architecture的争论就慢慢淡出人们视线的原因。

Exokernel正是在这样的 背景中出现的,它并不提供传统OS的abstraction(process, virtual memory等),而是专注于资源隔离与复用(resource isolation and multiplexing),由MIT提出。在exokernel之上,提供了一套库,著名的libOS,用于实现各种OS的interface。这样的 结构为application提供了最大的灵活度,使不同的application可以或专注于调度公平性或响应实时性,或专注于提高资源使用效率以优化 性能。以今天的眼光来看,exokernel更像是一个virtual machine monitor。

Singularity [Intro: http://research.microsoft.com/os/Singularity/, Paper: http://www.research.microsoft.com/os/singularity/publications/HotOS2005_BroadNewResearch.pdf]

Singularity 出现在virus,spyware取之不尽、杀之不绝的21世纪初期,由Microsoft Research提出。学术界和工业界都在讨论如何提供一个trust-worthy computing环境,如何使计算机系统更具有manage-ability。Singularity认为要解决这些问题,底层系统必须提供hard isolation,而以前人们都依赖的硬件virtual memory机制并无法提供高灵活性和良好性能。在.Net和Java等runtime出现之后,一个软件级的解决方案成为可能。

Singularity 在microkernel的基础上,通过.Net构建了一套type-safed assembly作为ABI,同时规定了数据交换的message passing机制,从根本上防止了修改隔离数据的可能。再加上对application的安全性检查,从而提供一个可控、可管理的操作系统。由 于.Net CLR的持续优化以及硬件的发展,加了这些检查后的Singularity在性能上的损失相对于它提供的这些良好特性,仍是可以接受的。

这种设计目前还处于实验室阶段,是否能最终胜出,还需要有当年UNIX的机遇。

2. Virtual Machines

VMWare ["Memory Resource Management in VMware ESX Server",OSDI’02, Best paper award]

耳熟能详的vmware,无需多说。

ZEN [“Xen and the Art of Virtualization”,

»» 继续阅读全文

git in a nutshell

一些参考资料

  1. kernel docs: https://www.kernel.org/pub/software/scm/git/docs
  2. git data format: http://git.rsbx.net/Documents/Git_Data_Formats.txt
  3. 源码

git的存储就是一个kv数据库。存储的对象包括blob(文件),tree(目录),还有commit等。 对象的key就是value的sha1值。

git将工作区组织成一个hash-tree,hash用的是sha1。hash-tree上的叶子结点是blob,也就是文件,中间结点是tree,也就是目录。任何一个结点的内容发生变化最终都会蔓延到根结点(意味着其sha1值发生变化,父结点的sha1值也会发生变化(因为它的目录项里是保存了子结点的sha1值,如果子结点被修改,这个sha1值也会被修改),其实从根结点到被修改的结点这个路径上所有的结点的sha1值都会发生变化)

另外,git并不直接修改原来结点的内容,而是直接存储一个新的结点,新的key是修改后内容(整个对象的内容,而不是仅仅指修改部分的内容)的sha1值。存储层会在恰当的时候对这些结点进行gc(因为很多结点实际上大部分内容都是相同的),打包到一个pack文件里以节省空间。

commit过程

commit会将当前修改过的所有文件(git add后会有记录),重新生成一个新的hash-tree,注意这个新的hash-tree大部分结点和上一个commit的结点都是相同的,如下图所示:当C文件被修改后,git会为A/B/C这条路径上的所有结点创建一个新的结点E/F/G。commit只需要知道当前的根结点和父commit即可(形成一个commit列表,git rev-list --all可以将这个链表打印出来)。

push过程

1、与服务器通讯,取得服务器当前分支所处的commit,与本地当前的commit比较,然后得出,本次需要push到服务端的commit列表。假设只有一个commit需要提交,如上图所示(多个commit的处理过程类似)。 设commit1是服务端当前分支的commit 设commit2是本地当前分支的commit

2、将commit1所有的结点找出来(不会消耗太多内存,因为叶子结点的内容,也就是文件数据是不会被读取到内存里的),做个标记。 将commit2所有的结点找出来,将带标记的结点去掉。剩下的结点就是本次需要push需要上传到服务端。这个过程也会很快,因为如果某个中间结点(例如上图的H结点)被标记了,下面所有的结点都不需要判断了。

3、将这些结点(key-value)打包成一个pack文件,和git在gc时(所有的key-value都参与)创建pack文件是一样的。 pack文件是自描述的。服务器解压pack后更新当前分支的commit信息。

Linux Performance Analysis and Tools

原文:Linux performance analysis and tools

 

世纪公园踏春篇

春天来了天气不错,拉几个朋友一起骑车到世纪公园踏春。

Linux: The Journaling Block Device

Kedar Sovani on kerneltrap

Atomicity is a property of an operation either to succeed or fail completely. Disks assure atomicity at the sector level. This means that a write to a sector either goes through completely or not at all. But when an operation spans over multiple sectors of the disk, a higher-level mechanism is needed. This mechanism should ensure that modifications to the entire set of sectors are handled atomically. Failure to do so leads to inconsistencies. This document talks about the implementation of the Journaling Block Device in Linux.

Let's look at how these inconsistencies could

»» 继续阅读全文

Haystack

文献原址:Finding a needle in Haystack: Facebook's photo storage 

一:简介:

  1. 2600亿照片,20PB数据量
  2. 每周60TB,10亿照片
  3. 每秒100w张图片的检索速度
  4. 对象存储,我们的图片只写,不修改,很少删除
  5. 传统POSIX文件系统成为瓶颈

论文中提到瓶颈是由于传统的POSIX文件系统是基于目录和metadata来管理文件的,通常取一张图片都会涉及好几个IO操作:

  1. 从文件名得到inode号
  2. 将inode信息从磁盘读取出来
  3. 读取文件。

对于一些稍微复杂的架构,1步骤可能会更频繁些。 Haystack设计的目标:

  1. 高吞吐量和低延迟
  2. 分区容忍性
  3. 低成本。通过两个维度来控制,每TB可用数据的利用率和每TB可用数据的读速率(这里的可用考虑到底层文件系统,磁盘阵列,冗余等各种因素)
  4. 简单。

二、背景

  1. 典型设计,存储集群 + cdn
  2. NFS文件系统

 

CDN通常是用来缓存热数据的,但是对于像facebook这样的互联网站,通常需要产生大量的非热数据内容,而恰恰是这些不太热的数据内容,大量地升高了CDN回源的压力,facebook引用了长尾理论来解析这一效应。在NFS卷里,facebook最初默认是每个目录存储上千个文件,但是由于NAS设备对目录metadata的管理方式,导致在一个目录里存放上千个文件相当困难,因为目录的blockmap太大了。这种情况下读1张图片最少也要10个IO,就算让目录存放的文件数降低到100,也仍然会有3个IO才能读到一张图片。 为了减少磁盘操作的次数,facebook还在Photo Store servers上缓存NAS设备返回的file handle,这个是通过增加内核API(open_by_filehandle)来实现的。facebook从NAS上学到的经验就是:通过缓存来降低磁盘IO的操作是很有限的。 也许有人会说,可以使用memcache来缓存所有的file handles。对此facebook坦言,也许这是一个解决方案,但是只能解决这里部分的问题,因为这么做的话需要NAS设备缓存所有的inodes信息,只不过是一种昂贵的传统存储方案罢了。 

三、设计与实现 

方案:CDN解决热数据问题,Haystack解决长尾效应。 Haystack的主要目的就是为了解决NFS存储方案中高磁盘IO的问题。Haystack的做法是:降低文件系统的metadata的内存占用,因此尽可能的将所有的metadata放在内存里,例如它将多个小文件存在一个大文件里。

1)三个核心组建:Haystack Directory, Haystack cache, Haystack store 

 

Store是由物理卷组成的,容量由物理卷的数量来控制,100个物理卷可提供10TB的存储空间。物理卷还会组合成一个逻辑卷,单个逻辑卷中的所有物理卷数据是相同的,冗余。Directory主要保存应用方面的数据信息,例如每张图片存放在哪个逻辑卷上,还有逻辑卷到物理卷的映射以及逻辑卷的剩余空间。Cache相当于一个内部的CDN。 

2)URL规格

»» 继续阅读全文

goroutine的实现原理

goroutine的实现主要依赖下面这几个API,linux386平台的实现在runtime/asm_386.s文件里。这里只显示API [c]// void gosave(Gobuf*)

// void gogo(Gobuf*, uintptr) // restore state from Gobuf; longjmp

// void gogocall(Gobuf*, void (*fn)(void)) // restore state from Gobuf but then call fn. // (call fn, returning to state in Gobuf)

// void mcall(void (*fn)(G*)) // Switch to m->g0's stack, call fn(g). // Fn must never return. It should gogo(&g->sched) // to keep running g.[/c] 而调度的实现是在runtime/proc.c文件里。

gosave类似于setjmp,但它也保存了当前正在运行的G的状态,PC和SP,gogo类似于longjmp,恢复G的SP和PC。SP和PC是通过一个Gobuf的结构来维护的。gogocall和gogo的作用差不多,但跳转到相应的G之后,会继续执行一个fn函数。mcall稍微复杂点,但也和googcall类似。

通常从M跳转到G的执行,是使用gogo,而从G跳转到M,是使用mcall。这是因为在M的栈上运行的只有一个mstart()函数,而在mstart()函数内主要的工作就是初始化一些数据,然后最后触发调度器schedule(),所以如果是使用gogo从G返回到M,那么M就会执行完毕。

整个过程就是通过一个全局的Sched结构来维护所有的调度状态。比libtask的实现复杂点,和xv6的proc实现也差不多。

lua 5.1虚拟机

  1. The Implementation of Lua 5.0
  2. 手册:http://www.lua.org/manual/5.1/manual.html
  3. lua源码欣赏:http://www.codingnow.com/temp/readinglua.pdf
  4. 指令集:A No Frills Intro To Lua51 VM Instructions.pdf

蛮有用的资料,对vm 5.1的理解很有帮助。

面向软件错误构建可靠的分布式系统

Making reliable distributed systems in the presence of sodware errors

1 问题域

  • 并发(concurrency)
  • 软实时(soft real-time)
  • 分布式(distributed)
  • 硬件交互(hardware interaction)
  • 大型软件系统(large software systems)
  • 复杂的功能(complex functionality)
  • 持续运行(continuous operation)
  • 高质量要求(quality requirements)
  • 容错(fault tolerance)

2 哲学

容错和故障隔离。例如进程和基于消息的交互。

3 系统需求

  • 并发性
  • 错误封装 即一个进程的错误一定不能破坏系统中其他的进程
  • 故障检测 包括本地和网络异常
  • 故障识别
  • 代码升级
  • 持久存储 以便恢复崩溃的系统。

4 语言需求

  • 封装原语
  • 并发性
  • 错误检测原语
  • 位置透明
  • 动态代码升级

5 库需求

  • 持久存储
  • 设备驱动程序
  • 代码升级
  • 运行基础

Lua之魂?

云风翻译了 《Masterminds of Programming: Conversations with the Creators of Major Programming Languages》中关于Lua发明人的一段对话,甚好,看来有必要一读此书

7. Lua

Lua 是一门非常之小,但五脏俱全的动态语言。它由 Roberto Ierusalimschy、Luiz Henrique de Figueiredo 和 Waldemar Celes在1993年创建。Lua 拥有一组精简的强大特性,以及容易使用的 C API ,这使得它易于嵌入与扩展来表达特定领域的概念。Lua在专有软件界声名显赫。例如,在诸多游戏中,比如 Blizzard(暴雪)公司的《魔兽世界》和 Crytek GmbH 公司的《孤岛危机》,还有 Adobe 的 Photoshop Lightroom ,都使用它来作脚本 和 UI 方面的工作。它继承了 Lisp 和 Scheme,或许还有 AWK 的血脉 ; 在设计上类似于 JavaScript、Icon 和 Tcl。

7.1 脚本的威力

你是如何定义 Lua 的?

LHF:一种可嵌入,轻量,快速,功能强大的脚本语言。

Roberto:不幸的是,越来越多的人们使用“脚本语言”作为“动态语言”的代名词。现在,甚至是 Erlang 或者 Scheme 都被称为脚本语言。这非常糟糕,因为我们无法精确的描述一类特定的动态语言。在最初的含义解释中,Lua 是一种脚本语言,这种语言通常用来控制其它语言编写的其他组件。

人们在使用Lua设计软件时,应该注意些什么呢?

Luiz:我想应该是用 Lua 的方式来做事。不建议去模拟出所有你在其它语言中用到的东西。你应该真的去用这个语言提供的特性,我想对于使用任何一门语言都是这样的。就 Lua 来讲,语言的特性主要指用 table 表示所有的东西,用 metamethod 做出优雅的解决方案。还有 coroutine 。

Lua 的用户应该是哪些人呢?

Roberto :我认为大多数没有脚本功能的应用程序都能从 Lua 中受益。

Luiz:问题在于,大多数设计者很长时间都不会意识到有这种需求。当已经有了诸多用 C 或 C++ 编写的代码,为时已晚。应用程序设计者应该从一开始就考虑脚本。这会给它们带来更多的灵活性。而且这样做还可以更好的把握性能问题。因为这样做以后,会迫 使他们去考虑程序中到底哪里是性能关键,而哪些地方无伤大雅。而这些性能不太重要之处,就交给脚本去处理,开发周期短,速度快。

从安全性的观点来看,Lua 能为程序员提供些什么呢?

Roberto:Lua 解释器的核心部分被构建为一个 “独立的应用程序(freestanding application)”。这个术语来自 ISO C,大意是说,这部分不使用任何跟外部环境有关的东西(不依赖 stdio、malloc 等)。所有那些功能都由扩展库来提供。使用这种体系结构,很容易让程序限制对外部资源的访问。具体来说,我们可以在 Lua 自身的内部创建出一个沙盒,把如何我们认为危险的操作从沙盒的外部环境中剔除。(比如打开文件等)

Luiz:Lua

»» 继续阅读全文

第 9 页,共 13 页« 最新...7891011...最旧 »