当数据库遇到分布式

数据模型

关系模型

存储引擎

面向页面

在B树的页面中对子页面的引用的数量称为分支因子，分支因子取决于页面大小和索引key的大小，分支因子越大越好。（分支因子为500的4KB页面的四级树可以存储多大256TB）

数据查询时，从根页面（通常缓存在内存）出发，根据页面引用寻找满足条件范围的页面，一直到叶子节点。

数据更新时，定位到叶子结点，用新数据覆盖磁盘的页面。

数据插入和删除时，会涉及到页面的拆分和合并，来保持B树的平衡

为了保证数据查询和写入的高性能，数据库通常会对页面数据进行内存缓存，当数据有更新时，不会立即更新磁盘数据，而是先更新内存缓存的页面数据，同步追加写入WAL日志（write-ahead-log），异步将内存中的脏页刷到磁盘上（将磁盘随机写变为顺序写）。当数据库崩溃后恢复时，这个日志用来是B树恢复到一致的状态。

日志结构

基于日志结构的存储模式，每次数据新增或更新时，仅仅将数据追加到特定日志文件中，当文件超过一定大小时，则打开一个新的文件写入。

每个日志结构存储段都是一系列键值对，但是为了后续便于查询数据，要求键值对在文件中按照键排序，这种排序的字符串表(Sorted String Table)称为SSTable。

为了保证日志文件保持在一定的个数，多个文件段进行合并（归并算法），当出现多个同一键值时，用新的值覆盖老的，保证一个合并段同一个键出现一次。

内存中维护者键到日志文件的索引，该索引是稀疏的，每几千个字节的段文件就有一个键就足够了，因为几千字节可以很快被扫描。（可以将部分记录分组到块，压缩写入磁盘）

如何构建和维护SSTable呢（保证按照键排序存储）

• 写入数据时（新增、删除、更改），将其添加到内存中的平衡树结构（如红黑树），这个内存树称为内存表（memtable);
• 为了避免丢失数据，写入内存表的同时会通过追加的方式写入WAL日志（数据库崩溃恢复时使用）；
• 当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。
  新的SSTable文件成为数据库的最新部分。

数据查询时，首先尝试在内存表中查找，然后在多个文件段中进行查找。（通过合并文件段使其维持在一定的个数，保证查找效率）

这种基于合并和压缩排序文件原理的存储引擎通常被称为LSM存储引擎。

当查找不存在的键时，LSM树算法可能会很慢。为了优化这种访问，通常使用额外的Bloom过滤器。

事务

• 数据库软件、硬件可能在任意时刻故障（包括写操作进行一半时）
• 应用程序任何时刻都可能崩溃（包括一系列操作的中间）
• 网络中断会切断应用与数据库的连接，或数据库之间的连接
• 多个应用可能会同时写入数据库，覆盖彼此的修改
• 应用可能会读取到无意义的数据，因为数据只更新了一部分
• 应用质检的竞争条件可能导致各种非预期结果

单对象 vs 多对象

脏写

脏写是指一个事务覆盖另一个事务未提交的数据，现有的隔离级别都会保证没有脏写。数据库通常使用行锁来防止脏写。

脏读

脏读是指一个事务写了部分数据，未提交，这是另一个事务读取到了这部分未提交的数据。

不可重复读

同一个事务两次读取的数据（读偏差） 或者 读取的记录数（幻读）不一致

丢失更新

两个事务同时读取数据，并进行更新，两个事务都更新成功，更新逻辑都是基于原先读取的值，但是事务提交会改变先前读取的值，导致丢失更新。典型的场景就是 读 -> 改 -> 写。

写偏差

可以将写入偏差视为丢失更新问题的一般化。如果两个事务读取相同的对象，然后更新其中的一些对象（不同的事务可能更新不同的对象），则可能发生写入偏差。

读已提交

读已提交提供两种保证

• 从数据库读时，只能看到已经提交的数据（没有脏读）

• 写入数据库时，只能覆盖已经写入的数据（没有脏写）

可重复读/快照隔离

