读书笔记： 分布式系统相关知识

(Updated: )
, ,

分布式系统相关知识

[TOC]

1. 分布式一致性哈希算法

一致性哈希算法常用于负载均衡中要求资源被均匀的分布到所有节点上,并且对资源的请求能快速路由到对应的节点上。同时，使服务器失效或者新增时的影响范围达到最小。

该算法的具体过程为：
①先构造一个长度为232的整数环（称作一致性Hash环），

②根据节点名称的Hash值（其分布范围为[0, 232-1]）将缓存服务器节点放置在这个Hash环上；（要保证n个服务器节点均衡地放置在环上）

③根据缓存数据的key的Hash值（其分布范围也为[0, 232-1]）在Hash环上顺时针查找距离这个key的Hash值最近的缓存服务器节点，即为该数据应该放置的的服务器。

④如果有节点的增加或者删除，原来节点的数据会顺时针迁移到最近的节点上。

img

2. 布隆过滤器

布隆过滤器一般用来判断一个数据是否在一个很大的数据集合里面。当然可以用数组，集合，树等数据结构和各种查找法都可以做同样的事情，但是布隆过滤器有更好的时间效率和空间效率。

布隆过滤器的核心是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k。布隆过滤器是一个假阳性的算法。

添加元素

  • 将要添加的元素给k个哈希函数进行计算
  • 得到位于位数组上面的k个位置
  • 将位数组上对应位置1

查询元素

  • 将要查询的元素给k个哈希函数
  • 得到对应于位数组上的k个位置
  • 如果k个位置有一个为0，则肯定不在集合中
  • 如果k个位置全部为1，则可能在集合中

3. LSM Tree

LSM的原理：将对数据的修改增量保存在内存中，达到指定大小限制之后批量把数据flush到磁盘中，磁盘中树定期可以做merge操作，合并成一棵大树，以优化读性能。不过读取的时候稍微麻烦一些，读取时看这些数据在内存中，如果未能命中内存，则需要访问较多的磁盘文件。极端的说，基于LSM树实现的hbase写性能比mysql高了一个数量级，读性能却低了一个数量级。

LSM-Tree 能将离散的随机写请求都转换成批量的顺序写请求（WAL + Compaction），以此提高写性能。

  • 读放大（Read Amplification）。LSM-Tree 的读操作需要从新到旧（从上到下）一层一层查找，直到找到想要的数据。这个过程可能需要不止一次 I/O。特别是 range query 的情况，影响很明显。
  • 空间放大（Space Amplification）。因为所有的写入都是顺序写（append-only）的，不是 in-place update ，所以过期数据不会马上被清理掉。
  • 写放大。实际写入 HDD/SSD 的数据大小和程序要求写入数据大小之比。正常情况下，HDD/SSD 观察到的写入数据多于上层程序写入的数据。

SSD 的使用寿命和其写入量有关，写放大太严重会大大缩短 SSD 的使用寿命。因为 SSD 不支持覆盖写，必须先擦除（erase）再写入。而每个 SSD block（block 是 SSD 擦除操作的基本单位） 的平均擦除次数是有限的。

SSD的写操作比较特殊，SSD的最小写入单元为4KB，称为页(page)，当写入空白位置时可以按照4KB的单位写入，但是如果需要改写某个单元时，则需要一个额外的擦除（erase）动作，擦除的单位一般是128个page（512KB），每个擦除单元称为块（block）。如果向一个空白的page写入信息时，可以直接写入而无需擦除，但是如果需要改写某个存储单元（page）的数据，必须首先将整个block读入缓存，然后修改数据，并擦除整个block的数据，最后将整个block写入，很显然，SSD改写数据的代价很高，SSD的这个特性，我们称之为erase-before-write。

基于SSD的优化就是解决erase-before-write产生的写入放大的问题，不同类型的IO分离，减少写操作带来的性能影响。

1.将sequential logging修改为In-page logging，避免对相同位置的反复擦写。In-page logging将日志和数据合并，将日志顺序写入改为随机写入，基于SSD对随机写和连续写IO响应延迟差异不大的特性，避免对同一位置反复擦写，提高整体性能。

