分类目录归档：所有Java文章

淘宝从几百到千万级并发的十四次架构演进之路！

发表于2019年8月26日由javahao123

作者：huashiou

1、概述

本文以淘宝作为例子，介绍从一百个并发到千万级并发情况下服务端的架构的演进过程，同时列举出每个演进阶段会遇到的相关技术，让大家对架构的演进有一个整体的认知，文章最后汇总了一些架构设计的原则。

2、基本概念

在介绍架构之前，为了避免部分读者对架构设计中的一些概念不了解，下面对几个最基础的概念进行介绍：

分布式系统中的多个模块在不同服务器上部署，即可称为分布式系统，如Tomcat和数据库分别部署在不同的服务器上，或两个相同功能的Tomcat分别部署在不同服务器上

高可用系统中部分节点失效时，其他节点能够接替它继续提供服务，则可认为系统具有高可用性

集群一个特定领域的软件部署在多台服务器上并作为一个整体提供一类服务，这个整体称为集群。如Zookeeper中的Master和Slave分别部署在多台服务器上，共同组成一个整体提供集中配置服务。在常见的集群中，客户端往往能够连接任意一个节点获得服务，并且当集群中一个节点掉线时，其他节点往往能够自动的接替它继续提供服务，这时候说明集群具有高可用性

负载均衡请求发送到系统时，通过某些方式把请求均匀分发到多个节点上，使系统中每个节点能够均匀的处理请求负载，则可认为系统是负载均衡的

正向代理和反向代理系统内部要访问外部网络时，统一通过一个代理服务器把请求转发出去，在外部网络看来就是代理服务器发起的访问，此时代理服务器实现的是正向代理；当外部请求进入系统时，代理服务器把该请求转发到系统中的某台服务器上，对外部请求来说，与之交互的只有代理服务器，此时代理服务器实现的是反向代理。简单来说，正向代理是代理服务器代替系统内部来访问外部网络的过程，反向代理是外部请求访问系统时通过代理服务器转发到内部服务器的过程。

3、架构演进

3.1、单机架构

以淘宝作为例子。在网站最初时，应用数量与用户数都较少，可以把Tomcat和数据库部署在同一台服务器上。浏览器往www.taobao.com发起请求时，首先经过DNS服务器（域名系统）把域名转换为实际IP地址10.102.4.1，浏览器转而访问该IP对应的Tomcat。

随着用户数的增长，Tomcat和数据库之间竞争资源，单机性能不足以支撑业务

3.2、第一次演进：Tomcat与数据库分开部署

Tomcat和数据库分别独占服务器资源，显著提高两者各自性能。

随着用户数的增长，并发读写数据库成为瓶颈

3.3、第二次演进：引入本地缓存和分布式缓存

在Tomcat同服务器上或同JVM中增加本地缓存，并在外部增加分布式缓存，缓存热门商品信息或热门商品的html页面等。通过缓存能把绝大多数请求在读写数据库前拦截掉，大大降低数据库压力。其中涉及的技术包括：使用memcached作为本地缓存，使用Redis作为分布式缓存，还会涉及缓存一致性、缓存穿透/击穿、缓存雪崩、热点数据集中失效等问题。

缓存抗住了大部分的访问请求，随着用户数的增长，并发压力主要落在单机的Tomcat上，响应逐渐变慢

3.4、第三次演进：引入反向代理实现负载均衡

在多台服务器上分别部署Tomcat，使用反向代理软件（Nginx）把请求均匀分发到每个Tomcat中。此处假设Tomcat最多支持100个并发，Nginx最多支持50000个并发，那么理论上Nginx把请求分发到500个Tomcat上，就能抗住50000个并发。其中涉及的技术包括：Nginx、HAProxy，两者都是工作在网络第七层的反向代理软件，主要支持http协议，还会涉及session共享、文件上传下载的问题。

反向代理使应用服务器可支持的并发量大大增加，但并发量的增长也意味着更多请求穿透到数据库，单机的数据库最终成为瓶颈

3.5、第四次演进：数据库读写分离

把数据库划分为读库和写库，读库可以有多个，通过同步机制把写库的数据同步到读库，对于需要查询最新写入数据场景，可通过在缓存中多写一份，通过缓存获得最新数据。其中涉及的技术包括：Mycat，它是数据库中间件，可通过它来组织数据库的分离读写和分库分表，客户端通过它来访问下层数据库，还会涉及数据同步，数据一致性的问题。

业务逐渐变多，不同业务之间的访问量差距较大，不同业务直接竞争数据库，相互影响性能

3.6、第五次演进：数据库按业务分库

把不同业务的数据保存到不同的数据库中，使业务之间的资源竞争降低，对于访问量大的业务，可以部署更多的服务器来支撑。这样同时导致跨业务的表无法直接做关联分析，需要通过其他途径来解决，但这不是本文讨论的重点，有兴趣的可以自行搜索解决方案。

随着用户数的增长，单机的写库会逐渐会达到性能瓶颈

3.7、第六次演进：把大表拆分为小表

比如针对评论数据，可按照商品ID进行hash，路由到对应的表中存储；针对支付记录，可按照小时创建表，每个小时表继续拆分为小表，使用用户ID或记录编号来路由数据。只要实时操作的表数据量足够小，请求能够足够均匀的分发到多台服务器上的小表，那数据库就能通过水平扩展的方式来提高性能。其中前面提到的Mycat也支持在大表拆分为小表情况下的访问控制。

这种做法显著的增加了数据库运维的难度，对DBA的要求较高。数据库设计到这种结构时，已经可以称为分布式数据库，但是这只是一个逻辑的数据库整体，数据库里不同的组成部分是由不同的组件单独来实现的，如分库分表的管理和请求分发，由Mycat实现，SQL的解析由单机的数据库实现，读写分离可能由网关和消息队列来实现，查询结果的汇总可能由数据库接口层来实现等等，这种架构其实是MPP（大规模并行处理）架构的一类实现。

目前开源和商用都已经有不少MPP数据库，开源中比较流行的有Greenplum、TiDB、Postgresql XC、HAWQ等，商用的如南大通用的GBase、睿帆科技的雪球DB、华为的LibrA等等，不同的MPP数据库的侧重点也不一样，如TiDB更侧重于分布式OLTP场景，Greenplum更侧重于分布式OLAP场景，这些MPP数据库基本都提供了类似Postgresql、Oracle、MySQL那样的SQL标准支持能力，能把一个查询解析为分布式的执行计划分发到每台机器上并行执行，最终由数据库本身汇总数据进行返回，也提供了诸如权限管理、分库分表、事务、数据副本等能力，并且大多能够支持100个节点以上的集群，大大降低了数据库运维的成本，并且使数据库也能够实现水平扩展。

数据库和Tomcat都能够水平扩展，可支撑的并发大幅提高，随着用户数的增长，最终单机的Nginx会成为瓶颈

3.8、第七次演进：使用LVS或F5来使多个Nginx负载均衡

由于瓶颈在Nginx，因此无法通过两层的Nginx来实现多个Nginx的负载均衡。图中的LVS和F5是工作在网络第四层的负载均衡解决方案，其中LVS是软件，运行在操作系统内核态，可对TCP请求或更高层级的网络协议进行转发，因此支持的协议更丰富，并且性能也远高于Nginx，可假设单机的LVS可支持几十万个并发的请求转发；F5是一种负载均衡硬件，与LVS提供的能力类似，性能比LVS更高，但价格昂贵。由于LVS是单机版的软件，若LVS所在服务器宕机则会导致整个后端系统都无法访问，因此需要有备用节点。可使用keepalived软件模拟出虚拟IP，然后把虚拟IP绑定到多台LVS服务器上，浏览器访问虚拟IP时，会被路由器重定向到真实的LVS服务器，当主LVS服务器宕机时，keepalived软件会自动更新路由器中的路由表，把虚拟IP重定向到另外一台正常的LVS服务器，从而达到LVS服务器高可用的效果。

此处需要注意的是，上图中从Nginx层到Tomcat层这样画并不代表全部Nginx都转发请求到全部的Tomcat，在实际使用时，可能会是几个Nginx下面接一部分的Tomcat，这些Nginx之间通过keepalived实现高可用，其他的Nginx接另外的Tomcat，这样可接入的Tomcat数量就能成倍的增加。

由于LVS也是单机的，随着并发数增长到几十万时，LVS服务器最终会达到瓶颈，此时用户数达到千万甚至上亿级别，用户分布在不同的地区，与服务器机房距离不同，导致了访问的延迟会明显不同

3.9、第八次演进：通过DNS轮询实现机房间的负载均衡

在DNS服务器中可配置一个域名对应多个IP地址，每个IP地址对应到不同的机房里的虚拟IP。当用户访问www.taobao.com时，DNS服务器会使用轮询策略或其他策略，来选择某个IP供用户访问。此方式能实现机房间的负载均衡，至此，系统可做到机房级别的水平扩展，千万级到亿级的并发量都可通过增加机房来解决，系统入口处的请求并发量不再是问题。

随着数据的丰富程度和业务的发展，检索、分析等需求越来越丰富，单单依靠数据库无法解决如此丰富的需求

3.10、第九次演进：引入NoSQL数据库和搜索引擎等技术

当数据库中的数据多到一定规模时，数据库就不适用于复杂的查询了，往往只能满足普通查询的场景。对于统计报表场景，在数据量大时不一定能跑出结果，而且在跑复杂查询时会导致其他查询变慢，对于全文检索、可变数据结构等场景，数据库天生不适用。因此需要针对特定的场景，引入合适的解决方案。如对于海量文件存储，可通过分布式文件系统HDFS解决，对于key value类型的数据，可通过HBase和Redis等方案解决，对于全文检索场景，可通过搜索引擎如ElasticSearch解决，对于多维分析场景，可通过Kylin或Druid等方案解决。

当然，引入更多组件同时会提高系统的复杂度，不同的组件保存的数据需要同步，需要考虑一致性的问题，需要有更多的运维手段来管理这些组件等。

引入更多组件解决了丰富的需求，业务维度能够极大扩充，随之而来的是一个应用中包含了太多的业务代码，业务的升级迭代变得困难

3.11、第十次演进：大应用拆分为小应用

按照业务板块来划分应用代码，使单个应用的职责更清晰，相互之间可以做到独立升级迭代。这时候应用之间可能会涉及到一些公共配置，可以通过分布式配置中心Zookeeper来解决。

不同应用之间存在共用的模块，由应用单独管理会导致相同代码存在多份，导致公共功能升级时全部应用代码都要跟着升级

3.12、第十一次演进：复用的功能抽离成微服务

如用户管理、订单、支付、鉴权等功能在多个应用中都存在，那么可以把这些功能的代码单独抽取出来形成一个单独的服务来管理，这样的服务就是所谓的微服务，应用和服务之间通过HTTP、TCP或RPC请求等多种方式来访问公共服务，每个单独的服务都可以由单独的团队来管理。此外，可以通过Dubbo、SpringCloud等框架实现服务治理、限流、熔断、降级等功能，提高服务的稳定性和可用性。

不同服务的接口访问方式不同，应用代码需要适配多种访问方式才能使用服务，此外，应用访问服务，服务之间也可能相互访问，调用链将会变得非常复杂，逻辑变得混乱

3.13、第十二次演进：引入企业服务总线ESB屏蔽服务接口的访问差异

通过ESB统一进行访问协议转换，应用统一通过ESB来访问后端服务，服务与服务之间也通过ESB来相互调用，以此降低系统的耦合程度。这种单个应用拆分为多个应用，公共服务单独抽取出来来管理，并使用企业消息总线来解除服务之间耦合问题的架构，就是所谓的SOA（面向服务）架构，这种架构与微服务架构容易混淆，因为表现形式十分相似。个人理解，微服务架构更多是指把系统里的公共服务抽取出来单独运维管理的思想，而SOA架构则是指一种拆分服务并使服务接口访问变得统一的架构思想，SOA架构中包含了微服务的思想。

业务不断发展，应用和服务都会不断变多，应用和服务的部署变得复杂，同一台服务器上部署多个服务还要解决运行环境冲突的问题，此外，对于如大促这类需要动态扩缩容的场景，需要水平扩展服务的性能，就需要在新增的服务上准备运行环境，部署服务等，运维将变得十分困难

3.14、第十三次演进：引入容器化技术实现运行环境隔离与动态服务管理

目前最流行的容器化技术是Docker，最流行的容器管理服务是Kubernetes(K8S)，应用/服务可以打包为Docker镜像，通过K8S来动态分发和部署镜像。Docker镜像可理解为一个能运行你的应用/服务的最小的操作系统，里面放着应用/服务的运行代码，运行环境根据实际的需要设置好。把整个“操作系统”打包为一个镜像后，就可以分发到需要部署相关服务的机器上，直接启动Docker镜像就可以把服务起起来，使服务的部署和运维变得简单。

在大促的之前，可以在现有的机器集群上划分出服务器来启动Docker镜像，增强服务的性能，大促过后就可以关闭镜像，对机器上的其他服务不造成影响（在3.14节之前，服务运行在新增机器上需要修改系统配置来适配服务，这会导致机器上其他服务需要的运行环境被破坏）。

使用容器化技术后服务动态扩缩容问题得以解决，但是机器还是需要公司自身来管理，在非大促的时候，还是需要闲置着大量的机器资源来应对大促，机器自身成本和运维成本都极高，资源利用率低

3.15、第十四次演进：以云平台承载系统

