Бесконфликтни копирајући тип података

У дистрибуираном рачунарству, неконфликтно копирајући тип података је врста специјално дизајнираних структура података које се користе за постизање јаке евентуалне конзистенције (стронг евентуал цонсистенцy - СЕЦ) и монотоније. Постоје два алтернативна начина обезбеђивања СЕЦ-а: рад заснован на ЦРДТ-овима и стање засновано на ЦРДТ-у. Ове две алтернативе су еквивалентне, тако што један може симулирати други, али радно-заснован ЦРДТ захтева додатне гаранције од посредничке комуникације.

ЦРДТ-ови се користе да умноже податке на више рачунара у мрежи, изврше ажурирања без потребе за даљинском синхронизацијом. То доводи до спајања сукоба у системима који користе СЕЦ технологију, али ЦРДТ-ови су дизајнирани тако да су сукоби математички немогући. Према ограничењима ЦАП теореме која пружа најјачу конзистентност гаранције за партитивно расположива подешавања. Насупрот томе, консензус протоколи као што је Паxос су потребни за партитивно конзистентна подешавања.

Концепт ЦРДТ је први пут формално дефинисан 2007. године од стране Марц Схапиро и Нуно Прегуиçа. Развој је првобитно мотивисан уређивањем текста. Концепт еволуције реплицирања стања дефинисан је од стране Баqуеро и Моура 1997. и првобитно је мотивисан мобилним рачунарством. Ова два концепта су спојена 2011.

Преглед

Евентуална конзистентност

Неформално, евентуална конзистентност значи да реплике на крају достижу исту вредност, ако клијенти зауставе подношење исправке. Евентуално конзистентни системи прихватају локалне исправке без даљинске синхронизације, побољшавајући перформансе и скалабилност преко јаке конзистенције. Без даљинске синхронизације, реплике истовремено имају различите вредности за које се очекује да се приближе током времена. Приближавање је закомпликовано сукобима који се јављају спајањем вредности између реплика. Сукоб је комбинација истовремених ажурирања која могу бити појединачно тачна, али заједно угрожавају инваријанту система.

Јака евентуална конзистентност

Јака евентуална конзистентност је својина неких евентуално козистентних система: реплике на које су примењена иста ажурирања имају еквивалентна стања. Не постоји конфликт арбитраже процеса, јер конфликти не постоје у јако конзистентним системима. ЦРДТ се користи за постизање јаке евентуалне конзистенције у дистрибуираном систему.

Математичка својства

Ако стање система монотоно расте, клијенти никада не посматрају повратну вредност. Скуп системских стања је делимично наређен, и операција спајања може бити комутативна, асоцијативна и идемпотентна.

ЦРДТ класе

Познато је да постоје две класе ЦРДТ-ова. Иако било који ЦРДТ једне класе има еквивалента друге класе, класе се разликују у претпоставкама и карактеристикама перформанси.

Радно заснован ЦРДТ

Радно заснован ЦРДТ је скраћеница за комутативне реплициране врсте података, или ЦмРДТ. ЦмРДТ реплике пропагирају стање емитовањем стања ажурирања саме операције, која мора бити комутативна. На пример, ЦмРДТ од једног интегер-а може да емитује операције (+10) или (-20). Реплике примају ажурирања и примењују их на локалном нивоу. Операције су комутативне, тако да могу бити примљене и примењене било којим редом, међутим, оне нису идемпотентне, а додатне гаранције мрежног протокола су дужне да обезбеде јединствену испоруку.

ЦРДТ заснован на стању

ЦРДТ заснован на стању је конвергентни реплицирани тип података, или ЦвРДТ. За разлику од ЦмРДТ, ЦвРДТ шаље своје целокупно локално стање другим репликама. ЦвРДТ има следећи локални интерфејс:

• Упит - чита стање реплика без нежељених ефеката
• Ажурирање - уписује на стање реплике у складу са одређеним ограничењима
• Спајање - спаја локално стање са стањем неке реплике

Функција спајања мора бити комутативна, асоцијативна и идемпотентна. Она обезбеђује спајање стања неког пара реплика, тако да скуп свих стања формира полурешетку. Унутрашње стање функције ажурирања мора монотоно да расте.

Поређење

