文章目錄
  1. 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. 如果没有中心会存在什么问题?
        1. 1.1.2.1. HDFS 无主情况的讨论
        2. 1.1.2.2. Storm 无主情况的讨论
        3. 1.1.2.3. 总结
    2. 1.2. Paxos登场
      1. 1.2.1. 拍脑袋的集中尝试

对Paxos一点浅薄的认识

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

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

引言:Paxos到底用来做什么

在讨论这个问题之前,我们不妨先想想:

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

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

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

HDFS/GFS

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

  1. [读]提供File->Block映射的查询
  2. [写]写入新文件时提供新的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节点,无主
  • 需求:对每个操作编号,全局认可

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

1
2
3
4
5
请求之间时间间隔很大时: 

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

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

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

  • 首先,每次更新一个请求的值都是一个二段提交的过程。因为这里面假想了可能有别的请求。
  • 我们细看C2的过程,N2有个
文章目錄
  1. 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. 如果没有中心会存在什么问题?
        1. 1.1.2.1. HDFS 无主情况的讨论
        2. 1.1.2.2. Storm 无主情况的讨论
        3. 1.1.2.3. 总结
    2. 1.2. Paxos登场
      1. 1.2.1. 拍脑袋的集中尝试