SE510050C2 - Metod för insamlande av logginformation vid förändring av databas - Google Patents

Description

20 25 30 35 v - o u a nu f 510 050 _ 2 - nast nyttjade, i primärminne och resten på ett skivminne.

Eftersökt information måste i detta fall hämtas från skivminnet till primärminnet om det inte råkar vara så att den redan finns där. Den före hämtningen befintliga informationen i primärminnet skrivs då över av den nya informationen och måste hämtas på nytt om den skall användas senare. Minnesinnehàllet delas upp i sidor och sidorna hanteras oberoende av varandra.

Således kan ny information hämtas till en sida medan en annan sida förblir orörd.

I.en skivminnes-databas är normalt datastrukturen i primärmin- net en l:l mappning av strukturen i skivminnet.

Eftersom minnesinnehållet inom primärminnet på en skivminnes- databas uppdateras till skivminnet en sida i taget så är länkar mellan olika sidor är inkonsistenta vid en återstart av ett system efter ett bortfall. Konsistenta kontrollpunkter är således svåra att realisera i samband med skivminnesdatabaser.

I en primärminnes-databas är det lättare att åstadkomma konsistenta kontrollpunkter. Detta kan exempelvis enkelt realiseras genom att ha två kopior av databasen på skivminne.

En kopia ev den senaste versionen av databasen och en kopia av den äldre versionen. Detta är möjligt eftersom hela databasen finns i primärminnet på en gång och olika versioner av databasen, där man vet att konsistens råder mellan samtliga sidor enligt en viss kontrollpunkt, kan då enkelt lagras på skivminne.

Det kan i en databas förekomma att vissa attribut hörande till ett objekt är primärminnes-baserade och andra attribut inom samma objekt är skivminnes-baserade. Det kan således finnas ta- beller som utgör en blandning mellan en skivminnes-databas och en primärminnes-databas.

En databas omfattar tabeller med data som formateras på olika sätt. En tabell utgöres av ett antal kolumner där varje kolumn 10 15 20 25 30 35 n f n | r f: u 0 o n c I n v o o u non IQ' vc o u c I c c _ 3 _ innehåller information av ett visst slag. Varje kolumn till- delas ett specifikt attribut och informationen inom kolumnen har ett format enligt detta attribut.

Exempel på attribut kan vara att informationen som lagras har format såsom att det är ett heltal, med eller utan tecken, ett flyttal, ett decimaltal, ett datum, text och så vidare.

Annat som attributet bestämmer är: - om det är ett fast attribut, det vill säga om innehållet upptager en fast minnesstorlek, - om det är ett variabelt attribut, det vill säga om det kan variera i storlek, eller - om det är ett dynamiskt attribut, det vill säga om attri- butet finns med eller ej, såsom ett valbart attribut.

Ett dynamiskt attribut kan vara antingen variabelt eller fast.

Ett objekt i en tabell motsvaras av en rad i tabellen och om- fattar de attribut (kolumner) som finns i tabellen. Ett objekt kan således omfatta en blandning av olika attribut enligt ovan.

Ett exempel kan vara en tabell över personuppgifter på en grupp personer. Olika attribut kan vara för- och efternamn, gatu- adress, postadress, telefonnummer, födelsedatum och eventuella kommentarer.

Födelsedatum är ett fast attribut (om det matas in på ett för- bestämt format), namn, adress och telefonnummer är variabla attribut och kommentarer är ett dynamiskt variabelt attribut.

Ett objekt är då en person med tillhörande uppgifter.

Det finns olika sätt att lagra en tabell enligt ovanstående 10 15 20 25 30 35 5:0 050 _ 4 _ exempel. Antingen lagras den inom fasta minnesutrymmen i en konsekutiv följd inom ett minne. Detta kräver stora utrymmen som till stor del kommer att vara tomma för att kunna bereda plats för variabla och dynamiska attribut. De variabla attri- buten kommer dä även endast att vara begränsat variabla till storleken för tilldelat minnesutrymme.

Ett annat sätt är att tilldela varje objekt ett huvud som anger storleken pà de variabla attributen samt huruvida det finns dynamiska attribut eller ej, och i sà fall även storleken för dessa. Detta medför att när ett objekt skapas så allokeras det minnesutrymme som behövs för respektive attribut och dessa sammanfogas till ett objekt. Huvudet anger storleken för respektive attribut och genom detta kan informationen i objek- tet tolkas på rätt sätt. Huvudet kan även omfatta ett index med pekare till respektive attribut.

Vid den praktiska lagringen av en tabell i ett minne är det sällan som ett sammanhängande minnesutrymme finns för att lagra hela tabellen eftersom ett minne oftast är mer eller mindre fragmenterat. En tabell är även för det mesta storleksmässigt för stor för att rymmas inom en sida. Således sprids de olika objekten inom en tabell ut på en sida, och en tabell delas upp över flera olika sidor.

Ett fragment är en del av en tabell, och omfattar även det flera olika sidor. Vid distribuerade databaser kan en tabell fördelas över ett flertal processornoder i den distribuerade databasen. Ett fragment är då en del av en tabell som finns inom en nod. Ett fragment omfattar även samtliga kopior av samma del av tabellen. Således kan ett fragment omfatta en primär kopia av en del av en tabell som finns lagrad på en nod samt en sekundär kopia av samma del av samma tabell lagrad pà en annan nod. I en nod kan flera olika kopior hörande till olika fragment av samma eller olika tabeller lagras.

