当数据库遇到分布式

数据库通常有着完善的事务支持，但是局限于单机的存储和性能，于是就出现了各种分布式解决方案。最近读了《Designing Data-Intensive Applications》这本书，所以做一个总结，供大家做个参考，有什么不对的请大家指正，一起讨论。

数据模型

数据模型可以说软件开发中最重要的部分，因为影响着我们的思考方式、解题思路以及代码的编写方式。多数应用使用层层叠加的数据模型进行构建，对于每层数据模型的关键问题是：它如何用低一层的数据模型来表示。

多数应用程序开发都使用面向对象编程的编程语言来开发，所以一个数据模型是否能够很好表示对象以及对象之间的关系就成为我们选择的标准。

对象由各类属性组成，对象的关系通常有一对多/多对一和多对多。

关系模型

关系模型使用表、行、字段分别表示一类实体的集合、一个实体以及一个实体的一个属性；在其中一个实体的字段中存储另一实体的Id标识来表示实体之间多对一的关系，使用单独的关联表存储两个实体的Id标识来表示实体建多对多的关系。

关系模型具有强模式，必须在写数据前定义好，即写模式，类似编程语言的静态（编译时）类型检查。

下面的示例是Linked的一个简历的关系型表示：

文档模型

采用类似JSON的格式存储，存储的内容是文档型。利用JSON天然的嵌套关系可以灵活表示一对多的实体关系，当然通过存储文档的Id，也可以表示多对一和多对多的关系。

相对于关系模型，文档模型减少了应用程序代码和存储层之间的阻抗不匹配，在一对多关系下，具有更好的局部性。

文档模型具有读时模式，对写入没有模式要求。类似编程语言的动态（运行时）类型检查。

对于上面简历的例子，使用文档模型的表示如下：

图模型

图模型强调是对象之间的连接，当应用是围绕众多对象连接以及对这些连接进行的查询和计算时，就需要考虑使用图模型的数据库。

一个图由顶点（表示的是实体）和边（实体之间关系）组成，一个复杂的图模型通常由数十亿的顶点和千亿的边组成。

以下是社交网络的一个示例：表示的是两个人之间的以及居住地点。

每种数据模型都有其对应的查询语言，关系型使用SQL，而图模型也有相应的查询语言来描述图模型的特点，但是还没有形成业界标准。

存储引擎

上面我们熟悉了数据模型，但是了解数据内部的存储和检索原理，对于我们设计和开发应用以及数据库的选型也是非常有帮助的。

数据库的主要功能是存储数据以及后续进行查询和更新，目前主要有两大类数据库：传统关系型数据库（面向页面 page-oriented） 和 NoSQL数据库（基于日志结构log-structured）。

面向页面

B树是几乎是数据库标准的索引实现，B数将数据库分解成固定大小的块或页面，通常在4k-32k范围，一次只能读取或写入一个页面。这种设计更接近与底层的硬件，因为磁盘也是由固定大小的块组成的。

每个页面都可以使用地址来标识，一个页面引用另一个页面，类似于指针，但是在磁盘而不是在内存中，如图所示：

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

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

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

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

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

日志结构

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

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

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

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

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

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

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

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

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

LSM树的基本思想

保存一系列在后台合并的SSTables，即使数据集比可用内存大得多，仍能继续工作。由于数据按序存储，因此可以高效地执行范围查询（扫描所有高于某些最小值和最高值的所有键），并且磁盘写入时连续的，所以可以支持非常高的写入吞吐量。

事务

在数据库系统中，会遇到各种问题：

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

事务一直是简化这些问题的首选机制。事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。从概念上讲，事务中的所有读写操作被视为单个操作来执行：整个事务要么成功，要么失败后回滚。如果失败，应用可以安全地重试。对于事务来说，应用的错误处理简单多了，不用担心部分失败的情况了。

事务提供的安全保障，由ACID来描述。即原子性Atomicity,一致性Consistency，隔离性Isolation，持久性Durability，旨在为数据库中的容错性建立精确的术语。

单对象 vs 多对象

事务通常被理解为，将对多个对象上的多个操作合并为一个执行单元的机制。但许多分布式数据库只提供了单对象的原子性和隔离性（原子性通过同步写日志实现崩溃恢复；隔离性通过每个对象上锁实现单线程访问），以及更复杂的原子操作，如自增 和 CAS。所以要注意这一点，看是否满足自己的应用场景。

多对象事务，除了要处理复杂原子性和隔离性，分布式场景下，还会涉及到跨分区（不能分区可能在不同的机器上），即分布式事务。

隔离级别

如果两个事务不触及相同的数据，它们可以安全地并行执行，因为两者都不依赖对方。当一个事务读取另一个事务同时修改的数据，或者两个事务试图同时修改相同的数据，并发问题才会出现。

并发bug很难通过测试找到，因为这样的错误只有在特殊时机下才会触发，很难重现。出于这个原因，数据库一直试图通过提供事务隔离来隐藏应用开发者的并发问题。事务隔离级别越强越能够避免发生的并发问题，比如可序列化保证事务的效果与串行执行是一样的，但这意味着并发性能的牺牲。所以数据库系统通常使用较弱的隔离级别，来防止一部分并发问题，而不是全部，所以了解这些对于开发出正确的应用非常重要。