2.通过缓存写入的方式将大量的in-place update随机写入合并为少量顺序写入。

3.利用SSD随机读写能力高的特点，减少写增加读，从而达到整体性能的提升。

4. CAP理论

CAP原则又称CAP定理，指的是在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。CAP 原则指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。

一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）
可用性（A）：保证每个请求不管成功或者失败都有响应。（可用性表示你总是能够访问集群，即使集群中的某个结点宕机了）
分区容忍性（P）：系统中任意信息的丢失或失败不会影响系统的继续运作。(分布式系统最先需要保证的就是分区容错性，一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中。这就叫分区。当你一个数据项只在一个节点中保存，那么分区出现后，和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。）

5. 2PC

2PC(tow phase commit)两阶段提交。

所谓的两个阶段是指：第一阶段：准备阶段(投票阶段)和第二阶段：提交阶段（执行阶段）。

我们将提议的节点称为协调者(coordinator)，其他参与决议节点称为参与者(participants, 或cohorts)。

第一阶段：准备阶段(投票阶段)

在阶段1中，协调者发起一个提议，分别问询各参与者是否接受，如下图：

img

第二阶段：提交阶段（执行阶段）

在阶段2中，协调者根据参与者的反馈，提交或中止事务，如果参与者全部同意则提交，只要有一个参与者不同意就中止。

优缺点

在异步环境并且没有节点宕机的模型下，2PC可以满足全认同、值合法、可结束，是解决一致性问题的一种协议。从协调者接收到一次事务请求、发起提议到事务完成，经过2PC协议后增加了2次RTT(propose+commit)，带来的时延增加相对较少。

二阶段提交有几个缺点：

  • 同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
  • 单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
  • 数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
  • 二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

6. 3pc

三阶段提交（Three-phase commit），是二阶段提交（2PC）的改进版本。

与两阶段提交不同的是，三阶段提交有两个改动点。

  • 引入超时机制。同时在协调者和参与者中都引入超时机制。
  • 在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。

也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。

CanCommit阶段

3PC的CanCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

  • 事务询问 协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
  • 响应反馈 参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No

PreCommit阶段

协调者根据参与者的反应情况来决定是否可以记性事务的PreCommit操作。根据响应情况，有以下两种可能。

假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。

  • 发送预提交请求 协调者向参与者发送PreCommit请求，并进入Prepared阶段。
  • 事务预提交 参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
  • 响应反馈 如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。

假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。

  • 发送中断请求 协调者向所有参与者发送abort请求。
  • 中断事务 参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

doCommit阶段

该阶段进行真正的事务提交，也可以分为以下两种情况。

执行提交

  • 发送提交请求 协调接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
  • 事务提交 参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
  • 响应反馈 事务提交完之后，向协调者发送Ack响应。
  • 完成事务 协调者接收到所有参与者的ack响应之后，完成事务。

中断事务

协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。

  • 发送中断请求 协调者向所有参与者发送abort请求
  • 事务回滚 参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
  • 反馈结果 参与者完成事务回滚之后，向协调者发送ACK消息
  • 中断事务 协调者接收到参与者反馈的ACK消息之后，执行事务的中断。

img

2pc和3pc的区别

相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。

在2PC中一个参与者的状态只有它自己和协调者知晓，假如协调者提议后自身宕机，在协调者备份启用前一个参与者又宕机，其他参与者就会进入既不能回滚、又不能强制commit的阻塞状态，直到参与者宕机恢复。

参与者如果在不同阶段宕机，我们来看看3PC如何应对：

  • 阶段1: 协调者或协调者备份未收到宕机参与者的vote，直接中止事务；宕机的参与者恢复后，读取logging发现未发出赞成vote，自行中止该次事务
  • 阶段2: 协调者未收到宕机参与者的precommit ACK，但因为之前已经收到了宕机参与者的赞成反馈(不然也不会进入到阶段2)，协调者进行commit；协调者备份可以通过问询其他参与者获得这些信息，过程同理；宕机的参与者恢复后发现收到precommit或已经发出赞成vote，则自行commit该次事务
  • 阶段3: 即便协调者或协调者备份未收到宕机参与者t的commit ACK，也结束该次事务；宕机的参与者恢复后发现收到commit或者precommit，也将自行commit该次事务

7. Percolator

Percolator 是 Google 的上一代分布式事务解决方案，构建在 BigTable 之上，在 Google 内部 用于网页索引更新的业务，原始的论文在此。原理比较简单，总体来说就是一个经过优化的二阶段提交的实现，进行了一个二级锁的优化。

假设一个分布式事务T1需要修改两个Cell，C1(Rowkey1:C1)和C2(Rowkey2:C2)，C1为primary cell，Value分别为Value1和Value2，并且两个Cell处于不同的tablet server，serverA和serverB。客户端commit之前首先将两个Cell都加入到客户端本地的一个数组中，最后事务commit(包括两阶段的prepare和commit)的时候才将所有Cell发向tablet server。

prepare阶段：

  1. 分布式事务T1启动，从全局时间戳服务器获取事务启动时间戳记作t1_start_ts。

  2. 首先写primary cell C1，往C1:data中写入t1_start_ts=>value1，往C1:lock中写入t1_start_ts=>primary cell 表示加锁，同理，写serverB，往C2:data中写入t1_start_ts=>value2, 往C2:lock中写入t1_start_ts=>primary cell

    commit阶段：

  3. 从全局时间戳服务器获取事务提交时间戳记作t1_commit_ts。

  4. 启动一个C1所在的BigTable行事务，包含以下两个操作

　　　　2.1 往primary cell C1:write写入t1_commit_ts=>t1_start_ts(这步是关键)

　　　　2.2 将primary cell的lock release(delete C1:lock，时间戳为t1_start_ts)

  1. Commit这个BigTable 事务，这一步实际上将这个事务的数据对外可见，因为随后的一个读事务(事务启动时间戳记作t2_start_ts)读C1之前，会首先读C1:write的小于t2_start_ts的最大的版本的数据获得t1_start_ts，然后拿着t1_start_ts才能去C1:data中读取真正的数据。

  2. 将其他secondary cell C2:write中写入t1_commit_ts=>t1_start_ts，release C2的lock

没有检测到冲突的读C1和C2的事务T3流程：

　　1. 从全局时间戳服务器获取事务提交时间戳记作t3_start_ts

　　2. 分别读C1和C2，读C:write的比t3_start_ts小的最大的一个事务提交时间戳的事务启动时间，然后拿这个事务启动时间去C:data中读真正的数据。

可以看出，一个Cell对外可见是通过写C:write来达到的，t1_commit_ts为事务提交版本号，t1_start_ts为t1这个事务修改后的数据版本号，真正读数据需要拿到t1_start_ts，而读t1_start_ts又需要首先拿到t1_commit_ts。

https://www.cnblogs.com/foxmailed/p/3887430.html

8. Paxos Raft ZAB

Basic-Paxos

角色分类

  • client 民众：请求发起者

  • Proposer 提案者：接受Client的请求，可以有多个，向集群发起一个议案（由client向Proposer发出），议案包括议案编号、议案内容

  • Acceptor 接收者、批准者：用于接收Proposer提出的议案，并决定采纳哪一个议案

  • Learner 学习者、记录者：在最终决定采纳某个议案后，进行记录，不做其他事

约束条件
  • Acceptor必须接受它收到的第一个议案
  • Acceptor只认可接收到的最新的议案（即议案编号最新）
  • 当某个议案被一半以上Acceptor认可后，那么该议案成功
运作流程

image-20210419021859202

1
2
3
4
5
6
7
8
9
10
11
12
Proposer 广播 ---Prepare(n)---> 所有的 Acceptor

Proposer <---接受--- Acceptor 1
Proposer <---接受--- Acceptor 2
Proposer <---否认--- Acceptor 3

// 如果有一半以上Acceptor接受，那么该议案成功
// 否则说明还有其他Proposer的议案（编号不同），隔一个随机时间，更新自己的议案编号，重提
Proposer 广播 ---Accpet(n, value)---> 所有的 Acceptor

// 议案通过
Proposer <---认可--- 所有的 Acceptor ---认可---> Learner [进行记录]
  1. Paxos算法包括两个阶段:
    第一个阶段主要是贿选,还没有提出提议;第二个阶段主要根据第一阶段的结果,明确接受谁的提议,并明确提议的内容是什么(这个提议可能是贿选胜出“提议者“自己的提议,也可能是前任意见领袖的提议,具体是哪个提议,见下面第3点原则)

2)编号(贿略金额)很重要,无论在哪个阶段,编号(贿赂金额)小的,都会被视(被拒绝)

