高级操作系统 第7章 分布式系统

ConsistencyandReplicationChapter77.1.1ReasonsforReplication:1)reliability2)performanceCaveatGaininperformance；Costofincreasedbandwidthformaintainingreplication；

Introduction(7.1)Dataaregenerallyreplicatedtoenhancereliabilityorimproveperformanceindistributedsystemorparallelcomputerssystem.Howtokeepreplicasconsistentisoneofthemajorproblems.whenonecopyisupdated,weneedtoensurethattheothercopiesareupdatedaswell.Introduction(7.1)7.1.2ObjectReplication1)Adistributedremoteobjectissharedbymultipleclients-------howtoprotecttheobjectagainstsimultaneousaccessbymultipleclients.2)Adistributedremoteobjectisreplicatedatdifferentnode-------howtoensurethatconcurrentinvocationsareperformedinthecorrectorderateachofthereplicas.Introduction(7.1)ObjectsharedOrganizationofadistributedremoteobjectsharedbytwodifferentclients.ObjectsharedAremoteobjectcapableofhandlingconcurrentinvocationsonitsown.AremoteobjectforwhichanobjectadapterisrequiredtohandleconcurrentinvocationsObjectsharedFig(a):Forexample,javaobject----whichcanbeconstructedasamonitorbydeclaringtheobject’smethodtobesynchronized.publicsynchronizedvoidenter(Objectitem){ while(count==BUFFER_SIZE) Thread.yield(); ++count; buffer[in]=item; in=(in+1)%BUFFER_SIZE;}ObjectReplicationAdistributedsystemforreplication-awaredistributedobjects.（SOS，Globeetc.）Adistributedsystemresponsibleforreplicamanagement(CORBAetc.)

实现机理与一致性模型?ObjectReplication7.1.3ReplicationasScalingTechniquePlacingcopiesofdataandobjectsclosetotheprocessesusingthemcanimproveperformancethroughreductionofaccesstime,andthussolvescalabilityproblems.Replicationandcachingforperformancearewidelyappliedasscalingtechniques.Dilemmaproblem:Scalabilityproblemcanbealleviatedbyapplyingreplicationandcaching,leadingtoimprovedperformance.Tokeepallcopiesconsistentgenerallyrequiresglobalsynchronization,whichisinherentlycostlyintermsofperformance.ObjectReplication1.DATA-CENTRICCONSISTENCYMODELS.2.CLIENT-CENTRICCONSISTENCYMODELSTWOCONSISTENCYMODELSDATA-CENTRICCONSISTENCYMODELSAdatastoremaybephysicallydistributedacrossmultiplemachines:(distributed)sharedmemory,(distributed)shareddatabase,ora(distributed)filesystem.Adataoperationisclassifiedas:writeoperation;readoperation;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)假设在DCS中，有如下情形：先读后写。NodeANode

BP1x

…

read(B:xatt1)P2

…t2-t1=1nsWrite(B:xatt2)严格一致性:A应该读出原来x值。假设机器间距离3米，从A到B传送读操作并使之先于B的写操作，则信号必须以十倍光速传递，与爱因斯坦相对论矛盾.1ns(纳秒)=10-9秒。可理解为单/多副本方式.StrictConsistency(7.2.1)Behavioroftwoprocesses,operatingonthesamedataitem.(a)Astrictlyconsistentstore；(b)Astorethatisnotstrictlyconsistent；StrictConsistency(7.2.1)严格一致性存储器，写操作在任一时刻对所有进程都是可见的，后读出的都是新更改值。反之，无论后面的写操作有多快，前面的读操作仍应是原来的值。系统维护一个绝对全局时间。严格一致性是理想的编程模式，在分布式系统中，这几乎不可能实现。LinearizabilityandSequentialConsistency(7.2.2)Sequentialconsistent(顺序一致性条件，Lamport1979)：Theresultofanyexecutionisthesameasifthe(readandwrite)operationbyallprocessesonthedatastorewereexecutedinsomesequentialorderandtheoperationsofeachindividualprocessappearinthissequenceintheorderspecifiedbyitsprogram.

