PatentDe  


Dokumentenidentifikation DE102004018808B3 29.12.2005
Titel Verfahren und Anordnung zur Verteilung von Datenblockmengen in Speichernetzwerken und/oder einem Datennetz sowie Computerprogramm-Erzeugnis und computerlesbares Speichermedium
Anmelder CONET AG, 53773 Hennef, DE
Erfinder Brinkmann, André, 33758 Schloß Holte-Stukenbrock, DE;
Scheideler, Christian, Prof. Dr., 33102 Paderborn, DE;
Meyer auf der Heide, Friedhelm, Prof. Dr., 33129 Delbrück, DE;
Rückert, Ulrich, Prof. Dr., 59494 Soest, DE
Vertreter Anwaltskanzlei Gulde Hengelhaupt Ziebig & Schneider, 10179 Berlin
DE-Anmeldedatum 15.04.2004
DE-Aktenzeichen 102004018808
Veröffentlichungstag der Patenterteilung 29.12.2005
Veröffentlichungstag im Patentblatt 29.12.2005
IPC-Hauptklasse G06F 12/16
Zusammenfassung Die Erfindung betrifft ein Verfahren zur Verteilung von Datenblöcken über Datenspeichersysteme in Computersystemen und/oder Speichernetzwerken und/oder einem Datennetz, vorzugsweise einem Intranet und/oder dem Internet, bei dem eine Menge von Datenblockmengen Di (i = 1, ..., m), die jeweils aus maximal s Datenblöcken bestehen, die nicht auf dasselbe Datenspeichersystem abgebildet werden dürfen, einer Menge von Datenspeichersystemen Sj (j = 1, ..., n) gemäß den folgenden Schritten zugeordnet und dort gespeichert wird: Zuerst wird der Gesamtmenge der Datenspeichersysteme ein virtueller Speicherraum zugeordnet, anschließend die einzelnen Partitionen der Datenspeichersysteme in Gruppen eingeteilt, wobei jede Partition maximal einer Gruppe zugeordnete wird und alle Partitionen eines Datenspeichersystems der gleichen Gruppe zugeordnet werden. Daran schließt sich ein Verfahren zur Lösung des Optimierungsproblems, die Datenblöcke derart über die Datenspeichersysteme zu verteilen, dass die genutzte Kapazität der Datenspeichersysteme maximiert wird. Dieses wird zu Beginn und dann nur bei Änderungen der Konfiguration der Datenspeichersysteme durchgeführt. Online wird dann laufend zur Speicherung der Daten ein Verfahren durchgeführt, das mithilfe der Ergebnisse aus Optimierungsschritt Datenblockmengen einer Menge von Gruppen zuordnet, sowie ein Verfahren, mit dem Datenblöcke über eine Gruppe verteilt werden.

Beschreibung[de]

Die Erfindung betrifft ein Verfahren und Anordnungen zur Verteilung von Datenblockmengen in Speichernetzwerken und/oder einem Datennetz gemäß Oberbegriff eines der Ansprüche 1 bzw. 18 sowie ein entsprechendes Computerprogrammprodukt gemäß Oberbegriff des Anspruches 26 und ein entsprechendes computerlesbares Speichermedium gemäß Oberbegriff des Anspruches 27, welche insbesondere einsetzbar sind für die Verteilung und das Wiederauffinden von Daten in fehlertoleranten sowie fehlerbehafteten Systemen, wie beispielsweise Speichernetzwerken oder einem Datennetz wie etwa einem Intranet oder dem Internet.

Im Rahmen der Beschreibung wird im Folgenden zwischen einer Menge von auf die Datenblöcke zugreifenden Einheiten, den sog. Clients, und einer Menge von Einheiten, die Datenblöcke ausliefert, den sog. Servern, unterschieden. Die Begriffe Server und Datenspeichersystem werden dabei synonym verwendet.

Die Organisation von mehreren Datenspeichersystemen als effizientes und flexibles Speichersystem erfordert die Lösung zahlreicher Aufgaben. Eine der wichtigsten ist es, eine geeignete Datenplatzierung, d. h. eine geeignete Strategie zur Verteilung der Datenblöcke über das Speichersystem zu finden, die einen schnellen Zugriff auf die Daten und eine hohe Sicherheit gegen Datenverlust erlaubt. Diese Aufgabe wird deutlich komplexer, wenn bei der Kodierung der Daten und ihrer Verteilung eine Sicherung gegen den Ausfall einzelner Datenspeichersysteme durchgeführt werden muss. Ein bekanntes Verfahren zur Sicherung der Daten gegen den Ausfall einzelner Speichersysteme besteht in der Hinzufügung von redundanten Informationen.

Die im Folgenden betrachteten Verfahren und Systeme zum Aufbau effizienter und flexibler Speichersysteme dienen unter anderem zum Aufbau von verteilten Datenservern und Speichernetzwerken sowie zum Aufbau von Web-Systemen zum sog. Caching von Daten. Ein verteilter Datenserver, bzw. ein Speichernetzwerk, besteht im Allgemeinen aus einer Menge von Computersystemen, die über ein Netzwerk mit einer Menge von Datenspeichersystemen verbunden sind. Das Verbindungsnetzwerk zwischen den Computersystemen und den Datenspeichersystemen besteht aus einer Menge von Übertragungsstationen, sog. Switches bzw. Routern, die eine Zustellung der Datenpakete zwischen kommunizierenden Einheiten sicherstellen (siehe 1). Weiterhin kann das System über eine Menge von sog. SAN-Appliances (SAN = Storage Area Network) verfügen, die an das Netzwerk angekoppelt sein können und eine Koordination zwischen den einzelnen Computersystemen und den Datenspeichersystemen sicherstellen (siehe 2). Weiterhin können so genannte In-Band-Appliances zwischen die Computersysteme und die Datenspeichersysteme geschaltet werden (siehe 3). In-Band-Appliances finden bei der so genannten In-Band-Virtualisierung Verwendung. Bei der In-Band-Virtualisierung befindet sich die Kontrollinstanz, die In-Band-Appliance, im Datenstrom zwischen Server und Speicher. Die Steuerdaten wie auch die Nutzdaten laufen durch die In-Band-Appliance, die den Clients als das Speichersystem selbst erscheint. Die Zuordnung von Speichersegmenten, auch als sog. logische Volumes bezeichnet, zu jedem einzelnen Server geschieht hier. Ebenso wird die Steuerung des Datenzugriffs über diese In-Band-Appliance abgewickelt. Demgegenüber gibt es auch den Ansatz, die Virtualisierung über die so genannte Out-of-Band-Virtualisierung zu realisieren (2). In diesem Falle befindet sich die Out-of-Band-Appliance außerhalb des Datenpfades und kommuniziert über das Netzwerk (beispielsweise ein LAN) mit dem Host-Bus-Adapter (HBA) im Client. Die Out-of-Band-Appliance definiert die logischen Volumes, die ein Server benutzen darf.

Ein ähnliches Problem stellt sich bei der Speicherverwaltung z.B. im Internet. Ein Web-Cache ist hierbei eine Einheit in einem Netzwerk, die stellvertretend für einen oder mehrere Web-Server Zugriffe von Web-Clients beantwortet. Um diese Funktionalität zur Verfügung zu stellen, verfügt der Web-Cache über ein Speichersystem, auf dem Teile der Inhalte der Web-Server gespeichert werden. Speichert der Web-Cache die von einem Client angefragten Information nicht, so wird die Anfrage an einen übergeordneten Web-Cache bzw. den ursprünglichen Web-Server weitergeleitet und von diesem beantwortet. Web-Caches erfreuen sich aus verschiedenen Gründen einer weiten Verbreitung im Internet. Durch den Einsatz eines Web-Caches kann die Latenzzeit, die zwischen dem Stellen einer Anfrage von dem Web-Client bis zu der erfolgreichen Auslieferung der Informationen an den Web-Client vergeht, signifikant reduziert werden. Dieses trifft besonders dann zu, wenn die Bandbreite zwischen dem Web-Cache und dem Web-Client größer als die Bandbreite zwischen dem Web-Server und dem Web-Client ist oder wenn die Belastung des Web-Servers so hoch ist, dass es bei der Auslieferung der Daten in dem Web-Server selbst zu Stauungen kommt. Weiterhin kann durch den Einsatz von Web-Caches der Datenverkehr im Internet reduziert werden, wodurch eine Steigerung der Leistungsfähigkeit des gesamten Systems Internet erzielt werden kann.

Durch die Kooperation mehrerer Web-Caches, die an verschiedenen Orten des Internets platziert werden, kann die Leistungsfähigkeit des Internets deutlich erhöht werden. Beispiele für die kooperative Zusammenarbeit mehrerer Web-Caches sind das NLANR (National Laboratory of Applied Network Research) Caching-System, das aus einer Menge von Backbone-Caches in den USA besteht, oder das Akamai Caching-System, das Caching-Services für Unternehmen auf der ganzen Welt bereitstellt.

Der Hauptunterschied in der Bereitstellung von Verfahren zum Wiederauffinden von Daten in Speichernetzwerken bzw. verteilten Dateiservern und für Web-Caches besteht darin, dass im Falle von Speichernetzwerken die angeschlossenen Computersysteme über alle Informationen bezüglich der Platzierungsstrategie verfügen, die zum Wiederauffinden der von ihnen verwendeten Daten notwendig sind. Dieses umfasst unter anderem die Anzahl und die Eigenschaften der angeschlossenen Clients, respektive der Datenspeichersysteme. Im Falle von Web-Caches verfügt der Client hingegen nur über eine beschränkte Sicht des Gesamtsystems, d. h. er kennt nicht alle an das System angeschlossenen Web-Caches. Werden nicht alle Daten auf allen Web-Caches gespeichert, kann dieses dazu führen, dass der Web-Client ein Datum nicht von einem Web-Cache, sondern nur direkt vom Web-Server anfordern kann, da er entweder keinen Web-Cache kennt, der die von ihm angefragten Informationen speichert, oder weil er zwar den für ihn relevanten Web-Cache kennt, jedoch diesen Web-Cache nicht als für dieses Datum zuständig identifizieren kann.

Die Nutzung von Redundanz zur Sicherung von Daten wird bereits seit geraumer Zeit in Datenspeichersystemen gegen den Ausfall einzelner Datenspeichersysteme genutzt. Die meistverwendeten Verfahren sind dabei als sog. RAID-Verfahren (Redundant Array of Independent Discs) in verschiedene Gruppen eingeteilt [PGK88]. Den RAID-Verfahren gemeinsam ist, dass ein zu speichernder Datenblock in einen oder mehrere Subblöcke aufgeteilt wird und ein oder mehrere zusätzliche Subblöcke generiert werden, in denen die Redundanzinformationen gesichert werden [BBBM94] [BHMM93] [HG92] [TPBG93]. Um nach dem Ausfall eines Datenspeichersystems die zugehörigen Informationen zurückgewinnen zu können, müssen im Allgemeinen alle Subblöcke, d.h. die Datensubblöcke und die Redundanzsubblöcke, auf unterschiedlichen, physikalischen Speichermedien gesichert sein.

Um diese Eigenschaft sicherzustellen, werden im allgemeinen Muster kreiert, mit deren Hilfe die Daten über die angeschlossenen Datenspeichersysteme verteilt werden. In der ursprünglichen Version wird dabei vorausgesetzt, dass alle Datenspeichersysteme, über die Datenblöcke verteilt werden, die gleiche Größe haben und dass sich die Anzahl der Datenspeichersysteme nicht ändert. Eine Hinzunahme einzelner Datenspeichersysteme würde bewirken, dass ein neues Muster generiert werden muss und nahezu alle bisher gesicherten Datenblöcke neu verteilt werden müssen.

Neuere Lösungen ermöglichen es, auch Datenspeichersysteme unterschiedlicher Größe zu einem RAID-System zusammenzufassen. Jedoch ist es auch bei diesen Verfahren notwendig, nahezu alle Daten zu verschieben, wenn neue Datenspeichersysteme in das System integriert werden oder Datenspeichersysteme aus dem System herausgenommen werden [CL00] [CL01].

Die US 2004/0030822 A1 befasst sich zum Beispiel damit, wie möglichst effizient auf Basis eines bereits bestehenden Dateisystems eine Speichervirtualisierung durchzuführen ist. Hierzu werden bestehende Komponente, wie zum Beispiel NAS-Filer als Grundlage der Speichervirtualisierung verwendet werden. Diese Patentanmeldung behandelt somit keine Verfahren zur Bereitstellung von redundanten Informationen zum Schutz gegen den Ausfall einzelner Speichermedien, sondern nutzt nur bereits im Stand der Technik bekannte Verfahren.

Die DE 102 36 796 A1 befasst sich mit der randomisierten Datenverteilung über Speichersysteme. Dabei kann es jedoch vorkommen, dass eine beliebige Submenge von Datenblöcken auf ein gemeinsames Speichermedium abgebildet wird. Hierdurch können auch Datenblöcke, die einer Redundanzgruppe angehören, auf ein gemeinsames Speichermedium abgebildet werden.

Bei der US-PS 5 568 629 wird Flexibilität beim Aufbau von Speichersystemen erhöht In dem schon vorher bekannten Stand der Technik wurden RAID-Systeme aus „ganzen" Festplatten zusammengestellt. So wurde z.B. beim RAID 1 das Original eines Datenblocks auf Festplatte 1 und die Kopie auf Festplatte 2 gesichert. Nach dem Ausfall von Festplatte 1 konnte das Original aus der Kopie eindeutig rekonstruiert werden. Gemäß der Lehre der US-PS 5 568 629 kann nun jede Festplatten in verschiedene Partitionen eingeteilt werden. D.h., eine physikalische Festplatte kann in verschiedene logische Anteile partitioniert werden, die von außen als eigenständige Festplatte zugegriffen werden. Somit ist es möglich, z.B. die untere Hälfte einer Festplatte in einen RAID 1-Pool zur Verfügung zu stellen und die obere Hälfte einem RAID 5-Systeme verfügbar zu machen. Somit können ohne Beeinträchtigung verschiedene RAID-Systeme ohne Zugriffskonflikt auf einer physikalischen Festplatte arbeiten. Ein weiterer Bestandteil der Erfindung besteht darin, verschiedene RAID Systeme zu verbinden und somit nach außen einen größeren Speicherplatz anzubieten: Beide Techniken haben zum heutigen Zeitpunkt eine weite Verbreitung gefunden. So werden heute Speichersysteme im allgemeinen nicht als ganzes verwendet, sondern vor ihrer Verwendung partitioniert, dass heißt in verschiedene logische Speicherbereiche eingeteilt, die voneinander unabhängig zugegriffen werden können. So werden Software-RAID-Systeme z.B. unter dem Betriebssystem Linux (und vielen weiteren Betriebssystemen) mit dem Programm md nicht auf Basis ganzer Festplatten, sondern auf Partitionen von Festplatten erstellt. Auch werden Speichersysteme häufig durch Konkatenierung, d.h. Hintereinanderschaltung, von bestehenden Systemen vergrößert. Dieses alles wird jedoch in der US-PS 5 568 629 statisch durchgeführt. Weiterhin müssen die einzelnen Partitionen der verwendeten Speichersysteme gewissen homogenen Eigenschaften (wie z.B. die Eigenschaft der gleichen Größe) genügen, um effizient gemeinsam als RAID-System verwendet werden zu können.

In der US 2004/0064641 A1 werden Verfahren vorgestellt, in denen die Speichersysteme eines logischen Laufwerkes in Parity-Gruppen eingeteilt werden. Eine Parity-Gruppe besteht dabei aus einer festen Menge von Partitionen von physikalischen Speichermedien. Jeder Parity-Gruppe wird ein Bereich des logischen Adressraums zugeordnet. Werden auf eine Parity-Gruppe zu viele Zugriffe abgebildet, so kann diese Parity-Gruppe noch einmal unterteilt werden. Ein Teil des Adressraumes der ursprünglichen Parity-Gruppe wird dann auf eine weitere Parity-Gruppe kopiert, um eine Entlastung der ursprünglichen Parity-Gruppe zu erzielen.

Aufgabe der vorliegenden Erfindung ist es daher, Verfahren zur Verteilung von Daten insbesondere in heterogenen Datenspeichersystemen und Anordnungen von heterogenen Datenspeichersystemen vorzuschlagen, die in der Lage sind, Mengen von Datenblöcken derart über verschiedenartige Speichersysteme so zu verteilen, dass niemals zwei Datenblöcke aus einer Menge von Datenblöcken auf das gleiche, physikalische Datenspeichersystem abgebildet werden und gleichwohl immer eine sichere redundante Verteilung der Daten gewährleistet ist, ohne daß bei jeder Veränderung an den heterogenen Datenspeichersystemen umfangreiche Umgruppierungen der Daten erforderlich werden.

Die Lösung der erfindungsgemäßen Aufgabe ergibt sich hinsichtlich des Verfahrens aus den kennzeichnenden Merkmalen des Anspruches 1, hinsichtlich der Anordnung aus den kennzeichnenden Merkmalen des Anspruches 18 sowie hinsichtlich des Computerprogrammproduktes aus den kennzeichnenden Merkmalen des Anspruches 26 und hinsichtlich des computerlesbaren Speichermediums aus den kennzeichnenden Merkmalen des Anspruches 27 jeweils in Zusammenwirken mit den Merkmalen des zugehörigen Oberbegriffes. Weitere vorteilhafte Ausgestaltungen der Erfindung ergeben sich aus den Unteransprüchen.

Die Erfindung hinsichtlich des Verfahrens gemäß Anspruch 1 geht dabei von einem Verfahren zur Verteilung von Datenblöcken über Datenspeichersysteme in Computersystemen und/oder Speichernetzwerken und/oder einem Datennetz, vorzugsweise einem Intranet und/oder dem Internet, aus. Ein derartiges Verfahren wird dadurch weiter gebildet, dass eine Menge von Datenblockmengen Di (i = 1, ..., m), die jeweils aus maximal s Datenblöcken bestehen, die nicht auf dasselbe Datenspeichersystem abgebildet werden dürfen, einer Menge von Datenspeichersystemen Sj (j = 1, ..., n) gemäß den folgenden Schritten zugeordnet und dort gespeichert wird: Zuerst wird der Gesamtmenge der Datenspeichersysteme ein virtueller Speicherraum zugeordnet und anschließend die einzelnen Partitionen der Datenspeichersysteme in Gruppen eingeteilt, wobei jede Partition maximal einer Gruppe zugeordnet wird und alle Partitionen eines Datenspeichersystems der gleichen Gruppe zugeordnet werden. Anschließend läuft erstmalig die Durchführung eines Verfahrens zur Lösung des Optimierungsproblems ab, bei dem die Datenblöcke derart über die Datenspeichersysteme verteilt werden, dass die genutzte Kapazität der Datenspeichersysteme maximiert wird. Dieser Optimierungsschritt wird dabei beim Inbetriebnehmen der Datenspeichersysteme erstmalig durchgeführt und dann immer wieder, wenn sich die Konfiguration der Datenspeichersysteme signifikant oder beispielsweise abhängig von Schrankenwerten ändert. Ist eine derartige optimale Verteilung der Datenblöcke gefunden, so wird anschliessend laufend ein Verfahren durchgeführt, das mit Hilfe der Ergebnisse aus der Lösung des Optimierungsproblems Datenblockmengen einer Menge von Gruppen zuordnet, woraufhin ebenfalls laufend ein Verfahren durchgeführt wird, mit dem Datenblöcke dann über eine Gruppe verteilt werden. Sowohl das Verfahren der Zuordnung von Datenblockmengen zu einer Menge von Gruppen als auch das Verfahren zur Verteilung der Datenblöcke über eine Gruppe wird dabei im laufenden Echtzeitbetrieb der Speichersysteme ausgeführt, um die entsprechenden Anfragen der Clients an die Server bzw. Caches zu bearbeiten, wobei die tatsächliche Verteilung der Daten anhand des in der Optimierungsphase gefundenen Verteilungsplanes erfolgt. Dieser bleibt solange gleich, wie sich keine entsprechenden Änderungen an der Konfiguration der Datenspeichersysteme einstellen oder auch andere Vorgaben zur Datenspeicherung etwa von Bedienpersonen vorgegeben werden.

Sowohl das Verfahren der Zuordnung von Datenblockmengen zu einer Menge von Gruppen als auch das Verfahren zur Verteilung der Datenblöcke über eine Gruppe kann anhand von grundsätzlich den Fachmann bekannten Algorithmen ausgeführt werden. Hierbei können insbesondere auch Algorithmen gemäss der DE 102 36 796 A1 zur Verwendung kommen.

Besondere Eigenschaften des Verfahrens sind, dass zum einen die verwendeten Datenspeichersysteme nicht über die gleiche Kapazität verfügen müssen und die Kapazität der Datenspeichersysteme im Rahmen der physikalischen Möglichkeiten dennoch optimal genutzt wird, als auch dass nach der Hinzunahme oder nach dem Entfernen von Datenspeichersystemen die Anzahl der zu verschiebenden Datenblöcke minimiert werden kann und somit der Transfer des Systems in einen optimalen Zustand in nahezu optimaler Zeit durchgeführt werden kann. Die Mengen von Datenblöcken werden hierbei im Folgenden als Datenblockmenge bezeichnet.

