从单机到分布式数据库存储系统的演进

日前，字节跳动技术社区 ByteTech 举办的第四期字节跳动技术沙龙圆满落幕，本期沙龙以《字节云数据库架构设计与实战》为主题。在沙龙中，字节跳动基础架构数据库开发工程师马浩翔，跟大家探讨了 《从单机到分布式数据库存储系统的演进》，本文根据分享整理而成。

存储系统概览

存储系统是指能高效存储，持久化用户数据的一系列系统软件。在众多的存储系统中，以下是三类比较主流的存储产品及其特点分析：

块存储

• 底层语义，基于 block 编程；
• 接口朴素：在 Linux 的 IO 软件栈中，要直接使用块存储的话就要基于 LBA 编程，因此接口较为简单朴素，再加上块存储本身处于整个存储软件栈的底层，这导致块存储使用起来并不十分友好；
• 追求低时延、高吞吐：研发一个块存储系统，在设计目标上我们往往会追求超高的性能，体现在超低的时延和超高的吞吐。但考虑到块存储的接口确实过于朴素，往往只有一些追求超高性能的系统才会直接基于块存储构建，然后自建应用层 cache。

对象存储

• 公有云上的王牌存储产品：在 IT 时代，“Everything is data”的趋势迅速催化了对象存储系统。尤其对于字节跳动的业务而言，使用对象存储系统来处理视频、图片、音频等非结构化的数据，语义最为自然；
• 非结构化数据，提供 immutable 语义：一旦图片或视频等非结构化数据上传至对象存储系统成功，则无法对其进行原地修改，只能通过删除旧数据，重新上传新数据的方式完成“修改”逻辑；
• 成本优先：一般不苛求单次操作的时延，但是非常注重系统吞吐 & 存储成本。

文件系统

• 接口语义丰富，普适性强：遵循 POSIX/弱 POSIX 语义，诸如 Open、Write、Read 等许多操作数据的接口都能在文件系统中被找到。
• 拥有较多开源的分布式实现，生态良好。
• 一般也不苛求时延，注重系统吞吐 & 存储成本。

单机数据库存储解析

单机数据库存储，要从内存层和持久化层两个方面来解析。在内存层，仅说关系型数据库，其内存数据结构特点可以总结为：一切都是“树”。我们以最常见的 B+ 树为例，B+ 树具有以下突出的特点：

• In memory 操作效率非常高：B+ 树搜索时间复杂度是 log 级别；并且 B+ 树的叶子节点构成链表，非常有利于在内存中对数据进行 scan 操作。
• 磁盘操作效率高：B+ 树的 Fanout 足够大，树的层级较少，呈矮胖状，可以减少磁盘 IO 数；同时 B+ 树的非叶子节点只存索引数据，叶子节点存实际数据，能大大压缩树高，进一步减少磁盘 IO 数。
• 数据结构高度统一：数据 & 索引都可以直接组织成 B+ 树，因此代码的可维护性、可读性和开发效率都比较好。

仅有内存数据结构当然是不够的，我们还需要设计高效的磁盘数据结构，下图展示了从内存数据结构到磁盘数据结构的数据持久化过程：

左边虚线框描绘的是 In Memory 结构示意图。举个例子，如果我们要修改 Page A 的某一行数据，对其中的一个字段进行自增，自增值是 2。自然而然会产生一个数据库的物理操作日志，即 Redo Log，用来描述我们对 Page A 的修改。同时，在数据库的事务执行过程中，可能还会产生大量临时数据（图里的 Temp data），当内存不够用的时候也需要将其持久化。

右边虚线框描绘的是 In Persistent Layer 的示意图。假设我们使用比较友好的文件系统来将内存数据持久化，我们需要设置不同的文件，让它们各司其职。例如图里的蓝色文件存储 Page，绿色文件存储 Redo Log，粉色文件存储临时数据。如果数据库发生 crash ，在恢复阶段我们就在各类文件中进行数据定位，结合 Redo Log File 和 Page File ，进行数据库的数据恢复。除此之外，如果直接基于块存储进行持久化，就需要数据库本身的存储引擎管理好 LBA，需要在用户态里面实现 buffer cache 等逻辑，这也是可行的。

