设计数据密集型应用

相关读书笔记。

第一部分 数据系统的基石

现今很多应用程序都是 数据密集型（data-intensive） 的，而非 计算密集型（compute-intensive） 的。

数据密集型应用通常由标准组件构建而成，标准组件提供了很多通用的功能；例如，许多应用程序都需要：

• 存储数据，以便自己或其他应用程序之后能再次找到 （数据库（database））

• 记住开销昂贵操作的结果，加快读取速度（缓存（cache））
• 允许用户按关键字搜索数据，或以各种方式对数据进行过滤（搜索索引（search indexes））
• 向其他进程发送消息，进行异步处理（流处理（stream processing））
• 定期处理累积的大批量数据（批处理（batch processing））

可靠性（Reliability）

• 系统在困境（adversity）（硬件故障、软件故障、人为错误）中仍可正常工作（正确完成功能，并能达到期望的性能水准）。

可扩展性（Scalability）

• 有合理的办法应对系统的增长（数据量、流量、复杂性）

可维护性（Maintainability）

• 许多不同的人（工程师、运维）在不同的生命周期，都能高效地在系统上工作（使系统保持现有行为，并适应新的应用场景）。

硬件故障：

在拥有10000个磁盘的存储集群上，平均每天会有1个磁盘出故障。通常都是增加单个硬件的冗余度。

人们经常讨论纵向扩展（scaling up）（垂直扩展（vertical scaling），转向更强大的机器）和横向扩展（scaling out） （水平扩展（horizontal scaling），将负载分布到多台小机器上）之间的对立。跨多台机器分配负载也称为“无共享（shared-nothing）”架构。可以在单台机器上运行的系统通常更简单，但高端机器可能非常贵，所以非常密集的负载通常无法避免地需要横向扩展。现实世界中的优秀架构需要将这两种方法务实地结合，因为使用几台足够强大的机器可能比使用大量的小型虚拟机更简单也更便宜。

跨多台机器部署无状态服务（stateless services）非常简单，但将带状态的数据系统从单节点变为分布式配置则可能引入许多额外复杂度。出于这个原因，常识告诉我们应该将数据库放在单个节点上（纵向扩展），直到扩展成本或可用性需求迫使其改为分布式。

新的非关系型“NoSQL”数据存储在两个主要方向上存在分歧：

1. 文档数据库的应用场景是：数据通常是自我包含的，而且文档之间的关系非常稀少。
2. 图形数据库用于相反的场景：任意事物都可能与任何事物相关联。

log日志结构和面向页的B+引擎

这篇文章总结的很好，可以看看这个. https://www.cnblogs.com/theseventhson/p/16757775.html

两大类存储引擎：日志结构（log-structured） 的存储引擎，以及面向页面（page-oriented） 的存储引擎（例如B树）。

日志一般是直接追加，读记录时读最新最后的一个值，前面的可后续压缩合并。

因为数据落到磁盘里，基本就两种方法，1. sstable，先内存后追加再不断合并； 2. 类似B树面向页，直接更新。 除此之外如果更新某个文件某一行，可能会导致后面的都变，因为offset变了，所以目前基本就这两种。为啥没hash, 磁盘哈希映射很难表现优秀。它需要大量的随机访问I/O，当它变满时增长是很昂贵的，并且散列冲突需要很多的逻辑

SSTable并发控制

由于写操作是以严格顺序的顺序附加到日志中的，所以常见的实现选择是只有一个写入器线程。数据文件段是附加的，或者是不可变的，所以它们可以被多个线程同时读取。

乍一看，只有追加日志看起来很浪费：为什么不更新文件，用新值覆盖旧值？但是只能追加设计的原因有几个：

