Tagged: replication

0

无leader replication的实现和问题介绍

我们在前面的《多leader replication的实现及常见问题介绍》和《分布式系统之leader-followers Replication深入介绍》分别介绍了多leader和单leader的情况,也许你会好奇是否有无leader的实现呢?答案是肯定的,本文就来深入介绍无leader replication的实现和相关的问题。 其实最早期的时候有很多无leader的实现,就是任何节点都可以进行写。后来慢慢大家就不太使用这个实现了,直到Amazon推出了它的Dynamo系统,这一实现又再次流行起来。现在Riak,cassandra以及Voldermort都是开源的无leader的数据库实现。 如何处理有节点出问题的写 在有leader的架构中,当有节点出现问题(假如在leader上),我们需要做failover,然后才能继续写。而在一个没有leader的结构中,failover就不存在,所以当有节点出问题时,整个流程如下图所示:客户端会给每一个节点发送写的请求,我们现在假设三个节点中有一个失败了,并且我们认为大多数节点写成功就是一个成功写,这里有两个节点写成功了,所以整个写操作是成功的,因此对user1234来说,这个写是ok的。 这样的实现问题很明显,比如说现在节点3恢复了,这个时候,任何到replica3的读都会有问题,因为它丢失了在出问题那段时间的写操作。一个比较简单的解决方案就是,读操作也不是只发送给一个节点,我们同时给三个节点发送,然后根据返回数值所在的version来决定谁是最新的,谁最新我们就使用谁。 读修复和反熵(Anti-entropy) 在分布式系统中,我们希望每一个replica最终都是一样的,所以就希望上文提到的replica3在回来之后能够通过一定的手段修复,就是得到它offline这段时间发生的写操作。那么如何才能达到这个效果呢?一般有以下的方法: 读修复(read pair) 当客户端从多个replica中读取数据的时候,它能看到哪个是最新的,哪些是还有问题的。所以这个时候一个比较常见的方法就是把它看到的最新的值写到它看到的有问题的节点中。这种方法在读比较多的时候很有效,其实可以想象,假如没有读,就没有 机会去比较和重写。 反熵 这个就是后台会有一个线程来不停地检查各个replica之间的差别,当发现有数据差别的时候,就会进行修复,这个和leader不同的是,这个修复不是顺序的,而且可能delay比较大。 Quorums读和写 我们在上面的例子中提到三个节点,有两个写成功,并且我们的读也是两个的话,就可以保证读到最新的写。其实这种读写我们称之为Quorums读和写。准确来讲,假如我们有n个节点,然后写的节点是w个,读的节点是r个,那么quorums读写就是保证w+r>n即可,因为这就意味着我们的读写节点必然有一个是交叉的。也就意味着肯定能读到最新的内容。 就如上图所示,n=5,w=3,r=3,这样哪怕有两个节点是有问题的,我们仍然可以看到replica3包含了最新的写的内容,同时它也被读操作读到了。 虽然上面的定义中是要求w+r>n,其实在现实中,我们很多时候的实现还是会选择>n/2,因为这就基本意味着两者的和肯定大于n了。 但是,是否w+r>n我们就一定什么问题也没有了呢?其实并不尽然,下面是一些常见的可能出问题的情况: 假如写和读同时发生,而这个写只写到了某一些节点,就很难说读到的是不是最新的值了。 假如写是部分成功的,比如说w=3,但是只有两个节点成功了,这个写是失败的,但是并没有去roll back成功的两个写,那么这时读的值很难确定是不是最新的了。 假如一个有新的值的节点突然出现问题了,然后我们从有旧的值得节点来进行replica,这个时候存有新的值的节点就被覆盖成旧的值了,这也就破坏了我们提到的quorum的要求了。 所以,尽管这种方法看起来不错,但是还是有可能会出现这样或那样的问题。 Sloppy Quorum和Hinted Handoff 我们在上文中提到的w+r>n 其实是一种严格的quorum要求,那么假如现实中我们在写的时候w设置的3,但是只有2个节点写成功了,是接受这个写的结果还是直接返回错误呢?你当然可以选择直接返回错误,但是其实还有一种实现就是在这种情况下,我们在n个节点之外再找一个节点去写一下,也保证写了w个节点,只是这里可能有不在n个节点中的节点出现,我们称这种情况为Sloppy Quorum。 当出问题的节点回来之后,任何写到第三节点的值我们需要再写回这个节点,这个过程我们称之为hinted handoff。...

