第一部分、数据系统基础

第一章：可靠、可扩展与可维护的应用系统

当今许多新型应用都属于数据密集型，而不是计算密集型。对于这些类型应用， CPU的处理能力往往不是第一限制性因素，关键在于数据量、数据的复杂度及数据的快速多变性。

• 常见的数据系统模块

1. 数据库：用以存储数据，这样之后应用可以再次面问。
2. 高速缓存： 缓存那些复杂或操作代价昂贵的结果，以加快下一次访问。
3. 索引： 用户可以按关键字搜索数据井支持各种过滤。
4. 流式处理：持续发送消息至另一个进程，处理采用异步方式。
5. 批处理： 定期处理大量的累积数据。

一个常见的数据系统，往往有多个模块组成，各自负责不同的工作。

可靠性

当出现意外情况如硬件、软件故障、人为失误等，系统应可以继续正常运转：虽然性能可能有所降低，但确保功能正确。

• 什么是一个可靠的应用？

1. 应用程序执行用户所期望的功能。
2. 可以容忍用户出现错误或者不正确的软件使用方法。
3. 性能可以应对典型场景、合理负载压力和数据量。
4. 系统可防止任何未经授权的访问和滥用。

硬件故障

硬盘崩溃，内存故障，电网停电，甚至有人误拔掉了网线。

• 传统防止硬件故障的方式：

磁盘配置 RAID，服务器配备双电源，甚至热插拔CPU， 数据中心添加备用电源、发电机等。

当一个组件发生故障，元余组件可以快速接管，之后再更换失效的组件。

• 现代硬件容错

随着数据量和应用计算需求的增加，现代应用运行在大规模机器上，随之而来的硬件故障率呈线性增长。

依靠传动办法以难以应对故障发生的频率，故而需要使用软件来做容错。

如当需要重启计算机时为操作系统打安全补丁，可以每次给一个节点打补丁然后重启，而不需要同时下线整个系统（滚动升级）

软件错误

• 常见的软件错误

1. 一个应用进程使用了某些共享资源如CPU、内存、磁盘或网络带宽，但却不幸失控跑飞了。
2. 系统依赖于某些服务，但该服务突然变慢，甚至无响应或者开始返回异常的响应。
3. 级联故障，其中某个组件的小故障触发另一个组件故障，进而引发更多的系统问题。

软件bug通常会长时间处于引而不发的状态，知道碰到特定条件才会触发。

软件错误有时没有快速的解决办法，只能仔细考虑更多的细节，认真检查依赖的假设条件与系统之间交互，进行全面的测试，进程隔离，允许进程崩溃并自动重启，反复评估，监控并分析生产环节的行为表现等。

人为失误

人无法做到万无一失。人是不可靠的，那么该如何保证系统的可靠性呢？

• 以最小出错的方式来设计系统（接口最小依赖，单一职责）

精心设计的抽象层，API以及管理界面，使“做正确的事情”很轻松，搞破坏很难。

• 想办法分离容易出错的地方（灰度环境）

提供一个功能齐 全但非生产用的沙箱环境，使人们可以放心的尝试、体验，包括导人真实的数 据，万一出现问题，不会影响真实用户。

• 充分测试（自动化全面测试）

从各单元测试到全系统集成测试以及手动测试。

• 当人为出现错误时，提供快速恢复机制尽量减少故障影响（小范围发布和回滚）

快速回滚配置改动，滚动发布新代码，并提供校验数据的工具。

• 详细的监控（链路追踪）

包括性能指标和错误率。链路追踪等。

• 推行管理流程并培训

重要且复杂。

可扩展性

随着规模的增长，例如数据量、流量或复杂性，系统应以合理的方式来匹配这种增长。

系统现在工作可靠，并不意味着它将来一定能够可靠运行。

如何描述负载

按“扇出”来描述

多个明星发布消息（生产者）

这些消息被推送给更多的用户（消费者）

每个用户维护一个时间线缓存。当有人发布新tweet，查询其关注者，将tweet插入到每个关注者的时间线缓存中。（推送效率随着关注者数量线性增长）

