参考：
《数据库系统内幕》
《数据密集型应用系统》及DDIA 逐章精读
分布式系统的8个谬误
下图来自戌米的论文笔记，本文就以下图所示脉络组织

CAP

CAP：一致性，可用性，分区容错性

• 一致性（Consistency）指的是在分布式系统中进行数据更新操作后，系统能够保证所有节点的数据是一致的。换句话说，系统的所有副本在任何时间点都具有相同的值。
• 可用性（Availability）指的是在分布式系统中，系统能够随时处理客户端的请求并返回响应。即使在某些节点或组件出现故障的情况下，系统也应该能够继续提供服务。
• 分区容错性（Partition Tolerance）指的是分布式系统节点之间进行通信时，即使出现网络分区（节点之间无法通信或通信延迟很高）的情况下，仍然能够保持数据的一致性和可用性

P分区是一定存在的，在允许分区存在的情况下，无法同时保证可用性和一致性，所以存在两种权衡：

• CP：倾向拒绝请求，而不是提供可能不一致的数据（不可用，但保证一致），如共识算法
• AP：允许提供不一致的数据（为了保证可用，违反一致），如只要有一个副本存活，就能提供读写

故障

故障分为如下几类：

• 程序本身的问题：进程崩溃
• 时钟：计算机通常支持两类时钟：日历时钟（挂钟时间）和单调时钟，前者常用于时间点需求，后者常用于计算时间间隔。日历时钟常常使用 NTP（网络时间协议）进行同步。单调时钟主用于取两个时间点的差值来测量时间间隔，如服务器的超时间隔和响应时间。在计算机系统中，其本身的硬件时钟以及用于校准的 NTP 服务都不是完全可靠的：日历时钟可能有时候会回跳。不同节点的时钟可能相差巨大
• 网络：消息传输缓慢或丢失
• 拜占庭故障

故障检测方法：心跳和ping。ping是自己向别的远程进程发送消息，根据在规定时间段是否得到消息（是否超时）来判断对方是否正常。心跳是自己向别的远程进程发送消息，告诉别人自己仍然正常

分片

分片Partition：解决数据量与单机容量不匹配的问题，分片之后可以利用多机容量
复本Replication：系统机器一多，单机故障概率便增大，为了防止数据丢失以及服务高可用，需要做多副本

分片基本要求：
保证每个分片的数据量尽量均匀，否则会有数据偏斜，形成数据热点。
分片后，需要保存路由信息，给一个KV条目，能知道去哪个机器上去查

如何保存数据条目路由信息（包括数据条目到逻辑分区的映射，逻辑分区到物理机器的映射）：

• 每个节点都有全局路由表
• 由一个专门的路由层记录，路由层依据分区路由信息，将请求转发给相关节点
• 让客户端感知分区到节点的映射。
  如何让节点本身、路由层、客户端及时感知分区到节点的映射变化：
• 依赖外部协调组件
• 使用内部元数据服务器
• 使用某种协议点对点同步（如gossip）

分片（分区）方法

• 按键范围分区：
  • 优点：快速范围查询
  • 缺点：数据分布不均匀，容易造成热点，需要动态调整规划
• 按哈希值分区：
  • 优点：分配均匀，不需要动态调整
  • 缺点：范围查询不友好
  • 一致性哈希：考虑逻辑分片和物理拓扑，将数据和物理节点按同样的哈希函数进行哈希，来决定如何将哈希分到不同机器上。
    • 优点：它可以避免在内存中维护逻辑分片到物理节点的映射。在某些物理节点宕机后，不需要调整该映射并手动进行数据迁移

在数据层，可以通过哈希将数据均匀分布，使得对数据的请求均摊。但在应用层，不同数据条目的负载本就有倾斜。那么仅在数据层哈希，就不能起到消除热点的作用。
如在社交网络中的大V，其发布的信息，天然会引起同一个键（假设键是用户id）大量数据的写入，因为可能会有针对该用户信息的大量评论和互动。
此时，就只能在应用层进行热点消除，如可以用拼接主键，对这些大V用户主键进行“分身”，即在用户主键开始或者结尾添加一个随机数，两个十进制后缀就可以增加100种拆分可能。但这需要应用层做额外的工作，请求时需要进行拆分，返回时需要进行合并。

次级索引
次级索引，即主键以外的列的索引；由于分区都是基于主键的，在针对有分区的数据建立次级索引时，就会遇到一些困难。在有分区的数据中，常见的建立次级索引的方法有：

• 本地索引，对每个数据分区独立地建立次级索引，即次级索引只针对本分区数据，而不关心其它分区数据
  • 优点：维护方便，在更新数据时，只需要在该分区所在机器同时更新索引即可。
  • 缺点：查询效率相对较低，所有基于索引的查询请求，都要发送到所有分区，并将结果合并
