DDIA阅读笔记(一)-数据系统的基石

第一章：可靠性、可伸缩性、可维护性

应用的两个分类：

• data-intensive：问题通常来自数据量、数据复杂性、以及数据的变更速度。
• compute-intensive：瓶颈在于CPU。

可靠性

可以把可靠性粗略理解为 “即使出现问题，也能继续正确工作”。

造成错误的原因叫做 故障（fault），能预料并应对故障的系统特性可称为 容错（fault-tolerant） 或 韧性（resilient）。

fault种类：

• 硬件故障（hardware faults）
  • 增加单个硬件的冗余度：磁盘可以组建RAID、服务器使用双路电源和热拔插CPU等。
  • 云平台的设计就是优先考虑 灵活性（flexibility）和 弹性（elasticity），而不是单机可靠性。
  • 引入软件容错机制。
• 系统性错误（systematic error）
  • 软件错误
  • 修复问题代码、进程隔离、监控分析
• 人为错误
  • 以最小化犯错机会的方式设计系统：精心设计的API
  • 与最容易犯错的模块解耦
  • 彻底的测试：单元测试、系统测试
  • 允许从人为错误中简单快速地恢复：快速回滚配置变更、分批发布新代码。
  • 配置详细地监控，比如性能指标和错误率。

可伸缩性

可伸缩性（Scalability） 是用来描述系统应对负载增长能力的术语。

描述性能的指标：

• 吞吐量（throughput）：每秒可以处理的记录数量。或者在特定规模数据集上运行作业的总时间。
• 响应时间（response time）：客户端发送请求到接收响应之间的时间。
  • 响应时间的高百分位点（尾部延迟）指标非常重要

处理方法：

• 垂直伸缩：转向更强大的机器。
• 水平伸缩：负载分布到多台小机器。

弹性（elastic）：在检测到负载增加时自动增加计算资源

可维护性

三个设计原则来避免自己的软件系统变为遗留系统：

• 可操作性
• 简单性
• 可演化性

可操作性

• 监控系统提供可见性
• 将系统与标准化工具集成
• 避免单机部署
• 提供良好的文档
• 提供良好的默认行为（配置参数？）
• 自我修复
• 行为可预测

简单性

消除额外复杂度的最好工具之一是抽象。

抽象帮助我们控制系统复杂度。

可演化性

系统的需求是变化的，使用敏捷工作模式来应对，例如TDD和重构。

第二章：数据模型与查询语言

问题：需要将数据模型抽象成对应的概念。

每个层都通过提供一个明确的数据模型来隐藏更低层次中的复杂性。

关系模型和文档模型

关系模型

常见分类：

• TP（事务性）：银行交易
• AP（分析型）：数据报表
• HTAP（混合型）

问题：关系模型很难直观表达一对多的关系．

文档模型的优势：

• 模式灵活：动态增删字段
• 更好的局部性：一个人的所有属性被集中访问
• 结构表达语义：JSON的树状结构能够表达语义

层次模型

几个要点：

• 树状结构，每个节点只允许一个父节点
• 节点存储数据，节点分类型
• 节点间使用指针连接

网状模型

多对一和多对多都由路径来表示，访问记录的唯一方式是顺着元素路径访问。

文档模型

文档型数据库的使用场景：

• 多种类型数据，放一张表不合适
• 数据类型和结构由外部决定，没办法控制数据的变化

MySQL和PgSQL支持JSON。

数据查询语言

分为声明式语言（SQL）和命令式语言（通用编程语言）。

命令式语言的优点：

• 描述目标复杂时，声明式表达能力不够。
• 可以通过抽象、编程范式等，让代码兼顾表达力和清晰性。

MapReduce

MapReduce模型：

• 借鉴自函数式编程
• 简单的编程模型

特点：

• 要求Map和Reduce是纯函数
• 非常底层，但是表达力强大，可基于其实现高级查询语言，例如Hive。

注意点：

• 不是所有的分布式SQL都基于MapReduce
• 不是只有MapReduce才能嵌入通用语言
• MapReduce有一定的理解成本

图模型

典型案例：

• 社交图谱
• 网络图谱
• 公路或铁路网络

应用场景：

• 文档数据库：数据都是自我包含的，文档之间的关系非常稀少
• 图数据库：任意事物都能其他事务相关联

第三章：存储与检索

存储使用的数据结构

世界上最简单的数据库案例：

#!/bin/bash
db_set () {
  echo "$1,$2" >> database
}

db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

两个bash函数实现了键值存储的功能，该模式下更新旧版本时不会覆盖，而是向文件末尾追加记录，查找最新值时，找到文件中key出现的最后一次位置。

当数据量激增，需要使用索引对查询进行优化。

大致思想：通过保存一些额外的元数据作为index帮我们找到想要的数据。

