深入理解分布式系统

1.初识

1.特点/优势

①.多进程、不共享操作系统、不共享时钟
②.将多个cpu“拼合”高性能、对于数据密集型的应用可扩展、在移动端时代高可用

2.分布式带来的挑战

①.网络不可靠: 消息丢失、延时(误判某个服务是否下线)、重复、非有序
②.部分失效: 跨机器的原子操作变得困难
③.时钟问题: 每台服务器的本地时间不一致，且网络传输有延时，使得各机器发生事件的顺序不清晰

3.指令速度

4.网络/水流

①.延时: 流速
②.宽带: 水流横截面积
③.吞吐量: 单位时间内流过水的体积

2.模型

1.名词

①.模型:为了简化实际问题会提出一些假设，塑造一个模型
②.两将军: 两个将军需要同时攻打一座城才能攻下，安排信使通讯，信使可能会被劫持，反应的问题是链路不可靠会导致消息丢失，会导致无休止的确认
③.拜占庭：n个军队要同时攻打一座城，有一半以上同时攻打才能攻下，安排信使通讯，n个军队中会存在叛徒，反应的问题是节点不可靠，结论m个叛徒军队，当n>3m时，忠诚将军可以做出一致的决策

2.网络链路模型

①.网络分区: 是指网络故障导致节点被分裂成多个组
②.链路模型
  可靠链路：不会丢失、不会重复、不会无中生有、无顺序性
  公平损失链路：会丢失、有限重复、不会无中生有、无顺序性
  任意链路：会无中生有
③.tcp
  tcp中 a->b a如果没有收到b的确认收到会重发，但是b并不知道a收到了这个条确认
  有可能a在发出消息以后就挂掉了，导致没收到b的确认也不会重发
  所以tcp没有彻底的解决两将军问题，但是算是工程上的一个实用解

3.节点故障模型

①.奔溃-停止
②.崩溃-恢复
③.拜占庭故障

4.按时间划分模型

①.同步：消息的响应会在有限且已知的时间内完成
②.异步：无法知道一条消息什么时候会到达
③.部分同步：大部分时间是同步的，偶尔故障转变成异步的 (大部分企业生成环境假设的模型)

5.幂等操作

①.幂等操作：多次操作产生相同的结果且不会有其他影响，实现方法通常是给消息加上唯一编号

3.数据基础

1.分区

①.垂直分区 适用业务：数据分析更快(对扫描、过滤、聚合等操作支持更好)(字段少IO更快、冷热数据拆分、更好支持不同业务的负载)
  水平分区 适用业务：联机事务处理(减少了表锁的冲突)
        分类：范围分区、哈希分区、一致性哈希
②.范围分区
  优点：简单、适用于关键字范围查找、可以通过简单的增删节点实现负载均衡
  缺点：可能产生数据分布不均(比如某个姓氏人很多)、热点数据(比如今年vs以前的订单访问频率)
③.哈希分区
  优点：数据分布相对均匀，一定程度上避免了热点数据
  缺点：在删除增加节点时会导致很多数据需要重新映射，使得大规模数据移动，在此期间系统无法工作。或者只能已倍数的增删节点
  哈希分区中的哈希函数只是均匀把数据分配到节点中去所以可以只是简单的取余操作和时间复杂度为O(1)的哈希算法是有区别的
④.一致性哈希
  优点：解决了哈希分区增删节点数据大规模移动的缺点
  缺点：在节点较少时会导致数据分布不均、在节点故障时会导致下个节点数据负载过大 (引入虚拟节点可以解决这两个缺点)
⑤.在redis中的通过增加桶来隔离数据和节点
  数据->桶->节点，增删节点只是桶的数据在节点中移动，通过这种方式来避免哈希分区的缺点
  移动落实的时候还是以桶里面的数据为单位，但是避免了所有数据都重新映射
⑥.分区带来的挑战是
  垂直分区会用到jion效率低
  水平分区的多节点范围查找效率低、事务的实现比较困难

2.复制

①.复制的好处：增强数据的可用性和安全性、减少RTT时间(数据部署在不同地理位置)、增加读吞吐

②.单主复制
  优点：简单、更容易支持事务(写都在主库里面)、读操作不会是瓶颈(可以有多个从库分布在不同地区)
  缺点：写操作会是瓶颈、主从人工切换会导致停机，主从自动切换可能会导致脑裂
  分类：同步复制、异步复制、半同步复制(以上分类是在效率和数据的安全性、一致性之间做出选择)

