分布式系統(tǒng)課件：chapter7

ConsistencyandReplicationChapter77.1.1ReasonsforReplication:1)reliability2)performanceCaveatGaininperformanceCostofincreasedbandwidthformaintainingreplicationIntroduction(7.1)Dataaregenerallyreplicatedtoenhancereliabilityorimproveperformanceindistributedsystemorparallelcomputerssystem.Howtokeepreplicasconsistentisoneofthemajorproblems(whenonecopyisupdated,weneedtoensurethattheothercopiesareupdatedaswell)7.1.2ObjectReplication1)Adistributedremoteobjectissharedbymultipleclients-------howtoprotecttheobjectagainstsimultaneousaccessbymultipleclients.2)Adistributedremoteobjectisreplicatedatdifferentnode-------howtoensurethatconcurrentinvocationsareperformedinthecorrectorderateachofthereplicas.Introduction(7.1)ObjectReplication(1)Organizationofadistributedremoteobjectsharedbytwodifferentclients.ObjectReplication(2)Aremoteobjectcapableofhandlingconcurrentinvocationsonitsown.AremoteobjectforwhichanobjectadapterisrequiredtohandleconcurrentinvocationsObjectReplication(2)Fig(a):Forexample,javaobject----whichcanbeconstructedasamonitorbydeclaringtheobject’smethodtobesynchronized.publicsynchronizedvoidenter(Objectitem){ while(count==BUFFER_SIZE) Thread.yield(); ++count; buffer[in]=item; in=(in+1)%BUFFER_SIZE;}ObjectReplication(2)ObjectReplication(3)Adistributedsystemforreplication-awaredistributedobjects.（SOS，Globeetc.）Adistributedsystemresponsibleforreplicamanagement(CORBAetc.)ObjectReplication(3)7.1.3ReplicationasScalingTechniquePlacingcopiesofdataandobjectsclosetotheprocessesusingthemcanimproveperformancethroughreductionofaccesstime,andthussolvescalabilityproblems.Replicationandcachingforperformancearewidelyappliedasscalingtechniques.dilemmaproblem:Ontheonehand,scalabilityproblemcanbealleviatedbyapplyingreplicationandcaching,leadingtoimprovedperformance.Ontheotherhand,tokeepallcopiesconsistentgenerallyrequiresglobalsynchronization,whichisinherentlycostlyintermsofperformance.ObjectReplication(3)1.DATA-CENTRICCONSISTENCYMODELS.2.CLIENT-CENTRICCONSISTENCYMODELS兩種一致性模型DATA-CENTRICCONSISTENCYMODELS(7.2)Adatastoremaybephysicallydistributedacrossmultiplemachines-----(distributed)sharedmemory,(distributed)shareddatabase,ora(distributed)filesystem.Adataoperationisclassifiedas:writeoperationreadoperation.Inparticular,eachprocessthatcanaccessdatafromthestoreisassumedtohavealocal(ornearby)copyavailableoftheentirestore.Writeoperationsarepropagatedtotheothercopies.Data-CentricConsistencyModelsThegeneralorganizationofalogicaldatastore,physicallydistributedandreplicatedacrossmultipleprocesses.Data-CentricConsistencyModelsAconsistencymodelisessentiallyacontractbetweenprocess(read/write)andthedatastore.Itsaysthatifprocessesagreetoobeycertainrules,thestorepromisestoworkcorrectly.Data-CentricConsistencyModelsIntheabsenceofaglobalclock,itisdifficulttodefinepreciselywhichwriteoperationisthelastone,soweneedtoprovidedefinitions,leadingtoarangeofconsistencymodels.Eachmodeleffectivelyrestricts（限定）thevaluesthatareadoperationonadataitemcanreturn.StrictConsistency(7.2.1)strictconsistency:

Anyreadonadataitemxreturnsavaluecorrespondingtotheresultofthemostrecentwriteonx.例：單一處理機(jī)遵守嚴(yán)格一致性，有如下程序：A=1；A=2；PRINT（A）；打印1或2以外的任何值是編程者無法理解的。StrictConsistency(7.2.1)假設(shè)在DCS中，有如下情形(t1<t2)：NodeANode

BP1x

…

read(B:xatt1)P2

