Masterarbeiten

Baqend + Uni Hamburg

Abschlussarbeiten von Baqend und der DBIS Arbeitsgruppe von Prof. Ritter

Offene Masterarbeiten

Performance-optimiertes A/B-Testing für E-Commerce-Webseiten

A/B-Tests sind eine im Web weit verbreitete Methodik, um neue Designs zu evaluieren oder die Empfänglichkeit von Nutzern/Kunden für bestimmte Angebote zu bestimmen. Typischerweise wird hierzu die Population der Nutzer (oder ein Teil davon) in 2 Gruppen unterteilt (normalerweise 50% vs. 50%). So kann beispielsweise eine Änderungen am Design der Webseite zunächst nur für eine der beiden Testgruppen ausgespielt werden, wobei die gleichen Metriken in beiden Gruppen erhoben werden. Durch den Vergleich der Messergebnisse zwischen beiden Gruppen kann kann zuverlässig ermittelt werden, ob die betrachtete Designänderung auch mit einer Verbesserung in den betrachteten Metriken einhergeht (beispielsweise Conversion Rate).

Es gibt diverse Tools die diese Funktionalität anbieten (Adobe Target, Trbo, ABTasty, …), welche jedoch alle einem kritischen Problem unterlegen sind: Die Durchführung eines A/B-Tests bedeutet nämlich einen gewissen Overhead beim Laden der Webseite und kann somit zu Lasten der Nutzererfahrung (UX) gehen und so auch die Ergebnisse maßgeblich verfälschen. Um diesen Effekt weitgehend zu vermeiden, wird bei der Webseitenbeschleunigung durch Speed Kit ein eigens entwickelter A/B-Testing-Ansatz genutzt. Das Ziel dieser Arbeit ist die Konzeption und prototypische Implementierung eines performance-optimierten A/B-Testing-Tools, welches die bereits in Speed Kit vorhandene Funktionalität erweitern kann.

Zunächst soll dazu die Tool-Landschaft für A/B-Testing genau analysiert werden, um eine Übersicht über übliche Features zu erstellen und ihre jeweiligen Auswirkungen auf die UX bzw. Performance herauszuarbeiten. Mit diesem Wissen soll dann in einem zweiten Schritt das Konzept eines A/B-Tools entworfen werden, das die Priorität auf Seitenperformance & UX setzt – im Zweifel auf Kosten der Funktionalität. In einem dritten Schritt soll der Ansatz prototypisch implementiert und evaluiert werden.

Ziele der Arbeit:

Recherche existierender A/B-Testing-Tools, insbesondere bezüglich deren Funktionsumfang (server-/clientseitig), Integrationsaufwand und Auswirkungen auf die UX / Performance (Latenz, Flicker Control etc.)
Kategorisierung der einzelnen Features nach Eigenschaften wie Tracking, Individualisierbarkeit, Verträglichkeit mit Caching & hohen Performance-Ansprüchen
Identifikation einer Liste an „Must-have“-Funktionalitäten für den Einsatz von A/B-Testing im Anwendungsfall Speed Kit
Konzeptionierung einer Erweiterung der bestehenden A/B-Funktionalitäten von Speed Kit, um diese „Must-haves“ zu erfüllen
Prototypische Umsetzung durch Erweiterung des Speed Kit-Clients (JavaScript)
Evaluation des Ansatzes durch Einsatz auf einer Webseite und Bestimmung des Overhead bzw. durch quantitativen Vergleich mit einem anderen Tracking-Tool

Literatur

Ressourcensammlung zu unseren Veröffentlichungen, Talks, etc.
Speed Kit Artikel auf Medium
Speed Kit Dokumentation

Anomaly Detection with RUM-Based Data

Heutige E-Commerce-Webseiten sind hochkomplex und so können selbst durch gründliche Qualitätssicherung und automatisierte Tests nicht alle Probleme vor Release aufgedeckt werden. Zusätzlich können durch Caching Layer oder Tools die frontend-seitige Veränderungen durchführen weitere Probleme auftreten. Um Umsatzeinbußen zu vermeiden, müssen daher Fehler im Betrieb umgehend erkannt und behoben werden. A/B Tests bieten die Möglichkeit lediglich einem Teil der Nutzer die neue Version auszuspielen und somit den möglichen Schaden gering zu halten. Hier werden dann verschiedene Metriken der beiden Gruppen miteinander verglichen um Auffälligkeiten und potentielle Fehlerquellen zu entdecken. Wenn keine A/B Tests vorhanden sind, können Vergleichswerte aus historischen Daten erhoben werden deren Überschreitung als Indikator dient.

