文章目錄

1. 对Paxos一点浅薄的认识
1. 1.1. 引言：Paxos到底用来做什么
  1. 1.1.1. 有主节点的系统中，主节点在做什么
    1. 1.1.1.1. HDFS/GFS
    2. 1.1.1.2. Storm
  2. 1.1.2. 如果没有中心会存在什么问题？
2. 1.2. Paxos登场
  1. 1.2.1. 拍脑袋的集中尝试

对Paxos一点浅薄的认识

Paxos作为大神的一篇经典之作，已经有太多的人尝试对其进行理解和解释。但很遗憾，由于本人理解能力有限，至今难以勾勒出对其一个清晰的轮廓。

因此尝试通过对本文的撰写理清一些思路。

引言：Paxos到底用来做什么

在讨论这个问题之前，我们不妨先想想：

1	为什么一个分布式系统里需要有主节点？

有主节点的系统中，主节点在做什么

那么我们不妨看看一些具有主节点的系统的工作方式吧。
（由于本人理解所限，很多信息不一定完全或者正确，欢迎补充，讨论）

HDFS/GFS

HDFS中有namenode负责中央控制，datanode负责数据存储，其他角色我们暂不考虑。NameNode提供的服务包括：

[读]提供File->Block映射的查询
[写]写入新文件时提供新的File->Blok的映射

简略而言，就是维护一张统一的映射表格，以确保清楚知道所谓文件在所有机器上的位置。而具体读写操作由DataNode完成。

Storm

Storm中主节点被称为Nimbus，其他节点被称为superviosr。Nimbus主要负责作业的

提交
状态监控
杀死
Reschedule

如果没有中心会存在什么问题？

我们尝试在这些系统中删除主节点，看看没有主节点的情况下，仅依靠节点间的协商，会出现怎样的问题。

HDFS 无主情况的讨论

一方面需要每个机器存储大映射表，我们假设每个机器都有足够的空间存下。或者我们找个第三方共享存储（HDFS依赖其他共享存储-.-! 循环依赖的感觉）。

更重要的是：有新的写请求到达时，没有主节点的HDFS集群需要商量一个统一的全局的位置把这个文件写下来。（比如文件A写在哪个机器哪个位置，文件B在哪个机器哪个位置）

这些节点需要有一个合理的算法保证大家“看到”，并且都“认为”File1写在了XXX，File2写在了XXX。但真的仅仅是这样么？怎么看到呢？

我们可以在每个机器上跑一套共同的算法，我们称之为全局空间分配算法，该算法保证每来一个数据，我给你分配一个空间。这下好了，File1来了，每个机器按照该算法一算，应该在XXXX位置，大家结果都一样，都”认为“这个文件在这里。File2也来了，同上。

这里面有啥问题？

File1，File2一起来呢？有的机器比如N1可能看到的顺序是File1先到，有的机器比如N2可能是看到File2先到。这时候N1机器上算法的输入是File1，File2。N2机器上执行的算法是File2，File1。肯定空间分配不一致了。

当然我们可以简单地把File1直接写在请求机N1上，File2写在N2上，这样不存在任何冲突（使用一定程度上的自治）。但终究会存在数据倾斜（即：部分机器上数据太多，部分机器上太少）需要一个均衡算法来协调。

所以在这里无论是：

文件来的时候就分配一个全局的位置
还是，文件倾斜了再均衡

在没有主节点的情况下，唯一需要的就是：

1	所有节点商量好，所有节点都看到

这话太通俗了是吧，我们先继续往下看。

Storm 无主情况的讨论

根据Storm中心的那四个工作里，作业的状态，杀死相对好办，我们可以找共享存储解决这个问题。其他节点轮训检查共享存储，你说杀我就杀，你说啥状态就是啥状态。

但是，想想提交和schedule咋办呢？无论提交还是reschedule，可认为每个任务（Topology）里有多个子任务（worker）。而且Storm部署在N1~Nk号机器上。如果没有中心

哪个机器上运行哪个worker呢？

不是没有办法，我们可以在每个机器上有一套相同的算法，来一个topology，每个机器算法相同，输入相同，结果就相同。大家都知道自己该干嘛拉！！

但这样真的可以么？

如果，同时有两个topology在不同的机器上被提交了呢？

比如，N1上有人提交了Toplogy1，N2上有人提交了Topology2。二者分别广播到其他机器，”来来来，跑作业，运行你的作业分配算法来跑的Topology1/Topology2“。

是不是和刚才没有主HDFS的类似？

所以在N3看来可能是N1先说，N2后说的。可能在N4上网络堵了那么一个瞬间，他先收到了N2，再收到了N1。

所以N3和N4上输入数据的顺序不同，得到的任务分配算法也不一样，肯定是跑不对了。

是不是感觉和之前的问题一样？

1	在没有主节点的环境中，如果请求之间时间间隔很大，或者都是读请求，或者全局一致的简单写请求，感觉上不会出现任何问题。

但一旦不是这些情况，就需要一个算法，或者一个主节点，他们都需要做同一件事情：

在HDFS的讨论里，我们称之为“大家都商量好，都看到”，更加形式化一些：

1	所有操作必须得到一个全局统一的编号。

总结

想想是么？

主节点做的事情：HDFS里空间映射的写入，Storm里作业的调度。

如果没有主节点，那么每个操作需要有一个全局认可的编号，那么每个机器“看到”的就一定一样。算法抛出来的结果也一定一样。
如果有了主节点，主节点其实是把自己看到的顺序认为是官方顺序，并把该顺序作为输入运行调度算法，把结果输出到所有其他节点。

1
2
3

所以，无论无主节点的环境共同商量也好，还是存在一个主节点也好，他们解决的完全是一样的问题:

把写操作编号，并让所有其他节点认可该编号。

无怪乎人家Google的人说，所有分布式算法，都是Paxos的变种，主从模式也不例外。

Paxos登场

等灯等灯！Lamport大神出场。再看看人家的话：

1
2
3

在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致

看了之前的两个例子，是不是一种茅塞顿开的感觉？前半句是基本假设，后半句就是Paxos要做什么

上节中我们讨论了半天无主的情况，我们希望无主的时候能做到的就是

1	把写操作编号，并让所有其他节点认可该编号。

这就是Paxos要做的啊！

拍脑袋的集中尝试

我们先抛开Paxos复杂的算法和听不懂的论证。

我看到Paxos第一想到的就是为什么要那么费劲，有没有别的办法？那么，我们来拍脑袋试试，来吧，土鳖博士最擅长这个。

先置调节：N节点，无主
需求：对每个操作编号，全局认可

首先，操作之间时间间隔很大的话显然不存在问题：

请求之间时间间隔很大时： 

- 请求C1来到N1，N1通知所有点，无异议后写入编号K=k1，广播告知大家。

- 然后再来一个请求C2，到达N2，N2已经收到(C1，k1),并且认可(C1,k1),所以广播C2，给其编号k1+1，所有人认可，发送确认更新（C2，K1+1）。结束。

这似乎都算不上是一个算法。但这里有很多词都值得推敲

首先，每次更新一个请求的值都是一个二段提交的过程。因为这里面假想了可能有别的请求。
我们细看C2的过程，N2有个