流行的共识算法如 Paxos[1] 和 Raft[2] 被广泛地应用于分布式系统中, 用于实现一致性. 但是, 这些算法本质上并不区别读和写操作, 因而给工程实践带来了极大的困扰. 这种困扰导致在具体实现时, 开发者往往基于性能优化方面的考虑, 对这些算法做没有经过理论验证的更改.
我想在区分读写操作的前提下, 设计一种对工程实践友好的分布式一致性协议, 能适应读多写少或者读少写多等不同场景的需求. 这个分布式协议基于 Quorum 机制, 采用 2PC 策略和复制状态机模型, 适用于有强一致性要求的分布式数据库系统和其它分布式系统.
业界对用 Paxos 还是用 Raft 争论(讨论)非常多. 我认为有争论是有好处的, 但要弄清楚为什么争论, 以及争论的点在哪. 否则, 上升到偏见或者信仰, 就没有意义了. 例如, 隔几天来一个"我为什么抛弃XX选择YY?", 或者借助"洋大人"之口(其实就是一个普通的外国程序员)说出什么"Why we choose XX over YY?", 那就非常可笑了.
我认为, 对 Paxos 和 Raft 的争论, 大多是基于软件工程上模块职责划分的见解不同, 也就是一个系统中, 共识模块(Paxos 和 Raft 都是共识算法)应该做什么功能, 加哪些限制条件.
Paxos, 我们首先要限制必须是 Basic Paxos, 否则没有争论的意义. Basic Paxos 本身是赤裸裸的, 限制少, 灵活, 因为它是基础中的基础. 也正因为太基础了, 所以脱离群众, 离真正实用太远. 这也是为什么这么多年, 业界没有一个真正意义上的开源的 Paxos 编程语言库.
Raft 是这么多年, 对 Paxos 工程实践的总结和提炼, 以学术研究(论文)的方式加以证明, 并提供了工程指导. 所以, 这才是为什么有那么多的 Raft 开源库, 而大家的代码结构又大同小异的原因. 因为, 幸福的家庭都是相似的, 不幸的家庭各有各的不同.
我总结一下, Paxos 和 Raft 的争议点在有哪些, 这些争议点是职责划分的问题, 你很快就会发现.
"单主"是很多人不选择 Raft 的原因(没什么所谓选择不选择 Paxos, Paxos 就是基础). 一是多写入点, 客户端可以随机选取任何一台服务器来接收请求, 所以, 客户端的代码非常简单, 配置服务器的 ip:port 列表, 用随机算法或者 round robin 算法选一台创建 socket 连接即可. 二是故障恢复时间, Paxos 把故障恢复隐含到了每一次请求当中, 不像 Raft 那样明确的划分职责, 独立出一个选主过程. 独立的选主过程占用独立的时间片, 阻塞正常请求, 所以理论上要增加故障时间.
但是, Raft 当然可以优化成在每一次请求都选主, 工程实践上没问题, 但是, 这不就成了 Basic Paxos 了吗? 所以, 没人这么做. 大多数情况下就是这样的, Paxos 加了限制就成了 Raft, 而 Raft 做了优化就变成了 Paxos. 向谁靠拢的选择而已.
这是争论最多的地方. 事实上, 一个系统必然有乱序(并发)的地方, 同时也会存在顺序(串行)的地方, 没有任何一个大型的系统只包含并发或者只包含串行, 不可能, 我在工程上没遇见过这样的系统. 问题就在于, 你想把并发(岔路口)开在哪?
举一个例子, 网络编程中, 你可以在 accept 之后就启动线程, 每个线程处理一个 socket, 也就是你把并发的岔路口开在了这里. 你当然也可以用 IO 多路复用(如 epoll), 在一个线程中顺序地(但不阻塞)地读取 socket, 然后在读完请求之后, 启动线程处理请求, 也就是, 你把并发的岔路开在了那里.
Paxos vs Raft 就是这样的例子, Raft 认为把串行的部分交给我, 然后你(状态机)再并发. 但是用 Paxos 的人认为, 关于是串行还并行, 应该由我(状态机)来决定, 共识算法没必要加这个限制. 孰优孰劣? 任何一个理性和聪明的人都能得出答案.
用 Paxos 的人, 希望自己把控更多的东西, 所以 Paxos 非常薄, 薄得几乎不存在, 也就没有所谓的 Paxos 库了, 因为它的职责太少, 以致于根本不值得独立成一个库. 用 Raft 的人相反, 把更多的职责加给 Raft, 不重新发明轮子.
所以, 通过一两个反例来说明 Paxos 好还是 Raft 好, 在技术上非常幼稚. 正确的说法是: 某个职责不应该交给这个模块, 因为某个职责交给另一个模块可以做一些优化. PS: 工程上优化并不是唯一的考量因素.
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 既不依赖版本号返回最新的数据, 也不是所谓的多数派读.
蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.
但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.
最近我的 MacBook Pro 因为屏幕涂层脱落, 让苹果 Genius Bar 免费更新之后, 我发现更换后的屏幕显示效果很差, 像素颗粒非常明显, 没有苹果引以为傲的 Retina 屏幕的那种细腻效果. 我甚至一度怀疑给我更换的是一个 10 年前技术的 PC 显像管显示器. 这个问题还好, 只要不抠像素, 眼睛离屏幕稍微远一点, 就察觉不到像素了.
前几天, 在做 Keynote 和表格的时候, 我突然发现 MacBook Pro 的显示器竟然在显示蓝色的时候出现细微的灰色条纹. 这个问题是怎么发现的呢?
在 Keynote 里添加一个默认颜色(蓝色)的方框, 然后靠近仔细观察, 你就会发现蓝色的纯色在一条一条的灰色条纹, 像是像素之间的间隙透光. 这个蓝色不是纯蓝(#0000ff), 而是带有绿色和黄色的蓝色(大概是 #3388ff).
之后, 对比了多台同型号同年份且没有更新过涂层脱落屏幕的 MacBook Pro, 最终确认新的苹果给换的屏幕确实不够细腻, 可以认定是低品质的.
特别是在看 Firefox 浏览器的 LOGO 图标时, 你会发现火狐抱着的中间那个蓝色的地球, 条纹最明显!
我外行地分析了一下, 苹果屏幕用的 LED 屏, 每个像素由三个分别是红(R)绿(G)蓝(B)颜色的灯管组成, 通过三个颜色的灯管的不同亮度叠加, 产生不同的颜色. 如果三个灯管全部最亮, 就是白色了. 这个原理就是 Additive Color .
有了上面的基本原理之后, MacBook Pro 低档屏幕显示蓝色出现白色条纹的原因就可以分析出来了.
1. 生产工艺太差, LED 灯管排列间距太大.
这个原因是很有可能. 苹果用的屏幕的品牌和型号等, 不像 PC 那么透明, 无法直观的对比不同型号的品质差异. 如果真是这个原因, 那么便是生产工艺缺陷, 导致两行像素之间的间隔太大.
不过, 为什么蓝色(#3388ff)那么明显的. 应该涉及到单个像素的 RGB 三个灯管的排列方式.
2. RGB 分组排列导致 R 和 G 出现在同一行
我觉得屏幕生产厂商不太可能这么蠢, 除非有特殊考虑. 如果真的出现这种状况, 不同组的红灯和绿灯刚好组成了一条黄线, 那么出问题的蓝色(#3388ff)中的 R(33) G(88) 组成一条绿线, 同时受蓝色灯管影响, 就会变成浅白色的条纹了.
外行分析, 如果有专业人数, 欢迎提供信息.
快速排序算法，也即快排，是递归和分而治之这两种计算机基本思想的应用，再加上其实现逻辑复杂度较好，性能较快，所以快速排序算法非常经典。
快速排序算法经常作为面试算法题。快速排序算法本身并不复杂，其本身的逻辑非常简单，要掌握其思想不是难事，甚至基于其实现代码的形而上学的表面形状背下来也很轻松。但是，如果仅掌握了快速排序的思想以及代码表面形状，就认为自己懂了快速排序，就是没有真正地理解。
快速排序算法作为面试题，一是考查理论结合实践的能力，要求面试者除了知道快速排序算法的实现逻辑和代码形状，还要知道快速排序为什么快，怎么快。二是考查编码细节的能力，考虑的是人经验之外的智商和思维水平。
|
带有此标志, 表示本博客已经被加入到IT牛人博客聚合网站. |
Loading ...