MIT 6.824 学习记录：Testing Distributed Systems for Linearizability
上周完成了 MIT 6.824 第二周的学习内容。在后半部分，重点学习了“线性化（Linearizability）”这一核心一致性概念。下面是我对相关内容的理解与思考。
概念引入：为什么需要 Linearizability？
在传统的单体系统中，系统内部状态与外部请求是确定性的，我们可以直接通过设计 test case 来验证系统的正确性。例如，一个请求执行后，系统的状态变化是可预期的，且请求之间不存在复杂的并发交互。
但在分布式系统中（如分布式 Key-Value 存储系统），我们面临几个挑战：
状态依赖性：某些操作依赖于系统当前状态（如 get 依赖于之前的 put）
并发性：多个客户端可能并发地向系统发起请求
非确定性调度：由于网络延迟和处理调度的差异，请求的到达顺序与处理顺序可能不一致
这些因素使得传统的逐条 test case 方法难以有效验证系统行为。于是，我们引入了一种更通用的正确性判定方式——Linearizability（线性化）。
简而言之，Linearizability 要求系统行为对客户端来说“看起来像是操作被一个接一个顺序执行的”，且每个操作在其开始和结束时间之间某个点生效。
例如，在分布式 KV 系统中，get 操作必须能观察到之前 put 的结果，而不能返回旧值。这种“看起来像串行执行”的模型，是我们在设计和验证分布式系统时追求的目标。
线性化测试：如何验证系统是否线性化？
在分布式环境中，由于并发的存在，我们无法通过静态 test case 验证所有可能的执行路径。因此需要一种动态的、基于执行历史（history）的分析方法。
测试流程如下：
构造并发请求历史：通过多个客户端随机并发地向系统发起操作，记录每个操作的 发起时间（start time）、完成时间（end time） 和 返回结果（response）。
在时间轴上建模：将每个操作在时间轴上表示为一个区间。
寻找线性化点（linearization point）：依次尝试为每个操作选择一个在线段区间中的时间点，作为其“生效”的时刻，使得：
所有操作的结果可以通过串行顺序来解释
操作顺序符合时间先后约束
每个操作的影响可以被后续操作正确感知
例子：线性化的系统行为
假设初始值 X=0，三位客户端发起如下操作：
客户端3首先执行
get，返回0客户端1随后执行
put(1)，将 X 设置为1客户端2执行
get，返回1
我们可以在线性时间线上为每个操作选定一个“生效”时间点，且该顺序可以用一个串行执行模型解释，因此该系统是 linearizable 的。
非线性化的反例
再看下面这个图例：
客户端2执行
get，返回1，说明其操作在线性时间线上必须在put(1)之后；客户端3执行
get，返回0，这要求其操作在线性时间线上在put(1)之前。
但由于操作的时间区间重叠，我们无法构造一个合法的顺序同时满足所有操作的因果依赖关系，因此该执行 不可线性化（non-linearizable）。
也就是说：若不能为所有操作找到符合条件的线性化点序列，则系统行为不满足线性化。
目前已有一些广泛使用的线性化测试工具，例如：
knossos：由 Jepsen 团队开发的分布式一致性验证工具。
Porcupine：Anish Athalye 开发的 Go 语言线性化验证框架，使用 model checking 方法验证系统历史。
思考：一致性模型的选择与系统设计权衡
在上周完成的 Lab 2 中，我们实现了一个保证线性化的分布式 Key-Value 存储系统。当时我就意识到：线性化其实是对系统一致性的强约束形式。
除了 Linearizability，还有其他常见的一致性模型，例如：
Eventual Consistency（最终一致性）
Causal Consistency（因果一致性）
Fork Consistency（分叉一致性）
Serializability（可串行化）
这些模型在多操作之间的可见性、时序依赖和状态传播上的约束强度各不相同。一般来说，一致性越强，系统的可扩展性和性能成本也越高。
例如，在我的 Lab 2 实现中，为了实现线性化，我们引入了加锁机制，这虽然提高了一致性，但也引入了性能瓶颈。这种一致性与性能之间的权衡，是分布式系统设计中始终存在的主题。
思考题：两个并发 get 是否可能返回不同值？
课程提供了一个阅读材料中的思考题：
With a linearizable key/value storage system, could two clients who issue get() requests for the same key at the same time receive different values? Explain why not, or how it could occur.
我的思考如下：
这种情况是有可能发生的，原因在于：
虽然两个
get()操作是“同时”发起的，但由于网络延迟和调度的不确定性，它们到达系统的时机可能不同Linearizability 并不要求系统按实际 wall-clock 时间顺序处理请求，只要存在一种合理的“线性顺序”可以解释结果即可
在这两个
get()操作之间，可能存在其他客户端发起的put()操作，并成功改变了状态
因此，如果一个 get() 在 put() 之前执行，而另一个在之后执行，那么返回值就可能不同。这并不违反线性化模型，而是符合其“操作在某一时间点原子生效”的定义。
总结
本周对 Linearizability 的学习让我更加深刻地认识到，在分布式系统中，即使是最基本的 get() / put() 操作，其一致性保证也是建立在复杂模型之上的。
相比传统单体系统中的“预期确定性”，分布式环境下的操作顺序、响应行为、网络延迟等因素都显著提升了验证正确性的难度。Linearizability 为我们提供了一个可行的、一致性强的语义模型，使我们可以在不依赖操作物理顺序的前提下，评估系统是否符合“对客户端而言看似串行”的执行逻辑。
通过本周的阅读和 Lab2 实践，我不仅理解了线性化背后的理论基础，还掌握了如何基于请求 history 对分布式系统进行一致性验证的方法。这也让我更加意识到在构建分布式服务时，一致性、性能与可伸缩性之间的权衡无处不在。
接下来，我将开启第 3 周的学习内容，进入分布式共识的核心主题 —— Raft 协议的实现。我对这个传说中的 Lab3 充满期待，也希望能够在实践中进一步加深对分布式系统核心原理的理解。
📚 参考资料：