separatestokyohotn0717

HotBlockClusteringforDiskArrayswithDynamicStriping=exploitationofaccesslocalityanditsperformanceanalysis=KazuhikoMogiMasaruKitsuregawaInstituteofIndustrialScience,TheUniversityofTokyo7-22-1,Roppongi,Minato,Tokyo106,Japan{mogi,kitsure}@tkl.
iis.
u-tokyo.
ac.
jpAbstractRAID5diskarraysprovidehighperformanceandhighreliabilityforreasonablecost.
HoweverRAID5suf-fersaperformancepenaltyduringblockupdates.
Inordertoovercomethisproblem,theuseofdynamicstripingwasproposed.
Thismethodbuffersanum-berofupdates,generatesanewstripecomposedofnewlyupdatedblocks,andthenwritesthenewfullstripebacktodisks.
Inthispaper,weexaminetheef-fectofaccesslocalityonthedynamicstripingmethod.
Tofurtherimproveperformanceinsuchanenviron-ment,weintroducethedynamicclusteringpolicyforhotblocks.
Performanceanalysiswithvariousaccesslocalitiesshowsthatthismethodhashigherperfor-mancethanordinarymethods.
Performanceisalsoexaminedforlocalitiesthatchangeovertime.
Thedynamicclusteringofhotblocksfollowslocalitytran-sitions,showingthatunderdynamicconditionsper-formanceimproves.
1IntroductionR.
ecently,duetotheprogressofsemiconductortech-nologies,microprocessorperformancehasimproveddramaticallywhilethatofsecondarystoragesystemshasnotkeptpace.
Forsecondarystorage,themaineffortshavebeendevotedtowardsincreasingcapac-ityandreducingsize,withonlyslightimprovementsinperformance.
Thishascausedtheaccessgapbe-tweenmainmemoryandsecondarystoragesystemtobecomeevenlarger.
DiskarraysystemshaveattractedPermissiontocopywithoutfeeallorpartofthismaterialisgrantedprovidedthatthecopiesarenotmadeOTdistributedfordirectcommercialadvantage,theVLDBcopyrightnoticeandthetitleofIhepublicationanditsdateappear,andnoliceisgiventhatcopyingisbypermissionofIheVeryLargeDataBaseEndowment.
Tocopyotherwise,OTtorepublish,requiresafeeand/orspecialpermissionfromtheEndowment.
Proceedingsofthe21stVLDBConferenceZiirich,Switzerland,1995strongattentionashighperformancesecondarystor-agesystems.
ARAID5diskarray[8]utilizesalargenumberofcommodityinexpensivedrivesinparalleltoachievehigherperformanceaswellasincorporatingparitydrivestoobtainhigherreliabilitywithlowstor-agecost.
RAID5whichsupportsconcurrentaccessofsmallblocksiscurrentlyregardedasoneofthemostpromisingapproachesforprovidinghighlyreliablelowcostsecondarystoragesystems.
RAID5diskarraysemployparityencodingforre-dundancy.
Sothenewparityforasmallwriteisde-rivedasfollows:Pnew=Pou&iDoudiDnew(1)Thusasingleblockupdaterequires4diskaccesses:oldblockread(D,ld),oldparityread(P,ld),newblockwrite(D,,,)dannewparitywrite(P,,,).
Thisdete-rioratesthethroughputofthewriteoperations.
Inordertoovercomethisproblemandachievehigherperformance,severalapproacheshavebeenproposed,suchasheadscheduling[lO],optimizingthestripingunit[2,31,floatingparity/data[6],smartcaching[5],paritylogging[ll],LRAID[l]anddynamicparitygrouping[131.
Toimprovetheperformanceofblockupdates,westudiedstoragemanagementmethodswhichusedy-namicstriping,whereinsteadofupdatingeachblockindependently,thismethodbuffersanumberofup-dates,generatesanewstripecomposedofthenewlyupdatedblocks,thenwritesthefullstripeontothefreearea.
Weconsideredtwoimplementationsofdynamicstriping.
OneisaLFS[S]basedmethodandtheotherisVirtualStriping[7].
Bothmethodswhichusedy-namicstripingachievemuchhigherperformancethanconventionalapproachesonrandomlyissuedaccesses.
Thedynamicstripingmethodneedstomakefreespacesfordynamicnewstripecreations.
Wecallthisactiongarbagecollection'.
Toget,higherperformance'III191,thisactioniscalledsegmentcleaning.
ButinVirt,ualStriping,wedon'tcallacontrolregionasegmentthusweusethisterm.
90fromdynamicstripingwehavetoreducethecostofgarbagecollection.
Usuallysomeblocksarefrequentlyaccessed(hotblocks)andtheothersarenon-frequentlyaccessed(coldblocks).
In[9],thecost-benefitpolicy,whichusesthisaccesslocalitytoefficientlygeneratefreeareas,wasproposedhoweveronlytheratioofex-traaccessesforthewriteoperationswasdiscussed.
Theeffectofaccessrequestscausedbyaaccesslocalityhasnotbeenclarified.
Thispaperexaminestheeffectofaccesslocalityforthedynamicstripingmethod.
Tomakeuseoftheaccesslocalitymoreeffi-cientlyforgarbagecollectionwiththedynamicstrip-ingmethod,weconsiderthedynamicclusteringofhotblocks,whichisanimprovementofthecost-benefitpolicy.
Wedivideeachdiskintotwocontinuousre-gions,ahotareaandacoldarea.
Allupdatedblocksareregardedashotblocksandcollectedintothehotarea.
Inthehotregion,morefreespaceisassignedthaninthecoldregionsothatthecostofgarbagecollectionbecomeslowerthaninthecaseofnosepa-rationbetweenhotblocksandcoldblocks.
Moreover,becausefrequentlyaccessedblocksareagatheredinalimitedarea,thismethoddecreasestheaverageseekdistance,whichimprovesreadperformance.
Weexam-inethefeasibilityofdynamicclusteringofhotblocksonvariousaccesslocalities.
Itispossiblethattheheatofblockschangesran-domly.
Themechanismofcollectinghotblocksfollowsthischange.
Wealsoexamineperformanceintheen-vironmentofhotspottransition.
Insection2wesurveythemethodswhichhavebeenproposedforimprovingtheperformanceofRAID5diskarrays.
Insection3anoutlineofthestoragemanagementschemesusingdynamicstripingarede-scribed.
Wealsoshowtheeffectofaccesslocalityforthesemanagementschemes.
Insection4thedetailsonthemethodfordynamicclusteringofhotblocksareexplained.
Extensivesimulationisdonetoiden-tifytheeffectofaccesslocalitiesandtheperformancecharacteristicsofhotblockclustering.
Section5givest,hesimulationexperiments.
Section6theresultsoftheanalysis.
2RelatedworksInthissectionwereviewthemethodswhichhavebeenproposedforimprovingtheperformanceofRAID5diskarrays.
ThemajorproblemwithusingtheRAID5diskarraysislowperformanceforsmallwriteaccesses.
Asshowninequation(l),traditionalmethodsal-waysperformtwopairsofreadmodifywriteaccessesforeachsmallwriteaccess,eachrequiringrotationaldelays.
Todecreasethesedelaysthemethodnamedfloatingparity/datamethod[6]wasproposed.
Inthismethodafixednumberoffreeblocksarereservedineachcylinder.
Oneachupdatethedatablockmovesfromitsoriginallocationtoanappropriatelocationphysicallywithinthesamecylinderinordertomini-mizerotationaldelays.
Paritylogging[ll]andLRAID[l]employdifferentapproaches.
Bothmethodsdelayparityupdatingbyrecordingupdateinformation.
Whenablockisup-dated,XOReddataoftheolddataandthenewdataarerecordedinthelogarea.
Theactionofwritingtothelogareaisperformedsequentiallysothatseekandlatencydelayscanbeeliminated.
Inparitylogging,logdisksandparitydisksaredistributedoverthear-ray,whereasLRAIDseparatesthelogandparitydisksfromthedatadisks.
Whenthelogareabecomesfull,thecontrollerreadsthelogandoldparities,calculatesnewparitiesandwritesthemouttotheproperdisks.
Theaccessesforupdatingtheparitiesrequiremainlysequentialaccesses.
Thistypeofparit,yupdatingre-quiresextradiskaccesses,butaccessefficiencyismuchhigherthantraditionalupdatemethods.
Inall,thesemethodsshowhigherperformancethannaiveR.
AID5diskarrays.
Dynamicparitygrouping[l3]overcomestheparityupdatepenaltybymaintainingsomeparityinforma-tionsinthecontroller.
Itisdesirablethatblockswhicharefrequentlyupdatedbemembersofstripeswhichhavetheirparityvaluesstoredinthecontrollerbecauseupdatingtheparitiesinthecontrollerrequiresnodiskaccess.
Butwecannotstorealloftheparitiesinthecontroller,soweneedtomigratehotblockstostripeswhoseparitiesaremaintainedinthecontroller.
Theproblembecomeshowtoselectblockswhichshouldbeallocatedtothosespecialstripes.
In[13],asortofaccessheatisusedtoguesshotblocks.
TogetfurtherperformancefromRAID5diskar-rays,wehavetoconsidertraditionalissuessuchasac-cessscheduling[lO],optimizingthestripingunit[2,31,andsmartcaching[5].
Wecancombinesuchmethodswiththeabovetechniques.
3DynamicstripingInnaiveRAID5diskarrays,whenablockisupdated,thenewparityhastoberecalculatedinordertomain-tainparityconsistency,whichrequiresreadingtheolddatablockandtheoldparityblock.
Howeverifalloftheblocksinastripearetobeupdated,thentheolddatablocksandtheparityblockswouldnotneedtobereferenced.
Thenewparitycanbederiveddi-rectlyfromthenewblocks.
Thuswecanavoidthepar-itygenerationoverheadbydynamicstripingmethod,whichallocatesanewstripedynamicallyforeverynblockupdates,wherenisthenumberofblocksinastripeexcludingparity(figure1).
Thismethodcreatesdirtyblocks,whichhaveno91ActiveHParityDiiyDFreeFigure1:Dynamicstripingvaliddatabecauseofdataupdating.
Hereweassumethatfreestripesareguaranteedtoexist,overwhichanewlygeneratedstripecanbestored.
Wecannotwritenewstripesoverdirtyblocksbecausetheseblocksarestillrequiredtomaintainparityconsistency.
Tocarryoutdynamicstriping,wemustreorganizetheparitystripestoproduceafreeareaintowhichthenewpar-itystripecanberecorded.
Thisreorganizationpro-cessiscalledgarbagecollection.
Weexaminedtwoapproacheswhichemploydynamicstriping,witheachmethodadoptingadifferentstoragemanagementandgarbagecollectionscheme.
3.
1LFSbasedstoragemanagement(LFS-SM)TheLFS(log-structuredfilesystem)wasdevelopedtoimprovethewritethroughputofthefilesystem.
WecanapplythisstoragemanagementschemetoRAID5diskarrays.
ThestoragemanagementschemebasedonLFSischaracterizedasfollows:1)Asetofsmallwriteaccessesisconvertedintoalargewrite.
2)Garbagecollectionisperformedbyalargemanagementunit(segment).
InLFS-SM,asetofsmallwritesarekeptinanon-volatilecacheforawhile.
Oncethecachefillstothecapacityofasegment,theupdatedsmallblocksarewrittenintothefreesegment.
Thisbulkupdatere-duceswriteco&s.
Updatedblocksarenotwrittenbacktotheiroriginallocationsbutintoadynamicallyallo-catedfreesegment.
LFS-SMemployssegmentbasedgarbagecollection(calledsegment,cleaningintheoriginalpaper[9]).
Thecontrollerreadsallblockswhichhavevaliddata(activeblocks)inthesegmentandcopiesthemtothenewsegment(figure2).
Thussegmentswhichincludedirtyblocksarecleanedupduringsegmentcleaning.
Cost-benefitpolicyThemethodusedtoexecutesegmentcleaningmustbecarefullyconsideredbecausetheefficiencyofthisactionhassignificantimpactonperformance.
Ifthereisaccesslocalitywhere90%oftheaccessesarecon-centratedon10%ofthedatablocks,thenabout90%Figure2:StripemanagementschemebasedonLFSofthewrittenblocksarehotblocks.
Whensegmentscontainingalotofhotblocksarecleaned,thenum-berofactiveblocksresidinginthesegmentwillbelowbecausethenumberofmodifiedblocksislarge.
Thishelpstomaketheprocessofsegmentcleaningquiteefficient.
Inthisscenario,determiningthesegmenttobecleanedisanimportantfactorforthecostofsegmentcleaningwhenthisactionisinvoked.
In[9],thecost-benefitpolicyisproposedtogethigherefficiencyofsegmentcleaningunderaccesslocality.
Inthecost-benefitpolicy,thesegmenttobecleanedisselectedbyt,hevalueofthebenefit/costmetricwhichiscalculat,edasfollows.
benefit-=freespacegenerated*age=(1-PL)*agecostcost1+u(2)Inthisequation,udenotestheutilizationoftheseg-mentandagedenotestheageoftheyoungestblockint,hesegment.
Ifageissmall,itisguessedthattherearesomehotblocksinthesegmentthusitwouldbebet-tertowaittocleanthesegment.
Inordertoefficientlydeterminewhichblocksarehotorcold,weneedtobecarefulaboutdistinguishingbetweenwriteaccessesbywriterequestsandthosebysegmentcleaning.
Almost,allblockswhicharewrittenbynormalwriteaccessesarehot,andthosewrittenbackduringsegmentclean-ingareconsideredtobecold.
3.
2VirtualStripingstoragemanagement(VS-SM)InVirtualStriping,paritystripesarevirtualizedsothatwecanchangethelinkageofblocksinapar-itystripedynamically(figure3).
ThemappingofthestripeandmemberblocksisnotdeterminedbytheirphysicalpositionbutbyatablenamedtheVirt,ualStripeTable(figure4)storedinthecontroller.
Int,heVirtualStripeTable,thestripenumber,theidentifiersofblocksinthestripe,andthenumberofdirtyblocksinthestripearerecordedforeachstripe.
Thestripe92Disk0Disk1Disk2.
aaDisknPhysicalBllcckS*peFreeStripe0ActiveBlockDirtyBlocklParityBlockFreeBlockFigure3:StripemanagementschemewithVirtualStriping.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
FreeM1***a-*nStripeFigure4:VirtualStripeTablenumberandtheblockidentifiersareusedfornormaladdressing.
Thedirtyblockcountisusedforgarbagecollection.
InVS-SM,asetofsmallwritesarekeptinanon-volatilecacheforawhileinthesamewayasinLFS-SM.
Thethresholdvalueforwritingisthesizeoffreeblocksinthecylinderwhichhasthelargestfreearea.
GarbagecollectioninVS-SMisquitedifferentfromthatofLFS-SM.
Thegarbagecollectorcollectsndirtyblocksandcreatesonefreestripebychangingthelink-ageofstripesasillustratedinfigure3.
Garbagecol-lectionisperformedintheunitofacylinderbecauseoftheaccessefficiency.
Thegarbagecollectionprocessisperformedasfollows.
1)Determinethetargetcylin-der.
2)Findthebasestripeformakingafreestripe.
Wecallthisstripethevictimstripe.
Itisdesirablethatthevictimhasfewactiveblocks.
3)Foreachitc-tiveblockinthevictim,selectastripethathasadirtyblockonthesamediskastheactiveblockofthevic-tim.
Wecallthislivestripethepartnerstripe.
4)Re-peatthesestepswhilenewvictimscanbefoundinthetargetcylinder.
5)Exchangetheactiveblocksonthevictimstripeswiththecorrespondingdirtyblocksfromthepartnerstripes.
WereferencethedirtyblockcountentriesintheVirtualStripeTabletofindthevictimstripes,andusethePhysicalBlockStateTa-ble(figure5)todeterminethestateofeachblockinordertofindthepartnerstripes.
Theexchangeprocessrequiresupdatingtheparityofthepartnerstripe.
Becauseanewparityiscal-culatedbyequation(l),weneed4accessestoup-dateparity:victimdataread(D,,,),partnerdata(Cylindel#,Blocktl)IFigure5:PhysicalBlockStateTable';;2@3.
3VS(nolocality)+LFS(nolocality)+-vs(90-10)'=.
.
Q150-LFSCost-Benefit(90-10)-*"0200400600LoadIIOdsec)Figure6:Effectofaccesslocalityread(D,ld),partneroldparityread(P,ld)andpartnernewparitywrite(P,,,).
Parityupdateisunnecessaryforthevictimstripe.
Thereasonwhythegarbagecol-lectorchoosesthelivestripewithfewactiveblocksisthatthisreducestheexchangecost.
3.
3TheimpactofaccesslocalityInthissectionweexaminetheeffect,ofaccesslo-calityontheperformanceofthedynamicstripingmethod.
WeassumethatZ%oftherequestsarecon-centratedtoy%ofthevaliddatablocks.
Wecallthisaccesslocality"z-y"later.
Wemeasuredt,heaver-agereadresponsetimewith90-10accesslocalityandwithoutaccesslocalityundertheconditionsdescribedinsection5.
Figure6showstheresults.
InLFS-SM,thecost-benefitpolicydegradesperformanceifthereisnoaccesslocality.
Thusweplottheperformancewithoutthecost-benefitpolicyinLFS-SMifthereisnoaccesslocality.
Wecangetbetterperformancewith90-10accesslocality,whichisduetotheefficiencyofgarbagecol-lection.
InLFS-SM,thecostofsegmentcleaningdecreasesbecausethecost-benefitpolicyselectsthepropersegmentforsegmentcleaning.
InVS-SM,thecostofgarbagecollectiondecreasesbecausehotblocksareconcentratedinthewrittenstripes,thisleadstothesameeffectasexplainedinthesectionont,hecost-benefitpolicy(section3.
1).
934Dynamicclusteringofhotblockscoldblocksmovedinandmovethemfromthehotarea4.
1SeparationoftheareaforhotblocksandtheareaforcoldblocksReductionofthecostofgarbagecollectionisthekeyt,ohighperformanceindynamicstriping.
Ingeneral,thereareaccesslocalitieswhichcanbeusedtoimprovet,heperformanceofRAID5diskarrayswithmethodssuchascachinganddynamicparitygrouping.
Dy-namicst,ripingisalsoabletouseaccesslocalitytoimproveperformancewiththecost-benefitpolicy.
Togatherhotblocksontoalimitedareaandtoincreaset,heamountofrecycledfreespaceduringgarbagecol-lectionarethebasicideasforthecost-benefitpolicy.
HotsegmentsinLFSarenotnecessarilyclusteredtoget,her.
Inthispaper,wepart,it,ionthespacephysi-callyintotwoareas,oneforhotblocksandoneforcoldblocks.
Ifthereareaccesslocalities,it,isdesirabletocollecthotblocksint)oacontinuousarea,whichcon-centratesthediskaccessesontoasmallarea,thusde-creasingtheaverageheadmovementdistance,whichisexpectedtoimprovetheperformanceofdiskarrays.
Thedynamicstripingmethodinherentlymovesthepo-sitionofblockswhendataareupdat,ed.
Thustheac-tionofcollectinghotblocksisquiteeasilyperformed.
Wemanagethetworegionsindependent,ly,thatis,writingnewdataandgarbagecollectionareperformedindependentlyoneacharea.
Fordynamicclusteringofhotblocks,theneedtomakefreespaceinthehotareaishigherthaninthecoldareabecausetheprobabilityofwritingtothehotareaisquitelargecomparedtothecoldarea.
Itisbettertohavealargerfreespaceratiointhehotareathaninthecoldarea,whichleadstolowgarbagecollectioncostsinthehotarea.
4.
2ThemethodofclusteringhotblocksWehavetobeabletodistinguishbetweenhotblocksandcoldblocks.
Iftheaccesslocalityisconsideredstat,icorpredictable,wecanuse"heat"[12],whichisthemeasureofthenumberofaccessesoveracertainperiod.
However,hotblocksmaychange.
Inthiscase,itisdifficulttodetermineaneffectivemethodforheatestimation.
Asdescribedabove,almost,allblockswrit-t,entobynormalwriteaccessescanbethoughtashotifthereareaccesslocalities.
Soweassumethatallblocksofnormalwriteaccessesarehotinthesamewayasthecost-benefitpolicy.
Writingallblockstothehotareaeasilyconsumesthefreespaceofthehotarea.
Whengarbagecollec-tionisexecutedonthehotarea,wehavetomovetheblockswhicharedeterminedtobecoldtothecoldarea.
Wecountthenumberofblockswhicharemovedfromthecoldareatothehotareabetweentwosuc-cessivegarbagecollectionsofthehotarea.
Thenweselectthesamenumberofblocksfromthehotareaastothecoldarea.
ThisblockmigrationisextraworkinVS-SM.
Ontheotherhand,noextraworkisrequiredinLFS-SM,sincethegarbagecollectioninLFS-SMexecutesblockmigrations.
Todeterminethecoldblocksinthehotarea,weusetheelapsedtimesincethelastaccessexecutedontheblock(whichexcludestheaccessesperformedbythegarbagecollector).
Thismethodmightcausemisesti-mation.
Twokindsofincorrectestimationcanoccur.
Ahotblockisassumedtobecoldandacoldblockisassumedtobehot.
Fromtheperformancepointofview,theformerhasastrongerinfluencethanthelat-ter.
Inordertoprevent,thisphenomena,morespaceshouldbeallocatedt,othehot,areasot,hatitdoesnotspillouthotblocks.
5SimulationExperimentsWeexaminetheperformancecharacteristicsofhotblockclust)eringthroughsimulationforeachofthedif-ferentstoragemanagementschemes(LFS-SMandVS-SM).
O.
ptimalorganizationforeachmethoddependsontheworkload.
Hereweassumetheloadsconsistofsmallaccesses,wheretheaverageaccesssizeisseveralkilobytes.
UseofcacheTheuseofawritecacheisessentialforLFS-SM.
VS-SMcanusethewrit,ecachetoimprovewriteefficiency.
Therefore,weassumet,hepresenceofawritecache.
Inthissimulationweemployacachewit,hasizeof1000blocks,whichcorrespondsto1.
5timeslargerthanthenumberofblocksinacylinderover8disksinthesimulation.
Thecacheisapart,ofthediskcontrollerforbothVS-SMandLFS-SM.
Ontheotherhand,wedon'tassumethepresenceofareadcachebecausewewanttoexaminet,herawper-formanceofthediskarrayasclearlyaspossible.
Weassumethathalfofthetotalrequestasarereadoper-ationsandtheotherhalfarewriteoperations.
Whilethewriteratiomightlookhigherthanfoundundernormalcircumstances,mostsystemstodayemployareadcache,thusreadswouldbeabsorbedbythecacheincreasingtheratioofwritesaccordingly.
Sincesim-ulationdoesnotemployareadcache,theread/writ,eratioissetto50%/50%.
AccessschedulingItisveryeffectivetoadoptaccessschedulingbecauseaccessesforwritingandgarbagecollectiontendtobelimitedt,oaverysmallarea.
Thewritingofthedynamicstripingmethodchangesthelocationofupdat,eddatatoalocationde-terminedbythecont,roller.
Thecontrollercandeter-minetheareaforgarbagecollectioninadvance.
Soinmostcasesthereissufficienttimetoscheduleaccesses.
Thisisthereasonwhyweemployaccessschedulingforthesimulation.
WeuseaSCANbasedalgorithmfor94capacity318MBcylinders/disk949tracks/cylinder14sectors/track6sectorsize4096bytesrevolutiontime13.
9msseektimemodelseek(d)=2.
0+0.
01.
d+0.
46.
4trackskew1sectorTable1:Diskmodelparametersinter-cylinderandashortesttimefirstalgorithmforintra-cylinderaccesses[7].
ExecutionofgarbagecollectionGarbagecollec-tionplaysthemostimportantroleindynamicstriping.
InourexperimentswithLFS-SM,weinvokegarbagecollectionwhenthenumberoffreesegmentsbecomeslessthan6forthehotarea,4forthecoldarea,and6ifhotblockclusteringisnotemployed.
ForVS-SM,whenthenumberofcylinderswhichhavefreestripesbecomeslessthan9ifhotblockclusteringisnotem-ployed.
Ifitisemployed,6forthehotareaand4forthecoldarea.
Successiveexecutionofgarbagecol-lectiondegradesperformance.
Ifeverydiskhassomeaccessrequestsorsomegarbagecollectionreadre-quests,westopmakinganewgarbagecollectionre-quest.
Oncesuchconditionsarefulfilled,wedeterminethetargetforgarbagecollectionandputitsrequestsontotheproperaccessqueue.
Garbagecollectionisunconditionallyperformedifthereisonlyonefreeseg-mentunderLFS-SMortherearelessthanthreecylin-derswhichhavefreestripesunderVS-SM.
OtherassumptionsWemakethefollowingas-sumptionsduringsimulation.
85%ofblocksassignedtothedataareaholdvaliddataand15%areusedasfreespace.
Accessrequestsarefixedat4KB.
Intervalbetweenaccessrequestarrivalshasanegativeexpo-nentialdistribution.
Theloadiscontrolledbychang-ingthemeantimebetweenaccessrequests.
Thatis,weassumethataccessrequestshavearandomdistri-bution.
Table1showsthediskmodelparameter,whichwasemployedin[4].
Theblocksizeis4KB.
Thestripingunitissettotheblocksize.
Thepositionofparitiesisincrementedbyonetrackwhenrotatedamongthedisks.
Thediskarrayiscomposedof8datadisksandoneparitydisk(SD+P).
InLFS-SM,thesegmentsizeissettohalfacylinder.
Thediskarraycontrollerissufficientlyfastsothattheoverheadofschedulingandtablemanipulationisnegligible.
Allthecontroltablesaremaintainedbythecontroller2.
Afterinitial2CurrentlymanycommercialRAID5productsemploydualcontrollersasdiscussedin[5].
ImportanttablesarestoredintheNV-RAMofthecontrollersandconsistencybetweenthetwocopiesismaintainedthroughappropriateimplementation.
NaiveRAID5+VSDynamicClustering(hot21%.
f=6.
0)*-Floating+-LFSDynamicClustering(hot20%,7=4.
5)*-vs-D-VSIdeal('I=6.
0)e-LFSCost-Benefit+LFSIdeal(7=4.
5)+-I600800Load~1Osk.
c)Figure7:Readresponsetimeanalysis(90-10accesslocality,8D+P,85%used)4millionaccesses,statisticscollectionbegins.
Thustheactiveblocks,thedirtyblocks,andfreeblocksareproperlydistributedoverthedisks.
6Evaluationsforthedynamiccluster-ingofhotblocks6.
1ComparisontoothermethodsFigure7showstheaveragereadresponsetimefor100,000accessrequests(50,000readrequests)for90-10accesslocality.
ThehorizontalaxisshowsthemeanarrivalratesforI/Orequests,theverticalaxisshowstheaveragereadresponsetime.
Wechangethepro-portionofthehotareaandtheratiooffreeblocksinthehotarea.
Theproportionofhotareaischangedbyincrementsof1%ofthetotalcapacity.
Theratiooffreeblocksinthehotareaarenormalizedbytheratiooffreeblocksinthecoldarea,becausewethinkthatthisvaluecorrespondstotheratioofefficiencyforgarbagecollectionbetweenthehotareaandthecoldarea.
WechangethevalueofQwhichiscalculatedaccordingtoequation(3)inincrementsofthevalueof0.
5forthevarianceoffreeblockratio.
numberoffreeblocksinthehotareav=numberofblocksinthehotareanumberoffreeblocksinthecoldarea(3)numberofblocksinthecoldareaInfigure7,weplottheperformancelineswhichwerethebest.
Thebestperformanceoccurswhenthepro-portionofthehotareais20%and7=4.
5inLFS-SMandtheproportionofthehotareais21%andq=6.
0inVS-SM.
Inordertocomparetheperformancewiththatoftheothermethods,wealsoplottheperformanceofnaiveRAID5andRAID5withfloatingparity/data&95050100150200250300ReadRewonseTime(ms)Figure8:Readresponsetimedistribution(90-10ac-cesslocality,400IOs/sec,8D+P,85%used)accessschedulinginthesamefigure.
Wealsoplottheperformanceofidealseparationofhotandcoldblocks.
Here"ideal"meansthatthecontrollerhastheperfectknowledgeaboutthehotnessoftheblocks.
Thestoragemanagementschemeswhichemploydy-namicstripinghaveamuchlargerrangeoflowre-sponsetimesthantheothertwomethods.
Inthemeth-odsusingdynamicstriping,onewithdynamiccluster-ingofhotblocksshowsashorterresponsetimeforlowloadsandcanbearhigherloadsthanonewhichdoesnotuseclustering.
Hotblockclusteringshowsclosetobutslightlyworseperformancethanwhenblocksareideallyseparated.
Atlowloads,LFS-SMwithcluster-ingshowsbetterperformancethanVS-SMwithclus-tering.
Weexaminethereasoninthenextsection.
6.
2ReadresponsetimedistributionanalysisFigure8illustratesthedistributionforthereadre-sponsetime.
Theselinesaremeasuredthroughsimu-lationat400IOs/secwith90-10accesslocalityusingthesameconditionsusedforreadresponsetimeanaly-sis.
Thehorizontalaxisshowsthereadresponsetime.
Theverticalaxisshowsthecumulativeratioforthereadaccesseswhichhaveasmallerresponsetimethanthegivenvalue.
Withclusteringofhotblocks,theratioofreadac-cesseswhichhaveshortresponsetimesishigherthanwithoutitbecauseamuchlargerfreeareaisgeneratedbythegarbagecollectionprocesswithclusteringthanwithoutitandclusteringreducesheadmovements.
InVS-SM,therearemoreaccesseswhichhavelongre-sponsetimeswithclusteringthanwithoutit.
Some,readaccesseswillhavetowaitforwriteandgarbagecollectionaccessestofinish.
Theefficiencyofgarbagecollectioninthehotareacausesthegarbagecollectionandwritetotakealongtime,whichmakesthereadVS(p=6.
0,400IOs/sec)+VS(7=6.
0.
600IOdsec)+-LFS(7=4.
5,400IOs/sec)+161820122242628ProoortionofHotAreaf%)(a)sensitivityofhotareaproportionVS(hot2I%,400IOs/sec)*VS(hot21%.
600IOs/sec)+-LFS(hot20%,4001Osk.
e~)'p--LFS(hot20%.
600IOs/sec)'K.
.
'23456789D(b)sensitivityofQFigure9:Sensitivityofparameters(90-10accesslo-cality,8D+P,85%used)responsetimeworse.
InLFS-SM,thewaitingtimeforsomereadaccessesismainlydeterminedbytheseg-mentsize.
Inthissimulation,thesegmentsizeissettohalfacylinder,whichissmallerthanVS-SM'sunit,.
ThisisthereasonwhyLFS-SMwithdynamiccluster-inghasashorterresponsetimethanVS-SMatlowloads.
6.
3SensitivityofparametersInthissection,weexaminethesensitivityoftheparameterswhenweadoptdynamicclusteringofhotblocks.
Wemeasuredthereadaverageaccessratesatthemeanrequestarrivalrateof400IOs/secand600IOs/secwith90-10accesslocalityforvariouspa-96.
2BLFSCost-Benefit+.
FVSDynamicClustering+-9!
15(-J-(hot14%,TJ=7.
5)8LFSDynamicClustering~~~~~2(hot11%.
rj=4.
0)d600800LoadflOs/sec)(a)90-5Q200.
!
z2LFSCost-Benefit.
I+.
.
d+al1502""'ELFSDynamicClusteringB(hot1l%,7=5.
0)SKI05P0'0200I400600800Load~IOs/sec)(c)95-5LFSCost-Benefit.
w0200400600800Load(IOs/sec)(b)95-10BLFSDynamicClustering+&(hot38%,'I=2.
5)I-dgb100-EOL-102ocl400600LoadUOs/sec)(d)80-20Figure10:Readresponsetimeanalysisonvariouslocalities(8D+P,85%used)rameters.
Figure9showstheresults.
Infigure9(a),wechangetheproportionratioofhotblocksleavingQfixedtothevaluesusedinfigure7.
Infigure9(b),thevalueof17ischangedatthefixedproportionratioofthehotareausedinfigure7.
Atlowloadssuchasameanarrivalrateof400IOs/sec,theresponsetimedoesnotvaryforeithermethod.
Butatameanarrivalrateof600IOs/secatwhichthebestresponsetimeisabout100msecforbothmethods,theresponsetimeissensitivetotheparameters.
Underthishighloadmanyreadaccessesmustwaituntilgarbagecollectionaccessesorwriteac-cessesfinish,thustheefficiencyofgarbagecollectionsignificantlyaffectsperformance.
Athighloads,LFS-SMismoresensitivethanVS-SM.
Althoughhighef-ficiencyhasapositiveeffect,thefrequencyofgarbagecollectionisalsoaprobleminLFS-SMbecausethecostofeachgarbagecollectionishigh.
Iftheproperparametersareset,clusteringofhotblocksshowsgoodperformanceinLFS-SM.
6.
4VarianceontheaccesslocalityInthissection,weexaminetheeffectofdifferentac-cesslocalities.
Weexaminetheaveragereadresponsetimeforvariousaccesslocalities,90-5,95-10,95-5,and80-20.
Figure10showstheresults.
Inthesefigures,weplottwolinesforeachstoragemanagement,scheme,oneshowingthebestperformanceandtheothershow-ingtheperformancewithouthotblockclustering,i.
e.
,normalVS-SMorLFS-SMwithcost-benefitpolicy.
Thehighaccesslocalityimprovestheperformancebothwithandwithouthotblockclustering.
Abetterimprovementisobtainedwithclusteringthanwith-outclustering.
Forlowaccesslocalitiessuchas80-20,VS-SMwithclusteringcannothaveashorterreadre-97LFSs2oorLFSCost-Benefit+.
VSDynamicClustering+-(hot19%.
rj=3.
5)LFSDynamicClustering+OLI0200400600Load(IOs/sec)(a)exchangeratio=l/10,90-10vsLFSCost-BenefitVSDynamicClustering(hot20%.
'I=4.
5)LFSDynamicClustering(hot19%.
7=4.
0)+.
D.
.
+-.
x.
.
400600LoadIIOs/sec)200400600LoadIIOslsec)(c)exchangeratio=l/20,90-10(d)exchangeratio=l/20,95-5LFSCost-Benefit+.
VSDynamicClustering-C-(hot12%,'74.
5)LFSDynamicClustering'*.
.
(hotlo%,7=4.
0)n'"0200400600Load(IOs/sec)(b)exchangeratio=l/10,95-5vsvsLFSCost-BenefitLFSCost-BenefitVSDynamicClusteringVSDynamicClustering(hot12%.
'I=5.
5)(hot12%.
v=5.
5)LFSDynamicClusteringLGDynamicbustekng(hot11%,7=5.
0)(hot11%,7=5.
0)y.
.
.
Figure11:Readresponsetimeanalysisonlocalitytransitions(8D+P,85%used)sponsetimeatlowloadsthanwithoutclusteringbe-causetheextraactionofcoldblockmigrationisex-pensiveinthissituation.
InLFS-SM,blockmigrationsisapartofgarbagecollectionsowecanimproveper-formanceatlowloads.
6.
5TheeffectoflocalitytransitionsItisquitepossiblethatthesetofhotblockswillchangeastimepasses.
Inthissection,weexaminethereadre-sponsetimeinanenvironmentoflocalitytransitions.
Wemodeledthetransitionoflocalityasfollows.
Thedatablocksaredividedintotwogroups,thehotgroupandthecoldgroup.
Thenumberofblocksinthehotgroupandtheaccessratioforthehotgroupisfixed,buttheexchangeofblocksbetweenthehotgroupandthecoldgroupareperformedrandomly.
Thisexchangeisexecutedbyoneblockeach.
Wesettherateoftheexchangetol/10orl/20oftheaccessratioofhotgroups,thatistosay,10and20areselectedfortheaveragenumberofaccessesinthehotgroup.
Fig-ure11showstheresults.
Inthesefigures,weplottwolinesforeachstoragemanagementscheme:thebestperformancewithhotblockclusteringandper-formancewithoutclustering.
Forlocalitytransitions,wecanimproveperformancebyusingdynamicclus-teringofhotblocks.
Butthehighprobabilityoftran-sitionsdegradesperformancebecausethetransitionofhotblocksisequivalenttothecoldblockwrites,i.
e.
,theefficiencyofgarbagecollectionisdegradedbythetransition.
ThesameeffectofblockmigrationinVS-SMasexplainedinsection6.
4isseenat90-10localityandahightransitionratioofl/10.
987ConclusionInthispaperweexaminetheimpactofaccesslocalitiesontheperformanceofthedynamicstripingmethod.
Asfarastheauthorsknow,noextensiveresearchhasnotbeendoneontheseissues.
Sincetheaccesslocalityisexpectedtobewellexploitedfordynamicstripingdiskarrays,wehavethroughlyperformedsimulationstudiestoclarifyitsviability.
Itwasshownthatiftheaccesslocalityis90-10,thedynamicstripingmethodswithhotblockclusteringhasmuchbetterperformancethanconventionalmethodssuchasnaiveRAID5andRAID5withfloatingparity/data&accessschedulingandbetterperformancethanmethodswhichdonotuseclustering.
Theclusteringofhotblocksdecreasestheaveragedistanceofheadmovement.
Thehigherratiooffreeblocksinthehotareaimprovestheef-ficiencyofgarbagecollection.
Theseeffectsleadtoashorterreadresponsetimeatlowloadsandmoretoleranceathighloads.
Thehighertheaccesslocalitybecomes,thehigherperformancebecomes.
Atlowlocalitysuchas80-20,VS-SMwithclusteringcannotimprovetheper-formanceatlowloadsbecausecoldblockmigrationscausehighoverhead.
Ontheotherhand,theclus-teringofhotblocksimprovestheperformanceofLFS-SMbecausetheactionofblockmigrationsiscombinedwithgarbagecollection.
Weexaminethesensitivityoftheoperatingparameters.
Thereislesseffectatlowloads.
Buttheparametersaffecttheperformanceathighloadsbecausetheparametersdeterminetheeffi-ciencyofgarbagecollection,whichisthemainfactorofperformanceathighloads.
Wecanalsoimprovetheperformancewithclusteringofhotblockswhenthelocalitychangesastimegoeson.
Inthiscase,theprobabilityoftransitionaffectsperformance.
Thisbe-haviorwasexamined.
Inthispaper,weintendedtoshowthefeasibilityofusingdynamicclusteringofhotblocksinvarioussit-uations.
Iftheaccesslocalitiesareknowninadvance,wecanusethepregivenknowledgetooptimizethepa-rameterssuchasthehotarearatioandtheratiooffreeblocksinthehotarea.
Thebestparametersandperformancearesomewhatsensitivetoaccesslocality,thusthebestperformancemaynotbeobtainedwhentheactualaccesslocalitydiffersfromthepredicted.
Themeansofoptimizingtheseparametersforarealenvironmentremainstobeinvestigated.
AcknowledgmentWewouldliketothanktoStephenDavisforhishelptoproofreadingthispaper.
ThisworkwassupportedbyaGrant-in-AidforScientificResearchonPriorityAreas#04235103,fromtheMinistryofEducation,ScienceandCulture,Japan.
References[l]A.
BhideandD.
Dias.
RAIDArchitecturesforOLTP.
IBMComputerScienceResearchReportRC17879(78489),March1992.
[2]P.
M.
ChenandD.
A.
Patterson.
MaximizingPerformanceinaStripedDiskArray.
InProc.
of17thAnnualInt.
Symp.
onComputerArchitec-ture(ISCA),pp.
322-331,May1990.
[3]J.
Gray,B.
Horst,andM.
Walker.
ParityStripingofDiscArrays:Low-CostReliableStoragewithAcceptableThroughput.
InProc.
of16thVLDBConf.
,pp.
148-161,August1990.
[4]M.
HollandandG.
A.
Gibson.
ParityDecluster-ingforContinuousOperationinRedundantDiskArrays.
InProc.
ofASPLOS-V,pp.
23-34,Octo-ber1992.
[5]J.
MenonandJ.
Cortney.
TheArchitectureofaFault-TolerantCachedRAIDController.
InProc.
of20thISCA,pp.
76686,1993.
[6]J.
MenonandJ.
Kasson.
MethodsforImprovedUpdatePerformanceofDiskArrays.
InProc.
of25thHawaiiInt.
Conf.
onSystemScience,vol.
I,pp.
74-83,January1992.
[7]K.
MogiandM.
Kitsuregawa.
DynamicParityStripeReorganizationsforRAID5DiskArrays.
InProc.
of3rdInt.
Conf.
onParallelandDistributedInformationSystems,pp.
17-26,September1994.
[8]D.
A.
Patterson,G.
A.
Gibson,andR.
H.
Katz.
ACaseforRedundantArraysofInexpensiveDisks(RAID).
InProc.
ofACMSIGMOD,pp.
109-116,June1988.
[9]M.
RosenblumandJ.
Ousterhout.
TheDesignandImplementationofaLog-StructuredFileSys-tem.
InProc.
of13thSymp.
onOperatingSystemsPrinciples,pp.
1-15,October1991.
[lo]M.
I.
Seltzer,P.
M.
Chen,andJ.
K.
Ousterhout.
DiskSchedulingRevisited.
InProc.
ofUSENIX,pp.
313-323,January1990.
[ll]D.
StodolskyandG.
A.
Gibson.
ParityLogging:OvercomingtheSmallWriteProbleminRedun-dantDiskArrays.
InProc.
of20thISCA,pp.
64-75,May1993.
[12]G.
Weikum,P.
Zabback,andP.
Scheuermann.
DynamicFileAllocationinDiskArrays.
InProc.
ofACMSIGMOD,pp.
406-415,May1991.
[13]P.
S.
Yu,K.
-L.
Wu,andA.
Dan.
DynamicPar-ityGroupingforEfficientParityBufferingtoIm-proveWritePerformanceofRAID-5DiskAr-rays.
IBMComputerScienceResearchReportRC19041(83137),July1993.
99