• 全局索引，即每个次级索引条目都是针对全局数据
  • 优点：全局索引能避免索引查询时的分散聚合操作
  • 缺点：维护起来复杂，因为每个数据的插入，可能会影响多个索引分区（基于该数据不同字段可能会有多个二级索引）

均衡策略
分区策略会影响均衡策略。比如动态分区、静态分区，对应的均衡策略就不太一样

• 静态分区，即，逻辑分区阶段的分区数量是固定的，并且最好让分区数量大于机器节点
  • 优点：
    • 应对将来可能的扩容。加入分区数量等于机器数量，则将来增加机器，仅就单个数据集来说，并不能增加其存储容量和吞吐。
    • 调度粒度更细，数据更容易均衡。
    • 应对集群中的异构性。比如集群中某些节点磁盘容量比其他机器大，则可以多分配几个分区到该机器上。
  • 缺点：
    • 分区信息也是有管理成本的：比如元信息开销、均衡调度开销等。
    • 对于数据量会超预期增长的数据集，静态分区策略就会让用户进退两难，已经有很多数据，重新分区代价很大，不重新分区又难以应对数据量的进一步增长。
• 动态分区：动态均衡会按着数据量多少进行动态切合，单个分区尺寸相对保持不变

副本

单主模型：

一个副本称为领导者，其他副本称为跟随者。写入时，主副本将改动写到本地后，将其发送给各个从副本，从副本收变动到后应用到自己状态机。读取时，客户端可以从主副本和从副本中读取；但写入，客户端只能将请求发到主副本

副本的复制内容

• 传语句：语句在不同副本执行可能不一样，如now()，如果使用自增列，如果存在并发事务，可能导致副本不一致
• 传预写日志
• 传逻辑日志：如binlog
• 对于插入行：日志需包含所有列值。
• 对于删除行：日志需要包含待删除行标识，可以是主键，也可以是其他任何可以唯一标识行的信息。
• 对于更新行：日志需要包含待更新行的标志，以及所有列值（至少是要更新的列值）

使用逻辑日志的好处有：

• 方便新旧版本的代码兼容，更好的进行滚动升级。
• 允许不同副本使用不同的存储引擎。
• 允许导出变动做各种变换。

副本复制方式：同步，异步，半同步。异步复制时出现复制滞后问题,解决：分布式事务

宕机处理
从副本宕机：追赶恢复。类似于新增从副本。如果落后的多，可以直接向主副本拉取快照+日志。如果落后的少，可以仅拉取缺失日志
主副本宕机：故障转移。

主副本切换时可能的问题

• 新老主副本数据冲突。新主副本在上位前没有同步完所有日志，旧主副本恢复后，可能会发现和新主副本数据冲突
• 相关外部系统冲突。即新主副本，和使用该副本数据的外部系统冲突
• 新老主副本角色冲突。即新老主副本都以为自己才是主副本，称为脑裂
• 超时阈值选取。如果超时阈值选取的过小，在不稳定的网络环境中可能会造成主副本频繁的切换。如果选取过大，则不能及时进行故障切换，且恢复时间也增长，从而造成服务长时间不可用。

多主模型

多数派写入，多数派读取，以及读时修复。

如何维持多个副本数据的一致性，让其弥补错过的数据：
读时修复，在读取时，同时读取多个副本，选取最新版本的值，如果不一致就发送变更让它一致。
反熵过程，读时修复不可能覆盖所有过期数据，因此需要后台进程，持续进行扫描，寻找陈旧数据，然后更新

读几个副本
如果副本总数为n，写入w个副本才认定写入成功，并且在查询时最少需要读取r个节点。只要满足w+r>n，我们就能读到最新的数据（鸽巢原理）。此时r和w的值称为quorum读写，即保证数据有效所需的最低票数。

但在w+r>n时，有一些情况，也会导致客户端读不到最新数据：
使用宽松的Quorum时（n台机器的范围可以发生变化），w和r可能并没有交集。
对于写入并发，如果处理冲突不当时。比如使用last-win策略，根据本地时间戳挑选时，可能由于时钟偏差造成数据丢失。
对于读写并发，写操作仅在部分节点成功就被读取，此时不能确定应当返回新值还是旧值。
如果写入节点数小于w导致写入失败，但并没有对数据进行回滚时，客户端读取时，仍然会读到旧的数据。
虽然写入时，成功节点数>w，但中间有故障造成了一些副本宕机，导致成功副本数小于w，则在读取时可能会出现问题。
即使都正常工作，也有可能出现一些关于时序的情况。

一致性