对于大V，让用户采用主动拉取的方式。

所谓的负载，应当为可线性描述。

描述性能

批处理系统中，通常关心吞吐量，每秒可处理的记录条数，某个指定数据集运行作业需要的总时间。

现在系统通常看中服务的响应时间，客户端从发送请求到接收响应之间的间隔。

**产生延迟的原因：**上下文切换和进程调度、网络数据包丢失和TCP重传、垃圾回收暂停、缺页中断和磁盘I/O，甚至服务器机架的机械振动。

• 中位数指标：一半用户的请求延迟低于此指标，另一则大于，可以很好的反映总体延迟情况。
• P999：有99.9%的请求响应时间快于阈值。这将直接影响用户的总体服务体验。（亚马逊，响应时间每增加100ms，销售额就下降1%）

应对负载增加的方法

当负载增加时，应该如何保证良好性能？

针对特定级别设计的架构，不太可能应付超出预设目标10倍的实际负载。

因此，负载增加时，应在在垂直扩展（即升级到更强大的机器）和水平扩展（即将负载分布到多个更小的机器）之间做取舍。

把无状态服务分布然后扩展至多台机器相对比较容易，而有状态服务从单个节点扩展到分布式多机环境的复杂性会大大增加。

对于有状态服务，将数据库运行在一个节点上（采用垂直扩展策略）， 直到高扩展性或高可用性的 要求迫使不得不做水平扩展。

最理想的扩展是具有弹性的，数据量增加自动扩容，数据量减少，自动缩容。（弹性）

可维护性

随着时间的推移，许多新的人员参与到系统开发和运维， 以维护现有功能或适配新场景等，系统都应高效运转。

• 监视系统的健康状况，井在服务出现异常状态时快速恢复服务。
• 追踪问题的原因，例如系统故障或性能下降。
• 保持软件和平台至最新状态， 例如安全补丁方面。
• 了解不同系统如何相互影响，避免执行带有破坏性的操作。
• 预测未来可能的问题，并在问题发生之前即使解决（例如容量规划）。
• 建立用于部署、配置管理等良好的实践规范和工具包。
• 执行复杂的维护任务， 例如将应用程序从一个平台迁移到另一个平台。
• 当配置更改时，维护系统的安全稳健。
• 制定流程来规范操作行为，并保持生产环境稳定。
• 保持相关知识的传承（如对系统理解），例如发生团队人员离职或者新员工加入 等。
• 提供对系统运行时行为和内部的可观测性，方便监控。
• 支持自动化， 与标准工具集成。
• 避免绑定特定的机器，这样在整个系统不间断运行的同时，允许机器停机维护。
• 提供良好的文档和易于理解的操作模式，诸如“如果我做了X，会发生Y”。
• 提供良好的默认配置，且允许管理员在需要时方便地修改默认值。
• 尝试自我修复，在需要时让管理员手动控制系统状态。
• 行为可预测，减少意外发生。

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

语言的边界就是世界的边界。

一一Ludwig Wittgenstein, 《逻辑哲学论》 ( 1922)

关系模型

SQL是最著名的关系数据模型，数据被组织成关系（表），每个关系都是元组的无序集合（行）。

关系模型的目标是将实现细节隐藏在更简洁的接口后面。

对象和关系的不匹配

如果数据存储在关系表中， 那么应用层代码中的对象与表、行和列的数据库模型之间需要一个笨拙的转换层。

• 如何在关系模型中表示简历

一个简历信息，通过userid在多个表之间关联。如果想要获取一个完整的简历，需要查询多个不同的表。

• 优点：可以读取表中的任何一行或者多行，支持任意条件查询。可以使用列作为条件，匹配这些列来读取特定行。可以在任何表中插入新行，而不用关心与其他表之间的关系问题。（业务逻辑可能需要关系，但数据本身不需要关心）

文档模型

由一些特定的键来确定文档，此文档中存在多个不同的属性，每个属性又指向一个文档数据（此数据可能多个文档共享）。

