分布式存储底座包括分布式文件系统和分布式一致性KV存储。对外满足的条件 1. 提供数据可靠性，底座之上不需要担心数据损坏 2. 提供数据可用性，节点崩溃不影响数据读写 3. 集群级接口，多机节点可访问

HDFS 分布式文件系统

Hadoop Distributed File System 分布式文件系统

由中心化节点namenode和多个datanode节点组成。namenode 维护文件目录结构，负责文件创建、打开、关闭、重命名等操作，不支持软链接/硬链接。namenode维护了文件信息，datanode只有块信息不感知文件，块大小默认是128MB。

对于文件系统的修改，例如创建打开文件，namenode会持久化到Editlog。为加快重启后恢复，Editlog使用checkpoint，同时secondNamenode会尽量接近namenode，以便namenode崩溃重新选主后恢复。

namenode借助zookeeper保证可用性，zookeeper同时记录服务信息，例如正在运行的namenode和可用的datanode地址。

client 使用FileStream抽象访问文件，FileStream自动和namenode/datanode交互。例如执行读操作时，FileStream自动从namenode获得文件包含的块和datanode信息，然后访问指定的datanode读对应的块。执行写操作时，FileStream从namenode拿到可写的块，然后向指定的datanode发写请求。如果使用三副本容错机制，写操作需要同时拿到三个位于不同datanode的可写的块，然后写三份等待返回。

三副本写有以下写策略

  1. 客户端向三个datanode发三个写请求，等待三个写成功返回
  2. 客户端向三个datanode发三个写请求，两个返回就可认为成功，最后一个请求可以后台慢慢追赶写。也就是二三异步写。这种延迟最低。
  3. 客户端链式发请求，即先写第一个副本，成功后写第二个，再成功后写第三个

为了保证数据完整性，数据在磁盘中存放和io链路都要进行crc校验。

hdfs的缺陷

hdfs的主要问题是元数据不可扩展

  1. 单点namenode，元数据无法横向扩展。读需要找namenode拿数据块的layout，写需要找namenode拿可写的数据库，单namenode无法支持高iops的读写和元数据
  2. 由于分布式系统存在飞着的请求，加上重试，可能导致数据安全风险。例如某客户端写完两副本，第三个副本挂了；该客户端重新申请个新的第三个副本，此时挂了的副本好了，飞着的请求被处理，导致写了两次第三个副本。

问题1, 可以使用通过子树划分的分布式元数据解决，分布式文件系统一般不实现link文件，对于rename操作，分布式元数据情况下需要保证多节点原子性。可以将rename操作统一打到一个节点，该节点单线程执行任务实现原子性，rename操作一般延迟较其他元数据操作差。

问题2, 可以使用seal 机制处理，seal后的chunk不可写。当chunk数据写完需要切chunk，或某chunk写失败需要换chunk写，原来的chunk会seal掉，seal的chunk只读不写，可以保证问题2 飞着的请求在seal 的chunk无法写操作。

Windows Azure Storage 这篇论文介绍的是更现代的分布式文件系统，主要有以下特点

  1. 服务分成Front-End (FE)、Partition、Stream三个部分。Front-End服务协议层接受请求，转发到指定的Partiton；Partiton存储逻辑数据；Stream真正存储数据，分成extent和block两层，extent大小1GB，block大小4M
  2. partition层提供的是支持事务的数据库表/对象/文件存储。partition由若干object组成，object是固定大小存储单位，partition内部object的操作是原子的，提供事务操作（即多个object操作提供原子性）。partition记录用户文件和stream存储位置的映射（Blob表）、文件属性表和目录表(entity表)，并且保证相同partition内的表支持事务操作。（分布式文件系统元数据主要有两种，一种维护layout布局信息，另一种维护文件目录信息，这两种元数据可以隔离防止干扰？）
  3. partition层有一个partition manager(master)，维护partition和节点ip信息，master由Paxos Lock保证一致性（分布式文件系统中处理元数据，还应该有一个元元数据角色，保存系统自己的配置和元信息，元元数据实现paxos协议保证可靠性）
  4. partition层的数据表是KV存储，类似LSM tree结构。partition按照key的range划分（相比一致性hash分片，Range Partitions更简单，能充分利用局部性）支持分裂。（需要考虑到分裂后的两个partition之间不提供事务和原子性保证了）
  5. stream层才是分布式文件系统层，它提供文件语义操作。stream层分为extent(1GB)和block(4MB)两层。stream只支持append-only写，且extent支持seal。seal后的extent只读。stream层有实现paxos协议的Stream Manager(master) 维护了文件系统namespace，block等布局信息（stream master应该能支持按子树划分，实现分布式元数据）

append-only系统

Append-only System – Having an append-only system and sealing an extent upon failure have greatly simplified the replication protocol and handling of failure scenarios. In this model, the data is never overwritten once committed to a replica, and, upon failures, the extent is immediately sealed. This model allows the consistency to be enforced across all the replicas via their commit lengths

An append-based system comes with certain costs. An efficient and scalable garbage collection (GC) system is crucial to keep the
space overhead low, and GC comes at a cost of extra I/O. In addition, the data layout on disk may not be the same as the virtual address space of the data abstraction stored, which led us to implement prefetching logic for streaming large data sets back
to the client.

