数据库面试题整理

• Mysql 面试题
  • 1. 能说下myisam 和 innodb的区别吗？
  • 2. 说下mysql的索引有哪些吧，聚簇和非聚簇索引又是什么？
  • 3. 那你知道什么是覆盖索引和回表吗？
  • 4. 锁的类型有哪些呢
  • 5. 你能说下事务的基本特性和隔离级别吗？
  • 6. 那ACID靠什么保证的呢？
  • 7. 什么是MVCC？
  • 8. 为什么说间隙锁是可重复读隔离级别下防止幻读的主要云因？
  • 9. 你们数据量级多大？分库分表怎么做的？
  • 10. 那分表后的ID怎么保证唯一性的呢？
  • 11. 分表后非sharding_key的查询怎么处理呢？
  • 12. 说说mysql主从同步怎么做的吧？
  • 13. 那主从的延迟怎么解决呢？
  • 14. InnoDB 引擎的四大特性是什么？
  • 15. Mysql如何进行后期优化？
  • 16. Mysql一条SQL语句的执行过程
  • 17. Mysql Join算法的原理
    • 18. 堆组织表，索引组织表和索引聚簇表
    • 19. LRU List、Free List和Flush List
    • 20. Mysql的 CheakPoint技术
  • 21 Mysql的Redo Undo BinLog
• 分布式算法
  • 1. 分布式一致性哈希算法
  • 2. 布隆过滤器
  • 3. LSM Tree
  • 4. CAP理论
  • 5. 2PC
    • 第一阶段：准备阶段(投票阶段)
    • 第二阶段：提交阶段（执行阶段）
    • 优缺点
  • 6. 3pc
    • CanCommit阶段
    • PreCommit阶段
    • doCommit阶段
    • 2pc和3pc的区别
  • 7. Percolator
  • 8. Paxos Raft ZAB
    • Basic-Paxos
    • Raft
    • ZAB与Raft的区别
  • 9. Google Online Schema
    • 算法思想
    • 在未知中构建已知
    • 在矛盾中构建一致
    • F1 中的算法实现

Mysql 面试题#

1. 能说下myisam 和 innodb的区别吗？#

myisam引擎是5.1版本之前的默认引擎，支持全文检索、压缩、空间函数等，但是不支持事务和行级锁，所以一般用于有大量查询少量插入的场景来使用，而且myisam不支持外键，并且索引和数据是分开存储的。

innodb是基于聚簇索引建立的，和myisam相反它支持事务、外键，并且通过MVCC来支持高并发，索引和数据存储在一起。

2. 说下mysql的索引有哪些吧，聚簇和非聚簇索引又是什么？#

索引按照数据结构来说主要包含B+树和Hash索引。

假设我们有张表，结构如下：

create table user(
    id int(11) not null,
  age int(11) not null,
  primary key(id),
  key(age)
);

B+树是左小右大的顺序存储结构，节点只包含id索引列，而叶子节点包含索引列和数据，这种数据和索引在一起存储的索引方式叫做聚簇索引，一张表只能有一个聚簇索引。假设没有定义主键，InnoDB会选择一个唯一的非空索引代替，如果没有的话则会隐式定义一个主键作为聚簇索引。

这是主键聚簇索引存储的结构，那么非聚簇索引的结构是什么样子呢？非聚簇索引(二级索引)保存的是主键id值，这一点和myisam保存的是数据地址是不同的。

最终，我们一张图看看InnoDB和Myisam聚簇和非聚簇索引的区别

3. 那你知道什么是覆盖索引和回表吗？#

覆盖索引指的是在一次查询中，如果一个索引包含或者说覆盖所有需要查询的字段的值，我们就称之为覆盖索引，而不再需要回表查询。

而要确定一个查询是否是覆盖索引，我们只需要explain sql语句看Extra的结果是否是“Using index”即可。

以上面的user表来举例，我们再增加一个name字段，然后做一些查询试试。

explain select * from user where age=1; //查询的name无法从索引数据获取
explain select id,age from user where age=1; //可以直接从索引获取

4. 锁的类型有哪些呢#

mysql锁分为共享锁和排他锁，也叫做读锁和写锁。

