Vektoruhr

A Vektoruhr ist ein Datenstruktur verwendet zur Bestimmung der teilweise Bestellung von Ereignissen in a verteiltes System und Erkennen Kausalität Verstöße. Genau wie in Lamport Timestemps, Inter-Process-Nachrichten enthalten den Status des Sendungsprozesses logische Uhr. Eine Vektoruhr eines Systems von N Prozesse ist ein Array/Vektor von N logische Uhren, eine Uhr pro Prozess; Eine lokale Kopie des Global Clock-Array "größtmögliche Werte" wird in jedem Prozess gehalten.

Bezeichnen ${\ displayStyle vc_ {i}}$ Da die Vektoruhr von Prozess I gepflegt wird, verlaufen die Uhr -Updates wie folgt:^[1]

Beispiel eines Systems von Vektoruhren. Ereignisse in der blauen Region sind die Ursachen, die zu Ereignis B4 führen, während diejenigen in der roten Region die Auswirkungen von Ereignis B4 sind.

• Anfangs sind alle Uhren Null.
• Jedes Mal, wenn ein Prozess ein internes Ereignis erfährt, erhöht es seine eigene logische Uhr im Vektor von einem. Zum Beispiel aktualisiert es bei einem Ereignis bei Process I ${\ displayStyle vc_ {i} [i] \ Leftarrow vc_ {i} [i] +1}$.
• Jedes Mal, wenn ein Prozess eine Nachricht sendet, erhöht er seine eigene logische Uhr im Vektor um eins (wie in der oben genannten Kugel, jedoch nicht zweimal für dasselbe Ereignis) und dann die Meldung eine Kopie eines eigenen Vektors.
• Jedes Mal, wenn ein Prozess eine Nachricht erhält, erhöht er seine eigene logische Uhr im Vektor um eins und aktualisiert jedes Element in seinem Vektor, indem der Wert des Wertes in seiner eigenen Vektoruhr und des Werts im Vektor in der empfangenen Nachricht (für den Vektor "(für den Wert jedes Element). Wenn der Prozess PJ beispielsweise eine Nachricht m aus PI empfängt, aktualisiert es sich durch Einstellen $oder$.

Geschichte

Ohne den spezifischen Namen "Vector Clock" wurde das Konzept einer Vektoruhr zuerst erwähnt^[2] in einem 1986er Artikel von 1986 Rivka Ladin und Barbara Liskov wo sie den Begriff "mehrteiler Zeitstempel" verwenden.^[3] So zitieren Sie aus Seite 31 des Liskov/Ladin -Papiers:

Wir lösen dieses Problem durch die Verwendung Mehrteilige Zeitstempel, wo es einen Teil für jede Replik gibt. Wenn es also N -Repliken gibt, ist ein Zeitstempel t t

t =

wo jeder Teil eine positive Ganzzahl ist. Da es in der Regel eine kleine Anzahl von Repliken (z. B. 3 bis 7) gibt, ist es praktisch, wenn ein solcher Zeitstempel verwendet wird.

Der Begriff "Vektoruhr" wurde erstmals unabhängig von Colin Fidge und verwendet Friedemann Matter 1988.^[4][5]

Teilweise Bestelleigentum

Vektoruhren ermöglichen die teilweise kausale Reihenfolge von Ereignissen. Definieren Sie Folgendes:

• ${\ displayStyle vc (x)}$ bezeichnet die Vektoruhr des Ereignisses ${\ displayStyle x}$, und ${\ displayStyle vc (x) _ {z}}$ bezeichnet die Komponente dieser Uhr für den Prozess ${\ displayStyle z}$.
• $oder z '} <vc (y) _ {z'}]}$
  • Auf Englisch: ${\ displayStyle vc (x)}$ ist weniger als ${\ displayStyle vc (y)}$, dann und nur dann, wenn ${\ displayStyle vc (x) _ {z}}$ ist kleiner als oder gleich zu ${\ displayStyle vc (y) _ {z}}$ Für alle Prozessindizes ${\ displayStyle z}$und mindestens eine dieser Beziehungen ist streng kleiner (dh,, ${\ displayStyle vc (x) _ {z '} <vc (y) _ {z'}}$).
