Masterarbeiten

Baqend + Uni Hamburg

Abschlussarbeiten von Baqend und der DBIS Arbeitsgruppe von Prof. Ritter

Offene Masterarbeiten

Providing Low Latency for PostgreSQL through the Orestes Caching Middleware

Orestes ist eine datenbankunabhängige Cloud-Middleware für (NoSQL) Datenbanken, die durch Caching extrem geringe Latenz erzielt. Orestes ist so konzipiert, dass durch die Implementierung bestimmter Schnittstellen (z.B. CRUD, Queries, Schemaänderungen) beliebige Datenbanken angebunden und durch eine Unified REST APIeinheitlich angesprochen werden können. Die Datenbank wird dabei automatisch angereichert um Fähigkeiten, die ihr sonst fehlen, u.a. gloabl verteiltes Web-Caching, semi-strukturierte Schemata, Zugriffskontrolle durch ACLs, etc. Ziel der Arbeit ist die Anbindung eines der Systeme DynamoDB, Cassandra, HBase oder PostgreSQL mit einer Studie darüber, welche Eigenschaften sich erzielen lassen und welche aufgrund der Datenbankarchitektur und seiner Schnittstellen nicht erreichbar sind.

Ziele:

  • Analyse der Datenbankeigenschaften aus Sicht der verschiedenen Orestes-Schnittstellen für CRUD, Queries, Partial Updates etc.
  • Problembeschreibung: Identifikation der fehlenden Fähigkeiten der Datenbank und Studie, welche sich durch Orestes automatisch erzielen lassen.
  • Konsistenzmodell: Welche Auswirkung haben die Konistenzgarantien der Datenbank für Clients und wie spielen sie mit Caching zusammen?
  • Optionale Vertiefung: welche Skalierbarkeitseigenschaften weist die Datenbank auf und wie können diese durch Orestes in Form von Auto-Scaling genutzt werden?
  • Implementierung: Anbindung der Datenbank an Orestes für die umsetzbaren Schnittstellen.
  • Evaluation:

Einführungsliteratur:

Vertiefungsliteratur:

Optimizing Bloomfilter-based Cache Coherence for Space and Cache Hit Rate

Ziel dieser Abschlussarbeit ist, es die False Positive Rate der Bloomfilter-basierten Cache Kohärenz in Orestes durch neuartige Strategien zu optimieren. Das Thema ist in zwei Bereiche aufgeteilt, die auch unabhängig voneinander untersucht werden können.

Ansatz für Server

  • Idee: der Bloomfilter (BF) kann serverseitig deutlich vergrößert werden, solange er bei Auslieferung effektiv komprimiert wird. Zu untersuchende und quantiativ zu vergleichende Strategien zu Kompression:
    • Halbierung der Bloomfiltergröße durch "Veroderung" beider Teile
    • Golomb codierte Sets
    • Sharding über mehrere Filter anhand des Datentyps oder Schemasubsets
    • Vergleich mit Standard Gzip und Brotli Kompressionsalgorithmen
  • Hypothese überprüfen: könnten Bloomier Filter verwendet werden, um die Version/Timestamps von Elementen mitzuspeichern und dadurch "Totzeiten" bei ungünstigen TTLs ganz vermeiden? (Wenn der Änderungszeitpunkt dem Client bekannt ist, können Elemente aktiv revalidiert werden deren Version nicht mit der im Bloomier Filter übereinstimmt).
  • Analog kann ein Count Min Sketch oder Counting Bloomfilter serverseitig den Änderungszeitpunkt pro Ressource codieren (nur Überschätzung möglich keine Unterschätzung). Ist die Performance insgesamt besser, wenn der Client stets abfragt ab, ob seine Version/timestamp des Cache entries größer ist (dann NICHT revalidieren) oder überwiegt der Overhead der größeren Datenstruktur

