加载中 ...

无中心化是如何实现的?

2019-01-08 11:28 编辑:btc268.com 来源:区块链资讯

  IPFS中国社区

  人人都是节点

 

  作者丨周明耀

  本文是 Apache Cassandra 3.X 系列的第三部分,介绍了 Cassandra 如何实现无中心化架构,特别对架构内部起实际作用的各项技术点进行了深入介绍,首先从针对无中心化的分布式系统的设计思维开始讨论,逐渐引申出 Cassandra 的特有特征。

设计无中心化系统

  假设请您设计一款无中心化的分布式系统,您觉得应该怎么来设计?

  我如果收到这样的无中心化设计需求,首先第一步是明确什么是无中心化?我认为,无中心化需求应该可以被分解为数据存储无中心化和读/写操作无中心化两个需求。

  如果想要我们设计的系统同时支持这两个无中心化需求,我们设计的系统应该满足以下条件:

  1.数据需要均匀分布在集群内的每一个节点上;

  2.同一份数据需要支持在集群内多个不同的节点内存在;

  3.不存在固定的中心节点,也不存在仅保存在中心节点的集群元数据;

  4.集群内的通信架构是按照整个集群思维设计的,而不是按照中心化思维设计;

  5.通信消息需要某种机制确保互相之间知道最新的状态;

  6.需要有某种机制确保客户端请求读取的数据副本是最新版本的。

  结合以上这些需求,我们来找找看业界的分布式系统。我们知道的一些知名的分布式系统,例如 HBase、HDFS、MongoDB,它们确实都是分布式的,但是 HBase 有 HMaster,HDFS 有 NameNode,MongoDB 有 Mongos,这些名词分别起什么作用?

  HMaster:用于管理 HRegionServer,实现其负载均衡;

  管理和分配 HRegion,比如在 HRegion split 时分配新的 HRegion;在 HRegionServer 退出时迁移其内的 HRegion 到其他 HRegionServer 上;

  实现 DDL 操作(Data Definition Language,namespace 和 table 的增删改,column familiy 的增删改等);

  管理 namespace 和 table 的元数据(实际存储在 HDFS 上);

  权限控制(ACL)。

  

图 1. HBase 架构图

  NameNode:维护着文件系统树(FILesystem tree)以及文件树中所有的文件和文件夹的元数据(metADAta)。管理这些信息的文件有两个,分别是 Namespace 镜像文件(Namespace image)和操作日志文件(edit log),这些信息被 Cache 在 RAM 中,当然,这两个文件也会被持久化存储在本地硬盘。

  

图 2. HDFS 架构图

  Mongos:数据库集群请求的入口,所有的请求都通过 mongos 进行协调,不需要在应用程序添加一个路由选择器,mongos 自己就是一个请求分发中心,它负责把对应的数据请求请求转发到对应的 shard 服务器上。在生产环境通常有多 mongos 作为请求的入口,防止其中一个挂掉所有的 mongodb 请求都没有办法操作。架构如图所示。

  

图 3. MongoDB 架构图

  综上所述,这些分布式系统都存在固定的中心节点,并且通信都是围绕这一中心化架构进行设计的,所以不能称为无中心化设计,即便可以针对中心节点做集群化设计,依然存在中心概念,也就没有消除节点之间的差异性。我们来看看 Cassandra。

  根据公开的资料显示,Cassandra 是无中心化的,每一个节点都可能担任协调者角色,也可能担任数据备份角色,这也意味着所有节点没有差异,也不会存在差异,因为所有行为都是按照规则约束的随机行为,因此可以认为所有节点本质上是没有差异的。具体内容我们接着逐一介绍。

  

  

Cassandra 的无中心化设计元素