• 追加和分段合并是顺序写入操作，通常比随机写入快得多，尤其是在磁盘旋转硬盘上。在某种程度上，顺序写入在基于闪存的 固态硬盘（SSD） 上也是优选的【4】。我们将在第83页的“比较B-树和LSM-树”中进一步讨论这个问题。
• 如果段文件是附加的或不可变的，并发和崩溃恢复就简单多了。例如，您不必担心在覆盖值时发生崩溃的情况，而将包含旧值和新值的一部分的文件保留在一起。
• 合并旧段可以避免数据文件随着时间的推移而分散的问题。

B树

B树存储是面向页的，文件就是页组成的，磁盘是按页划分的，指针都是页的指针，页位置不会变。

通常，页面可以放置在磁盘上的任何位置；没有什么要求附近的键范围页面附近的磁盘上。如果查询需要按照排序顺序扫描大部分关键字范围，那么每个页面的布局可能会非常不方便，因为每个读取的页面都可能需要磁盘查找。因此，许多B树实现尝试布局树，使得叶子页面按顺序出现在磁盘上。但是，随着树的增长，维持这个顺序是很困难的。相比之下，由于LSM树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在磁盘上彼此靠近。

额外的指针已添加到树中。例如，每个叶子页面可以在左边和右边具有对其兄弟页面的引用，这允许不跳回父页面就能顺序扫描。

比较B树和LSM树

尽管B树实现通常比LSM树实现更成熟，但LSM树由于其性能特点也非常有趣。根据经验，通常LSM树的写入速度更快，而B树的读取速度更快【23】。 LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。

B树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）。即使在该页面中只有几个字节发生了变化，也需要一次编写整个页面的开销。

LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。 B树存储引擎会由于分割而留下一些未使用的磁盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于LSM树不是面向页面的，并且定期重写SSTables以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时

1. LSM写入快，B读快。
2. B树写，一次要写log, 一次要更新页，页只能替换。
3. LSM碎片少，压缩的好，存储开销小。
4. LSM写入吞吐量大，需要合理配置压缩。
5. LSM压缩可能会干扰读写。
6. B树每个键只有一个位置，方便加锁。

OLTP 和 OLAP

在高层次上，我们看到存储引擎分为两大类：优化 事务处理（OLTP） 或 在线分析（OLAP） 。这些用例的访问模式之间有很大的区别：

• OLTP系统通常面向用户，这意味着系统可能会收到大量的请求。为了处理负载，应用程序通常只访问每个查询中的少部分记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。磁盘寻道时间往往是这里的瓶颈。
• 数据仓库和类似的分析系统会低调一些，因为它们主要由业务分析人员使用，而不是由最终用户使用。它们的查询量要比OLTP系统少得多，但通常每个查询开销高昂，需要在短时间内扫描数百万条记录。磁盘带宽（而不是查找时间）往往是瓶颈，列式存储是这种工作负载越来越流行的解决方案。

在OLTP方面，我们能看到两派主流的存储引擎：

日志结构学派

只允许附加到文件和删除过时的文件，但不会更新已经写入的文件。 Bitcask，SSTables，LSM树，LevelDB，Cassandra，HBase，Lucene等都属于这个类别。

就地更新学派

将磁盘视为一组可以覆写的固定大小的页面。 B树是这种哲学的典范，用在所有主要的关系数据库中和许多非关系型数据库。

日志结构的存储引擎是相对较新的发展。他们的主要想法是，他们系统地将随机访问写入顺序写入磁盘，由于硬盘驱动器和固态硬盘的性能特点，可以实现更高的写入吞吐量。在完成OLTP方面，我们通过一些更复杂的索引结构和为保留所有数据而优化的数据库做了一个简短的介绍。

然后，我们从存储引擎的内部绕开，看看典型数据仓库的高级架构。这一背景说明了为什么分析工作负载与OLTP差别很大：当您的查询需要在大量行中顺序扫描时，索引的相关性就会降低很多。相反，非常紧凑地编码数据变得非常重要，以最大限度地减少查询需要从磁盘读取的数据量。我们讨论了列式存储如何帮助实现这一目标。

*向后兼容 (backward compatibility)*

