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

数据模型

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

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

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

关系模型

关系模型使用表、行、字段分别表示一类实体的集合、一个实体以及一个实体的e @ { 5 c , m一个属性；在其中一个实体的字段中存储另一实体的Id标识来表示实体之间多对一的关系，使用单独的关联~ L A p - & [ g表存储两个实体的Id标识来表示实体建多对多的关系。

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

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

文档模型

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

相对于关系模型，文档模型减少了应用程序代码和存储层之间的阻抗不E K , 。

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

这种M | w x *基于合并和压缩排序文件原理的存储引擎通常被称为} w a n % u KLSM存储引擎。T o !

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

LSM树的基本思想

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

事务

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

数据库软件、硬件可能在任H p e 7 M =意时刻故障（包括写操作进行一半时）
应用g z 7 W r ` * Q 3程序任何时刻都可能崩溃（包括一系列操作的中间）
网络中断会切断应用与数据库的连接，或数据库之间的连接
多个应用可能会同时写. : k V ? i ) 1 ~入数据库，覆盖彼此的修v w (改
应用可能会读取到无意义的数据，因为数- S X j据只更新了N s / 0 K 0 5 d一部分
应用质检的竞争条件可能导致各种非预期结果

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

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

单对象 vs 多对象

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

多对象事务，除了要处理复杂原子性和隔离性，分Y } t A T ^ v f布式场景下，还会涉及到M E V R E 跨分区（不能分区可能在不同的机器上），即分布式事务。

隔离级别

如果{ e a I t S * {两个事务不触及相同的数据，它们可以安全地并行执行，因为两者都不依赖对方。P I n 2 = P ~当一个事务读取另一个事务同时_ o x c w B p s修改的数据，或者两个事务试图同时修改相同的数据，并发问题才会出现。

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

脏写

脏写是指一个事务覆盖另一个事L V d 1 M t 7务未提交的数据，现有的隔离级别都会保证没有脏写。数据库通常使用行锁来A % A Y i m 8 }防止脏写。

脏读

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

不可重复读

同一个事务两次读取的数据（读偏差）或者读取o 5 % a : &的记录数（幻读）不一致

丢失更新

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

写偏差

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

读已提交

读已提交提供两种保证

从数据库读时，d m G 7 B只能看到已经提交的数据（没有脏读）
写入数据库时，只能覆盖已经写p e T - O $ P K入的数据（没有脏写）

可j { .重复读/快照隔离

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

当一个事务开始，它被赋予一个唯一个的，永远增长的事务N v , S y 3 k iID（txid）。每当事务向数据库写入任何内容时，它W r ~ ` e M 1所写入的数据都会被标记上写入者的事务ID。

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

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

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

MySQL/InnoDB可重复读隔离D m 0 V 6级别下，可以使用锁定读（selI , X Z $ A T。

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

序列化

但对于写入数据无交叉的写偏差，只能通过8 t Z z序列化的隔离级别来避免，但是可以在应用层面通过物化冲突的方^ p ] U [ C [ F式，人为的在数据库中引入一个锁对象。2 t . U D h

序列化隔离{ : X级别有三种实现方式：

字面意义的串行顺序执行事务
两阶段锁定（2PL，tB P 7 g q S two-# | F V S b & y fphase lockn E i t R I ving）Q % ( | Q { 7 a，通过对读操作对象加X 5 | @ P共享锁，对写操作对象加独占锁实现，共享锁可以升级为独占锁。共享锁之间不互斥，共享锁与独占锁以及独占锁之间互斥。同时数据库会自动检测事务之间的思索，并中止一个。两阶段是一种所L f @ E / U z 7 G谓的悲观并发控制机制。
乐观并发控制技术，可序列化的快照隔离SSI（serializable snapshot isolatF 7 dion），是一种乐观的并发控制机制，读写数据时并不加锁，而是在事务提交时，M - I通过特定的算法检测写入之间的序列化冲突，并确定要中止哪些事务。好处是读v + D : v [ Y和写不相互阻塞，只读查询运行在一致的快照上，对于读取繁重的场景非常有吸引力。但是中止率显著影响SSI整体的表现。长时间读取和写入数据的事务很可能会发生冲突并中式，因为SSI要求同时读写的事, H u O )务尽量短。

分布式事务

在多对象事务中，如果不同对象存在不同的分区中，则就需要处理分布式事: + v种用于p p a实现跨多个节点的原子事务提交的算法。可以在数据库内部使用，也可以以XA事务的形式对应用可用。

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

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

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

Percolator

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

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

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

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

分区

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

分区方式

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

根据Key的范围分区 为每个分区指定一块D o 8连续的Key范围，分区Key的边界一w V K 8 { Q ] !般由数据库自动选择4 4 A r w 7 W 0 1。好处是范围扫描非常简单。但是如果Key的设计不合理，会到热点数据，影响查询效率。

根据Key的散列分区 通过一个散列函数对Ke^ $ z / W jy进行3 & :计算后，再进行分区。这样可以消除偏斜和热6 ~ i c点的风险，但是失去了原有Key的范围查询的属性。

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

索引构建

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

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

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

这种查询分3 u Y l ` S E + 1区数据库的方法有时l ` k j ] s #并w ^ , O 1行查询分区，已容易导致尾部延迟放大。MongoDB、Cassandra、ElasticSearch、SolrCloud都是使用这种文档分k 2 Y @ g !区二级索引。

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

理想情况下，索引总是最新的。写入数据库的每个文档都会立即反映在索引中。在基于关键词的全局索引中，这需要跨分区的分布式事务，并不是所有= R q # c o的数据库都Q K q 2支持。在实践中8 V 0，对全局二级索引的更新通( k T C 6 :常是异步的。

分区再平衡

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

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

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

平衡策略可以分为几种：固6 + +定数量的分区, b I U i } j 4、动态数量的分区和按节点比例分区

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

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

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

动态数量的分区 对于使用键范围进行分区的数据库，具有固定边界的固定数量的分区将非常不c A / A O + d X Q方便：如果出现边界错误，则可能会导致某些分区的没有数据。按键范围进行分区的数D e o = 1 ^ R据库通常会动态创建分区。

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

数据集开始7 d n L时很小，直到达到第一个分区的分隔点，所有写入操作都必须由单个节点处理，而其他节t O j P ~点处于空闲状态z 7 | v c h 2 (。为了f 5 x m ] T W )分区（预分隔，pre-splitting）。在键范围分区的情况下，预分隔需要提前知道键时如何分配的o R c E。