需要权衡的点：索引加快了读查询的速度，拖慢了写入的速度。

散列索引

将每个键都进行一次哈希映射，并存储到相应的偏移量位置，当查询指定键时，使用哈希函数计算出相应的值，并读取指定偏移位置的数据。Bitcask存储模型使用的该种方式，该结构适合多次更新键对应的值的情况。

优化的点：每当日志增长到对应阈值时，开始写入一个新的日志文件，并对之前的日志进行compaction。（Bitcask的Merge策略是类似方案）

实现过程中要考虑的问题：

• 文件格式：使用二进制最快，字节为单位进行编码
• 删除操作：删除操作向日志尾追加一个删除记录，当进行compaction时将被删除的数据都丢弃掉。
• 奔溃恢复：当数据库重新启动，需要从磁盘中的日志文件进行数据恢复。
• 部分写入记录：考虑写入校验和等信息
• 并发控制：保证线程安全

Q：为什么删除操作设计成追加方式，而不是直接在日志中进行修改？

• 追加操作是磁盘顺序写，比随机写入快
• 日志文件仅追加的话，并发和崩溃恢复更简单。’
• merge操作可以避免文件碎片化。

散列结构的局限性：

• 所有key必须放内存，存在大量的随机IO
• 范围查询效率不高，需要逐个遍历

SSTables和LSM Tree

将上述的键值对按照键排序，这个结构被称为Sorted String Table，要求每个键只出现一次（merge保证），该结构有如下优势：

1. 文件大于可用内存，合并操作仍然有效。
2. 可以通过类似二分查找的方式去查找（顺序列表特性）
3. 可以将table分组为block，并将其写入磁盘。

如何构建和维护SSTables？

• 构建：在内存中维护一个有序结构（MemTable），使用RB Tree、AVL Tree等
  • 达到指定阈值后全量dump到外存
  • 查询逻辑：
    1. 先去MemTable中查找，如果命中则返回。
    2. 否则再去SSTable按时间顺序由新到旧逐个查找。

存在的问题：出现宕机，内存中数据结构会丢失，使用WAL解决该问题

将上述内容继续优化，就会得到LevelDB和RocksDB所有的存储引擎LSM-Tree(Log-Structured Merge-Tree)，ElasticSearch使用的Lucene 也是使用类似结构。

优化：

• 优化SSTable的查找：使用Bloom Filter做数据初筛。

• 层次化组织SSTable：控制Compaction的顺序和时间，常用的有：size-tiered 和 leveled compaction

  • size-tiered：较新、较小的SSTables合并到较大、较旧的SSTables中。
  • leveled compaction：key被按照范围拆分到较小的SSTables，较旧的数据被移动到单独的level。

LSM-Tree的核心思想：保存一组合理组织、后台合并的SSTables。

B Tree

B Tree目前用于几乎所有的关系型数据库中，支持高效的定值查询和范围查询。

B Tree的优化：

• 不使用WAL，在写入时利用Copy On Write 技术。
• 对中间节点的key做压缩，增大了分支。
• 为了优化范围查询，有的B Tree将叶子节点存储时物理连续，但是数据插入时，维护有序性的代价很大。
• 为叶子节点增加兄弟指针（B+Tree），避免顺序查找时的回溯。

B Tree 对比 LSM Tree

存储引擎	B-Tree	LSM-Tree
优势	读取快	写入快
写放大	数据和WAL；更改数据时多次覆盖整个Page	数据和WAL；Compaction
写吞吐	低，存在大量随机写	顺序写入，写吞吐较高
压缩率	存在较多内部碎片	更紧凑，没有内部碎片
存储放大	有些Page没有用满	同一个key存储多遍
并发控制	同一个key只存在一个地方；树结构容易被范围锁	同一个key存多变，使用MVCC控制

其他结构

聚集索引和非聚集索引：

• 数据本身按照某个字段有序存储，基于该字段的索引被称为聚集索引。
• 索引中只存数据的引用的被称为非聚集索引。
• 一部分列嵌到索引中存储，剩余列额外存储，称为覆盖索引。

多列索引

多个字段联合查询的场景十分常见：

SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004;

方案：

• 将latitude和longitude合并存储，转为一维
• 使用类似R Tree的地理空间索引存储
• 使用类似MySQL的联合索引解决

全文索引和模糊索引

Lucene 中索引是字符的有限自动机，类似于Trie，支持在给定编辑距离内搜索单词。

全内存数据结构

内存数据库的优点：

• 提供丰富的数据抽象
• 实现简单

基于非易失性存储器（non-volatile memory，NVM）的存储引擎是最近的研究热点。

事务性 or 分析性

两者对比：

