1.1 可靠性、可伸缩性和可维护性

评估可伸缩性前需要先描述负载，
书中举了twitter订阅时间线的例子：

推特的两个主要业务是：
发布推文:
用户可以向其粉丝发布新消息（平均 4.6k 请求 / 秒，峰值超过 12k 请求 / 秒）;
主页时间线:
用户可以查阅他们关注的人发布的推文（300k 请求 / 秒）。

所以推特的主要负载来源为扇出^[1]。

1.2 数据模型与查询语言

数据模型

时下流行的数据模型主要有关系模型与文档模型；
他们之间有许多差异和共性，其中我觉得最有趣的点是他们对于模式 的处理。

文档数据库有时称为 无模式（schemaless），但这具有误导性，因为读取数据的代码通常假定某种结构 —— 即存在隐式模式，但不由数据库强制执行。一个更精确的术语是 读时模式（即 schema-on-read，数据的结构是隐含的，只有在数据被读取时才被解释），相应的是 写时模式（即 schema-on-write，传统的关系数据库方法中，模式明确，且数据库确保所有的数据都符合其模式）

读时模式就像编程语言的动态（运行时）类型检查， 写时模式就像编译时（静态）类型检查，孰优孰劣一直也没有定论。

查询语言

作者举了两种查询语言：命令式查询与声明式查询。

命令式语言告诉计算机以特定顺序执行某些操作。可以想象一下，逐行地遍历代码，评估条件，更新变量，并决定是否再循环一遍。

在声明式查询语言（如 SQL 或关系代数）中，你只需指定所需数据的模式 - 结果必须符合哪些条件，以及如何将数据转换（例如，排序，分组和集合） - 但不是如何实现这一目标。数据库系统的查询优化器决定使用哪些索引和哪些连接方法，以及以何种顺序执行查询的各个部分。

那么与大模型的交互实际上就是终极的声明式查询～

此外作者还介绍了图数据库以及相应的声明式查询语言，但是从来没有见过应用场景所以暂时作为了解。

1.3 存储与检索

驱动数据库的数据结构

世界上最简单的数据库，后续的优化也都从此开始

db_set () {
  echo "$1,$2" >> database
}

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

• 问题1：这个数据库查询太慢，时间复杂度为O(n)
  解： 引入哈希表作为索引
• 问题2: 一直使用的日志文件中包含太多过时的已经被覆盖或删除的记录，占用磁盘空间
  解：将日志分为特定大小的段（segment），当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行压缩（compaction。这里的压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新。
• 问题3: 这个数据库不支持遍历； 此外哈希表必须完整存储在内存中导致数据规模受限
  解：引出排序字符串表（Sorted String Table）数据结构，相对于问题2中得到的数据库，我们只需要对段文件的格式做一个简单的改变：要求键值对的序列按键排序，这样便可以按序对数据库进行遍历；既然段文件有了顺序那么哈希表也可以不再保存所有键值对。
• 问题4：SSTable会将写入的数据暂时存在内存中，只有达到阈值才会刷盘； 如果在这个过程中机器崩溃会导致数据丢失
  解：用回最初的日志文件思想，写入内存的同时在单独的日志文件中进行追加，如果崩溃则使用这个文件进行恢复。 （类似mysql 的 redoLog 对吧

至此我们从一个最简单的数据库开始逐步优化，得到了SSTable这样一个效率尚可的数据库雏形，而这实际上就是LSM树的基础，LSM树在SSTable的基础上提供了更完整的数据管理解决方案。

此外作者还介绍了B树，在mysql中应用非常广泛所以笔记中就不再额外介绍。

事务处理还是分析

这一部分就多记录一些概念吧
在线事务处理（OLTP, OnLine Transaction Processing）： 应用程序通常使用索引通过某个键查找少量记录。根据用户的输入插入或更新记录。交互式的应用程序对于数据库的访问模式。

在线分析处理（OLAP, OnLine Analytice Processing）：分析查询需要扫描大量记录，每个记录只读取几列，并计算汇总统计信息（如计数、总和或平均值），而不是将原始数据返回给用户。

数据仓库（data warehouse）： 起初，事务处理和分析查询使用了相同的数据库。 SQL 在这方面已证明是非常灵活的：对于 OLTP 类型的查询以及 OLAP 类型的查询来说效果都很好。尽管如此，在二十世纪八十年代末和九十年代初期，企业有停止使用 OLTP 系统进行分析的趋势，转而在单独的数据库上运行分析。这个单独的数据库被称为 数据仓库。

ETL: 数据仓库包含公司各种 OLTP 系统中所有的只读数据副本。从 OLTP 数据库中提取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数据仓库中的过程。

星形和雪花形：下图是可能在食品零售商处找到的数据仓库。在模式的中心是一个所谓的事实表（在这个例子中，它被称为 fact_sales）。事实表的每一行代表在特定时间发生的事件（这里，每一行代表客户购买的产品）。
事实表中的一些列是属性，例如产品销售的价格和从供应商那里购买的成本（可以用来计算利润率）。事实表中的其他列是对其他表（称为维度表）的外键引用。由于事实表中的每一行都表示一个事件，因此这些维度代表事件发生的对象、内容、地点、时间、方式和原因。
甚至事件发生的时间也可以设置为对维度表的外键引用，方便对于节假日等纬度进行分析处理。
而雪花形和星形的区别就是雪花形中维度表又会有对其他维度表的外键引用，类似雪花； 不过实际中星形更加常用。

列式存储

之前对于列示存储的认知只是”能存的比行式更多“，非常粗浅； 下面将介绍列式存储为什么存在，以及它这些特性的底层原理。