新代码可以读旧数据。

*向前兼容 (forward compatibility)*

旧代码可以读新数据。

服务器本身可以是另一个服务的客户端（例如，典型的Web应用服务器充当数据库的客户端）。这种方法通常用于将大型应用程序按照功能区域分解为较小的服务，这样当一个服务需要来自另一个服务的某些功能或数据时，就会向另一个服务发出请求。这种构建应用程序的方式传统上被称为 面向服务的体系结构（service-oriented architecture，SOA） ，最近被改进和更名为 微服务架构

REST不是一个协议，而是一个基于HTTP原则的设计哲学【34,35】。它强调简单的数据格式，使用URL来标识资源，并使用HTTP功能进行缓存控制，身份验证和内容类型协商

第二部分 分布式数据

复制

三种流行的变更复制算法：单领导者（single leader），多领导者（multi leader）和无领导者（leaderless）。几乎所有分布式数据库都使用这三种方法之一。

对于异步复制系统而言，主库故障时有可能丢失数据。这可能是一个严重的问题，因此研究人员仍在研究不丢数据但仍能提供良好性能和可用性的复制方法。 例如，链式复制【8,9】]是同步复制的一种变体，已经在一些系统（如Microsoft Azure存储【10,11】）中成功实现。

同步复制与异步复制

复制系统的一个重要细节是：复制是同步（synchronously）发生还是异步（asynchronously）发生。 （在关系型数据库中这通常是一个配置项，其他系统通常硬编码为其中一个）。

同步复制的优点是，从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上上找到。缺点是，如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。

通常情况下，基于领导者的复制都配置为完全异步。 在这种情况下，如果主库失效且不可恢复，则任何尚未复制给从库的写入都会丢失。 这意味着即使已经向客户端确认成功，写入也不能保证 持久（Durable） 。 然而，一个完全异步的配置也有优点：即使所有的从库都落后了，主库也可以继续处理写入。

复制日志的实现

基于主库的复制底层是如何工作的？实践中有好几种不同的复制方式

1. 基于语句的复制，比如原始的sql。

2. 物理日志， WAL 非常底层：包含哪些磁盘块中的哪些字节发生了更改。这使复制与存储引擎紧密耦合
3. 逻辑日志复制（基于行）复制改动的行的数据，删除传id, insert传所有，update传更新内容
4. 基于触发器

处理节点宕机

从库失效：追赶恢复

在其本地磁盘上，每个从库记录从主库收到的数据变更。如果从库崩溃并重新启动，或者，如果主库和从库之间的网络暂时中断，则比较容易恢复：从库可以从日志中知道，在发生故障之前处理的最后一个事务。因此，从库可以连接到主库，并请求在从库断开连接时发生的所有数据变更。

主库失效：故障切换

主库失效处理起来相当棘手：其中一个从库需要被提升为新的主库，需要重新配置客户端，以将它们的写操作发送给新的主库，其他从库需要开始拉取来自新主库的数据变更。这个过程被称为故障切换

问题

1. 异步复制可能会丢老主库最后写入
2. 主键重用什么的很麻烦
3. 老主库恢复可能有两个主 ，要强行杀死老的

复制延迟问题

1. 读己之写： 让用户提交一些数据，然后查看他们提交的内容。 写后立即读
2. 单调读： 从异步从库读取第二个异常例子是，用户可能会遇到 时光倒流（moving backward in time）。如果用户从不同从库进行多次读取，就可能发生这种情况。同步延迟太大造成的。
3. 一致前缀读（consistent prefix reads）：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。

多主复制的应用场景

在单个数据中心内部使用多个主库很少是有意义的，因为好处很少超过复杂性的代价。 但在一些情况下，多活配置是也合理的。

1. 运维多个数据中心
2. 需要离线操作的客户端
3. 协同编辑

自定义冲突解决逻辑

1. 写时执行
2. 读时执行 读修复