按照节点比例分区 分区数与节点数量成正比，即每个h W , y p节点具有固定数量的分区。每个分区的大小与数据集大小成比例的增长。当增加R w c ~ v R i节点时，随机选择固定数量的现有分区进y : g d 4 1 $ U行拆分，然后占有这些拆分分区中的每个分区的一半。

请求路由

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

不仅K i k G J +限于数据库，这个问题可以概L 6 x u t T 7括为服务发现（service dr ` 6 F + Z fiscovery），通常有以X C ; 1 z D返回的值。

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

以数据为中H O ^ |心

线性一致性

线性K G 7 7 $ P D (一致性也称为严格一致性（Strict Consistency）或者原子一致性（Atomic Consi] X m G T R o ; .s0 N y C 1 _ q C otency），需要满足以下* # J R u s G两个条件：

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

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

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

顺序一致性

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

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

在时间顺序Z J Y 7 X K上，C1发生于B2之后。对于线性一z ) q 8 e z v B致性来说，C1一定在B2之后，但是对于顺序一致性6 @ J 9 [ i j ; |B2可以发生在C1之后。

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

对于顺序一致 @为视角的一致T ^ ! Z A Q t性，在因果一致性以及更强的一致性模型中，从客户端而言是不 j Sow-reads Consistency）：同一个进程对数据项 x 执行的读操作之后的写操作，保证发生在与 x 读取值相同或比之更新的值上。即保证客户端对一m ) l j / D个数据项的写操作是基于该客户端最C t F @ z C O ! /新读取的值。
但是真实情况是，由于服务器负载均衡以及服务器故障的存在，会导Q N T K g & h & h致客户端会话会发生转移，因此基于客户端访问的一致性模型是不靠谱的。
共识协议
Lampon n p J krt时间戳
我们知道分布式系统中，各个机器拥有相同的时钟（全局时钟）是不太可能的。1978年Lamport在一篇论文中提出了一种逻辑时间戳，来解决分布式系统中区分事件发生的时序问题。这篇论文是分布式系统领域被引用最多的论文之一。

Lamport时间x d y !戳就是两者的简单结合：时间戳/计数器 + 节点ID，规则如下：
每个事件对应一个Lamport时间戳，初始值为0
如果事件在节点内发生，本地进程中的时间戳加1
如果事件属于P a W @ ! } J发送事件，本地进程中的时间戳加1并在 E v X ! # p消息中带上该时间P e 9 p o w l g {戳
如果事件属于接收事件，本地进程中的时间戳 = Max(本地时间戳，消息中的时间戳) + 1
事件的顺序按照时间戳排序，时间戳相同则按) 0 H照节点ID大小排序
上图，ABC节点的所有事件的全序关系如下：
Lamport时间戳背后的思想是：两个事件可以建立时序（因果）关系的前提是两个事件之间是否发生过信息传递。因此Lamport时间戳只保证因果关系（偏序）的正确性，不保证绝对时序的正确性。
全序广播
Lamport时间戳通过消息的传递来确定事件的时序关系，引出了全序广播（在节点间交换消息的协议）。3 h | B全序广播需要满足两个安全属性：
可靠N n n交付（reliable delivery），没有消息丢失：如果消息被传递到一个节点，它将传递到所有节点
全序交付（total ordered delivery），m r e 7消息以相同的顺序传递给每个节点
全序广播正是数据库复制所需要的：如果每个消息都代表一次数据库写入，且每个副本都按照相同的顺序处理相同的写入，那么副本相互保持一致（除了临时的复制延迟，可以将读操作也作为消息，g J L m n : E来实现一致读）。这个原理被称为状态机复制（state macn 6 q E } 3 & n Ahine replication）。
因为数据库的写入和读取操作都是通过消息交互达成一致，依据Lamport时间戳，所有的操作是全序b P , j :的，因此可以实现线性一致性存储。
Raft协议
Raft是X @ V D一种共识算法，旨在使其易于理解。它在容错和性能上与Paxos等效。不同之处在于它被分解为相对独立的子问题，并且干净地解决了实际系统所需的所有主要部分，实际将上面的全序广播/状态机复制的工程化。

Raft协0 j 3 % 3 5 t /议动8 . A W ^ i画演示：thesecretlivesofdata.com/raft/
在Raft集群里，服务器可能会是这三种身份其中一个：领导（leader）、追随者（follower），或是候选人（candidate）b f M R 7。在正常情况下只会有一个领导，其他都是追随者。而领导会负责所有外部的请求/ S V，如果不是领导的机器收到时，请求会被导到领袖。
Raft将问题拆成数个子问题分开解决：
领导选举（Leader Election）
日志复制（Log Replication）
集群成员C 1变化（Cluster memb8 l Qership changes）
安全性（Safety）

作者：Vd 9 - XectorJin
原文链接：https://juejin.im/post/5e5e4819f265da57337d0c38

苹果隐形创始人，乔布斯职场导师：自建豪宅，种植农场，一生逍遥