读锁是共享的，可以通过lock in share mode实现，这时候只能读不能写。

写锁是排他的，它会阻塞其他的写锁和读锁。从颗粒度来区分，可以分为表锁和行锁两种。

表锁会锁定整张表并且阻塞其他用户对该表的所有读写操作，比如alter修改表结构的时候会锁表。

行锁又可以分为乐观锁和悲观锁，悲观锁可以通过for update实现，乐观锁则通过版本号实现。

InnoDB锁机制之Gap Lock、Next-Key Lock、Record Lock解析#

MySQL InnoDB支持三种行锁定方式：

行锁（Record Lock）:锁直接加在索引记录上面，锁住的是key。

间隙锁（Gap Lock）:锁定索引记录间隙，确保索引记录的间隙不变。间隙锁是针对事务隔离级别为可重复读或以上级别而已的。

Next-Key Lock ：行锁和间隙锁组合起来就叫Next-Key Lock。

默认情况下，InnoDB工作在可重复读隔离级别下，并且会以Next-Key Lock的方式对数据行进行加锁，这样可以有效防止幻读的发生。Next-Key Lock是行锁和间隙锁的组合，这个锁机制其实就是前面两个锁相结合的机制，既锁住记录本身还锁住索引之间的间隙。加锁原则：

原则1:加锁的基本单位是next-key lock，前开后闭

原则2:查找过程中访问到的对象才会加锁

优化1:索引上的等值查询，给唯一索引加锁的时候，next-key lock退化成行锁

优化2:索引上的等值查询，向右遍历时且最后一个值不满足等值条件的时候，next-key lock退化为间隙锁

唯一索引上的范围查询会访问到不满足条件的第一个值为止

5. 你能说下事务的基本特性和隔离级别吗？#

事务基本特性ACID分别是：

原子性指的是一个事务中的操作要么全部成功，要么全部失败。

一致性指的是数据库总是从一个一致性的状态转换到另外一个一致性的状态。比如A转账给B100块钱，假设中间sql执行过程中系统崩溃A也不会损失100块，因为事务没有提交，修改也就不会保存到数据库。

隔离性指的是一个事务的修改在最终提交前，对其他事务是不可见的。

持久性指的是一旦事务提交，所做的修改就会永久保存到数据库中。

而隔离性有4个隔离级别，分别是：

read uncommit 读未提交，可能会读到其他事务未提交的数据，也叫做脏读。

用户本来应该读取到id=1的用户age应该是10，结果读取到了其他事务还没有提交的事务，结果读取结果age=20，这就是脏读。

read commit 读已提交，两次读取结果不一致，叫做不可重复读。

不可重复读解决了脏读的问题，他只会读取已经提交的事务。

用户开启事务读取id=1用户，查询到age=10，再次读取发现结果=20，在同一个事务里同一个查询读取到不同的结果叫做不可重复读。

repeatable read 可重复复读，这是mysql的默认级别，就是每次读取结果都一样，但是有可能产生幻读。

serializable 串行，一般是不会使用的，他会给每一行读取的数据加锁，会导致大量超时和锁竞争的问题。

6. 那ACID靠什么保证的呢？#

A原子性由undo log日志保证，它记录了需要回滚的日志信息，事务回滚时撤销已经执行成功的sql

C一致性一般由代码层面来保证

I隔离性由MVCC来保证

D持久性由内存+redo log来保证，mysql修改数据同时在内存和redo log记录这次操作，事务提交的时候通过redo log刷盘，宕机的时候可以从redo log恢复

7. 什么是MVCC？#

MVCC多版本并发控制机制

这个隔离性就是靠MVCC(Multi-Version Concurrency Control)机制来保证的，对一行数据的读和写两个操作默认是不会通过加锁互斥来保证隔离性，避免了频繁加锁互斥，而在串行化隔离级别为了保证较高的隔离性是通过将所有操作加锁互斥来实现的。

Mysql在读已提交和可重复读隔离级别下都实现了MVCC机制。

undo日志版本链与read view机制详解

undo日志版本链是指一行数据被多个事务依次修改过后，在每个事务修改完后，Mysql会保留修改前的数据undo回滚日志，并且用两个隐藏字段trx_id和roll_pointer把这些undo日志串联起来形成一个历史记录版本链(见下图，需参考视频里的例子理解)