自动解决由于数据修改引起的冲突。有几行研究值得一提：

• 无冲突复制数据类型（Conflict-free replicated datatypes）（CRDT）【32,38】是可以由多个用户同时编辑的集合，映射，有序列表，计数器等的一系列数据结构，它们以合理的方式自动解决冲突。一些CRDT已经在Riak 2.0中实现【39,40】。
• 可合并的持久数据结构（Mergeable persistent data structures）【41】显式跟踪历史记录，类似于Git版本控制系统，并使用三向合并功能（而CRDT使用双向合并）。
• 可执行的转换（operational transformation）[42]是Etherpad 【30】和Google Docs 【31】等合作编辑应用背后的冲突解决算法。它是专为同时编辑项目的有序列表而设计的，例如构成文本文档的字符列表。

无主复制

参考本人另一个博客。 尽管法定人数似乎保证读取返回最新的写入值，但在实践中并不那么简单。 Dynamo风格的数据库通常针对可以忍受最终一致性的用例进行优化。允许通过参数w和r来调整读取陈旧值的概率，但把它们当成绝对的保证是不明智的。

分区

分区主要是为了可扩展性。不同的分区可以放在不共享集群中的不同节点上

因此，大数据集可以分布在多个磁盘上，并且查询负载可以分布在多个处理器上。

对于在单个分区上运行的查询，每个节点可以独立执行对自己的查询，因此可以通过添加更多的节点来扩大查询吞吐量。大型，复杂的查询可能会跨越多个节点并行处理，尽管这也带来了新的困难。

大多数情况下，分区方案的选择与复制方案的选择是独立的

Key Range分区的缺点是某些特定的访问模式会导致热点。 由于偏斜和热点的风险，许多分布式数据存储使用散列函数来确定给定键的分区。

出于分区的目的，散列函数不需要多么强壮的加密算法：例如，Cassandra和MongoDB使用MD5，Voldemort使用Fowler-Noll-Vo函数。许多编程语言都有内置的简单哈希函数（它们用于哈希表），但是它们可能不适合分区：例如，在Java的Object.hashCode()和Ruby的Object#hash，同一个键可能在不同的进程中有不同的哈希值

如今，大多数数据系统无法自动补偿这种高度偏斜的负载，因此应用程序有责任减少偏斜。例如，如果一个主键被认为是非常火爆的，一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为100种不同的主键,从而存储在不同的分区中。

然而，将主键进行分割之后，任何读取都必须要做额外的工作，因为他们必须从所有100个主键分布中读取数据并将其合并。此技术还需要额外的记录：只需要对少量热点附加随机数;对于写入吞吐量低的绝大多数主键来是不必要的开销。因此，您还需要一些方法来跟踪哪些键需要被分割。

分区和二级索引之间的相互作用

同分区上的本地索引

文档分区索引也被称为本地索引（local index）。 在这种索引方法中，每个分区是完全独立的：每个分区维护自己的二级索引，仅覆盖该分区中的文档。它不关心存储在其他分区的数据。无论何时您需要写入数据库（添加，删除或更新文档），只需处理包含您正在编写的文档ID的分区即可。

这种查询某个调节的id可能需要将查询发送到所有分区，并合并所有返回的结果。 这种查询分区数据库的方法有时被称为分散/聚集（scatter/gather），并且可能会使二级索引上的读取查询相当昂贵。即使并行查询分区，分散/聚集也容易导致尾部延迟放大（参阅“实践中的百分位点”）。然而，它被广泛使用：MongoDB，Riak 【15】，Cassandra 【16】，Elasticsearch 【17】，SolrCloud 【18】和VoltDB 【19】都使用文档分区二级索引。

覆盖所有分区数据的全局索引

