文章归档

最短shell代码实现乘法表

the first version:

[shell] for i in {1..5}; do for j in {1..5}; do let k=$i*$j; echo $i*$j=$k; done; done; [/shell]

then, i research for a while, and write the 2rd

[shell] seq 5 | awk '{for(i=1;i<=$1;i++){printf($1 "*"i"="i*$1" ")};print""}' [/shell]

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

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

 

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

»» 继续阅读全文

go语言TCPConn.Close()方法处理不当引发的bug

今天服务器引发了一个很罕见的bug。原因是因为TCPConn在Close的时候,把fd给清空掉了,如下:

// Close closes the TCP connection. func (c *TCPConn) Close() error { if !c.ok() { return syscall.EINVAL } err := c.fd.Close() c.fd = nil return err }

而TCPConn是经常在多个goroutine里同时使用的。

// Read implements the Conn Read method. func (c *TCPConn) Read(b []byte) (n int, err error) { if !c.ok() { return 0, syscall.EINVAL } return c.fd.Read(b) }

这样就很有可能当某个goroutine,判断!c.ok(),为真,然后尝试读取数据时。注意,这个过程,中间,if语句之后和Read()数据之前,很可能TCPConn已经被关闭,fd被置为nil了,引发panic

go1版本有这个问题。新版已经fix了。不过我还觉得蛮奇怪的,想不清楚为什么作者要这么写。。。

Open Clound storage service

国庆这几天写的,套用阿里云的名称,就叫开放云存储服务吧,初衷只是想测试一下存储商的速度,后来发觉php写的SpeedTest不太好用,因为要依赖php和其他各个组件。

后来折腾了一下hiphop,这玩意依赖太过分了,用的很不爽,就用go重新实现了一遍存储的SDK。目前OCSS支持四个主流的云存储服务,包括盛大云,阿里云,又拍和七牛。它们的API是一样的(看起来是一样的,呵呵)

数据结构

在package fs里,有Object和Bucket,主要的结构如下,但不同的存储商的SDK又各有一些不同的地方,可看源码

type Object struct { EntryURI string Type string Mtime string Size int64 Body io.ReadWriter } type Bucket struct { EntryURI, Delimiter string Objs []*Object CommonPrefixes []string }

EntryURI通常由Bucket和Key组成,例如"/testbucket/resume.pdf"或者是"/testbucket/music/",Object可以表示一个文件或者目录。Bucket里的Delimiter是用来进行前缀查询的,会一直匹配到Delimiter才结束,然后返回的对象会保存到Objs和CommonPrefixes里,Objs通常可以理解成文件,CommonPrefixes可理解成当前路径下的文件夹名

存储API

所有的SDK都实现了如下的API,用法几乎是完全一样的,当然,还有其他的。

func (s *Service) Get(localfile, entryURI string) (code int, err error) func (s *Service) Put(entryURI, mimeType, localfile string) (code int, err error) func (s *Service) Delete(entryURI string) (code int, err error) func (s *Service) PutObject(o *fs.Object) (code int, err error) func (s *Service) GetObject(o *fs.Object) (code int, err error) func (s *Service) DelObject(o *fs.Object) (code int, err error) func (s *Service) NewBucket(b *fs.Bucket) (code int, err

»» 继续阅读全文

LIRS缓存

参考文献:LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance

LIRS算法主要计算两个参数,IRR和Recency,IRR表示一个页面最近两次被访问访问间隔,Recency表示页面最近一次被访问到现在的访问间隔。IRR越小,表明最近可能经常被访问,Recency越大,表明最近很久没被访问。IRR和Recency的计算方法如下:

这就是LIRS的理论模型,在任何一个时刻,缓存中的每个页面都会有一个IRR值和Recency值。LIRS的核心思想是,如果一个页面当前的IRR越大,将来的IRR会更大。

论文中没有对LIRS的实现作过多的描述,只是简单提到了一个基于Stack的实现方法。

一、替换规则

和LRU不同的是,就是当缓存达到阈值时

  1. 如果是LRU,就会将Recency值最大的那个页面剔除出去,因为这个页面是最近最久没有被访问的
  2. 如果是LIRS,优先剔除IRR值最大的页面,因为IRR越大,说明这个页面过去很少被访问,理所当然认为它在将来可能不会再被访问或者相对其他页面来说最不可能再被访问到。如果有两个页面的IRR相同,则剔除Recency值最大的页面。

显然,LIRS只是一个多了IRR参数的LRU

(待)

linear counting algorithm

最近看了篇文章:Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory

比较感兴趣,于是找了原论文来看看:A Linear-Time Probabilistic Counting Algorithm for Database Applications / HyperLogLog : the analysis of a near-optimal cardinality estimation algorithm. 无奈hyperloglog实在复杂,难以理解,哪天看懂了再分享吧。

linear counting的作用就是统计集合的容量。算法思想和bloom-filter差不多,很多时候精确计算是很难做到的,但是可以允许一定的误差,从而通过这个误差的概率分析来折射整个全局的概貌。

  1. Algorithm Basic Linear Counting:
  2. Let key_{i} = the key for the ith tuple in the relation.
  3. Initialize the bit map to "0"s.
  4. for i = 1 to q do
  5. hash_value = hash( key_{i} )
  6. bit map(hash_value) = "1"
  7. end for
  8. U_{n} = number of "0"s in the bit map
  9. »» 继续阅读全文

2012数据库技术交流会

分享几个大会的PPT,一时拿不全,后续慢慢补上。

内容很精彩,这几天实在太累了,因为住的地方,还有中午吃饭很成问题,干脆中午不吃饭,挨到晚上再吃点,哈哈。因为有时吃饭回来连门口都挤不进去了,酱油实在太多了。不过很好,可以结识更多的朋友。

>> Taobao数据库这5年

View more presentations from yp_fangdong >> 百度分布式数据实践与进展

View more presentations from yp_fangdong >> Redis大数据之路 dtcc-唐福林

View more presentations from yp_fangdong >> 百度数据库中间层

View more presentations from yp_fangdong >> 分布式文件系统Fast dfs架构剖析及配置优化

View more presentations from yp_fangdong >> Hbase在淘宝的应用与优化 修改

View more presentations from yp_fangdong >> »» 继续阅读全文

第 2 页,共 4 页1234