SE533007C2 - Distribuerad datalagring - Google Patents

Description

30 533 007 2 Med hjälp av en sådan metod kan varje lagringsnod vara aktiv med att underhålla data i hela systemet. I det fall att en lagringsnod faller bort kan dess data återskapas av andra noder i systemet, varför systemet kan anses vara självläkande. Övervakandet kan inkludera att avlyssna heartbeat-signaler från andra lagringsnoder i systemet. Ett tillstånd som implicerar behov av replikering kan i så fall vara en fallerande lagringsnod.

Nämnda data inkluderar filer, och ett tillstånd, som implicerar behov av replikeringar kan då vara endera av en filborttagning eller en filkonflikt.

En replikeringslista, som inkluderar filer i behov av replikering, kan underhållas och kan inkludera prioriteter.

Replikeringsprocessen kan vidare inkludera: mottagande av svar från de lagringsnoder som innehåller nämnda särskilda data, bestämning av huruvida nämnda särskilda data lagras i ett tillräckligt antal lagringsnoder, och, om så inte är fallet, val av åtminstone en ytterligare lagringsnod och sändning av nämnda särskilda data till denna lagringsnod. Vidare kan nämnda särskilda data på lagringsnoder, som innehåller föråldrade versioner därav, uppdateras.

Vidare kan replikeringsprocessen börja med att lagringsnoden försöker bli master, bland alla lagringsnoder i systemet, för den fil som ska replikeras. Övervakandet kan vidare innefatta övervakning av läsoperationer som utförs i datalagringssystemet.

Föreliggande beskrivning avser vidare en datalagringsnod för utförande av underhåll av data, vilken motsvarar metoden. Lagrlngsnoden innefattar då generellt medel för utförande av metodens steg.

Syftet uppnås även medelst en metod för skrivning av data till ett datalagringssystem av den inledningsvis nämnda typen, vilken metod åstadkommes i en server som kör en applikation som åtkommer data i datalagringssystemet. Metoden innefattar: sändning av en lP-multicast- lagringsförfrågan till ett flertal lagringsnoder, mottagning av ett flertal svar från en delmängd av nämnda lagringsnoder, varvid svaren inkluderar geografiska data avseende den geografiska positionen för varje lagringsnod, val av åtminstone två lagringsnoder i delmängden, på basis av nämnda svar, samt 10 15 20 25 30 533 00? 3 sändning av data och en dataidentifierare, som motsvarar nämnda data, till de valda lagringsnoderna.

Denna metod åstadkommer robust skrivning av data genom att geografisk diversitet åstadkommas på ett effektivt sätt.

Den geografiska positionen kan innefatta latitud och longitud för lagringsnoden i fråga, och svaren kan vidare inkludera systemlast och/eller systemàlder för lagringsnoden ifråga.

Nämnda lP-multicast-lagringsförfrågan kan inkludera en dataidentifierare, vilken identifierar de data som ska lagras.

Typiskt kan åtminstone tre noder väljas för lagring, och en lista med lagringsnoder, vilka framgångsrikt lagrar nämnda data, kan skickas till de valda lagringsnoderna.

Föreliggande beskrivning avser vidare en server, för utförande av skrivning av data, vilken motsvarar metoden. Servern innefattar då generellt medel för utförande av metodens steg.

Kort figurbeskrivning Fig 1 illustrerar ett distribuerat datalagringssystem.

Figs 2A -2C, och fig 3 illustrerar en dataläsningsprocess.

Figs 4A -4C, och fig 5 illustrerar en dataskrivningsprocess.

F ig 6 illustrerar schematiskt en situation där ett antal filer lagras hos ett antal datalagringsnoder.

F ig 7 illustrerar sändningen av heartbeat-signaler.

Fig 8 är en översikt av en dataunderhållsprocess.

Detaljerad beskrivning Föreliggande beskrivning avser ett distribuerat datalagringssystem, som innefattar ett flertal lagringsnoder. Strukturen hos systemet och det sammanhang i vilket det används är visat i fig 1.

En användares dator 1 åtkommer, via Internet 3, en applikation 5 som körs på en server 7. Användarsammanhanget, såsom det visas här, är således en vanlig client-server-konfiguration, vilken är i sig väl känd. Det skall 10 15 20 25 30 533 0D? 4 emellertid noteras att det datalagringssystem som kommer att visas även är användbart i andra konfigurationer. l det illustrerade fallet körs två applikationer 5, 9 på servern 7.