1

多leader replication的实现及常见问题介绍

我们在前面的文章中介绍的都是单leader的实现。也就是说所有的写操作都会通过这个leader来实现。虽然说这是一种比较常见的实现方法,但是它也尤其局限性,比如说leader可能会有问题,比如网络问题等,这个时候就会有一段时间没法进行写操作。或者说当写操作很重的时候,所有的写的load都需要到leader这边,无形中就加重了leader的traffic。本文就来介绍一种多leader的实现方案。 顾名思义,多leader实现方案就是可以同时有多个节点成为leader,所有的写操作可以同时通过这些节点来进行。当其中一个leader在写的时候,另外的leader就和follower一样,也需要从它这边进行replication。 多leader的使用场景 多leader其实并不是一个比较常见的方案。那么一般在什么情况下,我们会考虑多leader的方案呢? 多数据中心的操作 假如我们的数据库是在多个数据中心的时候(实际上为了防止但数据中心出问题,一般的数据库都会分布在不同的数据中心),假如使用单leader的实现,那么leader就会在一个数据中心,从而使得所有的写都得通过那个数据中心。 而假如是多leader的实现,我们就可以在每一个数据中心放一个leader,这样在每一个数据中心中,还是单leader的情况,但是这个数据库则是多leader的情况。具体的架构如下图所示: 下面我们来看看这样的实现有什么好处: 性能 单leader的情况下,所有的写都需要到leader那边,显然跨数据中心的访问性能不会很好。而多leader的情况下,所有的读操作可以直接访问本地的数据中心,虽然需要在数据中心进行数据replication,但是数据中心之间的延迟其实对用户来说是黑盒,所以对用户来说性能是有提升的。 数据中心宕机的容忍性 单leader的情况下,如果有数据中心宕机,那么需要通过failover来找到新的leader,然后可以继续服务。多leader的情况下,单个数据中心的宕机不影响整体的写操作,无需做额外的failover也可以继续进行写操作。 网络问题的容忍性 同样的,但leader其实受leader所在数据中心的网络情况所影响,而相对来说多leader则可以更好的容忍单个数据中心网络的问题。 虽然看起来多leader的实现有很多好处,但其实它也有其问题,那就是冲突写,比如两个写同时发生在两个不同的leader上,并且彼此冲突,该如何进行处理,这个问题我们后面会详细介绍一些处理的方案。 Offline操作的应用 另外一个多leader replication常见的场景就是offline操作,比如你有一个应用哪怕没有网络也希望能够持续工作。 比如说你手机中的日历程序,你希望安排你的日程,比如添加事项,看看后面哪天有哪些安排。这些操作哪怕是在没有网络的时候也希望能够正常工作。只要当这个设备能够再次访问网络的时候我们能够成功同步这些就可以了。其实这就是一个多leader的场景,你可以把你的设备想象成一个数据中心,有网络的时候,就是正常的多leader同步。没有网络的时候,本地的leader也支持读、写操作。当再次有网络的时候能够做跨数据中心(设备)的replication。 协同写操作的应用 另外一个常见的使用场景就是会有多人同时写一个文档。比如说Google Doc,它支持同时有多个人来编辑。这种常见就和上面的比较类似,我们不希望一个人的写去影响另外一个人的写,所以这里通常就会写入本地leader,然后进行多节点的同步。 处理写冲突 我们上面提到多leader最大的问题就是写冲突,毕竟两个leader完全有可能同时修改同样的内容,如下图所示: 这里User1通过Leader1修改了title到B,但是User2又通过leader2修改了title到C,这个时候在他们进行replication的时候就会出现了冲突的问题,究竟是该改成B还是改成C呢? 避免冲突 假如我们现在能够想到一个简单的方法来避免冲突,那么这个问题就自然而然解决了。比如所有修改title的请求全部要到同一个leader来处理,这就可以规避掉上文提到的写冲突。这个方案还是蛮常见的,比如说用户的资料只能他自己能修改,而所有这个用户修改自己资料的请求我们全部指向同一个leader,这样就可以实现冲突的避免。 但是世事显然不会总是这么一帆风顺,比如说有时候某一个数据中心突然就出问题了,那么无可避免的,你就只能把所有的写操作都指向另外数据中心,这样就还是会出现写冲突。 收敛到一致状态 多leader其实很难说谁是最后写的,所以最终应该是什么样的内容有时很难讲,就像上面的例子一样,你说最终title应该是B还是C呢?这个时候就需要一些额外手段来辅助判断: 给每一个写一个独有的ID(比如使用timestamp,UUID等等),然后比较他们的大小。大得获胜。当这个ID使用的时间,那我们称这种方法为最后写的获胜(Last write wins LWW)。这个方法听起来不错,但也有其问题,我们在后面的文章中再具体讨论。...