系统可部署到公有云上，利用公有云的海量机器资源，解决动态硬件资源的问题，在大促的时间段里，在云平台中临时申请更多的资源，结合Docker和K8S来快速部署服务，在大促结束后释放资源，真正做到按需付费，资源利用率大大提高，同时大大降低了运维成本。

所谓的云平台，就是把海量机器资源，通过统一的资源管理，抽象为一个资源整体，在之上可按需动态申请硬件资源（如CPU、内存、网络等），并且之上提供通用的操作系统，提供常用的技术组件（如Hadoop技术栈，MPP数据库等）供用户使用，甚至提供开发好的应用，用户不需要关系应用内部使用了什么技术，就能够解决需求（如音视频转码服务、邮件服务、个人博客等）。在云平台中会涉及如下几个概念：

IaaS：基础设施即服务。对应于上面所说的机器资源统一为资源整体，可动态申请硬件资源的层面；

PaaS：平台即服务。对应于上面所说的提供常用的技术组件方便系统的开发和维护；

SaaS：软件即服务。对应于上面所说的提供开发好的应用或服务，按功能或性能要求付费。

至此，以上所提到的从高并发访问问题，到服务的架构和系统实施的层面都有了各自的解决方案，但同时也应该意识到，在上面的介绍中，其实是有意忽略了诸如跨机房数据同步、分布式事务实现等等的实际问题，这些问题以后有机会再拿出来单独讨论

4、架构设计总结

4.1、架构的调整是否必须按照上述演变路径进行？

不是的，以上所说的架构演变顺序只是针对某个侧面进行单独的改进，在实际场景中，可能同一时间会有几个问题需要解决，或者可能先达到瓶颈的是另外的方面，这时候就应该按照实际问题实际解决。如在政府类的并发量可能不大，但业务可能很丰富的场景，高并发就不是重点解决的问题，此时优先需要的可能会是丰富需求的解决方案。

4.2、对于将要实施的系统，架构应该设计到什么程度？

对于单次实施并且性能指标明确的系统，架构设计到能够支持系统的性能指标要求就足够了，但要留有扩展架构的接口以便不备之需。对于不断发展的系统，如电商平台，应设计到能满足下一阶段用户量和性能指标要求的程度，并根据业务的增长不断的迭代升级架构，以支持更高的并发和更丰富的业务。

4.3、服务端架构和大数据架构有什么区别？

所谓的“大数据”其实是海量数据采集清洗转换、数据存储、数据分析、数据服务等场景解决方案的一个统称，在每一个场景都包含了多种可选的技术，如数据采集有Flume、Sqoop、Kettle等，数据存储有分布式文件系统HDFS、FastDFS，NoSQL数据库HBase、MongoDB等，数据分析有Spark技术栈、机器学习算法等。总的来说大数据架构就是根据业务的需求，整合各种大数据组件组合而成的架构，一般会提供分布式存储、分布式计算、多维分析、数据仓库、机器学习算法等能力。而服务端架构更多指的是应用组织层面的架构，底层能力往往是由大数据架构来提供。

4.4、有没有一些架构设计的原则？

N+1设计：统中的每个组件都应做到没有单点故障；

回滚设计：确保系统可以向前兼容，在系统升级时应能有办法回滚版本；

禁用设计：：应该提供控制具体功能是否可用的配置，在系统出现故障时能够快速下线功能；

监控设计：在设计阶段就要考虑监控的手段；

多活数据中心设计：若系统需要极高的高可用，应考虑在多地实施数据中心进行多活，至少在一个机房断电的情况下系统依然可用；

采用成熟的技术：刚开发的或开源的技术往往存在很多隐藏的bug，出了问题没有商业支持可能会是一个灾难；

资源隔离设计：应避免单一业务占用全部资源；

架构应能水平扩展：系统只有做到能水平扩展，才能有效避免瓶颈问题；

非核心则购买：非核心功能若需要占用大量的研发资源才能解决，则考虑购买成熟的产品；

使用商用硬件：商用硬件能有效降低硬件故障的机率；

快速迭代：系统应该快速开发小功能模块，尽快上线进行验证，早日发现问题大大降低系统交付的风险；

无状态设计：服务接口应该做成无状态的，当前接口的访问不依赖于接口上次访问的状态。

发表在设计 | 留下评论

分布式架构设计之架构演进之路

发表于2019年7月29日由javahao123

互联网产品的发展速度是很快的，若发展速度增快技术跟不上，是影响业务的发展和用户的体现。

今天我们以电商为例讲解决下分布式的技术架构的演进

1.一开始我们搭建一个初始版本的系统或在市场买一个系统，他们的架构或许是这样的如下图

一个机器部署一个tomcat和一个数据库。tomcat容器下部署所有的业务。由于你的业务发展的很好，用户量访问比较多。当某一天发现访问界面非常慢，可能会发生卡死的情况。由于我们会自己对架构进行调整，若不调整你的老板很快找到你。让你提出架构方案，若心里没有准备那么在老板眼里你就……

于是我们提出加一台机器做数据库分离开，分离后成为应用服务器和数据库服务器，如下图

刚刚拆分完没几天，发现流量又支持不住了，那么还是同样方法加一个机器，那么这次加的是应用服务器，把应用服务器搭建成一个集群，集群可以平滑对应用扩展，避免开发成本和开发速度两次都是采用加机器的方式来解决访问速度慢的问题。

刚做了集群后遇到一个问题，那就是一个用户发起两次请求时发现总是让提示登录，这样是体现不好的。是因为HTTP是无状态的我们通过用户本地（cookie+sessionid）方式保存会话。服务器以（sessionid，Object）的方式保存用户信息，若用户与服务器匹配成功，则允许访问否则会提示登录。若用户禁止cookie，则采用url请求带sessionId的方式。

那么集群是多个服务器，那么一个会话请求多个服务器会认识是两次会话。会造成总是提示登录问题。由于我们需要解决共享Session的问题，在用户每次请求时都会请求session服务器，判断用户的请求是否有效。

于是我们可以采用硬负载或软负载，搭建的集群架构引入硬负载或软负载如下

当用户越来越多，我们的界面能够抗的住，但发现我们数据库是个瓶颈，那我们会拆分数据库，添加一台数据库。那么我们可以做主备方案/主从方案，写操作放到写库中，读操作放到读库中，通过主备方案进行数据同步。

在互联网的产品场景下，搜索功能比较多，数据库搜索在当前场景下已经不满足要求。于是我们引入搜索引擎来解决检索问题。因为搜索引擎的数据是由数据库来，那么我们又有一些问题，如哪些数据是采用全量搜索，哪些数据采用增量数据。是采用同步同步还是异步同步等等问题，这里在不同场景所要关注的问题。

对于搜索还需要对搜索词进行分词、语义、sku进行处理等在这里是比较复杂的一个技术。

根据用户的请求越来越多，为了增加高访问量我们采用通过热点数据加入缓存处理。缓存可以对页面缓存、数据缓存。

对于缓存我们后面讲解决加入缓存后对缓存的存储、缓存雪崩、缓存击穿、布隆过滤器、缓存持久化，还有在使用缓存时如何对缓存和数据库之间的数据同步。

大多我们是把缓存是应用服务器和数据库之间，在应用服务器访问时优先访问缓存，若缓存不存在时在访问数据库，这样减少对数据库IO的访问。当修改时先修改数据库在修改缓存或先修改缓存在修改数据库的方式。那么对造成两边数据一致性问题，这些是引入缓存所带来的一些问题，当然引入后带来的性能也是非常大的。

网站大了用户量大了，对于数据量和IO也会非常大。所以我们在数据库层次上，会考虑到对数据库按照业务维度进行垂直分库

拆分以后我们每一个DB都是独立的，用户模块的应用访问用户的数据库，商品模块访问数据库。这样的好处有两种一种是对数据隔离，一种是对每个Db进行独立部署。可以利用多个计算资源来完成整合操作。通过垂直拆分可以解决对IO问题和访问量大的问题。

如果访问量还是很大，那么就会存在大表的情况。这种情况我们是采用水平拆分，水平拆分的规则是对于大数据表（100W条或1000W条以上的表），拆成每个表100W或1000W的小表。拆成小表了，那么在SQL检索时的性能会更大。这就是通过拆分所带来的好处。水平拆分又分为分库分表或分区分表，我们应该采用哪种方式也是我们要考虑的问题。

对于千万级的表即提供C端用户也会提供运营用户，这样会带来检索条件过多带来性能下降。由于我们要对数据做隔离，分在线数据和离线数据。

后面当业务发展比较快，我们的业务越来越多，那么应用会变的很复杂。应用包含业务、逻辑、体量那么会变的也很复杂，那么我们会对模块进行拆分。

体量比较大的情况下有以下几种困难，不满足我们敏捷迭代的一些要求

不好调优
不好扩展
改变影响比较大
开发运维部署

通过以上几点我们对应用进行拆分。原来如查询用户商品时直接把用户和商品组合起来，这样耦合度很多若对一个模块进行修改那么是个灾难。

于是把应用以服务的方式进行抽象，抽象的结果如下

业务服务分别是商品前台、用户前台、支付前台。

公共服务分别是商品中台、用户中台、支付中台

抽象出会发现商品前台调用商品中台，用户前台也会调用商品中台，那么支付前台也会调用商品中台。我举例的服务并不多，这么一来关系非常复杂。若有上百个服务或上千个服务，他们的关系更是一个灾难。由于现在比较流行的企业网关。

对于现在来说发展的比较大了，有些公司会根据自己的实力做一些中间件，来满足业务发展带来的技术问题。如服务治理中间件（dubbo）、消息中心（kafka/rabbitmq）、配置中心、定时调度中心、链路调用监控平台、系统监控等等。

以上是根据现在平台的技术，分析从开始到现在的发展架构

发表在设计 | 留下评论

到底啥是分布式系统开发经验？

发表于2019年5月31日由javahao123

来自：中华石杉

前言

现在有很多Java技术方向的同学在找工作的时候，肯定都会去招聘网站上找职位投递简历。

但是在很多职位JD上往往会有这样的一个要求：熟悉分布式系统理论、设计和开发，具备复杂分布式系统构建经验。

之前不少同学后台留言问过我：这个分布式系统的设计和开发经验，到底指的是什么？那么这篇文章就给大家来解释一下这个问题。

继续阅读 →

发表在设计 | 留下评论

从 0 开始手写一个 Mybatis 框架，三步搞定

发表于2019年5月31日由javahao123

来源：芋道源码

一、Mybatis框架流程简介
二、梳理自己的Mybatis的设计思路
三、实现自己的Mybatis

继续阅读 →

发表在设计 | 留下评论

API 设计最佳实践的思考

发表于2019年5月17日由javahao123

来源：阿里技术

前言

API 设计面临的挑战千差万别，很难有处处适用的准则，所以在讨论原则和最佳实践时，无论这些原则和最佳实践是什么，一定有适应的场景和不适应的场景。因此我们在下文中不仅提出一些建议，也尽量去分析这些建议在什么场景下适用，这样我们也可以有针对性地采取例外的策略。

为什么去讨论这些问题？ API 是软件系统的核心，而软件系统的复杂度 Complexity 是大规模软件系统能否成功最重要的因素。但复杂度 Complexity 并非某一个单独的问题能完全败坏的，而是在系统设计尤其是API设计层面很多很多小的设计考量一点点叠加起来的（John Ousterhout老爷子说的Complexity is incremental【8】）。成功的系统不是有一些特别闪光的地方，而是设计时点点滴滴的努力积累起来的

继续阅读 →

发表在设计 | 留下评论

集群调度系统的演进2-Kubernetes

发表于2019年4月29日由javahao123

来自：邵明岐

在这边文章，我会详细介绍一下 Kubernetes 的架构，您在看这篇文章之前，需要提前了解一下 Kubernetes 是什么，以及一些基本概念。

关于调度系统架构的文章，这是系列的第二篇，之前的第一篇请移步这这里阅读：集群调度系统的演进。在文章里面，通过介绍 Hadoop MRv1、YARN和Mesos调度系统，了解了调度系统的架构和演进过程，那么现在最新最流行的 Kubernetes 的架构是什么样子的呢？这篇文章就给大家介绍一下 Kubernetes 整体架构，并且会深入探讨其中 2 个比较深入的问题。

Kubernetes 的架构解析

首先，Kubernetes 的官方架构图是这样的。

这个架构图看起来会比较复杂，很难看懂，我把这个官方的架构图重新简化了一下，就会非常容易理解了：

ETCD ：是用来存储所有 Kubernetes 的集群状态的，它除了具备状态存储的功能，还有事件监听和订阅、Leader选举的功能，所谓事件监听和订阅，各个其他组件通信，都并不是互相调用 API 来完成的，而是把状态写入 ETCD（相当于写入一个消息），其他组件通过监听 ETCD 的状态的的变化（相当于订阅消息），然后做后续的处理，然后再一次把更新的数据写入 ETCD。所谓 Leader 选举，其它一些组件比如 Scheduler，为了做实现高可用，通过 ETCD 从多个（通常是3个）实例里面选举出来一个做Master，其他都是Standby。
API Server：刚才说了 ETCD 是整个系统的最核心，所有组件之间通信都需要通过 ETCD，实际上，他们并不是直接访问 ETCD，而是访问一个代理，这个代理是通过标准的RESTFul API，重新封装了对 ETCD 接口调用，除此之外，这个代理还实现了一些附加功能，比如身份的认证、缓存等。这个代理就是 API Server。
Controller Manager：是实现任务的调度的，关于任务调度你可以参考之前的文章，简单说，直接请求 Kubernetes 做调度的都是任务，比如比如 Deployment 、Deamon Set 或者 Job，每一个任务请求发送给Kubernetes之后，都是由Controller Manager来处理的，每一个任务类型对应一个Controller Manager，比如 Deployment对应一个叫做 Deployment Controller，DaemonSet 对应一个 DaemonSet Controller。
Scheduler：是用来做资源调度的（具体资源调度的含义请参考之前的文章），Controller Manager会把任务对资源要求，其实就是Pod，写入到ETCD里面，Scheduler监听到有新的资源需要调度（新的Pod），就会根据整个集群的状态，给Pod分配到具体的节点上。
Kubelet：是一个Agent，运行在每一个节点上，它会监听ETCD中的Pod信息，发现有分配给它所在节点的Pod需要运行，就在节点上运行相应的Pod，并且把状态更新回到ETCD。
Kubectl: 是一个命令行工具，它会调用 API Server发送请求写入状态到ETCD，或者查询ETCD的状态。