Naturligtvis kan detta antal applikationer vara ett annat. Varje applikation har ett APl (Application Programming interface) 11 som åstadkommer ett gränssnitt i förhållande till det distribuerade datalagringssystemet 13 och stödjer begäranden (requests), typiskt skriv- och läsbegäranden, från applikationer som körs på servern. Från applikationens synvinkel behöver inte läsande eller skrivande av information från/till datalagringssystemet 13 framstå såsom annorlunda än användning av vilken som helst annan typ av lagringslösning, exempelvis en filserver eller helt enkelt en hårddisk.

Varje API 11 kommunicerar med Iagringsnoder 15 i datalagrings- systemet 13, and lagringsnoderna kommunicerar med varandra. Dessa kommunikationer baseras på TCP (Transmission Control Protocol) och UDP (User Datagram Protocol). Dessa concept är väl kända för fackmannen och behöver inte förklaras vidare.

Det bör noteras att olika APl:er 11 på samma server 7 kan åtkomma olika uppsättningar Iagringsnoder 15. Det skall vidare noteras att det kan finnas mer än en server 7, som åtkommer varje lagringsnod 15. Detta påverkar emellertid inte det sätt på vilket lagringsnoderna fungerar, såsom kommer att beskrivas senare.

Det distribuerade datalagringssystemets komponenter är lagrings- noderna 15 och APl:erna 11 iden server 7 som åtkommer lagringsnoderna 15. Föreliggande beskrivning avser därför metoder som utförs i servern 7 och i lagringsnoderna 15. Dessa metoder kommer i första hand att implementeras såsom mjukvaror, som körs på server respektive lagringsnoderna och som tillsammans bestämmer hur datalagringssystemet kommer att fungera och vilka egenskaper det har.

Lagringsnoden 15 kan typiskt utföras såsom en filserver, vilken typiskt kan vara försedd med ett antal funktionella block . Lagringsnoden kan således innefatta ett lagringsmedium 17, vilket typiskt inbegriper ett antal hårddiskar, valbart konfigurerade såsom ett RAlD-(Redundant Array of 10 15 20 25 30 533 00? 5 lndependent Disk)-system. Även andra typer av lagringsmedia är emellertid tänkbara.

Lagringsnoden 15 kan vidare innefatta ett register 19, som innefattar listor av data-entitet/lagringsnod-relationer såsom en värdlista (host-list), vilken kommer att beskrivas senare.

Utöver värd-listan, innefattar varje lagringsnod vidare en nod-lista, som inkluderar IP-adresserna för alla lagringsnoder i dess uppsättning eller grupp av lagringsnoder. Antalet lagringsnoder i en grupp kan variera från ett fåtal till hundratals lagringsnoder. Nodlistan kan vidare ha ett versionsnummer.

Vidare kan lagringsnoden 15 inkludera ett replikeringsblock 21 och ett klusterövervakningsblock 23. Replikeringsblocket 21 innefattar ett lagrings- nod-API 25, och är konfigurerat att exekvera funktioner för identifiering av behovet av, och för utförande av, en replikeringsprocess, såsom kommer att beskrivas detaljerat senare. Lagringsnod-APl:et 25 i replikeringsblocket 21 kan innefatta kod som i stor utsträckning motsvarar koden i serverns 7 lagringsnod-API 11, eftersom replikeringsprocessen innefattar steg som i stor utsträckning motsvarar de steg som utförs av servern 7 under de läs- och skrivoperationer som kommer att beskrivas. Exempelvis motsvarar skriv- operationen som utförs under replikering l stor utsträckning skrivoperationen som utförs av servern 7. Klusterövervakningsblocket 23 är konfigurerat för utförande av övervakning av andra lagringsnoder i datalagringssystemet 13, såsom kommer att beskrivas mer detaljerat senare.

Det distribuerade datalagringssystemets lagringsnoder 15 kan anses befinna sig på samma hierarkiska nivå. Det finns inget behov av att utse någon master-lagringsnod, som är ansvarig för att upprätthålla ett register over lagrade dataentiteter och för övervakning av datakonflikter, etc. istället kan alla lagringsnoder 15 anses vara jämlika och kan tidvis utföra data- hanteringsoperationer vis-à-vis andra lagringsnoder i systemet. Denna jämlikhet tillförsäkrar att systemet är robust. l det fall att en lagringsnoci fallerar kommer andra noder I systemet att täcka upp för den fallerande noden och tillförsäkra tillförlitlig datalagring.