Vid stora objekt är det inte heller ovanligt att de olika ob- 10 15 20 25 30 35 _ 5 _ jekten måste delas upp och lagras på olika ställen inom en sida, eller till och med delas upp på olika sidor. Exempel på stora objekt kan vara där ett eller flera attribut utgöras av en textfil som kan omfatta flera tusen tecken.

Inom skivminnes-databaser är det känt att vid stora objekt an- vända avancerade datastrukturer för en tabell, och för objekten i en tabell, som bygger en träd-struktur, såsom ett B-träd.

Ett objekt delas då upp i olika delar som placeras ut i till- gängliga minnesutrymmen enligt träd-strukturen. Huvudet för respektive objekt omfattar då en pekare ner i ett B-träd vari- genom de olika delarna i objektet kan återfinnas. Delarna be- höver nödvändigtvis inte utgöra hela attribut utan objektet kan hanteras som en enda sammanhängande teckensträng och delas upp godtyckligt enligt de minnesutrymmen som finns tillgängliga.

Detta används vanligtvis när ett objekt är så stort att det täcker en hel sida och där en förändring skrivs direkt till skivminnet. Om informationen ej skrivs direkt till skivminnet krävs någon typ av logg, vilket i dessa fall med mycket stora objekt kräver mycket omfattande logg-filer.

Vid förändringar i ett fragment, såsom att lägga till eller ta bort ett objekt eller att förändra, uppdatera, ett attribut inom ett objekt, krävs det att förändringen förr eller senare lagras på ett varaktigt sätt, oavsett om det rör sig om en skivminnes-databas eller en primärminnes-databas.

Med varaktigt menas att informationen finns kvar även om exempelvis delar av, eller hela, systemet faller bort. varaktig lagring fås vid lagring på skivminnen, dock inte pà primärminnen. Att skriva till ett skivminne, och att läsa därifrån, tar tid och detta görs endast vid vissa tidpunkter.

En uppdatering av skivminnet enligt primärminnet görs med en hel sida åt gången. v 10 15 20 25 30 35 u. _ , ' I ' I I I vv I v v v v v v . v v . v v o v v v a ._ _ v v 1 vv v v v v v v a b f - v v vv v vv v vv., vvv _ 5 _ Vid ett bortfall av en processor måsta samtliga committade transaktioner genomföras och samtliga icke committade trans- aktioner avbrytas. Två typer av information lagras för att hantera detta handhavande.

REDO-information används för att kunna göra om committade för- ändringar som genomförts i primärminnet men ännu ej lagrats till skivminnet i samband med återskapandet av den information som gått förlorad vid ett bortfall av en processor.

UNDO-information används för att göra förändringar ogjorda som ännu ej var committade men som skrivits till skivminnet i sam- band med återskapandet av den information som gått förlorad vid ett bortfall av en processor.

Denna information lagras som logg-information och vanligtvis lagras en så kallad fragment-logg där samtliga förändringar som berör ett fragment lagras i en logg. Det finns olika sätt att samla in och lagra logg-information.

En fysisk logg lagrar samtliga förändringar som sker. Den arbetar på bit-nivå och lagrar hur informationen såg ut innan förändringen och efter förändringen. Den loggar samtliga för- ändringar, även en defragmentering av en fragmenterad fil eller ett fragmenterat minnesutrymme, vilket inte är en egentlig för- ändring av information utan endast en omfördelning av minnes- utrymmet. Det kan förstås att en sådan logg är mycket kapacitetskrävande både avseende minnesutrymme och processor- tid.

En fysiologisk logg lagrar endast förändringar av data inom en del av ett minnesutrymme, ej omfördelningar av minnesutrymmet.

I loggen sparas en intern adress till aktuell del, såsom ett index till ett sido-index till den aktuella delen, samt vilken förändring som skedde i delen.

En logisk logg lagrar endast en förändring av ett attribut inom 10 15 20 25 30 35 ett objekt.

Om exempelvis ett objekt med en nyckel "Kalle" och ett attribut med värdet ”l2" förändras så att det attributet ändras till "l4" lagras förenklat "Kalle" och attributen "l2" i UNDO-loggen samt "Kalle" och attributen “14" i REDO-loggen.

På detta sätt kan värdet för det attributet àterställas till "l2" genom UNDO-loggen och sättas till "l4“ genom REDO-loggen.

Denna information är inte kopplad till att objektet med nyckeln "Kalle" ligger lagrat pà en specifik position inom ett minne utan vid ett nyttjande av loggen eftersöks objektet med nyckeln "Kalle" och nödvändig korrigering utförs.

I det fall som ett objekt delats upp pà flera olika sidor krävs det att samtliga sidor laddas ner till skivminnet samtidigt för att konsistens skall råda mellan sidorna. Vid en start av nedladdning till skivminnet skapas således en kontrollpunkt, en fryst tidpunkt, och samtliga sidor inom ett fragment skrivs sedan ner till skivminnet.

Det finns två typer av konsistenta kontrollpunkter, aktions- konsistenta respektive transaktionskonsistenta kontrollpunkter.

Vid en transaktionskonsistent kontrollpunkt skall samtliga transaktioner som berör ett objekt inom ett fragment som håller på att skrivas ner till skivminnet stoppas och samtliga pågående transaktioner slutförs. Därefter genomförs själva skrivningen till skivminnet, vilken skrivning kan ta flera minuter för stora fragment. Detta medför motsvarande väntetid för stoppade transaktioner.