0

Replication lag常见问题分析

我们在《分布式系统之leader-followers Replication深入介绍》中深入介绍了replication了基本实现,本文主要来聊一聊replication lag常见的一些问题。 我们知道在leader-follower这样的系统中,写操作只能到leader,而读操作则可以分布在多个follower上进行。这也就意味着在一个读比较多而写比较少的系统中,我们其实可以把多个读的load分散到follower上,从而达到一个read scaling的结构。这个想法很好,但是问题也很明显,就是事实上follower和leader之间其实并不是同步的,也就是说你从follower上读到的内容和leader上的内容有可能是不同的。当然,我们说这种不同可能只是暂时的,比如说你不再往leader上写,一段时间之后,各个follower中的数据也就一样了。这种现象我们通常称之为最终一致(eventual consistency)。而这个delay的时间我们称之为replication lag。显然我们希望replication lag越小越好。 读你自己的写 (Read your own Writes) 在实际产品中一个比较常见的使用场景就是读你自己写的内容。比如说我们在某一个讨论下面发了一条评论,那么我们肯定希望自己能立即看到这条评论,而通常来说写是通过leader去写,而读则是通过follower来读的(当然现实中这种场景也不一定会去读,比如在前端就直接先把这条评论加进去,但是假如你刷新了,那可能还是需要去follower读),所以这里一个要求就是我能读到我写的内容。 我们来看下面这个图,假如用户在他写了之后立即来读,就会有可能读不到这个刚写的数据,看起来就像这个数据丢失了。 这时候我们就需要一个“写后读一致”(read-after-write consistency)的保证。也就是说用户重新加载页面,能够看到他写的内容,这个保证对别的用户没有影响,就是说别的用户重新加载可能看到的还是旧的内容。那么怎么实现这个效果呢,也很多方法,下面我们来列几个常见的: 当读一些用户可能会修改的内容,总是从leader来读。其他的内容还是从follower来读。这就是从business层面来定义哪些从leader读,哪些从follower读。比如说你微信自己的朋友圈,就总是从leader读,假如是别的朋友圈就从follower来读,因为你的朋友圈信息只有你才能修改。 但是假如你的使用场景就是很多东西都可以自己修改,假如按照1的方式来设计的话,你就会发现很多东西都需要从leader来读,这样就不能分散读的压力了,这个时候我们可能可以使用一些别的方法,比如看follower和leader之间的lag,假如lag大于一定的阈值就从leader读,否则就还从follower来读等等。 客户端可以记一个最近的更新时间,假如repica的更新时间是在这个时间之后的,就可以从follower读,否则就还是从leader来读。但是这种方法也有问题,比如你从多个设备登录了微信,从其中一个设备做了修改,那另外一个设备可能就看不到这个修改了。所以我们需要考虑一下更多的情况。 当然实际应用中情况可能比这种还要复杂,比如你可能需要考虑服务器在数据中心的分布,比如你被route到了数据中心A,而leader则在数据中心B,你又决定要从leader中取数据,该如何来实现,这些都是需要考虑的问题。 单调读(Monotonic reads) 另外一个常见的读的问题,就是有时我们会发现我们会读到以前的值。这是怎么回事呢?我们来看下图,这里有一个更新,就是插入了一个comments,在第一次读的时候,用户访问的是follower1,读的时候这个comments的插入在follower1上已经完成了,所以就读到了这条数据。但是当第二次读的时候,用户访问了follower2,而这个时候其实follwer2的这个插入的更新并没有完成,这个时候读的就是一个以前的值。这就造成了我们之前看到的读到以前值的情况。 而单调读就是保证上诉这种情况不会发生。它所保证的就是假如一个用户按顺序读,他读到的值不会变成之前的值。一个常见的来实现这个功能的方法,就是一个用户就一直从某一个follower上读,比如根据用户的user ID来决定他访问的follower。但是假如这个follower出问题了,他不得不redirect到别的follower,还是有可能会遇到类似的问题。 一致前缀读取(Consistent prefix reads) 我们来看这样一个场景: 现在我们假设有第三个人从一个follower上听这个对话,而Poons的replication lag比较大,Cake的replication lag比较小,这个第三个听到的对话可能变成了下面这样: 它具体的时间线可以见下图:...