在可重复读隔离级别，当事务开启，执行任何查询sql时会生成当前事务的**一致性视图read-view，**该视图在事务结束之前都不会变化(如果是读已提交隔离级别在每次执行查询sql时都会重新生成)，这个视图由执行查询时所有未提交事务id数组（数组里最小的id为min_id）和已创建的最大事务id（max_id）组成，事务里的任何sql查询结果需要从对应版本链里的最新数据开始逐条跟read-view做比对从而得到最终的快照结果。

版本链比对规则：

\1. 如果 row 的 trx_id 落在绿色部分( trx_id<min_id )，表示这个版本是已提交的事务生成的，这个数据是可见的；

\2. 如果 row 的 trx_id 落在红色部分( trx_id>max_id )，表示这个版本是由将来启动的事务生成的，是不可见的(若 row 的 trx_id 就是当前自己的事务是可见的）；

\3. 如果 row 的 trx_id 落在黄色部分(min_id <=trx_id<= max_id)，那就包括两种情况

a. 若 row 的 trx_id 在视图数组中，表示这个版本是由还没提交的事务生成的，不可见(若 row 的 trx_id 就是当前自己的事务是可见的)；

b. 若 row 的 trx_id 不在视图数组中，表示这个版本是已经提交了的事务生成的，可见。

对于删除的情况可以认为是update的特殊情况，会将版本链上最新的数据复制一份，然后将trx_id修改成删除操作的trx_id，同时在该条记录的头信息（record header）里的（deleted_flag）标记位写上true，来表示当前记录已经被删除，在查询时按照上面的规则查到对应的记录如果delete_flag标记位为true，意味着记录已被删除，则不返回数据。

**注意：**begin/start transaction 命令并不是一个事务的起点，在执行到它们之后的第一个修改操作InnoDB表的语句，事务才真正启动，才会向mysql申请事务id，mysql内部是严格按照事务的启动顺序来分配事务id的。

总结：

MVCC机制的实现就是通过read-view机制与undo版本链比对机制，使得不同的事务会根据数据版本链对比规则读取同一条数据在版本链上的不同版本数据。

8. 为什么说间隙锁是可重复读隔离级别下防止幻读的主要云因？#

解决幻读的方式很简单，就是需要当事务进行当前读的时候，保证其他事务不可以在满足当前读条件的范围内进行数据操作。

例如：

id(主键)	c（普通索引）	d（无索引）
5	5	5
10	10	10
15	15	15
20	20	20
25	25	25

以上数据为了解决幻读问题，更新的时候不只是对上述的五条数据增加行锁，还对于中间的取值范围增加了6个间隙锁，（-∞，5]（5，10]（10，15]（15，20]（20，25]（25，+supernum] （其中supernum是数据库维护的最大的值。为了保证间隙锁都是左开右闭原则。）

9. 你们数据量级多大？分库分表怎么做的？#

首先分库分表分为垂直和水平两个方式，一般来说我们拆分的顺序是先垂直后水平。

垂直分库

基于现在微服务拆分来说，都是已经做到了垂直分库了

垂直分表

如果表字段比较多，将不常用的、数据较大的等等做拆分

水平分表

首先根据业务场景来决定使用什么字段作为分表字段(sharding_key)，比如我们现在日订单1000万，我们大部分的场景来源于C端，我们可以用user_id作为sharding_key，数据查询支持到最近3个月的订单，超过3个月的做归档处理，那么3个月的数据量就是9亿，可以分1024张表，那么每张表的数据大概就在100万左右。

比如用户id为100，那我们都经过hash(100)，然后对1024取模，就可以落到对应的表上了。

10. 那分表后的ID怎么保证唯一性的呢？#

因为我们主键默认都是自增的，那么分表之后的主键在不同表就肯定会有冲突了。有几个办法考虑：

1. 设定步长，比如1-1024张表我们分别设定1-1024的基础步长，这样主键落到不同的表就不会冲突了。
2. 分布式ID，自己实现一套分布式ID生成算法或者使用开源的比如雪花算法这种
3. 分表后不使用主键作为查询依据，而是每张表单独新增一个字段作为唯一主键使用，比如订单表订单号是唯一的，不管最终落在哪张表都基于订单号作为查询依据，更新也一样。

