Vektorokra

Vektorokra on hajautettujen järjestelmien aikaleima, jolla tarkoitetaan vektorin muotoista tapahtumien tunnistetta. Vektorokra muistuttaa vektoria, jonka pituus vastaa järjestelmän prosessien määrää, ja jonka jokainen komponentti kuvaa kyseisen prosessin viimeksi tapahtunutta tapahtumaa.

Toimintaperiaate on seuraava: jokainen prosessi ylläpitää omaa vektoria V. Paikallinen tapahtuma kasvattaa sen omanssa indeksissä olevaa arvoa yhdellä. Kun prosessi lähettää viestin, viestiin liitetään nykyinen vektori. Viestin vastaanottaminen koostuu siitä, että vastaanottava prosessi kasvattaa omaa komponenttiaan yhdellä ja päivittää vektorin arvot niin, että jokainen komponentti V[i] asetetaan suurimmaksi arvoksi vastaanotetun vektorin vastaavan komponentin kanssa (elementwise max). Näin voidaan määritellä causal-suhde: A happened-before B, jos kaikilla i pätee V_A[i] ≤ V_B[i] ja on ainakin yksi i, jolla V_A[i] < V_B[i]. Jos kumpikin suhde pätee toisilleen, tapahtumat ovat ristiriidattomia (concurrent).

Käyttökohteita ovat tapahtumien causality-harjan määrittäminen hajautetuissa järjestelmissä, virheenkorjaus ja debugging, versionhallinta sekä joissakin CRDT- ja tietokantatekniikoissa tapa tarkistaa, ovatko tapahtumat järjestyksessä vai rinnakkaisia. Vektorokri käyttösääntöjä vastaa usein perinteisiä yksinkertaisia kelloja (Lamport-ajat), mutta ne tarjoavat tarkemman syy-seuraussuhteen.

Rajoitteita ovat tarve tuntea järjestelmän prosessien määrä, vektorin koon kasvu lineaarisesti siihen ja viestinnän lisääntyvä kustannus (O(n) tilaa ja viestiä kohti). Naksuissa verkon hajautetuissa järjestelmissä vektorokran käyttö voi olla haasteellista, jos prosesseja on paljon tai niiden määrä muuttuu usein.

Vektorokra otettiin käyttöön itsenäisesti Fidge ja Mattern vuonna 1988, ja siitä on sittemmin tullut keskeinen käsitteellinen työkalu hajautetuissa järjestelmissä.