属性	事务处理系统 OLTP	分析系统 OLAP
主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
主要写入模式	随机访问，写入要求低延时	批量导入（ETL）或者事件流
主要用户	终端用户，通过 Web 应用	内部数据分析师，用于决策支持
处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
数据集尺寸	GB ~ TB	TB ~ PB

一开始OLAP仍然使用传统数据库，但是传统数据库在AP负载表现较差，因此转向专门做AP查询的数据仓库。

数据仓库

数仓是一个独立的数据库，从OLTP数据库提取数据，转换成适合分析的结构，清理并加载到数仓中，这个过程称为：抽取-转换-加载（ETL）。

分歧

数仓的数据模型通常是关系型的，但是查询引擎和存储格式优化方面，与OLTP数据库差别十分大。

星状型 雪花型

• 星状型：包含一张事件表和多张维度表，数据表以事件流方式将数据组织起来，然后用外键指向不同的维度。
• 雪花型：会在上述的维度表中进行二次细分。

列式存储

传统数据库按行存储，如果只查询一个字段，也必须从磁盘中取出剩余字段，浪费了IO带宽，增大了读放大。

如果将每一列的所有值存储在一起，查询效率大大增加。

列压缩

当列中存在大量重复的数据，可以考虑对其进行压缩存储，数仓中特别有效的技术是位图编码。

列族

这是HBase和Cassandra中的概念，从BigTable继承，每个列族中，将一行中所有列与行键一起存储，并且不使用列压缩。

因此BigTable在使用时主要面向行，可以理解为每个列族是一张子表。

内存带宽和向量化处理

数仓的超大规模数据量带来的瓶颈：

• 内存处理带宽
• CPU分支预测错误

解决：

• 列式存储和压缩可以让数据缓存在L1中，结合位图快速处理
• 使用SIMD、在更少的时钟周期处理更多的数据。

排序

可以像LSM-Tree那样，对所有行按某一列排序后存储。

不同副本，不同排序

对数据的不同部分按照不同列进行有序存储，这样可以提供给不同查询需求，已有商用数仓Vertica 采用。

列式存储的写入

类似于LSM-Tree的追加操作：

• 新写入的数据在内存中Batch好，按行按列，具体结构看需求
• 达到指定阈值，批量刷到外存，并于老数据合并。

聚合

数仓查询通常涉及聚合函数，每次即时计算都会存在巨大浪费，可以考虑将其缓存下来。

与关系型数据库的View差别较大，视图是逻辑存在的，当物理存储发生改变，视图需要重新生成，写多读少的情况，维护代价很大。

数仓中的物化视图将其持久化存储，维护代价较低。

第四章：编码和演进

编码格式

涉及到跨进程通信，都需要对数据进行编码（序列化），因为通信都是面向字节流的，编码涉及两方面问题：

• 如何编码能够节省空间、提高性能。
• 如何编码以适应数据的演化和兼容。

当应用程序更新后，系统要顺利运行，要保证双向兼容性：

• 向后兼容：新代码读取旧数据
• 向前兼容：旧代码读取新数据

程序使用两种形式的数据：

• 内存中的数据结构
• 网络通信时，编码成的字节序列

语言特定格式

编程语言内置了将内存对象编码为字节序列的组件：

• java.io.Serializable
• Marshal
• pickle
• 第三方库

这类存在的问题：

• 与编程语言深度绑定，其他语言很难读取这类数据
• 解码过程需要实例化任意类，存在安全问题：RCE
• 不存在数据版本控制
• 编解码效率低

JSON、XML等

存在的问题：

• 数值的编码存在歧义：不能区分整数和浮点数
• 不支持二进制数据的字节序列
• XML和JSON支持额外的模式，但是增加了复杂度

二进制编码

如果数据只被单一程序读取，而不进行交换，不需要易读性等问题，可以使用二进制编码，其空间、速度方面都很可观。

Thrift与Protocol Buffers

上述两个是基于相同原理开发的二进制编码库

Protocol Buffers的接口定义语言（IDL）如下所示：

message Person {
    required string user_name       = 1;
    optional int64  favorite_number = 2;
    repeated string interests       = 3;
}

IDL与编程语言无关，可以利用代码生成工具，将上述IDL翻译为指定语言的代码。

Thrift还支持不同的编码格式：BinaryProtocol、CompactProtocol、JSON等

优势：

• 省去字段名，更加紧凑
• 模式是数据的注释或文档，总是最新
• 数据模式允许不读取数据
• 对于静态类型来说 ，可以利用代码生成做编译时的类型检查

数据流模型

• 经过数据库的数据流
• 经过服务的数据流：REST和RPC
  • REST是一种设计哲学
  • RPC问题：
    • 请求出现请求丢失、相应丢失等情况，需要重试
    • 重试需要考虑幂等性
    • 两端编程语言不同可能会有影响
• 经过消息传递的数据流