感受

主要回顾分布式学习前两篇 Paper 阅读感受。

Paper1——Time, Clocks, and the Ordering of Events in a Distributed System

回忆梳理关键词：Happen Before 关系、偏序全序（局部序全局序）、逻辑时钟、物理时钟。

主体内容总结

本文以分布式中系统中涉及时间概念的一个很困惑的问题作为引子— —在分布式系统的架构中，当消息传输的时间不可忽略（如同广义相对论中时间的相对性），我们该如何定义分布式系统中时间发生的顺序，Lamport 向读者介绍了以下内容。

• 分布式系统中事件发生先后的概念（happen before）。
• 基于 happen before 的逻辑时钟（偏序/局部）
• 逻辑时钟在给定条件后的全局化（全局序），并给出了一个基于全局序的解决资源争夺问题方法。
• 物理时钟及其他相关问题

Happen Before

这一段主要是用了离散数学里学到的关系，线序、偏序、全序的概念。

Lamport 不依赖物理时钟定义了事件 happen before（后面简写为 HB）的关系，基于以下的设想：

• 分布的各进程内的事件是线序，在先发生的对在后发生的具备 HB 关系
• 跨进程（进程间消息通信作为收/发两个事件）的事件，发出对接收有 HB 关系。

根据实际情况我们很容易总结出来，HB 关系应该是反自反、反对称、传递的。

整个分布式系统由于消息的通信构成一个从系统 start 开始的偏序集合。

Logical Clocks

基于 HB 关系，Lamport 给出了一个给事件赋值的函数（逻辑时钟）及其计算方法，先后可通过函数值（逻辑时钟值）大小反映出来（但反过来不行）。

分布式算法概括：

1. 每个 Process 对本进程的线序事件，计数值递增。
2. 每个 Process 的事件发送消息时，附带时间戳。
3. 每个 Process 接受到其他事件的消息时（HB 关系箭头的弧头），更新其计数器值为消息时间戳和本地计数器值 Max（+1）。

Order Totally

将偏序全局化，需要人工定义一个 Process 的优先值（Process 顺序）。

人工定义的 Process 顺序不同会导致全序的不同，所以对于一个确定的（消息发送等确定）分布式系统，偏序集是确定的（唯一的），而全局序是不唯一的。

托这个全局序（全局的时间戳值）的福，Lamport 给出了一个解决单资源互斥问题的分布式算法。

算法细节及证明见翻译 doc，直观理解，没有这个全局序我们就不能依靠全局序的时间戳来比较从而进行对应操作。

Physical Clocks

对于异常情况：存在外部的限制要求。Lamport 给出的解决方法。

1. 外部要求内部化
2. 引入实际物理时钟

对物理时钟的要求是：增速逼近单位 1，以及分布式物理时钟的一致性（数学证明还没有看懂）。

读完感受

虽然是 1970+的文章了，但是分布式的核心问题（我以为的）已然提及，Lamport 对分布式中事件顺序的认识像极了相对论世界中事件/时间的观点，着实让我 get 了分布式不同于我现在所用所看所学的单机系统最大的不同。

对于问题解决的思路也是极为清晰，从关系的定义，到不依赖实际时间的逻辑大小、到全局化、再到实际时钟，结合实际问题的分布式算法，可以从最初的构想到最终的实现有一个流水线似的认识。

自己最喜欢的离散数学也在这里面发挥了很大的作用，见识到了数学——这种基础学科作为科学发展地基般的作用，我反复读了四到五遍文章，也看了 Lamport 本人对他自己这篇文章的评价和网络上其他人的评价，对于文章中可推的公式和可证明的地方都尝试自己推导了一下，着实让人着迷，作为自己尝试科研的启蒙文章，真的非常开心。

Paper2——Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial

回忆梳理关键词：状态机，容错（Fault Tolerance）、两种故障

主体内容总结

看论文标题就知道，是一篇“Tutorial”，讲了用状态机模型来达到容错服务。

包括后面所看到的 GFS，自己学习的 LVM，都存在这样的问题：出错、出错、出错，由多台分布式机器构成的系统中难免会碰到这样那样的错误，防止出错此时显得太过较真，采用合适的策略（状态机、备份、心跳线热启动等）将出错导致的系统整体性能下降掩盖过去，达到高可用、用户层透明才是更“分布式”的思考方式。

State Machine

接触了算法中涉及的自动机（AC 自动机、后缀自动机）以及编译原理中的自动机（DFA，PDA），对于状态机的概念已经比较熟悉了，这里用文章中的定义再从另一个角度强调一下：状态机的输出完全由它处理的请求序列决定。

Fault Tolerance

两种计算机系统中常见错误：

• Byzantine Failures（拜占庭故障）：该组件可能表现出任意和恶意的行为，可能涉及与其他故障组件的勾结（个人理解是会反馈假结果，无法有效监测且可能影响周围组件）
• Fail-stop Failures. （异常终止错误）：允许其他组件检测到错误并停止。

考虑最坏情况下的 t tolerance

拜占庭故障所需组件数：2t+1（保证多数） 异常终止所需组件数：t+1（保证存在一个返回正确结果即可）

某些特殊条件下还可以弱化条件。

实现的条件是保证备份（副本）的协调（Replica Coordination）：所有备份（副本）都可以接收到且接收到顺序相同的请求序列。

拆分成两个子要求：

1. Agreement：每个非故障状态机都会接收到每个请求。
2. Order：每个非故障状态机都会以相同的顺序处理这些请求。

文章后续解释了个子要求的实现方式。

Agreement: 通过设置 transmitter 来使所有非故障状态机达到相同值。

Order

Order 条件极其稳定性测试，稳定的请求可以传递给后面的状态机副本。个人对稳定的理解：具备相对优先顺序、不会改变、可被执行。

文章介绍了几种实现方法：

• 使用逻辑时钟（Lamport 的方法）赋值
• 同步的物理时钟方法

对应的稳定性检测在文章翻译部分分析过了，逻辑时钟是基于 FIFO 假设以及错误信息告知假设，使得当收到其他机器发来了更晚时间戳请求时，则先前的请求就是稳定的。而物理时钟是满足在\(\tau - \delta\)时间之前的即为稳定的。

读完感受

应用了上一篇 Lamport 的时钟来解决 Order 的问题，感觉思路上是联通的。

状态机模型的应用有点感觉是执行状态的重复（但是说实话没有找到确切的状态描述，可能是论文看的还不够仔细）。

重新认识了两种类型，然后突然发现拜占庭问题还是 Lamport 等人最先提出来的，我想有机会去了解一下原论文，毕竟这个问题在网络/安全/系统中出现多次了。