Conflict Resolution: stratégiák, összevonás és működési elv

Mi az ütközésfeloldás mobilalkalmazásokban?

Ütközésfeloldás az elosztott adatok egységes konzisztens állapotba hozásának folyamata az ellentmondó változtatások észlelése után. Központosított rendszerekben nem fordulnak elő ütközések: a szerver szekvenciálisan dolgozza fel a kéréseket. Offline móddal rendelkező mobilalkalmazásokban a kliens helyben módosítja az adatokat, és később szinkronizál a szerverrel. Ha két kliens módosította ugyanazt az objektumot, a szerver két verziót kap azonos azonosítóval, de eltérő tartalommal.

Az ütközések elkerülhetetlenek a lazán kapcsolt replikációban (eventual consistency), amikor a rendszer az azonnali konzisztenciát áldozza fel a rendelkezésre állás és teljesítmény érdekében. A Princeton University kutatói (Aggarwal et al., GEO paper, KDD 2024) szerint a késleltetett replikációs rendszerek 28%-kal nagyobb teljesítményt mutatnak csüsterhelésnél, de a helyes működéshez ütközésfeloldó mechanizmusokra van szükségük.

A feloldási stratégia egy algoritmus, amelyet a rendszer automatikusan alkalmaz ütközés észlelésekor. Különböző adatbázisok és keretrendszerek eltérő stratégiákat valósítanak meg: a Firebase Realtime Database LWW-t használ, a CouchDB Merge támogatást ad hozzá, a Figma és a Notion pedig CRDT-re építi az architektúrát.

Miért keletkeznek ütközések adatszinkronizációnál

Az ütközések fő oka ugyanazon erőforrás egyidejű módosítása két vagy több kliens által, akik az adatok helyi másolatával dolgoznak. Tipikus forgatókönyv: A felhasználó offline szerkeszt egy feladatot a Trello-ban, miközben B felhasználó módosítja ugyanazon feladat leírását egy másik eszközön. Mindketten helyben mentik a verzióikat. Amikor az eszközök csatlakoznak a hálózathoz, a szerver két különböző értéket kap ugyanarra a mezőre.

További tényezők a hálózati késleltetések és a hálózat felosztása (network partition). A Raft vagy Paxos protokollt használó elosztott adatbázisokban ütközés akkor keletkezhet, amikor a fürt vezetője átmenetileg nem érhető el, és a kéréseket különböző csomópontok dolgozzák fel. Az Amazon DynamoDB whitepaper (2025) szerint a skálázható NoSQL rendszerekben az összes írási művelet kb. 0,3%-a vezet észlelhető ütközésekhez.

Ütközések a helytelen adatszerkezetből is származhatnak. Ha az alkalmazás egy műveletszámlálót vagy résztvevői listát tárol, két offline kliens olyan műveleteket végezhet, amelyek szekvenciálisan nem kompatibilisek. Például, A kliens hozzáad egy elemet a lista végéhez, míg B kliens töröl egy elemet a közepéből — szinkronizáláskor a szerver nem tudja, melyik műveletet alkalmazza először.

Last Write Wins — az idő szerinti győztes stratégia

Last Write Wins (LWW) — stratégia, amelyben a versengő verziók közül a legkésőbbi időbélyeggel rendelkező rekord kerül kiválasztásra. A rendszer összehasonlítja az egyes verziók timestamp-jét, és elfogadja az újabbat, elvetve a régit. Ez egy determinisztikus mechanizmus: azonos bélyegkészlettel az eredmény mindig ugyanaz, ami kiköszöböli a bizonytalanságot. Az LWW a Firebase Realtime Database-ben, az Apache Cassandra-ban és a Riak KV-ban van megvalósítva.

Mobilalkalmazásokban az LWW különösen vonzó a megvalósítás egyszerűsége miatt. A kliensnek nem kell elemeznie a verziók közötti különbséget, tárolnia a változtatások előzményeit, vagy választó párbeszédet megjelenítenie a felhasználónak. A szerver ezredmásodpercek alatt dönt. Az LWW-nek azonban van egy alapvető hátránya — adatvesztés. Ha két felhasználó egyidejűleg tölti ki egy űrlap különböző mezőit, az egyikük verziója teljesen elvetésre kerül.

Példa az LWW működésére egy REST API-n keresztül szinkronizáló mobil jegyzetalkalmazásban:

data class Note(
    val id: String,
    val title: String,
    val content: String,
    val updatedAt: Long
)

fun resolveWithLWW(
    local: Note,
    remote: Note
): Note {
    return if (local.updatedAt >= remote.updatedAt) local
    else remote
}

A resolveWithLWW függvény összehasonlítja az időbélyegeket és visszaadja az aktuális verziót. Azonos timestamp esetén (ami magas írási gyakoriságnál fordul elő) általában a helyi verzió győz.

Merge Strategy — ütköző verziók összevonása

