INTRODUCTION

Hyperspace 是一个由微软开发的开源的数据湖索引子系统。基于 spark+deltaLake 的实现，开源项目地址https://github.com/microsoft/hyperspace。

HYPERSPACE USE CASES

1. 高并发交互式分析查询

2. GDPR 规章下的索引隐私特性

3. 时序分析需求

4. 支持数据湖场景下的复杂视图

HYPERSPACE INDEXING SUBSYSTEM

本章节主要描述 Hyperspace 和 API，以 Spark 作为计算引擎

1. Hyperspace Indexes

Hyperspace 支持传统的非聚集索引，索引和数据是分离的，Hyperspace 索引包含以下特点：

• 列式存储（Columnar）：索引以列式存储，默认是 Parquet 格式，好处是可以应用 parquet 格式的 metrics 和 bloomfilter。

• 索引分区：采用 hash 分区，每个分区内按索引字段进行排序，能够提升查询效率。

• Lineage Tracking：每个索引（可选的）持有指向底层表的指针/引用，如果该表没有主键或聚簇索引，可以通过文件/Blob/文件夹的 URI 来访问底层数据。

2. Architectural Overview

Indexing Infrastructure:

可以是服务或 library，用户可以通过通过 indexing Infrastructure 创建和维护索引，索引数据和元数据存储在数据湖上，可以通过查询引擎并发扫描索引文件。索引元数据管理（Index metadata management）是一个核心模块，由 index manager 进行维护，包括创建、更新、删除，保证索引和索引元数据的一致性。

• Log Management API：为了支持多种引擎可以同时访问和管理索引，通过这个接口记录在索引上的操作，生成操作日志。

• Index Specs：提供了开放的索引的生命周期管理 API，用户可以实现自定义的索引结构。

• Concurrency Model：通过乐观锁的机制支持多用户检索和索引运维。

Query Infrastructure:

Hyperspace 在查询层的实现是继承了 Spark Catalyst 模块，安装 Hypserspace 插件的 Spark 可以通过重写执行计划的方式无感知到使用索引进行查询，设置 sparkSession.enableHyperspace()即可使用 Hyperspace 扩展插件。由于索引在数据湖上是以一个普通数据集存在的，所以扩展性良好，可以支持 spark 的并发访问。

Index Tuning：

为了能够提供一个高效的索引系统，需要给用户提供一个可以量化分析当前索引代价的能力。此外，hyperspace 实现了索引推荐功能，根据当前的存储和条件，自动为用户提供高性价比的索引。

3. Index Organization on the Lake

Hyperspace 索引元数据都存储在湖中，不会依赖其他组件。索引结构：