分布式一致性与事务隔离级别区别：
事务隔离级别是为了解决并发所引起的竞态条件
分布式一致性是处理由于多副本间延迟和故障所引入的数据同步问题

一致性模型
线性一致性：分布式系统有多个副本，多个副本复制会存在延迟，那么外界看到多个副本的状态是不一致的，导致了一致性问题。线性一致性保证一个系统对外表现的像所有数据只有一个副本。共识算法可以保证线性一致性。
因果一致性：只保证因果相关的操作有序。比如当从数据库读取数据的时候，如果能读到某个时间点的数据，就一定能读到其之前的数据（数据没有被删除的情况下）
最终一致性：允许副本出现分歧，最后协调合并后达到一致。大部分多副本数据库提供最终一致性的保证。

线性一致性和可串行化
线性一致性很容易和可串行化相混淆，因为他们看起来都意味着：可以进行顺序化组织。但他们是不同方面的约束：
可串行化是事务的一种隔离级别。每个事务可能会涉及多个数据对象的读写。可串行化可以保证所有事务好像按某种顺序依次执行。如果某种串行顺序和实际执行顺序不一致也没事，只要是串行执行就行。比如A、B、C三个事务并发执行，真实顺序是A、B、C，但如果对应用层表现为CAB的执行顺序，也可以叫可串行化，但CAB的执行顺序在某个对象上可能不满足线性一致性。
线性一致性是一种针对单个数据对像的读写新鲜度保证。
一个数据库可以同时提供可串行化和线性一致性保证，我们称之为严格可串行化或者单副本可串行化。

如何给操作定序
如果系统中没有唯一的单主节点（比如是多主模型或无主模型，或者系统存在多个分区），则如何为每个操作产生一个序列号。常用的方式有以下几种：

• 每个节点独立地生成不相交的序列集。如系统中有两个节点，一个节点只产生奇数序号，另一个节点只产生偶数序号。但不同节点上处理操作的速率很难完全同步。因此，如果一个节点使用奇数序号，另一个节点时用偶数序号，则两个序号消耗的速率也会不一致。这时即使有两个奇偶性不同的序号，还是难以通过比较大小来确定操作发生的先后顺序。
• 使用时间戳，但物理时间戳会由于多机时钟偏差，而不满足因果一致，出现了发生在之后的操作被分配了一个较小的时间戳
• 每次可以批量产生一组序列号。比如，在请求序列号时，节点A可以一次性声明占用1到1000 的序列号，节点B会一次占用1001到2000的序列号。但有可能发生较早的操作被分配了1001-2000的序列号，而较晚的操作被分配了1-1000的序列号。如此一来，序列号的分配不满足因果一致。
• Lamport时间戳。每个节点有一个唯一的id和一个记录处理过多少个操作的计数器，Lamport时间戳是上述两者组成的二元组：(counter, node ID) 。不同的节点可能会有相同的counter值，但通过引入node ID，可以使所有时间戳都是全局唯一的。
  让 Lamport 时间戳能够满足因果一致性的核心点在于：每个节点和客户端都会让counter追踪当前所看到（包括本机的和通信的）的最大值。当节点看到请求或者回复中携带的 counter值比自己大，就会立即用其值设置本地 counter。比如客户端A在收到节点2的 counter=5的回复后，会使用该值向节点1发送请求。节点1本来的counter值是1，在收到该请求后，会立即前移为5，下一个请求操作到来会将其增加为6。

全序广播或者原子广播
时间戳定序还不够，只有在收集到系统中所有操作之后，才能真正确定所有操作的全序。如果其他节点正在进行某些操作，但你并不知晓，也就自然不能确定最终的事件的全序。确定全局定序何时收敛，通过全序广播。全序广播是一种多个节点间交换消息的协议。它要求系统满足两个安全性质：

• 可靠交付。如果一个节点收到了消息，则系统内所有的相关节点都要收到该消息。
• 全序交付。每个节点接收到消息的顺序一致

一个正确的全序广播算法需要保证上述两条性质在任何情况下都能够满足，包括网络故障和节点宕机。如果网络出现故障时，消息肯定不能送达所有节点。但算法可以进行重试，直到网络最终恢复

全序广播等价于多轮次的共识协议（每个轮次，会使用共识协议对全序广播中的一条消息的全局顺序做出决策）。VSR，Raft和Zab都直接实现了全序广播，Paxos的全序广播版本是Multi-Paxos

分布式事务

现代系统使用共识算法实现分布式事务

两阶段提交
解决提交的问题，但不允许领导者发生故障
准备阶段：领导者询问每个参与者是否可以提交，参与者进行投票
提交终止阶段：如果都赞成，则发送commit通知提交，如果有不赞成，则发送abort终止提交，事务回滚