11. 分表后非sharding_key的查询怎么处理呢？#

1. 可以做一个mapping表，比如这时候商家要查询订单列表怎么办呢？不带user_id查询的话你总不能扫全表吧？所以我们可以做一个映射关系表，保存商家和用户的关系，查询的时候先通过商家查询到用户列表，再通过user_id去查询。
2. 打宽表，一般而言，商户端对数据实时性要求并不是很高，比如查询订单列表，可以把订单表同步到离线（实时）数仓，再基于数仓去做成一张宽表，再基于其他如es提供查询服务。
3. 数据量不是很大的话，比如后台的一些查询之类的，也可以通过多线程扫表，然后再聚合结果的方式来做。或者异步的形式也是可以的。

List<Callable<List<User>>> taskList = Lists.newArrayList();
for (int shardingIndex = 0; shardingIndex < 1024; shardingIndex++) {
    taskList.add(() -> (userMapper.getProcessingAccountList(shardingIndex)));
}
List<ThirdAccountInfo> list = null;
try {
    list = taskExecutor.executeTask(taskList);
} catch (Exception e) {
    //do something
}

public class TaskExecutor {
    public <T> List<T> executeTask(Collection<? extends Callable<T>> tasks) throws Exception {
        List<T> result = Lists.newArrayList();
        List<Future<T>> futures = ExecutorUtil.invokeAll(tasks);
        for (Future<T> future : futures) {
            result.add(future.get());
        }
        return result;
    }
}

12. 说说mysql主从同步怎么做的吧？#

首先先了解mysql主从同步的原理

1. master提交完事务后，写入binlog
2. slave连接到master，获取binlog
3. master创建dump线程，推送binglog到slave
4. slave启动一个IO线程读取同步过来的master的binlog，记录到relay log中继日志中
5. slave再开启一个sql线程读取relay log事件并在slave执行，完成同步
6. slave记录自己的binglog

由于mysql默认的复制方式是异步的，主库把日志发送给从库后不关心从库是否已经处理，这样会产生一个问题就是假设主库挂了，从库处理失败了，这时候从库升为主库后，日志就丢失了。由此产生两个概念。

全同步复制

主库写入binlog后强制同步日志到从库，所有的从库都执行完成后才返回给客户端，但是很显然这个方式的话性能会受到严重影响。

半同步复制

和全同步不同的是，半同步复制的逻辑是这样，从库写入日志成功后返回ACK确认给主库，主库收到至少一个从库的确认就认为写操作完成。

13. 那主从的延迟怎么解决呢？#

这个问题貌似真的是个无解的问题，只能是说自己来判断了，需要走主库的强制走主库查询。

在学习过程中,我喜欢找一些电子书，视频结合起来学习，有不明白的都可以到圈子里面讨论交流，主要对Java视频，Java学习路线，Java.面试题，电子书分享，程序员的聚集地。

14. InnoDB 引擎的四大特性是什么？#

插入缓冲（Insert buffer)#

Insert Buffer 用于非聚集索引的插入和更新操作。先判断插入的非聚集索引是否在缓存池中，如果在则直接插入，否则插入到 Insert Buffer 对象里。再以一定的频率进行 Insert Buffer 和辅助索引叶子节点的 merge 操作，将多次插入合并到一个操作中，提高对非聚集索引的插入性能。

二次写 (Double write)#

Double Write由两部分组成，一部分是内存中的double write buffer，大小为2MB，另一部分是物理磁盘上共享表空间连续的128个页，大小也为 2MB。在对缓冲池的脏页进行刷新时，并不直接写磁盘，而是通过 memcpy 函数将脏页先复制到内存中的该区域，之后通过doublewrite buffer再分两次，每次1MB顺序地写入共享表空间的物理磁盘上，然后马上调用fsync函数，同步磁盘，避免操作系统缓冲写带来的问题。

自适应哈希索引 (Adaptive Hash Index)#