…1nsWrite(B:xatt2)若按嚴(yán)格一致性，A都應(yīng)該讀出原來的值。然而，若T2-T1=1ns(1納秒=0.000000001秒)，而機(jī)器距離3米，從A到B傳送讀操作并使之先于寫操作，信號則必須以十倍光速的速度傳遞，與愛因斯坦相對論矛盾。StrictConsistency(7.2.1)Behavioroftwoprocesses,operatingonthesamedataitem.(a)Astrictlyconsistentstore.(b)Astorethatisnotstrictlyconsistent.StrictConsistency(7.2.1)嚴(yán)格一致性的存儲器，寫操作在任一時(shí)刻對所有進(jìn)程都是可見的，系統(tǒng)維護(hù)一個(gè)絕對全局時(shí)間。一旦存儲器中的值改變，不管讀寫之間的事件間隔多小，不管哪個(gè)進(jìn)程執(zhí)行讀操作，也不管進(jìn)程在何處，以后讀出的都是新更改的值。同樣，不管后面的寫操作有多迅速，執(zhí)行讀操作仍應(yīng)讀出原來的值。嚴(yán)格一致性是理想的編程模式，在分布式系統(tǒng)中，這幾乎不可能實(shí)現(xiàn)。StrictConsistency(7.2.1)wewillrelaxthismodelbyconsideringtimeintervalsinsteadofabsolutetime,anddefinepreciselywhatisacceptablebehaviorforconflictingoperationsinadistributedsystem.LinearizabilityandSequentialConsistency(7.2.2)Sequentialconsistent(順序一致)是比嚴(yán)格一致稍弱的模式，Lamport（1979）首先定義了順序一致性應(yīng)符合的條件：Theresultofanyexecutionisthesameasifthe(readandwrite)operationbyallprocessesonthedatastorewereexecutedinsomesequentialorderandtheoperationsofeachindividualprocessappearinthissequenceintheorderspecifiedbyitsprogram.

