🌐 Part 1 数据系统的基石
🛡️CH 1 可靠性、可伸缩性和可维护性
服务级别目标（SLO, Service Level Objectives）
服务级别目标（SLO）是一种性能目标，它定义了服务提供者希望达到的服务水平。SLO通常包括服务的可用性、响应时间、吞吐量等关键性能指标（KPIs）。SLO是服务提供者内部的目标，它们可以用于监控服务性能，并作为改进服务的基准。SLO是服务级别协议（SLA）的基础，但它们不具有法律约束力，更多是作为内部标准来使用。
服务级别协议（SLA, Service Level Agreements）
服务级别协议（SLA）是服务提供者和消费者之间的正式协议，它详细说明了服务提供者承诺提供的服务水平。SLA通常包括服务的可用性、响应时间、支持水平、问题解决时间等指标，并且这些指标都有明确的服务级别目标。SLA具有法律约束力，如果服务提供者未能达到SLA中规定的标准，可能会面临罚款或其他形式的处罚。
头部阻塞（Head-of-Line Blocking, HOL Blocking）
头部阻塞是计算机网络和多线程系统中的一个术语，指的是在多队列系统中，一个队列的头部（即等待时间最长的元素）由于资源被其他队列占用而无法前进，导致整个系统的性能下降。例如，在数据库系统中，如果一个事务持有锁并且正在等待其他资源，它就会阻塞在其后面的所有事务，即使这些事务不依赖于被锁定的资源。这种现象会导致系统效率降低，因为它阻止了其他可以独立处理的事务的执行。
排队延迟（queueing delay）
排队延迟通常占了高百分位点处响应时间的很大一部分。由于服务器只能并行处理少量的事务（如受其 CPU 核数的限制），所以只要有少量缓慢的请求就能阻碍后续请求的处理，这种效应有时被称为…
可靠性（Reliability）
可靠性意味着即使发生故障，系统也能正常工作。故障可能发生在硬件（通常是随机的和不相关的）、软件（通常是系统性的 Bug，很难处理）和人类（不可避免地时不时出错）。容错技术 可以对终端用户隐藏某些类型的故障。
可伸缩性（Scalability）
可伸缩性意味着即使在负载增加的情况下也有保持性能的策略。为了讨论可伸缩性，我们首先需要定量描述负载和性能的方法。我们简要了解了推特主页时间线的例子，介绍描述负载的方法，并将响应时间百分位点作为衡量性能的一种方式。在可伸缩的系统中可以添加 处理容量 以在高负载下保持可靠。
可维护性（Maintainability）
可维护性有许多方面，但实质上是关于工程师和运维团队的生活质量的。良好的抽象可以帮助降低复杂度，并使系统易于修改和适应新的应用场景。良好的可操作性意味着对系统的健康状态具有良好的可见性，并拥有有效的管理手段。
🔑 CH 2 数据模型与查询语言
- MySQL 执行
ALTER TABLE时会复制整个表，可以通过优化ALTER TABLE命令的执行或使用特定的工具来减少这种影响。例如，使用如pt-online-schema-change等在线表结构变更工具，可以在不锁定整个表的情况下进行表结构的更改。 - 通常对于声明式查询语言来说，在编写查询语句时，不需要指定执行细节：查询优化程序会自动选择预测效率最高的策略，因此你可以专注于编写应用程序的其他部分。
💾 CH 3 存储与检索
SSTable：Sorted String Table（排序字符串表）
排序的键值对
SSTable 包含一系列排序的键值对，这种排序是持久化到磁盘之前就完成的。这个特性使得 SSTable 能够支持高效的范围查询和顺序读取操作。
不可变性
一旦创建，SSTable 的内容不会改变。这使得 SSTable 非常适合并发读取，同时简化了数据的合并、缓存和恢复操作。
索引
为了快速查找数据，SSTable 通常包含一个索引部分，记录了键到数据在文件中位置的映射。这个索引可以存储在文件的末尾，也可以部分或全部存储在内存中以提高查找速度。
元数据
SSTable 可以包含额外的元数据，如最小和最大的键，这有助于在执行查询时快速确定是否需要查阅特定的 SSTable。
压缩
为了节省存储空间，SSTable 文件通常会被压缩。常见的压缩算法包括 Snappy、Zlib 等。
使用 SSTable 的存储引擎工作方式
- 新写入的数据首先添加至内存的平衡树数据结构，这个内存树有时被称为内存表（memtable）。
- 当内存表大于某个阈值时，将其作为 SSTable 写入硬盘，新的 SSTable 文件成为数据库的最新段，新的内容又可以写入一个最新的内存表实例。
- 收到请求后，优先在内存表寻找，接着再到最近的硬盘段，如果还没有再找下一个较旧的硬盘段，以此类推。
- 后台运行一个合并和压缩进程，以合并段文件并将已覆盖或删除的旧键删除。
LSM 树（Log-Structured Merge-tree）
LSM 树是一种数据结构，用于高效管理在数据库和文件系统中的大量写操作。LSM 树通过将更新操作写入到内存中的结构，并且定期合并到磁盘上，优化了写入性能，特别是在需要处理大量写入操作的应用场景中。
工作原理
- 内存中的写入：当进行数据插入、更新或删除操作时，LSM 树首先将这些变更写入到一个内存中的数据结构（通常是一个平衡树，如红黑树或AVL树），称为 MemTable。
- 日志写入：为了防止在系统崩溃时丢失数据，这些更改也会被写入到一个持久化的日志文件中。
- 磁盘合并：当 MemTable 达到一定大小后，它会被转换成一个不可变的磁盘文件，称为 SSTable（Sorted String Table）。这个过程被称为刷新（Flush）。
- 后台合并：随着时间的推移，这些 SSTable 会不断增加。LSM 树将定期在后台对这些 SSTable 进行合并和压缩（Compaction），以保持查询效率并回收空间。
优势与劣势
- 高效的写入性能：由于所有的写入首先进入内存，然后异步批量写入磁盘，因此可以获得非常高的写入性能。
- 写入放大问题的缓解：虽然 LSM 树在合并和压缩数据时会产生额外的磁盘写入，但通过优化这些操作可以有效管理写入放大问题。
- 适应大数据量的写入：LSM 树非常适合需要处理大量写入操作的应用，如日志数据处理和实时数据分析。
- 读取性能可能较低：由于数据分散在多个 SSTable 中，读取操作可能需要在多个文件中查找数据，导致读取性能不如 B-tree 等结构。
- 空间和写入放大：数据在合并过程中可能会被重写多次，导致磁盘使用效率较低和较高的写入放大。
Bloom Filters
Bloom filter 是一种空间效率很高的概率性数据结构，用于测试一个元素是否属于一个集合。它允许有误报（false positives）的存在，即可能会错误地判断某个不存在的元素为存在于集合中，但绝不会有漏报（false negatives），即如果它说某个元素不存在，那么这个元素一定不存在于集合中。
基本操作
- 添加元素：将元素通过多个哈希函数映射到一系列位置，并在这些位置上设置标记。
- 查询元素：对于给定的元素，再次使用相同的哈希函数计算位置，如果所有相关位置都被标记了，那么元素可能存在；如果有任何一个位置未被标记，则元素一定不存在。
Bloom filter 通常用在数据库和缓存系统中，以减少对磁盘的不必要访问，从而提高性能。
Size-Tiered 和 Leveled Compaction
这两种术语来自于数据库系统中用于管理存储的压缩策略，特别是在使用 LSM 树结构的系统中。
Size-Tiered Compaction (大小分层压缩)
- 这种压缩策略主要是将大小相似的 SSTables 合并成一个更大的 SSTable。当一组 SSTable 的总大小达到预设的阈值时，它们会被合并。
- 优点：适合写入量大、读取量小的场景，因为它可以减少合并频率，提高写入性能。
- 缺点：可能会产生较大的磁盘占用和延迟，因为合并操作本身较大且可能不够频繁。
Leveled Compaction (层级压缩)
- 在这种策略中，SSTables 被组织成多个层级。每个层级的大小是上一层的若干倍。新数据首先写入最低层，当这一层满了后，它会与下一层的 SSTables 进行合并。
- 优点：提供了更稳定的读性能和空间使用效率，因为每个键的数据版本在较少的文件中分散。
- 缺点：合并操作较频繁，可能会对写入性能产生影响。
B树
预写式日志（Write-Ahead Logging，简称 WAL）
为了使数据库能处理异常崩溃的场景，B 树实现通常会带有一个额外的硬盘数据结构：预写式日志（WAL，即 write-ahead log，也称为 重做日志，即 redo log）。
WAL 的基本原理是，在任何数据更改写入到主数据文件之前，先将这些更改记录到一个单独的日志文件中。
这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在崩溃后恢复时，这
个日志将被用来使 B 树恢复到一致的状态。
B树 VS LSM 树
B树和LSM树（Log-Structured Merge-tree）是两种常用的数据结构，用于数据库和存储系统中管理和存储大量数据。虽然两者都被广泛应用，但它们的设计哲学、结构和适用场景有着明显的差异。
B树的特点
- 结构：B树是一种自平衡的树，可以保持数据在多个层级中均匀分布。每个节点包含多个键和指向子节点的指针。B树通过分裂和合并节点来保持平衡。
- 读写性能：B树提供了较高的读写性能，尤其是在需要频繁读写且数据集较小（可以部分或完全放入内存）的情况下。
- 数据存取：在B树中，数据可以直接在任何节点中访问，这使得点查找非常快速。
- 适用场景：广泛用于传统的关系数据库中，如MySQL、PostgreSQL等，适合事务性应用。
LSM树的特点
- 结构：LSM树通过将所有写入操作首先记录在内存中的结构（如MemTable），然后异步批量写入磁盘，优化了写入性能。
- 写入优化：LSM树特别适合写密集型应用，因为它通过减少对磁盘的即时写入，延迟并批量处理这些操作来优化性能。
- 合并和压缩：LSM树定期在后台进行数据文件的合并和压缩，以保持高效的读取性能。
- 适用场景：常用于NoSQL数据库系统，如Cassandra和RocksDB等，适合大规模数据的分布式存储。
B树与LSM树的对比
- 读性能：B树由于其平衡的特性，提供了较快的读访问速度，特别是对于低延迟的点查找。LSM树可能在读取性能上不如B树，尤其是在存在大量SSTable时。
- 写性能：LSM树在写性能上通常优于B树，因为它通过批量写入和后台处理减少了磁盘I/O的需求。
- 空间和写入放大：LSM树在合并数据时可能会产生较大的写入放大和空间占用。B树通常对磁盘空间的利用更为高效。
- 维护复杂性：LSM树需要定期进行压缩和合并操作，这增加了系统的维护复杂性。B树的维护相对简单，因为它自动通过节点分裂和合并来保持平衡。
写入放大（write amplification）：在数据库的生命周期中每笔数据导致对硬盘的多次写入
事务处理还是分析
表 3-1 比较事务处理和分析系统的特点
| 属性 | 事务处理系统 OLTP | 分析系统 OLAP |
|---|---|---|
| 主要读取模式 | 查询少量记录，按键读取 | 在大批量记录上聚合 |
| 主要写入模式 | 随机访问，写入要求低延时 | 批量导入（ETL）或者事件流 |
| 主要用户 | 终端用户，通过 Web 应用 | 内部数据分析师，用于决策支持 |
| 处理的数据 | 数据的最新状态（当前时间点） | 随时间推移的历史事件 |
| 数据集尺寸 | GB ~ TB | TB ~ PB |
🔄 CH 4 编码与演化
向后与向前兼容性
向后兼容（Backward Compatibility）
当前代码可以读取由旧版本代码写入的数据。
向前兼容（Forward Compatibility）
当前代码可以读取由新版本代码写入的数据。
文本编码的缺点
数值类型支持不足
- CSV 和 XML：直接不支持数值类型，一切都是字符串。
- JSON：虽然区分字符串和数值，但不细分数值类型。
二进制数据支持不足
- 支持 Unicode 但对二进制数据支持不足，可能显示为乱码。
- 通常通过 Base64 编码来处理二进制数据，但这增加了处理复杂度。
额外的模式支持
- XML 和 JSON：支持通过模式来描述数据类型，虽然增强了功能，但也增加了复杂度。
- CSV：没有任何模式支持。
数据模式的优点
- 省去字段名：数据更紧凑。
- 作为数据的注释或文档：模式总是与数据同步更新。
- 允许进行模式比对：可以不读取数据，仅通过模式进行兼容性检查。
- 静态类型支持：支持编译时类型检查，利于静态类型语言。
数据流模型
RPC（Remote Procedure Call）
远程过程调用，允许程序调用另一台计算机上的过程或函数，无需关心底层网络通信细节。
消息队列
用于异步处理和分布式系统通信的技术，具有以下送达保证：
- 最少一次：可能重复送达。
- 最多一次：可能丢失。
- 严格一次：确保恰好送达一次。
Actor 模型
一种并发计算模型，旨在简化并行计算和通信，具有以下特点：
- 独立性：Actor之间不共享内存，通过消息传递交互。
- 并行性：支持并发执行，适用于分布式系统和多核环境。
- 隔离性和可扩展性：Actor故障互不影响，易于扩展系统。
🌍 Part 2 分布式数据
复制（Replication）
在几个不同的节点上保存数据的相同副本，可能放在不同的位置。
分区（Partitioning）
将一个大型数据库拆分成较小的子集（称为分区（partitions）），从而不同的分区可以指派 给不同的节点（node）（亦称分片（shard））
🔀 CH5 复制
关键：如何处理复制数据的变更
主从复制模式
- 客户端要向数据库写入时，必须将请求发送给 leader ，leader 会将新数据写入其本地存储
- leader 将新数据写入本地后，也会将数据变更发送给所有的 followers 复制日志（replication log）每个 followers 从leader 拉取日志后更新相应的本地数据库副本。
- 只有 leader 可写，followers 都是只读的
同步复制&异步复制
同步复制
- 优点：从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上找到。
- 缺点：如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。
半同步
如果同步从库变得不可用或缓慢，则使一个异步从库同步。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库
设置新从库步骤
- 获取某个时刻的主库的一致性快照
- 将快照复制到新的从库节点
- 从库连接到主库，并拉取快照之后的所有数据变更。
- 从库处理完数据变更后就 catch up 了主库
主库失效、故障切换
故障切换（Failover）：当主库失效时，一个从库被提升为新的主库，客户端和其他从库需要重新配置以指向新的主库。
故障切换的过程
- 确认主库失效：通常通过超时机制判断，如果节点在设定时间内无响应，则假定其失效。
- 选择新主库：可以通过选举过程或由控制器节点指定，最佳人选是拥有最新数据副本的从库。
- 系统重新配置：客户端的写请求需要指向新的主库，老主库需认可新领导并成为从库。
故障切换的挑战
- 数据一致性问题：异步复制可能导致新主库缺少老主库宕机前的写入操作。
- 冲突处理：老主库重新加入集群时，可能与新主库存在写入冲突，常见解决方案是丢弃老主库未复制的写入。
- 外部存储协调：与外部存储系统协调时，丢弃写入可能导致数据不一致。
- 脑裂（Split Brain）：两个节点同时认为自己是主库，若无冲突解决机制，可能导致数据丢失或损坏。
- 屏蔽机制（Fencing）：采取措施防止脑裂，如关闭错误的主库节点。
故障切换的配置
- 超时设置：超时时间需权衡，太长可能导致恢复延迟，太短可能导致不必要的故障切换。
- 手动与自动切换：尽管软件可能支持自动故障切换，但许多运维团队更倾向于手动执行以避免潜在问题。
日志复制
逻辑日志复制
- 通常是以行的粒度描述对数据库表的写入的记录序列
- 对于插入的行，日志包含所有列的新值
- 对于删除的行，日志包含足够的信息来唯一标识删除的行
- 对于更新的行，日志包含足够的信息来唯一标识更新的行及所有新列的值
复制延迟问题
read-your-writes consistency
在一个异步复制的分布式数据库里，同一个客户端，写入主副本后返回；稍后再去读一个落后的从副本，发现读不到自己刚写的内容
解决方式
- 内容维度：读取的是用户自身的强相关的只有用户自己能读取到的内容时从主库读，其余的从从库读
- 时间维度：读取的内容的更新时间间隔较短则从主库读。可以根据主从复制延迟决定这个时间
moving backward in time
查询一个延迟低的从库有数据，然后再去查询一个延迟高的从库却没数据。仿佛时光倒流，无事发生一样
解决方式
- 单调读取：确保每个用户都从同一份副本上读取
因果关系内容读取顺序颠倒
内容的顺序是先A -> B, 但由于某些分区的复制速度慢于其他分区，得到的内容顺序却是 B->A
解决方式
- 确保任何因果相关的写入都写入相同的分区
多主复制模式
写入的主库可以是多个，某个主库同时也是其他主库的 follow
适用场景
多个数据中心，每个数据中心有自己的主库
- 降低写入的延迟，提升性能体验
- 能够容忍某个数据中心停机
- 采用异步复制的多活配置能更好地承受网络问题
缺点
- 两个不同的数据中心可能同时修改数据，存在写入冲突
- 多主复制容易有配置缺陷，如自增主键，触发器，完整性约束
如何处理写入冲突
- 通过应用程序逻辑来避免冲突，例如确保相同的数据不会被多个节点同时修改。
- 最后写入胜出（Last Write Wins, LWW）：即最新的写入操作会覆盖旧的写入。
- CRDTs（Conflict-free Replicated Data Types）：使用特殊的数据结构，它们天然支持复制并在没有中心协调者的情况下解决冲突。
- 版本向量（Vector Clocks）：使用向量时钟来跟踪每个副本的写入操作，解决冲突时可以根据向量时钟确定哪个写入是“最新”的。
无主复制模式
- 去中心化：没有单一的控制节点，所有节点都是平等的，可以独立地进行数据复制和同步。
- 数据一致性：虽然每个节点独立操作，但系统设计需要确保数据的最终一致性。这通常通过版本控制、向量时钟等机制来实现。
- 容错性：由于没有单一的故障点，系统对节点故障具有更好的容错性。即使某些节点不可用，其他节点仍然可以继续提供服务。
- 可扩展性：新节点可以轻松加入网络，而不需要重新配置主节点。这使得系统可以灵活地扩展。
- 冲突解决：在无主复制模式中，数据冲突是不可避免的。系统需要有一套机制来解决冲突，比如最后写入胜出（Last Write Wins, LWW）或者更复杂的冲突解决算法。
- 网络分区容忍性：无主复制模式通常与一些网络分区容忍性协议（如Raft或Paxos）结合使用，以确保即使在网络分区的情况下也能保持数据一致性。
读修复（Read Repair）
读修复是一种在读取数据过程中动态进行数据修复的策略。当客户端从分布式数据库或存储系统请求数据时，系统可能从多个副本中获取数据，以保证读取操作的高可用性和快速响应。读修复的工作流程通常如下：
- 数据读取：客户端请求数据时，系统从多个数据副本中读取同一数据项。
- 版本比较：系统比较各副本的数据版本或时间戳。
- 检测不一致：如果发现副本之间存在版本差异，说明数据不一致。
- 修复数据：系统自动将最新版本的数据写回旧版本的副本中，更新这些副本。
读修复是一种懒惰修复策略，因为它仅在读取操作发生时才进行数据修复，可以降低网络和存储的压力，但可能导致过时数据在未被访问时长时间存在。
反熵过程（Anti-entropy Process）
反熵过程是一种更加积极的数据一致性维护策略，用于系统地识别和修正数据副本间的不一致。它不依赖于用户的读取操作，而是周期性地在后台运行，扫描并同步数据副本。反熵过程主要有以下几种实现方式：
- Merkle树同步：使用Merkle树（一种哈希树）来比较数据副本的完整性和一致性。Merkle树可以有效地定位到不一致的数据块，从而减少数据同步过程中需要传输的数据量。
- 版本向量：通过维护一个包含所有副本版本信息的向量，系统可以识别并同步那些过时的副本。
- 全量或增量同步：定期进行全副本之间的数据比对和同步，或者仅同步自上次同步以来发生变化的数据部分。
反熵过程更加适合于那些对数据一致性要求较高的场景，能够确保即使在没有读取操作的情况下，数据副本也能保持一致。
读写的法定人数（Quorum）
在分布式计算中，是一种确保数据一致性和可用性的常见策略。法定人数是基于多数投票的概念，用于决定在读取和写入操作中必须参与的节点的最小数量。这种策略是处理复制数据时一致性和可用性之间权衡的一种方法。
基本概念
法定人数的计算通常基于以下公式：
- 写法定人数 (W)：必须成功写入的最小副本数。
- 读法定人数 (R)：必须成功读取的最小副本数。
- N：总的副本数。
为了保证在任何时候都能读取到最新写入的数据，法定人数需要满足以下关系：
R+W>N
这个关系确保了至少有一个节点在读和写操作中同时被访问，从而能获取到最新的数据。
法定人数策略的选择
强一致性
：
- 如果系统要求非常强的数据一致性，可以选择较高的读写法定人数，例如 W=N和 R=1或 W=N和 R=N。这确保所有副本在每次写入后都是最新的，且每次读取都能返回最新数据。
高可用性
：
- 如果系统更重视可用性，可能选择 W=1 和 R=N，这样任何单一节点的写入都足以完成操作，而所有节点都参与到读操作中来确保返回最新数据。
平衡一致性和可用性
：
- 在许多实际应用中，会选择 W>N/2 和 R>N/2，这样任何写操作都至少会影响多数节点，任何读操作也至少访问多数节点，从而提供良好的一致性保证和合理的可用性。