InnoDB会根据访问的频率和模式，为热点页建立哈希索引，来提高查询效率。索引通过缓存池的 B+ 树页构造而来，因此建立速度很快，InnoDB存储引擎会监控对表上各个索引页的查询，如果观察到建立哈希索引可以带来速度上的提升，则建立哈希索引，所以叫做自适应哈希索引。

缓存池#

为了提高数据库的性能，引入缓存池的概念，通过参数 innodb_buffer_pool_size 可以设置缓存池的大小，参数 innodb_buffer_pool_instances 可以设置缓存池的实例个数。缓存池主要用于存储以下内容：

缓冲池中缓存的数据页类型有：索引页、数据页、undo页、插入缓冲 (insert buffer)、自适应哈希索引(adaptive hash index)、InnoDB存储的锁信息 (lock info)和数据字典信息 (data dictionary)。

15. Mysql如何进行后期优化？#

1. 选择合适的存储引擎
2. 尽量保证从内存中读取数据，将数据保存在内存中
3. 减少磁盘写入操作
4. 充分使用索引，在Join表的时候使用相当类型的例，并将其索引
5. 分析查询日志和慢查询日志

16. Mysql一条SQL语句的执行过程#

查询语句#

1. 先检查该语句是否有权限，如果没有权限，直接返回错误信息，如果有权限，在 MySQL8.0 版本以前，会先查询缓存，以这条 sql 语句为 key 在内存中查询是否有结果，如果有直接缓存，如果没有，执行下一步。
2. 通过分析器进行词法分析，提取 sql 语句的关键元素，比如提取上面这个语句是查询 select，提取需要查询的表名为 tb_student,需要查询所有的列，查询条件是这个表的 id=‘1’。然后判断这个 sql 语句是否有语法错误，比如关键词是否正确等等，如果检查没问题就执行下一步。
3. 优化器进行确定执行方案，优化器根据自己的优化算法进行选择执行效率最好的一个方案（优化器认为，有时候不一定最好）。
4. 进行权限校验，如果没有权限就会返回错误信息，如果有权限就会调用数据库引擎接口，返回引擎的执行结果。

SQL 等执行过程分为两类，一类对于查询等过程如下：权限校验—》查询缓存—》分析器—》优化器—》权限校验—》执行器—》引擎

更新语句#

1. 先查询到需要修改的这一条数据，如果有缓存，也是会用到缓存。
2. 然后拿到查询的语句，进行值的修改，然后调用引擎 API 接口，写入这一行数据，InnoDB 引擎把数据保存在内存中，同时记录 redo log，此时 redo log 进入 prepare 状态，然后告诉执行器，执行完成了，随时可以提交。
3. 执行器收到通知后记录 binlog，然后调用引擎接口，提交 redo log 为提交状态。
   更新完成。

对于更新等语句执行流程如下：分析器—-》权限校验—-》执行器—》引擎—redo log prepare—》binlog—》redo log commit

17. Mysql Join算法的原理#

一、Simple Nested-Loop Join（简单的嵌套循环连接）#

简单来说嵌套循环连接算法就是一个双层for 循环 ，通过循环外层表的行数据，逐个与内层表的所有行数据进行比较来获取结果，当执行

select * from user tb1 
left join level tb2 
on tb1.id=tb2.user_id

时，我们会按类似下面代码的思路进行数据匹配：

整个匹配过程会如下图：

特点：

Nested-Loop Join 简单粗暴容易理解，就是通过双层循环比较数据来获得结果，但是这种算法显然太过于粗鲁，如果每个表有1万条数据，那么对数据比较的次数=1万 * 1万 =1亿次，很显然这种查询效率会非常慢。

当然mysql 肯定不会这么粗暴的去进行表的连接，所以就出现了后面的两种对Nested-Loop Join 优化算法，在执行join 查询时mysql 会根据情况选择 后面的两种优join优化算法的一种进行join查询。

二、Index Nested-Loop Join（索引嵌套循环连接）#

Index Nested-Loop Join其优化的思路:
主要是为了减少内层表数据的匹配次数， 简单来说Index Nested-Loop Join 就是通过外层表匹配条件 直接与内层表索引进行匹配，避免和内层表的每条记录去进行比较， 这样极大的减少了对内层表的匹配次数，从原来的匹配次数=外层表行数 内层表行数,变成了 外层表的行数 内层表索引的高度，极大的提升了 join的性能。

