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解决该问题

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

优化:

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

  • 层次化组织SSTable:控制Compaction的顺序和时间,常用的有:size-tieredleveled 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问题:
      • 请求出现请求丢失、相应丢失等情况,需要重试
      • 重试需要考虑幂等性
      • 两端编程语言不同可能会有影响
  • 经过消息传递的数据流