Motsvarande aktionskonsistenta kontrollpunkter genomförs på samma sätt med skillnaden att ett stopp tillåts mitt i en transaktion med en inväntning av slutförandet av samtliga pågående aktioner, delar av en transaktion. väntetiden i sam- band med aktionskonsistenta kontrollpunkter blir således kor- 510 ÛBÛ _ 3 _ tare än väntetiden vid transaktionskonsistenta kontrollpunkter.

Det är känt att använda något som kallas luddig kontrollpunkt (fuzzy checkpoint) i kombination med en lokal fysiologisk logg. 5 Den lokala fysiologiska loggen i samverkan med en skrivning till skivminne av samtliga sidor hörande till ett fragment möj- liggör en luddig kontrollpunkt som eliminerar väntetiderna för aktioner som berör objekt som skall skrivas till skivminne. 10 Det är även känt att, i samband med primärminnes-databaser, skapa en ny kopia av ett objekt vid en förändring av objektet, där den nya kopian innehåller objektet efter förändringen och den gamla kopia innehåller objektet före förändringen, eller 15 vice versa, med en länk mellan de två kopiorna.

Eftersom de två kopiorna omfattar både den gamla och nya infor- mationen behövs här ingen logisk UNDO-information utan endast en logisk REDO-log. Detta är svårt att använda vid skivminnes- 20 databaser eftersom det är troligt att den nya kopian hamnar på en annan sida än den gamla kopian, men det är möjligt i primärminnes-databaser eftersom dessa ofta nyttjar trans- aktionskonsistenta kontrollpunkter, vilket sällan finns inom skivminnes-databaser. 25 Begreppet plats- och kopia-oberoende logg (location and replication independent log) skall även beskrivas. Med detta menas en logg som kan nyttjas vid áterskapandet av förlorad information, i samband med ett bortfall av ett fragment eller 30 ett totalt bortfall av hela systemet, där återskapandet kan ske i en godtycklig processor och tillhörande minne (plats- oberoende) och med utgångspunkt från en godtycklig kopia, såsom primär eller sekundär kopia, av loggen (kopia-oberoende). 35 Följande publikationer beskriver handhavandet av logg-informa- tion samt olika datastrukturer. Dessa får även anses utgöra en del av känd teknik. 10 15 20 25 30 35 v :nan vv o: I I: o 4:: v | 1 | 1 n 1 o o r 0 g ”fo 050' v ' u v u o _ , _ 9 _ ”ARIES: A Transaction Recovery Method supporting Fine Granularity Looking and Partial Rollbacks using write-Ahead Logging", C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, Peter Schwarz, ACM Transactions on Database Systems, march 1992, vol. 7, no. l, p. 94.

"The Architecture of the Dali Main-Memory Storage Manager", P.

Bohannon, D. Liuwen, R. Rastogi, S. Shesadri, A. Silberschatz, S. Sudarshan,Memoranda from Lucent Technologies, http://www.bell-labs.com/project/dali/papers.html "Transaction Processing: Concepts and Techniques", J. Gray, A.

Reuter, Morgan Kaufman 1993.

"The Lorel Query Language for Semistructured Data", S.

Abiteboul, D. Quass, J. Mcfiugh, J. Widom, J. Wiener, Technical Report from Department of Computer Science, Stanford University.

"Main Memory Database Systems: An Overwiev", H. Garcia-Molina, K. Salem, IEEE Transactions on Knowledge and Data Engineering, vol. 4, no. 6, dec 1992.

“INFORMIX-OnLine Dynamic Server, Database Server", Informix Software Inc., dec 1994.

"Recovery in Parallell Database Systems", S-O. Hvasshovd, Vieweg, ISBN 3-528-05411-5.

"An Evaluation of Starburst's Memory Resident Storage Component", T.J. Lehman, E.J. Shekita, L-F. Cabrera, IEEE Transactions on Knowledge and Data Engineering, vol. 4, no. 6, dec 1992.

"System Support for Software Fault Tolerance in Highly Available Database Management Systems", M.P. Sullivan, Ph.D.

Report. 10 15 20 25 30 35 510 050 ' 0 ”fff _ 10 _ r 1 r IEKHISKI_2BQELEM Under beaktande av teknikens tidigare ståndpunkt, såsom den be- skrivits ovan, torde det fá anses vara ett tekniskt problem att kunna erbjuda metod för att hantera logg-information som erbjuder en tillförlitlig databas, där en enkel hantering av variabla och dynamiska attribut är möjlig, och vilken metod kräver en betydligt mindre mängd logg-information än vad som tidigare är känt.

Det är ett tekniskt problem att kunna erbjuda en logg som är oberoende av plats och kopia, och speciellt en metod som är lämpad för distribuerade databaser där loggen kan komma att användas för att återskapa delar av en tabell eller en hel tabell som förlorats vid bortfallet av en eller flera processornoder, eller vid ett totalt bortfall av hela systemet, och där àterskapandet kan ske i en helt annan processornod än den ursprungliga.

Det är ett tekniskt problem att erbjuda en metod som möjliggör ett insamlande av nödvändig logg-information, och ett sparande av förändringar av databasen från ett primärminne till ett skivminne, i realtid.

Det är även ett tekniskt problem att kunna erbjuda en metod som fungerar för såväl skivminnes-databaser som primärminnes- databaser.