Ansatz für Client

  • Strategie I - Fingerprinting des Client Caches: Bloomfilter des Cache Inhalts konstruieren (gleiche Parametrisierung) und schicken. Serverseitig (in VCL möglich? Oder Lambda Edge? Cloudflare SW?) die Schnittmenge (Verundung der Filter) zurücksenden. Hypothese ist, dass die FPR signifikant reduziert, da die Schnittmenge sehr viel kleiner ist als das Set aller gecachter Inhalte.
  • Strategie II - Fingerprinting mit Versionen: wenn kleiner Cache oder während Client idle die URLs mit Last-Modified direkt schicken, oder als Bloomier, oder Counting Filter (Vorteil: Weiterverwendung von Cache Entries, die zwar im BF enthalten aber nicht stale im Client Cache).
  • Strategie III - Fallback auf Fingerprinting, wenn BF überfüllt: nur wenn empfangener BF zu voll, Strategie I oder II triggern, ansonsten den kleinen Bloomfilter verwenden (z.B. bis zu einer FPR Threshold von 1%).

Ansatz für Client

  • Quantitative Analyse der Strategien für sich: False Positive Rate, vs. Größe der Datenstruktur, vs. Overhead in der Client- und Server-seitigen Erzeugung und Pflege der Datenstruktur.
  • Case Study: Evaluation mithilfe von Speed Kit für eine größere Seite mit echtem Traffic und bekannten Workloads. Ladezeiten der Clients mit den verschiedenen Strategien vergleichen, z.B. auf Basis von WebPagetest.

Literatur:

Browser-based Staleness Detection for Highly Dynamic Websites

Die Idee für diese Abschlussarbeit ist, dass personalisierte Seiten in Speed Kit automatisch erkannt werden (über Dynamic Blocks hinaus). Um Inkonsistenzen zu vermeiden, sollen die entsprechen HTML Dateien dann in diesem nicht mehr aus dem Cache ausgeliefert werden und stattdessen nur noch statische Ressource beschleunigt werden.

Das Konzept zur Beschleunigung personalisierter Websites mit Speed Kit basiert auf folgenden 4 Bausteinen:

  1. Erkennen von Personalisierung
  2. Unterscheiden von personalisierten Seiten und lediglich divergierenden Versionen
  3. Dynamisches Backlisten von personalisierten Seiten
  4. Reaktivieren des Caches für nicht mehr personalisierte Seiten

Außerdem wird davon ausgegangen, dass für vorhersehbare Personalisierung (bspw. Login und Warenkorb) bereits Dynamic Blocks eingesetzt werden.

Erkennen von Personalisierung

Zur Erkennung von Personalisierung soll Speed Kit folgendermaßen vorgehen (siehe Abbildung 1 weiter unten):

  • Beim Anfragen der Seite, stellt Speed Kit zwei HTML Requests (1). Einen gegen Baqend’s Caching Infrastruktur und einen gegen die Originalseite. Die von Baqend gecachte, schnelle Response wird an den Browser gegeben. Sobald die Response der Originalseite eintrifft, können die Dynamic Blocks ausgetauscht werden (2). Im Hintergrund (asynchron, weil nicht zeitkritisch) werden die beiden Responses in einem Web Worker (zusätzlicher Worker-Thread) per DOM-Diffing verglichen (3). Ergibt sich hierbei, dass sich die Seiten nicht nur bezüglich der dynamischen Blöcke unterscheiden, wird eine mögliche Personalisierung an Baqend’s Server reported.

Der Server löst daraufhin eine Revalidierung der Seite aus und entscheidet, ob die Seite geblacklistet wird. Für alle folgenden Nutzer, die eine geblacklistete Seite laden, wird das HTML vom Originalserver geladen und alle Assets weiterhin über Speed Kit beschleunigt.

Unterscheiden von personalisierten Seiten und lediglich divergierenden Versionen