脏写

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

脏读

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

不可重复读

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

丢失更新

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

写偏差

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

读已提交

读已提交提供两种保证

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

可重复读/快照隔离

支持快照隔离的数据库保留了一个对象的不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同时间点的状态。这种技术被称为多版本并发控制（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要求同时读写的事务尽量短。

分布式事务

在多对象事务中，如果不同对象存在不同的分区中，则就需要处理分布式事务。提到分布式事务，就不得不介绍两阶段提交，两阶段提交是分布式事务的基本思想。

两阶段提交

两阶段提交2PC（two-phase commit）是一种用于实现跨多个节点的原子事务提交的算法。可以在数据库内部使用，也可以以XA事务的形式对应用可用。

两阶段提交引入了协调者的角色，整体分为两个阶段，具体的过程如下：

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

两阶段提交固有的成本：由于崩溃恢复所需的强制刷盘以及额外的网络往返，另外整个过程会进行资源的锁定。

Percolator

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

Percolator 是一个无中心化（没有协调者）的两阶段提交，基于BigTable的单行事务，实现了跨行的事务引擎。另外借助BigTable的多时间戳版本，可以实现快照隔离级别。

Percolator依赖中心的授时器，没有单点 Coordinator 的角色，交由所有客户端来协调上锁协议，但是赶上崩溃锁会泄露。Percolator 选择了惰性地回收泄露的锁：其他客户端在 Get() 到这行数据时，如果遇到锁，则选择等待退避重试，或者清理锁。

但是由于Percolator使用乐观锁检测机制，对于热点数据的并发更新不友好。我觉得这一点可以通过在Percolator之上实现悲观锁机制来解决。

分区

分区（partitions）也叫分片（sharding），是将数据集进行拆分成多个分区，每个分区存储在不同的机器上，扩展了整体的存储量，提高了写入和读取的性能。但也带来了新的困难，数据库要支持跨分区的写入和读取。

分区方式

分区的目标是将数据和查询负载均匀的分布在各个节点上。如果分区是不公平的，或者没有考虑热点数据，那么一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。数据分区通常基于Key进行拆分，在考虑数据偏斜的情况，要根据数据库的特定的分区算法，特别注意Key的设计。

根据Key的范围分区为每个分区指定一块连续的Key范围，分区Key的边界一般由数据库自动选择。好处是范围扫描非常简单。但是如果Key的设计不合理，会到热点数据，影响查询效率。

根据Key的散列分区通过一个散列函数对Key进行计算后，再进行分区。这样可以消除偏斜和热点的风险，但是失去了原有Key的范围查询的属性。

有些数据库，如Cassandra，采取了折中的策略，使用多个列组成的复合主键来声明。键中只有第一列会作为散列的依据，而其他列则被用作Cassandra的SSTables中排序数据的连接索引。尽管查询无法在复合主键的第一列中按扫描扫表，但如果第一列已经指定了固定值，则可以对该键的其他列执行有效的范围扫描。组合索引的方法为一对多关系提供了一个优雅的数据模型。

索引构建

上面我们讨论了主键的分区策略，实际情况上辅助索引/二级索引也是很有必要的，特别是在关系模型中。

辅助索引的构建方式有两种：本地索引和全局索引

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

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

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

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

分区再平衡

随着数据集大小增加、查询吞吐量的增加，需要更多的机器来处理。这些都需要数据和请求从一个节点移动到另一个节点，这一过程称为再平衡（reblancing）。

再平衡通常要满足以下几点要求：

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

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

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

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

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

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

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

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

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

请求路由

现在我们已经数据集分割到多个节点上运行的多个分片上，客户端发起请求时，如何知道连接哪个结点。随着分区再平衡，分区对节点的分配也发生变化。

不仅限于数据库，这个问题可以概括为服务发现（service discovery），通常有以下三种方案：

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

以上问题的关键在于：做出路由决策的组件如何了解分区-节点之间的分配关系变化？这是一个具有挑战性的问题，因为需要所有的参与者达成一致。

很多分布式系统都依赖于一个独立的协调服务，比如ZooKeeper来跟踪集群元数据。

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

复制

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

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

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

单领导者复制过程：

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

同步 or 异步

复制系统的一个重要细节是 复制 是 同步发生 还是 异步发生。同步复制会使得数据写入时间变长，而异步复制会使得副本之间的数据不一致，客户端可能会读取到历史的数据，并且在主库故障时有可能会丢失数据。所以复制系统的核心就是如何让副本保持一致，并且在主库故障时能够自动切换。

一致性模型

一致性模型（consistency model）实质上是进程和数据存储存储之间的一个约定。即，如果进程同意遵守某些规则，那么数据存储将正常运行。正常情况下，一个进程在一个数据项执行读操作时，它期待该操作返回的是该数据在其最后一次写操作之后的结果。