3)在第一阶段中,一旦“接受者”已经接受了之前意见领袖的提议,那后面再来找这个“接受者“的“提议者”,即便在贿赂中胜出,也要被洗脑,默默将自己的提议改为前任意见领袖的提议,然后他会在第二阶段提出该提议(也就是之前意见领袖的提议,以力争让大家的意见趋同)。如果“接受者”之前没有接受过任何提议,那贿选胜出的“提议者”就可以提出自己的提议了

Raft

角色

Leader：所有请求的处理者，Leader副本接受client的更新请求，本地处理后再同步至多个其他副本；
Follower：请求的被动更新者，从Leader接受更新请求，然后写入本地日志文件
Candidate：如果Follower副本在一段时间内没有收到Leader副本的心跳，则判断Leader可能已经故障，此时启动选主过程，此时副本会变成Candidate状态，直到选主结束。

选举任期

  • Raft将时间分为任意长度的任期(term)。一个任期从一个选举开始。注意图中的t3，此时由于平票等原因没有产生Leader，则重新开始一个新的选举产生term4.
  • 使用时间的一致性机制显然是不合理的。故server可能任然处于旧的任期(term)下，即使全局的Leader已经更新。如果server发现其term已过时，则更新到最新的term。而一个来自过时term的请求会被server拒绝。
