LCARS


Die Herausforderung

Die Anforderungen an Computersysteme haben sich in den letzten Jahren besonders im privaten Bereich deutlich verändert, hin zu einem Speicher- und Wiedergabesystem für digitale Medien wie Musik, Videos und Fotos. Diese Entwicklung wird durch die noch immer wachsende Beliebtheit von MP3-Dateien und ihren Derivaten, digitaler Fotografie und neuerdings auch durch digitale hochauflösende Filme angetrieben.

Leider sind die heute eingesetzten Dateisysteme nicht weiterentwickelt worden, um den veränderten Anforderungen beim Speichern und vor allem Wiederfinden tausender Dateien gerecht zu werden. Auf logischer Ebene bieten die üblichen Dateisysteme als Ordnungsschema noch immer eine Verzeichnishierarchie an. Ein alternativer Zugang zu Dateien über Verzeichnisgrenzen hinweg ist jedoch dringend notwendig, da eine Ordnerstruktur deutliche Nachteile aufweist. Zunächst können Dateien nur an genau einem Platz in der Verzeichnishierarchie abgelegt werden. Ein Beispiel dafür ist der folgende Verzeichnisbaum, in den ein fiktiver Nutzer seine Fotos einsortiert:



Verzeichnisbaum

Auf der obersten Ebene sind alle Fotos in Aufnahmen von Geburtstagsfeiern und Urlaubsfotos eingeteilt - erstere dann nach Personen, letztere nach Ländern und schließlich weiter nach Orten. Dieses System weist aber prinzipielle Lücken auf: wo sollen beispielsweise Fotos von Bertas Geburtstag abgelegt werden, wenn sie ihn auf Mallorca gefeiert hat ? Wenn entsprechende Bilder in beiden Zusammenhängen auffindbar sein sollen, müssen sie auch durch beide Ordner zugänglich gemacht werden, etwa durch Einführung von symbolischen Links. Bei Einführung weiterer Kategorien, etwa des Aufnahmejahres, steigert sich dieser Aufwand zusehends weiter. Darüber hinaus ist eine Verzeichnishierarchie auf der Mitarbeit des Benutzers angewiesen, der geeignete Kategorien für seine Dateien finden und entsprechende Unterverzeichnisse anlegen muss. In der Praxis wird es zudem oft vorkommen, dass Dateien in falschen Verzeichnissen gespeichert werden, so dass sie nicht mehr aufgefunden werden können und „verloren gehen“. Für diese Probleme bietet das LCARS-Dateisystem eine grundlegende und wirksame Lösung.


Integration

Ein Grundpfeiler des LCARS-Dateisystems stellt die Verwendung von Metadaten und die Integration von relationalen Datenbanken ins Dateisystem dar.


Metadaten


Metadaten in JPEG-Bildern von Digitalkameras

Metadaten sind Informationen, die nicht zu den eigentlichen Nutzdaten einer Datei gehören, sondern diese beschreiben. Klassische Metadaten sind der Dateiname und das Datum der letzten Änderung einer Datei. Darüber hinaus speichern die meisten Bildformate die Größe des Bildes, also Länge und Höhe in Pixeln. Audiodateien müssen die Samplerate und Bittiefe des Klangs abspeichern. Diverse Multimedia-Dateiformate enthalten zusätzlich noch weitere Metadaten, wie zum Beispiel Titel, Copyright oder das verwendete Aufnahmegerät:

Dateiname Geändert am Größe Dateikörper

BILD.JPG

08.12.2005

89237 Byte

JPEG-Bild mit Metadaten

Dateien enthalten also heute viele strukturierte Attribute, die für ein herkömmliches Dateisystem jedoch unsichtbar sind: abgesehen von den klassischen Attributen wie Dateiname, Erstellungsdatum und Größe können keine anderen Attribute zum Ordnen von Dateien verwendet werden. Für das Speichern von strukturierten Daten sind klassische Dateisysteme daher ungeeignet, so dass viele Applikationen kleine Datenbanken implementieren, um ihre Nutzdaten abzuspeichern - ein klares Indiz dafür, dass Dateisysteme den Anforderungen dieser Applikationen nicht genügen.


Libraries

Durch das Verwenden von Metadaten, also beliebigen Attributen für Dateien, verschwimmen die Grenzen von Datenbanken und Dateisystemen, bzw. beide können als äquivalent angesehen werden:



