• 2020-04-21

    Paxos学习-instance

    Views: 8176 | No Comments

    在讨论 Paxos 之前, 我想抛出几个包括我在内很多人都会提出的问题:

    * 如何更新一个 key?
    * 如何让两个数据库完全相同(最终一致)?

    先不管最终一致性, 强一致性, 或者什么时间线性一致性顺序一致性. 我的需求是让两台或者更多台机器上的数据库的数据是完全相同的. 经过对隐晦的 Paxos 协议和其相关的资料的来来回回的阅读和理解, 我又一次得出了新的结论...

    Paxos 用来确定一个 instance 的值, 一旦确定, 不可更改!

    什么? 不可更新? 不可修改? 太违反常理了吧? 这样, 有个鸟用? 我今天终于在 stackoverflow 上看到了这个说法, 然后再回头阅读 Paxos made simple, 我不得不得出同样的理解. 所以, 我昨天"关于 Paxos 论文中的迷惑之处"的问题也得到了解答. 如果你把 instance 当作 key, 用 Paxos 来对 key 的值达成共识, 确实只能是一次性的, 确定之后你就不能再更新它的值了.

    如果 Paxos 是这样, 那它几乎没有任何实践意义, 一个不能更新的 key 有什么用? 一个只能写一次的数据库? 问题就在于, 你把 instance 当做什么. 如果要更新 key, 你就不能把 instance 对应成 key, 你应该把 instance 对应成对这个 key 做的一次操作(一条 binlog)... 再看论文最后提到状态机, 这才发觉, 原来, Paxos 天生就是复制状态机模型. 所以, 那些 multi paxos 到底在扯什么鬼?

    只要把 instance 对应成对整个数据库做的一次操作, 然后对多次操作指定顺序, 就是我们常见的 binlog 同步.

    Posted by ideawu at 2020-04-21 22:14:56 Tags:
  • 2020-04-20

    分布式存储名词解析 – 一致性

    Views: 5389 | 3 Comments

    一致性分为访问一致性和数据一致性. 访问一致性, 是指从观察者的角度, 其访问结果是可预期的. 数据一致性是指从上帝视角看, 多个副本的数据是完全相同的.

    Paxos 协议, 这里指的是原始(Basic) Paxos, 其本质是解决访问一致性, 并不解决数据一致性, 它不保证多个副本数据现在是(或者将来是)完全相同的, 它只是在可能不一致的多个副本上提供可预期(一致性)的服务. 这个说法不代表不能使用 Paxos 来保证数据一致性, 而是说, Paxos 的设计目的不在于此.

    Raft 同时解决访问一致性和数据一致性. 使用了 Raft 协议的分布式存储系统, 既能提供可预期的数据访问服务, 也能在时间维度上保证多副本数据一致性. 例如, 在系统隔断外部输入的情况下(不再接受写请求), 经过一定的时间(一般从几毫秒到数秒)之后, 使用了 Raft 协议的集群内的多个副本的数据将是完全相同的.

    Paxos 协议本身并不能保证系统级的数据的最终一致性, 因为它是基于外界触发的消极全量数据拷贝协议. 如果没有外界输入触发, Paxos 就不拷贝数据, 所以它是消极的. 当需要拷贝时, 它拷贝的是全量的数据, 如果你需要保证整个数据库在多台机器上相同, 你应该拷贝整个数据库, 这显然没有实际意义. 另外, 当拷贝结束时, Paxos 并不保证数据被拷贝到所有节点, 这是第二个消极. 所以, 仅仅使用 Paxos 协议的系统, 在隔断外部输入的情况下, 如果数据不一致, 那么过一百年, 多个副本的数据仍然不一致.

    相对比, Raft 的数据拷贝是自动的, 不仅仅依赖外界输入触发, 还依赖时间触发, 所以, Raft 是积极的. 同时, 拷贝结束时, Raft 保证数据被拷贝到了所有节点, 从而实现所有副本是完全相同, 如果达不到这个目的, Raft 就不会停止(不达目的绝不罢休), 这是第二个积极.

    前面说过, 你一定要区分就充分和必要. 所以, 我不是说用了 Paxos 就必须是消极的, 而是 Paxos 本身是消极的, 如果你用了 Paxos, 你自己要积极起来, 不能只依赖 Paxos. 例如, 你必须引入日志复制状态机模型, 避免全量拷贝. 另外, 你还必须引入超时重传机制, 主动积极拷贝. 为了优化, 避免读请求也要走完整的 Paxos 流程, 你还要引入 Leader. 天啊, 你在重新发明 Raft!

    Posted by ideawu at 2020-04-20 22:50:48 Tags: ,
  • 2020-04-20

    关于 Paxos 论文中的迷惑之处

    Views: 4127 | 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 22:47:39 Tags:
  • 2020-04-09

    C++ const& 的坑

    Views: 5078 | 1 Comment

    我们一般很喜欢把函数的参数定义为 const&, 这样即能传引用减少内存拷贝, 也能限定参数为 const 类型不可修改, 似乎很美好. 但是, 如果把对象的属性传给函数, 而对象又被删除时, 就会出错.

    struct C
    {
        std::string id;
    };
    
    class S
    {
        C *c = NULL;
    
        void f1(){
            c = new C();
            c->id = "a";
            f2(c->id);
        }
    
        void f2(const std::string &id){
            delete c;
            c = new C();
            c->id = "b";
            printf("deleted %s\n", id.c_str()); // core
        }
    };
    

    当然, 理论上是写代码的人的错误. 但是, 这确实是一个大坑. 我相信, 这种 case 在实际中还是有不少的. 函数的编写者可能仅仅把参数当作一个无害的对象, 完全没有意识到, 参数变量是和某个要销毁的对象是绑定的. 但是, 又不能强制规定 string 类型只能传值, 然后期待编译器能优化 string 类.

    真是坑.

    Posted by ideawu at 2020-04-09 16:21:10
  • 2020-04-05

    接口与实现分离

    Views: 3085 | No Comments

    我在遇到"接口与实现分离"这个编程领域的概念时, 感到非常模糊. 随着编程经验的积累, 才明白了"接口与实现分离". 用 Java 的程序员应该天天用到 interfalce 和 class, 不过, 即使是 Java 程序员, 可能偶尔也会违反广义的分离原则.

    我最近接触到的一个违反"接口与实现分离"原则的例子, 可以分享一下.

    RTT(round trip time)是一个非常重要的时间概念, 这会让程序变得很"慢". 例如:

    func(1);
    func(2);
    func(3);
    

    如果每一次函数调用要花 100ms 的话, 那么做完 3 件事要花 300ms. 有经验的程序员立即就做了代码"优化":

    func([1,2,3]);
    

    把函数参数改成数组, 一次传入 3 个任务, 利用了 batch 机制, 做完 3 件事也仅需要 100 ms. 看起来完美解决问题. 但是, 工程上这样做带来了缺点, 那就是改变了接口(interface). 这是一个经典的违反"接口与实现分离"原则的例子, 接口因实现而被迫改变.

    如果函数执行是放在网络服务器上面, 而调用者是所谓的客户端, 一般的网络编程都是可以并发处理的, 例如在 3 个线程中调用函数. 这时, 接口改变之后, 反而没有用. 因为任务是不同的客户端发起的, 除非你增加一层抽象来积累请求. 这个优化看起来美好, 但是却增加了使用者的成本.

    所以, 工程上应该由 func() 函数的实现者来做请求积累, 在函数内部把并发的请求合并成一个 batch, 减少 RTT.

    Posted by ideawu at 2020-04-05 12:15:41
  • 2020-03-09

    “一致性”是镜花水月

    Views: 4406 | 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: ,
|<<<5678910111213>>>| 9/136 Pages, 812 Results.