所有进程对数据执行的结果顺序与每个进程各自对数据执行的结果顺序一致。不同机器上并发运行的进程，任何有效的交错是可以接受的，但所有进程必须遵守同一访问顺序。LinearizabilityandSequentialConsistency(7.2.2)Asequentiallyconsistentdatastore.Adatastorethatisnotsequentiallyconsistent.不保证读返回值是1ns/1ms/1分钟以前另一进程写入的。只保证所有进程以相同的顺序看见存储器访问(图a)，如果缺少明确的同步操作，则结果是不确定的。LinearizabilityandSequentialConsistency(2)Threeconcurrentlyexecutingprocesses.ProcessP1ProcessP2ProcessP3x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);6个语句共有720(6！)种可能的执行顺序，但是，只有90个是有效的。注：x=1开始的顺序有120(5！)种,其中只有1/4（y=1/z=1在print()前,各1/2）即30个是有效的。另外，分别是以y=1和z=1开头的各30个。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:Theresultofanyexecutionisthesameasifthe(readandwrite)operationbyallprocessesonthedatastorewereexecutedinsomesequentialorderandtheoperationsofeachindividualprocessappearinthissequenceintheorderspecifiedbyitsprogram.Inaddition,iftsOP1(x)<tsOP2(y),thenoperationOP1(xshouldprecedeOP2(y)inthissequence.LettsOP1(x)denotethetimestampassignedtooperationOPthatisperformedondataitemx；满足顺序一致性约束的同时满足时间戳的顺序（比顺序一致性强）LinearizabilityandSequentialConsistency(4)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.所有进程仅看到满足因果关系一致性模型的写操作结果。CasualConsistency(2)Thissequenceisallowedwithacasually-consistentstore,butnotwithsequentiallyorstrictlyconsistentstore.(W2(x)bandW1(x)careconcurrent).可以是不同进程的因果顺序.比如W(x)b与W(x)b有因果关系写无因果关系写CasualConsistency(3)Aviolationofacasually-consistentstore（不满足）.Acorrectsequenceofeventsinacasually-consistentstore.Implement:requiringkeepingtrackofwhichprocesseshaveseenwhichwrites(实现思想:建立并维护一个依赖图：即一个操作依赖于其它什么操作)。FIFOConsistency(orPRAM)(7.2.4)NecessaryCondition:

Writesdonebyasingleprocessareseenbyallotherprocessesintheorderinwhichtheywereissued,butwritesfromdifferentprocessesmaybeseeninadifferentorderbydifferentprocesses

一个进程的写操作可以被其它进程以相同的顺序接收到，但不同进程的写操作在不同进程看来次序可以是不同的.强调一个进程的操作顺序.

PRAM一致性由LIPTON和SANDBERG（1988）提出，PRAM代表管道RAM，一个进程的写操作可以是流水线的，进程不必在开始下一个操作之前等待一操作结束，只要求一个进程的写操作顺序被所有进程看到。FIFOConsistencyAvalidsequenceofeventsofFIFOconsistency

保证由同一个进程的写操作顺序被所有进程看到。可通过设置序列号实现。

themodelcanbeimplementedbysimplytaggingeachwriteoperationwitha(process,sequencenumber)pair,andperformingwritesperprocessintheorderoftheirsequencenumber.

与因果一致性的区别：因果关系可以是不同进程之间，比如同步点。确定的顺序FIFOConsistencyStatementexecutionasseenbythethreeprocessesfromthepreviousslide.Thestatementsinboldaretheonesthatgeneratetheoutputshown.(结果只受本进程顺序影响)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)如果将三个进程的输出顺序相接,得到结果为001001FIFOConsistency在FIFO中不同进程看到的语句执行顺序不同，进程P1、P2和P3分别看到的是图(a)、(b)和(c)。对于顺序一致存储器,三个不同显示是不允许的，比如结果“001001”在顺序一致性下不可能的。yzxzxy不同之处：前者尽管未确定语句（和存储器访问）的执行顺序,但至少所有进程都遵守共同的顺序。后者就不遵守，不同进程看到的操作顺序不同(不同进程写结果可不同)。FIFOConsistencyTwoconcurrentprocesses.GOODMAN（1989）提出了一种略微不同但仍支持PRAM一致的存储器形式。上述例子中，顺序一致性只能出现三种结果:1）P1被KILL;2）P2被KILL;3）两者都不被KILL。

FIFO一致性两个进程都可能被KILL（不同进程的写是并发的）。ProcessP1ProcessP2x=1;if(y==0)kill(P2);y=1;if(x==0)kill(P1);WeakConsistency(7.2.5)FIFO要求一个进程的写操作顺序被所有进程看到，实际应用中，并非所有应用程序必须要看到所有写操作。比如：临界区中一个进程通过循环读写复制数据。只需让进程完成临界区后的操作结果可见,中间结果不重要。Properties(Duboisetal.1986):AccessestosynchronizationvariablesassociatedwithadatastorearesequentiallyconsistentNooperationonasynchronizationvariableisallowedtobeperformeduntilallpreviouswriteshavebeencompletedeverywhereNoreadorwriteoperationondataitemsareallowedtobeperformeduntilallpreviousoperationstosynchronizationvariableshavebeenperformed.WeakConsistency(7.2.5)需要一个同步变量完成一致性操作。1．对同步变量的访问是顺序一致的；2．在先前所有的写操作完成之前,不能访问同步变量；3．在先前所有同步变量的访问完成前，不能访问（读或写）数据；