Systemets funktion kommer att beskrivas i följande ordning: läsning av data, skrivning av data och dataunderhåll. Även om dessa metoder fungerar 10 15 20 25 30 533 GCI? 6 bra tillsammans bör det noteras att de i princip kan utföras oberoende av varandra. Exempelvis ger datalagringsmetoden utmärkta egenskaper även om inte dataskrivningsmetoden används och vice versa.

Läsmetoden beskrivs nu med hänvisning till figurerna 2A-2C och 3, varav den senare är ett flödesschema som illustrerar metoden.

Läsningen, likaväl som andra funktioner i systemet, använder sig av multicast-kommunikation för att kommunicera samtidigt med ett flertal lagringsnoder. Med multicast eller lP-multicast avses här punkt-till-multipunkt- kommunikation som åstadkommes genom sändning av ett meddelande till en IP-adress som är reserverad för multicast-tillämpningar.

Exempelvis skickas ett meddelande, typiskt en begäran (request) till en sådan IP-adress (exempelvis 244.0.0.1), och ett antal mottagande servrar är registrerade såsom abonnenter för denna IP-adress. Var och en av mottagarna har sin egen lP-adress. När en switch i nätverket mottar meddelandet riktat till 244.0.0.1, vidarebefordrar switchen meddelandet till IP- adresserna för varje server som är registrerad såsom en abonnent.

I princip kan endast en server vara registrerad såsom abonnent för en multicast-adress, i vilket fall en punkt-till-punkt-kommunikation uppnås.

Emellertid anses i detta sammanhang en sådan kommunikation trots detta vara en multicast-kommunikation, eftersom en multicast-metod används.

Unicast-kommunikation används också och avser en kommunikation med en enda mottagare.

Med hänvisning till fig 2A och fig 3, innefattar metoden för inhämtning av data från ett datalagringssystem sändningen 31 av en multicast-förfrågan till ett flertal lagringsnoder 15. l det illustrerade fallet finns fem lagringsnoder som vardera har en IP-(Internet Protocol)-adress 192.168.1.1, 19216812, etc. Naturligtvis är antalet lagringsnoder bara ett exempel. Förfrågningen innefattar en dataidentifierare "2B9B4A97-76E5-499E-A21A6D7932DD7927", somexempelvis kan vara en UUlD (Universally Unique identifier), vilken är välkänd i sig.

Lagringsnoderna avsöker sig själva med avseende på data som överensstämmer med identifieraren. Om sådana data hittas sänder en lagringsnod ett svar, vilket mottas 33 av servern 7, jfr. fig 2B. Såsom visas 10 15 20 25 30 533 00? 7 kan svaret valbart innehålla ytterligare information utöver en indikation av att lagringsnoden har en kopia av relevanta data. Närmare bestämt kan svaret innehålla information från lagringsnodens register avseende andra lagrings- noder som innehåller nämnda data, information avseende vilken version av nämnda data som finns i lagringsnoden och information avseende vilken belastning lagringsnoden för närvarande är utsatt för.

På basis av svaren väljer 35 servern en eller flera lagringsnoder från vilka data skall inhämtas och sänder 37 en unicast-begäran om data till denna/dessa lagringsnoder, jfr. fig 2C.

Som svar på begäran om data sänder lagringsnoden/-noderna relevanta data med hjälp av unicast till servern, som mottar 39 nämnda data. l det illustrerade fallet väljs endast en lagringsnod. Även om detta är tillräckligt är det möjligt att välja mer än en lagringsnod i syfte att motta två upp- sättningar data, vilket möjliggör en konfliktkontroll (consistency check). Om överföringen av data misslyckas kan servern välja ännu en lagringsnod för inhämtning.

Valet av lagringsnoder kan baseras på en algoritm som tar hänsyn till åtskilliga faktorer i syfte att erhålla goda övergripande systemprestanda.

Typiskt väljs den lagringsnod som har den senaste versionen och den lägsta lasten, även om andra koncept är fullt tänkbara.

Valbart kan operationen fullbordas genom att servern sänder en lista till alla inblandade lagringsnoden vilken indikerar vilka noder som innehåller nämnda data och av vilken version. På basis av denna information kan lagringsnoderna själva underhålla data med den replikeringsprocess som kommer att beskrivas.

Figurerna 4A -4C och fig 5 illustrerar en dataskrivningsprocess för det distribuerade datalagringssystemet.

