Load Balancing

Wir betreiben mehrere Gatways, zu denen sich die Nodes (Freifunk-Router) verbinden können. Diese VPN-Verbindung funktioniert mit fastd. Jeder Node hält immer höchstens eine fastd-Verbindung zu einem Gateway. Welches Gateway das ist, entscheidet sich unserer Erfahrung nach eher zufällig. Das führt dazu, dass ohne manuellen Eingriff auch stark ausgelastete Gateways neue Nodes aufnehmen und sich die Last nicht gleichmäßig verteilt.

Wir haben daher einen Mechanismus entwickelt, um die Last zwischen unseren Gateways besser zu verteilen. Dieser besteht aus zwei Komponenten:

• dem Präferenz-Konzept, mit dem Gateways ausdrücken, wie stark sie gewillt sind, neue Knoten aufzunehmen,
• dem Verteilungsmechanismus, mit dem Nodes auf die Gateways verteilt werden

Jedes Gateway gibt für jedes bediente Segment eine Präferenz bekannt, deren Berechnung es selbst bestimmen kann, auch unterschiedlich für die einzelnen Segmente. Eine Präferenz ist eine Ganzzahl zwischen -∞ und 100. Je größer die Präferenz, desto mehr ist ein Gateway gewillt, neue Nodes aufzunehmen. Aktuell (Stand Mai 2021) verwenden alle Gateways denselben Algorithmus, um die Präferenz zu ermitteln, und unterscheiden dabei nicht zwischen den Segmenten.

Ziel ist, den durch die Nodes transportierten Gesamt-Traffic im Freifunknetz so auf die Gateways zu verteilen, dass kein Gateway überlastet wird. Im Prinzip geht es also nicht darum, die VPN-Verbindungen der Nodes gleichmäßig zu verteilen, sondern den Traffic, der durch die Clients erzeugt wird.

Die Herausforderung bei der Präferenz-Bestimmung liegt nun darin, dass ein Gateway zum Zeitpunkt der Verbindungsanfrage eines Nodes nicht vorhersehen kann, welchen zusätzlichen Traffic das zur Folge hat. Darüber hinaus ist der Traffic auch von der Tageszeit und äusseren Umständen abhängig, die nicht kalkulierbar sind (siehe kurze Spitze gegen 22 Uhr in der nachfolgenden Grafik).

Wir greifen derzeit auf den Verlauf des Traffics in den letzten 24 Stunden zurück, konkret auf das Maximum der letzten 24 Stunden-Mittelwerte, und zusätzlich auf den jeweils aktuellen Traffic-Wert. Der Peak wird dann ins Verhältnis zu dem maximalen Durchsatz gesetzt, den das Gateway dauerhaft liefern kann (wird vom Gateway-Betreiber festgesetzt). So ergibt sich eine Präferenz von 100, wenn der Peak gleich Null ist, und eine Präferenz von 0, wenn der Peak dem definierten Maximalwert entspricht. Übersteigt der Peak den vorgegeben Maximalwert, wird die Präferenz negativ.

Im obigen Beispiel sieht man sehr schön, dass ein Gateway eine sehr niedrige Präferenz haben kann, obwohl der aktuelle Traffic gar nicht am Maximalwert liegt (wäre hier 250 MBit/s).

Jedes Gateway stellt seine Präferenz als JSON-Dokument per HTTP unter dem Pfad /data/gwstatus.json zur Verfügung. Das Format ist in einem JSON-Schema beschrieben.

Erste Ideen zur Verteilung basierten darauf, dass sich ein Gateway unterhalb einer minimalen Präferenz aus dem DNS austrägt, und so beim VPN-Verbindungsaufbau für die Nodes nicht mehr erreichbar ist. Steigt die Präferenz dann wieder über einen Schwellwert, trägt sich das Gateway erneut ein. Hierbei müsste aber eine aufwendige Koordination zwischen den Gateways implementiert werden, wenn man auf eine zentrale Verteilinstanz verzichten will, damit zu keiner Zeit alle Gateways gleichzeitig ausgetragen sind.