用户可以通过键来高效的获取此文档。（一次获取文档内容）

和关系模型对比

优点

• 文档模型

文档模型主要是模式灵活，由于数据局部，所以可以带来更好的性能，对于应用程序来说，更接近应用程序所使用的数据结构。

• 关系模型

强在联结操作，多对一和多对多关系更简洁。

缺点

• 文档模型

文档模式修改如果变更了文档的大小，可能需要重写整个文档。且如果文档内容过大，即使只需要文档中的一小部分内容，也必须加载整个文档。

• 关系模型

如果数据被划分在多个表中，查询则需要多次磁盘IO，花费大量的时间。

融合

大多数关系数据库系统 （MySQL除外）都支持XML。其中包括 对XML文档进行本地修改，在XML文档中进行索引和查询等，这样应用程序可以获得与文档数据库非常相似的数据模型。

随着时间的推移，关系数据库和文档数据库变得越来越相近。

查询语句

• 命令式查询语言（编程语言常见）

告诉计算机以特定的顺序执行某些操作。你完全可以推理整个过程，逐行遍历代码、评估相关条件、更新对应的变量，并决定是否再循环一遍。

• 声明式查询语言（关系模型常用）

1

SE LECT * FROM animals WHERE family =’Sharks';

只需指定所需的数据模式，结果需要满足什么条件，以及如何转换数据，而不需要说明如何实现这一目标。数据库系统的查询优化器会决定采用哪些索引和联结，以及用何种顺序来执行查询的各个语句。

能够在不改变查询语句的情况下提高性能。

• MapReduce查询

MapReduc e是一种编程模型，用于在许多机器上批量处理海量数据，兴起于 Google。大部分NoSQL（Not only sql）数据库都支持有限的MapReduce方式的执行只读查询。

**MapReduce既不是声明式查询语句也不是命令式查询语句。而是介于二者之间的。**主要包括map和reduce两个函数组成。

假设你是一名海洋生物学家，每当你看到海洋中的动物时， 就会在数据库 中添加观察记录。现在你想生成一份报告，来说明每个月看到了多少鲨鱼。

在PostgreSQL中的查询：

1
2
3
4
5

SELECT date_trunc(’month ’, observation_timestamp) AS observation_month,
sum(num_animals) AS total_animals 
from observations
WHERE family= 'Sharks' 
GROUP BY observation_month ; 

先对物种过滤，只查询鲨鱼，然后根据月份分组，汇总每个月的动物数量。

MongoDB中的MapReduce功能也可以实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

db.observations.mapReduce( 
function map() {
var year = this. observationTimestamp.getFullYear(); 
var month = this.observationTimestamp.getMonth() + 1; 
emit (year +"-"+ month, this.numAnimals);  
},
function reduce(key, values) {
	return Array.sum(values);
},
{
query: { family:"Sharks"},
out :"monthlySharkReport"
   }
);

1. 通过query方法指定种类为鲨鱼
2. 对于所有需要查询的文档，都会调用一次map函数
3. map函数返回一个KV对，其中key是年份和月份字符串，value为动物的数量
4. map方法的kv对被reduce函数接收，并汇总。
5. 最后通过out方法输出到monthlySharkReport。

MapReduce用于在计算集群上分布执行。必须编写两个密切协调的函数，一个对于多个数据过滤需要的条件，另一个对于过滤出的条件进行汇总。

第三章： 数据存储和检索

如果你把东西整理得井井有条， 下次就不用查找了。

​ —–德国谚语

数据库的核心：数据结构

日志

如果所有的数据都以KV的形式简单存储在一个文件中。

每次新增数据：在文件末尾追加新的KV，如果多次更新某个键，旧的值不会被覆盖，文件最后一次出现的KV表示最新的值。

只追加到末尾形式，写性能很好，但读取非常困难。

写入开销几乎为O(1)，查询开销为O(n)

哈希索引

数据以KV和追加的形式存储在磁盘中，在内存中建立key对应偏移量的hashmap。每次查询通过内存中的hashmap获取偏移量，通过偏移量高效的读取磁盘上的数据。