这样是不是简单了很多。如果还是觉得不清楚，我们就用部署一个服务的例子来解释一个整个过程，假设你要运行一个多个实例的Nginx，那么在Kubernetes内部，整个流程是这样的：

通过kubectl命令行，创建一个包含Nginx的Deployment对象，kubectl会调用 API Server 往ETCD里面写入一个 Deployment对象。
Deployment Controller 监听到有新的 Deployment对象被写入，就获取到对象信息，根据对象信息来做任务调度，创建对应的 Replica Set 对象。
Replica Set Controller监听到有新的对象被创建，也读取到对象信息来做任务调度，创建对应的Pod来。
Scheduler 监听到有新的 Pod 被创建，读取到Pod对象信息，根据集群状态将Pod调度到某一个节点上，然后更新Pod（内部操作是将Pod和节点绑定）。
Kubelet 监听到当前的节点被指定了新的Pod，就根据对象信息运行Pod。

上面就是Kubernetes内部的是如何实现的整个 Deployment 被创建的过程。这个过程只是为了向大家解释每一个组件的职责，以及他们之间是如何相互协作的，忽略掉了很多繁琐的细节。

目前为止，我们有已经研究过了几个非常具有代表性的调度系统：Hadoop MRv1、YARN、Mesos和Kubernetes。我当时学习完这些调度系统的架构之后，在我脑子里面实际上有2个大大的疑问：

Kubernetes是二次调度的架构么，和Mesos相比它的扩展性如何？
为什么所有调度系统都是无法横向扩展的？

后面我们就针对这两个问题深入讨论一下。

Kubernetes 是否是二层调度？

在 Google 的一篇关于他们内部的 Omega 的调度系统的论文，把调度系统分成三类：单体、二层调度和共享状态三种，按照它的分类方法，通常Google的 Borg被分到单体这一类，Mesos被当做二层调度，而Google自己的Omega被当做第三类“共享状态”。论文的作者实际上之前也是Mesos的设计者之一，后来去了Google设计新的 Omega 系统，并发表了论文，论文的主要目的是提出一种全新的“Shard State”的模式来同时解决调度系统的性能和扩展性的问题，但是实际我觉得 Shared State 模型太过理想化，根据这个模型开发的Omega系统，似乎在Google内部并没有被大规模使用，也没有任何一个大规模使用的调度系统采是采用 Shared State 模型。

因为Kubernetes的大部分设计是延续 Borg的，而且Kubernetes的核心组件（Controller Manager和Scheduler）缺省也都是绑定部署在一起，状态也都是存储在ETCD里面的的，所以通常大家会把Kubernetes也当做“单体”调度系统，实际上我并不赞同。

我认为 Kubernetes 的调度模型也完全是二层调度的，和 Mesos 一样，任务调度和资源的调度是完全分离的，Controller Manager承担任务调度的职责，而Scheduler则承担资源调度的职责。

实际上Kubernetes和Mesos调度的最大区别在于资源调度请求的方式：

主动 Push 方式。是 Mesos 采用的方式，就是 Mesos 的资源调度组件（Mesos Master）主动推送资源 Offer 给 Framework，Framework 不能主动请求资源，只能根据 Offer 的信息来决定接受或者拒绝。
被动 Pull 方式。是 Kubernetes 的方式，资源调度组件 Scheduler 被动的响应 Controller Manager的资源请求。

这两种方式所带来的不同，我会主要从下面 5 个方面来分析。另外注意，我所比较两者的优劣，都是从理论上做的分析，工程实现上会有差异，一些指标我也并没有实际测试过。

1）资源利用率：Kubernetes 胜出

理论上，Kubernetes 应该能实现更加高效的集群资源利用率，原因资源调度的职责完全是由Scheduler一个组件来完成的，它有充足的信息能够从全局来调配资源，然后 Mesos 缺却做不到，因为资源调度的职责被切分到Framework和Mesos Master两个组件上，Framework 在挑选 Offer 的时候，完全没有其他 Framework 的工作负载的信息，所以也不可能做出最优的决策。我们来举一个例子，比如我们希望把对耗费 CPU的工作负载和耗费内存的工作负载竟可能调度到同一台主机上，在Mesos里面不太容易做到，因为他们是属于不同的 Framework。

2）扩展性：Mesos胜出

从理论上讲，Mesos 的扩展性要更好一点。原因是Mesos的资源调度方式更容易让已经存在的任务调度迁移上来。我来举一个例子说明一下，假设已经有了一个任务调度系统，比如 Spark ，现在要迁移到集群调度平台上，理论上它迁移到 Mesos 比 Kubernetes 上更加容易。

如果迁移到 Mesos ，没有改变它原来的工作流程和逻辑，原来的逻辑是：来了一个作业请求，调度系统把任务拆分成小的任务，然后从资源池里面挑选一个节点来运行任务，并且记录挑选的节点 IP 和端口号，用来跟踪任务的状态。迁移到 Mesos 之后，还是一样的逻辑，唯一需要变化的是那个资源池，原来是自己管理的资源池，现在变成 Mesos 提供的Offer 列表。

如果迁移到 Kubernetes，则需要修改原来的基本逻辑来适配 Kubernetes，资源的调度完全需要调用外部的组件来完成，并且这个变成异步的。

3）灵活的任务调度策略：Mesos 胜出

Mesos 对各种任务的调度策略也要支持的更好。举个例子，如果某一个作业，需要 All or Nothing 的策略，Mesos 是能够实现的，但是 Kubernetes 完全无法支持。所以为的 All or Nothing 的意思是，价格整个作业如果需要运行 10 个任务，这 10个任务需要能够全部有资源开始执行，否则的话就一个都不执行。

4）性能：Mesos 胜出

Mesos 的性能应该更好，因为资源调度组件，也就是 Mesos Master 把一部分资源调度的工作甩给 Framework了，承担的调度工作更加简单，从数据来看也是这样，在多年之前 Twitter 自己的 Mesos 集群就能够管理超过 8万个节点，而 Kubernetes 1.3 只能支持 5千个节点。

5）调度延迟：Kubernetes 胜出

Kubernetes调度延迟会更好。因为Mesos的轮流给Framework提供Offer机制，导致会浪费很多时间在给不需要资源的 Framework 提供Offer。

为什么不支持横向扩展？

看到可能注意到了，几乎所有的集群调度系统都无法横向扩展（Scale Out），比如早期的 Hadoop MRv1 的管理节点是单节点，管理的集群上线是 5000 台机器，YARN 资源管理节点同时也只能有一个节点工作，其他都是备份节点，能够管理的机器的上限1万个节点，Mesos通过优化，一个集群能够管理 8 万个节点，Kubernetes 目前的 1.13 版本，集群管理节点的上限是 5000 个节点。

所有的集群调度系统的架构都是无法横向扩展的，如果需要管理更多的服务器，唯一的办法就是创建多个集群。集群调度系统的架构看起来都是这个样子的：

中间的 Scheduler（资源调度器）是最核心的组件，虽然通常是由多个（通常是3个）实例组成，但是都是单活的，也就是说只有一个节点工作，其他节点都处于 Standby 的状态。为什么会这样呢？看起来不符合互联网应用的架构设计原则，现在大部分互联网的应用通过一些分布式的技术，能够很容易的实现横向扩展，比如电商的应用，在促销的时候，通过往集群里面添加服务器，就能够提升服务的吞吐量。如果是按照互联网应用的架构，看起来应该是这样的：

Scheduler 应该是可以多活的，有任意多的实例一起对外提供服务，无论是资源的消费者，还是资源的提供者在访问 Scheduler 的时候，都需要经过一个负载均衡的组件或者设备，负责把请求分配给某一个 Scheduler 实例。为什么这种架构在集群调度系统里面变得不可行么？为了理解这件事情，我们先通过一个互联网应用的架构的例子，来探讨一下具备横向扩展需要哪些前提条件。

横向扩展架构的前提条件

假设我们要实现这样一个电商系统吧：

这是一个二手书的交易平台，有非常多的卖家在平台上提供二手书，我们暂且把每一本二手书叫做库存吧
卖家的每一个二手书库存，根据书的条码，都可以找到图书目录中一本书，我们把这本书叫做商品吧
卖家在录入二手书库存的时候，除了录入是属于哪一个商品，同时还需要录入其他信息，比如新旧程度、价钱、发货地址等等。
买家浏览图书目录，选中一本书，然后下单，订单系统根据买家的要求（价格偏好、送货地址等），用算法从这本书背后的所有二手书库存中，匹配一本符合要求的书完成匹配，我们把这个过程叫订单匹配好了。

这样一个系统，从模型上看这个电商系统和集群调度系统没啥区别，这个里面有资源提供者（卖家），提供某种资源（二手书），组成一个资源池（所有二手书），也有资源消费者（买家），提交自己对资源的需求，然后资源调度器（订单系统）根据算法自动匹配一个资源（一本二手书），但是很显然，这个电商系统是可以设计成横向扩展架构的，这是为什么呢，这个电商系统和集群调度系统的区别到底在什么地方？我想在回答这个问题之前，我们先来回答另外一个问题：这个电商系统横向扩展的节点数是否有上限，上限是多少，这个上限是有什么因素决定的？

系统理论上的并发数量决定了横向扩展的节点数

怎么来理解这个事情呢，假设系统架构设计的时候，不考虑任何物理限制（比如机器的资源大小，带宽等），能够并发处理 1000个请求，那么很显然，横向扩展的节点数量上限就是1000，应为就算部署了 1001个节点，在任何时候都有一个节点是处于空闲状态，部署更多的节点已经完全无法提高系统的性能。我们下面需要想清楚的问题其实就变成了：系统理论上能够并发处理请求的数量是多少，是有什么因素决定的。

系统的并发数量是由“独立资源池”的数量决定的

“独立资源池”是我自己造出来的一个词，因为实在想不到更加合适的。还是以上面的电商系统为例，这个订单系统的理论上能够处理的并发请求（订购商品请求）数量是由什么来决定的呢？先看下面的图吧：

在订单系统在匹配需求的时候，实际上应该是这样运行的，在订单请求来了之后，根据订单请求中的购买的商品来排队，购买同一个商品的请求被放在一个队列里面，然后订单的调度系统开始从队列里面依次处理请求，每次做订单匹配的时候，都需根据当前商品的所有库存，从里面挑选一个最佳匹配的库存。虽然在实现这个系统的时候，这个队列不见得是一个消息队列，可能会是一个关系型数据库的锁，比如一个购买《乔布斯传》的一个订单，系统在处理的时候需要先要从所有库存里面查询出《乔布斯传》的库存，将库存记录锁住，并且做订单匹配并且更新库存（将生成订单的库存商品设置为”不可用”状态）之后，才会将数据库锁释放，这个时候实际上所有后续购买《乔布斯传》的订单请求都在队列中等待，也有些系统在实现的时候采用“乐观锁”，就是在每一次订单处理的时候，并不会在第一开始就锁住库存信息，而是在最后一步更新库存的时候才会锁住，如果发生两个订单匹配到了同一个库存物品，那么其中一个订单处理就需要完全放弃然后重试。这两种实现方式不太一样，但是本质都是相同的。

所以从上面的讨论可以看出来，之所以所有购买《乔布斯传》的订单需要排队处理，原因是因为每一次做订单匹配的时候，需要所有乔布斯传的这个商品的所有库存信息，并且最后会修改（占用）一部分库存信息的状态。在这个订单匹配的场景里面，我们就把乔布斯传的所有库存信息叫做一个“独立资源池”，订单匹配这个“调度系统”的最大并发数量就完全取决于独立资源池的数量，也就是商品的数量。我们假设一下，如果这个二手书的商城只卖《乔布斯传》一本书，那么最后所有的请求都需要排队，这个系统也几乎是无法横向扩展的。

集群调度系统的“独立资源池”数量是 1

我们再来看一下集群调度系统，每一台服务器节点都是一个资源，每当资源消费者请求资源的时候，调度系统用来做调度算法的“独立资源池”是多大呢？答案应该是整个集群的资源组成的资源池，没有办法在切分了，因为:

调度系统的职责就是要在全局内找到最优的资源匹配。
另外，就算不需要找到最优的资源匹配，资源调度器对每一次资源请求，也没办法判断应该从哪一部分资源池中挑选资源。

正是因为这个原因，“独立资源池”数量是 1，所以集群调度系统无法做到横向扩展。

发表在设计 | 留下评论

集群调度系统的演进1-MRv1 Yarn Mesos

发表于2019年4月29日由javahao123

来自：倒霉砖家

