博文

目前显示的是 二月, 2015的博文

关于Replicated State Machines的一些笔记

当同一个数据存在多个副本的时候,怎么管理它们就成了问题。在Map-Reduce的场景下,数据都是一次写入永不更改,那么问题就变得非常简单,让每一份数据都有多个拷贝,然后处理好分发和读取的细节问题就行了。这些细节问题包括:所有的拷贝不能处于同样的环境下。这样单一环境的故障不至于引起所有拷贝都损坏。具体来说,如果你想容忍整个IDC的停机故障,那么就得让数据有跨IDC的副本。 读取的算法能容忍某些副本是坏的,它能检测数据的完整性,当遇到错误时,从其它副本位置重试 有一个监控程序能有效的检测数据完整性并为损坏的数据创建新的副本在上述场景下,因为数据都是只读的,所以没有一致性问题。这也是为什么Map-Reduce能这么流行这么备受推崇的原因之一。Replicated State Machines用于支持数据可被修改。比如分布式系统中的元数据信息。具体例如,一个分布式系统中,一个目录下有哪些文件。虽然文件本身可以做到一次写入永不修改,但是目录不可能。目录的内容总是动态变化的。Replicated State Machines(后面简称RSM)的最早提出是在图灵奖得主Leslie Lamport的著名论文"Time, clocks, and the ordering of events in a distributed system(1978)"论文中,比较系统性的阐述是在Fred Schneider的论文"Implementing fault-tolerant services using the state machine approach(1990)"中。Fred Schneider现在是Cornell大学计算机系主任。它的基本思想是一个分布式的RSM系统由很多个replica组成,每个replica是一个状态机,它的状态保存在一组状态变量中。状态机的状态通过并且只能通过外部命令(commands)来改变。比如你可以把MySQL服务器想像成一个状态机。它每接收到一条带修改功能的SQL语句(比如update/insert)就会改变它的状态。一组配置好replication的MySQL servers就是典型的RSM。RSM能够工作基于这样的假设:如果一些状态机具有相同的初始状态,并且他们接收到的命令也相同,处理这些命令的顺序也相同…

使用逻辑时钟重述paxos协议

