当今使用的几乎所有软件都是分布式系统的一部分，手机上的应用程序与云中托管的服务一起工作，托管服务本身很大-规模分布式系统，通常运行在遍布世界各地的机器上，大数据系统和大型数据库分布在很多机器上，大多数科学计算和机器学习系统在多个处理器上并行工作，甚至传统的桌面操作系统和电子表格和文字处理器等应用程序与分布式后端服务紧密集成。在分布式系统中，多台不可靠的机器并行运行，通过网络链接以任意延迟相互发送消息。面对混乱，我们如何确定这些系统会做我们想做的事？构建正确的分布式系统并不新鲜，传统的解决方案是通过保证内存一致性来降低这种复杂性，即确保以受控方式访问内存（堆变量、数据库等）。然而，用于实现这些机制的分布式协议往往阻碍了分布式系统的高性能、可扩展性和可用性。1.分布式协议相关问题通过分布式协议，自治和松耦合的机器可以共同决定如何控制基本行为，包括访问共享内存的顺序。这些协议在分布式计算中被广泛引用，一些著名的技术包括paxos和两阶段提交(2PC)协议等。1.协调成本高不幸的是，分布式协议的成本使其最终难以实现。分布式系统中高可扩展性的首要原则可能是最小化共识机制并将它们移出关键路径，或者将它们隐藏在系统中很少访问的角落，然后让应用程序开发人员很难获得使用它们的权限.事实上，问题不在于分布式协议难以实现，而在于分布式协议会减慢或停止分布式服务中的计算。这些协议的延迟很高，大约为10ms-100ms。依赖这些协议的大型系统并不意味着在应用程序快速路径中使用。另外，分布式协议的延迟问题也会转化为微观层面的问题，多台服务器的key-value存储可能会花费90%的时间等待协调。2.程序一致性传统的一致性研究主要集中在线性和冲突序列化方面。这些属性通过限制冲突的内存访问序列来确保内存一致性。这掩盖了是否需要协调以保持程序一致的基本问题。整体解决这个问题，是否有程序语义支持？现实中，十字路口的红绿灯是相对于分布式协议而言的，但是如果有立交桥或者隧道，就相当于没有分布式协议就达到了目的。从本质上讲，通过巧妙地控制进入道路重叠的地图关键区域的顺序，无法找到更好的解决方案。解决方案是设计道路以避免需要协调。然而，并不是所有的问题都有这样的解决方案。对于任何给定的计算问题，我们如何知道它是否需要分布式协议来保持程序的一致性？3.死锁检测在传统的数据库系统中，死锁检测器通过分析有向图来识别这种“等待”循环，其中节点代表事务，边代表锁队列上的一个事务在等待另一个事务。死锁一个稳定的属性是：事务在等待周期内无法取得进展，所以所有的边都会无限继续下去。在分布式数据库的有向图中，等待图的“本地”视图仅包含全局等待图中边的子集。在这种情况下，局部死锁检测器如何协同工作来识别全局死锁？为了识别这种分布式死锁，每台计算机都与其他计算机交换其边的副本，以积累有关全局有向图的更多信息。任何时候机器观察到它接收到的信息中的循环，它都可以在该循环上声明事务中的死锁。在这种分布式计算中，可能会担心由于延迟或重新排序的消息而导致的瞬态错误。本地检测器是否必须与其他机器协调以确保观察到死锁？额外的事实只会导致检测到额外的周期：每台机器的输出随着输入单调增长。最后，如果所有边最终在所有机器之间共享，那么机器就基于完整图的结果达成一致。4.垃圾收集分布式系统中的垃圾收集器必须识别分布式内存引用图中无法访问的对象。垃圾收集通过识别与系统运行时的“根”断开连接的组件来工作。一旦图形组件与根的连接被删除，该组件内的对象将不会被重新引用。在分布式系统中，对对象的引用可以跨越机器，并且引用图的本地视图仅包含全局图中边缘的子集，多个本地垃圾收集器如何协同工作以识别真正无法访问的对象？一台机器可能有一个本地对象，但不知道该对象是否连接到根。同样，每台机器都与其他机器交换图中边的副本，以积累更多关于该图的信息。本地收集器能否自主判断和回收垃圾？这里真的需要一个分布式协议来协调！机器必须确保它在声明一个对象不可到达之前已经听到了它需要听到的所有内容。知道它已经听到所有声音的唯一方法是与所有其他机器协商以确定这一事实。协商的一个特点是即使在没有数据依赖性的情况下也需要进行通信。2.一致性问题的核心抽象如果存在分布式系统，程序无需协商就可以计算出一个一致的输出，那么这个计算问题就是不协调的，不需要使用分布式协议来实现一致性。那么，没有协调的边界是什么？分布式协议的使用是实现选择的结果，而内在要求是计算问题的属性。因此，人们希望关注程序的一致性：尽管消息和计算之间可能存在竞争条件，但实现是否产生了预期的结果？那么，一致性问题的核心是程序的逻辑单调性吗？简而言之，一个问题具有一致的、无协调的分布式实现当且仅当它在逻辑上是单调的。相比之下，非单调性的问题是在所有信息都到达之前无法继续操作，必须通过分布式协议来达成共识。换句话说，对于具有逻辑单调性的问题，输出仅取决于输入的内容，而不取决于输入到达的顺序。1.程序的一致性分布式系统给程序带来了显着的非确定性，包括不同步的并行性、不可靠的组件、具有不可预测延迟的网络。因此，分布式程序可以针对给定的输入表现出大量可能的行为。在非确定性消息传递的上下文中，如果单个机器上的操作为任何非确定性排序和输入请求集生成相同的输出响应集，则该操作是程序一致的。程序一致性可以应用于单个操作、数据流中的组件，甚至整个分布式程序。与传统的内存一致性属性（例如线性化）不同，程序一致性对新近度（例如，读取不能保证返回最近发出的写入请求的结果）或操作顺序（例如，一个write不保证在同一顺序中应用所有副本）没有要求或承诺。如果应用程序是程序一致的，则内存或存储级别的任何此类异常都不会影响应用程序的结果。程序一致性是分布式系统的一个强大但松散的正确性标准。它排除了由于竞争和非确定性导致的应用程序级不一致，同时允许在实践中防止代价高昂的非确定性排序操作的时间安排。例如，在电子商务平台的购物车功能中，客户通过网络浏览器请求添加和删除在线购物车中的商品，这是一个逻辑单调的过程。设定并计算设定差的结果来确定。然而，支付账单的过程在程序上并不一致。2.分布式系统的可计算性模型分布式计算中的每台机器都支持一些本地计算模型、跨机器的数据分区以及机器随时间进行通信的能力，大致抽象为转换器网络。简单地说，关系转换器是一个事件驱动的服务器，内存中是关系数据库，每个转换器运行一个顺序事件循环。获取并处理一批无序的请求，以插入和删除本地关系中的记录，这些请求可能来自其他机器或特定的输入关系。查询本地关系，计算某处应该发送什么，以便处理请求记录。查询结果作为请求被发送到网络中的相关机器进行处理，在事件循环的下一次迭代中被消化，结果也可以被“发送”到一个特殊的输出。在这个计算模型中，每台机器上的状态由记录集（即关系）表示，而消息由接收机器上从关系中插入或删除的记录表示。每台计算机上的计算是通过在事件循环的每次迭代中对当前本地关系的逻辑查询来指定的。3、逻辑单调性经典的数据库查询语言包括关系演算和代数、SQL、数据模型都是基于一阶逻辑的。大多数常见的表达式是单调的，而语法揭示了潜在的非单调表达式。因此，具有逻辑单调性的程序是一个一致性网络，其中每台机器的查询仅使用单调语法。有了计算模型以及程序一致性和逻辑单调性的定义，在单调关系转换器的网络中，很容易证明任何机器最终都会摄取和发送一组确定性的消息并产生确定性的输出。在执行期间的任何时候，任何机器输出的消息构成最终输出的有效子集。直观地，数据流消息是那些组装其组件不在同一位置的数据的消息。为了隔离协调消息，数据在程序启动时在网络中的机器之间进行分区。在程序执行过程中，每个起点都会产生一个消息模式。如果一个程序需要在所有可能的分区下发送消息，那么就涉及到协调。每个分区发送的消息与数据流无关；这是一条协调信息。单调问题不仅是无协调问题，而且是不需要网络成员知识的问题。3.现实中的一致性实现Brewer的CAP理论非正式地指出，系统只能展示以下三个属性中的两个：一致性、可用性和分区容错性。CAP仅在我们假设所讨论的系统需要执行程序时才有效，并不表示特定程序是否可以同时具有所有三个属性！如果分布式系统满足程序一致性，那么对于逻辑单调性问题实际上可以同时满足CAP的三个性质，但对于非单调性问题则不能。传统的编程语言将世界建模为一组命名变量，其值随时间变化，并进行赋值，使最终程序状态取决于输入到达的顺序。函数式编程长期以来提倡使用不可变变量，这些变量在计算过程中被限制只能取一个值。不可变变量是一种简单的单调模式，可推广到不可变数据结构，使编程不可变树、列表和图形更加实用。基于单调逻辑的编程模式在分布式存储系统的设计中很常见。CRDT为基于单调逻辑的编程模式提供了面向对象的框架，通常用于状态复制场景。CRDT是一种抽象数据类型，其可能的内部状态形成一个网格，并根据网格的相对偏序单调演??化。从面向对象的角度来看，CRDT利用互换性来实现并发下的确定性。这可以追溯到Linux内核，crts的一个问题是它们的保证仅适用于单个对象。可交换性的好处已扩展到可组合的库和编程语言，在这些库和编程语言中，可以验证本地的、以状态为中心的保证并自动组合成全局的、面向结果的、程序级的保证。非单调逻辑问题必然需要分布式系统中各个组件的协调，需要通过分布式协议来实现。将分布式协议从关键路径转移到后台任务需要一定的编程技能和创造力。简而言之，基于单调逻辑的编程并不是构建高效分布式系统的唯一途径，但它作为识别不确定性的分析框架很有用，因此我们可以创造性地处理分布式系统中的一致性问题。4.总结CAP定理确定了在一般分布式系统中不可能实现的事情。事实上，我们需要弄清楚可以实现什么，以及如何在分布式系统中实现一致性，同时最大限度地降低复杂性和成本。如果问题是单调的，则不需要通过分布式协议协商来保证一致性。任何不是单调问题的程序都需要运行时强制协调以确保一致的结果。
