Distributed Systems for Fun and Profit 笔记（二）
2. 抽象的上下不同层次 系统模型 分布式系统中的程序： 在独立节点上同时运行 通过可能引入不确定性和消息丢失的网络连接 并且没有共享内存或共享时钟 系统模型列举了与特定系统设计相关的许多假设，实现分布式系统的环境和设施的假设： 节点具有什么功能以及它们如何失败 通信连接如何运行以及它们如何可能失败 整个系统的属性，例如关于时间和顺序的假设 健壮的系统模型做出最弱假设，强有力的假设创建易于推理的系统模型 此模型中的节点 作为计算和存储的主机： 执行程序的能力 能够将数据存储到内存和稳定持久状态的能力 时钟 节点执行确定性算法 故障模型：崩溃恢复而非拜占庭容错（任意错误） 此模型中的通信连接 通信连接将各个节点相互连接，并任一方向发送消息 网络不可靠，消息易延迟丢失 网络分区：网络断开但节点存活 时间和顺序的假设 信息最多以光速传播 如果距离不同，节点间消息的到达时间、顺序可能不同 同步系统模型 进程以锁定步骤执行；消息传输延迟有已知上限；每个进程都有准确的时钟 异步系统模型 没有时间假设，进程以独立的速率执行；消息传输延迟没有限制；有用的时钟不存在 共识问题 多个节点都同意一些值时达成共识 一致：每个正确节点都同意相同的值 完整：每个正确的进程最多只能决定一个值，如果决定某个值，那么一定是某些进程提议的 终止：所有进程最终达成决定 有效：如果所有正确进程提议相同的值 V，那么所有正确进程决定值 V 两种不可能的结果 FLP 不可能 假定节点只能因崩溃而失效；网络可靠，并且异步系统模型的典型时序假设成立：例如，消息延迟没有限制， 在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法 CAP 定理 三个属性： （强）一致性：所有节点同时看到相同的数据 可用性：节点故障不会阻止幸存者继续运行 分区容错：网络或节点故障导致消息丢失时，系统仍可继续运行 同时具备这三种属性的系统无法实现： 三种不同的系统类型： CA（一致性+可用性）：完全严格的仲裁协议，例如两阶段提交 CP（一致性+分区容错）：多数仲裁协议，其中少数分区不可用，例如Paxos AP（可用性+分区容错）：使用冲突解决方案的协议，例如Dynamo 一致性模型：程序员与系统之间的合同，其中系统保证，如果程序员遵循某些特定规则，则对数据存储区的操作结果将是可预测的 强一致性模型（能够维护单个副本） Linearizable consistency （可线性化一致性） Sequential consistency （顺序一致性） 弱一致性 Client-centric consistency models （客户端为中心一致性） Causal consistency: strongest model available （因果一致性） Eventual consistency models （最终一致性） 线性化一致性要求操作生效的顺序等于操作的实际实时顺序，顺序一致性允许对操作进行重新排序，只要在每个节点上观察到的顺序保持一致