任何操作的執(zhí)行結(jié)果都應(yīng)該與所有的進(jìn)程以程序規(guī)定的順序，好象在各自單個(gè)進(jìn)程執(zhí)行的順序一致。表明:對于在不同機(jī)器上并發(fā)運(yùn)行的進(jìn)程，任何有效的交錯(cuò)都是可以接受的行為，但所有進(jìn)程必須遵守同一訪問順序。LinearizabilityandSequentialConsistency(7.2.2)Asequentiallyconsistentdatastore.Adatastorethatisnotsequentiallyconsistent.順序一致存儲器不保證讀返回的值是1ns、1ms甚至1分鐘以前另一進(jìn)程寫入的。它只保證所有進(jìn)程以相同的順序看見存儲器訪問。如圖a)，或許會得到圖b)的結(jié)果。如果缺少明確的同步操作，則結(jié)果是不確定的。LinearizabilityandSequentialConsistency(2)Threeconcurrentlyexecutingprocesses.ProcessP1ProcessP2ProcessP3x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);LinearizabilityandSequentialConsistency(2)6個(gè)獨(dú)立的語句，有720(6！)種可能的執(zhí)行順序。從x=1開始考慮的順序有120(5！)種,其中只有1/4（y=1/z=1在print()前,各1/2）即30個(gè)是有效的。另外30個(gè)有效順序是以y=1開頭的，還有30個(gè)以z=1開頭。共有90個(gè)有效執(zhí)行順序。LinearizabilityandSequentialConsistency(3)Fourvalidexecutionsequencesfortheprocessesofthepreviousslide.Theverticalaxisistime.x=1;print((y,z);y=1;print(x,z);z=1;print(x,y);Prints:001011Signature:

001011(a)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:101011Signature:

101011(b)y=1;z=1;print(x,y);print(x,z);x=1;print(y,z);Prints:010111Signature:010111(c)y=1;x=1;z=1;print(x,z);print(y,z);print(x,y);Prints:111111Signature:111111(d)LinearizabilityandSequentialConsistency(3)Linearizabilityconsistency(weakerthanstrictconsistency,strongerthansequentialconsistency):Theresultofanyexecutionisthesameasifthe(readandwrite)operationbyallprocessesonthedatastorewereexecutedinsomesequentialorderandtheoperationsofeachindividualprocessappearinthissequenceintheorderspecifiedbyitsprogram.Inaddition,iftsOP1(x)<tsOP2(y),thenoperationOP1(xshouldprecedeOP2(y)inthissequence.(與順序一致性同，但是應(yīng)滿足時(shí)間戳的順序)(LettsOP1(x)denotethetimestampassignedtooperationOPthatisperformedondataitemx)LinearizabilityandSequentialConsistency(3)Acommonapproachtoformallyexpresssequentialconsistencyisasfollows(Ahamadetal.,1992;Mizunoetal.,1995).EachprocessPihasanassociatedexecutionEi,whichisasequenceofreadandwriteoperationsbyprocessPiperformedonadatastoreS.ThissequenceadherestotheprogramorderassociatedwithPi.Forexample.

E1:W1(x)a;E2:W2(x)b;E3:R3(x)b,R3(x)a;E4:R4(x)b,R4(x)a;ThenH=W1(x)b,R3(x)b,R4(x)b,W2(x)a,R3(x)a,R4(x)aCasualConsistency(7.2.3)Necessarycondition:Writesthatarepotentiallycasuallyrelatedmustbeseenbyallprocessesinthesameorder.Concurrentwritesmaybeseeninadifferentorderondifferentmachines.有因果關(guān)系的寫操作，相關(guān)進(jìn)程看到是一致的。CasualConsistency(2)Thissequenceisallowedwithacasually-consistentstore,butnotwithsequentiallyorstrictlyconsistentstore.(W2(x)bandW1(x)careconcurrent).有因果關(guān)系寫無因果關(guān)系寫CasualConsistency(3)Aviolationofacasually-consistentstore（不滿足）.Acorrectsequenceofeventsinacasually-consistentstore.Implement:requiringkeepingtrackofwhichprocesseshaveseenwhichwrites(實(shí)現(xiàn)因果一致性需要由記錄來跟蹤哪個(gè)進(jìn)程看到哪個(gè)寫操作。這要建立和維護(hù)一個(gè)依賴圖：即一個(gè)操作依賴于其它什么操作)。FIFOConsistency(orPRAM)(7.2.4)NecessaryCondition:

Writesdonebyasingleprocessareseenbyallotherprocessesintheorderinwhichtheywereissued,butwritesfromdifferentprocessesmaybeseeninadifferentorderbydifferentprocesses(一個(gè)進(jìn)程的寫操作可以被其它進(jìn)程以指定的順序接收到，但不同進(jìn)程的寫操作在不同進(jìn)程看來次序可以是不同的).

PRAM一致性由LIPTON和SANDBERG（1988）提出，PRAM代表管道RAM，由于一個(gè)進(jìn)程的寫操作可以是流水線的，即進(jìn)程不必在開始下一個(gè)操作之前等待一操作結(jié)束。只要求一個(gè)進(jìn)程以一定順序的寫操作被所有進(jìn)程看到。FIFOConsistencyAvalidsequenceofeventsofFIFOconsistency它不保證不同進(jìn)程看到的寫操作順序是一致的，除非是一個(gè)源的一個(gè)或多個(gè)寫操作，才必須按次序到達(dá)，就好象在管道中。由不同進(jìn)程產(chǎn)生的寫操作是并發(fā)的。

themodelcanbeimplementedbysimplytaggingeachwriteoperationwitha(process,sequencenumber)pair,andperformingwritesperprocessintheorderoftheirsequencenumber.指定順序FIFOConsistencyStatementexecutionasseenbythethreeprocessesfromthepreviousslide.Thestatementsinboldaretheonesthatgeneratetheoutputshown.(結(jié)果只受本進(jìn)程順序影響)x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);Prints:00(a)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:10(b)y=1;print(x,z);z=1;print(x,y);x=1;print(y,z);Prints:01(c)FIFOConsistency在FIFO一致下,不同進(jìn)程所看到的語句執(zhí)行順序不同,如圖(a)顯示P1怎樣看到事件，而(b)顯示P2所看到的，(C)則是P3所見。對于順序一致存儲器,三個(gè)不同顯示是不允許的。如果使三個(gè)進(jìn)程的輸出順序相接,得到結(jié)果為001001，這在順序一致性下是不可能的。兩者的關(guān)鍵不同在于：前者盡管未確定語句（和存儲器訪問）的執(zhí)行順序,但至少所有進(jìn)程都遵守共同的順序。后者就不遵守。不同進(jìn)程看到的操作順序不同。FIFOConsistencyTwoconcurrentprocesses.GOODMAN（1989）提出了一種略微不同但仍支持PRAM一致的存儲器形式。如上述例子中，在順序一致下只能出現(xiàn)三種結(jié)果之一:1）P1被KILL;2）P2被KILL;3）兩者都不被KILL。但是，在FIFO一致下,可能兩個(gè)進(jìn)程都被KILL，即若P1在看到P2中B賦值之前讀取B,P2在看到P1中A賦值之前讀取A。ProcessP1ProcessP2x=1;if(y==0)kill(P2);y=1;if(x==0)kill(P1);WeakConsistency(7.2.5)盡管FIFO一致性比強(qiáng)模式的更好,但它仍對很多應(yīng)用程序做了不必要的限制，即要求一個(gè)進(jìn)程以一定順序的寫操作被所有進(jìn)程看到，并非所有應(yīng)用程序要看到所有寫操作。比如在臨界區(qū)中一個(gè)進(jìn)程循環(huán)讀寫被復(fù)制數(shù)據(jù)。只需讓進(jìn)程完成臨界區(qū)操作以后,將最后結(jié)果發(fā)送到各處,而不用太關(guān)心甚至不用關(guān)心中間結(jié)果是否也順序發(fā)送到所有結(jié)點(diǎn)。WeakConsistency(7.2.5)Properties(Duboisetal.1986):AccessestosynchronizationvariablesassociatedwithadatastorearesequentiallyconsistentNooperationonasynchronizationvariableisallowedtobeperformeduntilallpreviouswriteshavebeencompletedeverywhereNoreadorwriteoperationondataitemsareallowedtobeperformeduntilallpreviousoperationstosynchronizationvariableshavebeenperformed.WeakConsistency(7.2.5)1．對同步變量的訪問是順序一致的(所有進(jìn)程以相同順序看到對同步變量的訪問)；2．在所有先前的寫操作完成之前,不能訪問同步變量(同步訪問開始前。在更新共享數(shù)據(jù)后做同步操作，進(jìn)程可將新值傳遍所有存儲器)；3．在先前所有同步變量的訪問完成前，不能訪問（讀或?qū)懀?shù)據(jù)(訪問一般非同步變量，不管是讀是寫，只有在所有前序的同步操作結(jié)束后方可進(jìn)行。在讀共享數(shù)據(jù)前做同步操作，可以保證進(jìn)程讀到最新值)；它是對一組操作的一致性約束,而不是單獨(dú)的讀或?qū)?。?dāng)基本上以簇的形式（短時(shí)間內(nèi)有很多訪問，每一訪問時(shí)間都不長）訪問共享變量時(shí)，這個(gè)模型很有用。WeakConsistencyAprogramfragmentinwhichsomevariablesmaybekeptinregisters.若允許另外一個(gè)進(jìn)程可隨意讀取存儲器的話，只需讓編譯器寫一標(biāo)志位說明存儲器沒有更新。若另一進(jìn)程訪問A，它會在標(biāo)志位上等待。該思想已經(jīng)得到許多應(yīng)用，例如：一個(gè)優(yōu)化的編譯器可以在寄存器中計(jì)算a和b，并保存片刻，不更新存儲器，只有當(dāng)調(diào)用函數(shù)f后才將a和b當(dāng)前值返還存儲器。inta,b,c,d,e,x,y; /*variables*/