Kubernetes 已经成为容器编排领域的事实标准，将来所有应用都会在 Kubernetes 上开发和运行，这个系列文章的目的是深入浅出的介绍 Kubernetes 底层实现的原理。

Kubernetes 是一个集群调度系统，今天这篇文章主要是介绍 Kubernetes 之前一些集群调度系统的架构，通过梳理他们的设计思路和架构特点，我们能够学习到集群调度系统的架构的演进过程，以及在架构设计时需要考虑的主要问题，对理解 Kubernetes 的架构会非常有帮助。

基本概念

我们需要先了解集群调度系统里面的一些基本的概念，为了方便大家理解，我通过一个例子来解释这些概念，假设我们要实现一个分布式的定时任务系统（分布式的 Cron），这个系统管理了一组 Linux 主机，用户通过系统提供的的 API / UI 定义定时任务（就类似在 Linux 里面定义 Crontab），系统会根据任务的定义，来定时来执行相应的任务，在这个例子里面有如下基本概念：

集群（Cluster）：这个系统管理的 Linux 主机组成一个资源池，用来运行任务，这个资源池就是集群。
作业（Job）：就是定义集群如何去执行任务，在例子里面 Crontab 就是一个简单的作业，里面明确的告诉了集群需要在什么时间（时间间隔），做什么事情（执行的脚本）。一些作业的定义会复杂很多，比如还会定义一个作业分几个任务做完，以及任务之间的依赖关系，还包括每一个任务对资源的需求。
任务（Task）：作业需要被调度成具体的执行任务，如果我们定义了一个作业是每天晚上凌晨 1 点执行一个脚本，那么在每天凌晨 1点被执行的这个脚本进程就是任务。

在设计集群调度系统的时候，这个调度系统的核心任务也就是 2 个：

任务调度。作业提交给集群调度系统之后，需要对提交的作业拆分成具体的执行任务，并且跟踪和监控任务的执行结果。在分布式 Cron 的例子中，调度系统需要按照作业的要求定时启动进程，如果进程执行失败，需要重试等，一些复杂的场景，比如 Hadoop 的 Map Reduce ，调度系统需要把 Map Reduce 任务拆分成相应的多个 Map 和 Reduce 任务，并且最终拿到任务执行结果的数据。
资源调度：本质上是对任务和资源做匹配，根据集群中主机的资源使用情况，分配合适的资源来运行任务。和操作系统的进程调度算法比较类似，资源调度的主要目标是，在固定的资源供给的情况下，尽可能提高资源使用率，减少任务等待的时间（任务等待资源去执行的时间），减少任务运行的延迟或者响应时间（如果是批量任务的话，就是任务从开始执行到结束的时间，如果在线响应式任务的话，比如 Web 应用，就是每一次响应请求的时间），尽可能公平（资源公平的被分配到所有任务）的同时，还需要考虑任务的优先级。这些目标里面有一些是有冲突的，需要平衡，比如资源利用率和响应时间，公平和优先级。

Hadoop MRv1

Map Reduce 是一种并行计算模型，Hadoop 是可以运行这种并行计算的集群管理平台，其中 MRv1 是 Hadoop 平台的 Map Reduce 任务调度引擎的第一代版本，简单来说，用户定义了一个 Map Reduce 计算，提交给 Hadoop 之后，由 MRv1 负责在集群上调度和执行这个作业，并且返回计算结果。 MRv1 的架构看起来是这样的：

架构还是比较简单的，标准的 Master/Slave 的架构，有 2 个核心组件：

Job Tracker 是集群主要的管理组件，同时承担了资源调度和任务调度的责任。
Task Tracker 运行在集群的每一台机器上，负责在主机上运行具体的任务，并且汇报状态。

随着 Hadoop 的流行和各种需求的增加，MRv1 有如下问题需要改进：

性能有一定瓶颈：支持管理的最大节点数是 5千个节点，支持运行的任务最大数量 4万，还有一定的提高空间。
不够灵活，无法扩展支持其他任务类型。Hadoop 生态里面除了 Map Reduce 类型任务，还有其他很多任务类型需要调度，比如 Spark，Hive，HBase，Storm，Oozie 等，所以需要一个更加通用的调度系统，能够支持和扩展更多的任务类型。
资源利用率比较低。MRv1 给每个节点静态配置了固定数目的 Slot ，每个 Slot 也只能够运行的特定的任务的类型（Map or Reduce），这就导致资源利用率的问题，比如大量 Map 任务在排队等待空闲资源，但实际上机器有大量 Reduce 的 Slot 被闲置。
多租户和多版本的问题。比如不同部门在同一个集群里面运行任务，但是彼此是逻辑上隔离的，或者在同一个集群里面运行不同版本的 Hadoop。

YARN

YARN( Yet Another Resource Negotiator）是 Hadoop 的第二代调度系统，主要目的就是为了解决 MRv1 中的各种问题。YARN 的架构看起来是这样的

YARN 简单的理解就是，相对于 MRv1 的主要改进就是，把原来的 JobTrack 的职责，拆分给两个不同的组件来完成：Resource Manager 和 Application Master

Resource Manager：承担资源调度的职责，管理所有资源，将资源分配给不同类型的任务，并且通过“可插拔”的架构来很容易的扩展资源调度算法。
Application Master：承担任务调度的职责，每一个作业（在 YARN 里面叫做 Application）都会启动一个对应的 Application Master，它来负责把作业拆分成具体的任务、向 Resource Manager 申请资源、启动任务、跟踪任务的状态并且汇报结果。

我们看看这种架构改变是如何解决 MRv1 的各种问题的：

将原来的 Job Tracker 的任务调度职责拆分出来，大幅度提高了性能。原来的 Job Tracker 的任务调度的职责拆分出来由 Application Master 承担，并且 Application Master 是分布式的，每一个实例只处理一个作业的请求，将原来能够支撑的集群节点最大数量，从原来的5千节点提升到1万节点。
任务调度的组件，Application Master，和资源调度解耦，而且是根据作业的请求而动态创建的，一个 Application Master 实例只负责一个作业的调度，也就更加容易支持不同类型的作业。
引入了容器隔离技术，每一个任务都是在一个隔离的容器里面运行，根据任务对资源的需求来动态分配资源，大幅提高了资源利用率。不过有一个缺点是，YARN 的资源管理和分配，只有内存一个维度。

Mesos 的架构

YARN 的设计目标依然是服务于 Hadoop 生态的调度，Mesos 的目标更近一步，被设计成一个通用的调度系统，能够管理整个数据中心的作业，看的出来 Mesos 的架构设计很多借鉴了 YARN，将作业调度和资源调度分别由不同的模块承担，不过 Mesos 和 YARN 很大不同的地方是对资源的调度方式，设计了一个叫非常独特的 Resource Offer 的机制，进一步释放了资源调度的压力，增加了作业调度的扩展性。

Mesos 的主要组件是：

Mesos Master ，单纯是承担资源分配和管理的组件，的对应到 YARN 里面就是那个 Resource Manager，不过工作方式会稍微有些不太一样，后面会讲到。
Framework，承担作业调度，不同的作业类型都会有一个对应的 Framework，比如负责 Spark 作业的 Spark Framework。

Mesos 的 Resource Offer

看起来 Mesos 和 YARN 架构非常类似，不过实际上在资源管理的方面， Mesos 的 Master 有非常独特（甚至有些奇怪）的 Resource Offer 机制：

YARN 中 Resource Manager 提供资源的方式是被动的，当资源的消费者（Application Master) 需要资源的时候，会调用 Resource Manager 的接口来获取到资源，Resource Manager 只是被动的响应 Application Master 的需求。
Mesos 的 Master 提供资源的方式是主动的。Mesos 中的 Master 会定期的主动推送当前的所有可用的资源（就是所谓的 Resource Offer，后面统一都叫 Offer）给 Framework，Framework 如果有任务需要被执行，不能主动申请资源，只有当接收到 Offer 的时候，从 Offer 里面挑选满足要求的资源来接受（在 Mesos 里面这个动作叫做 Accept），剩余的 Offer 就都拒绝掉（这个动作叫做 Reject），如果这一轮 Offer 里面没有足够能够满足要求的资源，只能等待下一轮 Master 提供 Offer。

相信大家看到这个主动的 Offer 机制的时候，会和我有同样的感觉，就是效率比较低，会产生如下问题：

任何一个 Framework 的决策效率会影响整体的效率。为了一致性，Master 一次只能给一个 Framework 提供 Offer，等待这个 Framework 挑选完 Offer 之后，再把剩余的提供给下一个 Framework，这样的话，任何一个 Framework 做决策的效率就会影响整体的效率；
“浪费”很多时间在不需要资源的 Framework 上。 Mesos 并不知道哪个 Framework 需要资源，所以会出现有资源需求的 Framework 在排队等待 Offer，但是没有资源需求的 Framework 却频繁收到 Offer 的情况。

针对上面的问题，Mesos 提供了一些机制来做一定程度的缓解，比如给 Framework 设置一个做决策的超时时间，或者允许 Framework 可以通过设置成 Suppress 状态来表示不需要接受 Offer等，因为不是本次讨论的重点，所以细节就不展开了。

实际上，Mesos 采用这种主动 Offer 的机制，也是有一些明显的优点的：

性能明显提高。根据模拟测试一个集群最大可以支撑 10 万个节点，Twitter 的生产环境最大集群支撑 8 万个节点，主要原因是 Mesos Master主动 Offer 的机制，进一步简化了 Mesos Master 的工作职责，Mesos 中将资源调度的过程（资源 —> 任务的匹配）分成了 2 个阶段：资源 —> Offer —> 任务。Mesos Master 只负责完成第一个阶段，第二个阶段的匹配交给 Framework 来完成。
更加灵活，能够满足更加负责的任务调度的策略。举个例子，All Or Nothings 的资源使用策略。

Mesos 的调度算法 DRF（Dominant Resource Fairness)

关于 DRF 算法，其实对我们理解 Mesos 架构并没有什么关系，但是在 Mesos 中却非常核心和重要，所以多啰嗦几句。

上面说了，Mesos 是轮流给 Framework 提供 Offer 的，那么每次该挑选哪个 Framework 提供 Offer 呢？这就是 DRF 算法要解决核心的问题，基本原则就是要兼顾公平和效率，在经量满足所有 Framework 对资源需求的同时，也要应该尽可能公平，避免某一个 Framework 占用太多资源而把其他 Framework 给“饿死”。

DRF 是 min-max fairness 算法的一个变形，简单来说就是每次都挑选支配资源占用率（Dominant Resource Usage）最低的那个 Framework 提供 Offer。如何计算 Framework 的“支配资源占用率”呢？就是从 Framework 占用的所有资源类型里面，挑选资源占用率最小的那个资源类型最为支配资源（Dominant Resource），它的资源占用率就是这个 Framework 的支配资源占用率（ Dominant Resource Usage），举个例子，一个 Framework X 的 CPU 占用了整体资源的 20%，内存是 30%，磁盘是 10%，那么这个 Framework 的支配资源占用率就是 10%，官方术语把磁盘叫做支配资源，这个 10% 叫做支配资源占用率。

DRF 的最终目的是把资源平均的分配给所有 Framework，如果一个 Framework X 在这一轮 Offer 中接受（Accept Offer）了过多的资源，那么就要等更长的时间才能获得下一轮 Offer 的机会。不过仔细的读者会发现，这个算法里面有一个假设，就是 Framework 接受了资源之后，会很快释放掉，否则就会有 2 个后果：

其他 Framework 被“饿死“。某个 Framework A 一次性的接受了集群中大部分资源，并且任务一直运行不退出，这样大部分资源就被 Framework A 一直霸占了，其他 Framework 就没法获得资源了。
自己被饿死。因为这个 Framework 的支配资源占用率一直很高，所以长期无法获得 Offer 的机会，也就没法运行更多的任务。

所以实际上，Mesos 只适合调度短任务，而且实际上，在企业的数据中心的资源 80% 都是被短任务消耗掉的（数据实时查询，日志流式计算，人工智能/大数据计算等），另外根据 Mesos 的 Paper 里面的数据，Facebook 的 Hadoop 平台的任务平均时长是 84 秒。

总结一下

从大的架构上，所有调度系统的架构都是 Master / Slave 的架构，Slave 端安装在每一台需要管理的机器上，用来收集主机信息，在主机上执行任务。Master 主要负责做资源调度和任务调度，资源调度对性能要求比较高，任务调度对可扩展性要求较高，总体趋势是讲这两类职责解耦，分别由不同的组件来完成。

发表在设计 | 留下评论

分布式系统的Raft算法

发表于2019年4月19日由javahao123

分布式系统的Raft算法

　　来自：Jdon

过去, Paxos一直是分布式协议的标准，但是Paxos难于理解，更难以实现，Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。

　　来自Stanford的新的分布式协议研究称为Raft，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。

　　在了解Raft之前，我们先了解Consensus一致性这个概念，它是指多个服务器在状态达成一致，但是在一个分布式系统中，因为各种意外可能，有的服务器可能会崩溃或变得不可靠，它就不能和其他服务器达成一致状态。这样就需要一种Consensus协议，一致性协议是为了确保容错性，也就是即使系统中有一两个服务器当机，也不会影响其处理过程。

　　为了以容错方式达成一致，我们不可能要求所有服务器100%都达成一致状态，只要超过半数的大多数服务器达成一致就可以了，假设有N台服务器，N/2 +1 就超过半数，代表大多数了。

　　Paxos和Raft都是为了实现Consensus一致性这个目标，这个过程如同选举一样，参选者需要说服大多数选民(服务器)投票给他，一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同。