②.多主复制(客户端的写请求可以发到任意一个主节点上)
  优点：提高写的效率、不存在主从切换的问题
  缺点：更容易数据冲突
     避免数据冲突的办法: 通过哈希函数某账号请求都路由到相同节点上/不同节点上部署不同业务
     解决冲突的方法: 由客户端解决冲突: 例如购物车会将所有数据都返回客户端让用户自己解决冲突，对用户的体验受影响
最后写入胜利: 由于时钟问题并不会很好的知道真实的顺序
因果关系跟踪: 追踪哪个操作是基于哪个操作先发生，用向量时钟等方式判断操作之间的依赖顺序，成本高
  多主从的复杂性很高，一般只用于多个数据中心之间，以避免写请求跨越数据中心，数据中心一般部署的地理位置相距很远

③.无主复制(客户端W节点>n/2、W+R>n可以确保读到最新数据)
  优点：读写性能可调
  缺点：读写性能取决于最慢的那一个读写节点、数据冲突更严重
     解决冲突的方法: 读修复: 由客户端在读取时去负责更新数据旧的节点
反熵过程: 把存储的所有key分成若干个区间，每个区间计算hash值作为树的叶子，
相邻hash合并再hash，一层层合并到根，最后根相同时所以数据一致，即Merkle Tree(默克尔树)
在查找不同数据时就是一个二分法，树数据是在定时维护+按需维护

3.CAP

①.定义
  C:一致性(客户端访问所有节点，返回的都是同一份最新的数据)
  A:可用性(每次请求都能获取非错误的响应，并不保证获取的数据是最新的)
  P:分区容错性(在网络分区时，系统仍然提供服务)
  一个系统只能满足这三项中的两项，P一定存在，所以分为CP或AP，即网络分区时在一致性和可用性之间做选择
②.网络延时
  其实网络分区一般不是很常见，但是网络延时却经常发生，在网络延时发生时选择降低一致性级别或降低可用性即效率
  比如客户端的写请求，如果选择保存一致性那么写的效率就会降低即可用性降低，如果保证写的效率那么一致性就会降低

4.一致性模型

1.一致性名词

①.CAP中的C，强调的是用户视角下数据一致性的 体验
②.paxos和raft算法中的一致性，这里有一个更好的名词代替:共识，共识侧重于节点达成共识的 过程和算法
③.数据库ACID中的一致性(应用程序来保证的A+B=100、或指常见的完整性约束例如主键、外键、触发器、check)

2.定义

①.以下涉及客户端和进程是同一个意思，都是并发操作的发起者
②.在并发编程中(单机或分布式)，系统和开发者之间的一种约定，
  如果开发者遵循某些规则，那么开发者执行读操作或写操作的结果是可预测的。
  其本质是定义了写操作的顺序和可见性，即并发写操作执行的顺序是怎样的，写操作的结果何时能够被别的进程看见。
  侧重于研究副本(主从)最终的稳定状态，一般不考虑拜占庭问题

3.分类(系统角度)

①.线性一致性(强一致性):
  非严格定义:在分布式系统中所有的操作看起来都是原子的，整个分布式系统看起来只有一个节点
  严格定义(50页):任意一个操作都是有时间段的
两个客户端的操作有重叠时间段时其先后顺序不确定(由系统任意决定)，没有重叠时间段时其先后顺序确定
每个读的值都必须能通过这个顺序解释为“上一次写入的结果”
举个栗子:两次写有时间重叠，所以读x可以=1也可以=2都是合法的
A: ────|─── 写x=1 ────|─────
B: ──────|─── 写x=2 ────|─────|── 读x=1 ───|───

  实现:
  在单机中: 通过cas(比较-交换)或者原子操作来实现线性一致性
例如多个线程对一个变量进行++操作，每个线程看到的这个变量的值是线性一致的
每个线程都会有自己的L1 L2 寄存器缓存，所以即使是单机的一个变量也会存在多个副本
  在分布式中: 通过共识算法来实现
包括如何选择领导者、如何处理重复请求、如何确保请求在每个副本上的执行顺序是一致的
请求的目的是修改数据，所以最后一个包括的意思是如何确保每个副本修改数据的顺序是一致的

  代价:
  在单机中: 现代cpu在访问内存时并不保证线性一致性，因为同步指令开销大，速度慢。