Det är ett tekniskt problem att kunna erbjuda en metod som hanterar luddiga kontrollpunkter i kombination med en fysiolo- gisk log, där mängden logg-information som krävs kan reduceras väsentligen relativt känd teknik.

Det är ett tekniskt problem att kunna erbjuda en metod där antalet cache-missar vid sökningen av viss logg-information kan 10 15 20 25 30 35 :en H anno no nu oo u 4 I n u "... ...,.. ... r I O I O I I I I I I I .~.. M H. . .. .. . . . ._ . . . } {] .. . . .... -ll- reduceras avsevärt relativt känd teknik.

Det är ett tekniskt problem att kunna nyttja lokal logg-infor- mation som kan vara olika för olika delar av databasen för att erbjuda en lokal- och applikations-oberoende logg.

LQSHIHQEH För att kunna lösa ett eller flera av de ovan angivna tekniska problemen, och med utgångspunkt från en metod enligt den i in- ledningen beskrivna, anvisar nu föreliggande uppfinning att, för att erbjuda en möjlighet att klara sig med endast en fysiologisk UNDO-logg och en logisk REDQ-logg, den för den luddiga kontrollpunkten erforderliga logiska UNDO-informationen för vilken inte en traditionell logg skapas realiseras genom att, vid en förändring av en av delarna, där gammal data- information skall ersättas med ny data-information, en ytterligare del skapas på en av sidorna, vilken ytterligare del är strukturmässigt en kopia av den förändrade delen, och där den förändrade delen och den ytterligare delen är länkade till varandra.

Den logiska UNDO-informationen realiseras genom att den för- ändrade delen omfattar den nya data-informationen och den ytterligare delen omfattar den gamla data-informationen.

Möjligheten att upprätthålla nödvändig logg i realtid erbjuds genom att den luddiga kontrollpunkten och den fysiologiska log- gen samverkar. Denna samverkan består i att, i det fall den fysiologiska loggen utgöres av en UNDO-logg, allt som sker lokalt på en sida efter att en lokal kontrollpunkt satts och fram till dess att en skrivning av sidan till motsvarande skivminne utförts sparas i UNDO-loggen, eller i det fall den fysiologiska loggen utgöres av en fysiologisk REDO-logg, att allt som sker lokalt på en sida efter att en skrivning av sidan till motsvarande skivminne utförts och fram till dess att en lokal kontrollpunkt satts sparas i REDO-loggen. 10 15 20 25 30 35 EViO 050 _ 12 _ Det skall här nämnas att fallet med en fysiologisk REDO-logg endast fungerar i samband med rena primärminnesdatabaser, medan fallet med en fysiologisk UNDO-logg fungerar för såväl primärminnesdatabaser som skivminnesdatabaser, och således även för databaser som är kombinerade primärminnes- och skivminnes- databaser.

Med syftet att erbjuda an metod som fungerar för såväl primärminnesdatabaser som skivminnesdatabaser, och i databaser som är kombinerat primärminnes- och skivminnes-baserade, anvisar således föreliggande uppfinning att den fysiologiska loggen utgöres av en fysiologisk UNDO-logg. I den fortsatta beskrivningen nyttjas således en fysiologisk UNDO-logg.

För att spara på minnesutrymme och inte i onödan lagra onödig information tas den ytterligare kopian bort efter, eller i samband med, att den transaktion som orsakat förändringen slutförts eller committats.

I samband med att denna ytterligare kopia skapas lagras infor- mation om detta i den fysiologiska loggen. När den ytterligare kopian tagits bort, och i det fall förändringen är skriven till skivminnet, lagras information angående att den ytterligare kopian tagits bort i den fysiologiska loggen.

Föreliggande uppfinning anvisar att i det fall loggningen av förändringen ännu är oskriven till skivminnet så tas information angáende skapandet av den ytterligare kopian bort från den fysiologiska loggen i stället för ett införande av informationen om att den ytterligare kopian tagits bort. På detta sätt minskar loggens omfång i stället för att öka, vilket ytterligare minskar mängden erforderlig logg-information.

Med avsikten att förenkla inhämtandet av den information som ersätter en av de logiska loggarna, och med avsikten att där- igenom även öka möjligheten att finna eftersökt information med så få accesser av minnet som möjligt, det vill säga så få in- I r n n o n no 10 15 20 25 30 35 -13- hämtningar av information till cache-minnet som möjligt, anvisar föreliggande uppfinning att en speciell sida nyttjas för lagrandet av eventuella ytterligare kopior.

I en databas, och speciellt inom en distribuerad databas, skapas ett antal olika lokala kontrollpunkter för olika områden av databasen, exempelvis för olika tabeller eller olika fragment. Dessa olika kontrollpunkter kontrolleras lokalt inom respektive område av databasen.

En plats- och kopia-oberoende logg erhålls genom följande. En global kontrollpunkt genereras kontinuerligt och periodiskt.

Denna realiseras förenklat genom en räknare som regelbundet räknas upp. Varje transaktion tilldelas värdet för den globala kontrollpunkten vid tillfället som transaktionen i fråga committas.

En global system-kontrollpunkt är den tidpunkt som logg- informationen är lagrad till ett skivminne, vilken logg- information avser att samtliga transaktioner med en gemensam global kontrollpunkt, och samtliga transaktioner hörande till föregående globala kontrollpunkter, är committade.

