\chapter{Bezkonfliktné replikovateľné dátové typy}

\label{kap:cdrt} % id kapitoly pre prikaz ref

\section{Úvod}

Súbežné úpravy dokumentu bez koordinácie medzi jednotlivými používateľskými počítačmi môžu viesť k
nekonzistentnostiam, ktoré vo všeobecnosti nie je možné vyriešiť. Na zabezpečenie konzistentnosti sa
v takýchto prípadoch vyžaduje vrátenie \textit{(angl. rollback)} niektorých operácií.

V distribuovanom výpočte je bezkonfliktný replikovaný dátový typ (CRDT) dátová štruktúra,
ktorá môže byť replikovaná vo viacerých počítačoch v sieti. Jednotlivé inštancie je možné
aktualizovať nezávisle a súbežne bez koordinácie medzi ostatnými inštanciami, pričom je vždy
matematicky možné vyriešiť nezrovnalosti, ktoré by mohli nastať. Z toho vyplýva, že použitím typu
CRDT nemôže nastať situácia, kedy by sme museli nejakú operáciu vrátiť. 

Koncept CRDT formálne definovali v roku 2011 osoby
Marc Shapiro, Nuno Preguiça, Carlos Baquero a Marek Zawirski \cite{crdt_definition}.
Ide teda o celkom nový koncept, ktorý rýchlo našiel v informatike podporu.

\section{Typy CRDT}
V súčasnosti sú preskúmané 2 typy CRDT:
\begin{enumerate}
  \item CRDT založené na operáciách
  \item CRDT založené na stavoch
\end{enumerate}

\subsection{CRDT založené na operáciách}
CRDT založené na operáciách sú označované ako komutatívne replikované dátové typy alebo 
\textit{CmRDT}. CmRDT menia dokument vysielaním iba operácií aplikovaných lokálne
u všetkých používateľov, ktorí dokument zdieľajú. Operácie musia byť komutatívne, avšak nemusia 
byť idempotentné. Je preto nutné zaručiť idempotenciu pomocou vhodnej implementácie
komunikácie (správa musí byť vyslaná práve raz). 
CmRDT je vhodné použiť napríklad na aktualizovanie počtu zdieľaní
príspevkov na sociálnych sieťach, kde server zaručuje idempotentnosť. 

\subsection{CRDT založené na stavoch}
CRDT založené na stavoch sa nazývajú konvergentné replikované dátové typy alebo \textit{CvRDT}.
Na rozdiel od CmRDT posielajú celý svoj stav, kde stavy sa potom zlučujú funkciou,
ktorá musí byť komutatívna, asociatívna a idempotentná.

Posielanie celého stavu nie je vždy optimálne. Častokrát stačí posielať zmeny, ktoré sa na dokumente
uskutočňujú. Takéto CRDT označujeme ako \textit{Delta CRDTs}

\section{Princíp fungovania CRDT}
CRDT funguje tak, že každý znak v dokumente sa prerobí do objektu so špecifickými vlastnosťami:
\begin{enumerate}
  \label{def_pozicie}
  % TODO: change 'znak' to 'atom'
  \item znak, ktorý objekt predstavuje
  \item relatívna pozícia tohto znaku
  \item množina pozícií musí tvoriť úplné usporiadanie
  \item priestor tvorený množinou pozícií musí byť hustý
\end{enumerate}
Vzhľadom na to, že každý z týchto objektov je jedinečný a môže byť identifikovaný
týmito vlastnosťami, môžeme zabrániť vloženiu alebo vymazaniu znakov viac ako raz.
To umožňuje komutativitu a idempotenciu. Nevýhodou tohto prístupu je veľké množstvo metaúdajov.
Tým sa zvyšuje spotreba pamäte aplikácie.

Zaujímavým aspektom CRDT, ktorý ho odlišuje od OT, sú relatívne pozície znakov. Tieto pozície majú
nasledovné vlastnosti:
\begin{enumerate}
  \item žiadne dva CRDT objekty nemajú rovnakú pozíciu
  \item pozícia nejakého objektu sa nikdy nezmení
  \item ak dva CRDT objekty A a B operujú na tej istej pozícii v dokumente a objekt A
  nastane skôr než B, tak relatívna pozícia A musí byť menšia ako B.
\end{enumerate}
Vytvorenie takýchto pozícií je celkom jednoduché.
Znaky si môžeme predstaviť ako vrcholy na strome, kde každý znak má väčsie číslo ako znak pred
ním, no menšie ako znak po ňom. Pozície môžu vyzerať zhruba nasledovne:

\begin{figure}[H]
\centerline{\includegraphics[width=0.6\textwidth]{images/relativne_pozicie1}}
\caption[Relatívne pozície znakov]{Relatívne pozície znakov}
\label{obr:relativne}
\end{figure}

Pridanie znaku potom funguje veľmi jednoducho. Nájdeme v strome vrcholy, medzi ktoré
chceme pridať ďalší znak a ako pozíciu mu dáme priemer relatívnych pozícií daných
vrcholov. Napríklad:
\begin{figure}[H]
\centerline{\includegraphics[width=0.6\textwidth]{images/relativne_pozicie2}}
\caption[Pridanie relatívnej pozície znakov]{Pridanie relatívnej pozície znakov}
\label{obr:relativne_pridanie}
\end{figure}

\begin{flushleft}\textbf {Komutativita a idempotentnosť CRDT}\end{flushleft}
Ak predpokladáme, že pozície spĺňajú podmienky z \ref{def_pozicie}, tak CRDT objekty sú
komutatívne a idempotentné.

Idempotencia je daná tým, že ak chceme do dokumentu pridať znak s nejakou relatívnou pozíciou, a tá
sa tam už nachádza, tak opätovné pridanie už nič neurobí. Ak sa naopak snažíme vymazať niečo na
pozícii, ktorá sa v dokumente už nenachádza, tak vieme, že uz vymazaná bola. Obe operácie teda
zachovávajú idempotentnosť.
\cite{nuno_preguica}

\section{Použitie v praxi}
Aplikácie CRDT sa dajú nájsť nielen v oblasti kolaboratívnych editorov, ale na mnohých ďalších
miestach ako napríklad databáza \textit{Redis}, platforma na zdieľanie hudby \textit{SoundClound}
alebo NoSQL 
dátové úložisko \textit{Riak}, ktoré sa používa na vnútorný četovací systém v hre 
\textit{League of Legends}.

% TODO: obrazky
