分布式协议与算法
2020-06-01 17:13:43 2 举报
AI智能生成
登录查看完整内容
分布式协议与算法
作者其他创作
大纲/内容
分布式
CAP理论
CAP 理论对分布式系统的特性做了高度抽象,形成了三个指标:一致性(Consistency)可用性(Availability)分区容错性(Partition Tolerance)
一致性
一致性说的是客户端的每次读操作,不管访问哪个节点,要么读到的都是同一份最新的数据,要么读取失败。一致性强调的不是数据完整,而是各节点间的数据一致。也就是说,在客户端看来,集群和单机在数据一致性上是一样的。
可用性
可用性说的是任何来自客户端的请求,不管访问哪个节点,都能得到响应数据,但不保证是同一份最新数据。但不保证数据一致性
比如名字路由系统,如果仅仅因为发生了分布故障,节点中的数据会不一致,集群就拒绝写入新的路由信息,之后,当客户端查询相关路由信息时,系统就一直返回给客户端出错信息,那么相关的服务都将因为获取不到指定路由信息而不可用、瘫痪,这可以说是灾难性的故障了。
分区容错性
当节点间出现任意数量的消息丢失或高延迟的时候,系统仍然可以继续提供服务。也就是说,分布式系统在告诉访问本系统的客户端:不管我的内部出现什么样的数据同步问题,我会一直运行,提供服务。这个指标,强调的是集群对分区故障的容错能力。
因为分布式系统与单机系统不同,它涉及到多节点间的通讯和交互,节点间的分区故障是必然发生的,所以我要提醒你,在分布式系统中分区容错性是必须要考虑的。
CAP不可能三角
CAP 不可能三角说的是对于一个分布式系统而言,一致性(Consistency)、可用性(Availability)、分区容错性(Partition Tolerance)3 个指标不可兼得,只能在 3 个指标中选择 2 个。
如何使用 CAP 理论
我们都知道,只要有网络交互就一定会有延迟和数据丢失,而这种状况我们必须接受,还必须保证系统不能挂掉。所以就像我上面提到的,节点间的分区故障是必然发生的。也就是说,分区容错性(P)是前提,是必须要保证的。现在就只剩下一致性(C)和可用性(A)可以选择了:要么选择一致性,保证数据绝对一致;要么选择可用性,保证服务可用。
当选择了一致性(C)的时候,如果因为消息丢失、延迟过高发生了网络分区,部分节点无法保证特定信息是最新的,那么这个时候,当集群节点接收到来自客户端的写请求时,因为无法保证所有节点都是最新信息,所以系统将返回写失败错误,也就是说集群拒绝新数据写入。当选择了可用性(A)的时候,系统将始终处理客户端的查询,返回特定信息,如果发生了网络分区,一些节点将无法返回最新的特定信息,它们将返回自己当前的相对新的信息。
这里我想强调一点,大部分人对 CAP 理论有个误解,认为无论在什么情况下,分布式系统都只能在 C 和 A 中选择 1 个。 其实,在不存在网络分区的情况下,也就是分布式系统正常运行时(这也是系统在绝大部分时候所处的状态),就是说在不需要 P 时,C 和 A 能够同时保证。只有当发生分区故障的时候,也就是说需要 P 时,才会在 C 和 A 之间做出选择。而且如果各节点数据不一致,影响到了系统运行或业务运行(也就是说会有负面的影响),推荐选择 C,否则选 A。
CA 模型,在分布式系统中不存在。因为舍弃 P,意味着舍弃分布式系统,就比如单机版关系型数据库 MySQL,如果 MySQL 要考虑主备或集群部署时,它必须考虑 P。CP 模型,采用 CP 模型的分布式系统,一旦因为消息丢失、延迟过高发生了网络分区,就影响用户的体验和业务的可用性。因为为了防止数据不一致,集群将拒绝新数据的写入,典型的应用是 ZooKeeper,Etcd 和 HBase。AP 模型,采用 AP 模型的分布式系统,实现了服务的高可用。用户访问系统的时候,都能得到响应数据,不会出现响应错误,但当出现分区故障时,相同的读操作,访问不同的节点,得到响应数据可能不一样。典型应用就比如 Cassandra 和 DynamoDB。
ACID理论
ACID,是指在数据库管理系统(DBMS)中事务所具有的四个特性:原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation,又称独立性)、持久性(Durability)
原子性:事务必须是原子工作单元;对于其数据修改,要么全都执行,要么全都不执行。通常,与某个事务关联的操作具有共同的目标,并且是相互依赖的。如果系统只执行这些操作的一个子集,则可能会破坏事务的总体目标。原子性消除了系统处理操作子集的可能性。
一致性:事务在完成时,必须使所有的数据都保持一致状态。在相关数据库中,所有规则都必须应用于事务的修改,以保持所有数据的完整性
例如,当开发用于转帐的应用程序时,应避免在转帐过程中任意移动小数点。
隔离性:由并发事务所作的修改必须与任何其它并发事务所作的修改隔离。事务查看数据时数据所处的状态,要么是另一并发事务修改它之前的状态,要么是另一事务修改它之后的状态,事务不会查看中间状态的数据。
持久性:事务完成之后,它对于系统的影响是永久性的。该修改即使出现致命的系统故障也将一直保持。
事务(Transaction): 事务(Transaction)是并发控制的单位,是用户定义的一个操作序列。这些操作要么都做,要么都不做,是一个不可分割的工作单位。在关系数据库中,一个事务可以是一条SQL语句,一组SQL语句或整个程序。当对多个表进行更新的时候,某条执行失败。为了保持数据的完整性,需要使用事务回滚。
实现分布式系统 ACID 特性的方法
二阶段提交协议
是通过二阶段的协商来完成一个提交操作
先进入提交请求阶段(又称投票阶段)收到所有回复后,进入提交执行阶段(又称完成阶段), 也就是具体执行操作了
在第一个阶段,每个参与者投票表决事务是放弃还是提交。一旦参与者投票要求提交事务,那么就不允许放弃事务。也就是说,在一个参与者投票要求提交事务之前,它必须保证能够执行提交协议中它自己那一部分,即使参与者出现故障或者中途被替换掉。
TCC
TCC 是 Try(预留)、Confirm(确认)、Cancel(撤销) 3 个操作的简称,它包含了预留、确认或撤销这 2 个阶段。
第一步,预留阶段:苏秦分别发送消息通知赵、魏、韩,让他们预留明天的时间和相关资源。第二部,确认阶段,苏秦实现确认操作(明天攻打秦国)如果确认阶段出错执行撤销操作(取消明天攻打秦国
1.幂等性,是指同一操作对同一系统的任意多次执行,所产生的影响均与一次执行的影响相同,不会因为多次执行而产生副作用。常见的实现方法有 Token、索引等。它的本质是通过唯一标识,标记同一操作的方式,来消除多次执行的副作用。2. Paxos、Raft 等强一致性算法,也采用了二阶段提交操作,在“提交请求阶段”,只要大多数节点确认就可以,而具有 ACID 特性的事务,则要求全部节点确认可以。所以可以将具有 ACID 特性的操作,理解为最强的一致性。
BASE理论
定义:BASE理论是Basically Available(基本可用),Soft State(软状态)和Eventually Consistent(最终一致性)三个短语的缩写。
基本可用
什么是基本可用呢?假设系统,出现了不可预知的故障,但还是能用,相比较正常的系统而言:响应时间上的损失:正常情况下的搜索引擎0.5秒即返回给用户结果,而基本可用的搜索引擎可以在2秒作用返回结果。功能上的损失:在一个电商网站上,正常情况下,用户可以顺利完成每一笔订单。但是到了大促期间,为了保护购物系统的稳定性,部分消费者可能会被引导到一个降级页面。
软状态
什么是软状态呢?相对于原子性而言,要求多个节点的数据副本都是一致的,这是一种“硬状态”。软状态指的是:允许系统中的数据存在中间状态,并认为该状态不影响系统的整体可用性,即允许系统在多个不同节点的数据副本存在数据延时。
最终一致性
软状态,然后不可能一直是软状态,必须有个时间期限。在期限过后,应当保证所有副本保持数据一致性,从而达到数据的最终一致性。这个时间期限取决于网络延时、系统负载、数据复制方案设计等等因素。
实现基本可用的 4 板斧
流量削峰、延迟响应、体验降级、过载保护这 4 板斧
最终的一致
最终一致性是说,系统中所有的数据副本在经过一段时间的同步后,最终能够达到一个一致的状态。也就是说,在数据一致性上,存在一个短暂的延迟。
的核心就是基本可用(Basically Available)和最终一致性(Eventuallyconsistent)。根据业务的场景特点,来实现非常弹性的基本可用,以及实现数据的最终一致性。 BASE 理论主张通过牺牲部分功能的可用性,实现整体的基本可用,也就是说,通过服务降级的方式,努力保障极端情况下的系统可用性。
分区容错一致性Raft算法
痛点
受限于 Raft 的强领导者模型。所有请求都在领导者节点上处理,整个集群的性能等于单机性能。这样会造成集群接入性能低下,无法支撑海量或大数据量的时序数据。
一致哈希算法:如何分群,突破集群的“领导者”限制?
背景:如果我们通过 Raft 算法实现了 KV 存储,虽然领导者模型简化了算法实现和共识协商,但写请求只能限制在领导者节点上处理,导致了集群的接入性能约等于单机,那么随着业务发展,集群的性能可能就扛不住了,会造成系统过载和服务不可用,这时该怎么办呢?其实这是一个非常常见的问题。在我看来,这时我们就要通过分集群,突破单集群的性能限制了。对 Key 做哈希找到对应的集群就可以了,哈希算法的确是个办法,但它有个明显的缺点:当需要变更集群数时(比如从 2 个集群扩展为 3 个集群),这时大部分的数据都需要迁移,重新映射,数据的迁移成本是非常高的。那么如何解决哈希算法,数据迁移成本高的痛点呢?答案就是一致哈希(Consistent Hashing)。
一致性hash寻址
一致哈希算法也用了取模运算,但与哈希算法不同的是,哈希算法是对节点的数量进行取模运算,而一致哈希算法是对 2^32 进行取模运算。你可以想象下,一致哈希算法,将整个哈希值空间组织成一个虚拟的圆环,也就是哈希环:
过程:首先,将 key 作为参数执行 c-hash() 计算哈希值,并确定此 key 在环上的位置;然后,从这个位置沿着哈希环顺时针“行走”,遇到的第一节点就是 key 对应的节点。
使用了一致哈希算法后,扩容或缩容的时候,都只需要重定位环空间中的一小部分数据。也就是说,一致哈希算法具有较好的容错性和可扩展性。
客户端访问请求集中在少数的节点上,出现了有些机器高负载,有些机器低负载的情况,那么在一致哈希中,有什么办法能让数据访问分布的比较均匀呢?
虚拟节点
就是对每一个服务器节点计算多个哈希值,在每个计算结果位置上,都放置一个虚拟节点,并将虚拟节点映射到实际节点。比如,可以在主机名的后面增加编号,分别计算“Node-A-01”“Node-A-02”“Node-B-01”“Node-B-02”“Node-C-01”“Node-C-02”的哈希值,于是形成 6 个虚拟节点
一致哈希是一种特殊的哈希算法,在使用一致哈希算法后,节点增减变化时只影响到部分数据的路由寻址,也就是说我们只要迁移部分数据,就能实现集群的稳定了。当节点数较少时,可能会出现节点在哈希环上分布不均匀的情况。这样每个节点实际占据环上的区间大小不一,最终导致业务对节点的访问冷热不均。需要你注意的是,这个问题可以通过引入更多的虚拟节点来解决。最后我想说的是,一致哈希本质上是一种路由寻址算法,适合简单的路由寻址场景。比如在KV 存储系统内部,它的特点是简单,不需要维护路由信息。
12 | Quorum NWR算法:想要灵活地自定义一致性,没问题!
NWR 的三要素
N 表示副本数,又叫做复制因子(Replication Factor)。也就是说,N 表示集群中同一份数据有多少个副本
在实现 Quorum NWR 的时候,你需要实现自定义副本的功能。也就是说,用户可以自定义指定数据的副本数,比如,用户可以指定 DATA-1 具有 2 个副本,DATA-2 具有 3 个副本
W,又称写一致性级别(Write Consistency Level),表示成功完成 W 个副本更新,才完成写操作
DATA-2 的写副本数为 2,也就说,对 DATA-2 执行写操作时,完成了 2 个副本的更新(比如节点 A、C),才完成写操作。
R,又称读一致性级别(Read Consistency Level),表示读取一个数据对象时需要读 R个副本。你可以这么理解,读取指定数据时,要读 R 副本,然后返回 R 个副本中最新的那份数据
DATA-2 的读副本数为 2。也就是说,客户端读取 DATA-2 的数据时,需要读取 2 个副本中的数据,然后返回最新的那份数据。
通过设置 R 为 2,即使读到前面问题中的第三份副本数据(比如节点 B),也能返回更新后的那份数据,实现强一致性了。
N、W、R 值的不同组合,会产生不同的一致性效果
当 W + R > N 的时候,对于客户端来讲,整个系统能保证强一致性,一定能返回更新后的那份数据。当 W + R < N 的时候,对于客户端来讲,整个系统只能保证最终一致性,可能会返回旧数据。
当 W + R > N 时,可以实现强一致性。另外,如何设置 N、W、R 值,取决于我们想优化哪方面的性能。比如,N 决定了副本的冗余备份能力;如果设置 W = N,读性能比较好;如果设置 R = N,写性能比较好;如果设置 W = (N + 1) / 2、R = (N + 1) / 2,容错能力比较好,能容忍少数节点(也就是 (N - 1) / 2)的故障。
如何实现 Quorum NWR?
在 InfluxDB 企业版中,可以在创建保留策略时,设置指定数据库(Database)对应的副本数,具体的命令,就像下面的样子:create retention policy “rp_one_day” on “telegraf” duration 1d replication 3通过 replication 参数,指定了数据库 telegraf 对应的副本数为 3。
InfluxDB 企业版,支持“any、one、quorum、all”4 种写一致性级别
any:任何一个节点写入成功后,或者接收节点已将数据写入 Hinted-handoff 缓存(也就是写其他节点失败后,本地节点上缓存写失败数据的队列)后,就会返回成功给客户端。one:任何一个节点写入成功后,立即返回成功给客户端,不包括成功写入到 Hinted\u0002handoff 缓存。quorum:当大多数节点写入成功后,就会返回成功给客户端。此选项仅在副本数大于 2时才有意义,否则等效于 all。all:仅在所有节点都写入成功后,返回成功。
16 | InfluxDB企业版一致性实现剖析:他山之石,可以攻玉
什么是时序数据库?
时序数据库,就是存储时序数据的数据库,就像 MySQL 是存储关系型数据的数据库。而时序数据,就是按照时间顺序记录系统、设备状态变化的数据,比如CPU 利用率、某一时间的环境温度等
时序数据最大的特点是数据量很大,可以不夸张地说是海量。时序数据主要来自监控(监控被称为业务之眼),而且在不影响业务运行的前提下,监控埋点是越多越好,这样才能及时发现问题、复盘故障。
META 节点
META 节点存放的是系统运行的关键元信息,比如数据库(Database)、表(Measurement)、保留策略(Retention policy)等。它的特点是一致性敏感,但读写访问量不高,需要一定的容错能力。
DATA节点
DATA 节点存放的是具体的时序数据。它有这样几个特点:最终一致性、面向业务、性能越高越好,除了容错,还需要实现水平扩展,扩展集群的读写性能。
如何实现 META 节点一致性?
META 节点存放的是系统运行的关键元信息,那么当写操作发生后,就要立即读取到最新的数据。比如,创建了数据库“telegraf”,如果有的 DATA 节点不能读取到这个最新信息,那就会导致相关的时序数据写失败,肯定不行。
META 节点需要强一致性,实现 CAP 中的 CP 模型,使用raft算法
如何实现 DATA 节点一致性?
DATA 节点存放的是具体的时序数据,对一致性要求不高,实现最终一致性就可以了。但是,DATA 节点也在同时作为接入层直接面向业务,考虑到时序数据的量很大,要实现水平扩展,所以必须要选用 CAP 中的 AP 模型,因为 AP 模型不像 CP 模型那样采用一个算法(比如 Raft 算法)就可以实现了,也就是说,AP 模型更复杂,具体有这样几个实现步骤。能实现 AP型分布式系统
自定义副本数
你需要考虑冗余备份,也就是同一份数据可能需要设置为多个副本,当部分节点出问题时,系统仍然能读写数据,正常运行。
Hinted-handoff
一个节点接收到写请求时,需要将写请求中的数据转发一份到其他副本所在的节点,那么在这个过程中,远程 RPC 通讯是可能会失败的,比如网络不通了,目标节点宕机了
那么如何处理这种情况呢?答案是实现 Hinted-handoff。在 InfluxDB 企业版中,Hinted-handoff 是这样实现的:写失败的请求,会缓存到本地硬盘上 ;周期性地尝试重传 ;相关参数信息,比如缓存空间大小 (max-szie)、缓存周期(max-age)、尝试间隔(retry-interval)等,是可配置的。在这里我想补充一点,除了网络故障、节点故障外,在实际场景中,临时的突发流量也会导致系统过载,出现 RPC 通讯失败的情况,这时也需要 Hinted-handoff 能力。虽然 Hinted-handoff 可以通过重传的方式来处理数据不一致的问题,但当写失败请求的数据大于本地缓存空间时,比如某个节点长期故障,写请求的数据还是会丢失的,最终的节点的数据还是不一致的,那么怎么实现数据的最终一致性呢?答案是反熵。
反熵
实现反熵是以什么为准来修复数据的不一致呢?我想说的是,时序数据像日志数据一样,创建后就不会再修改了,一直存放在那里,直到被删除。所以,数据副本之间的数据不一致,是因为数据写失败导致数据丢失了,也就是说,存在的都是合理的,缺失的就是需要修复的。这时我们可以采用两两对比、添加缺失数据的方式,来修复各数据副本的不一致了。
Quorum NWR
如何实现分布式集群推荐使用 Raft 算法实现分布式集群
创建集群
在 Raft 算法中,我们可以这样创建集群。先将第一个节点,通过 Bootstrap 的方式启动,并作为领导者节点。其他节点与领导者节点通讯,将自己的配置信息发送给领导者节点,然后领导者节点调用 AddVoter() 函数,将新节点加入到集群中。
写操作
方法 1:跟随者接收到客户端的写请求后,拒绝处理这个请求,并将领导者的地址信息返回给客户端,然后客户端直接访问领导者节点,直到该领导者退位
方法 2:跟随者接收到客户端的写请求后,将写请求转发给领导者,并将领导者处理后的结果返回给客户端,也就是说,这时跟随者在扮演“代理”的角色
综合
在我看来,虽然第一种方法需要客户端的配合,但实现起来复杂度不高;另外,第二种方法,虽然能降低客户端的复杂度,客户端像访问一个黑盒一样,访问系统,对领导者变更完全无感知。但是这个方法会引入一个中间节点(跟随者),增加了问题分析排查的复杂度。而且,一般情况下,在绝大部分的时间内(比如 Google Chubby 团队观察到的值是数天),领导者是处于稳定状态的,某个节点一直是领导者,那么引入中间节点,就会增加大量的不必要的消息和性能消耗。所以,综合考虑,我推荐方法 1。
读操作
实现多种读一致性模型,将最终的一致性选择权交给用户,让用户去选择,就像下面的样子。1 curl -XGET http://raft-cluster-host02:8091/key/foo?level=consistent -L
类似 Consul 的 3 种读一致性模型。default:偶尔读到旧数据。consistent:一定不会读到旧数据。stale:会读到旧数据。
数据存储
决定数据层组件的成本的最关键的一个理念是冷热分离,一般而言,可以这么设计三级缓存:热数据:经常被访问到的数据,我们可以将它们放在内存中,提升访问效率。冷数据:有时会被访问到的数据,我们可以将它们放在 SSD 硬盘上,访问起来也比较快。陈旧数据:偶尔会被访问到的数据,我们可以将它们放在普通磁盘上,节省存储成本。在实际系统中,你可以统计热数据的命中率,并根据命中率来动态调整冷热模型。在这里,我想强调的是,冷热分离理念在设计海量数据存储系统时尤为重要,比如,自研 KV 存储的成本仅为 Redis 数十分之一,其中系统设计时非常重要的一个理念就是冷热分离。希望你能重视这个理念,在实际场景中活学活用。
0 条评论
回复 删除
下一页