案例：

如SQL：

select * from user tb1 
left join level tb2 
on tb1.id=tb2.user_id

当level 表的 user_id 为索引的时候执行过程会如下图：

注意：使用Index Nested-Loop Join 算法的前提是匹配的字段必须建立了索引。

三 Block Nested-Loop Join（缓存块嵌套循环连接）#

Block Nested-Loop Join 其优化思路是减少内层表的扫表次数，通过简单的嵌套循环查询的图，我们可以看到，左表的每一条记录都会对右表进行一次扫表，扫表的过程其实也就是从内存读取数据的过程，那么这个过程其实是比较消耗性能的。

所以缓存块嵌套循环连接算法意在通过一次性缓存外层表的多条数据，以此来减少内层表的扫表次数，从而达到提升性能的目的。如果无法使用Index Nested-Loop Join的时候，数据库是默认使用的是Block Nested-Loop Join算法的。

当level 表的 user_id 不为索引的时候，默认会使用Block Nested-Loop Join算法，匹配的过程类似下图。

注意：

1、使用Block Nested-Loop Join 算法需要开启优化器管理配置的optimizer_switch的设置block_nested_loop为on 默认为开启，如果关闭则使用Simple Nested-Loop Join 算法；

通过指令：Show variables like ‘optimizer_switc%’; 查看配置

2、设置join buffer 的大小

通过join_buffer_size参数可设置join buffer的大小

指令：Show variables like ‘join_buffer_size%’;

总结#

不论是Index Nested-Loop Join 还是 Block Nested-Loop Join 都是在Simple Nested-Loop Join的算法的基础上进行优化，这里 Index Nested-Loop Join 和Nested-Loop Join 算法是分别对Join过程中循环匹配次数和IO 次数两个角度进行优化。

Index Nested-Loop Join 是通过索引的机制减少内层表的循环匹配次数达到优化效果，而Block Nested-Loop Join 是通过一次缓存多条数据批量匹配的方式来减少内层表的扫表IO次数，通过 理解join 的算法原理我们可以得出以下表连接查询的优化思路。

1、永远用小结果集驱动大结果集(其本质就是减少外层循环的数据数量)

2、为匹配的条件增加索引(减少内层表的循环匹配次数)

3、增大join buffer size的大小（一次缓存的数据越多，那么内层包的扫表次数就越少）

4、减少不必要的字段查询（字段越少，join buffer 所缓存的数据就越多）

18. 堆组织表，索引组织表和索引聚簇表#

堆表#

• 堆就是无序数据的集合,索引就是将数据变得有序,在索引中键值有序,数据还是无序的
• 数据存放在数据里面,索引存放在索引里
• 堆表中,主键索引和普通索引一样的,叶子节点存放的是指向堆表中数据的指针（可以是一个页编号加偏移量）,指向物理地址,没有回表的说法
• 堆表中,主键和普通索引基本上没区别,和非空的唯一索引没区别
• mysql 的 myisam 引擎，oracle pg 都支持的是堆表

索引组织表#

• innodb 引擎支持的就是索引组织表
• 对于主键的索引,页子节点存放了一整行所有数据,其他索引称为辅助索引(二级索引),它的页子节点只是存放了键值和主键值
• 主键包含了一张表的所有数据,因为主键索引的页子节点中保存了每一行的完整记录,包括所有列。如果没有主键,MySQL会自动帮你加一个主键,但是对用户不可见
• innodb中数据存放在聚集索引中,换言之,按照主键的方式来组织数据的
• 其他索引(唯一索引,普通索引)的页子节点存放该索引列的键值和主键值
• 不管是什么索引非页子节点存放的存放的就是键值和指针,不存数据,这个指针在innodb中是6个bit,键值就看数据大小了

索引聚簇表#

聚簇是指：如果一组表有一些共同的列，则将这样一组表存储在相同的数据库块中；聚簇还表示把相关的数据存储在同一个块上。

利用聚簇，一个块可能包含多个表 的数据。概念上就是如果两个或多个表经常做链接操作，那么可以把需要的数据预先存储在一起。

聚簇还可以用于单个表，可以按某个列将数据分组存储。

