第一章：可靠性，可扩展性，可维护性

• 许多应用程序都需要：数据库，缓存，搜索索引，流处理，批处理。
• 三个软件系统中的重要问题：可靠性（在困境中仍能正常工作），可扩展性（应对系统的增长，数据量、流量、复杂性etc），可维护性（使系统保持现有行为，并适应新的应用场景）。
• 故障：硬件故障，软件错误，人为错误。
• 描述负载：负载参数（读写比率，用户量，缓存命中率etc），推特主页的时间线获取方式：1.查询关注用户的推文集合并按时间线合并。2.每个用户维护一个时间线缓存，发布推文时插入到所有关注者的推文集合。方法2的缺点：关注者数量庞大时写入次数非常多，解决方法：结合1和2，推拉结合。
• 描述性能：吞吐量，响应时间。衡量响应时间的方式：算术平均值，中位数，p95，p99，p99.9，尾部延迟，排队延迟（头部阻塞）。
• 应对负载的方法：水平扩展（将负载分布到更多机器，无共享架构），垂直扩展（转向更强大的机器）。
• 可维护性：管理复杂度，保持简单性，抽象解耦，拥抱变化。

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

• 1970提出的SQL数据模型：数据被组织成关系，其中每个关系是元组的无序集合。
• SQL模型之间的阻抗不匹配：需要一个笨拙的转换层来处理行、列和数据对象的相互转换。
• 文档数据库：层次模型：把数据表示为嵌套在记录中的记录树，具有自包含性。网络模型：访问记录的唯一方法是跟随从根记录起沿这些链路所形成的路径。
• 图形数据库：任意事物都可能与任何事物相关联。
• 数据查询语言：命令式语言：告诉计算机以特定顺序执行某些操作。声明式语言：指定所需数据的模式-结果必须符合哪些条件-如何将数据转换（例如，排序，分组和集合）。
• 图数据模型：一个图由两种对象组成：顶点（实体）和边（关系）。
• 属性图的声明式查询语言：Cypher。
• 三元组存储（主语，谓语，宾语）：SPARQL。

第三章：存储与检索

• 存储引擎：日志结构（log-structured，案例：Bitcask，SSTables，LSM树，LevelDB，Cassandra，HBase，Lucene），面向页面（page-oriented，案例：B-Tree）。
• 原始存储：往文件末尾追加键值记录。挑战：查找效率。
• 哈希索引：用内存中的记录保存磁盘数据文件位置的偏移量。挑战：数据压缩（去重），删除记录，崩溃恢复，范围搜索。
• SSTable：要求键值对序列按键排序，归并合并多个段，保持最新记录，特点：合并高效，查找效率高。
• 构建和维护SSTable：写入时将记录添加到内存中的平衡树结构（也称作内存表，memtable），当内存表大小高于某个阈值，将其作为SSTable写入磁盘，之后再构建一个新的memtable实例。处理读取顺序：memtable中搜索->最近的磁盘段中搜索->更旧的磁盘段中搜索。问题：发生崩溃时，处于memtable中未写入磁盘的记录会丢失，解决方式：在磁盘保存一个写入日志（commit log），每个写入都会附加到磁盘上，用来发生崩溃后重建memtable。
• B树：将数据库分为固定大小的块或页面，一次只能读取或写入一个页面，每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面。崩溃恢复：预写式日志，并发控制：锁存器。
• LSM树和B树的比较：LSM树支持更高的写入吞吐量（具有较低的写放大问题，顺序写入），缺点：压缩会影响读写操作。
• OLTP（事务处理）：查询少量记录，按键读取。随机访问，写入要求低延时。
• OLAP（分析系统）：在大批量记录上聚合。批量导入（ETL），事件流。
• 列存储：把来自同一列的所有值存储在一起。

第四章：编码与演化

• 向后兼容（backward compatibility）： 新代码可以读旧数据。
• 向前兼容（forward compatibility）：旧代码可以读新数据。
• 从内存中表示到字节序列的转换称为编码，反之称为解码。
• 文本格式编码：JSON，XML，CSV
• 二进制编码：MessagePack，Protobuf，Thrift，Avro
• 基于模式的编码格式的优点：空间更加紧凑，编译时进行类型检查，检查向前和向后兼容性。
• 服务器本身可以是另一个服务的客户端，这种方法通常用于将大型应用程序按照功能区域分解为较小的服务，这种构建应用程序的方式传统上被称为面向服务的体系结构。
• RPC的问题：网络问题不可预测，超时、重试、幂等，编码etc
• 消息代理系统的优点：提供缓冲区防止过载，重新发送，将生产者和消费者逻辑分离。

第五章：复制

