实时分析都靠它→揭秘 YashanDB 列式存储引擎的技术实现

01 概述

YashanDB 列式存储引擎，又称为 LSC（Large-scale Storage Columnar Table)。其通过自研的 CBO 优化器、向量化执行、原生列存格式等技术，达到业界领先的查询分析能力。

YashanDB LSC 是专为海量数据的实时分析场景而设计，致力于实现简单操作、极速分析、实时导入、低成本四个目标。

简单操作

YashanDB LSC 基于 YashanDB 统一平台，在一定程度上降低用户的使用和维护难度；同时 LSC 具备完善的事务能力，支持 MVCC、HA 同步，支持同行表方式进行备份恢复等。

极速分析

YashanDB LSC 依次通过块级过滤、行级过滤减少数据量；然后针对不同数据量和查询需求，智能选择缓存策略、支持小切片合并以提升查询效率，或是灵活采用多种索引和排序技术来加速数据访问。

实时导入

YashanDB LSC 支持批量导入、流式导入以及全实时导入三种方式。最高可达到单 DN 300MB/S 的导入速度，且支持可变列存结构，实现毫秒级的数据导入。

低成本

YashanDB LSC 通过列存压缩编码，以及存算分离等技术实现海量数据的低成本分析。

下面我们将深入探讨 LSC 技术实现原理，并围绕其四大目标以及未来的发展规划进行阐述。

02 融合架构

本章采用整体至局部的叙述方式详细介绍 LSC 结构，依次介绍 LSC 整体架构、LSC 的表结构、LSC 的切片文件格式。

统一存储结构

YashanDB 存储引擎在接口、元数据管理、存储结构、空间管理等方面都是高度融合的。同时在存储引擎的基础组件上是高度统一的，比如事务机制、备份恢复、HA 等等。

存储引擎对外有统一的接口，如支持 DDL 的 create/alter/drop 等操作表结构的接口、DML 等插入、修改、删除记录的接口。行表由于操作主要是单行的，所以接口传递的数据主要是 Row 结构；列表侧重批量处理，其传递的数据是列式的 DataSet 结构。但是不论行表还是列表，我们都提供了单条/批量查询的能力，这为行列混合处理奠定了基础。

在元数据管理上，列表使用了行表同样的系统表来表达，包括分区、索引等的表示都是高度统一的。同时 YashanDB 行表支持采用列式索引来加速，列表也可以使用 Btree 索引，列表的部分列还可以用 Heap 结构来存储。

在数据缓存上，LSC 根据其数据特征扩展实现了变长块缓存。此外实现了本地磁盘缓存来加速存算分离下的数据访问。

在空间管理上，列表扩展了 Tablespace 能力，支持采用 databucket 来管理列表的空间，databucket 是通过目录和文件来进行空间管理的。这与行表 DataFile 基于 Segment/Page 的管理有较大差异。

YashanDB LSC 表支持完善的事务能力，保证事务 ACID 特性，支持 MVCC，支持行表一样的方式来进行备份恢复，支持 HA 同步。

LSC 表结构

LSC 表通过分布/分区/切片(Slice)三层来组织其数据。首先通过分布将数据打散到不同的数据节点，分布实质上是一个一级分区；然后在数据节点内通过分区进一步划分数据，LSC 表支持 Range/List/Hash 等分区方式；在分区内数据由切片组成，切片又可以分为可变切片，内存切片，以及稳态切片。

• 可变切片：支持原地更新，小事务操作，主要针对实时导入等场景。

• 内存切片：主要用于快速导入，导入完成后生成稳态切片。

• 稳态切片：生成后不可修改，采用列式存储，且其数据经过排序，编码，压缩等处理，查询性能非常好，支持标记删除。

切片文件格式

那么切片的数据如何组织呢？这里我们重点介绍下稳态切片的存储格式。稳态切片从逻辑结构展开主要由 SliceMeta、ColumnMeta、ColumnData、BlockData 组成。

• SliceMeta：其中包含切片的格式版本、元数据的 CRC 校验信息，以及每列 Meta 的位置信息。

• ColumnMeta：其中包含切片/块粒度的 MIN/MAX 统计信息、Extent 元数据(Block 的集合)、Block 元数据、布隆过滤器、字典元数据等。

• ColumnData：其中包含某列的所有 Block。

• BlockData Block：数据由 NotNull、Offset、Values 三个向量组成。其中 NotNull 向量和 Offset 向量是可选的，NotNull 向量用于表示列的空值信息，Offset 向量用于记录变长数据的长度信息，以及完成某行数据的快速定位。

切片的物理结构有多种形式，可以根据需要将不同的逻辑部分组合存储。

方式 1：Slice 所有数据一起存储。

方式 2：Slice 的每列单独存储。

方式 3：Slice 的每列的元数据和数据独立存储。