Wenn eine Seite tatsächlich personalisiert ist, sollte sie geblacklistet und damit für andere Nutzer nicht mehr gecacht werden. Um diese Entscheidung zu treffen, muss der Baqend-Server zwischen einer personalisierten Seite und einer Seite, die noch nicht in der aktuellen Version vorliegt unterscheiden. Das passiert auf folgende Weise:

  • Wenn ein Nutzer eine Seite als personalisiert reportet, wird als erstes eine Revalidierung ausgelöst (1), damit in jedem Fall die aktuelle Version der Seite vorliegt. Stellt sich bei der Revalidierung heraus, dass die Seite nicht geändert wurde, steht fest, dass es sich um eine personalisierte (oder A/B-getestete) Seite handelt. Die Seite wird daraufhin für die nächste Stunde (konfigurierbar) auf die Blacklist gesetzt (3).

Hat sich die Seite bei der Revalidierung geändert, kann der Server nicht mit Sicherheit sagen, ob es sich um eine personalisierte Seite handelt. Er verlässt sich deshalb auf 2 einfache Mechanismen. Angenommen die Seite ist personalisiert, dann A) ändert sie sich aus Sicht des Baqend Servers nur sporadisch oder B) ändert sich für den Baqend Server bei jedem Aufruf.

In Fall A) wird sich bei einem der folgenden Nutzer-Reports die Seite beim Revalidieren nicht ändern und somit die Seite auf die Blacklist gesetzt.

In Fall B) greift der nächste Schritt (2). Es wird geprüft, wie viel Zeit zwischen den Revalidierungen der Seite liegt. Wird die Updaterate zu hoch, wird die Seite zur Blacklist hinzugefügt, da sie ohnehin nicht gut cachebar ist. Ändert sich die Seite, wie in Fall B) bei jedem Aufruf, wird sie demnach sehr schnell der Blacklist hinzugefügt.

Dynamisches blacklisten von personalisierten Seiten

Das Blacklisten einer Seite funktioniert wie folgt:

Der Service Worker fragt, wie gewohnt sowohl über Baqend’s Caching-Infrastruktur als auch über den Originalserver die HTML Datei an (1). Anhand von Metadaten an der gecachten Response, kann Speed Kit direkt feststellen, dass die Seite geblacklistet ist und daraufhin die Originalseite an den Browser übergeben (2). Dynamic Blocks müssen in diesem Fall natürlich nicht ausgetauscht werden.

Die gecachte Response wird nicht an den Browser gegeben. Trotzdem werden weiterhin asynchron per DOM-Diffing die beiden Seiten verglichen und ggf. eine Personalisierung an den Baqend Server gemeldet. Damit kann sichergestellt werden, dass die Seite nur so lange wie nötig auf der Blacklist bleibt (siehe nächsten Abschnitt).

Reaktivieren des Caches für nicht mehr personalisierte Seiten

Seiten, die nicht mehr personalisiert sind, sollten automatisch wieder von Speed Kit gecacht werden. Hier erweist sich der Mechanismus, der im Abschnitt 2 beschrieben wurde als besonders elegant:

Während eine Seite auf der Blacklist ist, reporten die Nutzer weiterhin asynchron, ob sie unterschiede zwischen der Originalversion und der gecachten Version sehen, die nicht innerhalb von Dynamic Blocks liegen. Die Nutzer tun dies, obwohl sie die gecachte HTML Version nicht im Browser anzeigen (diese ist ja geblacklistet).

Wann immer der Server in dieser Zeit entscheidet, dass die Seite personalisiert ist, wird die Zeit auf der Blacklist auf 1h erhöht. Bei der Entscheidung verwendet der Server die gleiche Kriterien, wie in Abschnitt 2 beschrieben. Dadurch bleiben personalisierte Seite dauerhaft auf der Blacklist; nicht mehr personalisierte Seiten, sind aber nach einer Stunde wieder cachbar.

Literatur:

