Paxos 算法

Posted on by
回复

一、写在之前

Byzantine 算法面对分布式系统中节点的可信问题，提出了可信节点达成一致性解决方法。Paxos 算法是为了解决分布式系统中节点失效而提出的一致性算法。就分布式存储系统而言，Paxos 算法的价值更大，因为节点是可信的且会因为故障或者扩容发生节点失效。

不仅只用在分布式系统，凡是多个过程需要达成某种一致性的都可以用到Paxos 算法。一致性方法可以通过共享内存（需要锁）或者消息传递实现，Paxos 算法采用的是后者。下面是Paxos 算法适用的几种情况：一台机器中多个进程/线程达成数据一致；分布式文件系统或者分布式数据库中多客户端并发读写数据；分布式存储中多个副本响应读写请求的一致性。

Lamport 最初Paxos 算法的论文The Part-Time Parliament 在理解起来比较有挑战性，个人认为部分原因是Lamport 通过故事的方式来表述、解释这个问题，所以在阅读文章的时候读者需要透过故事讲的本身看到作者想说明什么。比如文章中会有很多讲到Paxon 文明没有被发现和考证的，这些映射到实际系统中往往是简单、大家都心知肚明的基础，但如果读者苦于想知道这些内容是什么时，就上当了。下面章节安排如下：第二节对应原文的1.1-2.1。第三节对应原文2.2-3.2。

继续阅读 →

可视化函数调用

Posted on by
1

所需工具：

  1. GCC
  2. Graphviz
  3. 中间件pvtrace，下载
  4. addr2line 下载

过程：

  1. 编译／安装 pvtrace（make，make install 即可）
  2. 将 pvtrace 中instrument.c 拷贝到要进行编译的路径
  3. 按如下代码编译测试程序(注意第三行-finstrument-functions 是连起来的)：
 1: $ ls
 2: instrument.c    test.c
 3: $ $ gcc -g -finstrument-functions test.c instrument.c -o test
 4: $ ./test
 5: $ ls
 6: instrument.c     test.c
 7: test             trace.txt
 8: $ pvtrace test
 9: $ ls
 10: graph.dot        test           trace.txt
 11: instrument.c     test.c
 12: $ dot -Tjpg graph.dot -o graph.jpg
 13: $ ls
 14: graph.dot        instrument.c   test.c
 15: graph.jpg        test           trace.txt
 16: $

我的源码：

 1: #include <stdlib.h>
 2:
 3: void step1(){
 4: printf(“I am step1 !\n”);
 5: }
 6:
 7: void step(){
 8: printf(“I am last step !\n”);
 9: }
 10:
 11: void step2(){
 12: printf(“I am step2 !\n”);
 13: step();
 14: }
 15:
 16: int main(void){
 17: step1();
 18: step2();
 19: return 1;
 20: }
 21:

 

编译生成的图片：

PS：在makefile 中添加中间件编译参考[2]。

参考：

[1].http://www.ibm.com/developerworks/cn/linux/l-graphvis/

[2].http://blog.csdn.net/seasonpplp/article/details/7399053

[3].http://blog.csdn.net/fisher_jiang/article/details/6828427

拜占庭将军问题

Posted on by
回复

参考 The Byzantine Generals Problems 。

这个问题的最初描述是：n 个将军被分隔在不同的地方，忠诚的将军希望通过某种协议达成某个命令的一致（比如一起进攻或者一起后退）。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport 证明了在将军总数大于3m ，背叛者为m 或者更少时，忠诚的将军可以达成命令上的一致。

为了保证上面的需求，必须满足下面两个条件：

1. 每两个忠诚的将军必须收到相同的值 v(i)（v(i)是第i 个将军的命令）

2. 如果第i 个将军是忠诚的，那么他发送的命令和每个忠诚将军收到的v(i)相同

为了简化以上模型，我们使用一个将军发送命令给多个副官的形式来证明，发送命令的将军称为发令者，接收命令的将军为副官，那么上面的两个条件可以表述为：

IC1. 所有忠诚的副官遵守相同的命令

IC2. 如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守相同的命令

特别提示：发送命令的每次只有一个将军，将其命令发送给n-1 个副官。m 代表叛国者的个数，因为将军总数为n，所以副官总数为n-1 个。IC2 中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。

一、通过口头消息

通过口头消息传递达到一致，如果有m 个叛国将军，则将军们的总数必须为3m+1 个以上。下面是口头消息传递过程中默认的一些条件：

A1. 每个被发送的消息都能够被正确的投递

A2. 信息接收者知道是谁发送的消息

A3. 能够知道缺少的消息

A1 和A2 假设了两个将军之间通信没有干扰，既不会有背叛者阻碍消息的发送（截断）也不会有背叛者伪造消息的情况（伪造）。即是每个将军都可以无误地将自己的消息发送给其他每个将军。（下一节中可以不需要这个必要条件）

