Sortierung, Seitengrössen und algorithmische Ungerechtigkeit

Angenommen wir hätten ein System, dass Suchresultate paginiert (d.h. die Resultate werden in mehrere Seiten aufgeteilt) und nach Anzahl Interaktionen sortiert auflistet. Ein solches System könnte zum Beispiel ein Online Shop (Käufe), eine Suchmaschine (Clicks), ein Social Media Feed (Clicks) oder ein News-Aggregator (Clicks) sein. Hat die Darstellung der Resultate einen Einfluss auf die resultierende Verteilung der Interaktionen? Führt dies zu einer durch den Algorithmus eingeführte Ungerechtigkeit, d.h. werden einige Resultate mit der Zeit ungerechtfertigt bevorzugt behandelt? Eine erste Idee der Auswirkungen eines solches Systems kann durch Simulation gewonnen werden!

Modell

Für die Simulation wird eine agentenbasierte Modellierung verwendet. Jeder Agent durchstöbert eine paginierte, sortierte Liste von Elementen und interagiert mit einem zufällig ausgewählten Element. Es besteht die Möglichkeit, dass der Verbraucher nur die erste Seite durchblättert. Nach einigen Interaktionen wird die Liste absteigend nach Anzahl Interaktionen sortiert.

Zur Bestimmung der Ungleichverteilung wird der Hoover Index (der normierten mittleren absoluten Abweichung) berechnet:

Resultat

Eine Simulation mit 100 Elementen und 50 Interaktionen / Agenten pro Sortierung zeigt, dass je kleiner die Seitengrösse und je grösser die Wahrscheinlichkeit, nur die erste Seite zu durchstöbern, desto grösser die resultierende Ungleichverteilung. Überraschend ist dabei, dass bereits sehr geringe Wahrscheinlichkeiten zu einer merkbaren Ungleichverteilung führen.

Abbildung 1: Ungleichverteilung in Abhängigkeit der Seitengrösse und Wahrscheinlichkeit.

Weiter ist zu sehen, dass die Ungleichverteilung bereits nach wenigen Neusortierungen entsteht und relativ konstant bleibt (100 Items, Seitengrösse 20). Das Histogramm zeigt eine bimodale Verteilung: Einige wenige Elemente besitzen viele Interaktionen, viele Elemente haben nur sehr wenige Interaktionen.

Abbildung 2: Entwicklung der Ungleichverteilung und finale Verteilung.

Moderierende Faktoren

In einem solchen System kann es weitere moderierende Faktoren geben, welche zum Beispiel den Effekt der Ungleichverteilung abschwächen. Ein solcher Faktor könnte zum Beispiel ein maximales Alter der Elemente sein, z.B. in einem Shop Artikel, welche nicht mehr geliefert werden.

Das Modell wird so angepasst, dass jedes Element ein Alter in Anzahl Sortierungszyklen besitzt und nach einer bestimmten Anzahl Zyklen durch ein neues (mit Alter 0) ersetzt wird. Die initialen Elemente werden mit zufälligem Alter initialisiert.

Eine Simulation mit 100 Elementen, 50 Interaktionen / Agenten pro Neusortierung und einer Seitengrösse von 20 zeigt, dass die Ungleichverteilung dadurch bereits zu Beginn höher ist. Allgemein ist die Ungleichverteilung grösser, je kleiner das maximale Alter.

Abbildung 3: Ungleichverteilung in Abhängigkeit der Seitengrösse und Wahrscheinlichkeit, mit rotierendem Bestand.

Ein Blick auf die zeitliche Entwicklung (100 Items, Seitengrösse 20) zeigt den Unterschied zu vorher: Zwar gibt es auch hier bereits nach wenigen Neusortierungen bereits eine Ungleichverteilung, diese variiert mit der Zeit aber stärker. Zudem gibt nun eine unimodale Verteilung statt einer bimodalen Verteilung: die meisten Elemente besitzen nur wenige Interaktionen. Die Verteilung scheint ein kleines Bisschen fairer.

Abbildung 4: Entwicklung der Ungleichverteilung und finale Verteilung, mit rotierendem Bestand.

Weiterführende Informationen

Proxy Cache Simulation