Constraint-Checking in Distributed Database-as-a-Service Systems

In dieser Arbeit soll untersucht werden, welche Constraints auf Datenmodell-Ebene wichtig für ein Database/Backend-as-a-Service System sind und wie sie deklarativ umgesetzt werden können. Beispiele für derartige Constraints sind Wertebereiche (z.B. Datum zwischen x und y) oder Not-Null-Constraints. Diese Form der Datenmodell-gebundenen Verifizierung von Constraints hat den großen Vorteil, dass sie keiner zusätzlich zu wartenden Code-Basis bedarf und direkt im Frontend, z.B. bei der Formularvalidierung, genutzt werden kann.

Ziele:

  • Recherche: Aufstellen einer Matrix, die Datentypen zu sinnvollen Constraints in Relation setzt, d.h. für welchen Datentyp sind welche Validierungen sinnvoll? Als Grundlage können hier Content-Management-Systeme und SQL dienen. Systematische Unterteilung von Constraints nach ihren Anforderungen: benötigt nur neues Objekt (z.B. Range Constraints), benötigt Informationen über andere Objekte (z.B. Unique Constraint), benötigt vorherige Version des Objekts (z.B. monoton steigende Versionsnummern).
  • Entwurf und Implementierung eines Constraint-Checkings in Orestes. Hier soll das bestehende Schema-System so angepasst werden, dass Constraints automatisch und skalierbar geprüft werden. Dazu soll die vorhandene Schema-Web-UI (siehe Baqend-Webseite) so angepasst werden, dass Constraints elegant deklariert werden können.
  • Evaluation der Implementation durch Tests auf Erfüllung der Constraints und einer kleinen Case-Study (z.B. komplexes Formular mit Randbedingungen).

Literatur:

Polyglot Persistence Mediator: Annotation-based Scoring

Der Polyglot Persistence Mediator (PPM) ist die Vision einer automatisierten Verwendung verschiedener Datenbanksysteme (Polyglot Persistence) durch die deklarative Angabe von Anforderungen. Diese werden in Form von Service Level Agreements (z.B. Latenz < 30ms, Top-K-Queries) am Schema annotiert. Ein Scoring ermittelt anhand dieser Annotationen die ideale Datenbank für jedes Element des Schemas (Routing Model). Der PPM routet zur Laufzeit gemäß des Routing-Models die Anfragen und CRUD Operationen zur passenden Datenbank. Ziel dieser Arbeit ist das Anlegen eines Katalogs einiger umsetzbarer Annotationen/SLAs, die Implementierung des Scoring Algorithmus für diese SLAs (siehe Paper), sowie die Umsetzung des Routings für die Kombination aus Redis und MongoDB.

Ziele:

  • Katalog von SLAs anlegen: kategorisieren nach functional, non-functional und continuous non-functional, Annotationslevel (DB, Table, Feld). Jeweils “Patterns” zu einer möglichen naiven Implementierung ohne PPM sammeln, zu messende Metriken und Arten der Erfassung pro SLA diskutieren, bei binären Eigenschaften: Literatur-Recherche, wie/ob sie in Redis und MongoDB sicherzustellen sind.
  • Routing-Strategien: Katalog für die notwendigen Aktionen des PPMs zur Sicherstellung der jeweiligen SLAs diskutieren, sowie Metrik-Erfassung. Vier Modelle erötern:
    • PPM-mixed: unterschiedliche Zieldatenbanken für jedes Schemaelement (Feld, Table, DB) zulassen -> maximale Heterogenität, maximaler Koordinationsaufwand, potentiell ideale Performance
    • PPM-microbatched: wie PPM-mixed, aber ein System wird als “primary database” designiert und erhält in Microbatches (z.B. alle 5 Sekunden), alle (verdichteten) Updates -> beliebige Queries auf allen Daten mit Staleness-Bound des Microbatch-Intervalls
    • PPM-entity: Es wird garantiert, dass Objekte jeweils vollständig (ohne Zerlegung) in einer Datenbank angespeichert werden -> einfaches Routing, ponteziell konfliktierende Anforderungen zwischen Feldern
    • PPM-advisory: Es wird lediglich ermittelt, welche Datenbank für das Gesamtschema den besten Score erzielen kann -> effektiv kein Routing und keine polyglotte Persistenz, sondern nur ein Hint welches System insgesamt den besten Trade-off liefert.
  • Implementierung: SLAs modellieren und Schema erweitern um Annotationen zu tragen. Scoring Algorithmus aus Paper implementieren und Routing Modell generieren. Laufzeit-Routing für ausgewählte SLAs in Orestes implementieren, d.h. korrekte Weiterleitungen an die Redis und MongoDB Schnittstellen und Ergänzungen von Metadaten, um spätere Auflösung bei Reads und Queries vorzunehmen.
  • Evaluation: Performance verschiedener SLA-Kombinationen messen und mit nicht-polyglotter Umsetzung auf jeweils MongoDb und Redis vergleichen (mit und ohne Orestes).

