RSS Feed

Posts Tagged ‘paper’

  1. Lease Activating

    August 30, 2016 by xudifsd

    Lease is a very useful and pervasive technique in distributed system, it can be used to authorize other nodes in the system. For example, in master election, follower nodes would use lease to promise current master that they will not elect another master until the lease is expired. But the problem is how can you make sure that current master will not think it still holds the lease after lease grantors think otherwise?

    It is not an easy question in practice, because you have to cope with clock skew and asynchronous network. So you can not grant lease on absolute time, and you have to assume your package may have arbitrary time delays.

    Normally, we can make a conservative guess about network delay. To be absolutely safe, we have to be very conservative. So we may build a system that its lease is valid for 60 seconds, but the master have to assume the package has been delayed, say 30 seconds, and the master refresh its lease every 10 seconds. This looks good if the lease duration is long enough, but it won’t work if the lease expired quickly. The benefit of shorter lease is higher availability in the system, because long-lived lease will prevent system from working for longer time if the master crashed.

    I didn’t have a very good solution to this until I read a paper. The paper proposed a novel way to perform reads with high throughput and low latency in Paxos system without sacrificing consistency. It is especially useful in wide-area scenarios. Apart from the main topic of the paper, it also has a new way to grant & refresh leases without depending on external clock synchronization.

    lease

    As above picture shown, it uses guard to bound the promise duration: if grantor does not receive promise_ACK during t_guard, lease would expire at T3 + t_guard + t_lease. If holder does not receive promise during t_guard, the lease won’t be activated at all. The receival of promise_ACK only shorten the lease duration. When renewing active leases, there is no need to send the guard anymore, the most recent promise_ACK plays the role of the guard.

    With this protocol, we can use very short lease in the system because we make no guess at all. In the evaluation section of the paper, authors set lease duration to 2 seconds, and let grantor renew the current lease after 500ms. In this case if the holder crashed or unavailable, the lease won’t prevent the system from working for more than 2 seconds.


  2. 近两个月总结

    June 30, 2013 by xudifsd

    最近挺忙,发现都有两个月没写博客了,当年花钱买个主机而不是建个免费博客就是为了逼自己每个月写一篇博客的,但是这两个月实在是太忙了。眼看这7月就要到了,GR也要推上断首台了。总要挤些东西出来,恩。

    之前没上过班时觉得就算上班时间也应该挺充裕,能有自己的时间做东西。但是事实是,每天早上起来后马上就去上班,下完班吃完饭就已经7点了。而且由于盯了一天电脑了,回到家实在是不想再看电脑,顶多看下kindle或纸质书。而且在coursera上报了ML的课,每天下班看点视频,周末把编程作业做了,这样一来其他空闲时间就不多了,真心佩服那些报几个coursera课的人。而且这个月又是毕业季,上半个月总要花些时间整毕业论文的东西(特别是格式。。)。

    这两个月在公司里基本上没怎么干活,都在学习(不过从明天开始美好的日子就要过去,要开始干活了)。学了clojure,看了Google很久前发的几篇论文,还看了spark的论文。虽然说是看了,不过很多都看得很浅显,没空闲时间,基本上没有在学校那种能坚持下来看一些东西,并且形成一篇好的博客或程序的,或许也是因为自己才工作,没有形成一种好的习惯吧。

    好吧,能坚持看到我废话到现在的人也不容易,给你们些可能对你们有用的东西吧,是这两个月看的分布式方面的一些总结。

    在这里的分布式,我指的是类似于Google数据中心的廉价PC服务器组成的集群,也就是cluster。

    关于为什么需要使用这样的cluster《The Datacenter as a Computer》里说得很清楚了,就是因为便宜。虽然廉价PC的错误率虽然很高,但是就算加上容错所需要多出来的PC,价格也会比硬件超好的服务器便宜。而由于硬件的错误,软件就必须在设计时考虑容错与灾难恢复,这两点也是在Google那三篇论文中强调的。Google那三篇论文加上一篇冷门论文就是、GFSBigTableMapReducechubby。他们对应的开源版本分别是HDFS、HBase、Hadoop和zookeeper。都是apache的项目,而且都用的是java,这也是为什么互联网企业会有这么多用java的。如果想真正学好分布式就需要从chubby也就是zookeeper入手,其他一些东西只是建立在它之上的,学起来对于真正的分布式似乎没太大作用,对使用开源版本倒是有些作用。所以要想自己做个分布式框架能复用的就只有chubby了,但是chubby又很底层,知道和学习的并不多。不过很多分布式的框架和一些底层都会依赖于它,比如mesos、spark(因为基于mesos)、storm等。

    再说说spark,spark的论文在,不过这篇论文介绍的主要却不是spark,而是spark的原理,论文最有意思的地方是它介绍的灾难恢复的技术,这也是分布式程序需要做最多优化和权衡的地方。另外据论文描述,使用它进行ML计算比用hadoop计算要快20倍。。当时看到这个比例就惊了,那就是说hadoop需要计算一天的东西spark一小时就能搞定诶(看完后就问我厂研究院的新员工他们拿什么计算,想推荐下这个,她竟然说具体不知道,她是拿单机算,于是我就只能呵呵呵了)。spark的缺点就是它的语言接口是scala根据评论发现spark的接口既有scala和也有python,不过豆瓣有克隆版dpark,接口是python,应该比较好用,还要问豆瓣厂工。

    所以如果是我,我会先拿chubby入手,并且看看一些使用zookeeper的程序是如何使用它的,一旦这个学会,再自己实现个什么小东西,分布式也就基本上差不多了,同时再推一个解释chubby挺好的博文