Google Spanner架构上的分布式PostgreSQL - 存储层

Google Spanner架构上的分布式PostgreSQL ---存储层

Sid Choudhury BlockedUnblockFollow关注3月18日

在这篇文章中，我们将深入探讨 YugaByte DB 的分布式存储层架构，该架构受Google Spanner设计的启发。我们后续的文章介绍了 查询层 ，其中存储层将PostgreSQL作为SQL API。最后，请留意后续帖子，重点介绍我们在设计YugaByte DB的 SQL 功能时学到的经验教训。

逻辑架构

YugaByte DB由 两个逻辑层组成 ，每个 层 都是在多个节点（或Kubernetes的情况下为pod）上运行的分布式服务。

YugaByte查询层（YQL）构成YugaByte DB的上层，应用程序使用客户端驱动程序进行交互。 YQL处理API特定方面（例如查询编译，数据类型表示，内置函数等）。它在构建时考虑了可扩展性，并支持两个API，即 YugaByte SQL 或YSQL（PostgreSQL兼容）和 YugaByte Cloud QL 或YCQL（具有Cassandra QL根）。

DocDB 是一个由Google Spanner启发的高性能分布式文档存储，作为下层。它提供了强大的一致性语义，包括单行线性化以及多行ACID事务（当前具有快照隔离，并且在不久的将来可以进行可序列化隔离）。最近成功进行了Jepsen测试，对各种失败具有很强的适应能力（请尽快收到官方公告）。

为什么Google Spanner会成为DocDB的灵感来源？

为了支持其地理分布式随机访问OLTP工作负载（想想Gmail，日历，AdWords，Google Play等），Google构建了Spanner，可以说是世界上第一个全球一致的数据库。尽管它在2012年作为 设计论文 首次引入全球，但是Spanner的工作在2007年早些时候开始。最初，Spanner只提供了一个键值API，同时支持分布式事务，外部一致性和跨数据的透明故障转移中心。从那时起，它已发展成为 一个全球分布式，基于SQL的RDBMS ，如今几乎支持Google的所有关键任务服务。 Spanner系统的一个子集于2017年在Google Cloud Platform上公开发布，作为名为Google Cloud Spanner的专有托管服务。

DocDB的分片，复制和交易设计受到Spanner论文中概述的设计的启发。 此选择的最重要的好处是，数据库的任何单个组件都不会成为地理分布式随机访问基于SQL的OLTP工作负载的性能或可用性瓶颈。 其他论文中提出的交易数据库设计，如耶鲁大学的 卡尔文 ，亚马逊的 Aurora 和谷歌的 过滤器， 都无法保证这一优势。用于加尔文交易处理的单一全球共识领导者本身可能成为瓶颈。此外， 在Calvin中不可能使用 关键的SQL构造，例如长时间运行的会话事务和高性能的二级索引。亚马逊的Aurora在分布式存储层上使用单片SQL层，因此缺乏水平写入可扩展性。最后， Google 构建Spanner 的主要理由 是解决Percolator中缺少低延迟分布式事务的问题。

DocDB如何工作？

DocDB中的数据存储在表中。每个表由行组成，每行包含一个键和一个文档。 DocDB围绕4个主要设计原则构建。正如前一节所强调的那样，前3个受到Spanner架构的启发，而最终原则是确保高性能和灵活存储系统的关键。

• 表的透明分片
• 碎片数据的复制
• 跨分片的事务（又称分布式事务）
• 基于文档的行持久性

表的透明分片

用户表由DocDB隐式管理为多个分片。这些碎片称为平板电脑。表中每行的主键唯一地确定了行所在的平板电脑。将数据划分为平板电脑的策略有不同，下面概述了几个。

基于散列的数据分区方案计算每行的分区ID。这是通过计算表的主键列（或其子集）的散列值来实现的。此策略可在整个节点集中生成均匀的分布数据和查询。它非常适合需要低延迟，高吞吐量和处理大型数据集的应用。但是，此方案不适用于范围查询，其中应用程序希望列出较低和上限之间的所有键或值。

您可以在下图中看到此分区方案的示例。每行所属的分区由唯一颜色表示。因此，我们将下面的7行表分成3个平板电脑，每行都落入随机分区。 基于散列的数据分区

基于范围的数据分区方案按主键的自然顺序对表进行分区。此策略允许应用程序执行有效的范围查询，其中应用程序要查找下限和上限之间的所有值。然而，该方案可能导致数据的不均匀分割，这需要频繁地对片剂进行动态重新分区。此外，根据访问模式，此方案可能无法均衡地平衡所有节点上的查询。 基于范围的数据分区

DocDB目前支持散列分区方案，并且在工作中积极支持范围分区。

碎片的复制---单行线性化

