XJC's Journal Container

时间: TrueTime 书接上回, Lamport 老爷子的工作证明了用Wall Clock的可行性, 这回我们来看看工业界是如何基于Wall Clock来做serializable的. 2012 年 Google推出 Spanner的时候发布了 TrueTime API. 10多年后, AWS在re:Invent上介绍Xanadu时提到了Bounded Clock, 很明显是抄TrueTime的作业. 这也侧面印证了基于物理时间戳的快照隔离是真的香. 本文重点关注TrueTime的工作原理, SI(Snapshot Isolation)会是另一篇文章了. 理论工作 看过上篇博客关于论文前半部分的讨论之后我们已经知道, 分布式系统中的不同节点间是很难在时间上达成共识的. 每个节点的时钟都有误差, 读取自己的本地时间并仅不能产生全序,还会引发神经错乱. 逻辑时钟可以解决这个问题, 但一个系统总要和外部交互, 这又会带来因外部消息导致的因果关系错乱问题. 这次我们继续回到上篇文章的后半部分, 仔细看一下 Lamport 老爷子对于物理时钟需要满足条件的定义, 以及延申的定理. 要解决因外部事件导致的因果关系错乱, Lamport 引入了物理时钟. 但物理时钟也有它的固有问题: 分布式系统中不存在单一的权威时间源, 这会导致单点故障,性能瓶颈等问题. 且即使存在也会因权威授时本身忽快忽慢以及信息传播延迟的不确定性导致没法完全时间同步. 时钟漂移: 由于硬件差异, 环境等因素, 每个节点的时钟都以不同的速率在运行, 且这个速率本身也在不断变化. 装逼的说法就是一个时钟的一阶导数不为1, 且它的二阶导数不为0. Lamport做出以下假设: 系统中消息传递的延迟是不确定的, 但存在一个已知的上限 $\delta$. 也就是说系统内任何消息的传播时间都不会超过 $\delta$ 存在一个时钟漂移率的上限 $\rho$, 表示为时钟频率相对于理想时钟频率的最大偏差. 例如 $\rho=10^{-5}$ 表示理想时钟走过 $1s$ 后某个实际时钟的偏差最多是 $10^{-5}$. 如果某一时刻某个时钟 $C$ 和理想时间完全对齐, 则理想时钟 $T$ 过去 $1s$, $C$ 的时间会在 $[T+1-10^{-5}, T+1+10^{-5}]$ 之间.

Continue reading 

Time, Clocks, and the Ordering of Events in a Distributed System 宇宙中没有时间, 只有事件发生的顺序. 为了描述观测到事件的先后, 我们定义了时间. 40年前Lamport老爷子说墙上的钟不好使, 不准. 尤其是分布式环境下时钟没法对齐. 结果Google还是做了个Spanner, 然后一众厂商跟着抄, LOL…… 首先定义 $\to$, 称之为 “happened befor”, $a \to b$即 $a$ 在 $b$之前发生. 我们现在在系统中引入时钟。我们从一个抽象的视角开始，其中一个时钟只是给事件分配一个数字的方式，这个数字被视为事件发生的时间。更准确地说，我们为每个进程 $P_i$ 定义一个时钟 $C_i$，它是一个函数，将进程中的任意事件 $a$ 分配一个数字 $C_i(a)$。整个时钟系统由函数 $C$ 表示，它将任意事件 $b$ 分配一个数字 $C(b)$，其中如果 $b$ 是进程 $P_j$ 中的事件，则 $C(b) = C_j(b)$。目前，我们不对数字 $C_i(a)$ 与物理时间的关系做任何假设，因此我们可以将时钟 $C_i$ 视为逻辑时钟而非物理时钟。它们可以通过计数器来实现，而不需要任何实际的计时机制。 对于所有事件 a 和 b: 若 $a \to b$ 则 $C(a) < C(b)$ Condition: 若a, b是同一进程的两个事件, 且a发生在b之前,则有$C(a) < C(b)$; 若a, b是不同进程的事件, 且a是一条发送消息的事件, b是接收这条消息的事件,则有$C(a) < C(b)$; 现在我们可以尝试在图一中划虚线, 每条线表示时钟走过了一个tick.

Continue reading 

