PostgreSQL码农集散地

数据库筑基 2 | 理解行列混合存储

今天如果还要学数据库,那就只筑基。这就是数据库领域的九阳神功。

今天聊一个行列混合存储开源项目 zedstore,虽然这个项目已经封存了,但值得学习。

先讲个你大概遇到过的场景。手上有一张几亿行的宽表,分析师跑过来问:「帮我算算某个日期字段的 distinct 有多少。」你低头看了眼 SQL——从头到尾只出现了一个列。可数据库呢?它把整行整行的数据从盘上搬进内存,因为 PostgreSQL 默认的 heap 是行存,一个 page 里塞的是完整的 tuple。读了几十个 G,最后只用一个字段。

浪费吗?太浪费了。但你可能没细想过:要治这个浪费,光把行拆成列是不够的。拆完之后一连串问题会追着你跑。zedstore 有意思的地方就在这儿——它顺着「怎么让 PG 原生地支持列存」这个念头一路推下去,最后长出一套挺特别的结构。我们顺着这条链子走一遍。

一、要少读,就得先拆开

思路很直白:既然查询只要少数列,那就别把整行放在一起,按列存。少列查询只读那几列的 page,IO 自然就下来了;同类数据挤在一起,压缩比也能上去;列式布局还方便对接 CPU 的批量计算指令集。这些好处原文开篇就列了,没什么争议。

但列存有个绕不开的麻烦:一行数据被拆到好几个地方之后,你怎么知道哪些散片属于同一行?

更麻烦的是 MVCC。PostgreSQL 的行可见性靠 tuple 头里的 xmin/xmax 判断,行存里这个是现成的。你一列一列拆开存,可见性信息放哪儿?每个列的副本里都存一份?那更新一行就得改所有列,麻烦且不一致。

所以真正的问题不是「怎么拆」,而是「拆开之后,拿什么把散片重新串起来,并且只在一个地方判断可见性」。

二、给每一行发一个号

zedstore 的答案是一个逻辑行号,叫 zstid。

你可以把它理解成「这张表里这一行的身份证号」。只要不发生 update,它永远不变;在表里也唯一。为了兼容 PG 原来的 tid 接口,它还能和 ctid 一对一换算:

zstid = ctid.blknum * 128 + ctid.offset

这里有个细节特别值得停下来看:逻辑行号和物理位置是解耦的。B-tree 的页会分裂、会合并,一条记录可能在不同 page 之间搬家,但 zstid 不动。这就是为什么它敢用 B-tree 当主结构——后面会看到,这个选择挺关键。

别急着把它当主键用。原文特意提醒了:update 之后 zstid 可能变化;delete 再 vacuum 之后,那个号还可能被后来的 tuple 复用。它是内部的线头,不是给你做业务主键的。

有了这根线,散落各处的列就能串回来了。

三、真正的关键一步:可见性和列值分家

想通上面那层,接下来这步就顺了。zedstore 把两类信息彻底分开管:

  • zstid tree:以 zstid 为 key,叶子节点存的是这一行的可见性和 undo point——注意,不存列值。
  • att tree:每一列(或每一组列)一棵 B-tree,key 同样是 zstid,叶子节点存的是列值或者 toast 指针——不存可见性。

所有树共用一个 key,于是「哪些散片属于同一行」这个问题消失了:它们就是同一个 zstid 在不同树里的值。而可见性只在一棵树里判断,更新时也就只有一个地方要改。

那为什么偏偏是 B-tree?有两层原因。表层原因是 PG 12 引入了 table access method API,zedstore 是严格按这套 API 做的插件式存储,复用 PG 自己的 buffer manager 和存储管理器;深层原因是 B-tree 是 PostgreSQL 最熟的地形,页分裂、逻辑 TID 移动这些语义都是现成的,不用重新发明。

数据文件开头有个 0 号页,叫 meta page,相当于整个文件的路由表:每棵树的 root page 在哪、每条 free page 链表从哪个 page 开始,都记在这儿。文件里一共六类 page——meta、zstid btree、att btree、undo、toast、free。其中 undo 只有 zstid tree 需要指向,toast 只有 att page 需要指向。这个「谁指向谁」的不对称,正是上一节那个「可见性和列值分家」在物理层面的投影。

结构讲完了。但写进去的数据,长什么样?

四、写进去:先图快,再图省

先看 zstid page。连续多个 zstid 打包存,用的是 Simple-8b 格式——一个精确值加若干偏移量,省空间。页面里同时塞进对应 tuple 的 undo point,可见性就在这里。原文给的格式是:

Header | 1-16 TID codewords | 0-2 UNDO pointers | UNDO "slotwords"

列数据的 att leaf page 更有意思,它被分成上下两段:

  • lower attstream(未压缩区):新数据先写这里,速度优先。
  • upper attstream(压缩区):存压缩后的数据。

写满未压缩区之后怎么办?不是就地压一下,而是把未压缩区和已有的压缩区一起重新压缩,替换掉压缩区;腾出来的空间继续当未压缩区写,直到压不动为止。