DocDB跨多个节点复制每个平板电脑中的数据，使平板电脑具有容错能力。平板电脑的每个副本称为平板电脑同行。容错（或FT）是平板电脑在继续保持数据正确性的同时可以存活的最大节点故障数。复制因子（或RF）是YugaByte数据库Universe中的数据副本数。 FT和RF高度相关 - 为了在k故障中存活，RF应配置为2k + 1。

作为一个高度一致的数据库核心，DocDB的复制模型使单键更新即使在出现故障时也可线性化。线性化是最强的单密钥一致性模型之一，并暗示每个操作似乎以原子方式进行，并且以某些完全线性顺序进行，这与这些操作的实时 排序 一致。

使用分布式一致性算法在各种平板电脑对等体上复制平板电脑数据。一致性算法允许一组机器就一系列值达成一致，即使这些机器中的一些可能会失败。 Raft 和Paxos是众所周知的分布式共识算法，并且已被正式证明是安全的。扳手使用Paxos。但是，我们之所以选择Raft，是因为它比Paxos 更容易理解 ，并提供了动态更改成员资格等关键功能。

领导租赁

实现容错分布式存储系统的最直接方式是通过上面讨论的分布式一致性算法之一将其实现为复制状态机。状态机上的每个操作都将通过共识模块，以确保状态机的所有副本都同意操作及其应用顺序。

然而，大多数实际系统（例如： Paxos Made Live 和 Paxos Made Simple ）只需要通过共识模块执行写入操作，同时允许Raft组的领导者提供读取操作，这样做会稍微好一些，这将得到保证拥有所有最新值。由于Raft组中的不同对等体可能以不同的方式运行（具有不同的领导者），因此多个对等体可能同时认为自己是领导者（针对不同的术语）。为了确保系统只允许读取与最新术语相对应的领导者的价值，Raft文件建议领导者 - 在回应阅读操作之前 - 应与大多数同行沟通以确认领导力最新的一期。

这种方法的主要缺点是读取性能可能会受到影响，尤其是在地理分布式集群中。 YugaByte DB通过使用 Leader Leases克服了这种性能限制，这是另一种确保读取仅由最新领导者提供服务的方法。这可确保您可以从领导者读取数据，而无需往返任何其他节点。领导者租赁机制保证在任何时间点，任何平板电脑的Raft组中最多只有一台服务器认为自己是最新的领导者，可以提供一致的读取或接受写入请求。换句话说，如果没有领导者租约，可能会发生陈旧的读取，因为被分区的旧领导者可能会提供一致的读取请求，认为它仍然是领导者。

通过领导租约，新当选的领导者在获得领导租约之前不能提供阅读（或接受写入）。在领导人选举期间，选民必须将该选民所知道的老领导人的最长剩余持续时间传播给他投票的新候选人。在获得多数选票后，新领导人必须等待旧领导人的租约期限才能认为自己有租约。这位老领导人在其领导人租约到期后退出，不再担任领导职务。作为Raft复制的一部分，新领导者不断扩展其领导租约。

请注意，领导者租约不依赖于任何类型的时钟同步或原子钟，因为只有时间间隔通过网络发送。每个服务器都以其本地单调时钟运行。时钟实现的唯一两个要求是：

• 不同服务器之间的有限单调时钟漂移率。例如，如果我们使用低于每秒500μs漂移率的标准 Linux 假设，我们可以通过将上述所有延迟乘以1.001来解释它。
• 单调时钟不会冻结。例如，如果我们在临时冻结的VM上运行，则管理程序在重新开始运行时需要从硬件时钟刷新VM的时钟。

跨越碎片的交易---多行分布式交易

分布式ACID事务修改多个分片中的多个行。 DocDB支持分布式事务，支持强一致的二级索引和多表/行ACID操作等功能。

让我们举个例子，看看这个例子中的架构。下面是一个简单的分布式事务，它更新了两个密钥k1和k2。

BEGIN TRANSACTION`

 UPDATE k1`

 UPDATE k2`

COMMIT`

我们已经从前面的章节中了解到（在一般情况下）这些密钥可以属于两个不同的平板电脑 - 每个平板电脑都有自己的Raft组，它们可以存在于一组单独的节点上。所以问题现在归结为原子地更新两个单独的Raft组。原子地更新两个Raft组要求两个Raft组的领导者（接受这些键的写入和读取）同意以下内容：

• 使密钥在同一物理时间对最终用户可读
• 一旦写入操作被确认为成功，则密钥应该是可读的

请注意，我们还没有讨论处理冲突，这些冲突是来自另一个事务的重叠部分更新。

在相同物理时间跨两个节点进行更新需要一个可以跨节点同步时间的时钟，这不是一件容易的事。 Google Spanner使用的 TrueTime 是高度可用的全局同步时钟的示例，具有严格的误差范围。但是，许多部署中都没有此类时钟。定期可用的 物理时钟 不能在节点之间完美同步，因此无法跨节点提供排序。