3

分布式系统之leader-followers Replication深入介绍

我们在前面有简单讲过Replication的作用,简单说就是为在多个机器上保存同样的拷贝来服务的。有了这个拷贝之后我们就可以做很多事情,比如说它可以成为一个读的源从而分散读的压力,它可以在原来数据机器出问题(或者deploy)等的时候作为一个backup等等。 这个想法其实很简单,但真正在我们做这个拷贝的时候,会遇到很多问题,比如说我们是使用同步还是使用异步来进行同步多个拷贝,如何保证多个拷贝之间的一致性等等。那么本文就来从各个方面详细介绍这些内容。 Leaders和Followers 我们把每一个保存数据的节点称之为replica,当我们有多个节点的时候,最明显的一个问题就是怎么去保证每个节点的内容都是一样的呢?其中最常见的方法就是基于leader的模式(也成为master-slave模式或者active/passive模式)。总得来说,它的工作方法如下: 一个节点是leader。所有的写操作都必须经过leader。 其他的节点我们成为follower,每次leader写数据的时候,也把相关的内容发送到每一个follower(replication log),然后每个follower根据这些log来更新本地的数据。 当有读的操作的时候,既可以从leader读也可以从follower读。 同步VS.异步Replication 上面这种方法其实在很多关系型数据库中很常见。这里遇到的一个最大的问题就是使用同步还是异步来进行replication。 就比如上面的这个case,它实现的功能很简单。就是把user id 1234这个用户的picture更新一下,它首先发送了update的请求到了leader的replica上。在这之后,leader会把这个更新的请求分别发送给两个follower的replica,从而最终达到所有的replica上这个用户的picture都更新了的效果。 我们就以这个例子来分析一下同步和异步在这两个上面的差别。如下图所示,我们看到leader的返回是在Follower1 更新完成之后,也就是说follower1是一个同步的更新。而leader并没有等待follower2完成更新再返回,这也就意味着follower2的更新是一个异步的。 从这个图中可以看到follower1和follower2的更新其实都是由一个延时的,尽管大多数时候这个延时都很小,但是当我们遇到网络问题或者别的情况的时候(CPU占用率很高,内存不够等等),这个延时有可能会很大,谁也不能保证什么时候能被更新。 所以,同步更新的好处就是follower其实和leader是同步的,当leader有问题的时候我们甚至可以直接切换到同步更新的follower,当然它的问题也很明显,就是每一个更新(写操作)都需要等待这个follower的更新完成才行,这有可能会导致整个request延迟很久,甚至超时。所以,假如你想做同步的更新,一般来说也不会想让所有的节点都同步,而是选择leader和一个节点是同步的,这样就可以在leader出问题的切换和同步的效率之间达到一个很好的trade off。 当然,事实情况下基于leader的replication基本都是完全使用异步。这样的问题就是leader出问题,那些没有sync到别的node的数据就会丢失。好处就是leader完全不收别的节点的影响,哪怕别的节点都出问题也可以正常独立运行(通常这个时候就会出alert,然后oncall就到了表现的时候了,哈哈)。生产环境中这样的选择其实有很多原因,比如说为了保证随时都有节点是健康的,这些节点通常会分布在不同的地区(数据中心),所以他们之间的通信通常不是那么可靠,如果使用同步就会很容易出现问题等等。 Follower的建立 有时我们需要从无到有建立一个新的follower,这种情况在生产环境中特别常见,比如说机器的磁盘坏了,原有follower的数据就都不能用了,这个时候就需要从头开始建立,或者说某个时刻你没有足够的follower了(比如说数据中心出问题了,或者机器出问题了),你需要在一个新的机器上建立一个 follower,那么如何从头开始来建立一个节点呢? 首先想到的就是从leader上拷贝过来就好了,但是我们知道leader其实是在不停改变的,也就是说随时都在不停地被写入,而数据的拷贝速度不会很快(主要瓶颈在HDD的写入速度上,目前基本在200MB/s左右),所以在这个过程中不允许写可能也不是一个很好的方法。那么一般来说是怎么做的呢?大概会有以下的步骤: 得到一个数据库某一个节点的snapshot(这个snapshot不影响写)。大多数数据库都支持这样的功能。 拷贝这个snapshot到新的follower Follower联系leader去得到所有的在这个snapshot之后的操作(log sequence)。 然后follower根据得到的信息来apply snapshot之后 的操作,我们称这个过程为catch up。 处理节点的中断 我们上文中也提到了任何节点在任何时候都有可能出问题。那么要是真的出问题了,我们一般会怎么处理呢? 假如这个出问题的节点是follower,假如这个问题只是service...