通过棒球解释的复制数据一致性 Doug Terry 微软研究院硅谷分部 MSR 技术报告 2011年10月 摘要 一些云存储服务，例如 Windows Azure，通过复制数据为客户提供强一致性，而其他服务，例如 Amazon，为了获得更好的性能和可用性，选择了最终一致性。对于读取共享数据的客户，可以（也许应该）提供更广泛的一致性保证。在一场棒球比赛中，不同的参与者（记分员、裁判、体育记者等）在读取当前比分时受益于六种不同的一致性保证。最终一致性对大多数参与者来说是不够的，但强一致性也不是必需的。 1. 引言 面向云的复制存储系统为读取数据的应用程序提供了不同的一致性保证。某些系统（如微软的 Azure）仅为其应用程序提供强一致性存储服务。这确保了 Windows Azure 存储的客户始终可以看到某个数据对象的最新值。尽管在数据中心内提供强一致性是理想且合理的，但当系统开始提供跨多个大陆多个数据中心的地理复制服务时，这种一致性引发了一些担忧。 另一些系统，例如 Amazon 的简单存储服务（S3），基于强一致性在大型系统中代价过高的考量，仅提供弱一致性。设计者选择牺牲一致性以获得更好的性能和可用性。在这种系统中，客户端的读取操作可能会返回陈旧的数据。读取操作返回的数据是某一时刻对象的值，但不一定是最新值。这种情况发生在读取操作定向到尚未接收到其他副本所接受的所有写入操作的副本时。这样的系统称为最终一致的。 一些近期的系统认识到需要支持不同类型的应用程序，因而提供了访问存储的多种操作选择。例如，Amazon 的 SimpleDB 提供了最终一致性读取和一致性读取两种模式，后者读取延迟更高且读取吞吐量有所降低（尽管系统文档并未量化其额外成本）。类似地，Google App Engine Datastore 增加了最终一致性读取，以补充其默认的强一致性。PNUTS（支持 Yahoo 的许多网络服务）提供了三种读取操作（读任意副本、关键读取、最新读取）和两种写入操作（写入和测试并设置写入）。 在过去的三十年里，研究社区提出了多种分布式和复制系统的一致性模型。这些模型提供的保证在强一致性和最终一致性之间。例如，一个系统可能保证客户端看到的数据最多滞后5分钟，或客户端始终能观察到其自身写入的结果。实际上，有些一致性模型甚至比最终一致性还要弱，但我会忽略那些实用性较差的模型。探索不同一致性模型的原因在于一致性、性能和可用性之间存在基本的权衡。提供更强的一致性通常会导致读取或写入的性能降低和可用性下降。每种提出的一致性模型都占据了权衡空间中的某一点。 但不同的一致性在实际中是否有用？应用程序开发者能否应对最终一致性？云存储系统是否应该提供比 Amazon SimpleDB 的一致性和最终一致性读取更多的选择？ 本文试图至少部分地回答这些问题，通过一个示例（显然是虚构的）应用场景：棒球比赛。特别地，我探讨了不同访问比赛比分的人的需求，包括记分员、裁判、广播记者、体育记者和统计员。假设比分存储在基于云的复制存储服务中，我展示了最终一致性对大多数参与者来说不够，但也不需要强一致性。大多数参与者从某种中间的一致性保证中受益。 本文的结构如下。下一节定义了六种可能的读取一致性保证。第3节提出了一个模拟棒球比赛的算法，指出数据的写入和读取位置，并表明在不同保证下读取比分时可能返回的结果。第4节则分析了各个访问棒球比分的角色及其所需的一致性保证。最后，我从这一简单示例中总结出结论。 2. 读取一致性保证 尽管过去 30 年来复制系统提供了多种类型的数据一致性，计算机科学研究社区也探索了多种一致性模型，但许多模型都与特定实现绑定。通常情况下，理解一个系统提供的一致性以及适用的情况需要了解系统的运行方式，这给基于此类存储系统开发应用程序的人带来了不小的负担。 我在本节中倡导的六种一致性保证可以用一种简单且独立于实现的方式描述。这不仅能使应用程序开发者受益，还允许底层存储系统在设计、操作和演变上具有更大的灵活性。 这些一致性保证基于一个简单的模型，其中客户端对数据存储执行读写操作。数据在一组服务器间复制，但复制协议的细节对客户端是隐藏的。写操作按顺序进行，最终在所有服务器上按相同顺序完成。此顺序与客户端提交写操作的顺序一致。读取操作返回先前写入的一个或多个数据对象的值，但不一定是最新值。每个读取操作可以请求一致性保证，该保证规定了允许的返回值范围。每种保证通过定义读取操作可见的先前写入集合来描述。表 1 总结了这六种一致性保证。 一致性 可见性 强一致性 可见所有先前的写入。 最终一致性 可见先前写入的子集。 一致前缀 可见初始序列的写入。 有界陈旧性 可见所有“旧的”写入。 单调读取 可见不断增加的写入子集。 自己的写入 可见读取者执行的所有写入。 表 1. 六种一致性保证 强一致性特别容易理解。它保证读取操作返回给定对象的最后写入值。如果写操作能够修改或扩展数据对象的部分内容（例如将数据追加到日志），那么读取会返回对该对象应用所有写入后的结果。换句话说，读取观察到所有已完成写入的效果。 最终一致性是最弱的保证，意味着它允许最大的可能返回值集合。对于整个对象的写入，最终一致性读取可以返回过去写入的任何数据对象的值。更一般而言，此类读取可以从接收到数据对象任意写入子集的副本中返回结果。 通过请求一致前缀，读取者可以确保观察到从数据对象的第一次写入开始的有序写入序列。例如，读取可以由一个按顺序从主副本接收写入的副本来响应，但尚未接收到无限数量的最近写入。换句话说，读取者看到的是某一过去时间点主副本中的数据存储版本。这类似于许多数据库管理系统提供的“快照隔离”一致性。 有界陈旧性确保读取结果不会过于过时。通常，陈旧性通过时间段 T（例如 5 分钟）来定义。存储系统保证读取操作将返回任何 T 分钟前写入的值或更近写入的值。或者，一些系统根据缺失写入的数量或数据值的不准确程度来定义陈旧性。我发现时间限制的陈旧性对于应用程序开发者而言是最自然的概念。