索引存储在/indexes/*/<index name>，由两部分组成：

（1）_hyperspace_log 目录存储索引从一开始的操作日志。

（2）index-directory 下的索引数据。索引是通过多个目录存储的，这样能够支持多个快照的隔离和增量索引。

4. Usage API & Customization Knobs

Hyperspace 提供了一些公共 API：

Index maintenance API

• 比如 create，delete，restore，vacuum，refresh，cancel。delete 接口实现了软删除，不会被真正删除，但是优化器不会使用这部分索引，删除的索引还可以通过 restore 接口恢复，可以通过 vacuum 接口物理删除索引。cancel 接口可以取消正在执行的索引维护作业。

Utility APIs for debugging and recommendation

• 比如 explain、whatIf、recommend。explain 接口可以打印被重写的执行计划，可以看到索引是否被应用。whatIf 接口可以让用户设置索引配置，并可以看到这些配置带来的收益。recommend 接口可以对不同的索引实现进行排名，可以选择最适合的索引。

• Storage and query optimizer configuration

  可以让用户重写查询优化器和 index management

INDEX MANAGEMENT

Hyperspace 的目标是实现一个低成本的 serverless 索引系统，索引信息存在湖中，操作都记录在 operation logs 中，这部分主要探讨如何通过乐观锁多并发更新索引。

1. Foundation: Metadata in the Lake

索引元数据的管理和数据湖表格式的设计类似，采用无服务化设计，降低了系统复杂性，减少了系统依赖和服务成本。

索引元数据包含以下模块：

• Contents

  记录对应索引文件的 schema 和属性，索引类型，文件路径等。

• Lineage

  记录数据来源、时间戳、执行引擎等。

• State

  记录索引状态

2. Index State Management

索引状态包括稳定态和过渡态

稳定态：Active、DNE（Do Not Exist）、Deleted

过渡态：Creating、Restoring、Deleting、Refreshing（更新索引）、Optimizing（合并索引文件）

如何解决过渡态之间的冲突问题？比如 Deleting 状态不能 Restoring。

Hyperspace 定义了状态之间的兼容性矩阵，N 表示状态之间不兼容，Y 表示状态之间不兼容。

3. Multi-user Concurrency Control

通过乐观锁的方式保证多个用户可以同时操作，操作实现流程图：

• LogOp()方法封装用户的操作参数

• Validate()检查当前状态是否跟提交的操作冲突

• Begin()为索引操作分配一个 id

• RunOp()执行操作，更新当前索引的状态。

• Commit()更新对应 id 的操作状态，由过渡态转变为稳定态。

这个流程需要依赖文件系统提供的文件重命名原子特性，比如 HDFS 就可以提供，我认为 Hive metastore、RDMS 提供的事务操作也可以实现。通过文件重命名原子操作，可以保证 Commit()操作是原子的，在 Commit 时如果发现索引当前的状态被修改了，Hyperspace 就直接取消当前操作然后重试。

对于多个用户同时读索引的场景，不需要锁机制，但是只能读稳定态的索引，比如当前索引正在 Rrefreshing，可以直接读之前 active 状态的索引副本。另外 Hyperspace 采用标签机制保证索引和对应数据文件的一致性，使用最新数据文件的 timestamp 产生的一个 md5hash 标签，在查询时可以通过标签进行校验索引是否覆盖了最新数据。

INCREMENTAL INDEX MAINTENANCE

1. Mutable Datasets and Semantics

用户的数据经常更新和新增，比较常见的应用场景包括流式写入，数据修正。数据湖里的数据和索引都需要更新和新增，一般采用多版本和日志追加的机制实现。

2. Index REFRESH & OPTIMIZE

Hyperspace 创建索引的过程本质是收集数据文件的元数据的过程，包括文件名，更新时间，文件大小等，为了支持删除操作，hyperspace 索引系统应该能够跟踪删除记录当前所在哪个文件。索引的维护采用多种模式，能够根据负载情况选择合适的模式

Full Refresh，扫描整个数据表，重建索引。比较适合没有实时流写入的静态表。

Incremental Refresh，如果数据表一直有增量数据写入，可以采用增量刷新的方式创建增量索引。对于删除数据，先找到对应的索引的文件，然后重写整个索引文件，所有新的索引文件提交后会产生一个新的快照。

Quick Refresh,增量数据写入比较频繁的情况下，实时创建索引会比较消耗资源，索引文件小而多，收益比较小。hypserspace 提供了一种快速刷新的的方式，快速扫描新增的数据文件，然后将元数据记录下来。

Optimize,频繁刷新索引会产生较多的小索引文件，可以通过 optimize 合并小文件。

3. Support for ACID Data Formats

Delta Lake，Iceberg，Hudi 支持数据文件的事务操作，Hypserspace 可以使用他们的事务日志获取最新数据或增量数据，而不用再去检查文件的元数据。

QUERY PROCESSING USING INDEXES

Hyperspace 在 Spark 优化器中实现了基于 RBO 的索引感知的能力，在 Catalyst 中定义新的规则。另外对于索引过期的情况，可以采用 hybrid scan 的机制查询数据。

1. Index-aware Optimizer Extension

上图描述了 Hyperspace 在 Spark optimizer 上的扩展，优化器获取当前的索引信息后，通过优化规则处理当前的查询计划，index strategy 筛选出最合适的索引，将索引应用到执行计划上，当前的执行计划可能是多个，所以还需要通过 plan ranker strategy 比较所有的计划，选择代价最低的，实际上 CBO 和 what if utility 模块的应用，what if utility 实际上也是 CBO 模型，只是把索引的代价考虑进去，选择更低成本的索引类型。

Index Strategies 包含两个规则，FilterIndexRule 和 JoinIndexRule，分别加速 filter 和 join 查询。

FilterIndexRule 的原理：索引列和条件列的交集字段可以应用索引。

JoinIndexRule 的原理：索引支持等值条件的 join，当 join 字段都存在索引时，如果两个字段的分区数量相同，可以选择 sort-merge join，避免了 shuffle，并且分区内的索引文件都是排序的，可以采用 TimSort，时间复杂度是 O(n)，如果分区数量不同，选择最大的分区数作为 join 的分区数，只 shuffle 一个字段，并且并行度更高。

2. Hybrid Scan

索引和原始数据通常是无法保持一致的，流式写入数据的时候，如果实时创建索引，会影响写入的性能，同时产生大量小文件索引，维护成本较大，一般采用异步的方式刷新索引。这种情况下在查询引擎端如何高效的利用索引？Hyperspace 在 spark 实现了混合扫描的功能，

如上图所示，新增了 7 和 8 两个数据，删除了 4，对于新增数据，重写执行计划，由原来的 table A scan 的算子转换为一个 Union 算子，将旧的索引文件和新增数据文件进行合并。对于删除的数据，插入一个 filter 算子，过滤删除的数据。

hyperspace 索引系统支持多快照的，所以也支持时间旅行的，索引的快照号是基于原始数据的某个版本的，比如访问 deltaLake 中的 v4 版本时，需要扫描 v1 版本的索引和 v4-v2 版本的增量数据，v3 版本会跳过，因为 v3 中的删除数据已经在 v1 索引中合并删除了。如果访问 v6 版本的数据，则有两种访问方式，这时需要对这两种方式进行评估，选择代价最小的方式。

CONCLUSION

1. Hypersace 作为索引系统，定义了索引存储格式和存储布局，以列存的格式存储，按哈希分区，分区内排序，这样设计的目的主要是为了快速扫描索引文件，spark 适配这种哈希分区可以减少 join 时的 shuffle，适配 sort merge join。可以支持聚集索引和非聚集索引。

2. 采用无服务化设计，没有服务接口依赖，降低资源消耗。

3. 维护了一系列元数据文件，记录索引的操作日志，支持快照级别隔离，每个快照会产生一个新的索引目录，跟数据湖表格式的原理类似，Hyperspace 本身是基于 spark+deltaLake 的。

4. 提供了完整的生命周期管理和索引维护接口，通过乐观锁解决多个用户的并发操作的冲突问题。

5. 在 SQL 引擎端，通过 RBO 的方式新增 FilterIndexRule 和 JoinIndexRule，重写执行计划，将执行计划的叶子节点替换为 index scan，在 CBO 阶段也评估索引的执行代价。

6. hybrid scan 能够充分利用索引，原始数据和索引混合扫描，即使出现过期的索引也不影响正确性，索引也支持时间旅行，实现基于不同索引快照和数据快照的混合扫描。