Leader选举(leader election)

所有分布式节点初始化为follower，当选举出的Leader发送心跳包(AppendEntries不包含实际log entry)，则follower认为leader有效。当follower超时(election timeout)任然未收到心跳包，则认为leader失效，需要重新选举。

一个follower成为candidate，并行的向所有其它servers发起RequestVote RPC请求。candidate保持在该状态直到：

  • 该candidate成功成为leader

当candidate获得了大多数的选票，则成为leader。每一个server，包括candidate本身，至多给一个candidate投票，且投票给第一个来自candidate的RPC请求，即先来先得的原则。

该机制保证了选举的安全性，即一个任期term至多只有一个leader被选出。

当某一server成为leader后，会向所有其它servers发送心跳包，告知其leader以选出。

  • 另一个server成为了leader，则其回退到follower状态

当server接收到来自一个被选出leader的心跳包，且其任期term大于等于该server当前的任期，则认为该leader为合法的。

  • 在有限时间内，整个系统没有任何一个节点成为leader，比如出现平票，则等到timeout后，退出candidate状态，等待发起下一次选举。

要注意的是，当没有相应的措施，下一次选举仍然会出现平票的情况。Raft采取Randomized election timeouts保证平票发生概率很低，即每个server选举超时时间是随机的，尽可能避免了平票的发生。

ZAB与Raft的区别

Zab和Raft都是强一致性协议，但是Zab和Raft的实质是一样的，都是mutli-paxos衍生出来的强一致性算法。简单而言，他们的算法都都是先通过Leader选举，选出一个Leader，然后Leader接受到客户端的提议时，都是先写入操作日志，然后再与其他Followers同步日志，Leader再commit提议，再与其他Followers同步提议。
如果Leader故障，重新走一遍选举流程，选取最新的操作日志，然后同步日志，接着继续接受客户端请求等等。过程都是一样，只不过两个的实现方式不同，描述方式不同。实现Raft的核心是Term，Zab的核心是Zxid，反正Term和Zxid都是逻辑时钟。

9. Google Online Schema

算法思想

为了更好地阐释算法思想，本节我们以一个简化的情境做类比。

假想我们有一家跨国公司，公司员工分布在全球各地，员工之间以电子邮件的方式互相通信，同时工作的性质要求员工之间发送的消息不能出现丢失。之后在某一天出现这样的需求：管理层决定把员工通信方式由邮件改为 QQ。