append-only系统清理碎片：新建文件，将旧文件的非垃圾数据写到新文件，删除旧文件（旧文件除了最后一个chunk, 前面的chunk是seal的，GC时不用担心新增数据）

zookeeper 和zab 一致性KV协议

zookeeper依赖ZAB（Zookeeper Atomic Broadcast）协议实现分布式数据一致性。zab协议通过两阶段提交和多数通过两个原则保证即使leader挂了，系统仍可具备数据可靠性和强一致性。zab选择了强一致性，牺牲了可用性，即leader选举过程中，zookeeper不可用。zab协议下，集群的节点有两种角色：leader和follower。

两阶段提交，leader将写请求广播到follower，写请求会携带一个自增的zxid，follower 接收到写请求，将写请求写到本地事务日志，成功后再向Leader 回一个ACK确认。leader收到多数确认后，认为事务已经提交，通知follower执行消息。zxid记录了事务日志的最新更新，leader的zxid肯定最大，同时任意时刻系统超过多数follower的zxid和leader一致。

当leader崩溃时,zxid可以保证选举上来的follower的zxid和崩溃的leader一致，也就是本地事务日志是最新的。如果选举上来的leader发现自己本地的zxid没有执行，有两种可能1. zxid是最新的，leader尚未来得及通知执行就崩溃了，这时候应该执行；2. zxid是未提交的，需要重新进行两阶段提交。不管怎样，新leader上来对自身的zxid广播一遍，如果具有最新zxid的节点过半数，则通知他们执行；如果未过半数，则重新广播一次提交。

两阶段提交是单点串行的，也就是一个写操作执行完之后下一个才能执行，这就导致zookeeper不能执行高iops的写操作。

读操作需要经由leader返回版本和leader一致的follower，再从该follower里读。

新leader选举成功后，epoch+1，同时广播给follower，follower更新自身的epochid和leader一致。

当集群启动，或leader崩溃时，zookeeper需要进行leader选主

  1. 集群开始启动时，每个节点状态都是follower。follower自身会维护leader信息，集群中节点的数量，定期检查leader的存在。如果leader不存在，follower 将状态改为LOOKING，准备选举
  2. 节点携带(myid, zxid，epochid)向集群其他节点发选主请求（包括自己），只要同意的节点超过集群节点数量的1/2，当前节点就会认为自己是leader。myid 是每个节点初始化配置的id，zxid是leader执行一次事务就会递增的id。当节点收到选主请求时，会先比较epochid，相等再比较zxid, zxid相等则比较myid，请求携带的id如果比自身大，就返回投票响应，否则拒绝投票。集群开始启动时，所有节点的zxid都为0，最终myid大的会被投票成leader
  3. 如果节点处于looking状态，收到投票请求，且发现对方id比自己大，节点会选择投票给对方id，并广播出去
  4. 如果一个节点收到选择自己作为leader的数量大于一半节点，会将自己作为leader，同时广播给集群其他节点
  5. epochid和zxid小的不可能成为leader，借助两阶段提交，保证成为leader的节点必然具有所有的提交

如果某个节点收到请求A，发现比自己id大投票给他，后来又收到请求B，发现比自己id大又投票给了B。会不会导致A，B同时被选为leader？

  1. 什么时候出现？ 假设集群节点A、B、C、D，且四个节点zxid一致；leader挂了，节点C先发现，它向节点A、B、D发投票请求，A、B同意，D虽然反对，但不影响，C成了leader。后面节点D也发现leader挂了，于是向A、B、C发信息，A、B投票给了D，此时C已经成了leader，所以集群出现了两个leader？No，在C自认为成为leader后，需要广播到follower，follower会检查合法性，只有合法性过半数才能正式成为leader。所以如果A，B后来投票给了D，那么C的合法性检查会不通过；如果C合法性检查通过了，D再给A、B发选举请求，A、B将不予处理，C依然成为leader，C成为leader后将epoch更新通知D，D也会接受C成为leader。
  2. 因此只有当A，B节点检查到leader挂了，它才会进入looking状态，如果A、B检测到leader存活，其他节点对A、B发送请求选择，A、B将不予理会。

raft 一致性KV协议

raft 集群节点的角色有三种，leader, follower和candidate。其中candidate用于选举。

raft leader的写提交同样是zab的两阶段提交。因为两阶段提交能保证，leader挂了选上来的follower具有全部的已经提交的记录 。缺点是两阶段提交必须串行，不能高并发写

  1. leader issue AppendEntries RPC in parallel；leader wait for majority response
  2. leader notify follower apply log

raft 选举leader的协议和zab有所不同。当follower一定时间没有收到leader的心跳时，会进入选举状态

  1. raft节点维护一个term信息，当自己身份变为candidate时，会将term +1。
  2. 向所有节点发起 RequestVoteRPC 请求，请求包含（term，最后一条日志的任期号，最后一条日志的索引号
    1. 节点收到RequestVoteRPC请求时，先比较term， 再比较最后一条日志任期号，最后比较最后一条日志索引号。这些是保证投票给的节点具有所有已提交的日志）
  3. 等待rpc期间，如果收到其他节点声明自己是 Leader的请求
    1. 该 Leader 的 term 号大于等于自己的 term 号，说明对方已经成为 Leader，则自己回退为 Follower。
    2. 该 Leader 的 term 号小于自己的 term 号，那么会拒绝该请求并让该节点更新 term。

