分布式计算理论基础(一)

CAP定理

  • 一致性 (Consistency): 无论是做删除还是更新操作,集群系统都能为客户端提供最即时的数据
  • 可用性 (Availability): 即使节点出现异常,集群系统也能够不间断的提供获取服务,保证客户端能够在有效的时间内获得数据
  • 分区容错性 (Partition tolerance): 即使出现网络故障或信息丢失,系统也能够提供可靠的容错服务

CAP

CAP

CAP原理认为,一致性、可用性和分区容错性这三点是不能够同时满足的,这三点只能做到妥协其中一点、尽力满足其它两点:

  • AP: 弱化一致性,适用于对数据一致性不敏感的应用,在客户端操作数据完毕后,可能需要过一段时候后才能获取到最新的数据。例如聊天软件,个人资料的更新不能保证即时被其它用户获取
  • CP: 弱化可用性,适用于对数据一致性敏感的应用,当系统出现故障时会直接拒绝服务。例如银行取款机
  • CA: 弱化分区容忍性,通常情况下基本不采用这种模式,因为分区容错性基本上就是分布式系统的基础

CAP原理本质上讲解的就是一个典型的三角约束,鱼与熊掌不可得兼,这三者只能舍弃一而得其二。通常的情况下,设计一个分布式系统,P作为容错性就构建的根本是不容舍弃的,这样的话一般的设计都是在A和C之间做妥协,设计的策略没有好坏之分,多数情况下都是根据业务场景来做设计的

关于这个理论,可用使用一个极端的场景进行证明,假设分布式系统中的一个节点在相应客户端请求时出现了异常,无法完成该操作,一般来说系统没有完美的方案,只有两种选择:

  1. 牺牲一致性 (C),保证可用性 (A),返回旧的数据给客户端
  2. 牺牲可用性 (A),保证一致性 (C),阻塞等待,直到系统恢复并操作完成,才将最新的数据返回给客户端

拜占庭将军问题 (Byzantine Generals Problem)

谈到分布式系统的构建,就不得不确保容错性,在这方面最早的相关术语就是拜占庭将军问题,是一个典型的分布式对等网络通信容错问题。理解这个问题其实很简单,以一个示例来阐述:

18个拜占庭将军被分派到国家边境的不同地点去打仗,他们在各自负责的范围内灵活应变敌情,分别可以发出两种信号:进攻或者撤退,这个信号是由各个将军制定并由信使们进行传递,传送给其它将军作为参考。对于整个拜占庭帝国,最佳的作战方案是各个地方的部队需要同进退,不能各自为战

那么不同的将军判断不同,又要制定统一的作战行动,最直观的解决方案就是才用投票法,少数服从多数。然而这种方法十分容易受到帝国间谍、本国叛徒的影响,容易导致行动结果错误、行动不一致等问题。这个问题也就是拜占庭将军问题,解决它的方案其实和分布式系统中的容错性方案思路一致

同样的,在分布式计算系统中,通常会遇到因为节点异常导致的数据丢失问题,常见的数据容错解决方案有:

  1. 进行数据冗余。著名的GFS就是采用了这种方案,一个大型文件的元数据被保存在专门的Master服务器上,记载着该文件的信息与存储情况。而它的文件内容被切分成多个Chunk,分布式存储在不同的Chunk Server中,同一份Chunk会被重复保存在不同的Chunk Server中,这样即使一个Chunk Server出现宕机等异常,客户端也可以通过Master的信息找到存有该Chunk的其它Server。这样就保证了数据的容错性
  2. 设置CheckPoint,检测到出错后恢复上一个CheckPoint的状态。热门的Spark系统正是采用了这种方案,在不同的执行点设置检查点机制,如果发现了不同,则会使用Lineage机制重新计算,回复之前内存中存储的数据

有状态与无状态

状态的定义:发起请求的客户端是否与服务端具备上下文关系。如果是有状态的请求,那么服务器可以直接使用之前请求的信息,如果是无状态的请求,服务器处理的请求信息需要从这个请求中获取或者重新进行加载

典型的无状态计算框架有MapReduce,不同的MapReduce任务涉及的数据都是需要从磁盘中获取或写出的,不能简单的通过内存直接进行共享、获取。有状态的计算框架有很多,例如Spark RDD, GraphLab, DAG框架等等,都是将无状态变为有状态,以达到提升整体作业计算效率的目的

计算并行化

机器学习算法虽然多种多样,但是归根结底,大多数的算法的训练都是通过降低目标函数的值,迭代计算直至结果收敛,得出的参数通常都是向量或者矩阵类型。

top Created with Sketch.