Paxos是一个分布式选举协议,被广泛用在很多分布式系统中,比如Google的Chubby,MegaStore,Linux的Ceph。它的目的是为了让一群机器通过选举的方式达成一个一致性的决议。比如现在有5台MySQL服务器,它们要选举一个Master出来(无人工干预),所有的数据修改请求都发给这个Master,其它的做为Slave,以备在Master死掉后自动顶上去。Paxos协议将参与通信的主体分为两个角色:proposer和acceptor。分别各有多个。分布式选举协议的基本框架是:一个proposer提出一个提案,然后把这个提案发给所有的acceptor。acceptor可以选择接受或者拒绝这个提案。一个提案如果被过半数的acceptor接受,那么此提案被选中(chosen)。一个系统中可以同时有多个proposer提出多个提案,但是最终只能有一个被选中。并且应该至少有一个被选中。选举过程中机器可能crash掉,或者网络中断,机器一会儿死了一会儿活了。但是无论如何,只要死掉的机器数不过半,选举就应正常进行下去。Paxos协议是一个被公认的晦涩难懂的协议。但是今天突然发现,如果按照逻辑时钟的角度去阐述它,它就变得简单清晰了许多。下面介绍如何利用带逻辑时钟的RPC协议来实现Paxos。基于逻辑时钟的RPC协议为了让这套系统能正确运行,我们需要一个精确的时钟。由于操作系统的物理时钟经常是有偏差的,所以我们决定采用一个逻辑时钟。时钟的目的是给系统中发生的每一个事件编排一个序号。逻辑时钟可以利用全局计数器来实现。我们可以找一台机器提供一个全局的计数服务。它只支持一个方法:incrementAndGet()。这个方法的作用是将计数器的值加一,并且返回增加后的值。我们将这个计数器称为globalClock。globalClock的初始值为0。然后,系统中的每个其它机器,都有一个自己的localClock,它的初始值来自globalClock。假设机器和机器之间通过request-response这样的模式通讯。每条网络消息的类型要么是reqeust,要么是response。response又分为两种:OK和Rejected。我们规定无论什么类型的网络消息,都必须带有一个时间戳,时间戳取自这台机器的localClock。我们规定消息的接收方必须执行以下行为:if(mess…

挖了一些关于nodejs的八卦

TimelineNode.js诞生于2009年,它的初始作者是Ryan Dahl。他出生于美国加州San Diego,2009年时居住在德国,是一个自由职业者。在那时他创作了nodejs。在完成nodejs的初始开发并公之于众后,硅谷一家创业公司Joyent找到他并雇佣了他。Joyent给他发工资让他依然以100%的时间做自己原本喜欢做的事情(开发nodejs),一场愉快的交易。当时的CEO是David Young,CTO是Jason Hoffman。Joyent这个公司很难说清楚它到底是做什么的,因为它经历了数次转型和合并。
2011年,Isaac Z. Schlueter开发了nodejs的包管理工具npm,并于2011年11月将之合并到nodejs中。Isaac出生于美国康涅狄格州,曾就读于南康涅狄格州立大学,肄业。据他说他先是在Yahoo工作(2006/01 - 2010/01),然后辞职做了npm,然后受雇于Kakai了几个月(2010/04 - 2010/08),然后加入了Joyent(2010/09 - 2013/12)。据他声称npm恰好是他在换工作的间隙做的,于是版权属于他个人,不属于任何公司。但事实绝非如此,不细说了。
在2012年1月31日,Ryan Dahl公布他将nodejs的领导位置让位于Isaac Schlueter,然后Ryan Dahl就去纽约了,从此从网络上消失了。
2012年5月,Joyent当时的CEO David Young离开Joyent。11月,Henry Wasik接任CEO。
2013年9月,Jason Hoffman从CTO的位置上离职,去了Ericsson。Bryan Cantrill接任CTO。Bryan Cantrill当时刚30岁,加入Joyent 3年半。
2014年1月,负责管理nodejs的Isaac Schlueter离开了Joyent,创办了npm,Inc,并担任CEO。nodejs的管理工作由Timothy J Fontaine接任。而Fontaine刚加入Joyent不到1年。他于2013年2月加入Joyent,4月加入nodejs的核心贡献团队。
2014年6月,Joyent从思科请来了Scott Hammond作为新CEO,代替Henry Wasik。同时,TJ Fontaine 也宣…

Intel CPU的BUG导致reboot起不来

这个BUG是我去年11月撞见的,早该写出来了。因为这个BUG造成的灾难后果远远超出我的想像。当时的现象是某些机器重启后起不来,/var/log/message中有这样的信息:Nov 15 03:46:09 kernel: INFO: task sh:7684 blocked for more than 120 seconds.
Nov 15 03:46:09 kernel: "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
Nov 15 03:46:11 kernel: Call Trace:
Nov 15 03:46:11 kernel: [] ? ext4_file_open+0x0/0x130 [ext4]
Nov 15 03:46:11 kernel: [] schedule_timeout+0x215/0x2e0
Nov 15 03:46:12 kernel: [] ? nameidata_to_filp+0x54/0x70
Nov 15 03:46:12 kernel: [] ? cpumask_next_and+0x29/0x50
Nov 15 03:46:12 kernel: [] wait_for_common+0x123/0x180
Nov 15 03:46:12 kernel: [] ? default_wake_function+0x0/0x20
Nov 15 03:46:13 kernel: [] wait_for_completion+0x1d/0x20
Nov 15 03:46:13 kernel: [] sched_exec+0xdc/0xe0
Nov 15 03:46:13 kernel: [] do_execve+0xe0/0x2c0
Nov 15 03:46:13 kernel: [] sys_execve+0x4a/0x80
Nov 15 03:46:13 kernel: [] stub_execve+0x6a/0xc0 上网一查,发现这是一个已知的BUG, 请见 http://www.intel.com/content/dam/www/public/us/en/documents/specificat…

关于内嵌v8的一些性能测试

我写了个插件把google的javascript引擎v8嵌入到ATS中去,目的是希望以脚本的方式修改http请求。然后我刚刚在网上看见nginx的作者对v8的声讨:http://sysoev.ru/prog/v8.html 说为什么v8不适合嵌入到http server中(比如嵌入到nginx),其中一个理由是,创建一个V8 context需要2ms,那么一个单线程的http server每秒就最多只能处理500个请求,这样的结果简直不可接受。nginx的这篇文章是2010年写的,时过境迁,我刚做了下实验,发现并不属实。创建Context并不慢首先,v8中创建第一个context确实很慢。因为它需要初始化很多global的变量和函数。你想想看启动一个java的vm要多久,相比而下2ms算什么。请看下面这段代码:Isolate::Scope isolate_scope(isolate); HandleScope handle_scope(isolate); MESURE_TIME_BEGIN(create_context1) Local<Context> context = Context::New(isolate); Context::Scope context_scope(context); MESURE_TIME_END(create_context1) MESURE_TIME_BEGIN(create_context2) v8::Local<v8::Context> context2 = v8::Local<v8::Context>::New(isolate, context); Context::Scope context_scope2(context2); MESURE_TIME_END(create_context2) 第二个context是在第一个context的基础上创建的。在我的笔记本上测试:create_context1 time=28440968 nano secondscreate_context2 time=414 nano seconds也就是说创建一个新的context的时间小于1微秒。对于我的场景来说,我是在服务器启动、加载js代码的时候创建第一个co…

故障排查经历:负载高CPU低

今天我们一台服务器出了问题,负载异常高。正常情况下它的负载应该是0.5 -1.5左右,但是今天突然变成了5-6。我上去看,cpu很闲,IO也很少啊。没看出任何异常。为啥呢。后来用ps发现有几个进程始终处于uninterruptible sleep状态$ ps aux|grep power
root 23840 0.0 0.0 0 0 ? D Feb06 0:01 [power_saving/0]
root 23841 0.0 0.0 0 0 ? D Feb06 0:01 [power_saving/1]
root 23844 0.0 0.0 0 0 ? D Feb06 0:00 [power_saving/2]
root 23845 0.0 0.0 0 0 ? D Feb06 0:00 [power_saving/3]它们虽然不占CPU,但是会被记录到load中。恰好有4个进程,恰好比平时的负载大了4。但是它们是从哪来的呢? 我向运维工程师申请了查看/var/log/message的权限,发现Feb 6 01:48:03 xxx kernel: CPU5: Package power limit normal
Feb 6 01:48:03 xxx kernel: CPU17: Package power limit normal
Feb 6 01:48:03 xxx kernel: CPU23: Package power limit normal
Feb 6 01:50:25 xxx kernel: INFO: task kacpi_notify:179 blocked for more than 120 seconds.
Feb 6 01:50:25 xxx kernel: "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
Feb 6 01:50:25 xxx kernel: kacpi_notify D 0000000000000000 0 179 2 0x00000000
Feb 6 01:50:25 xxx kernel: ffff88032aa4db30 0000000000000046 0000000000000001 00000000000000…

排错经历:全局变量被多次析构

我们team有一套C++写的server程序,最近发现它在每次退出的时候会崩溃,core dump文件的栈如下:(gdb) bt
#0 0x0000003ea4e32925 in raise () from /lib64/libc.so.6
#1 0x0000003ea4e34105 in abort () from /lib64/libc.so.6
#2 0x0000003ea4e70837 in __libc_message () from /lib64/libc.so.6
#3 0x0000003ea4e76166 in malloc_printerr () from /lib64/libc.so.6
#4 0x0000003ea729d4c9 in std::basic_string\, std::allocator\ >::~basic_string() ()
from /usr/lib64/libstdc++.so.6
#5 0x0000003ea4e35e22 in exit () from /lib64/libc.so.6
#6 0x0000003ea4e1ed24 in __libc_start_main () from /lib64/libc.so.6
#7 0x0000000000400629 in _start ()下面介绍一下我是如何找到出问题的代码。请注意,因为编译器优化的缘故,这个栈是不完整的。安装完调试符号后,栈应该是这样:(gdb) bt
#0 0x0000003ea4e32925 in raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1 0x0000003ea4e34105 in abort () at abort.c:92
#2 0x0000003ea4e70837 in __libc_message (do_abort=2, fmt=0x3ea4f58aa0 "*** glibc detected *** %s: %s: 0x%s ***\n")
at ../sysdeps/unix/sysv/linux/libc_fatal.c:198
#3 0x0000003ea4e76166 in …