Die Vielfalt der Begriffe und deren unterschiedliche Interpretationen in der Literatur erfordern es, der weiteren Diskussion der Eigenschaften von Namen und Objekten und deren Einfluß auf die dynamische globale Namensverwaltung eine klärende Begriffsdefinition voranzustellen. Die hierbei verwendete Notation stützt sich teilweise auf die Arbeiten von Peterson und Comer [Comer, 89].
Die Beschäftigung mit Namen hat eine lange Tradition. Zahlreiche Versuche wurden unternommen, ein tieferes Verständnis im Umgang mit Namen zu gewinnen. Aus den Bestrebungen, Namen theoretisch zu ergründen, sind eine ganze Reihe interessanter Modelle hervorgegangen. Ein erster Versuch, das Wesen von Namen begrifflich zu bestimmen, war die vielzitierte Shochsche Sentenz [Shoch, 78]:
The
name of an object specifies what a process seeks,
an
address specifies where this object is,
a
route specifies how to get there.
Die von Shoch aufgestellte Definition für Namen und Adressen war wenig erfolgreich. In der Literatur finden sich hierzu zahlreiche Kritiken [Saltzer, 82] [Hauzeur, 86]. Die Hauptgründe, warum die Shochsche Sentenz keine befriedigende Begriffsbildung darstellt, sind folgende:
• Die Definition der Adresse läßt eine vieldeutige Interpretation zu. Zudem existieren Adressen, die nicht den Ort eines Objekts angeben (z.B. Ethernet-Adressen).
• Die Shochsche Definition ignoriert ein weiteres Schlüsselkonzept der Namens- und Adreß-problematik, das Konzept der Abbildung.
Weitere Modelle zur Umsetzung und Auflösung von Namen wurden insbesondere von Saltzer [Saltzer, 78], Comer und Peterson [Comer, 89] und Younger [Younger, 92] aufgestellt. Saltzer schlägt eine breitere Definition des Begriffs „Name“ vor. Hierzu führt er als Beziehung zwischen Namen und Adressen den Begriff der Bindung ein. Die Adresse eines Objekts definiert er hierauf aufbauend als Name desjenigen Kommunikationsobjekts, an das das Objekt gebunden ist. Diese Beziehung von Namen und Adressen wird auch von Hauzeur [Hauzeur, 86] für das ISO/OSI-Schichtenmodell aufgegriffen (vgl. Abschnitt 1.2.2).
An
object’s address is the name of the object it is bound to.
In der vorliegenden Arbeit werden Benutzer-Namen und System-Namen unterschieden. Diese Kategorisierung von Namen ist zum einen durch die ursprüngliche Definition von Shoch, aber auch durch die Arbeiten von Terry [Terry, 85] motiviert:
• Benutzer-Namen werden vom Anwender für Objekte vergeben.
• System-Namen werden Objekten vom System oder vom Systemadministrator zugeteilt.
In diese einfache Kategorisierung fügen sich o.g. Namen als Benutzer-Namen ein, während Adressen der weitergefaßten Kategorie der System-Namen zuzuordnen sind. Eine nähere Charakterisierung von Benutzer- und System-Namen geben die folgenden Abschnitte.
Der Begriff „Name“ findet somit nicht nur für symbolische Namen der Anwendungsebene, sondern auch für system- und kommunikationsorientierte Bezeichner und Adressen Verwendung. Die unterschiedlichen Namen bilden dabei eigene Namensräume, die zueinander in Beziehung stehen.
Die Eigenschaften von Namen korrelieren mit den Eigenschaften benannter Objekte. Objekte treten in verteilten Systemen auf unterschiedlichen Systemebenen auf[AL1], die zur Kategorisierung der zugehörigen Namensräume herangezogen werden können. Alternativ besteht die Möglichkeit zur Kategorisierung von Namen anhand ihrer Struktur und den Systemsichten, d.h. den Schnittstellen zum System, an denen Namen auftreten.
Verteilte Systeme ermöglichen nicht nur den Zugriff auf lokale, sondern über Kommunikationskanäle auch auf entfernte Objekte im Netzwerk integrierter Knoten. Somit erhöht sich die Anzahl zu benennender Objekte im Gesamtsystem um ein Vielfaches. Aufgrund der Quantität der verwalteten Objekte kann in verteilten Systemen kein Anwender die gesamten, systemweit existierenden Informationen lokal verfügbar haben, sondern immer nur einen Teilausschnitt. Dabei besteht die Gefahr, daß ein Anwender wichtige Informationen nicht findet oder übersieht, da diese ungeeignet strukturiert sind oder durch die Namensverwaltung nicht erfaßt werden.
Definition: Objekt
Ein Objekt o in einem Rechnersystem ist eine physische oder logische Ressource bestehend aus Code, Daten oder Hardware, auf die Aktionen gerichtet sind. Objekte dienen der Abstraktion von den Implementierungsdetails. Die Gesamtheit der Objekte bildet die Menge O.
Wie Abbildung 2.1 verdeutlicht, treten zu den in konventionellen Systemen verwalteten Objekten in verteilten Systemen kommunikationsbezogene Objekte wie Kommunikationsports, Knoten, Cluster, Zonen, Netzwerke und Kommunikationswege (Routes) hinzu [Goscinsky, 91]. Diese tragen Bezeichner, wie Adressen und Port-Nummern. Zur systemübergreifenden Identifikation von Objekten werden global eindeutige System-Namen (Bezeichner) generiert. Anwender greifen auf Objekte knotenübergreifend über symbolische Benutzer-Namen zu, die dabei von der Namensverwaltung auf System-Namen abgebildet werden.
Abbildung 2.1: Namen auf verschiedenen Ebenen eines verteilten Systems
Nicht immer ist die Transparenz soweit realisiert, daß für den Anwender im Gesamtsystem nur ein einziger globaler Namensraum sichtbar wird. Viele Systeme verwalten für Namen von Objekten verschiedener Eigenschaften und Systemebenen separate Namensräume.
In verteilten Systemen findet sich eine Vielzahl adressierbarer Objekte unterschiedlichster Eigenschaften. Das Spektrum benannter Objekte reicht von globalen logischen Gruppierungen über Netzwerke bis zu einzelnen Variablen:
Netzwerke, Zonen, Cluster, Knoten, Sockets, Ports, Server,
Dienste, Devices, Ressourcen, Schnittstellen, Hauptspeicherbereiche, Dateisystemobjekte,
Prozesse, Umgebungsvariablen, Benutzer und Benutzergruppen, Kommunikationswege
und -objekte, Mailboxen, Peripheriegeräte, Drucker, Tastatur, Maus,
Grafikfenster, …
In diesem Spektrum existieren Objekte mit unterschiedlicher Lebensdauer, Zugriffseffizienz und Verfügbarkeit. Diese und weitere Objekteigenschaften beeinflussen das Verhalten der Namensverwaltung wie folgt:
· Lebensdauer von Objekten: Informationen über langlebige Objekte sollten im System einen höheren Replikationsgrad aufweisen als Informationen über kurzlebige Objekte, die oft nur lokalen Charakter besitzen. Die Anforderungen an die Zugriffszeit über Namen sind um so höher, je kurzlebiger die referenzierten Objekte sind.
· Zugriffsfrequenz: Die Frequenz des Zugriffs über den Namen auf ein Objekt muß bei der Namensgebung und der Plazierung des Namens im Namensraum und in den Namensverwaltern Berücksichtigung finden. Je häufiger auf ein Objekt zugegriffen wird, desto effizienter[AL3] muß die Abbildung des Namens auf die Ortsinformation sein.
· Granularität von Objekten: Sie ist eng verbunden mit der Lebensdauer von Objekten. Große Objekte sind in der Regel langlebig, während kleinere Objekte oft nur temporär existieren.
· Relative Entfernung: Objekte lassen sich in entfernte und nahe Objekte einordnen[1]. Die mittlere, relative Entfernung der Objekte zueinander bestimmt den Grad der Verteilung im System. Je näher Objekte zueinander plaziert sind, desto kürzer sollten die relativen Namen sein. Diese Forderung ist jedoch nur zu erfüllen, wenn Namen Ortsinformationen enthalten.
· Mobilität: Mit der physikalischen Lokation ändert sich auch die Adresse eines Objekts[AL4]. Eine Lokationsänderung von Objekten impliziert zwar nicht in jedem Fall eine Namensänderung, je nach Art der Namensabbildung werden jedoch entweder Anpassungen der Namens- oder der Adreßtabellen erforderlich (vgl. Abschnitt 1.2.2 und Abschnitt 2.4.5).
· Replikationsgrad: Zur Steigerung der Verfügbarkeit (Zugriffszeit, Ausfallsicherheit) werden in verteilten Systemen häufig Objekte repliziert. Sofern die Objektverwaltung nicht bereits Replikationstransparenz bietet, muß die Namensverwaltung Replikationen berücksichtigen.
Objekte in verteilten Systemen können verschiedenen Systemebenen zugeordnet werden. Dabei werden die Objekte unterschiedlicher Systemebenen häufig in autonomen Namensräumen benannt. Eine Klassifizierung der Systemebenen [Autenrieth, 90] und der zugehörigen Namensräume zeigt Abbildung 2.2.
Abbildung 2.2: Ebenen eines verteilten Systems
Innerhalb dieser Systemebenen können Aspekte der Zugriffseffizienz, des gesicherten Wachstums, der Zuverlässigkeit und der Sicherheit ihre individuelle Ausprägung finden:
· Die verteilungsunabhängigen, objektinternen Namen (z.B. für Variablen, Datenstrukturen, Methoden, Instanzen) der Intraprogrammebene nehmen in der Namensverwaltung eine Sonderstellung ein, da ihre Bindungen zu Objekten statischen Charakter haben und nur zum Zeitpunkt der Übersetzung, des Bindens oder des Ladens hergestellt werden. Diese Bindungen werden über programminterne oder allgemeine Vereinbarungen wie Header- bzw. Include-Dateien bereitgestellt.
· Die Interprogrammebene mit systemspezifischen Identifikationen (z.B. für Ports, Prozesse, Dateien, Objekte) enthält die Umgebungsvariablen von Programmen. Namen dieser Ebene können gezielt zur Abstraktion eingesetzt werden. Dabei lassen sich die Vorzüge der indirekten Interprozeßkommunikation über Ports mit den Effizienzvorteilen der direkten Kommunikation verbinden, indem logisch indirekt über Namen, physikalisch jedoch direkt über assoziierte Systemidentifikationen kommuniziert wird.
· Auf der Objektverwaltungsebene mit Namen objektverwaltender Dienste (z.B. Knoten, Server) sind Objekte zusammengefaßt, die unter der gemeinsamen Verwaltung sog. Objektmanager stehen (z.B. Verzeichnisse oder Dateien unter der Verwaltung eines Dateiservers, Funktionen und Daten eines Gerätetreibers oder auch Verzeichnisse eines Namensverwalters).
· Objekte der Administrativebene mit administrativen Namen (z.B. für Zonen) gehören zum Einflußbereich organisatorischer Einheiten (z.B. Netzwerke, Firmen, Forschungsinstitute und Verwaltungen) und enthalten die Namen untergeordneter Abteilungen und Verwaltungsstrukturen. Einer solchen logischen Zuordnung unterliegt häufig gleichzeitig die Anbindung an ein gemeinsames Teilnetzwerk (Ethernet, Tokenring o.ä.). Administrative Verzeichnisse können hierarchisch angeordnet sein, wobei ihre Einträge auf Verzeichnisse der Objektverwaltungsebene oder untergeordneter Administrativebenen verweisen.
· Die Globalebene mit globalen Namen, die den Verbund organisatorischer Einheiten und Gruppierungen angeben (Netzwerk), faßt Objekte zusammen, die unabhängige Organisationen oder Organisationsgruppen repräsentieren. Namen für Objekte der Globalebene besitzen eine große Stabilität, d.h. die Bindungen zu Objekten unterliegen kaum Änderungen. Die Verfügbarkeit globaler Verzeichnisse ist wichtig, jedoch für den Betrieb eines verteilten Systems nicht elementar, da das System im administrativen Bereich weiter funktionsfähig bleibt und nur Funktionseinbußen in der globalen Kommunikation erleidet.
Unabhängig von Struktur und Eigenschaften können die Namen dieser Systemebenen anhand ihres Verteilungsgrads wie folgt lokalen oder globalen Namensräumen zugeordnet werden:
· Lokale Namensräume enthalten verteilungsunabhängige, objektinterne Namen für knoteninterne Objekte der Intraprogrammebene und Basisnamen für Objekte der Interprogrammebene.
· Globale Namensräume enthalten Namen für Objekte der Objektverwaltungsebene, der Administrativebene und der Globalebene, die den Verbund organisatorischer Einheiten und Gruppierungen angeben.
Lokale und globale Namensverwaltungen enthalten Namen für Objekte unterschiedlicher Granularität, Lebensdauer und Mobilität. Hierin sind die differenzierten Anforderungen an die Skalierbarkeit und Effizienz begründet.
Betriebssysteme identifizieren Objekte durch eindeutige Bezeichner und Adressen. Diese sind für Protokolle wesentlich einfacher zu handhaben als Namen. Dem Anwender hingegen prägen sich Bezeichner und Adressen wegen der fehlenden Assoziation mit realen Gegenständen und der schlechten Mnemonik nur schwer ein. Sie sollten daher an der Benutzer-Schnittstelle nicht in Erscheinung treten.
Protocols
Use Addresses, People Prefer Names
Namen leisten für den Benutzer die Abstraktion vom Objekt. Der Anwender eines Systems arbeitet ausschließlich mit symbolischen Benutzer-Namen. Diese sind in der Regel syntaktische Namen, deren Struktur sich gut einprägt und ihm den Umgang mit dem System erleichtert.
In Betriebssystemen existieren verschiedene Sichten auf Objekte, die Systemsicht und die Benutzersicht. Je nach Sicht werden Objekte durch Benutzer-Namen oder System-Namen identifiziert. Der Begriff „Name“ wird dabei nicht im engen Sinne nur für symbolische Benutzer-Namen verwendet, sondern auch für Identifikation von Objekten auf allen Systemebenen. Benutzer-Namen existieren an der Benutzerschnittstelle zum System (vgl. Abbildung 2.1) in Form beliebig langer Zeichenketten mit eigener Syntax und Semantik. Ein System-Name ist ein eindeutiger Bezeichner, der dem System die Handhabung von Objekten erleichtert und in Form von Zeichenketten, Bitstrings oder Integers auftritt. System-Namen treten für Benutzer eines Systems nicht in Erscheinung.
Definition: Objekt-Bezeichner, Objekt-Identifikation (OID)
Objekt-Bezeichner sind System-Namen, die Objekte eindeutig in Zeit und Raum identifizieren. Die Menge der erzeugten Objekt-Bezeichner I ist potentiell unendlich und stets gleich mächtig wie die Menge der existierenden Objekte O.
Auf der Ebene der System-Namen koexistieren u.U. mehrere Namensräume unterschiedlicher Ausprägung. System-Namen, die relativ zu einem physikalischen Namensraum aufgelöst werden, sind als physikalische Namen oder Adressen bekannt. Aus der Adresse eines Objekts wird eine konkrete Lokation und gegebenenfalls ein Pfad ( Route) zu dieser Lokation ermittelt.
Benannte Objekte treten in verteilten Systemen auf unterschiedlichen Systemebenen auf. Die hohe Mobilität, Dynamik und Diversität der benannten Objekte stellt erhebliche Anforderungen an die Verwaltung von Namen.
Die vorliegende Arbeit beschäftigt sich mit der globalen Verwaltung von Benutzer-Namen. Diese wird maßgeblich beeinflußt von der syntaktischen Beschaffenheit und den Eigenschaften der verwalteten Namen. Der nachfolgende Abschnitt kategorisiert daher Benutzer-Namen anhand ihrer syntaktischen Struktur, beschreibt ihre Eigenschaften und diskutiert verschiedene Formen der Skalierung von Namensräumen.
Namenskonventionen sind Regelungen zur Benennung von Objekten. Ein Namensraum ist als Menge von Namen definiert, die einer gegebenen Namenskonvention entsprechen [Terry, 86].
Definition: Namenskonvention
Eine Namenskonvention X bestimmt durch syntaktische und semantische Regeln, wie ein gültiger Name aufgebaut ist.
Definition: Namensraum (Name Space)
Der Namensraum N ist die Menge aller gültigen Namen, die eine Namenskonvention erfüllen.
Namenskonventionen können strukurierte oder unstrukturierte Namen beinhalten:
Unstrukturierte Namen sind wahrscheinlich die einfachste Namenskonvention, da sie keine vorherrschende oder konsistente Struktur aufweisen. Gewöhnlich bilden unstrukturierte Namen einen flachen, homogenen Namensraum.
Strukturierte Namen andererseits weisen eine syntaktische Partitionierung in Teilnamen
auf. Ein strukturierter Name muß nicht notwendigerweise syntaktisch erkennbar
sein; die Struktur kann durchaus algorithmisch definiert werden. Namen, die
nach syntaktischen Regeln aufgebaut sind, werden auch als syntaktische Namen bezeichnet. Besteht ein strukturierter Name aus einer Menge von
Attributen, so wird er als attributierter
Name bezeichnet,
andernfalls als nicht-attributierter Name. Die Reihenfolge, in der die
Attribute angegeben sind, muß dabei jedoch nicht notwendigerweise eine Ordnung
auf den Attributen definieren.
Abbildung 2.3: Arten von Benutzer-Namen
Die gebräuchlichste Organisationsform von Namen sind hierarchische, baumartige Namensräume. Diese korrelieren vielfach mit der organisatorischen oder geographischen Verteilung von Informationen. Derartige Namensräume unterstützen die dezentrale Namensverwaltung, da lokale Änderungen keinen Einfluß auf den gesamten Namensraum haben.
Abbildung 2.4: Arten von Namensräumen
Strukturierte Namen können auch Namensräume in Form zyklischer oder azyklischer gerichteter Graphen bilden. Im Gegensatz zu Bäumen besteht in azyklischen gerichteten Graphen die Möglichkeit, daß Knoten mehrere Namen besitzen. In der Praxis werden azyklische Namensräume häufig durch das Einfügen sog. „soft links“ realisiert. In zyklischen gerichteten Graphen ist die Ordnung des Graphen nicht signifikant. Nicht alle Kanten müssen spezifiziert sein, um ein Objekt zu identifizieren. Diese Art von Namensraum ist für attributierte und generische Namen gebräuchlich und bietet die Möglichkeit zur Suche mit unvollständigen Namensangaben. Eine derartige Suchmöglichkeit in einem zyklischen gerichteten Graphen erhöht die Benutzerfreundlichkeit des Systems [White, 84], ist allerdings sehr zeitaufwendig.
Benutzer-Namen existieren in Form von Zeichenketten mit eigener Syntax und Semantik. Anhand des Einflußes ihrer syntaktischen Struktur auf die Interpretation der Namen werden flache, partitionierte, hierarchische und attributierte Namen unterschieden.
Die einfachsten denkbaren Benutzer-Namen sind
flache Namen[2]. Sie bestehen aus einer unstrukturierten Folge beliebiger Zeichen und
entsprechen Wörtern einer Sprache N über einem endlichen Alphabet von Symbolen .
Der durch flache Namen erzeugte Namensraum zeichnet sich durch
seine Einfachheit aus. Ein flacher Namensraum enthält eine oder mehrere
Namensformen, wobei seine Elemente den von diesen Namensformen erfaßten
Symbolfolgen entsprechen.
Aus der Sicht der Namensverwaltung werden flache Namen als syntaktische Atome betrachtet, da sie nicht weiter aufgelöst werden können. Das heißt nun aber nicht, daß flache Namen keine ausgeprägte syntaktische Struktur besitzen können. Die Strukturierungsmöglichkeiten flacher Namen sind vielfältig. Allerdings kommt den einzelnen Strukturelementen bei der Interpretation von Namen keine Bedeutung zu. In der Regel finden flache Namen als absolute Namen Verwendung. Da sie keinerlei Ortsinformationen enthalten, erfordert die Migration gebundener Objekte keine Anpassung des Namens.
Für große verteilte Systeme sind flache Namensräume ungeeignet, da sie die verteilte Namensverwaltung in keiner Weise unterstützen. Bei der Vergabe flacher Namen muß die Eindeutigkeit systemweit geprüft werden, indem sie gegen jeden existierenden Namen im flachen Namensraum getestet werden. Da Ortsinformationen in flachen Namen fehlen, besitzt ein Namensverwalter keinerlei Hinweise, wo ein gegebener flacher Name letztendlich verwaltet wird[3]. Namensverwalter müssen daher entweder den gesamten Namensraum verwalten oder zumindest über Informationen verfügen, welche Namensverwalter an der Verwaltung des Namensraums beteiligt sind. Da beide Methoden einen hohen Kommunikations- und Speicheraufwand erfordern, sind flache Namensräume nicht beliebig skalierbar.
Weiter ist zu berücksichtigen, daß für Menschen flache Namen nur dann einprägsam sind, wenn sie Wörtern einer natürlichen Sprache entsprechen. In flachen Namensräumen wird es daher mit steigender Anzahl von Namen zunehmend schwieriger, eindeutige und gleichzeitig aussagekräftige Namen zu finden (vgl. hierzu auch Tabelle 1.1). Eine weitere Qualifizierung der Namen ist somit dringend erforderlich[AL5].
Durch die Kombination flacher Namensräume entstehen partitionierte Namen. Sie können als Folge primitiver Namen betrachtet werden, die jeweils durch einen Separator getrennt sind. Der partitionierte Namensraum kann in disjunkte Bereiche zerlegt werden, die sogenannte Domains, Subdomains, Subsubdomains, usw. bilden.
Anhand der Partitionierung des Namensraums unterscheidet man:[V6]
· Physikalisch partitionierte Namensräume, die Ortsangaben enthalten, so daß aus dem Namen sofort auf die Lokation des benannten Objekts geschlossen werden kann. Physikalisch partitionierte Namensräume erweisen sich jedoch besonders bei der Umorganisation als inflexibel. (z.B.: name@lokation)
· Organisatorisch partitionierte Namensräume, die Namen nach der Zugehörigkeit zu organisatorischen Einheiten gruppieren. Sie unterstützen die dezentrale Namensverwaltung unterhalb des die Organisation bezeichnenden Kontextes. Bei gegenseitigem Mißtrauen wird jedoch ein entsprechender Schutzmechanismus der eigenen Präfixes/Suffixes erforderlich. (z.B.: vs.informatik.uni-ulm.de)
· Logisch partitionierte Namensräume, die anhand der Semantik der Namensteile oder des Typs der benannten Objekte partitioniert sind. Logische Namen besitzen keinen direkten Bezug zu einer physikalischen Lokation oder organisatorischen Einheit. (z.B.: aida.verdi.oper.music)
Enthalten Namen keine Abhängigkeiten von der darunterliegenden physikalischen Konfiguration, so werden sie auch als pure Namen bezeichnet. Unpure Namen enthalten Ortsinformationen und müssen daher bei der Relozierung von Objekten entsprechend aktualisiert werden.
Partitionierte Namen sind immer an einen Kontext gebunden, der ihren Gültigkeitsbereich beschreibt. Kontexte können verschachtelt sein (nested context) und Namen können in mehreren Kontexten vorkommen.
Definition: Kontext
Ein Kontext Y ist eine Partition eines Namensraums, die durch die syntaktische Struktur der Namen oder durch eine Gruppierungs- oder Abbildungsvorschrift definiert wird.
Kontexte werden explizit durch die Struktur der Namen definiert oder implizit durch eine Abbildungsvorschrift, die kein Teil des Namens ist. Implizite Kontexte treten bei der Auflösung von Namen nicht in Erscheinung. Sie werden zuvor entweder durch den Prozeß der Namensauflösung oder durch den Benutzer gesetzt.
Eine Teilmenge der partitionierten Namen[AL7] sind die hierarchischen Namen, wie sie in vielen bekannten Systemen verwendet werden. Die Komponenten hierarchischer Namen besitzen im Gegensatz zu partitionierten Namen eine strenge Ordnung. Hierarchische Namen sind syntaktisch strukturiert. Sie bestehen aus einer geordneten Folge primitiver Namen und werden anhand einer Interpretationsvorschrift bei der Namensauflösung wieder in eine solche zerlegt. Ein vollständiger hierarchischer Name eines Objekts kann sich dabei aus der Bezeichnung eines Kontextes, die sich selbst wieder aus primitiven Namen zusammensetzt, und dem Objektnamen relativ zu diesem Kontext konkatenieren.
Hierarchische Namen aus Objekt- und Kontextbezeichnung
spannen einen hierarchischen Namensraum auf.
Hierarchische Namensräume lassen sich als gerichteter Graph darstellen. Die Knoten in diesem Graphen stellen benannte Objekte oder Kontexte dar. Namen werden an den Kanten des Graphen angetragen. Benannt werden also nicht die Objekte selbst, sondern die Beziehungen zwischen den einzelnen Kontexten und Objekten.
Abbildung 2.5: Die hierarchische Strukturierung eines Namensraums mit disjunkten Kontexten
Die Beschreibung eines hierarchischen Namensraums in Form eines gerichteten Graphen aus Abbildung 2.5 kann beispielsweise als regulärer Ausdruck wie folgt dargestellt werden:
Wurzel = {(uni-ulm{(med), (math), (info{(dbis, vs)}) }), (daimler{(Mercedes), (AEG)})}
Die Baumstruktur eines hierarchischen Namensraums definiert eine Folge von Mengeninklusionen. Alle Kontexte und Objekte eines Teilbaums sind in dem Kontext enthalten, aus dem der Teilbaum hervorgeht. Objekt-Eigenschaften, die mit dem Namen eines Kontexts assoziiert werden, vererben sich an alle im Teilbaum enthaltenen Objekte. Dieser Umstand motiviert die Darstellung hierarchischer Namensräume als Mengendiagramme. Verschachtelte Kontexte werden hierbei als Inklusionen von Mengen dargestellt. Disjunkte Mengen repäsentieren Kontexte derselben Hierarchiestufe (vgl. Abbildung 2.6).
Abbildung 2.6: Darstellung eines hierarchischen Namensraums als Mengendiagramm
Hierarchische Namensräume unterstützen die Untergliederung der Namensverwaltung zur Bewältigung der unterschiedlichen Erfordernisse, wobei die Lebensdauer von Objekten ein wesentliches Strukturierungsmerkmal vorgibt. Ebenen mit Namen langlebiger Objekte liegen dabei in der Hierarchie typischerweise höher als die kurzlebiger Objekte. Die Quantität der Objekte einer bestimmten Eigenschaft korreliert ebenfalls mit der Hierarchiestufe im Namensraum. Je weiter oben im hierarchischen Namensraum eine Eigenschaft repräsentiert ist, desto mehr Objekte erben diese Eigenschaft.
Hierarchische Namen haben sich als fundamentales und nützliches Prinzip zur Strukturierung von Informationen erwiesen. Für Anwender, die vor die Aufgabe gestellt sind, eine große Menge diverser Objekte zu organisieren, ist es nichts ungewöhnliches, diese in eine hierarchische Struktur einzuordnen. Hierarchische Anordnungen sind schließlich u.a. die Basis zahlreicher wissenschaftlicher Klassifikationen. Hierarchische Datenmodelle wurden bereits von frühen Datenbanksystemen (IMS, [McGee, 77]) aufgegriffen und hierarchische Verzeichnisstrukturen bilden seit MULTICS [Daley, 65] den organisatorischen Rahmen für Dateisysteme. Hierarchische besitzen gegenüber flachen Namensräumen folgende Vorteile:
· Hierarchische Namen erlauben das Delegieren der Zuständigkeiten für Teile des Namensraums. Somit können wesentlich mehr Namen verwaltet werden, ohne die Überlastung einer zentralen Instanz zu verursachen.
· Durch die hierarchische Organisation wird die Abkapselung von Namensräumen möglich, so daß die Namensverwaltung für jede Ebene individuell zugeschnitten werden kann. Jeder Unterbaum im hierarchischen Namensraum kann wiederum als vollwertiger Namensraum betrachtet werden, in dem strukturelle Veränderungen nicht an den übergeordneten Namensraum propagiert werden müssen.
· Sie ermöglichen die autonome Vergabe von Namenskomponenten durch Autoritäten, die wieder anderen Autoritäten untergeordnet sind.
· Namen müssen nur innerhalb des jeweiligen Kontextes eindeutig sein und sind daher einfacher zu erzeugen.
· Die Namensauflösung kann effizient gestaltet werden, indem sie der hierarchischen Struktur des Namensraums angepaßt wird.
· Hierarchische Namensräume ermöglichen eine Verteilung der Namensinterpretation auf verteilte Instanzen, die dann meist mit den genannten Autoritäten zusammengefaßt werden. Jede Instanz vertritt dabei einen oder mehrere Kontexte.
· Hierarchische Namensräume können an beliebiger Stelle miteinander verbunden werden und erlauben ein Wachstum des Namensraums (Skalierung) in alle Richtungen (vgl. Abschnitt 2.2.4). Die Extraktion und das Anfügen hierarchischer Namensräume sind die Basis der Konstruktion großer verteilter Namensräume.
Trotz der aufgezeigten Vorteile sind einige gravierende Nachteile streng hierarchischer Namensräume nicht zu übersehen:
· Werden hierarchische Namensräume verwendet, um die Eigenschaften von Objekten zu beschreiben, so besteht das Problem, im hierarchischen Namensraum Objekte zu unterstützen, die alle bis auf eine übergeordnete Eigenschaft besitzen.
· Es ist schwierig, logisch unabhängige oder nicht-kontext-beschränkte Informationen in hierarchische Namensräume aufzunehmen.
· Die hierarchische Organisation von Namen etabliert subjektive Sichten auf die verwalteten Objekte, die nur eine bestimmte Form von Abfragen erlauben[4]. Die Reihenfolge, in der Namensteile angegeben werden müssen, ist daher signifikant.
· Die vollständige Beschreibung der Eigenschaften eines Objekts durch hierarchische Namen führt zu sehr langen Namen und tiefen Verschachtelungen, die schwer handhabbar sind.
· Die Kontextabhängigkeit der Namen erschwert die Suche nach generischen Namen. Dieselben Namensteile und Eigenschaften treten u.U. in mehreren Unterbäumen auf, wodurch die generische oder attributierte Suche aufwendiger wird, da alle Teilbäume traversiert werden müssen.
· Sind hierarchische Namen bezüglich physikalischer, geographischer oder organisatorischer Strukturen organisiert, so ist es schwierig, Objekte zu relozieren, ohne sie umzubenennen.
Die hier angeführten Nachteile lassen sich abschwächen, indem die strenge Hierarchie aufgelöst und in mehrere Teilbäume aufgebrochen wird. Diese Teilbäume werden so miteinander verbunden, daß ein Graph entsteht. Ansätze hierzu zeigen die folgenden Abschnitte. Weitgehende Freiheiten zur Beschreibung von Objekten durch Namen bieten generische und attributierte Namen, die in den folgenden Abschnitten behandelt werden. Besonders bei der logischen Partitionierung von Namensräumen sind attributierte Namen vorteilhaft.
Soll eine Menge von Objekten durch Namen identifiziert werden, so geschieht das durch generische Namen. Zur Beschreibung generischer Namen wird die Syntax strukturierter Namen um Symbole erweitert, die repräsentativ für beliebige Zeichen und Namensteile stehen. Generische strukturierte Namen setzen sich aus primitiven Namen und Platzhaltern (Wildcards) zusammen. Primitive Namen können ihrerseits generisch sein und Platzhalter enthalten.
Als Platzhalter oder Wildcard für ein beliebiges Zeichen innerhalb eines primitiven Namens steht beispielsweise ein Stern "*", wie er auch von anderen Systemen (z.B. MS-DOS) bekannt ist. Ein primitiver generischer Name besitzt dann folgende syntaktische Beschreibung:
Beliebige Namensteile in strukturierten Namen können durch ein Fragezeichen "?" repräsentiert werden, so daß ein strukturierter generischer Name folgender syntaktischen Beschreibung genügt:
Sowohl der Platzhalter für beliebige Zeichen innerhalb eines Namens als auch derjenige für beliebige Namen innerhalb eines strukturierten Namens kann in beliebiger Wiederholung auftreten. Die Anzahl der Repetitionen wird durch einen Bereich spezifiziert, der in spitzen Klammern „< >“ angegeben wird und im Anschluß an den Platzhalter folgt. Eine beliebig häufige Wiederholung wird durch einen offenen Bereich gekennzeichnet.
Dem generischen Namen "Universit*<1,3>" entsprechen beispielsweise die Namen "Universität", "University" oder "Universitaet". Das nachfolgende Beispiel für einen generischen Namen kann z.B. alle Einrichtungen der Universität Ulm erfassen, die einen WWW-Dienst offerieren.
/uni.ulm.?<1,2
>.www
Der Platzhalter "?<1,2 >" läßt beispielsweise die Optionen "informatik.dbis", "informatik.vs" oder "rz" zu. Platzhalter für Zeichen und primitive Namen können in strukturierten Namen auch in Kombination auftreten.
Die soeben beschriebenen generischen Namen weisen Ähnlichkeiten mit deskriptiven oder attributierten Namen auf, da diese ebenfalls flexible Namensanfragen erlauben. Den Besonderheiten attributierter Namen wendet sich der nachfolgende Abschnitt zu.
Die Bindung von Namen an Objekte kann einer willkürlichen Zuordnung entsprechen. Namen müssen daher keine erfahrbaren Eigenschaften eines Objekts repräsentieren. Zusätzlich zum Namen existieren über Objekte weitere Informationen, die ihre Charakteristika beschreiben und zur Identifizierung eines Objekts herangezogen werden können.[AL8]
Die Beschreibungsinformationen für Objekte lassen sich in Hinblick auf den Verwendungszweck in vier Kategorien unterteilen[5]:
• Merkmalsinformationen sind für ein Objekt spezifische Merkmale, die ein hohes Maß an Stabilität besitzen und i.d.R. für die gesamte Lebensdauer dem Objekt erhalten bleiben.
• Zustandsinformationen sind kurzlebige Informationen, deren Änderungsrate die Abfragerate übertrifft. Sie werden nicht als Attributwert abgelegt, sondern zum Abfragezeitpunkt aktuell ermittelt.
• Zugangsinformationen enthalten die für den Objektzugriff notwendigen Informationen. Hierzu zählen u.a. Objekt-Bezeichner und Zugriffsrechte auf Objekte.
• Verwaltungsinformationen dienen den operationellen Erfordernissen der Verwaltung von Objekten (z.B. Zeitstempel und Zugriffsrechte).
Die Beschreibung der Eigenschaften von Objekten erfolgt durch typisierte Attribute mit einem bestimmten Wertebereich. Alle oder einzelne dieser Attribute eines Objekts können verwendet werden, um als Komponenten eines attributierten Namens ein Objekt zu identifizieren. [AL9]
Attributierte oder deskriptive Namen bestehen aus einer Folge von Attributen in Form von typisierten Attribut/Wert-Paaren, die für ein Objekt zutreffen und es beschreiben. Die Bezeichnung „Folge“ impliziert bereits, daß eine Ordnung unter den Attributen existieren kann. Die Flexibilität attributierter Namen wurde insbesondere durch Bowman und Peterson [Bowman, 90a] eingehend dargelegt. Einen deskriptiven Namen bilden z.B. folgende Attribut/Wert-Paare:
(Farbe:grün) (Größe:groß) (Form:rund)
Die Darstellung attributierter Namen kann in Form von Tabellen erfolgen [Sechrest, 92]. In den Spalten der Tabelle werden dabei die Attributtypen und in den Zeilen die Werte der Attribute für die Objekte angetragen. Ein Beispiel für die Beschreibung von Objekten anhand diskreter Attribute gibt Abbildung 2.7.
Abbildung 2.7: Tabellendarstellung orthogonaler Attribute
Attributetypen in Abbildung 2.7 sind die Farbe, die Größe und die Form eines Objekts. Attributwerte sind z.B. rot, klein und rund. Eine äquivalente Darstellung für attributierte Namensräume sind Mengendiagramme [Hauzeur, 86]. Die Identifizierung von Objekten erfolgt durch den Schnitt von Objektmengen gleicher Attribute (vgl. Abbildung 2.8).
Abbildung 2.8: Mengendarstellung orthogonaler Attribute
Wie bereits erwähnt, bestehen attributierte Namen aus einer Folge von Attributen. Die Attribute eines Objekts wiederum werden als Tupel aus Attributtyp und Attributwert definiert:
Attribut
:= (Attributtyp: {Attributwert})
Attributierter
Name := {Attribut1 … Attributn}
Attributtypen sind einfache Zeichenketten, die ein Attribut typisieren. Sie haben vornehmlich die Aufgabe, den Benutzer über die Bedeutung des Attributwerts zu informieren und in der Datenbank die Relation zu benennen. Ferner wird durch den Attributtyp der Wertebereich eines Attributs bestimmt. Daher muß zu jedem Attributtyp der zugehörige Wertebereich spezifiziert werden. Teil einer solchen Spezifikation ist zum einen die Beschreibung des Wertebereichs und zum anderen eine Auswertungsfunktion, die die Ordnung zwischen den Werten definiert. Die Auswertungsfunktion kann bei Basistypen in der Namensverwaltung integriert sein oder gesondert definiert werden. Bei der Auswertung lassen sich diskrete und kontinuierliche Attributwerte unterscheiden.[AL10]
Attribute können einfache oder mehrfache Attributwerte besitzen. Einwertige Attribute umfassen immer nur einen Wert, mehrwertige hingegen ein Wertemenge. Der subtile Unterschied liegt in der Behandlung der Einfügeoperation. Während das Einfügen in eine Menge den Wert ergänzt, wird der Wert einer einelementigen Menge ersetzt.
(Farbe:grün) (Größe:groß) (Form:(rund) (eckig))
Für den Anwender verfügbare Objektinformationen sind in expliziten Attributen abgelegt. Zugangs- und Verwaltungsinformationen der Namens- und Objektverwaltung werden in impliziten Attributen geführt. Auch für Attributeinträge sind Zugangs- und Verwaltungsinformationen erforderlich, die ebenfalls als implizite Attribute angelegt werden können. Die Sichtbarkeit von Attributen für den Anwender kann durch attributspezifische Zugangsinformationen flexibel gehandhabt werden.
Unter den Attributen eines Objekts lassen sich identifizierende Attribute definieren. Diese kennzeichnen ein Objekt eindeutig und sind zwingend für ein Objekt anzugeben. Während für beliebige Attribute keine Eindeutigkeit vorliegen muß, erfordern identifizierende Attribute operationelle Maßnahmen zur Gewährleistung der Eindeutigkeit. Identifizierend für ein Objekt kann beispielsweise ein willkürlich gesetzter Name oder der Objekt-Bezeichner sein.
Die Werte eines Attributs können statisch zugeordnet sein oder sich dynamisch ändern. Statische Attributwerte dienen der Objektbeschreibung und werden nur explizit geändert. Dynamische Attributwerte enthalten Zustandsinformationen, die einer stetigen Änderung unterworfen sind. Aus Aktualitätsgründen werden diese erst zum Zeitpunkt der Anfrage ermittelt.
Anstelle von Zeichenketten können als Werte reguläre Ausdrücke angegeben werden. Hierdurch kann ein endlicher Wertebereich spezifiziert werden, der alternative Schreibweisen oder gebräuchliche Abkürzungen berücksichtigt. Hinsichtlich einer vertiefenden Diskussion dieser Repräsentationsmöglichkeiten wird auf die Arbeiten von Peterson [Peterson, 88a] und Bowman [Bowman, 90a] verwiesen.
Attributierte Namen können unvollständig sein, zum einen weil sie vom Benutzer nicht exakt spezifiziert wurden, zum anderen aus verwaltungstechnischen Gegebenheiten[AL11] der Datenbank. Dieser Umstand motiviert die Einführung von Präferenzen [Bowman, 90a], die verschiedene Qualitäten von Attributen bezeichnen. Präferenzen dienen bei der Auflösung von Namen dazu, bestimmten Attributen oder Attributwerten ein höheres Gewicht zu verleihen als anderen. Objekte, die durch eine Menge von priorisierten Attributen beschrieben sind, werden bevorzugt ausgewählt. Präferenzen können als Meta-Attribute[AL12] der internen Repräsentation eines Attributs verstanden werden. Verschiedene Präferenzen dienen lediglich Administrationszwecken und sind für den Benutzer nicht sichtbar. Andere wiederum können entweder bereits bei der Registrierung in der Datenbank zu einem Attribut abgelegt oder bei der Auflösung eines attributierten Namens spezifiziert werden.
Attributpräferenzen lassen sich zu Klassen zusammenfassen [Bowman, 90b]. Innerhalb der Klassen besteht eine Ordnung der Attributpräferenzen, die die Bevorzugung von Attributen bei der Auflösung attributierter Namen regelt. Diese Klassen können in Benutzer- und in Datenbankpräferenzen eingeteilt werden.
• Benutzerpräferenzen sind für Benutzer bei der Spezifikation von Anfragen sichtbar. Hierzu zählt die Registrierungspräferenz, die angibt, ob ein Attribut optional oder obligatorisch registriert werden muß. Eine Suchpräferenz beeinflußt die Suchkriterien bei der Auflösung von Namen. Die Gültigkeitsdauer von Attributwerten wird durch die Änderungspräferenz (dynamisch oder statisch) beschrieben. Die Eindeutigkeitspräferenz gibt an, ob Attributwerte eindeutig sein müssen. Auch die Reihenfolge der Angabe von Attributen kann eine Präferenz bei der Auflösung von Namen darstellen.
• Datenbankpräferenzen sind für die Verwaltung von Attributen vorgesehen. So kann eine Auswahlpräferenz die Übereinstimmung von Attributen mit der gegebenen Beschreibung regeln. Entsprechend werden Objekte ausgewählt, deren Attribute eindeutig, exakt, partiell oder nur möglicherweise übereinstimmen. Eine Votierungspräferenz regelt die Exaktheit der ermittelten Objektbeschreibungen. Zeitpräferenzen geben Auskunft über die Aktualität der Einträge und priorisieren bei der Auswahl originale vor vorgehaltenen oder ungültigen Einträgen.
Ein mögliches Kriterium für die Auswahl von Einträgen stellt die Anzahl der Objekte dar, für die ein Attribut registriert wurde. Attribute, die für wenige Objekte zutreffen, können bevorzugt behandelt werden, da ihr Informationsgehalt höher ist als der anderer. Dieses Vorgehen ist insbesondere bei der verteilten Verwaltung von Namenseinträgen sinnvoll, wie sich in den nachfolgenden Kapiteln zeigen wird.[V13]
Eine typische Operation auf attributierten Namensräumen ist das Auflösen eines Namens in Form vorgegebener Attribut/Wert-Paare. Schnell wird klar, daß die Identifizierung von Objekten anhand von Attributen nicht notwendigerweise eindeutig ist. Dieselben Attribut/Wert-Paare können mehrere Objekte bezeichnen. Erst in Kombination mit identifizierenden Attributen wird die Eindeutigkeit erreicht. Die Auflösung deskriptiver Namen liefert entweder den vollständigen Satz von Attributen zurück, oder das Ergebnis wird auf eine Teilmenge der vorhandenen Attribute projiziert.
Attributierte Namen sind prädestiniert zur Identifizierung von Objekten anhand ihrer Eigenschaften. Ein inhärentes Problem bleibt jedoch die globale Verwaltung attributierter Namensräume. Hierarchische Namensräume eignen sich sehr viel besser für die verteilte Verwaltung, da die Position eines Namens im Namensraum bereits einen Hinweis auf den zuständigen Namensverwalter enthält.
Namen jeder Ausprägung tragen oft eine Bedeutung, die teilweise mit den Eigenschaften der benannten Objekte korreliert. Darüber hinaus besitzen Namen selbst bestimmte Eigenschaften, die Einfluß auf die Verwaltung von Namen besitzen.
Eine der Grundanforderungen, die an Namen gestellt werden, ist Eindeutigkeit. Der Bereich, in dem Namen bekannt und eindeutig sind, wird Gültigkeitsbereich eines Namens genannt. Namen können unterschiedliche Verbreitungsgrade aufweisen. Der Gültigkeitsbereich kann sowohl auf physische Bereiche, wie einzelne Rechner, Namensverwalter oder Netzwerkbereiche als auch auf logische und organisatorische Bereiche, wie Arbeitsbereiche, Benutzerumgebungen und Kontexte, beschränkt sein. Gültigkeitsbereiche erleichtern einerseits das Herstellen der Eindeutigkeit von Namen und erhöhen andererseits die Sicherheit im System.
Folgende Differenzierung der physischen Verteilung von Namen hat sich als geeignet erwiesen:
· Lokale Namen: Im einfachsten Fall werden Namen nur lokal registriert und verwendet. Eine Verteilung der Namenseinträge über Verwaltergrenzen hinaus findet dabei nicht statt, so daß sie außerhalb des lokalen Namensverwalters nicht bekannt sind.
· Verbundweite Namen: Besonders in Rechnerverbundsystemen ist es aufgrund des hohen Kooperationsgrades notwendig, Namen allen Knoten im Verbund zugänglich zu machen. Hierzu werden Namen entweder verbundweit propagiert oder ihre Gültigkeit auf bestimmte Namensverwalter beschränkt. Eine globale Verteilung von Namen ist hierbei weder wünschenswert noch erforderlich.
· Globale Namen: Vielfach müssen Objekte über Namen auch außerhalb des lokalen Knotens und Rechnerverbundes global zugänglich sein. Dazu werden Namen global eindeutig vergeben und so im Verwalternetz verteilt, so daß sie global aufgelöst werden können.
Abbildung 2.9: Inklusion von Namen
Die Menge der lokalen Namen ist dabei eine Obermenge der verbundweiten Namen und diese wiederum ist eine Obermenge, der global registrierten Namen. Die Beschränkung der Registrierung und Auflösung von Namen auf Gültigkeitsbereiche ermöglicht dem Anwender der Namensverwaltung, die Gültigkeit von Namen seinem Wirkungskreis und seinen Sicherheitsbedürfnissen entsprechend anzupassen. Weitreichende administrative Entscheidungen, wie die Auswahl des administrativen Namensverwalters für einen Namenseintrag oder die Zuweisung eines Segments des Namensraums zu einem Namensverwalter bleiben hierbei der Namensverwaltung vorbehalten. Die in dieser Arbeit vorgestellte dynamische globale Namensverwaltung plaziert entsprechend dem Gültigkeitsbereich eines Namens den zugehörigen Namenseintrag auf dem hierfür zuständigen Namensverwalter.
Neben den physischen existieren darüber hinaus auch logische Gültigkeitsbereiche in Form von Kontexten oder Benutzer- und Arbeitsbereichen. Hierarchische Namen dabei sind stets bezüglich eines Kontextes eindeutig, da Bindungen nur in gegebenen Kontexten existieren (vgl. Abbildung 2.10). Generische und attributierte Namen hingegen sind u.U. im gesamten Namensraum mehrdeutig, können jedoch durch Arbeitsbereiche eingeschränkt werden.
Entspricht der Gültigkeitsbereich dem gesamten Namensraum, dann wird ein Name als absoluter Name bezeichnet. Da absolute Namen häufig flache Namen sind und in bezug auf den globalen Kontext aufgelöst werden, sind sie migrationstransparent und sehr benutzerfreundlich.
absoluter Name =
Concat(Kontext-Name , „.“, relativer Name)
Entspricht der Gültigkeitsbereich des Namens n einer echten Teilmenge des gesamten Namensraums, dann wird er als relativer Name bezeichnet. Relative Namen beginnen, vorausgesetzt der Name kann im Kontext interpretiert werden, nicht mit dem Symbol für die Wurzel (z.B. „/“), sondern bestehen aus dem vollständigen globalen Namen abzüglich dem Namen des Kontexts, in dem der Name gültig ist (Präfix/Suffix). Die Interpretation relativer Namen erfolgt in Bezug auf einen Start-Kontext. Die Eindeutigkeit relativer Namen ist einfach zu gewährleisten, da sie jeweils nur im Kontext eindeutig sein müssen.
Abbildung 2.10: Kontextabhängigkeit eindeutiger hierarchischer Namen
Für das Verständnis der Mechanismen der dynamischen globalen Namensverwaltung sind die aufgezeigten Definitionen des Gültigkeitsbereichs und der Eindeutigkeit hinreichend. Eine formale Definition der Begriffe findet sich in [Comer, 89].
Eine primäre Eigenschaft von Namen ist ihre Lebensdauer. Hierbei wird zwischen kurzlebigen und langlebigen Namen unterschieden. Ungeklärt blieb bisher die Frage, wie weit die Lebensdauer eines Namens an die Existenz eines Objekts gebunden ist. Im einfachsten Fall kann die Existenz eines Namens in direktem Bezug zur Existenz des benannten Objekts stehen. Wird ein Name für die gesamte Lebensdauer (LT) einem Objekt zugeordnet, so handelt es sich um einen statischen Namen und es gilt:
Namen können Objekte durchaus überleben. Der Name ist dann im Laufe seines Lebens mehreren Objekten in chronologischer Folge zugeordnet. Die Existenz eines Namens ist nicht unmittelbar mit der Existenz einer Bindung für diesen Namen gleichzusetzen, d.h. ein gültiger Namen muß nicht unbedingt gebunden sein.
Existieren Objekte länger als die an sie gebundenen Namen, so spricht man von temporären Namen. Insbesondere Synonyme sind häufig nur kurzzeitig an Objekte gebunden. Die Existenz eines Objekts ist nicht notwendigerweise mit der Existenz eines Namens verbunden.
Die Überlegungen zur Existenz von Namen und Objekten motivieren die Frage, wann Namen eigentlich existieren. Mattes vertritt die Auffassung, Namen seien ein Betriebsmittel und lassen sich wie ein solches verwalten [Mattes, 91]. Durch Erzeugen und Aufgeben werden potentielle Namen und verfügbare Namen[AL14] ineinander übergeführt. Durch das Binden eines verfügbaren Namens an ein Objekt (Belegen) wird der Name gültig. Das Freigeben bei Aufhebung der Bindung macht den Namen erneut verfügbar (vgl. Abbildung 2.11).
Abbildung 2.11: Verwaltung von Namen als Betriebsmittel
Dieser These ist entgegenzuhalten, daß Namen nicht nur im Betriebssystem erzeugt, belegt und freigegeben werden, sondern der Benutzer mit einem Namen ein bestimmtes Objekt assoziiert. Diese Assoziation kann jedoch nicht im gleichen Maße freigegeben und erneut belegt werden wie ein Betriebsmittel.
Eine grundlegende Anforderung an Namensverwaltungen ist Skalierbarkeit. Voraussetzung hierfür ist, daß die Struktur von Namensräumen das Wachstum eines verteilten Systems berücksichtigt. Somit verbieten sich statische Strukturen, z.B. in Form fester Hierarchiestufen, die das Wachstum von Namensräumen limitieren. Verschiedene Arten des Wachstums lassen sich bei Namensräumen identifizieren:
· numerisch
· administrativ
· geographisch
Das numerische Wachstum eines Namensraums geht einher mit der Zunahme benannter Objekte und bewirkt normalerweise zunächst eine horizontale Ausdehnung des Namensraums. Erst wenn sich die Namensverwaltung oder der Anwender nicht mehr im Stande sieht, die Flut von Namen durch die horizontale Verbreiterung des Namensraums zu bewältigen, wird der Namensraum administrativ wachsen. Hierbei nimmt die Tiefe des hierarchischen Namensraums zu. Das geographische Wachstum eines Namensraums wird durch den Aspekt der Verteiltheit motiviert. Insbesondere das Verbinden lokaler Namensräume zu einem einheitlichen globalen Namensraum erfordert in verteilten Systemen besondere Aufmerksamkeit.
Frühe Namensverwaltungen unterstützten lediglich eine feste Anzahl von Hierarchiestufen des Namensraums (vgl. Grapewine und Clearinghouse in Anhang B). Ihr Wachstum war ebenso wie das Wachstum flacher und attributierter Namensräume auf die horizontale Ausdehnung beschränkt. Obwohl dieser Ansatz nicht beliebig skalierbar ist, genügte er doch den Anforderungen zur Verwaltung einiger tausend Namen. Insbesondere bestand die Schwierigkeit, mit zunehmender Anzahl benannter Objekte auf den jeweiligen Hierarchiestufen aussagekräftige und eindeutige Namen zu finden. Das horizontale Wachstum verursacht besonders bei der verteilten Auflösung generischer Namen hohe Kosten, da in breiten Namensräumen Anfragen eventuell an alle Verwalter untergeordneter Kontexte propagiert werden müssen.
Abbildung 2.12: Horizontales und vertikales Wachstum hierarchischer Namensräume
Die Zahl der Hierarchieebenen in baumartigen Namensräumen kann aus Gründen der Einfachheit fest sein. Dieser Ansatz skaliert jedoch nicht, denn je weniger Ebenen vorgesehen sind, desto schwieriger wird die Verteilung von Namen in einem globalen Netzwerk. Um ein administratives Wachstum zu ermöglichen, muß die Anzahl der Hierarchieebenen variabel sein. Namensräume wachsen zum Beispiel vertikal, wenn sie zur Bildung eines größeren Namensraums miteinander verbunden werden. Mit zunehmender Tiefe des Namensraums wird jedoch die Auflösung von Namen teurer, da mehr Resolutionsschritte notwendig werden.
Zur Benennung von Rechnerknoten reichen im allgemeinen zwei bis drei Hierarchieebenen aus; im Internet werden beispielsweise häufig drei Ebenen verwendet. Dabei ist dann eine 1:1-Zuordnung von Kontexten zu verwaltenden Instanzen möglich. Zur Benennung weiterer Objekte sind jedoch beliebig viele Ebenen wünschenswert; Dateien in einem verteilten Dateisystem können beispielsweise in Verzeichnissen mit beliebig vielen Hierarchiestufen abgelegt sein. In diesem Fall verwaltet aus Effizienzgründen eine Instanz meist mehrere Kontexte.
In verteilten Systemen stellt insbesondere das geographische Wachstum von Namensräumen eine Herausforderung dar. Die Konstuktion verteilter Namensräume wäre nicht denkbar, ohne die Möglichkeit lokale, autonome Namensräume durch verschiedene Mechanismen zu verbinden:
· Einführen einer neuen Dimension
· Mehrpunktverbindungen
· Einführen einer gemeinsamen Wurzel (super root)
· Montieren von Verzeichnissen
· Lokale Namensräume als Blätter eines globalen Namensraums
Der älteste Ansatz zum Verbinden autonomer Namensräume ist das Einführen einer zusätzlichen Dimension. Lokale Verzeichnisse werden durch ein orthogonales Verzeichnis von Knoten- oder Volume-Namen miteinander verbunden. Globale Dateinamen bestehen dann aus dem Knotennamen und dem lokalen Dateinamen. Dieser Ansatz ist daher kaum orts- jedoch weitgehend zugriffstransparent.
Eine weitere Möglichkeit zum Verbinden lokaler Namensräume sind Mehrpunktverbindungen (Multicast/Broadcast) (vgl. Abbildung 2.13). Die einzelnen Namensräume existieren gleichberechtigt nebeneinander und besitzen keine gemeinsame Wurzel. Sie werden implizit durch Broadcast-Nachrichten verbunden. Bei der Auflösung und Registrierung von Namen wird der für einen Namensraun zuständige Verwalter durch Broadcast-Nachrichten kontaktiert. Ein Vorteil dieses Verfahrens ist, daß keine externen Verweise verwaltet werden müssen. Broadcast-Verfahren sind jedoch i.a. sehr teuer und skalieren nicht. Ursache hierfür ist primär nicht die Anzahl der erforderlichen Netzwerknachrichten, sondern deren Bearbeitung. Jeder Netzwerkknoten muß die Broadcast-Nachricht bearbeiten, unabhängig davon, ob sie ihn betrifft oder nicht. Oftmals besitzt das Kommunikationsmedium auch keine Mehrpunktfähigkeit.
Abbildung 2.13: Methoden zum Vereinigen von Namensräumen
Die Konstruktion großer verteilter Namensräume wäre nicht möglich ohne die Fähigkeit, lokale Namensräume zu kombinieren. Eine verbreitete Methode, autonome Verzeichnisse in einer verteilten Struktur zu arrangieren, ist das Einführen einer gemeinsamen Wurzel (super root). Lokale Verzeichnisse werden hierbei orts- und zugriffstransparent unter der sogenannten super root zu einem Verzeichnis zusammengefaßt, das alle Unterbäume enthält. Super root-Einträge sind virtueller Natur und werden durch die Software-Schichten realisiert.
Eine der Eigenschaften des hierarchischen Namensmodells, die es für die Namensverwaltung so wertvoll machen, ist, daß die Wurzel einer jeden Hierarchie an jeden beliebigen Knoten einer anderen Hierarchie gebunden werden kann und so ein Konstrukt entsteht, das wiederum eine Hierarchie darstellt (Montieren). Formaler ausgedrückt, die Klasse der hierarchischen Namensräume ist abgeschlossen unter der Operation des Zusammenfügens.
Die Verwaltung lokaler Namensräume als Blätter hierarchischer globaler Namensräume (vgl. Abbildung 2.14) ist eine Verallgemeinerung des super root-Ansatzes. An den Blättern befinden sich flache, hierarchische oder auch attributierte Namensräume, die von der globalen Namensverwaltung autonom sind. Die unterschiedlichen Namensräume lassen sich oft durch einen syntaktischen Bruch in globalen Namen identifizieren (z.B.: hermes.informatik.uni-ulm.de/papers /naming/dns).
Abbildung 2.14: Lokale Namensräume als Blätter eines globalen Namensraums
Ein verbreiteter Ansatz zur Konstruktion knotenübergreifender Verzeichnisstrukturen ist das wechselseitige Montieren autonomer Namensräume. In Unterverzeichnissen sind hierzu Verweise auf entfernte Verzeichnisse angelegt (vgl. NFS), die lokal in sog. Mount-Tabellen gehalten werden. Das Montieren von Verzeichnissen bietet einen hohen Grad an Flexibilität in der Konfiguration. Da jeder Knoten seine eigene Verzeichnisstruktur besitzt, ist das Ziel der Ortstransparenz nur bedingt realisierbar. Durch das wechselseitige Montieren gemeinsam genutzter Bereiche kann jedoch eine einheitliche Verzeichnisstruktur erzeugt werden (vgl. Coda). Da jeder Punkt in einem „gemounteten“ Verzeichnis selbst wieder ein „Mount“-Punkt sein kann, impliziert der Ausfall eines Knotens das Verschwinden einer Menge von Unterverzeichnissen. Die Skalierbarkeit des Konzepts ist durch die Verwaltung der entfernten Verweise in Mount-Tabellen beschränkt.
Die Struktur und die Eigenschaften des Namensraums geben wesentliche Rahmenbedingung für den Entwurf einer dynamischen globalen Namensverwaltung vor.
Hierarchien bilden einen vergleichsweise restriktiven organisatorischen Rahmen. Datenbank-Designer haben bereits früh erkannt, daß ausschließlich hierarchische Strukturen nicht geeignet sind, um die komplexen Beziehungen realer Objekte in Datenbanken zu repräsentieren[AL16]. Daher wurden Anstrengungen unternommen, um die hierarchische Struktur ganz zu überwinden. Zur Identifizierung von Objekten in verteilten Systemen wurden attributierte Namensverwaltungen untersucht (vgl. hierzu z.B. [Bowman, 90a], [Peterson, 88a]). Unter der Annahme, daß die attributierten Namen eines Objekts orthogonal sind, legten sie diese in flachen Namensräumen ab. Das Fehlen von Gültigkeitsbereichen für Attribute und von Navigationsinformationen setzt der Skalierbarkeit attributierter Namensverwaltungen jedoch enge Grenzen und verhindert die Übertragung dieser Konzepte auf globale verteilte Systeme.
Die Konzepte der in dieser Arbeit vorgestellten dynamischen globalen Namensverwaltung geben dem Anwender die Möglichkeit, globale Objekte selbständig zu benennen und durch Namen zu beschreiben. Nachfolgender Abschnitt diskutiert Ansätze, um attributierte Namen in hierarchischen Namensräumen zu repräsentieren und so die verwaltungstechnischen Vorteile hierarchischer Namensräume mit der Flexibilität attributierter Namensräume zu verbinden.
Aufgrund der Unzulänglichkeiten sowohl hierarchischer als auch attributierter Namensverwaltungen wurde in den vergangenen Jahren eine Vielzahl von Modellen vorgeschlagen, die das herkömmliche hierarchische Organisationsschema um Elemente der attributierten Namensverwaltung erweitern.
Verschiedene attributierte Namensmodelle wurden für hierarchische Dateisysteme entwickelt. Diese Ansätze versuchen eine attributierte Charakterisierung von Dateien zu ermöglichen, wobei gleichzeitig die Vertrautheit und Einfachheit der hierarchischen Organisation soweit wie möglich erhalten bleiben soll. In dem von Mogul [Mogul, 86] vorgeschlagenen Schema besitzt eine Datei einen eindeutigen hierarchischen Pfadnamen und zusätzlich eine orthogonale Menge von typisierten Attributen in einem flachen attributierten Namensraum (vgl. Abbildung 2.15). Das Semantic File System [Gifford, 91] wendet Analyseprogramme auf Dateiinhalte an und generiert aus den gewonnenen Informationen und Dateieigenschaften virtuelle Verzeichnisse, deren Einträge Attributwerte sind. Prospero [Neuman, 93] ermöglicht die Anbindung eines Filterprogramms an einen Pfad, das die Interpretation des restlichen Namens bestimmt.
Diese Ansätze bieten eine höhere Flexibilität als streng hierarchische Namensverwaltungen, sie erzwingen jedoch, daß jede Dateieigenschaft entweder in einem flachen attributierten Namensraum oder als Teil einer Hierarchie abgelegt wird. Hierdurch wird das Spektrum der repräsentierbaren Namenskonstrukte deutlich eingeschränkt.
Abbildung 2.15: Speicherung von Attributen im hierarchischen Namensraum
Ein weiteres Beispiel für eine semi-hierarchische Namensverwaltung ist der X.500 Directory Service [CCITT/ISO, 88]. Jede Ebene der X.500-Namenshierarchie enthält eine bestimmte Menge von Attributen. Daher besteht zwischen den Attributen unterschiedlicher Ebenen eine vordefinierte Ordnung. Neufeld [Neufeld, 89] schlägt für die Flexibilisierung dieses Schemas eine Lockerung der Ordnung der Namenskomponenten vor.
Erste allgemeine Ansätze zur Vereinheitlichung attributierter und hierarchischer Namen finden sich in [Sechrest, 92]. Die Schwächen dieser Ansätze liegen insbesondere in der fehlenden syntaktischen Unterstützung der selbständigen Konfigurierung des Namensraums.
Keines der vorgestellten Systeme stellt für sich eine befriedigende Lösung dar. Vielmehr zeigen sie Konzepte auf, die sinnvoll in einen Rahmen gebracht werden müssen, der eine Vielzahl von Namensmodellen unterstützt. Dabei ist vor allem darauf zu achten, daß sowohl für attributierte als auch für hierarchische Namen eine einheitliche Syntax und Interpretationsvorschrift besteht. Wie Pike und Wineberger [Pike, 85] herausstellen, bieten Systeme, in denen jeder Teil eines Namens syntaktisch uneinheitlich interpretiert wird, sehr viel weniger Flexibilität, als ein System, das jede Komponente gleich behandelt. Sowohl die tool-basierten Umgebungen moderner Betriebssysteme als auch die umfangreichen Namensräume verteilter Dateisysteme sind zum Teil deshalb so erfolgreich, weil sie auf einem einheitlichen Namensschema basieren.
Um die Problematik der Integration attributierter und hierarchischer Namensräume zu verdeutlichen und mögliche Ansätze zur Integration aufzuzeigen, sei der weiteren Diskussion zunächst ein Beispiel vorangestellt. Betrachten wir ein typisches Problem: Eine Menge von Geräten der Fakultät für Informatik soll benannt werden, um später auf sie zuzugreifen (vgl. Tabelle 2.1).
Objekt 1 |
600 dpi PostScript Laser-Drucker der Abteilung „Verteilte Systeme (vs)“ der Fakultät „Informatik“ mit der Bezeichnung „KomLab“ |
Objekt 2 |
AppleShare Datei-Server der Abteilung „Verteilte Systeme (vs)“ der Fakultät „Informatik“ mit der Bezeichnung „VSServer“ |
Objekt 3 |
300 dpi PCL Tintenstrahl-Drucker der Abteilung „Verteilte Systeme (vs)“ der Fakultät „Informatik“ mit der Bezeichnung „VSOffice“ |
Tabelle 2.1: Natürlichsprachliche Beschreibung von Geräten anhand ihrer Eigenschaften
Ausgehend von dieser Menge von zu benennenden Objekten und deren Beschreibung muß zunächst eine Menge atomarer Ausdrücke identifiziert werden, die die Objekte eindeutig beschreiben und als Namenskomponenten verwendet werden können. Dabei ist festzustellen, daß die vorliegende Beschreibung der Objekte sowohl Eigenschaften als auch natürliche Namen enthält. Um nun einen Namensraum zur Beschreibung dieser Objekte aufzubauen, sind zwei grundlegende Ansätze denkbar:
• Ein graph-orientiertes Namensmodell, das die Namensteile als Kanten in einem Graphen repräsentiert. Ein vollständiger Name in diesem Modell beschreibt einen Pfad im Graphen von der Wurzel zum benannten Objekt. Dieses graph-orientierte Modell ist die Basis der hierarchischen Namensverwaltung.
• Ein mengen-orientiertes Namensmodell, das den Namensraum in Form einer Tabelle repräsentiert. Die Attribute, die ein Objekt identifizieren, sind in den Spalten der Tabelle aufführt (vgl. Abschnitt 2.2.2.5). Ein attributierter Name im mengen-orientierten Modell entsteht durch den Schnitt von Mengen und wird durch die Zeilen der Tabelle repräsentiert.
Der wesentliche Unterschied zwischen diesen Namensmodellen ist, daß die Einbindung von Attributen in einen Graphen eine Reihe von Einschränkungen über ihren Gebrauch in Namen festlegt.
Nehmen wir nun an, daß diese kleine Menge von Informationen aus Tabelle 2.1 so in einen hierarchischen Namensraum aufgenommen werden soll, daß jedes Gerät aus einer willkürlichen Menge anderer Geräte einfach herausgefunden werden kann. Dabei sollen zunächst keine Attributtypen im Namensraum repräsentiert werden.
Abbildung 2.16: Partielle Darstellung der Informationen aus Tabelle 2.1 in einem Graphen
Abbildung 2.16 zeigt einen einfachen Graphen, der einige der Informationen aus Tabelle 2.1 enthält. Die Struktur ist intuitiv und leicht nachzuvollziehen. Würden jedoch alle Informationen aus Tabelle 2.1 dargestellt, so wären die Namen der Objekte viel zu lang, um noch handhabbar zu sein. Die zu repräsentierenden Objekteigenschaften sind teilweise logisch unabhängig. Der Anwender hat daher bei der Registrierung zu entscheiden, welche Eigenschaften im hierarchischen Namensraum zu akzentuieren sind.
Gleichzeitig erzwingt die Repräsentation von Informationen in Graphen eine feste Ordnung. Während die üblichen Suchfunktionen in hierarchischen Systemen adäquat sind, um im Namensraum in Abbildung 2.16 alle Drucker der Abteilung „Verteilte Systeme“ aufzulisten, so gibt es keine einfache Möglichkeit, alle Laser-Drucker mit 600 dpi zu ermitteln. Streng hierarchische Strukturen allein sind für eine derartige Selektion von Objekten nicht geeignet, da dazu das Traversieren des gesamten Namensgraphen notwendig ist.
Abbildung 2.17: Tabellarische Darstellung der Informationen aus Tabelle 2.1
Im Vergleich hierzu zeigt Abbildung 2.17 eine Tabelle, die sämtliche[AL17] Informationen aus Tabelle 2.1 enthält. In den Zeilen der Tabelle befinden sich attributierte Namen als Prädikate aus Attributwerten, die in den Spalten der Tabelle dargestellt werden. So ist es möglich, Objekte zu identifizieren, indem beliebige Kombinationen von Informationen über sie verwendet werden. Es gibt keine willkürliche Festlegung, welche Information wichtiger ist, wie in hierarchischen Namensräumen.
Diese Freiheit hat jedoch ihren Preis. Was verlorengeht, sind die Ortsinformationen, die hierarchische Namensräume enthalten. Während graph-orientierte Namensräume die Navigation im Verwalternetz bei der Namensauflösung unterstützen, sind attribut-basierte Namensräume mehr für die iterative Verfeinerung von Informationen geeignet. Diese beiden Vorzüge sind für die Organisation von Informationen komplementär zueinander.
Abbildung 2.18: Hierarchische und tabellarische Darstellung der Informationen aus Tabelle 2.1
Die Stärken der beiden unterschiedlichen Darstellungen für Namensräume können in vielerlei Hinsicht kombiniert werden. So werden in Abbildung 2.18 einige der Eigenschaften, die im Namensgraphen nicht dargestellt sind, als Attribute in einem orthogonalen, attributierten Namensraum erfaßt. Dies ist die Basis der Darstellung von Dateiattributen, die von Mogul [Mogul, 86] und Gifford [Gifford, 91] vorgeschlagen wurde.
Die im folgenden vorgestellte einheitliche Darstellung für hierarchische und attributierte Namensräume berücksichtigt Beziehungen zwischen Attributen. Ohne Attribute und Objekte in eine einzige Baumstruktur zu zwängen, können so bestehende Abhängigkeiten zwischen Attributen in einem Namensraum modelliert werden. Im Zentrum dieses Ansatzes steht folgende Überlegung:
Ein hierarchischer Name „info.vs.Drucker.KomLab“ kann sowohl eine Charakterisierung eines Objekts bei der Erzeugung als auch in einer Suchanfrage darstellen. Wie gezeigt, unterliegen beide Aktivitäten starken Einschränkungen durch die hierarchische Struktur. Obwohl die Kategorie „Drucker“ logisch orthogonal zu „vs“ erscheint, ist der Anwender dennoch gezwungen, zu entscheiden, welcher Namensteil bevorzugt, d.h. weiter oben im Namensraum zu positionieren ist. Es gibt keinen ersichtlichen Grund, warum „Drucker.info.vs.KomLab“ kein gleichwertiger Name des Objekts O1 sein sollte (vgl. Abbildung 2.19).
Abbildung 2.19: Restrukturierung von Hierarchien mit Teilordnungen
Es wird klar, daß die Struktur eines hierarchischen Namensraums eine vordefinierte Sicht auf die darin benannten Objekte darstellt. Auswertungen von Namen nach Kriterien, die dieser Sicht nicht entsprechen, sind sehr aufwendig. Bei genauerer Betrachtung hierarchischer Namensräume wird deutlich, daß die hierarchische Ordnung der Namen in Teilordnungen zerfällt. Innerhalb einer Teilordnung ist keine Vertauschung von Namensteilen möglich, da zwischen ihnen Abhängigkeiten in Form von Inklusionen bestehen. Falls die Reihenfolge von attributierten Namen oder von Teilordnungen von attributierten Namen nicht signifikant ist, werden diese als orthogonal zueinander bezeichnet. Orthogonale Attribute können umgeordnet werden, ohne daß sich die Eigenschaften beschriebener Objekte ändern (vgl. Abbildung 2.19).
Abbildung 2.20: Orthogonale Attribute aus Tabelle 2.1 in hierarchischen Namensräumen
Im Graphen in Abbildung 2.20 ist nun die ganze Information aus Tabelle 2.1 enthalten. Im Vergleich zu Abbildung 2.16, sind hier auch Attributtypen wie Fakultät, Abteilung und Geräte im Namensraum repräsentiert. Volle Linien in Abbildung 2.20 kennzeichnen hierarchische und komplementäre Beziehungen zwischen Attributen, graue Linien repräsentieren orthogonale Attribute. Die Interpretation eines Namens kann mehreren grauen Linien folgen, jedoch immer nur einer vollen Linie. Die im Graphen repräsentierten Beziehungen zwischen Attributen schränken somit die Interpretation von Namen ein.
Innerhalb einer Teilordnung können wiederum Teilordnungen existieren, die zueinander orthogonal sind (z.B. Seitenbeschreibung, Druckwerk und Auflösung in Abbildung 2.20). Hieraus ergibt sich eine rekursive Verschachtelung von Teilordnungen. Die Vertauschbarkeit ist dabei nur zwischen Teilordnungen derselben Ebene gegeben. Orthogonale Attribute, zwischen denen keine hierarchische Ordnung besteht, bilden einen attributierten Namensraum und können in separaten Teilbäumen untergebracht werden. Dieses Vorgehen erhält die Vorteile hierarchischer Namensräume bei der Navigation im Verwalternetz, während gleichzeitig die Restriktionen einer strikten Hierarchie weitgehend vermieden werden.
In hierarchischen Namensräumen wird die Interpretation eines Namens einzig durch den Kontext bestimmt, in dem er enthalten ist. Es ist gerade diese Interpretationsvorschrift, die hierarchische Namensräume so mächtig macht. Diese Kontextabhängigkeit verursacht jedoch viele der Einschränkungen graph-orientierter Namensverwaltungen (vgl. Abschnitt 2.2.2.2).
Für die Repräsentation von Attributen wird die Semantik hierarchischer Namen erweitert, wobei die von hierarchischen Namensräumen bekannte Semantik der Namensinterpretation weitgehend erhalten bleibt. Ein Attribut stellt einen Kontext (virtuelles Verzeichnis) dar, der alle Objekte einer bestimmten Eigenschaft enthält. Das Maß, in dem Attribute mit den einzelnen Namenskontexten verbunden sind, bestimmt den Grad, in dem der Namensraum graph-orientierte Semantiken verkörpert. Namen werden sukzessive im Kontext des vorangegangenen Namensteils interpretiert. Jeder neue Namensteil fügt dem Prädikat, das die Interpretation des Namens bestimmt, eine weitere Komponente hinzu. Jeder vollständige Name repräsentiert ein Prädikat, das entweder ein einzelnes Objekt oder einen Kontext identifiziert. Jedes Präfix eines vollständigen Namens repräsentiert einen Kontext, so daß die Notation des aktuellen Verzeichnisses, bezüglich dessen relative Pfadnamen interpretiert werden, seine Gültigkeit behält.
Ein Namensraum in diesem Schema wird aus einer Menge von Attributen und einer Menge von Interpretationsvorschriften bestimmt. Diese Interpretationsvorschriften definieren die Beziehungen zwischen den Attributen und somit die Struktur des Namensraums. Werden diese Interpretationsvorschriften strikt angewendet, so sind sie hinreichend, um eine gewöhnliche Hierarchie zu bilden. Indem syntaktisch mehr oder weniger Beschränkungen eingeführt werden, kann ein ganzes Spektrum von möglichen Namenskonstrukten abgedeckt werden.
Im folgenden wird ein Rahmenwerk zur Namensverwaltung vorgestellt, das hierarchische und attributierte Prinzipien vereint. Die Basis des hier vorgestellten Ansatzes ist die Darstellung der Beziehungen, die die Struktur des Namensraums bilden, als explizite Interpretationsvorschriften. Indem Klassen von Interpretationsvorschriften definiert werden, die verschiedene Facetten von Namensraum-Semantiken widerspiegeln, können Namensräume erzeugt werden, die alle Kombinationen dieser Semantiken enthalten. Nachfolgend werden Namenskonstrukte für die Integration hierarchischer und attributierter Namensräume vorgestellt:
· Hierarchische Namensräume sind ein fundamentales und hilfreiches Konstrukt. Jeder Kontext des hierarchischen Namensraums beschreibt eine Eigenschaft, die alle Objekte relativ zu diesem Kontext erben. Ein Objekt besitzt dann eine bestimmte Eigenschaft, wenn es sich in einem Kontext befindet, der ein Attribut mit dieser Eigenschaft darstellt.
·
Mehrere
unabhängige Hierarchien: Das Konzept graph-förmiger Namensräume
kann durch mehrfache Hierarchien, die orthogonale Objekteigenschaften
enthalten, erweitert werden. Nicht alle Eigenschaften eines Objekts sind
miteinander vereinbar und lassen sich in derselben Hierarchie unterbringen, da
sie oft nicht in direkter Beziehung zueinander stehen.
· Optionale Kontexte: Eine wesentliche Einschränkungen hierarchischer Namensräume ist der Zwang, Objekte extensiv charakterisieren zu müssen. Werden einzelne Teile von Namen als optional gekennzeichnet, dann ist es einfacher tiefe Verschachtelungen zu bilden, die die enthaltenen Objekte voll charakterisieren.
· Graph-förmige Namensräume: Durch Kontexte, die Verweise in andere Kontexte enthalten, und durch Synonyme entstehen graph-förmige Namensräume, die eine individuelle Anpassung des Namensraums an die Erfordernisse eines Anwenders erlauben.
· Nicht-hierarchische Namensräume als Blätter hierarchischer Namensräume: Hierarchien eignen sich bestens für die oberen Ebenen eines großen Namensraums. Jeder hierarchische Namensraum kann attributierte Namensräume in seinen Blättern enthalten. (vgl. Abschnitt 2.2.4 und Abbildung 2.23).[AL18]
· Implizite und explizite Repräsentation von Attributtypen: Einerseits können Attributtypen implizit in den Knoten des Namensgraphen abgelegt werden, wobei im hierarchischen Namensraums nur Attributwerte enthalten sind (vgl. Abbildung 2.16), andererseits können sowohl Attributtypen als auch Attributwerte im Namensraum repräsentiert sein.
Die vorgestellten Konzepte für sich stellen jeweils nur einzelne Ansätze zur Konstruktion globaler attributierter Namensverwaltungen dar. Erst die Kombination dieser Konzepte bildet ein Rahmenwerk zur Namensverwaltung, das Namensräume mit vielen unterschiedlichen Strukturen ermöglicht und es den Anwendern erlaubt, Namensräume zu erzeugen, die ihren individuellen Anforderungen genügen. Gleichzeitig läßt dieses Schema es zu, Namensräume unterschiedlicher Struktur zu kombinieren, um weiträumige verteilte Systeme zu bilden.
Die Darstellung der Attribute aus Abbildung 2.7 in einem streng hierarchischen Namensraum zeigt Abbildung 2.21. Die Farb-, Form- und Größen-Attribute sind logisch unabhängig und orthogonal zueinander, jedoch erzwingt die Darstellung in streng hierarchischen Namensräumen das Festlegen einer willkürlichen Ordnung (vgl. Abbildung 2.21). Diese Ordnung schränkt die Möglichkeiten zur attributierten Suche nach Objekten erheblich ein. Da die Attribute orthogonal sind, ist der Name „rot.mittel.eckig“ prinzipiell äquivalent mit dem Namen „eckig.rot.mittel“, jedoch erlaubt es ein streng hierarchischer Namensraum nicht, letzteren Namen aufzulösen, wenn er nicht zuvor in dieser Reihenfolge registriert wurde.
Abbildung 2.21: Alternative Repräsentation von Attributwerten in hierarchischen Namensräumen
Um Namen unabhängig von der Reihenfolge ihrer Komponenten aufzulösen, bieten sich verschiedene Möglichkeiten an. Zum einen können orthogonale Komponenten von Namen permutiert werden, um diese Permutationen jeweils separat im hierarchischen Namensraum abzulegen. Da somit alle möglichen Darstellungen eines Namens im Namensraum repräsentiert sind, ist die Reihenfolge der Attribute im Prädikat bei der Suche nicht signifikant.
eckig.rot.mittel wird registriert
als: eckig.rot.mittel, rot.mittel.eckig
Alternativ besteht die Möglichkeit, die orthogonalen Attribute eines Namens in der gegebenen Reihenfolge zu registrieren und erst bei der Suche unabhängige Attribute im Prädikat zu permutieren.
eckig.rot.mittel wird gesucht als: eckig.rot.mittel, rot.mittel.eckig
Die Namenskomponenten „rot.mittel“ stellen in obigem Beispiel eine Teilordnung dar. An dieser Stelle sei nochmals darauf hingewiesen, daß Teilordnungen innerhalb orthogonaler Attributhierarchien verschachtelt sein können. Ebenso sind im hierarchischen Namensraum in Abbildung 2.21 keine Attributtypen, sondern nur Werte repräsentiert.
Um eine attributierte Suche im Namensraum zu erleichtern, sollten sich einerseits orthogonale Attribute von Attributen mit einer Ordnungsbeziehung in der Syntax der Namen unterscheiden, andererseits sollten orthogonale Attribute auch in der Struktur des Namensraums repräsentiert werden.
Um orthogonale Attribute in Namen zu kennzeichnen, wird in der dynamischen globalen Namensverwaltung die streng sequentielle Interpretationsvorschrift für Namen, die Kontexte z.B. durch Punkte „.“ trennt, um die Notation der runden Klammer „()“ erweitert. Attribute, die durch runde Klammern zusammengefaßt sind, definieren eine Teilordnung. Der Name „eckig.(rot.mittel)“ kann somit als „eckig.rot.mittel“ oder „rot.mittel.eckig“ interpretiert werden.
Orthogonale Attribute und Teilordnungen, die in Namen durch runde Klammern getrennt sind, können in unabhängigen Hierarchien verwaltet werden. Diese Art der Repräsentation reduziert die Tiefe der Verschachtelung der Namensräume, ermöglicht eine bessere Parallelisierung der Suche und vermeidet eine willkürliche Ordnung zwischen orthogonalen Attributen. Optionale Pfade in einem Kontext kennzeichnen orthogonale Attribute. Separate Teilbäume für orthogonale Attribute bilden auf der obersten Ebene einen attributierten Namensraum als Wurzel für untergeordnete hierarchische Namensräume.
Abbildung 2.22: Repräsentation orthogonaler Attribute in separaten Hierarchien
Abbildung 2.22 zeigt unabhängige Attribute in separaten Hierarchien. Wie ersichtlich ist, sind die Einträge an den Blättern der Teilbäume nicht mehr eindeutig, selbst wenn die einzelnen Objekte eindeutige Beschreibungen durch Attribute aufweisen.
Da die globale attributierte Suche nach einem bestimmten Objekt durch die Notwendigkeit der Schnittmengenbildung der zu den einzelnen, spezifizierten Attributen ermittelten Objektmengen einen hohen Aufwand und eine erhebliche Netzwerklast verursacht, ist es sinnvoll, in jeder Teilhierarchie alle Attribute eines Objekts vollständig abzulegen (vgl. Kapitel 4).
Der Gültigkeitsbereich eines Attributs wird durch die Interpretationsvorschrift definiert. In streng hierarchischen Namensräumen wird ein Attribut stets relativ zu einem Kontext interpretiert und hat somit nur lokal eindeutig zu sein. Attribute in unterschiedlichen Teilbäumen eines hierarchischen Namensraums können daher dieselben Bezeichnungen besitzen.
Abbildung 2.23: Attribute in den Blättern eines hierarchischen Namensraums
Da jedes Attribut in einer Hierarchie einen separaten Kontext einführt, besteht zwischen den Komponenten eines attributierten Namens eine Ordnung. Diese Ordnung kann gelockert werden, wenn Attribute zugelassen werden, die keinen neuen Kontext einführen. Die Attribute Farbe, Größe und Form werden im Kontext „info.vs.KomLab“ interpretiert, der das unterste hierarchische Attribut darstellt. Die Attribute Farbe, Form und Größe spannen einen attributierten Namensraum auf und schließen sich nicht gegenseitig aus (orthogonal):
info.vs.KomLab.(Farbe.blau) (Größe.klein) (Form.eckig)[AL19]
Neben der Koexistenz orthogonaler Attribute im selben Kontext besteht weiterhin die Möglichkeit, daß für ein Objekt Attribute mit mehreren, nicht-exklusiven Attributwerten registriert werden. Die Darstellung mehrwertiger Attribute in hierarchischen Namensräumen erfolgt durch optionale Pfade. Schließen sich Attributwerte gegenseitig aus, so sind die Mengen der Objekte mit diesen Attributwerten disjunkt und die Pfade im Graphen exklusiv. Auf diese Art können Elemente der attributierten Namensverwaltung in hierarchische Namensräume eingebracht werden. Das Attribut Farbe kann beispielsweise für ein Objekt mehrere Werte annehmen, während die Werte des Attributs Größe komplementär zueinander sind:
info.vs.KomLab.(Farbe.(blau) (rot)) (Größe.klein) (Form.eckig)
Zusätzlich zu den im hierarchischen Namensraum bereits erfaßten Attributen können weitere orthogonale Attribute eines Objekts in attributierten Namensräumen an den Blättern eines hierarchischen Namensraums abgelegt werden (vgl. Abbildung 2.23). Als Nachteil ist hierbei anzusehen, daß diese Attribute nicht nach derselben Interpretationsvorschrift behandelt werden können, wie die Attribute im hierarchischen Namensraum. Außerdem ist bei der Suche nach Objekten mit Eigenschaften, die nicht in der Hierarchie erfaßt sind, die Hierarchie, in deren Blätter sich die gesuchten Attribute befinden, immer vollständig zu durchlaufen. In den Blättern eines hierarchischen Namensraums empfiehlt es sich deshalb, primär Attribute zu speichern, die keinen diskreten Wertebereich aufweisen oder ständigen Änderungen unterworfen sind.
Eine Möglichkeit zur Erhöhung der Flexibilität bei der Vergabe und Verwendung von Namen bieten unvollständige Namen in hierarchischen Namensräumen. Diese können realisiert werden, indem bestimmte Namensteile optional registriert werden, sich aber ansonsten normal in die Hierarchie einfügen. Realisiert werden kann dies durch Querverweise (Links) oder durch optionale Kontexte bei der Registrierung von Namen. Im nachfolgenden Namen ist der Teilname „uni-ulm“ optional:
(uni-ulm).info.vs
Optionale Kontexte erzeugen keine Baumstruktur, sondern einen zyklischen, gerichteten Graphen (vgl. Abbildung 2.24). Da in derartigen Graphen die Ordnung nicht signifikant ist, ist es nicht erforderlich, alle Namensteile zu spezifizieren, um ein Objekt zu identifizieren. Falls Kontexte durch Verweise beliebig verbunden werden, besteht beim Durchlaufen eines Graphen die immanente Gefahr der Entstehung von Zyklen. Diese sind zu erkennen, um ein Terminieren der Operationen auf dem Namensgraphen zu gewährleisten.
Abbildung 2.24: Optionale Namensteile im zyklischen gerichteten Graphen
Für attributierte Namen sind u.a. Namensräume in Form zyklischer Graphen gebräuchlich. Neben der Möglichkeit zur Angabe unvollständiger Namen mit optionalen Teilnamen in zyklischen, gerichteten Namensgraphen sollte ein Objekt gleichzeitig durch mehrere alternative Namen identifiziert werden können. Im folgenden Beispiel wird der Kontext „uni-ulm.info“ auch durch den alternativen Namen „home“ bezeichnet:
(uni-ulm.info) (home).vs
Im Gegensatz zu Bäumen besteht in azyklischen gerichteten Graphen die Möglichkeit, daß zu einem Knoten im Graphen mehrere Kanten mit alternativen Namen (Synonyme vgl. Abschnitt 4.4.2.3) führen. Zu beachten ist, daß ein Knoten im Namensgraphen nicht notwendigerweise nur einen Vorgänger besitzt. Somit ist die Flexibilität gegeben, Objekte in verschiedenen Kontexten zu benennen.[AL20]
Abbildung 2.25: Darstellung von Synonymen im azyklischen gerichteten Graphen und in Baumstukturen
Die Darstellung synonymer Namen für Kontexte kann in azyklischen gerichteten Graphen oder auch in Baumstrukturen erfolgen (vgl. Abbildung 2.25). In der Baumstruktur bezeichnen „uni-ulm“ und „home“ nach wie vor denselben Kontext, wobei der Kontext allerdings durch verschiedene Knoten im Graphen repräsentiert wird. Dieser Umstand ist jedoch für die Verteilung von Kontexten auf Namensverwalter hinderlich (siehe Kapitel 4)[AL21].
Die Unterstützung synonymer und generischer Namen steigert die Benutzerfreundlichkeit einer Namensverwaltung. Um als Optionen für die Auflösung von Namen zur Verfügung zu stehen, müssen diese jedoch bereits bei der Registrierung Berücksichtigung finden.
In den vorangegangenen Abschnitten traten Attributtypen wie Farbe, Form und Größe in Namen nicht explizit in Erscheinung:[AL22]
blau.klein.rund
Implizite Attributtypen werden in den Knoten des Namensgraphen abgelegt. Sie sind allenfalls für Vergleiche beim Traversieren im Namensgraphen relevant, treten im Graphen jedoch selbst nicht in Erscheinung. Aufgrund der impliziten Repräsentation der Attributtypen ist die Reihenfolge, in der die Attributwerte im Namen angegeben werden, signifikant und muß vorab definiert werden, da aus dem Namen allein keine Zuordnung von Wert zu Attribut möglich ist. Hierdurch wird jedoch die Flexibilität bei der Namensvergabe erheblich eingeschränkt.
Attributtypen können in Objektnamen auftreten, ohne daß sie sich syntaktisch von Attributwerten unterschieden. Die Interpretation derartiger Namen behandelt daher Attributtypen und -werte gleich. Einen Namen, in dem Attributtypen zwar enthalten, jedoch syntaktisch nicht hervorgehoben sind, zeigt folgendes Beispiel:[AL23]
Farbe.blau.Größe.klein.Form.rund
Um Attributtypen in Namen explizit darzustellen, kann die übliche Namenssyntax, in der die Teile hierarchischer Namen durch einen Punkt getrennt wurden, durch den Doppelpunkt „:“ erweitert werden, der den Attributtyp vom Attributwert trennt (vgl. X.500 [CCITT/ISO, 88]). Explizite Attributtypen enthält z.B. die Beschreibung der Eigenschaften von Objekt 1 aus Abbildung 2.21 durch folgenden Ausdruck:
Farbe:blau.Größe:klein.Form:rund
Hierbei ist zu beachten, daß der obige Ausdruck eine Ordnung (Inklusion) auf den Attributen definiert. Die hervorgehobenen Attributtypen können explizit im Namensgraphen repräsentiert sein (vgl. Abbildung 2.26 und Abbildung 2.27) oder aber auch implizit in Knoten abgelegt werden, so daß sie nicht im Namensgraphen in Erscheinung treten (vgl. Abbildung 2.21).
Unabhängig von der Repräsentation von Attributtypen in Namen können diese unterschiedlich im Namensraum dargestellt werden. Werden Attributtypen implizit in den Knoten des Namensgraphen erfaßt (vgl. Abbildung 2.26), so treten an den Kanten des Graphen lediglich Attributwerte und keine Attributtypen auf. Unter Umständen können unterschiedliche Attribute dieselben Werte besitzen, so daß die Namen an den Kanten eines Knotens nicht notwendigerweise eindeutig sind. Um ein gewünschtes Objekt zu lokalisieren, muß die Namensinterpretation den impliziten Attributtyp mit einbeziehen, bevor entschieden werden kann, welchem Pfad zu folgen ist. Diese Vorgehensweise impliziert eine Änderung der Interpretationsvorschrift hierarchischer Namen.
Abbildung 2.26: Implizite Attributtypen
Die Änderung der Interpretationsvorschrift kann vermieden werden, falls Attributtypen explizit im Namensraum repräsentiert werden. Im Vergleich zur impliziten (vgl. Abbildung 2.26) bedeutet die explizite Repräsentation der Attributtypen eine Flexibilisierung der Namensverwaltung. Ein Attributtyp wird in hierarchischen Namensräumen durch einen Kontext und die zugehörigen Attributwerte durch Einträge in diesem Kontext repräsentiert (vgl. Abbildung 2.27).
Abbildung 2.26 zeigt die hierarchische Darstellung des Attributes Farbe mit den Werten rot, grün und blau. Zwischen den Attributen können Abhängigkeiten (Inklusionen) bestehen, die sich in der Ordnung der Namensteile ausdrücken. Abbildung 2.27 zeigt die Darstellung abhängiger und unabhängiger Attribute in einer hierarchischen Struktur. Die Attribute Farbe und Größe sind orthogonal zueinander, hängen jedoch beide vom Attribut Form ab. Objekt 1 kann so durch den Namen Form.rund.(Farbe.blau) (Größe.klein) beschrieben werden.
Abbildung 2.27: Aufnahme von Attributtypen in den hierarchischen Namensraum
Wie Abbildung 2.27 verdeutlicht, können in verschiedenen Unterbäumen dieselben Attribute vorhanden sein. Dieser Umstand erhöht den Aufwand für die Suche nach Objekten mit Eigenschaften, die tief in der Hierarchie dargestellt sind. Schließlich erzeugt diese Art der Repräsentation von Attributtypen mehr Einträge und eine tiefere Verschachtelung als die implizite Darstellung.
Abbildung 2.28: Repräsentation von expliziten Attributtypen in hierarchischen Namensräumen
Die explizite syntaktische Kennzeichnung von Attributtypen ermöglicht die Darstellung von Attributen in separaten Hierarchien (vgl. Abbildung 2.28). Attributtypen und Attributwerte werden dazu in unterschiedlichen Teilbäumen erfaßt. Falls z.B. die Attribute Größe und Farbe eines Objekts im folgenden Ausdruck
Form: rund. (Farbe: blau) (Größe: klein)
orthogonal sind (runde Klammern fassen orthogonale Ausdrücke zusammen), jedoch beide von der Form abhängig sind, stellen sich die Attribute im Namensgraphen wie in Abbildung 2.28 gezeigt dar. Die Verwaltung orthogonaler Attribute in separaten Unterbäumen erleichtert die Repräsentation von Objekteigenschaften, falls bestimmte Attribute optional sind. Sie führt dazu, daß sich an den Blättern, die Attributwerte repräsentieren, mehrfache Objekteinträge befinden, auch wenn die einzelnen Objekte eindeutig identifiziert sind. Nachteil der expliziten Repräsentation von Attributtypen ist die Notwendigkeit zur Erweiterung der Syntax und der Interpretationsvorschriften für Namen.
Der in Abschnitt 2.3 aufgezeigte Ansatz ermöglicht die selektive Lockerung der Einschränkungen des hierarchischen Namensmodells. Hierdurch kann ein einheitlicher graph-förmiger Namensraum konstruiert werden, in den attributierte Namen integriert sind. Somit wird dem Anwender die Möglichkeit gegeben, in der dynamischen globalen Namensverwaltung attributierte Namen für die Beschreibung von Objekten zu verwenden.
Das Aufbrechen des streng hierarchischen Organisationsschemas ermöglicht die flexible Verwaltung von Objekten anhand ihrer Eigenschaften, wobei die administrativen Vorzüge hierarchischer Organisationsstrukturen für die globale Namensverwaltung erhalten bleiben.
Namen für Objekte finden in verteilten Systemen dann Anwendung, wenn die menschliche Interaktion zur Erfüllung bestimmter Aufgaben erforderlich wird und infolgedessen von der physikalischen Erscheinungsform eines Objekts abstahiert werden muß. Jedes adressierbare Objekt kann prinzipiell einen Namen tragen und von der Namensverwaltung erfaßt werden. Der nachfolgende Abschnitt handelt von den Beziehungen, die zwischen Namen und Objekten bzw. deren Bezeichnern bestehen. Bezüglich der Definitionen der hierbei in Beziehung gesetzten Mengen O und N sei auf Abschnitt 2.1 und 2.2 verwiesen.
Adressen sind absolute Ortsangaben und beschreiben entweder den physikalischen Aufenthaltsort oder eine physikalische Identifikation eines Objekts. Jedes logische Objekt kann mehrere physikalische Replikationen besitzen und daher unter verschiedenen Adressen zu finden sein. Umgekehrt ist es nicht möglich, unter derselben Adresse mehrere Objekte abzulegen, d.h. die Abbildung von Objekt auf Adresse ist injektiv. Diese Eigenschaft der Adreßzuordnung verdeutlicht Tabelle 2.2.
Objekt |
Objekt-Adresse |
|
$14567834 |
|
$13465123,
$23765328 |
|
$73565922 |
Tabelle 2.2: Zuordnung von Objekt zu Adressen
Adressen sind im Gegensatz zu Objekt-Bezeichnern Änderungen unterworfen und nur temporär zugeordnet. Die Adresse eines Objekts ändert sich beispielsweise bei der Migration oder der Substitution des Objekts.
Objekte werden auf der Benutzerebene in der Regel durch grafische Symbole (Piktogramme) dargestellt. Mit diesen Symbolen kann zwar der Anwender sehr bequem arbeiten, nicht jedoch das System selbst. Protokolle verwenden für die Identifizierung von Objekten sogenannte Objekt-Bezeichner, in der Regel ganze positive Zahlen mit ausreichender Kardinalität.
Objekt-Bezeichner |
Objekt |
#1 |
|
#2 |
|
#3 |
|
Tabelle 2.3: Zuordnung von Objekt-Bezeichnern zu Objekten
Bei der Erzeugung von Objekten generiert das System für jedes Objekt einen Bezeichner, der es für die gesamte Lebensdauer eindeutig in Zeit und Raum von anderen Objekten unterscheidet (vgl. Tabelle 2.3). Die Zuordnung eines Objekts zu einem Objekt-Bezeichner ist bijektiv (injektiv und surjektiv) und damit umkehrbar, d.h. ein Objekt-Bezeichner kann nicht mehrere Objekte identifizieren und jedem Objekt ist genau ein Objekt-Bezeichner eindeutig zugeordnet. Aufgrund dieser Bijektion werden im folgenden die Begriffe Objekt und Objekt-Bezeichner äquivalent verwendet.
Die Identifizierung von Objekten anhand von Objekt-Bezeichnern ist für Anwender nicht praktikabel, da diese aufgrund der fehlenden Mnemonik wenig einprägsam sind. Namen hingegen eignen sich hierfür wesentlich besser, weshalb Objekte zusätzlich zu Objekt-Bezeichnern symbolische Namen besitzen.
Objekt-Name |
Objekt(-Bezeichner) |
Telefon |
#1 |
Ball, Kugel |
#3 |
Tabelle 2.4: Zuordnung von Namen zu Objekt-Bezeichnern
Tabelle 2.4 läßt bereits erkennen, daß einem
Objekt(-Bezeichner) mehrere Namen
zugeordnet sein
können. Umgekehrt kann ein primitiver Name
eine ganze Gruppe von
Objekten
bezeichnen.
Die beiden grundlegenden Funktionen, die die Beziehungen zwischen Namen und Objekten beschreiben, sind das sog. Binden und das Mapping: Als Binden wird die erstmalige Zuordnung eines Namens zu einem Objekt bezeichnet. Die Abbildung eines gegebenen Namens auf ein Objekt bzw. dessen Bezeichner wird Mapping genannt.
Definition: Binden
Die erstmalige Zuordnung eines Namens n im Namensraum N zu einem Objekt wird als Binden bezeichnet.
Definition: Mapping
Die Abbildung , die jedem Namen
genau ein Objekt
zuordnet, heißt Mapping vom Namen zum Objekt.
Die Abbildung ist bijektiv, wenn ein Objekt
genau einen Namen
besitzt. Bezeichnet
ein Name
eine Menge von
Objekten
, dann ist
keine Abbildung.
Trägt ein Objekt o mehrere Namen
, so ist die Abbildung
surjektiv[6] aber nicht injektiv.
Das Mapping vom Namen zum Objekt kann mehrstufig sein. Namen können ihrerseits wieder als Objekte verstanden und durch ein anderes Namensschema benannt werden. Somit entstehen verschiedene Ebenen der Abstraktion (z.B. die Abbildung von Dateinamen auf I-Nodes und Dateien oder von Domain-Namen auf IP- und Ethernet-Adressen).
Namen können sowohl an einzelne Objekte als auch an Gruppen von Objekten gebunden sein. Umgekehrt können Objekte gleichzeitig mehrere Namen tragen. Diese mehrfachen Bindungen müssen bei der Namensverwaltung Berücksichtigung finden. Zur Ermittlung der Anforderungen von Mehrfachbindungen an die Namensverwaltung ist eine quantitative Kategorisierung von Namen-Objekt-Bindungen hilfreich.
Eine Klassifizierung von Namen-Objekt-Bindungen zeigt Abbildung 2.29. Die Funktion |{o}| liefert hier die Anzahl der Objekte, die Funktion |{n}| die der zugehörigen Namen. Bezeichnet ein eindeutiger Name genau ein Objekt (|{n}| = |{o}|=1), so liegt ein individueller Name vor. Identifiziert ein Name n mehrere Objekte (|{n}|=1, |{o}|>1), so ist n ein mehrfacher Name. Mehrfache Namen werden unterschieden in Gruppen-Namen und generische Namen. Gruppen- oder Multicast-Namen sind von Bedeutung, um transparent Nachrichten an eine Gruppe von Empfängern senden zu können und um gleichzeitig auch einen vorhandenen, effizienten Multicast-Dienst auszunutzen, wie er z.B. vom Ethernet angeboten wird. Generische Namen identifizieren u.U. eine Menge von Objekten, die der unvollständigen Beschreibung entsprechen.
Abbildung 2.29: Quantitative Beziehungen zwischen Namen und Objekten
Trägt ein Objekt mehrere Namen (|{n}|>1, |{o}|=1), so spricht man von synonymen Namen. Falls synonyme Namen gleichberechtigt nebeneinander koexistieren, werden sie Synonyme genannt. Existiert ein primärer Name, dem die weiteren Namen eines Objekts untergeordnet sind, so bezeichnet man die sekundären Namen als Alias-Namen.
Abkürzungen sind primitive synonyme Namen, die relativ zu einem gegebenen Kontext interpretiert werden und nur innerhalb dieses Kontexts eindeutig sind, der durch einen Benutzer oder durch einen Prozeß definiert wird. Spitznamen sind primitive synonyme Namen mit globaler Signifikanz (absolut).
Die Namen der unterschiedlichen Namensräume eines verteilten Systems stehen zueinander in Beziehung (vgl. Abbildung 2.30). Die Bindungen zwischen Namen auf der Anwendungsebene werden vom Benutzer und auf der System-Ebene durch das Betriebssystem hergestellt.
Abbildung 2.30: Einstufige Abbildung von Namen auf Adressen
Prinzipiell ist eine einstufige Namensverwaltung denkbar, die symbolische und physikalische Namensräume direkt zueinander in Beziehung setzt. Dies hat den Vorteil, daß nur eine einzige, über das System verteilte Abbildung von Namen auf Adressen realisiert werden muß. Wie aus Abbildung 2.30 ersichtlich ist, sind durch einstufige Abbildungen sowohl Synonyme als auch Replikationen von Objekten realisierbar. Dennoch hat die einstufige Abbildung von Namen auf Adressen besonders in verteilten Systemen viele negative Aspekte:
· Die Migration von Objekten bewirkt eine Änderung der Adresse und des Zugriffspfades. Die Namensverwaltung muß daher die Bindung des Namens zur Adresse des migrierten Objekts aktualisieren. Um den Kontakt zum migrierten Objekt nicht zu verlieren, muß der Objektzugriff durch den Anwender stets über den Namen erfolgen und dieser muß jedesmal erneut aufgelöst werden.
· Greifen Anwender nicht über Namen, sondern direkt über Adressen auf Objekte zu, so hat die Namensverwaltung dafür Sorge zu tragen, daß bei der Migration eines Objekts alle Referenzen des Anwenders auf das Objekt aktualisiert werden (vgl. [Traub, 94]).
· Allein anhand von Adressen ist nicht zu erkennen, ob zwei unterschiedliche Namen verschiedene Replikationen desselben logischen Objekts bezeichnen. Es besteht keine Möglichkeit, die Zugehörigkeit verschiedener Adressen zum selben Objekt festzustellen.
Der Wunsch nach Ortsunabhängigkeit und Migrationsinvarianz motiviert mehrere Namensräume mit System-Namen unterschiedlicher Ausprägung.[AL25] Ein zusätzlicher Namensraum mit eindeutigen Objekt-Bezeichnern vermeidet die angeführten Nachteile, erfordert allerdings eine zusätzliche Abbildungsstufe (von Objekt-Bezeichnern auf Adressen).
Viele verteilte Betriebssysteme, wie z.B. Xero [Kato, 91] und PluriX [Traub, 94], verwalten aus dem obengenannten Grund drei Namensräume. Auf der obersten Ebene findet der Anwender symbolische Namen (Benutzer-Namen) vor. Das System identifiziert logische Objekte anhand global eindeutiger Objekt-Bezeichner. Der Aufenthaltsort physikalischer Instanzen logischer Objekte wird durch Adressen beschrieben.
Abbildung 2.31: Die zweistufige Abbildung zwischen den Namensräumen in verteilten Systemen
Die Einführung eines Namensraums mit global eindeutigen Objekt-Bezeichnern (OID) hat den Vorteil, daß OIDs ortsunabhängig und damit migrationsinvariant gewählt werden können. Somit kann ein Objekt migrieren, ohne daß die Bindung vom Namen zum Objekt angepaßt werden muß. Durch die Verwendung von OIDs sind synonyme Namen für Objekte durch die Namensverwaltung leichter zu handhaben, und die Replikation von Objekten bleibt für die Namensverwaltung transparent.
Schwierigkeiten hingegen bereiten die global eindeutige Generierung von OIDs und die Lokalisierung von Objekten, wenn nur die OID bekannt ist und diese keine Ortsinformation enthält. Diese Fragen tangieren jedoch v.a. die Objektverwaltung und die zugrundeliegenden Kommunikationsdienste und sind nicht zentraler Gegenstand dieser Arbeit[7]. Die globale dynamische Namensverwaltung beschäftigt sich daher primär mit der globalen Verwaltung von Bindungen von Benutzer-Namen an Objekt-Bezeichner.
Objekt-Bezeichner bieten eine zusätzliche Abstraktion vom physikalischen Objekt und ermöglichen Migrations- und Replikationstransparenz für die Namensverwaltung.
Nachdem die grundlegenden Beziehungen zwischen Namen und Objekten diskutiert wurden, wendet sich dieser Abschnitt der Verwaltung lokaler Namensräume zu. Diese wiederum bildet die Grundlage für die dynamische globale Namensverwaltung.
Zu den Grundfunktionen einer Namensverwaltung zählen das Registrieren, Auflösen und Löschen primitiver Namen in der Namensbasis lokaler Namensverwalter. Diese Funktionalität bietet prinzipiell jede Standarddatenbank. Basierend auf diesen Funktionen werden die lokalen Operationen auf hierarchischen Namensräumen definiert.
Da die dynamische globale Namensverwaltung dem Anwender die Möglichkeit geben soll, selbständig Namen zu vergeben, wird in dieser Arbeit der Registrierung von Namen besondere Bedeutung zugemessen. Das lokale Registieren eines Namenseintrags[8] entspricht dem im vorangegangenen Abschnitt beschriebenen Binden eines primitiven Namens an ein Objekt. Die Funktionen zur Registrierung hierarchischer und globaler Namen bauen hierauf auf (vgl. Abbildung 3.7).[AL26]
Die primäre Funktion einer Namensverwaltung ist das Auflösen von Namen. Das im vorangegangenen Abschnitt beschriebene Mapping von Namen zu Objekten entspricht dem lokalen Auflösen primitiver Namen. Dabei kann der Suchhorizont durch die Vorgabe eines Kontextes eingeschränkt werden. Die lokale Auflösungsfunktion ermittelt alle Namen-Objekt-Bindungen, die den gesuchten Namen enthalten. Das Ergebnis der lokalen Auflösung primitiver Namen muß jedoch nicht notwendigerweise immer eindeutig sein, z.B., wenn ein generischer Name oder ein partieller Name eines attributierten Namens gesucht ist.
[AL27]Um die Eindeutigkeit primitiver Namen zu gewährleisten, wird vor dem Registrieren lokal nach einem Namenseintrag gesucht, der den neuen Namen enthält. Wird kein derartiger Namenseintrag ermittelt, so kann der neue Name in das Verzeichnis des lokalen Namensverwalters aufgenommen werden. Die Gültigkeit des flachen Namens kann dabei gegebenfalls wieder durch die Angabe eines Kontextes eingeschränkt werden. Tritt ein Konflikt durch doppelte Namen auf, so wird der primitive Name nur dann registriert, wenn es sich um einen partiellen Namen eines attributierten Namens handelt. Nur bei der Registrierung attributierter Namen ist es möglich, daß partielle Namen im selben Kontext auf verschiedene Objekte verweisen (vgl. Abschnitt 4.4).
Dem Wesen einer dynamischen Namensverwaltung entspricht es, daß Namenseinträge nicht nur registriert, sondern auch wieder entfernt werden, entweder weil die Bindung eines Namens an ein Objekt aufgehoben oder weil im Rahmen einer Aktualisierung ein Eintrag durch einen modifizierten ersetzt wird. Hierbei kann zwischen dem aktiven Löschen seitens des Anwenders und dem passiven Löschen durch die Alterung bestimmter Arten von Namenseinträgen unterschieden werden (vgl. Kapitel 5). An dieser Stelle sei bereits darauf hingewiesen, daß in der dynamischen globalen Namensverwaltung das Ändern einer Namen-Objekt-Bindung nicht als atomare Funktion realisiert ist, sondern als zusammengesetzte Transaktion aus Löschen und erneutem Registrieren.
Der Löschvorgang besteht aus zwei Phasen, dem Ermitteln und dem Entfernen des zu löschenden Namenseintrags. Für das Löschen eines primitiven Namens ist nicht nur der vom Namenseintrag belegte Speicher zu entfernen, sondern auch alle Referenzen, die auf den Namenseintrag verweisen. Besitzt das Betriebssystem eine automatische Freispeichersammlung (Garbage Collection), so genügt das Entfernen aller Referenzen, um den Eintrag freizugeben. Er wird dann bei Gelegenheit von der Garbage Collection aus dem Speicher entfernt, da er nicht mehr referenziert wird.
Pseudocode für die Funktionen der dynamischen globalen Namensverwaltung zur lokalen Verwaltung primitiver Namen findet der interessierte Leser in Anhang D. Die Struktur der Namenseinträge ist in Anhang C beschrieben.
In den
vorangegangenen Abschnitten wurden Beziehungen zwischen primitiven Namen und
Objekten betrachtet. Bei flachen Namensverwaltungen gibt es eine einzige
Abbildung , so daß gilt:
Typischerweise sind Namen jedoch
kontextbezogen, um die Mächtigkeit des Namensraums zu vergrößern und die
Eindeutigkeit von Namen besser gewährleisten zu können. Für eine formale
Definition kontextbezogener Namen (vgl. [Younger, 92])
wird die Menge O der Objekte in m Teilmengen zerlegt. Für jede
Teilmenge
sei weiter eine
Funktion
gegeben, so daß gilt:
Die Funktionen werden als Kontexte bezeichnet, die jeder für sich
eine flache Namensverwaltung bilden, in der nur die Objekte aus
benannt werden. Die
Kontexte
sind surjektiv. Sie
können bijektiv sein, wenn auf Synonyme verzichtet wird. Die aus einzelnen
Kontexten zusammengesetzte Gesamtabbildung
kann dennoch
mehrdeutig sein. Die flachen Namen sind dabei nur innerhalb eines bestimmten
Kontextes eindeutig. Das Objekt o
wird durch das Tupel
bestimmt.
Die Frage bleibt, wie ein Kontext
identifiziert wird. Die natürliche Antwort lautet: Er wird ebenfalls benannt.
So kann eine Namensverwaltung konstruiert werden, die eine weitere Menge von
Kontexten enthält und Namen auf Kontexte in abbildet. An dieser
Stelle sei darauf hingewiesen, daß dieser Vorgang potentiell unendlich ist, da
jeder Kontext in einem Kontext höherer Stufe benannt wird. Um das zu vermeiden,
muß es auf einer Stufe der Hierarchie von Kontexten einen oder mehrere
(Wurzel-)Kontexte geben, die folgende Eigenschaften besitzen:
• Sie benennen alle Kontexte auf der nächst niedrigeren Stufe.
• Sie sind in keinem höheren Kontext benannt und ein impliziter Teil der Namensverwaltung.
Die bislang entwickelte Namensverwaltung besteht aus,
• einem oder aus mehreren Wurzel-Kontexten, die nicht benannt werden müssen,
• einer Hierarchie von Kontexten fester Tiefe (potentiell unendlich), wobei jeder Kontext auf einer gegebenen Stufe in wenigstens einem Kontext einer höheren Stufe benannt ist,
• und einer niedrigsten Stufe von Kontexten, auf der keine Kontexte mehr, sondern einfache Objekte benannt werden.
Formal läßt sich diese hierarchische Namensverwaltung wie folgt beschreiben [Younger, 92]:
Gegeben sei eine Menge von zu benennenden
Objekten O, sowie m Teilmengen Oi von O.
Ferner eine Menge von m Relationen , so daß gilt:
Gleichzeitig seinen n Teilmengen und n Relationen
gegeben, die die
Kontexte in
benennen. Weiter wird
vorausgesetzt, daß es eine Menge von Kontexten
gibt, die in einem
oder mehreren Wurzel-Kontexten benannt werden.[AL28]
Verallgemeinert man weiter, so läßt sich die
Eigenschaft der festen Tiefe der Hierarchie eliminieren. Dazu wird erlaubt,
einen Kontext oder ein Objekt von einem Kontext auf jeder höheren Stufe der
Hierarchie aus zu benennen. Die Funktionen stellen sich dann wie
folgt dar:
Dieses Prinzip erlaubt die Benennung eines
jeden Objekts oder Kontextes im System. Im folgenden wird ohne Beschränkung
der Allgemeinheit ein einziger Wurzel-Kontext vorausgesetzt. Eine
Funktion resolve zur lokalen
Auflösung absoluter hierarchischer Namen wird dann wie folgt definiert:
Die gegebene Definition der kontextbezogenen Namensauflösung begründet die Vorstellung von Pfadnamen als geordnete Liste von Namen. Die Namensinformation im System kann als Graph mit der Relation „ist benannt in“ dargestellt werden, wobei die Knoten im Graphen die Kontexte und Objekte repräsentieren, und eine direkte Verbindung zwischen Kontext 1 und Kontext 2 besteht, wenn Kontext 2 in Kontext 1 benannt wird. Werden die resultierenden Kanten mit dem Namen versehen, an den Kontext 2 in Kontext 1 gebunden ist, dann ist die Auflösung eines Pfadnamens ein Wandern durch den Graphen mit der Relation „ist benannt in“.
Oben vorgestellte lokale Auflösungsfunktion resolve beginnt die Auflösung von Namen
stets beim Wurzelkontext. In tief verschachtelten hierarchischen Namensräumen
ist das jedoch sehr ineffizient, weshalb viele Systeme einen Kontext oder den
Namen eines Kontexts speichern, der als alternativer Startkontext zum
Wurzelkontext verwendet werden kann. Abhängig davon, ob der Name mit dem
Wurzelsymbol „/“ beginnt oder nicht, wird der Name entweder als absoluter Name
bezogen auf den Wurzelkontext oder als relativer Name bezogen auf den
Startkontext aufgelöst.
Bisher wurde eine statische Namensverwaltung beschrieben. Eine dynamische Namensverwaltung muß um Operationen zum Ändern der Bindungen zwischen Namen, Kontexten und Objekten ergänzt werden. Das ist nicht trivial, da Kontexte auf einer bestimmten Ebene durch die Kontexte der nächst niedrigeren Stufe bestimmt werden.
Die Funktionen register und remove manipulieren Bindungen von Kontexten oder Objekten zu primitiven Namen in einem gegebenen Kontext und werden wie folgt formal beschrieben:
|
|
Ausgehend von der formalen Definition der kontextbezogenen Operationen auf Namensräumen, werden in den folgenden Abschnitten die lokalen Operationen auf hierarchischen Namensräumen der dynamischen globalen Namensverwaltung weiter präzisiert.
Die lokale Funktion resolve bildet die Grundlage für die globale Auflösung
hierarchischer und attributierter Namen in der dynamischen globalen Namensverwaltung.
Die lokale Auflösung hierarchischer Namen kann als syntaxgesteuertes
Traversieren des Namensgraphen implementiert werden und basiert auf zwei Grundoperationen,
dem Wandern nach oben zum Wurzel-Kontext und dem Wandern zum nächsten, unteren
Knoten im Namensgraphen. Die schrittweise
lokale Auflösung hierarchischer Namen mit der Funktion resolve nimmt dabei verschiedene Zustände an, und jeder Auflösungsschritt
liefert einen neuen Teilnamen, der weiter interpretiert wird.
Beginnend beim Ausgangszustand start werden abhängig von den Beziehungen zwischen dem gesuchten und den im Namensraum N existierenden Namen die jeweiligen Zwischenzustände search, prev context und next context angenommen. Schließlich terminiert die Auflösung mit einem der Endzustände found, not found oder global search.
Die Beziehungen zwischen einem gegebenen hierarchischen Namen n und den Namen in einem Namensraum N lassen sich wie folgt definieren:
no match(n, N) |
|
z.B. n=a.b.c, m=e.f.g |
related(n, N) |
|
z.B. n=a.b.c, m=a.b.d |
partial match(n, N) |
|
z.B. n=a.b.c , m=a.b |
full match(n, N) |
|
z.B. n=a.b.c, m=a.b.c |
Unter Berücksichtigung der o.g. Zustände und der soeben definierten Beziehungen zwischen Namen läßt sich die lokale Interpretation eines hierarchischen Namens n wie folgt beschreiben:
Beginnend im aktuellen Kontext (Zustand: start) wird versucht, den
ersten Teil des hierarchischen Namens zu interpretieren (Zustand: search) (vgl. Abbildung 2.32).
Wird hier keine Übereinstimmung mit vorhandenen Namenseinträgen festgestellt (no match, related), so wechselt sich
die Auflösung zum übergeordneten Kontext (Zustand:
prev context) und versucht, falls dieser existiert (prev context found), dort erneut einen Teil des Namens zu
ermitteln (Zustand: search). Wenn
dieser nicht vorhanden ist und kein externer Verweis existiert (prev context not found), wird die
Auflösung erfolglos abgebrochen (Zustand:
not found). Existiert jedoch ein Verweis auf einen externen Namensverwalter
(prev node found), dann wird die
Auflösung bei diesem fortgesetzt (Zustand:
global search).
Gelingt im Zustand search im aktuellen Kontext die teilweise Interpretation (partial match), so wechselt die Auflösung zu dem Kontext, dessen Name erkannt wurde (Zustand: next context). Ist der Name vollständig interpretiert (full match), so terminiert das Verfahren und gibt die Objekt- oder Kontext-Bezeichner der letzten Station der Auflösung aus (Zustand: found). Wenn der Name nur partiell interpretiert wurde (Zustand: next context) und kein Nachfolgekontext mehr existiert (next context not found), so terminiert die Auflösung erfolglos (Zustand: not found). Andernfalls (next context found) wird die Suche nach weiteren Namensteilen aufgenommen (Zustand: search). Kann der Name weiter interpretiert werden (partial match), so wird der Kontext, den der partielle Name bezeichnet, zum aktuellen Kontext (Zustand: next context). Falls kein weiterer Teil des Namens ermittelt werden kann (no match), wird die Suche erfolglos abgebrochen (Zustand: not found).
Bei der Auflösung von Namen relativ zu einem Startkontext läuft die Suche den Kanten des Namensbaumes entlang nach oben (Zustand: prev context), bis ein partieller Name gefunden oder die Suche erfolglos beendet wird. Existieren dabei im Graphen mehrere Pfade, über die ein Knoten im Graphen (Kontext oder Objekt) erreicht werden kann, so wird ein Pfad ausgewählt, und die übrigen Namenseinträge werden für eine spätere Bearbeitung festgehalten. Alternativ können in einem Multitasking-Betriebssystem separate Prozesse abgespalten werden, die optionale Pfade verfolgen und die jeweiligen Resultate ermitteln.[AL29]
Abbildung 2.32: Zustände der lokalen Auflösung hierarchischer Namen (resolve)
Um die Auflösung von Namen zu beschleunigen, sollte sie in einem Startkontext beginnen. Namen werden dann relativ zu diesem Startkontext aufgelöst. Sofern relative Namen aufzulösen sind, läßt sich hierdurch die Anzahl der notwendigen Auflösungsschritte entscheidend verringern. Liegen jedoch absolute Namen vor, so beginnt die Auflösung stets an der Wurzel. Absoluten Namen steht als Präfix das Symbol für die Wurzel (z.B. „/“) voran, wodurch die Wurzel als Startkontext feststeht und die aufsteigende Suchphase entfallen kann.
Die Auflösung absoluter Namen kann auch die Ähnlichkeit des gesuchten Namens mit dem Namen des aktuellen Kontexts berücksichtigen. Besteht weitgehende Übereinstimmung des gesuchten absoluten Namens mit dem Namen des aktuellen Startkontexts (related), so ist es u.U. effektiver, die Suche nicht bei der Wurzel zu beginnen, sondern sich schrittweise nach oben zur Wurzel vorzuarbeiten. Diese Art der Suche gewinnt jedoch erst bei der globalen Auflösung von Namen verstärkt an Bedeutung.
In Betriebssystemumgebungen werden gewöhnlich zur Strukturierung von Namen Unterverzeichnisse als Kontexte angelegt. Diese werden nicht ad hoc, sondern vielmehr sukzessive durch den Anwender explizit mittels Befehlssequenzen zum Erzeugen und zum Wechseln von Verzeichnissen generiert. Neue Kontexte werden relativ zum aktuellen Kontext erzeugt. Zuletzt wird der primitive Name des Objekts im aktuellen Kontext registriert.
md uni, cd uni, md vs, …
Im Gegensatz zu den meisten anderen Namensverwaltungen ist es in der dynamischen globalen Namensverwaltung nicht Aufgabe des Benutzers oder Administrators, Kontexte oder Verzeichnisse anzulegen. Benutzer registrieren stets nur vollständige Objektnamen, jedoch keine Kontextnamen (Verzeichnisse). Wird ein hierarchischer Objektname registriert, für den noch kein geeigneter Kontext existiert, so werden die Namenseinträge für die fehlenden Kontexte von der Namensverwaltung selbständig erzeugt.
Wird ein hierarchischer Name für ein Objekt registriert, so muß zunächst die Eindeutigkeit des Namens geprüft werden. Dabei dürfen verschiedene Objekte oder Kontexte nicht die gleichen hierarchischen Namen tragen[10]. Umgekehrt darf ein Objekt oder Kontext jedoch mehrere Namen besitzen. Die lokale Eindeutigkeit eines Namens wird geprüft, indem der Registrierung eine Auflösung vorangestellt wird. Erst wenn der Name so weit wie möglich aufgelöst und dessen Eindeutigkeit sichergestellt ist, werden der restliche Teil des Namens sukzessive registriert und fehlende Kontexte erzeugt. Den Ablauf einer Registrierung zeigt Abbildung 2.33.
Abbildung 2.33: Zustände der lokalen Registrierung hierarchischer Namen
Das Registrieren eines neuen Namens im Namensraum geschieht zunächst nur im lokalen Namensverwalter. Lokale Einträge sind den übrigen Namensverwaltern nicht bekannt. Soll der Name über die Grenzen des lokalen Namensverwalters hinaus bekannt gegeben werden, so muß er entweder im Broadcast-Bereich oder global registiert werden.
In der dynamischen globalen Namensverwaltung besteht analog zum Registrieren von Namen für den Anwender zunächst lediglich die Möglichkeit, einzelne Namen von Objekten aus der lokalen Namensbasis zu löschen. Soll eine Gruppe von Namen oder gar ein Kontext gelöscht werden, so werden diese durch einen attributierten oder generischen Namen beschrieben, wobei alle Namenseinträge entfernt werden, auf die die Beschreibung zutrifft.
Abbildung 2.34: Zustände des lokalen Löschens hierarchischer Namen
Vor dem Löschen eines lokalen Namens wird dieser aufgelöst, um den zugehörigen Namenseintrag in der lokalen Namensbasis zu ermitteln. Bezeichnet der Name ein Objekt, so wird der entsprechende Namenseintrag gelöscht. Kontexte werden nur dann entfernt, wenn keine nachfolgenden Namenseinträge vorhanden sind, d.h. der Kontext leer ist (vgl. Abbildung 2.34). Werden durch das Löschen von Objektnamen übergeordnete Kontexte obsolet, so werden diese so lange rekursiv entfernt, bis weitere Einträge enthalten sind. Anschließend wird erneut versucht, den zu löschenden Namen aufzulösen. Dadurch werden beim Löschen generischer Namen alle Einträge entfernt, die der gegebenen Beschreibung entsprechen[AL30].[AL31]
Gelegentlich muß der Anwender über im System auftretende Ereignisse informiert werden. Beziehen sich diese Ereignisse auf Benutzerobjekte, so ist es erforderlich, den für den Benutzer relevanten Namen anstatt eines Objekt-Bezeichners auszugeben (z.B. „Rechner alpha wurde abgeschaltet!“). Aus diesem Grund muß die Namensverwaltung eine Umkehrabbildung von Objekt-Bezeichnern auf hierarchische Namen bereitstellen.
Um zu einem gegebenen Objekt-Bezeichner den zugehörigen hierarchischen Namen, der die Kanten des Pfades von der Wurzel zum Namenseintrag mit dem Objekt-Bezeichner benennt, zu bestimmen, wird zunächst der zugehörige Namenseintrag ermittelt (vgl. Abbildung 2.35). Falls zu einem Objekt-Bezeichner ein Namenseintrag existiert, wird der enthaltene primitive Name ausgegeben. Anschließend wird zum übergeordneten Kontext gewechselt und der primitive Name des Kontexts im übergeordneten Kontext ausgegeben. Dieser Vorgang wiederholt sich, bis die Wurzel des hierarchischen Namensraums erreicht ist. Auf diese Weise wird der hierarchische Namen eines Objekts sukzessive aus dem primitiven Namen des Objekts und den primitiven Namen der übergeordneten Kontexte konkateniert.
Abbildung 2.35: Lokales Ermitteln des hierarchischen Namens eines Objekts
Wie bereits die vorangegangenen Abschnitte gezeigt haben, liefert die Namensauflösung nicht notwendigerweise stets eindeutige Resultate. Insbesondere generische und attributierte Namensanfragen, wie sie in Abschnitt 4.4 eingehender diskutiert werden, geben in der Regel als Resultat eine Menge von Objekten zurück. Bestehen bei der Ermittlung des Namens eines Objekts durch Synonyme und Querverweise alternative Pfade vom Namenseintrag zur Wurzel, so werden diese in der dynamischen globalen Namensverwaltung zunächst in einer besonderen Datenstruktur (vgl. Abschnitt 4.3.2) vermerkt und anschließend abgearbeitet.
Die lokalen Namensoperationen auf hierarchischen Namensräumen bilden die Basis für die dynamische Verwaltung globaler Namen.
[1] Die relative Entfernung kann z.B. aus der Nachrichtenlaufzeit, der Zugriffszeit oder der Anzahl der Zwischenknoten abgeleitet werden.
[2] Flache Namen werden in der Literatur häufig auch als primitive, einfache oder atomare Namen bezeichnet.
[3] Dennoch existieren Algorithmen, die flache Namen netzwerkweit eindeutig vergeben [Segall, 84].
[4] Abgesehen davon, daß eine beliebige Anordnung der Attribute eine vollständige Suche erfordern würde.
[5] [Mattes, 91] identifiziert drei Kategorien, die sich von den hier aufgezeigten teilweise unterscheiden.
[6] Vorausgesetzt, es existieren keine versteckten Objekte, die über Namen nicht zu erreichen sind.
[7] Der interessierte Leser sei hierzu auf die Literatur verwiesen (vgl. z.B. [Kato, 91]).
[8] Die Struktur von Namenseinträgen wird in Anhang C dargestellt.
[9] Diese Forderung kann aus Sicherheitsgründen durchbrochen werden (versteckte Objekte oder Kontexte).
[10] Ausnahmen bilden lediglich partielle hierarchische Namen eines attributierten Namens, falls diese Objekteigenschaften repräsentieren, die für mehrere Objekte zutreffen können.
[AL1]Struktur!!
[AL2]Sollte es hier nicht besser Objekt heißen????
[AL3] Warum kann man nicht auf alle Namen effizient zugreifen?
[AL4] nicht immer, z.B. GSM und Ethernet
[AL5] „scheinbare Hierarchie“ auf der Benutzerebene
[V6] Diesen Anschnitt könnte man auch in Kapitel 4 gut unterbringen, da die Partitionierung etwas mit der Verteilung auf Namensverwalter zu tun hat.
[AL7] Rekursive Partitionierung
[AL8]Keine Unterscheidung Namen Attribute, der Name ist eben falls ein Attribut.
Jedes Objekt hat eine Adresse als Attribut (email, IP, Telefon). Zusätzliche Attribute sind Paßwörter, homedirectories, Versionsnummern usw.
[AL9]Daten der Namensverwaltung liegen oftmals als Paare (Name, Attribute) vor. Typischerweise werden Attribute der Art (Typ, Wert) zu Namen gespeichert.
[AL10]Ordnung auf den Attributen ><= usw.
[AL11] Welche sind das?
[AL12]inplizite Attribute
[V13] Welchen Einfluß hat das auf die Namensauflösung von attributierten Namen in Kapitel 4 und weiter hinten??
[AL14] Wo liegt denn der genaue Unterschied zwischen potentiellen und verfügbaren Namen.
[AL15]etwas durcheinander!
[AL16]Ref
[AL17]Bis auf den Namen
[AL18]Das ist noch schief!!
[AL19]Kann es danach noch weitergehen???
[AL20]Probleme bei der Lokation, Zusammenfügen
Verschiedene Prozesse treffen sich beim Ergebnis
Ver schiedene Prozesse liefern das Ergebnis an den Namensverwalter zurück, der die Schnittmenge bildet
Jeder Prozeß enthält die vollständige Beschreibung der Suchanfrage und liefert nur Ergebnisse, die dieser Angabe entsprechen.
Nachteil Ermitteln der Kontexte
Kontexte als Blätter ergeben ein Weglenkungsproblem
Problem: gleiche Objekt und Kontextnummern
Kontexte an den Blättern
Wie werden Kontext verteilt zusammengefaßt?
Wie erhalten solche Kontexte eine eigene ID?
[AL21]Wie wirkt sich das auf die globale Registrierung und die Lokation aus aus???
Unspezifische Anfragen
[AL22]Im Namensgraphen können auch verschiedene Attribute nebeneinander implizit auftreten.
[AL23]Repräsentation im Grahpen wie bei Werten
Nachteil bei Einsortieren, Clustern
Der Name "uni-ulm" enthält Attrinut und Wert in einem Namen.
[AL24]Aliases
[AL25]Dieser Satz ist noch schief!
[AL26]Flexible Erzeugung von IndexBäumen von expliziten Attributen???
[AL27]Das gilt aber nicht für attributierte NAMEN!!!!!!!
[AL28]Stimmt das so????
[AL29]Wie wirkt sich das ganze auf den Hintstack und das Zusatndsdiagramm aus????
[AL30] Eventuell sollte man die Kontexte noch eine Weile behalten, obwohl temorär keine Objekte darin sind, damit keine nützliche Information verloren geht.
[AL31]Sind das Einfügen und das Löschen von Namen kommutativ?