OceanBase4.0 跟我学--分布式到底可靠不可靠，到底丢不丢数-- 核心实现

开头还是介绍一下群，如果感兴趣PolarDB ,MongoDB ,MySQL ,PostgreSQL ,Redis, OceanBase, Sql Server等有问题，有需求都可以加群群内有各大数据库行业大咖，可以解决你的问题。加群请联系 liuaustin3 ，（共2610人左右 1 + 2 + 3 + 4 +5 + 6 + 7 + 8 ）(1 2 3 4 5 6群均已爆满，新人进7群300+，8群，准备9群)

抱歉大家，昨天的0ceanBase的活动，太火爆了，早上帖子一发，6:30就有人答题过了60分，本来打算搞3天，但是在打开活动后的8:37活动就只能停止了，人太多了，会OB源代码的客户都来了，银行的大佬也都来了，太卷了，还有答题六遍的，OB开源的真爱粉，搞得我昨天都要神经了。

最后辛苦OB 市场的老师了，一会找人家问，大家开心拿到礼物就好。

这边周五老师会总体统计，下周就有同学可以收到礼物了，感谢OB。

----------------------------------------------------------------

最近一直在学习OceanBase,对于分布式事务中的一些细节还是比较看重的，上一篇的白皮书中提到了，4.0在分布式事务中的改进，尤其2PC的部分。但个人因素，虽然看了多遍，但对于优化的点还是有一些需要再理解和深入的部分，同时对于分布式数据库的事务的稳定性，或者直白的说，丢不丢数这个事情，我也是比较在意的，所以也想通过研究白皮书中的理论来确认，在理论的部分OB在分布式事务中是严谨的。在搜寻中，发现这篇白皮书是针对我关心的部分进行论述的，所以这篇文章应该能确定我的那些疑问。

OceanBase4.0 跟我学--分布式到底可靠不可靠，到底丢不丢数 ---- 什么是PALF

OceanBase4.0 跟我学--分布式到底可靠不可靠，到底丢不丢数 ---- 什么是PALF

这是这篇译文的第二部分

2 背景 

本节简要描述了 OceanBase 数据库的架构，以便为 PALF 的设计提供背景。

2.1 OceanBase 数据库

      OceanBase是一个基于shared noting架构的分布式关系型数据库系统。OceanBase 的主要设计目标包括与传统关系型数据库管理系统 (RDBMS) 的兼容性、可扩展性和容错性。OceanBase 支持 ACID 事务、重做日志归档、备份与恢复、物理备用数据库等多种功能。为了提高数据写入效率，OceanBase 从零开始构建了基于日志结构的合并树 (LSM-tree)的存储引擎，并与事务引擎共同设计。

       事务引擎通过使用悲观记录级锁和多版本并发控制，确保 ACID 属性；它还针对shared nothing架构进行了高度优化。例如，通过改进的两阶段提交过程，分布式事务的提交延迟已经减少到几乎只有一次交互的程度。

       OceanBase 依赖于基于 Paxos 的wal系统来容忍故障，这带来了分布式系统的优势，但同时也增加了日志复制的开销。

2.2 重新设计的架构 

       在 OceanBase 之前的版本（1.0-3.0）中，事务处理、日志记录和数据存储的基本单元是表分区。随着越来越多的应用采用 OceanBase，我们发现之前的架构更适用于大型公司的大规模集群，而不太适合中小型企业。其中一个问题是日志复制的开销。OceanBase 允许用户在每个服务器上创建成千上万的分区，而这些 Paxos 组的数量消耗了大量资源，却没有实际意义，还提升了部署和运维的难度。另一个挑战是大事务问题。这样的事务可能跨越成千上万个分区，这意味着在两阶段提交协议中有成千上万的参与者，这会导致系统不稳定并牺牲性能。

       为了解决这些问题，OceanBase 数据库 4.0 版本的内部架构进行了重新设计 。提出了一个新的组件——Stream，它由多个数据分区、一个复制的WAL日志系统和一个事务引擎组成。Stream 的关键思想是，虽然数据库中的表仍然是分区的，但事务和日志的基本单元是 Stream 中的一组分区，而不是单个分区。表分区仅表示存储引擎中存储的数据的一部分。事务引擎生成redo log，记录 Stream 内多个分区的修改，并将日志存储在该 Stream 的 WAL 中。Stream 会在不同的服务器上创建多个副本，其中只有一个副本会被选举为leader，负责处理数据写入请求。集群中的复制组数量可以减少到服务器的数量，从而消除由大量复制组带来的开销。