全局索引 我们可以构建一个覆盖所有分区数据的全局索引，而不是给每个分区创建自己的次级索引（本地索引）。但是，我们不能只把这个索引存储在一个节点上，因为它可能会成为瓶颈，违背了分区的目的。全局索引也必须进行分区，但可以采用与主键不同的分区方式。 我们将这种索引称为关键词分区（term-partitioned），因为我们寻找的关键词决定了索引的分区方式。例如，一个关键词可能是：颜色：红色。关键词(Term) 来源于来自全文搜索索引（一种特殊的次级索引），指文档中出现的所有单词。

关键词分区的全局索引优于文档分区索引的地方点是它可以使读取更有效率：不需要分散/收集所有分区，客户端只需要向包含关键词的分区发出请求。全局索引的缺点在于写入速度较慢且较为复杂，因为写入单个文档现在可能会影响索引的多个分区（文档中的每个关键词可能位于不同的分区或者不同的节点上） 。

在实践中，对全局二级索引的更新通常是异步的（也就是说，如果在写入之后不久读取索引，刚才所做的更改可能尚未反映在索引中）。例如，Amazon DynamoDB声称在正常情况下，其全局次级索引会在不到一秒的时间内更新，但在基础架构出现故障的情况下可能会有延迟【20】。

分区再平衡

随着时间的推移，数据库会有各种变化。

• 查询吞吐量增加，所以您想要添加更多的CPU来处理负载。
• 数据集大小增加，所以您想添加更多的磁盘和RAM来存储它。
• 机器出现故障，其他机器需要接管故障机器的责任。

所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（reblancing）。

反面教材：hash mod N

模$N$方法的问题是，如果节点数量N发生变化，大多数密钥将需要从一个节点移动到另一个节点。例如，假设$hash(key)=123456$。如果最初有10个节点，那么这个键一开始放在节点6上

键值 固定数量的分区 hash slot

类似hash slot.

创建比节点更多的分区，并为每个节点分配多个分区。

如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。如果从集群中删除一个节点，则会发生相反的情况。

原则上，您甚至可以解决集群中的硬件不匹配问题：通过为更强大的节点分配更多的分区，可以强制这些节点承载更多的负载。在Riak 【15】，Elasticsearch 【24】，Couchbase 【10】和Voldemort 【25】中使用了这种再平衡的方法。

范围，动态分区 Hbase

按键范围分区。一个节点对应多个分区，当分区大了就拆分，当小了就和相邻分区合并， 类似B树。

大型分区拆分后，可以将其中的一半转移到另一个节点，以平衡负载。在HBase中，分区文件的传输通过HDFS（底层分布式文件系统）来实现【3】。可以是不复制数据而直接挂载存储的

动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据，少量的分区就足够了，所以开销很小;如果有大量的数据，每个分区的大小被限制在一个可配置的最大值

动态分区不仅适用于数据的范围分区，而且也适用于散列分区。从版本2.4开始，MongoDB同时支持范围和哈希分区，并且都是进行动态分割分区。

按节点比例分区 不常用

每个节点有固定的分区数量，当新节点加入，随机选择某个分区拆一半给新节点。

请求路由 服务发现

当客户想要发出请求时，如何知道要连接哪个节点？随着分区重新平衡，分区对节点的分配也发生变化。

这个问题可以概括为 服务发现(service discovery) ，它不仅限于数据库。任何可通过网络访问的软件都有这个问题，特别是如果它的目标是高可用性（在多台机器上运行冗余配置）。

概括来说，这个问题有几种不同的方案（如图6-7所示）:

1. 请求任意节点做协调。允许客户联系任何节点（例如，通过循环策略的负载均衡（Round-Robin Load Balancer））。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求;否则，它将请求转发到适当的节点，接收回复并传递给客户端。
2. 加个路由层做负载均衡。 首先将所有来自客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。
3. 把路由信息放到客户端，客户端订阅。要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介。

许多分布式数据系统都依赖于一个独立的协调服务，比如ZooKeeper来跟踪集群元数据。 每个节点在ZooKeeper中注册自己，ZooKeeper维护分区到节点的可靠映射。 其他参与者（如路由层或分区感知客户端）可以在ZooKeeper中订阅此信息。 只要分区分配发生的改变，或者集群中添加或删除了一个节点，ZooKeeper就会通知路由层使路由信息保持最新状态。