想保持线性一致性需要通过加锁和原生原子操作，并发的性能会降低
  在分布式中: 存在时钟问题，需要用到共识算法，所以成本高

②.顺序一致性:
  只要求同一个客户端的操作在系统排序后保持先后顺序不变，两个客户端之间的先后顺序可以任意改变
  在现代cpu单线程执行时会优化指令的执行顺序，所以也不保证顺序一致性

③.因果一致性：每个进程必须以相同的顺序看到因果相关的操作，没有因果关系的并发操作可以被不同进程以不同的顺序观察到

④.最终一致性：在最终的状态下，只要不再执行写操作，读操作将返回相同的、最新的结果

4.分类(客户端角度)

①.单调读：客户端一直读，读到的数据只会更新
②.单调写：同一个客户端的写操作在所有副本上都已相同的顺序执行，即保证客户端的写操作是串行的
③.读你所写: 当写完成后，在同一个副本或者其他副本上读操作必须能够读到写入的值，读写是同一个客户端时保证
x=1，A客户端写x=2，AB同时读任一副本，A读到的一定是x=2，但是B可能读到x=1
④.读后写：写操作要基于之前读到的值或者比之前读到的值更新的值
⑤.PRAM：单调读+单调写+读你所写 (todo:这里的定义和下面会有冲突 先暂时按这个理解吧)
即同一个客户端的多个写操作，将被所有副本按照同样的执行顺序观察到，但不同客户端的写操作顺序可以以不同的执行顺序被观察到

5.隔离级别

①.脏写/脏读/不可重复读/幻读 见conn.1.3(隔离级别)
②.更新丢失: 是指两个事务的读写操作非原子操作

③.读偏移: 是指读到了一致性约束被破坏的数据

③.写偏移: 是指两个事务读写操作破坏了数据的一致性约束

4.共识算法

1.特性

①.终止性：所有正确的进程最终都会认同某一个值
②.协定性：所有正确的进程认同的值都是同一个值
③.完整性(也叫有效性)：最后被认同的值必定是某个节点提出来的，而不是凭空出现的值

2.目的/实现过程/解决问题

①.目的：在网络不可靠、时钟不一致、节点故障的环境下达成共识
①.复制状态机: 所有节点都维护一份完全相同的初始状态机副本，所有节点以相同顺序处理客户端请求，最终每个副本的状态也一致
②.实现过程：共识算法(Raft)->多副本日志系统->复制状态机->↓解决了以下问题->使得分布式具备高可用性、自动容错、高性能
③.解决了的问题：分布式锁、选主、原子提交等问题

3.FLP

①.名称(在这里汇个总)

②.定义
  在异步网络(见2.4)中，不可能存在能够容忍节点故障的共识算法，哪怕只有一个节点故障
  这里很好理解就是投票的时候，比票为n/2比n/2，只有最后一票能做决定，要么选择牺牲安全性做出一个不一定正确的结论，要么等节点恢复就牺牲了活性，即三个不能同时满足
  也就是CAP不能同时满足，只能是CP或者AP

③.FLP的工程解:
  故障屏蔽: 让节点是故障-恢复的模型，就能变异步为同步
  故障检测器: 检测节点有没有发生故障，故障检测器必须拥有的两个属性
完全性: 每个故障的进程都会被每个正确的进程怀疑
精确性: 正确的进程不会被别的进程怀疑
  不完美的故障检测器: 只要通信可靠(消息最终不会丢失)，失效的进程不超过n/2，那么依然可以用来解决共识问题
最终弱完全性: 每个故障的进程最终都会被一些正确的进程检测到
最终弱精确性: 经过段时间后，一个正确的进程不会被其他正确的进程怀疑
  使用随机算法: 解决拜占庭问题，增加进程故障的成本

4.Paxos

①.节点分类
  客户端：向分布式系统发送请求，并等待响应，(在分布式批准提案的时候会响应客户端)
  提议者：接受客户端的请求，提出相关提案，试图让接收者接受该提案，并在冲突时进行协调，推动算法进行
  接收者：对提议者的提案进行投票，超半数接收者接受提案，则提案被批准
  学习者：不参与投票，只能学习被批准的提案
