vektoriaikaleimat

Vektoriaikaleimat ovat hajautetuissa järjestelmissä käytettyjä tapahtumien aikaleimoja, jotka auttavat määrittämään tapahtumien välistä suhdetta. Jokaisessa prosessissa ylläpidetään oma vektori, jonka jokainen komponentti vastaa yhtä järjestelmän prosessia ja kertoo sen tästä hetkestä, kuinka monta omaa tapahtumaa kyseinen prosessi on tuolloin tuottanut.

Toiminta: Kun prosessi lähettää viestin, se kasvattaa oman komponenttinsa arvoa yhdellä ja liittää vektorin viestin mukaan. Vastaanottava prosessi päivittää oman vektorinsa ottamalla vastaanotetun vektorin ja oman nykyisen vektorinsa komponenttien maksimit, ja tämän jälkeen merkitsee vastaanoton yhden tapahtumana omassa järjestelmässään.

Vertaaminen ja syy-seuraus: Vektorit A ja B voidaan vertailla siten, että A edeltää B, jos kaikilla i A[i] <= B[i] ja ainakin yhdessä i:llä A[i] < B[i]. Jos A <= B ja B <= A eivät päde yhtä aikaa, kyseessä ovat rinnakkaiset tapahtumat. Tämä peruste on syy-seurausvaikutuksen arvioinnissa ja järjestelmän konsistenssissa.

Sovellukset: Vektoriaikaleimoja käytetään hajautetuissa tietokannoissa, tapahtumien lajittelussa ja konfliktienratkaisussa CRDT-pohjaisissa järjestelmissä, joissa on useita päivittyviä kopioita. Ne mahdollistavat konvergenssin ja paikallisen päätöksenteon ilman luotettavaa, globalisoitua kelloa.

Rajoitukset: Vektoriaikaleimojen muistivaatimus kasvaa lineaarisesti prosessien määrän mukaan. Kun järjestelmään lisätään tai poistetaan prosesseja, vektorin pituutta on muutettava, mikä voi lisätä hallinnollista kompleksiutta. Vertailu vaatii O(n) aikaa, ja suurissa järjestelmissä viestintä- ja laskentakuorma kasvaa.