Vektor klocka - Vector clock

En vektorklocka är en datastruktur som används för att bestämma den partiella ordningen av händelser i ett distribuerat system och detektera kausalitetsöverträdelser . Precis som i Lamports tidsstämplar innehåller meddelanden mellan processer statusen för sändningsprocessens logiska klocka . En vektorklocka i ett system med N -processer är en array /vektor av N logiska klockor, en klocka per process; en lokal "största möjliga värden" -kopia av den globala klockmatrisen förvaras i varje process.

Beteckna som vektorklockan som upprätthålls av process i, klockuppdateringarna fortsätter enligt följande: ${\ displaystyle VC_ {i}}$

Exempel på ett system med vektorklockor. Händelser i den blå regionen är orsakerna till händelse B4, medan de i den röda regionen är effekterna av händelse B4.

• Inledningsvis är alla klockor noll.
• Varje gång en process upplever en intern händelse, ökar den sin egen logiska klocka i vektorn med en. Till exempel, vid en händelse vid process i, uppdateras den .${\ displaystyle VC_ {i} [i] \ leftarrow VC_ {i} [i] +1}$
• Varje gång en process skickar ett meddelande, ökar den sin egen logiska klocka i vektorn med en (som i punkten ovan, men inte två gånger för samma händelse) och sedan tar meddelandet en kopia av sin egen vektor.
• Varje gång en process tar emot ett meddelande, ökar den sin egen logiska klocka i vektorn med ett och uppdaterar varje element i sin vektor genom att ta maxvärdet i sin egen vektorklocka och värdet i vektorn i det mottagna meddelandet (för varje element). Till exempel, om process Pj får ett meddelande m från Pi, uppdateras det genom att ställa in .${\ displaystyle VC_ {j} \ leftarrow max (VC_ {j} [k]+1, VC_ {i} [k]), \ forall k}$

Historia

Utan att använda det specifika namnet "vektorklocka" nämndes begreppet en vektorklocka först i ett papper från 1986 av Rivka Ladin och Barbara Liskov där de använder termen "flerdelstidsstämpel". För att citera från sidan 31 i Liskov/Ladin -papperet:

Vi löser detta problem genom att använda tidsstämplar med flera delar , där det finns en del för varje replika. Således, om det finns n kopior, är en tidsstämpel t

t = <t1, …, tn>

där varje del är ett positivt heltal. Eftersom det vanligtvis kommer att finnas ett litet antal kopior (t.ex. 3 till 7) är det praktiskt att använda en sådan tidsstämpel.

Termen "vektorklocka" användes först oberoende av Colin Fidge och Friedemann Mattern 1988.

Delbeställningsfastighet

Vektorklockor möjliggör en partiell kausal ordning av händelser. Definierar följande:

• ${\ displaystyle VC (x)}$betecknar händelsens vektorklocka och betecknar komponenten i klockan för processen .${\ displaystyle x}$${\ displaystyle VC (x) _ {z}}$${\ displaystyle z}$
• ${\ displaystyle VC (x) <VC (y) \ iff \ forall z [VC (x) _ {z} \ leq VC (y) _ {z}] \ land \ exist z '[VC (x) _ { z '} <VC (y) _ {z'}]}$
  • På engelska: är mindre än , om och bara om är mindre än eller lika med för alla processindex , och minst en av dessa relationer är strikt mindre (det vill säga ).${\ displaystyle VC (x)}$${\ displaystyle VC (y)}$${\ displaystyle VC (x) _ {z}}$${\ displaystyle VC (y) _ {z}}$${\ displaystyle z}$${\ displaystyle VC (x) _ {z '} <VC (y) _ {z'}}$
• ${\ displaystyle x \ to y \;}$betecknar att händelsen inträffade före händelsen . Det definieras som: om , då${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x \ to y \;}$${\ displaystyle VC (x) <VC (y)}$

Egenskaper:

• Antisymmetri : om , då ¬${\ displaystyle VC (a) <VC (b)}$${\ displaystyle (VC (b) <VC (a))}$
• Transitivitet : om och , då ; eller, om och , då${\ displaystyle VC (a) <VC (b)}$${\ displaystyle VC (b) <VC (c)}$${\ displaystyle VC (a) <VC (c)}$${\ displaystyle a \ to b \;}$${\ displaystyle b \ to c \;}$${\ displaystyle a \ to c \;}$

Förhållande till andra order:

• Låt vara i realtid när händelse inträffar. Om , då${\ displaystyle RT (x)}$${\ displaystyle x}$${\ displaystyle VC (a) <VC (b)}$${\ displaystyle RT (a) <RT (b)}$
• Låt vara Lamport -tidsstämpeln för händelsen . Om , då${\ displaystyle C (x)}$${\ displaystyle x}$${\ displaystyle VC (a) <VC (b)}$${\ displaystyle C (a) <C (b)}$

Andra mekanismer

• År 1999 utvecklade Torres-Rojas och Ahamad Plausible Clocks , en mekanism som tar mindre plats än vektorklockor men som i vissa fall helt kommer att ordna händelser som är kausalt samtidiga.

• År 2005 skapade Agargwal och Garg Chain Clocks , ett system som spårar beroenden med hjälp av vektorer med mindre storlek än antalet processer och som automatiskt anpassar sig till system med dynamiskt antal processer.
• 2008, Almeida et al. introducerade Interval Tree Clocks . Denna mekanism generaliserar vektorklockor och möjliggör drift i dynamiska miljöer när identiteten och antalet processer i beräkningen inte är kända i förväg.

• År 2019 utvecklade Lum Ramabaja Bloom Clocks , en sannolikhetsdatastruktur vars rymdkomplexitet inte beror på antalet noder i ett system. Om två klockor inte är jämförbara kan blomklockan alltid härleda det, dvs. falska negativ är inte möjliga. Om två klockor är jämförbara kan blomklockan beräkna tillförlitligheten för det påståendet, det vill säga det kan beräkna den falska positiva hastigheten mellan jämförbara klockpar.

Se även

• Lamport tidsstämplar
• Matris klockor
• Versionsvektor

Referenser

externa länkar

• Varför logiska klockor är enkla (Jämför orsakshistorier, vektorklockor och versionsvektorer)
• Förklaring av vektorklockor
• Tidsstämpelbaserad vektorklockaimplementering i Erlang
• Vektorklockaimplementering i Objective-C
• Vektor klocka implementering i Erlang
• Varför vektorklockor är svåra
• Varför Cassandra inte behöver vektorklockor