　　在Raft中，任何时候一个服务器可以扮演下面角色之一：

Leader: 处理所有客户端交互，日志复制等，一般一次只有一个Leader.
Follower: 类似选民，完全被动
Candidate候选人: 类似Proposer律师，可以被选为一个新的领导人。

Raft阶段分为两个，首先是选举过程，然后在选举出来的领导人带领进行正常操作，比如日志复制等。下面用图示展示这个过程：

1. 任何一个服务器都可以成为一个候选者Candidate，它向其他服务器Follower发出要求选举自己的请求：

2. 其他服务器同意了，发出OK。

注意如果在这个过程中，有一个Follower当机，没有收到请求选举的要求，因此候选者可以自己选自己，只要达到N/2 + 1 的大多数票，候选人还是可以成为Leader的。

3. 这样这个候选者就成为了Leader领导人，它可以向选民也就是Follower们发出指令，比如进行日志复制。

4. 以后通过心跳进行日志复制的通知

5. 如果一旦这个Leader当机崩溃了，那么Follower中有一个成为候选者，发出邀票选举。

6. Follower同意后，其成为Leader，继续承担日志复制等指导工作：

值得注意的是，整个选举过程是有一个时间限制的，如下图：

　　Splite Vote是因为如果同时有两个候选人向大家邀票，这时通过类似加时赛来解决，两个候选者在一段timeout比如300ms互相不服气的等待以后，因为双方得到的票数是一样的，一半对一半，那么在300ms以后，再由这两个候选者发出邀票，这时同时的概率大大降低，那么首先发出邀票的的候选者得到了大多数同意，成为领导者Leader，而另外一个候选者后来发出邀票时，那些Follower选民已经投票给第一个候选者，不能再投票给它，它就成为落选者了，最后这个落选者也成为普通Follower一员了。

日志复制

　　下面以日志复制为例子说明Raft算法，假设Leader领导人已经选出，这时客户端发出增加一个日志的要求，比如日志是”sally”：

2. Leader要求Followe遵从他的指令，都将这个新的日志内容追加到他们各自日志中：

3.大多数follower服务器将日志写入磁盘文件后，确认追加成功，发出Commited Ok:

4. 在下一个心跳heartbeat中，Leader会通知所有Follwer更新commited 项目。

对于每个新的日志记录，重复上述过程。

如果在这一过程中，发生了网络分区或者网络通信故障，使得Leader不能访问大多数Follwers了，那么Leader只能正常更新它能访问的那些Follower服务器，而大多数的服务器Follower因为没有了Leader，他们重新选举一个候选者作为Leader，然后这个Leader作为代表于外界打交道，如果外界要求其添加新的日志，这个新的Leader就按上述步骤通知大多数Followers，如果这时网络故障修复了，那么原先的Leader就变成Follower，在失联阶段这个老Leader的任何更新都不能算commit，都回滚，接受新的Leader的新的更新。

总结：目前几乎所有语言都已经有支持Raft算法的库包，具体可参考：raftconsensus.github.io

英文动画演示Raft

CAP定理

分布式Paxos算法

ZooKeeper在服务发现中应用

分布式事务

发表在设计 | 留下评论

如何浅显易懂地解说 Paxos 的算法？

发表于2019年4月18日由javahao123

来自：知乎

看了几篇前面的答案，感觉都是为了逻辑的验密性，进行了大篇幅的推理，这样确实非常严谨，但是理解起来就要废一番功夫了。我就不用一步一步的推理来描述了，这样虽然丧失一些严密性，但是会尽量提高可读性，争取让每个人都能理解这个算法的要点。

Paxos算法背景介绍：
Paxos算法是分布式技术大师Lamport提出的，主要目的是通过这个算法，让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说，就是在一个选举过程中，让不同的选民最终做出一致的决定。
Lamport为了讲述这个算法，假想了一个叫做Paxos的希腊城邦进行选举的情景，这个算法也是因此而得名。在他的假想中，这个城邦要采用民主提议和投票的方式选出一个最终的决议，但由于城邦的居民没有人愿意把全部时间和精力放在这种事情上，所以他们只能不定时的来参加提议，不定时来了解提议、投票进展，不定时的表达自己的投票意见。Paxos算法的目标就是让他们按照少数服从多数的方式，最终达成一致意见。

Paxos算法的具体情况：

1、在整个提议和投票过程中，主要的角色就是“提议者”（向“接受者”提出提议）和“接受者”（收到“提议者”的提议后，向“提议者”表达自己的意见）。

2、整个算法的大致过程为：
第一阶段：因为存在多个“提议者”，如果都提意见，那么“接受者”接受谁的不接受谁的？太混乱了。所以，要先明确哪个“提议者”是意见领袖有权提出提议，未来，“接受者”们就主要处理这个“提议者”的提议了（这样，也可以在提出提议时就尽量让意见统一，谋求尽早形成多数派）。
第二阶段：由上阶段选出的意见领袖提出提议，“接受者”反馈意见。如果多数“接受者”接受了一个提议，那么提议就通过了。

3、必须要了解的其他相关背景：
1）怎么明确意见领袖呢？通过编号。每个“提议者”在第一阶段先报个号，谁的号大，谁就是意见领袖。如果不好理解，可以想象为贿选。每个提议者先拿着钞票贿赂一圈“接受者”，谁给的钱多，第二阶段“接受者”就听谁的。（注：这里和下文提到的“意见领袖”，并不是一个新的角色，而是代表在那一轮贿赂成功的“提议者”。所以，请把意见领袖理解为贿赂中胜出的“提议者”即可）
2）有个跟选举常识不一样的地方，就是每个“提议者”不会执着于让自己的提议通过，而是每个“提议者”会执着于让提议尽快达成一致意见。所以，为了这个目标，如果“提议者”在贿选的时候，发现“接受者”已经接受过前面意见领袖的提议了，即便“提议者”贿选成功，也会默默的把自己的提议改为前面意见领袖的提议。所以一旦贿赂成功，胜出的“提议者”再提出提议，提议内容也是前面意见领袖的提议（这样，在谋求尽早形成多数派的路上，又前进了一步）。
3）钱的多少很重要，如果钱少了，无论在第一还是第二阶段“接受者”都不会尿你，直接拒绝。
4）上面2）中讲到，如果“提议者”在贿选时，发现前面已经有意见领袖的提议，那就将自己的提议默默改成前面意见领袖的提议。这里有一种情况，如果你是“提议者”，在贿赂的时候，“接受者1”跟你说“他见过的意见领袖的提议是方案1”，而“接受者2”跟你说“他见过的意见领袖提议是方案2”，你该怎么办？这时的原则也很简单，还是：钱的多少很重要！你判断一下是“接受者1”见过的意见领袖有钱，还是“接受者2”见过的意见领袖有钱？如何判断呢？因为“接受者”在被“提议者”贿赂的时候，自己会记下贿赂的金额。所以当你贿赂“接受者”时，一旦你给的贿赂多而胜出，“接受者”会告诉你两件事情：a.前任意见领袖的提议内容（如果有的话），b.前任意见领袖当时贿赂了多少钱。这样，再面对刚才的情景时，你只需要判断一下“接受者1”和“接受者2”告诉你的信息中，哪个意见领袖当时给的钱多，那你就默默的把自己的提议，改成那个意见领袖的提议。
5）最后这一部分最有意思，但描述起来有点绕，如果不能一下子就理解可以先看后面的例子。在整个选举过程中，每个人谁先来谁后到，“接受者”什么时间能够接到“提议者”的信息，是完全不可控的。所以很可能一个意见领袖已经产生了，但是由于这个意见领袖的第二阶段刚刚开始，绝大部分“接受者”还没有收到这个意见领袖的提议。结果，这时突然冲进来了一个新的土豪“提议者”，那么这个土豪“提议者”也是有机会让自己的提议胜出的！这时就形成了一种博弈：a.上一个意见领袖要赶在土豪“提议者”贿赂到“接受者”前，赶到“接受者”面前让他接受自己的提议，否则会因为自己的之前贿赂的钱比土豪少而被拒绝。b.土豪“提议者”要赶在上一个意见领袖将提议传达给“接受者”前，贿赂到“接受者”，否则土豪“提议者”即便贿赂成功，也要默默的将自己的提议改为前任意见领袖的提议。这整个博弈的过程，最终就看这两个“提议者”谁的进展快了。但最终一定会有一个意见领袖，先得到多数“接受者”的认可，那他的提议就胜出了。

4、总结
好啦，故事到这里基本讲述完了，咱们来总结一下，其实Paxos算法就下面这么几个原则：
1）Paxos算法包括两个阶段：第一个阶段主要是贿选，还没有提出提议；第二个阶段主要根据第一阶段的结果，明确接受谁的提议，并明确提议的内容是什么（这个提议可能是贿选胜出“提议者”自己的提议，也可能是前任意见领袖的提议，具体是哪个提议，见下面第3点原则）。
2）编号（贿赂金额）很重要，无论在哪个阶段，编号（贿赂金额）小的，都会被鄙视（被拒绝）。
3）在第一阶段中，一旦“接受者”已经接受了之前意见领袖的提议，那后面再来找这个“接受者”的“提议者”，即便在贿赂中胜出，也要被洗脑，默默将自己的提议改为前任意见领袖的提议，然后他会在第二阶段提出该提议（也就是之前意见领袖的提议，以力争让大家的意见趋同）。如果“接受者”之前没有接受过任何提议，那贿选胜出的“提议者”就可以提出自己的提议了。

5、举例

最后举个例子，加深一下印象：

有两个“提议者”和三个“接受者”。

1）首先“提议者1”贿赂了3个“接受者”

2）3个“接受者”记录下贿赂金额，因为目前只有一个“提议者”出价，因此$1就是最高的了，所以“接受者”们返回贿赂成功。此外，因为没有任何先前的意见领袖提出的提议，因此“接受者”们告诉“提议者1”没有之前接受过的提议（自然也就没有上一个意见领袖的贿赂金额了）。

3）“提议者1”向“接受者1”提出了自己的提议：1号提议，并告知自己之前已贿赂$1。

4）“接受者1”检查了一下，目前记录的贿赂金额就是$1，于是接受了这一提议，并把1号提议记录在案。

5）在“提议者1”向“接受者2”“接受者3”发起提议前，土豪“提议者2”出现，他开始用$2贿赂“接受者1”与“接受者2”。

6）“接受者1”与“接受者2”立刻被收买，将贿赂金额改为$2。但是，不同的是：“接受者1”告诉“提议者2”,之前我已经接受过1号提议了，同时1号提议的“提议者”贿赂过$1；而，“接受者2”告诉“提议者2”，之前没有接受过其他意见领袖的提议，也没有上一个意见领袖的贿赂金额。

7）这时，“提议者1”回过神来了，他向“接受者2”和“接受者3”发起1号提议，并带着信息“我前期已经贿赂过$1”。

8）“接受者2”“接受者3”开始答复：“接受者2”检查了一下自己记录的贿赂金额，然后表示，已经有人出价到$2了，而你之前只出到$1，不接受你的提议，再见。但“接受者3”检查了一下自己记录的贿赂金额，目前记录的贿赂金额就是$1，于是接受了这一提议，并把1号提议记录在案。

9）到这里，“提议者1”已经得到两个接受者的赞同，已经得到了多数“接受者”的赞同。于是“提议者1”确定1号提议最终通过。

10）下面，回到“提议者2”。刚才说到，“提议者2”贿赂了“接受者1”和“接受者2”，被“接受者1”告知：“之前已经接受过1号提议了，同时1号提议的‘提议者’贿赂过$1”，并被“接受者2”告知：“之前没有接到过其他意见领袖的提议，也没有其他意见领袖的贿赂金额”。这时“提议者2”，拿到信息后，判断一下，目前贿赂过最高金额（即$1）的提议就是1号提议了，所以“提议者2”默默的把自己的提议改为与1号提议一致，然后开始向“接受者1”“接受者2”发起提议（提议内容仍然是1号提议），并带着信息：之前自己已贿赂过$2。

11）这时“接受者1”“接受者2”收到“提议者2”的提议后，照例先比对一下贿赂金额，比对发现“提议者2”之前已贿赂$2，并且自己记录的贿赂金额也是$2，所以接受他的提议，也就是都接受1号提议。

12）于是，“提议者2”也拿到了多数派的意见，最终通过的也是1号提议。

这里再多说一句：

回到上面的第5）步，如果“提议者2”第一次先去贿赂“接受者2”“接受者3”会发生什么？那很可能1号提议就不会成为最终选出的提议。因为当“提议者2”先贿赂到了“接受者2”“接受者3”，那等“提议者1”带着议题再去找这两位的时候，就会因为之前贿赂的钱少（$1<$2）而被拒绝。所以，这也就是刚才讲到可能存在博弈的地方：a.“提议者1”要赶在“提议者2”贿赂到“接受者2”“接受者3”之前，让“接受者2”“接受者3”接受自己的意见，否则“提议者1”会因为钱少而被拒绝；b.“提议者2”要赶在“提议者1”之前贿赂到“接受者”，否则“提议者2”即便贿赂成功，也要默默的将自己的提议改为“提议者1”的提议。但你往后推演会发现，无论如何，总会有一个“提议者”的提议获得多数票而胜出。