对于这样一个跨国公司来说，我们无法瞬间把新的工作方式通知给所有员工。假如先收到通知的员工先改为用 QQ 了，而未收到通知的员工还在用邮件，这样一来自然就会发生大量的消息丢失。

那么我们能不能通知员工在未来的某个时刻统一换用 QQ 呢？仔细一想也是不行的。因为每个员工的手表不可能是完全对准的，总是有的快点有的慢点，只要不能保证所有员工的时间完全校准，总有那么一个不一致的时刻。

下面让我们来看看 Google 的工程师们是怎么解决这个棘手的问题的。

在未知中构建已知

根据上面的讨论，最根本的难点在于无法保证所有员工同时改变通信方式，这基本上是不可能做到的。本来员工都在用邮件，一旦通知发布出去，员工的工作方式就完全是未知的了——在任意一个时刻，任意一个员工都可能收到过通知而换用 QQ，也可能没收到通知而继续用邮件。

如果从现实层面来考虑，员工即使是离得远些，一段足够长的时间以后也应该能收到通知。员工的时间即使是没校准，也不至于错得太离谱。所以我们可以认为在足够长的时间过后，所有员工应该都已经换用 QQ 了。

我们可以使用一系列方案使“足够长的时间”变成“确定长度的时间”。首先，公司创建一个网站张贴最新的员工手册，其中自然包含员工应使用的通信方式等细则。其次，在员工入职时进行培训，要求员工每隔 30 分钟必须上网查看一下员工手册，并依照最新的手册行事。另外，如果出现网络故障等情况，员工在尝试访问网站 10 分钟后还没有看到新的手册，必须立即停止工作，直到重新看到手册为止。

基于这些规定，我们就至少可以知道从通知发布之后的某个时刻开始，所有工作中的员工都已经更新自己的通信方式了。例如我们中午 12:00 在网站上张贴新的手册，员工从 12:00 到 12:30 开始陆续查看手册并换用 QQ，到 12:30 时所有员工都应该尝试过访问网站了，到 12:40 时所有未能看到手册的员工都已经停止了工作，这时我们就可以认为所有工作中的员工都在用 QQ 了。如果再考虑手表时快时慢等特殊情形，我们不妨再多等 20 分钟。到了 13:00 ，我们可以非常自信地说：现在所有员工都换用 QQ 了。

在此基础之上，我们再规定两次修改员工手册的时间间隔不能少于 1 小时。例如在 QQ 之后我们还想换用微信，那么最早只能在 13:00 发布新的员工手册。根据前面的讨论，13:00 已经没有员工用邮件了，所以在整个演化过程中，有些时刻邮件和 QQ 同时被使用，有些时刻 QQ 和微信同时被使用，但一定不会发生邮件和微信同时被使用的情况。也就是说，在员工手册不断更新的过程中，最多只有两份手册生效：最新发布的这一份以及上一份。

在矛盾中构建一致

上面我们设计了大量的规定和方案，最后只得到了不那么强的结论，看起来对问题的解决并没有什么帮助。不难发现问题的关键在于邮件和 QQ 这两种通信方式是矛盾不兼容的，只要有一个时刻有员工用邮件而有员工用 QQ，那么就很可能会造成消息丢失。

那么问题的本质其实是：在通信方式由邮件变成 QQ 的过程中，邮件和 QQ 这两种通信方式不能同时生效。

请回想一下上一节中我们得到过的结论，邮件和微信一定不可能同时被使用……你想到了吗？

BING！没错，只要我们在邮件和 QQ 中间加入一个其他的通信方式 X 作为过渡，因为同时只有两种连续的手册生效，邮件和 QQ 就很自然地被隔离了。很显然通信方式 X 一定不是微信，它一定是同时与邮件和 QQ 兼容的，在这里 X 的定义可以是：同时从邮件和 QQ 查收消息，发送消息时邮件和 QQ 各发送一遍。

以上就是 F1 schema 变更的主要思想了。具体在 F1 schema 变更的过程中，由于数据库本身的复杂性，有些变更无法由一个中间状态隔离，我们需要设计多个逐步递进的状态来进行演化。万变不离其宗，只要我们保证任意相邻两个状态是相互兼容的，整个演化的过程就是可依赖的。