那么基于单机的 FS / 块存储去做持久化，我们会遇到哪些问题呢？通过下面的单机数据库系统的典型架构图，我们可以发现三个问题：

• 单机容量瓶颈：在 Database 层的单机服务器上运行着 database 进程，服务器上挂载了大量本地磁盘用作数据持久化。但一台物理服务器能挂载的磁盘容量总是有限的，这就导致了单机的容量瓶颈问题。
• 扩缩容困难：当容量、CPU 或者内存等资源不够时，我们需要进行扩容。在单机时代，扩容意味着将数据从这个磁盘搬迁到另一个磁盘。但不管我们是通过网络还是有线连接手段，都需要花费一定的时间，这可能导致业务较长时间的停写（不可用），因此扩缩容是非常困难的。
• 多份独立数据，成本高：如果我们要在“复制集”之间或者主备机之间去做数据冗余或数据同步，那么每新增一分计算能力（新增一个计算节点），就要新增一分存储冗余，就会导致存储成本提高。

分布式数据库存储解析

为了解决单机数据库存储系统面临的问题和挑战，字节跳动的数据库团队调研了一些业界主流的分布式数据库方案。

MyRocks: MySQL + RocksDB

需要说明的是，MyRocks 不是分布式数据库或者分布式解决方案，它是单机 SQL over kv 的典型代表。

• 核心理念：用 RocksDB 替换 InnoDB 。使用 RocksDB 能够有效缓解单机容量瓶颈的问题；
• 特点：一是：数据可压缩比例较高。RocksDB 实现了一种比较优秀的压缩算法，根据实际调研结果显示，在关系型数据库场景，基本上它能实现 2-4 倍的压缩比，能有效缓解单机的容量瓶颈问题。例如，单机原本挂载了 10 块磁盘，只能承载 10 TB 数据，使用 RocksDB 就能在不改变硬件条件下帮助单机承载 20 TB 或 30 TB 等更多的数据；二是，顺序写性能较好，这也是 LSM-Tree 这种数据结构在 HDD 年代出现的核心原因。
• 难点：Compaction 会导致性能抖动，且兼容性一般。众所周知，RocksDB 基于 LSM-Tree 构建，必然会遇到一些典型的 LSM-Tree-based 系统的问题。虽然 RocksDB 对顺序写特别友好，但它一定程度上牺牲了读性能—— RocksDB 在读的过程中会触发 Compaction，可能引发性能抖动，导致前台的写出现卡顿现象；同时，这一类 SQL over kv 解决方案的兼容性能表现较为一般。

Amazon Aurora: 计算存储分离

• 核心理念：计算存储分离，Log is Database。
• 特点：架构灵活，存储层带有特定的数据库计算逻辑，除了具备存储能力之外，还具备 Redo Log 解析、回放生成数据库 Page、维护多版本数据的能力。
• 优势：兼容性强、读扩展能力较优。基于共享存储系统的特点，Amazon Aurora 的读计算节点具备较好的扩展性，能够实现一主 15 备的部署形态，其兼容性、读扩展性表现较好。

Spanner 系: Shared-Nothing

• 核心理念：计算存储分离，且 Share-Nothing。
• 特点：Spanner 系的数据库系统一般基于分布式 k-v 存储构建，由存储层保证事务特性，计算层做成纯计算的无状态节点。
• 难点：要解决当前数据库生态兼容性问题 & 分布式 k-v 系统的 hotspot 问题比较麻烦。

最佳实践：veDB 分布式存储系统

基于上述字节数据库团队的调研结果，我们设计了 veDB 分布式存储系统以解决单机数据库存储系统面临的问题与挑战，本节将主要介绍 veDB 分布式存储系统的系统目标与核心技术特点。

系统目标

在设计理念上，我们期望存储系统能够实现以下四个主要目标：

• 极致弹性：存储节点与计算节点解耦，随时弹性扩缩容；
• 极致易用性：构建 one-size-fits-all 的存储系统，而非专用存储，要能兼容多个主流数据库（MySQL & PostgreSQL & Mongo……）；
• 极致性价比：低时延、低成本；
• 极致可靠性：具备高性能、高可靠的备份恢复能力。