YashanDB 默认采用方式 3，列的元数据和数据独立存储。一个 Slice 存储的例子如下图：

业界已经有很多开源格式了，为什么 YashanDB 还要引入自己的文件格式呢？主要有以下两方面的原因：

一是 YashanDB 的数据格式是专门设计的，与开源格式存在差异，写入和查询时有额外转换的开销，没法做零拷贝等极致优化。

二是方便扩展新的类型和编码，尤其是在一些特定业务场景下，可以结合数据特征达到极致的编码效果。

03 极速分析

在本地三节点测试中，TPC-H 100G 首次执行 35 秒，二次执行接近 22 秒，达到了业界领先的水平。接下来我们将展开介绍 LSC 如何实现快速的查询分析。

在列存的基础下，要实现快速的查询分析，首先需要尽可能的过滤数据，减少需要处理的数据量；其次在加载数据量确定的情况下，考虑如何以最快的速度把数据加载到内存向执行层返回；再次需要考虑在实际导入过程中如何快速的查询；最后还需要考虑分析中的点查场景。下面依次展开介绍具体如何实现。

块级过滤

查询语句的条件下推到存储层，存储可以通过如下方式完成 Block 粒度的过滤。

首先过滤列在 Slice 粒度的 MIN/MAX 统计信息。如果不满足，则说明没有 Block 满足条件，可快速跳过该条件；其次过滤列在 Block 粒度的 MIN/MAX 统计信息，将条件与 MIN/MAX 向量做比较，得到满足条件的 Block 位图；最后过滤列上的布隆过滤器，用于等值条件快速过滤。

MIN/MAX 统计信息也叫 Zonemap，其和布隆过滤器都属于稀疏索引。稀疏索引作为元数据存储在 ColumnMeta 中。

下图展示了一条语句块级过滤过程：

语句“SELECT C1,C3 FROM TABLE WHERE (C1 < 30 OR C1 > 100) AND (C2 = 2 OR C2 = 3)” ，其中 C1 上的条件可以通过 Slice/Block 粒度的 MIN/MAX 统计信息来过滤。C2 列除了用 MIN/MAX 过滤外，还可以使用布隆过滤器来过滤。

另外 C2 列并未出现在最终结果中，所以实际不必向执行层返回其数据。基于稀疏索引的块级过滤，提前将不满足条件的 Block 过滤掉，降低了 IO/解压/解码/行级过滤/结果集生成等步骤的开销，极大的提升了查询性能。

行级过滤

在完成块级过滤后，就可以按照过滤结果将块加载到内存。这时的数据是尚未解码的，在这里可以做不解码数据的行级过滤。对比执行层的过滤，其好处非常明显，一方面降低了解码开销，另外还减少了数据拷贝。

这里以字典编码为例，来说明实现不解码过滤。

字典编码后列数据被转换为字典元数据和编码数据，其中字典元数据包含字典值、字典号、排序号。编码数据中存储的是字典号。

等值条件过滤

等值条件过滤可以基于字典号比较完成。通过字典元数据将条件转为字典号，然后与编码数据的字典号比较，就可以得到满足条件的行位图。

范围条件过滤

由于字典号之间并无大小关系，因而范围条件无法通过字典号比较完成，需要将范围条件通过字典元数据转为排序号，将编码数据也转换为排序号，通过排序号之间的比较就能完成范围条件的比较。

缓存与 IO

那过滤之后，如何将数据快速载入缓存？

在块级过滤时，就需要加载 ColumnMeta，块级过滤完成后加载 ColumnData。最快的加载方式就是数据本身在我们的应用缓存中。

YashanDB LSC 表可根据查询计划自动选择缓存策略，也支持多层次的缓存，如下图：

其中操作系统的 PageCache 可对本地文件系统的数据加速，DiskCache 可针对对象存储等远端数据进行加速，SColDataBuffer 可根据业务场景来缓存数据。

如果数据不在缓存中，那么就需要实际发起 IO 了。这里我们支持根据块过滤的结果，一次性将连续的 Block 读取。尤其在对象存储场景下，可极大提升读取速度。

删除合并

上面都是正常场景下的查询加速手段，那么在导入期间，在有删除的情况下，如何保证快速的分析呢？这里首先就涉及到如何表示删除的问题了。

我们知道行表是每行都有删除事务信息的，其读取时每行都需要做可见性判断。这对于列表是不可接受的，一方面分析场景下删除比较少，通常不需要处理行可见性；另外列表通常批量读取，每列进行事务判断会带来离散 IO，效率非常低下。

YashanDB LSC 表的稳态切片将多个 Block 的删除信息使用一个位图来存储，并且通过 roaring bitmap 来存储，这样读取时只需要一次 IO 就能完成多个 Block 的删除位图读取。如下图：