raft 选举基于《只要选择出的节点具有所有已经提交的日志，选谁都行》的原则，没有zab的myid这项规则，比zab选举要快。zab等待rpc期间收到其他节点声明自己是leader的请求，由于Myid的原因可能也会否决。

raft 两阶段提交写操作时，如果某节点落后太多，会强制将该节点日志和leader日志拉齐；如果某节点有很多日志但是没有提交，这些没有被提交的日志会被需要提交的日志覆盖。

如果不同节点日志中的两个条目有着相同的索引和任期号，则它们之间的所有条目都是完全一样的。

Paxos和multi Paxos 一致性协议

Basic Paxos

paxos的角色：Proposer提案者，Acceptor 投票者，Learner学习者

准备阶段Prepare

  1. 提案者向集群中的投票者发起提案编号为n的请求
  2. 投票者检查，如果发现自己之前的提案都小于n，则接受请求并承诺不会接受编号小于n的提案；否则拒绝提案

如果准备阶段提案者接受到了半数以上通过，则继续批准阶段Accept

  1. 提案者携带提案号n和提案值发给投票者
  2. 投票者确认提案编号不小于已承诺的最大编号，如果确认返回同意，否则拒绝
    如果结果超半数同意，广播给集群所有的Proposer，Acceptor，Learner，Learner负责记录最终结果

提议者可以同时也是决策者，提议者可以多个

basic paxos达成共识至少需要prepare和accept两次网络往返，高并发情况下可能导致活锁(多个提议者同时发起提案且一直重试，反复更新决策者上的提案编号，且任何一方都无法达到多数派决议来通过准备阶段)。因此，Paxos 算法主要用于理论研究，较少直接应用于工程实践。

multi Paxos

Multi-Paxos 通过选举出一个 Proposer 主节点，只有主节点可以发提案，避免多个Proposer同时发起提案反复影响。

集群中的若干Proposer 定期监测Proposer 主节点是否存在。当监测不存在时，向 Acceptors 发出选主 Proposer 申请。如果选主申请得到大多数Acceptors节点同意，该 Proposer 成为主节点。

TODO

Tikv 和分布式KV存储

zab, raft, multi paxos这些协议提供服务自身的可用性保证。hdfs的datanode如果挂了，可以通过namenode找到数据块另外的可用节点，namenode挂了，可以通过zookeeper重新选主，但是zookeeper的leader挂了，这个只能zookeeper利用协议自己去保证。

tikv 的记录会写入三副本，三副本按照multi-paxos组织，位于不同的三个节点。三副本其中一个作为leader，如果其中一个副本挂了（包含副本的节点挂了），会自动选出新的leader副本。单paxos以及zab, raft写入都是串行的，也就是说不论集群有多大，写入都经过一个leader。multi-paxos的最大优势是提高并发，例如一个数据子表一个paxos，可以实现多个数据子表的并行写。同时paxos自身可实现三副本自身的可用性（不依赖外部namenode就可以在崩溃后找到新的替代节点），同时利用leader实现写操作的事务支持。使用multi-paxos的好处还有，十分方便扩缩容/横向扩展，只需要扩一个follower进去, leader会自动将数据同步。

tikv 的设计来自google 的spanner

At every replica that is a leader, each spanserver also implements a transaction manager to support distributed transactions. The transaction manager is used to implement a participant leader; the other replicas in the group will be referred to as participant slaves.
(tidb的paxos不是server节点级别的，而是表切片级别的，表会按照固定大小划分成切片，每个切片是支持事务的单位)

kv和append-only文件系统的最大区别是，数据库的日志要求有序性，而append-only只要求原子性。数据库的操作包括增删改，因此日志必须严格按照用户的写入顺序执行，以便通过replay日志恢复状态。因此数据库需要递增id来让请求保序（类似tcp的seq）。而append-only系统只要求数据append写入就行了，不要求写入顺序，只要求写入的完整性。kv系统的版本是顺序性日志的id，append-only文件系统的版本是写成功后，chunk的最新位置（如果master记录的某chunk最新位置和server记录的不同，以master为准）。

另外的区别是，append写之前一般就要通知给master定版本(告知master自己这次要写多少，写完后chunk新长度是多少)，这样append写失败了master可以知道（可能导致数据丢失）。而kv leader自己不能决定版本，需要1/2以上follower确认才能定，否则数据库认为写失败。原因在于数据节点的master 分布式元数据场景下实际是元数据的server，它本身依赖元数据master提供可用性。

分布式文件系统除了三副本之外，通常使用EC纠删码实现数据冗余，EC可以降低存储成本，但使用EC的[offset, length]区间一般要求至少是4K对齐的。

三副本+multi-paxos+leader写 的存储模型对kv存储有很大思考价值