• 2020-03-09

    “一致性”是镜花水月

    Views: 1262 | No Comments

    分布式系统要达到强一致性(一致性), 所有的实现算法最终都是基于 W+R > N, 例如将 W 和 R 设置成多数派(后面按这个设置讨论), 即 N/2+1. 具体是指:

    1. 尝试写全部节点, 如果写了 W 个节点就算是写成功.
    2. 同样, 读的时候读全部节点, 如果 R 个节点达到一致(注意, 不是读多数派, 而是多数派达成共识).
    3. 最后, 也是最重要的, 如果无法满足前面两个条件, 必须强制将系统设置为"不可用"状态.

    最后一项条件非常重要, 如果不强制将系统设置为不可用, 将违反一致性原则.

    工程实践上极度厌恶"不可用", 追求的是"高可用", 所以, 最后一项很少有人能完全坚持. 这也是各种分布式系统优化的基础. 大部分的工程都是对读操作的优化, 不要求读操作达到多数派, 从而避免去执行第 3 项.

    例如, 系统可以只读取唯一个节点, 返回该节点的数据即可. 这样做有工程上的价值. 如果某个节点故障, 换另一个节点继续尝试(例如一致性 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: 1293 | 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: 1425 | No Comments

    为什么 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: 1489 | No Comments

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

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

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

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

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

    补充一点: Paxos 充满了各种工程上的错误暗示, 如果按它的暗示来, 你会犯各种错误. 例如, Paxos 暗示同步的是一个(唯一的一个) key 和对应的全量值, 工程上你不可能每一次都同步整个全量数据库, 对吧? 不要提 multi-paxos, 因为你会被它错误地暗示而独立地处理每一个 key, 然后你实现不了数据 Catch Up, 无法实现副本的最终一致性.

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

    再次注意, Paxos 并不是按数据版本号来返回最新的数据, 这种想法是错误的. 也不是所谓的多数派读(Quorum Read). 仅仅 Quorum Read 并不能保证强一致性, 因为某个节点可能随时上下线, 导致一会是多数派一会是少数派, 这种结果不是一致性的. 提一句, 这是个经典问题, Raft 通过不 commit 前任的 log 来解决这个问题.

    总结:

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

    补充: Paxos 与薛定谔的猫

    因为副本的不一致性是无法避免的, 所以 Paxos 在执行 accept 操作时, 可能只写了一个副本, 那么对于用户来说, 它期望的数据到底有没有写入成功呢? 答案是薛定谔的猫. Paxos 无法告诉你有没有写入成功, 可能成功了也可能没成功, 通过观察是不能下结论的, 你必须去读它, 读了之后才能知道有没有成功. 因为 Paxos 读即是写的特性, 处理读请求时, 如果同步到了之前写入的数据就是成功了, 如果同步的不是之前写入的数据就是(用户的前一个操作)失败, 它会确保不会再次同步用户前一个操作写入的那个唯一的副本.

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

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

    Views: 2175 | No Comments

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

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