Med hänvisning till fig 4A och fig 5 innefattar metoden en server som sänder 41 en multicast-lagringsförfrågan till ett flertal lagringsnoder.

Lagringsförfrågan innefattar en identifierare och består i grunden av en fråga avseende huruvida mottagande lagringsnoder kan lagra denna fil. Valbart kan lagringsnoderna kontrollera i sina interna register huruvida de redan har en fil 10 15 20 25 30 533 DB? 8 med detta namn, och kan notifiera servern 7 vid den osannolika händelsen att så är fallet. så att servern kan döpa om filen. l vilket fall som helst kommer åtminstone en delmängd av lagrings- noderna att tillhandahålla svar via unicast-sändningar till servern 7. Typiskt svarar lagringsnoder med ett förutbestämt minsta ledigt diskutrymme på förfrågan. The servern 7 mottar 43 svaren, vilka inkluderar geografiska data avseende varje servers geografiska position. Exempelvis kan, såsom indikeras i fig 4B, nämnda geografiska data inkludera latitud, longitud och altitud för varje server. Andra typer av geografiska data kan också vara tänkbara, exempelvis postnummer eller liknande.

Utöver nämnda geografiska data kan ytterligare information tili- handahållas. som tjänar som indata till en lagringsnodvalprocess. l det visade exemplet tillhandahålles mängden fritt lagringsutrymme i varje lagringsnod, tillsammans med en indikation avseende lagringsnodens systemålder och den last som lagringsnoden för närvarande är utsatt för.

På basis av de mottagna svaren väljer 45 servern åtminstone två, i en typisk utföringsform tre, lagringsnoder i delmängden, för lagring av data. Valet av lagringsnoder utförs med hjälp av en algoritm som tar hänsyn till olika data. Selektionen utförs i syfte att åstadkomma något slags geografisk diversitet. Åtminstone bör det undvikas att endast filservrar i samma rack väljs såsom lagringsnoder. Typiskt kan en omfattande geografiskt diversitet åstadkommas även innefattande val av lagringsnoder på skiljda kontinenter.

Utöver den geografiska diversiteten kan andra parametrar inkluderas i valalgoritmen. Så länge en viss minimal geografisk diversitet åstadkommes kan ledigt lagringsutrymme, systemålder och nuvarande last också tas hänsyn till.

När lagringsnoden har valts skickas de data som ska lagras och en motsvarande dataidentifierare till varje nod, typiskt med hjälp av en unicast- sändning.

Valbart kan operationen avslutas med att varje lagringsnod, som framgångsrikt har utfört skrivoperationen, skickar en kvittenssignal till servern.

Servern skickar sedan en lista till alla lagringsnoder som är involverade, vilken indikerar vilka noder som framgångsrikt har skrivit nämnda data och 10 15 20 25 30 533 0D? 9 vilka som inte har gjort det. På basis av denna information kan lagrings- noderna själva underhålla nämnda data på ett korrekt sätt med hjälp av replikeringsprocessen som kommer att beskrivas. Om till exempel en lagringsnods skrivning misslyckats, finns ett behov av att replikera filen till en ytterligare lagringsnod i syfte att uppnå det önskade antalet lagringsnoder för den filen.

Dataskrivningsmetoden, i sig, tillåter att ett API i en server 7 lagrar data på ett mycket robust sätt, eftersom utmärkt geografisk diversitet kan åstad- kommas.

Utöver skrivnings- och läsningsoperationerna kan APl:et i servern 7 utföra operationer som raderar filer och uppdaterar filer. Dessa processer kommer att beskrivas i samband med dataunderhàllsprocessen som beskrivs _ nedan.

Syftet med dataunderhàllsprocessen är att tillförsäkra att ett rimligt antal icke-fallerande lagringsnoder vardera lagrar den senaste versionen av varje fil. Vidare kan den tillhandahålla funktionen att inga raderade filer lagras vid någon lagringsnod. Underhållet utförs av lagringsnoderna själva. Det finns således inget behov av någon utsedd "master", som tar ansvar för underhållet av datalagringen. Detta tillförsäkrar förbättrad tillförlitlighet, eftersom mastern själv annars skulle vara en svag punkt i systemet.

F ig 6 illustrerar schematiskt en situation där ett antal filer är lagrade bland ett antal datalagringsnoder. l det illustrerade fallet visas, såsom ett exempel, tolv noder, som har löpande numrerade IP-adresser från 19216811 till 192.168.1.12. Självklart behöver emellertid lP-adresserna inte alls vara i samma intervall. Varje nod lagrar en eller två filer, som för enkel- hets skull identifieras med bokstäverna A-F.

