An Efficient Scheme for Dynamic Data Replication

zhuying2006
2 ℃
2020-06-19

整理文档很辛苦，赏杯茶钱您下走！

还剩 ... 页未读，继续阅读 >>

免费阅读已结束，点击下载阅读编辑剩下 ... 页

阅读已结束，您可以下载文档离线阅读编辑

资源描述

AnEcientSchemeforDynamicDataReplicationSwarupAcharyaandStanleyB.ZdonikDepartmentofComputerScienceBrownUniversityProvidence,RhodeIsland02912CS-93-43September1993AnEcientSchemeforDynamicDataReplicationSwarupAcharyaStanleyB.ZdonikDept.ofComputerScienceBrownUniversityProvidence,RI02912-1910email:fsa,sbzg@cs.brown.eduAbstractThispaperpresentsanecientschemefordynamicreplicationofdataindistributedenvironments.Theaimoftheschemeistoincreasesystemperformancebyintelligentdataplacementsoastooptimizethemessagetracinthenetwork.Researchintherecentpasthascomparativelyfocussedverylittleonusingreplicationforincreasingperformancebuthasinsteadbeendirectedmoreatimprovingsystemavailabilitythroughreplication.However,withtheadventofmobileornomadiccomputing,researchinreplicationneedstochangedirection{theunderlyingassumptionofhighspeednetworksnolongerholdtrue.Wirelessnetworksnotonlyhavelowerbandwidthbutarealsoveryexpensivetouse.Insuchanenvironment,itisimperativethatdatabedistributedintelligentlytoachieveagoodsystemperformanceintermsofmessagecostsandturnaroundtime.Besides,withmobilityintroducedinthesystem,earlierstaticschemesforimprovingperformance(e.g.,theFileAllocationProblem[DoF82])arenolongerapplicable.Asarststep,weproposeatotallydistributeddynamicreplicationscheme,whichusesaniteautomatonbasedtechniquetolearnaccesspatterns.Thisaccruedinformationisthenusedtopredictfutureaccesssequencesanddynamicallyreorder{replicateordeletecopiesofdatainthenetwork,inanticipationofpredictedaccesses,toreducenetworkmessagecosts.Beingdistributed,eachnodeofthenetworkbasesitsdecisiontoreplicateordeleteanexistingcopysolelyonlocalinformation.Ouralgorithmisalsointegratedandcorrectssomeofthedrawbacksofearliertheoreticalworkinthisarea.Finally,wepresentsomepreliminarysimulationresultswhichshowthatourschemeisverypromising.ThisresearchwassupportedinpartbyDECResearchAgreement1139.11IntroductionReplicationofdataisanessentialcomponentofdis-tributeddatabases.Therearetwomajormotivationsforreplication{increasingavailabilityandincreasingsystemperformance.Replicationcreatesredundantinformationinthenetwork,whichallowsthesystemtoremainoperationalinspiteofnodeandlinkfail-uresandthusincreasereliability.Also,ifdataisrepli-catednearthenodewhereitisaccessed,communica-tioncostisgreatlyreduced.However,replicasincurspaceoverheadandrequirespecialeorttomaintaindataconsistency.Researchintherecentpastonreplicationhasfo-cussedmainlyontheavailabilityissue([AhA89],[JaM90],[PaL88],[KRS93],[AgE90])thoughtheper-formanceangleofreplicationhasreceivedattentionearlier([DoF82]).Improvementsintechnologyhavebeenmainlyresponsibleforsuchchangesinfocus.Whensystemsevolvedfromcentralizedtodistributedsystems,thenetworkbandwidthwasrelativelyverylow.Thatledtoafocusonreducingnetworktrans-missioncostandhenceontheperformanceissue.Butasdistributednetworksbecamecommonplaceandtechnologyimproved,communicationcostswerenolongerasimportantasothersiterelatedresourcecosts.Consequently,researchinreplicationstartedtoaddressissuesoffaulttoleranceinreplicatedsystems.Butwiththeadventofmobilenetworks,theunderly-ingassumptionofhighspeedlinkswillnolongerbetrue[AlK93].Insuchanenvironment,userswillhavetheabilitytomovefromoneplacetotheotherandyetbeconnectedtotheircomputersystemsthroughawirelesslink.Whilethegrowthinphysicalnetworkbandwidthhasbeentremendous(currenttechnologywillsupport600Mbit/sec),itisveryunlikelythatthewirelessbandwidthwillbeableachieveacompa-rablevalue.Forexample,NCR’sWaveLANachieves2Mbit/sec,atypicalbandwidthovertheair.Be-sides,datatransmissionovertheairismonetarilyex-pensivetoo[Hay92].Consequently,forsuchasystemtoachievealevelofperformancecomparabletocur-rentstaticsystems,itisverycrucialhowdatainthenetworkisdistributed.Notonlyshoulddatabedis-tributedtoreducemessageoverheadbutitmayalsohavetotakeintoaccountthemonetaryexpensesofeachoperation.Consequently,wepredictthatrepli-cationofdata{howmanyreplicastohaveandwheretoplacethem{willbeaveryimportantissueindesignofsuchsystems.Thisdoesnotimplythatavailabilityandfaulttoleranceissuesinreplicationwillbecomepassebutthatwiththeadventofno-madiccomputing,signicanceofperformanceissuesinreplicationwillgreatlyincrease.Asarststepinthedirectionofintelligentrepli-cationforbetterperformance,weproposeadynamicreplicationalgorithmforatypicaldistributednet-work.Theperformanceofadistributedsystemisverysensitivetothedistributionofdataamongthenodes.Sinceanodereadsanobject1fromthenear-estneighborhavingacopy(sometimesdependingontheprotocol,morethanonereplicamayhavetoberead),itisverycriticalthatobjectsbeasnearthenodesthatreadthem.However,anupdateisusuallydoneonmanyreplicas(dependingontheprotocolfol-lowed,updatescouldbedoneonalloramajorityorawrite-quorumsubsetofthereplicas)andthisneces-sitatescopiesbeasclosetoeachotheraspossible.Agoodreplicationschemeshouldthusbeabletocor-rectlytrade-obetweenthetwoconictingcriteriabasedontheread-writepatternoftheobject.Thealgorithmweproposeisadaptive,inte-grated[WoJ92a],onlineanddistributedinnature.It1Agenericterm{couldbeanobject,le,relati