Vektor verze - Version vector

A vektor verze je mechanismus pro sledování změn dat v a distribuovaný systém, kde může více agentů aktualizovat data v různých časech. Vektor verze umožňuje účastníkům určit, zda jedna aktualizace předcházela jiné (stalo se předtím ), následoval ji, nebo pokud k oběma aktualizacím došlo souběžně (a proto by mohly být ve vzájemném konfliktu). Tímto způsobem se povolují vektory verzí kauzalita sledování mezi replikami dat a jsou základním mechanismem pro optimistická replikace. Z matematického hlediska generuje vektor verze a předobjednávka který sleduje události, které předcházejí pozdějším aktualizacím a mohou proto ovlivnit jejich pozdější aktualizaci.

Vektory verzí udržují stav stejný jako v a vektorové hodiny, ale pravidla aktualizace se mírně liší; v tomto příkladu mohou repliky zaznamenat lokální aktualizace (např. uživatel, který upravuje soubor v místním uzlu), nebo mohou synchronizovat s jinou replikou:

• Zpočátku jsou všechny vektorové čítače nulové.
• Pokaždé, když replika zažije událost místní aktualizace, zvýší svůj vlastní čítač ve vektoru o jednu.
• Pokaždé dvě repliky A a b synchronizovat, oba nastavili prvky ve své kopii vektoru na maximum prvku přes oba čítače: ${ displaystyle V_ {a} [x] = V_ {b} [x] = max (V_ {a} [x], V_ {b} [x])}$. Po synchronizaci mají dvě repliky identické vektory verzí.

Dvojice replik, A, b, lze porovnat kontrolou jejich vektorů verzí a určit, zda jsou: identické (${ displaystyle a = b}$), souběžně (${ displaystyle a paralelní b}$), nebo objednané (${ displaystyle a$ nebo ${ displaystyle b$). Uspořádaný vztah je definován jako: Vektor ${ displaystyle a$ právě když každý prvek ${ displaystyle V_ {a}}$ je menší nebo rovno odpovídajícímu prvku v ${ displaystyle V_ {b}}$a alespoň jeden z prvků je přísně menší než. Pokud ne ${ displaystyle a$ nebo ${ displaystyle b$, ale vektory nejsou totožné, pak musí být oba vektory souběžné.

Vektory verzí^[1] nebo varianty se používají ke sledování aktualizací v mnoha distribuovaných souborových systémech, například Coda (souborový systém) a Ficus a jsou hlavní datovou strukturou za optimistickou replikací.^[2]

Další mechanismy

• Hash historie ^[3] vyhněte se používání čítačů udržováním sady hodnot hash každé aktualizované verze a porovnáním těchto sad zahrnutím sady. Tento mechanismus však může poskytnout pouze pravděpodobnostní záruky.
• Stručná verze vektorů ^[4] umožňují výrazné úspory místa při manipulaci s více replikovanými položkami, například v adresářových strukturách v souborových systémech.
• Verze Razítka ^[5] povolit sledování variabilního počtu replik a neuchylovat se k počítadlům. Tento mechanismus může v některých nastaveních zobrazit problémy se škálovatelností, ale může být nahrazen Intervalovými hodinami stromu.
• Intervalové hodiny stromu^[6] zobecnit vektory verze a vektorové hodiny a umožňuje dynamický počet replik / procesů.
• Vázaná verze vektory ^[7] povolit omezenou implementaci s omezenými čítači velikosti, pokud lze atomově synchronizovat páry replik.
• Tečkovaná verze vektory ^[8] škálovatelnost adres s malou sadou serverů zprostředkujících přístup k replikám velkým počtem souběžných klientů.

Reference

externí odkazy

• Proč jsou logické hodiny snadné (srovnává kauzální historie, vektorové hodiny a vektory verzí)