awesome-fenix
awesome-fenix copied to clipboard
fenixsoft
「Comment」https://icyfenix.cn/distribution/consensus/
state tranfer 的定义应该是直接传内存磁盘里的数据来保证不同机器间的一致性吧，可以参考6.824 课程第四讲 vmware fault tolerant 第 8-11 分钟的讲授内容。 mysql cluster 基于 binlog 的主从同步方式实际上也是基于 RSM 吧，即假设应用相同顺序的日志能够保证不同节点上的 mysql 实例达到相同状态？
@LebronAl state tranfer 的定义应该是直接传内存磁盘里的数据来保证不同机器间的一致性吧，可以参考6.824 课程第四讲 vmware fault tolerant 第 8-11 分钟的讲授内容。 mysql cluster 基于 binlog 的主从同步方式实际上也是基于 RSM 吧，即假设应用相同顺序的日志能够保证不同节点上的 mysql 实例达到相同状态？
State Tranfer的核心思想是“当状态发生变化后，应在主、从状态同步一致之后再接受新的外部输入”，这个思想就是文中例子“手工复制文件到几块备份硬盘”背后的逻辑。 Robert Morris教授在课程中的举例是“主内存中的数据变化了，将完整的拷贝复制到备份节点，备份节点保留完整的状态”。从内存中复制数据这是一个具体的例子，如同文中举例的将硬盘中的数据复制到其他硬盘，不应该将它当作是State Tranfer的定义来理解。 Operation Transfer（State Machine Replication）的核心思想是“基于状态机初始状态一致、接受到的指令序列一致，就会得到一致结果的特性，只需保证各直接点接收的操作指令的内容及顺序一致，即可保证子节点最终状态的一致，此时并不妨碍主节点继续接受外部输入”。 MySQL默认的binlog复制是Asynchronous Replication，这种是State Machine Replication实现无疑。而文中举例是Fully Synchronous Replication，不妨对比一下两种思想的差异来判断一下它哪种的实现。
State Tranfer 的核心思想是“当状态发生变化后，应在主、从状态同步一致之后再接受新的外部输入”
这个定义有可参考的文献吗？我查了一些文献，感觉学术界对此概念的定义似乎更多的是“当状态发生变化后，主、从状态同步一致的方式”这一出发点来说的，比如直接传内存的数据，或者类似于 raft 的 state machine 的 snapshot 等等，总之都是直接传输状态（应用层状态或者硬件状态均可）而不是需要重放的 operations。
比如我找到一篇 2006 年 OSDI 的论文 HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance，其中对 state transfer 有这样的描述
如果按照他们的定义，MySQL 的 Fully Synchronous Replication 显然就不是 State Transfer了，否则他们第一句话 State transfer is required to bring slow replicas up to date so that they may execute more recent writes 描述的情况就不会出现了，因为一旦有一个 Slave 报异常就拒绝服务了。
@LebronAl
State Tranfer 的核心思想是“当状态发生变化后，应在主、从状态同步一致之后再接受新的外部输入”
这个定义有可参考的文献吗？我查了一些文献，感觉学术界对此概念的定义似乎更多的是“当状态发生变化后，主、从状态同步一致的方式”这一出发点来说的，比如直接传内存的数据，或者类似于 raft 的 state machine 的 snapshot 等等，总之都是直接传输状态（应用层状态或者硬件状态均可）而不是需要重放的 operations。
State Transfer传输的当然是状态而不是操作序列，这点确凿无疑，不然也不会选择叫State Transfer这个名字。
我那句话的关键词是“同步一致之后再接受新输入”，这是它与Operation Transfer的核心区别，Operation Transfer是持续接受操作序列，以此重演历史来达成一致，这种复制并不要求同步的，这点也是State Transfer通常效率不佳的根源所在。
此前你引用的MIT课程中，Robert Morris教授的看法是：The idea behind state transferor's that if we have two replicas of a server, the way you cause them to be to stay in sync that is to be actual replicas, so that the backup can has everything it needs to take over if the primary fails.
在维基百科上对State Transfer的概念解释是：When a new replica is made available or an old replica is restarted, it must be brought up to the current State before processing Inputs. Logically, this requires applying every Input from the dawn of the system in the appropriate order.
上面两个观点，与文中的陈述思想相符合。至于同步状态的具体方式，诸如介质（内存、磁盘，或者别的）是什么、协议是什么，有着充分的自由度，白话说就是有很多种不同的方式都能实现State Transfer。譬如维基百科（Optimizing State Transfer节），以及Robert Morris都提到为了改善效率，可以按Checkpoint的变动为单位来同步状态变化，减少传输完整完整状态的负担。
Robert Morris: If you wanted to be efficient, you would only send the parts of the memory that it's changed since the last time you sent in memory
再具体到MySQL的Fully Synchronous Replication，不妨将日志就视作是此时同步的状态量，以一个事务的完整日志作为同步结束的标志，也可以理解为Checkpoint。
感觉这个概念还是有一定争议。比如对于 vm-ft 这篇论文来说，其主要思想是从硬件层次传输 CPU 指令，中断等来使得 primary 和 backup 达到一致，论文其中的 Output Rule 规定了 primary 只能在得到 backup 的 ack 之后才能返回结果给客户端，否则永远不响应客户端的请求。这样的实现和 MySQL 的 Fully Synchronous Replication 思想基本是一致的，但是 Robert Morris 教授在课程中却将 vm-ft 描述为一个 RSM 系统。
for today's if today's paper worked as a state transfer system which it doesn't then the state we'd be talking about would be the contents of the RAM the contents of the memory of the primary ...
谢谢您耐心的解答！ 读您这个博客收获很大！
@LebronAl 感觉这个概念还是有一定争议。比如对于 vm-ft 这篇论文来说，其主要思想是从硬件层次传输 CPU 指令，中断等来使得 primary 和 backup 达到一致，论文其中的 Output Rule 规定了 primary 只能在得到 backup 的 ack 之后才能返回结果给客户端，否则永远不响应客户端的请求。这样的实现和 MySQL 的 Fully Synchronous Replication 思想基本是一致的，但是 Robert Morris 教授在课程中却将 vm-ft 描述为一个 RSM 系统。
for today's if today's paper worked as a state transfer system which it doesn't then the state we'd be talking about would be the contents of the RAM the contents of the memory of the primary ...
谢谢您耐心的解答！ 读您这个博客收获很大！
我觉得周老师的理解和解释是对的，您的这个理解太纠结于细节和具体实现
按照周老师引用维基的原话来说吧。
When a new replica is made available or an old replica is restarted, it must be brought up to the current State before processing Inputs (see Joining). Logically, this requires applying every Input from the dawn of the system in the appropriate order.
Typical deployments short-circuit the logical flow by performing a State Transfer of the most recent Checkpoint (see Checkpoints). This involves directly copying the State of one replica to another using an out-of-band protocol.
A checkpoint may be large, requiring an extended transfer period. During this time, new Inputs may be added to the log. If this occurs, the new replica must also receive the new Inputs and apply them after the checkpoint is received. Typical deployments add the new replica as an observer to the ordering protocol before beginning the state transfer, allowing the new replica to collect Inputs during this period.
后面两段也讲到一般在 state transfer 的过程中会先以 observer （Paxos 的概念，类似于 Raft Learner）的方式加入共识组。不论对于 observer 还是 learner，其都是不阻塞整个共识组的写入的，仅仅是增量的在同步日志而已。
所以我感觉这一定程度上与周老师给出的 state transfer 的核心：同步一致之后再接受新输入 有所不符。
其实上次和周老师讨论完，我感觉严格的去纠结定义没有意义。可能就跟 CAP 定理一样，实际上理论和实现的 gap 很大，基本也就只能当个参考，不能当做什么理论依据。具体可以参考 DDIA 作者的博客。
老师，请教一下，“这样就可以容忍少数（通常是不超过半数）的节点失联，使得增加机器数量对系统整体的可用性变成是有益的”，为什么容忍少数节点的失联，就能够使得增加机器数量对整体变成有益的，这个是怎么证明出来的？ 我个人的粗浅理解，假设3/5是指系统中共5个节点，其中需要3个节点通过才能够认可操作转移的请求，那么3/5则表示系统达成一致性的阈值，当节点数量不断增加，例如增加到21个时，一致性的阈值为11/21，比3/5小，也就是系统达成一致性的阈值减少，我们由CAP理论可知，P不变，可用性和一致性成负相关，那么一致性阈值越低，那么系统整体的可用性则越高。 那么为什么是超过半数呢？如果是小于半数会怎么样呢？ 超过半数是(n+1)/(2n)，小于半数是(n-1)/(2n)，通过在线求导器可知，(n+1)/(2n)单调递减，(n-1)/(2n)单调递增，那么当“多数服从少数时”，随着节点数量的增加，系统达成一致性的阈值增加，则整体系统的可用性越低。 （没有严谨的证明，如果有理解不对的地方，希望老师能够指出）
让数据高可靠的办法，就是分开存多份。
线上环境中，数据动态变化。如何在网络不可靠的条件下，保证分存的动态变化的数据的一致性和可用性？
方法一：状态转移
它将数据拷贝多份（符合人类思维），但可用性低（因为拷贝过程中数据不可用）。而且，但节点增多时，可用性降低（反规模效应）。
方法二：操作转移
拷贝操作，节点执行相同的操作。
状态机复制：初始状态一样的状态机，如果执行的命令序列一样，则最终达到的状态也一样。
优点：
- 节点接收和执行指令的时间可以不同：提高可用性；
- 允许短时间不一致，只要不一致性不对外暴露即可：妥协一致性；
- 多数服从少数（过半节点完成状态转换，则认为数据已持久化）：可容忍网络分区，而且节点越多越有利。
难点：设计一种算法，能够让分布式系统内部暂时容忍存在不同的状态，但最终能够保证大多数节点的状态达成一致；同时，能够让分布式系统在外部看来始终表现出整体一致的结果 -- 协商共识。
