Replikácia dát

[pajon]

Dobrý deň.

Potýkam sa s problémom, keď mám viacero uzlov a každý generuje dáta (key-value), ktoré sa majú zdielať medzi uzlami. Je to v podstate master-master replikácia.

Chcel by som sa spýtať, či by ste mi nevedeli doporučiť nejaký konkrétny algoritmus, prípadne info ako by sa dalo s tým niečo spraviť.

Ďakujem

[Reklama]

[anonym]

si schopny rict (nebo upravit aplikaci aby si byl schopny) ze domeny klicu jednotlivych uzlu jsou disjunktni? pak by to bylo jednoduche

hezke reseni sem videl v AD, kde si kazdy uzel drzi posledni "verzi" kterou videl od ostatnich, a navzajem si vymenuji zmeny (coz znamena ze kazdej uzel si drzi nekolik verzi dozadu, jak moc zavisi na tom jak moc velky vypadky spojeni to ma prezit)

[Withy14]

Ahoj, v AD tento algoritmus zvládá DFSR a BITS (BITS není nutný, ale snížuje nároky na síť), jinak by to chtělo upřesnit dotaz, co se myslí těmi daty? Pokud sou to data = soubory, tak to může být problém, představ si, že uzel A vygeneruje soubor AB s nějakými údaji, uzel B vygeneruje soubor AB, ale s jinými údaji, teď jak rozhodnout který je platný? Nebo to sou data, která ti například generuje nějaká databáze?

[pajon]

Skúsim to trocha upresniť. Kľúč predstavuje identifikátor používateľa (32 - bajtový identifikátor) a hodnota je adresa uzla kde je používateľ pripojený (napríklad IPv4). Ak sa používateľ pripojí na daný uzol, vytvorí sa záznam (key-value už spomínané), ktorý upozorní, že sa daný používateľ pripojil na daný uzol.

[franz]

Zkuste byt trochu konkretni, co ten system ma delat/resit, tohle je stale nic nerikajici, nebo je to tajne?

[Reklama]

[pajon]

Je to verejné, ale myslel som, že toto bude stačiť. ( https://github.com/pajon/crycom )

Jedná sa o decentralizovaný komunikačný protokol realizovaný dvoma druhmi uzlov označovaný ako nodea snode, kde snode je superuzol. V princípe je to tak, že klienti sa pripájajú na nody a tie komunikujú s minimálne jedným snode. Vzhľadom na povahu protokolu, prebieha autentifikácia kde je potrebné overiť klienta. Po úspešnej autentifikácií sa vytvorí spomínaný key-value, ktorý sa rozpošle na ostatné snody. A tento záznam potrebujem udržať konzistentný na všetkých snodoch.

A používa sa to na to, že keď je klientA pripojený na node1 a klientB pripojený na node2 a chcú medzi sebou komunikovať aby vedel každý snode odpovedať kde sa aký klient nachádza.

Snáď to pochopíte.

[ps]

Pri predpoklade že všetky snody o sebe vedia, určite nepotrebuješ aby všetky snody držali konzistentné kópie všetkých dát.
Rozmýšľal si rozdeliť možné hash hodnoty kľúčov medzi snody? Príklad: máš N (>= M) snodov a chceš držať aspoň M replík dát. To znamená že pre každú hash hodnotu budeš musieť vedieť určiť M snodov kde sa má hodnota nachádzať. A teraz máš nasledovné možnosti: [http://en.wikipedia.org/wiki/Quorum_(distributed_computing)]
a) chceš aby synchrónny zápis do takejto key value distribuovanej databázy prebehol čo najrýchlejšie. Zapisuješ naraz na všetkých M nodov, ale klientovi (v tomto prípade asi anodu) potvrdzuješ zápis už pri prvom úspešnom potvrdení od ktoréhokoľvek s-nodu.
b) chceš aby čítanie z DB prebehlo čo najrýchlejšie - Potvrdzuješ zápis až keď je zmena rozkopírovaná na všetky zodpovedné snody. Čítanie môžeš potom robiť z ktoréhokoľvek z nich.
c) chceš niečo medzi a a b - pri zápise čakáš na potvrdenie od n/2+1 uzlov.  Takisto realizuješ čítanie z n/2+1 uzlov.
Samozrejme pre hodnoty si musíš ukladať aj timestamp aby si vedel posúdiť ktorá verzia je najnovšia. Pri vymazaní hodnoty kľúč nemažeš, ale poznačíš si timestamp zmazania.