Eine Idee von NeoRaider hat uns einen neuen Ansatz geliefert.

Wenn ein Node eine Verbindung zu einem Gateway aufbaut, schickt er Handshakes an die Gateways. Der Node stellt die Verbindung dann zu dem Gateway her, das zuerst auf den Handshake antwortet. Verzögert man also auf den Gateways die Antwort auf den initalen Handshake eines Nodes in Abhängigkeit der Präferenz - je niedriger die Präferenz ist, um so länger die Verzögerung der Antwort - dann lässt sich damit eine Verteilung realisieren, ohne dass sich die Gateways untereinander abstimmen müssen.

Um Verzögerungen beim Verbindungsaufbau verwenden zu können, musste die fastd-Konfiguration auf den Gateways angepasst werden. Ursprünglich wurden den fastd-Instanzen die Dateien mit den Keys direkt zur Verfügung gestellt, so dass diese bei einer Verbindungsanfrage eigenständig ermitteln konnten, ob der Node zur Verbindung berechtigt ist. Will man statt dessen Einfluss auf den Verbindungsaufbau nehmen, so ist das durch die Nutzung eines Scriptes „on-verify“ möglich, aber beim Original-fastd nur, wenn die Key-Dateien nicht mehr direkt angeboten werden.

Wir haben zwar einen Patch für fastd entwickelt, der nur den Handshake verzögert, allerdings nicht produktiv ausgerollt, da wir keinen selbst kompilierten fastd auf allen Gateways ausrollen wollten.

Deshalb muss auf den Gateways das on-verify Script zusätzlich zur Verzögerung auch die Authentisierung übernehmen, indem es im Dateisystem die Key-Dateien nach dem angebotenen fastd-Key durchsucht, und mit einem passenden exit-Code antwortet.

Bei Tests hat sich gezeigt, dass die Verzögerung maximal 10 Sekunden betragen darf, damit überhaupt noch eine Verbindung zustande kommt.

Wir haben außerdem beobachtet, dass fastd nicht alle Gateways gleichzeitig anfragt, sondern pro Gateway ein zufälliges Delay zwischen 0 und 3 Sekunden einfügt, um eine gleichmäßigere Verteilung zu erreichen. Da das mit unserem Verzögerungsmechanismus auf den Gateways im Konflikt steht, haben wir seit Firmware 2.3 einen Gluon-Patch, der das Delay auf den Nodes entfernt.

Geeignete Verzögerungswerte aus den Präferenzen zu ermitteln, lässt sich über unterschiedliche Funktionen (Kennlinien) realisieren.

Von uns wurde nach mehreren Versuchen die 50/2-Kennlinie (grün) implementiert. Sie berücksichtigt, dass

• es auch ohne aktive Clients immer eine Grundlast im Freifunknetz gibt, die Präferenz also kaum über 80 steigt
• die Nodes eine einmal hergestellte Verbindung nur selten wieder trennen, also rechtzeitig gegengesteuert werden muss
• es unvorhersehbare Lastsprünge geben kann, d.h. ausreichend Reserve einzuplanen ist

Die bisherige Erfahrung bestärkt uns in der Annahme, dass wir hier eine sehr gute Lösung zum Load Balancing gefunden haben.

Wir haben ein Grafana-Dashboard, um die Präferenzen und Tunnel zu überwachen. Der Gesamt-Traffic im Freifunknetz und auf den Gateways wird hier dargestellt.

Unsere Implementierung steht auf Github zur Verfügung:

• Die Präferenz wird im Script genGwStatus.py ermittelt, das per cron alle 5 Minuten ausgeführt wird
• Die Prüfung des fastd-Keys und das Delay ist in fastd-verify.py realisiert, das vom fastd bei jedem Verbindungsversuch (Handshake) aufgerufen wird und die notwendigen Informationen per Environmentvariablen zur Verfügung stellt.