使用筏和混合逻辑时钟（HLC）消除对TrueTime的需求

DocDB不使用TrueTime，而是使用Raft操作ID和 混合逻辑时钟（HLC）的组合 。 HLC将粗略同步的物理时钟（使用NTP）与追踪因果关系的Lamport时钟相结合。集群中的每个节点首先计算其HLC。 HLC表示为 （物理时间组件，逻辑组件）元组 ，如下图所示。通过单调增加的计数器实现在粗略同步的物理时间间隔内的事件的更细粒度排序。

一旦HLC在每个节点上可用，DocDB就会利用Raft操作ID和HLC时间戳（两者都由平板电脑领导者发布）是严格单调的序列。因此，YugaByte DB首先在该平板电脑的Raft领导者（包括物理时间组件和逻辑组件）上建立Raft操作id（由术语和索引组成）和相应HLC之间的一对一关联。将每个条目的两个值写入Raft日志。

因此，HLC可以用作Raft操作id的代理。 集群中的HLC充当分布式全局时钟，在独立的Raft组之间进行粗略同步。 仅使用Raft操作ID就不可能实现这一点。因此，我们现在有一个独立节点可以达成一致的物理时间概念。

问题的第二部分是节点应该提供读取。这是通过使用HLC来跟踪 读取点 来实现的。读取点确定最终客户端应该可以看到哪些更新。在单行更新的情况下，领导者向更新发出HLC值。根据Raft协议安全地复制到大多数节点上的更新可以被认为对客户端是成功的，并且可以安全地为该HLC提供所有读取。这构成了DocDB中多版本并发控制（MVCC）的基础。

对于分布式事务，节点将处于挂起状态和临时记录中的事务记录。有关 分布式事务如何在YugaByte DB中工作 的单独帖子中详细介绍了这一点 。 当事务记录更新为已提交状态时，将为事务分配提交HLC。当该HLC值变得安全以便为客户端提供服务时，该事务将以原子方式对终端客户端可见。请注意， 确定可以提供读取的安全时间 的确切算法更复杂，并且是一个全新帖子的主题。

基于文档的行持久性

在上一节中，我们研究了如何在容错的同时以强一致性复制每个平板电脑中的数据。下一步是以对读写高效的方式将其保存在每个平板电脑对等体的本地文档存储中。 DocDB本地存储使用 RocksDB 的高度自定义版本，这是一种基于日志结构的合并树（LSM）的键值存储。我们显着 增强了 RocksDB，以实现规模和性能。

DocDB中文档的确切持久性如何？我们来看一个示例文档，如下所示。

DocumentKey1 = {`

 SubKey1 = {`

 SubKey2 = Value1`

 SubKey3 = Value2`

 },`

 SubKey4 = Value3 }`

在此示例中，名为 DocKey 的文档密钥具有值 DocumentKey1 。对于每个文档密钥，存在可变数量的子密钥。在上面的示例中，文档的子键是 SubKey1, SubKey1.SubKey2, SubKey1.SubKey3 和 SubKey4 。这些子密钥中的每一个都根据下面显示的序列化格式进行编码。

序列化一个或多个文档产生的字节缓冲区是 前缀压缩的 ，以便有效地存储在内存（块缓存）或磁盘（文件）上。 DocDB高效支持以下操作：

• 替换整个文档
• 从文档更新属性的子集
• 查询整个文档或仅查询属性的子集
• 在文档中比较和设置操作
• 扫描文档内或文档中的内容

SQL表中的每一行都对应于DocDB中的文档。由于DocDB允许对单个文档属性进行细粒度更新和查找，因此可以非常有效地更新和查询SQL表中行的列。有关其工作原理的详细信息将在本系列的后续部分中介绍。

摘要

将Google Spanner架构融入开源，云原生基础架构的世界，同时保留高性能特征，至少可以说是令人兴奋的工程之旅。除此之外，还有机会重用和扩展成熟的SQL层，例如PostgreSQL。众所周知的"糖果店里的孩子"的感觉对我们来说非常真实

在 本系列 的 下一篇文章中 ，我们将详细介绍我们如何重用PostgreSQL的查询层并使其在DocDB上运行。在后续文章中，我们将重点介绍我们在过去3年多来构建这样一个"Spanner meet PostgreSQL"数据库时所学到的经验教训。

下一步是什么？

• 将 YugaByte DB与 CockroachDB ，Google Cloud Spanner和 MongoDB 等数据库进行深入 比较 。
• 在macOS，Linux，Docker和Kubernetes上 开始 使用YugaByte DB。
• 联系我们 以了解有关许可，定价或安排技术概述的更多信息。

查看英文原文

查看更多文章

公众号：银河系1号

联系邮箱：public@space-explore.com

（未经同意，请勿转载）