On the modeling and performance characteristics of

measurements-basedapproachthatleadstoalocatemodelfortheDLT4000.Thismodelsupportseectivescheduling.Withoutscheduling,theDLT4000executesabout50randomretrievalsperhourfromonetape.TheLOSSscheduledescribedinthispapercanimprovetheretrievalratetonearly400perhourforlengthysched-ules.Thisisfarfromthe200,000to400,000randomI/O’sperhourservedbyamagneticdisk,butstillrep-resentsanorderofmagnitudeimprovement.Weplantocontinueourworktobridgethegapbetweendiskandtapetofurtherexpandthenumberofapplicationsthatcanexploitthecost-andvolumetric-eciencyoftape.References[1]ProceedingsoftheTwelfthIEEESymposiumonMassStorageSystems(Monterey,CA,Apr.26{291993).[2]Carey,M.J.,Haas,L.M.,andLivny,M.Tapesholddata,too:challengesoftuplesontertiarystore.InProceedingsSIGMODInternationalConferenceonManagementofData(Washington,DC,May26{281993),pp.413{417.[3]Coyne,R.A.,andHulen,H.Anintroductiontothemassstoragesystemreferencemodel,version5.InProceedingsoftheTwelfthIEEESymposiumonMassStorageSystems[1],pp.47{53.[4]Drapeau,A.L.,andKatz,R.H.Stripedtapear-rays.InProceedingsoftheTwelfthIEEESymposiumonMassStorageSystems[1],pp.257{265.[5]ExabyteCorporation.SCSIReference:EXB-8205andEXB-85058mmCartridgeTapeSubsystemsforStandardandeXtendedLength(XL)Congurations,510503-004.168538thSt.,Boulder,CO,May1994.[6]Federighi,C.,andRowe,L.A.Adistributedhi-erarchicalstoragemanagerforavideo-on-demandsys-tem.InProceedingsStorageandRetrievalforImageandVideoDatabasesII(SanJose,CA,Feb.7{81994),no.2185inProceedingsSeries,SPIE,pp.185{197.[7]Golubchik,L.,Muntz,R.R.,andWatson,R.W.Analysisofstripingtechniquesinroboticstorageli-braries.InProceedingsoftheFourteenthIEEESym-posiumonMassStorageSystems(Monterey,CA,Sept.11{141995),pp.225{238.[8]Hillyer,B.K.,andSilberschatz,A.RandomI/Oschedulinginonlinetertiarystoragesystems.InPro-ceedingsofthe1996ACMSIGMODInternationalCon-ferenceonManagementofData(Montreal,Canada,June3{61996),pp.195{204.[9]Katz,R.H.,Anderson,T.E.,Ousterhout,J.K.,andPatterson,D.A.Robo-linestorage:lowlatency,highcapacitystoragesystemsovergeographicallydis-tributednetworks.Tech.Rep.Sequoia2000Techni-calReportS2K-91-3,UniversityofCalifornia,Berkeley,Oct.1991.[10]Keeton,K.,Drapeau,A.,Patterson,D.,andKatz,R.H.Storagealternativesforvideoservice.InProceedingsoftheThirteenthIEEESymposiumonMassStorageSystems(Annecy,France,June12{161994),pp.100{105.[11]Kohl,J.,Stonebraker,M.,andStaelin,C.High-Light:alesystemfortertiarystorage.InProceedingsoftheTwelfthIEEESymposiumonMassStorageSys-tems[1],pp.157{161.[12]Kollias,J.G.,Manolopoulos,Y.,andPapadim-itriou,C.H.Theoptimumexecutionorderofqueriesinlinearstorage.InformationProcessingLetters36,3(Nov.11990),141{145.[13]Lawler,E.L.,Lenstra,J.K.,Kan,A.H.G.R.,andShmoys,D.B.TheTravelingSalesmanProblem.Wiley,Chichester,1985.[14]Myllymaki,J.,andLivny,M.Disk-tapejoins:syn-chronizingdiskandtapeaccess.InProceedingsofthe1995ACMSigmetricsConferenceonMeasurementandModelingofComputerSystems(Ottawa,Canada,May15{191995),pp.279{290.[15]QuantumCorporation.QuantumDLT4000/DLT4500/DLT4700STapeMini-LibraryProductManual,81-108336-01.715SycamoreAve.,Milpitas,CA95035,1995.[16]Sarawagi,S.Queryprocessingintertiarymemorydatabases.InProceedingsofthe21stInternationalCon-ferenceonVeryLargeDatabases(Zurich,Switzerland,Sept.11{151995),pp.585{596.[17]Sarawagi,S.,andStonebraker,M.Executionre-orderingintertiarymemorydatabases.(inprogress,~sunita/).[18]Silberschatz,A.,Stonebraker,M.,andUllman,J.Databasesystems:achievementsandopportunities.CommunicationsoftheACM34,10(Oct.1991),110{120.[19]Wong,C.K.Minimizingexpectedheadmovementinone-dimensionalandtwo-dimensionalmassstoragesystems.ACMComputingSurveys12,2(June1980),167{178.estimate,asitincludestheoverheadofrandomnumbergenerationandstatisticscalculation.Thetimerequiredtogenerateascheduleislessthan0.6sforupto256re-quests,2.3sfor512requests,8.1sfor1024requests,and17.8sfor1536requests.Formorethan1536requestsschedulingisnoteective:itisfastertoreadtheentiretape,whichtakesslightlylessthan4hours.AspreviouslydescribedinSection3.3,theagree-mentbetweentheDLT4000locate-timemodelandmea-suredlocatetimesisreasonablygood.Itremainstobedeterminedwhetherthisimpliesthatthesimulatedexe-cutiontimeofascheduleisagoodapproximationoftheactualexecutiontimeofthisscheduleontheDLT4000.Toassessthis,theestimatedandmeasuredexecutiontimesarecomparedfor4trialsateachschedulesize.Theresultisthatthesimulationisveryaccurateforschedulesoffewerthan384requests,typicallywithanerrorconsiderablylessthan1%.Withlargeschedulestheerrorincreasestoasmuchas5%,whichisstillsuf-cientlyaccuratetobeuseful.Thereasonforthede-creasingaccuracywithincreasingschedulelengthisthatascheduleofmanyrequestscontainsnumerousshortlo-catesnearthetrackends,andthisregionofthelocate-timemodelislessaccurate.(SeeSection3.3).Toassesshowsensitivethesimulatedscheduleex-ecutiontimeistoerrorsinthelocate-timemodel,oneexperimentinvestigateshowtheestimatesdeterioratewhenthekeypointsofatapearedeterminedinaccu-rately,andanotherexperimentexplorestheimpactofinaccuraciesinthelocate-timemodeli