例如，LinkedIn的Espresso使用Helix 【31】进行集群管理（依靠ZooKeeper），实现了如图6-8所示的路由层。 HBase，SolrCloud和Kafka也使用ZooKeeper来跟踪分区分配。 MongoDB具有类似的体系结构，但它依赖于自己的配置服务器（config server） 实现和mongos守护进程作为路由层。

Cassandra和Riak采取不同的方法：他们在节点之间使用流言协议（gossip protocol） 来传播群集状态的变化。请求可以发送到任意节点，该节点会转发到包含所请求的分区的适当节点（图6-7中的方法1）。这个模型在数据库节点中增加了更多的复杂性，但是避免了对像ZooKeeper这样的外部协调服务的依赖。

Couchbase不会自动重新平衡，这简化了设计。通常情况下，它配置了一个名为moxi的路由层，它会从集群节点了解路由变化【32】。

当使用路由层或向随机节点发送请求时，客户端仍然需要找到要连接的IP地址。这些地址并不像分区的节点分布变化的那么快，所以使用DNS通常就足够了。

分布式系统的麻烦

单调钟适用于测量持续时间（时间间隔），例如超时或服务的响应时间：Linux上的clock_gettime(CLOCK_MONOTONIC)，和Java中的System.nanoTime()都是单调时钟。这个名字来源于他们保证总是前进的事实（而时钟可以及时跳回）。

你可以在某个时间点检查单调钟的值，做一些事情，且稍后再次检查它。这两个值之间的差异告诉你两次检查之间经过了多长时间。但单调钟的绝对值是毫无意义的：它可能是计算机启动以来的纳秒数，或类似的任意值。特别是比较来自两台不同计算机的单调钟的值是没有意义的，因为它们并不是一回事。

一致性与共识

强一致性也叫线性一致性。

dynamo不能强一致性

因为是无主复制系统，可能写时只有一个节点写入成功了，然后读的节点正好没有它，造成读不到。

除非所有节点都写，读所有节点，才可以强一致性。

一致性

强一致性和性能、可用性往往冲突。

时代编号

用于区分谁是新领导，谁是旧的，新领导说的算。投票赞成的一个有效依据就是没有其他更高时代编号

时代编号（epoch number）（在Paxos中称为投票编号（ballot number），视图戳复制中的视图编号（view number），以及Raft中的任期号码（term number）），并确保在每个时代中，领导者都是唯一的。

每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新领导。这次选举被赋予一个递增的时代编号，因此时代编号是全序且单调递增的。如果两个不同的时代的领导者之间出现冲突（也许是因为前任领导者实际上并未死亡），那么带有更高时代编号的领导说了算。

在任何领导者被允许决定任何事情之前，必须先检查是否存在其他带有更高时代编号的领导者，它们可能会做出相互冲突的决定。

它必须从法定人数（quorum）的节点中获取选票（参阅“读写的法定人数”）。对领导者想要做出的每一个决定，都必须将提议值发送给其他节点，并等待法定人数的节点响应并赞成提案。法定人数通常（但不总是）由多数节点组成【105】。只有在没有意识到任何带有更高时代编号的领导者的情况下，一个节点才会投票赞成提议。

因此，我们有两轮投票：第一次是为了选出一位领导者，第二次是对领导者的提议进行表决。关键在于，这两次投票的法定人群必须相互重叠（overlap） 如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举【105】。因此，如果在一个提案的表决过程中没有出现更高的时代编号。那么现任领导者就可以得出这样的结论：没有发生过更高时代的领导选举，因此可以确定自己仍然在领导。然后它就可以安全地对提议值做出决定。

参考

https://vonng.gitbooks.io/ddia-cn/content/part-i.html