xiaohanliang
Database
DatabaseDockerGolangNetworkOS
Database
DatabaseDockerGolangNetworkOS
  • review
  • MySQL
    • 0. 索引就是树吗
    • 1. 索引是怎么发挥作用的
    • 2. 聊聊怎么估时间
    • 3. 主键玄学
    • 4. 事务的执行过程@ACD
    • 5. MVCC就是用undolog回退
    • 6. 事务如何彼此隔离@I
    • 7. 如何人为的制造死锁
    • 8. 引擎是干什么的
    • 9. 主从复制怎么做到的
    • 10. 寻找同步起始点GTID
    • 11. 预解析Statement
  • Redis
    • 0. Hash@数据结构
    • 1. ZSet@数据结构
    • 2. 场景与玩法@数据结构
    • 3. 可能的风险点
    • 4. Redis的落盘
    • 5. 关于效率的讨论
    • 6. 主从模式@集群化
    • 7. [WIP]Proxy实现@集群化
    • 8. 标准玩法@集群化
  • KV/Distributed
    • 0. 面临的问题
    • 1.Raft@原理
    • 2. LSM@原理
    • 3. [WIP]分布式事务@原理
Powered by GitBook
On this page
  • Introduction
  • 一次写操作的例子
  • AppendEntries RPC
  • RequestVote RPC
  • etcd集群数据一致性
  • 为什么会出现日志不一致
  • 日志不一致的风险
  • 强主节点的风险
  • 新上任的日志同步
  • 总结
  • 为什么需要分布式集群
  • 但是MySQL也可以搞集群

Was this helpful?

  1. KV/Distributed

1.Raft@原理

Previous0. 面临的问题Next2. LSM@原理

Last updated 4 years ago

Was this helpful?

Introduction

Raft算法存在于分布式存储集群里, 通俗说就是我们有好多个节点在一起, 这么多节点里包含了一个主节点与一大堆从节点, 算是一个数据库. 而算法本身用于保证这么多个节点之间的一致性, 就是说大家存储的数据也许某个时刻下不太一样, 但最终会是一模一样的. 我们接下来会通过一次数据库写操作来说明一些定义与概念.

一次写操作的例子

客户端的写请求只能由主节点受理, 从节点仅受理读操作. 客户端通过RPC调用向主节点发起写请求. 这个请求发给主节点以后, 主节点会往自己的日志里追加一个条目. 接着它会给所有的从节点通过AppendEntriesRPC, 要求他们也添加一下这个条目.

这些人有的会收到, 有的不会收到, 收到的人也往自己的日志里追加这个条目, 然后回复一个OK消息给主节点. 等主节点收到半数以上的人的OK时, 主节点认为时机已经成熟, 于是执行(commit)这个条目, 并返回ACK给从节点, 返回ACK给客户端, 代表请求已经执行

从这里我们能看出: 一个写命令就是一个日志条目, 在我们收到命令后不会立刻执行, 而是转换成日志, 随后我们应用(commit)这个日志, 这才算命令被执行了. log index + term + command.

  • logIndex + term: 表示日志序号以及日志产生的任期

  • command: 日志要求修改那一条数据

AppendEntries RPC

Raft中很多需要做的事情都通过ARPC实现, 可以拿来:

  • 心跳与领导人确认: Term字段. 在后面的竞选环节我们可以看到, 一旦超过一定时间没有收到心跳, 我们就默认主节点宕机, 从节点开始竞选, 一个节点一旦当选就会开始广播心跳包

  • 日志一致性校验: log字段. 在后面的日志一致性校验里我们可以看到, 领导人会发上一条日志的序号, 如果上一条日志缺失, 这就说明这个从节点日志有点问题, 于是主从开始同步日志, 具体过程见于一致性校验

  • 追加日志: [ ] Entries字段: 里面是一个一个的日志

  • 让从节点提交日志: leaderCommit: 这个就说明了从节点会在什么时候提交一条日志, 主节点为每一个节点维护一个他已经commit的序号, 如果这个数字大于自己维护的commitedId, 从节点就会将日志一直提交到leaderCommit.

RequestVote RPC

我们都知道如果节点挂了, 那么从节点会晋升为新主节点. 每个从节点有一个随机的"超时时间", 如果超过这个时间还没收到主节点的心跳包, 就认为主节点已挂, 自己将自己的term+1, 开始竞选拉票. 每个节点都有一票, 参选人会先把票投给自己, 然后通过RequestVote RPC找别人拉票. 如果拉到了超过50%的票就算成功. 这里面有几个问题:

我们要求50%才能当选, 但如果10个人竞选那么不见得有任何人能拿到50%这么多票. 这也是我们设置随机超时时间的原因, 这样大家不会一起开始拉票, 而是你先拉, 我再拉的模式, 总会有一个人选上的.

当选的人会播报自己当选的消息, 其他参选人收到这条消息会将信将疑的打开这条消息, 发现term任期正确, 就将自己参选人的身份改回从节点

etcd集群数据一致性