Merge Strategy — megközelítés, amelyben a rendszer nem dobja el az egyik verziót teljesen, hanem megpróbálja egyesíteni a változtatásokat mindkettőből egy konzisztens állapotba. Ez analóg a Git-ben az ágak összevonásával: minden ütközés az egyes mezők vagy műveletek szintjén oldódik fel. A Merge stratégiák automatikus (CRDT, OT) és kézi (a felhasználó választ változatot) csoportokra oszthatók.

A legismertebb megvalósítás a háromirányú összevonás (three-way merge). A rendszer három verziót tárol: helyit, távolit és közös ősüket (az alapverziót a szétválás előtt). Ha egy mezőt csak az egyik kliens módosított, a változtatás automatikusan elfogadásra kerül. Ha mindkét kliens módosította ugyanazt a mezőt — ütközés kerül rögzítésre, amely feloldást igényel. A CouchDB és a PouchDB aktívan használja ezt a modellt dokumentumok szinkronizálására.

Példa a háromirányú összevonás megvalósítására felhasználói profilhoz:

data class Profile(
    val name: String,
    val email: String,
    val avatarUrl: String
)

fun threeWayMerge(
    base: Profile,
    local: Profile,
    remote: Profile
): Profile {
    return Profile(
        name = if (local.name != base.name) local.name
                else remote.name,
        email = if (local.email != base.email) local.email
                else remote.email,
        avatarUrl = if (remote.avatarUrl != base.avatarUrl) remote.avatarUrl
                    else local.avatarUrl
    )
}

Háromirányú összevonás akkor hatékony, ha az adatszerkezet kellően stabil. Problémák merülnek fel mezők átnevezésekor, típusok változtatásakor és tömbökkel végzett műveleteknél — ezekben az esetekben összetettebb logikára van szükség.

CRDT — ütközésmentes adatszerkezetek

CRDT (Conflict-Free Replicated Data Type) — matematikai modell, amely garantálja az adatok konvergenciáját központi koordinátor nélkül. A CRDT-k úgy vannak tervezve, hogy minden művelet kommutatív: az alkalmazás sorrendje nem befolyásolja a végeredményt. Ez algebrai tulajdonságok révén érhető el: a CRDT-k összevonása mindig ugyanazt az eredményt adja, függetlenül a változtatások fogadásának sorrendjétől.

A fő CRDT típusok közé tartozik a G-Counter (csak növelést támogató számláló), a PN-Counter (növeléssel és csökkentéssel rendelkező számláló), az LWW-Register (verziókezeléssel ellátott regiszter) és az OR-Set (hozzáadást és eltávolítást nyomon követő halmaz). Minden típus garantálja, hogy két replika összevonásakor nem keletkeznek ütközések. Az INRIA kutatása (Marc Shapiro et al., 2024) szerint a CRDT-k a gyakori adattípusok 95%-ához biztosítanak determinisztikus konvergenciát.

Példa G-Counter-re — egy számlálóra, amelyet csak növelni lehet:

class GCounter {
    private val counts = mutableMapOf<String, Int>()

    fun increment(nodeId: String) {
        counts[nodeId] = (counts[nodeId] ?: 0) + 1
    }

    fun value(): Int = counts.values.sum()

    fun merge(other: GCounter) {
        other.counts.forEach { (node, count) ->
            counts[node] = maxOf(counts[node] ?: 0, count)
        }
    }
}

GCounter garantálja az összevonás helyességét, mert minden csomópont csak a saját számlálóját tárolja, és a merge a maximumot veszi minden csomóponthoz. Ez egy klasszikus példa az ütközésmentes szerkezetre, amelyet decentralizált rendszerekben használnak.

Hogyan válasszunk ütközésfeloldási stratégiát

Stratégia választása az adatok jellegétől és a használati forgatókönyvektől függ. Az LWW olyan alkalmazásokhoz optimális, ahol a legújabb verziónak mindig prioritása van — hírfolyam, értesítések, állapotok. A Merge Strategy strukturált dokumentumokhoz alkalmas, ahol minden mező független — felhasználói profilok, űrlapok, konfigurációk. A CRDT ideális közös szerkesztéshez, listákhoz és számlálókhoz elosztott rendszerekben.

A stratégia választásakor három tényezőt értékelnek: adatkonzisztencia, teljesítmény és megvalósítási összetettség. Az LWW maximális teljesítményt és minimális összetettséget nyújt, de adatvesztéshez vezethet. A Merge magas pontosságot biztosít, de mechanizmust igényel a változtatások mezőszintű észleléséhez. A CRDT matematikai helyességet garantál, de korlátozásokat állít az adattípusokra és a metaadatok méretére.

A gyakorlatban gyakran kombinált megközelítést alkalmaznak: a rendszerek LWW-t használnak metaadatokhoz, Merge-t a dokumentumok tartalmához és CRDT-t a listaszerkezetekhez. A Firebase Firestore például LWW-t alkalmaz a legfelső szintű mezőkhöz, és tranzakciókat támogat atomi frissítésekhez. A CouchDB Merge-t használ a változtatások előzményeinek tárolásával. A Figma és a Notion CRDT-alapú architektúrát épít többfelhasználós valós idejű szerkesztéshez.