一、背景

传统的关系型数据库有着悠久的历史，从上世纪60年代开始就已经在航空领域发挥作用。因为其严谨的强一致保证以及通用的关系型数据模型接口，获得了越来越多的应用，大有一统天下的气势。

2000年以后，随着互联网应用的出现，很多场景下，并不需要传统关系型数据库提供的强一致性以及关系型数据模型。相反，由于快速膨胀和变化的业务场景，对可扩展性(Scalability)以及可靠性(Reliable)更加需要，而这个又正是传统关系型数据库的弱点。

自然地，新的适合这种业务特点的数据库出现，就是我们常说的NoSQL。但是由于缺乏强一致性及事务支持，很多业务场景被NoSQL拒之门外。同时，缺乏统一的高级的数据模型，访问接口，又让业务代码承担了更多的负担。数据库的历史就这样经历了否定之否定，又螺旋上升的过程。而这一次，鱼和熊掌我们都要。

PolarDB就是在这种背景下出现的，由阿里巴巴自主研发的下一代关系型分布式云原生数据库。在兼容传统数据库生态的同时，突破了传统单机硬件的限制，为用户提供大容量，高性能，极致弹性的数据库服务。

二、核心技术之共享存储

PolarDB采用了Share Storage的整体架构。采用RDMA高速网络互连的众多Chunk Server一起向上层计算节点提供块设备服务。一个集群可以支持一个Primary和多个Secondary节点，分别以读写和只读的挂载模式通过RDMA挂载在Chunk Server上。PolarDB的计算节点通过libpfs挂载在PolarStores上，数据按照Chunk为单位拆分，再通过本机的PolarSwritch分发到对应的ChunkServer。每个ChunkServer维护一组Chunk副本，并通过ParallelRaft保证副本间的一致性。PolarCtl则负责维护和更新整个集群的元信息。

• Bypass Kernel

PolarDB诞生于2015年，由于RDMA高速网络的出现，使得网络带宽接近于总线带宽。PoalrDB作出大胆的假设，那就是未来数据库的瓶颈将由网络转向软件栈自己。因此PolarStore中采用了大量的Bypass Kernel的设计。首先是新硬件的使用，NVME和RDMA的使用，摆脱了IO访问过程中的用户态内核态交互。

软件设计中，在绑定CPU，非阻塞IO的模式下， 通过状态机代替操作系统的线程调度，达到Bypass Kernel的目的。

• ParallelRaft

PolarStore中采用三副本的方式来保证数据的高可用，需要保证副本间的一致性。工业界有成熟的Raft协议及实现，但Raft由于对可理解的追求，要求顺序确认以及顺序提交。而副本的确认提交速度会直接影响整个PolarStore的性能。为了获得更好的访问速度，PolarStore提出了ParallelRaft协议，在Raft协议的框架下，利用块设备访问模式中方便判定访问冲突的特点，允许一定程度的乱序确认和乱序提交，如下图所示：在所有已经确认提案中，那些对前序访问有访问Range冲突的提案会被暂时Block，而没有冲突的提案会进入Ready状态并commit，commit以后的提案会继续反馈给当前的Scheduler，之前被Block的提案有可能会进入Ready状态，进而继续被提交。

三、核心技术之物理复制

采用了共享存储的模式之后，Secondary上依然需要从Primary来的复制逻辑来刷新内存结构，如果Buffer Pool以及各种Cache。但是，由于读写节点和只读节点访问的是同一份数据，传统的基于binlog的逻辑复制方式不再可用，这时由于逻辑复制由于最终执行顺序的变化，导致主从之间不同的物理数据结构。因此DB层基于Redo Log的物理复制的支持是必不可少的：

不同于逻辑复制自上而下的复制方式，物理复制的复制方式是自下而上的，从共享存储中读取并重放REDO，重放过程会直接修改Buffer Pool中的Page，同步B+Tree及事务信息，更新Secondary上的各种内存Cache。除了支持共享存储外，物理复制还可以减少一份日志写。同时，由于整个复制过程不需要等到事务提交才能开始，显著地减少了复制延迟：

四、交易场景优化

针对双十一峰值交易场景，PolarDB也做了大量优化。

• Blink Tree

在峰值交易场景中，会有大量涉及热点page的更新及访问，会导致大量关于这些热点Page的SMO操作，

之前PolarDB在SMO场景下由于B+Tree实现有如下的加锁限制：

• 同一时刻整个B+Tree 有且只能有一个SMO在进行；
• 正在做SMO的B+Tree分支上的读取操作会被阻塞直到整个smo完成。