Med hänvisning till fig 8, innefattar metoden för underhåll av data detekteringen 51 av tillstånd i datalagringssystemet, vilka implicerar behovet av replikering av data mellan noderna i datalagringssystemet, samt en replikeringsprocess 53. Resultatet av detekteringsprocessen 51 är en lista 55 av filer för vilka behovet av replikering har identifierats. Listan kan vidare inkludera data avseende prioritetsordningen för olika replikeringsbehov. På basis av denna lista utförs replikeringsprocessen 53. 10 15 20 25 30 533 00? 10 Robustheten hos den distribuerade lagringen bygger på att ett rimligt antal kopior av varje fil, korrekta versioner, är lagrade i systemet. l det illustrerade fallet lagras tre kopior av varje fil. Om emellertid exempelvis lagringsnoden med adressen 19216815 skulle fallera, skulle det önskade antalet lagrade filer för "B" och "C" understigas.

En händelse som resulterar i behovet av replikering är därför att en lagringsnod i systemet slutar fungera.

Varje lagringsnod i systemet kan övervaka statusen hos andra lagringsnoder i systemet. Detta kan göras genom att låta varje lagringsnod avge en så kallad heartbeat-signal vid jämna mellanrum, såsom visas i fig 7. l det illustrerade fallet avger lagringsnoden med adress 192.168.1.7 en multicast-signal 57 till andra lagringsnoder i systemet, vilket indikerar att den fungerar korrekt. Denna signal kan mottas av alla andra fungerade lagringsnoder i systemet som utför heartbeat-övervakning 59 (cf. fig 8), eller en del av dessa. l fallet med lagringsnoden med adress 192.168.1.5 fallerar emellertid denna nod och den avger ingen heartbeat-signal. Således kommer de andra lagringsnoderna att upptäcka att ingen heartbeat-signal har avgetts av denna nod under en lång tid, vilket indikerar att lagringsnoden i fråga är nedkopplad.

Heartbeat-signalen kan, utöver lagringsnodens adress, innefatta dess nodlistversionsnummer. En annan lagringsnod, som lyssnar till heartbeat- signalen och finner att den sändande lagringsnoden har en senare version av nodlistan, kan då begära att den sändande lagringsnoden sänder sin nodlista.

Detta innebär att tilläggande eller borttagande av lagringsnoder kan åstad- kommas helt enkelt genom tilläggande eller borttagande av en lagringsnod och sändning av en ny nodlisteversion till en enda lagringsnod. Denna lagringsnod kommer sedan att spridas till alla andra lagringsnoder i systemet. Återigen med hänvisning till fig 8, söker 61 varje lagringsnod i sitt interna register efter filer som är lagrade iden fallerande lagringsnoden.

Lagringsnoder, vilka själva lagrar filerna "B" och "C" kommer att hitta den fallerande lagringsnoden och kan därför lägga till motsvarande fil på sina listor 55. 10 15 20 25 30 533 DD? 11 Detekteringsprocessen kan emelleitid även upptäcka andra tillstånd som implicerar behovet av replikering av en fil. Typiskt kan ett sådant tillstånd vara en konflikt, dvs att en eller flera lagringsnoder har en obsolet version av filen. En borttagningsoperation ger även den en replikeringsprocess, eftersom denna process kan utföra den effektiva fysiska boittagnlngen av filen.

Serverns borttagningsoperation behöver då endast tillförsäkra att lagrings- noderna sätter en borttagningsflagga för filen ifråga. Varje nod kan därför övervaka läs- och skrivoperationer som utförs i datalagringssystemet. information som tillhandahålles av servern 7 vid avslutandet av läs- respektive skrivoperationer kan indikera att en lagringsnod innehåller en obsolet version av en fil (i fallet med en läsoperation) eller att en lagringsnod inte framgångsrikt har fullföljt en skrivoperatlon. l båda fallen finns ett behov av dataunderhàll genom replikering. så att de övergripande syftena med underhållsprocessen uppfylls.