Hierzu wird in weiterer Ausgestaltung bei Änderungen an den Datenspeichersystemen das Verfahren zur Lösung des Optimierungsproblems erneut ausgeführt und anschließend ein Verfahren zur Umverteilung in den Datenspeichersystemen gespeicherter Daten durchgeführt, mit dem die schon in den Datenspeichersystemen gespeicherten Daten entsprechend der nunmehr gültigen optimalen Datenzuordnung umgruppiert werden. Auch derartige Verfahren sind grundsätzlich bekannt, doch kann durch die erfindungsgemässe Ausführung des Verfahrens dafür gesorgt werden, dass bei der Umverteilung nur eine geringe Teilmenge der in den Datenspeichersystemen gespeicherten Daten in ihrer Speicherzuordnung verändert werden, um die neue nunmehr gültige optimale Datenzuordnung einzustellen. Auch ist es dabei denkbar, dass das Verfahren zur Umverteilung in den Datenspeichersystemen gespeicherter Daten parallel zum laufenden Betrieb der Datenspeichersysteme durchgeführt wird, wodurch insbesondere bei grossen Mengen von Datenspeichersystemen bzw. grossen Datenmengen entsprechende Zeitersparnisse einhergehen.

Um eine hohe Effizienz, Skalierbarkeit und Robustheit eines Datenspeichersystems sicherzustellen, werden an ein Verfahren, dass z.B. zur Sicherung von redundanzbehafteten Daten genutzt werden kann, die folgenden Anforderungen gestellt:

  • – Es werden keine zwei oder mehr Datenblöcke einer Datenblockmenge auf dem gleichen physikalischen Datenspeichersystem gesichert.
  • – Es werden Datenspeichersysteme unterschiedlicher Kapazität und Übertragungsrate unterstützt.
  • – Die in einem Datenspeichersystem vorhandene Speicherkapazität wird nahezu optimal genutzt.
  • – Nach einer Hinzunahme oder nach dem Entfernen eines Datenspeichersystems zu einer zusammengehörigen Menge von Datenspeichersystemen müssen nur eine minimale Anzahl von Daten umplatziert werden, um wieder alle vorangegangenen Anforderungen zu erfüllen.

Verfügt der Client nur über unvollständige Informationen über die Verteilung der Daten über die Datenspeichersysteme, wie z. B. der Client von Web-Caches, so muss zusätzlich der folgende Punkt unterstützt werden:

  • – auch wenn der Client nur über unvollständige, bzw. falsche Informationen über den Aufbau des Speichersystems verfügt, muss die Datenplatzierungsstrategie sicherstellen, dass eine höchst mögliche Anzahl von Zugriffen auf das Speichersystem erfolgreich ist, d. h. an einen die Informationen speichernden Server gestellt werden.

Im Folgenden werden nun Verfahren vorgestellt, die den hier gestellten Anforderungen entsprechen. Diese Verfahren greifen auf Strategien zurück, die in der Lage sind, Daten gemäß einer Anforderungsverteilung gleichmäßig über eine Menge von Datenspeichersystemen zu verteilen (siehe z.B. [BSS02] [KLL+97] [SBS+02]).

Als Eingabe für die Verfahren dienen:

  • – Eine Menge von Partitionen von Datenspeichersystemen.
  • – Die Kapazität der einzelnen Partitionen.
  • – Eine Zuordnung der Partitionen zu physikalischen Datenspeichersystemen.
  • – Gewählte maximale Anzahl s an Datenblöcken, die in einer Menge von Datenblöcken auftreten können. Für das hier vorgestellte Verfahren ist nur die Anzahl der Datenblöcke innerhalb einer Datenblockmenge relevant. Die Bedeutung eines Datenblocks geht nicht in die folgenden Berechnungen mit ein.
  • – Gewählte Datenblockgröße.

Voraussetzung für die Verfahren ist nun, dass die Anzahl der physikalischen Datenspeichersysteme, die an dem Verfahren teilnehmen, größer oder gleich der maximalen Anzahl s der Datenblöcke innerhalb einer Datenblockmenge ist. Die Verfahren sind in eine Vorverarbeitungsphase und in eine Online-Phase eingeteilt. Die Vorverarbeitung wird immer dann ausgeführt, wenn sich die Anzahl der Partitionen in dem System verändert (siehe 4 und 5) und entspricht im wesentlichen den Verfahrensschritten a) bis c) gemäß der Merkmalsgliederung des Anspruches 1. Die Online-Phase entspricht hierbei den Verfahrensschritten d) und e) gemäß der Merkmalsgliederung des Anspruches 1.

Verfahren zur pseudo-zufälligen Speicherung von Datenblockmengen in Speichersystemen

Im Rahmen dieser Erfindung werden die folgenden Verfahren und Anordnungen zur Speicherung von Datenblockmengen beschrieben, die auf den folgenden Grundlagen beruhen:

Die Speicherung von Datenblockmengen wird in einem mindestens zweistufigen Prozess durchgeführt, wobei die folgenden zwei Stufen wichtiger Bestandteil des Verfahrens und der Anordnung sind:

  • – In einer Vorverarbeitungs- bzw. Optimierungsphase wird berechnet, welche Anteile von Datenblöcken auf welche Gruppen von Speichersystemen verteilt werden sollen.
  • – In der Online-Phase werden auf Basis von wie noch nachfolgend angegeben berechneten Gewichten und unter Verwendung von Verfahren zur Verteilung über heterogene Speichersysteme Datenblöcke auf Basis ihrer virtuellen Adresse über die Speichersysteme verteilt.

Die Optimierungsphase sollte immer dann durchgeführt werden, wenn sich die Anzahl der Speichersysteme verändert hat oder wenn durch die Datenverteilung über die Speichersysteme neue Eigenschaften erzielt werden sollen (siehe 4 und 5) und sich somit die Eingabe der Optimierungsphase verändert hat.

Im Anschluss an die Optimierungsphase sollte eine Umverteilungsphase durchgeführt werden (siehe 5), in der die bereits gespeicherten Datenblöcke gemäß der neuen Eigenschaften über die Speichersysteme verschoben werden.

Bei den bevorzugt vorgestellten Verfahren kann sichergestellt werden, dass die Anzahl der Umplatzierungen, die nach einer neuen Optimierungsphase notwendig werden, minimiert werden kann.

Die Optimierungsphasen und die Umverteilungsphasen können natürlich auch nach anderen Kriterien ausgewählt werden. Die Umverteilungsphase sollte für den Benutzer der Speichersysteme transparent durchgeführt werden, d.h. während einer Umverteilung kann weiterhin auf die Daten lesend und schreibend zugegriffen werden.

Im Folgenden werden bevorzugte Verfahren zur Verteilung der Datenblockmengen für den Fall, dass die Anzahl der Datenblöcke innerhalb einer Datenblockmenge konstant sind, bzw. nicht konstant sind, vorgestellt.

Bevorzugtes Verfahren zur Verteilung von Datenblockmengen mit konstanter Anzahl von Datenblöcken über alle Datenblockmenge

Das bevorzugte Verfahren zur Verteilung von Datenblockmengen mit konstanter Anzahl von Datenblöcken über alle Datenblockmenge ist in eine Optimierungs- und eine Online-Phase eingeteilt.

Optimierungsphase