通过 Stream 的抽象，OceanBase 数据库 4.0 版本在独立模式下能达到与集中式数据库相媲美的性能（适用于中小型企业），同时可以通过增加机器轻松扩展到分布式集群（适用于大型企业）。在默认设置下，每个服务器上有一个 Stream，其leader会在该服务器上选举产生，因此，多个服务器中不同 Stream 的leader可以同时处理查询，实现了主动-主动架构。除了由leader提供的强一致性服务外，OceanBase 数据库的其他副本还可以在最终一致性保证下提供读取请求。

3 PALF 设计 

       PALF 的设计目的是提供一个复制的wal日志系统，该系统应能够为 OceanBase 数据库提供服务，同时又具有足够的通用性，可用于构建其他分布式系统。

       PALF 的设计目标促成了其架构的形成：采用分层架构来平衡数据库的特定性和日志系统的通用性。数据库特定的需求已被抽象为 PALF 原语，并在不同层次中集成。

      本节首先描述 PALF 作为 OceanBase 数据库的复制 WAL 系统，然后介绍 PALF 提供的接口。最后，详细描述了共识协议的实现。

3.1 复制 WAL 模型 

       在 OceanBase 数据库中，复制日志系统被抽象为一个只追加的日志文件，事务引擎与 PALF 的交互类似于与本地文件的交互。如图 1 所示，事务直接修改内存存储引擎中的数据（步骤 2-3）。因此，事务的大小上限大大扩展，仅受存储引擎容量的限制。然后，日志记录被生成并追加到 PALF（步骤 4）。领导者的事务引擎将 PALF 视为本地日志文件系统，并且只关心日志记录是否已被刷新。PALF 的职责是将leader所做的修改复制到follower（步骤 5）。如果日志已由 PALF 提交，leader将通知事务引擎提交结果（步骤 6），follower将重放leader对自己所做的修改（步骤 7-8）。

      当大多数 PALF 副本将日志持久化后。与某些将leader选举和日志复制绑定在一起的 Paxos 变体不同，PALF 中的leader候选人由一个独立的选举模块选举产生，重新配置模块管理 PALF 组的成员资格（§5.3）。

     在每台服务器上，会激活一个名为 PALFEnv 的 PALF 运行环境，提供远程过程调用（RPC）接口，并管理 PALF 副本的磁盘资源。具体来说，PALF 副本中的所有日志条目都作为多个固定大小的块存储在 LogStorage 中的唯一目录下。MetaStorage 存储元数据信息，如所有 PALF 副本的成员信息。BlockGC 负责修剪不再需要的日志块。所有由 PALF 副本发出的 I/O 请求都由 PALFEnv 中的统一 I/O 工作池处理。

我们将 PALF 与事务引擎之间的交互抽象为接口层。这一做法将数据库特性对 PALF 的影响隔离开，从而提高了 PALF 的通用性。leader中的日志通知器会通知事务引擎日志是否已提交。follower中的日志重放器会将日志条目中的记录变更重放给事务引擎。如果 PALF 副本的角色发生了切换（例如，从leader到follower，或从follower到leader），它会向角色协调器发送角色变更信号，角色协调器再将信号转发到事务引擎，改变其角色。

3.3 系统接口 