基于以上系统目标，数据库团队设计并开发了 veDB 分布式存储系统，如下图所示：

从图中可以看出，分布式存储层基于 LogStore 和 PageStore 这两个子系统构建，其系统特点与我们的设计目标相互呼应。

• 高弹性：存储层可独立扩缩容，计算层完全不感知；
• 高性价比：在 LogStore 实现了高性能 Log 存储 & 在 PageStore 实现了低成本 Page 存储；
• 兼容性好：LogStore 和 PageStore 都支持多 DB Engine 插件化；
• 高可靠：PageStore 侧支持 Segment 级别的 PITR 功能。

核心技术

以下主要从研发背景（Problem）、解决思路（Solution）、解决成效（Outcome）三个方面来分别介绍 veDB 分布式存储系统的五个核心技术。

Distributed Data Model

Problem：从单机 FS 到分布式存储，需要有高效的数据布局模型。基于单机的文件系统或块存储系统去实现数据持久化是比较简单的，我们可以直接通过申请一批 LBA 或者一批文件来存储数据，然后控制并发即可，但是这对于分布式存储并不容易。从上面的示意图可以看到，最上层的 Tablespace 代表一张数据库表，里面可能包含上百万甚至上千万的 Page data（数据库的基础管理单元）。然而存储系统的管理单元，却不可能是 Page —— Page 的粒度过小，往往只有 KB 级别，如果存储层以过小的粒度去管理数据，可能会造成元数据膨胀，增加管理成本。

Solution：Tablespace -> Segement 分布式映射。基于上述问题，我们可以在存储层利用相对大的管理单元 Segment 去进行数据管理。此时，数据库的管理单元是 Page，存储系统的管理单元是 Segement。Tablespace 和 Segement 之间必然要存在一层映射关系，该映射关系可以根据不同数据库引擎的数据管理空间大小要求进行设置，可能 MySQL 和 PostgreSQL 的映射规则就大不相同。上述示意图展示了最简单的模 2 规则，我们也可以发展出其他更加复杂的打散规则，此处不进行赘述。当我们将 Page 打散到对应的 Segement 之后，数据库就不需要管数据 Replication 的逻辑，不管底层存储是多副本还是 EC 策略，可以完全由存储系统来做透明的 Replication ，数据库就像在使用单机文件系统一样简单。

Outcome

• 天然负载均衡；
• 分布式打散，可最大程度实现并行计算；
• Scale in/out 简单，仅需部分 Segement 数据 rebalance，摒弃了将整个数据库表的 TB 级数据在硬盘间搬迁的繁杂流程。

Log-Only Segement

Problem：数据冗余成本高，需要降低存储成本。

Solution：开发 Log-Only Segement，节省非必要的 Page 副本空间。什么是 Log-only segement? 关系型数据库中往往都包含 Log 数据和 Page 数据。在存储层中，存了多副本的 Log 数据后，我们可以选择性地只回放一部分 Log 数据来生成 Page，让另一部分 Log 数据保持不动，不要生成任何 Page 数据。以上面的示意图为例，Rep_0 和 Rep_1 都是 Log 数据生成的各种版本 Page 数据，然而 Rep_2 是一个空的 Page 数据副本，它里面只有 Redo log。我们都知道 Redo log 和 Page data 的数据大小比例是比较夸张的，Page data 的大小可能是 Redo log 的几倍甚至十几倍，因此通过以上方法能够较大的节省单机的 Page 存储空间。

Outcome：结合单机引擎的压缩算法，能将存储空间放大倍数从 3.x -> 1.x，较好缓解成本问题。

高性能 IO 引擎

Problem：存储层写性能容易成为系统性能瓶颈，如何解决？

Solution：全异步 IO + 无锁结构 +并发打散。当数据库提交了一个 Redo log 到 Log Storage 之后，Log Storage 中会有一个无锁的 Ring buffer 去对 Redo log 进行有序组织，然后我们将 Redo Log 的 Ring buffer 进行线性的定长切割，并发打散到底层存储的 Blob 单元。

