2019秋 分布式系统期末考试卷1

分布式系统是现代互联网服务的核心，涉及到多个计算机之间的协作以提供高可用性、可扩展性和容错性。本试卷涵盖了分布式系统中的多个关键概念，包括一致性、互斥协议、共识算法、Kubernetes、RPC、时钟同步、Paxos协议、Chord分布式散列表等。 1. DNS服务器并不直接使用Paxos算法来避免不一致性。DNS通常使用主从复制的方式进行数据同步，而Paxos是一种用于在分布式环境中达成共识的算法，确保在存在网络分区的情况下也能正确处理请求。 2. 共识的应用场景包括选举（例如，确定集群中的领导者）、故障检测（通过多数派投票来确认系统状态）和容错（确保即使部分节点失败，系统仍能正常运行）。故障检测不是Paxos共识算法的直接应用场景，而是可能利用共识结果来辅助实现。 3. Ricart & Agrawala互斥算法相比于集中式的互斥协议，后者发送的消息数量通常是前者的两倍。这是因为Ricart & Agrawala算法要求每个请求和响应都需要双向通信，而集中式协议只需单向通信。 简答题： 1. 分布式系统的可扩展性是指系统能够通过增加硬件资源（如服务器）来提升性能和处理能力。实现可扩展性通常涉及负载均衡、数据分区、服务化和水平扩展等技术。 2. 代码迁移是在运行时将代码从一个计算节点移动到另一个节点的过程，目的是优化资源分配、负载均衡或应对故障。代码迁移模型包括热迁移（无需停止服务）和冷迁移（需停止服务）。虚拟化迁移属于热迁移的一种，因为它可以在不中断应用的情况下迁移虚拟机。 3. Kubernetes（K8s）的主要模块包括API服务器（处理REST请求）、etcd（持久化数据存储）、控制器管理器（执行后台任务）、调度器（决定哪个节点运行Pod）、以及kubelet和容器运行时（管理Pod和容器）。这些组件协同工作，以自动化容器的部署、扩展和管理。 4. RPC（远程过程调用）的全过程通常包括客户端发起请求、网络传输、服务端处理请求、返回响应以及客户端接收响应。具体步骤涉及序列化、网络传输、反序列化以及错误处理。 分析题： 第一题涉及时间同步问题，包括计算时间偏差、校准方法（如调整中断频率）以及在无UTC服务器时的集群内时钟同步策略。 第二题考察了逻辑时钟和向量时钟的概念，以及如何判断事件的happen before关系，并分析检查点作为恢复线的可能性。 第三题涉及一致性模型，特别是以客户为中心的一致性、单调读一致性以及各种一致性强度的比较。题目还要求根据特定场景判断是否满足单调读，以及如何修改。 第四题讨论了多副本系统中的MPC（Message Passing Completeness）模型，区分不同情况下的消息确认策略，如OK、DUP、ZERO和文档更新次数。 第五题深入探讨了Paxos协议，包括其角色（提议者、接受者和学习者）、两阶段协议流程，以及为何Paxos可能存在活锁问题。 第六题涉及Chord分布式散列表，包括构建Chord环、维护指针表、插入操作和查询过程，以及与集中式文件系统如NFS的比较优势。 这些知识点涵盖了分布式系统设计和实现的关键要素，对理解分布式系统的工作原理至关重要。