Die Optimierungsphase ist durch ein Optimierungsproblem gekennzeichnet, dass implizit durch die folgenden Schritte beschrieben wird. Die Qualität der Lösung des Optimierungsproblems ist dabei entscheidend für die Qualität des Verfahrens. Neben der hier beschriebenen Optimierung durch ein lineares Programm kann auch jeder weitere Optimierungsalgorithmus verwendet werden:

Teile die Partitionen in nG Gruppen ein. Alle Partitionen, die einem physikalischen Laufwerk angehören, sind in einer gemeinsamen Gruppe. Jede Partition ist nur in einer Gruppe vertreten. Es ist erlaubt, dass Partitionen unterschiedlicher physikalischer Speichersysteme in einer Gruppe vertreten sind, solange die Anzahl der Gruppen größer als die maximale Anzahl s der Datenblöcke einer Datenblockmenge ist.

Für jede Gruppe i wird über alle Partitionen j dieser Gruppe die mögliche Kapazität

in Subblöcken berechnet. Der Parameter Cj kennzeichnet dabei eine Kapazität, die proportional zu der Anzahl der Datenblöcke, die auf der Partition gesichert werden sollen, ist. Dieser Wert kann proportional zu der Speicherkapazität der Partition sein, er kann jedoch auch gemäß anderer Parameter oder gemäß Kombinationen anderer Parameter gewählt werden. Der Vektor
kennzeichnet die Verteilung der Kapazitäten der einzelnen Gruppen.

Besteht jede Datenblockmenge aus s Datenblöcken, so gibt es

verschiedene Möglichkeiten, einen Datenblock über die Gruppen zu verteilen. Aus diesen möglichen Kombinationen werden k Kombinationen ausgewählt. Hierbei kann k zu
gesetzt werden und das Optimierungsproblem somit alle möglichen Kombinationen umfassen, es kann jedoch auch eine beliebige Anzahl k von Kombinationen ausgewählt werden.

Ziel des Optimierungsproblems ist es, die Anzahl der von einer Kombination i zu speichernden Datenblöcke und die als xi bezeichnet wird, zu berechnen, so dass die Summe über alle Kombinationen maximal wird. Der zugehörige Vektor

aller Kombinationen, wird als Belegungsvektor bezeichnet.

In einer Gruppe i werden aTix Subblöcke gespeichert, wobei aij = 1, wenn die Gruppe i der j-ten Kombination angehört, ansonsten wird aij zu Null gesetzt. Der Vektor A wird als

definiert.

Über die Kombinationen wird nun das folgende lineare Optimierungsproblem gelöst:

max (1 ... 1)x

unter Ax ≤ b

x ≥ 0

Die Lösung dieses Optimierungsproblems gibt die maximale Anzahl an Blöcken an, die für die gewählten Gruppen und Kombinationen unter den Restriktionen, dass die Datenblöcke einer Datenblockmenge auf verschiedene Datenspeichersysteme verteilt gesichert werden müssen, in dem System gespeichert werden können. Die Berechnung dieses Optimierungsproblems wird nur dann notwendig, wenn sich die Aufteilungen der Gruppen in dem System verändert haben, bzw. wenn Partitionen in das System integriert werden oder aus dem System herausgenommen werden, d.h. sich der Vektor b verändert hat.

Aus den k möglichen Kombinationen werden nun l Kombinationen ausgewählt. In der bevorzugten Variante werden diejenigen 1 Kombinationen gewählt, die eine Maximierung der genutzten Kapazität ermöglichen.

Aus der Lösung dieses Problems wird nun die Variable

abgeleitet, die den normierten Anteil der Datenblöcke, die von der Kombination i gespeichert werden sollen, beschreibt.

Online-Phase

Die Speicherung, bzw. das Lesen von Datenblöcken erfolgt nun in zwei Schritten:

  • – In dem ersten Schritt wird mit Hilfe einer Verteilungsfunktion, die Daten über heterogene Speichermedien verteilen kann, eine Kombination i herausgesucht, auf der dieser Datenblock platziert wird. Als Eingabe für die Größe der Kombination i wird der Wert ci gewählt.
  • – In dem zweiten Schritt wird für jede Gruppe der Kombination i diejenige Partition bestimmt, auf der der zugehörige Subblock gespeichert ist. Diese Berechnung wird ebenfalls mit Hilfe einer Verteilungsfunktion für heterogene Speichersysteme bestimmt.

Als Verteilungsfunktion können z.B. die unter [BSS02] [KLL+97] [SAS+02] beschriebenen Verfahren verwendet werden.

Bevorzugtes Verfahren zur Verteilung von Datenblockmenqen mit nicht konstanter Anzahl von Datenblöcken über alle Datenblockmenqen

Das hier vorgestellte Verfahren zur Verteilung von Datenblockmengen mit nicht konstanter Anzahl von Datenblöcken über alle Datenblockmenge ist ebenfalls in eine Vorverarbeitungs- bzw. Optimierungsphase und eine Online-Phase aufgeteilt:

Optimierungsphase

In diesem Fall ist die Anzahl der Datenblöcke s nicht für alle Datenblockmengen identisch. Es wird nun angenommen, dass es w verschiedene Anzahlen von Datenblöcken s1,...,sw in Datenblockmengen gibt. Vor der Durchführung der Optimierungsphase kann geschätzt werden, welcher Anteil psi von Datenblöcken auf jede der möglichen Anzahlen si entfällt. In dem bevorzugten Verfahren wird ohne Einschränkung der Allgemeinheit angenommen, dass die Größe der Subblöcke in allen Datenblockmengen identisch ist.

Die Optimierungsphase wird nun für jeden der w verschiedenen Anzahlen von Datenblöcken in den Datenblockmengen voneinander unabhängig durchgeführt, wobei jeweils die zugeordnete Kapazität für die Anzahl si mit einem Faktor &ggr;i gewichtet wird. In dem einfachsten Fall wird der Faktor &ggr;i 1. Es können selbstverständlich auch andere Gewichtungen verwendet werden, in denen unter anderem der Faktor psi einfliesen kann, um neben der reinen Speicherkapazität andere Eigenschaften einfließen zu lassen.

Online-Phase

Auf Basis der in dem Optimierungsproblem für eine Anzahl si gewonnenen Gewichte wird nun die Online-Phase wie für den oben beschriebenen Fall mit konstanter Anzahl von Datenblöcken über alle Datenblockmengen durchgeführt.

Eine besonders bevorzugte Ausführungsform der erfindungsgemäßen Verfahren bzw. der erfindungsgemäßen Anordnung zeigt die Zeichnung.

Es zeigen:

1 – grundsätzlicher Aufbau eines Speichernetzwerkes gemäß dem Stand der Technik,

2 – modifizierter Aufbau eines Speichernetzwerkes gemäß 1 mit Out-of-Band-Virtualisierung der Speichernetzwerkorganisation,

3 – modifizierter Aufbau eines Speichernetzwerkes gemäß 1 mit In-Band-Virtualisierung der Speichernetzwerkorganisation,

4 – Schematische Darstellung eines Ablaufs der erfindungsgemäßen Verfahren bei der Inbetriebnahme einer erfindungsgemäßen Anordnung,

5 – Schematische Darstellung eines Ablaufs der erfindungsgemäßen Verfahren im laufenden Betrieb einer erfindungsgemäßen Anordnung durch Umplatzierung von Daten nach einer Änderung der Konfiguration von Datenspeichersystemen,