Einführungsliteratur:

Vertiefungsliteratur:

Content Management for Serverless Architectures

In dieser Arbeit soll untersucht werden, wie Content-Management Funktionen in Backend-as-a-Service (BaaS) Systemen implementiert werden können. Bisher treten beide Paradigmen getrennt auf: BaaS als wichtiger Ansatz für Serverless Architectures verspricht durch potente Standard-APIs für Daten und Anwendungslogik die Entwicklung von Webseiten und Apps zu vereinfachen, während Content Management Systeme (CMS) integraler Bestandteil vieler Webplattformen sind, um Autoren und Redakteruren eine möglichste einfache Gestaltung von Inhalten zu ermöglichen. Diese Arbeit soll untersuchen, wie sich Content Mangement in der BaaS-Plattform Orestes umsetzen lässt, um die Vorteile beider Ansätze zu vereinen.

Ziele:

  • Recherche: Welche Funktionen benötigt ein modernes CMS: Autoren-UI, Audit-Trail mit Versionshistorie, verschiedene Zustände von Artikeln (Draft, Public)? Wie funktioniert die Datenmodellierung in Orestes/Baqend? Kann ein bestehendes Headless CMS (z.B. Netlify CMS) oder ein Static Site Generator (Jekyll) sinnvoll adaptiert werden?
  • Entwurf und Implementierung von Content Management in Orestes: neue Autoren-Dashboard-Oberfläche zum Editieren und Prüfen von Content. Erweiterung der Datenmodellierung um Abstraktionen für Content-Management (welche Felder können geändert werden, wie werden sie dargestellt, Constraints, etc.).
  • Evaluation der Implementation durch die Realisierung eines Blogs oder einer News-Webseite als Case Study. Vergleich der Funktionalität mit verbreiteten CMS. Performance-Analyse z.B. gegenüber Wordpress oder Drupal.

Literatur:

The NoSQL Toolbox: an Interactive Database Selection Tool

In dieser Arbeit soll die Idee des “NoSQL Entscheidungsbaums” weiterentwickelt werden zu einem interaktiven Web-Tool. Ziel: Anwender geben ihre Anforderungen ein (z.B. geringe Latenz bei Reads, Joins, hohe Verfügbarkeit) und das Tool wählt darauf in Frage kommende NoSQL Systeme aus. Das existierende Klassifikationsschema kann dabei erweitert und um neue Dimensionen vertieft werden. Ferner ist eine “User-generated Recommendations” Funktion interessant, bei der Anwender ihre Erfahrungen mit den jeweiligen Systemen angeben, die daraufhin mit in den Bewertungsschlüssel einfließen.\ Die Arbeit basiert auf:

Ziele:

  • Analyse des NoSQL Toolbox Ansatzes (siehe Paper und Präsentation)
  • Entwurf und Implementierung einer Webanwendung zu Filterung passender Systeme, mit Bewertungsoption durch Nutzer.
  • Erweiterung des NoSQL Toolbox Ansatzes um weitere Systeme, z.B. anhand von DB Engines.

Einführungsliteratur:

Vertiefungsliteratur:

  • Ressourcensammlung zu unseren Veröffentlichungen, Talks, etc.
  • NoSQL Literatur aus dem allgemeinen Teil oben
  • Vorschlag zur Umsetzung als Web-Anwendung: Angular.js mit Baqend

A Scalable Revalidation Architecture for Large-Scale Web Content

In dieser Arbeit soll eine Architektur konzipiert und entwickelt werden, die in der Lage ist, den gesamten Content großer Webseiten effizient und skalierbar zu aktualisieren und sowohl als Rohdaten (Files) und Metadaten (Attribute, z.B. Content Type) abzuspeichern.

Ziele:

  • TBD

Literatur:

  • TBD

Attributbasierte Invalidierung

In dieser Arbeit soll die Querysprache um Projektionen (vgl. MongoDB) erweitert und die Invalidierung mithilfe der Bloomfilter verfeinert werden.

Die Querysprache ermöglicht es bisher u.A. ganze Datenbankobjekte zu laden. Durch Projektionen wäre es jedoch auch möglich nur Teilmengen eines Objektes zu laden. Diese Erweiterung müsste im ersten Schritt implementiert werden. Die aktuelle Invalidierung mithilfe der Bloomfilter reagiert auf beliebige Änderungen innerhalb eines Datenbankobjektes. Würde nun mithilfe der zuvor implementierten Projetionen z. B. der Name einer Person abgefragt werden, würde das Queryergebnis auch dann invalidiert werden, wenn sich die Adresse ändert. Folglich müsste die Invalidierung im nächsten Schritt feiner gestaltet werden. Queries sollen nur dann invalidiert werden, wenn die Projektion eine Schnittmenge zu den Änderungen hat. Dabei soll insbesondere die Auswirkung auf den Bloomfilter untersucht werden. Dabei stehen Größe und False-Positive Rate im Vordergrund. Als Kompromiss könnte dann noch untersucht werden, inwieweit sich einzelne Attribute eines Datenbankobjektes in dem Bloomfillter zusammenfassen lassen können. So führt z. B. eine Änderung der Hausnummer einer Person auch sehr wahrscheinlich zu einer Änderung der Straße und PLZ. Diese könnten somit als ein Objekt im Bloomfilter gespeichert werden. Hier wäre auch interessant, inwieweit sich eine solche Erkennung automatisieren lassen könnte. Abschließend könnten dann die Auswirkungen auf die Perfomance von der bisherigen Implementierung, der einzelnen Attribute und der Gruppierung gegenüber gestellt werden.

Ziele:

  • Entwurf und Erweiterung der Querysprache durch Projections
  • Analyse der Auswirkungen auf den Bloomfilter
  • Evaluation: Wie Verhalten sich die drei Implementierungen zueinander?

Literatur:

Benchmarking Real-Time Databases (Baqend vs. Firebase/Meteor/RethinkDB)

Real-time databases extend traditional databases through push-based access to data: Real-time queries produce not only the initial query result, but also a continuous stream of updates over time. While there is a wealth of benchmarking frameworks for traditional database functionality (e.g. TPC-*), there is currently no standardized approach for quantifying the characteristics of systems such as Firebase, Meteor, or Baqend. The goal of this thesis is to develop a benchmarking framework for real-time databases and to conduct a quantitative comparison of different real-time implementations.

Goals:

  • Design & Implementation of a system-agnostic framework for quantifying central aspects of a real-time database
  • Specification of a workloads that reflect typical usage scenarios
  • Performance Analysis for at least two contestants (e.g. Baqend & Firebase)

Literatur: