• 2020-04-20

    关于 Paxos 论文中的迷惑之处

    Views: 6391 | No Comments

    1. 值的选择

    Paxos 论文提到, 发起 proposal(即 accept 类型的消息)时, 用的"值" v 是之前 prepare 时收集到的, 否则就是 any value.

    这个说法其实非常具有迷惑性, 并导致了大量奇怪的说法. 如果用的是收集到的旧值, 那我(用户)要更新数据怎么更新?

    所以, 大家实现 Paxos 时, 这里就变成了用的是用户请求的值回复自己发出的 prepare. 这其实违反了论文, 因为论文提到, 收集到的值必须是曾经 accepted 的值, 但是, 用户的请求还没有开始呢, 何来已接受?

    另一个迷惑的地方是"any value", 很多人都翻译成"随机/随意选取一个值". 这属于不严谨. 怎么能随意呢? 选择哪个值的依据(算法或者逻辑)是确定的, 两个集群做了同样的操作, 一个选择 a, 另一个选择 b? 当然, 实际的意思并不是"随机", 而是"决定", 实践上, 就是决定使用客户端所请求的那个值(如果进度相同的话).

    2. Proposal number

    Paxos 要求每个节点使用不同的 number 来 prepare, 但是, 即使使用相同的 number 来 prepare 似乎也没有问题? 因为只有唯一的一个能 prepare 成功.

    所以, 如果有人知道, 请告诉我, 两个 proposer 使用同一个 number 来 prepare 会导致什么问题? prepare 不就是要解决 number 分配的问题(同时交换最新值)的吗?

    Posted by ideawu at 2020-04-20 22:47:39 Tags:
  • 2020-03-09

    “一致性”是镜花水月

    Views: 7074 | No Comments

    Paxos 实现一致性的基础是每一次 touch 集群时, 都要走所谓的 2 phases. 这个 2 phases 是一个实实在在的写操作, 并没有所谓的只读. 对于 Paxos, 它并不关心是读操作还是写操作, 它要做的, 就是将数据复制到多个节点上. 有一种特殊情况下的优化, 那就是 Paxos proposer 获得了集群的全部副本, 并且知道全部副本都是完全相同的, 就不需要执行 phase 2.

    在某些情况下, 并不能这样优化, 因为等待全部节点返回结果, 可能消耗很长的时间. 而且, 某个节点故障时, 显然不应该等也等不到全部结果. 所以, 简单的做法是无论怎样, 都从多数派里获取最新的值, 然后要求所有节点都接受这个值(phase 2).

    所以, 对于 Paxos 来说, 要么全部节点都查询一遍(并且期望全部节点是完全相同的), 要么产生一个新的共识, 否则不能返回结果给客户端.

    这增加了系统的故障机率. 工程实践上极度厌恶"不可用", 追求的是"高可用", 所以, 很少人这样做, 也就是人们选择了 CAP 中的 AP.

    例如, 系统可以只读取唯一个节点, 返回该节点的数据即可. 这样做有工程上的价值. 如果某个节点故障, 换另一个节点继续尝试(例如一致性 hash).

    更进一步(更接近强一致性, 但仍然不是)的做法, 可以读取多数节点, 但不要求多数节点达成共识, 只返回多数节点之中最新版本的数据.

    这些对于读操作的优化, 都只能达到数据本身的"最终一致性", 从用户的观察角度看, 系统的状态在某个时间段是飘忽不定的(不一致). 无论你是否愿意承认, 只要你违反了 3 项原则中的任何一项, 你的系统就不是强一致性的. 不管你借鉴了 Paxos 还是 Raft. Raft 比较特殊一点, 把 Leader 当作存储共识的单点, 只需要查询 Leader 就能知道是否达成共识, 写或者读.

    强一致性既然那么难, 所以工程不太可能会去实现强一致性的系统. 正如前面所说, 大部分都对读操作进行了简化(优化). 那么, 写操作还是强一致的吗? 答案是否定的. 一旦读不是强一致性的, 写便不再是强一致性的. 一致性是对整个系统而言.

    那么, 很多借鉴了 Paxos 或者 Raft 的写流程的系统, 它们在做什么? 其实, 大部分只是利用了多数派顺序写特性. 多数派(多副本)是为了达到高可靠性, 顺序写是为了最终一致. 例如 Paxos 的 prepare 阶段就像是在申请全局递增的序号同时拷贝多副本, 而 accept 阶段是拷贝多副本.

    是的, 大部分系统最终实现的是高可靠, 高可用, 和最终一致性.

    Posted by ideawu at 2020-03-09 18:10:23 Tags: ,
  • 2020-03-07

    关于分布式存储的上帝视角和观察者视角

    Views: 6038 | No Comments

    我认为, 讨论分布式存储时, 一定要区分上帝视角和观察者视角, 否则经常会导致混乱. 上帝视角是指对多个副本进行同一时刻完整性的观察, 而观察者就是通常说的用户角度. 上帝的观察是非常绝对而准确的, 而且不会对系统产生任何作用. 而观察者则不是, 观察者的每一次观察可能会导致系统的状态发生改变. 例如, 对于 Paxos 来说, 读操作可能导致数据的写和删除.

    对于一个3个节点的集群, 我们说某一份数据存在两个副本, 这是上帝视角的观察. 从用户的角度来观察, 可能观察到0到2个副本. 一致性协议要解决的一般是观察者的线性一致性, 同时要隐藏副本数量, 只让观察者看到数据的存在或者不存在, 而不是副本的数量.

    一个很经典的一致性问题, 在3个节点的集群中, 如果上帝视角看到是两个副本, 那么观察者第一次看到是存在(按多数派来决定是否存在), 那么第二次观察就不能说不存在.

    之前讨论过, 即使上帝看到2/3多数派副本存在, 观察者的观察结果未必就是存在. 如果观察者观察时只看到两个节点其中一个节点无数据, 这种情况就是所谓的 unknown(未决, uncommitted). 因为观察者讨厌 unknown, 所以, Paxos 会更新集群的状态(同步数据), 让集群的状态变成 committed.

    回到线性一致性的问题来, 如果第二次观察时, 虽然不能说不存在, 但可以说 unknown, 这并不违反系统的一致性原则. 不过, 违反了高可用原则.

    分布式系统, unknown 状态是一个非常重要的概念. 上帝视角没有 unknown, 但观察者视角有. 我们有上帝视角, 但集群的用户只有观察视角, 一定要注意.

    Posted by ideawu at 2020-03-07 19:10:12 Tags:
  • 2020-03-07

    为什么 Leader Based 的分布式协议 Raft 是更好的

    Views: 9186 | 1 Comment

    为什么 Leader Based 的分布式协议 Raft 是更好的? 这个问题隐式地表达了 Paxos 多主特性是不好的. 之前谈过, Paxos 不区分读写, 读和写都要进行完整的 Paxos prepare-accept 两阶段流程, 否则, 就无法保证一致性. 事实上, 我看过一些 Paxos 实现, 它们基于优化的考虑, 简化了 prepare-accept 两阶段流程, 最终失去了一致性保证而不自知. 可见, 优化是万恶之源.

    一个常见的错误是把多数派读当做一致性读, 之前已经谈过, 这是错误的.

    但是, 为什么大家一而再, 再而三地一定要优化 Paxos 呢? 很显然, 大家已经发现 Paxos 的理论模型在很多场景并不实用(请原谅我这么直白, 你可以自己想象成非常委婉的语言). 于是, 每个人都按自己的理解去简化 Paxos 实现, 然后错误地拿"Paxos"来当挡箭牌证明自己拥有 Paxos 的所有优点, 而不知道自己犯了逻辑上不严谨的错误, 只是因为计算机和网络环境出错的概率比较小, 而自己的代码其它部分又有 bug, 所以不愿意把 bug 算到自己错误地简化了 Paxos 这个做法头上.

    我发现, 错误的 Paxos 实现各有各的不同, 而正确的 Paxos 实现最终都实现成了 Raft 的样子.

    首先, 日志复制状态机的理论更有普适的实际意义. Multi-Paxos 错误地暗示要实现成以 key 为维度, 但现实世界的数据是结构化的, KV 是特例. 结构化要求不能以离散的 key 为维度来同步数据, 而是应该同步数据的操作序列, 也就是日志复制. 所以, 除非全量同步数据, 否则把 Paxos 应用到结构化数据上面一定会带来严格意义上的错误的.

    其次, Leader Based 是更有普适意义的一种理论上已经证明具有严谨性和正确性的优化手段. 我所见过的任何不基于选主的对 Paxos 进行优化的方案, 几乎全是错误的, 都没有理论上的严谨证明, 实际上的错误也显而易见. 如果你的 Paxos 实现不是基于选主的, 同时你又意图做优化, 那么, 我几乎非常确定, 你已经犯错了.

    为什么优化必须先选主? 之前的文章已经谈过, 多个副本数据的不一致性是一定的, 没有任何协议和手段能避免, 所有的一致性协议都是让数据看起来一致来让自己具有一致性功能. 当多个副本不一致时, Paxos 要求在读和写的时候同步数据, 来修复这种不一致, 修复完后才能返回给客户端. 但是, 所有的优化都破坏了这个原则, 然后声称自己对 Paxos 做了优化. 哪有这样的好事? 你破坏了 Paxos 基石, 却没有提供对等的理论证明.

    再回到选主这个话题. 选主的一个重要作用, 就是对多副本的不一致性进行统计和确认. 一个简单的例子, 当某个 key 只存储于一个节点或者两个节点, 无论是多数节点还是少数节点没关系, 那么这个 key 到底是不是有效的? Paxos 的做法是读的时候做同步. 有一个非常违反直觉的的地方, 那就是, 如果数据存在于多数节点, 那么这个数据是否是有效的呢? 答案仍然是未知的

    很违反常理, 是不是? 设想这样一场景, 当你去读这份数据时, 你会遇到两个情况: 一是多数节点有共识, 二是没有多数节点共识. 对于有共识, 很简单, 那就是有共识. 但是, 对于无共识, 除非你读到了所有节点的明确的答复, 否则你不能确定是否有共识, 因为还有节点未答复.

    但是, 如果有 Leader, 那么 Leader 自己就能确定, 不需要读"全部"节点. 这就是做了优化. 现在, 问题就剩下怎么避免出现两个"自认"的 Leader. 这也是 Raft 要解决的问题.

    Posted by ideawu at 18:47:08 Tags: ,
  • 2020-03-06

    Paxos 与分布式强一致性

    Views: 10197 | No Comments

    Paxos 有着"难以理解"的恶劣名声, 事实确实如此. 它用大段篇幅来做证明, 却对现实问题避而不谈. 例如最简单(常见)的问题: 怎么实现一致性读功能?

    因为 Paxos 太难以理解, 所以无数人用各自不同的角度去理解 Paxos, 而且实现上千差万别和漏洞百出. 我觉得这种现象和一句名言类似: 不幸的家庭各有各的不幸. 但是, 学习 Raft 的人都很开心, 而且大家在实现(implement) Raft 协议时, 代码基本是一样的. 正如名言所说: 幸福的家庭都是相似的.

    我也用我自己的角度去理解 Basic Paxos, 我认为它最大的特点是不区别读和写. 简单说, Paxos 的读过程就是写操作, 就是在做数据同步.

    首先, 无论使用何种一致性协议, 都无法解决在任何时刻副本数据不一致的问题. 也就是说, 一定存在某个时间点, 多个副本不一致. 这是无法解决的. 要解决的是读一致性, 即从观察者(用户)的角度看, 数据是一致的. 写操作永远都是"最终一致"的.

    其次, Basic Paxos "暗示"在读操作的时候进行数据同步, 以修复数据达到"最终一致性". 而工程上的常识是, 多个副本必须自动地最终一致, 而不依赖外界触发. 如果某个系统依赖 Paxos 的这种"暗示", 那么这个系统将是不可靠的, 也不是(最终)一致性的.

    Basic Paxos 充满了各种工程上的错误暗示, 如果按它的暗示来, 你会犯各种错误. 例如, Paxos 暗示同步的是一个(唯一的一个)实例(key)和对应的状态(value), 工程上你不可能每一次都同步整个全量数据库, 对吧? 而且共识之后就不能更改, 哪有不能更改的数据库?

    别提 Multi Paxos, 日志复制状态机是 Raft 的核心, 心里想着 Paxos, 但做着做着, 全是围绕复制状态机来做, 最终还是做成了 Raft 的样子.

    对于读操作, Basic Paxos 要求收到读请求的节点(Proposer)向其它节点发起数据同步操作, 也即所谓的 prepare-accept 两阶段. 在 prepare 的过程中, Proposer 收集其它节点的数据. Prepare 阶段除了同步数据, 还有一个作用是更新版本号(num), 之后就是 Proposer 将其所知的最新的数据同步到其它节点. 注意, 两阶段中间如果有失败, 不做回滚, 而是继续重试, 等最终成功, 或者放弃并告知用户. Basic Paxos 是读修复.

    再次注意, Basic Paxos 并不是按数据版本号来返回最新的数据, 这种想法是错误的. 也不是所谓的多数派读(Quorum Read). 仅仅 Quorum Read 并不能保证强一致性, 因为某个节点可能随时上下线, 导致一会是多数派一会是少数派, 这种结果不是一致性的. 提一句, 这是个经典误解. Paxos 对一致性的保证, 来源于其无论读写, 都必须达成新的共识.

    总结:

    1. Paxos 读即是写, 读即是数据同步.
    2. Paxos 既不依赖版本号返回最新的数据, 也不是所谓的多数派读.

    Posted by ideawu at 2020-03-06 13:57:02 Tags: ,
  • 2020-02-21

    分布式一致性协议-Raft和Paxos

    Views: 8128 | 1 Comment

    分布式一致性协议-以Paxos和Raft为例.001
    Continue reading »

    Posted by ideawu at 2020-02-21 16:45:39 Tags: ,
|<<<1234>>>| 4/4 Pages, 24 Results.