• 2020-03-09

    “一致性”是镜花水月

    Views: 1261 | 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

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

    Views: 1424 | 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 2020-03-07 18:47:08 Tags: ,
  • 2020-03-07

    Raft 选主优化之 PreVote

    Views: 1308 | No Comments

    Raft 的论文介绍了一种普适性的分布式一致性协议, 但在工程实际上, 不太可能完全照搬论文实现, 因为工程上应对很非理想状况下的场景. 工程上实现 Raft 时, 单单是集群选主这个环节, 就会引入一些 Raft 协议本来没有的概念, 比如 PreVote.

    在实际使用时, 当网络分区出现时, 被隔离的节点会不断增加 currentTerm 并发起选主流程. 当网络恢复时, 它的 currentTerm 比其它所有的节点都要大, 所以, 它将导致原来的 Leader 变成 Follower 然后重新选主. 这种情况其实是非常不好的, 原来的 Leader 工作得好好的, 突然就被一个不稳定的节点给破坏了.

    所以, 要引入 PreVote, 在发起选主前, 一是判断是否和其它节点能网络连通, 二是询问其它节点是否要选主. 如果 Follower 最新刚刚收到了 Leader 的心跳包, 它就不同意选主.

    Leader 也要对 PreVote 请求进行响应, 而不能忽略. 因为在双节点集群时, 如果 Leader 不响应 PreVote, 那么两个节点永远都选不出新 Leader. Leader 通过心跳包和 Followers 保持联系, 如果失去联系, 它不会发起选主流程, 而是继续认为自己仍然是 Leader. 当收到 PreVote 时, 它要同意新的选主流程.

    Posted by ideawu at 16:14:26 Tags:
  • 2020-03-06

    Paxos 与分布式强一致性

    Views: 1488 | 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: 2174 | No Comments

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

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