月度归档：4月 2012

Web caching with consistent hashing 一致性哈希Web 缓存

Posted on by
回复

读这篇文章源自于一致性哈希的开山之作：Consistent hashing and random trees: Distributed caching protocol for relieving hot spots on World Wide Web。在STOC 上下了原文后觉得估计得花和The part-time parliament 差不多时间来读吧，以后有必要深入学习再看吧！一致性哈希Web 缓存是与开山之作同一作者David Karger 1999年所写 。

STOC 会议上有许多经典的算法，但很多有晦涩难看懂没有引起大家的注意，直到某个采用了该算法的应用得到大家的认可，该算法才得以为大家所接受。分布式一致性Paxos 算法也是这样。（下面左图是consistent hash 开山作引用情况，右边是The part-time parliament 每年引用量，可见在这些牛文在引用量巅峰期之前都有几年的沉寂期，来自CiteSeerX）

conshashing  paxos

言归正传：

problem

congested network and swmaped servers 集中式缓存存在问题

related work

cooperating cache 将缓存复制到不同的机器，存在数据复制和副本一致性问题

hashing 缓存通过哈希保存到不同机器上，存在扩展性以及churn 问题：当一个节点失效或新增一个节点会导致大量失效和缓存的迁移，比如 7×i+4 mod 24 到 7×i+4 mod 23

our work

浏览器上添加哈希函数，将URL 资源定向到动态变化的可用缓存，无副本且减少失效率

consistent hashing

假设有n 个缓存节点，根据其哈希结果使用二叉树进行组织

our system

组成：1.actual cache system  2.user’ browsers   3.domain name server

浏览器对URL 进行哈希得到虚拟地址，返回给DNS 服务器

DNS 服务器通过客户端的虚拟地址查到到对应的缓存节点物理地址IP

缓存节点从原始Web 服务器取数据并保存一份副本，可相应浏览器请求

Consistent hashing 的python 实现

Posted on by
1

部分代码参考之前的“写一个分布式存储系统有多简单？”，保持数据服务器端不变，修改客户端节点选择方式即可。

修改：1、添加HashRing 类，进行一致性哈希环的管理，保存在客户端client ，因此节点/数据服务器端可以不做任何修改（添加hello 测试）。2、客户端修改节点选择方式，使用consistent hashing。

接受一致性哈希的国内的也比较多了，可以参考这里

继续阅读 →

常见key-value 存储系统

Posted on by
回复

Berkeley DB

1991 年，软件库可构建嵌入式key-value 数据库，C 语言，被MySQL使用。

memcached

2003 年，分布式全内存数据库，C 语言，使用网站：YouTube，Reddit，Facebook，和Twitter

Bigtable、Hbase

2004 年、2007年，基于DFS 的NoSQL 数据库，Java 语言，2010 年Facebook 开始使用Hbase

Hypertable

2009 年，灵感来自Google Bigtable，C++，百度

Cassandra

2008 年，key-value 数据库，Java 语言，Facebook 开发

couchDB

2005 年，使用JSON 保存数据的NoSQL 数据库，Erlang 语言，IBM 开发

Dynamo

2007 年SOSP 论文，结构key-value 存储，Java 语言（未开源），Amazon S3 使用

MongoDB

2009年，面向文档的数据库系统，C++ 语言，使用网站：SourceForge，The New York Times

Redis

2009年，类似但优于memcached、基于内存、优化耐久性key-value 数据库，C 语言，VMware 赞助

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})得到命令。

继续阅读 →