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