图 3 显示了一组与数据相关的 API，省略了系统管理接口，如引导和重新配置。PALF 提供了两种写日志的方法：追加（append）和镜像（mirror）。追加方法将记录 𝑟 提交给 PALF 组的领导者，并返回一个日志序列号（LSN）来标识该日志条目。日志条目的 LSN 是单调递增的，它表示日志条目在日志块中的物理偏移量。变更序列号（CSN）是另一种日志条目标识符，将在 §4.2 中讨论。为了实现高吞吐量，追加方法是异步的。当返回时，事务引擎仅保证该日志条目已分配一个唯一的 LSN，并提交到leader的缓冲区中。事务引擎将通过回调函数 AppendCb 得知该日志条目是否已提交。具体来说，当日志条目被提交并持久化时，方法将被调用成功。

当大多数副本将日志持久化后，日志不会丢失，否则将调用方法失败。PALF 保证每个日志条目的回调函数最多只会被调用一次。

      镜像（mirror）方法提供了另一种wal log到 PALF 的方式，它专为 PALF 组的镜像设计，仅接受由其他 PALF 组提交的日志条目。在同一时间，只有这两种方法中的一种能够写入给定的 PALF 组（见 §5.2）。

     读取方法（read）允许通过给定的 LSN 随机访问日志条目。定位方法（locate）用于将变更序列号（CSN）映射到日志序列号。为了方便在所有副本中进行实时日志消费（例如日志重redo），提供了 monitor_tail 方法来注册一个回调函数 TailCb 来监控 PALF 组的尾部日志。当有新的日志被提交时，PALF 副本会调用该方法通知日志消费者当前日志的尾部位置。RoleCb 函数用于协调 PALF 副本和事务引擎的角色。当 PALF 副本的角色从leader切换为follower（或从follower切换为leader）时，to_follower（to_leader）方法会被调用。最后，trim 方法用于标示在给定 LSN 之前的无用日志条目，BlockGC 负责回收这些日志。

3.4 一致性协议的实现 

       Paxos 协议及其变体被广泛认为可用于解决分布式系统中的一致性问题。Raft 是 Paxos 的典型实现，具有良好的可理解性，为实际系统提供了坚实的基础。PALF 实现了一个强leader的方法，并保留了 Raft 的日志复制机制以简化设计。与 Raft 不同，PALF 将leader选举与一致性协议解耦，使得数据库leader的位置能够灵活调整而不牺牲可用性。更多的差异总结在 §7 中。

leader选举的需求。 

在分布式数据库中，leader的位置几乎影响所有功能，如故障恢复、维护操作和应用偏好。例如，在跨区域部署中，用户通常希望上层应用程序和数据库领导者位于同一区域，以减少延迟。Raft 提供了leader转移扩展来操作leader的位置 。然而，leader权力转移仅在前任leader和期望leader都存活时有效。如果前任leader崩溃，是否能选举出副本作为新leader完全受其存储的日志限制，而不是用户的期望。如果一个能被选举的副本被选为新leader，则依赖外部协调器来检测故障并执行leader权力转移操作。如果协调器崩溃，这种方法可能会给数据库带来可用性风险。

为了解决这个问题，PALF 将leader选举与一致性协议解耦。用户可以灵活地指定副本的优先级，以便选举leader。如果前任leader崩溃，具有第二高优先级的副本将优先被选举为新leader，无需任何外部操作。如果前任leader从故障中恢复，并且其优先级仍高于当前领导者，则领导权可以自动转移回恢复的副本。

角色转换。 在任何给定时刻，每个副本都有四种角色之一：leader、follower、candidate或pending followers。图 4 显示了这些角色及其之间的转换。当副本启动时，它的角色初始化为follower。每个副本会定期轮询选举算法，判断自己是否成为候选人。如果follower发现自己成为候选人，它会切换为候选人角色并执行日志重新确认，然后成为正常的leader。我们将在下面的段落中介绍为什么需要日志重新确认以及其过程。

如果leader发现candidate不再是自己，或者leader收到来自新leader的消息，它会撤销自己的leader权，并切换到pending follower角色。之所以切换到pending follower而不是folloer，是因为在领导权转移之前，事务引擎可能已经将一些日志追加到leader。为了确定这些待定日志的复制结果，前任领导者必须进入待定追随者角色，并等待来自新领导者的日志（§4.1）。在所有待定日志的状态明确之后，该副本将切换为追随者。

