一致性问题-PAXOS算法

[raymond]

PAXOS 声称解决一致性问题，我也看了几篇文章，大概明白了该算法的一些步骤，但是关于具体的细节心里却没有一点底。
哪位能具体说说

paxos的一些资料
http://blog.chinaunix.net/u3/94300/showart_1962723.html

场景假定（不知道是否合理）
3台客户端，他们的command如下：
1. change file 'a' to be 'b'
2. change file 'a' to be 'c'
3. change file 'c' to be 'e'

5 台服务器,以防止服务器宕机

那么使用paxos算法，这五台服务器是如何执行上面的一系列请求的，从而最终达到一致？

我最不明白的几个问题：
1. 算法中有number and value, 假设有一个service是专门提供unique的序列号的，那么是服务器收到客户端请求的时候申
请序列号，还是客户端自己在发送请求的时候申请这个号码？ value是不是就是客户端的命令？

2. 一致 是否意味 正确？ 假设，client 1的请求发到了server1,client 2的请求发送到了server 3,那么文件
文件’a‘最后的名字可能不是’c‘，而是‘b’？也就是一致性得到了维护，但是却不正确了（按照时间顺序，a的名字应该是c），这个问题是否应该依赖
于具体实现的语义？

3. paxos made simple上面举了个例子，说命令序列1-135会得到执行，我就很纳闷，为什么不是收到请求然后取得一致就执行呢？难
道服务器定时执行请求？那岂不是每个请求都会过一段时间才能得到应答？

谢谢高手解释一下。

[Kouga]

该算法很有趣，正在拜读，理清思路后继续探讨(大约时间，1天后，呵呵。

2009/6/12 raymond <shiq...@gmail.com>

--
签名是什么东西？？

[Kouga]

嗯，其实3台客户机的指令，我们将其标记为 1 2 3 ，各个指令之间没有必然的先后关系(偶认为是并发环境下)(所以不要看表面的序号)，那么可能生成的指令序列是：

1. 1 -> 2 -> 3
2. 1 -> 3 -> 2
3. 2 -> 1 -> 3
4. 2 -> 3 -> 1
5. 3 -> 1 -> 2
6. 3 -> 2 -> 1

而PAXOS保证的算法则是，所有5台服务器均按照上述任一一条顺序执行该指令集，而不能出现偏差，比如 server1 按照 1 序列执行而 server3 按照 5序列执行所造成的不一致->它无法保证的是按照设想的顺位执行这3条指令。(几乎所有的并发环境都这样，单次原子事务与同级事务无法严格按照顺位执行)

所以你的三个疑问：

1.序列号是服务器间通信时产生的(最可能的情况，一个服务器有自己的一个unique的产生器)。

2.如前所述，的确是保证了一致性而不是按照顺序来(但是，如果指令间间隔时间较大，超过了一次选举结束的时间，那么就会按照顺位执行)

3.如前所述，指令其实是取得一致性后就 执行了的，而该算法保证的是所有服务器的执行序列一致。

--
签名是什么东西？？

[raymond]

On 6月17日, 上午10时07分, Kouga <ncwh...@gmail.com> wrote:
> 嗯，其实3台客户机的指令，我们将其标记为 1 2 3
> ，各个指令之间没有必然的先后关系(偶认为是并发环境下)(所以不要看表面的序号)，那么可能生成的指令序列是：
>

> 1. 1 -> 2 -> 3
> 2. 1 -> 3 -> 2
> 3. 2 -> 1 -> 3
> 4. 2 -> 3 -> 1
> 5. 3 -> 1 -> 2
> 6. 3 -> 2 -> 1

>
> 而PAXOS保证的算法则是，所有5台服务器均按照上述任一一条顺序执行该指令集，而不能出现偏差，比如 server1 按照 1 序列执行而 server3

> 按照 5序列执行所造成的不一致->它*无法保证*

> 的是按照设想的顺位执行这3条指令。(几乎所有的并发环境都这样，单次原子事务与同级事务无法严格按照顺位执行)
>
> 所以你的三个疑问：
>
> 1.序列号是服务器间通信时产生的(最可能的情况，一个服务器有自己的一个unique的产生器)。

那么就可以理解成序列号是在服务器接收到请求后产生的，但是"个服务器有自己的一个unique的产生器"这句话好像不对，如果每个服务器都有自己的
unique 产生器，那么产生的unique数字就没有可比性了，所以，我想应该是服务器集群共享一个产生器。

[Kouga]

呵呵，注意算法里面，所有提案发起者都有当前最大提案代号——所以，下一个提案完全可以依据此编号再产生，这个并没有矛盾的地方。

2009/6/18 raymond <shiq...@gmail.com>

> 1.序列号是服务器间通信时产生的(最可能的情况，一个服务器有自己的一个unique的产生器)。

那么就可以理解成序列号是在服务器接收到请求后产生的，但是"个服务器有自己的一个unique的产生器"这句话好像不对，如果每个服务器都有自己的
unique 产生器，那么产生的unique数字就没有可比性了，所以，我想应该是服务器集群共享一个产生器。

--
签名是什么东西？？

[guonix]

一致性hash 之前也用过 ，是自己写的 不是很好，就不多说了 ，最近在用的 是一个叫ketama的算法。
这个算法比较好，实现起来也比较简单，对资源的消耗也还不错。

http://www.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients
页面中有详细的介绍，他提供的源代码中，有一些地方还需要根据个人的需求进行更改。
代码还是比较简洁的。大家也可以参考一下。
关于这个算法，我的测试结果是： 当设平均每个服务器占有 200个点时，对于资源的分配基本符合权重比例。当进行删除或者添加操作时，
也是基本根据服务器的权重来重新分配资源。算法中一点小缺陷，是当进行添加或者删除操作时，小部分资源会在现有服务器间跳转，可以自己动手更改算法。

缺点是：实例代码中hash函数使用的是md5， hash如果大家对于效率要求比较高的话，可以参考使用fnv32或者crc32算法。fnv32算
法测试后发现
确实在小数据量（我们的资源是一个20字节长度的任务id号）的情况下比md5快很多。

至于paxos 我还在看看，看完再发表评论

On 6月12日, 下午3时51分, raymond <shiqu...@gmail.com> wrote:
> PAXOS 声称解决一致性问题，我也看了几篇文章，大概明白了该算法的一些步骤，但是关于具体的细节心里却没有一点底。
> 哪位能具体说说
>

> paxos的一些资料http://blog.chinaunix.net/u3/94300/showart_1962723.html