Axiome bei der Programmausführung brechen

Neue Fehler machen

Ich bin jetzt seit etwa 15 Jahren Softwareentwickler. Im Laufe meiner Karriere habe ich viel gelernt und diese Erkenntnisse angewendet, um viele verteilte Systeme zu entwerfen und zu implementieren (und gelegentlich auslaufen zu lassen oder so zu belassen, wie sie sind). Auf dem Weg dorthin habe ich zahlreiche Fehler gemacht und mache sie immer noch. Da mein Hauptaugenmerk jedoch auf Zuverlässigkeit lag, habe ich auf meine Erfahrungen und die Community zurückgegriffen, um Möglichkeiten zu finden, die Fehlerhäufigkeit zu minimieren. Mein Motto ist: Wir müssen unbedingt versuchen, neue Fehler zu machen (weniger offensichtlich, raffinierter). Einen Fehler zu machen ist in Ordnung – so lernen wir, ihn zu wiederholen – ist traurig und entmutigend.

Das ist wahrscheinlich das, was mich an der Mathematik schon immer fasziniert hat. Nicht nur, weil es elegant und prägnant ist, sondern auch, weil seine logische Strenge Fehler verhindert. Es zwingt Sie dazu, über Ihren aktuellen Kontext nachzudenken und darüber nachzudenken, auf welche Postulate und Theoreme Sie sich verlassen können. Das Befolgen dieser Regeln erweist sich als fruchtbar, Sie erhalten das richtige Ergebnis. Es stimmt, dass die Informatik ein Teilgebiet der Mathematik ist. Aber was wir normalerweise praktizieren, ist Software-Engineering, etwas ganz Besonderes. Wir wenden die Errungenschaften und Entdeckungen der Informatik in die Praxis an und berücksichtigen dabei Zeitbeschränkungen und Geschäftsanforderungen. Dieser Blog ist ein Versuch, halbmathematisches Denken auf den Entwurf und die Implementierung von Computerprogrammen anzuwenden. Wir werden ein Modell verschiedener Ausführungsregime vorschlagen, das einen Rahmen bietet, um viele Programmierfehler zu vermeiden.

Von bescheidenen Anfängen

Wenn wir lernen zu programmieren und unsere ersten vorsichtigen (oder gewagten) Schritte machen, beginnen wir normalerweise mit etwas Einfachem:

• Schleifen programmieren, Grundrechenarten durchführen und die Ergebnisse in einem Terminal ausdrucken
• Lösen mathematischer Probleme, wahrscheinlich in einer speziellen Umgebung wie MathCAD oder Mathematica

Wir erwerben das Muskelgedächtnis, lernen die Syntax der Sprache und, was am wichtigsten ist, wir ändern die Art und Weise, wie wir denken und argumentieren. Wir lernen, den Code zu lesen und Annahmen darüber zu treffen, wie er ausgeführt wird. Wir beginnen fast nie mit der Lektüre eines Sprachstandards und lesen uns den Abschnitt „Speichermodell“ genau durch – weil wir noch nicht in der Lage sind, diese Standards vollständig zu schätzen und zu nutzen. Wir üben Versuch und Irrtum: In unseren ersten Programmen führen wir logische und arithmetische Fehler ein. Diese Fehler lehren uns, unsere Annahmen zu überprüfen: Ist diese Schleifeninvariante korrekt, können wir den Index und die Länge des Array-Elements auf diese Weise vergleichen (wo setzen Sie diese -1 ein)? Aber wenn wir bestimmte Fehler nicht sehen, verinnerlichen wir oft implizit welche Invarianten Das System erzwingt und versorgt uns.

Nämlich dieses hier:

Codezeilen werden immer in derselben Reihenfolge ausgewertet (serialisiert).

Dieses Postulat erlaubt uns anzunehmen, dass die folgenden Sätze wahr sind (wir werden sie nicht beweisen):

• Die Bewertungsreihenfolge ändert sich zwischen den Ausführungen nicht
• Funktionsaufrufe kehren immer zurück

Mathematische Axiome ermöglichen es, größere Strukturen auf einer soliden Grundlage abzuleiten und aufzubauen. In der Mathematik haben wir die euklidische Geometrie mit 4+1 Postulaten. Der Letzte sagt:

Parallele Linien bleiben parallel, sie schneiden sich nicht und divergieren nicht

Jahrtausende lang versuchten Mathematiker, es zu beweisen und es aus den ersten vier abzuleiten. Es stellt sich heraus, dass das nicht möglich ist. Wir können dieses „Parallellinien“-Postulat durch Alternativen ersetzen und erhalten verschiedene Arten von Geometrien (nämlich hyperbolische und elliptische), die neue Perspektiven eröffnen und sich als anwendbar und nützlich erweisen. Schließlich ist die Oberfläche unseres eigenen Planeten nicht flach, und das müssen wir beispielsweise bei GPS-Software und Flugrouten berücksichtigen.

