日志复制状态机, 也叫复制状态机, 是分布式数据库领域最重要的基石之一. 当前市面上所有实用的分布式数据库, 几乎都是用日志复制状态机技术来实现多副本. 像 MySQL 的主从同步, Redis 的主从同步, SSDB 的主从同步等, 是大家非常熟知的日志复制状态机的例子. 而更复杂的共识算法 Paxos, 以及最流行的分布式一致性协议 Raft, 前者的实现基本离不开日志复制状态机, 后者则是直接以日志复制状态机作为其核心组成.
那么, 什么是日志复制状态机呢? 首先, 我们先理解什么状态机. 状态机基于一个定理, 这个定理是显然的, 不需要证明的. 那就是, 如果两个被称为状态机的对象, 它们按相同的顺序执行(Apply)相同的指令序列, 那么, 指令执行完毕后, 这两个状态机的状态将必然是相同的(一致的).
指令序列也称为日志序列, 一般每一条日志带有一个唯一整数编号以确定顺序. 如果日志序列被复制到不同的地方, 然后由状态机执行, 那么分布在不同地方的状态机的状态就一致了. 这种技术便称为日志复制状态机. 状态机对象便是一个副本, 例如是一个数据库实例.
你是不是也很奇怪, Paxos 既然被称为唯一的共识算法(分布式一致性算法), 是分布式系统的基石, 那么为什么极少看到开源的 Paxos 库呢? 反观 Raft, 有 etcd 开源的 go 语言写的库, 有 PingCap(tidb)开源的 Rust 语言写的, 还有百度, 阿里等等公司开源的各种语言的库. 既然 Paxos 那么牛逼, 为什么江湖中只有它的传说, 却从来没有人见过它的身影呢?
原因很简单, Paxos(准确的说是 Basic Paxos) 是共识算法, 用于对一个实例的状态形成共识, 这个用途和工程上的一致性协议基本是金属铁块和汽车的关系. 工程师对 Paxos 最大的疑问经常是:
在开发复杂系统时, 有判断力(决断力), 懂得去选择简单正确的架构和方案, 先把系统做出来. 大部分的程序员并没有这种思考决断能力. 如果让他们自己做决策, 他们会陷入思维混乱, 面对多个选项时优柔寡断. 几乎每一次内心将要下决断, 都会被"性能优化"思想给驳回.
虽然大部分程序员没有开发一个完整系统的能力, 但是, 仅仅用最简单的方案把系统做出来, 还不是终点. 只要方案足够简洁, 第一版一般能满足短期需求, 也许不能满足. 但业务的发展要求系统必须持续优化和升级, 这就要求程序员持续投入体力活优化系统. 大多数的优化, 就是不断地增加几个判断, 多封装几个类. 系统的维护和改进, 大部分是体力活, 程序员如果不具备耐力和恒心, 将会很快放弃.
其实, 工程上的一致性读, 本质是操作的先后顺序. 只要让读操作在某一个节点上发生的顺序, 在我们预想的那个写操作之后, 这时只依赖该节点, 就能保证一次正确的一致性读. 例如, 假设我们知道某次写操作的序号是 idx, 对应某条编号为 idx 的日志, 只要我们等某个节点 apply 了这条日志, 然后直接读状态机就可以了, 就能满足强一致性的定义.
但是, 虽然可以要求客户端请求读操作时带上它所依赖的那次写操作的编号, 但工程上并不合理, 所以, 只能由集群节点自己找到那次写操作的编号.
收到读请求的节点, 向其它节点发送一个请求, 询问最新的日志编号是多少, 如果收到全部节点的回应, 那么自然就知道了. 要求全部节点回应, 不能容忍少数节点宕机, 这种方案还需要优化. 其实, 超过半数回应就可以了.
简单的说, 就是任何一个 Raft 成员, 无论 Leader 还是 Follower, 收到读请求时, 通过某些手段获知当前集群最大的 commit index, 然后等待自己 apply 等于或者超过这个 commit index 之后, 直接读本地状态机.
大多数人可能并不知道, 即使是 Leader, 直接读本地状态机, 也是有可能违反"强一致性"的定义的. 因为, 除非站在上帝视角, 否则, 一个 Leader 节点只能是"自认为自己是 Leader", 既然是自认为是, 就有可能错认.
所以, 如果读本地状态机, 就必须停止等待, 确保状态机已经 apply 了"那一条日志"之后才能读. 具体是哪一条日志? 前面说了.
相关文章: PingCap - 线性一致性和 Raft
有不少对分布式系统感兴趣的同学问我:"Paxos 算法是最基础的分布式共识算法, 但是, 我看完之后, 似懂非懂. Paxos 到底应该如何进行工程落地呢?"
业界对 Paxos 算法有着非常高的美誉, 一方面是因为 Paxos 的开创性, 更多的原因, 至少我所知道的, 许多人之所以赞美 Paxos, 主要是因为"看不懂". 说看不懂似乎不对, 许多人有时觉得自己懂 Paxos, 有时觉得不懂, 今天懂, 明天不懂, 但是必须懂. 要命的是,没法落地, 即使看懂了学完了, 一行代码也写不出来, 写出来了, 代码也没实际意义, 说句俗话, 就是"没啥卵用".
回复那些对分布式共识算法(Consensus)和分布式系统感兴趣的同学的话: Paxos 的落地就是选主(Leader Election)和日志复制状态机(Log Replicated State Machine). 也就是我一直说, 不想再说, 但又不得不再重复一次的话: 就是 Raft 做的那样!
俗话说:
Keep It Simple, Stupid!
由于大部分新手程序员在从学生转换成为工程师之前, 都经过所谓的"算法"编程训练, 特别是不少人还主动进行大量的"刷题"行为, 因此, 对"性能"的追求被潜移默化地植入了所有程序员的基因, 这就造成了程序员往往把细节上的所谓性能优化放到第一优先的位置.
这种片面追求细节性能, 从而缺少大局观的思维, 其实是非常错误的. 比如 C++ 程序员, 几乎把性能优化等同于减少内存拷贝和无锁(lock free), 认为内存拷贝等于性能差, 认为加锁等于阻塞, 因此, C++ 程序员的代码主要在语法和语句层面上做优化, 逻辑非常别扭. 这种观念是非常落后的, 没有大局观, 这种程序员的技术视野极其狭窄.
根据我多年的软件开发经验, 我想针对那些认为"性能最重要"的程序员, 表明一个事实: 所有的代码层面性能优化, 必然以增加逻辑分支, 增加更多的 Indirection 作为代价.
什么意思呢? 也就是说, 所谓的性能优化, 必然会在代码里增加 if 分支, 增加新的类, 从而造成代码行数膨胀, 类的数量变多, 类的交叉调用关系变得更加复杂混乱. 这些后果都是非常负面的, 甚至无法抵消减少1%内存拷贝带来的性能提升.
|
带有此标志, 表示本博客已经被加入到IT牛人博客聚合网站. |
Loading ...