这其实是个挺聪明的取舍:用一次性的压缩代价,换写入路径上的持续吞吐。高频更新场景最怕的就是每次插入都做重活,zedstore 把重活推迟到了页面写满的那一刻。

五、读出来:把上面倒着走一遍

插入是先领 zstid、再写 zstid tree、最后以 zstid 为 key 写各棵 att tree。查询就反过来:

  1. 扫 zstid tree,过滤掉不可见的 tuple;
  2. 按要查的列,只扫对应的 att tree;
  3. 把列值收齐返回。

到这儿,最初那个「少读」的愿望终于兑现了——一条只要两个列的查询,确实不用碰其它列的树。

但顺着这个机制往下推,你会立刻发现它的边界:目标列越多,要扫的 att tree 就越多,列存的优势就越薄。如果一条查询把大部分列都要了,那它得挨个访问几十棵树,反而不如行存读整页来得干脆。

怎么办?zedstore 给的解法是 column group:把经常一起访问的列打包成一组,共用一棵树。比如 a,b,c 总是一块儿查,就放一起;e 到 j 是另一拨分析常用列,另成一组;其余各管各。原文那句总结很到位——「忽略列存概念,它首先是一个压缩的行存;列存是这个概念的扩展」。

不过,这里留下了一个 hard case:既要频繁查单列的大量记录,又要频繁查很多列的大量记录。两种物理布局的诉求是相反的,column group 也救不了。记住这个矛盾,后面数据会把它再放大一次。

六、上数据:它赢在哪,又输在哪

结构讲得再漂亮,也得拿数字说话。原文引用了 PGCon 2020 的测试,我挑三组最能说明问题的。

第一组,NVMe SSD 上做单列冷查询。 同样是 ss_sold_date_sk 这一列:

Heap
Zedstore
读取字节
112 G
1.4 G
I/O time
62 s
20 s
总耗时
129 s
75 s

这就是「少读」的胜利的直观样子:读的量差了快一百倍,时间也差不多砍半。表本身的落盘体积也从 21.0 G 降到 10.1 G(N=1000, P=16)。

第二组,同一条查询,只把盘换成 HDD。 结论直接翻了:

Heap
Zedstore(未优化)
读吞吐
185 MB/s
2.3 MB/s
I/O time
115 s
634 s
总耗时
212 s
730 s

慢了三倍多。有意思的不是「它变慢了」,而是为什么变慢。它其实读得更少了(还是 1.4 G),但读得散——zstid 和每一列都用 B-tree 组织,leaf page 在物理上可能东一块西一块。SSD 不怕随机读,HDD 怕得要命。所以瓶颈从来不是「读多少」,而是「读得多散」。

第三组,把散的问题治一治。 zedstore 提供了 zedstore_rel_extension_factor,做 block 预分配,让 leaf page 在物理上更连续。HDD 上把因子设到 4096,读吞吐从 2.3 MB/s 冲到 573 MB/s,总耗时从 730 s 降到 82 s。这个反转很漂亮,说明前面的失败不是设计错误,是布局参数没调。

但别高兴太早。同样是优化后,跑 SELECT *:

Heap
Zedstore
NVMe SSD 总耗时
127 s
812 s
HDD 总耗时
214 s
716 s

还是输。这就是第五节末尾那个 hard case 的实证版本——列存的结构性代价,预分配救不了。

七、绕回来,给它一个诚实的定位

把链条收一下:因为想少读,所以按列拆;因为拆开要能串回来,所以引入逻辑行号;因为可见性不能到处复制,所以 zstid tree 和 att tree 分家;因为 PG 有 table AM 和成熟的 B-tree,所以树成了主结构;因为写入怕重活,所以先写未压缩区再整页压缩;因为多列查询要扫很多树,所以有了 column group——然后数据告诉我们,这套结构在少列、大表、SSD 上赢得干脆,在多列或者 HDD 上就得靠调参甚至认输。

原文有句话我挺喜欢:「兼顾就意味着平庸,两者都要做到拔尖的话可能会比较难。」zedstore 从来不是要在 OLTP 和 OLAP 两头都当冠军,它是想用一套存储把两类活儿都接住——这个折中本身就有价值,尤其是当你的表很宽、查询很偏、数据量又大到每次全表扫都肉疼的时候。

所以别问「zedstore 好不好」,问自己三个问题就够了:你的查询通常碰几列?你的盘是 SSD 还是 HDD?你的表更新频繁吗? 这三个答案一对,它适不适合你,基本就出来了。

想动手试的话,原文给了完整步骤:拉 greenplum-db/postgres-archive 的 zedstore 分支,./configure --with-lz4,make world,initdb 之后 create table ... using zedstore 就能跑。作者自己测的 100 万行插入用了 317 ms,count(distinct c1) 用了 270 ms——三千毫秒都不到,够你先把直观感受建立起来,再决定要不要往深里挖。


延伸:PGCon 2020 session 44《Zedstore – In-core Column Store for Postgres》· VMware 开源博客 2020-07-14 · greenplum-db/postgres-archive zedstore 分支 · zedstore_internal.h

Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image