0

分布式系统简介(总论)

我们在前面几篇文章中简单介绍了单个服务器对数据的处理,而在现实中数据的存储和获取会涉及到多个机器,也就是说我们会把数据分布在多台机器上,这样做有很多好处: 可扩展性(Scalability) 随着你的数据增加,一个机器可能很难处理日益增长的读写需求,你可以把这些负载分散到多个机上。 容错性/高可靠性(Fault Tolerance/ high availability) 在现实环境中,任何一个机器都有可能出现故障,可能是磁盘故障,网络故障等等,假如你希望某一个或几个机器出现问题,你的产品仍然能够继续工作,那么就需要分布式系统。 延迟(Latency) 假如你的用户遍布全球,那么你肯定希望让你的服务器物理上更加靠近对应的用户,这样才能减少相应的延迟。总得来说,就像我们之前介绍的,当需求增加的时候,你就需要进行扩展,要不是垂直扩展,增加机器的处理能力,要不就是水平扩展,使用更多的机器来处理。前者有尽头,后者则无涯。具体可以参见我之前介绍的《负载均衡》。 Replication和Partitioning 我们在之后将重点来介绍如何水平扩展,通常来说有两者方法来实现水平扩展: Replication 这种方法就是在多个节点(机器)上存放同样的数据,并把它们分布到不到的地方(防止自然灾害等),当一个或几个节点出现问题的时候,保证仍然能有一个节点可以工作。同样的这样的处理也能提高性能。 Partitioning 所谓的partitioning就是把一个大的数据分块存在不同的节点上。 它们两相互是独立的,不过通常我们会同时使用它们,具体的如下图所示: 我们将在后面的文章中来具体详细地介绍如何做replica,如何做partition,以及如何处理数据读写过程中发生的常见问题等。