Utöver de grundläggande läs- och skrivoperationerna 63, 65, kan åtminstone två ytterligare processer tillhandahålla indikationer på att ett behov av replikering föreligger, nämligen borttagnings- 67 och uppdaterings- processerna, vilka nu kommer att ges en kort beskrivning. j Borttagningsprocessen initieras av servern 7 (jfr. fig 1). l likhet med vid läsprocessen skickar servern en förfrågan med hjälp av multicasting till alla lagringsnoder, i syfte att ta reda på vilka lagringsnoder som har data med en särskild dataidentifierare. Lagringsnoderna avsöker sig själva efter data med den relevant identifieraren, och svarar med en unicast-sändning om de har ifrågavarande data. Svaret kan inkludera en lista, från lagringsnodens register, på andra lagringsnoder som har nämnda data. Servern 7 skickar sedan en unicast-begäran, till de lagringsnoder som antas lagra filen, att filen skall raderas. Varje lagringsnod sätter en flagga med avseende på filen och indikerar att den skall raderas. Filen läggs sedan till replikeringslistan, och en bekräftelse skickas till servern. Replikeringsprocessen raderar därefter filen fysiskt, såsom kommer att beskrivas.

Uppdateringsprocessen har en sökfunktion, liknande borttagnings- processen, och en skrivfunktion, liknande den som utförs i skrivprocessen.

Servern skickar en förfrågan med hjälp av multicasting till alla lagringsnoder, i 10 15 20 25 30 533 DD? 12 syfte att ta reda på vilka lagringsnoder som har data med en särskild dataidentifierare. Lagringsnoderna avsöker sig själva efter data med den relevant identifieraren, och svarar med en unicast-sändning om de har ifrågavarande data. Svaret kan inkludera en lista, från lagringsnodens register, över andra lagringsnoder som innehåller nämnda data. Servern 7 skickar sedan en unicast-begäran, som beordrar lagringsnoderna att uppdatera nämnda data. Begäran innehåller förstås nämnda uppdaterade data. Lagringsnoderna uppdaterar nämnda data och skickar en kvittens till server, vilken svarar genom att skicka en unicast-sändning som innehåller en lista över lagringsnoderna som framgångsrikt har uppdaterat nämnda data, samt lagringsnoder som inte gjort det. Återigen kan denna lista användas av underhållsprocessen. Återigen med hänvisning till fig 8 kan läs- 63, skriv- 65, borttagnings- 67, och uppdateringsoperationerna 69 alla indikera att ett behov av replikering föreligger. Detsamma gäller för heartbeat-övervakningen 59. Den övergripande detekteringsprocessen 51 genererar således data avseende vilka filer som behöver replikering. Exempelvis kan en läs- eller uppdaterings- operation påvisa att en särskild lagringsnod innehåller en obsolet version av en fil. En borttagningsprocess kan sätta en borttagningsflagga för en särskild fil. Heartbeat-övervakningen kan påvisa att ett antal filer, vilka lagras på en fallerande lagringsnod, behöver replikeras till en ny lagringsnod.

Varje lagringsnod övervakar behovet av replikering av de filer den lagrar och upprätthåller en replikeringslista 55. Replikeringslistan 55 inne- håller således ett antal filer som behöver replikeras. Filerna kan ordnas i motsvarighet till prioriteten för varje replikering. Typiskt kan det finnas tre olika prioritetsnivåer. Den högsta nivån reserveras för filer som lagringsnoden har den sista online-kopian av. En sådan fil behöver snabbt replikeras till andra lagringsnoder, så att en rimlig redundansnivå kan uppnås. En mellannivå för prioriteten kan avse filer där versionerna inte överensstämmer bland lagringsnoderna. En lägre nivå för prioriteten kan avse filer som lagras på en fallerande lagringsnod. ' Lagringsnoden hanterar filerna på replikeringslistan 55 i enlighet med dessas prioritetsnivåer. Replikeringsprocessen beskrivs nu för en lagringsnod 10 15 20 25 30 533 00? 13 som här kallas den opererande lagringsnoden, även om alla lagringsnoder kan fungera på detta sätt.

Replikeringsdelen 53 av underhållsprocessen börjar med att den opererande lagringsnoden försöker 71 bli "master" för den fil den försöker replikera. Den opererande lagringsnoden sänder en unicast-begäran om att bli master till de andra lagringsnoder som är kända för att lagra filen i fråga.

Registret 19 (jfr. fig 1) tillhandahåller en värdlista innefattande information avseende vilka lagringsnoder som skall tillfrågas. l händelse av, exempelvis i fallet med en kolliderande begäran, att en av lagringsnoderna inte svarar jakande, flyttas filen tillbaka till listan för ögonblicket, och ett försök görs istället med nästa fil på listan. Annars anses den opererande lagringsnoden vara "master" för denna fil och de andra lagringsnoderna sätter en flagga som indikerar att den opererande lagringsnoden är "master" för filen i fråga.

Nästa steg är att hitta 73 alla kopior av filen i fråga i det distribuerade lagringssystemet. Detta kan göras genom att den opererande lagringsnoden skickar en multicast-förfrågan till alla lagringsnoder och frågar vilka av dem som har filen. Lagringsnoderna som har filen skickar svar på förfrågan, vilket svar innehåller såväl den version av filen de_har som deras värdlistor, dvs listan av lagringsnoder som har den relevanta filen och som lagras i varje lagringsnods register. Dessa värdlistor slås därefter samman 75 av den opererande lagringsnoden, så att en "master"-värdlista skapas, vilken motsvarar unionen av alla inhämtade värdlistor. Om ytterligare lagringsnoder påträffas, vilka inte blev tillfrågade när den opererande lagringsnoden gjorde försöket att bli master, kan detta steg nu återupprepas för de ytterligare lagringsnoderna. Nämnda master-värdlista innehåller information avseende vilka versioner av filen som olika lagringsnoder har och ger en bild av filens status över hela lagringssystemet.

Om den opererande lagringsnoden inte har den senaste versionen av filen i fråga, inhämtas 77 denna fil från en av de lagringsnoder som har den senaste versionen.

Den opererande lagringsnoden avgör 79 därefter huruvida värdlistan behöver ändras, typiskt om ytterligare lagringsnoder bör tilläggas. Om så är fallet kan den opererande lagringsnoden utföra en process som i mycket 10 15 20 25 30 533 007 14 liknar skrivprocessen såsom den utförs av servern och såsom beskrivs i samband med figurerna 4A-4C, och 5. Resultatet av denna process är att filen skrivs till en ny lagringsnod. l fallet med versionskonflikter kan den opererande lagringsnoden uppdatera 81 kopior av filen som lagras på andra lagringsnoder, så att alla lagrade filer har korrekt version. Överflödiga kopior av den lagrade filen kan borttas 83. Om replikeringsprocessen initieras av en borttagningsoperation kan processen hoppa direkt till detta steg. Därefter, så snart alla lagringsnoder har accepterat borttagning av filen begär helt enkelt den opererande lagrings- noden, genom att använda unicast, att alla lagringsnoder fysiskt raderar filen i fråga. Lagringsnoderna bekräftar att filen raderats.

Vidare uppdateras statusen, dvs filens master-värdlista. Därefter är det valbart möjligt att återupprepa stegen 73-83 för att tillförsäkra att behovet av replikering inte längre föreligger. Denna repetering kommer att resultera i en ensartad master-värdlista som inte behöver uppdateras i steg 85.

Därefter avslutas replikeringsprocessen för denna fil och den opererande lagringsnoden kan släppa 87 statusen såsom filens master genom att sända ett motsvarande meddelande till alla andra lagringsnoder på värdlistan.

Detta system. där varje lagringsnod tar ansvar för underhåll av alla filer den lagrar över hela uppsättningen lagringsnoder åstadkommer ett själv- reparerande (i fallet med en fallerande lagringsnod), självrensande (i fallet med filkonflikter eller filer som skall tas bort) system med utmärkt tillförlitlighet.

Det är enkelt skalbart och kan lagra filer för ett stort antal applikationer samtidigt.

Uppfinningen är inte begränsad till de särskilda visade exemplen och kan varieras och ändras på olika sätt inom omfånget för de bilagda patent- kraven.

Claims (18)

10 15 20 25 30 533 00? 1 5 PATENTKRAV

1. Metod för underhåll av data i ett datalagringssystem, vilket innefattar ett flertal datalagringsnoder, varvid metoden används i en lagringsnod i datalagringssystemet och innefattar: -övervakning av statusen (59) hos andra lagringsnoder i systemet såväl som skrivoperationer (65, 67, 69) som utförs i datalagringssystemet; -detektering (51), på basis av övervakandet, av tillstånd i datalagringssystemet som implicerar behovet av replikering av data mellan noderna i datalagringssystemet; och -initiering av en replikeringsprocess (53) i det fall att ett sådant tillstånd detekteras, varvid replikeringsprocessen inkluderar sändning av ett iP- multicast-meddelande till ett flertal lagringsnoder, vilket meddelande frågar vilka av dessa lagringsnoder som lagrar särskilda data.

