Last updated Unknown

（水平分片 垂直分片）

• 分片算法

• 复制

  • 单主复制
  • 多主复制

• 心跳检测法
• Gossip 协议检测
• φ 值检测

• 评价存储引擎

  • 缓存形式
  • 可变/不可变数据
  • 排序

• 数据文件 索引数据表SSTable
• 数据缓冲 跳表
• 查询路径 布隆过滤

• 两阶段提交

  • 协调器与参与者

• 三阶段提交

  • 三阶段相比于两阶段主要是解决协调器在准备阶段失败中描述的阻塞状态。它的解决方案是在两阶段中间插入一个阶段，第一阶段还是进行投票，第二阶段将投票后的结果分发给所有参与者，第三阶段是提交操作。其关键点是在第二阶段，如果协调者在第二阶段之前崩溃无法恢复，参与者可以通过超时机制来释放该事务。一旦所有节点通过第二阶段，那么就意味着它们都知道了当前事务的状态，此时，不管协调者还是参与者崩溃都不会影响事务执行。
  • 问题：在第二阶段的时候，一些参与者与协调器失去联系，它们由于超时机制会中断事务。而如果另外一些参与者已经收到可以提交的指令，就会提交数据，从而造成脑裂的情况。

• Percolator 乐观事务

  • TiDB 乐观事务冲突处理

• Spanner

  • TrueTime 和 Paxos Group

    • 读写事务：该事务是通过分布式锁实现的，并发性是最差的。且数据写入每个分片 Paxos Group 的主节点。
    • 只读事务：该事务是无锁的，可以在任意副本集上进行读取。但是，如果想读到最新的数据，需要从主节点上进行读取。主节点可以从 Paxos Group 中获取最新提交的时间节点。
    • 快照读：顾名思义，Spanner 实现了 MVCC 和快照隔离，故读取操作在整个事务内部是一致的。同时这也暗示了，Spanner 可以保存同一份数据的多个版本。

  • 隔离方面，Spanner 实现了 SSI，也就是序列化的快照隔离。其方法就是上文提到的 lock table。该锁是完全的排他锁，不仅仅能阻止并发写入数据，写入也可以阻止读取，从而解决快照隔离写偏序的问题。

• Calvin 与 FaunaDB

  • Calvin 的方案是让事务在每个副本上的执行顺序达到一致，那么执行结果也肯定是一致的。这样做的好处是避免了众多事务之间的锁竞争，从而大大提高了高并发度事务的吞吐量。同时，节点崩溃不影响事务的执行。因为事务执行步骤已经分配，节点恢复后从失败处接着运行该事务即可，这种模式使分布式事务的可用性也大大提高。目前实现了 Calvin 事务模式的数据库是 FaunaDB。
  • 同时 Calvin 事务有 read set 和 write set 的概念。前者表示事务需要读取的数据，后者表示事务影响的数据。这两个集合需要在事务开始前就进行确定，故Calvin 不支持在事务中查询动态数据而后影响最终结果集的行为。这一点很重要，是这场战争的核心。

• 基于消息队列

  • 先让订单系统把要发送的消息持久化到本地数据库里，然后将这条消息记录的状态设置为代发送，紧接着订单系统再投递消息到消息队列，优惠券系统消费成功后，也会向消息队列发送一个通知消息。当订单系统接收到这条通知消息后，再把本地持久化的这条消息的状态设置为完成

• 高可用、强一致

  • 主要分为四个部分：HTTP Server、Store、Raft 以及 WAL（预写式日志）。

    • Store：用于处理 Etcd 支持的各类功能的事务，包括数据索引、节点状态变更、监控与反馈、事件处理与执行等等，是 Etcd 对用户提供的大多数 API 功能的具体实现。
    • Raft：Raft 强一致性算法的具体实现，是 Etcd 的核心。
    • WAL：Write Ahead Log（预写式日志），是 Etcd 的数据存储方式。除了在内存中存有所有数据的状态以及节点的索引，Etcd 还通过 WAL 进行持久化存储。WAL 中，所有的数据提交前都会事先记录日志。Snapshot 是为了防止数据过多而进行的状态快照。Entry 表示存储的具体日志内容。
    • HTTP Server：用于处理客户端发送的 API 请求以及其它 Etcd 节点的同步与心跳信息请求。
    • 通常，一个用户的请求发送过来，会经由 HTTP Server 转发给 Store 进行具体的事务处理；如果涉及到节点的修改，则交给 Raft 模块进行状态的变更、日志的记录，然后再同步给别的 Etcd 节点以确认数据提交；最后进行数据的提交，再次同步。

  • 租约机制（TTL，Time To Live），Etcd 可以为存储的 Key-Value 对设置租约，当租约到期，Key-Value 将失效删除；同时也支持续约，通过客户端可以在租约到期之前续约，以避免 Key-Value 对过期失效；此外，还支持解约，一旦解约，与该租约绑定的 Key-Value 将失效删除；

  • Prefix 机制：即前缀机制，也称目录机制，如两个 Key 命名如下：key1=“/mykey/key1”，key2="/mykey/key2"，那么，可以通过前缀“/mykey”查询，返回包含两个 Key-Value 对的列表；

  • Watch 机制：即监听机制，Watch 机制支持监听某个固定的 Key，也支持监听一个范围（前缀机制），当被监听的 Key 或范围发生变化，客户端将收到通知；

  • Revision 机制：每个 Key 带有一个 Revision 号，每进行一次事务便加一，因此它是全局唯一的，如初始值为 0，进行一次 Put 操作，Key 的 Revision 变为1，同样的操作，再进行一次，Revision 变为 2；换成 Key1 进行 Put 操作，Revision 将变为 3。这种机制有一个作用，即通过 Revision 的大小就可知道写操作的顺序，这对于实现公平锁，队列十分有益。