Док ЦмРДТ захтева додатне гаранције од протокола мреже, користи мањи пропусни опсег него ЦвРДТ када је број трансакција мали у односу на величину унутрашњег стања. Међутим, пошто је функција спајања ЦвРДТ асоцијативна, спајањем са стањем неке реплике даје сва претходна ажурирања за ту реплику. "Госсип" протоколи добро раде за пропагирање ЦвРДТ стања са другим репликама док смањују употребу мреже и манипулишу топологијом промена.

Познати ЦРДТ-ови

Инкрементирајући бројач заснован на стању

   payload integer[n] P
     initial [0,0,...,0]
   update increment()
     let g = myId()
     P[g] := P[g] + 1
   query value() : integer v
     let v = \sum\nolimits_{i} P[i]
   compare (X, Y) : boolean b
     let b = (\forall i \in [0, n - 1] : X.P[i] \leq Y.P[i])
   merge (X, Y) : payload Z
     let \forall i \in [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])

Овај ЦвРДТ имплементира бројач за скуп од н чворова. Сваком чвору у том скупу је придружен ИД од 0 до н-1, који је добијен позивом функције мyИд(). Тако је сваком чвору додељен индекс у низу П, који се локално инкрементира. Ажурирања се извршавају у позадини, и спајана коришћењем функције маx() сваког елемента из П. Функција поређења је комутативна, асоцијативна и идемпотентна. Унутрашње стање функције ажурирања монотоно расте у односу на функцију поређења. На овај начин ЦвРДТ је испавно дефинисан и обезбеђује јаку евентуалну конзистентност.

ПН-бројач заснован на стању

   payload integer[n] P, integer[n] N
     initial [0,0,...,0], [0,0,...,0]
   update increment()
     let g = myId()
     P[g] := P[g] + 1
   update decrement()
     let g = myId()
     N[g] := N[g] + 1
   query value() : integer v
     let v = \sum\nolimits_{i} P[i] - \sum\nolimits_{i} N[i]
   compare (X, Y) : boolean b
     let b = (\forall i \in [0, n - 1] : X.P[i] \leq Y.P[i] \and \forall i \in [0, n - 1] : X.N[i] \leq Y.N[i])
   merge (X, Y) : payload Z
     let \forall i \in [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])
     let \forall i \in [0, n - 1] : Z.N[i] = max(X.N[i], Y.N[i])

Стратегија у развоју ЦРДТ-а је да се придружи више примитивних ЦРДТ-ова да би се направио сложенији ЦРДТ. У овом случају, два инкрементирајућа бројача су комбинована да направе ЦвРДТ подржавајући операције инкрементирања и декрементирања. Треба имати на уму да унутрашње стање ЦвРДТ-а мора монотоно да расте, иако је његово спољашње стање изложено упиту повратка претходне вредности.

Растуће поставке засноване на стању

   payload set A
     initial \emptyset
   update add(element e)
     A := A \cup {e}
   query lookup(element e) : boolean b
     let b = (e \in A)
   compare (S, T) : boolean b
     let b = (S.A \subseteq T.A)
   merge (S, T) : payload U
     let U.A = S.A \cup T.A

Растуће поставке су поставке које омогућавају само додавање, које имплементира ЦвРДТ. Све док је немогућа комутација додавања и уклањања (једна мора имати предност у односу на другу), било који ЦвРДТ који подржава операције додавања и уклањања мора да изабере своју семантику.

2П поставке засноване на стању

   payload set A, set R
     initial \emptyset, \emptyset
   query lookup(element e) : boolean b
     let b = (e \in A \and e \notin R)
   update add(element e)
     A := A \cup {e}
   update remove(element e)
     pre lookup(e)
     R := R \cup {e}
   compare (S, T) : boolean b
     let b = (S.A \subseteq T.A \or S.R \subseteq T.R)
   merge (S, T) : payload U
     let U.A = S.A \cup T.A
     let U.R = S.R \cup T.R

Две растуће поставке ЦвРДТ-а се комбинују и стварају 2П поставку ЦвРДТ-а. Са додатком поставке "томбстоне", елементи могу да се додају и уклањају. Једном уклоњен, елемент не може поново да се дода, тј. за тај елемент(е) истинитосна вредност више никада неће бити ТРУЕ. 2П поставка користи "ремове-wинс" семантику, што значи да функција ремове(е) има предност у односу на адд(е).

Употреба у индустрији

Подршка за ЦРДТ се спроводи у компанији РИАК. Леагуе оф Легендс користи РИАК ЦРДТ имплементацију за свој цхат систем унутар игре који барата са 7.5 милиона истовремених корисника и 11.000 порука у секунди.