• ${\ displayStyle x \ bis y \;}$ bezeichnet dieses Ereignis ${\ displayStyle x}$ passiert vor Ereignis ${\ displayStyle y}$. Es ist definiert als: wenn ${\ displayStyle x \ bis y \;}$, dann ${\ displayStyle vc (x) <vc (y)}}$

Eigenschaften:

• Antisymmetrie: wenn ${\ displayStyle vc (a) <vc (b)}$dann ¬${\ displayStyle (vc (b) <vc (a))}$
• Transitivität: wenn ${\ displayStyle vc (a) <vc (b)}$ und ${\ displayStyle vc (b) <vc (c)}$, dann ${\ displayStyle vc (a) <vc (c)}$; oder wenn ${\ displayStyle a \ bis b \;}$ und ${\ displayStyle b \ bis c \;}$, dann ${\ displayStyle a \ bis c \;}$

Beziehung zu anderen Bestellungen:

• Lassen ${\ displayStyle rt (x)}$ Sei die Echtzeit beim Ereignis ${\ displayStyle x}$ tritt ein. Wenn ${\ displayStyle vc (a) <vc (b)}$, dann ${\ displayStyle rt (a) <rt (b)}$
• Lassen ${\ displayStyle c (x)}$ sei der Lamport Timestamp der Veranstaltung ${\ displayStyle x}$. Wenn ${\ displayStyle vc (a) <vc (b)}$, dann ${\ displayStyle c (a) <c (b)}}$

Andere Mechanismen

• 1999 entwickelten sich Torres-Rojas und Ahamad Plausible Uhren,^[6] Ein Mechanismus, der weniger Platz als Vektoruhren benötigt, in einigen Fällen jedoch Ereignisse, die kausal gleichzeitig sind, vollständig bestellen.

• Im Jahr 2005 kreierten Agargwal und Garg Kettenuhren,^[7] Ein System, das Abhängigkeiten anhand der Vektoren mit einer Größe von kleiner als der Anzahl der Prozesse verfolgt und sich automatisch an Systeme mit dynamischer Anzahl von Prozessen anpasst.
• Im Jahr 2008 Almeida et al. eingeführt Intervall -Baumuhren.^[8][9][10] Dieser Mechanismus verallgemeinert Vektoruhren und ermöglicht den Betrieb in dynamischen Umgebungen, wenn die Identität und die Anzahl der Prozesse in der Berechnung im Voraus nicht bekannt sind.

• Im Jahr 2019 entwickelte sich Lum Ramabaja Blüte Uhren,^[11] Eine probabilistische Datenstruktur, deren Raumkomplexität nicht von der Anzahl der Knoten in einem System abhängt. Wenn zwei Uhren nicht vergleichbar sind, kann die Bloom -Uhr sie immer ableiten, d. H. Falsche Negative sind nicht möglich. Wenn zwei Uhren vergleichbar sind, kann die Bloom -Uhr das Vertrauen dieser Aussage berechnen, d. H. Sie kann die falsch positive Rate zwischen vergleichbaren Uhrenpaaren berechnen.

Siehe auch

• Lamport Timestemps
• Matrixuhren
• Versionsvektor

Verweise

Externe Links

• Warum logische Uhren einfach sind (vergleicht Kausalakten, Vektoruhren und Versionsvektoren)
• Erläuterung der Vektoruhren
• Zeitstempel-basierte Vektoruhr-Implementierung in Erlang
• Implementierung der Vektoruhr in Objective-C
• Implementierung der Vektoruhr in Erlang
• Warum Vektoruhren hart sind
• Warum Cassandra keine Vektoruhren benötigt