[WIP] Storage in AP Systems

上层架构 / 对存储的需求

相关的论文：

  1. SIGMOD‘16，知名的： The Snowflake Elastic Data Warehouse
  2. SIGMOD’22: Amazon Redshift Reinvent
  3. NSDI’20: snowflake 的弹性存储：Building An Elastic Query Engine on Disaggregated Storage
  4. (BigQuery) Dremel: A Decade of Interactive SQL Analysis at Web Scale
  5. PushdownDB / FlexPushdownDB

我们分成几个子话题

数据分布：

  1. [PVLDB’20] Fast and effective distribution-key recommendation for amazon redshift / [SIGMOD’20] Learning a partitioning advisor for cloud databases.
  2. https://cloud.google.com/blog/topics/developers-practitioners/bigquery-admin-reference-guide-storage / snowflake paper

调度 / 弹性

这块其实不太完全是 AP 系统的知识

  • Yarn / Mesos (机制)
  • DRF (策略)

计算 ( colocate )

Cache

相关文章：

  1. facebook 关于 CacheLib 的两篇论文

  2. snowflake 弹性存储

  3. Crystal: A Unified Cache Storage System for Analytical Databases

  4. Alluxio

shuffle service

  • Cosco: An Efficient Facebook-Scale Shuffle Service
  • Dremel: A Decade of Interactive SQL Analysis at Web Scale

Multi-tanent

这里感觉得分开来讨论， Dynamo 这些用的都是 quota 之类的，Yarn 之类的是上层调度，我不确定这里合不合适

计算下推

  • PushdownDB: Accelerating a DBMS using S3 Computation (Presto 用了这套逻辑)

Metadata

  • Big Metadata: When Metadata is Big Data
  • Delta-Lake

存储格式

Parquet: https://github.com/apache/parquet-format/blob/master/Encodings.md

ORC: https://orc.apache.org/specification/ORCv2/

Doris: https://xie.infoq.cn/article/4f7d09d6185fb3055d4e7e51c

ClickHouse MergeTree

HyPer

Umbra: 内存数据库的特殊优化

Kudu: CFile，本质上和 Doris 那些 Unique 是同一套

Encoding

https://github.com/apache/parquet-format/blob/master/Encodings.md

要点：压缩率 / 性能对比，能否 SIMD，针对 pattern 做特定的优化（子问题：如何识别 pattern）

还有一些 HTAP 的编码方式。

此外，关注 SIGMOD’21 CodecDB

Query on Encoded Data

要点：https://blog.mwish.me/2022/01/15/format-thinking-2/#DB-%E7%9B%B4%E6%8E%A5%E5%9C%A8%E5%8E%8B%E7%BC%A9%E7%9A%84%E6%95%B0%E6%8D%AE%E4%B8%8A%E8%BF%9B%E8%A1%8C%E8%AE%A1%E7%AE%97

DB 可以直接在压缩的数据上跑一些简单的计算，但是这个需要让存储知道具体走了什么样的算子

Lazy Evaluation

要点：行中的列可以需要的时候再 load，不访问可以不加载，加载出来的结构也可以标识自己是 RLE 还是什么样的，来避免：

  1. 访问 Page 的开销
  2. 加载不需要的列的开销

这部分其实和实现绑定的特别死，主要是 runtime 的实现，甚至有一些是 Query Optimizer 有关的部分

字典和全局字典

要点：字典和字符串有序性

例如：StarRocks2.0.1低基数全局字典优化测试 和 PolarDB MySQL·HTAP·浅析IMCI的列存数据压缩 . 这里关心：

  1. 是否走到字典上（有的地方字符串类型之外的类型不会走到字典上）
  2. 字典的顺序是否和原始顺序一样
  3. 是否物化（字典可能不那么急着物化，上层可以根据字典来做 JOIN、DISTINCT 之类的优化）。

索引

这里说索引这个词有歧义，TP 方面一般这里指全局的 1:1 的索引，而 AP 这里既有 1:1 的索引，更多还是稀疏索引、Page 上、RowGroup 上的信息统计。因为做 skipping 要考虑这些信息，所以我们汇总到索引这里。

这里有：

  1. Page 上的统计信息，例如 Page Index / Zone Map
  2. Z-ordering，可以当成是拍平的 zone-map

可参考的：

  1. pinot: https://docs.pinot.apache.org/basics/indexing

有很多统计信息相关的，见：http://dimacs.rutgers.edu/~graham/ssbd.html 。论文有

此外，还有一些 SuRF 之类的 Succinct 类型: https://6.5210.csail.mit.edu/

还需要关注 Inverted Index，见 Lucene。

特殊的索引

本来 z-ordering 应该放这里的，但是由于其重要性，我们放到了上面？

  1. 空间索引。
  2. 相似度索引：https://github.com/ClickHouse/ClickHouse/blob/master/docs/en/engines/table-engines/mergetree-family/annindexes.md

IO Pattern

Share-nothing

ClickHouse

Doris

Shared-storage

Apache-Arrow

Velox

变更 (Insert / Update / Delete)

  • Positional Update Handling in Column Stores：最早用 Positional Delta 描述删除的论文之一
  • SQL Server (Delete + Insert 的代表，论文很多地方描述非常详细，包括 Positional Delete 和 Conditional Delete)
  • Kudu （Delta File 的代表，机制和 MVCC 是整合的，Update 支持很高效，但是对 Scan / Pruning 不是很友好）
  • ClickHouse MergeTree （Merge-on-Read 的代表，暴力实现）
  • TiFlash (复杂的树结构)
  • S2DB SingleStore

MVCC

特殊类型: struct / array / map / json

dremel and parquet

Schema Evolution

Iceberg schema evolution

Compaction

kudu compaction

Auto Clustering

snowflake auto clustering

数据导入

CDC: databus

Flink

Kafka

Husky

BigQuery Streaming / Snowflake Unistore

Data Lake

  1. Iceberg
  2. Hudi
  3. DeltaLake