Das Bedürfnis nach Veränderung

Aber vorher wollen wir innehalten und die technischsten Fragen stellen: Warum sich die Mühe machen? Wenn das Programm seine Aufgabe erfüllt, es leicht zu unterstützen, zu warten und weiterzuentwickeln ist, warum sollten wir dann diese gemütliche Invariante der vorhersehbaren sequentiellen Ausführung überhaupt aufgeben?

Ich sehe zwei Antworten. Der erste Punkt ist die Leistung . Wenn wir unser Programm doppelt so schnell oder ähnlich schnell laufen lassen können – also die Hälfte der Hardware benötigen – ist das eine Ingenieursleistung. Wenn wir die gleiche Menge an Rechenressourcen verwenden, können wir 2x (oder 3, 4, 5, 10x) Daten durcharbeiten – es können völlig neue Anwendungen desselben Programms eröffnet werden. Es kann auf einem Mobiltelefon in Ihrer Tasche statt auf einem Server ausgeführt werden. Manchmal können wir die Geschwindigkeit steigern, indem wir clevere Algorithmen anwenden oder in eine leistungsfähigere Sprache umschreiben. Das sind unsere ersten Optionen, die wir erkunden können, ja. Aber sie haben eine Grenze. Architektur schlägt fast immer die Umsetzung. Moors Gesetz funktioniert in letzter Zeit nicht so gut, die Leistung einer einzelnen CPU wächst langsam, die RAM-Leistung (hauptsächlich Latenz) hinkt hinterher. Daher begannen die Ingenieure natürlich, nach anderen Optionen zu suchen.

Der zweite Gesichtspunkt ist die Zuverlässigkeit . Die Natur ist chaotisch, der zweite Hauptsatz der Thermodynamik arbeitet ständig gegen alles Präzise, Sequentielle und Wiederholbare. Bits kippen um, Materialien verschlechtern sich, der Strom fällt aus, Kabel werden durchtrennt und verhindern die Ausführung unserer Programme. Die Aufrechterhaltung einer sequentiellen und wiederholbaren Abstraktion wird zu einer schwierigen Aufgabe. Wenn unsere Programme Software- und Hardwareausfälle überdauern könnten, könnten wir Dienstleistungen erbringen, die einen Wettbewerbsvorteil für uns bieten – das ist eine weitere technische Aufgabe, der wir uns widmen können.

Mit dem Ziel ausgestattet, können wir Experimente mit nicht-serialisierten Ansätzen starten.

Threads der Ausführung

Schauen wir uns diesen Teil des Pseudocodes an:

```

def fetch_coordinates(poi: str) -> Point:

…

def find_pois(center: Point, distance: int) -> List[str]:

…

def get_my_location() -> Point:

…
def fetch_coordinates(p) - Point:
…

def main():

me = get_my_location()

for point in find_pois(me, 500):
loc = fetch_coordinates(point)
sys.stdout.write(f“Name: {point} is at x={loc.x} y={loc.y}”)

Wir können den Code von oben nach unten lesen und vernünftigerweise davon ausgehen, dass die Funktion „find_pois“ nach „get_my_location“ aufgerufen wird. Und wir rufen die Koordinaten des ersten POI ab und geben sie zurück, nachdem wir den nächsten abgerufen haben. Diese Annahmen sind korrekt und ermöglichen die Erstellung eines mentalen Modells und einer Begründung für das Programm.

Stellen wir uns vor, wir könnten unseren Code so gestalten, dass er nicht sequentiell ausgeführt wird. Es gibt viele Möglichkeiten, dies syntaktisch zu tun. Wir überspringen Experimente mit der Neuordnung von Anweisungen (das machen moderne Compiler und CPUs) und erweitern unsere Sprache, sodass wir ein neues Funktionsausführungsregime ausdrücken können: gleichzeitig oder auch parallel zu im Hinblick auf andere Funktionen. Um es anders auszudrücken: Wir müssen mehrere Ausführungsthreads einführen. Unsere Programmfunktionen werden in einer bestimmten Umgebung ausgeführt (vom Betriebssystem erstellt und verwaltet). Im Moment interessieren uns adressierbarer virtueller Speicher und ein Thread – eine Planungseinheit, etwas, das von einer CPU ausgeführt werden kann.

Threads gibt es in verschiedenen Varianten: POSIX-Thread, grüner Thread, Coroutine, Goroutine. Die Details sind sehr unterschiedlich, aber es kommt auf etwas an, das ausgeführt werden kann. Wenn mehrere Funktionen gleichzeitig ablaufen können, benötigt jede eine eigene Planungseinheit. Das heißt, wo Multithreading herkommt, haben wir statt einem mehrere Ausführungsthreads. Einige Umgebungen (MPI) und Sprachen können Threads implizit erstellen, aber normalerweise müssen wir dies explizit tun, indem wir „pthread_create“ in C, „threading“-Modulklassen in Python oder eine einfache „go“-Anweisung in Go verwenden. Mit einigen Vorsichtsmaßnahmen können wir dafür sorgen, dass derselbe Code größtenteils parallel ausgeführt wird:

 def fetch_coordinates(poi, results, idx) -> None: … results[idx] = poi def main(): me = get_my_location() points = find_pois(me, 500) results = [None] * len(points) # Reserve space for each result threads = [] for i, point in enumerate(find_pois(me, 500)): # i - index for result thr = threading.Thread(target=fetch_coordinates, args=(poi, results, i)) thr.start() threads.append(thr) for thr in threads: thr.wait() for point, result in zip(points, results): sys.stdout.write(f“Name: {poi} is at x={loc.x} y={loc.y}”)

Wir haben unser Leistungsziel erreicht: Unser Programm kann auf mehreren CPUs laufen und mit zunehmender Anzahl an Kernen skalieren und schneller abgeschlossen werden. Die nächste technische Frage, die wir stellen müssen: Zu welchem Preis?

Wir haben bewusst auf eine serialisierte und vorhersehbare Ausführung verzichtet. Es gibt keine Bijektion zwischen einer Funktion + Zeitpunkt und den Daten. Zu jedem Zeitpunkt gibt es immer eine einzige Zuordnung zwischen einer laufenden Funktion und ihren Daten:

Die nächste Konsequenz besteht darin, dass eine Funktion diesmal vor einer anderen beendet werden kann, beim nächsten Mal kann es umgekehrt sein. Dieses neue Ausführungsregime führt zu Datenwettläufen: Wenn gleichzeitige Funktionen mit Daten arbeiten, bedeutet dies, dass die Reihenfolge der auf die Daten angewendeten Operationen undefiniert ist. Wir stoßen auf Datenrennen und lernen, mit ihnen umzugehen, indem wir:

• Kritische Abschnitte: Mutexe (und Spinlocks)
• Sperrfreie Algorithmen (die einfachste Form finden Sie im Snippet oben)
• Tools zur Rassenerkennung
• usw

An diesem Punkt entdecken wir mindestens zwei Dinge. Erstens gibt es mehrere Möglichkeiten, auf Daten zuzugreifen. Einige Daten sind lokal (z. B. funktionsbezogene Variablen) und nur wir können es sehen (und darauf zugreifen) und daher ist es immer in dem Zustand, in dem wir es verlassen haben. Einige Daten werden jedoch weitergegeben bzw Fernbedienung . Es befindet sich immer noch in unserem Prozessspeicher, aber wir verwenden spezielle Methoden, um darauf zuzugreifen, und es kann sein, dass es nicht mehr synchron ist. Um damit zu arbeiten, kopieren wir es in einigen Fällen in unseren lokalen Speicher, um Datenrennen zu vermeiden – deshalb == .Klon() ==ist in Rust beliebt.

Wenn wir diese Argumentation fortsetzen, kommen andere Techniken wie Thread-lokale Speicherung ganz natürlich ins Spiel. Wir haben gerade ein neues Gerät in unseren Programmier-Werkzeuggürtel aufgenommen, das unsere Möglichkeiten beim Erstellen von Software erweitert.

Es gibt jedoch eine Invariante, auf die wir uns immer noch verlassen können. Wenn wir von einem Thread nach freigegebenen (entfernten) Daten greifen, erhalten wir diese immer. Es gibt keine Situation, in der ein Speicherblock nicht verfügbar ist. Das Betriebssystem beendet alle Teilnehmer (Threads), indem es den Prozess abbricht, wenn der unterstützende physische Speicherbereich eine Fehlfunktion aufweist. Das Gleiche gilt für „unseren“ Thread: Wenn wir einen Mutex gesperrt haben, besteht keine Möglichkeit, dass wir die Sperre verlieren und wir müssen sofort aufhören, was wir gerade tun. Wir können uns auf diese Invariante (durch das Betriebssystem und moderne Hardware erzwungen) verlassen, dass alle Teilnehmer entweder tot oder lebendig sind. Alle teilen das Schicksal : Wenn der Prozess (OOM), das Betriebssystem (Kernel-Fehler) oder die Hardware auf ein Problem stößt, werden alle unsere Threads nicht mehr zusammen existieren, ohne dass externe Nebenwirkungen übrig bleiben.

Einen Prozess erfinden

Eine wichtige Sache ist zu beachten. Wie haben wir diesen ersten Schritt durch die Einführung von Threads gemacht? Wir trennten uns, spalteten uns. Anstelle einer Planungseinheit haben wir mehrere eingeführt. Lassen Sie uns diesen Unsharing-Ansatz weiter anwenden und sehen, wie er funktioniert. Dieses Mal kopieren wir den virtuellen Prozessspeicher. Das nennt man - einen Prozess erzeugen . Wir können eine andere Instanz unseres Programms ausführen oder ein anderes vorhandenes Dienstprogramm starten. Dies ist ein großartiger Ansatz für:

• Anderen Code mit strengen Grenzen wiederverwenden
• Führen Sie nicht vertrauenswürdigen Code aus und isolieren Sie ihn aus unserem eigenen Speicher

Fast alle == moderne Browser ==Auf diese Weise funktionieren sie, sodass sie nicht vertrauenswürdigen, aus dem Internet heruntergeladenen ausführbaren Javascript-Code ausführen und ihn zuverlässig beenden können, wenn Sie einen Tab schließen, ohne die gesamte Anwendung herunterzufahren.

Dies ist ein weiteres Ausführungsregime, das wir entdeckt haben, indem wir die gemeinsame Schicksalsinvariante aufgegeben und den virtuellen Speicher freigegeben und eine Kopie erstellt haben. Kopien sind nicht kostenlos:

• Das Betriebssystem muss speicherbezogene Datenstrukturen verwalten (um die virtuelle -> physische Zuordnung aufrechtzuerhalten).
• Einige Bits könnten gemeinsam genutzt worden sein und daher verbrauchen Prozesse zusätzlichen Speicher

Ausbrechen

Warum hier aufhören? Lassen Sie uns untersuchen, was wir sonst noch kopieren und unser Programm verteilen können. Aber warum sollte man überhaupt verteilt werden? In vielen Fällen können anstehende Aufgaben mit einer einzigen Maschine gelöst werden.

Wir müssen verteilt vorgehen um dem gemeinsamen Schicksal zu entkommen Grundsätze, so dass unsere Software abhängig von den unvermeidlichen Problemen, auf die die zugrunde liegenden Schichten stoßen, stoppt.

Um ein paar zu nennen:

• Betriebssystem-Upgrades: Von Zeit zu Zeit müssen wir unsere Maschinen neu starten

• Hardwareausfälle: Sie kommen häufiger vor, als uns lieb ist

• Externe Ausfälle: Strom- und Netzwerkausfälle sind an der Tagesordnung.

  
  

Wenn wir ein Betriebssystem kopieren, nennen wir das eine virtuelle Maschine und können Kundenprogramme auf einer physischen Maschine ausführen und darauf ein riesiges Cloud-Geschäft aufbauen. Wenn wir zwei oder mehr Computer nehmen und unsere Programme auf jedem ausführen, kann unser Programm sogar einen Hardwareausfall überstehen, einen 24/7-Service bieten und sich einen Wettbewerbsvorteil verschaffen. Große Unternehmen gingen vor langer Zeit sogar noch weiter, und jetzt betreiben Internetgiganten Kopien in verschiedenen Rechenzentren und sogar auf Kontinenten und machen so ein Programm widerstandsfähig gegenüber einem Taifun oder einem einfachen Stromausfall.

Aber diese Unabhängigkeit hat ihren Preis: Die alten Invarianten werden nicht durchgesetzt, wir sind auf uns allein gestellt. Keine Sorge, wir sind nicht die Ersten. Es gibt viele Techniken, Tools und Dienste, die uns helfen.

Imbissbuden

Wir haben gerade die Fähigkeit erlangt, über Systeme und ihre jeweiligen Ausführungsregime nachzudenken. In jedem großen Scale-Out-System sind die meisten Teile sequenziell und zustandslos, viele Komponenten sind Multithreading mit Speichertypen und Hierarchien, die alle durch eine Mischung einiger wirklich verteilter Teile zusammengehalten werden:

Das Ziel besteht darin, unterscheiden zu können, wo wir uns gerade befinden, welche Invarianten gelten und entsprechend zu handeln (zu modifizieren/designen). Wir haben die grundlegende Argumentation hervorgehoben und „unbekannte Unbekannte“ in „bekannte Unbekannte“ umgewandelt. Nehmen Sie es nicht auf die leichte Schulter, das ist ein bedeutender Fortschritt.