分布式一致性协议

一致性协议2010.05.19主要内容持续一致性基于主备份的协议复制的写协议高速缓存相关性协议实现以客户为中心的一致性0.预备知识7.4.3.1状态和操作P219复制管理中实际传播的三个可能信息：1).只传播更新的通知(无效化协议，几乎不占用带宽）适用于更新和写操作相对较多，即R/W相对很小的情况。2).把数据从一个副本传送到另外的一个副本R/W较高的情况3).把更新操作传播到其他的副本(主动复制)每个进程主动地联系最新的数据7.4.3.2拉协议与推协议P220更新的方式：1.基于推式的方法(基于服务器的协议)不需要其他的副本请求更新，这些更新就被传播到那些副本那里应用于多个副本需要维持相对较高程度的一致性。主要是读操作，R/W较高。2.基于拉式的方法(基于客户的协议)通常被应用于客户高速缓存。客户轮询服务器以查看是否需要更新。R/W较低3.基于租用的更新传播(推的数据超期无效之后，采用拉式)1.持续的一致性对复制数据问题没有最好的解决办法。复制数据会导致一致性问题，这用一般方法不能有效地解决。除非放宽对一致性的限制才有希望获得有效的解决办法。(Yu和Vahdat2002)给出了一种通用的办法，为定义不一致性区分了三个相互独立的坐标轴：副本之间的数值偏差、副本之间新旧程度的偏差以及更新操作顺序的偏差。他们称这些偏差形成了持续一致性的范围。1.1限定复制的数值偏差数据具有数值语义的应用程序可以用数值偏差来度量不一致性。如股票市场价格记录的复制。如何把数值偏差限定在一定的范围之内？单个数据项x的写数据操作W(x):对数据项x的写操作weight(W(x))：用于更新x的数值，假定weight(W)0)()(iiLSWorigin开始时，写操作被提交给N个可用副本中的一个，即写操作的源。然后将已提交的写操作传播给所有的服务器。最后，每个服务器保存一个写操作日志，记录服务器在本地副本x上执行的写操作。}&)(|)({],[iWjLWSWoriginWweightjiTWTW[i,j]表示的是源自Sj提交给Si的中的总的写操作WiLWjSSweightjiTWi)(],[如何把数值偏差限定在一定的范围之内？Goal:对任意时间t，使得服务器Si的当前值vi在数据项x的实际值v(t)的一定范围内发生偏差。(该实际值完全由所已提交的写操作来确定。))(],[)0(],[)0()(11tvvkiTWvvkkTWvtviNkiNk对每个服务器Si，指定一个上限，这样就需要确保：iiivtv)(12Nit[1,1][2,2][i,i][N,N]∑:Vi[1,1][i,i][2,2][N,N]V(t)(提交，本地执行）(传播给Si)注：wight(W)0,表明每次更新的值都是增加的。传播给其他的服务器(感染协议)0],[],[],[jiTWjiTWjjTWSSSkkij在任何情况下，服务器Si把来自Sj的一个写操作传播给Sk时，Sk可以知道写操作发送时的值TW[i,j]。换句话说，Sk可以维护一个视图TWk[i,j],它相信Si会有一个TW[i,j]。jikTW[j,j]TW[i,j]TWk[i,j]TW[k,j]ikkkSLjkWsendjkTWjiTWiftjiTWtjiTW)],[(]),[],[()](,[)](,[//01t0t1当服务器Sk知道Si与提交给Sk的更新操作步调不一致时，它就把写操作从其日志中转发给Si。该转发操作可以有效地把Sk的视图TWk[i,k]往TW[i,k]靠近，使其偏差更小。尤其当应用程序提交一个新的写操作时，Sk会把其视图往TW[i,k]推进，这使得？)1/(],[],[NkiTWkiTWik],[],[kiTWkiTWk1.2限定复制的新旧程度偏差让服务器Sk保持一个实时的向量时钟RVCk，其中表示：到时间T(i)时，Sk看到了已提交给Si的所有写操作。假定：每个已提交的W由其origin(W)添加时间戳，T(i)表示的是Si的本地时间。)(][iTiRVCk如果副本服务器之间的时钟是松散同步化的，那么一个可接受的限定新旧程度的协议是这样的：只要服务器Sk通知将超出指定的界限，那么它就开始拉入来自Si的时间戳晚于RVCk[i]的写操作。][][iRVCkTk1.3限定顺序偏差顺序偏差产生的原因：副本服务器会暂时地应用已提交给它的更新因此，每个服务器都有一个暂时写操作的本地队列，这些写操作应用到x的本地副本中的顺序还需确定。通过指定暂时写操作队列的最大长度，就可以限定顺序偏差。当本地队列的长度超过指定的最大长度时，服务器不再接受任何新提交的操作，而是按照应执行的写操作的顺序，通过与其他服务器协商，尝试提交暂时写操作。换句话说，就是需要执行一个暂时写操作的全局一致性的顺序。2.基于主备份的协议在顺序一致性中，基于主备份的协议比较盛行。在这些协议中，数据存储中的每个数据项有一个相关的主备份，该备份负责协调在x上的写操作。根据1).主备份时候固定在一个远程的服务器上2).主备份移到启动写操作的进程那里之后写操作时候可以在本地执行来区分各种基于主备份的协议。2.1远程写协议(最简单的协议)：把所有的读写操作都转发给固定的远程服务器。工作原理：Goal：在数据项x上执行一个写操作Steps：1.把W(x)转发给x的主服务器2.在x的主服务器上执行本地更新3.把x上的更新操作转发给备份服务器4.每个备份服务器执行更新操作5.备份服务器往主服务器返回一个完成的确认消息6.主服务器回送一个确认信息给初始进程备份服务器数据项x的主服务器客户客户数据存储W1W5W4W3W4W3W2W3W4R1R2W1:写请求W2:把写请求转发给主服务器W3:通知备份服务器更新W4:确定更新W5:确定写操作已完成R1:读请求R2:读请求响应运行初始进程【潜在的性能问题】启动更新的进程在被允许继续执行之前，可能需要等待很长的时间。【分析】阻塞操作。【改进】采用非阻塞的方法。只要主服务器已经更新了其x的本地副本，它就给初始进程返回确定消息。然后，它再通知备份服务器也执行这个更新。【新的问题】容错能力。客户端进程无法确定其他的备份服务器执行了更新操作。2.2本地的写协议基于主备份的本地写协议有两种：1).每个数据项x都只有一个单一的拷贝。也就是说不存在副本.备份服务器数据项x的旧主服务器客户数据存储3214数据项x的新主服务器1.读请求或写请求；2.向x的当前服务器发转发请求；3.将数据项x移动到客户的服务器上；4.返回在客户的服务器上执行的操作的结果。【问题】需要跟踪每个数据项的当前位置2).主备份要在多个要执行写操作的进程之间迁移每当一个进程要更新数据项x时，它先定位x的主备份，然后将该备份移动到自己的位置。【优点】多个相继的写操作可以在本地执行，而执行读操作的进程仍然可以访问它的本地备份。但是如上所述，只有使用非阻塞协议，即在主备份接收到更新后，通过该协议将更新传播到其他副本时，才可能实现这个优点。这个协议已经被应用于各种分布式共享存储器系统。备份服务器数据项x的旧主服务器客户客户数据存储R1R2W5W4W2W5W4W1W3W1:写请求W2:把数据项x移到新主服务器上W3:确定操作已经完成W4:通知备份服务器更新W5:确定更新R1:读请求R2:读请求响应W5W4数据项x的新主服务器【注】两本书都存在错误。3.复制的写协议写操作基于主备份的协议只在一个副本上执行复制的写协议在多个副本上执行区别主动复制主动复制中的操作被转发到所有副本基于多数表决的一致性协议3.1主动复制在主动复制中，每个副本都有一个相关联的进程，该进程执行更新操作。与其他的协议相比，更新通常是通过引起更新的写操作来传播的。也就是说，该操作被发送到每个副本。【问题1】操作需要在各地以相同的顺序来执行。因而需要一个全序的多播机制。【解决办法1】Lamport时间戳。但是用于大型分布式系统时的扩展性不好。【解决办法2】使用中心协调器(定序器sequencer)来实现全序。将所有的操作转发到定序器，由定序器为每个操作分配一个唯一的序列号。(可扩展性问题依然存在)【解决办法3】结合1和2。(Rodrigues1996)【问题2】被复制的调用AB3B2B1C复制的对象客户复制调用请求对象三次收到相同的调用3.2基于多数表决的协议【基本思想】要求客户在读或写一个复制的数据项之前向多个服务器提出请求，并获得它们的许可。e.g.1).半数以上的人同意修改，则修改。文件获得一个最新的版本号。2).半数以上的人的文件版本号一致，那么该文件为最新版本。（因为剩下的人不可能发起步骤1）Gifford方案Goal_1：读取一个具有N个副本的文件Need：读团体(NR个以上服务器的任何集合)Goal_2：修改这个文件Need：写团体(至少NW个服务器的集合)限制条件：(1).防止读写操作冲突(2).防止读读操作冲突2/).2().1(NNNNNWWR2/).2().1(NNNNNWWR(1)式说明NR和NW两个集合必须有交集。也就是说，在读团体里面有写团体的成员。客户在查看版本号时，会知道哪个服务器是最新的，并选择那个服务器。NwN-Nw成员的版本号是一致的读团体NR，必须是包含所有可能版本的集合，那么客户才能选择最新的版本和服务器。1)(WRNNNABCDEFGHIJKLNR=3，NW=10ABCDEFGHIJKLNR=7，NW=6ABCDEFGHIJKLNR=1，NW=12N=12，NW6可能导致写写操作冲突“读一个，写全部”(ROWA)代价：写操作需要获取所有的副本4.高速缓存相关性协议高速缓存是一类特殊的复制，通常由客户而不是服务器来控制。高速缓存相关性协议保证高速缓存与服务器启动的副本一致，在原理上，高速缓存相关性与迄今为止我们讨论过的各种一致性协议没有多大的差别。高速缓存相关性方面的两个问题：1).相关性检测策略2).相关性实施策略4.1相关性检测策略【静态方法】假定编译器在运行之前执行必要的分析，并确定哪些数据可能因为它们被缓存而导致不一致性。编译器仅插入一些避免不一致性的指令。【动态方法】不一致性在运行时检测。例如检查服务器，查看被缓存的数据自从被缓存后是否被改变。在分布式数据库中，根据事务处理器件进行检测的确切时间，将动态的基于检测的协议(Franklin1997)分为三类。1.事务处理期间访问高速缓存的数据项时，检验是否与服务器中的一致。完成一致性检测之前，不能使用缓存的数据项。（先检测后用）2.进行一致性检测时，继续执行事物处理。若检测出不一致性，事务处理异常中止。（边检测便用，结果出来了再考虑）3.只在事务处理委托检测时才检测数据项是否为最新。（乐观的）第2种方法是最有效的，因为节约了方法1的等待时间，并且大部分情况下，数据是最新的。4.2相关性实施策略该策略决定了高速缓存如何与服务器存储的各副本保持一致。最简单的办法就是不允许缓存共享数据，把共享数据仅保存在服务器上，客户只允许缓存私有数据。当共享数据被缓存时，实现高速缓存的一致性可采用两种办法：1).每当一个数据项被修改后，服务器向所有的高速缓存发送无效化信息。2).仅传播更新。进程修改了被缓存的数据可能发生的情况：1).高速缓存——只读。更新只能发生在服务器上，然后由服务器把更新操作传播到缓存中。用户检测到高速缓存过时了，就向服务器请求更新。2).允许用户直接修改被缓存的数据项，并将更新转发到服务器。直写式高速缓存：类似于基于主备份的本地写协议，客户的高速缓存成了一个临时的主备份。回写式高速缓存：？5.实现以客户为中心的一致性上述问题是由用户对不同的副本进行操作的事实引起的，引入以客户为中心的一致性可以缓解这个问题。本质上，以客户为中心的一致性为单一的客户提供一致性保证，保证该客户对数据存储访问的一致性它并不为不同客户的并发访问提供任何一致性的保证。四种类型：——单调读、单调写、写后读