XJC's Journal Container

TL, DR 能原地扩容就原地扩容, 不能的时候就迁移. 迁移的本质是一个 bin packing problem. Aurora 采用了反应式MCDM迁移决策算法, 但具体的屁都没说. Intro 无服务器这个需求很容易理解. 没有Serverless, 用户需要自己预估工作负载购买合理容量的计算资源, 设计扩容缩容策略, 甚至还要自己负责安全, 软件更新, OS tuning等等工作. 并不是所有用户都有精力自己搞定这些, 相当一部分用户更愿意专注在业务逻辑的开发上, 这有助于他们早日实现生意的成功. Aurora Serverless中将资源抽象为了ACU, 一个ACU定义为2GB内存以及与之配套的CPU, 网络, IOPS等计算资源的集合. 用户只需要指定资源用量(预算)上下界, 然后就可以开使干活儿了. 当然, Serverless只是一个用户视角的称呼, 服务器并不是真的消失不见了. 真正的服务仍然运行在某一台机器中, 云服务提供商需要来负责orchestration. Aurora Serverless的论文里主要讨论了两个问题的解决方案: 1) 什么时候扩容/缩容. 2) 扩缩容时发生需要迁移的情况时, 把谁迁移到哪儿? 在Aurora中, 这两个问题由Fleet级的决策系统和Host级的决策系统的组合来解决. 开始讨论之前先澄清一些词汇. Fleet: 一组物理机器组成的集群, 每个AZ都有一个fleet. Host: 一台物理机. Instance: 一台VM. Fleet级 迁移 舰队资源管理器的一个重要的职责是定期轮询监控实例的情况, 并执行以下三步: 1. 决定哪些主机需要迁出 对于每个主机, 舰队管理器会通过定期查看该主机上的每个实例的预留ACU的和是否超过了阈值(多少没说)判断主机是否过热, 过热就迁出. 论文里说了判断过热后会继续判断是否有足够网络带宽自持迁出, 但也没说不支持的时候会怎么办. 2. 决定从主机上迁出哪些实例 考量有3: CPU,网络占用大的可能合适. memory map大小和脏页率影响迁移时间. 公平, 不要频繁迁移一个实例.

Continue reading 

Resource Management in Aurora Serverless 摘要 Amazon Aurora Serverless 是 Amazon Aurora 的一种按需自动扩展配置，完全兼容 MySQL 和 PostgreSQL。它根据客户数据库应用程序的需求自动提供容量扩展/缩减(即垂直扩展)。通过这种方式，它使客户无需显式管理其数据库容量；客户只需使用一个简单易懂的多资源容量抽象概念——Aurora 容量单位(ACU)来指定最小和最大边界。对于工作负载随时间变化的客户，由于其灵活和细粒度的扩展以及基于使用的计费模式，与预置的 Aurora 或其他替代方案相比，它可以节省成本。本文描述了 Aurora Serverless 资源管理的关键思想。为了帮助实现其目标，Aurora Serverless 采用并微调了与资源过度订阅相关的成熟思想；基于近期测量的反应式控制；分布式和分层决策；以及数据库引擎、操作系统和虚拟机管理程序在效率方面的创新。也许最具挑战性的目标是在以高度利用率运行主机的同时提供一致的资源弹性体验。Aurora Serverless 实现了几个新颖的想法，以在这些相互对立的需求之间取得平衡。其将工作负载映射到主机的技术确保在常见情况下，主机内有足够的备用容量来支持工作负载的快速扩展。在罕见的情况下，如果不是这样，它被设计为实时迁移工作负载以确保无缝扩展。其负载分配策略的特点是跨主机"不平衡"负载，以实现灵活的实时迁移。最后，它采用基于令牌桶的速率调节机制，以防止不断增长的工作负载在基于实时迁移的补救措施之前使其主机饱和。 1 引言和动机 Amazon Aurora [1] 是一种现代关系数据库服务，为完全开源的 MySQL 和 PostgreSQL 兼容版本提供大规模的性能和高可用性保证 [37]。2014 年推出的原始预置 Aurora 产品允许客户选择按需实例（虚拟机），按小时付费使用数据库，无需长期承诺或预付费用，或选择预留实例以获得额外优惠 [2]。最近，Amazon 开始提供 Aurora Serverless [3]，这是 Amazon Aurora 的一种按需自动扩展配置。Aurora 提供的自动扩展能力是向上/向下扩展（即单个数据库实例分配资源的"垂直"扩展），而不是某些其他系统提供的横向扩展（“水平"扩展）。Aurora Serverless 旨在快速扩展数据库工作负载，从每秒数百次事务到数十万次事务。第一个 Aurora Serverless 产品（ASv1）于 2018 年 8 月推出，而最新产品（ASv2）于 2022 年 4 月发布。 为什么选择 Aurora Serverless？Aurora Serverless 的主要卖点是它在很大程度上减轻了客户管理其数据库资源容量如何响应动态工作负载的需求。客户无需预先选择特定的实例大小或配置，只需以称为 Aurora 容量单位（ACU）[4] 的单位指定数据库容量。每个 ACU 是 2 GB 内存、相应的 CPU、网络和块设备 I/O 吞吐量的组合。Aurora Serverless 根据应用程序需求，在客户指定的（最小，最大）ACU 范围内持续自动扩展客户数据库集群中的每个写入器或读取器。与预置的 Aurora 或其他替代方案相比，Aurora Serverless 因以下原因带来的成本节省和便利性而吸引各种客户：

Continue reading 

时间: 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 