【金猿技术展】一种分布式 HTAP 数据库上基于索引的数据任意分布方法——为 HTAP 数据库实现 Collocation 优化

PingCAP技术

本项目由PingCAP投递并参与“数据猿年度金猿策划活动——2022大数据产业创新技术突破榜单及奖项”评选。

‍数据智能产业创新服务媒体

——聚焦数智 · 改变商业

本技术提供了一种数据处理方法，涉及数据库技术领域。该方法包括：接收数据查询请求，并确定数据查询请求对应的目标数据表；从多个重分布索引中确定与目标数据表对应的目标索引；其中，重分布索引中的数据是基于重分布索引的索引列分布存储在分布式数据库中的；当针对数据查询请求的操作指向目标索引的索引列时，根据目标索引，对原始执行计划进行优化，生成目标执行计划；针对数据查询请求的操作包括单表聚合操作和/或多表关联操作；运行目标执行计划，得到数据查询请求对应的查询结果。本技术实现了查询优化，减少了跨节点的数据交换操作，提高了数据处理的效率，提升整个分布式数据库的性能。

技术说明

HTAP（混合事务和分析处理）是近年来提出的一种新型的数据库架构，旨在打破事务处理和分析之间界限， 在一份数据上保证事务处理的同时支持实时分析，并且可以灵活配置两种负载的资源占比，使得在线交易和分析互不影响，并可以分别实现线性扩展，一站式地解决企业级应用的各种需求，从而大幅度降低成本，同时提高了企业决策的效率。当前，HTAP 已成为数据库发展的前沿领域。

TiDB HTAP 采用了事务处理与分析查询物理分离的架构，同一份数据根据业务的需要，在后台进行自动的行式存储到列式存储的转换以分别响应 OLTP 和 OLAP 两种类型的负载。存储层大幅优化了从 TiKV “行”存储到 TiFlash “列”存储格式的转换效率，在“行 - 列”转换环节的 CPU 效率大幅提升，进而使得高负载情况下可以节约出更多的 CPU 资源用于其他环节的计算任务。

在分布式 OLAP 数据库中，用户通常可以对一张表选择任意的一列作为其分布的 key，这样这张表的数据就可以按照这个 key 列分布到不同的数据库节点上。在进行单表聚合或多表关联时，如果聚合的分组列或关联的关联列是上述的分布 key，则各个节点可以仅在本地进行这个聚合或关联计算，避免跨节点的数据交换，从而获得巨大的性能提升。这一般被称作 collocation 优化。在分布式 HTAP 数据库中，数据有行存和列存两种形式，分别对应于面向 OLTP 的场景和面向 OLAP 的场景，行存和列存的数据通过某种方式进行同步。在一个强实时性的 HTAP 数据库中，这种同步方式要求行存和列存中的数据满足相同的分布以保证同步效率即实时性，这要求 HTAP 数据库中的数据应以 OLTP 中的分布形式为准，而 HTAP 中的 TP 能力需要数据按照主键进行分布，这使得 AP 能力中无法有效的实现 collocation 优化，对于单表聚合或多表关联，需要进行跨节点的数据交换，使得性能落后于专用的 OLAP 数据库。

为了解决这一问题，本技术引入了一种基于索引的数据重分布及 collocation 优化的方法，包括：

S1、建立一种新的索引：重分布索引。用户可以为一张表指定一个或多个重分布索引，其中每个重分布索引值包含一到多列。重分布索引同时具有聚簇索引和二级索引的性质：与聚簇索引相同，重分布索引存储完整的行数据，与二级索引相同，重分布索引独立于表数据存储。数据库通过在事务中同时处理表数据和重分布索引数据以维持两者的一致性。

S2、重分布索引需要指定归属于某个 collocation 组。同个 collocation 组内所有重分布索引均拥有相同的数据分布，也就是索引列相同的数据均位于分布式集群中的同一个节点。

S3、查询优化器对于单表聚合或两表关联的查询，检查其聚合的分组列或关联列是否为重分布索引列，如果是，则执行后续步骤。

S4、查询优化器对于单表聚合，检查其聚合的分组列是否有重分布索引，对于两表关联，检查两表的关联列是否都有重分布索引并且都属于同个 collocation 组，如果是，则执行后续步骤。

S5、将对该表的扫描转化为对重分布索引的扫描。

S6、消除原执行计划上的跨界点数据交换算子。

S7、分布式集群扩缩容或者热点调度时，部分重分布索引数据会被复制到新节点，数据分布会发生变化。在同个 collocation 组内的所有重分布索引按照最新的数据分布迁移完成之前，查询优化器依然可以使用原来的重分布索引做 collocation 优化。等到 collocation 组内所有重分布索引数据均迁移完成之后，查询优化器才可以使用新的重分布式索引，此时旧的重分布索引可以被删除。因为重分布索引数据与表数据是独立存放的两份数据，因此重分布索引与表数据的数据分布也是相互独立的，进而他们的调度也是相互独立的，这样可以互不影响。

一种基于索引的数据重分布及 collocation 优化的系统，包括：

1、元信息模块，用于为用户提供建立、删除重分布索引的方法，用户可以通过建表语句或 alter table 语句，为某张表建立或删除重分布索引。

2、事务模块，用于在事务中随着表数据的插入、更新、删除，同步的对重分布索引数据进行对应的操作，以保证重分布索引数据与表数据一样具有 ACID 语义。

3、分布式存储计算模块，存储部分用于分布式的存储重分布索引数据，根据数据调度模块的指令将重分布索引数据调度到指定节点，从而满足 collocation 优化的条件；计算部分用于分布式的执行一个查询计划，分布式集群上的每个节点可以对存储在该节点上的数据按照执行计划进行计算。

