黄东旭解析 TiDB 的核心优势
854
2023-05-19
今年,Spanner 终于发了另一篇 Paper 「 Spanner: Becoming a SQL System 」,里面提到 Spanner 使用了一种新的存储格式 - Ressi,用来支持 OLTP 和 OLAP。在 Ressi 里面,使用了 PAX 来组织数据。因为 TiDB 定位就是一个 HTAP 系统,所以我也一直在思考在 TiKV 这层如何更好的存储数据,用来满足 HTAP 的需要,既然 Spanner 使用了 PAX,那么就有研究的必要了。
PAX 的论文可以看看 「 Weaving Relations for Cache Performance 」 或者 「 Data Page Layouts for Relational Databases on Deep Memory Hierarchies 」。
在谈 PAX 之前,NSM 和 DSM 还是绕不开的话题,NSM 就是通常说的行存,对于现阶段很多偏重 OLTP 的数据,譬如 MySQL 等,都采用的这种方式存储的数据。而 DSM,则是通常的说的列存,几乎所有的 OLAP 系统,都采用的这种方式来存储的底层数据。
NSM 会将 record 依次在磁盘 page 里面存放,每个 page 的末尾会存放 record 的 offset,便于快速的定位到实际的 record。如果我们每次需要得到一行 record,或者 scan 所有 records,这种格式非常的高效。但如果我们的查询,仅仅是要拿到 record 里面的一列数据,譬如 select name from R where age < 40,那么对于每次 age 的遍历,除了会将无用的其他数据一起读入,每次读取 record,都可能会引起 cache miss。
不同于 NSM,DSM 将数据按照不同的 attributes 分别存放到不同的 page 里面。对于上面只需要单独根据某一个 attribute 进行查询的情况,我们会直接读出 page,遍历处理,这个对 cache 也是非常高效友好的。
但是,如果一个查询会涉及到多个不同的 attributes,那么我们就可能需要多次 IO 来组合最终的 tuple。同时,对于写入,DSM 因为会将不同的 attributes 对应的数据写到不同的 page,也会造成较多的随机 IO。
可以看到,NSM 和 DSM 都有各自的优劣,所以如何将它们的优点结合起来,就是现在很多 hybrid storage 包括 PAX 考虑的问题。
PAX 全称是 Partition Attributes Across,它在 page 里面使用了一种 mini page 的方式,将 record 切到不同的 mini page 里面。
假设有 n 个 attributes,PAX 就会将 page 分成 n 个 mini pages,然后将第一个 attribute 放在第一个 mini page 上面,第二个放在第二个 mini page,以此类推。
在每个 page 的开头,会存放每个 mini page 的 offset,mini page 对于 Fixed-length attribute 的数据,会使用 F-minipage ,而对于 variable-length attribute 的数据,则会使用 V-minipage。对于 F-minipage 来说,最后会有一个 bit vector 来存放 null value。而对于 V-minipage 来说,最后会保存每个 value 在 mini page 里面的 offset。
可以看到,PAX 的格式其实是 NSM 和 DSM 的一种折中,当要依据某一列进行 scan 的时候,我们可以方便的在 mini page 里面顺序扫描,充分利用 cache。而对于需要访问多 attributes 得到最终 tuple 的时候,我们也仅仅是需要在同一个 page 里面的 mini page 之间读取相关的数据。
当数据插入的时候,PAX 会首先生成一个新的 page,然后根据 attribute 的 value size 分配好不同的 mini page, 这里需要注意下 variable-length value,因为它们的长度是不固定的,PAX 会使用一些 hint 来得到一个平均的 size。插入一个 record 的时候,PAX 会将这个 record 里面的数据分别 copy 到不同的 mini page 上面。如果一个 record 还能插入到这个 page,但这个 record 里面某一个 attribute 的数据不能插入到对应的 mini page 了,PAX 会重新调整不同 mini page 的 boundary。如果一个 page 已经 full 了,那么 PAX 就会重新分配一个 page。
当数据更新的时候,PAX 会首先计算这个 record 需要更新的 attributes 在不同 mini page 里面的 offset,对于 variable-length value 来说,如果更新的数据大小超出了 mini page 可用空间,mini page 就会尝试向周围的 mini page 借一点空间。如果邻居也没有额外的空间了,那么这个 record 就会被移到新的 page 上面。
当数据删除的时候,PAX 会在 page 最开始会维护一个 bitmap,用来标记删除的数据。当删除标记越来越多的时候,就可能会影响性能,因为会导致 mini page 里面出现很多 gap,并不能高效的利用 cache。所以 PAX 会定期去对文件重新组织。
PAX 其实是一个原理比较简单的东西,但它并没有成为一个业界主流的存储方案,应该有一些局限是我现在还不知道的。但既然 Spanner 敢用,证明在 HTAP 领域,PAX 也是一个可选择的方案,对我们后续 HTAP storage 的技术选型也有一定的指导作用。这里也就先记录一下,也希望能跟这方面有经验的同学多多交流下心得体会。
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。