int*p,*q; /*pointers*/

intf(int*p,int*q); /*functionprototype*/a=x*x; /*astoredinregister*/

b=y*y; /*baswell*/

c=a*a*a+b*b+a*b; /*usedlater*/

d=a*a*c; /*usedlater*/

p=&a; /*pgetsaddressofa*/

q=&b /*qgetsaddressofb*/

e=f(p,q) /*functioncall*/WeakConsistencyAvalidsequenceofeventsforweakconsistency.Aninvalidsequenceforweakconsistency.ReleaseConsistency(7.2.6)弱一致性存在的問題，即當(dāng)訪問同步變量時(shí)，存儲器并不知道這是因?yàn)檫M(jìn)程已完成對共享變量的寫操作還是要開始讀共享變量。若存儲器能夠區(qū)分進(jìn)入還是離開臨界區(qū)的話，應(yīng)用起來會更有效。因此，引入釋放一致性（Gharachorlooetal.,1990），這里需要提供兩種操作：獲?。╝cquire）——訪問用于通知存儲器系統(tǒng)臨界區(qū)已就緒。釋放(release)——訪問表明臨界區(qū)剛退出。程序員都需要在程序中編寫明確的代碼說明何時(shí)做這些操作。ReleaseConsistency(7.2.6)Avalideventsequenceforreleaseconsistency.ReleaseConsistencyRules:Beforeareadorwriteoperationonshareddataisperformed,allpreviousacquiresdonebytheprocessmusthavecompletedsuccessfully.Beforeareleaseisallowedtobeperformed,allpreviousreadsandwritesbytheprocessmusthavecompletedAccessestosynchronizationvariablesareFIFOconsistent(sequentialconsistencyisnotrequired).ReleaseConsistency遵守以下規(guī)定：1．在訪問共享變量前，進(jìn)程所有先前的獲取訪問都必須成功地完成；2．在允許釋放訪問前，進(jìn)程先前的所有讀寫操作都必須結(jié)束；3．獲取訪問和釋放訪問必須是FIFO一致的。ReleaseConsistency釋放一致性在DSM中的簡單應(yīng)用（為多處理機(jī)而設(shè)計(jì)的）。為了執(zhí)行獲取操作，進(jìn)程將消息發(fā)送給同步管理者，要求A在一特殊的鎖定上執(zhí)行獲取訪問。在沒有競爭時(shí)，請求獲準(zhǔn)，獲取訪問完成。對共享數(shù)據(jù)的讀寫就可以在本地開始了。它們不用傳送到其他機(jī)器。當(dāng)執(zhí)行釋放訪問時(shí)，修改過的數(shù)據(jù)被傳送到使用它們的機(jī)器上。當(dāng)每個(gè)機(jī)器確認(rèn)收到數(shù)據(jù)后，同步管理者被告知可以執(zhí)行釋放了。EntryConsistency(7.2.7)Conditions:Anacquireaccessofasynchronizationvariableisnotallowedtoperformwithrespecttoaprocessuntilallupdatestotheguardedshareddatahavebeenperformedwithrespecttothatprocess.Beforeanexclusivemodeaccesstoasynchronizationvariablebyaprocessisallowedtoperformwithrespecttothatprocess,nootherprocessmayholdthesynchronizationvariable,noteveninnonexclusivemode.Afteranexclusivemodeaccesstoasynchronizationvariablehasbeenperformed,anyotherprocess'snextnonexclusivemodeaccesstothatsynchronizationvariablemaynotbeperformeduntilithasperformedwithrespecttothatvariable'sowner.