• 应用场景

  • 服务发现

  • 消息发布和订阅

  • 分布式锁

    • 媲美业界“名宿”ZooKeeper
    • 通过前缀“/mylock” 查询，返回包含两个 Key-Value 对的 Key-Value 列表，同时也包含它们的 Revision，通过 Revision 大小，客户端可以判断自己是否获得锁，如果抢锁失败，则等待锁释放（对应的 Key 被删除或者租约过期），然后再判断自己是否可以获得锁
    • 多个客户端同时抢锁，根据 Revision 号大小依次获得锁，可以避免 “羊群效应” （也称“惊群效应”），实现公平锁
    • 如果抢锁失败，可通过 Prefix 机制返回的 Key-Value 列表获得 Revision 比自己小且相差最小的 Key（称为 Pre-Key），对 Pre-Key 进行监听，因为只有它释放锁，自己才能获得锁
    • Lease 机制可以保证分布式锁的安全性，为锁对应的 Key 配置租约，即使锁的持有者因故障而不能主动释放锁，锁也会因租约到期而自动释放

  • 集群监控与 Leader 竞选

• 范围分片和哈希分片

  • 一致性 Hash 算法

• Twitter 的 Snowflake（又名“雪花算法”）

  • 生成的是 64 位唯一 ID（由 41 位的 timestamp + 10 位自定义的机器码 + 13 位累加计数器组成）

• UUID/GUID（一般应用程序和数据库均支持）

• MongoDB ObjectID（类似 UUID 的方式）

失败模型、失败侦测、领导选举和一致性的合体

• 广播协议是一类将数据从一个节点同步到多个节点的协议。特别是其中的 Gossip 协议可以保障大规模的数据同步，而 Gossip 在正常情况下就是采用广播模式传播数据的

  • 原子广播协议：Zookeeper Atomic Broadcast（ZAB）。

• Proposer：Proposer 可以有多个，Proposer 提出议案（value）。所谓 value，可以是任何操作，比如“设置某个变量的值为 value”。不同的 Proposer 可以提出不同的 value。但对同一轮 Paxos 过程，最多只有一个 value 被批准。

• Acceptor：Acceptor 有 N 个，Proposer 提出的 value 必须获得 Quorum 的 Acceptor 批准后才能通过。Acceptor 之间完全对等独立。

• Learner：上面提到只要 Quorum 的 Accpetor 通过即可获得通过，那么 Learner 角色的目的就是把通过的确定性取值同步给其他未确定的 Acceptor。

• Multi-Paxos

  • 如果完全执行上面描述的过程，那性能消耗是任何生产系统都无法承受的，因此我们一般使用的是 Multi-Paxos 可以并发执行多个 Paxos 协议，它优化的重点是把 Propose 阶段进行了合并，这就引入了一个 Leader 的角色，也就是领导节点
  • replicated log：值被提交后写入到日志中。这种日志结构除了提供持久化存储外，更重要的是保证了消息保存的顺序性。而 Paxos 算法的目标是保证每个节点该日志内容的强一致性。
  • state snapshot：由于日志结构保存了所有值，随着时间推移，日志会越来越大。故算法实现了一种状态快照，可以保存最新的日志消息。当快照生成后，我们就可以安全删除快照之前的日志了。
  • 缺点：Multi-Paxos 随机性使得没有一个节点有完整的最新的数据，因此其恢复流程非常复杂，需要同步节点间的历史记录

• 节点三种状态Leader、 Follower、Candidate

• 一致性问题

  • 选举（Leader Election）当 Leader 宕机或者集群初创时，一个新的 Leader 需要被选举出来；

    • Candidate 收到超过半数节点的投票（N/2 + 1），它将获胜成为 Leader
    • 请求节点的 Term 大于自己的 Term，且自己尚未投票给其它节点，则接受请求，把票投给它，否则投给自己

  • 日志复制（Log Replication）Leader 接收来自客户端的请求并将其以日志条目的形式复制到集群中的其它节点，并且强制要求其它节点的日志和自己保持一致

    • 只有 Leader 节点能够处理客户端的请求（如果客户端的请求发到了 Follower，Follower 将会把请求重定向到 Leader），客户端的每一个请求都包含一条被复制状态机执行的指令。Leader 把这条指令作为一条新的日志条目（Entry）附加到日志中去，然后并行得将附加条目发送给 Followers，让它们复制这条日志条目。

      • 这时就会把 Follower 冲突的日志条目全部删除并且加上 Leader 的日志。一旦附加日志成功，那么 Follower 的日志就会和 Leader 保持一致

  • 安全性（Safety）：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其它服务器节点不能在同一个日志索引位置应用一个不同的指令。

    • 日志条目的传送是单向的，只从 Leader 传给 Follower，并且 Leader 从不会覆盖自身本地日志中已经存在的条目