②.RPC
  第一阶段(perpare)：提议者争取本轮提案的所有权，获取上一轮可能已达成的共识提案
  a.提议者在收到客户端的请求后，选择一个最新的提案编号n(n为本地自增)，向超半数的接收者广播perpare消息，请求接收者对提案编号进行投票
  b.接受者收到perpare消息以后如果n为它所见到的最大提案编号则响应否则不响应或者拒绝，如果之前有接受其他提议者的提案则需要放回对于的提案编号和提案值

  第二阶段(accept)：决定提案是否通过
  a.提议者在收到超半数接收者的promise响应后，
  提议者向超半数的接收者发起accept请求，需要带上提案编号n和提案值，提案值需要在promise响应中选则，
  如果没有可以自由决定提案值
  b.接收者如果在收到accept没有收到比n更大的提案编号则响应接受该提案否则不响应或者拒绝

  超半数的接收者accept提案以后响应客户端请求，学习者学习该提案

③.活锁：两个提议者一直发起perpare消息争取一轮提案的所有权，导致该轮提案第二阶段一直不被通过

④.疑问
  paxos通过本地n自增解决了时钟问题，但是网络不可靠、节点故障、异步？
  为什么accept请求是发给超半数？不会导致没有接受到accept的节点有旧数据需要修复么？
  提案是如何进行到下一轮提案的，下一个提案会不会返回了上轮提案的提案值？
  少个实际案例

5.Raft

1.关注点

(1).领导者选举
(2).算法正常运行，如何实现日志复制
(3).领导者变更时的安全性和一致性，算法中最棘手和最关键的部分，描述新选举出来的领导者要做的日志清理工作
(4).处理旧领导者，万一旧的领导者并没有真的下线怎么办？该如何处理系统中存在两个领导者的情况？
(5).客户端交互，集群如何与客户端交互？
(6).配置变更，如何在集群中增加或删除节点？以及讨论一个在Raft论文中没有提及的配置变更Bug
(7).日志压缩，为了减少磁盘存储空间，同时让新节点快速跟上系统状态， Raft算法还会压缩日志生成快照。
(8).实现线性一致性，如何通过Raft算法实现线性一致性读？
(9).性能优化，一些性能优化的技巧。

2.术语

①.节点分类
  领导者(Leader)：负责处理所有cli的请求和日志复制，同一时刻集群内只有一个领导者
  跟随者(Follower)：不主动发送RPC请求，只是响应收到的RPC请求
  候选者(Canclidate)：在选举时参选节点的状态

②.状态机
  Leader每隔一段时间向其他节点发送AppendEntries消息作为心跳，以维持自己的Leader身份
  Follower在一段时间都没有收到心跳，就会转换为候选者，发起投票，获票超半数成为leader(>1/2所以每次选举只会出现一个leader，维持了选举的安全性)

③.任期(Term)
  Raft将分布式系统中的时间划分成一个个不同的任期来解决之前提到的时序问题
  每一个节点都需要持久化存储currentTerm变量(当前节点知道的最新任期号)
  同时节点也持久化存储votedFor变量(当前任期，投票给了哪一个候选者)，防止宕机->恢复，投票给另外一个候选者

④.RPC
  Raft中服务器之间的通信主要通过两个RPC调用实现
  RequestVote(领导者选举)
  AppendEntries(领导者用来复制日志和发送心跳)

3.领导者选举

①.网络分区+currentTerm飙高
  q1:如图4-29如果一个节点A离线了，他会一直选举导致本地的currentTerm飙高，这个时候网络恢复了
    A节点带着他虚高的currentTerm竞选，会导致其他节点投票给A么
  答:currentTerm虽然很高，但是节点A落地日志的最高任期却很低(没有当选不处理cli请求)
   如图4-33，假设节点S4离线，落地日志的最高任期(即最后落地日志的任期)是1

②.等价于paxos活锁
  安全性:一个任期一定只有一个Leader 活性:系统最终一定能选举出一个Leader
  q2:系统是如何解决活锁问题的 活锁:在选举的时候多个选举者参与竞选导致票被瓜分导致没有一个达到1/2的票数，如此反复
  答:系统给节点设置随机选举超时时间[1T,2T]。这样在下一轮同时参与选举的概率就降低了，
   先参与第二轮选举的候选者有足够多的时间获取到足够的选票，T远远大于网络传播时间，效果越佳

4.日志复制

