A rewrite for the ORS // Ein Rewrite für das ORS


#1

ENGLISH

Over the last weeks, reports from our development team were rather scarce given that we spent much time and effort on an important but to players mostly invisible system: the ORS.

The ORS - ‘Online Reservation System’ - is one of the most remarkable and central features of AirlineSim. Not necessarily the graphical search interface known by most of you as ORS, but the underlying system which is responsible for connection calculation and distribution of demand. This system has now been completely rebuilt and put on a completely new technical basis. Why and how will be described in this Dev-log entry.

Why a Rewrite?

The original and most important reason for the rewrite was and is the ‘Devau-problem’. This game world is different from the others due to its exotic configuration with significantly longer transfer times. These transfer times caused the complete game world to crash regularly while calculating big airports and negatively influenced overall performance. Our sole options were to successively shorten transfer times - diminishing Devau’s unique feature - or to deploy more powerful - and therefore more expensive - hardware. Today, Devau is running on hardware so expensive that it forced us to act: Either we would find a way to handle the performance problems or we would have to shut down a game world for the first time in AS-history.

The original plan

The ORS is as old as the current AS generation, about 5 years by now. Back then our servers had 4, maybe 8 processor cores; nowadays our servers run on 24 to 32 cores. Therefore, it seemed obvious to rebuild the ORS for an efficient use of those cores. To achieve this, the ‘big work package’ is separated into several ‘small work packages’ for parallel calculation. Hence the original idea was to distribute the demand not per airport but per relation.

The advantage: Instead of calculating a small number of big airports one after the other, many small relations could easily be calculated in a distributed manner. Additionally, demand distribution would be much more realistic as flights are filling over time and not all of a sudden with an airport being calculated.

The disadvantage: Instead of 4,000 airports we have between 800,000 and 900,000 relations per day. This resembles 1000 players doing 900 ORS requests each day.

When distributing load between different cores, you always have to deal with overhead, but after weeklong development and extensive tuning it became clear that we couldn’t solve the problem with single relations although it would have been favorable for several reasons. Even our most potent hardware could not do the trick.

Well then, back to the drawing board…

A hybrid out of old and new

Fortunately, work on the new system was not completely in vain. Calculating connections separately still had the potential of speeding up the process even when airports are calculated ‘in one piece’. Only one problem remains when you want to calculate e.g. the approximately 2,000 destinations from LAX on Devau: memory! In this example, so many relations are being calculated that the result of the calculation does not fit into the memory at all. This will lead to deteriorated server performance the good cases but would crash the server in the worst case.

Hence we rebuilt the system for calculating airports as a whole but distributing the list of destinations into several small packages. Additionally, the processes of ‘searching’ and ‘booking’ were separated more strictly, allowing the system to book a search result while packages from the same or the following airport are still in search. As soon as the searched relations are booked they are no longer needed and can be removed from memory. As a result it might take longer for all packages of one airport to be completed but memory usage remains below a critical level.

Risks and side-effects

Like all medicine, this treatment is also not without side-effects. But they come mildly in this case:

  • The order and time for calculation of the airports remains the same. But calculation happens in a parallel fashion now which means that other processes such as flight updates or insertion of new flights can overrun the demand update and vice versa. Nevertheless, delays should be within some seconds during normal usage and the general sequence will always be maintained.

  • Due to performance reasons, the booking system will distribute its work depending on the distance between the airport and the respective destination. Destinations which are farther away will be calculated prior to destinations in closer distance. This could have some influence on the distribution of demand.

  • Some edge cases like DEN and LAX on Devau are just hopeless: Demand distribution will work and the server won’t crash, but during the short time they are updated, server performance might be sub-standard.

Status-quo and Release

At the moment we are running final tests during which potential side-effects and performance characteristics are evaluated. For this reason, two mirrored game worlds with data from Idlewild and Devau are running on a separate test server. As soon as we are sure that everything works as planned and no major mistakes have been introduced into the demand distribution algorithms, we will set and communicate a release date. But until that’s the case several weeks might pass.

DEUTSCH

In den letzten Wochen war es von unserer Seite eher ruhig was die Berichte aus der Entwicklungsabteilung betrifft. Dies lag daran, dass wir sehr viel Zeit und Arbeit in ein wichtiges aber weitgehend für Spieler unsichtbares System gesteckt haben: Das ORS.

Das ORS - das "Online Reservation System" - ist eines der markantesten und zentralsten Features von AirlineSim. Nicht unbedingt die grafische Suchmaske, welche den meisten unter dem Namen ORS geläufig ist, sondern das darunter liegende System, welches bei AirlineSim für das Errechnen der Flugverbindungen und die Verteilung des Aufkommens verantwortlich ist. Dieses System wurde nun in wochenlanger Arbeit generalüberholt und technisch auf ein vollständig neues Fundament gestellt. Wie und warum soll dieser Dev-Log-Eintrag beleuchten.

Warum ein Rewrite?

Der ursprüngliche und wichtigste Anlass für den Rewrite war und ist die "Devau-Problematik". Diese Spielwelt unterschiedet sich von den anderen durch ihre exotische Konfiguration mit einer deutlich längeren maximalen Transferzeit. Diese Transferzeit führte regelmäßig dazu, dass die gesamte Spielwelt bei der Berechnung großer Flughäfen abstürzte und dass die generelle Performance zu wünschen übrig lies. Unsere einzigen Optionen waren, die Transferzeit sukzessive zu reduzieren - womit das Alleinstellungsmerkmal von Devau zunehmend verschwand - und immer leistungsfähigere - und somit teurere - Hardware zu installieren. Mittlerweile läuft Devau auf Hardware die so teuer ist, dass wir uns gezwungen sahen zu handeln: Entweder wir bekommen das Performance-Problem in den Griff oder wir müssen erstmals in der AS-Geschichte eine Spielwelt abschalten.