以上，只是把大致的Paxos算法的思路介绍了一下，因为情景实在太复杂，比如：“提议者”、“接受者”如果是4个、5个……，比如：“提议者”与“接受者”之间的交互谁先谁后，等等各类情况。但是，其实都是能够严谨的推导出最后能够选出一个多数派的，不过篇幅就会太长了。大家有兴趣可以按照上面的思路，自己再模拟模拟“提议者”“接受者”数量或多或少，交互或先或后的各种情况，结果肯定是最终唯一一个提议会获得多数票而胜出。

回想当时自己看Paxos算法时，走过很多的弯路，花了很长时间，这篇文章也是结合自己看Paxos算法时的一些心得所写，希望对初学者能有些启发。

———————————————-

之前的回答本来就觉得一些细节处并不严谨，现在回看=/=。我觉得严谨是一个讨论技术的必要条件，觉得现在也有能力写的严谨，于是想把回答改的尽量严谨，最后发现不如重写，顺便补充了我想补充的内容，结果就是更长=.=。Paxos是个精巧，又强大的协议，仅从过程的复杂度来说，确实如作者本人一再说的那样是个“简单的协议”，但是可以从非常多的角度来理解它为何正确，而原本的流程也并不适合直接工程化，这也是大概为什么工程上它存在如此多的变体。希望这个回答的让人更快的感受paxos的魅力，建立一个初步印象的同时不给人以误导。最后依然推荐larmport自己写的和paxos相关的三篇论文：<< The Part-Time Parliament>>、<<Paxos made simple>>、<<Fast Paxos>>前面关于Paxos的论述。
2016/12/28

上周和一个有真正paxos工程经验的人讨论一下paxos，paxos现在大多是应用于replication的一致性，用来实现一个多节点一致的日志，和他的讨论让我觉得要想真正的精确掌握paxos和它对应的强一致性领域，也许只有真正的在工程中实现过才行。这个回答只能当做是想要了解原理的入门吧，甚至可能有些微妙的地方还会产生误导。它介绍了paxos面向的问题，以及为何它的流程要这么设计，但还是希望对有兴趣阅读这个问题的有所帮助。
2016 10/30

现在看开头这段话是在是觉得有点羞耻，遂改之。我了解paxos是从找工作开始，比较详细的了解则是在毕设，自己动手了写了个类似Zookeeper的系统，paxos本身并不复杂，在<<paxos made simple>> Lamport用两段话就描述清楚了它的流程，他老人家也说paxos其实是个简单的算法。但是是我在工程领域见过最为精妙的算法。我想论述Paxos为什么难以理解会比描述Paxos的流程长的多的多。我最初学习Paxos是从《从Paxos到Zookeeper:分布式一致性原理与实践》，现在看来并不是个很好选择，作者讲解的方式是直接翻译论文，论述ZAB和paxos关系的部分我也觉得不是很严谨。如果真心觉得Paxos的原文不知所云，也不知道能拿来干嘛，可以从阅读Raft的论文开始，如果真的有兴趣，强推Raft作者Diego Ongaro那篇300页的博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》，不只是讲解了Raft协议，而且系统的论述Paxos类似的一致性协议，不仅从原理，也从工程角度出发，涉及方方面面，在写毕设中了就是写不动就翻翻的良作。我个人觉得阅读任何号称浅显易懂的解说Paxos算法的描述（比如下文=/=），最多只是让你更好的入门，要更深的理解Paxos以及所有等同于它的一致性协议，ZAB,Raft,ViewStamp，直接阅读相关论文，理解证明，理解它们哪里不同，为何本质上相同，与人探讨，在工程上自己实现，或者阅读开源实现的源代码才是最好的方式。分布式一致性是个有趣的领域，而Paxos和类似的协议对这个问题的重要性不喻，在过去的十年，Paxos几乎等价于分布式一致性。
2016 6/20

之前的答案最大的不严谨之处在于两个事件“先后”这种时序关系的处理上。paxos是个分布式一致性协议，它的事件需要多个节点共同参与，一个事件完成是指多个节点上均完成了自身负责的单机子事件(就让我门把这样的事件称为”分布式事件”)，这样的分布式事件可以看作是多个单机子事件的复合，但是即不能从两个分布式事件的先后推导出某个节点上它们的单机子事件的先后，也不能根据某个节点上两个单机子事件的先后断言它们对应的分布式事件的先后。举一个简单的例子，两个节点P1，P2;分布式事件a1设置每节点的本地变量v=1,分布式式事件a2设置每个节点本地变量v=2，如果我们称a1先于a2完成，那么对于节点P1而言，v=1发生在v=2之前还是之后都有可能;反之如果P1上v=1发生在v=2之前，a1和a2哪个县完成也都有可能。

原来的回答有些地方论述分布式事件a1在a2之后(先)时，默认了单节点上，a1会比a2先达成状态，或者反之。

