Ein probabilistischer Task-Scheduling Ansatz

In einem aktuellen Projekt stellte sich mir die folgende Problemstellung:
Für eine beliebig große Anzahl von Usern sollen bestimmte Aufgaben kontinuierlich ausgeführt werden. Ein Beispiel für so eine wiederkehrende Aufgabe ist der fortlaufende Datenabgleich userbezogener Daten mit einem externen Backend.

Constraints in der Problemstellung

Die Aufgaben dürfen nicht für alle User gleichzeitig ausgeführt werden.
Es soll möglich sein, die Arbeitslast für alle User nicht nur in einem Durchgang zu planen, sondern das Gesamtintervall soll in mehrere Sub-Intervalle trennbar sein.
Wenn ein Task für User X ausgeführt wurde, soll der Zeitraum zur nächsten Ausführung (unabhängig davon, wie groß dieser ist) immer konstant sein.
Die User-Zahl verändert sich fortlaufend.

Zu 1:
In einem naiven Ansatz könnte man über einen Cron-Job (1) alle User im definierten Planungs-Intervall auf einmal bearbeiten. Bei sehr großen Nutzerzahlen führt das aber dann schnell zu einer Überlast an der Gegenstelle bzw. zu extremen Lastspitzen zum Ausführungszeitpunkt, während in der Zwischenzeit keine „Arbeit“ verrichtet wird. Stattdessen sollen alle Jobs gleichmäßig auf das Planungs-Intervall verteilt werden.
Eine Cron-Job-Lösung kommt also nicht in Frage.

Zu 2:
Angenommen wir möchten einmal im Monat das Profil von jedem Benutzer bei Service „Foo“ abgleichen. Jetzt können wir natürlich am Anfang jeden Monats die Tasks für alle User definieren. Doch was geschieht mit Usern, die im Laufe des Monats hinzukommen? Diese werden erst zum nächsten Monat berücksichtigt!
Viel hilfreicher wäre es am Anfang jedes Tages festzulegen, welche Tasks an diesem Tag ausgeführt werden sollen, jedoch bezogen auf das Gesamtintervall (1 Monat).

Zu 3:
Wenn wir zum Beispiel für alle User eine bestimmte Aufgabe einmal pro Tag ausführen sollen, soll dies für User Y nicht einmal morgens um 10 Uhr und am nächsten Tag abends um 18 Uhr usw. geschehen. Vielmehr sollen für User Y die Tasks immer zur gleichen Uhrzeit passieren. Bezogen auf das Gesamtintervall (hier ein Tag) ist es also egal, wann dies geschieht.

Zu 4:
Es reicht also nicht aus, ausschließlich die Gesamtzahl der User zu betrachten, wenn es darum geht, die aktuell zu berechnenden User zu ermitteln. Wenn sich die Gesamtzahl der User ändert, führt das zwangsläufig zum Drift des Ausführungszeitpunktes. (s. Punkt 2)

Ein möglicher Ansatz

Man könnte die Problemstellung angehen, indem man in einer Datenbank festhält, wann bestimmte Tasks auszuführen sind. Weil die Last verteilt werden soll (Punkt 1), müssen die Tasks gleichmäßig eingeteilt werden. Weil sich aber die Userzahlen sich permanent ändern (Punkt 2), muss daraus folgend auch permanent der Zeitpunkt der Ausführung des Tasks verschoben werden, damit die Gleichverteilung gewährleistet werden kann.
Punkt 3 zu berücksichtigen wird bei diesem Ansatz schwierig bis unmöglich.

Zusätzlich zu diesen Schwierigkeiten ist es notwendig, eine separate Datenbasis zu halten, die Speicherplatz benötigt, korrupt werden kann bzw. generell nicht performant ist.

Ein probabilistischer Ansatz