Ett àterskapande av ett förlorat område, såsom ett förlorat fragment i samband med ett bortfall av en eller flera processor-noder hörande till databasen eller vid ett totalt bortfall av hela databasen, genomförs genom att återskapa området enligt den lokala logg-information som finns för om- rådet efter den senaste skapade globala system-kontrollpunkten och före den senast skapade lokala kontrollpunkten.

En metod enligt ovan erbjuder aktionskonsistenta kontrollpunk- ter i realtid, vilket i sin tur erbjuder möjligheten att skapa länkar till andra sidor, vilka länkar är tillförlitliga även vid förändringar i databasen.

Detta medför att komplicerade datastrukturer kan utnyttjas där 10 15 20 25 30 35 nu; a 510 _ 14 _ objekt med variabla och/eller dynamiska attribut på ett enkelt, tidseffektivt och minnesutrymmes-mässigt sätt kan realiseras och hanteras.

Föreliggande uppfinning anvisar speciellt möjligheten att nyttja en data-struktur som utgöres av ett B-träd, där delarna utgöres av löv-noder hörande till B-trädet.

Ytterligare en möjlig datastruktur är att låta element vara utplacerade enligt en struktur som bygger på en matematisk funktion, såsom en hash-funktion, där delarna utgöres av dessa element. u De fördelar som främst kan få anses vara kännetecknande för en metod enligt föreliggande uppfinning är att nödvändig logg-in- formation på ett effektivt och enkelt sätt är tillgänglig trots att en avancerad datastruktur används vid lagringen av objekt.

Dessutom omfattar loggen en fysiologisk UNDO-logg samt endast en logisk REDO-logg, eftersom UNDO-information erhålls genom skapandet av kopior av delar som ändras, där kopian i kombination med originalet innehåller nödvändig UNDO- information. Mängden information som krävs vid nyttjandet av den ytterligare kopian är mindre än den mängd information som krävs i en logisk UNDO-logg.

Föreliggande uppfinning erbjuder även en aktionskonsistent kontrollpunkt för såväl primärminnes-databaser som skivminnes- databaser, vilket medför att referenser mellan sidorna är till- förlitliga, som i sin tur medför en flexibel hantering av ett objekts datastruktur även på en skivminnes-databas.

Det som främst kan få anses vara kännetecknande för en metod, i enlighet med föreliggande uppfinning, anges i det efterföljande i' I O If UIlO II Ulf' . . . . . . . . . . .". : __ - I ' v r v r v c c n f q . . . .n "- .. .U - -- v f . . - - . .. . . v . . « . « . . . .. . n . f... f- 10 15 20 25 30 35 lo lol: oo o o I I I o I I I o “än o--'65n'= _ 15 _ patentkravets l kännetecknande del.

En metod, uppvisande de med föreliggande uppfinning förknippade egenheterna, skall i exemplifierande syfte nu närmare beskrivas med hänvisning till bifogad ritning, där; figur figur figur figur figur figur figur visar schematiskt en del av ett B-träd, samt kopieringen av en del av detta träd, visar schematiskt uppdelningen av ett träd enligt figur 1 på ett antal olika sidor, illustrerar två olika sätt att arbeta med en fysiologisk logg, visar förenklat en del av en fysiologisk logg, avser att illustrera samverkan mellan olika lokala kontrollpunkter och en global kontroll- punkt, visar schematiskt en alternativ struktur för ett objekt, eller en del av ett objekt, i samband med hanteringen av olika attribut, och visar schematiskt ytterligare en alternativ struktur för ett objekt, eller en del av ett ob- jekt, i samband med hanteringen av dynamiska att- ribut. u u u Enligt vad som visats utgöra teknikens tidigare ståndpunkt så I no O o o 10 15 20 25 30 35 c u f v :v _ 15 _ finns det en mängd olika sorters logg-information.

Då det i samband med distribuerade databaser finns ett stort behovet av att erhålla en plats- och kopia-oberoende logg så bygger föreliggande uppfinning på nyttjandet av en logisk logg.

En logisk logg kräver en konsistent kontrollpunkt, vilket är svårt att erhålla i samband med exempelvis skivminnes-baserade databaser. Valet av kontrollpunkt blir en aktionskonsistent kontrollpunkt eftersom denna kräver en kortare väntetid än vad en transaktionskonsistent kontrollpunkt kräver.

Det är önskvärt att upprätthålla en tillfölitlig logg i real- tid, vilket medför att inga väntetider är acceptabla, således nyttjas luddiga kontrollpunkter.

En luddig kontrollpunkt i kombination med en fysiologisk logg erbjuder en aktionskonsistent kontrollpunkt, vilket i sin tur erbjuder en möjlighet att nyttja referenser mellan olika sidor.

Detta möjliggör nyttjandet av kopior av förändrade attribut inom ett objekt där kopiorna kan läggas på vilken sida som helst, och där dessa kopior kan ersätta exempelvis den logiska UNDO-informationen.

Detta erbjuder även en möjlighet att nyttja loggen vid ett återställande efter bortfall för såväl olika objekt-strukturer som index-strukturer.