Der Fokus dieser Arbeit liegt in der Erkennung von Fehlerszenarien anhand von Daten, die durch Real-User-Monitoring (RUM) auf Webseiten erhoben werden - sowohl in aufgeteilten Populationen (A/B Test) als auch auf Basis von Vergleichswerten.

Mögliche Anhaltspunkte für Vorliegen eines Fehlers könnten sein:

Drop in der Conversion Rate
Unterschiedliche Events (z.B. Klick auf bestimmte Elemente)
Unterschiedliche Sessionlängen
häufige oder unerwartete JavaScript-Fehler
Erhöhte Bouncerates auf bestimmten Seiten
Häufige Reloads
Signifikante Unterschiede bei Klickpfaden
sonstige Auffälligkeiten bei bestimmten Nutzergruppen (etwa nach Gerät oder Browser)

Im Rahmen der Arbeit sollen sowohl Analyseverfahren zur Erkennung von Fehlerszenarien erarbeitet als auch durch Einsatz von SQL (Batch-Verarbeitung) und Apache Flink (Echtzeitverarbeitung) praktisch umgesetzt werden. Zum Testen der erarbeiteten Lösung werden anonymisierte Daten aus Zeiträumen zur Verfügung gestellt, in denen tatsächlich Fehler beobachtet wurden. Diese wurden sowohl in A/B Tests, als auch in Vorher-nachher-Vergleichen mithilfe von Speed Kit erhoben.

Ziele der Arbeit:

Recherche:
- Wie können die derzeit erfassten Metriken zur Fehlererkennung genutzt werden?
- Gibt es neben den bisherigen noch weitere nützliche Metriken und wie können diese erfasst werden?
- Gibt es bereits Lösungen zur Fehlererkennung anhand von Tracking-Daten und welche Schwächen bzw. Stärken weisen diese auf?
- Wie können Fehler visualisiert werden? (z. B Ampelsystem oder eine Matrix)
Konzeption und Implementierung: Die automatisierte Fehlererkennung sollte auf Basis von Apache Flink implementiert werden. Einige der Kernaspekte sind:
- Parametrisierung: Wie kann die Erkennung flexibel eingestellt werden, sodass sie für große und kleine Webseiten gleichermaßen praktikabel ist?
- Eskalationslevel / Alerting: Welche Maßnahmen werden bei welcher Art von Fehler getriggert?
Evaluation: Evaluation auf Basis historischer und/oder aktueller Daten.
- Wie gut funktioniert die Erkennung? (Wie lange dauert es, bis hohe Konfidenz erreicht ist? Lässt sich dieser Trade-off konfigurieren? Wie gut können Schwankungen wie z.B. das Weihnachtsgeschäft berücksichtigt werden?)

Literatur

Ressourcensammlung zu unseren Veröffentlichungen, Talks, etc.
Speed Kit Artikel auf Medium
Speed Kit Dokumentation

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 API einheitlich angesprochen werden können. Die Datenbank wird dabei automatisch angereichert um Fähigkeiten, die ihr sonst fehlen: Beispiele für solche Fähigkeiten sind etwa global verteiltes Web-Caching, semi-strukturierte Schemata und Zugriffskontrolle durch ACLs. Ziel der Arbeit ist die Anbindung des Systems 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:

Dissertation zu Orestes
Ressourcensammlung zu unseren Veröffentlichungen, Talks, etc.
PostgreSQL

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:

Grundlagen zu Bloomfiltern:
Ressourcensammlung zu unseren Veröffentlichungen, Talks, etc.
Doktorarbeit von Felix, insbesondere Kapitel 3 und 4 und Related Work zu Datenstrukturen
The Cache Sketch: Revisiting Expiration-based Caching in the Age of Cloud Data Management
Quaestor: Query Web Caching for Database-as-a-Service Providers
Cache Digests HTTP/2

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:

Erkennen von Personalisierung
Unterscheiden von personalisierten Seiten und lediglich divergierenden Versionen
Dynamisches Backlisten von personalisierten Seiten
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:

Ressourcensammlung zu unseren Veröffentlichungen, Talks, etc.
"Service Workers: The Technology Behind Progressive Web Apps" - Talk von Felix auf der Code.Talks - Slides | Video
Speed Kit Artikel auf Medium sowie weitere Blog-Posts
Speed Kit Dokumentation

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.