Property-Based Testing za CRDT Action Registere bez Raft lidera

Raft vam daje linearnost, ali po cijeni vođe (leader). Za rojeve agenata, CRDT-ovi (Conflict-free Replicated Data Types) nude alternativu—ako možete dokazati da stvarno konvergiraju. Ovdje donosimo metodologiju testiranja temeljenog na svojstvima (property-based testing) koja hvata bugove koje Jepsen propušta.

Zašto CRDT-ovi, a ne Raft?

U distribuiranim sustavima, Raft osigurava linearnost, ali zahtijeva izbor vođe i sinkronizaciju. Za rojeve agenata (agent swarms) koji rade asinkrono, to može biti usko grlo. CRDT-ovi omogućuju replikaciju bez centralnog autoriteta, ali njihova konvergencija nije uvijek očigledna. Ključno je osigurati da sve replike na kraju imaju isto stanje, čak i uz mrežne kvarove i poruke koje stižu izvan reda.

Što je action register?

Action register je struktura podataka koja bilježi radnje (actions) agenata. Svaka radnja ima jedinstveni identifikator, vremensku oznaku i podatke. Cilj je da sve replike, nakon primitka svih radnji, imaju identičan skup radnji, bez obzira na redoslijed primitka. To je temelj za koordinaciju u rojevima agenata.

Metodologija property-based testinga

Umjesto da pišemo pojedinačne test slučajeve, definiramo svojstva (properties) koja sustav mora zadovoljiti. Zatim generator nasumičnih operacija (npr. dodavanje, brisanje, ažuriranje) stvara sekvence radnji koje se izvode na više replika. Na kraju provjeravamo da su sve replike konvergirale. Ovo je posebno učinkovito za CRDT-ove jer otkriva rubne slučajeve koje ručno testiranje propušta.

Ključna svojstva za verifikaciju

• Konvergencija: Nakon što sve replike prime sve radnje, njihova stanja moraju biti identična.
• Komutativnost: Redoslijed izvršavanja radnji ne smije utjecati na konačno stanje.
• Idempotencija: Ponavljanje iste radnje ne smije promijeniti stanje.
• Asocijativnost: Grupiranje radnji ne smije utjecati na rezultat.

Ova svojstva osiguravaju da CRDT ispravno funkcionira u mrežnim uvjetima s kašnjenjima i ponavljanjima.

Primjer: testiranje action registra

Pretpostavimo da imamo action register koji podržava operacije add(action) i remove(action_id). Property-based test bi generirao nasumične sekvence ovih operacija, replicirao ih na više čvorova s različitim redoslijedom primitka, te na kraju provjerio da su svi skupovi radnji jednaki. Ovaj pristup može otkriti bugove poput gubitka radnji ili nekonzistentnog brisanja.

Zašto Jepsen nije dovoljan?

Jepsen je izvrstan za testiranje linearnosti i mrežnih particija, ali se fokusira na specifične scenarije. Property-based testing ide korak dalje: generira tisuće nasumičnih scenarija, uključujući one koje Jepsen ne pokriva. Na taj način povećava povjerenje u ispravnost CRDT implementacije.

Zaključak

Property-based testing je moćan alat za verifikaciju CRDT-ova bez Raft lidera. Definirajući ključna svojstva i koristeći nasumične generatore, možemo uhvatiti bugove koji bi inače ostali skriveni. Ova metodologija omogućuje pouzdanu konvergenciju u distribuiranim sustavima, što je ključno za skalabilne rojeve agenata.