(toiminnot)

hwechtla-tl: Eventual consistency -synkkausalgoritmit: viime muutokset

(nettipäiväkirja 11.01.2016) Äärimmäisen mielenkiintoista! Vaikuttaa siltä, että OT:n (https://en.wikipedia.org/wiki/Operational_transformation) ja CRDT:n (https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type) suhdetta ei täysin ymmärretä. Jossain yleisemmässä mielessä nämä vastaavat [versionhallinta]tapojen kahta päähaaraa: sitä, jossa yhdistely ([merge, revision control]) tehdään kommutoimalla muutoksia, ja sitä, jossa tietorakenteiden oikea tila päätellään vanhojen tilojen DAG:sta.

Ensimmäistä lähestymistapaa edustaa versionhallinnassa puhtaimmillaan [darcs] ja vähän sovelletummassa muodossa [git]:n rebase-toiminnallisuus, jälkemmäistä taas melkein kaikki muut joilla edes on konvergenssi. Mutta versionhallintajärjestelmät joutuvat huolehtimaan konflikteista, kun taas replikoiduissa tietotyypeissä konfliktit estetään arbitraatiolla (OT:n tapauksessa) tai tekemällä ne mahdottomiksi (ainakin CRDT:issa, mutta ehkä tämä on mahdollista myös OT:ssa). Erityisesti treedoc (https://hal.inria.fr/file/index/docid/445975/filename/icdcs09-treedoc.p df) näyttää minusta kovasti weave merge -algoritmilta, joka on eksplisiittisesti tehty konfliktittomaksi disambiguaattoreilla.

(Jessus muuten mitä suomea?! Olisiko vaikka näin: treedoc vaikuttaa kudeyhdistelyalgoritmilta, joka on erikseen varmennettu yksiselitteistäjillä sellaiseksi, ettei ristiriitatilanteita voi syntyä.)

Katso huviksesi myös: http://stackoverflow.com/questions/26694359/differences-between-ot-and-c rdt

Sitten on vielä ''differential synchronisation'' (ks. esim. https://neil.fraser.name/writing/sync/), joka muistuttaa (jos oikein ymmärrän) symmetristä versiota siitä algoritmista, joka on mielestäni [parempi tapa synkronoida tietoja laitteiden välillä]. Diffsync on siinä mielessä "erilainen", että se ei salli todellista hajautusta vaan riippuu siitä, että on yksi palvelin, jolla on sekä totuus tietorakenteesta että todenmukainen näkemys kaikkien clientien viime käsityksestä palvelimen tilasta.

Prominenteimmat toteutukset näistä kaikista ovat (tietenkin!) Javascriptiä. * https://github.com/share/sharejs * https://github.com/gritzko/swarm * https://github.com/benjamine/dialogo

----

* [merkintä: 2016-01] * [atehwa] * [kategoria: päiväkirjamerkintä] * [algoritmi] * [muutosten merge]


(viimeksi muutettu 11.01.2016 11:59)