《Time, Clocks, and the Ordering of Events in a Distributed System》中文版

分布式系统中的时间,时钟,以及事件顺序

原文:Time, Clocks, and the Ordering of Events in a Distributed System
作者:Leslie Lamport
发表日期:1978 年 07 月
译者:ou@http://ouonline.net/

摘要

本文研究了“分布式系统中一个事件在另一个事件之前发生”这个概念,并用它来定义事件的偏序关系。给出了用于同步逻辑时钟系统的分布式算法,该算法可以用来确定事件的全序关系。用解决同步问题的方法来说明全序的使用。这个算法被专门用来同步物理时钟,并得出时钟同步的最大偏离范围。

引言

时间的概念是我们思维的基础。它源自一个更基础的概念,即事件发生的顺序。如果某事发生在我们的时钟读数为 3:15 之后并且在其读数变为 3:16 之前,我们就说 3:15 发生了某事。事件的时间顺序概念充斥着我们对系统的思考。例如,在航空公司的预定系统中,我们指定如果在航班满员之前提出预定请求,那么应该允许该请求。然而,我们会看到,在考虑分布式系统中的事件时,必须仔细重新检查这个概念。

一个分布式系统由空间上分离的不同进程的集合组成,这些进程通过交换消息来互相通信。一个互相连接的计算机的网络,例如 ARPA,就是一个分布式系统。单个计算机也可以被看作是一个分布式系统,其中的中央控制单元,存储单元和输入输出通道都是独立的进程。如果消息传输延迟与单个进程中事件发生的间隔相比不能忽略,则这个系统就是分布式的。

我们将主要关注空间上分离的计算机系统。但是,我们的许多结论将会更通用。特别地,单台计算机上的多进程系统会遇到与分布式系统类似的问题,因为某些事件的发生顺序不可预测。

在分布式系统中,有时候无法决定两个事件中的哪一个先发生。因此,“先发生”关系只是系统中事件的偏序关系。我们发现这个问题经常出现,是因为人们没有完全意识到这个事实以及它的含义。

在本文中,我们讨论了由“先发生”关系定义的偏序,并给出了一种分布式算法,用于将偏序扩展为所有事件的一致全序。这个算法可以为实现分布式系统提供有用的机制。我们通过一个解决同步问题的简单方法来说明它的用法。如果由这个算法得到的顺序和用户感知的顺序不同,则可能会发生意外的异常行为。通过引入真实的物理时钟可以避免这种情况。我们介绍了一种用来同步这些时钟的简单的方法,并推导出它们漂移的不同步程度的上限。

偏序

如果事件 a 发生的时间早于事件 b,大部分人可能会说 …

阅读全文…

《Reconfiguring a State Machine》中文版

重新配置状态机

原文:Reconfiguring a State Machine
作者:Leslie Lamport, Dahlia Malkhi, Lidong Zhou
发表日期:2010 年 01 月 29 日
译者:ou@http://ouonline.net/

摘要

重新配置意味着更改分布式系统中的执行任务的进程。我们介绍几种方法(包括一些新方法),用来重新配置一个使用状态机方式来实现的系统。本文将讨论这些方法与之前的重新配置算法之间的关系——特别是在组通信中的视图变更。

目录

  • 1 引言
  • 2 状态机
    • 2.1 准备工作
    • 2.2 垃圾回收
    • 2.3 重新配置的简单方法
    • 2.4 正确性
  • 3 重新配置的复杂方法
    • 3.1 停止状态机
      • 3.1.1 “停止标记”法

阅读全文…

《Paxos Made Simple》中文版

深入浅出 PAXOS

原文:Paxos Made Simple
作者:Leslie Lamport
发表日期:2001 年 11 月 01 日
译者:ou@http://ouonline.net/

摘要

Paxos 算法,如果用简明的语言来描述,其实很简单。

目录

  • 1 引言
  • 2 共识算法
    • 2.1 问题描述
    • 2.2 选定一个值
    • 2.3 获得被选定的值
    • 2.4 推进
    • 2.5 实现
  • 3 实现一个状态机
  • 参考文献

1 引言

Paxos 是一个用来实现具有容错特性的分布式系统的算法。很多人认为 …

阅读全文…