领导者选举。候选人通过基于租约的选举算法进行选举，确保不会有两个或更多副本在同一时间被选为候选人。用户可以为副本分配不同的选举优先级，选举算法保证在大多数副本中，优先级最高的副本将被选为候选人。该选举算法本质上是 Basic Paxos 的变体，那个副本在大多数副本中拥有最高优先级达成共识。为确保这一点，每个副本在提议新一轮选举之前会尝试广播其优先级到所有副本；一个副本会响应在一定时间内收到的所有请求中优先级最高的请求。此外，选举算法利用每个副本的单调时间来保证，如果任何多数副本存活，候选人在一定时间内会被选举为leader。本文主要聚焦于复制日志系统的设计，因此我们将选举算法的实现细节留待另文讨论。

日志重新确认。由于灵活的领导者选举，候选人可能比其他副本拥有更少的日志。在接管领导者角色之前，候选人应重新确认前任领导者追加的日志，以确保其日志不少于大多数副本。日志重新确认（算法 1）本质上是 Basic Paxos 的一个完整实例。具体来说，候选人通过 Paxos 准备消息广播高级 ProposalID（领导者任期标识符）𝑝𝑖𝑑 + 1 给所有副本（第 2 行）。每个副本会存储该准备消息中的 𝑝𝑖𝑑，并且只有在准备消息中的 𝑝𝑖𝑑 高于当前副本的 𝑝𝑖𝑑 时，才会回应候选人并返回其日志。

大于副本已看到的最大 ProposalID 𝑝𝑖𝑑𝑚𝑎𝑥（第 9 行）。为了避免传输无用的日志，准备消息的确认仅包含日志的尾部 LSN。一旦候选人收到大多数副本的投票（第 3 行），它开始 Paxos 接受阶段：选择具有最长日志的副本（第 4 行），从该副本获取日志（第 5 行），并将这些日志复制到所有副本（第 6 行）。最后，候选人将一个 StartWorking 日志复制到所有副本（第 8 行）。需要注意的是，StartWorking 日志是一个特殊的重配置日志（§5.3），它用于回滚前领导者可能未提交的成员变更。只要 StartWorking 日志达到大多数副本，候选人就会成为领导者并开始工作。

日志复制。一旦leader成功接管，它将负责日志的复制和提交。PALF 中的日志复制与 Raft 中的机制相似。简而言之，日志条目首先追加到leader，随后由leader复制，follower确认，最后由leader按 LSN 顺序提交。当记录被追加到leader时，日志序列号（LSN）将由日志序列器分配给每个日志条目。LSN 表示日志条目在日志块中存储的物理偏移量。如图 5 所示，LogStorage 中的日志块持续存储日志条目，下一条日志的 LSN 等于当前日志的 LSN 加上日志大小。使用 LSN 来标识日志条目的方式使得客户端可以像操作普通文件一样操作 PALF，并便于数据库中的重做日志消费。

       当日志条目到达follower时，follower不会接受该条目，直到所有前置日志都已被接受。如果现有日志与具有较高提案号的新日志发生冲突，PALF 将按照 Raft 的方式截断冲突的日志。这个机制确保了日志匹配特性 。

      正确性。得益于 Raft 中的安全性论证，我们只需要验证 PALF 是否确保以下属性：选举安全、leader仅追加、日志匹配、leader完整性和状态机安全性。leader仅追加和日志匹配是 PALF 自然提供的，因为它借用了 Raft 的相同日志复制方案。Raft 和 PALF 的主要区别在于日志重新确认。候选人执行 Basic Paxos 实例，从在大多数副本中接受最多日志的副本中学习缺失的日志。如果前任leader提交的日志条目已被大多数副本接受，则该日志条目必须被候选人看到并学习，因此选举安全性和leader完整性得以保证。我们将在 §4.1 中证明状态机安全性，因为它与日志应用到事务引擎的方式有关。

截止今天共发布1272篇文章