实际上为了论证paxos的正确性，并不需要借助于分布式事件的时序(起码无用太在意物理时序），对于paxos流程中的分布式事件，例如提案被通过，值被决定，让我们忘记它们之间物理时间上的先后关系吧。

下面就开始假装推导出paxos，作为一种理解协议的流程和协议如何保证正确性的方式。这样的推导的过程远比我想象的冗长；相比之下，论文中Lamport自己推导出Paxos的过程简洁、巧妙、漂亮，但是更抽象。在末尾用自己的语言描述了这种方式，作为补充。补充的版本基本思路来自<<Paxos made simple>>，和原文略有不同；总共不到1500字，却既说明了Paxos是如何得到的，又严谨的论证了Paxos的正确性。

首先我们简单介绍paxos所保证的一致性的具体含义；达成一致的条件(何时达成一致）；基于的一个基本的数学原理；以及它需要满足的假设。

什么是一致性?实际上这个词在不同地方语义并不那么一致，Paxos面向的是一个理论的一致问题，这个问题的通俗描述是：

有一个变量v，分布在N个进程中，每个进程都尝试修改自身v的值，它们的企图可能各不相同，例如进程A尝试另v=a,进程B尝试另v=b，但最终所有的进程会对v就某个值达成一致,即上述例子中如果v=a是v达成一致时的值，那么B上，最终v也会为a。需要注意的是某个时刻达成一致并不等价于该时刻所有进程的本地的v值都相同，有一个原因是进程可能挂掉，你不能要求挂掉的进程任何事；更像是最终所有存活的进程本地v的值都会相同。

这个一致性需要满足三个要求：

1.v达成一致时的值是由某个进程提出的。这是为了防止像这样的作弊方式：无论如何，最终都令每个进程的v为同一个预先设置好的值，例如都令v=2，那么这样的一致也太容易了，也没有任何实际意义。
2.一旦v就某个值达成了一致，那么v不能对另一个值再次达成一致。这个要求称为安全性。
3.一致总是能够达成，即v总会被决定为某个值。这是因为不想无休止的等待，这个要求也称为活性。

Paxos中变量v达成一致的条件： N个进程中大多数（超过一半）进程都认为v是同一个值，例如c，那么我们称v被决定为c。这样即使少数进程挂掉了，也不会使得一致无法达成。

Paxos保证的一致性如下：不存在这样的情形，某个时刻v被决定为c，而另一个时刻v又决定为另一个值d。由这个定义我们也看到，当v的值被决定后，Paxos保证了它就像是个单机的不可变变量，不再更改。也因此，对于一个客户端可以多次改写值的可读写变量在不同的节点上的一致性问题，Paxos并不能直接解决，它需要和状态机复制结合。

Paxos基于的数学原理：我们称大多数进程组成的集合为法定集合，两个法定集合必然存在非空交集，即至少有一个公共进程，称为法定集合性质。例如A,B,C,D,F进程组成的全集，法定集合Q1包括进程A,B,C，Q2包括进程B,C,D，那么Q1和Q2的交集必然不在空，C就是Q1，Q2的公共进程。如果要说Paxos最根本的原理是什么，那么就是这个简单性质。同时，可以注意到，这个性质和达成一致的定义相呼应。

Paxos中进程之间是平等的，即不存在一个特殊的进程，这是由于如果协议依赖于某个特殊的进程，那么这个进程挂掉势必会影响协议;而对于分布式环境，无法保证单个进程必然必活，能够容忍一定数量的进程挂掉，是分布式协议的必然要求。这是推导过程所要遵循的一个原则，就称为平等性原则好了。

消息是进程间通信的唯一手段，对于分布式环境来说，这是显然的。

Paxos要求满足的前置假设只有一个：消息内容不会被篡改；更正式的说是无拜占庭将军问题。

假装的推导总是先从一些具体的场景开始，既然Paxos的假设仅仅只是消息不会被篡改,保证了这点任意场景下都能保证一致性，那么对于举例的场景它必然是能够保证一致性的；因此不妨先使得协议流程能在当前场景下能保证一致性，然后再举出另一个场景，当前的协议流程无法再该场景下满足一致性，接着再丰富协议流程，满足该场景，如此往复，最终得到完整的paxos协议，最后再不失一般性的论证协议对任意场景都能保证一致性。

进程的平等性假设会带来如下的问题，考虑如下的场景1：三个进程的场景P1,P2P3（n个进程的场景类似），P1尝试令v的值被决定为a,P2尝试令v被决定为b。假设它们都先改写了自身的v值，然后发送消息尝试改修P3的v值。显然如果P3收到两个消息后都满足了它们的企图，那么v就会两次被决定为不同的值，这破坏了之前的定义。因此P3必须得拒绝掉其中一个进程的请求，如何拒绝也是我们最先考虑的问题。一个最简单的拒绝策略是先来后到，P3只会接受收到的第一个消息，拒绝之后的消息，即只会改写v一次。按照这个策略，如果P1发送的消息首先到达P3，那么P3接受该消息令v=a,拒绝掉后到的来自P2的消息。但是这个策略会引入一个另外的问题；在场景1的基础上考虑这样的场景1’，P3也尝试决定v的值，P3尝试令v被决定为c，那么P1，P2，P3都尝试修改v的值，首先P1令v=a,P2令v=b,P3令v=c(相当于自己给自己发消息），按照之前的策略，每个进程只会改写v的值一次，那么将永远不会出现两个进程的v值相等的情况，即v永远无法被决定。更正式的说，这样的协议不满足活性，活性要求协议总能达成一致。由此我们也得到第一个结论:进程必须能够多次改写v的值。同时我们也要意识到：当进程收到第一个消息时，进程是没有任何理由拒绝这个消息的请求的。

拒绝策略总是需要有一个依据，之前我们的依据是消息到达的先后，只接受第一个到达的消息，但这导致不满足活性。现在我们需要另一个拒绝策略，也就是需要另一个依据，这个依据至少能够区分两个消息。为此我们引入一个ID来描述这个消息，这样就可以根据ID的大小来作为拒绝或接受的依据；选择ID更大的消息接受和选择ID更小的消息接受是两种完全对称的策略，不妨选择前者。这个策略不会导致明显的活性问题，ID更大的消息总是能被接受，一个节点可以多次更改v的值。例如在场景1’中，只要P1的消息ID比P3发送给自己的消息ID更大，P3就会接受P1的消息，令v=a，从而令v的值被决定为a。再来考虑最初的场景1，不妨假设P1的消息ID大于P2的消息ID，根据P3收到消息的先后可以分为两种情况：

1. P3先收到P1的消息，记做场景1-2。由于P1的消息是P3收到的第一个消息，P3接受该请求，令v=a；同时为了能对之后收到的消息作出是否接受的判断，P3需要记录该消息的ID作为判断的依据。之后P3又收到P2的消息，该消息的ID小于P3记录的ID(即P1的消息ID)，因此P3拒绝该消息，这样我们的目的就达到。

2. P3先收到P2的消息，记作场景1-3。同样P3接受该消息，令v=b,记录该消息的ID。之后P3收到P1的消息，由于P1的消息ID大于P3记录的ID，因此P3无法拒绝该消息，之前的问题依旧存在。

尽管对于场景1-3，目前的策略依旧无法保证一致性，但是起码我们缩小协议不适用的范围。先总结下我们目前的策略，并定义一些称谓以方便后面的论述。我们称呼进程P发送的尝试修改另一个进程中变量v的值的消息称之为提案，记作Proposal；提案的ID记作proposal_id；提案中会附带一个值，如果一个进程接受一个提案，则修改自身的v值为该提案中的值。如果一个提案被大多数进程所接受，那么称提案被通过，此时显然v被决定为提案中的值。进程P记录的接受的提案ID记做a_proposal_id。

之前我们尚未清晰定义a_proposal_id，实际上我们也就并未清晰的定义我们的拒绝策略，当P收到一个提案Proposal-i时，可能已经收到过多个提案，Proposal-i.proposal_id该和其中哪个提案的proposal_id比较，我们并未定义。我们定义为其中的最大者，这样实际上进程P只需维护一个a_proposal_id即可，当收到一个Proposal时，更新a_proposal_id = Max(Proposal.proposal_id，a_proposal_id）。同时在之前的描述中我们应当注意到实际上一个进程存在两个功能：

1. 进程主动尝试令v的值被决定为某个值，向进程集合广播提案。

2. 进程被动收到来自其它进程的提案，判断是否要接受它。

因此可以把一个进程分为两个角色，称负责功能1的角色是提议者，记作Proposer，负责功能2的角色是接受者，记作Acceptor。由于两者完全没有耦合，所以并不一定需要在同个进程，但是为了方面描述，我们假定一个进程同时担任两种角色，而实际的工程实现也往往如此。

接着我们尝试解决场景1-3,这看起来很难。P3作为接受者，收到P2的提案之前未收到任何消息，只能接受该提案，而由于P1的提案proposal_id大于P2的提案，我们的拒绝策略也无法让P3拒绝P2。我们先不急着推导具体可行的策略，先考虑下解决1-3场景可能的角度，有如下三种角度可以入手：

1. P3能够拒绝掉P2的提案。

2. P3能够拒绝掉P1的提案。

3. 限制P1提出的提案中的值，如果P1的提案中的值与P2的提案一致，那么接受P1也不会破坏一致性。

接着我们分析三个角度的可行性：

角度1需要P3有做出拒绝的依据，由于消息是进程间通信唯一手段，这要求P3在收到P2的提案之前必须先收到过其它消息。对于场景1-3，只有P1，P2是主动发送消息的进程，P2当然不可能额外还发送一个消息试图令P3拒绝自己随后的提案。那么唯一的可能是P1在正式发送提案前，还发送了一个消息给P3，这个消息先于P2的提案到达，给了P3拒绝P2提案的理由。如果沿用目前的拒绝策略，那么P1只需先发送随后提案的proposal_id给P3，P3更新a_proposal_id 为该消息附带的proposal_id，这样a_proposal_id将大于P2的提案的proposal_id，而导致P2的提案被拒绝，似乎这是一个可行的角度。

对于角度2，我们目前的策略无法做到这一点，因此除了proposal_id外，我们还得给提案附加上额外的信息作为另外的拒绝策略的依据。提案由进程提出，也许我们可以附加进程的信息，但是就算P3得知P1的提案由P1提出，P3又凭什么歧视P1，这违反进程的平等性假设。似乎这个角度不是一个好角度。

最后我们分析一下角度3，角度3提供了与1,2截然不同的思路，它不再是考虑如何拒绝，而把注意力放在如何对提案的值做出恰当的限制上。对于场景1-3而言，从这个角度，由于P3无法拒绝P1和P2的提案中的任何一个，因此P1的提案的值就必须与P2的提案一致；这也意味着了P1在正式提出提案前，需要有途径能获悉P2的提案的值。如我们上面一直强调的，消息是唯一的通信手段，P1必须收到来自其它节点消息才有可能得知P2提出的提案的值。P1可以被动的等待收到消息，也可以主动的去询问其它节点等待回复。后者显然是更好的策略，没有收到想要的消息就一直等待未免也太消极了，这种等待也可能一直持续下去从而导致活性问题。

经过上面的分析，我们暂时排除了从角度2入手（实际上后面也不会再考虑，因为从1,3入手已经足以解决问题）。下面将沿着角度1,3进行更深入的分析，我们先尝试从角度1出发，毕竟考虑如何拒绝已经有了经验。先来总结下我们在分析角度1时引入的额外的流程:

进程P在发送提案前，先广播一轮消息，消息附带着接下来要发送的提案的proposal_id。由于该消息和接下来发送的提案相关，且在提案被提出之前发送，不妨称这个消息为预提案，记作PreProposal，预提案中附带着接下来的提案的proposal_id。当作为接受者的进程Pj收到预提案后，更新Pj. a_proposal_id。还记得我们之前的拒绝策略中a_proposal_id的更新策略嘛：a_proposal_id = max(proposal_id,a_proposal_id)，a_proposal_id是递增的。因此如果预提案的proposal_id小于Pj.a_proposal_id，Pj完全可以忽略这个预提案，因为这代表了该预提案对应的提案的proposal_id小于Pj.a_proposal_id，必然会被拒绝。我们沿用之前拒绝策略中a_proposal_id的更新策略。这样当收到预提案或者提案后，a_proposal_id的值均更新为 max(a_proposal_id,proposal_id)。

接着我们来看看引入了预提案后，能否真正解决场景1-3。根据P1和P2的预提案到达P3的先后也存在两种场景：

1.场景1-3-1：P1的预提案先到达，P3更新a_proposal_id 为该提案的proposal_id，这导致随后到达的P2的提案的proposal_id小于a_proposal_id，被拒绝。满足一致性

2.场景1-3-2：P2的提案先到达，P3接受P2的提案，此时和原始的场景1-3存在同样的问题。归根结底，预提案阶段能否使得P3拒绝该拒绝的，也依赖消息到达的顺序，和提案阶段的拒绝策略存在相同的问题，但至少又缩小了不能保证安全性的场景范围。

幸好我们还有角度3可以着手考虑，所以仍有希望完全解决场景1-3。在深入角度3之前，先总结下协议目前为止的流程，现在协议的流程已经分为了两个阶段：预提案阶段和提案阶段，两种消息：预提案 和提案，两种角色：接受者 和 提议者，流程如下：

阶段一 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)

阶段二 提议者Proposer：向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id 接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

为了更形象，之前的讨论是基于三个进程的场景,实际上对于N进程的场景也是一样的。N个进程时，与之前场景1对应的场景是：

N个进程，存在两个进程Pi,Pj，Pi尝试另v被决定为a,Pj尝试另v被决定为b，Pi提出的预提案记作PreProposal-i，提案记作Proposal-i；Pj的预提案PreProsal-j，提案Proposal-j。

之拒绝策略的讨论都是基于一个关键的进程P3，只要P3最终能拒绝Proposal-i和Proposal-j中的一个，两个提案就不会都被通过，那么一致性就不会被破坏。Pi的提案被通过代表了存在一个法定集合Q-i，Q-i中的进程都接受了Proposal-i，Pj同理，存在一个Q-j，Q-j中的进程都接受了Proposal-j。由于法定集合的性质，两个多数集Q-i和Q-j中必然存在一个公共进程Pk。Pk即相当于场景1中的P3，只要Pk能够拒绝Proposal-i和Proposal-j中的一个，协议依旧是安全的。为了不失一般性，下面我们都以N个进程的场景作为讨论的基础，称为场景2，由于场景1和场景2可以一一对应，所以接下来顺着限制提案的值的角度，我们直接针对场景2-3-2，之前的场景和场景1一样，我们的拒绝策略已经足以应付。v的值被决定代表有一个提案，它被法定数目的集合接受，我们称这为提案被通过。

首先我们看下场景2-3-2，Pi对应场景1-3-2中的P1，Pj对应P2，Pk对应P3。Pj的提案Proposal-j最终会被法定集合Q-j接受，即v的值被决定为b，且Proposal-i.proposal-id > Proposal-j.proposal_id。我们需要限制Pi的提案的值，不能让Pi自由的给Proposal-i中的v赋值。在2-3-2中，由于拒绝策略失效，所以只能令Proposal-i.v = Proposal-j.v=b。要做到这一点，正如前面的分析所言，Pi需要先主动询问进程集合，来得知Proposal-j.v =b这一事实。显然Pi是没有先验信息来得知Proposal-j由哪个进程提出，也不知道Q-i和Q-j的公共节点Pk是谁，因此Pi只能广播它的查询。由于我们需要允许少数进程失败，Pi可能只能得到大多数进程的回复，而这之中可能不包括Pj。我们称这些回复Pi的查询的进程的集合为Q-i-2,为了描述更简单，无妨假设Q-i-2=Q-i。尽管Pi的查询可能得不到Pj的回复，好在作为将会被通过的提案，Proposal-j将会被Q-j内所有进程接受，因此如果进程作为接受者在接受提案时，顺便记录该提案，那么Q-j内所有进程都将得知Proposal-j.v=b。由于Pk属于Q-i和Q-j的交集，所以Pk即收到了Pi的查询，又接受了提案Proposal-j。之前我们已经引入了预提案阶段，显然我们可以为预提案附带上查询的意图，即Pk作为接受者收到Pi的预提案后，会回复它记录的接受过的提案。有一个问题是Pk此时是否已经记录了Proposal-j呢?很巧的是在场景2-3-2中，Pj的提案Proposal-j是先于Pi的预提案PreProposal-i先到达，所以Pk已经记录了Proposal-j.v = b，Pj收到的来自Pk的回复中包含了提案Proposal-j，而2-3-2之外的场景，拒绝策略已经足以应付。这里依旧还有两个问题，先讨论第一个：

实际上除了Pi和Pj外可能还会有多个进程发起预提案和提案，所以收到 PreProposal-i时Pk可能已经接受过多个提案，并非只有Proposal-j，那么Pk应该回复PreProposal-i其中哪个提案，或者都回复？Pk并不知道Proposal-j会被通过，它只知道自己接受了该提案。都回复是个效率很低但是稳妥，可以保证Pk不会遗漏Proposal-j，Pk已经回复了它所能知道的全部，我们也无法要求更多。需要注意到的是进程是平等的，所以Q-i中所有进程都和Pk一样回复了它接受过的所有提案。当Pi收到所有来自Q-i的回复时，随之而来的是第二个问题：

Pi收到了多个Proposal作为一个Acceptor组成的法定集合Q-i对PreProposal-i的回复，记这些Proposal组成的集合记坐K-i，那么它应当选择K-i中哪个一个提案的值作为它接下来的提案Proposal-i的v值？记最终选择的这个提案为Proposal-m。

在场景2-3-2中，我们第一直觉是希望选择的Proposal-m 即是 Proposal-j，但是实际上，我们只要保证Proposal-m .v = Proposal-j.v即可。从另一个角度，K-i中很可能存在这样的提案Proposal-f,Proposal-f.v!=Proposal-j.v，我们要做的是避免选择到这类提案。我们可以根据一些依据瞎选碰碰运气，但是这并明智。我们不妨假设存在一个策略CL，CL满足需求，使得选择出的提案Proposal-m满足Proposal-m.v= Proposal-j.v。然后让我们来分析一下此时Proposal-f有什么特征。

Proposal-f能够被提出，代表存在一个多数集合Q-f，Q-f中每个进程都接受了PreProposal-f，同时假设是进程P-f提出了PreProposal-f和Proposal-f。Q-f和Q-j必然存在一个公共节点，记做Ps，Ps即接受了PreProposal-f又接受了Proposal-j。Ps收到PreProposal-f和Proposal-j的顺序只有两种可能：

1.Ps先收到PreProposal-f

2.Ps先收到Proposal-j

PreProposal-f.proposa-id和Proposal-j. proposal_id的大小也只有两种可能，不妨先假设PreProposal-f.proposal_id > Proposal-j.proposal_id。

对于情形1，Ps先收到PreProposal-f，接受它，更新Ps.a_proposal_id = PreProposal-f.proposal_id > Proposal-j.proposal_id，同时之前的a_proposal_id的更新策略又使得Ps.a_proposal_id是递增的，于是导致收到Proposal-j时,Proposal-j.proposal_id小于Ps.a_proposal_id,被拒绝，而这于Ps的定义矛盾。

对于情形2，Ps将把提案Proposal-j回复给PreProposal-f。由于我们假设了策略CL的存在，于是P-f在收到所有Q-f对PreProposal-f的回复后，将令Proposal-f.v=Proposal-j.v，CL就是干这个的。因此由于Proposal-f.v!=Proposal-j.v矛盾。

于是当假设PreProposal-f.proposal_id > Proposal-j.proposal_id 时，情形1,2我们都得出了矛盾，同时两者的proposal_id又不相等(最初的假设），所以必然PreProposal-f.proposal_id < Proposal-j.proposal_id，即Propsoal-f.proposal_id < Proposal-j.proposal_id。

于是我们得到的结论是：如果策略CL存在，提案Proposal-j最终会被通过，任意一个proposal_id更大的预提案PreProposal-i，对于它得到的Q-i的回复K-i中的Proposal-f，只要Proposal-f.v!= Proposal-j.v，那么必然 Proposal-f.proposal_id < Proposal-j.proposal_id。

既然K-i中所有v值不等于Proposal-j.v的提案，proposal_id都比Proposal-j更小，那代表所有proposal_id比Proposal-j更大的提案，v值都等于Proposal-j.v，因此选择K-i中proprosal_id最大的提案，就能保证Proposal-i.v = Proposal-j.v。于是我们得到了策略CL的具体形式。

我们得到了具体可行的策略CL是建立在策略CL存在这一前提之上，因此反过来，对于这个具体的选值策略CL，结合之前我们得到了协议流程，它是否能保证如下的性质CP1，依旧需要进一步的论证：
如果一个提案Proposal-j最终会被通过，那么对于任意的一个提案Proposal-i,如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么Proposal-i.v = Proposal-j.v。

我们先总结下目前得到的协议流程：

阶段一预提案阶段 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id大于a_proposal_id，那么回复该预提案的提议者改接受者接受过的所有提案。

阶段二提案阶段 提议者Proposer：等待直到收到大多数接受者对预提案的回复，从所有回复的提案组合成的集合K中挑选proposal_id最大的提案，以该提案的值作为本次提案的值。如果K是空集，那么可以给提案任意赋值。 向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id 接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

这些流程是为了解决举例的场景而不断丰富的，接着就让我们论证下协议流程是否总是可以确保CP1。

首先假设Proposal-i.v != Proposal-j.v，如果得出矛盾即可证明CP1。在尝试推出矛盾前，我们先做一些定义，以便后续的推导。

记大多数接受者组成的法定集合为Q，K是提议者在提案阶段收到的所有Q回复的提案组成的集合，如果K不为空，记K中proposal_id最大的提案是MaxProposal(K)，本次提案的值即是MaxProposal(K).v；如果K是空集，那么MaxProposal(K).v = null。特别的，对于提案Proposal-i,回复它预提案接受者的集合为Q-i,回复的提案组成的集合为K-i，Proposal-i.v = MaxProposal(K-i)，Proposal-i.v=null代表可以随意赋值。为了描述方便，我们令Proposal-i的proposal_id为i，即Proposal-i代表了proposal_id=i的提案，Proposal-j意味着Proposal-j.proposal_id =j。

论证过程如下：

(1) Proposal-i.v!=Proposal-j.v，即MaxProposal(K-i) .v！= Proposal-j.v，即MaxProposal(K-i)!=Proposal-j

(2) Proposal-j最终会被通过，代表最终会存在一个多数集合Q-j，Q-j中每个接受者都接受了Proposal-j。

(3) 两个多数集必然存在公共成员，故Q-j和Q-i必然存在一个公共的进程Pk，Pk即收到了PreProposal-i又收到了Proposal-j，且都接受了它们；Pk收到消息的先后关系只存在如下两种可能：

1.Pk先收到了PreProposal-i

2.Pk先收到了Proposal-j

(4) 情形1中Pk先收到了PreProposal-i，那么Pk收到Proposal-j时，Pk.a_proposal >= PreProposal-i.proposal_id ＞Proposal-j.proposal_id，Pk会拒绝Proposal-j，与(3)矛盾，因此情况1不可能，Pk必然是先收到Proposal-j。

(5) 情形2中Pk收到PreProposal-i时，已经接受了Proposal-j，因此Pk回复PreProposal-i的提案中包含了Proposal-j，因此K-i中必然包含了Proposal-j。

(6) 由(1)已知MaxProposal(K-i) != Proposal-j，即存在另一个提案Proposal-m = MaxProposal(K-i),而Proposal-j属于K-i,因此Proposal-m.proposal_id > Proposal-j.proposal_id，且Proposal-m.v != Proposal-j.v。

(7)由预提案阶段，接受者回复预提案的条件可知：Proposal-i.proposal_id大于集合K-i中任意一个提案的Proposal-id，故Proposal-i.proposal_id>Proposal-m.proposal_id。

(8) 目前我们已经论证如下一点：

在Proposal-j最终会被通过的前提下，如果存在一个提案Proposal-i.v!=Proposal-j.v，且Proposal-i.proposal_id >Proposal-j.proposal_id,我们一个数学符号来带表示这个情况，记CF(j,i)；那么必然存在一个提案Proposal-m, Proposal-m！=Proposal-j.v,且Proposal-m.proposal_id > Proposal-j.proposal_id，同样的我们可以记做CF(j,m)。并且Proposal-m.proposal_id < Proposal-i.proposal_id，m < i。

即如果CF(i,j)成立，那么必然CF(m,j)成立，且i>m，即 CF(i,j) —> CF(m,j)。这个过程可以继续往下递归，但由于区间[j,i]范围是有限的，因此一定会递归到一个CF(j,e)，此时不可能存在一个提案，它的proposal_id在区间(j,e)内，无法往下递归，这与(8)矛盾。这也就意味着CF(e,j)不成立，而如果CF(i,j)成立，那么CF(e,j)成立,因此CF(i,j)不成立，故假设不成立，即Proposal-i.v 必然等于Proposal-j.v，即证CP1。

通过归约的方式得出矛盾的方式依旧有些抽象，我们可以通过更好的定义假设来更容易得到的矛盾：

我们加强对Proposal-i的约束;先假设存在一个提案的非空集合KD，KD中的任意一个提案Proposal-k,Proposal-k.v!=Proposal-j.v，且Proposal-k.proposal_id > Proposal-j.v;再假设Proposal-i是KD中proposal_id最小的提案；由于KD是非空集合，故Proposal-i必然存在。

我们依旧可以从Proposal-i出发，(1)~(7)与上面相同，同理得到：存在一个提案Proposal-m, Proposal-m！=Proposal-v,且Proposal-m.proposal_id > Proposal-j.proposal_id，且Proposal-m.proposal_id < Proposal-i.proposal_id。

显然Proposal-m满足集合KD对提案的要求，故Proposal-m属于KD，又Proposal-m.proposal_id<Proposal-i.proposal_id，这和Proposal-i是KD中proposal_id最小的提案的定义矛盾。因此不存在这样的非空集合KD，即不存在一个提案Proposal-k,Proposal-k.v!=Proposal-j.v且Proposal-k.proposal_id>Proposal-j.proposal_id，即如果一个提案Proposal-j最终会被通过，对于任意的一个提案Proposal-i,如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么必定Proposal-i.v = Proposal-j.v，即CP1。

CP1约束了proposal_id大于Proposal-j的提案的值，保证了如果一个提案Proposal-j最终会被通过，不会存在另一个proposal-id更大且值不同的提案被通过，因为这些提案的值都和Proposal-j相同。那么对于proposal_id更小的提案呢？我们假设存在一个提案Proposal-o,Proposal-o.proposal_id < Proposal-j.proposal_id，且Proposal-o.v!=Proposal-j.v,Proposal-o最终会被通过，将CP1应用于Proposal-o,则可知Proposal-j不存在，这矛盾，故Proposal-o不存在。故由CP1我们可知：如果一个提案Proposal-j最终会被通过，那么不存在另一个提案，它最终会被通过，且它的值与Proposal-j不同。由此协议必然是安全的。

虽然我们得到了一个安全的一致性协议，基本上它就是Paxos，但是真正的Paxos要比我们假装推导出的协议更简单一点。

回过头来看下我们的阶段1中接受者Acceptor的行为，它要回复所有的它接受过的提案，从实践的角度，不论是在本地保存所有它接受过的提案还是通过网络将它们传输给提议者，开销都太大且不可控。再看下阶段二中，提议者的选值策略，它只是选择了收到的多数集接受者回复的提案中proposal_id最大的那一个，因此接受者实际上只需要回复它接受过的proposal_id最大的提案即可，因为其它提案根本不可能会被选值策略选中。因此最终的协议如下，它就是Paxos:

阶段一预提案阶段： 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id>a_proposal_id，Acceptor回复记录的接受过的proposal_id最大的提案。

阶段二提案阶段：提议者Proposer：等待直到收到大多数接受者对预提案的回复，从所有回复的提案组成的法定数目的提案集合K中挑选proposal_id最大的提案，以该提案的值作为本次提案的值。如果K是空集，那么可以给提案任意赋值。然后把该提案广播给接受者们，提案和预提案共享同一个proposal_id。 接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)，更新记录的提案。

补充部分：

上面的过程从具体的场景开始推导Paxos，虽然直观但是繁琐，如果从抽象的概念和分析入手，那么过程将会相当简洁和漂亮，这也是Lamport的原始论文中的方式。这种方式理解起来更困难的地方在于：

1.没有任何具体的认知下，直接抽象的讨论容易让人摸不着头脑。

2.大神总是在一些地方觉得显然而不加以展开论述，而普通读者如我的内心OS:显然你mei!

但是原文引出Paxos算法的过程实在是简洁、漂亮；而经过上面的轮述，相信有了直观的印象后，再来看抽象的方式也不那么困难，所以补充下。

回顾下定理CP1：

如果一个提案Proposal-j最终会被通过，那么对于任意的一个提案Proposal-i,如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么必定Proposal-i.v = Proposal-j.v。

上面我们已经论证了只要协议能够保证CP1就能够保证一致性。但是CP1依旧过于宽泛，从CP1引出具体的协议流程依然是一头雾水，那么我们是否可以得到一个更加具体的定理CP2，保证CP2即可保证CP1，同时从CP2出发更容易引出协议的具体流程。为了描述方便，我们令Proposal-i的proposal_id为i，即Proposal-i代表了proposal_id=i的提案。

要导出CP2不妨先考虑下如何证明CP1，利用归纳法，只要如能证明如下性质成立，即可证明CP1：
如果proposal_id在区间[j,i）内任意的提案，提案的值均为Proposal-j.v，那么必定Proposal-i.v=v;这个定理记做CP1_2。

现在我们用高中时简单而效果神奇的归纳法，利用CP1_2证明下CP1:

假设propsal_id小于i的提案中最大的提案是Proposal-(i-1)。

1.如果对于[j,i-1)内的任意提案，值均为Proposal-j.v，那么由CP1_2可知Proposal-i.v = Proposal-j.v。

2.由1可知如果对于[j,i-1)内的任意提案，值均为Proposal-j.v，[j,i)内的任意提案，值均为Proposal-j.v

3.假设Proposal-(j+1)是proposal-id大于j的最小提案，由CP1_2可知Proposal-(j+1).v = Proposal-j.v

4.由3,2归纳可知[j, $\infty$ )内任意提案Proposal-i，Proposal-i.v = Proposal-j.v，即CP1

来看下CP1_2，相比CP1，它结论不变，但是多了一个前置条件：proposal_id在区间[j,i）内任意的提案值均为Proposal-j.v；这是一个重大的进步。CP1_2相比CP1看起来容易保证很多，但是它们却是等价的。考虑CP1_2的三个前置条件：

1.i > j
2.提案Proposal-j最终会被通过。因此由提案被通过的定义可知必然存在一个法定集合Q-j，Q-j中任意一个接受者最终都接受了Proposal-j
3.proposal_id在区间[j,i)内的提案的值均为Proposal-j.v

对于任意的一个法定集合Q，考虑Q最终（包括过去和未来的所有时空）会接受的所有proposal_id小于i的提案组成的集合K。根据法定集合性质，Q和Q-j必然存在一个公共的节点，即Q中必然存在一个节点，该节点最终会接受Proposal-j，因此集合K包含Proposal-j。

由K包含Proposal-j可知K中最大的提案proposal_id >= j；由CP1_2的前置条件3和K的定义可知如果K中存在proposal-id大于j的提案，那么该提案的值等于Proposal-j.v，因此K中proposal_id最大的提案的值等于Proposal-j.v。

综上所述由CP1_2的前置条件可知：对于任意的一个法定集合Q，Q最终会接受的proposal_id小于i的提案组成的集合K，K中proposal_id最大的提案的值必定为Proposal-j.v。如果我们能证明该条件下，Proposal-i.v = Proposal-j.v，即可证明CP1_2。将CP1_2的前置条件替换为该条件，我们可以得到一个如下的性质CP2，保证CP2即可保证CP1_2：
对于任意的一个法定集合Q，Q最终会接受的所有proposal_id小于i的提案组成的集合K，如果K中proposal_id最大的提案的值为Proposal-j.v;那么Proposal-i.v = Proposal-j.v。

而引出满足CP2的流程就比较容易了，由于集合K中proposal_id最大的提案的值等于Proposal-j.v，看起来只要令Proposal-i的值为K中proposal-id最大提案的值就可以保证CP2。由于Q是任意一个法定集合，因此获取K似乎在实现上也不难，提出Proposal-i的提议者只要向Q中所有接受者询问即可。

然后： CP2 —> CP1_2—> CP1 —>一致性

但是实际上获取K没有那么简单，K包含的是Q所有最终接受的proposal-id小于i的的提案，不仅包含已经接受过的提案，还包括未来会接受的提案。获取已经接受过的提案是容易的，Q中的接受者只需记录它所有接受过的提案，当收到提出Proposal-i的提议者询问时，回复当中proposal_id小于i的提案即可;但是如何知晓未来？我们可以换个思路，既然无法知晓未来，那么我们约束未来，收到询问后，令Q中的接受者都承诺不再接受任何proposal_id小于i的提案，即接受者未来将不接受任何proposal_id小于i的提案;既然未来已不存在，那么Proposal-i的提议者根据Q的回复获能得到完整的K。

于是协议的流程如下：

对于提议者，在正式提案前，先向任意的法定集合Q发送一个消息，这个消息即是预提案，消息中要附带提案的proposal-id，作为接受者承诺和回复的依据。

接受者收到预提案后，承诺：不再接受比预提案中附带的proposal-id更小的提案；并回复:已经接受的proposal-id比于提案的proposal-id更小的提案，如之前所论述的，回复的所有满足条件的提案可以优化为只回复一个比预提案proposal_id更小的提案中proposal_id最大的那个提案。

提议者收到所有Q中接受者回复的提案后，挑选其中proposal_id最大的提案的值作为本次提案的值。

这样我们就得到了Paxos中最为关键的几步，阅读了之前冗长的假装推导，相信读者很容易就能补全它得到完整的Paxos。

相比于之前近万字的假装推导，这个推导过程才1500字左右，但是即说清了Paxos是如何得出的，又论证Paxos为何正确，简洁却更有力。所以最后还是建议真有兴趣的话去看下原文，在我看来它无疑是计算机领域那数不尽的论文中最值得阅读的那一类。末尾我所描述的版本思路来自<<Paxos made simple>>，基本一致但也并不完全相同；而<< The Part-Time Parliament>>则别有一番风味。

最后需要注意的是Paxos并不完全满足开头解决一致性问题需要满足的三个条件中的3。理论上，Paxos存在永远无法达成一致的可能，哪怕是在所有进程都存活的情况下。想象一下这样的场景，一个提案Proposal-j被提出时，恰好一个proposal-id更大的预提案Proposal-i被提出，导致Proposal-j无法被通过，而Proposal-i同样的又因为一个proposal_id更大的其它预提案被提出，导致无法被通过。这种情况理论上存在无限递归的可能，这个问题也称为活锁;FLP早就证明了就算是容忍一个进程的失败，异步环境下任何一致性算法都存在永不终止的可能。但是实际的工程中，很多手段可以来减小两个提案的冲突概率，使得v被决定的均摊开销是一个提案，多个提案还无法决定v值的情形是极小概率事件，且概率随着提案个数增加越来越小。另外的一点，通常认为Paxos可以容忍少数进程挂掉，但这只是为了保证它的活性，对于安全性，实际上Paxos永远满足1,2，哪怕进程都挂掉了，此时只是显然一致无法达成而已。