①.特性
  Raft算法没有被提交的日志index+任期号构成日志的唯一索引
  Raft已经被提交的日志index就是唯一索引，即index相同时任期一定相同
  (一个任期只有一个leader，所以已提交的日志在index相同时，一定是同一个leader复制的，即日志一定相同)
  如果给定的日志记录已提交，那么前面所有的记录也已提交

②.实现方式
  Raft和Paxos不同之处，Paxos允许日志不连续地提交，Raft日志必须连续地提交不允许出现日志空洞
  日志追加，如果领导者收到超过半数节点的追加响应，则认为新的日志记录可以被commit，然后向客户端返回写响应
  AppendEntries消息在给跟随者追加日志时，会带上Leader前面一个日志的index&任期，跟随者只有在前一个日志和本地的前一个日志index和任期都相同时才会追加日志

5.领导者更替

①.在领导者更替的时候日志复制会变得非常乱，有可能领导者在没有同步完上任后的第一条日志就宕机了，又开始了新的一轮选举，如此继续
  上图的leader转换 s5(2/3)->s4(4)->s3(5)->s1(6)->s2(7)
②.未提交的日志可以被丢弃(这里指的是跟随者未提交的日志会被新leader的日志覆盖，新leader不会把未提交的日志清理，而是继续推进)
③.清理不一致的日志：领导者根据不同跟随者的日志一条一条往上翻找到相同的以后然后覆盖或者补全
④.被commit的日志会有一半以上的节点中落地，所以新的领导者一定包含commit的日志，不然有一半以上有全commit日志的节点不会投票给该节点
⑤.所以新的领导者所拥有的日志不是最新的而是足够新的
⑥.旧的leader如果想commit日志，至少需要向1台新leader的追随者发起日志复制，复制请求会被新leader的追随者拒绝，并且告诉旧leader现在最新的任期号，旧leader转换成新leader的追随者
⑦.客户端给每个请求加上唯一id，避免一个请求被新旧领导执行两次(旧leader执行完且commit但没有回包给cli后宕机，cli会再次发出同样的请求)

6.延时提交

①.图4-35是正常情况
②.图4-36描述的是
  S1当选任期2的leader，复制把日志index3复制到S2的时候宕机了
  S5当选任期3的leader，S5创建了日志(index345/任期3)但是没有开始复制就宕机了
  S1当选任期4的leader，这个时候S1复制的是(index3/任期2)的日志到S3，(index4/任期4)日志还没有开始复制
  即使这个日志(index3/任期2)被多数节点落地，这个日志也并不能被commit，因为有可能commit以后S1宕机
  S5可能成为任期5的leader(因为他落地日志的最高任期是3，他可以获取S2/S3/S4的选票)
  这个时候(任期2/index3)在S1/S2/S3的日志会被S5的(任期3/index3)的日志覆盖，导致已经被commit的日志被修改
③.延时提交解决，领导者必须看到超过半数的节点响应了至少一条自己任期内的日志才能进行commit
④.延时提交会把日志commit的驱动交到了cli手中，使得满足commit条件的日志无法被回复给cli，便不满足线性一致性
  超过半数节点把日志落地了该cli的请求就成功了，但是没有被commit(非当期任期日志，不满足延时提交的约束)，
  这个时候cli读不能获取到最新的数据(与强一致性不符)(这个时候leader迫切的需要知道这条日志能不能被commit)
  Raft通过引入no-op的空日志解决这一问题

7.实现线性一致性

①.问题描述
  旧的leader在收到cli的读req时，认为自己还有权威，会返回旧的数据给cli (与强一致性不相符)
  为了提高leader的写效益，把读req交给cli处理，也会返回旧的数据给cli
②.解决1.把读req当作写req来处理，每次读写一个空日志
③.解决2.Raft算法的readIndex变量
 1.leader在任期开始时会提交一个no-op的空日志，在no-op被提交时，leader的commitIndex就是整个系统的日志提交index
 2.赋值readIndex=commitIndex
 3.leader在收到cli的req请求时，会向所有Follower发生心跳，确认自己还是leader
 4.leader等待日志中的命令应用到状态机(日志有两个使命，同步/改变数据)，只是应用到readIndex
 5.leader执行cli的读req，将结果返回给cli
④.解决2相对于解决1节约了写日志的开销
⑤.把读交给Follower来处理，leader执行123步，Follower知道最新的readIndex后执行45步

8.配置变更

