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

任何操作的執(zhí)行結(jié)果都應(yīng)該與所有的進程以程序規(guī)定的順序，好象在各自單個進程執(zhí)行的順序一致。表明:對于在不同機器上并發(fā)運行的進程，任何有效的交錯都是可以接受的行為，但所有進程必須遵守同一訪問順序。LinearizabilityandSequentialConsistency(7.2.2)Asequentiallyconsistentdatastore.Adatastorethatisnotsequentiallyconsistent.順序一致存儲器不保證讀返回的值是1ns、1ms甚至1分鐘以前另一進程寫入的。它只保證所有進程以相同的順序看見存儲器訪問。如圖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個獨立的語句，有720(6！)種可能的執(zhí)行順序。從x=1開始考慮的順序有120(5！)種,其中只有1/4（y=1/z=1在print()前,各1/2）即30個是有效的。另外30個有效順序是以y=1開頭的，還有30個以z=1開頭。共有90個有效執(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)滿足時間戳的順序)(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)進程看到是一致的。CasualConsistency(2)Thissequenceisallowedwithacasually-consistentstore,butnotwithsequentiallyorstrictlyconsistentstore.(W2(x)bandW1(x)careconcurrent).有因果關(guān)系寫無因果關(guān)系寫CasualConsistency(3)Aviolationofacasually-consistentstore（不滿足）.Acorrectsequenceofeventsinacasually-consistentstore.Implement:requiringkeepingtrackofwhichprocesseshaveseenwhichwrites(實現(xiàn)因果一致性需要由記錄來跟蹤哪個進程看到哪個寫操作。這要建立和維護一個依賴圖：即一個操作依賴于其它什么操作)。FIFOConsistency(orPRAM)(7.2.4)NecessaryCondition:

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

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

