DDIA 读书分享会，会逐章进行分享，结合我在工业界分布式存储和数据库的一些经验，补充一些细节。每两周左右分享一次，欢迎加入，Schedule 在这里[1]。我们有个对应的分布式&数据库讨论群，每次分享前会在群里通知。如想加入，可以加我的微信号：qtmuniao，简单自我介绍下，并注明：分布式系统群。
事务型还是分析型
术语 OL（Online）主要是指交互式的查询。
术语事务（ transaction ）由来有一些历史原因。早期的数据库使用方多为商业交易（commercial ），比如买卖、发工资等等。但是随着数据库应用不断扩大，交易\事务作为名词保留了下来。
事务不一定具有 ACID 特性，事务型处理多是随机的以较低的延迟进行读写，与之相反，分析型处理多为定期的批处理，延迟较高。
下表是一个对比：
| 属性 | OLTP | OLAP |
| 主要读取模式 | 小数据量的随机读，通过 key 查询 | 大数据量的聚合（max,min,sum, avg）查询 |
| 主要写入模式 | 随机访问，低延迟写入 | 批量导入（ETL）或者流式写入 |
| 主要应用场景 | 通过 web 方式使用的最终用户 | 互联网分析，为了辅助决策 |
| 如何看待数据 | 当前时间点的最新状态 | 随着时间推移的 |
| 数据尺寸 | 通常 GB 到 TB | 通常 TB 到 PB |
一开始对于 AP 场景，仍然使用传统数据库。在模型层面来说，SQL 足够灵活，能够基本满足 AP 查询需求。但在实现层面，传统数据库在 AP 负载中的表现（大数据量吞吐较低）不尽如人意，因此大家开始转向在专门设计的数据库中进行 AP 查询，我们称之为数据仓库（Data Warehouse）。
数据仓库
对于一个企业来说，一般都会有很多偏交易型的系统，如用户网站、收银系统、仓库管理、供应链管理、员工管理等等。通常要求高可用与低延迟，因此直接在原库进行业务分析，会极大影响正常负载。因此需要一种手段将数据从原库导入到专门的数仓。
我们称之为 ETL：extract-transform-load。
提取 转换 导入
一般企业的数据量达到一定的量级才会需要进行 AP 分析，毕竟在小数据量尺度下，用 Excel 进行聚合查询都够了。当然，现在一个趋势是，随着移动互联网、物联网的普及，接入终端的类型和数量越来越多，产生的数据增量也越来越大，哪怕初创不久的公司可能也会积存大量数据，进而也需要 AP 支持。
AP 场景下的聚合查询分析和传统 TP 型有所不同。因此，需要构建索引的方式也多有不同。
同样接口后的不同实现
TP 和 AP 都可以使用 SQL 模型进行查询分析。但是由于其负载类型完全不同，在查询引擎实现和存储格式优化时，做出的设计决策也就大相径庭。因此，在同一套 SQL 接口的表面下，两者对应的数据库实现结构差别很大。
虽然有的数据库系统号称两者都支持，比如之前的 Microsoft SQL Server 和 SAP HANA，但是也正日益发展成两种独立的查询引擎。近年来提的较多的 HTAP 系统也是类似，其为了 serve 不同类型负载底层其实有两套不同的存储，只不过系统内部会自动的做数据的冗余和重新组织，对用户透明。
AP 建模：星状型和雪花型
AP 中的处理模型相对较少，比较常用的有星状模型，也称为维度模型。
星状建模
如上图所示，星状模型通常包含一张事件表（fact table）和多张维度表（dimension tables）。事件表以事件流的方式将数据组织起来，然后通过外键指向不同的维度。
星状模型的一个变种是雪花模型，可以类比雪花（❄️）图案，其特点是在维度表中会进一步进行二次细分，将一个维度分解为几个子维度。比如品牌和产品类别可能有单独的表格。星状模型更简单，雪花模型更精细，具体应用中会做不同取舍。
在典型的数仓中，事件表可能会非常宽，即有很多的列：一百到数百列。
列存
前一小节提到的分维度表和事实表，对于后者来说，有可能达到数十亿行和数 PB 大。虽然事实表可能通常有几十上百列，但是单次查询通常只关注其中几个维度（列）。
如查询人们是否更倾向于在一周的某一天购买新鲜水果或糖果：
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 带宽、增大了读放大。
于是一个很自然的想法呼之欲出：每一个列分开存储好不好？
列式存储
不同列之间同一个行的字段可以通过下标来对应。当然也可以内嵌主键来对应，但那样存储成本就太高了。
列压缩
将所有数据分列存储在一块，带来了一个意外的好处，由于同一属性的数据相似度高，因此更易压缩。
如果每一列中值阈相比行数要小的多，可以用位图编码（ bitmap encoding[2] ）。举个例子，零售商可能有数十亿的销售交易，但只有 100,000 个不同的产品。
位图编码，游程编码
上图中，是一个列分片中的数据，可以看出只有 {29, 30, 31, 68, 69, 74} 六个离散值。针对每个值出现的位置，我们使用一个 bit array 来表示：
- bit map 下标对应列的下标
- 值为 0 则表示该下标没有出现该值
- 值为 1 则表示该下标出现了该值
如果 bit array 是稀疏的，即大量的都是 0，只要少量的 1。其实还可以使用 游程编码[3]（RLE， Run-length encoding） 进一步压缩：
- 将连续的 0 和 1，改写成
数量+值，比如product_sk = 29是9 个 0，1 个 1，8 个 0。 - 使用一个小技巧，将信息进一步压缩。比如将同值项合并后，肯定是 0 1 交错出现，固定第一个值为 0，则交错出现的 0 和 1 的值也不用写了。则
product_sk = 29编码变成9，1，8 - 由于我们知道 bit array 长度，则最后一个数字也可以省掉，因为它可以通过
array len - sum(other lens)得到，则product_sk = 29的编码最后变成：9，1
位图索引很适合应对查询中的逻辑运算条件，比如：
WHERE product_sk IN（30，68，69）
可以转换为 product_sk = 30、product_sk = 68和 product_sk = 69这三个 bit array 按位或（OR）。
WHERE product_sk = 31 AND store_sk = 3
可以转换为 product_sk = 31和 store_sk = 3的 bit array 的按位与，就可以得到所有需要的位置。
列族
书中特别提到列族（column families）。它是 Cassandra 和 HBase 中的的概念，他们都起源于自谷歌的 BigTable[4] 。注意到他们和列式（column-oriented）存储有相似之处，但绝不完全相同：
- 同一个列族中多个列是一块存储的，并且内嵌行键（row key）。
- 并且列不压缩（存疑？）
因此 BigTable 在用的时候主要还是面向行的，可以理解为每一个列族都是一个子表。
内存带宽和向量化处理
数仓的超大规模数据量带来了以下瓶颈：
- 内存处理带宽
- CPU 分支预测错误和流水线停顿[5]
关于内存的瓶颈可已通过前述的数据压缩来缓解。对于 CPU 的瓶颈可以使用：
- 列式存储和压缩可以让数据尽可能多地缓存在 L1 中，结合位图存储进行快速处理。
- 使用 SIMD 用更少的时钟周期处理更多的数据。
列式存储的排序
由于数仓查询多集中于聚合算子（比如 sum，avg，min，max），列式存储中的存储顺序相对不重要。但也免不了需要对某些列利用条件进行筛选，为此我们可以如 LSM-Tree 一样，对所有行按某一列进行排序后存储。
注意，不可能同时对多列进行排序。因为我们需要维护多列间的下标间的对应关系，才可能按行取数据。
同时，排序后的那一列，压缩效果会更好。
不同副本，不同排序
在分布式数据库（数仓这么大，通常是分布式的）中，同一份数据我们会存储多份。对于每一份数据，我们可以按不同列有序存储。这样，针对不同的查询需求，便可以路由到不同的副本上做处理。当然，这样也最多只能建立副本数（通常是 3 个左右）列索引。
这一想法由 C-Store 引入，并且为商业数据仓库 Vertica 采用。
列式存储的写入
上述针对数仓的优化（列式存储、数据压缩和按列排序）都是为了解决数仓中常见的读写负载，读多写少，且读取都是超大规模的数据。
我们针对读做了优化，就让写入变得相对困难。
比如 B 树的原地更新流是不太行的。举个例子，要在中间某行插入一个数据，纵向来说，会影响所有的列文件（如果不做 segment 的话）；为了保证多列间按下标对应，横向来说，又得更新该行不同列的所有列文件。
所幸我们有 LSM-Tree 的追加流。
- 将新写入的数据在内存中 Batch 好，按行按列，选什么数据结构可以看需求。
- 然后达到一定阈值后，批量刷到外存，并与老数据合并。
数仓 Vertica 就是这么做的。
聚合：数据立方和物化视图
不一定所有的数仓都是列式存储，但列式存储的种种好处让其变得流行了起来。
其中一个值得一提的是物化聚合（materialized aggregates，或者物化汇总）。
物化，可以简单理解为持久化。本质上是一种空间换时间的 tradeoff。
数据仓库查询通常涉及聚合函数，如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果这些函数被多次用到，每次都即时计算显然存在巨大浪费。因此一个想法就是，能不能将其缓存起来。
其与关系数据库中的视图（View）区别在于，视图是虚拟的、逻辑存在的，只是对用户提供的一种抽象，是一个查询的中间结果，并没有进行持久化（有没有缓存就不知道了）。
物化视图本质上是对数据的一个摘要存储，如果原数据发生了变动，该视图要被重新生成。因此，如果写多读少，则维持物化视图的代价很大。但在数仓中往往反过来，因此物化视图才能较好的起作用。
物化视图一个特化的例子，是数据立方（data cube，或者 OLAP cube）：按不同维度对量化数据进行聚合。
数据立方
上图是一个按日期和产品分类两个维度进行加和的数据立方，当针对日期和产品进行汇总查询时，由于该表的存在，就会变得非常快。
当然，现实中，一个表中常常有多个维度，比如 3-9 中有日期、产品、商店、促销和客户五个维度。但构建数据立方的意义和方法都是相似的。
但这种构建出来的视图只能针对固定的查询进行优化，如果有的查询不在此列，则这些优化就不再起作用。
在实际中，需要针对性的识别（或者预估）每个场景查询分布，针对性的构建物化视图。
参考资料
[1]DDIA 读书分享会: https://docs.qq.com/sheet/DWHFzdk5lUWx4UWJq
[2]bitmap encoding: https://en.wikipedia.org/wiki/Bitmap_index
[3]游程编码: https://zh.wikipedia.org/zh/%E6%B8%B8%E7%A8%8B%E7%BC%96%E7%A0%81
[4]BigTable: https://en.wikipedia.org/wiki/Bigtable
[5]流水线停顿: https://zh.wikipedia.org/wiki/%E6%B5%81%E6%B0%B4%E7%BA%BF%E5%81%9C%E9%A1%BF