Der ursprüngliche Plan

Das ORS ist so alt wie die aktuelle AirlineSim-Version, also etwa 5 Jahre. Zur damaligen Zeit hatten unsere Server 4, vielleicht 8 Prozessor-Kerne. Inzwischen ist das anders: Unsere aktuelle Servergeneration läuft mit 24 bis 32 Kernen. Es lag also nahe, das ORS auf die effektive Nutzung dieser Kerne umzubauen. Dies erreicht man, indem man "große Arbeitspakete" in "viele kleine Arbeitspakete" aufteilt. Die anfängliche Idee war also, das Aufkommen nicht mehr pro Flughafen, sondern pro Relation zu verteilen.

Der Vorteil: Statt weniger großer Flughäfen, die nacheinander berechnet werden müssen, hätte man viele kleine Einzelverbindungen, die sich sehr gut verteilt berechnen lassen. Zudem wäre die Aufkommensverteilung viel realistischer, da sich die Flüge nach und nach auffüllen würden und nicht wie bisher schlagartig, sobald ein Flughafen als ganzes berechnet wird.

Der Nachteil: Statt 4.000 Flughäfen reden wir von 800.000 bis 900.000 Einzelrelationen pro Tag. Das ist in etwa so, als würden 1000 Spieler jeden Tag 900 ORS-Abfragen anstoßen.

Bei der Verteilung von Last auf mehrere Kerne hat man es immer mit Overhead zu tun, aber nach mehrwöchiger Entwicklung und langem Tuning wurde klar: Auf Einzelrelationen können wir das Problem nicht herunter brechen, so schön es aus den verschiedensten Gründen auch wäre. Selbst unsere potenteste Hardware schaffte dieses Kunststück nicht.

Also zurück ans Reißbrett…

Ein Hybrid aus Neu und Alt

Ganz vergebens war die Arbeit am neuen System jedoch nicht. Die verteilte Verbindungsberechnung hatte weiterhin das Potential die Berechnung zu beschleunigen, selbst wenn man Flughäfen "am Stück" berechnet. Lediglich mit einem Problem hat man es auch weiterhin zu tun, wenn man zum Beispiel die knapp 2.000 Ziele ab LAX auf Devau berechnen will: Speicher! Hier kommen derart viele Verbindungen zustande, dass das Ergebnis der Berechnung nicht mehr in den Speicher passt. Das führt im harmloseren Fall zu zeitweise schlechter Erreichbarkeit, im schlimmsten Fall zu einem Absturz des Servers.

Folglich bauten wir das System dahingehend um, dass zwar Flughäfen jeweils nacheinander als Ganzes berechnet werden, die Liste der Destinationen aber in kleinere Pakete aufgeteilt wird. Des weiteren wurden die Vorgänge des "Suchens" und des "Buchens" deutlicher getrennt, so dass das Ergebnis einer Suche bereits gebucht werden kann, während nachfolgende Pakete des selben oder eines nachfolgenden Flughafens noch in der Suchphase sind. Sobald die gefundenen Verbindungen gebucht sind, werden sie nicht mehr benötigt und der verwendete Speicher kann wieder freigegeben werden. In der Folge kann es zwar etwas länger dauern bis alle Pakete für einen Flughafen abgearbeitet sind, dafür bleibt man beim Speicherverbrauch unter einem kritischen Wert.

Risiken und Nebenwirkungen

Wie jede Medizin ist auch diese Behandlung nicht ganz ohne Nebenwirkungen. Diese fallen aber milde aus:

  • Flughäfen werden grundsätzlich weiterhin in ihrer bisherigen Reihenfolge und zu den bekannten Terminen berechnet. Allerdings geschieht dies parallelisiert, das heißt andere Aktionen des Spiels wie das Flugupdate oder das Einbuchen neuer Flüge können das Aufkommensupdate überholen wenn dieses zurück liegt und umgekehrt. Diese Abweichung sollte im Normalbetrieb aber bei höchstens einigen Sekunden liegen und die grundsätzliche zeitliche Abfolge wird stets eingehalten.

  • Das Buchungssystem teilt sich seine Arbeit aus Optimierungsgründen nach der Entfernung zwischen dem zu berechnendem Flughafen und den Destinationen ein. Weiter entfernte Ziele werden vor solchen berechnet, die im näheren Umkreis liegen. Dies kann u.U. Auswirkungen auf die Aufkommensverteilung haben.

  • Es gibt einige hoffnungslose Fälle wie LAX oder DEN auf Devau: Die Aufkommensverteilung wird durchlaufen und der Server wird nicht abstürzen, aber während der Minuten in denen einer dieser Flughäfen aktualisiert wird, ist die allgemeine Server-Performance unter dem, was man erwarten würde.

Aktueller Status und Release

Gegenwärtig geht das überarbeitete System in die finale Testphase, in der wir eventuelle weitere Nebenwirkungen und die endgültigen Performanceeigenschaften ermitteln wollen. Zu diesem Zweck laufen momentan zwei gespiegelt Spielwelten mit aktuellen Echtdaten von Idlewild und Devau auf einem eigenen Testserver. Sobald wir zuversichtlich sind, dass alles so funktioniert wie es soll und sich keine schwerwiegenden Fehler in der Aufkommensverteilung eingeschlichen haben, werden wir einen Releasetermin festsetzen und veröffentlichen. Bis dahin können aber u.U. noch einige Wochen vergehen.