随着导入的进行，删除的增多，LSC 表会产生一些保护删除空洞的切片，以及一些小切片。这些小切片编码压缩效果差，无法快速批量过滤，且产生很多小 IO。YashanDB 支持小切片合并来提升查询性能，合并是在后台进行的，并且支持资源管控来降低对业务的影响。

点查优化

在实际业务场景中，除了分析常见的批量查询外，还有一些少量数据查询的场景。比如查询明细数据，以及导入或业务执行的 DML 操作。YashanDB 支持多种方式来加速点查：

方式 1：基于 Btree 的主键和索引。

方式 2：用排序键。切片数据按照排序键组织，可以在块和行级别进行快速的二分查找。

方式 3：用稀疏索引。若查找条件不在主键、索引和排序键中，可以采用该方式。

04 实时导入

实时分析对导入的基本诉求是快和实时，下面看看我们如何实现这两个目标。

批量导入

YashanDB LSC 表支持两种批量导入方式：

方式 1：Yasldr 工具导入。用于离线导入场景，通过客户端分批，直连 DN(数据节点)等技术，可达到单 DN 300MB/S 的导入速度。

方式 2：DataX 等工具导入 。用于在线批量导入场景，通过连接 CN（协调节点）来导入，支持完善的事务能力。单 DN 可达到 50MB/S 的导入速度。

在导入时，我们先将数据写入到内存切片进行攒批，然后按批生产稳态切片格式，同时将数据发送给备机，实现了全流程的批量化，并行化处理。

流式导入

YashanDB LSC 表支持通过 Flink 等导数工具来进行流式导入，流式导入关键点是如何高效删除和去重。LSC 表通过 Upsert 索引去重技术和延迟合并删除，可以实现非常高效的删除去重。如下图：

通过 UPSERT 索引来判断重复性，这样一次性完成了索引写入和判重逻辑，接下来只要将老记录删除即可。可以用 YashanDB Btree 专门的 Upsert 接口来支持该操作，Upsert 语义下的导入性能比 Insert on duplicate update 或 Merge Into 等实现更加高效。

YashanDB LSC 表稳态 Slice 的删除信息是合并存储的，因而我们在内存中先对删除信息进行分组合并，然后批量进行删除。这样既避免了删除信息的写放大，也避免删除信息合并存储可能引起的死锁问题。

全实时导入

批量导入和流式导入虽然都实现了在线导入，但是为了避免生成很多小切片文件，影响查询性，对时效性有一定的约束。YashanDB LSC 表支持可变列存结构实现毫秒级的数据导入。

可变列存是一种可以原地更新的列存结构，支持行级事务，因而可以实现无限制的实时导入。并且支持 All in mem 的表空间来加速可变列存的导入和查询。

05 低成本

分析场景下数据量通常都很大，且分析业务的执行通常不是持续稳定的。在这种场景下可以通过一些技术来降低业务的成本，提高资源的有效利用率。

编码压缩

编码压缩不仅可以帮助提升查询性能，还可以大幅降低成本。

YashanDB LSC 表支持如下编码方式：

• 数值/时间类型，支持 Rle/Delta 编码。

• Decimal 类型，支持 Decimal32/Decimal64/Decimal128/Byte-Packed 编码。

• 字符串类型，支持字典/前缀编码。

在切片生成时会自动根据数据特征选择编码类型，无需用户指定。

YashanDB LSC 支持 ZSTD/LZ4 压缩算法，针对每个压缩算法可以配置高/中/低三种压缩等级；支持在数据库、表、列等粒度指定压缩算法；默认采用 LZ4(low)压缩方法。

在 TPCH 场景下测试，ZSTD 最大压缩比约为 5:1, LZ4 也能达到 3:1。大幅降低了数据的存储和访问成本。

对象存储

另一个能大幅降低成本的技术是对象存储的使用。

YashanDB LSC 表的稳态列存在写入后是不会修改的，非常适合使用对象存储。另外结合数据访问策略，可以将部分热点数据放在本地，非热点数据存入对象存储。对象存储的数据还可以通过本地磁盘缓存来进行加速。

这样从整体上达到性能不下降，存储成本大幅下降的好处。同时还实现了数据的集中管理。

此外通过对象存储分离存储，可实现计算节点的无状态化。如上图中的 PN 节点，其本身不持久化任何数据，元数据通过 DN 获取，数据从对象存储获取，因而可以根据业务需要快速的扩缩。从而大幅降低业务成本。

06 展望

YashanDB 列式存储引擎未来也将持续提升核心竞争力和产品成熟度，在高并发、低延时、检索等能力上继续完善。其架构会沿着存算分离，湖仓方向持续演进。

本文源自 Meetup 第 16 期实时数仓专场直播，相关视频可咨询官方助手号获取视频链接。若有更多想听的、想看的内容，也可以在评论区告诉我们~