列存zedstore

yzsDBA

发布于 2020-10-28 10:22:35

2.1K0

发布于 2020-10-28 10:22:35

文章被收录于专栏：PostgreSQL研究与原理解析

邮件列表

1、动机与目标

1）列子集查询性能提升（减小IO）

2）相对于heap表，减小磁盘占用空间。Tuple头更小，利用压缩数据

3）表数据可以列式存储形式独立于表数据

4）完全符合MVCC

5）支持所有索引

6）混合行列存储，一些列可以一起存储，另外可独立存储

7）分列的粒度非常灵活，可以把一起访问的列存储到一起

8）不需要分开的toast表

9）快速add/drop列或者更改列的数据类型，避免全部重写表

2、设计

简单说，忽略列存储概念，将之认为压缩的行存储。列存储是这个概念的扩展，在下节解释。最基本的磁盘数据结构是B-tree，以TID为索引列。注意，这不是现有的Btree索引，而是独立于表数据存储的另外新Btree。

TID-逻辑行标识符

TID是一个48位的行标识符。传统的分割方法：分为block和偏移显得无意义。为了通过TID查询一个tuple，必须深度遍历B-tree。页分裂或者合并操作可以通过逻辑TID将tuple移动到不同页。

B-tree内部页非常简单，每个页仅仅存储TID数组以及downlinkpairs。叶子页具有short未压缩的头，接着为btree的条目。存在两种条目：普通条目，包含一个元组或者一个数据，未压缩的payload；一个“container item”，有多个普通条目，压缩的payload.

+-----------------------------

| Fixed-size page header:

| LSN

| TID low and hi key(for Lehman & Yao B-tree operations)

| left and right pagepointers

| Items:

| ...

+----------------------------

行存

元组一个接一个的存储，通过TID排序。每个元组包括：48位的TID、undo记录指针、未压缩的用户数据。

未压缩形式下，页会很大。但是压缩后能够满足8K大小。当insert、update一个记录时，如果页压缩后还超过8k，会引起分裂。TID是逻辑的而不是物理，所以可以随意移动记录到其他页而不改变TID值。

Buffer cache缓存压缩的block。同样类似的WAL、全页镜像等等。读时后端私有内存需要改数据页，会解压。对于某些压缩例如表编码或者delta编码，可以从压缩数据中直接构造元组。

列存

列存使用同样的结构，每列都是一个B-tree，以TID为索引值。所有列的B-tree存储到同一个物理文件中。

0号block为元数据页，保存B-tree的root指针。叶子页和行存类似，但是只存储单个字段值而不是整个tuple。为了通过TID获得一行数据，需要遍历TID的所有列的B-tree，并获取所有列字段值。同样，顺序扫描会扫描一个B-tree锁一个树。总结来说，zedstore存储的是B-trees的森林，一列一个树，以TID为索引列。

这种数据布局方式使得行列混合存储比较容易，其中一些列存储在一起，另外一些存储到一个B-tree里。需要有面向用户的语法来指定如何对列进行分组。

以这种方式存储数据的主要原因

以映射的方式布局数据，而不是独立于实际数据的逻辑到物理的映射。因此将元数据和数据逻辑保存到单个文件流中，避免需要独立的文件存储元数据和数据。

采用固定大小的物理块。可变大学的块需要增加逻辑到物理映射的维护，以及并发读写文件的限制。

MVCC

Zedstore和zheap的MVCC机制类似。通过undo记录指针实现MVCC。事务信息没有和数据直接存在一起。Zheap中每页有小、固定的“事务槽”，但是zedstore通过undo指针指向元组。压缩下，压缩会将其压缩到几乎为零。

Implementation

Insert：插入一行，将行分成多列。对于第一列决定将同一block插入到哪个block中，并为其选择一个TID，然后写一个undo log。剩下的列使用相同的TID以及指向相同的undo位置。

压缩：元组以未压缩形式插入Btree。如果页满插不进新元组，此时触发压缩。现有的未压缩元组传入压缩器以压缩。已压缩的元组原样添加到页，页面以压缩数据进行重写，压缩后页仍放不下，则发生分裂。

Toast：当字段值非常大时，分割成多个chunk，每个chunk存储到同一个物理文件的专门的一个toast页上。字段的toast页形成list，每页有next/prev指针。

Select：如果利用AM进行扫描，将property添加到表AM中。当利用这个字段通过AM进行表扫描时，执行器解析这个计划。利用目标列和等职查询所需的列。这个列表在beginscan中传递给AM。Zedstore使用这个列投影列表从选择的列中拉取数据。使用虚拟元组表slot传递返回列子集。当前表am api需要在这里进行增强，以便将列投影传递给AM。这个patch显示了两种不同方式：对于顺序扫描，新增beginscan_with_column_projection()函数API。执行器检测AM属性以便决定调用这个新API还是通用的beginscan API；对于索引扫描，增加新的API，获取tuples前，调用begin scan后，将指定列投影列表传递给scan描述符。

索引支持：通过列存储仅仅扫描需要的列构建索引。索引和heap表工作类似。将数据插入表中，并将TID存储到索引中。索引扫描中，通过给定的TID和使用虚拟元组传回的datums扫描需要的列Btrees。

页格式：zedstore表包括各种不同页，都在同一个文件中：元数据页、每个btree内部和叶子页、undo log页、toast页。每种页类型都有子集不同的数据存储格式。

0号页，总是元数据页，包括其他数据结构的页数，例如btree、undolog。

改进

不是一批将页内所有元组压缩，会存储一个小的“dictionary“，包括页头或元数据页；使用它分别压缩每个元组，可以使随机读取和update单个元组速度更快。

添加列时，仅需要创建新的Btree并链接到元数据页。不需要将现有的内容重写。

当drop列后，扫描这个列的Btree，立即在FSM中国将这些页标记free。但是实际上不需要遍历到leaf级：所有的叶子元组在父级都有一个downlink，仅需要扫描到这级内部页。除非这个列特别宽，否则这只是数据的一小部分。新插入时，立即标记这些空间可重用。但是不会将这个空间收回到操作系统。为了做到这些，仍需要进行碎片整理，并将页从文件尾部移动到头部，然后截断文件。

这个设计中，在page cache中仅缓存压缩页。如果想要缓存未压缩的页，需要设计一个全新的缓冲机制以处理可变大小的block。

如果进行了大量update，文件数据变得非常离散，页内有大量未使用的空间。失去TID和物理顺序的相关性后会变得非常糟。因为时顺序扫描非常慢，由于不再使用顺序IO。可以设计碎片整理机制，通过重新存储TID/physical关联性，将half page合并、删除。这些不会有MVCC的问题，可容易的进行在线修改。当列值不在扫描范围时，可通过存储block的最大和最小值轻松跳过扫描。

当前补丁

支持两种压缩算法pg_lzcompress和lz4。编译时—with-lz4开启LZ4压缩，否则使用默认的pg_lzcompress。Lz4在压缩和解压缩时都非常快。并不是所有的AM API都完成了。Zedstore可以通过下面命令：CREATE TABLE <name> (column listing)USING zedstore；

可通过COPY执行批量加载。INSERT，SELECT，UPDATE，DELETE也可以执行。可创建B-tree索引。也可使用Btree和bitmap索引扫描。/src/test/regress/sql/zedstore.sql测试这个功能是否正常。

References 1] https://github.com/greenplum-db/postgres/tree/zedstore 2] https://www.postgresql.org/message-id/flat/CAJrrPGfaC7WC9NK6PTTy6YN-NN%2BhCy8xOLAh2doYhVg5d6HsAA%40mail.gmail.com 3] https://www.postgresql.org/message-id/flat/20150611230316.GM133018%40postgresql.org 4] https://www.postgresql.org/message-id/flat/20150831225328.GM2912%40alvherre.pgsql 5] https://github.com/citusdata/cstore_fdw 6] https://www.postgresql.org/message-id/flat/CAOykqKfko-n5YiBJtk-ocVdp%2Bj92Apu5MJBwbGGh4awRY5NCuQ%40mail.gmail.com 7] https://www.postgresql.org/message-id/d0fc97bd-7ec8-2388-e4a6-0fda86d71a43%40iki.fi