注意一下上面有个nextIndex字段非常有趣, 我们从这里展开说说, etcd集群数据的一致性是怎么保证的. 试想一个问题, 我们说etcd集群的数据存储会保证最终它们是一致的, 怎么保证的这一点?

  • 如果大家初始数据相同, 又应用了相同的日志, 那么到最后大家数据也是相同的.

  • 那么etcd集群的数据一致性的问题就被转换成: 如何保证每个节点上日志到最后都是一样的

为什么会出现日志不一致

我们都知道所有的日志(写命令)都是从主节点发往从节点的. 只要超过半数人回复OK以后, 主节点就会执行这条命令, 随后从节点也执行了这条命令. 那么那些没有回复OK的人呢? 他们可能正在遭遇网络故障, 他们甚至都不一定收到了这条消息. 此时不同节点因为执行了不同的命令而产生了数据不一致的问题

除了这个不一致, 如果假设主节点产生了三条日志, 但是产生完了还没来得及日志分发就立刻宕机, 那么就会导致主节点产生了一些别人都没有的日志.

  • 回答第一个问题:

    • 如果主节点执行了命令, 那么代表这条日志在大多数节点上都是存在的, 只有少数节点上没有这条日志. 主节点为每一个从节点分别维护了一个index, 对于那些响应了A-RPC的从节点, index会加一, 而某个人没响应, 主节点会不停尝试直到它响应.

  • 回答第二个问题:

    • 主节点虽然是产生了一些别人没有的日志, 但这些命令并不会执行. 因为日志没有分发, 自然都不会执行.

日志不一致的风险

我们已经知道了不同节点之间的确会出现日志不一致的问题, 甚至会出现数据都不一致的问题, 那一致性怎么保证呢? 假设A节点刚刚网络故障因此日志/数据跟别人都不一样.

某个时刻下节点A突然恢复正常, 与主节点之间的通讯也恢复了, 主节点之前因为没联络上节点A而在不停调用ARPC, 也突然联络上了, 于是主节点会让这个从节点慢慢补上所有的缺掉的日志

强主节点的风险

我们从上面的内容可以发现, Raft模式下都是主节点把自己的日志分发给从节点, 也就是默认了主节点日志一定正确, 这种套路看起来没问题, 假设某个时刻下主节点宕机, 现在我们不得不重新选一个主节点了, 那么这个新主节点日志一定正确吗? 如果新主节点日志不正确, 那么它会带的所有从节点日志全都跑偏.

一个节点想从普通的从节点晋升为主节点, 必须有超过50%的从节点同意, 为了避免跑偏的风险, RequestVote RPC的调用方(参选人)会带上自己最新的log index以及term, 选民收到了这个请求以后会对比参选人的日志与自己的日志, 如果参选人的日志更新, 则贡献出自己的一票, 否则拒绝, 怎么定义日志的"新与旧"?

  • 如果自己最新日志的term大于参选人的term, 则自己的日志更新

  • 如果term相等, 但是自己的logindex更大, 则自己的日志更新

我们再回到刚刚节点A的故事里, 节点A日志不全, 但他现在也想参选, 于是它通过RequestVote RPC拉票, 但是刚刚节点A没收到的日志有超过50%的节点都有, 这些节点全都会拒绝他的拉票请求, 因此节点A根本不可能晋升.

新上任的日志同步

从新主节点上任, 他的日志最新, 超级无敌新, 开始给别人发A-RPC, 但是别人没有他新, 他因为是新主节点, 因此也不知道那些节点, 缺少那些日志. 于是我们的AppendEntries还能这么用:

主: 你好, 添加一下这条日志xxx, index=100 从: 不行 主: 那写99行吗? 从: 不行 主: 写98行吗? 从: 好的 ...

然后主节点发现从节点最新是98, 找到了分歧的第一个点, 然后主节点通过一条A-RPC一次性推来98-100的所有日志, 完成了新官上任的第一次同步.

总结

为什么需要分布式集群

林林总总我们说了这种算法的工作原理过程, 有点复杂的同时有点有趣. 但是回头想想为什么要搞这一套, 它解决了MySQL的什么问题, 出于什么背景什么目的, 为什么etcd成为了云原生的标配.

写过程序的都知道, 程序的瓶颈基本取决于你读数据有多快, 对应MySQL就是你的SQL有多快. 但是数据一旦暴涨查SQL速度可以说直线下降, 于是这个时候我们开始优化SQL语句, 加索引, 读写分离, 分库分表那一套就出来了.

或者如果你有一种数据库, 随着实例数量的增多查询表现也变好. 这下数据越多, 我们就增加实例数量. 这基本对照出了云/容器那一套里的扩容, 没有顾虑扩就完事. 但是MySQL你就玩不了这一套了, MySQL实例变多你的程序也得跟着改.

但是MySQL也可以搞集群

MySQL的主从是一种鬼畜弱主从, 因为不受Raft控制, 所以主节点拿到命令直接执行, 然后过段时间将log发给从节点执行, 这样造成的问题是:

  • raft算法的共识机制会导致任意时刻下大部分节点数据都是一致的, MySQL集群没有共识控制就直接执行, 导致集群里其实只有你自己执行了这条语句

  • raft算法每条语句通过socket通信发出去, 而MySQL集群通过将log文件发出去让别人执行, 这个文件是MySQL集群间同步的唯一依据, 换句话说只要文件不对了或者没了, 集群同步就gg了