Die Integration der Datenverteilungsstrategien in ein Speichernetzwerk 1 geht von einer Struktur gemäß 1 aus. Das Gesamtsystem besteht aus einer Menge von Datei- oder Datenbankservern, im Folgenden als Computersysteme bzw. Clients 3 bezeichnet, die über ein Speichernetzwerk 1 an Datenspeichersysteme 4 angeschlossen sind. Das Speichernetzwerk 1 umfaßt weiter eine Menge von Switches bzw. Routern 2, die die Zustellung der Datenpakete zwischen kommunizierenden Einheiten sicherstellen. Die Computersysteme sind in dem hier vorliegenden Kontext als Clients 3 zu betrachten, die von den Datenspeichersystemen 4 Datenblöcke lesen oder auf den Datenspeichersystemen 4 Datenblöcke schreiben. Mit Hilfe der hier vorgestellten Datenspeicherstrategie kann jede beliebige Teilmenge M der an das Speichernetzwerk 1 angeschlossenen Speichersysteme 4 wie ein einziger logischer Speicherpool verwaltet werden, der über einen virtuellen Adressraum verfügt. Die Menge der Speichersysteme 4 kann dabei in mehrere kleinere oder einen großen Speicherpool aufgeteilt werden, wobei keine der Speichersysteme 4 mehr als einem Speicherpool zugeordnet werden sollte. Es wird im Folgenden nur der Fall betrachtet, dass das System aus einem Speicherpool besteht.

Wird von einem Computersystem auf einen Datenbereich (Extent) zugegriffen, der bisher von dem Computersystem noch nicht verwendet wurde und für den keine Zuordnung in diesem Computersystem vorliegt, muss eine konsistente Zuordnung dieses Datenbereiches zu einem Speichersystem und zu einer Adresse auf diesem Speichersystem durchgeführt werden.

Die Allokation kann z.B. auf die folgenden Arten erfolgen:

Das Computersystem fragt bei einer zentralen Instanz, die über globales Wissen über alle Zuordnungen verfügt, nach einer Zuordnung für den Extent nach. Diese zentrale Instanz hat entweder diese Zuordnung bereits durchgeführt und kann diese an das Computersystem zurücksenden, oder es führt in einem ersten Schritt gemäß der hier vorgestellten Datenverteilungsverfahren eine Zuordnung des Datenbereiches zu einer Menge von Speichersystemen 4 durch und ordnet in einem zweiten Schritt Adressen auf den Speichersystemen 4 dem Extent zu.

Wird die Koordination nicht durch eine zentrale Instanz vorgenommen, so kann, muß aber nicht, diese Aufgabe nach 1 von einem oder mehreren der angeschlossenen Computersysteme übernommen werden. Weiterhin können jedoch auch ein oder mehrere dedizierte Geräte, die als SAN-Appliances 5 bezeichnet werden, zur Koordination der Computersysteme gemäß 2 bzw. 3 an das Speichernetzwerk 1 angeschlossen werden. Neben der Entlastung der Computersysteme um die Koordination kann durch den Einsatz von SAN-Appliances 5 sichergestellt werden, dass alle angeschlossenen Computersysteme die gleiche Sicht auf die Speichersysteme 4 haben, d. h. zum gleichen Zeitpunkt über das Verlassen bzw. Hinzukommen von Speichersystemen 4 informiert werden.

Die in der 2 dargestellte Out-of-Band-Virtualisierung durch eine parallel angeordnete SAN-Appliance 5 bietet eine Reihe von Schnittstellen, über die Informationen zwischen den SAN-Appliances 5 und den Client-Rechnern 3 ausgetauscht werden können. Diese können unter anderem die folgenden umfassen:

Anfrage der Grundkonfiguration von jedem Client 3,

Anfrage nach neuen Extents von jedem Client 3,

Information der Clients 3 über Veränderungen der Infrastruktur.

Das erfindungsgemäße Datenspeicherverfahren kann auch in so genannte In-Band-Appliances 5 integriert werden (siehe 3). Bei den In-Band-Appliances 5 handelt es sich um dedizierte Systeme, die eine Transformation der logischen Adresse eines Datenblocks, die sie von den angeschlossenen Computersystemen erhalten, in die physikalische Adresse vornehmen. Der Einsatz von In-Band-Appliances 5 ist dann sinnvoll, wenn die Funktionalität der Datenspeicherstrategie nicht in die Computersysteme 3 direkt integriert werden kann, da keine Software-Version der Datenspeicherstrategie für diese Computersysteme 3 verfügbar ist oder die Leistung der angeschlossenen Computersysteme 3 nicht ausreichend groß ist, um die Transformation der logischen Adressen in die physikalischen Adressen durchzuführen.

Eine In-Band-Appliance 5 verhält sich aus Sicht der Speichersysteme 4 wie ein angeschlossenes Computersystem 3, aus der Sicht der an die In-Band-Appliance 5 angeschlossenen Computersysteme 3 wie ein physikalisches Speichersystem.

In dem Speichernetzwerk 1 können In-Band-Appliances 5 mit Computersystemen 3, in denen die Datenspeicherstrategie ausgeführt wird, gemischt werden.

In einem anderen, verteiltem Verfahren kann auf jedem Speichersystem 4 ein Bereich reserviert sein, der eine Zuordnung zwischen virtueller Adresse und physikalischer Adresse vornimmt. Das Computersystem sucht zuerst auf Basis der virtuellen Adresse des Extents nach den Speichersystemen, die diesem Extent zugeordnet sind. Anschließend sucht das Computersystem nach einer noch freien Adresse auf dem Speichersystem 4.

In den 4 und 5 ist sehr schematisch dargestellt, wie bei der Inbetriebnahme eines Systems gemäss 1 mit den Datenblöcken s bzw. den Partitionen durch die Lösung des Optimierungsproblems in der vorangehenden Optimierungsphase die Gewichte für die Online-Zuordnung der Daten wie vorstehend beschrieben ermittelt und dann anschliessend im laufenden Betrieb die Online-Zordnung anhand von virtuellen Adressen ausgeführt wird.

Wird hingegen durch Änderungen an den Speichersystemen wie etwa Herausnahme oder Hinzufügung von einzelnen oder mehreren Speichersystemen eine Änderung der Konfiguration der Speichersysteme vorgenommen, so wird gemäss 5 durch erneutes Berechnen einer für diese geänderte Konfiguration dann optimalen Speicherstrategie in einer neuen Optimierungsphase ein neuer Satz von Gewichten ermittelt, der dann für die weitere Datenspeicherstrategie zugrunde gelegt werden kann. Die nicht mehr optimal platzierten Daten, die schon vor der erneuten Optimierung auf den Datenspeichersystemen abgelegt waren, werden dann durch ein Umplatzierungsverfahren auf die neuen, der nunmehr optimalen Datenspeicherstrategie entsprechenden Positionen verschoben, wobei hier nur eine sehr geringe Menge derartiger Daten zu verschieben sind und damit eine wesentliche Verbesserung gegenüber bekannten optimierten Datenspeicherstrategien festzustellen ist.