支持快照隔离的数据库保留了一个对象的不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同时间点的状态。这种技术被称为多版本并发控制（MVCC，multi-version concurrency control）。

当一个事务开始，它被赋予一个唯一个的，永远增长的事务ID（txid）。每当事务向数据库写入任何内容时，它所写入的数据都会被标记上写入者的事务ID。

一个事务能查到一个对象，满足以下两个条件：

• 读事务开始时，创建该对象的事务已经提交

• 对象未被标记为删除，或如果被标记为删除，请求删除的事务在读事务开始时尚未提交

对于丢失更新和有数据交叉的写偏差，数据库可以结合快照隔，可以自动检测到丢失更新，中止相应的事务。但是MySQL/InnoDB的可重复读并不会检测丢失更新。有些作者认为，数据能防止丢失更新才能称得上快照隔离，所以这种定义下，MySQL并不提供快照隔离。

MySQL/InnoDB可重复读隔离级别下，可以使用 锁定读 （select for update）或者 比较并设置CAS 来避免丢失更新。

需要注意的是，如果数据库允许where字句从旧快照中读取，则此语句可能无法防止丢失更新，因为即使发生了另一个并发写入，where条件也可能是真的。

序列化

但对于写入数据无交叉的写偏差，只能通过序列化的隔离级别来避免，但是可以在应用层面通过 物化冲突的方式，人为的在数据库中引入一个锁对象。

• 字面意义的串行顺序执行事务
• 两阶段锁定（2PL，two-phase locking），通过对读操作对象加共享锁，对写操作对象加独占锁实现，共享锁可以升级为独占锁。
  共享锁之间不互斥，共享锁与独占锁 以及 独占锁之间互斥。
  同时数据库会自动检测事务之间的思索，并中止一个。
  两阶段是一种所谓的悲观并发控制机制。
• 乐观并发控制技术，可序列化的快照隔离SSI（serializable snapshot isolation），是一种乐观的并发控制机制，读写数据时并不加锁，而是在事务提交时，通过特定的算法检测写入之间的序列化冲突，并确定要中止哪些事务。
  好处是读和写不相互阻塞，只读查询运行在一致的快照上，对于读取繁重的场景非常有吸引力。
  但是中止率显著影响SSI整体的表现。
  长时间读取和写入数据的事务很可能会发生冲突并中式，因为SSI要求同时读写的事务尽量短。

分布式事务

• 当应用想要启动一个分布式事务时，它向协调者请求一个全局唯一的事务ID。
• 应用在每个参与者启动单节点事务，每个单节点事务都带上这个全局事务ID。
  所有的读写都是在单节点事务中各自完成的。
  如果这个阶段出现任何问题，则协调者或任何参与者都可以中止。
• 当应用准备提交时，协调者向所有参与者发送一个准备请求，并带上全局事务ID。
  如果任意一个请求失败或超时，则协调者向所有参与者发送针对该事务ID的中止请求。
• 参与者收到准备请求时，需要确保在任何情况下都的确可以提交事务。
  这包括所有事务数据写入磁盘（出现故障，电源故障，或磁盘空间不足都不能是稍后拒绝提交的理由）以及检查是否存在任何额冲突或违反约束。
  一旦作出承诺，就不允许反悔。
• 当协调者收到所有准备请求的答复时，会就提交或中止事务作出明确的决定（只有所有参与者赞成的情况下才会提交）。
  协调者必须吧这个决定写到磁盘的事务日志中。
• 一旦协调者的决定落盘，提交或放弃请求会发送给所有参与者。
  如果请求超时或失败，协调者必须永远保持重试。

Percolator是由Google公司开发的、为大数据集群进行增量处理更新的系统，主要用于google网页搜索索引服务。使用基于Percolator的增量处理系统代替原有的批处理索引系统后，Google在处理同样数据量的文档时，将文档的平均搜索延时降低了50%。

分区

索引构建