4、查询优化器模块，用于根据重分布索引信息，对满足条件的单表聚合和多表关联查询进行 collocation 优化，消除查询计划中的跨节点数据交换操作。

5、数据调度模块，用于在分布式集群扩缩容或热点调度时对数据进行调度。按照 S6 中所述方案，在调度过程中保留原来的重分布索引，调度完成之后再使用新的重分布索引，这样 collocation 优化在调度期间仍然可以生效。

本发明的一个分布式 HTAP 数据库系统的实施例：

如上图所示，本发明基于一个分布式 HTAP 数据库系统，该 HTAP 数据库由三部分组成：

1、SQL 层：负责接收用户的 SQL 查询请求，生成和优化 SQL 的执行计划，并完成一些简单的计算

2、调度层：负责决定如何分布式存储数据，例如一张表的数据如何被分成多份，并存储在多个节点中

3、存储/计算层：负责存储数据以及相关的查询计算

本发明实施例具体步骤包含：

1、在 SQL 层支持一种新的索引：重分布索引，该索引具备三个特征：

① 该索引的每一行都存储了对应表的所有数据，即该索引包含了表的所有数据。

② 该索引与表数据独立存储。

③ 该索引值包含一列或多列数据，使用哈希算法索引值到整数值域。

2、在 SQL 层通过事务保证重分布索引的数据与表里面的数据的一致性。

3、对于同一个表可以支持定义一个或者多个不同的重分布索引，同时重分布索引需要指定归属于某个 collocation 组。

4、在 SQL 层，对于单表聚合，优化器检查其聚合列是否包含该表中某个重分布索引的索引列：

① 如果包含了，则优化器将对表的扫描转换为对应重分布索引的扫描，并且两阶段聚合优化为每个存储/计算节点上的 collocation 聚合。

② 如果没包含，则优化器按照传统的算法生成相关的分布式聚合的执行计划。

5、在 SQL 层，对于关联操作，优化器依次检查如下情况：

① 如果参与关联的两个表都包含某个重分布索引使得关联列包含该重分布索引的索引列，并且两个重分布索引属于同个 collocation 组，则优化器将对这两个表的扫描都改成对对应重分布索引的扫描，并消除原始执行计划中的数据交换算子，将分布式关联算法改为只需要存储/计算节点自己内部做关联的collocation关联。

② 如果参与关联的其中一个表包含某个重分布索引使得关联列包含重分布索引的索引列，则优化器将对这个表的扫描改成对重分布索引的扫描，并消除原始执行计划中该表一侧的数据交换算子，并修改另一侧表的数据交换算子使其按照相应重分布索引所属 collocation 组的分布进行数据交换，将两个表都需要做数据交换的分布式关联算法改成仅需要一个表做数据交换的分布式关联算法。

③ 如果参与关联的两个表都没有相关重分布索引，则优化器按照传统的算法生成分布式关联的执行计划。

在调度层，由于重分布索引值为哈希值，范围为整数值域，可将这个值域切分为多个相邻的范围，均匀的调度到所有存储节点上。在分布式集群扩缩容或热点调度时，可根据相应的机制重新划分值域范围，并且需要对同个 collocation 组的不同重分布索引使用相同的值域划分。此外，在调度过程中需要保留原来的重分布索引，完成之后再使用新的重分布索引，这样 collocation 优化在调度期间仍然可以生效。

在数字化转型过程中，企业对“海量、实时、在线”的数据需求变得更加迫切，企业中的任意人在任意时间、任意地点对任意形态的数据都可能产生消费的需求，HTAP作为数据库的创新形态，用一个数据平台应对规模化交易和实时分析的需求，提升业务决策的时效性并且降低数据技术栈的复杂性，已经成为金融、运营商、制造、零售、新经济、互联网、政府业务创新的重要引擎。HTAP 数据库在这些行业的应用场景不断延伸，例如通过用户的各种行为、金融交易、征信、风控、风险偏好等数据可以识别出客户的风险特征和投资偏好，进而推荐合适的产品；对营销线索的转化周期实时跟踪监测，根据用户需求的变化实时调整，提升转化效率等。

开发团队 ·带队负责人姓名：孙若曦

孙若曦，TiDB Cloud Compute Engine 团队研发负责人，负责 TiDB 核心计算引擎的架构演进及功能开发。曾任职 NVIDIA、星环科技，专注于数据库、大数据领域，有十余年并行计算、系统软件的开发经验。

团队其他重要成员姓名：徐飞，耿立琪、陈书宁。

·隶属机构：PingCAP

PingCAP 是业界领先的企业级开源分布式数据库企业，提供包括开源分布式数据库产品、解决方案与咨询、技术支持与培训认证服务，致力于为全球行业用户提供稳定高效、安全可靠、开放兼容的新型数据服务平台，解放企业生产力，加速企业数字化转型升级。

相关评价

用时间换空间和用空间换时间是个永恒的话题，Redistribute Index 在时间和空间的推敲中找到了一个新的方法。让计算的数据尽量在同一台机器上，既可以加快数据处理的速度又可以减少网络数据的传输，而 Collocation Group 是一个确保数据分布的新思路，让 Redistribute Index 的实现成为可能。当然，优化没有银弹，在时间和空间上的权衡不可避免。

——李雨来 TiDB Committer, Seaweedfs Contributor

网络IO开销是分布式数据库的一大性能痛点，redistributed key利用存储分布规则的变化在代价极小的情况下解决了常用场景的分析计算问题，创新且实用。

——刘子东 小米数据库工程师

提示：了解更多相关内容，点击文末左下角“阅读原文”链接可直达该机构官网。