F1 中的算法实现

租约

F1 中 schema 以特殊的 kv 对存储于 Spanner 中，同时每个 F1 服务器在运行过程中自身也维护一份拷贝。为了保证同一时刻最多只有 2 份 schema 生效，F1 约定了长度为数分钟的 schema 租约，所有 F1 服务器在租约到期后都要重新加载 schema 。如果节点无法重新完成续租，它将会自动终止服务并等待被集群管理设施重启。

中间状态

前面已经提过，F1 在 schema 变更的过程中，会把一次 schema 的变更拆解为多个逐步递进的中间状态。实际上我们并不需要针对每种 schema 变更单独设计中间状态，总共只需要两种就够了： delete-only 和 write-only 。

delete-only 指的是 schema 元素的存在性只对删除操作可见。

例如当某索引处于 delete-only 状态时，F1 服务器中执行对应表的删除一行数据操作时能“看到”该索引，所以会同时删除该行对应的索引，与之相对的，如果是插入一行数据则“看不到”该索引，所以 F1 不会尝试新增该行对应的索引。

具体的，如果 schema 元素是 table 或 column ，该 schema 元素只对 delete 语句生效；如果 schema 元素是 index ，则只对 delete 和 update 语句生效，其中 update 语句修改 index 的过程可以认为是先 delete 后再 insert ，在 delete-only 状态时只处理其中的 delete 而忽略掉 insert 。

总之，只要某 schema 元素处于 delete-only 状态，F1 保证该 schema 元素对应的 kv 对总是能够被正确地删除，并且不会为此 schema 元素创建任何新的 kv 对。

write-only 指的是 schema 元素对写操作可见，对读操作不可见。

例如当某索引处于 write-only 状态时，不论是 insert 、 delete ，或是 update ，F1 都保证正确的更新索引，只是对于查询来说该索引仍是不存在的。

简单的归纳下就是 write-only 状态的 schema 元素可写不可读。

示例推演

Google 论文的叙述过程是描述完两种中间状态后就开始了冗长的形式化推导，最后得以证明按照特定的步骤来做 schema 演化是能保证一致性的。这里我想先拿出一个例子把 schema 变更的过程推演一遍，这样形成整体印象后更有助于看懂证明：）我们以添加索引为例，对应的完整 schema 演化过程如下：

1
absent --> delete only --> write only --(reorg)--> public

其中 delete-only 和 write-only 是介绍过了的中间状态。 absent 指该索引完全不存在，也就是schema变更的初始状态。 public 自然对应变更完成后就状态，即索引可读可写，对所有操作可见。

reorg 指 “database reorganization”，不是一种 schema 状态，而是发生在 write-only 状态之后的一系列操作。这些操作是为了保证在索引变为 public 之前所有旧数据的索引都被正确地生成。

根据之前的讨论，F1 中同时最多只可能有两分 schema 生效，我们逐个步骤来分析。

先看 absent 到 delete-only 。很显然这个过程中不会出现与此索引相关的任何数据。

再看 delete-only 到 write-only 。根据 write-only 的定义，一旦某节点进入 write-only 状态后，任何数据变更都会同时更新索引。当然，不可能所有节点同时进入 write-only 状态，但我们至少能保证没有节点还停留在 absent 状态， delete-only 或 write-only 状态的节点都能保证索引被正确清除。于是我们知道：从 write-only 状态发布时刻开始，数据库中不会存在多余的索引。

接下来是 reorg ，我们来考察 reorg 开始时数据库的状态。首先因为 delete-only 的存在，我们知道此时数据库中不存在多余的索引。另外此时不可能有节点还停留在 delete-only 状态，我们又知道从这时起，所有数据的变更都能正确地更新索引。所以 reorg 要做的就是取到当前时刻的snapshot，为每条数据补写对应的索引即可。当然 reorg 开始之后数据可能发生变更，这种情况下底层Spanner提供的一致性能保证 reorg 的写入操作要么失败（说明新数据已提前写入），要么被新数据覆盖。

基于前面的讨论，到 reorg 完成时，我们的数据不少不多也不错乱，可以放心地改为 public 状态了。