本地索引文档分区所以，在这种索引方法中，每个分区是完全独立的，每个分区维护自己的二级索引，仅覆盖该分区中的文档。当数据写入时（添加、删除、更新），只需要处理分区内数据的索引更新。数据查询时，则需要将查询发送到所有的分区，并合并所有返回的结果。

这种查询分区数据库的方法有时被称为分散/聚集（scatter/gather），并且可能会是二级索引上的读取查询相当昂贵。即使并行查询分区，已容易导致尾部延迟放大。MongoDB、Cassandra、ElasticSearch、SolrCloud都是使用这种文档分区二级索引。

全局索引关键词分区，这种索引方法跟主键分区的方式是一样的。相对于文档分区索引，读取更有效率，不需要分散/聚集所有分区，客户端只需要向包含关键词的分区发出请求。缺点在于写入速度较慢且较为复杂，因为写入单个文档可能会影响索引的多个分区。

理想情况下，索引总是最新的。写入数据库的每个文档都会立即反映在索引中。在基于关键词的全局索引中，这需要跨分区的分布式事务，并不是所有的数据库都支持。在实践中，对全局二级索引的更新通常是异步的。

分区再平衡

• 再平衡之后，负载（数据存储、读取和写入请求）应该在集群中的节点之间公平地共享
• 再平衡发生时，数据库应该继续接受读取和写入
• 节点之间只移动必须的数据，以便快速再平衡，并减少网络和磁盘I/O负载

平衡策略可以分为几种：固定数量的分区、动态数量的分区和按节点比例分区

固定数量的分区创建比节点更多的分区，并为每个节点分配多个分区。如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。ElasticSearch使用这种方式分区策略。

只有分区在节点间移动，分区的数量不会改变，键所对应的分区也不会改变，唯一改变的是分区所在的节点。这种变更不是实时的（网络上传输数据需要时间），传输过程中，原有分区仍然会接手读写请求。

分区的数量通常在数据库第一次建立时确定，之后不会改变。每个分区包含了总数据量固定比率的数据，因此每个分区的大小与集群中的数据总量成比例增长。如果数据集的总大小难以预估，选择正确的分区数是困难的。分区太大，再平衡和节点故障恢复变得昂贵；分区太小，则会产生太多的开销。

动态数量的分区对于使用键范围进行分区的数据库，具有固定边界的固定数量的分区将非常不方便：如果出现边界错误，则可能会导致某些分区的没有数据。按键范围进行分区的数据库通常会动态创建分区。

当分区增长到超过配置的大小时，会被拆分成两个分区，每个分区约占一半的数据。动态分区的优点是分区数量适应总数据量，能够平衡各方面的开销。HBase和MongoDB采用的就是这种策略。

数据集开始时很小，直到达到第一个分区的分隔点，所有写入操作都必须由单个节点处理，而其他节点处于空闲状态。为了解决这个问题，HBase和MongoDB允许在一个空的数据库上配置一组初始分区（预分隔，pre-splitting）。在键范围分区的情况下，预分隔需要提前知道键时如何分配的。

按照节点比例分区分区数与节点数量成正比，即每个节点具有固定数量的分区。每个分区的大小与数据集大小成比例的增长。当增加节点时，随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中的每个分区的一半。

请求路由

• 允许客户端连接任何节点，如果该节点恰巧拥有请求的分区，则直接处理该请求；
  否则将请求转发到适当的节点，接收结果并返回给客户端。
• 客户端发送请求到路由层，它决定了应该处理请求的节点，并相应的转发。
• 客户端知道分区和节点的分配，直接连接到适当的节点。

• 每个节点在ZooKeeper上注册自己，ZooKeeper维护分区到节点的可靠映射
• 路由层可以在ZooKeeper订阅此信息，当分区分配发生变化能实时感知

复制

复制意味着在通过网络连接的多台机器上保留相同数据的副本，复制数据能带来以下的好处：

• 提高可用性，即使系统的一部分出现故障，系统也能继续工作
• 扩展可以接受读请求的机器数量，从而提高读取吞吐量
• 使得数据与用户再地理上接近，从而减少延迟