Gossip

  为什么使用

  

  为什么 Cassandra 能够做到各个节点之间无差异对待?因为 Cassandra 使用了 Gossip 协议。Gossip 协议允许每个节点每秒钟(可调整)自动运行,用以保持追踪集群内其他节点的状态信息。

  Gossip 协议(有时候也被称为八卦协议)通常被用在大型的无中心化网络环境中,并且假设网络环境不太稳定,这种协议也被用在分布式数据库的自动备份机制里面。

  从何而来

  

  Gossip 协议取自人类的"八卦"概念,两个人只要愿意,可以随时互相交换信息。Gossip 协议最初是在 1987 年由 Alan Demers 发明的,他当时是 Xerox 的 Palo Alto 研究中心的研究员,专门研究在不可信网络环境中路由信息的方式。

  Gossip 协议在 Cassandra 里被定义在类 Gossiper,负责本地节点的 Gossip 管理。当一个服务节点启动的时候,它会把自己注册到 Gossip,用于接受终端(endpoint)状态信息,因此就有了 Cassandra 网络内交换信息的数据基础架构层。

  因为 Cassandra 的 Gossip 是为失败检测服务的,Gossiper 类维护了一个节点列表,这个列表里包括存活的和死亡的节点。

  工作流程

  

  我们来看看 Gossiper 的工作流程:

  1.每一秒钟,Gossiper 会随机选择集群内的一个节点,初始化和它之间的 Gossip 会话。每一轮 Gossip 需要三组数据;

  2.Gossip 初始化器选择一个节点发送一个 GossipDigestSynMessage;

  3.当节点收到这个信息,它返回一个 GossipDigestAackMessage;

  4.当初始化器从节点收到一个 ack 信息,它会发送给节点一个 GossipDigestAck2Message 以完成本轮 Gossip。

  流程如图 1 所示。

  

图 4. Gossiper 交互流程图

  注意,当 Gossiper 决定另一个终端死亡,它会在本地列表中标记该节点死亡并且做记录。

  节点之间初始化 Gossip 交换需要遵循以下准则:

  1.随机 Gossip 到存活节点(所有节点);

  2.随机 Gossip 到不可达节点,这是在依赖于不可达和存活节点的一定概率;

  3.存活节点的数量小于种子数,或者没有种子,随机 Gossip 种子依赖于未达或者存活节点的概率。

  这个准则是为了确保一旦网络启动,所有的节点最终都可以拿到其他节点的状态。

  为了明确节点是否存活,Gossiper 类的方法实现如清单 1 所示。

清单 1. 明确节点是否存活

  1

  2

  3

  4

  5

  6

  7

  8

  9

  10

  11

  12

  13

  14

  15

  16

  17

  public void convict(InetAddress endpoint, double phi)

  {

          EndpointState epState = endpointStateMap.get(endpoint);

          if (epState == null)

              return;

          if (!epState.isAlive())

              return;

          logger.debug("Convicting {} with status {} - alive {}", endpoint, getGossipStatus(epState), epState.isAlive());

          if (isShutdown(endpoint))

          {

              markAsShutdown(endpoint);

          }

          else

          {

              markDead(endpoint, epState);

          }

  }

  GossipTask 是位于 org.apche.cassandra.gms.Gossip 类下的一个内部类,这个类负责管理本地节点的 Gossip。当一个服务节点启动后,这个类把自己注册到 Gossiper,用以接收终端状态信息。

  GossipTask 的 run 方法如下:

  主要做了几件事:

  1.GossipTask 在 Gossip 启动后并不会立即运行,阻塞在 listenGate 这个变量上,当 Gossip 服务调用 listen 时才开始运行;

  2.首先更新本节点的心跳版本号,然后构造需要发送给其他节点的消息 gDigests;

  3.从存活节点中随机选择一个节点发送、从失效节点中随机选取一个发送。如果当前存活节点数小于种子数,向其中一个种子节点发送消息;

  检查节点状态。

  GossipTask 用于向其他节点发送 Gossip 消息,Cassandra 还提供了 SOCketThread 这样一个线程来负责接收消息,接收消息的代码在 org.apache.cassandra.net.IncomingTcpConnection 类中。不管是发送还是接收 Gossip 消息,都是调用 org.apache.Cassandra.MessagingServcice 的 sendOneWay 方法实现的。


