美文网首页
论文阅读之Spinnaker

论文阅读之Spinnaker

作者: zsc347 | 来源:发表于2018-07-21 13:17 被阅读0次

    原文地址

    简介

    传统数据库已无法满足大规模数据的需求。传统的解决方案是分片,事务只能局限在一个分片节点。且通常需要人工维护。分片的方式会有成百上千个节点,节点数量多导致小概率事件变成大概率事件。因此需要实现高可用性和错误容忍。一个解决方案是使用同步备份策略(一个主多从,写数据需要从机确认后才能返回写成功)。然而这种策略在有些场景下会失去一致性。

    1. 传统策略的问题

    1.1 传统同步备份的问题

    传统的两路同步备份思路,
    同步一主机一从机,写确认需要从机确认。如果从机宕机,主机继续提供服务;如果主机宕机,则从机一定处于最新的状态,因此可以由从机继续提供服务。

    使得这种模式出现不一致的场景:

    1. 主机接受命令m1, 从机接受命令m1
    2. 从机失败,主机继续工作
    3. 主机接受命令m2
    4. 在主机将m2复制到从机之前,主机宕机,同时从机恢复
    5. 此时只有一台机器处于宕机状态(主机),但由于主机已经接受的命令没有
      拷贝到从机,从机不能接受命令。

    同步一主两从,假定有三个节点A,B,C
    假定有以下命令序列[1,2,3], 三个节点状态按如下顺序变化
    1 1 1 (A,B,C均正常服务)
    2 2 1(A, B正常,C宕机)
    3 2 1 (A正常,B宕机,C恢复,命令未完成复制)
    3 2 1 (A宕机,B恢复,C恢复)此时无法接受命令,虽然只有一个节点处于宕机状态。

    多机一致性的问题研究了近30年,Paxos协议家族目前被认为是唯一保证了正确性的协议,它能保证在有2F+1个节点时,能够容忍F个节点宕机(少数)。然而,Paxos算法还没有被应用在数据库的复制中,因为通常认为它太复杂并且很慢。(本文发表于2011年,貌似阿里的oceanbase中是使用Paxos协议来实现数据库备份)。

    1.2 强一致性 vs 最终一致性

    强一致性是指所有副本都对应用表现的完全一致。然而根据CAP理论,强一致性跟可用性和网络分区容忍不能共存。
    数据库系统如Dynamo使用了最终一致性模型,客户端可能会看到多个不同旧版本的数据,作为结果,客户端需要自己处理好冲突检查。我们所熟悉的数据库ACID事务并不被支持。
    尽管有些系统可以接受最终一致性,但是大部分应用仍然需要强一致性的保障。并且需要有一定的事务支持。
    在单数据中心中,网络分区现象很少见。因此选择CA可能比选择AP+最终一致性更合适。

    1.3 Spinnaker

    基于key的range partitioning
    3路副本
    带事务的get-put,可选强一致或time-line一致性(取舍:提高性能,允许可能返回旧版本数据)
    使用Paxos确保大多数节点存活时的可用性
    在CAP中选择CA

    2. 相关工作

    2.1 两阶段提交

    2PC允许每一个参与者都是一个独立的资源管理器
    缺陷:
    一个节点失败会导致全局失败
    每一个事务都需要2PC会导致性能很差
    2PC有coordinator角色,当coordinator宕机时会阻塞。3PC是非阻塞的,但是因为性能差很少再实践中使用。

    3 数据模型和API

    数据模型
    类似多版本关系数据库。表+行。每个column有对应的verison
    table + row["key"]["column"]["version"]
    客户端API
    get(key, column, consistent=strong/timeline)
    put(key, colname, colvalue)
    delete(key, colname)
    conditionalPut(key, colname, value, v)
    conditionalDelete(key, colname, v)

    4 架构

    基于key range分片,每个分片默认3个副本分布在不同的节点


    Example of a Spinnaker cluster

    4.1 节点架构

    The main components of a node

    每个节点包含多个组件,且每个组件都是线程安全的。
    每一条log由LSN唯一标志
    commit queue位于内存,log只有在多数节点确认时才能提交,在此期间它们存储在commit queue中。
    committed log存储结构:memtable + SSTable(GFS)

    4.2 Zookeeper

    提供错误容忍,分布式协调服务

    5 副本协议

    The replication protocol

    每个分片有一个Leader,两个Follower
    协议有两个阶段:Leader选举阶段和投票提交阶段,Leader提议Follower投票。在没有出现错误的情况下(服务器宕机,网络分片等),Leader不需要改变,只需要执行投票阶段。
    当客户端需要写数据时,总是会被路由到Leader(只有一个节点写数据)。
    Leader将写命令Append到commit queue中。持久化到硬盘。
    Leader发起提议,
    Follower接收到提议,持久化log,将命令放到commit queue。返回ACK
    Leader接收到多数人的ACK,此时可以确认commit->将命令应用到memtable。
    Leader阶段性的发送异步的commit message给follower,follower相应的将写命令应用到memtable。
    强一致性读需要从Leader读,timeline 一致性读可以从副本中读取。

    6. 恢复

    6.1 Follower恢复

    Follower恢复有两个阶段。

    • Local Recovery
    • Catch Up
      在Local Recovery阶段,Follower能从checkpoint开始,一直应用到f.cmt来恢复memtable的状态。f.cmt之后的log可能没有被Leader commit,这些log在catch up阶段恢复。如果Follower因为磁盘错误丢失了所有的数据,那么Follower直接进入Catch Up阶段。
      在Catch Up阶段,Follower告诉Leader它的f.cmt的值,Leader将Follower缺的f.cmt之后的所有log发回Follower。在catch up的最终阶段,Leader会临时的阻塞写操作,从而确保Follower能完整的catch up。
      在实践中,Leader由于会执行log压缩,从而有些Follower需要的log记录已经不能获得。此时的处理是直接将合适的SSTable发送给Follower,并从SSTable记录开始恢复。
      当选出新的Leader的时候,f.cmt之后的有些记录可能并没有被Leader Apply,因此这些记录需要丢弃。那么是否可以直接截断f.cmt之后的log呢?答案是不能。
      原因是这些log可能属于不同的分片。

    6.2 Leader 接管

    新Leader选举时会确保新的Leader包含了所有的旧Leader已经commit的log。这一点会在第七节介绍。
    旧Leader恢复时需要执行Follower恢复流程。
    新Leader需要为旧Leader发送那些已经被commit但是commit message还没有
    发送的commit的commit message。使用如下算法。


    Leader takeover

    7 Leader选举

    Leader选举会在一个分片的Leader出错时发生。
    Leader选举必须达成共识只有一个Leader。
    Leader选举必须保证选举出来的Leader必须拥有所有的已经commit的log。

    7.1 Zookeeper 数据模型和API简介

    Zookeeper的数据模型类似文件系统中的目录树。每一个节点由其路径标志。
    举个例子 /a/b/c。每一个znode节点可以设置关联数据。
    客户端可以创建或删除znode节点。
    znode节点可以是持久化的节点或临时节点。当客户端断开链接时,Zookeeper会自动删除临时节点,而持久化的节点需要客户端显式删除。znode可以包含一个连续属性,从而允许唯一性,单调性的需求。
    znode提供了watcher,客户端可以监听znode或者其children的事件。

    7.2 Leader选举协议

    每一个Spinner的节点都包含了一个Zookeeper的客户端,用于实现Leader的选举。
    r代表分片的范围(比如图2中的[1, 199])
    选举r分片所需的信息会存储的Zookeeper的/r目录
    首先清除所有的前一次选举的状态信息
    然后,每一个节点都宣称自己是备选人(candidate),使用自己的n.lst,创建在/r/candidates目录下。
    然后给目录/r/candidates设置一个watcher,一旦目录信息发生变化通知分片节点。
    当大多数节点的信息出现在此目录时。即可选出新Leader,选举规则是哪个的n.lst最大就选哪个。
    然后新Leader将其host信息写入/r/leader,并执行Leader 接管算法。
    使用临时的节点可以应对新选出来的Leader潜在的可能出错。
    最终,所有的Follower从/r/leader中读取leader信息。
    这个算法是可以保证

    1. 所有节点对Leader达成共识
    2. 新的Leader拥有所有旧的Leader已经commit的log
      第一条很显然。
      第二条依赖的就是两个多数人的集合必然有交集。旧Leader已经commit的log必然在新Leader的candidate目录中必然至少有一个包含了旧Leader所有的commit log。而选择的新Leader拥有最大的lst,因此新Leader log要么就是至少的那一个,要么比至少的那一个还要长。于是可以得出结论新的Leader必然包含了所有已经commit的log。

    8 可用性和持久性保障

    对于三路复制。
    写操作至少需要两个节点存活。
    强一致读需要重定向到Leader节点,也至少需要两个节点存活。
    timeline一致性允许读到旧数据,只要有一个节点存活即可。

    相关文章

      网友评论

          本文标题:论文阅读之Spinnaker

          本文链接:https://www.haomeiwen.com/subject/xutcmftx.html