• 每一次向数据库的写入操作都需要传播到所有的副本上，否则副本就会包含不一样的数据。
  最常见的解决方案被称为基于领导者的复制 或 主从复制
• 副本之一被指定为领导者（或主库），当客户端要向数据库写入时，它必须发给领导者，领导者会将新数据写入其本地存储；
• 其他副本被称为追随者（只读副本、从库），会同步主库的变更日志，按照主库相同的顺序写入
• 当客户端从数据库读取数据时，可以向领导者或追随者查询

一致性模型

注意：不将数据库事务的一致性与其混淆，分布式副本的一致性指的是单个对象的写入和读取。

线性一致性

• 任何一次读都能读取到某个数据最近的一次写的数据。
• 所有进程看到的操作顺序都跟全局时钟下的顺序一致。

• 任何执行的结果都与所有处理器的操作按某种顺序执行的相同。
• 每个单独的处理器的操作顺序均按照其程序指定的顺序。
• 所有操作都必须相对于每个其他处理器立即或原子执行（立即可见）。

在时间顺序上，C1发生于B2之后。对于线性一致性来说，C1一定在B2之后，但是对于顺序一致性B2可以发生在C1之后。

顺序一致性可能会产生不确定的结果。这是因为在程序的不同运行期间，处理器之间的顺序操作的顺序可能会有所不同。

对于顺序一致性来说，它要找到一个合法的顺序执行过程，该执行过程要保留线程/进程内部原有的顺序

对于线性一致性来说，它也是要找到一个合法的顺序执行过程。但是这个顺序执行过程，不仅要保留线程/进程内部的先后顺序，还要保留线程/进程之间的操作的先后顺序。

以客户端为中心

上面讨论的以数据存储为视角的一致性，在因果一致性以及更强的一致性模型中，从客户端而言是不会发生预料之外的读写问题的。但是在更弱的一致性模型而言，出现各种读写问题。

• 单调读一致性（Monotonic-read Consistency）：
  如果一个进程读取数据项 x 的值，那么该进程对于 x 后续的所有读操作要么读取到第一次读取的值要么读取到更新的值。
  即保证客户端不会读取到旧值。
• 单调写一致性（Monotonic-write Consistency）：
  一个进程对数据项 x 的写操作必须在该进程对 x 执行任何后续写操作之前完成。
  即保证客户端的写操作是串行的。
• 读写一致性（Read-your-writes Consistency）：
  一个进程对数据项 x 执行一次写操作的结果总是会被该进程对 x 执行的后续读操作看见。
  即保证客户端能读到自己最新写入的值。
• 写读一致性（Writes-follow-reads Consistency）：
  同一个进程对数据项 x 执行的读操作之后的写操作，保证发生在与 x 读取值相同或比之更新的值上。
  即保证客户端对一个数据项的写操作是基于该客户端最新读取的值。

共识协议

Lamport时间戳

• 每个事件对应一个Lamport时间戳，初始值为0
• 如果事件在节点内发生，本地进程中的时间戳加1
• 如果事件属于发送事件，本地进程中的时间戳加1并在消息中带上该时间戳
• 如果事件属于接收事件，本地进程中的时间戳 = Max(本地时间戳，消息中的时间戳) + 1
• 事件的顺序按照时间戳排序，时间戳相同则按照节点ID大小排序

全序广播

• 可靠交付 （reliable delivery），没有消息丢失：
  如果消息被传递到一个节点，它将传递到所有节点
• 全序交付（total ordered delivery），消息以相同的顺序传递给每个节点

Raft协议

Raft是一种共识算法，旨在使其易于理解。它在容错和性能上与Paxos等效。不同之处在于它被分解为相对独立的子问题，并且干净地解决了实际系统所需的所有主要部分，实际将上面的 全序广播/状态机复制 的工程化。

• 领导选举（Leader Election）
• 日志复制（Log Replication）
• 集群成员变化 （Cluster membership changes）
• 安全性（Safety）

TODO

参考资料

如喜欢本文，请点击右上角，把文章分享到朋友圈
如有想了解学习的技术点，请留言给若飞安排分享

·END·