文章归档

goroutine scheduler

some references

  • Analysis of the Go runtime scheduler
  • Dmitry Vyukov. Scalable Go Scheduler Design Doc

go runtime and go scheduler

The runtime keeps track of each goroutine, and will schedule them to run in turn on a pool of threads belonging to the process. Goroutines are separate from threads but rely upon them to run, and scheduling goroutines onto threads effectively is crucial for the efficient performance of Go programs. The idea behind goroutines is that they are capable of running concurrently, like threads, but are also extremely lightweight in comparison. So, while there might be multiple threads

»» 继续阅读全文

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

原文:架构相关领域的一些学习材料 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

 

世纪公园踏春篇

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