• 2021-09-06

    关于多写入点数据库集群的一些想法

    Views: 23243 | No Comments

    在分布式数据库系统领域, 多主(多写入点, Leader-less)是一个非常诱人的特性, 因为客户端可以随机请求任何一个节点. 这种可随机选择访问点(写入点)的特性, 使得系统的高可用唾手可得, 因为当客户端发现某个节点出故障时, 更换另一个节点重试就可以了, 只要系统没有完全宕机, 几次重试之后一定成功, 也就可以达到百分之百高可用.

    传统的 Basic Paxos 常常被误认为是 Leader-less 的, 也即多主, 但 Basic Paxos 只能用于确定一个实例的共识, 真正落地还需要结合日志复制状态机, 如果复制组(多节点)不指定 Leader 的话, 那么就会出现争取同一个位置的日志的情况, 也就是在尝试达成这个位置的日志的共识时出现活锁. 这种多节点争取同一个位置的情况, 在实践上将导致系统不可用, 因为, 通常自称采用 Paxos 的多副本数据库系统, 依然要显式指定 Leader, 并不是真正 Leader-less 的.

    Continue reading »

    Posted by ideawu at 2021-09-06 20:51:04 Tags: ,
  • 2021-09-05

    什么是分布式一致性

    Views: 20085 | No Comments

    在工程实践上, 分布式一致性和多副本有关系, 如果没有多副本, 就没有分布式一致性的问题.

    多副本的定义: 多副本可以放在多台机器上, 也可以放在同一个进程内的不同内存地址内, 或者一个副本在内存, 一个副本在硬盘. 只要同一个对象出现在多处, 或者在多处被引用, 就是多副本.

    各个副本的写入操作序列必须先经过共识, 按同样的顺序写入, 因此所有副本的状态将是最终一致的(相同). 但是, 有可能单独地读取某个副本, 这就导致读操作在不同副本上发生的顺序并不相同, 这显然会导致最终结果不一致(符合预期), 因为我们本能地知道, 顺序决定结果.

    例如, 先写后读与先读后写, 显然读出来的结果不一样, 这个很显然. 因为日志序列的复制和执行必然是异步的, 绝对不可能所有副本在同一个时间点同时写入, 必然有一个时间差, 这也是很显然的. 因此, 如果轻率地去读取不同副本, 将可能导致读取的结果不同, 因为某个写入操作可能只在某个副本上执行了, 而在另一个副本上还没有执行, 所以读取的结果不同, 这是很显然的.

    Continue reading »

    Posted by ideawu at 2021-09-05 10:49:53 Tags: ,
  • 2021-08-07

    Paxos 和 Raft 的结构差异

    Views: 8105 | No Comments

    如果用面向对象的方法来分析 Paxos 和 Raft 的对象层次结构关系, 我们会发现, 两者其实没那么多差异, 或者说, 这种差异我们平时在做面向对象建模和编写代码时经常使用.

    Basic Paxos

    type Entry struct {
    	promised_num int64
    	proposal_num int64
    	proposal_value []byte
    }
    

    Multi Paxos

    type Node struct {
    	entries []struct {
    		promised_num int64
    		proposal_num int64
    		proposal_value []byte
    	}
    }
    

    Raft

    type Node struct {
    	currentTerm int64 // promised_num
    	entries []struct {
    		term  int64   // proposal_num
    		value []byte  // proposal_value
    	}
    }
    

    首先, Basic Paxos 关注的是一条日志(Log Entry), 和 Raft 不是一个层次的东西. Multi Paxos 和 Raft 的结构类似, 本质上都是"日志复制状态机".

    Continue reading »

    Posted by ideawu at 2021-08-07 09:09:04 Tags: ,
  • 2021-08-05

    什么是日志复制状态机?

    Views: 13016 | No Comments

    日志复制状态机, 也叫复制状态机, 是分布式数据库领域最重要的基石之一. 当前市面上所有实用的分布式数据库, 几乎都是用日志复制状态机技术来实现多副本. 像 MySQL 的主从同步, Redis 的主从同步, SSDB 的主从同步等, 是大家非常熟知的日志复制状态机的例子. 而更复杂的共识算法 Paxos, 以及最流行的分布式一致性协议 Raft, 前者的实现基本离不开日志复制状态机, 后者则是直接以日志复制状态机作为其核心组成.

    那么, 什么是日志复制状态机呢? 首先, 我们先理解什么状态机. 状态机基于一个定理, 这个定理是显然的, 不需要证明的. 那就是, 如果两个被称为状态机的对象, 它们按相同的顺序执行(Apply)相同的指令序列, 那么, 指令执行完毕后, 这两个状态机的状态将必然是相同的(一致的).

    指令序列也称为日志序列, 一般每一条日志带有一个唯一整数编号以确定顺序. 如果日志序列被复制到不同的地方, 然后由状态机执行, 那么分布在不同地方的状态机的状态就一致了. 这种技术便称为日志复制状态机. 状态机对象便是一个副本, 例如是一个数据库实例.

    Continue reading »

    Posted by ideawu at 2021-08-05 21:37:58 Tags: , ,
  • 2021-07-30

    为什么极少有开源的Paxos库?

    Views: 9008 | No Comments

    你是不是也很奇怪, Paxos 既然被称为唯一的共识算法(分布式一致性算法), 是分布式系统的基石, 那么为什么极少看到开源的 Paxos 库呢? 反观 Raft, 有 etcd 开源的 go 语言写的库, 有 PingCap(tidb)开源的 Rust 语言写的, 还有百度, 阿里等等公司开源的各种语言的库. 既然 Paxos 那么牛逼, 为什么江湖中只有它的传说, 却从来没有人见过它的身影呢?

    原因很简单, Paxos(准确的说是 Basic Paxos) 是共识算法, 用于对一个实例的状态形成共识, 这个用途和工程上的一致性协议基本是金属铁块和汽车的关系. 工程师对 Paxos 最大的疑问经常是:

    • 什么是实例? 一整个 database 是一个实例吗? 一个 key 是实例吗?
    • 共识是什么? 是一个 key 对应的 value 吗? 形成共识之后就不能更改? 有什么用?

    Continue reading »

    Posted by ideawu at 2021-07-30 00:24:42 Tags: ,
  • 2021-07-25

    Raft ReadIndex 有什么神奇之处?

    Views: 4689 | No Comments

    其实, 工程上的一致性读, 本质是操作的先后顺序. 只要让读操作在某一个节点上发生的顺序, 在我们预想的那个写操作之后, 这时只依赖该节点, 就能保证一次正确的一致性读. 例如, 假设我们知道某次写操作的序号是 idx, 对应某条编号为 idx 的日志, 只要我们等某个节点 apply 了这条日志, 然后直接读状态机就可以了, 就能满足强一致性的定义.

    但是, 虽然可以要求客户端请求读操作时带上它所依赖的那次写操作的编号, 但工程上并不合理, 所以, 只能由集群节点自己找到那次写操作的编号.

    收到读请求的节点, 向其它节点发送一个请求, 询问最新的日志编号是多少, 如果收到全部节点的回应, 那么自然就知道了. 要求全部节点回应, 不能容忍少数节点宕机, 这种方案还需要优化. 其实, 超过半数回应就可以了.

    简单的说, 就是任何一个 Raft 成员, 无论 Leader 还是 Follower, 收到读请求时, 通过某些手段获知当前集群最大的 commit index, 然后等待自己 apply 等于或者超过这个 commit index 之后, 直接读本地状态机.

    大多数人可能并不知道, 即使是 Leader, 直接读本地状态机, 也是有可能违反"强一致性"的定义的. 因为, 除非站在上帝视角, 否则, 一个 Leader 节点只能是"自认为自己是 Leader", 既然是自认为是, 就有可能错认.

    所以, 如果读本地状态机, 就必须停止等待, 确保状态机已经 apply 了"那一条日志"之后才能读. 具体是哪一条日志? 前面说了.

    相关文章: PingCap - 线性一致性和 Raft

    Posted by ideawu at 2021-07-25 19:45:34 Tags:
|<<<1234>>>| 1/4 Pages, 24 Results.