EntryConsistency(7.2.7)1．只有某一進(jìn)程的保護(hù)共享變量全部被更新以后，該進(jìn)程才允許執(zhí)行同步變量的獲取訪問(當(dāng)進(jìn)程執(zhí)行獲取訪問時(shí)，所有被保護(hù)數(shù)據(jù)的遠(yuǎn)程修改都必須是可見的)；2．在一進(jìn)程以互斥模式訪問該進(jìn)程的同步變量之前，不允許其它進(jìn)程持有此同步變量(在更新一個(gè)共享變量前，進(jìn)程必須以互斥方式進(jìn)入臨界區(qū)，以確定沒有其它進(jìn)程同時(shí)更新它)；3．在結(jié)束互斥模式下對一個(gè)同步變量的訪問后，任意其它進(jìn)程必須與該變量的擁有者核查，才能試圖以非互斥模式訪問該同步變量(若進(jìn)程試圖以非互斥方式進(jìn)入臨界區(qū)，它必須與保護(hù)此臨界區(qū)的同步變量的擁有者核查，以獲得被保護(hù)共享變量的最新拷貝)。EntryConsistencyAvalideventsequenceforentryconsistency.SummaryofConsistencyModelsConsistencymodelsnotusingsynchronizationoperations.Modelswithsynchronizationoperations.ConsistencyDescriptionStrictAbsolutetimeorderingofallsharedaccessesmatters.LinearizabilityAllprocessesmustseeallsharedaccessesinthesameorder.Accessesarefurthermoreorderedaccordingtoa(nonunique)globaltimestampSequentialAllprocessesseeallsharedaccessesinthesameorder.AccessesarenotorderedintimeCausalAllprocessesseecausally-relatedsharedaccessesinthesameorder.FIFOAllprocessesseewritesfromeachotherintheordertheywereused.Writesfromdifferentprocessesmaynotalwaysbeseeninthatorder(a)ConsistencyDescriptionWeakShareddatacanbecountedontobeconsistentonlyafterasynchronizationisdoneReleaseShareddataaremadeconsistentwhenacriticalregionisexitedEntryShareddatapertainingtoacriticalregionaremadeconsistentwhenacriticalregionisentered.(b)Client-CentricConsistencyModels(7.3)Inthissection,wetakealookataspecialclassofdistributeddatastores,whicharecharacterizedbythelackofsimultaneousupdates,orwhensuchupdateshappen,theycaneasilyberesolved.Client-centricconsistencyprovidesguaranteesforasingleclientconcerningtheconsistencyofaccessestoadatastorebythatclient.NoguaranteesaregivenconcerningconcurrentaccessesbydifferentclientsEventualConsistency(7.3.1)Theprincipleofamobileuseraccessingdifferentreplicasofadistributeddatabase.EventualConsistencyTherearemanycasesof(large-scale)distributedandreplicateddatabasesthattoleratearelativelyhighdegreeofinconsistency.Theyhaveincommonthatifnoupdatestakeplaceforalongtime,allreplicaswillgraduallybecomeconsistent.Thisofconsistencyiscalledeventualconsistency.Forexample,DNS,WWW,etc.（WS(xi[t])表示在時(shí)刻t，本地副本Li上的一系列write操作的結(jié)果，t可以省略）。Monotonic-ReadConsistency(7.3.2)Condition:Ifaprocessreadsthevalueofadataitemx,anysuccessivereadoperationonxbythatprocesswillalwaysreturnthatsamevalueoramorerecentvalue.