2和3说明了对同步变量操作的约束。弱一致性是对一组操作的一致性约束，不是单独的读或写。WeakConsistencyAvalidsequenceofeventsforweakconsistency.Aninvalidsequenceforweakconsistency.WeakConsistencyAprogramfragmentinwhichsomevariablesmaybekeptinregisters.若允许另外一个进程可随意读取存储器的话，只需让编译器写一标志位说明存储器没有更新。若另一进程访问A，它会在标志位上等待。应用实例：一个优化的编译器可以在寄存器中计算a和b，并保存中间结果不更新存储器，只有当调用函数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*/ReleaseConsistency(7.2.6)弱一致性存在的问题：访问同步变量时，存储器不知道是因为进程已完成对共享变量的写操作还是要开始读共享变量。因此引入释放一致性（Gharachorlooetal.,1990），提供两种操作：获取（acquire）——访问用于通知存储器系统临界区已就绪。释放(release)——访问表明临界区刚退出。程序员需要在程序中编写代码明确说明何时做这些操作。ReleaseConsistency(7.2.6)Avalideventsequenceforreleaseconsistency.ReleaseConsistencyRules:Beforeareadorwriteoperationonshareddataisperformed,allpreviousacquiresdonebytheprocessmusthavecompletedsuccessfully.Beforeareleaseisallowedtobeperformed,allpreviousreadsandwritesbytheprocessmusthavecompletedAccessestosynchronizationvariablesareFIFOconsistent(sequentialconsistencyisnotrequired).ReleaseConsistency遵守以下规定：在访问共享变量前，进程所有先前的获取访问都必须成功地完成；在允许释放访问前，进程先前的所有读写操作都必须结束；获取访问和释放访问必须是FIFO一致的。ReleaseConsistency在DSM的应用：进程A将获取操作请求发送给同步管理者，要求在一特殊锁上执行获取访问：无竞争时请求获准，获取访问完成。A对共享数据在本地进行读写，不必同步更新副本。当执行释放访问时，同步更新副本完成后，同步管理者被告知可以执行释放了。EntryConsistency(7.2.7)Conditions:Anacquireaccessofasynchronizationvariableisnotallowedtoperformwithrespecttoaprocessuntilallupdatestotheguardedshareddatahavebeenperformedwithrespecttothatprocess.Beforeanexclusivemodeaccesstoasynchronizationvariablebyaprocessisallowedtoperformwithrespecttothatprocess,nootherprocessmayholdthesynchronizationvariable,noteveninnonexclusivemode.Afteranexclusivemodeaccesstoasynchronizationvariablehasbeenperformed,anyotherprocess'snextnonexclusivemodeaccesstothatsynchronizationvariablemaynotbeperformeduntilithasperformedwithrespecttothatvariable'sowner.EntryConsistency(7.2.7)1．当某一进程的保护共享变量全部被更新以后，该进程才允许执行同步变量的获取访问；2．在一进程以互斥模式访问该进程的同步变量之前，不允许其它进程持有此同步变量；3．在结束互斥模式下对一个同步变量的访问后，任意其它进程必须与该变量的拥有者核查，才能试图以非互斥模式访问该同步变量。EntryConsistencyAvalideventsequenceforentryconsistency.SummaryofConsistencyModelsConsistencymodelsnotusingsynchronizationoperations.Modelswithsynchronizationoperations.ConsistencyDescriptionStrictAbsolutetimeorderingofallsharedaccessesmatters.LinearizabilityAllprocessesmustseeallsharedaccessesinthesameorder.Accessesarefurthermoreorderedaccordingtoa(nonunique)globaltimestampSequentialAllprocessesseeallsharedaccessesinthesameorder.AccessesarenotorderedintimeCausalAllprocessesseecausally-relatedsharedaccessesinthesameorder.FIFOAllprocessesseewritesfromeachotherintheordertheywereused.Writesfromdifferentprocessesmaynotalwaysbeseeninthatorder(a)ConsistencyDescriptionWeakShareddatacanbecountedontobeconsistentonlyafterasynchronizationisdoneReleaseShareddataaremadeconsistentwhenacriticalregionisexitedEntryShareddatapertainingtoacriticalregionaremadeconsistentwhenacriticalregionisentered.(b)Client-CentricConsistencyModels(7.3)Client-centricconsistencyprovidesguaranteesforasingleclientconcerningtheconsistencyofaccessestoadatastorebythatclient.Noguaranteesaregivenconcerningconcurrentaccessesbydifferentclients(Nosimultaneousupdates)Client-CentricConsistencyModels