Im modernen Web findet man oft den für eine Webapplikation typischen Aufbau mit Webserver und Applikation. Ein Benutzer macht dabei die Requests alle an einen Webserver (NGINX, Apache, Traefik) welche seinerseits die Requests an eine Applikation (z.B. Django) weiterleitet.

Der Webserver kümmert sich dabei typischerweise um Themen wie SSL Terminierung oder Load Balancing. Neben diesen Aufgaben kann aber der Webserver aber auch als sogenannter Proxy Cache agieren, dabei werden die Antworten bestimmter Requests im Cache gespeichert und von da aus beantwortet, die Requests gelangen nie zur Applikation.

Wie viel bringt ein solches Proxy Caching in welchen Situationen? Ein Experimentieren am laufenden System erfordert teure Load Tests und mühsame Auswertung von Serverlogs. Einen ersten Einblick in das Verhalten und das Auswirken von Variieren der Parameter kann aber auch einfacher mittels Simulation erhalten werden.

Modell

Für die Simulation wird SimPy verwendet, ein Python Paket für diskrete Ereignissimulation. Das ganze System wird über verschiedene Klassen modelliert, welche sich an der Übersicht weiter oben orientieren:

  • Der UserGenerator erzeugt exponentialverteilt mit einer gegeben Ankunftsrate neue User.

  • Ein User erzeugt einen initialen Page-Request (z.B. HTML Seite) und anschliessend 5 gleichzeitige Asset-Requests (z.B. JavaScript, CSS, Webfonts).

  • Der Page- oder Asset-Request wartet der Reihe nach auf einen Webserver-Worker, eine Applikations-Instanz (falls ohne Cache), die Application-Antwort (falls ohne Cache) und schliesslich auf die Webserver-Antwort.

  • Der Webserver ist eine Warteschlange mit einer Kapazität von 768 Worker und einer triangular-verteilten Verarbeitungszeit von 10/15/20ms.

    • Optional werden für den Cache Page-Requests für 5s respektive Asset-Requests unendlich lange beim ersten Request gespeichert.

  • Die Application ist eine Warteschlange mit einer Kapazität von 4 Instanzen und triangular-verteilten Verarbeitungszeit von 0.5/5/60s für Page-Requests respektive 100/150/200ms für Asset-Requests.

Währen der Simulation werden pro Request verschiedene Zeiten gemessen:

  • waiting_time_webserver : Wie lange auf einen Webserver-Worker gewartet wird.

  • waiting_time_application : Wie lange auf eine Applikations-Instanz gewartet wird.

  • response_time_application: Wie lange die Applikation für die Antwort braucht.

  • response_time_webserver: Wie lange der Webserver für die Antwort braucht.

  • total_time: Die Gesamtzeit des Requests.

Baseline: Ohne Cache

Ohne Cache – d.h. jeder Request wird vom Webserver direkt an die Applikation weitergereicht – steigt die Drop Rate – d.h. die Anzahl Requests, welche während der Simulationszeit von einer Stunde nie eine Antwort erhalten – ab einer Rate von rund 10 Benutzern pro Minute.

Bei nur einem Benutzer pro Minute gibt es keine Wartezeiten und die Antwortzeiten bestimmen sich durch die vorgegebenen Verteilungen. Die Gesamtzeit ist praktisch nur von der langsamen Applikation bestimmt. Bei 50 Benutzern pro Minute zeigt sich hingegen ein anderes Bild: Hier sind nun die Antwortzeiten verhältnismässig irrelevant, am meisten Zeit braucht das Warten auf eine Applikations-Instanz sowie das Warten auf einen Webserver-Worker. Das Bottleneck ist wie zu erwarten die langsame Applikation.

Caching von Assets

Assets wie JavaScript-, CSS- und Webfont-Dateien verändern sich relativ selten und können daher meist problemlos für einen längeren Zeitraum im Cache des Webserver gespeichert werden. Request für solche Dateien werden dadurch bereits vom Webserver beantwortet, die Applikation wird weniger belastet. Zwar steigt auch hier die Drop Rate ab ca. 10 Benutzern pro Minute, allerdings etwas weniger steil.