①.配置: 描述系统里面有多少个节点在运行
②.问题描述: 如图4-43，颜色的变化是新旧配置交替的时候，在虚线框内选举，有可能在新旧配置节点里面分别出现一个leader
③.解决方案: 加一个C(old+new)的日志提交，这个日志commit以后，应用于状态机后的节点会维护新旧两个配置数据，
在交替的阶段选举需要新旧配置节点都达到n/2票以上，才会当选leader
④.衍生问题: 在C(new)配置生效以后，如果不在new配置节点没有退出，
这个节点不会收到leader的心跳，他会带着更高的任期去参与选举，
虽然他不会当选(因为落地日志的index小所以不会获得选票)，
但是他会使得现任leader退位使得整体系统的可用性降低
⑤.衍生解决: 新增一个Pre-Vote阶段，使得系统不会扰乱一个活跃的领导者
如果超过半数的节点同意Pre-Vote请求，则发起请求的节点才能真正发起新的选举
如果一个节点在选举超时时间内收到领导者的心跳，那么它将不会同Pre-Vote请求
Pre-Vote不仅解决了这个问题，还解决了4.5.3.①网络分区+currentTerm飙高的问题
⑥.单个节点同意Pre-Vote请求的条件
  最后落地日志的任期更大，或者任期相同但日志索引更大
  至少一次选举超时时间内没有收到领导者心跳
⑦.Pre-Vote导致系统能容忍的故障节点的数量减少

  4是leader 5是故障节点 4只能和2通信 123能相互通信
  这个时候4推进不了日志的commit(只有24两票)，
  13没收到4心跳发起选举也不会成功(只有13两票，2收到了4的心跳不会投票)
  原本能容忍2个节点故障的系统只能容忍1个节点故障
  解决方案: 领导者没有收到超过半数节点的心跳响应时就主动下台，123发起选举都能当选

9.日志压缩

①.定义: 只保留变量的最后状态，初始状态和演化过程的日志都被舍弃
②.不将压缩任务集中在领导者身上，每个节点独立的压缩其已提交的日志
③.不会压缩所有的日志，至少会留下一条日志，用于复制时告诉leader这条日志及之前的日志都已经同步，从下一条日志开始复制就ok了
④.如果服务器重启了或者日志远落后于领导者，领导者将最新的快照加载到状态机然后再接受日志

10.内存快照

①.状态机的数据集小于10GB时选择基于内存的状态机是合理的 (状态机:数据的集合)
②.安全的快照: 序列化将花费很长的时间，所以fork子进程(写时复制)来进行快照
系列化: 让数据离开内存在别的地方活下去，例如磁盘或者网络
包括: 把数据转换成线性的字节流(内存里面会有指针)/类型转换/编码/压缩
③.何时快照: 如果日志超过之前快照大小的好几倍，那么就需要生成快照
轮流快照，避免有一半的节点在快照影响整体系统的性能，领导者先下台在进行快照
⑤.避免反序列化加载到未完成的快照，快照先存入临时文件然后原子操作的重命名
⑥.让跟随者去生成快照领导者在获取，只是对已经commit的数据进行压缩，所以是安全的，并不会影响领导者的权威

11.磁盘快照

①.对于每一个日志，当其被提交并应用到状态机之后，就可以被丢弃了
  因为磁盘已经持久化存储了，可以理解为每条日志生成了一个快照
  每应用一条命令都需要进行一次或多次随机磁盘写入，这会限制系统的整体吞吐量，所以性能是讨论的要点

②.LSM Tree(Log-Structured Merge Tree) todo:以下是暂时从GPT得到的理解
  这里的tree和二叉树中的树不是同一个意思，而是Merge Tree指的是一种多层合并结构
  MemTable:最新写入的数据(内存)
  WAL:写入数据的日志，用于在宕机以后恢复MemTable类似于redis AOF日志
  L0:在MemTable满了以后，数据被落地到L0(L1会有多个L0，在读的时候依旧是先新后旧)
  L1:在L0的空间满了会触发compaction(去重&合并)到L1
  L2:同上，L2的空间是L1的10倍(可调)
  L3:同上
  …

  L层数据结构包含:索引块/Bloom过滤/SSTable数据(按key排序的文件块 类似于k1,v1,k2,v2,k3,v3… 因为是排序了的所以compaction的效率也很高)
  写:顺序写很快
  读:依次从MemTable L0 L1 L2…找数据，越后面的数据越久远，Bloom过滤可以快速判断数据是不是在这一层