针对这个问题PolarDB做了如下优化：

• 通过优化加锁，支持同一时刻有多个SMO同时进行，这样原本等待在其他分支做SMO的插入操作就无需等待，从而提高写入性能；
• 引入Blink Tree来替换B+Tree并通过缩小SMO的加锁粒度，将原本需要将所有涉及SMO的各层Page加锁直到整个SMO完成后才释放的逻辑，优化成Ladder Latch，即逐层加锁，修改完一层即可放锁然后去加上一层Page锁继续修改。这样原本被SMO阻塞的读操作会有机会在SMO中间进来：通过对每个节点增加一个后继链接的方式，使得在Page Split的中间状态也可以完成对Page安全的访问，如下图所示，传统的B+ Tree必须通过一把锁来Block整个Page Split过程中对所影响的Page的访问。而Blink Tree则不需要，即使Split还在进行中，父节点到子节点的链接还没有完成建立，依然可以通过前一个节点的后继链接找到正确的子节点。并且通过特殊处理确保访问到正确的Page，从而提高读取性能。
  

通过这些对B+ Tree的优化，可以实现交易场景PolarDB读写性能提升20%。

• Simulated AIO

InnoDB中有simulated AIO的逻辑，用于支持运行在不包含AIO的系统下，PolarDB下的共享存储文件系统就是没有AIO的，所以采用的是simulated AIO的逻辑。

但是原版中的simulated AIO是基于本地存储设计的，与分布式存储的特性并不适配。为了进行IO合并，原版的simulated IO设计，将所有异步IO请求按照目标地址进行组织，存放在同一个IO数组中，方便将目标地址连续的小IO合并成大IO来操作，以提升IO的吞吐。

但是这个设计与分布式存储是不相适配的，连续的大IO操作，会使得同一时刻，只有一个或少量存储节点处在服务状态，浪费了其他存储节点的作用；另外，分布式存储的网络延迟较大，高负载下，网络中的Inflight IO会较多，IO组中的IO请求数量也会很多，而这种组织方式下，IO数组中的槽位状态都无序的，往数组中添加IO请求和移除IO请求的开销都很大。

所以，PolarDB在高负载下的性能比较差且不稳定，为此PolarDB专门对simulated AIO进行了重新的设计，主要包括：

a.合理地选择IO合并和拆解，充分利分布式存储的多节点优势；

b.建立状态有序的IO服务队列，减少高负载下的IO服务开销。

重新设计下，性能提升了很多

稳定性也有了很大的提升

• Partitioned Lock System

PolarDB采用的是2PL + MVCC的并发控制方式。也就是用多版本数据构建Snapshot来服务读请求，从而避免读写之间的访问冲突。而读写之间的冲突需要通过两阶段锁来保证，包括表锁，记录锁，谓词锁等。每当需要加锁的时候，之前的做法都需要去log_sys中先获得一把全局的mutex保护。在峰值的交易场景中，大量的写入会导致这个地方的mutex成为瓶颈。因此PolarDB采取了Partition Lock System的方式，将log_sys改造成由多个LockSysShard组成，每个Shard中都有自己局部的mutex，从而将这个瓶颈打散。尤其是在这种大压力的写入场景下明显的提升写入性能。

• Lockless Transaction System

PolarDB中支持Snapshot Isolation的隔离级别，通过保留使用的Undo版本信息来支持对不同版本的记录的访问，即MVCC。而实现MVCC需要事务系统有能力跟踪当前Active及已经Commit的事务信息。在之前的实现中每当有写事务开始时，需要分配一个事务ID，并将这个ID添加到Transaction System中的一个活跃事务列表中。当有读请求需要访问数据时，会首先分配一个ReadView，其中包括当前已分配最大的事务ID，以及当前这个活跃事务列表的一个备份。每当读请求访问数据时，会通过从Index开始的Roll ptr访问到这个记录所有的历史版本，通过对比某个历史版本的事务ID和自己ReadView中的活跃事务列表，可以判断是不是需要的版本。

然而，这就导致每当有读事务开始时，都需要在整个拷贝过程对这个活跃事务列表加锁，从而阻塞了新的写事务将自己的ID加入。同样写事务和写事务之间也有访问活跃事务列表的冲突。从而活跃事务列表在这里变成一个明显的性能瓶颈，在双十一这种大压力的读写场景下尤为明显。

对此，我们将Tansaction System中的这个活跃事务列表改造成无锁Hash实现，写事务添加ID以及读事务拷贝到ReadView都可以并发进行。大大提升了性能。