Deutlich gesunken ist hingegen die durchschnittlich Gesamtzeit (aufgrund der schneller beantworteten Assets-Requests). Immer noch ist jedoch das Warten auf freie Applikationsinstanzen das Bottleneck, da jeder User einen intitialen Page-Request benötigt. Mit steigender Anzahl Benutzer werden auch diese Requests nicht mehr beantwortet und der Assets-Cache ist wirkungslos.

Wie wirkt sich eigentlich eine Erhöhung der Anzahl Instanzen und Worker aus? Mit der Erhöhung der Anzahl Instanzen sinkt die Drop Rate stark, da mehr Requests gleichzeitig abgearbeitet werden können. Aber auch die Erhöhung der Anzahl Worker wirkt sich positiv auf die Drop Rate aus, da diese die stark variierende Antwortzeit der Applikation aber auch die unterschiedlichen Ankunftszeiten der User glätten können.

Caching von Pages und Assets

HTML Seiten sind generell kritischer bezüglich Cache, da sie meist dynamisch sind. Die Anzahl möglicher Benutzer pro Minute ohne Drop Rate steigt um den Faktor 100. Bereits eine nur kurze Cache Dauer von 5s für Page-Requests kann aber bereits einen starken Einfluss haben, da damit Spitzen gebrochen werden können.

Auch die mittlere Antwortzeit sinkt mit nur wenigen Sekunden Pages Cache. Schlussendlich ist auch hier wieder die langsame Applikation das Bottleneck respektive das Warten auf freie Applikations-Instanzen.

Ressourcen

Monte-Carlo-Simulation des Kartenspiels “Tschau Sepp”

Wie oft sagt man eigentlich im Spiel “Tschau Sepp” durchschnittlich “Tschau”? Die kurze Antwort: Einmal, und zwar egal ob man verliert oder gewinnt. Die etwas längere Antwort: Es kommt auf die Anzahl Spieler und Anzahl Karten zu Beginn des Spieles an. Bei zwei Spielern sind es ungefähr eineinhalb Mal, bei vier oder mehr Spielern weniger als ein Mal, siehe Abbildung 1.

Abbildung 1: Durschnittliche Anzahl gesagter “Tschau” pro Spiel.

 

Die Resultate stammen nicht etwa aus einer langwierigen Versuchsreihe, in der Angehörige der Hochschule tagelang “Tschau Sepp” gespielt haben, sondern aus einer sogenannten Monte-Carlo-Simulation. Bei einer Monte-Carlo-Simulation – der Name ist eine Anlehnung an die gleichnamige Spielbank in Monaco – wird versucht, ein analytisch nicht oder nur schlecht lösbares Problem mit Hilfe von Wahrscheinlichkeitstheorie numerisch zu lösen. Dazu wird in diesem Fall zuerst die Spielmechanik, also die Spielregeln und der Spielablauf, programmiert. Anschliessend wird eine grosse Anzahl Spiele simuliert (hier 100’000) und dabei gewisse Parameter zufällig gewählt: die initiale Reihenfolge der Karten im Stapel, welche Karte gespielt wird, usw. Zählt man nun alle gesuchten Ereignisse (also zum Beispiel wie oft in einem Spiel das Wort “Tschau” gefallen ist), kann man daraus mit der Gesamtanzahl Spiele die durchschnittlichen Werte schätzen.

Genauso ist es nun auch möglich, die Anzahl gespielter Züge und damit die Dauer des Spieles abzuschätzen. Je mehr Spieler und Anzahl Karten zu Beginn, desto länger dauert das Spiel. Bei zwei Spielern sind es durchschnittlich etwas mehr als 30 Züge pro Spiel, bei fünf Spielern 40 bis 50, siehe Abbildung 2.

Abbildung 2: Durchschnittliche Anzahl Züge.

Wir können auch abschätzen, wie viele Karten man durchschnittlich auf der Hand hat. Das ist bei Spielen mit Kindern eine durchaus relevante Frage. Auch hier gilt wieder: je mehr Spieler und Karten zu Beginn des Spieles, desto mehr Karten hat man auch durchschnittlich auf der Hand. Bei fünf Karten zu Beginn sind es im Schnitt etwas mehr als drei, bei sieben Karten und mehr als vier Spieler beinahe vier, siehe Abbildung 3.

Abbildung 3: Durschnittliche Anzahl Karten auf der Hand.

Mehr Informationen: