`
jimmee
  • 浏览: 538733 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

Keyspace中的paxos [转载]

阅读更多

1. Keyspace

Keyspace是一款基于Paxos的开源Key-Value的数据库,底层存储基于BerkelyDB,Keyspace的核心功能是在 BerkelyDB之上添加了一致层,保证每个节点的数据完全一致。Keyspace基于Master-Slave模式,所有的写均有Master承担, 并通过paxos一致传播到slave,读可以根据基本路由到master或slave。因此,当master出现宕机或不可访问时,会存在一套 master的选举机制,在keysapce中成为PaxosLease算法。默认,master拥有Lease的时间是7秒,但只要master没有 crash可以继续持有。

要指出的是,因为基于master,所有keyspace对paxos实现进行了改造,把2 phase的paxos改造为1 phase。

2. Keyspace配置

Keyspace提供了众多的端口和服务,具体如下:

Item Port
HTTP服务 8080
非HTTP客户端 7080
内部 数据复制 10000
master lease 10001
catch up 10002

Catch UP是指节点长时间离开后又加入的情况

3. Keyspace架构

Keysapce的基本架构是在BerkelyDB之上加了一层paxos,其图如下:


Paxos与PaxosLease同属于Paxos层,PaxosLease倾向于解决Leader选举问题,Paxos主要是解决数据一致性,我们重点放在Paxos上。

在Paxos的实现上,Keysapce还有几个描述更细致的组件:

  • KeyspaceDB:对外部协议的一致性操作接口,隐藏了对Paxos和BerkelyDB的调用。
  • ReplicatedLog:逻辑上的DB Log,封装了Paxos的一致性
  • PaxosProposer:Paxos算法中的提案者
  • PaxosAcceptor:Paxos算法中的acceptor
  • PaxosLearn:Paxos算法中的Learn

在Keysapce中的每个节点都集Proposer、Acceptor、Learn三种角色于一身,有ReplicatedLog统一协调。

另,Keyspace使用的是TCP协议,其他非核心模块、功能则不再介绍。

4.Paxos实现

Keyspace采用了基于Master的Paxos算法,只要Master没有crash,所有的写请求均有Master上的proposer进 行提案,并一致性地写到所有的slave。因为Master的存在,Keyspace把传统paxos算法的prepare、accept两个阶段,简化 为仅有prepare的1个阶段,但keyspace对prepare阶段的两个过程进行了概念上的重新定义:

  • propose:master提出proposal
  • prepare resposne:acceptor对proposer的response

如果因为网路延迟或其它原因导致master提交的proposal被拒,则master需要提高proposal的编号继续提交,此时称为:

  • prepare:master提供编号后继续提交proposal
  • prepare response:对应的response

以前paxos算法中的proposal是个抽象的概念,但在Keyspace中是非常具体的,就是Key-value对。那paxos是如何保证一致性的呢?每次用户提交Key-value,Keyspace都进行下面流程:

  1. ReplicatedLog把接收到的Key-Value传递给Master Proposer
  2. Master给当前的(K,V)分配paxosID即instance id,并作为propose消息发送给其他的Node
  3. 之前其他Node的多数派都响应了accept消息,Master便把该(K,V)连通paxosID一起发送给所有的Learn(也是其他Node)
  4. Learn 在接收到Master的消息后,会检查消息中的paxosID之前所有的paxosID是否已经学习过了,即保证(K,V)要按顺序执行,不能跳号。如果 之前的均已学习过了,则把当前paxosID对应的(K,V)持久化到BerkelyDB;否则Learn要请求Master学习之前的paxosID对 应的消息。

按编号顺序学习消息是Keyspace保证一致性复制的核心。我们在详细说明下4的过程,在Learn收到消息(msg)后要检查:

  • 如果msg.paxosID==local.paxosID+1,这直接执行消息中的(K,V)
  • 如果local.paxosID < msg.paxosID,则需首先学习[local.paxosId+1,msg.paxosId-1]对应的(K,V),然后在执行msg.paxosID对应的(K,V)已保证一致性,这个过程称为跳号

为了节省空间,master会缓存一部分已经发送的paxosID,也即最新数据,比如为[minPaxosId,maxPaxosId]:

  • 在Master收到跳号请求时,要查询Master本地缓存中已经发送过的paxosID:
    • 如果minPaxosId<=msg.paxosId<=maxPaxosId,则直接从缓存中取出
    • 否则Master回应Learn,指示其应该进行catch up,catch up的意思是需要从master上传输大量数据,有可能是全部数据,以保证learn与master一致。
  • 在Learn收到catch up消息后,立即启动catch up过程,把Master上的数据全复制过来,从而保证了一致性

持久化

Keyspace无论是对paxosID的缓存还是最终数据,都是持久化到了BerkelyDB,这就保证了Node重启后算法的正确性。

容错

Keysapce做了很好的持久化,并充分相信BerkelyDB,可以解决网络、宕机等众多失败,但对BerkelyDB失败的情况是无法处理的,在实际中可以参考其catch up实现

问题

Keyspace的特点是所有的写都经过Master,所有的Node数据都与Master保持一致,但在实际中,需要的是动态分片、复制,而不是所有的节点数据都完全一致,因此跟Keyspace宣称的一样,它的目标只是做一个分布式底层,而不是终端产品。

5. Master选举

很显然,还有一个要解决的问题是Master宕机后如何选择新的Master,请参考:http://blog.csdn.net/chen77716/archive/2011/03/21/6265394.aspx

6. 疑问

在Keyspace对Paxos算法进行大刀阔斧地改造后,我们不仅要问这还是paxos算法吗?不考虑Master选举,这明明就是一个有Master来保证的一致性问题。

的确是的,但因为有网络延迟、节点重启、磁盘失败等诸多情况,如果没有多数派的投票机制,仅靠Master还是很难保证一致性,尤其是错误情况下的 正确性,因此,改造后的还是paxos算法,Google Chubby的人曾说,任何分布式一致性算法都是paxos的特例,这也算是特例之一。

其实原生的Paxos算法很难不加任何改造就在工程中实现,因为其有性能问题,这一点微软的人也说过。所以,不必在乎是否是血统纯正的paxos算法,只要把握住要领灵活应用即可,paxos不是有形的剑,而是无形的气,看你如何驾驭它,而不是被它驾驭。

分享到:
评论

相关推荐

    cassandra3.9配置参数说明

    allocate_tokens_for_keyspace参数被默认注释,但如果启用,它会尝试根据指定的键空间使用的复制策略选择令牌,以优化数据复制负载分布。 initial_token参数允许手动为节点指定令牌。它主要用于向未启用虚拟节点...

    该隐:Kubernetes上Cassandra的备份和还原工具

    使用nodetool snapshot获取备份数据-它在给定namespace keyspace中的所有Cassandra nodetool snapshot创建keyspace的快照(根据selector )。 使用将文件parallel复制到云存储-它将文件复制到指定的dst ,位于...

    监听redis的key的变化

    - **配置**:在Redis配置文件中启用Keyspace Notifications,设置`notify-keyspace-events`参数。不同的字母组合表示不同的事件类型,如K代表键被修改,E代表键被删除等。 - **事件类型**:包括键空间事件(如所有...

    cassandra入门demo

    在Cassandra中,Keyspace类似于关系数据库中的Database。使用CQL创建一个Keyspace,例如: ```sql CREATE KEYSPACE my_keyspace WITH replication = {'class': 'SimpleStrategy', 'replication_factor': '1'}; ``` ...

    java NoSql Cassandra hector

    3. 定义Keyspace和ColumnFamily:Cassandra中的数据存储在Keyspace(类似数据库)和ColumnFamily(类似表)中。Hector提供了相应的API来定义它们。 ```java KeyspaceDef keyspaceDef = HFactory....

    NoSQL数据库笔谈.pdf

    在手段篇中,文章详细探讨了多种分布式技术,如一致性哈希、Quorum机制、向量时钟、虚拟节点、Gossip协议(状态转移模型和操作转移模型)、Merkle树以及Paxos算法等。这些技术用于解决数据分布、复制、冲突检测和...

    Redis-3.2.100-Windows-32

    `notify-keyspace-events`是Redis配置中的一个选项,用于设置键空间通知(Keyspace Notifications)。它允许订阅者接收到关于键操作的事件通知,例如键的创建、删除、过期等,这对于监控、数据同步或者其他基于事件...

    Cassandra的基础应用

    - **创建键空间**:使用`CREATE KEYSPACE keyspace_name WITH REPLICATION = {'class' : 'SimpleStrategy', 'replication_factor' : 1};`创建键空间。 - **查询键空间**:使用`DESCRIBE KEYSPACES;`查看所有键空间...

    cassandra 安装教程

    - 使用`create keyspace Keyspace1;`命令创建一个新的Keyspace。 - 使用`use Keyspace1;`切换到刚创建的Keyspace。 2. **创建Column Family**: - 使用`create column family users with comparator=UTF8Type ...

    cassandra教程

    这个示例将'username'字段的值'doe'插入到Keyspace1的Standard1表中,对应的Key是'john'。 总的来说,Cassandra是一个强大的分布式数据库系统,适合处理大量数据并要求高可用性和可扩展性的应用场景。学习Cassandra...

    cassandra 学习

    - **列族**是键空间中的容器,类似于关系型数据库中的表。 - **行**是一组有序的列的集合,由主键标识。 **Cassandra查询语言(CQL)**是一种类似于SQL的语言,用于与Cassandra交互。它提供了一种简洁的方式来进行...

    skinny-test_2.11-1.2.7.zip

    在IT行业中,开源项目扮演着至关重要的角色,它们提供了丰富的资源和工具,使得开发者能够更高效地进行软件开发。"skinny-test_2.11-1.2.7.zip" 文件中包含的 "astyanax.zip" 是一个针对NETFLIX CasdRaJava客户端的...

    Java连接cassandra实现简单的增删查demo

    在Java编程环境中,连接Cassandra数据库并实现基本的增、删、查操作是常见的任务。Cassandra是一款分布式NoSQL数据库,常用于处理大规模数据。在这个示例中,我们将探讨如何通过Java来操作Cassandra数据库。 首先,...

    Vitess-Docs-8.0-10-27-2020.pdf

    - **Keyspace**:Keyspace是Vitess中的逻辑数据库,可以包含一个或多个分片。每个Keyspace有自己的分片策略和Vindexes。 - **MoveTables**:Vitess提供了一种机制,可以在线迁移表到不同的分片,无需停机。这个...

    Redis 中文文档

    #### 三、键空间通知(keyspace notification) 键空间通知是Redis为客户端提供的一种监听机制,允许客户端注册对键空间的变化进行监听。例如,当某个键被设置或删除时,可以通过该机制接收到通知。这对于构建实时...

    NoSQL数据库笔谈

    - **背景**: Paxos协议是一种解决分布式系统中一致性问题的算法。 - **作用**: 确保分布式系统中的所有节点就某个值达成一致。 ##### 8. 分布式哈希表(DHT) - **定义**: DHT是一种分布式的数据结构,用于在去中心化...

    NoSQL数据库学习教程.pdf

    Paxos是分布式系统中的一个概念,它是指使用Paxos协议来达成一致性。 背景是指分布式系统中的一个概念,它是指系统的架构和设计。 DHT是分布式系统中的一个概念,它是指使用分布式哈希表来存储数据。 Map Reduce ...

    C# Redis发布订阅Demo

    在C#中,通过`Subscribe`方法订阅`__keyspace@0__:keys`(或者其他数据库的`__keyspace@&lt;db&gt;__:keys`)频道,就可以监听所有数据库的Key事件。例如,当Key过期时,Redis会发送一个`expired`类型的事件。 ```csharp ...

    GoCrawler

    cqlsh&gt; use ptt_keyspace; 卡桑德拉清单表 cqlsh:ptt_keyspace&gt; desc tables; Cassandra列表表架构 cqlsh:ptt_keyspace&gt; desc table article; 卡桑德拉列表表记录 cqlsh:ptt_keyspace&gt; select * from article; ...

    32位版本的redis【 REDIS-WIN32-2.6】

    总结来说,`REDIS-WIN32-2.6`是一个针对32位Windows系统的Redis版本,它包含了一些关键特性,如lua脚本支持和Keyspace通知,而且通过提供的VBScript和bat脚本,使得在Windows环境中部署和管理Redis变得更加简单。...

Global site tag (gtag.js) - Google Analytics