Outcome：4KB + depth 8，write latency ~100+us，较好支撑了数据库下发日志的性能刚需。

PITR

PITR（Point-in-time Recovery）是指我们都可以迅速地恢复在过去一段时间内某个时间点的数据库快照。

Problem：如何快速备份恢复，且降低对前台业务影响？

Solution：基于 Segement 的高并发 PITR 机制，Segement 间互不影响。之前提到存储层的管理单元是 Segement ，我们也可以基于 Segement 做备份恢复。这样做有两个好处：首先计算层是完全透明的，计算层完全不会感知，并且计算层的性能不会抖动。其次基于 Segment 可以做到天然的并发打散，因此备份恢复也可以做到并发恢复。

Outcome

• 性能优秀，恢复 1TB 数据 ~15min；
• 扩展性强，不受数据大小影响，性能与数据大小呈近常数关系：因为基于 Segment 单元去做并发备份恢复，每个 Segment 都是独立的，其性能能够与数据大小解耦开来。因此不管数据大小是多少，只要备份恢复资源足够，都能做到常数级的备份恢复性能。

多计算引擎插件化

Problem：数据库团队希望统一的存储层能够支持不同的数据库引擎，做到 100% 兼容和快速接入。

Solution：Write Ahead Log + Log Replay = 任意 Page Data。基于本地存储引擎的 k-v 结构，或者基于裸的块设备抽象出一种相对通用的数据结构，从而高效地存储 Page data。同时，我们在 SDK 侧和 Server 侧都做了 Log parse 的插件化，要接入新的数据库引擎只需要其提供适配存储接口的日志插件，从而可以快速接入各式各样的数据库计算引擎。

Outcome：

• 基于统一接口，计算引擎仅需提供 Log parse + Replay lib 即可接入 veDB 存储层。
• 统一存储层已支持 MySQL、PostgreSQL、MongoDB 计算引擎，目前仍在持续拓展。

数据库存储系统：What's Next

在谈及数据库存储的未来演进时，首先我们可以思考一下哪些因素会触发数据库存储架构的变革和演进？答案可能包含：存储架构自身的革命、数据库理论的突破、或者新硬件冲击引发存储系统架构迭代。基于这三个方向的思考，我们总结了以下几个数据库存储系统的演进趋势：

HTAP/HSAP

我们总结的第一个趋势即 HTAP/HSAP 系统将会逐渐爆发。在 HTAP/HSAP 系统中，“实时”是第一关键词。为了支持实时，存储系统可能会发生架构演进和变革，因此我们需要探索：

• 行列存 All-in-one：既要存储行式的数据，又要存储列式的数据。
• 近实时，写时计算：我们需要在存储层实现写时计算的逻辑来支持实时性。

AI Enhancement

AI 技术运用领域广泛，具体在数据库存储领域，我们可以利用 AI 技术进行以下工作：

• 存储参数调优；
• 智能存储格式：利用 AI 技术进行智能的行存和列存格式转换，AI 可以提醒我们什么时间进行转换，什么时候绝对不能转换，从而避免格式转换为前台业务带来的性能 overhead。

Hardware Revolution

在硬件变革趋势上，我们总结了三个变革方向：

• 存储介质变革：前几年，我们可能更多关注 SSD、HDD。目前我们处于 SSD 往 persistent memory 转变的风口，那么如何利用 persistent memory 去定制软件架构？目前看在文件系统侧已经有一些研究，但是在数据库侧并没有太多公开实践。
• 计算单元变革：CPU 产品已经从 multi-core 变成了 many-core （从 96c 变成了 192c、384c）。要怎么利用多核的能力？对于非计算密集型的存储系统而言，多余的算力能否用来加速数据库算子？一些无锁的数据结构是不是需要要重新设计？以上都需要我们认真考虑。
• 网络设施变革：例如 RDMA ，以及可编程的 P4 交换机这类全新的一些网络设施，可能会对我们的软件架构特别是分布式存储架构造成较大的冲击。相应地，我们需要在存储侧做出调整。