12.性能优化

①.批处理和流水线
  Leader将日志写磁盘和把日志发送给Follower并行
  批量处理cli的请求，多个日志打包一起发给Follower，多个日志一起调用fsync写磁盘
②.目击者节点
  不存储数据，只参与选举，在有节点故障的时候开始存储日志
③.Quorum大小优化
  Q1:给Leader投票的节点数，Q2:复制日志成功的节点数
  Q1+Q2>N就可以，不需要Q2>N/2，比如5个节点可以设置Q1=4 Q2只需要>=2就可以commit了
④.MultiRaft
  解决Follower节点较多的时候心跳给主节点带了的性能问题 (todo:)

5.分布式事务

1.原子提交

①.原子提交协议必须满足的2个特性
  协定性:所有节点要么一起提交事务，要么一起中止事务
  终止性:强终止条件(非阻塞提交算法):无论是否有节点故障，系统中的所有非故障进程最终都能做出决定(3PC)
弱终止条件(阻塞提交算法):只保证在没有故障的情况下，参与者能最终做出决定(2PC)

②.二阶段提交(2PC 图5-1)
  第一次通信: 协调节点发送准备消息，所有参与节点处理事务的所有步骤除了commit，
包括权限验证、上锁、执行事务、记录操作日志。最后是否成功给协调者发信息
  第二次通信: 如果第一次通信所有参与者节点都回的是，则通知参与者commit，等待回包结束事务
如果第一次通信有一个参与者节点回的否，则通知参与者回退，等待回包结束事务

  可能出现的问题: 协调者和参与者在任意一个时刻都可能宕机，导致阻塞、数据不一致 (所以很多分布式系统选择不实现分布式事务)
  1.参与者在收到准备消息后宕机(图5-1 ①位置)，协调者可以加个超时，超时就当作参与者发的否来处理
  2.协调者在发送准备消息后宕机(图5-1 ②位置)，这个时候所有参与者就需要等协调者恢复以后才能知道事务是提交还是回滚了，所以是二阶段提交是阻塞的协议
  3.协调者在发送提交消息给部分参与者以后发生了网络分区(图5-1 ③位置)，导致只有部分节点提交了事务，会导致整个系统的数据不一致
  这个时候没有commit的节点的数据也是在加锁状态，并不会导致数据不一致，还是导致阻塞
  4.协调者在发送提交消息给一个参与者以后宕机(图5-1 ③位置)，收到消息的参与者也跟着宕机(图5-1 ③位置)，而后面新的协调者不知道这个事务是需要提交还是回退

③.三阶段提交(3PC 图5-2)
  与二阶段提交相比三阶段提交多了第一次通信的询问，可以避免一些后续的阻塞和无效的操作
  参与者也引入了超时机制，会单方面的中止事务，对应上面的问题3 (所以三阶段是通过牺牲正确性换来的非阻塞)

④.Paxos提交算法
  将是否提交事务，当作一个共识问题去处理

⑤.基于Quorum的提交协议(可以解决三阶段的正确性的问题)
  在三阶段的预提交消息中，如果发生了网络分区，发起新的协调者竞选(在这里可以选出多个新协调者)
  如果有Vc个节点向其中一个新协调者提交了提交票，则事务提交 (总共V个节点)
  如果有Va个节点向其中一个新协调者提交了中止票，则事务中止 (总共V个节点)
  因为有限制Vc+Va>V (Vc Va可调)，所以即使是网络分区一只会产生一个结果，在网络分区恢复的时候会执行合并协议
  如果网络分区足够的严重，还是会导致Vc Va的票数都达不到，还是会阻塞

⑥.Saga事务
  事务中的操作往往会占用一些系统资源，如上锁等，事务的持续时间越长，对系统的整体吞吐量的影响就越大
  有些业务的事务会持续几个小时或者几天，例如保险的理赔，中间还有人工输入数据
  Saga事务把事务拆解成T1 T2 T3… Tn个事务可以和其他的事务交替的执行(T1-Tn要么全部执行要么全部没有执行)，每个事务Tx都有一个Cx事务对于回滚，Cx由业务程序实现
  Saga事务无法保证隔离性

2.并发控制