Bitcask（Riak中的默认存储引擎）所采用的做法。

可以提供高效读写，只要所有的key放到内存中，而vlaue都保存在磁盘上。只需要一次磁盘IO就可以把Value加载到内存中。

此种结构非常适合值频繁更新的场景，适合key不是特别多，但更新特别频繁的情况。

• 磁盘数据的压缩

由于数据依然采用文件追加的形式保存，所以当文件达到一定大小，就新建一个文件来追加。此时老文件可以进行压缩操作。

• 哈希索引的局限性

1. hash表必须全部存在内存中（如果放到磁盘里，修改需要大量的随机IO，效果很差）
2. 区间查询效率不高，对于范围查询只能扫描所有键，来确定当前键是否数据对应范围

SSTable和LSM-Tree

在hash索引的基础上，新增要求，对KV要求按照顺序排序。

排序字符串表（SSTable）

• 压缩过程

• 如何写入数据

存储虽然是有序，但写入并不会按照排序的顺序写入。那该如何在乱序写入时保证顺序追加？

1. 在内存中维护一个AVL结构树（红黑树）
2. 当内存大于某个阈值时，就把树写入到新的磁盘段中。
3. 读取数据：先在内存表中查找键，然后去最新的磁盘段中查找，接下来是次新段。
4. 后台线程周期性合并磁盘的段。

• 从SSTable到LSM-Tree

LSM-Tree(Log-Structured Merge-Tree)：以日志结构的合并树

如果查找不存在的值：需要先查询内存表，在根据内存表查找每个磁盘段，直到最后一个段。

可以添加布隆过滤器来过滤掉不存在的值，但会占用额外空间

LSM-Tree的思想：

1. 数据集远远大于可用内存，它仍然能正常工作。
2. 由于数据按排序存储，可以有效的进行范围查询。
3. 由于磁盘是顺序写入，所以LSM-Tree可以支持非常高的写入吞吐量。

B-Trees

最常见，也几乎是最标准的数据存储结构。

有序：按键值来排序KV对（可以范围查找）

把数据库分成固定大小的块和页，传统大小为4kb，页是内部读写的最小单位。这样更接近硬件，因为磁盘也是固定大小的块排序。

每个页都使用地址来进行标识，这样可以让一个页引用另一个页。（形成链表），每个指针都指向磁盘地址。

某个页被指定为B-tree的根，所有查询都需要从根页开始。根页包含若干个键和对子页的引用，每个子页都负责一个连续范围内的键，相邻的键指示这些范围之间的边界。

页的分裂：如果修改或新增值在页的范围内，修改对应页并刷盘。如果添加的新键，页中没有足够的空间容纳新键，则需要将此页分裂成两个半满的页，并且父页也需要包含分裂后新键的范围。

通过分裂，可以确保树始终保持平衡，且查询效率为Logn，分支因子为500的4k页，四级树可以存储256TB的数据。

如何使B-Tree可靠

• 可能存在的问题

B-Tree的写操作，需要覆盖磁盘上的旧页。（LSM-tree只在文件末尾追加写入，不会修改文件）

修改操作在机械磁盘上的操作：磁头移动到正确位置，旋转盘面，用新的数据覆盖相应的扇区。

SSD：必须一次擦除并重写非常大的存储片块。

在分裂的情况下：需要写两个分裂页，并修改父页对两个子页的引用。

如果部分页写入后发生了崩溃，会导致索引被破坏，出现孤儿页。

• 通过预写日志来解决（WAL：write-ahead log，重做日志）

  mysql中对应redo log

通过一个仅支持追加修改的日志文件，每次B-tree修改操作，都需要先修改WAL，然后再修改树本身的页。当数据库崩溃后，通过该日志恢复到最近的一致状态。

• 通过日志可以解决原子性问题，在并发状态下与锁配合，可以做到原子更新。

• 数据连续的不同页在磁盘上可能不是连续的，可以通过分区尽量把连续的数据放到一起。但如果数据量特别大，此成本将远远高于LSM-Tree