清单 2. GossipTask 类的线程执行代码

  1

  2

  3

  4

  5

  6

  7

  8

  9

  10

  11

  12

  13

  14

  15

  16

  17

  18

  19

  20

  21

  22

  23

  24

  25

  try

  {

         //wait on messaging service to start listening

         MessagingService.instance().waitUntilListening();

         taskLock.lock();

         /* Update the local heartbeat counter. */

        endpointStateMap.get(FBUtilities.getBroadcastAddress()).gETHeartBeatState().updateHeartBeat();

        if (logger.isTraceEnabled())

            logger.trace("My heartbeat is now {}", endpointStateMap.get(FBUtilities.getBroadcastAddress()).getHeartBeatState().getHeartBeatVersion());

            final List<GossipDigest> gDigests = new ArrayList<GossipDigest>();

            Gossiper.instance.makeRandOMGossipDigest(gDigests);

            if (gDigests.size() > 0)

            {

                GossipDigestSyn digestSynMessage = new GossipDigestSyn(DatabaseDescriptor.gETClusterName(),

                DatabaseDescriptor.getPartitionerName(),gDigests);

                MessageOut<GossipDigestSyn> message = new MessageOut<GossipDigestSyn>(MessagingService.Verb.GOSSIP_DIGEST_SYN, digestSynMessage, GossipDigestSyn.serializer);

                /* Gossip to some random live member */

                boolean gossipedToSeed = doGossipToLiveMember(message);

                /* Gossip to some unreachable member with some probability to check if he is back up */

                maybeGossipToUnreachableMember(message);

                if (!gossipedToSeed || liveEndpoints.size() < seeds.size())

                    maybeGossipToSeed(message);

                doStatusCheck();

            }

  }

  适用场景

  

  Gossip 比较适合在没有很高一致性要求的场景中用于信息的同步。信息达到同步的时间大概是 log(N),这个 N 表示节点的数量。Gossip 中的每个节点维护一组状态,状态可以用一个 key/value 对表示,还附带了一个版本号,版本号大的为最新更新的状态。

  总结

  

  Cassandra 集群中的节点没有主次之分,通过 Gossip 协议,可以知道集群中有哪些节点,以及这些节点的状态如何等等。每一条 Gossip 消息上都有一个版本号,节点可以对接收到的消息进行版本比对,从而得知哪些消息是我需要更新的,哪些消息是我有而别人没有的,然后互相倾听吐槽,确保二者得到的信息相同,这很像现实生活中的八卦,一传十,十传百,最后尽人皆知。

  在 Cassandra 启动时,会启动 Gossip 服务,Gossip 服务启动后会启动一个任务 GossipTask,每秒钟运行一次,这个任务会周期性与其他节点进行通信。

  因为有了 Gossip 协议,所以能够满足我们之前提出的 3-5 条需求。

Snitch


  既然 Cassandra 是无中心化的,那么如何来计算各个节点上存储的数据之间的差异呢?如何判断自己申请的那一份数据就是最新版本的?这里我要引出 Snitch(告密者)机制了。

  现实生活中的"告密者"会向别人告密谁有需要寻找的东西,Snitch 机制在 Cassandra 集群里也起到了这样的作用。Snitch 机制的功能是决定集群每个节点之间的相关性(值),这个值被用于决定从哪个节点读取或写入数据。此外,由于 Snitch 机制收集网络拓扑内的信息,这样 Cassandra 可以有效路由各类外部请求。Snitch 机制解决了节点与集群内其他节点之间的关系问题(前面介绍的 Gossip 解决了节点之间的消息交换问题)。

  当 Cassandra 收到一个读请求,需要去做的是根据一致性级别联系对应的数据副本。为了支持最快速度的读取请求,Cassandra 选择单一副本读取全部数据,然后要求附加数据副本的 hash 值,以此确保读取的数据是最新的数据并返回。Snitch 的角色是帮助验证返回最快的副本,这些副本又被用于读取数据。

  默认的 snitch 是 SimpleSnitch,它对网络拓扑不敏感,也就是说,对于集群内的机架和数据中心,它根本不认识,所以不适用多数据中心方案。针对这个原因,Cassandra 对云端环境(Amazon EC2、Google Cloud、Apache Cloudstack)提供了多种 Snitch。

  Snitch 的代码在 org.apache.cassandra.locator 包,每个 snitch 类都通过继承超类 AbstractEndpointSnitch 实现了 IEndPointSnitch 接口。

  Snitches 按实现分为三种:

  

  1.SimpleSnitch:这种策略不能识别数据中心和机架信息,适合在单数据中心使用;

  2.NetworkTopologySnitch:这种策略提供了网络拓扑结构,以便更高效地消息路由;

  3.DynamicEndPointSnitch:这种策略可以记录节点之间通信时间间隔,记录节点之间的通信速度,从而达到动态选择最合适节点的目的。

  再次强调,Snitches 收集整个网络拓扑信息,这样 Cassandra 集群可以有效地路由请求。Snitch 内部会解决节点之间的关联关系。通过引入 Snitch 机制,解决了第 6 条需求。