Samozrejme situácia je iná pokiaľ nepotrebuješ synchrónny zápis a je ti jedno že v niektorých okamihoch bude databáza nekonzistentná, a je pre teba dôležité iba aby niekedy doiterovala do konzistentného stavu.
Poprípade ak jednotlivé snody nevedia o všetkých s-nodoch a vymieňajú si informácie iba cez susedov. To by sa dalo riešiť najjednoduchšie tak že každý node po prijatí transakcie skontroluje či je pre neho nová ak áno tak si ju uloží a prepošle na všetkých ostatých susedov. Ak by bolo treba minimalizovať komunikáciu potom bude treba asi najprv treba skúsiť vytvoriť minimálny graf aby sa dáta neposielali duplicitne.

Ale to sú už iné story.

[pajon]

Pri predpoklade že všetky snody o sebe vedia, určite nepotrebuješ aby všetky snody držali konzistentné kópie všetkých dát.
Rozmýšľal si rozdeliť možné hash hodnoty kľúčov medzi snody? Príklad: máš N (>= M) snodov a chceš držať aspoň M replík dát. To znamená že pre každú hash hodnotu budeš musieť vedieť určiť M snodov kde sa má hodnota nachádzať. A teraz máš nasledovné možnosti: [http://en.wikipedia.org/wiki/Quorum_(distributed_computing)]
a) chceš aby synchrónny zápis do takejto key value distribuovanej databázy prebehol čo najrýchlejšie. Zapisuješ naraz na všetkých M nodov, ale klientovi (v tomto prípade asi anodu) potvrdzuješ zápis už pri prvom úspešnom potvrdení od ktoréhokoľvek s-nodu.
b) chceš aby čítanie z DB prebehlo čo najrýchlejšie - Potvrdzuješ zápis až keď je zmena rozkopírovaná na všetky zodpovedné snody. Čítanie môžeš potom robiť z ktoréhokoľvek z nich.
c) chceš niečo medzi a a b - pri zápise čakáš na potvrdenie od n/2+1 uzlov.  Takisto realizuješ čítanie z n/2+1 uzlov.
Samozrejme pre hodnoty si musíš ukladať aj timestamp aby si vedel posúdiť ktorá verzia je najnovšia. Pri vymazaní hodnoty kľúč nemažeš, ale poznačíš si timestamp zmazania.

Samozrejme situácia je iná pokiaľ nepotrebuješ synchrónny zápis a je ti jedno že v niektorých okamihoch bude databáza nekonzistentná, a je pre teba dôležité iba aby niekedy doiterovala do konzistentného stavu.
Poprípade ak jednotlivé snody nevedia o všetkých s-nodoch a vymieňajú si informácie iba cez susedov. To by sa dalo riešiť najjednoduchšie tak že každý node po prijatí transakcie skontroluje či je pre neho nová ak áno tak si ju uloží a prepošle na všetkých ostatých susedov. Ak by bolo treba minimalizovať komunikáciu potom bude treba asi najprv treba skúsiť vytvoriť minimálny graf aby sa dáta neposielali duplicitne.

Ale to sú už iné story.

V prvom rade ďakujem za super odpoveď.

snody o sebe vedia a každý je s každým prepojený. Ak táto sieť bude reálne spustená tak počet snodov bude pár. Predpokladám max +-5

1. Na základe toho by sa dala aplikovať metóda, kedy pri vytvorený key-value bude potvrdená od všetkých snodoch.

2. Metóda, ktorá by sa dala použiť je práve práca s časom, kde sa hodnota uloží lokálne a rozpošle ostatným aktívnym snodom. V prípade ak by nastalo v rovnakom okamihu viac rovnakých autentifikácií na rozdielnych nodoch, bude platiť tá s menším časom a ostatné prepíše.

Pravdepodobne to spravím tým druhým spôsobom.