--- title: "Entwurf einer mehrdimensionalen Kapazitätswarteschlange" date: 2020-12-02 language: de topics: ["data", "ecommerce", "lemmid-store", "payments", "server", "work"] source_url: https://willem.com/de/2020-12-02_entwurf-einer-mehrdimensionalen-kapazitatswarteschlange/ --- # Entwurf einer mehrdimensionalen Kapazitätswarteschlange *Küchen-, Liefer- und Abholkapazität steuern* > Diesen Monat musste ich einer Warteschlange für Kapazitäten weitere Dimensionen hinzufügen. Die Bestell-App, die ich gebaut habe, muss die Kapazität begrenzen können: nach der Zahl der Bestellungen, nach dem Inhalt einzelner Bestellungen und nach der Art der Übergabe (Abholung oder Lieferung). Lies weiter, dann erfährst du, wie ich dafür eine Lambda-Architektur genutzt habe. ## Kapazität begrenzen Vielleicht ist dir das nicht klar, aber eine der mächtigsten Funktionen der Bestell-App,_die_ich_gebaut_habe (https://willem.com/blog/lemmid-store/), ist die Möglichkeit, die Zahl der Bestellungen zu begrenzen. Das klingt widersprüchlich, aber wenn meine Kunden (die Restaurants und Ladenbesitzer, die meine App nutzen) die Zahl der möglichen Bestellungen begrenzen, können sie sicherstellen, dass die Bestellungen gut zubereitet und geliefert werden. ## Die Komplexität von drei Pizzen Nehmen wir an, du willst drei Pizzen bestellen. Dann muss die Bestell-App Folgendes wissen: - Willst du sie **abholen** oder **liefern lassen**? - Zu **welcher Uhrzeit?** Wann müssen sie in den Ofen? - Ist **zu dieser Zeit genug Platz im Ofen** für *drei* Pizzen? - Wenn du Abholung gewählt hast: **Können wir dich zu dieser Zeit gefahrlos empfangen?** - Wenn du Lieferung gewählt hast: **Ist ein Fahrer oder eine Fahrerin frei**, um dir deine Pizzen zu bringen? - **Überall Ja?** Dann **bitte bezahlen**, während wir **deine Pizzen im Ofen und für Lieferung oder Abholung eingeplant lassen**. Zahlung fehlgeschlagen? Doch umentschieden? Dann machen wir die ganze Planung rückgängig und warten, bis jemand anderes Pizzen bestellt! ![Pizza essen während der Entwicklung heißt, den Algorithmus zu „leben“](https://willem.com/global/images/e9229d524bd1.webp) ## Drei Kapazitätsdimensionen Gerade zur Abendessenszeit besteht die Gefahr, dass zu viele Leute gleichzeitig Essen bestellen. Die App kommt dank ihrer hochskalierbaren_Architektur (https://willem.com/en/2020-05-11_scalable-application-design-without-magic/) mit dem zusätzlichen Verkehr zurecht, aber die physischen Grenzen bleiben, zum Beispiel: - **Küchenkapazität**: wie viele Gerichte du gleichzeitig zubereiten kannst - **Abholkapazität**: wie viele Leute du unter den COVID-19-Beschränkungen gleichzeitig gefahrlos empfangen kannst - **Lieferkapazität**: wie viele Bestellungen du unter Berücksichtigung von Verkehr, Entfernung und Route ausliefern kannst ![Drei Kapazitätsgrenzen: Küche / Lieferung / Abholung](https://willem.com/global/images/db564dd30d9f.webp) ### Verschieden, aber voneinander abhängig Diese drei Arten von Grenzen hängen voneinander ab. Eine große Abholbestellung kann zum Beispiel die ganze Küchenkapazität belegen, sodass auch für Lieferungen nichts mehr frei ist. Kleinere Bestellungen könnten die Küchenkapazität noch auffüllen, während für große Bestellungen vielleicht nicht mehr genug übrig ist. Du brauchst also einen Mechanismus, der *alle* Kennzahlen zusammen betrachtet, um zu entscheiden, ob neue Bestellungen möglich sind, einschließlich des Inhalts einer noch nicht abgeschickten Bestellung (zum Beispiel dessen, was in deinem Warenkorb liegt). ### Unterschiedlich lange Zeitspannen Üblicherweise legt man eine physische Grenze über eine Zeitspanne fest, zum Beispiel *„die Küche schafft 10 Gerichte pro 15 Minuten“*. Schwierig wird es, wenn andere Grenzen mit anderen Zeitspannen definiert sind. Die Küche mag pro 15 Minuten begrenzt sein, die Lieferkapazität dagegen auf eine längere Zeitspanne (zum Beispiel 3 Lieferungen pro 30 Minuten). Der Mechanismus muss irgendwie mit diesen unterschiedlichen Zeitspannen umgehen können. ### Im Voraus bestellen Die Sache wird noch schwieriger, weil Leute ihre Bestellung im Voraus aufgeben können. Sie wählen ein Zeitfenster in der Zukunft und lassen die nötige Kapazität reservieren. Manchmal bestellen Leute Tage im Voraus, um sicher zu sein, dass ihr Essen an einem bestimmten Tag zu einer bestimmten Zeit geliefert wird. Zu jeder Bestellung gehören also (mindestens) zwei Zeitpunkte: der Bestellzeitpunkt und der Lieferzeitpunkt. ### Kapazität reservieren und freigeben Die meisten Geschäftsinhaber verlangen für Online-Bestellungen eine Online-Zahlung, damit alle Bestellungen echt sind und weder Kapazität noch Essen für Nichterscheinen oder Geisterbestellungen verschwendet wird. Das Problem_mit_Online-Zahlungen (https://willem.com/en/2020-03-25_designing-and-implementing-a-micro-payment-system/) ist, dass nicht jede Transaktion klappt. Manchmal wird eine Kredit- oder Debitkartenzahlung abgelehnt (zum Beispiel wegen fehlender Deckung). Manchmal schließen Leute die App einfach, bevor sie die Bestellung abgeschlossen haben. Das System sollte die nötige Kapazität für eine Bestellung reservieren, während der Kunde online bezahlt, und die reservierte Kapazität wieder freigeben, wenn die Bestellung abgebrochen wird oder die Zahlung scheitert. ### Große Mengen, hohe Geschwindigkeit Zu guter Letzt muss der Mechanismus zuverlässig und schnell sein. Ob eine Bestellung noch möglich ist, muss in Millisekunden feststehen, bei hoher Parallelität, denn zur Stoßzeit sind viele verschiedene Clients mit der Bestell-App verbunden. Wenn jemand bestellt, ändert das die Verfügbarkeit für alle anderen (möglichen) Bestellungen. Nicht jeder hat eine stabile Verbindung, denn manche nutzen die App auf Telefonen mit schlechtem Empfang oder WLAN. Das System muss unter wechselnden Bedingungen mit vielen verbundenen Leuten gut funktionieren. ## Lambda-Architektur Die Lambda-Architektur_(Wikipedia) (https://en.wikipedia.org/wiki/Lambda_architecture) ist eine Möglichkeit, große Datenmengen zu verarbeiten, und zwar sowohl per Stream-Verarbeitung als auch per Batch-Verarbeitung. Sie setzt ein Datenmodell mit einer Datenquelle voraus, an die man nur anhängen kann und die unveränderlich ist, meist aus Ereignissen mit Zeitstempel. ### Unveränderliche Daten Das ist eine sehr wichtige Grundlage des Mechanismus: Alle Daten haben einen Zeitstempel und ändern sich *nie*. Statt bestehende Datensätze zu ändern, kommen einfach neue dazu, die die bestehenden überschreiben. Das ermöglicht hohe Parallelität und verteilte Algorithmen, denn die Synchronisierung wird einfacher: Man muss nur nach neuen Daten suchen (statt nach neuen und geänderten!). ### Echtzeit- oder Speed-Schicht Die Stream-Verarbeitung, die Echtzeit- oder Speed-Schicht einer Lambda-Architektur, liefert superschnelle Antworten auf Echtzeit-Anfragen. Sie hält Ansichten und Kennzahlen bereit, die sie aus der Echtzeitverarbeitung der Ereignisse berechnet. ### Vorberechnungsschicht Die Batch-Verarbeitung, die Vorberechnungsschicht, liefert eine vollständige und genaue Basis aller Daten im System. Große Datenmengen zu verarbeiten dauert, deshalb ist die Batch-Verarbeitung nicht schnell genug, um alles sofort zu erledigen. Darum arbeiten die beiden Schichten in einer Lambda-Architektur Hand in Hand. ## Umsetzung Die Backend-Server, die die Essensbestellungen der App verarbeiten, arbeiten mit einem Datenstrom aus Ereignissen mit Zeitstempel. Im Kern ist jede Bestellung ein Ereignis im System. Jede Bestellung wird mit Bestelldatum und -zeit, Datum und Zeit der Übergabe (geplante Liefer- oder Abholzeit), Kundendaten und Bestellinhalt (Zahl der Gerichte und so weiter) gespeichert. ### Kapazität reservieren und freigeben Schlägt die Zahlung fehl oder wird eine Bestellung abgebrochen, kommt eine „negative“ Bestellung in den Datenstrom. Sie hebt durch ihre negativen Werte jede Wirkung auf die Kapazitätsgrenzen auf. Ein Beispiel: Um eine Bestellung über drei Pizzen zu stornieren, entsteht im Datenstrom eine negative Bestellung über „minus drei Pizzen“ mit demselben Zeitstempel der Übergabe. So werden Kapazitäten auf elegante Weise reserviert und wieder freigegeben. ### Mehrdimensionale Echtzeit-Kennzahlen Statt die Kapazität in Zähler zu verpacken, beantwortet der Backend-Server Abfragen nach Echtzeit-Kennzahlen mit den *echten* Stream-Daten. So kann das System mit unterschiedlich langen Zeitspannen umgehen. ![Ein Ereignisstrom aus Bestellungen ist das Herz des Mechanismus, Abfragen werden beantwortet, indem man diesen Strom betrachtet: Wie viele Pizzen sind um 18:00 Uhr fertig?](https://willem.com/global/images/1e59e0b31de7.webp) Wenn zum ersten Mal eine Abfrage für eine bestimmte Kennzahl eingeht, lädt das System per Batch historische Daten, um das Modell zu initialisieren, das es dann in Echtzeit aktuell hält. Diese Kennzahl wird aktuell gehalten, indem alle neuen Bestellungen im System betrachtet werden, solange Abfragen für sie eingehen. Wird sie nicht mehr abgefragt, wird das Modell entladen. Wird es wieder gebraucht, beginnt der Vorgang von vorn. Das Schöne an diesem Ansatz: Die meisten Abfragen werden in wenigen Millisekunden beantwortet, weil sie direkt aus dem Arbeitsspeicher gelesen werden, ganz ohne Datenbank oder Festplatte. So erreichst du extrem hohe Leistung nach dem Prinzip „nur wenn nötig“. Das passt gut zur Bestell-App, denn nicht *alle* Zeitspannen sind gleich beliebt. Die Bestell-App fragt immer wieder einen zentralen Kapazitätsserver ab, der die Kennzahlen der Warteschlange führt. Sie filtert dann die verfügbaren Zeitfenster, indem sie sich ansieht, was der Kunde für seine Bestellung auswählt. Ein (wahrscheinlich) freies Zeitfenster zu wählen geschieht also auf dem Client, was das Backend entlastet. Sobald eine Bestellung abgeschickt ist, reserviert das Backend die Kapazität, indem es die zentralen Kennzahlen aktualisiert, und verhindert so, dass andere denselben Platz in der Warteschlange belegen. ## Fazit Warteschlangen können knifflig sein, wenn mehrere Kennzahlen die Geschwindigkeit bestimmen. Nimm dir wirklich die Zeit, es richtig zu modellieren, und überlege, welche Daten du für die Prüfungen rund um die Warteschlange *wirklich* brauchst. Jetzt weißt du, dass es gar nicht so einfach ist, drei Pizzen zu bestellen! Zu garantieren, dass sie heiß und pünktlich auf den Tisch kommen, ist eine große technische Herausforderung, und gut kochen muss man obendrein. Zum Glück kümmere *ich* mich nicht um Letzteres, ha!