2. Metod enligt krav 1, varvid övervakandet innefattar lyssnandet (59) till heartbeat-signaler från andra lagringsnoderi systemet, och varvid ett tillstånd som implicerar behovet av replikering är en fallerande lagringsnod.

3. Metod enligt krav 1 eller 2, varvid nämnda data inkluderar filer och ett tillstånd är endera av en filborttagning och en filkonflikt.

4. Metod enligt något av föregående krav, varvid en replikeringslista, som innefattar filer i behov av replikering, underhållas.

5. Metod enligt krav 4, varvid replikeringslistan inkluderar prioriteter.

6. Metod enligt något av föregående krav, varvid replikeringsprocessen vidare inkluderar: -mottagning av svar från de lagringsnoder som innehåller nämnda särskilda data; -bestämning av huruvida nämnda särskilda data lagras på ett tillräckligt antal lagringsnoder; och -om så inte är fallet, val av åtminstone en ytterligare lagringsnod och sändning av nämnda särskilda data till denna lagringsnod.

7. Metod enligt krav 6, vidare innefattande uppdatering av nämnda särskilda data på lagringsnoder som innehåller obsoleta versioner därav. 10 15 20 25 30 533 DO? 16

8. Metod enligt krav 6 eller 7, varvid replikeringsprocessen inleds med att lagringsnoden försöker bli master för filen som ska replikeras, bland alla lagringsnoder i systemet.

9. Metod enligt något av föregående krav, varvid övervakandet vidare inkluderar övervakning av läsoperationer (63) som utförs idatalagrings- systemet.

10. Datalagringsnod för underhåll av data i ett datalagringssystem. som innefattar ett flertal datalagringsnoder, vilken datalagringsnod innefattar: -medel för övervakning av statusen hos andra lagringsnoder i systemet såväl som skrivoperationer som utförs i datalagringssystemet; - medel för detektering, på basis av övervakandet, tillstånd i datalagringssystemet, vilka implicerar behovet av replikering av data mellan noderna idatalagringssystemet; och -medel för initlering av en replikeringsprocess ifall ett sådant tillstånd detekteras, varvid replikeringsprocessen inkluderar sändning av ett lP- multioast-meddelande till ett flertal lagringsnoder, vilket meddelande frågar vilka av dessa lagringsnoder som lagrar särskilda data.

11. Metod för skrivning av data till ett datalagringssystem, vilket innefattar ett flertal datalagringsnoder, vilken metod används i en server, som kör en applikation, vilken åtkommer data i datalagringssystemet, och innefattar: -sändning (41) av en lP-multicast-lagringsförfrågan till ett flertal bland lagringsnoderna; -mottagning (43) av ett flertal svar från en delmängd bland nämnda lagringsnoder, varvid svaren inkluderar geografiska data avseende varje lagringsnods geografiska position; -val (45) av åtminstone två lagringsnoder l delmängden, på basis av nämnda svar; och -sändning (47) av data och en dataidentifierare, motsvarande dessa data, till de valda lagringsnoderna.

12. Metod enligt krav 11, varvid den geografiska positionen inkluderar latituden och longituden för lagringsnoden i fråga. 10 15 20 533 00? 17

13. Metod enligt krav 12, varvid svaren vidare inkluderar systemåldern för lagringsnoden i fråga.

14. Metod enligt krav 12 eller 13, varvid svaren vidare inkluderar systemlasten för lagringsnoden i fråga.

15. Metod enligt något av krav 12-14, varvid nämnda lP-multicast- lagringsförfrågan inkluderar en dataidentifierare, som identifierar nämnda data som ska lagras.

16. Metod enligt något av krav 12-15, varvid åtminstone tre noder väljs.

17. Metod enligt något av krav 12-16, varvid en lista med lagringsnoder, vilka framgångsrikt lagrat nämnda data, skickas till de valda lagringsnoderna.

18. Server, anordnad för skrivning av data till ett datalagringssystem och innefattande ett flertal datalagringsnoder, vilken server innefattar: -medel för sändning av en lP-multicast-lagringsförfrågan till ett flertal bland nämnda lagringsnoder; -medel för mottagning av ett flertal svar från en delmängd bland nämnda lagringsnoder, varvid svaren inkluderar geografiska data avseende varje lagringsnods geografiska position; -medel för val av åtminstone två lagringsnoder i delmängden på basis av nämnda svar; och -medel för sändning av data och en dataidentifierare, som motsvarar dessa data, till den valda lagringsnoden.