2021电子科技大学分布式系统期末考点精析与实战解析
1. 分布式系统期末考试核心考点解析
分布式系统作为计算机专业的核心课程，其期末考试往往让不少同学感到头疼。根据2021年电子科技大学期末考试的回忆版试题，我们可以梳理出几个高频考点，这些内容不仅出现在选择题和判断题中，更是大题的重点考查方向。
分布式事务是考试中的常客。回忆版试题中多次出现关于事务号分配阶段、分布式事务实现方案的题目。在实际操作中，事务号通常在事务开始阶段分配，这一点需要牢记。另外，像两阶段提交（2PC）和三阶段提交（3PC）的区别、TCC分布式事务模型等也是需要重点掌握的内容。我在复习时发现，画流程图是理解这些概念的好方法，比如画出2PC的协调者和参与者之间的交互过程，能帮助记忆各个阶段可能出现的故障场景。
时钟同步问题几乎每年必考。试题中出现了关于时钟偏移、漂移的判断题，以及Cristian算法和Berkeley算法的应用题。这里有个易错点：时钟内部同步和外部同步的区别。内部同步关注系统内各节点时钟的一致性，而外部同步则要求系统时钟与外部时间源同步。在解决"接收方何时能忽略具有时间戳T的消息"这类问题时，关键是要理解时钟同步精度与消息传递延迟的关系。
GFS设计原理是另一个重点。回忆题中多次要求分析GFS的设计动机和Master节点无瓶颈的原因。GFS通过将控制流与数据流分离、采用单Master多ChunkServer的架构、使用64MB大块存储等设计，有效避免了性能瓶颈。我在实验室搭建简易分布式存储系统时，就深刻体会到这些设计决策的巧妙之处。
2. 分布式事务与时钟同步实战详解
分布式事务的实现方案是考试的重点难点。回忆题中出现的"实现至多一次的可靠消息传递"问题，考察的就是如何在分布式环境下保证消息传递的可靠性。题目给出的方案是使用同步时钟加时间戳的方法，这实际上是实现了类似TCP协议中序列号去重的机制。
对于问题a"何时能忽略时间戳T的消息"，答案看似简单（T ≤ T'时忽略），但需要理解背后的原理：这利用了时钟同步范围（200ms）和消息最大延迟（100ms）的关系。假设时钟同步误差最大为D，消息最大延迟为t，那么当T' - T > D + t时，可以确定T消息是重复的。这种题型在2017年和2020年的考题中都有出现，只是参数不同。
时钟同步的题目往往结合具体算法考察。比如2020年考到的Cristian算法应用题，要求写出时间设置公式T_server + 1/2 RTT，并分析误差范围。这里容易出错的是忽略最小延迟T_min的影响，实际误差应该是1/2 RTT - T_min。我在实验课做时钟同步时，就曾因为没考虑网络延迟的波动导致同步精度不达标。
Berkeley算法是另一个常考点，它采用主从式架构，主节点定期收集从节点时间，计算平均值后调整各节点时钟。与Cristian算法不同，Berkeley算法不依赖外部时间源，适用于内部同步场景。考试可能会要求比较这两种算法的适用场景和精度差异。
3. GFS架构与分布式哈希表深度剖析
GFS的设计思想是分布式系统课程的经典案例。回忆题中多次出现关于GFS设计动机的问题，正确答案包括"流式读取"和"大文件"，而"随机写"通常不是GFS的设计目标。GFS通过三个关键设计实现高性能：单一Master管理元数据、64MB的大数据块、客户端缓存元数据减少Master访问。
Master无瓶颈的原因是考试热点。回忆题答案指出，Master的元数据量很小（64B:64MB），全部保存在内存中；而且客户端不通过Master读写数据，只有元数据操作需要访问Master。我在课程设计中尝试实现简化版GFS时，就体会到将数据流与控制流分离的重要性。
分布式哈希表(DHT)和Chord算法也是高频考点。Chord通过finger表实现O(log N)的查询效率，每个节点只需维护O(log N)的路由信息。考试可能会给出具体节点和键值，要求画出路由路径。比如2020年考题给出了m=7的Chord环，要求找出K=123的存储节点和N28的指针表。
Chord的四个特点需要熟记：确定性、可扩展性、负载均衡和容错性。在分析对P2P系统的影响时，可以举例说明：确定性保证了查询总能成功；可扩展性使得系统能处理节点动态加入退出。这些概念在BitTorrent等实际P2P系统中有广泛应用。
4. 并发控制与一致性模型考点精讲
并发控制方法的选择是考试常见题型。回忆题中"大量写操作最适合的并发控制方法"，正确答案通常是时间戳排序或乐观并发控制。两阶段锁(2PL)虽然能保证可串行化，但在写密集场景下性能较差。乐观控制通过验证阶段解决冲突，适合冲突较少的场景。
乐观并发控制的验证方式经常被考到。向前验证和向后验证可以独立使用，也可以组合使用，这取决于系统的隔离级别要求。在课程实验中，我实现过基于时间戳的乐观并发控制，验证阶段检查读写集冲突，效果比悲观锁好很多。
一致性模型是另一个难点。回忆题中出现了"顺序一致性=>线性一致化"的判断，这个命题是正确的。线性一致性比顺序一致性更强，要求所有操作看起来是原子性的。在分析分布式系统行为时，Lamport时钟和向量时钟是重要工具。
2021年考题给出了一个事件图，要求计算Lamport时间和向量时钟，并判断一致割集。解这类题的关键是：Lamport时间只需维护一个计数器，而向量时钟需要为每个进程维护一个分量。一致割集要求没有"因果倒置"的事件，即如果事件e在割集中，那么e的所有前驱事件也必须在割集中。
5. 典型算法伪代码实现与优化
分布式算法伪代码是考试大题的重头戏。Chandy-Lamport快照算法几乎每年都以某种形式出现，其核心思想是通过标记消息记录分布式系统的全局状态。算法伪代码要掌握两个规则：标记发送规则（记录状态后发送标记）和标记接收规则（根据是否已记录状态采取不同动作）。
基于环的选举算法也是常考内容。当节点发现协调者失效时，向邻居发送选举消息，携带自己的ID。收到选举消息的节点比较ID，转发较大者，最终最大的ID成为新协调者。我在实现这个算法时，特别注意处理并发选举的情况，避免产生多个协调者。
组播协议的实现经常出现在考题中。用基本组播(B-multicast)实现可靠组播时，需要添加确认和重传机制。伪代码通常包括：发送方序列号分配、接收方的ACK机制、定时器处理超时等。可靠组播要满足三个性质：完整性（不丢失消息）、有效性（正确传递）和有序性（FIFO或因果序）。
Gossip协议的分析题可能要求描述查询和更新流程。在反熵模式下，节点定期随机选择邻居交换状态；在谣言传播模式下，更新像病毒一样扩散。这种流行病传播方式虽然简单，但能提供最终一致性，适合大规模分布式系统。
6. 真题实战与应试技巧
选择题和判断题往往考察细节知识点。比如2020年考到的"异步分布式系统的故障不包括"，正确答案是"屏蔽故障"；"GFS的设计动机不包括"应选择"随机写"。这类题目需要对概念有准确理解，复习时要特别注意容易混淆的术语。
简答题需要结构化回答。比如"拜占庭将军问题及算法要求"，应该分三部分回答：问题描述（将军们如何达成一致）、算法要求（终止性、协定性、完整性）、典型解决方案（如PBFT）。我在备考时，为每个高频简答题准备了答题模板，确保不遗漏要点。
计算题通常涉及时间戳和一致性检查。Lamport时间计算要注意每个消息传递都会增加时间戳；向量时钟更新规则是：本地事件增1，接收消息时取各分量的最大值再加1。考试时建议先画出事件图，再逐步计算。
对于有图的题目，如判断事务序列是否可串行化，可以采用优先图方法：画出操作之间的依赖关系，检查是否有环。2021年考题要求给出两种先U后T的串行等价序列，这需要分析操作冲突，找出不违反依赖关系的排列。