协调者(Coordinator)


  前面介绍的 Gossip 协议和 Snitch 机制为无中心化设计提供了通信基础架构,那么当用户对 Cassandra 集群进行请求操作时,哪个节点来处理这些请求呢?HDFS 有 NameNode,Cassandra 呢?Cassandra 有协调者。

  理论上来说,每一个节点都可以作为协调者。协调者是在每一次请求时被挑选出来的,我们可以通过指定使用哪种机制进行协调者的选择,例如轮询算法(Round-Robin,默认算法),也可以通过 DC-aware 或者 LatencyAware,在 cassandra.yaml 文件里面指定。一旦选择成功,就会通过"八卦"协议在集群内部传播。

  当外部请求需要向集群里写入数据时,该请求所指定的一致性级别(consistency level)决定了协调者节点需要接触几个节点之后才能返回结果。协调者节点会根据分区键和副本策略决定将请求发给哪些可用节点。如下图所示,假设节点 1 是第一个副本,节点 2 和节点 3 都是副本节点。

  协调者节点会等待满足一致性要求的所有节点返回后才返回结果给客户端。以 QUORUM 为本例一致性级别要求,需要根据公式(n/2 1)进行计算,这里 n 指的是副本因子。这里由于 n 等于 3,因此 3/2 1=2,即需要等待至少 2 个节点返回信息后才能决定是否返回客户端成功标记。

图 5. Coordinator 节点工作模式图通过该机制可以动态确定一个节点作为数据链路的临时大脑,由它来发起、组织、汇总元数据的计算结果,并将真正的处理请求发送给明确的节点,所有节点理论上都可以作为协调者,所以也就实现了节点无差异需求。Rings 和 Tokens


  前面两条解决了 3-6 条需求,那么我们现在解决第 1、第 2 条需求。

  Cassandra 集群内的数据被管理为一个 Ring(环形)。Ring 内的每个节点被分配 1 到多个数据范围(也就是 token),这个 token 决定了 ring 内部的分区。什么是 Token?Token 是一个 64 位的整数 ID,被用于区分每个分区,通常是-2 的 63 次方到 2 的 63 次方-1。

  通过 hash 函数去决定分区键的 token 值,这样就能知道数据被分配到了哪个节点。分区键 token 会和各个节点的 token 值比较,然后决定哪些节点拥有该数据。Token 范围在 org.apache.cassandra.dht.Range 类里面实现。

图 6. Cassandra 主要概念关系图上面这张图是一个 Cassandra 环形数据分布的例子,例子中把数据分为了 255 个 token,均匀地分布在 4 个节点上。虚拟节点(Virtual Nodes)


  除了上面这个特性以外,虚拟节点、Partitioners(分区)也起到了数据分布均衡作用。

  早期的 Cassandra 为每一个节点分配单一的令牌,基于公平原则,需要你为每一个节点计算令牌。虽然有工具可以基于给定的节点数量计算令牌值,在 cassandra.yaml 文件里仍然需要手动过程为每一个节点配置 initial_token 属性,增加或者替换节点时也会有额外的工作,这种设计造成一种情况,就是为了平衡集群需要移动大量的数据。

  Cassandra1.2 开始引入了虚拟节点概念,也叫作 vnodes。替代了对于一个节点分配单一令牌方式,令牌范围被分片为多个小范围,每一个物理节点被分配多个令牌。默认每个节点被分配 256 个令牌,意味着包含 256 个虚拟节点,虚拟节点在 V2.0 正式成为默认选项。

  虚拟节点让包含异构机器的集群更加容易维护。对于集群内的节点有更多的可用计算资源,你可以通过改变 num_tokens 属性方式增大虚拟节点数量。相反地,也可以减少可用机器能力。

  Cassandra 自动处理令牌范围的计算对于集群内的每一个节点,令牌设置算法在类 org.apache.cassandra.dht.tokenallocator.ReplicationAwareTokenAllocator。

  虚拟节点的好处是加速了重量级的 Cassandra 操作,例如引导新节点、淘汰老节点、替换节点等。这是因为多个小型范围内的这些操作相关的加载操作在集群内部是跨节点的。