①.分布式事务还需要实现隔离性，隔离性(即并发控制)就是要在保证数据正确性的基础上提供尽可能高的性能
  悲观: 如果一个事务持有了数据的锁，那么另一个事务必须等待前一个事务结束并释放锁，才能获取锁并使用数据，串行化的隔离级别
  乐观: 只管执行读写操作。在事务提交的时候，再检查是不是有其他并发事务引起了冲突，如果有则回退
  MVCC: 保存每个数据项的多个版本，并保证每个事务的读操作读取到的数据版本是比该事务开始时间早的最后一个提交的版本

②.二阶段锁
  将一个事务分为扩张阶段，事务不断上锁，但不允许释放任何锁；收缩阶段，事务陆续释放锁，但没有新的加锁动作
  解决死锁的方式，在分布式中主要方法是 过一段时间再来抢占锁 和 判断能否抢到所有锁 conn.3.2.④ conn.4.6.③

③.乐观并发控制: 认为事务之间的冲突并不会很多
  基于检查的并发控制: 和单机的cas相似，分了3个阶段
读取:该阶段将事务涉及的数据复制一份副本放在私有空间，之后事务的读写都是在操作私有空间
校验:当事务准备提交时，先检查在此期间事务是否与其他事务产生冲突，有冲突则回退
写入:如果校验阶段成功提交事务，那么该阶段将私有工作空间中的数据永久地写到数据库
  基于时间戳的并发控制: 在事务读写数据前，会先判断数据最近一次的读写时间，决定事务是回退还是继续
TS(Ti):事务Ti的开始时间戳
W-TS(X):数据项X最近一次被写入的时间戳，使用锁或者cas维护
R-TS(X):数据项X最近一次被读取的时间戳，使用锁或者cas维护
读X:先判断TS(Ti) < W-TS(X)是否成立，如果成立，说明从事务Ti开始到现在有其他事务写入了X数据，事务Ti需要中止
即在TS(Ti)这个时刻读取到了未来版本W-TS(X)的数据
写X:先判断TS(Ti) < W-TS(X) || TS(Ti) < R-TS(X)是否成立，如果成立，说明从事务Ti开始到现在有其他的事务读取或者写入了X数据，事务Ti需要中止
脏读的案例:T2开始 T2写x=9 T1开始 T1读x T1写x=x+1 T1提交 T2回退 没有违反时间戳的并发控制，但是T1写x=x+1是基于一个不存在的值操作的
解决方案:出现这个问题的原因是事务没有隔离性，把写操作先放在私有空间，这里好像就是退化成基于检查并发控制了

④.MVCC: 用空间换取读效率，需要额外的数据来支撑多版本控制
  Tid: 事务T开始时，系统会给该事务分配一个唯一单调递增的时间戳作为标识，称为事务开始时间戳(逻辑时间戳)
  txn-id: 持有当前数据项最新版本写锁的事务的开始时间戳Tid，如果没有事务持有则为0，使用cas更新该字段
  begin-ts: 创建该版本数据项的事务提交时的时间戳，提交时间戳用Tcommit表示
  end-ts: 该数据项下一个版本的begin-ts 即[begin-ts,end-ts)为该数据这个版本的生存周期。如果是最新数据则end-ts为INF无穷大

⑤.MVCC: 不同版本悲观/乐观并发控制 其中乐观版本不在维护变量的副本(也同样是维护数据的版本)
  read-cnt: 占用当前数据项某个版本读锁事务的数量 (MVCC二阶段锁)
  read-ts: 该字段记录最近一次读取该数据项的事务的Tid (MVCC基于时间戳并发控制)

  读: 找到begin-ts<=Tid<end-ts的数据版本Xv，判断数据的写锁有没有被其他事务占用txn-id(Xv)==0||txn-id(Xv)==Tid，满足条件则返回数据，不满足则abort
  写: 找到最新版本的数据，判断没有其他事务在读写该数据txn-id(Xv)==0&&read-cnt(Xv)==0，
   占用写锁txn-id(Xv)，创建新版本的数据Xv+1，占用写锁txn-id(Xv+1)，维护Xv和Xv+1的生命周期数据，commit，释放锁

⑥.MVCC: 存储方式

⑦.MVCC: 垃圾回收
  元组级别垃圾回收:只要某个数据版本的end-ts小于所有活跃事务的start-ts，说明它不再对任何事务可见，可以安全删除
  当一个事务结束后，系统可以判断它所涉及的读写版本是否对其他事务再无用，直接清理这些版本，需要事务维护一个数据的读写集，实现复杂