University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Marc Kramis

Research Student in the PhD program from 01.09.2008 to 31.12.2012.

advisors

  1. Prof. Dr. Marcel Waldvogel
  2. Prof. Dr. Marc Scholl

organisational data

Room:
Tel.:
E-mail:marc.kramis [at] uni-konstanz.de
Other Resources:
picture

project description

Grundlagen : Im Rahmen meiner Untersuchungen zu Personal Information Management, Collaborative Document Authoring und Geographic Visual Analytics habe ich festgestellt, dass heutige Systeme i.d.R. nur den aktuellen Zustand der Daten reproduzieren können, d.h., denjenigen Zustand, der durch die letzte Benutzermodifikation erzeugt wurde. Nur wenige Systeme erlauben den Zugriff auf vergangene Zustände und die jeweiligen änderungen. Diese Funktionalität kann auf Seite der Applikation nur unter Inkaufnahme einer erhöhten Komplexität nachgebildet werden. Davon betroffen sind Design, Implementation, Tests auf Sonderfälle und die Ausführungsgeschwindigkeit. Als mögliche Ursache für die mangelnde Unterstützung für vergangene Zustände und änderungen habe ich die historisch stark limitierte Zugriffsgeschwindigkeit und Kapazität der Speichermedien identifiziert. Erst in neuerer Zeit haben sich die Speichermedien durch Anwendung neuer Technologien wie z.B. Flash oder Perpendicular Recording in die Geschwindigkeits- und Speichergrössenordnungen entwickelt, die nötig sind, um nebst dem letzten Zustand auch die vergangenen Zustände und änderungen zu speichern. Erstaunlicherweise nützen Dateisysteme und Datenbanken diese neuen Möglichkeiten nur vergleichsweise selten aus, d.h., sie reduzieren die Objektgrösse der persistent gemachten Daten noch zu wenig konsequent. Diese Reduktion ist selbst mit den heute vorhandenen grossen Speichermedien notwendig, um die laufend wachsenden Datenbestände und den Wunsch nach Miniaturisierung und Energieeffizienz zu stillen. Insgesamt habe ich zu diesem Themenkreis zwei grundlegende Thesen aufgestellt:
  1. Degree of Granularity: Je schneller ein Speichermedium auf einen zufälligen Speicherbereich zugreift, desto feiner können die gespeicherten Objekte gegliedert und desto effizienter können gewünschte Informationen auch aus grossen Datenmengen extrahiert werden (Fig. 1).
    Fig 1. Degree of granularity in Relation zur wahlfreien Zugriffszeit und Objektgrösse.
  2. Evolution of State : Je feiner die gespeicherten Objekte gegliedert werden, desto besser kann man die natürliche überführung eines Zustandes in den nächsten mittels einer änderung abbilden. Die änderung selbst wird dabei zu einem Teil des neuen Zustandes und kann gleichermassen als selbstständiges Objekt oder im Verbund erfragt werden (Fig. 2).
    Fig 2. Evolution of state durch eine Sequenz von Modifikationen.
Beide Mechanismen können in meiner Arbeit dank durchgängiger Versionierung und Append-Only-Semantik sehr effizient und einfach abgebildet werden.

Storage Manager Interface: Mit einem einfach zu verwendenden Interface erschliesse ich dem Benutzer den Zugang zu vergangenen Zuständen und den jeweiligen änderungen. Die Schnittstelle kann dabei gleichermassen über einen RESTful HTTP-Service oder über ein API angesprochen werden. Prototypisch wurde dazu ein XML-Schema für Anfragen und Antworten entwickelt und die RESTful URL um eine temporale Komponente ergänzt. Diese wird durch runde Klammern begrenzt und dient der Unterscheidung zwischen einer Anfrage an einen Zustand (Zeitpunkt) oder an die änderungen zwischen zwei Zuständen (Zeitperiode). Durch die Einheitlichkeit der Schnittstelle habe ich erreicht, dass eine Implementation auf einer herkömmlichen (objekt-)relationalen Datenbank aber auch einer nativen XML-Datenbank basieren kann.

Storage Manager: Ich habe einen Storage Manager entwickelt, der auf die Bedürfnisse des beschriebenen Storage Ich habe einen Storage Manager entwickelt, der auf die Bedürfnisse des beschriebenen Storage Manager Interfaces optimiert wurde und folgende Features bietet:
  • Einheitlicher Storage Manager für baumbasierte Datenstrukturen wie z.B. B+-Baum oder Trie;
  • Integrierter Zugriff auf alle Zustände und änderungen des gespeicherten Baumes;
  • Stark verbesserte Speichereffizienz für änderungen dank Techniken wie Sliding Snapshot und Dynamic Page Compression;
  • Hochparallelisierbare Multicore-Architektur für die Software- und Hardware-Implementation;
  • Optimiertes Speicherlayout für hochperformanten Zugriff bei gleichzeitigem sequentiellen Schreiben, siwe zufälligem Lesen - wie es z.B. durch neuere flashbasierte Medien sehr gut unterstützt wird;
  • Bewährte Sicherheitsalgorithmen für starke Verschlüsselung und Ende-zu-Ende-Integrität;
  • Geschützter transaktionaler Zugriff, der zu jedem Zeitpunkt mehrere lesende und (vorerst) einen einzigen schreibenden Zugriff erlaubt;
  • Zuverlässige, automatische und inkrementelle Sicherheitskopie auf einem oder mehreren lokalen oder entfernten Storage Managern zur aktiven Nutzung der Redundanz.

  • Diese modulare Kombination erlaubt es, mittels eines oder mehreren kleinen, energieeffzienten Geräten eine verlässliche baumstrukturierte Datenbank für sehr grosse Datenmengen mit vollem Einblick in die Vergangenheit zu erreichen.

    publications

    The following list of publications covers only those, which are or were published during participation at the Graduiertenkolleg / PhD program.

    Articles in Journals

    2009

    Conference Papers

    2011200820072006
    2011
    2008
    2007
    2006

    Phd Theses

    2014