19. LRU List、Free List和Flush List#

数据库中的缓冲池是通过LRU（Latest Recent Used，最近最少使用）算法来进行管理的。即最频繁使用的页在LRU列表的前端，而最少使用的页在LRU列表的尾端。当缓冲池不能存放新读取到的页时，将首先释放LRU列表中尾端的页。

InnoDB存储引擎中，缓冲池中页的大小默认为16KB，同样使用LRU算法对缓冲池进行管理。稍有不同的是InnoDB存储引擎对传统的LRU算法做了一些优化。在InnoDB的存储引擎中，LRU列表中还加入了midpoint位置。新读取到的页，虽然是最新访问的页，但并不是直接放入到LRU列表的首部，而是放入到LRU列表的midpoint位置。这个算法在InnoDB存储引擎下称为midpoint insertion strategy。在默认配置下，该位置在LRU列表长度的5/8处。midpoint位置可由参数innodb_old_blocks_pct控制。

为什么不采用朴素的LRU算法，直接将读取的页放入到LRU列表的首部呢？
这是因为若直接将读取到的页放入到LRU的首部，那么某些SQL操作可能会使缓冲池中的页被刷新出，从而影响缓冲池的效率。常见的这类操作为索引或数据的扫描操作。这类操作需要访问表中的许多页，甚至是全部的页，而这些页通常来说又仅在这次查询操作中需要，并不是活跃的热点数据。如果页被放入LRU列表的首部，那么非常可能将所需要的热点数据页从LRU列表中移除，而在下一次需要读取该页时，InnoDB存储引擎需要再次访问磁盘。

LRU列表用来管理已经读取的页，但当数据库刚启动时，LRU列表是空的，即没有任何的页。这时页都存放在Free列表中。当需要从缓冲池中分页时，首先从Free列表中查找是否有可用的空闲页，若有则将该页从Free列表中删除，放入到LRU列表中。否则，根据LRU算法，淘汰LRU列表末尾的页，将该内存空间分配给新的页。当页从LRU列表的old部分加入到new部分时，称此时发生的操作为page made young，而因为innodb_old_blocks_time的设置而导致页没有从old部分移动到new部分的操作称为page not made young。可以通过命令SHOW ENGINE INNODB STATUS来观察LRU列表及Free列表的使用情况和运行状态。

20. Mysql的 CheakPoint技术#

缓冲池的设计目的为了协调CPU速度与磁盘速度的鸿沟。因此Checkpoint（检查点）技术的目的是解决以下几个问题：

• 缩短数据库的恢复时间；
• 缓冲池不够用时，将脏页刷新到磁盘；
• 重做日志不可用时，刷新脏页。

对于InnoDB存储引擎而言，其是通过LSN（Log Sequence Number）来标记版本的。而LSN是8字节的数字，其单位是字节。每个页有LSN，重做日志中也有LSN，Checkpoint也有LSN。

有两种Checkpoint，分别为：

• Sharp Checkpoint

• Fuzzy Checkpoint

Sharp Checkpoint#

Sharp Checkpoint发生在数据库关闭时将所有的脏页都刷新回磁盘，这是默认的工作方式，即参数innodb_fast_shutdown=1。

但是若数据库在运行时也使用Sharp Checkpoint，那么数据库的可用性就会受到很大的影响。故在InnoDB存储引擎内部使用Fuzzy Checkpoint进行页的刷新，即只刷新一部分脏页，而不是刷新所有的脏页回磁盘。

Fuzzy Checkpoint#

在InnoDB存储引擎中可能发生如下几种情况的Fuzzy Checkpoint：

• Master Thread Checkpoint
  Master Thread中发生的Checkpoint，差不多以每秒或每十秒的速度从缓冲池的脏页列表中刷新一定比例的页回磁盘。这个过程是异步的，即此时InnoDB存储引擎可以进行其他的操作，用户查询线程不会阻塞。

• FLUSH_LRU_LIST Checkpoint
  FLUSH_LRU_LIST Checkpoint是因为InnoDB存储引擎需要保证LRU列表中需要有差不多100个空闲页可供使用。