EventualConsistency(7.3.1)Theprincipleofamobileuseraccessingdifferentreplicasofadistributeddatabase.EventualConsistencyTherearemanycasesof(large-scale)distributedandreplicateddatabasesthattoleratearelativelyhighdegreeofinconsistency.Theyhaveincommonthatifnoupdatestakeplaceforalongtime,allreplicaswillgraduallybecomeconsistent.---eventualconsistency.Forexample,DNS,WWW,etc.Monotonic-ReadConsistency(7.3.2)Condition:

Ifaprocessreadsthevalueofadataitemx,anysuccessivereadoperationonxbythatprocesswillalwaysreturnthatsamevalueoramorerecentvalue.

(toguaranteethatifaprocesshasseenavalueofxattimet,itwillneverseeanolderversionofxatalatertime).MonotonicReadsThereadoperationsperformedbyasingleprocessPattwodifferentlocalcopiesofthesamedatastore.Amonotonic-readconsistentdatastore;Adatastorethatdoesnotprovidemonotonicreads;（WS(xi[t])表示在时刻t，本地副本Li上的一系列write操作的结果，t可以省略）。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)WritesFollowReadsAwrites-follow-readsconsistentdatastoreAdatastorethatdoesnotprovidewrites-follow-readsconsistencyWrites-Follow-ReadsWrites-Follow-ReadsConsistencycanbeusedtoguaranteethatusersofanetworknewsgroupseeapostingofareactiontoanarticleonlyaftertheyhaveseentheoriginalarticle.Implementation(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.Implementation(7.3.6)ClientARead-setReadAfterthereadoperationisperformed,thewriteoperationsthathavetakenplaceattheselectedserverandwhicharerelevantforthereadoperation,areaddedtotheclient’sreadset.Implementation(7.3.6)monotonic-writeconsistency:wheneveraclientinitiateanewwriteoperationataserver,itcontactstheotherserverstoensurethatitisbroughtuptodatebeforecarryingoutthewriteoperation.orthewritesetisforwardedtoaserverwherethewriteoperationsthatalreadytakenplace.Itthenensuresthattheidentifiedwriteoperationsareperformedfirstandinthecorrectorder.Implementation(7.3.6)ClientAWrite-setWriteAfterperformingthenewoperation,thatoperation’swriteidentifierisaddedtothewriteset.Implementation(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/pushmode：toreducetheloadonaserver；tobemigrated,orreplicatedtoserverplacedintheproximityofclientsthatissuemanyrequestsforthosefiles；Eachserverkeepstrackofaccesscountsperfile,andwhereaccessrequestscomefrom.Server-InitiatedReplicasCountingaccessrequestsfromdifferentclients.Server-InitiatedReplicascntQ(P,F)-allaccesscountforFatQfromC1andC2(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/pullmode.Creatingacacheattheclientwhenneededandmanagingthecacheisleftentirelytothatclient.UpdatePropagation(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.PandQsendupdatestoeachother(pull-pull)CONSISTENCYPROTOCOLS(7.5)Implementaspecificconsistencymodel(sequential,weakconsistency,andatomictransaction).“Globalsequence”7.5.1Primary-basedProtocolsRemote-WriteProtocols(1)Primary-basedremote-writeprotocolwithafixedservertowhichallreadandwriteoperationsareforwarded(主副本固定).BlockingornonblockingRemote-WriteProtocols(2)Theprincipleofprimary-backupprotocol(带复制的主副本).Local-WriteProtocols(1)Primary-basedlocal-writeprotocolinwhichasinglecopyismigratedbetweenprocesses(可移动的主副本).Local-WriteProtocols(2)Primary-backupprotocolinwhichtheprimarymigratestotheprocesswantingtoperformanupdate(带复制的可移动主副本).ActiveReplication(1)Theproblemofreplicatedinvocations(eachreplicahasanassociatedprocessthatcarriesoutupdateoperation).Replicated-WriteProtocols(7.5.2)ActiveReplication(2)Forwardinganinvocationrequestfromareplicatedobject.Returningareplytoareplicatedobject.Quorum-BasedProtocolsTwoconstraints(forNreplicas):1.NR+NW>N;2.NW

>N/2Threeexamplesofthevotingalgorithm:(a)Acorrectchoiceofreadandwriteset;(b)Achoicethatmayleadtowrite-writeconflicts;(c)Acorrectchoice,knownasROWA(readone,writeall);背景:Paxos是古希腊的一个小岛,其法令通过议会表决形成，议员和信使都是兼职,且不一定在会议厅，议员通过信使传递消息,并且信使可能重复投递消息,也可能一去不复返。需要一种协议:

保证在这种情况下法令仍然能够正确产生，并且不会出现冲突！Paxos算法LeslieLamport1998在ACMTCS上发表了关于paxos的论文“ThePart-TimeParliament”，由于晦涩难懂，2001年又发表了“PaxosMadeSimple”；Paxos算法介绍Google使用该算法后使其声名大噪，GoogleChubby的作者MikeBurrows：Thereisonlyoneconsensusprotocol,andthat‘sPaxos”-allotherapproachesarejustbrokenversionsofPaxos.（OSDI2006）在分布式系统中有一组Process，它们需要确定一个Value。每个Process都提出了一个Value，共识(consensus)就是指只能有一个Value被选中作为最后确定的值，并且当这个值被确定后，所有Processes都要被通知到.IntroductionLockistheeasiestwaytomanageconcurrencyMutexandsemaphore.Readandwritelocksin2PLfortransaction.Indistributedsystem:Nomasterforissuinglocks.Failures.Problem:

Howtoreachconsensus/dataconsistencyindistributedsystemthatcantoleratenon-maliciousfailures?RequirementsSafetyOnlyavaluethathasbeenproposedmaybechosen.只有提案才能被选定；Onlyasinglevalueischosen.只能有一个值被选定;Anodeneverlearnsthatavaluehasbeenchosenunlessitactuallyhasbeen.除非那个提案被选中，否则，某个节点不会知道有提案被选中。RequirementsLivenessSomeproposedvalueiseventuallychosen.保证最终有一个提案会被选定;Ifavaluehasbeenchosen,anodecaneventuallylearnthevalue.当提案被选定后，进程最终也能获取到被选定的提案。Paxos‘snotationandalgorithmClassesofagentsAnodecanactasmorethanoneclients(usually3):Proposers；Acceptors；Learners；算法思想PaxosalgorithmPhase1(prepare):Aproposerselectsaproposalnumbernandsendsapreparerequestwithnumberntomajorityofacceptors.Ifanacceptorreceivesapreparerequestwithnumberngreaterthanthatofanypreparerequestitsaw,itresponsesYEStothatrequestwithapromisenottoacceptanymoreproposalsnumberedlessthannandincludethehighest-numberedproposal(ifany)thatithasaccepted.

接受者只响应目前收到的编号最大的提案请求者.PaxosalgorithmPhase2(accept):IftheproposerreceivesaresponseYEStoitspreparerequestsfromamajorityofacceptors,thenitsendsanacceptrequest

toeachofthoseacceptorsforaproposalnumberednwithavaluesv

whichisthevalueofthehighest-numberedproposalamongtheresponses.Ifanacceptorreceivesanacceptrequestforaproposalnumberedn,itacceptstheproposalunlessithasalreadyrespondedtoapreparerequesthavinganumbergreaterthann.DefinitionofchosenAvalueischosenatproposalnumberniffmajorityofacceptoracceptthatvalueinphase2oftheproposalnumber.Paxos’spropertiesP1:Anyproposalnumberisunique.P2:Anytwosetofacceptorshaveatleastoneacceptorincommon.P3:thevaluesentoutinphase2isthevalueofthehighest-numberedproposalofalltheresponsesinphase1.LearningachosenvalueTherearesomeoptions:Eachacceptor,wheneveritacceptsaproposal,informsallthelearners.Acceptorsinformsadistinguishedlearner(usuallytheproposer)andletthedistinguishedlearnerbroadcasttheresult.ClassicPaxos情形1:PaxoswithoutProposerCompetitionPreparesetabc=0abc=X(1)Response(1)&&PromiseResponse

ClassicPaxosAcceptabc=XAccept(1,setabc=0)&&Promise(1,setabc=0)Response(1)&&PromiseClassicPaxosAcceptabc=0Acceptedsetabc=0accpetedAccep