Uppfinningen bygger huvudsakligen på en kombination av tre kända saker: - att objekt, oavsett storlek, lagras i en struktur som erbjuder en uppdelning av objektet i mindre delar, - att luddiga kontrollpunkter och en fysiologisk logg används vid uppdatering av skivminnet relativt primärminnet, och r r : r : ar 10 15 20 25 30 35 _34” Inn nu n u :o 1100 rv l(rn 00 c c o o I v I c I c I z I O Il 1 0 1 x 0 n I I i u n z c z Wïšíüflóšøfi Mnm _ 17 _ - att en ytterligare del, en ny kopia av en del, skapas vid en förändring av delen i fråga, där exempelvis den ytterligare delen omfattar informationen före förändringen och den ur- sprungliga delen omfattar informationen efter förändringen, där den ursprungliga delen exempelvis utgöres av en lövnod i träd-strukturen eller ett element utplacerat genom en mate- matisk funktion, såsom en hash-funktion.

Detta gör att den logiska UNDO-loggen kan utelämnas eftersom denna ersätts av den ytterligare delen.

Vid nyttjandet av en luddig kontrollpunkt krävs en fysisk eller fysiologis logg såväl som logisk UNDO- och REDO-information för att skapa en konsistent kontrollpunkt.

Figur l avser att visa en del av ett B-träd, där en löv-nod l omfattar data-information vilken skall förändras. Den erforderliga logiska UNDO-informationen kan här realiseras genom att, vid förändringen av delen l, där den gamla data- informationen A skall ersättas med ny data-information A', en ytterligare del 1' skapas på en av databasens sidor. Denna ytterligare del 1' är strukturmässigt en kopia av den förändrade delen l. Den förändrade delen 1 och den ytterligare delen 1' är på nàgot sätt länkade 2 till varandra.

Här omfattar den förändrade delen 1 den nya data-informationen A' och den ytterligare delen l' omfattar den gamla data- informationen A.

Den nödvändiga logiska REDO-informationen lagras i en traditio- nell logisk REDO-logg.

I figur 2 visas en del av en trädstruktur enligt figur 1, där respektive delar är fördelade pà olika sidor pl, p2, ..., pn i databasen. Föreliggande uppfinning anvisar att en speciell sida pn nyttjas för lagrandet av eventuella ytterligare kopior l'. 10 15 20 25 30 35 510 _ 13 - Fördelen med detta är att: - en snabbare access av denna sida erhålls eftersom samma sida pn används om och om igen, och - en primärminnesbaserad sida används, även om aktuell del av databasen är skivminnesbaserad, vilket kräver en mindre mängd fysiologisk UNDO-information än vad som krävs vid en skivminnesbaserad sida.

Den luddiga kontrollpunkten samverkar med en fysiologisk logg, vilken utgöres av en UNDO-logg.

Figur 3 avser att visa hur denna fysiologiska logg samverkar med.uppdateringen av skivminnet i förhållande till de förändringar av data-informationen som ständigt sker i pri- märminnet. Dessa uppdateringar sker vid speciella tidpunkter tl, t2, t3, ... tering. och vid respektive tidpunkt startar en uppda- Uppdateringen kan beröra ett antal olika sidor, exempelvis alla sidor hörande till en tabell eller alla sidor hörande till ett fragment. Dessa sidor skrivs efter varandra en i taget till skivminnet. Det tar en viss tid, tl - tl', att skriva samtliga berörda sidor. I samband med varje uppdatering sätt en lokal kontrollpunkt LC.

Figur 3 visar att den lokala kontrollpunkten LC skall sättas när uppdateringen startar t. I en primärminnesdatabas sparas allt som sker lokalt på en sida efter att en lokal kontroll- punkt LC satts och fram till dess att en skrivning av sidan till motsvarande skivminne utförts, vilket sker någonstans mellan tidpunkterna t och t', i den fysiologiska UNDO-loggen.

I en skivminnesdatabas skrivs alla förändringar kontinuerligt till den fysiologiska loggen. En skivminnesdatabas kräver således avsevärt mycket mer logg-information än vad en .. . ..

. ..... . ..."W J. _ _ ...... .. . .. _ . r . .u ... .. ... . .- . , , .

. .... .. ... . U . . .. ._ . ... nu n o annan: o 10 15 20 25 30 35 - na ~ u encore o c _19- primärminnesdatabas kräver.

Oavsett om databasen utgöres av en primärminnesdatabas eller skivminnesdatabas så utgöres den totala logg-informationen som lagras av en logisk REDO-logg samt en fysiologisk UNDO-logg och den nödvändiga logiska UNDO-informationen som erhålls genom den ytterligare delen l'.

Detta är en avsevärt mindre mängd logg-information än vad som traditionellt krävs för att upprätthålla nödvändig logg-infor- mation.

Efter committ behövs inte längre den logiska UNDO-informati- onen. Detta erbjuder möjligheten att ta bort den ytterligare delen 1' efter, eller i samband med, att den transaktion som orsakat förändringen slutförs eller committas. Således erbjuds en ytterligare minskning av mängden nyttjat minnesutrymme.

Figur 4 visar att i samband med att den ytterligare delen 1' skapas lagras information 381 angående detta i den fysiologiska loggen 3. I det fall loggningen av förändringen är skriven till skivminnet innan transaktionen är committad lagras även information 3B2 angáende att den ytterligare delen l' tagits bort i den fysiologiska loggen 3.

Om däremot loggningen av förändringen fortfarande är oskriven till skivminnet anvisar föreliggande uppfinning att informationen 3Bl angáende skapandet av den ytterligare delen 1' tas bort från den fysiologiska loggen 3 i stället för att tillföra ytterligare information 3B2 om att den ytterligare delen l' är borttagen.

Detta sparar ytterligare minnesutrymme för den fysiologiska loggen 3.

Nyttjandet av en metod enligt ovan ger ett antal olika lokala kontrollpunkter för olika områden av databasen, exempelvis för 10 15 20 25 30 35 510 050 _ 20 _ en tabell eller för ett fragment. Figur 5 illustrerar hur res- pektive område har olika lokala kontrollpunkter LCI, LC2, LC3, ..., LCn, där de olika kontrollpunkterna kontrolleras lokalt i respektive område.

En plats- och kopia-oberoende logg erhålls genom följande. En global kontrollpunkt GC genereras kontinuerligt och periodiskt GCI, GC2, GC3, ... räknare som regelbundet räknas upp. Varje transaktion tilldelas värdet för den globala kontrollpunkten GC vid tillfället som transaktionen i fråga committas.

. Denna realiseras förenklat genom en En global system-kontrollpunkt GSCI, GSC2, GSC3, ... är den tidpunkt som en specifik logg-information är lagrad till ett skivminne, vilken logg-information avser att samtliga transaktioner med en gemensam global kontrollpunkt GC, och samtliga transaktioner hörande till föregående globala kontrollpunkter, är committade.

Ett återskapande av ett förlorat område, såsom ett förlorat fragment i samband med ett bortfall av en eller flera processor-noder hörande till databasen eller vid ett totalt bortfall av hela databasen, genomförs genom att återskapa området enligt den lokala logg-information LC som finns för om- rådet efter den senaste skapade globala system-kontrollpunkten GSC och före den senast skapade lokala kontrollpunkten LC.

Logg-informationen kan då nyttjas globalt, exempelvis vid åter- skapande av ett lokalt förlorat område, såsom ett förlorat fragment i samband med ett bortfall av en eller flera proces- sor-noder hörande till databasen, genom att det lokala området áterskapas enligt den lokala logg-information som finns för området efter den senaste skapade globala system- kontrollpunkten GSC och före den senast skapade lokala kontrollpunkten LC.

Den data-struktur som nyttjas kan lämpligen utgöras av ett B- 10 15 20 25 30 35 510 050 _ 21 _ träd, där delarna utgöres av löv-noder hörande till B-trädet, eller av en struktur som bygger på en utplacering av element enligt en matematisk funktion, såsom en hash-funktion, där delarna utgöres aven element, eller delar av elementen.

Föreliggande uppfinning erbjuder även en möjlighet att nyttja de uppfinningar som beskrivs i de svenska patentansökningarna med ansökningsnummer 97 02760-l “Metod för att lagra element i en databas" samt 97 02761-9 "Struktur vid databas", i såväl primärminnes-databaser som skivminnes-databaser. Dessa ansökningar kan även anses utgöra en del av denna ansökan.

Kombinationen av tillförlitliga länkar mellan olika sidor och en avancerad datastruktur, som exempelvis B-träd-strukturen, erbjuder en enkel och flexibel hantering av variabla och dyna- miska attribut. Även för en uppdelning av fasta attribut, oav- sett storleken pà attributen, erbjuds genom ovanstående kombi- nation.

Uppdelningen av attributen i en träd-struktur gör även att löv- noderna blir anpassat små varigenom den del som behöver kopieras i samband med förändringar blir lika liten som mot- svarande lövnod.

Ett attribut kan tilldelas en struktur enligt figur 6. Ett huvud hörande till ett objekt omfattar då den information som utgör en rot-nod Al i B-trädet. Rot-noden Al pekar vidare mot mellanliggande noder Bl, B2 eller direkt till en löv-nod Cl. De mellanliggande noderna Bl, B2 pekar i sin tur mot ytterligare mellanliggande noder B3 eller mot en löv-nod C2, C3, C4, C5, C6.

Löv-noden Cl, C2, C3, C4, C5, C6 kan vara anpassat stor för att omfatta ett attribut. Detta erbjuder en enkel hantering av variabla attribut, det vill säga attribut som kan variera i storlek frän objekt till objekt inom en tabell. Löv-noden Cl, C2, C3, C4, C5, C6 kan även vara anpassat stor för att rymmas f' 10 15 20 o o u ø on 0.... 51Ü ÜÉSÜ _22- inom ett tillgängligt minnesutrymme. Detta erbjuder en flexibel och effektiv minneshantering.

Figur 7 avser att visa hur dynamiska attribut kan hanteras. Ett objekthuvud Dl pekar D12 på ett register D2 över olika dyna- miska attribut. Olika positioner D21, D22, registret D2 pekar vidare mot befintliga dynamiska attribut D3.

..., D2n inom Om ett attribut inte finns för ett specifikt objekt existerar inte motsvarande pekare D12 i huvudet D1.

Det dynamiska attributet D3 kan i sin tur utgöras av ett variabelt attribut, vilket kan delas upp i en trädstruktur enligt figur 6.

Denna beskrivning skall inte betungas med en mer detaljerad förklaring av strukturen för variabla och dynamiska attribut.

Denna information finns att finna i avhandlingen "Design and Modelling of a Parallell Data Server for Telecom Applications", Ericsson Utvecklings AB, Mikael Ronström, 1997.

Uppfinningen är givetvis inte begränsad till den ovan såsom exempel angivna utföringsformen utan kan genomgå modifikationer inom ramen för uppfinningstanken illustrerad i efterföljande patentkrav.

Claims (10)

10 15 20 25 30 35 v vvv o o vc :vn v v v o v c o v v v ._ v v v v o o v v vv vvvv vv v v v v v v v v v v v f III II III f ll I O C l I v v vv v v v v v v v1- fivÛv vvvv :vv v v _ 23 _ BBIENKBBI

1. l. Metod vid databas, avsedd att erbjuda ett tillförlitligt insamlande av logg-information i samband med förändringar av nämnda databas, där luddiga kontrollpunkter nyttjas med syftet att erbjuda en möjlighet att minska de väntetider som normalt uppkommer vid konsistenta kontrollpunkter, där nämnda luddiga kontrollpunkt kombineras med en fysiologisk logg med syftet att erbjuda en möjlighet att insamla logg-information i realtid, och där data-information hörande till nämnda databas är uppdelad i mindre delar enligt en förbestämd data-struktur, där respektive delar är fördelade på gemensamma eller olika sidor hörande till nämnda databas, att för nämnda luddiga kontrollpunkt erforderlig logisk UNDO- information realiseras genom att, vid en förändring av en av nämnda delar, där gammal data-information skall ersättas med ny k ä n n e t e c k n a d därav, data-information, en ytterligare del skapas på en av nämnda sidor, att nämnda ytterligare del är strukturmässigt är en kopia av nämnda förändrade del, att nämnda förändrade del och nämnda ytterligare del på något sätt är länkade till varandra, att nämnda förändrade del omfattar nämnda nya data-information och att nämnda ytterligare del omfattar nämnda gamla data- information, eller vice versa.

2. Metod enligt patentkravet 1, k ä n n e t e c k n a d därav, att nämnda luddiga kontrollpunkt och nämnda fysiologiska logg samverkar genom att nämnda fysiologiska logg utgöres av en UNDO-1099, att allt som sker lokalt pà en sida efter att en lokal kontrollpunkt satts och fram till dess att en skrivning av nämnda sida till motsvarande skivminne utförts sparas i nämnda UNDO-logg, eller att nämnda fysiologiska logg utgöres av en fysiologisk REDO-logg, och att allt som sker lokalt pà en sida efter att en skrivning av nämnda sida till motsvarande skivminne utförts och fram till dess att en lokal kontrollpunkt satts sparas i nämnda REDO-logg.

3. Metod enligt patentkravet 2, k ä n n e t e c k n a d 10 15 20 25 30 35 I «a- ,,, ._ « v' v o - q o o "f .' . < v . a o a u o u n . u f- ." nu wo :av u n v v o . . . i' v o vv u | v . a , . I 0 v n n o. n nu av: _ 24 _ 510 därav, att nämnda ytterligare kopia tas bort efter, eller i samband med, att den transaktion som orsakat nämnda förändring slutförs eller committas.

4. Metod enligt patentkravet 3, där information angáende att nämnda ytterligare kopia skapats är lagrad i nämnda fysiologi- ska logg, och där nämnda ytterligare kopia tagits bort, k ä n n e t e c k n a d därav, att, i det fall den fysiologiska loggen för nämnda förändring är skriven till nämnda skivminne, information angáende att nämnda ytterligare kopia tagits bort lagras i nämnda fysiologiska logg, och att, i det fall den fysiologiska loggen för nämnda förändring ännu är oskriven till nämnda skivminne, nämnda information angáende skapandet av nämnda ytterligare kopia tas bort fràn nämnda fysiologiska logg.

5. k ä n n e t e c k n a d därav, att nämnda fysiologiska logg utgöres av en fysiologisk UNDO-logg. Metod enligt patentkravet 4,

6. k ä n n e t e c k n a d därav, att en speciell sida nyttjas för lagrandet av eventuella Metod enligt patentkravet l, ytterligare kopior.

7. k ä n n e t e c k n a d därav, att nämnda speciella sida utgöres av en Metod enligt patentkravet 6, primärminnesbaserad sida.

8. punkter skapas för olika områden av nämnda databas, exempelvis för en tabell eller för ett fragment, där de olika kontroll- punkterna kontrolleras lokalt i nämnda område av nämnda data- Metod enligt patentkravet 1, där olika lokala kontroll- bas, k ä n n e t e c k n a d därav, att en plats- och kopia- oberoende logg erhålls genom att en global kontrollpunkt gene- reras vid specifika tidpunkter, att globala system- kontrollpunkter skapas utifrån nämnda globala kontrollpunkter, och att ett àterskapande av ett förlorat område, såsom ett för- 10 15 V l ' 0 II c a g . oc: : o o q g y ' v ne _ 25 _ lorat fragment i samband med ett bortfall av en eller flera processor-noder hörande till nämnda databas, genomförs genom att återskapa nämnda område enligt den lokala logg-information som finns för nämnda område efter den senaste skapade globala system-kontrollpunkten och före den senast skapade lokala kon- trollpunkten.

9. Metod enligt patentkravet 1, k ä n n e t e c k n a d därav, att nämnda data-struktur utgöres av ett B-träd, och att nämnda delar utgöres av löv-noder hörande till nämnda B-träd.

10. Metod enligt patentkravet l, k ä n n e t e c k n a d därav, att nämnda data-struktur utgöres av element utplacerade enligt en struktur som bygger på en matematisk funktion, såsom en hash-funktion, och att nämnda delar utgöres av nämnda element, eller delar av nämnda element.