首先明确一下场景，在上一小节介绍的事实表往往有几百列和万亿行的数据，维度表则相对简单，所以列式存储部分我们重点关注对于事实表的存储和查询。

尽管事实表通常超过 100 列，但典型的数据仓库查询一次只会访问其中 4 个或 5 个列（ “SELECT *” 查询很少用于分析）。以 分析人们是否更倾向于在一周的某一天购买新鲜水果或糖果的查询为例：它访问了大量的行（一年中所有购买了水果或糖果的记录），但只需访问 fact_sales 表的三列：date_key, product_sk, quantity。

所以为了解决这种场景而生的列式存储的思想很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。

传统的行式数据库和文档数据库总是将一行的数据存储在一起，无法很好的处理数据分析请求；而列式存储数据库则只需要读取和解析查询中使用的那些列，这可以节省大量的工作。

此外由于一列中的数据都是对同一个维度表的外键引用，而维度表的行数往往有限，所以一列中会有很多重复数据，可以方便的进行列压缩，进一步提高了存储效率。

1.7 事务

没错 我跳过了 1.4-编码与演化、1.5-复制、1.6-分区 三个章节； 因为这三个章节内容要么是太偏底层和理论要么是太浅显，暂时没有想到应用场景，所以暂不记录； 将来如果有那一天用上了这些知识会回来补上。

ACID的含义

首先是事务的特性 已经是陈词滥调了：

事务所提供的安全保证，通常由众所周知的首字母缩略词 ACID 来描述，ACID 代表 原子性（Atomicity），一致性（Consistency），隔离性（Isolation） 和 持久性（Durability）

但实际上不同数据库的 ACID 实现并不相同，ACID几乎已经成为了数据库的营销术语。
不过还是要了解一下这四个特性原本的含义:

原子性

能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。 或许可中止性（abortability） 是更好的术语，可以与并发编程中的原子性进行区分；
换一种我自己的理解：即整个事务要么成功要么失败，没有中间状态。

一致性（凑数的）

这是一个更容易混淆的概念，许多场景会用到“一致性”这个词，
ACID中一致性的概念是，对数据的一组特定约束必须始终成立。即不变式（invariants）。
举个例子就是会计系统中，总是借贷相抵的；很明显多数情况下一致性不应该由数据库来保证，而是应该由应用程序来负责正确定义它的事务并保持一致性。
所以很大程度上这个一致性属于是为了凑出ACID这个单词而扔进来的……

隔离性

同时执行的事务是相互隔离的，他们不能相互冒犯。

持久性

持久性是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。但是这个特性很明显不会十分绝对，不过数据库们永远也不会停止向着绝对努力~

弱隔离级别

要严格的实现ACID，直接将事务隔离级别设置为“可串行化”固然是最简单严谨的； 但是可串行化的性能损代价是许多数据库都不愿意支付的。
因此，系统通常使用较弱的隔离级别来防止一部分，而不是全部的并发问题。这些隔离级别难以理解，并且会导致微妙的错误，但是它们仍然在实践中被使用。

读已提交

最基本的事务隔离级别^[2]，提供两个保证：

1. 从数据库读时，只能看到已提交的数据（没有脏读，即 dirty reads）。
2. 写入数据库时，只会覆盖已提交的数据（没有脏写，即 dirty writes）。

没有脏读

个人理解：一个事务的中间结果被另一个同时进行的事务读取到，这种情况称为脏读。
需要防止脏读有两个原因：

1. 如果需要在一个事务中更新多个对象，脏读可能会导致另一个事务读取到不一致的数据；比如用户可以看到新的未读邮件，但是未读邮件计数器没有更新。
2. 事务是有可能回滚的，如果一个事务B读到了事务A的中间结果并依赖这个中间结果进行了一些写入操作，那么当事务A异常回滚后事务B写入的数据将是不可理解的。

没有脏写

个人理解：同一时间只能有一个事务写入某个对象
通过防止脏写可以避免的问题：
两个人同时购买一个物品，购买物品的事务需要先后写入“购买人表”和“发票邮寄”表； 如果允许脏写那么由于执行顺序的问题我们不能保证最终记录的购买人和发票邮寄人是同一个，如图

实现读已提交

最常见的是使用行锁来实现防止脏写，同时只有一个事务可以获取到当前行的写锁； 至于防止脏读有两种实现方式: 使用行读锁和使用快照；

快照隔离和可重复读

读已提交看起来已经足够ACID了对吧？ 实际上有些场景还是会产生并发问题，例如：
两个事务A和B，A中会两次查询账户中的余额，B会利用这个余额进行一次购买（扣减余额），如果在A的两次查询之间B事务开始执行并提交了，那么在读已提交的隔离级别下，事务A的两次读取讲获取到不同的值；这种异常叫做不可重复读。

不过这并不是一个会长期持续的问题，首先是概率极小其次是如果事件A因此发生异常进行重试，那么问题也就不复存在；但是部分场景仍不能忍受这种错误：

• 备份
  备份可以看成一个大读取事务，会耗时很长；这个过程中数据库必须继续接受写入操作，因此备份可能会包含一些旧的数据和一些新的数据；如果从这种备份中进行恢复，这些错误的钱就会变成永久的。
• 分析查询和完整性检查
  在进行OLAP事务或者是完整性检查时，这种问题也可能造成最终得到不准确的结论而不自知。

实现可重复读

快照隔离 是这个问题最常见的解决方案，具体解释一下就是：
每个事务都从数据库的一致快照中读取，即一个事务看到的数据总是这个事务开始前的版本，本事务执行过程中其他提交的事务对本事务来讲是不可见的。

数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它同时维护着单个对象的多个版本，所以这种技术被称为 多版本并发控制（MVCC, multi-version concurrency control）。

防止丢失更新

TODO