Partitioners(分区)


  Cassandra 使用 shared nothing 架构,因此每个节点都需要负责数据的存储。

  分区决定数据在分布式环境下如何分布的。Cassandra 存储数据在跨度行上,或者"分片"。每一行有一个分区键,被用于认证分区。每行数据都有一个分区键被用于验证分区。分区是 hash 函数用于计算每个分区键的 token。

  Cassandra 提供了几种不同的分区器(org.apache.cassandra.dht 包,DHT 的全称是 distributed hash table)。Murmur3Partitioner 是默认的分区器,生成 64 位 hash。支持通过申明 org.apache.cassandra.dht.IPartitioner 类并放置在 Cassandra 的 classpath 下启用自定义的分区器。

复制策略(Replication Strategy)


  Cassandra 使用 shared nothing 架构,因此每个节点都需要负责数据的存储,这样就引入了单点故障问题,即节点宕机后数据就不可被访问了。克服这种问题的方式是进行数据备份,避免单点故障。

  数据副本的作用是当一个节点宕机,其他节点可以响应数据查询。如果副本系数是 3,那么每一行在环形节点里有 3 份。

  为了决定副本位置,Cassandra 提供了四种策略模式,所有策略都实现了抽象接口类 org.apache.cassandra.locator.AbstractReplicationStrategy。

  如果一个节点宕机了,其他节点也可以被用于处理数据的查询请求。第一个副本一般情况下是拥有令牌的节点,但是其余的副本则是根据副本策略决定的。

结束语


  本文主要介绍了 Cassandra 如何实现无中心化架构,首先通过 Gossip 协议让内部节点之间的消息传送方式实现同质化,即所有节点都被相同对待,互相交换信息,而不是将信息汇总于某一个或某几个特点的节点。

  接下来介绍了 Snitch 机制,通过该机制解决了多个节点上数据副本的版本比较,确保在最短读取路径前提下返回最新版本的数据给客户端调用方。

  然后介绍协调者机制,通过该机制可以动态确定一个节点作为数据链路的临时大脑,由它来发起、组织、汇总元数据的计算结果,并将真正的处理请求发送给明确的节点,所有节点理论上都可以作为协调者,所以也就实现了节点无差异需求。

  最后通过环形数据分布、令牌机制、虚拟节点、数据分区以及数据复制策略等实现了数据的均匀分布,为无中心化实现提供了基础。

  从 Cassandra 的无中心化设计分析,没有哪一个设计可以是通过单一功能实现的,都是基于若干个复杂特性互相帮助的基础上实现的。

参考资源


  参考 developerWorks 上的 Apache Cassandra,了解更多 Apache Cassandra 知识。

  参考书籍 Cassandra The Definitive Guide 2nd Edition Jeff Carpenter&Eben Hewitt

  如果社区成员希望开发 

  去中心化数据库系统

  有兴趣的大牛可以与我们联系

  

  

  什么是IPFS?

  IPFS是一个分布式的存储项目,与激励层Filecoin形成了一个有效的市场闭环,构建出一个去中心化存储网络系统。

Filecoin是2017年最大的私募项目,短短时间募集了2.57亿美元。目前期货价格约45.5元左右,按照20亿枚Token计算,未上线已市值910亿人民币。

  我们是IPFS中国社区,垂直专注于IPFS领域,努力提供客观的、第三方的IPFS、Filecoin、挖矿等最新资讯,共同推进IPFS相关应用的发展,建立一个良好的IPFS生态圈。 

  热门阅读

IPFS生态研究报告破纪录的顶级风险投资Filecoin ICOFilecoin挖矿逻辑:分布式非均衡企业级弹性矿池探讨

  IPFS中国社区赖楚航:IPFS如何构建下一代互联网

  _________________________

  

  公众号后台回复【社群】

  加入IPFS中国社群哦~

  点击【阅读原文】,可以浏览我们的官网哦~

转载自比特币新闻网(www.btc268.com),提供比特币行情走势分析与数字货币投资炒币最新消息。

原文标题:无中心化是如何实现的?

原文地址:http://www.btc268.com/qkl/zs/4114.html

本文来源:区块链资讯编辑:btc268.com

本文仅代表作者个人观点,与本网站立场无关。

本网站转载信息目的在于传递更多信息。请读者仅作参考,投资有风险,入市须谨慎!

'); })();