themodelcanbeimplementedbysimplytaggingeachwriteoperationwitha(process,sequencenumber)pair,andperformingwritesperprocessintheorderoftheirsequencenumber.指定順序FIFOConsistencyStatementexecutionasseenbythethreeprocessesfromthepreviousslide.Thestatementsinboldaretheonesthatgeneratetheoutputshown.(結(jié)果只受本進程順序影響)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一致下,不同進程所看到的語句執(zhí)行順序不同,如圖(a)顯示P1怎樣看到事件，而(b)顯示P2所看到的，(C)則是P3所見。對于順序一致存儲器,三個不同顯示是不允許的。如果使三個進程的輸出順序相接,得到結(jié)果為001001，這在順序一致性下是不可能的。兩者的關(guān)鍵不同在于：前者盡管未確定語句（和存儲器訪問）的執(zhí)行順序,但至少所有進程都遵守共同的順序。后者就不遵守。不同進程看到的操作順序不同。FIFOConsistencyTwoconcurrentprocesses.GOODMAN（1989）提出了一種略微不同但仍支持PRAM一致的存儲器形式。如上述例子中，在順序一致下只能出現(xiàn)三種結(jié)果之一:1）P1被KILL;2）P2被KILL;3）兩者都不被KILL。但是，在FIFO一致下,可能兩個進程都被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一致性比強模式的更好,但它仍對很多應(yīng)用程序做了不必要的限制，即要求一個進程以一定順序的寫操作被所有進程看到，并非所有應(yīng)用程序要看到所有寫操作。比如在臨界區(qū)中一個進程循環(huán)讀寫被復(fù)制數(shù)據(jù)。只需讓進程完成臨界區(qū)操作以后,將最后結(jié)果發(fā)送到各處,而不用太關(guān)心甚至不用關(guān)心中間結(jié)果是否也順序發(fā)送到所有結(jié)點。WeakConsistency(7.2.5)Properties(Duboisetal.1986):AccessestosynchronizationvariablesassociatedwithadatastorearesequentiallyconsistentNooperationonasynchronizationvariableisallowedtobeperformeduntilallpreviouswriteshavebeencompletedeverywhereNoreadorwriteoperationondataitemsareallowedtobeperformeduntilallpreviousoperationstosynchronizationvariableshavebeenperformed.WeakConsistency(7.2.5)1．對同步變量的訪問是順序一致的(所有進程以相同順序看到對同步變量的訪問)；2．在所有先前的寫操作完成之前,不能訪問同步變量(同步訪問開始前。在更新共享數(shù)據(jù)后做同步操作，進程可將新值傳遍所有存儲器)；3．在先前所有同步變量的訪問完成前，不能訪問（讀或?qū)懀?shù)據(jù)(訪問一般非同步變量，不管是讀是寫，只有在所有前序的同步操作結(jié)束后方可進行。在讀共享數(shù)據(jù)前做同步操作，可以保證進程讀到最新值)；它是對一組操作的一致性約束,而不是單獨的讀或?qū)?。當基本上以簇的形式（短時間內(nèi)有很多訪問，每一訪問時間都不長）訪問共享變量時，這個模型很有用。WeakConsistencyAprogramfragmentinwhichsomevariablesmaybekeptinregisters.若允許另外一個進程可隨意讀取存儲器的話，只需讓編譯器寫一標志位說明存儲器沒有更新。若另一進程訪問A，它會在標志位上等待。該思想已經(jīng)得到許多應(yīng)用，例如：一個優(yōu)化的編譯器可以在寄存器中計算a和b，并保存片刻，不更新存儲器，只有當調(diào)用函數(shù)f后才將a和b當前值返還存儲器。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)弱一致性存在的問題，即當訪問同步變量時，存儲器并不知道這是因為進程已完成對共享變量的寫操作還是要開始讀共享變量。若存儲器能夠區(qū)分進入還是離開臨界區(qū)的話，應(yīng)用起來會更有效。因此，引入釋放一致性（Gharachorlooetal.,1990），這里需要提供兩種操作：獲取（acquire）——訪問用于通知存儲器系統(tǒng)臨界區(qū)已就緒。釋放(release)——訪問表明臨界區(qū)剛退出。程序員都需要在程序中編寫明確的代碼說明何時做這些操作。ReleaseConsistency(7.2.6)Avalideventsequenceforreleaseconsistency.ReleaseConsistencyRules:Beforeareadorwriteoperationonshareddataisperformed,allpreviousacquiresdonebytheprocessmusthavecompletedsuccessfully.Beforeareleaseisallowedtobeperformed,allpreviousreadsandwritesbytheprocessmusthavecompletedAccessestosynchronizationvariablesareFIFOconsistent(sequentialconsistencyisnotrequired).ReleaseConsistency遵守以下規(guī)定：1．在訪問共享變量前，進程所有先前的獲取訪問都必須成功地完成；2．在允許釋放訪問前，進程先前的所有讀寫操作都必須結(jié)束；3．獲取訪問和釋放訪問必須是FIFO一致的。ReleaseConsistency釋放一致性在DSM中的簡單應(yīng)用（為多處理機而設(shè)計的）。為了執(zhí)行獲取操作，進程將消息發(fā)送給同步管理者，要求A在一特殊的鎖定上執(zhí)行獲取訪問。在沒有競爭時，請求獲準，獲取訪問完成。對共享數(shù)據(jù)的讀寫就可以在本地開始了。它們不用傳送到其他機器。當執(zhí)行釋放訪問時，修改過的數(shù)據(jù)被傳送到使用它們的機器上。當每個機器確認收到數(shù)據(jù)后，同步管理者被告知可以執(zhí)行釋放了。EntryConsistency(7.2.7)Conditions:Anacquireaccessofasynchronizationvariableisnotallowedtoperformwithrespecttoaprocessuntilallupdatestotheguardedshareddatahavebeenperformedwithrespecttothatprocess.Beforeanexclusivemodeaccesstoasynchronizationvariablebyaprocessisallowedtoperformwithrespecttothatprocess,nootherprocessmayholdthesynchronizationvariable,noteveninnonexclusivemode.Afteranexclusivemodeaccesstoasynchronizationvariablehasbeenperformed,anyotherprocess'snextnonexclusivemodeaccesstothatsynchronizationvariablemaynotbeperformeduntilithasperformedwithrespecttothatvariable'sowner.

EntryConsistency(7.2.7)1．只有某一進程的保護共享變量全部被更新以后，該進程才允許執(zhí)行同步變量的獲取訪問(當進程執(zhí)行獲取訪問時，所有被保護數(shù)據(jù)的遠程修改都必須是可見的)；2．在一進程以互斥模式訪問該進程的同步變量之前，不允許其它進程持有此同步變量(在更新一個共享變量前，進程必須以互斥方式進入臨界區(qū)，以確定沒有其它進程同時更新它)；3．在結(jié)束互斥模式下對一個同步變量的訪問后，任意其它進程必須與該變量的擁有者核查，才能試圖以非互斥模式訪問該同步變量(若進程試圖以非互斥方式進入臨界區(qū)，它必須與保護此臨界區(qū)的同步變量的擁有者核查，以獲得被保護共享變量的最新拷貝)。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])表示在時刻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ù)需要動態(tài)進行復(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