我们定义口头消息算法OM(m) 。对于所有的非负整数m ，每个发令者通过OM(M) 算法发送命令给n-1 个副官。下面将说明OM(m) 算法在最多有m 个背叛者且总将军数为3m+1 或者更多的情况下可以解决拜占庭将军问题。（考虑到网络应用实际环境，原文使用了收到值代替收到命令，本文不做修改）

算法定义一个函数：$majority(com_1,com_2,\dots,com_n)$ 等于多数派命令。

OM(0)算法

（1）发令者将他的命令发送给每个副官。

（2）每个副官采用他从发令者发来的命令，或者默认使用撤退命令，如果没有收到任何命令。

OM(m)算法

（1）发令者将他的命令发送给每个副官。

（2）对于每个i ，vi 是每个副官i 从发令者收到的命令，如果没有收到命令则为撤退命令。副官i 在OM(m-1) 中作为发令者将vi 发送给另外n-2 个副官。

（3）对于每个i，并且$j\neq i$，vj 是副官i 从第（2）步中的副官j 发送过来的命令（使用OM(m-1) 算法），如果没有收到第（2）步中的副官j 的命令则默认为撤退命令。最后副官i 使用majority(v_1,\dots,v_{n-1})得到命令。

继续阅读 →

为WordPress 博客添加分页功能

Posted on by
回复

参考：脱离插件，实现WordPress主题分页功能

一直觉得WordPress 默认的Older Entries 不太友善，想改成分页功能，google 的分页的插件，wp-pagenavi 还是比较流行，安装之后发现主页响应非常慢，过了十多分钟还是以没有分页的方式显示出来了，感觉可能是主题与插件的兼容性，更可能是之前修改了页面的布局，wp-pagenavi 插件与我修改的布局不太兼容，于是参考了网上的一些方法，自己添加了一些分页的功能。再次提醒广大站长：要么不要对源WP 或者主题进行修改，一旦修改了以后都要做好自己动手改代码的觉悟。

继续阅读 →

【翻译】对lamport 的一段采访

Posted on by
回复

源地址：http://research.microsoft.com/en-us/um/people/lamport/pubs/ds-interview.pdf

Dejan Milojicic: 你从事的许多具有想象力的问题都在实际应用中有成就，甚至在几十年之后仍有影响。你对研究方向的选择在时机上有什么特别么？

Leslie Lamport: 遇到一些问题是因为工程师们在构建系统时碰到了，需要算法来解决， fast mutual exclusion algorithm 和 disk Paxos 就是这类。还有一些，比如cache coherence，是我自己想出来的。我在选择这类问题的时候没有考虑到时机是否合适。

Dejan Milojicic: 你认为你的哪个贡献对现代计算机科学与产业具有最大的影响力？

Leslie Lamport: 我的引用量最多的文章是“Time, Clock, and Ordering of Events  in a Distributed System.”，我不知道这和你说的影响是不是一回事，因为我并不能从该文章直接指导出许多工作，但可能它影响了人们对思考分布式系统的方法。我认为我在工业界还没有太多影响，虽然我期望Paxos 和状态机方法将在分布式系统设计上有重要影响。这是在微软发现的（注：Lamport 加入了微软）。

继续阅读 →

SSD 并行的性能影响

Posted on by
回复

原文： Performance Impact and Interplay of SSD Parallelism through Advanced Commands, Allocation Strategy and Data Granularity

文章是胡杨博士在2011 ICS 上发表的,通过他的模拟软件SSDsim 对SSD 的并行和高级命令（advanced commands）的分析得出了一些SSD 设计实现上的建议.之前都苦于没有SSD 比较详细的综述,于是自己凑了和了一篇（之前写过的综述），而这篇文章则似乎更适合作SSD 的综述，讲的很清晰。

Idea

通过多层次的SSD 仿真器SSDsim 分析了SSD 内部影响性能的因素（并行）。

总结

  1. large pages 在许多情况下对SSD 有比较大的负面影响
    1. 越大的pages 更易导致数据的迁移
  2. 不同physical-page allocation 可应用于不同环境中，对任意工作负载都会有一个最优方案
    1. Static allocation 读性能在所有情况下最优
  3. 高级命令在一些情况下能够改进SSD 性能，但是用不当会适得其反
    1. 使用高级命令必须带有约束条件才能够提升性能
  4. SSD 四种并行：channel 层、chip 层、die 层和plane 层并行，它们优先级对性能有影响并和2、3中physical-page allocation 与高级命令相互作用、影响。
    1. 并行的优先顺序应该为：1、channel-level  2、chip-level  3、die-level  4、plane-level