Beziehung zwischen Datenbanken und Dateisystemen
  • Während physikalische Dateisysteme eine einheitliche Struktur für alle Dateien erzwingen, gehen geeignete semantische Dateisysteme typspezifisch vor und können insbesondere für jedes Dateiformat eine eigene Struktur verwalten.
  • Sowohl relationale als auch BLOB-relationale Datenbanken können für jede Relation eine andere Struktur verwenden. Die Fähigkeit, unstrukturierte Daten in Form von BLOBs abspeichern zu können, ist jedoch nur bei BLOB-relationalen Datenbanken gegeben.
  • Virtuelle Dateisysteme sind ein Spezialfall, da sie nicht auf einem physikalischen Dateisystem basieren, sondern das Dateikonzept zur Darstellung anderer Daten nutzen.

Hierdurch lassen sich Datenbanken und Dateisysteme auf logischer Ebene nicht mehr unterscheiden. Als einheitliche Bezeichnung wird der Begriff „Library“ eingeführt, der das Speicherkonzept im Sinne einer Datenbibliothek beschreibt.


Implementierung

DESKWORK setzt ein mehrstufigen Entwurf für das Dateisystem um, der das Betriebssystem vollständig vom unterliegenden physikalischen Dateisystem isoliert. Das Dateisystem setzt sich aus mehreren Domains zusammen, die auf dem physikalischen Dateisystem aufbauen: entweder durch Abbildung von Dateien in die Library, oder durch die Interpretation von Datenbank-Tupeln als Dateien. Ein Sonderfall sind virtuelle Domains, die auf keinem Dateisystem aufbauen, sondern andere Informationen (z.B. das Boot-Protokoll) in Form von Dateien präsentieren. Applikationen greifen nicht mehr direkt auf das physikalische Dateisystem zu, sondern nur noch über Domains. Dies wurde in der Praxis durch Ersetzen der entsprechenden API-Funktionen innerhalb des Betriebssystems realisiert, so dass dieser Vorgang für alle Programme völlig transparent abläuft.



Architektur des LCARS-Dateisystems


Vererbungshierarchie von Programmen, die Dateilisten erstellen können (Ausschnitt)

Intern ist das gesamte LCARS-Dateisystem objektorientiert aufgebaut. Oberste Klasse der rechts dargestellten Vererbungshierarchie ist die abstrakte Klasse DDataAbstract, die eine beliebige Datei eines beliebigen Formats repräsentiert. Neben den obligatorischen Attributen Dateiname, Schlüssel, Typ und diversen Steuerbits definiert diese Klasse eine Reihe von abstrakten Methoden, die von vollständigen Klassen implementiert werden müssen. Durch Aufruf dieser Methoden können Datei-Objekte von außen manipuliert, etwa umbenannt, werden. Die konkrete Realisierung, insbesondere die Funktionsweise und das physikalische Format der beteiligten Domains, bleibt dem Aufrufer dabei verborgen.

Von der abstrakten Klasse DDataAbstract werden auf der nächsten Ebene alle Domains abgeleitet. Bestimmte Methoden, die für alle Dateien der Domain unabhängig von ihrem Format gleich sind, werden dort implementiert, beispielsweise das Umbenennen (Rename) oder Löschen (Kill) von Dateien. Außerdem existieren Methoden zum physikalischen Zugriff auf Dateien, etwa zum Öffnen und Schließen (Open und Close), zum Verschieben des Dateizeigers (Seek) sowie zum Lesen und Schreiben von Daten an der aktuellen Position des Dateizeigers (Read und Write). Diese Operationen werden in geeigneter Weise auf das physikalische Dateisystem abgebildet und sind nur in der Domainklasse selbst sowie allen abgeleiteten Klassen sichtbar (protected).

Zusätzlich enthalten alle Domains die Methode CreateList. Diese Methode bekommt einen Suchfilter übergeben und liefert alle gespeicherten Dateien zurück, die den Bedingungen des Filters genügen. Die konkrete Implementierung kann sich von Domain zu Domain unterscheiden, beispielsweise durch die Verwendung eines geeigneten Indexes. Ein solcher Index kann für alle Applikationen transparent verwaltet werden, da der Zugriff auf Dateien ausschließlich über die von der Domain bereitgestellten Methoden durchgeführt wird. So kann bei jedem Aufruf von Close mit vorherigen Schreiboperationen automatisch eine Aktualisierung des Indexes bzw. der betroffenen Teile vorgenommen werden.

Erst in den Applikations-Klassen werden alle Methoden von DDataAbstract implementiert. Die Objekte von Applikations-Klassen repräsentieren damit eine konkrete Datei, die nach dem Aufruf von Load in aller Regel in den Arbeitsspeicher eingelesen wurde und zur Benutzung bereitsteht. Alternativ kann ein solches Objekt auch von einer Domain erzeugt worden sein, um durch Aufruf der Methode LoadMeta nur die Attributwerte einzulesen und danach in einem Index zu speichern.

Da der Dateiname nur ein Attribut unter vielen ist und im LCARS-Dateisystem keine Schlüsselfunktion mehr hat, können übrigens beliebig viele Dateien denselben Dateinamen haben:


Normalerweise eine Katastrophe:
zwei Dateien mit dem gleichen Namen


Digitaler Hub

Die stenge Typisierung und die Metadaten von LCARS-Dateien erlauben die Einführung von Funktionen, die über die reine Dateiverwaltung weit hinausgehen. Beim Schreibzugriff (Export) auf Geräte ohne kompatible Library geht der Zugriff auf Metadaten verloren, beim Lesezugriff (Import) muss er wiederhergestellt werden. Diese Aufgabe übernehmen sog. Übersetzer.

Beim Importieren, also Übertragen von Dateien in eine Library, wird das Dateiformat normiert, so dass es einem intern von einer Applikation verwalteten Dateiformat entspricht. Dabei können die Besonderheiten verschiedener Geräte, z.B. die proprietären Metadaten in JPEG-Bildern, die von einem Siemens S65 erzeugt wurden, berücksichtigt werden. Darüber hinaus müssen evtl. zusätzliche Datenstrukturen wie Indexe angelegt oder aktualisiert werden. Beim Exportieren, also Übertragen von Dateien aus einer Library in ein herkömmliches Dateisystem, muss das Dateiformat einem vom Zielgerät oder -dateisystem akzeptierten Format entsprechen. Wird z.B. eine Bilddatei auf eine digitale Kamera übertragen, so muss in jedem Fall ein JPEG-Bild ausgegeben werden. Liegt das Bild in der Library in einem anderen Format vor, ist eine geeignete Konvertierung erforderlich.

Durch dieses Zusammenspiel von Übersetzern und Library lässt sich auf einfache Art und Weise ein sog. „Digitaler Hub“ realisieren. Mit Im- und Export-Modulen für diverse Geräte und Dateiformate kann automatisch ein Datenaustausch zwischen diesen Geräten durchgeführt werden. Ein Anwendungsbeispiel ist ein DESKWORK-PC, an den ein Mobiltelefon und eine Digitalkamera angeschlossen sind. Sie können nun mit ein paar Mausklicks ein Bild von der Kamera direkt als Logo an Ihr Mobiltelefon schicken ! Intern wird dazu das JPEG-Bild der Kamera in den LCARS-Datentyp „Bild“ umgewandelt. Wenn diese Datei nun ans Mobiltelefon gesendet werden soll, wird ein weiterer Übersetzer aktiv, der sie in ein BMP-Bild umwandelt, was das native Datenformat für die Logos aller unterstützter Mobiltelefone ist. Die notwendigen Konvertierungen der Dateiformate werden dabei automatisch und ohne Ihr Zutun veranlasst !


Von DESKWORK erkannte Geräte (Beispiel)


Weitere Informationen

In diesen Dokumenten finden Sie weiterführende Informationen zu Datenbanken und Dateisystemen.

Vortrag „Gemeinsamkeiten von Datenbanken und Dateisystemen
Gehalten am 16.11.2006 im Diplomanden- und Doktorandenseminar des LS1, Universität Dortmund
Vortrag „Eine Speziallösung für multidimensionales Indexieren
Gehalten am 23.11.2006 im Diplomanden- und Doktorandenseminar des LS1, Universität Dortmund
Vortrag „DESKWORK 9.0 HTTP server
Gehalten am 10.11.2007 beim 21. „SuperHappyDevHouse“, San Francisco
Testprogramm zur Ermittelung des verschwendeten Speicherplatzes auf Laufwerk C:
EXE-Datei für DOS incl. Quellcode für Borland/Turbo Pascal
Stand: 30.11.2007
Vortrag „File systems should be like burger meals: Supersize your allocation units !
Gehalten am 27.02.2008 bei der USENIX Conference on File and Storage Technologies, San Jose
A relational filesystem as an example for tailor-made DMS
11th International Conference on Extending Database Technology
25.03.2008 - 29.03.2008, Nantes
Vortrag „A relational file system as an example for tailor-made DMS
Gehalten am 29.03.2008 bei der 11th International Conference on Extending Database Technology, Nantes
Einführung in relationale Datenbanken und semantische Dateisysteme
Stand: 23.07.2008
Indexing file attributes with the master/slave index
SAICSIT Conference 2008
06.10.2008 - 08.10.2008, George (Wilderness)
Vortrag „Indexing file attributes with the master/slave index
Gehalten am 06.10.2008 bei der SAICSIT Conference 2008, George (Wilderness)
Vortrag „Integration, Indexierung und Interaktion hochdimensionaler Datenobjekte
Gehalten am 18.02.2009 an der Technischen Universität Dortmund
Integration, Indexierung und Interaktion hochdimensionaler Datenobjekte
Dissertation, Technische Universität Dortmund
Stand: 05.03.2009