Die Lösung, die ich für die Problemstellung wählte, versucht nicht auf die Sekunde genau zu berechnen, welcher Task wann und wie verteilt werden soll. Stattdessen mache ich mir die Gesetze der Wahrscheinlichkeit zu Nutze. Wenn ein neuer User angelegt wird, wird diesem eine zufällige Zahl zwischen 0 und 1 zugewiesen. Wichtig ist, dass dabei ein Zufallsalgorithmus gewählt wird, bei dem die generierten Zahlen möglichst gleichmäßig verteilt sind.
Schauen wir uns eine fiktive User-Basis von 4 Benutzern an. Jeder der Benutzer hat eine zufällige Zahl erhalten. Auf dem folgenden Zahlenstrahl sind diese aufgetragen:

Der Zahlenstrahl repräsentiert nun unser Planungs-Intervall, zum Beispiel „ein Tag“. Dabei steht nun die 0 auf dem Zahlenstrahl für 00:00:00 Uhr und die 1 für 23:59:59.

Jetzt ist es einfach aus der zugewiesenen Zahl zu berechnen, wann die Ausführung passieren soll: die Gesamtzahl der Sekunden pro Tag (60 * 60 * 24) wird mit der zugewiesenen Zufallszahl multipliziert und anschließend wird dieser Sekunden-Offset in eine Uhrzeit umgerechnet.

2 * 60s * 60m * 24h = 17280s => 04:48:00 Uhr
45 * 60s * 60m * 24h = 38880s => 10:48:00 Uhr
77 * 60s * 60m * 24h = 66528s => 18:28:48 Uhr
84 * 60s * 60m *24h = 72576s => 20:09:36 Uhr

Diese Herangehensweise funktioniert natürlich unabhängig vom Planungs-Intervall. Statt „ein Tag“ kann das Intervall auch „3 Tage“ sein. Die Berechnung kann einfach dementsprechend angepasst werden.

Werden alle Constraints eingehalten?

Punkt 1: Nicht alle Tasks sollen auf einmal ausgeführt werden

Durch die zufällig gewählte Verteilung auf das Planungs-Intervall ist sichergestellt, dass nicht alle Tasks auf einmal ausgeführt werden. Hundertprozentig gleichförmig sind die Tasks natürlich nicht auf das Planungs-Intervall verteilt, das liegt in der Natur der Sache. Letztendlich sind die geplanten Tasks aber „gut genug“ verteilt. Insbesondere bei einer sehr großen Anzahl von Benutzern spielt dieser Zufalls-Faktor keine Rolle mehr.

Punkt 2: Unterteilung in Sub-Intervalle

Sollen die Tasks für den Zeitraum „1 Monat“ in mehreren Sub-Intervallen geplant werden, ist dies ohne weiteres möglich:

Hier wurde das Planungs-Intervall in vier Sub-Intervalle aufgeteilt. Über die definierten Zahlenräume wissen wir eindeutig, für welche User ein Task geplant werden soll:
Im ersten Intervall: alle User von 0 – 0.25
Im zweiten Intervall: alle User von 0.25 – 0.5
usw.

Punkt 3: Konstanter Zeitabstand zur nächsten Ausführung

Jede Zufallszahl steht (in Relation zum Planungs-Intervall) für einen eindeutigen Zeitpunkt, der sich nicht mehr ändert. Dadurch wird z.B. bei einer täglichen Ausführung der User mit der Zahl 0.2 immer um 04:48Uhr bearbeitet.

Punkt 4: Wachsende User-Basis

Wenn weitere User hinzukommen, hat dies keine Auswirkungen auf die vorhandene User-Basis:

Der Zeitpunkt, an dem die bereits existierenden Nutzer eingeplant werden, ist nicht von der Gesamtgröße der User-Basis abhängig, sondern ist nach wie vor exakt gleich und damit deterministisch.

Bonus: Es ist nicht notwendig, einen Status festzuhalten (z.B. in einer Datenbank), weil sich zu jedem Zeitpunkt eindeutig ermitteln lässt, wann welcher Task auszuführen ist.

[1]: https://de.wikipedia.org/wiki/Cron

Photos:
https://www.piqsels.com/de/public-domain-photo-jiqtk
https://www.piqsels.com/de/public-domain-photo-jzzog