木鸟杂记

分布式系统,程序语言,算法设计

DDIA 读书笔记(三): TP AP 和列存

DDIA 读书分享会,会逐章进行分享,结合我在工业界分布式存储和数据库的一些经验,补充一些细节。每两周左右分享一次,欢迎加入,Schedule 在这里。我们有个对应的分布式&数据库讨论群,每次分享前会在群里通知。如想加入,可以加我的微信号:qtmuniao,简单自我介绍下,并注明:分布式系统群。

事务型还是分析型

术语 OL(Online)主要是指交互式的查询。

术语事务( transaction )由来有一些历史原因。早期的数据库使用方多为商业交易(commercial ),比如买卖、发工资等等。但是随着数据库应用不断扩大,交易\事务作为名词保留了下来。

事务不一定具有 ACID 特性,事务型处理多是随机的以较低的延迟进行读写,与之相反,分析型处理多为定期的批处理,延迟较高。

作者:木鸟杂记 https://www.qtmuniao.com/2022/04/16/ddia-reading-chapter3-part2 转载请注明出处

下表是一个对比:

属性 OLTP OLAP
主要读取模式 小数据量的随机读,通过 key 查询 大数据量的聚合(max,min,sum, avg)查询
主要写入模式 随机访问,低延迟写入 批量导入(ETL)或者流式写入
主要应用场景 通过 web 方式使用的最终用户 互联网分析,为了辅助决策
如何看待数据 当前时间点的最新状态 随着时间推移的
数据尺寸 通常 GB 到 TB 通常 TB 到 PB

一开始对于 AP 场景,仍然使用的传统数据库。在模型层面来说,SQL 足够灵活,能够基本满足 AP 查询需求。但在实现层面,传统数据库在 AP 负载中的表现(大数据量吞吐较低)不尽如人意,因此大家开始转向在专门设计的数据库中进行 AP 查询,我们称之为数据仓库(Data Warehouse)。

数据仓库

对于一个企业来说,一般都会有很多偏交易型的系统,如用户网站、收银系统、仓库管理、供应链管理、员工管理等等。通常要求高可用低延迟,因此直接在原库进行业务分析,会极大影响正常负载。因此需要一种手段将数据从原库导入到专门的数仓

我们称之为 ETL:extract-transform-load

ddia-3-8-etl.png

一般企业的数据量达到一定的量级才会需要进行 AP 分析,毕竟在小数据量尺度下,用 Excel 进行聚合查询都够了。当然,现在一个趋势是,随着移动互联网、物联网的普及,接入终端的类型和数量越来越多,产生的数据增量也越来越大,哪怕初创不久的公司可能也会积存大量数据,进而也需要 AP 支持。

AP 场景下的聚合查询分析和传统 TP 型有所不同。因此,需要构建索引的方式也多有不同。

同样接口后的不同

TP 和 AP 都可以使用 SQL 模型进行查询分析。但是由于其负载类型完全不同,在查询引擎实现和存储格式优化时,做出的设计决策也就大相径庭。因此,在同一套 SQL 接口的表面下,两者对应的数据库实现结构差别很大。

虽然有的数据库系统号称两者都支持,比如之前的 Microsoft SQL Server 和 SAP HANA,但是也正日益发展成两种独立的查询引擎。近年来提的较多的 HTAP 系统也是类似,其为了 serve 不同类型负载底层其实有两套不同的存储,只不过系统内部会自动的做数据的冗余和重新组织,对用户透明。

AP 建模:星状型和雪花型

AP 中的处理模型相对较少,比较常用的有星状模型,也称为维度模型

ddia3-9-star-schema.png

如上图所示,星状模型通常包含一张事件表(fact table和多张维度表(dimension tables。事件表以事件流的方式将数据组织起来,然后通过外键指向不同的维度。

星状模型的一个变种是雪花模型,可以类比雪花(❄️)图案,其特点是在维度表中会进一步进行二次细分,讲一个维度分解为几个子维度。比如品牌和产品类别可能有单独的表格。星状模型更简单,雪花模型更精细,具体应用中会做不同取舍。

在典型的数仓中,事件表可能会非常宽,即有很多的列:一百到数百列。

列存

前一小节提到的分维度表事实表,对于后者来说,有可能达到数十亿行和数 PB 大。虽然事实表可能通常有几十上百列,但是单次查询通常只关注其中几个维度(列)。

如查询人们是否更倾向于在一周的某一天购买新鲜水果或糖果

1
2
3
4
5
6
7
8
9
10
11
12
SELECT
dim_date.weekday,
dim_product.category,
SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
JOIN dim_date ON fact_sales.date_key = dim_date.date_key
JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
dim_date.year = 2013 AND
dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
dim_date.weekday, dim_product.category;

由于传统数据库通常是按行存储的,这意味着对于属性(列)很多的表,哪怕只查询一个属性,也必须从磁盘上取出很多属性,无疑浪费了 IO 带宽、增大了读放大。

于是一个很自然的想法呼之欲出:每一个列分开存储好不好?

ddia-3-10-store-by-column.png

不同列之间同一个行的字段可以通过下标来对应。当然也可以内嵌主键来对应,但那样存储成本就太高了。

列压缩

将所有数据分列存储在一块,带来了一个意外的好处,由于同一属性的数据相似度高,因此更易压缩。

如果每一列中值阈相比行数要小的多,可以用位图编码( bitmap encoding。举个例子,零售商可能有数十亿的销售交易,但只有 100,000 个不同的产品。

ddia-3-11-compress.png

上图中,是一个列分片中的数据,可以看出只有 {29, 30, 31, 68, 69, 74} 六个离散值。针对每个值出现的位置,我们使用一个 bit array 来表示:

  1. bit map 下标对应列的下标
  2. 值为 0 则表示该下标没有出现该值
  3. 值为 1 则表示该下标出现了该值

如果 bit array 是稀疏的,即大量的都是 0,只要少量的 1。其实还可以使用 游程编码(RLE, Run-length encoding) 进一步压缩:

  1. 将连续的 0 和 1,改写成 数量+值,比如 product_sk = 299 个 0,1 个 1,8 个 0
  2. 使用一个小技巧,将信息进一步压缩。比如将同值项合并后,肯定是 0 1 交错出现,固定第一个值为 0,则交错出现的 0 和 1 的值也不用写了。则 product_sk = 29 编码变成 9,1,8
  3. 由于我们知道 bit array 长度,则最后一个数字也可以省掉,因为它可以通过 array len - sum(other lens) 得到,则 product_sk = 29 的编码最后变成:9,1

位图索引很适合应对查询中的逻辑运算条件,比如:

1
WHERE product_sk IN306869

可以转换为 product_sk = 30product_sk = 68和 product_sk = 69这三个 bit array 按位或(OR)。

1
WHERE product_sk = 31 AND store_sk = 3

可以转换为 product_sk = 31和 store_sk = 3的 bit array 的按位与,就可以得到所有需要的位置。

列族

书中特别提到列族(column families)。它是 Cassandra 和 HBase 中的的概念,他们都起源于自谷歌的 BigTable 。注意到他们和列式(column-oriented)存储有相似之处,但绝不完全相同:

  1. 同一个列族中多个列是一块存储的,并且内嵌行键(row key)。
  2. 并且列不压缩(存疑?)

因此 BigTable 在用的时候主要还是面向行的,可以理解为每一个列族都是一个子表。

内存带宽和向量化处理

数仓的超大规模数据量带来了以下瓶颈:

  1. 内存处理带宽
  2. CPU 分支预测错误和流水线停顿

关于内存的瓶颈可已通过前述的数据压缩来缓解。对于 CPU 的瓶颈可以使用:

  1. 列式存储和压缩可以让数据尽可能多地缓存在 L1 中,结合位图存储进行快速处理。
  2. 使用 SIMD 用更少的时钟周期处理更多的数据。

列式存储的排序

由于数仓查询多集中于聚合算子(比如 sum,avg,min,max),列式存储中的存储顺序相对不重要。但也免不了需要对某些列利用条件进行筛选,为此我们可以如 LSM-Tree 一样,对所有行按某一列进行排序后存储。

注意,不可能同时对多列进行排序。因为我们需要维护多列间的下标间的对应关系,才可能按行取数据。

同时,排序后的那一列,压缩效果会更好。

不同副本,不同排序

在分布式数据库(数仓这么大,通常是分布式的)中,同一份数据我们会存储多份。对于每一份数据,我们可以按不同列有序存储。这样,针对不同的查询需求,便可以路由到不同的副本上做处理。当然,这样也最多只能建立副本数(通常是 3 个左右)列索引。

这一想法由 C-Store 引入,并且为商业数据仓库 Vertica 采用。

列式存储的写入

上述针对数仓的优化(列式存储、数据压缩和按列排序)都是为了解决数仓中常见的读写负载,读多写少,且读取都是超大规模的数据。

我们针对读做了优化,就让写入变得相对困难。

比如 B 树的原地更新流是不太行的。举个例子,要在中间某行插入一个数据,纵向来说,会影响所有的列文件(如果不做 segment 的话);为了保证多列间按下标对应,横向来说,又得更新该行不同列的所有列文件。

所幸我们有 LSM-Tree 的追加流。

  1. 将新写入的数据在内存中 Batch 好,按行按列,选什么数据结构可以看需求。
  2. 然后达到一定阈值后,批量刷到外存,并与老数据合并。

数仓 Vertica 就是这么做的。

聚合:数据立方和物化视图

不一定所有的数仓都是列式存储,但列式存储的种种好处让其变得流行了起来。

其中一个值得一提的是物化聚合(materialized aggregates,或者物化汇总)

物化,可以简单理解为持久化。本质上是一种空间换时间的 tradeoff。

数据仓库查询通常涉及聚合函数,如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果这些函数被多次用到,每次都即时计算显然存在巨大浪费。因此一个想法就是,能不能将其缓存起来。

其与关系数据库中的视图(View)区别在于,视图是虚拟的、逻辑存在的,只是对用户提供的一种抽象,是一个查询的中间结果,并没有进行持久化(有没有缓存就不知道了)。

物化视图本质上是对数据的一个摘要存储,如果原数据发生了变动,该视图要被重新生成。因此,如果写多读少,则维持物化视图的代价很大。但在数仓中往往反过来,因此物化视图才能较好的起作用。

物化视图一个特化的例子,是数据立方(data cube,或者 OLAP cube):按不同维度对量化数据进行聚合。

ddia-3-12-data-cube.png

上图是一个按日期和产品分类两个维度进行加和的数据立方,当针对日期和产品进行汇总查询时,由于该表的存在,就会变得非常快。

当然,现实中,一个表中常常有多个维度,比如 3-9 中有日期、产品、商店、促销和客户五个维度。但构建数据立方的意义和方法都是相似的。

但这种构建出来的视图只能针对固定的查询进行优化,如果有的查询不在此列,则这些优化就不再起作用。

在实际中,需要针对性的识别(或者预估)每个场景查询分布,针对性的构建物化视图。


我是青藤木鸟,一个喜欢摄影的分布式系统程序员。如果你觉得文章还不错,欢迎关注我的公众号:“木鸟杂记”,比心~
wx-distributed-system-s.jpg