• 复制：使得数据与用户在地理上接近（从而减少延迟），即使系统的一部分出现故障，系统也能继续工作（从而提高可用性），扩展可以接受读请求的机器数量（从而提高读取吞吐量）。
• 常用的复制方式：单领导者，多领导者，无领导者。
• 同步复制：主库等待从库复制完成返回成功，从库保证有与主库一致的数据副本。异步复制：主库不等待从库复制完成返回，从库不保证有与主库一致的数据副本。
• 处理节点宕机：从库失效：故障恢复（拉取快照，同步变更，消费数据积压）。主库失效：故障转移（确认失效，选举新主库，重新配置）。
• 故障转移的麻烦：复制日志不同步导致新老主库的写入冲突，脑裂（两个节点认为自己是主库）。
• 复制日志的实现：基于语句的复制（麻烦：非确定性函数，自增列），传输预写式日志，逻辑日志复制（基于行），基于触发器的复制。
• 最终一致性：从库最终会赶上并与主库保持一致。
• 读写一致性：用户总能看到自己提交的任何更新。
• 单调读：一个用户顺序地进行多次读取，应该看到一致的数据。（比强一致性弱，比最终一致性强）
• 一致前缀读：如果一系列写入按某个顺序发生，那么任何人在读取这些写入时，也能看到它们以相同的顺序出现。
• 多主数据库最大的问题：处理写入冲突，解决方式：同步和异步冲突检测（等待写入复制到所有副本），避免冲突（所有写入通过同一个领导者）。处理冲突合并的方式：最后写入为准（LWW），即给每个写入一个唯一的ID/时间戳，选择最新的ID作为胜利者。
• 无领导者式复制（Dynamo风格）：客户端/协调者向多个副本发送写入。
• 读写的法定人数：如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。只要$w + r> n$，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值，w值的读写称为法定人数（quorum）的读和写。

第六章：分区

• 分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。 即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。
• 分区目标是将数据和查询负载均匀分布在各个节点上。
• 一些分区比其他分区有更多的数据或查询，称之为数据倾斜。不均衡导致的高负载的分区，称之为热点。
• 根据键的范围分区：为每个分区指定一块连续的键范围。
• 根据键的散列分区：每个键通过散列函数落在适合的分区上。
• 文档分区的二级索引：每个分区维护自己分区中文档记录的二级索引，查询时并行查找所有分区的二级索引，把结果聚集返回。
• 关键词分区的二级索引：根据特定的关键词把二级索引分布在不同的分区，查询时需要找到关键词所在的分区，直接查询结果返回。
• 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡。平衡策略：反面教材：hash mod N。固定数量分区：创建比节点更多的分区，添加分区时从各节点中移动分区。动态分区：当分区增长到一定数量后自动再分区。按节点比例分区：每个节点具有固定数量的分区。
• 服务发现的三种方式：1.客户端联系任何节点，节点处理或将请求转发到合适的其他节点上。2.客户端联系路由层，路由层将请求转发到合适的其他节点上。3.客户端知道分区和节点的分配，将请求直接发送到合适的节点上。
• 协调服务：ZooKeeper跟踪集群的元数据，节点上面注册，ZooKeeper维护分区和节点的可靠映射。

第七章：事务

• 事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。事务ACID：A（原子性，要么全部成功，要么全部失败），C（一致性，对数据的一组特定陈述必须始终成立），I（隔离性，事务之间不应该相互干扰），D（持久性，事务成功后写入的数据不会丢失）。
• 脏读：一个客户端读取到另一个客户端尚未提交的写入。
• 脏写： 一个客户端覆盖写入了另一个客户端尚未提交的写入。
• 读已提交：从数据库读时，只能看到已提交的数据（没有脏读）。写入数据库时，只会覆盖已经写入的数据（没有脏写）。
• 不可重复读：一个事务中两个相同的查询中间由于其他事务的提交，导致查询返回了不一样的结果。
• 快照隔离：MVCC：当一个事务开始时，它被赋予一个唯一的，永远增长的事务ID（txid）。每当事务向数据库写入任何内容时，它所写入的数据都会被标记上写入者的事务ID。
• 一致性快照的可见性原则：读事务开始时，创建该对象的事务已经提交。对象未被标记为删除，或如果被标记为删除，请求删除的事务在读事务开始时尚未提交。
• 写偏差：两个事务同时更新两个不同的对象，导致不符合预期。写偏差模式：1.查询找出特定的行。2.根据第一个查询的结果决定是否进行。3.如果判断成功执行更新事务。例子：医生值班，多人游戏，抢注用户名，会议室预订。解决方法：为更新的对象加行锁（SELECT FOR UPDATE），唯一索引，可序列化。
• 一个事务中的写入改变另一个事务的搜索查询的结果，被称为幻读。
• 可序列化三种技术：顺序执行事务，2PL，SSI。
• 2PL：写阻塞读，读阻塞写。锁模式：共享锁，排它锁。读对象：要求共享锁，有排它锁则阻塞。写对象：有任何锁存在则阻塞。
• 间隙锁：通过对索引范围的间隙加锁防止其他事务写入导致的幻读。

第八章：分布式系统的麻烦