Continue reading 

收录了一些做题时看到的奇技淫巧

Continue reading 

写在最前 当你特别在乎性能, 找到一个良好抽象的概念, 打破它, 把脚伸进泥潭里. 传统的数据库都基于posix语义的文件系统来设计的. 当我知道我要在挂着EBS的EC2上跑数据库, 后面还有S3给我做备份, 一切都可以重新设计. 这就是云原生的魅力吧. Background 这二年都上云, 云上都玩儿存算分离. 存算分离导致了数据库服务的磁盘IO负载瓶颈变成了网络IO负载瓶颈, 但为了高可用又到处复制还是搞得写放大严重. 而且为了数据一致性一些同步操作, 二阶段提交(2PC, Two Phase Commit)等操作更是对性能影响严重. Aurora践行日志流即数据库的思想, 通过只持久化预写日志(WAL, Write Ahead Log, 和MySQL中的redo log是一个概念)减少写放大. 还通过单写实例模式避免复杂的共识问题. 设计思想 集群容错 第二章这部分也是分布式系统的老话了, 熟悉这个领域的人一看就懂. 说的其实就是 Quroum + Segmentation (文中称一组复制为PG, Protection Group). Quorum模型, 即在分布式系统中, 每份数据副本都有一票, 共$V$票. 读写操作都需要保证获得的票数大于最小票数限制才可以进行操作. 虽小票数限制要保证: 1.$V_{read} + V_{write} \gt V$; 2. $V_{write} > \frac{V}{2}$. 规则1保证了数据不会被并发读写, 也就保证了读的时候可以读到至少一份最新的数据. 规则2保证了两个写入操作不会同时发生, 这两条规则保证了数据的串行化. 至于Segmentation, 无非就是将上述读写操作的对象拆分(或聚合)成合理的大小, 使之成为系统中检测失效和修复的最小单元. 讨论故障恢复时有两个常见概念: 平均故障发生时间(MTTF, Mean Time to Failure) 和平均故障修复时间(MTTR, Mean Time to Repair).

Continue reading 