• 主从服务器之间采用的是「读写分离」的方式，所有的数据修改只在主服务器上进行，然后将最新的数据同步给从服务器，这样就使得主从服务器的数据是一致的
• 主从服务器间的第一次同步的过程可分为三个阶段：第一阶段是建立链接、协商同步，第二阶段是主服务器同步数据给从服务器，第三阶段是主服务器发送新写操作命令给从服务器。之后双方之间就会维护一个 TCP 连接
• 网络断开又恢复后，从主从服务器会采用增量复制的方式继续同步，也就是只会把网络断开期间主服务器接收到的写操作命令，同步给从服务器
• 从节点是无法自动升级为主节点的，这个过程需要人工处理

• 哨兵其实是一个运行在特殊模式下的 Redis 进程，所以它也是一个节点。从“哨兵”这个名字也可以看得出来，它相当于是“观察者节点”，观察的对象是主从节点：监控、选主、通知。
• 哨兵节点通过 Redis 的发布者/订阅者机制，哨兵之间可以相互感知，相互连接，然后组成哨兵集群，同时哨兵又通过 INFO 命令，在主节点里获得了所有从节点连接信息，于是就能和从节点建立连接，并进行监控了

• 实现基础：分片 Slot（客户端分片和代理分片）采用哈希槽（Hash Slot），来处理数据和节点之间的映射关系。在 Redis Cluster 方案中，一个切片集群共有 16384 个哈希槽，这些哈希槽类似于数据分区，每个键值对都会根据它的 key，被映射到一个哈希槽中
• 节点通信原理（分布式一致性协议）：Gossip 算法ping、pong消息通信，通信节点选择过多虽然可以做到信息及时交换但成本过高。节点选择过少则会降低集群内所有节点彼此信息交换的频率，Gossip 协议需要兼顾信息交换实时性和成本开销。
• 故障转移：选举，但是有脑裂问题，由于网络问题，集群节点之间失去联系。主从数据不同步；重新平衡选举，产生两个主服务。等网络恢复，旧主节点会降级为从节点，再与新主节点进行同步复制的时候，由于会从节点会清空自己的缓冲区，所以导致之前客户端写入的数据丢失了 解决：当主节点发现从节点下线或者通信超时的总数量小于阈值时，那么禁止主节点进行写数据，直接把错误返回给客户端
• 集群规模超过百节点级别后，Gossip 协议的效率将会显著下降，通信成本越来越高 Gossip算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了Gossip的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。

• SET 命令有个 NX 参数可以实现「key不存在才插入」，EX/PX 设置其过期时间以预防死锁，key区分不同客户端

• 1 判断锁的 unique_value 是否为加锁客户端，是的话，才将 lock_key 键删除，解锁是有两个操作，Lua 脚本来保证解锁的原子性。 2 如果持有的锁已经因过期而释放（或者过期释放后又被其它客户端持有），则 Key 对应的 Value 将改变，释放锁的事务将不会被执行。

• 1 超时时间不好设置，如果锁的超时时间设置过长，会影响性能，如果设置的超时时间过短会保护不到共享资源。（先给锁设置一个超时时间，然后启动一个守护线程，让守护线程在一段时间后，重新设置这个锁的超时时间，实现复杂） 2 主从复制模式中数据是异步复制的，导致分布式锁的不可靠性。主节点获取到锁后，在没有同步到从节点时，主节点宕机了，此时新的主节点依然可以获取锁，所以多个应用服务就可以同时获取到锁。

• RedLock

  • 客户端和多个独立的主节点依次请求申请加锁，如果客户端能够和半数以上（>=N/2+1）的节点成功地完成加锁操作，那么我们就认为，客户端成功地获得分布式锁，否则加锁失败（t2-t1 < 锁的过期时间）（因此成功是两个条件）
  • 向所有 Redis 节点发起释放锁的操作lua脚本

• ZooKeeper分布式锁（如InterProcessMutex），能有效的解决分布式问题，不可重入问题，使用起来也较为简单
• ZooKeeper实现的分布式锁，性能并不太高。每次在创建锁和释放锁的过程中，都要动态创建、销毁瞬时节点来实现锁功能。大家知道，ZK中创建和删除节点只能通过Leader服务器来执行，然后Leader服务器还需要将数据同不到所有的Follower机器上，这样频繁的网络通信，性能的短板是非常突出的。