vektortidsstämplar

Vektortidsstämplar är en logisk klocka som används i distribuerade system för att fånga kausaliteten mellan händelser. Varje process i systemet upprätthåller en vektor av räknare vars längd motsvarar antalet aktiva processer som kan kommunicera. Vid varje lokal händelse ökas den egna komponenten i vektorn med ett steg. När ett meddelande skickas bifogas vektortidsstämpeln och mottagaren uppdaterar sin vektor genom att ta komponentvis maximum mellan sin nuvarande vektor och den mottagna.

Relationen mellan händelser definieras av vektorerna: X hände före Y om för varje i gäller X[i] ≤ Y[i] och det finns minst en i där X[i] < Y[i]. Om inga sådana villkor uppfylls är händelserna samtidiga (konkurrenta). Denna konstruktion gör det möjligt att avgöra kausalitet utan att använda exakt fysisk tid, vilket är viktigt i system där klockor inte kan synchroniseras helt.

Implementationen bygger på att varje process i varje lokal händelse uppdaterar sin egen komponent och att varje skickat meddelande bär med sig den aktuella vektorn. Vid mottagande uppdateras mottagarens vektor genom att ta maximum mellan den egna och den inkomna vektorn. Till skillnad mot enklare logiska klockor fångar vektortidsstämplar kausalitet mellan flera processer och kan avgöra om två händelser är samtidiga eller inte.

Begränsningar inkluderar att storleken på vektorn växer med antalet processer, vilket gör lagring och uppdateringar kostsamma i stora eller mycket dynamiska system. Per händelse krävs ofta O(N) tid och bandbredden ökar eftersom vektorn piggybacks på meddelanden. Dynamiska system kräver mekanismer för att hantera processer som går in och ut, samt möjligheter till garbage collection och uppdatering av indexering.

Användningsområden inkluderar databasreplikering och versionskontroll i MVCC, konfliktlösning i CRDT-baserade system samt generellt spårning av orsakssamband i distribuerade loggar och händelsebaserade arkitekturer. Vektortidsstämplar är ett verktyg för att uppnå konsekvens och felrapportering utan global tidsstämpling.