在没有全局时钟的情况下，精确地定义哪次写操作时最后一次写操作是十分困难的。作为替代的方法，我们需要提供其他的定义，因此产生了一系列的一致性模型。每种模型都有效地限制了在一个数据项上执行一次读操作所应返回的值。

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

以数据为中心

线性一致性

线性一致性也称为严格一致性（Strict Consistency）或者原子一致性（Atomic Consistency），需要满足以下两个条件：

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

线性一致性的想法是让一个系统看起来只有一个数据副本，而且所有的操作都是原子性的。应用不用担心多个副本带来诸多问题，是一个完美的理想模型，作为其他模型的参考（最强一致性模型）。

在线性一致性的数据存储中不存在并发操作：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。

顺序一致性

顺序一致性最早出现在Shared-Memory Multi-Processor System单机模型中，为程序员提供了极强的内存可见性保证。顺序一致性内存模型有两大特性：

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

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

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

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

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

线性一致性可以定义为具有实时约束（real-time constraint）的顺序一致性。

个人理解，在分布式副本的领域中，不太可能找到 除了时序之外，各个进程能够一致认可的顺序。所以在分布式副本领域参考意义不大，更容易造成疑惑。

因果一致性

相对于线性一致性保证读写具有全局顺序，而因果一致性只需要保证具有相互依赖的读写操作保持相同的顺序即可。实际上因果一致性是性能和可用最高的强一致性模型。

因果一致性实现的难点在于如何定义和捕获因果关系，你需要知道哪个操作发生在哪个操作之前（happen before）。但是这种因果关系更多是来自上层应用，底层存储是无法感知的，所以跟踪所有的因果关系是不及实际的。

因果关系的操作在时序上一定是有先后，所以通过全序的的序列化或时间戳（逻辑时钟）来排序操作，这样所有的操作都有了时间上的因果先后关系。所以线性一致性是所有操作都满足因果一致性（即使大部分操作没有依赖关系）。

最终一致性

最终一致性不能算是一致性模型，没有任何一致性保证，只是说在没有更新的情况下，副本之间会在一定时间内保持一致。因为由于网络延迟的存在，应用任何时候都可能读取到不一致的数据。可以说是可接受的最弱的一致性模型。

以客户端为中心

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

以客户端为中心的一致性为单一客户端提供一致性保证，保证该客户端对数据存储的访问的一致性，但是它不为不同客户端的并发访问提供任何一致性保证。

以客户端为中心的一致性包含了四种模型：

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

但是真实情况是，由于服务器负载均衡以及服务器故障的存在，会导致客户端会话会发生转移，因此基于客户端访问的一致性模型是不靠谱的。

共识协议

Lamport时间戳

我们知道分布式系统中，各个机器拥有相同的时钟（全局时钟）是不太可能的。1978年Lamport在一篇论文中提出了一种逻辑时间戳，来解决分布式系统中区分事件发生的时序问题。这篇论文是分布式系统领域被引用最多的论文之一。

Lamport时间戳就是两者的简单结合：时间戳/计数器 节点ID，规则如下：

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

上图，ABC节点的所有事件的全序关系如下：

Lamport时间戳背后的思想是：两个事件可以建立时序（因果）关系的前提是两个事件之间是否发生过信息传递。因此Lamport时间戳只保证因果关系（偏序）的正确性，不保证绝对时序的正确性。

全序广播

Lamport时间戳通过消息的传递来确定事件的时序关系，引出了全序广播（在节点间交换消息的协议）。全序广播需要满足两个安全属性：

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

全序广播正是数据库复制所需要的：如果每个消息都代表一次数据库写入，且每个副本都按照相同的顺序处理相同的写入，那么副本相互保持一致（除了临时的复制延迟，可以将读操作也作为消息，来实现一致读）。这个原理被称为状态机复制（state machine replication）。

因为数据库的写入和读取操作都是通过消息交互达成一致，依据Lamport时间戳，所有的操作是全序的，因此可以实现线性一致性存储。

Raft协议

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

Raft协议动画演示：thesecretlivesofdata.com/raft/

在Raft集群里，服务器可能会是这三种身份其中一个：领导（leader）、追随者（follower），或是候选人（candidate）。在正常情况下只会有一个领导，其他都是追随者。而领导会负责所有外部的请求，如果不是领导的机器收到时，请求会被导到领袖。

Raft将问题拆成数个子问题分开解决：

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

详细的介绍请移步：

Raft论文:https://Framcloud.atlassian.net/Fwik/download/attachments/6586375/raft.pdf

Raft中文翻译:https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md

TODO

后面有时间分析下TiDB（分布式开源HTAP数据库，兼顾事务性和分析性）。可惜OceanBase不开源啊。

参考资料

en.wikipedia.org/wiki/Consis…

en.wikipedia.org/wiki/Sequen…

github.com/ept/hermita…

duanple.com/?p=964

jin-yang.github.io/post/raft-c…

juejin.cn/post/684490…

github.com/ngaut/build…

tikv.org/deep-dive/d…

zhuanlan.zhihu.com/p/47299592

pingcap.com/blog-cn/per…