1Speichernetzwerk 2Switches bzw. Router 3Client 4Datenspeichersystem 5AN-Appliance Referenzen
  • [BBBM94] M. Blaum, J. Brady, J. Bruck und J. Menon, EVENODD: An Optimal Scheme for Tolerating Double Disk Failures in RAID Architectures", In Proceedings of the 21st Annual International Symposium on Computer Architecture, Seiten 245–254, 1994
  • [BHMM93] M.Blaum, H.T. Hao, R.L. Mattsoll und J.M. Menon, "Method and Means for Encoding and Rebuilding Data Contents of up to two unavailable DASDs in an in an Array of DASDs", US Patent No. 5,271,012, Dezember 1993
  • [BSS02] Brinkmann, A., K. Salzwedel und C. Scheideler: Compact, adaptive placement schemes for non-uniform distribution requirements. In Proc. of the 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), Seiten 53–62, 2002.
  • [CL00] Cortes, T. und J. Labarta: A Case for Heterogeneous Disk Arrays. In: Proceedings of the 1st IEEE International Conference on Cluster Computing, Chemnitz, Deutschland, November 2000.
  • [CL01] Cortes, T. und J. Labarta: Extending Heterogeneity to RAID level 5. In: Proceedings of the USENIX Annual Technical Conference, Boston, MA, Seiten 119–132, Juni 2001.
  • [HG92] M. Holland und G. Gibson, "Parity Declustering for Continuous Operation in Redundant Disk Arrays", In Proceedings of the Fifth International Conference on Architectural Support for Programming Languages ans Operating Systems, Seiten 23–35, 1992
  • [KLL+97] Karger, D., E. Lehman, F.T. Leighton, M. Levine, D. Lewin und R. Panigrahy: Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. In: Proceedings of the 29th ACM Symposium on Theory of Computing (STOC), Seiten 654–663, Mai 1997.
  • [PGK88] Patterson, D.A., G. Gibson und R.H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). In: Proceedings of the 1988 ACM Conference on Management of Data (SIGMOD), Seiten 109–116, Juni 1988.
  • [SBS+02] Deutsche Patentanmeldung DE 102 36 796 A1 von C. Scheideler, A. Brinkmann, K. Salzwedel, F. Meyer auf der Heide und U. Rückert: Verfahren und Anordnung zur randomisierten Datenspeicherung in Speichernetzwerken und/oder einem Intranet und/oder dem Intranet sowie ein entsprechendes Computerprogramm-Erzeugnis und ein entsprechendes computerlesbares Speichermedium
  • [TPBG93] F.A. Tobagi, J. Pang, R. Baird und M. Gang, "Streaming RAID: A Disk Array Management System for Video Files", In Proceedings of Computer Graphics (Multimedia '93 Proceedings), Seiten 393–400, 1993

Anspruch[de]
  1. Verfahren zur Verteilung von Datenblöcken über Datenspeichersysteme in Computersystemen und/oder Speichernetzwerken und/oder einem Datennetz, vorzugsweise einem Intranet und/oder dem Internet,

    dadurch gekennzeichnet, dass

    eine Menge von Datenblockmengen Di (i = 1, ..., m), die jeweils aus maximal s Datenblöcken bestehen, die nicht auf dasselbe Datenspeichersystem abgebildet werden dürfen, einer Menge von Datenspeichersystemen Sj (j = 1, ..., n) gemäß den folgenden Schritten zugeordnet und dort gespeichert wird:

    a) der Gesamtmenge der Datenspeichersysteme wird ein virtueller Speicherraum zugeordnet,

    b) die einzelnen Partitionen der Datenspeichersysteme werden in Gruppen eingeteilt, wobei jede Partition maximal einer Gruppe zugeordnet wird und alle Partitionen eines Datenspeichersystems der gleichen Gruppe zugeordnet werden,

    c) Durchführung eines Verfahrens zur Lösung des Optimierungsproblems, die Datenblöcke derart über die Datenspeichersysteme zu verteilen, dass die genutzte Kapazität der Datenspeichersysteme maximiert wird,

    d) Durchführung eines Verfahrens, das mit Hilfe der Ergebnisse aus Schritt c) Datenblockmengen einer Menge von Gruppen zuordnet,

    e) Durchführung eines Verfahrens, mit dem Datenblöcke über eine Gruppe verteilt werden.
  2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass bei Änderungen an den Datenspeichersystemen das Verfahren zur Lösung des Optimierungsproblems erneut ausgeführt und anschließend ein Verfahren zur Umverteilung in den Datenspeichersystemen gespeicherter Daten durchgeführt wird, mit dem die schon in den Datenspeichersystemen gespeicherten Daten entsprechend der nunmehr gültigen optimalen Datenzuordnung umgruppiert werden.
  3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass bei der Umverteilung nur eine geringe Teilmenge der in den Datenspeichersystemen gespeicherten Daten in ihrer Speicherzuordnung verändert werden, um die neue nunmehr gültige optimale Datenzuordnung einzustellen.
  4. Verfahren nach einem der Ansprüche 2 oder 3, dadurch gekennzeichnet, dass das Verfahren zur Umverteilung in den Datenspeichersystemen gespeicherter Daten parallel zum laufenden Betrieb der Datenspeichersysteme durchgeführt wird.
  5. Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet, dass als Verfahren der Zuordnung von Datenblockmengen zu einer Menge von Gruppen und als Verfahren zur Verteilung der Datenblöcke über eine Gruppe Verfahren zur randomisierten Datenspeicherung in Speichernetzwerken genutzt werden.
  6. Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet, dass das Verfahren der Zuordnung von Datenblockmengen zu einer Menge von Gruppen und die Durchführung des Verfahrens der Verteilung der Datenblöcke über eine Gruppe laufend während des Betriebes der Datenspeichersysteme durchgeführt wird.
  7. Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet, dass das Verfahren zur Lösung des Optimierungsproblems einmalig beim Inbetriebnehmen der Datenspeichersysteme und anschließend bei jeder Änderung der Konfiguration der Datenspeichersysteme durchgeführt wird.
  8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass die Durchführung des Verfahrens zur Lösung des Optimierungsproblems parallel zum laufenden Betrieb der Datenspeichersysteme durchgeführt wird.
  9. Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet, dass es sich bei dem Verfahren zur Lösung des Optimierungsproblems um ein Näherungsverfahren handelt.
  10. Verfahren nach einem der vorstehenden Ansprüche, dadurch gekennzeichnet, dass ein für eine spezifische Gesamtmenge von Datenspeichersystemen abgestimmter Parameter Ci vorgegeben wird, der charakteristisch für eine Konfiguration der Gesamtmenge der Datenspeichersysteme ist und entweder die jeweilige physikalische Kapazität der Datenspeichersysteme oder die gewünschte Anfragelast an die Datenspeichersysteme beschreibt oder Abweichungen von der gewünschten Verteilung der Daten auf den Datenspeichersystemen korrigiert.
  11. Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass bei Änderungen mindestens eines der Werte C = (C1, ..., Cn) des vorgebbaren Parameters Ci eine erneute Zuordnung der Datenblöcke Di zu den Datenspeichersystemen Sj nach dem Verfahren zur Verteilung von Datenblöcken gemäß einem der vorstehenden Ansprüche unter Zugrundelegung der neuen Parameterwerte C' = (C1', ..., Cn') erfolgt.
  12. Verfahren nach einem der Ansprüche 10 oder 11, dadurch gekennzeichnet, dass bei Änderungen mindestens eines der Werte C = (C1, ..., Cn) des vorgebbaren Parameters eine erneute Zuordnung der Datenblöcke Di zu den Datenspeichersystemen Sj nach dem Verfahren zur Verteilung von Datenblöcken gemäß einem der vorstehenden Ansprüche unter Zugrundelegung der neuen Parameterwerte C' = (c1', ..., cn') nur erfolgt, wenn ein neuer Parameterwert ci' sich von dem entsprechenden aktuellen Parameterwert ci um eine vorgebbare Konstante &mgr; unterscheidet.
  13. Verfahren nach einem der Ansprüche 10 bis 12, dadurch gekennzeichnet, dass bei Änderungen mindestens eines der Werte C = (C1, ..., Cn) des vorgebbaren Parameters in einen neuen Parameterwert C' = (C1', ..., Cn') stufenweise eine erneute Zuordnung der Datenblöcke Di zu den Datenspeichersystemen Sj nach dem Verfahren zur Verteilung von Datenblöcken gemäß einem der vorstehenden Ansprüche erfolgt, wobei in jeder Stufe k Zwischen-Parameterwerte Ck = (Ck1, ..., ckn) mit |ci – cki| ≤ |ci – c'i| (i = 1, ..., n) zugrundegelegt werden.
  14. Verfahren nach einem der vorangehenden Ansprüche, dadurch gekennzeichnet, dass zur Abspeicherung der Datenblöcke in einem Speichermedium mindestens eine Tabelle bereitgestellt wird, in denen die Zuordnung zwischen virtueller Adresse und physikalischer Adresse auf dem Speichermedium abgespeichert ist.
  15. Verfahren nach Anspruch 14, dadurch gekennzeichnet, dass mehrere Datenblöcke zu einem Extent zusammengefasst werden, dem in der Tabelle eine gemeinsame physikalische Adresse auf dem Speichermedium zugeordnet wird, wobei die Datenblöcke eines Extents im logischen Adressraum miteinander verbunden sind, indem der erste Datenblock eines aus 2&lgr; Datenblöcken bestehenden Extents eine Adresse der Form x00...000 erhält, wobei die unteren &lgr; Bits durch die Ziffer Null repräsentiert sind, der letzte Block dieses Extents die Adresse x11...111 erhält, wobei die untersten &lgr; Bits durch die Ziffer Eins repräsentiert sind und die physikalische Position eines Datenblocks durch eine Addition des Tabelleneintrags für den zugehörigen Extent mit den letzten &lgr; Bits der logischen Adresse des Datenblocks gewonnen wird.
  16. Verfahren nach Anspruch 15, dadurch gekennzeichnet, dass mehrere Datenblöcke zu einem Extent zusammengefasst werden, dem in der Tabelle eine gemeinsame physikalische Adresse auf dem Speichermedium zugeordnet wird, wobei die Datenblöcke eines Extents im logischen Adressraum miteinander verbunden sind, jedoch unterschiedliche Größen aufweisen können.
  17. Verfahren nach Anspruch 15, dadurch gekennzeichnet, dass die zu einem Extent zusammengefassten Datenblöcke im Adressraum nicht hintereinander folgend platziert sein müssen und die Startadresse eines aus 2&lgr; Datenblöcken bestehenden Extents nicht eine Adresse der Form x00...000 enthalten muss, wobei die unteren &lgr; Bits durch die Ziffer Null repräsentiert sind, und der letzte Block dieses Extents nicht die Adresse x11...111 enthalten muss, wobei die untersten &lgr; Bits durch die Ziffer Eins repräsentiert sind, und die physikalische Position eines Datenblocks nicht ausschließlich durch eine Addition des Tabelleneintrags für den zugehörigen Extent mit den letzten &lgr; Bits der logischen Adresse des Datenblocks gewonnen werden kann.
  18. Anordnung mit mindestens einem Prozessor, die derart eingerichtet ist, dass ein Verfahren zur Verteilung von Datenblöcken in Speichernetzwerken und/oder in einem Datennetz, insbesondere einem Intranet und/oder dem Internet, durchführbar ist, wobei die Datenspeicherung die Verfahrensschritte gemäß einem der Ansprüche 1 bis 17 umfasst.
  19. Anordnung nach Anspruch 18, dadurch gekennzeichnet, dass die Anordnung mindestens ein Datenspeichersystem und/oder mindestens ein Computersystem, das lesend und/oder schreibend auf die Speichermedien zugreift und/oder mindestens eine zwischen und/oder neben das Computersystem und das Datenspeichersystem geschaltete Kontroller-Einheit zur Steuerung des Verfahrens umfasst.
  20. Anordnung nach einem der Ansprüche 18 oder 19, dadurch gekennzeichnet, dass das Datenspeichersystem Festplattenfelder und/oder als Web-Cashes ausgebildete Zwischenspeicher umfasst.
  21. Anordnung nach einem der Ansprüche 18 bis 20, dadurch gekennzeichnet, dass die Anordnung mindestens eine zwischen das Computersystem und das Datenspeichersystem geschaltete Kontroller-Einheit zur Steuerung des Verfahrens zur Verteilung von Datenblöcken umfasst.
  22. Anordnung nach Anspruch 19, dadurch gekennzeichnet, dass die Anordnung mindestens ein über die Kontroller-Einheit auf die Speichermedien zugreifendes Computersystem umfasst.
  23. Anordnung nach einem der Ansprüche 18 bis 22, dadurch gekennzeichnet, dass das Verfahren zur Verteilung von Datenblöcken als Hardware-RAID-Verfahren in der Kontroller-Einheit implementiert ist.
  24. Anordnung nach einem der Ansprüche 18 bis 23, dadurch gekennzeichnet, dass die Anordnung mindestens ein dediziertes, über Mittel zum Datenaustausch mit Speichermedien und Computersystemen der Anordnung verbundenes Computersystem (SAN-Appliance) zur Koordination der Datenspeicherung und/oder über Mittel zum Datenaustausch mit Speichermedien und Computersystemen der Anordnung verbundene Rechenressourcen (In-Band-Appliances) zur Verteilung der Datenblöcke umfasst.
  25. Anordnung nach einem der Ansprüche 18 bis 24, dadurch gekennzeichnet, dass die Anordnung heterogene Speichermedien umfasst.
  26. Computerprogrammprodukt, das ein computerlesbares Speichermedium umfasst, auf dem ein Programm gespeichert ist, das es einem Computer ermöglicht, nachdem es in den Speicher des Computers geladen worden ist, ein Verfahren zur Verteilung von Datenblöcken in Speichernetzwerken und/oder einem Datennetz durchzuführen, wobei das Verfahren zur Verteilung von Datenblöcken die Verfahrensschritte gemäß einem der Ansprüche 1 bis 17 umfasst.
  27. Computerlesbares Speichermedium, auf dem ein Programm gespeichert ist, das es einem Computer ermöglicht, nachdem es in den Speicher des Computers geladen worden ist, ein Verfahren zur Datenspeicherung in Speichernetzwerken und/oder einem Datennetz durchzuführen, wobei die Datenspeicherung die Verfahrensschritte gemäß einem der Ansprüche 1 bis 17 umfasst.
Es folgen 5 Blatt Zeichnungen






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com