(toguaranteethatifaprocesshasseenavalueofxattimet,itwillneverseeanolderversionofxatalatertime).MonotonicReadsThereadoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.Amonotonic-readconsistentdatastore;Adatastorethatdoesnotprovidemonotonicreads;Monotonic-WriteConsistence(7.3.3)Condition:Awriteoperationbyaprocessonadataitemxiscompletedbeforeanysuccessivewriteoperationonxbythesameprocess.MonotonicWritesThewriteoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastoreAmonotonic-writeconsistentdatastore.Adatastorethatdoesnotprovidemonotonic-writeconsistency(missingW(x1)).Read-Your-WritesConsistency(7.3.4)Condition:Theeffectofawriteoperationbyaprocessonadataitemxwillalwaysbeseenbyasuccessivereadoperationonxbythesameprocess.Read-Your-WritesConsistency(7.3.4)Adatastorethatprovidesread-your-writesconsistency.Adatastorethatdoesnot(W(x1)notbeenpropagatedtoL2).Writes-Follow-ReadsConsistency(7.3.5)Condition:Awriteoperationbyaprocessonadataitemxfollowingapreviousreadoperationonxbythesameprocess,isguaranteedtotakeplaceonthesameoramorerecentvalueofthatwasread.(Inotherwords,anysuccessivewriteoperationbyaprocessonadataitemxwillbeperformedonacopyofxthatisuptodatewiththevaluemostrecentlyreadbythatprocess)

Whichcanbeusedtoguaranteethatusersofanetworknewsgroupseeapostingofareactiontoanarticleonlyaftertheyhaveseentheoriginalarticle.WritesFollowReadsAwrites-follow-readsconsistentdatastoreAdatastorethatdoesnotprovidewrites-follow-readsconsistencyImplementation(7.3.6)Anativeimplementation:Eachwriteoperationisassignedagloballyuniqueidentifierbytheserverthatacceptstheoperationforthefirsttime(initiatedbyserver).Foreachclient,wekeeptrackoftwosetsofwriteidentifiers.Thereadset={thewriteidentifiersrelevantforthereadoperationsperformedbyaclient}.Forexample:Pid-read-set={wid1,wid2,……widn}Thewriteset={theidentifiersofthewritesperformedbytheclient}.Implementation(7.3.6)monotonic-readconsistency:

whenaclientperformsareadoperationataserver,thatserverishandedtheclient’sreadsettocheckwhetheralltheidentifiedwriteshavetakenplacelocally.Ifnot:1)itcontactstheotherserverstoensurethatitisbroughtuptodatebeforecarryingoutthereadoperation.or2)thereadoperationisforwardedtoaserverwherethewriteoperationsthatalreadytakenplace.

