AP存储-Intro
date
slug
tags
summary
type
status
这系列文章用于记录个人对AP负载存储系统的理解，会实时更新。如有错误欢迎指正。
针对AP负载的各种存储系统，目标主要在于：
- 更友好的cache locality，提高计算效率
- 提高IO利用率，使每次IO尽量获取有效数据
- (optional) 在OLAP的场景下，虽然对小而频繁的写负载要求不高，对于批量写入的请求需要提供：快速upsert，支持ACID
针对以上的目的，优化手段大体有：
- PAX列式存储格式，数据编码，数据压缩
- 维护元数据，用于快速过滤和索引无效数据
- 读写分离的更新
列式格式
列式存储相比于行式存储具有以下的优点：
- 提高IO的利用率，查询某些列时不需要花费额外的IO在无关列上
- 内存中的列式表示具有更好的cache locality，以及具有向量化计算的潜能
- 同列中一致的数据类型，对数据编码压缩更加友好
因此，列式存储是目前AP存储系统中普遍采用的格式。而当数据量变大时，列式存储进一步分块是一个必然的趋势，即PAX格式。
如下图，Parquet，Orc都采用了类似的存储格式：将表分成多个row group，row group内部再切分成多个column chunk。一般，column chunk会保证是一段连续的数据，其大小可以进行调整，column chunk越大，在计算某列场景下带来的好处更大，同时占用内存也越大。这是一个需要用户根据场景去进行选择的trade off。
编码&&压缩
列存下，一个column chunk中的数据是相同类型且连续的，因此更方便于编码和压缩。具体的编码和压缩手段在之后的文章进行讨论。
元数据索引
列存存储将数据分成多个块，高效率的查询依赖在读路径上快速过滤掉无关的数据：
- 减少无效的IO
- 减少无效的内存访问
- 快速索引
因此，AP存储格式一般都提供了相应的元数据进行索引，其作用在于过滤掉不需要的数据。目前常用的元数据索引主要有两种类型：
- Zone Map，Page Index
维护对数据块的数据统计量，比如最大值，最小值，Null值。通过这些统计值用于判断数据块中是否有所需要的数据。这类元数据一般用于多种Level，比如从File Level，RowGroup Level到Column Chunk Level，能够减少无效的IO以及无效的内存访问。
- Bloom Filter
用于快速判断数据块中是否具有某个数据。Bloom Filter是比Zone Map更加细粒度的索引，一般用于最小粒度的数据块，比如Column Chunk Level，能够减少无效的内存访问。
- 稀疏索引
稀疏索引在ClickHouse中被使用，其会根据配置的粒度范围，在每个数据个数范围取一个排序键进行记录，比如
sort_key1,sort_key2,sort_key3。之后这些排序键可以被构建成一系列区间[0,sort_key1),[sort_key1,sort_key2),.. ，对于每个查询，可以抽取去对应的区间，与上面的区间进行一个交集进而快速定位查询的数据范围。元数据索引的位置一般有两种：Footer或者数据块头部。
- 对于前者，可以提前加载，用于判断是否进行下一个IO，减少无效的IO。
- 对于后者，则可以随着数据块共同加载到内存，在查询时进行过滤，减少无效的内存访问。
更新
Iceberg，Delta，Hudi三个方案的动机都存在着不满足于data lake的更新机制。原有data lake方案通常会有以下不足：
- 无法支持ACID，批量导入失败后很麻烦
- 无法快速更新，支持upsert
对于支持ACID批量写入，快速upsert，各个lake format都有各自的实现，不过整体思想是一致的。
一般分成两种写入模式：copy-on-writer，merge-on-read。
- copy-on-write：拷贝原有的数据文件，重写一份新的，这种方案的写性能较差，但是好处是读性能很好。
- merge-on-read：将更新写入一个delta文件，读时需要合并delta和当前快照，这种方案写性能比较好，但是读性能比较差。为了降低读开销，后台定期合并delta和快照。
- 除此之外，也有方案Paimon通过维护一个delete vector的方式来实现更加均衡的读写性能。
其次，将读写文件分开，实现读写并发（一般是Snapshot Isolation的形式
Ref
Loading...