• Async/Sync Flush Checkpoint
  Async/Sync Flush Checkpoint指的是重做日志文件不可用的情况，这时需要强制将一些页刷新回磁盘，而此时脏页是从脏页列表中选取的。若将已经写入到重做日志的LSN记为redo_lsn，将已经刷新回磁盘最新页的LSN记为checkpoint_lsn。

• Dirty Page too much Checkpoint
  最后一种Checkpoint的情况是Dirty Page too much，即脏页的数量太多，导致InnoDB存储引擎强制进行Checkpoint。其目的总的来说还是为了保证缓冲池中有足够可用的页。其可由参数innodb_max_dirty_pages_pct控制

21 Mysql的Redo Undo BinLog#

MySQL中有六种日志文件，
分别是：重做日志（redo log）、回滚日志（undo log）、二进制日志（binlog）、错误日志（errorlog）、慢查询日志（slow query log）、一般查询日志（general log），中继日志（relay log）。

重做日志Redo log#

作用：

　　1. 确保事务的持久性。
　　2. 防止在发生故障的时间点，尚有脏页未写入磁盘，在重启mysql服务的时候，根据redo log进行重做，从而达到事务的持久性这一特性。

内容：
物理格式的日志，记录的是物理数据页面的修改的信息，其redo log是顺序写入redo log file的物理文件中去的。

什么时候产生：
事务开始之后就产生redo log，redo log的落盘并不是随着事务的提交才写入的，而是在事务的执行过程中，便开始写入redo log文件中。

什么时候释放：
当对应事务的脏页写入到磁盘之后，redo log的使命也就完成了，重做日志占用的空间就可以重用（被覆盖）。

回滚日志 Undo log#

作用：
　　保存了事务发生之前的数据的一个版本，可以用于回滚，同时可以提供多版本并发控制下的读（MVCC），也即非锁定读

内容：
　　逻辑格式的日志，在执行undo的时候，仅仅是将数据从逻辑上恢复至事务之前的状态，而不是从物理页面上操作实现的，这一点是不同于redo log的。

什么时候产生：
　　事务开始之前，将当前是的版本生成undo log，undo 也会产生 redo 来保证undo log的可靠性

什么时候释放：
　　当事务提交之后，undo log并不能立马被删除，
　　而是放入待清理的链表，由purge线程判断是否由其他事务在使用undo段中表的上一个事务之前的版本信息，决定是否可以清理undo log的日志空间。

二进制日志（binlog）：#

作用：
　　1，用于复制，在主从复制中，从库利用主库上的binlog进行重播，实现主从同步。
　　2，用于数据库的基于时间点的还原。
内容：
　　逻辑格式的日志，可以简单认为就是执行过的事务中的sql语句。
　　但又不完全是sql语句这么简单，而是包括了执行的sql语句（增删改）反向的信息，
　　也就意味着delete对应着delete本身和其反向的insert；update对应着update执行前后的版本的信息；insert对应着delete和insert本身的信息。
　　在使用mysqlbinlog解析binlog之后一些都会真相大白。
　　因此可以基于binlog做到类似于oracle的闪回功能，其实都是依赖于binlog中的日志记录。

什么时候产生：
　　事务提交的时候，一次性将事务中的sql语句（一个事物可能对应多个sql语句）按照一定的格式记录到binlog中。
　　这里与redo log很明显的差异就是redo log并不一定是在事务提交的时候刷新到磁盘，redo log是在事务开始之后就开始逐步写入磁盘。
　　因此对于事务的提交，即便是较大的事务，提交（commit）都是很快的，但是在开启了bin_log的情况下，对于较大事务的提交，可能会变得比较慢一些。
　　这是因为binlog是在事务提交的时候一次性写入的造成的，这些可以通过测试验证。

什么时候释放：
　　binlog的默认是保持时间由参数expire_logs_days配置，也就是说对于非活动的日志文件，在生成时间超过expire_logs_days配置的天数之后，会被自动删除。

分布式算法#

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

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

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

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

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

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

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中，协调者发起一个提议，分别问询各参与者是否接受，如下图：

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

在阶段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消息之后，执行事务的中断。

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)

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

4. 将其他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认可后，那么该议案成功

运作流程#

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 演化过程如下：

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 状态了。