LSM-Tree vs B-tree

LSM-Tree写入更快，B-tree 查询效率高

• 写放大

指完成一次写入操作，需要向硬盘中进行多少次写操作。

现代固态硬盘可以把磁盘的随机写入变成顺序写入，但更小的写放大依然可以带来更高的性能。

• 内存数据库和磁盘数据库对比

内存数据库的优点并不是不需要读取磁盘。如果内存足够大，完全可以把磁盘结构的数据存储到内存中。

内存数据库的优点在于不需要使用磁盘的格式对内存数据结构编码的开销。（内存数据库中可以直接按照应用使用的内存结构来存储数据，而无需转换）

事务处理与分析处理

事务主要指组成一个逻辑单元的一组读写操作。（不一定具有ACID属性）

OLTP（事务处理系统）与OLAP（分析系统）

mysql是典型的OLTP与OLAP同时处理的数据库。但随着发展，公司放弃使用OLTP 系统用于分析目的，而在单独的数据库上运行分析。

数据仓库

数据仓库包含公司所有各种OLT 系统的只读副本。从OLTP数据库（使用周期性数据转储或连续更新流） 中提取数据，，转换为分析友好的模式。

• ETL

  将数据导入数据仓库的过程称为提取－转换－加载。（Extract-Transform-Load）

星型与雪花型分析模式

• 星型表

一个事实表关联多个维度的配置信息表

列式存储

大部分OLTP数据都是按行来存储数据，如果一行数据有上百个列（甚至更多），则按列式存储是一个更好的方式。

• 列式存储的思想

不要将一行数据中的所有值存储在一起，，而是将每列中的所有值存储在一起。如果每个列存储在 个单独的文件中，查询只需要读取和解析在该查询中使用的那些列，这可以节省大量的工作。

• 列压缩

列式存储出现了大量的重复数据，对于这些大量重复的列可以做压缩。

压缩思路

用一个超长的二进制字符串，每一位代表每一行，0/1表示是否存在，每个枚举值对应当前值的位图。这样可以把大量重复的值都存储在同一个位图里。如果多个值查询只需把多个位图的值做或运算。

对与二进制位图本身，也可以使用游程编码的方式来进一步压缩。（第一个数字表示前置0，后一个表示1，然后交替）

• 列式存储如何排序

规定排序的列应尽可能的让具有相同值的列排在一起，这样可以更好的压缩数据。

如果业务必须要按照不同的排序条件来查询数据，可以考虑按不同的规则复制几份不同的列存储。

现代生产中数据本身就会被备份多份，不如利用起来，按照不同的排序规则备份相同数据，然后根据业务决定查询哪一份。

• 列式存储的写操作

对于排序后的列式存储，如果按照常规原地更新的方式插入数据，那将重写所有的列，这是灾难性的。

vertica的做法：参考LSM-tree的解决方案，先把数据存储在内存中，当达到一定阈值，与磁盘中的列文件合并，生成新的列文件。

查询时，先查询内存中是否存在，再去磁盘中搜索列。

• 现代使用列式存储的数据库（扩展）

1. ClickHouse: 一个开源的分布式列式数据库，以其惊人的查询速度闻名。它非常适合处理海量数据，常用于实时分析、用户行为分析和日志处理等场景。
2. Apache Druid: 一个为实时分析设计的开源数据库。它在处理流数据、快速聚合和亚秒级查询方面表现出色，常用于实时数据仪表盘和事件驱动的分析应用。
3. Vertica: 一个高性能的企业级列式数据库，专为大规模数据仓库和商业智能（BI）场景设计，支持复杂的分析查询。
4. Apache HBase: 一个基于 Hadoop HDFS 的分布式、面向列的数据库。它提供对海量数据的随机、实时读写访问，常用于日志分析、实时推荐等场景。
5. Apache Cassandra: 一个分布式、高可用的 NoSQL 数据库。它的数据模型是“宽列存储”，虽然也常被归为列式家族，但其设计更侧重于高写入吞吐量和跨数据中心的容错性。