故障情况：
准备阶段参与者故障：提交失败，最终回滚
提交终止阶段参与者故障：通过领导者保存的日志进行恢复，达到一致后再对外服务
准备阶段领导者发生故障：如果领导者已经收集到投票，但是故障。只有等待新的领导者重新发起投票
提交阶段领导者发生故障：领导者发送commit通知过程中故障，参与者需要通过其他参与者的日志得到决策信息（提交还是中断）

三阶段提交
解决即使领导者发生故障，参与者也可以继续提交
提议阶段：协调者发出提议值并收集投票
准备阶段：协调者将投票结果通知参与者。如果投票通过并且所有参与者都决定要提交，则领导者会发送一条Prepare消息，指示它们准备提交。否则，将发送Abort消息并退出流程。
提交阶段：协调者通知参与者提交事务。

参与者有超时机制，如果超时之前没有收到领导者信息就会终止
如果所有参与者都进入了准备状态，无论谁发生故障都会被提交

共识算法

共识算法三个特点
可以解决网络延迟，网络分区，丢包，重复发送，乱序问题，无法解决拜占庭问题
保证大多数机器正常情况下可用
不依赖外部时间保证日志一致性（但也造成受网络影响大）

复制状态机按需要同步的数据量分类
数据量小：适合使用无leader的共识算法：basic paxos 实现有chubby zookeeper
数据量大，但可以拆分为各不相干的部分（如大规模存储系统）：适合使用有leader的共识算法：raft multi paxos 实现有GFS HDFS
数据量大，数据之间还存在关联：将数据分片给多个状态机（共识算法集群），状态机间通过两阶段提交保证一致性，实现有spanner tidb

paxos

提议者（proposer）从客户端接收值，创建提案，并尝试从接受者收集投票。
接受者（acceptor）投票接受或拒绝提议者提议的值，只要大多数的接受者投票即可接受提案。
学习者（learner）扮演副本的角色，保存被接受提案的结果
每个提案包含一个由客户端提出的值和一个唯一且单调递增的提案编号。这个提案编号之后还会被用于确保操作的全序性。提案编号通常用(id,timestamp)实现。

投票阶段：
提议者请求接受者投票
如果接受者没有回应过编号更高的请求，则投票
如果已经回应过更高的请求，则通知提议者有更高的编号
复制阶段：
提议者如果获得了大多数投票，就将值分发给接受者
如果接受者已经回应过更高的请求，则拒绝，并通知它所知道的最高的编号
然后接受者通知学习者，学习者得到大多数接受者通知后才确定

multi-paxos
paxos每轮复制都要一轮提议，multi-paxos有领导者，跳过提议，直接复制

raft

MIT6.5840 lab2,3记录

拜占庭共识

拜占庭将军问题是两将军问题的泛化
共识算法：PBFT

批处理

web服务如此普遍，以至于我们理所当然的认为系统就应该请求/应答风格。但这并非构建系统的唯一方式，其他方法也各有其应用场景。

• 服务（在线系统）
  服务类型的系统会等待客户端发来的请求或指令。当收到一个请求时，服务会试图尽快的处理它，然后将返回应答。响应时间通常是衡量一个服务性能的最主要指标，且可用性通常很重要（如果客户端不能够触达服务，则用户可能会收到一条报错消息）。
• 批处理系统（离线系统）
  一个批处理系统通常会接受大量数据作为输入，然后在这批数据上跑任务，进而产生一些数据作为输出。任务通常会运行一段时间，因此一般来说没有用户会死等任务结束。相反，批处理任务通常会周期性的执行（例如每天一次）。吞吐量（处理单位数据量所耗费的时间）通常是衡量批处理任务最主要指标。
• 流式系统（近实时系统）
  流式处理介于在线处理和离线处理之间。和批处理系统一样，流式处理系统接受输入，产生一些输出。然而，一个流式任务通常会在事件产生不久后就对其进行处理，所以流式处理系统比同样功能的批处理系统具有更低的延迟。

MapReduce任务的输入和输出都是分布式文件系统上的文件。在Hadoop的MapReduce实现中，该文件系统被称为HDFS（Hadoop Distributed File System），是谷歌文件系统（GFS，Google File System）的一个开源实现
HDFS 由一组运行在每个主机上的守护进程组成，对外暴露网络接口，以使其他的节点可以访问存储于本机的数据文件（机器节点上都有一定数量的磁盘）。一个中心节点会保存文件块和其所在机器的映射（也即文件块的 placement 信息）。因此，HDFS 可以利用所有运行有守护进程的机器上存储空间，在逻辑上对外提供单一且巨大的文件系统抽象