Afterthereadoperationisperformed,thewriteoperationsthathavetakenplaceattheselectedserverandwhicharerelevantforthereadoperation,areaddedtotheclient’sreadset.Implementation(7.3.6)ClientARead-setReadImplementation(7.3.6)monotonic-writeconsistency:wheneveraclientinitiateanewwriteoperationataserver,thatserverishandedovertheclient’swriteset.Itthenensuresthattheidentifiedwriteoperationsareperformedfirstandinthecorrectorder.Afterperformingthenewoperation,thatoperation’swriteidentifierisaddedtothewriteset.Implementation(7.3.6)ClientAWrite-setWriteImplementation(7.3.6)read-your-writesconsistency:Requiringthattheserverwherethereadoperationisperformedhasseenallthewriteoperationsintheclient’swriteset.1)Thewritescansimplybefetchedfromotherserversbeforethereadoperationisperformed.2)Theclient-sidesoftwarecansearchforaserverwheretheidentifiedwriteoperationsintheclient’swritesethavealreadybeenperformed.Implementation(7.3.6)ClientAWrite-setReadImplementation(7.3.6)writes-follow-readsconsistency:bringingtheselectedserveruptodatewiththewriteoperationsintheclient’sreadset,andthenlateraddingtheidentifierofthewriteoperationtothewriteset,alongwiththeidentifiersinthereadset.Implementation(7.3.6)ClientARead-setWriteImprovingEfficiencySetssizesession:Client’sreadandwriteoperationsaregroupedintosessionsassociatedwithanapplication,whichopenedwhentheapplicationstartsandisclosedwhenitexits.Setsrepresentation:ts(WID),ts---timestampDISTRIBUTIONPROTOCOLS(7.4)Discussingthedifferentwaysofpropagating(distributingupdatestoreplicas).Decidingwhere,when,andbywhomcopiesofthedatastorearetobeplaced.ReplicaPlacement(7.4.1)Thelogicalorganizationofdifferentkindsofcopiesofadatastoreintothreeconcentricrings.TheinitialsetofreplicasthatconstituteadistributeddatastoreServer-InitiatedReplicasKnowsaspushcaches.服務(wù)器根據(jù)需要?jiǎng)討B(tài)進(jìn)行復(fù)制：1)toreducetheloadonaserver2)tobemigrated,orreplicatedtoserverplacedintheproximityofclientsthatissuemanyrequestsforthosefiles.Eachserverkeepstrackofaccesscountsperfile,andwhereaccessrequestscomefrom.Server-InitiatedReplicasCountingaccessrequestsfromdifferentclients.Server-InitiatedReplicascntQ(P,F)-allaccesscount(atQ)forFatQfromC1andC2(C1andC2sharethesameclosestserverP)del(S,F)-deletionthresholdrep(S,F)-replicationthresholdIfcnt(S,F)<del(S,F)thenremoveFfromS;Ifcnt(S,F)>rep(S,F)thenreplicateFatS;Ifdel(S,F)<cnt(P,F)andcnt(P,F)<rep(S,F)thenonlytobemigrated.Client-InitiatedReplicasKnownasclientcaches.

creatingacacheattheclientwhenneededandmanagingthecacheisleftentirelytothatclientUpdatePropagation(7.4.2)threepropagations:1.Propagateonlyanotificationofanupdate(knownasinvalidationprotocols)2.Transferdatafromonecopytoanother.3.Propagatetheupdateoperationtoothercopies.EnsuringrelevantconsistencyaccordingtoneedPullversusPushProtocolsAcomparisonbetweenpush-basedandpull-basedprotocolsinthecaseofmultipleclient,singleserversystems.IssuePush-basedPull-basedStateofserverListofclientreplicasandcachesNoneMessagessentUpdate(andpossiblyfetchupdatelater)PollandupdateResponsetimeatclientImmediate(orfetch-updatetime)Fetch-updatetimeIfinvalidationprotocolEpidemicProtocolsImplementeventual-consistentbasedonepidemics.aserverPpicksanotherserverQatrandom,andsubsequentlyexchangesupdateswithQ.Threeapproaches:1.PonlypushesitsownupdatestoQ2.PonlypullsinnewupdatesfromQ3.P