Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Vícebodová synchronizace dat protokolem WebDAV

Za´padoˇceska´ univerzita v Plzni Fakulta aplikovanyćh vˇed Katedra informatiky a vy´poˇcetn´ı techniky

Diplomov´ a pr´ ace V´ıcebodov´ a synchronizace dat protokolem WebDAV

Plzeˇ n 2012

Jiˇr´ı Praus

Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem diplomovou práci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 13. kvˇetna 2012 Jiˇr´ı Praus

Multipoint synchronization using WebDAV protocol Abstract The goal of this thesis is to verify whether the WebDAV communication protocol and its implementation by Kerio Connect email server is a suitable tool for data synchronization between more Kerio Connect servers in a distributed environment and to design fault-tolerant synchronization algorithm, which would use the WebDAV communication interface to transfer data between Kerio Connect servers. The work describes in detail the communication protocol WebDAV and various algorithms and technologies for maintaining data consistency in a distributed environment. Based on learned facts the algorithm is designed to efficiently synchronize data between servers in a distributed environment, deal with possible conflict situations and resolve possible error conditions. Behavior of the algorithm is extensively tested both in terms of functionality and reliability as well as performance and efficiency.

Obsah ´ 1 Uvod

6

2 Protokol HTTP a WebDav 2.1 HTTP . . . . . . . . . . . . . . . . . 2.1.1 Vybrané vlastnosti . . . . . . 2.1.2 D˚ uleˇzité metody . . . . . . . 2.1.3 Návratové kódy . . . . . . . . 2.2 Protokol WebDAV . . . . . . . . . . 2.2.1 Slovn´ık pojm˚ u. . . . . . . . . 2.2.2 Odpovˇed’ 207 Multi-Status . . 2.3 Exchange Store WebDAV . . . . . . 2.3.1 Metoda PROPFIND . . . . . 2.3.2 Metoda PROPPATCH . . . . 2.3.3 Metoda MKCOL . . . . . . . 2.3.4 Metoda SEARCH . . . . . . . 2.3.5 Metoda LOCK a UNLOCK . 2.3.6 Metoda SUBSCRIBE a POLL 2.4 D˚ uvody pro pouˇzit´ı WebDAV . . . . 3 Replikace 3.1 Konzistence . . . . . . . . . . 3.2 Pesimistická replikace . . . . . 3.3 Optimistická replikace . . . . 3.3.1 Single-master . . . . . 3.3.2 Multi-master . . . . . 3.4 Soubˇeˇznost operac´ı . . . . . . 3.4.1 Syntaktické plánovaˇce 3.4.2 Sémantické plánovaˇce . 3.5 Zpracován´ı konflikt˚ u . . . . . 3.6 Synchronizace replik . . . . . 3.6.1 Pomalá synchronizace 3.6.2 Zmˇenová synchronizace 3.6.3 Aktivn´ı synchronizace 3.7 Replikace a WebDAV . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

7 7 7 8 9 10 10 11 12 12 13 13 13 14 14 15

. . . . . . . . . . . . . .

16 16 16 17 17 17 18 18 19 21 22 22 22 24 24

OBSAH

OBSAH

4 N´ avrh modelu synchronizace 4.1 Poˇzadavky a pˇredpoklady . . . . 4.2 C´ıle synchronizace . . . . . . . . 4.3 Architektura . . . . . . . . . . . . 4.4 Konzistence . . . . . . . . . . . . 4.5 Pravdivostn´ı databáze . . . . . . 4.5.1 Lokace . . . . . . . . . . . 4.5.2 Objekt . . . . . . . . . . . 4.5.3 Kopie . . . . . . . . . . . 4.6 Synchronizace . . . . . . . . . . . 4.6.1 Synchronizace kolekce . . 4.6.2 Pomalá synchronizace . . 4.6.3 Zmˇenová synchronizace . . 4.6.4 Aktivn´ı synchronizace . . 4.7 Nedostupnost server˚ u . . . . . . . 4.8 Detekce zmˇen . . . . . . . . . . . 4.8.1 Nová kolekce . . . . . . . 4.8.2 Nov´ y dokument . . . . . . 4.8.3 Zmˇenˇená kolekce . . . . . 4.8.4 Zmˇenˇen´ y dokument . . . . 4.8.5 Smazan´ y zdroj . . . . . . 4.8.6 Detekce faleˇsn´ ych zmˇen . 4.9 Párován´ı zdroj˚ u . . . . . . . . . . 4.9.1 Konflikt tˇr´ıd kolekc´ı . . . 4.10 Poˇrad´ı operac´ı . . . . . . . . . . . 4.11 Aktualizace . . . . . . . . . . . . 4.11.1 Operace smazán´ı . . . . . 4.11.2 Aktualizace zdroje . . . . 4.11.3 Detekce konflikt˚ u . . . . . 4.11.4 Zpracován´ı konflikt˚ u . . . 4.12 Plánovaˇc . . . . . . . . . . . . . . 4.12.1 Heuristická synchronizace 4.12.2 Rychlost propagace zmˇen

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25 25 26 28 29 30 31 31 31 31 31 32 33 33 34 34 35 35 36 36 37 38 38 39 40 42 42 42 43 44 46 47 47

5 Implementace 5.1 Programové prostˇredky . . . 5.2 Knihovny . . . . . . . . . . 5.3 Architektura . . . . . . . . . 5.3.1 WebDAV klient . . . 5.3.2 Objektov´ y model . . 5.3.3 Reprezentace zdroj˚ u 5.3.4 Synchronizace . . . . 5.4 Testován´ı . . . . . . . . . . 5.5 Zátˇeˇzov´ y test . . . . . . . . 5.6 Urychlen´ı . . . . . . . . . . 5.7 Dlouhodob´ y test . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

48 48 48 50 50 51 51 52 53 54 55 57

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

4

OBSAH

OBSAH

6 Z´ avˇ er

59

A Uˇ zivatelsk´ a pˇ r´ıruˇ cka A.1 Instalace . . . . . . . A.1.1 UNIX/Linux A.1.2 Windows . . . A.1.3 MAC OS . . A.2 Nastaven´ı . . . . . . A.3 Spuˇstˇen´ı . . . . . . .

63 63 63 63 64 64 65

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

5

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

´ 1 Uvod V modern´ı dobˇe jsou pro nás data uloˇzená v poˇc´ıtaˇci to nejcennˇejˇs´ı, ˇc´ım náˇs poˇc´ıtaˇc disponuje, bez nich je poˇc´ıtaˇc bezcenn´ y. Svá data chceme ˇcasto sd´ılet s ostatn´ımi uˇzivateli a publikovat na veˇrejn´ ych prostorech. Emailov´ y server Kerio Connect od spoleˇcnosti Kerio Technologies s.r.o. tuto moˇznost nab´ız´ı a dovoluje uˇzivatel˚ um sd´ılet d˚ uleˇzitá data nebo události mezi sebou. Uˇzivatelé mohou takto sd´ılená data libovolnˇe upravovat a mˇenit. Problém ovˇsem nastává v distribuované doménˇe, kde jsou uˇzivatelé stejné domény distribuováni mezi v´ıce Kerio Connect server˚ u. Uˇzivatelé mohou veˇrejná data nadále sd´ılet mezi sebou, ale pouze v rámci jednoho serveru. Motivac´ı pro tuto práci je právˇe potˇreba sd´ılená data distribuovat mezi vˇsechny servery domény tak, aby kaˇzd´ y z uˇzivatel˚ u distribuované domény mohl pˇristupovat ke stejn´ ym veˇrejn´ ym dat˚ um na libovolném serveru. Ideáln´ım rozhran´ım pro takovou v´ ymˇenu dat mezi servery je pˇritom otestované a funkˇcn´ı komunikaˇcn´ı rozhran´ı WebDAV pouˇz´ıvané pro pˇripojen´ı Entourage emailového klienta ke Kerio Connect serveru. Distribuce dat s sebou ovˇsem pˇrináˇs´ı nemalé problémy. Data jsou replikována mezi servery a jsou uloˇzena ve v´ıcenásobn´ ych kopi´ıch. Uˇzivatelé mohou stejné soubory mˇenit na libovolném serveru a vyvolat t´ım nutnost pˇrenáˇset zmˇeny do ostatn´ıch kopi´ı tak, aby vˇsichni uˇzivatelé vidˇeli stejná data. Situace se dále komplikuje, pokud je zmˇena stejného souboru provedena na v´ıce serverech souˇcasnˇe. Vzniká tak konflikt, kter´ y je potˇreba uspokojivˇe vyˇreˇsit. Distribuované systémy dále trp´ı ˇcast´ ymi v´ ypadky a nestálost´ı s´ıtˇe, ˇc´ımˇz docház´ı k doˇcasné nedostupnosti jednotliv´ ych uzl˚ u systému. C´ılem práce je v´ yˇse zm´ınˇené problémy vyˇreˇsit v prostˇred´ı distribuované domény Kerio Connect server˚ u s pouˇzit´ım komunikaˇcn´ıho protokolu WebDAV. Druhá kapitola práce se podrobnˇe zab´ yvá ovˇeˇren´ım moˇznost´ı WebDAV komunikaˇcn´ıho rozhran´ı implementovaného v Kerio Connect serveru a jeho vhodnost´ı pro replikaci dat mezi servery. Ve tˇret´ı kapitole je pˇredstaven pojem replikace a detailnˇe popsány r˚ uzné zp˚ usoby udrˇzen´ı dat na v´ıce replikách v konzistentn´ım stavu. Z´ıskané poznatky jsou ve ˇctvrté kapitole vyuˇzity pro návrh vhodného synchronizaˇcn´ıho algoritmu, kter´ y bude spolehlivˇe udrˇzovat repliky v konzistentn´ım stavu a vhodnˇe ˇreˇsit vzniklé konflikty. Navrˇzen´ y algoritmus je v závˇereˇcné páté kapitole provˇeˇren jak z hlediska funkˇcnosti a spolehlivosti, tak i v´ ykonnosti a efektivity.

6

2 Protokol HTTP a WebDav HTTP (HyperText Transfer Protocol) je jednoduch´ y aplikaˇcn´ı protokol, kter´ y se dá vyuˇz´ıt nejen k pˇrenosu hypertextov´ ych dokument˚ u a obrázk˚ u, ale má i mnoho zaj´ımav´ ych rozˇs´ıˇren´ı a vlastnost´ı. A právˇe jeho v´ yznamné rozˇs´ıˇren´ı WebDAV, které umoˇzn ˇuje mimo klasického stahován´ı obsahu i jeho správu, je pouˇzito v této práci jako komunikaˇcn´ı prostˇredek pro pˇrenos dokument˚ u. V této kapitole budou uvedeny základy protokolu HTTP a d˚ uleˇzité vlastnosti WebDAV, které byly v dalˇs´ım textu práce pouˇzity.

2.1

HTTP

Hypertext Transfer Protokol pocház´ı z roku 1996 (respektive HTTP 1.1 z roku 1999) a byl pouˇz´ıván pro pˇrenos dat pˇres internet. V dneˇsn´ı dobˇe je pouˇz´ıván zejména pro WWW. HTTP je aplikaˇcn´ı protokol nad transportn´ım protokolem TCP a je zaloˇzen na principu poˇzadavek/odpovˇed’. Klient vˇzdy inicializuje spojen´ı odeslán´ım poˇzadavku a server mu patˇriˇcnˇe odpov´ı. Dotaz se vˇzdy skládá z poˇzadované metody, cesty k souboru (URL), verze protokolu a hlaviˇcek. V nˇekter´ ych pˇr´ıpadech následuje po hlaviˇckách i tˇelo dotazu oddˇelené jedn´ım prázdn´ ym ˇra´dkem. Vˇse je pˇrenáˇseno v textové podobˇe, je tedy moˇzné poˇzadavky jednoduˇse vytváˇret nebo ˇc´ıst: 1 GET / HTTP/1.1 2 Host: www.example.com

Server poˇzadavek vyˇr´ıd´ı a vrát´ı odpovˇed’, která m˚ uˇze vypadat napˇr´ıklad takto: 1 2 3 4 5 6 7 8

HTTP/1.1 200 OK Date: Sat, 10 Dec 2011 20:22:25 GMT Server: Apache Content−Length: 27072 Connection: Keep−Alive Content−Type: text/html;charset=UTF−8 ...

Odpovˇed’ obsahuje verzi protokolu, návratov´ y kód, hlaviˇcky a tˇelo odpovˇedi. Opˇet je veˇsker´ y pˇrenos provádˇen pouze v textové podobˇe. Jak je moˇzné z pˇredchoz´ıho pozorovat, protokol HTTP je velice jednoduch´ y a proto také velmi obl´ıben´ y a pouˇz´ıvan´ y. Dále se budeme zab´ yvat pouze nejnovˇejˇs´ı verz´ı protokolu HTTP 1.1.

2.1.1

Vybran´ e vlastnosti

Perzistentn´ı spojen´ı Server podporuj´ıc´ı protokol 1.0 po vrácen´ı odpovˇedi ihned naˇ vázané spojen´ı uzavˇre. Casto je toto protokolu vyˇc´ıtáno, protoˇze otevˇren´ı TCP spojen´ı pro kaˇzd´ y pár poˇzadavek/odpovˇed’ je pomˇernˇe drahé. Protokol 1.1 pˇricház´ı s perzistentn´ım spojen´ım, kdy server spojen´ı neuzavˇre ihned, ale ˇceká na dalˇs´ı poˇzadavky. Klient m˚ uˇze pokraˇcovat v dotazován´ı a spojen´ı ukonˇcit sám. 7

Protokol HTTP a WebDav

HTTP

Bezstavovost Poˇzaduje-li opakovanˇe klient stejná data, zaˇsle nov´ y poˇzadavek a server vygeneruje novou odpovˇed’. Pˇr´ıpadné uchován´ı nˇekter´ ych informac´ı o komunikaci mezi klientem a serverem je zcela v reˇzii klienta. Protokol si informace o jiˇz proveden´ ych spojen´ıch neudrˇzuje, je to protokol bezstavov´ y. MIME typ (form´ at) Pomoc´ı hlaviˇcky Accept m˚ uˇze klient poˇzadovat urˇcit´ y MIME typ. Takˇze pˇri poˇzadavku na stejné URL, ale s jinou hlaviˇckou m˚ uˇze dostat v pˇr´ıpadˇe Accept: text/plain stránku pˇrevedenou na prost´ y text, zat´ımco v pˇr´ıpadˇe Accept: application/xhtml+xml dostane hypertext. Stejnˇe tak pomoc´ı této hlaviˇcky m˚ uˇzeme vyjednat se serverem vhodn´ y formát napˇr´ıklad obrázk˚ u [RFC2616]. Bezpeˇ cnost Poˇzadavky i odpovˇedi jsou pˇrenáˇseny ˇcistˇe v textové podobˇe, coˇz m˚ uˇze znamenat znaˇcná bezpeˇcnostn´ı rizika, a proto je moˇzné pˇridat TLS vrstvu a vytvoˇrit tak zabezpeˇcen´ y protokol naz´ yvan´ y HTTPS [RFC2818].

2.1.2

D˚ uleˇ zit´ e metody

Pouˇzitou metodu HTTP protokolu specifikuje klient v poˇzadavku a oznamuje tak serveru, jakou operaci chce provést. S metodami jsou svázány hlaviˇcky a kaˇzdá metoda se m˚ uˇze chovat trochu jinak pˇri pouˇzit´ı rozd´ıln´ ych hlaviˇcek, podrobnosti je moˇzné nalézt v oficiáln´ı specifikaci [RFC1945]. Metoda GET pˇredstavuje poˇzadavek na zaslán´ı dokumentu urˇceného pomoc´ı URL, ˇcili napˇr´ıklad staˇzen´ı HTML stránky nebo obrázk˚ u z webového serveru. Metoda HEAD je shodná s metodou GET, ale v odpovˇedi serveru jsou uvedeny pouze hlaviˇcky vyˇza´daného dokumentu bez tˇela obsahuj´ıc´ı samotn´ y dokument. Tato metoda se pouˇz´ıvá pro zjiˇstˇen´ı existence dokumentu nebo jeho vlastnost´ı. Metoda POST se pouˇz´ıvá v pˇr´ıpadˇe, kdy má c´ılov´ y server pˇrijmout data z poˇzadavku. Skuteˇcná funkce metody závis´ı na implementaci a urˇcené URL. M˚ uˇze se jednat o zaslán´ı emailu, pˇredán´ı dat do procesu a podobnˇe. U klasick´ ych webov´ ych server˚ u se jedná pˇredevˇs´ım o odeslán´ı formuláˇre. Metoda PUT pˇredstavuje poˇzadavek na uloˇzen´ı pos´ılan´ ych dat pod specifikované URL na server. Takto uloˇzená data budou dostupná napˇr. následn´ ymi dotazy GET. Webové servery toto samozˇrejmˇe nepodporuj´ı, klient nemá moˇznost mˇenit obsah na vzdáleném serveru. Metoda DELETE je poˇzadavkem na zruˇsen´ı dokumentu na serveru. Ruˇsen´ y dokument je specifikován v URL. Stejnˇe jako u metody PUT ji klasické webové servery nepodporuj´ı.

8


2.1.3

HTTP

N´ avratov´ e k´ ody

Na kaˇzd´ y poˇzadavek server odpov´ı jednou odpovˇed´ı, tato odpovˇed’ vˇzdy obsahuje tˇr´ıcifern´ y návratov´ y kód vˇcetnˇe popisuj´ıc´ıho textu, kter´ y oznamuje stav poˇzadavku. Návratov´ y kód se dˇel´ı podle prvn´ı cifry na pˇet tˇr´ıd [RFC1945]: • 1 - informativn´ı Poˇzadavek byl v poˇra´dku obdrˇzen, ale nen´ı doposud kompletnˇe zpracován. • 2 - u ´ spˇ ech Dotaz byl serverem pochopen, akceptován a pˇr´ıpadná data jsou v odpovˇedi. Nejˇcastˇejˇs´ı odpovˇed´ı je známá 200 OK. • 3 - pˇ resmˇ erov´ an´ı Poˇzadovan´ y c´ıl existuje, ale byl pˇresunut, klient mus´ı provést dalˇs´ı akce pro jeho z´ıskán´ı (zaslat nov´ y poˇzadavek). Napˇr´ıklad známé pˇresmˇerován´ı 301 Moved Permanently. • 4 - chybn´ y poˇ zadavek Klient poloˇzil chybn´ y dotaz nebo nemá dostateˇcná oprávnˇen´ı z´ıskat poˇzadovan´ y c´ıl. Opˇet m˚ uˇzeme uvést pˇr´ıklad typické návratové hodnoty 404 Not Found. • 5 - chyba serveru Server nen´ı z nˇejakého d˚ uvodu schopen obslouˇzit poˇzadavek. ˇ Casto nepˇr´ıjemná odpovˇed’ 500 Internal Server Error.

9


2.2

Protokol WebDAV

Protokol WebDAV

Web Distributed Authoring and Versioning - WebDAV - je mnoˇzina rozˇs´ıˇren´ı HTTP protokolu, která poskytuje moˇznost vzdálené správy soubor˚ u, adresáˇr˚ u a vlastnost´ı na datovém serveru. Protokol tak ˇcin´ı ze vzdáleného serveru zapisovatelné médium. Vytváˇr´ı prostˇred´ı, ve kterém mohou klienti vytváˇret, mˇenit, pˇresouvat a mazat soubory a adresáˇre. Prostˇred´ı organizuje soubory do standardn´ı stromové adresáˇrové struktury [RFC2818] WebDAV spojuje dvˇe jiˇz propracované technologie HTTP a XML (Extensible Markup Language) [W3C]. Protokol HTTP je pouˇz´ıván pro zajiˇstˇen´ı zp˚ usobu komunikace. Kromˇe standardn´ıch metod vyuˇz´ıvan´ ych v rámci protokolu HTTP (GET, POST, PUT . . . ) zavád´ı WebDAV pro své potˇreby nové metody a hlaviˇcky. XML naopak WebDAV vyuˇz´ıvá jako nositele strukturovan´ ych informac´ı, které upˇresˇ nuj´ı jak dotaz klienta, tak i v´ ysledek zas´ılan´ y serverem. V XML ˇcásti komunikace jsou odes´ılány v´ ysledky zpracován´ı pˇr´ıkaz˚ u pro jednotlivé soubory, informace o souborech, adresáˇr´ıch a jiné. Nejlepˇs´ı bude ukázat WebDAV poˇzadavek a odpovˇed’ na jednoduché ukázce vytvoˇren´ı nové kolekce. Odpovˇ ed’

Poˇ zadavek 1 2 3 4 5 6 7 8 9 10 11 12

1 HTTP/1.1 201 Created

MKCOL /folder/ HTTP/1.1 Host: www.example.com Content−Type: text/xml

Folder

V podstatˇe se nejedná o nic nového, poˇzadavek je shodn´ y s poˇzadavkem v HTTP protokolu, s t´ım rozd´ılem, ˇze tˇelo obsahuje XML dokument s podrobnostmi o poˇzadavku, kter´ ym se v tomto pˇr´ıpadˇe nastav´ı vlastnost kolekce displayname na hodnotu Folder“. ”

2.2.1

Slovn´ık pojm˚ u

WebDAV protokol definuje nˇekolik nov´ ych pojm˚ u, které jsou v následuj´ıc´ım textu objasnˇeny, a tyto pojmy budou i v dalˇs´ım textu této práce pouˇzity. Zdroj - libovolná entita, se kterou je moˇzné pracovat. Je identifikován jedineˇcnou URL nebo URI adresou. Neformálnˇe ˇreˇceno se jedná o soubory, kolekce a vlastnosti (z angl. Resource [RFC4918]). Vlastnost - pár jméno/hodnota obsahuj´ıc´ı popisné informace o zdroji - typ zdroje, velikost, autor . . . (z angl. Property [RFC4918]).

10


Protokol WebDAV

Kolekce - zdroj, kter´ y se souˇcasnˇe chová jako kontejner referenc´ı na dalˇs´ı zdroje. V podstatˇe se jedná o analogii adresáˇre v klasickém souborovém systému. Kolekce sm´ı obsahovat vlastnosti a dalˇs´ı zdroje, at’ uˇz kolekce nebo dokumenty (z angl. Collection [RFC4918]). Dokument - zdroj, kter´ y nen´ı kolekc´ı. Dokumenty jsou analogi´ı soubor˚ u v klasickém souborovém systému (z angl. Document). Vnitˇ rn´ı ˇ clen kolekce - zdroj, kter´ y je pˇr´ım´ ym potomkem dané kolekce, ˇcili kolekce obsahuje referenci na tento zdroj (z angl. Internal Member of a Collection [RFC4918]). ˇ Clen kolekce - zdroj, kter´ y je potomek dané kolekce neboli je vnitˇrn´ı ˇclen dané kolekce nebo vnitˇrn´ı ˇclen libovolné vnoˇrené kolekce (z angl. Member of a Collection [RFC4918]). Aktivn´ı vlastnost - vlastnost, jej´ıˇz sémantika a syntaxe je vynucená serverem. Pˇr´ıkladem takové aktivn´ı vlastnosti m˚ uˇze b´ yt DAV:getcontentlength, jej´ıˇz hodnota, vrácená v poˇzadavku GET, je automaticky spoˇc´ıtána na stranˇe serveru z aktuáln´ıho stavu zdroje (z angl. Live Property [RFC4918]). Pasivn´ı vlastnost - vlastnost jej´ıˇz sémantika a syntaxe nen´ı vynucená serverem. Server pouze hodnotu ukládá a za u ´drˇzbu konzistence a správnosti sémantiky a syntaxe hodnoty je odpovˇedn´ y klient. Pˇr´ıkladem této vlastnosti m˚ uˇze b´ yt jméno autora zdroje (z angl. Dead Property [RFC4918]).

2.2.2

Odpovˇ ed’ 207 Multi-Status

WebDAV mimo klasick´ ych dotaz˚ u a odpovˇed´ı nad jedn´ım konkrétn´ım zdrojem, zavád´ı i hromadné (z angl. batch) operace, napˇr´ıklad pro smazán´ı nebo nastaven´ı vlastnost´ı zdroje. V tomto pˇr´ıpadˇe je ovˇsem nutné obdrˇzet od serveru odpovˇed’ se stavem pro kaˇzd´ y d´ılˇc´ı c´ıl hromadné akce. WebDAV proto zavád´ı odpovˇed’ 207 Multi-Status, ˇc´ımˇz oznamuje, ˇze stav proveden´ ych operac´ı je k nalezen´ı v XML tˇele odpovˇedi pro kaˇzd´ y jednotliv´ y zdroj samostatnˇe.

11


2.3

Exchange Store WebDAV


Celá specifikace protokolu WebDAV je k nalezen´ı v oficiáln´ım [RFC2818]. V této práci je ovˇsem nutné se zamˇeˇrit na specifickou ˇca´st celého dokumentu, kterou podporuje server Kerio Connect. Kerio Connect je emailov´ y server vyv´ıjen´ y spoleˇcnost´ı Kerio, kter´ y mimo jiné poskytuje i komunikaˇcn´ı rozhran´ı se sluˇzbami WebDAV [Connect]. Motivac´ı pro implementaci WebDAV komunikaˇcn´ıho rozhran´ı byla nutnost podporovat emailového klienta Entourage vyv´ıjeného spoleˇcnost´ı Microsoft pro operaˇcn´ı systém OS X. Microsoft Entourage byl souˇcást´ı bal´ıku Microsoft Office pro MAC a jednalo se o sourozence známého emailového klienta Microsoft Outlook. Tento klient umˇel komunikovat se serverem Microsoft Exchange a to právˇe pomoc´ı protokolu WebDAV. Jak jiˇz to ˇcasto b´ yvá a zvláˇstˇe u spoleˇcnosti Microsoft, komerˇcn´ı spoleˇcnost pˇrevezme oficiáln´ı specifikaci a uprav´ı ji podle sv´ ych konkrétn´ıch potˇreb a poˇzadavk˚ u. Tak tomu je i v pˇr´ıpadˇe implementace WebDAV produktem Microsoft Exchange. Spoleˇcnost Microsoft má svoji vlastn´ı oficiáln´ı specifikaci protokolu WebDAV, která p˚ uvodn´ı [RFC2818] rozˇsiˇruje o nové vlastnosti. Podstata protokolu z˚ ustává stále stejná, ale d´ıky drobn´ ym odliˇsnostem mus´ıme vycházet právˇe z této Microsoft Exchange specifikace [MSDN]. Do jisté m´ıry limituj´ıc´ım faktorem je to, ˇze celá implementace komunikaˇcn´ıho rozhran´ı WebDAV produktem Kerio Connect se omezuje pouze na potˇreby emailového klienta Microsoft Entourage, kter´ y vyuˇz´ıvá jen nˇekteré z moˇznost´ı WebDAV protokolu. Nebylo tud´ıˇz nutné implementovat celou specifikaci protokolu, ale pouze ty metody a vlastnosti, které emailov´ y klient opravdu pouˇz´ıvá. Komunikaˇcn´ı rozhran´ı se tedy omezuje jen na urˇcitou podmnoˇzinu a tato podmnoˇzina je v následuj´ıc´ıch ˇrádc´ıch uvedena. Vˇsechny tyto vlastnosti byly zjiˇstˇeny pˇr´ım´ ym testován´ım komunikaˇcn´ıho rozhran´ı produktu Kerio Connect.

2.3.1

Metoda PROPFIND

Pouˇz´ıvá se pro z´ıskán´ı vlastnost´ı zdroje specifikovaného podle URI. Vlastnosti, které chceme z´ıskat, m˚ uˇzeme uvést v XML tˇele poˇzadavku nebo uvést zástupnou vlastnost DAV:allprop, která donut´ı server v odpovˇedi vrátit veˇskeré dostupné vlastnosti. Server vrac´ı odpovˇed’ 207, která obsahuje ˇca´steˇcné odpovˇedi 200 pro vlastnosti existuj´ıc´ı a dostupné a 403 pro vlastnosti neexistuj´ıc´ı. Pouˇzit´ım hlaviˇcky Brief je moˇzné serveru ˇr´ıci, at’ neexistuj´ıc´ı vlastnosti vynechá a vrac´ı pouze existuj´ıc´ı. Nav´ıc existuje speciáln´ı vlastnost descriptor, která vrac´ı tzv. security descriptor neboli bezpeˇcnostn´ı popis zdroje. Tato vlastnost je specifická pro kolekce a obsahuje definici práv, kter´ ymi skupina uˇzivatel˚ u nebo uˇzivatel disponuj´ı vzhledem k c´ılové kolekci [MSDN]. Hlaviˇ cka Depth Uveden´ım hlaviˇcky Depth m˚ uˇzeme vyˇza´dat kromˇe vlastnost´ı zdroje uvedeného v URL i vlastnosti vˇsech jeho ˇclen˚ u (samozˇrejmˇe relevantn´ı pouze pro kolekce). Implicitn´ı hodnota hlaviˇcky Depth je 0“, coˇz je pouze dotazovan´ y zdroj. Explicitn´ım uveden´ım hodnoty 1“ ” ” z´ıskáme vlastnosti veˇsker´ ych vnitˇrn´ıch ˇclen˚ u kolekce a hodnotou infinity“ vlastnosti vˇsech ” ˇclen˚ u kolekce [MSDN].

12


2.3.2


Metoda PROPPATCH

Metoda PROPPATCH umoˇzn ˇuje nastavit nebo odstranit vlastnosti c´ılového zdroje specifikovaného podle URI. Vˇsechny vlastnosti jsou uvedeny v XML tˇele poˇzadavku a maj´ı pˇr´ıznak DAV:set pro nastaven´ı nebo DAV:remove pro odebrán´ı vlastnosti z mnoˇziny vlastnost´ı. Server stejnˇe jako v pˇr´ıpadˇe PROPFIND vrac´ı odpovˇed’ 207 s ˇca´steˇcn´ ymi odpovˇedi 200 pro vlastnosti u ´spˇeˇsnˇe nastavené a 403 pro vlastnosti nenastavené (vlastnost neexistuje nebo se jedná o aktivn´ı vlastnost).

2.3.3

Metoda MKCOL

Metoda MKCOL vytváˇr´ı novou kolekci um´ıstˇenou do stromové struktury podle URI poˇzadavku. Server vrac´ı odpovˇed’ 207 s ˇca´steˇcnou odpovˇed´ı 200 pro u ´spˇeˇsnˇe vytvoˇrenou kolekci a 403 pro kolekci, kterou se nepodaˇrilo vytvoˇrit. Cesta ke kaˇzdé kolekci, kterou chceme vytvoˇrit, mus´ı jiˇz existovat v dobˇe vytváˇren´ı. WebDAV cestu rekurzivnˇe nevytváˇr´ı. Pˇri vytváˇren´ı kolekce je vˇzdy nutné uvést tˇr´ıdu kolekce, která se má vytvoˇrit. Tˇr´ıda kolekce urˇcuje sémantiku, s jakou se má s kolekc´ı v prostˇred´ı e-mailového serveru a klienta pracovat. Urˇcuje napˇr´ıklad jej´ı vzhled a moˇzn´ y obsah. Kolekce se dˇel´ı celkem do pˇeti tˇr´ıd: • • • • •

IPF.Note sloˇzka e-mailov´ ych zpráv, IPF.Contact sloˇzka obsahuj´ıc´ı kontakty, IPF.Appointment kalendáˇr s událostmi, IPF.Task sloˇzka u ´kol˚ ua IPF.StickyNote sloˇzka poznámek.

2.3.4

Metoda SEARCH

SEARCH je v´ yznamnou metodou zavádˇej´ıc´ı moˇznost vyhledávat ve zdroj´ıch dotazovac´ım jazykem SQL. Je moˇzné tedy napˇr´ıklad vyhledat vˇsechny kolekce nebo vˇsechny zdroje urˇcitého typu nebo velikosti. Metoda umoˇzn ˇuje pouˇz´ıt 2 typy vyhledáván´ı: • Hierarchical stromové vyhledáván´ı hledá ve ˇclensk´ ych kolekc´ıch a • Shallow mˇelké vyhledáván´ı hledá ve vˇsech vnitˇrn´ıch ˇclenech kolekce. Kromˇe velice efektivn´ıho zp˚ usobu vyhledáván´ı, je moˇzné z´ıskat v odpovˇedi Manifest of a Collection, coˇz je seznam zmˇen v hledané kolekci [MSDN]. Kaˇzd´ y nalezen´ y zdroj je oznaˇcen jedn´ım ze tˇr´ı moˇzn´ ych stav˚ u: • new zdroj byl novˇe pˇridán, • change vlastnost nebo obsah zdroje byly zmˇenˇeny nebo • delete zdroj byl smazán. K oznaˇcen´ı verze kolekce je pouˇzita nepr˚ uhledná textová známka collblob. Tato známka je vˇzdy obsaˇzena v odpovˇedi na metodu SEARCH a oznaˇcuje novou verzi kolekce, kterou jsme právˇe odpovˇed´ı obdrˇzeli. Tuto známku m˚ uˇzeme pouˇz´ıt pˇri dalˇs´ım hledán´ı metodou SEARCH a dostaneme seznam veˇsker´ ych zmˇen, které nastaly od verze oznaˇcené známkou. Pokud pouˇzijeme známku prázdnou, vrac´ı server vˇsechny zdroje se stavem new. 13


2.3.5


Metoda LOCK a UNLOCK

K e-mailovému serveru m˚ uˇze najednou pˇristupovat konkurenˇcnˇe v´ıce klient˚ u a proto je nutné pˇri vytváˇren´ı nebo u ´pravˇe zdroje tento zdroj explicitnˇe zamknout pomoc´ı metody LOCK a vytvoˇrit tak novou transakci. Metoda LOCK umoˇzn ˇuje zamknout i neexistuj´ıc´ı zdroj a to pro pˇr´ıpad, kdy potˇrebujeme nov´ y zdroj vytvoˇrit. Transakce se vytváˇr´ı pouze pro nahráván´ı dokument˚ u metodou PUT a PROPPATCH, kdy pˇrenos trvá ˇrádovˇe déle neˇz u jin´ ych operac´ı jako DELETE nebo MKCOL. Transakce je vˇzdy vytvoˇrena na dobu jedné hodiny a po této dobˇe se automaticky zruˇs´ı. Server vrac´ı odpovˇed’ 200, pokud je transakce u ´spˇeˇsnˇe vytvoˇrena, nebo 403, pokud transakci nelze vytvoˇrit nebo jin´ y zámek je jiˇz aktivn´ı nad stejn´ ym zdrojem. V odpovˇedi je také uvedena nepr˚ uhledná známka Lock-Token identifikuj´ıc´ı transakci, která se pouˇzije v hlaviˇcce If pro vˇsechny metody transakce. Transakci je moˇzné ukonˇcit explicitnˇe metodou UNLOCK. V XML tˇele poˇzadavku se uvád´ı, zda byla transakce u ´spˇeˇsnˇe provedena a zmˇeny se maj´ı zapsat (element DAV:commit) nebo transakce nebyla u ´spˇeˇsná a zmˇeny se maj´ı zruˇsit (element DAV:abort). Po ukonˇcen´ı transakce je zámek uvolnˇen a jin´ y klient m˚ uˇze pˇristupovat ke stejnému zdroji.

2.3.6

Metoda SUBSCRIBE a POLL

Metodou SUBSCRIBE je moˇzné pˇrihlásit se ke sledován´ı zmˇen nad kolekc´ı specifikovanou v URI poˇzadavku. T´ımto zp˚ usobem je moˇzné z´ıskat informace o zmˇenˇe v reálném ˇcase hned, jakmile nastane. Pˇrihláˇsen´ı je identifikováno celoˇc´ıseln´ ym Subscription-ID, které server vrac´ı pˇri u ´spˇeˇsné odpovˇedi 200. Pˇrihláˇsen´ı je moˇzné provést pouze na kolekce, pokud se pokus´ıme vytvoˇrit pˇrihláˇsen´ı na jin´ y zdroj, server odpov´ı 501. Pˇrihláˇsen´ı trvá implicitnˇe jednu hodinu a pˇred uplynut´ım této doby je moˇzné jej obnovit opˇetovn´ ym volán´ım metody SUBSCRIBE, ale tentokrát s hlaviˇckou Subscription-ID obsahuj´ıc´ı identifikátor pˇrihláˇsen´ı. Klient m˚ uˇze b´ yt o zmˇenách informován dvˇema zp˚ usoby: • Metodou NOTIFY Klient oznám´ı serveru, na které URL bude ˇcekat na oznámen´ı zmˇeny, hlaviˇckou Call-Back, pouˇz´ıvaj´ıc´ı protokol HTTPU. Na tuto URL následnˇe server pˇri kaˇzdé zmˇenˇe zavolá metodu NOTIFY, takˇze klient je informován o zmˇenˇe ihned, jakmile na stranˇe serveru nastane. Nev´ yhodou je nutnost implementace HTTP serveru na stranˇe klienta pro podporu naslouchán´ı HTTP volán´ı [MSDN]. • Metodou POLL Klient se periodicky ptá serveru metodou POLL s hlaviˇckou Subscription-ID, zda nastala zmˇena nad dan´ ym pˇrihláˇsen´ım. Pˇri volán´ı metody POLL je moˇzné uvést v´ıce identifikátor˚ u pˇrihláˇsen´ı. Server v u ´spˇeˇsné odpovˇedi 207 rozdˇel´ı identifikátory do tˇr´ı skupin: 200 pro existuj´ıc´ı pˇrihláˇsen´ı se zmˇenou, 204 pro existuj´ıc´ı pˇrihláˇsen´ı beze zmˇeny a 403 pro neexistuj´ıc´ı pˇrihláˇsen´ı. Nev´ yhodou je, ˇze oznámen´ı o zmˇenˇe klient dostane, aˇz ve chv´ıli kdy se zeptá. To samozˇrejme m˚ uˇze b´ yt i v´ yhodou, protoˇze právˇe má ˇcas zmˇeny obslouˇzit. Znaˇcnou v´ yhodou je jednoduchost klienta, nen´ı nutné implementovat HTTP server [MSDN]. Pˇrihláˇsen´ı je zruˇseno automaticky po uplynut´ı ˇcasového limitu, pˇri zruˇsen´ı kolekce nebo je moˇzné jej zruˇsit explicitnˇe volán´ım metody UNSUBSCRIBE s hlaviˇckou SubscriptionID obsahuj´ıc´ı identifikátor pˇrihláˇsen´ı. 14


D˚ uvody pro pouˇzit´ı WebDAV

Typy pˇ rihl´ aˇ sen´ı Metodou SUBSCRIBE je moˇzné pˇrihlásit se k odbˇeru r˚ uzn´ ych typ˚ u událost´ı do r˚ uzné hloubky pomoc´ı hlaviˇcek Depth a Notification-Type: • Hlaviˇ cka Depth stejnˇe jako v pˇr´ıpadˇe metody PROPFIND (2.3.1) umoˇzn ˇuje odeb´ırat zmˇeny pouze pro vnitˇrn´ı ˇcleny kolekce nebo pro vˇsechny ˇcleny kolekce. • Hlaviˇ cka Notification-Type specifikuje sledovanou událost. E-mailov´ y server Kerio Connect podporuje celkem dva typy událost´ı. Hodnotou update“ sledujeme ” zmˇeny obsahu nebo vlastnost´ı zdroj˚ u. Hodnotou delete“ sledujeme událost sma” zán´ı zdroje. Je nutné poznamenat, ˇze událost update“ sleduje v implementaci i udá” lost smazán´ı, takˇze druhá hodnota nen´ı potˇreba, pokud nechceme sledovat pouze odstranˇen´ı zdroje.

2.4

D˚ uvody pro pouˇ zit´ı WebDAV

• Standard WebDAV je velice dobˇre popsan´ y a jednoznaˇcn´ y standard provˇeˇren´ y mnoha pouˇzit´ımi. Je to jedna z v´ yhod pro pouˇzit´ı protokolu WebDAV. Jak´ ykoliv jin´ y emailov´ y server bude moˇzné synchronizovat pomoc´ı protokolu WebDAV, pokud bude server toto komunikaˇcn´ı rozhran´ı implementovat. A i kdyˇz se jedná o pouˇzit´ı standardu od spoleˇcnosti Microsoft, stále se jedná pouze o nadmnoˇzinu oficiáln´ıho standardu RFC 4918. • Pouˇ zit´ı HTTP Bez protokolu HTTP se ˇza´dn´ y dneˇsn´ı standardn´ı poˇc´ıtaˇc nem˚ uˇze obej´ıt, jelikoˇz by ˇzádn´ y z uˇzivatel˚ u nemohl prohl´ıˇzet webové stránky. Proto je tento protokol zaveden jako standardn´ı ve veˇsker´ ych firewallech, port 80 nen´ı blokován a nen´ı nutné pro nˇej nastavovat specifická pravidla. • Bezpeˇ cnost Protokol HTTP umoˇzn ˇuje ˇsifrovanou komunikaci pˇridán´ım SSL vrstvy s v´ ymˇenou certifikát˚ u, ˇc´ımˇz vznikne jeho zabezpeˇcená varianta HTTPS. Je proto moˇzné m´ısto standardn´ıho textového formátu pos´ılat data zaˇsifrovanˇe bez jakékoliv nutnosti zmˇenit komunikaˇcn´ı protokol. Nav´ıc se opˇet jedná o standardn´ı protokol na portu 443, kter´ y nen´ı blokován. • Komprimace Protokol HTTP umoˇzn ˇuje pˇrenáˇsen komprimovaná data, ˇc´ımˇz je moˇzné znaˇcnˇe ulehˇcit komunikaˇcn´ımu médiu pˇri pˇrenosu dat. • Podpora replikace Jak bude uvedeno dále, rozˇs´ıˇren´ı WebDAV od spoleˇcnosti Microsoft v sobˇe pˇr´ımo zahrnuje podporu replikace dat mezi servery. Takˇze kromˇe Manifest of a Collection jsou k dispozici dalˇs´ı data pomáhaj´ıc´ı pˇri replikaci. • Kerio Connect Nejvˇetˇs´ım d˚ uvodem pro pouˇzit´ı WebDAV je ovˇsem existence otestovaného a funkˇcn´ıho komunikaˇcn´ıho rozhran´ı v produktu Kerio Connect. Nen´ı tedy nutné pro synchronizaci emailov´ ych server˚ u mˇenit produkt Kerio Connect, ale pouze pouˇz´ıt toto rozhran´ı.

15

3 Replikace Replikace dat udrˇzuje v´ıcenásobné kopie dat, naz´ yvané repliky, na oddˇelen´ ych poˇc´ıtaˇc´ıch. Tato velice d˚ uleˇzitá technologie umoˇzn ˇuje existenci distribuovan´ ych sluˇzeb. Replikace zvyˇsuje dostupnost a propustnost, jelikoˇz data jsou uloˇzena ve v´ıcenásobn´ ych kopi´ıch, ke kter´ ym lze pˇristupovat najednou a oddˇelenˇe [Saito].

3.1

Konzistence

Hlavn´ım c´ılem vˇsech replikaˇcn´ıch technik a algoritm˚ u je udrˇzovat konzistenci dat [Saito]. Konzistence jsou pravidla, která mus´ı replikaˇcn´ı algoritmus dodrˇzovat pro udrˇzen´ı vˇsech replik v konzistentn´ım stavu. Model konzistence definuje, za jak dlouho budou zmˇeny dostupné na ostatn´ıch replikách nebo v jakém poˇrad´ı se provád´ı operace. Model˚ u konzistence existuje celá ˇrada, liˇs´ı se pˇredevˇs´ım ve striktnosti pravidel. Následuj´ıc´ı text uvád´ı pro pˇredstavu dva v´ yraznˇe odliˇsné modely: • Striktn´ı konzistence znamená, ˇze aby mohla b´ yt libovolná zmˇena na jedné z replik u ´spˇeˇsná, je nutné, aby tato zmˇena byla okamˇzitˇe zreplikována na vˇsech ostatn´ıch replikách. Jakmile je obdrˇzeno potvrzen´ı o u ´spˇeˇsném proveden´ı na vˇsech replikách, je i volaj´ıc´ı operace u ´spˇeˇsná. Jedin´ ym moˇzn´ ym zp˚ usobem jak této konzistence dosáhnout je pouˇzit´ı zámk˚ u a vˇsechny repliky v dobˇe aktualizace uzamknout, coˇz má samozˇrejmˇe fatáln´ı dopad na propustnost systému. • Eventual consistency neformálnˇe znamená, ˇze vˇsechny repliky nakonec (z angl. eventually) dosáhnou koneˇcného stejného stavu, pokud uˇzivatel pˇrestane vytváˇret nové operace [Saito]. Tento model striktnˇe nepˇredepisuje, kdy maj´ı repliky dosáhnout stejného stavu, jen ˇr´ıká, ˇze ho nakonec mus´ı dosáhnout. V dneˇsn´ı dobˇe se jedná o velmi populárn´ı koncept u systém˚ u s optimistickou replikac´ı (viz sekce 3.3), systémy jsou jednoduˇsˇs´ı a lépe ˇskálovatelné. Tento koncept pouˇz´ıvá napˇr´ıklad Google File System [Ghemawat].

3.2

Pesimistick´ a replikace

Tradiˇcn´ı technikou replikace je udrˇzován´ı jedné primárn´ı kopie na primárn´ım serveru v distribuovaném systému. Primárn´ı replika zpracovává veˇskeré poˇzadavky na zmˇenu dat. Jakmile je zmˇena provedena, je asynchronnˇe zreplikována na ostatn´ı, sekundárn´ı repliky. V dobˇe, kdy jsou data na sekundárn´ıch replikách neaktuáln´ı, je pˇr´ıstup k nim blokován. Pokud primárn´ı kopie vypadne, ostatn´ı repliky si zvol´ı novou primárn´ı kopii a systém funguje dále. Tato technika se naz´ yvá pesimistická replikace“ [Saito]. ” Pesimistická technika je jednoduchá a nemus´ı ˇreˇsit ˇza´dné konflikty, jelikoˇz veˇskeré aktualizace se provád´ı vˇzdy nad aktuáln´ımi daty. Tato technika funguje dobˇre na lokáln´ıch s´ıt´ıch, kde latence mezi replikami je malá a v´ ypadky nepravdˇepodobné. Nem˚ uˇzeme od n´ı ovˇsem oˇcekávat dobré v´ ykony v prostˇred´ı internetu, s vysokou latenc´ı, malou propustnost´ı a ˇcast´ ymi v´ ypadky. Propagace zmˇen na sekundárn´ı repliky je pomalá a propustnost v´ yznamnˇe klesá, d´ıky blokován´ı neaktuáln´ıch dat. Nav´ıc je zde velká pravdˇepodobnost ztráty 16

Replikace

Optimistická replikace

dat pˇri v´ ypadku primárn´ı kopie, pokud se zmˇeny nestaˇc´ı zreplikovat na sekundárn´ı repliky. Je velice tˇeˇzké vytvoˇrit systém s pesimistickou replikac´ı v prostˇred´ı internetu s ˇcastou potˇrebou zápis˚ u, jelikoˇz jeho propustnost dramaticky klesá s nar˚ ustaj´ıc´ım poˇctem uˇzivatel˚ u. V tomto prostˇred´ı nalezne vyuˇzit´ı replikace optimistická [Saito].

3.3

Optimistick´ a replikace

Kl´ıˇcovou myˇslenkou pro optimistickou replikaci je povolit pˇr´ıstup pro zápis na libovolné replice bez dˇr´ıvˇejˇs´ı synchronizace a optimisticky pˇredpokládat, ˇze konflikt v´ıce zápis˚ u do jednoho objektu nastane velice vzácnˇe, pokud v˚ ubec kdy nastane. Vˇsechny provedené zmˇeny jsou propagovány na pozad´ı, a pokud v´ıcenásobn´ y zápis do jednoho objektu nastane, je konflikt vyˇreˇsen bˇehem synchronizace [Saito]. Optimistická replikace nab´ız´ı mnoho v´ yhod. Dostupnost dat se zv´ yˇs´ı a data jsou zpracovávána i pˇri v´ ypadku libovolné repliky. Umoˇzn ˇuje asynchronn´ı spolupráci mezi v´ıce uˇzivateli. Repliky z˚ ustávaj´ı stále autonomn´ı a nezávislé na primárn´ı replice [Saito]. Oproti pesimistické replikaci je vˇsak nutné ˇreˇsit konflikty. Tam kde pesimistická replikace ˇceká na aktuáln´ı data, optimistická replikace mus´ı hádat jak vyˇreˇsit konflikt mezi konkurentn´ımi operacemi. Takˇze je pouˇzitelná pouze pro systémy, které toleruj´ı obˇcasné konflikty a nekonzistentn´ı data. Optimistickou replikaci pouˇz´ıvaj´ı napˇr´ıklad systémy DNS, CVS a SVN.

3.3.1

Single-master

V distribuovaném prostˇred´ı je ˇcasto mnohem sloˇzitˇejˇs´ı problém distribuovaného algoritmu pˇreveden na jednoduˇsˇs´ı algoritmus centralizovan´ y napˇr´ıklad proveden´ım distribuovaného v´ ybˇeru 1 z N pro zvolen´ı centráln´ıho prvku. Stejnˇe je tomu i v pˇr´ıpadˇe architektury singlemaster. Systém stále dovoluje zápis do vˇsech replik, ale za plánován´ı poˇrad´ı operac´ı a ˇreˇsen´ı konflikt˚ u je zodpovˇedn´ y pouze jedin´ y uzel, tzv. master“. Master pˇrij´ımá operace ” od ostatn´ıch replik a po vhodném naplánován´ı odeˇsle operace ostatn´ım replikám. Systém je podstatnˇe jednoduˇs´ı, jelikoˇz konflikty jsou ˇreˇseny centralizovanˇe a poˇrad´ı urˇcuje pouze jeden uzel. Pokud tento uzel vypadne, je zvolen nov´ y uzel opˇet pouˇzit´ım algoritmu v´ ybˇeru 1 z N. Nev´ yhodou je samozˇrejmˇe omezená propustnost pˇri velkém poˇctu operac´ı, ale systém nen´ı blokován jako u pesimistické replikace.

3.3.2

Multi-master

Naproti tomu existuj´ı systémy multi-master, kde nˇekolik nebo vˇsechny repliky systému rozhoduj´ı o poˇrad´ı operac´ı. Replika odeˇsle operaci, která na n´ı byla vykonána, ostatn´ım replikám. Pokud se na tˇechto replikách neprovádˇela ve stejnou dobu konfliktn´ı operace, je operace u ´spˇeˇsnˇe provedena. Pokud ovˇsem konfliktn´ı operace probˇehla, je nutné naplánovat na vˇsech replikách správné a hlavnˇe stejné poˇrad´ı operac´ı, aby byla udrˇzena konzistence. Systém mus´ı tedy disponovat algoritmem shody (z angl. commitment protocol), kter´ ym se repliky shodnou na spoleˇcném v´ ysledku provádˇen´ı operac´ı [Saito]. To s sebou ovˇsem pˇrináˇs´ı velkou reˇzii pˇri vysokém poˇctu konfliktn´ıch operac´ı. Na druhou stranu, pokud systém nepˇredpokládá vysok´ y poˇcet konflikt˚ u, je tato architektura mnohem v´ ykonnˇejˇs´ı a ˇskálova-

17

Replikace

Soubˇeˇznost operac´ı

telná, d´ıky chybˇej´ıc´ımu u ´zkému m´ıstu jako v architektuˇre single-master. Pro optimalizaci reˇzie je také moˇzné zvolit r˚ uzn´ y poˇcet master˚ u.

3.4

Soubˇ eˇ znost operac´ı

Optimistická replikace pˇrináˇs´ı jiˇz zm´ınˇenou komplikaci v podobˇe nutnosti detekovat a ˇreˇsit ´ konflikty vzniklé zápisem do stejného objektu na r˚ uzn´ ych replikách. Ukolem systému je naplánován´ı, seˇrazen´ı a detekce konflikt˚ u tˇechto operac´ı tak, aby v´ ysledkem byl opˇet konzistentn´ı stav. Systém ovˇsem nen´ı schopn´ y správnˇe seˇradit a naplánovat operace, pokud nezná jejich vzájemné poˇrad´ı, tzv. happened-before relaci [Lamport]. Bohuˇzel v distribuovaném prostˇred´ı, ve kterém komunikaˇcn´ı zpoˇzdˇen´ı je nepˇredv´ıdatelné, nem˚ uˇzeme jednoduˇse urˇcit poˇrad´ı událost´ı podle poˇrad´ı pˇr´ıchodu, jako je tomu u bˇeˇzn´ ych aplikac´ı. Pˇredstavme si dvˇe operace α a β, které mohli vzniknout na jedné z replik i nebo j. Operace α nastala pˇred operac´ı β (α happened before β), právˇe kdyˇz: • i = j a operace α nastala pˇred operac´ı β (operace se udály na stejné replice v jin´ y ˇcasov´ y okamˇzik) nebo • i 6= j a β nastala aˇz poté, co j obdrˇzela a vykonala operaci α, nebo • existuje jiná operace γ, kdy α pˇredcház´ı γ a γ pˇredcház´ı β. Pokud ani jedna z tˇechto podm´ınek nen´ı splnˇena, nen´ı moˇzné jednoduˇse urˇcit happenedbefore relaci a obˇe operace jsou povaˇzovány za soubˇ eˇ zn´ e [Lamport]. Existuj´ı dvˇe základn´ı skupiny technik k urˇcen´ı poˇrad´ı a plánován´ı operac´ı, a to syntaktické a sémantické. Syntaktické plánován´ı urˇcuje v´ ysledné poˇrad´ı operac´ı z ˇcasu a m´ısta vzniku dané operace. Naproti tomu sémantické plánován´ı vyuˇz´ıvá sémantiku operac´ı.

3.4.1

Syntaktick´ e pl´ anovaˇ ce

Syntaktick´ y plánovaˇc urˇcuje poˇrad´ı operac´ı pouze na základˇe informace kdy, kde a k´ ym byla operace vytvoˇrena [Saito]. Syntaktické plánovaˇce jsou jednoduché a obecné, ale mohou vyvolat zbyteˇcné konflikty. Uvaˇzujme napˇr´ıklad systém pro rezervaci dataprojektor˚ u, kde následuj´ıc´ı tˇri operace vzniknou soubˇeˇznˇe: uˇzivatel A si vyp˚ ujˇc´ı projektor (1), uˇzivatel B si vyp˚ ujˇc´ı projektor (2) a uˇzivatel C vrát´ı projektor (3). Syntaktick´ y plánovaˇc tyto operace naplánuje v poˇrad´ı vzniku, tedy 1,2 a 3, coˇz znamená, ˇze operace 2 se nezdaˇr´ı, jelikoˇz projektor je jiˇz vyp˚ ujˇcen. Typick´ ym pˇr´ıkladem syntaktického plánovaˇce jsou ˇcasové znaˇcky. Re´ aln´ e hodiny Nejjednoduˇsˇs´ı technikou pro urˇcen´ı happened-before relace je pouˇzit´ı hodin reálného ˇcasu. Kaˇzdá z replik t´ımto ˇcasem disponuje a jednoduˇse ho uvede v operaci. Porovnán´ı tˇechto ˇcas˚ u mezi replikami je ovˇsem smˇerodatné pouze pokud jsou hodiny na vˇsech replikách správnˇe synchronizovány. Kupˇr´ıkladu mˇejme dvˇe operace, α na replice i a β na replice j.

18

Replikace


ˇ operace β m˚ Cas uˇze stále pˇredcházet ˇcas operace α, i kdyˇz j jiˇz dávno operaci α pˇrijalo, jelikoˇz hodiny j m˚ uˇzou b´ yt o hodnˇe pozadu oproti i. Tento problém ovˇsem nen´ı neˇreˇsiteln´ y. V dneˇsn´ı dobˇe je velkou snahou právˇe správná synchronizace ˇcas˚ u v distribuovaném prostˇred´ı. Existuje napˇr´ıklad modern´ı algoritmus NTP (Network Time Protocol), kter´ y dokáˇze udrˇzet synchronizaci hodin s pˇresnost´ı ˇ na des´ıtky milisekund s témˇeˇr zanedbateln´ ymi náklady [Saito]. Casy replik tak m˚ uˇzou b´ yt dostateˇcnˇe pˇresné pro urˇcen´ı vˇetˇsiny happened-before relac´ı. Logick´ e hodiny Logické hodiny, naz´ yvané také Lamportovy hodiny, jsou rostouc´ı skalárn´ı ˇcasová znaˇcka udrˇzovaná na kaˇzdé jednotlivé replice [Lamport]. Ve chv´ıli, kdy je provedena operace α, replika zv´ yˇs´ı svoji ˇcasovou znaˇcku a pˇriˇrad´ı novou hodnotu k operaci α. Tato hodnota se oznaˇcuje Cα . Replika pˇrij´ımaj´ıc´ı operaci od jiné repliky zmˇen´ı svoji ˇcasovou znaˇcku tak, aby byla vyˇsˇs´ı neˇz ˇcasová znaˇcka pˇr´ıchoz´ı operace a zároveˇ n vyˇsˇs´ı neˇz aktuáln´ı hodnota logick´ ych hodin. Pokud tedy operace α nastala pˇred operac´ı β mus´ı platit, ˇze Cα < Cβ . Bohuˇzel logické hodiny (ani jiné skalárn´ı hodiny) nemohou detekovat soubˇeˇznost, jelikoˇz Cα < Cβ nutnˇe neznamená, ˇze operace α nastala pˇred operac´ı β [Lamport]. Vektorov´ e hodiny Vektorové hodiny jsou rozˇs´ıˇren´ım klasick´ ych logick´ ych hodin a je dokázáno, ˇze jsou nejmenˇs´ı datovou strukturou pro pˇresné mˇeˇren´ı happened-before relace [Saito]. Vektorové hodiny jsou datová struktura V Ci uloˇzená na replice i obsahuj´ıc´ı M logick´ ych hodin, kde M je poˇcet master replik, ˇcili obsahuje informace o logick´ ych hodinách vˇsech master replik. Pˇri proveden´ı nové operace α jsou nav´ yˇseny pouze logické hodiny dané repliky V Ci [i] a k operaci je pˇriˇrazena nová hodnota V Ci . Replika pˇrij´ımaj´ıc´ı operaci zamˇen´ı logické hodiny pro repliku, na které operace nastala, za pˇrijatou hodnotu a zv´ yˇs´ı svoje logické hodiny. Na základˇe v´ yˇse uvedeného principu m˚ uˇzeme urˇcit, ˇze operace α nastala pˇred operac´ı β právˇe tehdy, jsou-li vektorové hodiny rozd´ılné a zároveˇ n vˇsechny logické hodiny V Cα jsou rovny nebo menˇs´ı neˇz logické hodiny V Cβ pro stejné pozice, neboli V Cα je dominantn´ı nad V Cβ . Pokud ani jedna z vektorov´ ych hodin nen´ı dominantn´ı, jsou operace soubˇeˇzné. Pokud V Ci [j] = t, replika i pˇrijala veˇskeré operace od j do logického ˇcasu t [Lamport]. Obecn´ ym problémem vektorov´ ych hodin je jejich velikost pro velk´ y poˇcet master replik [Saito].

3.4.2

S´ emantick´ e pl´ anovaˇ ce

Sémantické plánován´ı uvaˇzuje sémantické relace mezi jednotliv´ ymi operacemi, ˇcili zkoumá operace do hloubky a zjiˇst’uje napˇr´ıklad jejich komutativitu nebo idempotenci. Pokud pouˇzijeme sémantické plánován´ı na pˇr´ıklad vyp˚ ujˇcen´ı dataprojektor˚ u ze sekce 3.4.1, sémantick´ y plánovaˇc tyto operace naplánuje v poˇrad´ı 1, 3 a 2, ˇcili vˇsechny operace se zdaˇr´ı. Sémantické plánován´ı se pouˇz´ıvá bud’to samostatnˇe nebo v kombinaci s happened-before relac´ı urˇcenou syntaktickou metodou, kdy syntaktické plánován´ı nem˚ uˇze jiˇz dále rozhodnout, jelikoˇz se jedná napˇr´ıklad o soubˇeˇzné operace [Saito]. Sémantické plánovaˇce jsou ˇcasto aplikaˇcnˇe specifické a v´ ypoˇcetnˇe nároˇcné na rozd´ıl od obecn´ ych syntaktick´ ych plánovaˇc˚ u. 19

Replikace


Komutativita Pokud dvˇe po sobˇe jdouc´ı operace α a β jsou navzájem komutativn´ı, mohou b´ yt provedeny v libovolném poˇrad´ı, i kdyˇz nezachovaj´ı happened-before relaci, jelikoˇz tyto operace jsou na sobˇe nezávislé [Saito]. Bˇeˇzn´ ym pˇr´ıkladem je operace zápisu do dvou nezávisl´ ych objekt˚ u. D´ıky tomu nemus´ıme provádˇet rollback pokaˇzdé, kdyˇz obdrˇz´ıme komutativn´ı operaci mimo poˇrad´ı. Kanonick´ e poˇ rad´ı Ramsey a Csirmaz [Ramsey] definovali sémantická pravidla pro ˇrazen´ı operac´ı v souborovém systému. Nesoubˇeˇzné operace jsou ˇrazeny podle syntaktické happened-before relace a pro kaˇzd´ y moˇzn´ y pár soubˇeˇzn´ ych operac´ı jsou definována pravidla, která ˇr´ıkaj´ı, jak je moˇzné dané operace seˇradit. Mˇejme napˇr´ıklad operaci vytvoˇren´ı dvou soubor˚ u a/b a a/c. Tyto operace mohou b´ yt provedeny v libovolném poˇrad´ı, i kdyˇz modifikuj´ı spoleˇcn´ y objekt - sloˇzku a. Jako dalˇs´ı pˇr´ıklad m˚ uˇzeme uvést operace smazán´ı a modifikace stejného souboru. Tyto operace jsou oznaˇceny jako konfliktn´ı a uˇzivatel je vyzván k jeho vyˇreˇsen´ı. Ramsey a Csirmaz ve svém souborovém systému uvaˇzuj´ı pouze tˇri operace create, remove a edit, kdy napˇr´ıklad neuvaˇzuj´ı operaci move, která by znaˇcnˇe systém zkomplikovala, jelikoˇz pracuje celkem se tˇremi objekty - dva adresáˇre a jeden soubor. I pˇresto bylo vˇsak nutné specifikovat celkem 36 pravidel, s kter´ ymi dokázali, ˇze repliky pouˇz´ıvaj´ıc´ı tento systém z˚ ustávaj´ı konzistentn´ı [Ramsey]. Transformace operac´ı Transformace operac´ı je technika vyvinutá pro umoˇznˇen´ı spolupráce v´ıce editor˚ u [Saito]. Editor uprav´ı text objektu na lokáln´ı replice a tato opearace (pˇridán´ı nebo smazán´ı textu) je propagována na ostatn´ı repliky ve formˇe pˇr´ıkazu - delete(x) nebo insert(y). Ostatn´ı repliky provádˇej´ı pˇr´ıchoz´ı operace v poˇrad´ı jejich pˇr´ıjmu. Z ˇcehoˇz vypl´ yvá, ˇze dvˇe repliky mohou vykonat stejné pˇr´ıkazy v jiném poˇrad´ı. Pro kaˇzd´ y takov´ y moˇzn´ y pár operac´ı jsou definována transformaˇcn´ı pravidla, která pˇr´ıchoz´ı pˇr´ıkaz pˇrep´ıˇs´ı tak, aby v´ ysledek operace byl stejn´ y, i kdyˇz je proveden v jiném poˇrad´ı. Mˇejme napˇr´ıklad text abc“ sd´ılen´ y mezi dvˇema editory na replikách i a j. Editor ” na replice i provede pˇridán´ı X“ na zaˇca´tek textu - insert(X) - a operace je odeslána ” na repliku j. Editor na replice j provede smazán´ı prvn´ıho znaku - delete(1) - a stejnˇe tak odeˇsle operaci na repliku i. Pokud bychom nepouˇzili transformaci operac´ı, dostali bychom na replice j správn´ y ˇretˇezec Xbc“, ale na replice i nesprávn´ y ˇretˇezec abc“, jelikoˇz operace ” ” smazala prvn´ı znak m´ısto znaku a“. S pouˇzit´ım transformac´ı dojde k pˇrepsán´ı operace ” delete(1) na delete(2) a obˇe repliky z˚ ustávaj´ı konzistentn´ı. Systémem tˇechto pˇrepisovac´ıch pravidel se zab´ yvá napˇr´ıkald studie A Calculus for Concurrent Update [Cormack]. Existuj´ı i varianty pro pouˇzit´ı v tabulkov´ ych editorem nebo souborov´ ych systémech [Saito]. Tato sémantická technika i pˇresto, ˇze je nutné definovat velice sloˇzitá pˇrepisovac´ı pravidla i pro jednoduché operace, pˇrináˇs´ı obrovskou v´ yhodu - nen´ı nutné na jiˇz aplikované operace provádˇet rollback a modifikace objekt˚ u tak prob´ıhá pouze smˇerem dopˇredu.

20

Replikace

Zpracován´ı konflikt˚ u

Optimalizaˇ cn´ı pˇ r´ıstup Jednou ze sofistikovan´ ych metod pro sémantické ˇrazen´ı je pˇreveden´ı tohoto problému na problém optimalizaˇcn´ı [Preguica]. Operace v této metodˇe jsou navzájem podm´ınˇené. Metoda podporuje nˇekolik r˚ uzn´ ych podm´ınek a mimo jiné napˇr´ıklad i závislost (operace α mus´ı b´ yt provedena po operaci β), implikaci (pokud je provedena operace α, je provedena i operace β) a v´ ybˇer (jedna z operac´ı α nebo β bude provedena, ale nikdy obˇe). Napˇr´ıklad uˇzivatel m˚ uˇze provést rezervaci m´ıstnosti A nebo B (v´ ybˇer), pokud má rezervovanou m´ıstnost, mus´ı si vyp˚ ujˇcit dataprojektor (implikace), ale pouze pokud má dostatek kredit˚ u (závislost). Metoda se k tˇemto operac´ım chová jako k optimalizaˇcn´ımu problému, kdy se snaˇz´ı naplánovat nejlepˇs´ı poˇrad´ı operac´ı pro uspokojen´ı podm´ınek. Implementaci této metody pouˇz´ıvá napˇr´ıklad systém IceCube, kter´ y d´ıky efektivn´ımu hillclimbing algoritmu dokáˇze seˇradit 10.000 operac´ı bˇehem pouh´ ych 3 sekund, i kdyˇz je optimalizace NP-tˇeˇzk´ ym problémem [Preguica].

3.5

Zpracov´ an´ı konflikt˚ u

Operace α je konfliktn´ı, pokud jej´ı pˇredpoklady nejsou splnˇeny. Nejlepˇs´ım pˇr´ıstupem je vzniku konflikt˚ u zabránit u ´plnˇe - tzv. prevence. Systémy s pesimistickou replikac´ı konflikt˚ um zabraˇ nuj´ı zablokován´ım nebo zruˇsen´ım operac´ı. Bohuˇzel toto ˇreˇsen´ı má velkou nev´ yhodu v tom, ˇze sniˇzuje propustnost systém, jak je popsáno v sekci 3.2. Nˇekteré systémy konflikty dokonce ignoruj´ı. Jakákoliv operace, která by mohla b´ yt konfliktn´ı, je jednoduˇse pˇrepsána novˇejˇs´ı operac´ı jako napˇr´ıklad v pˇr´ıpadˇe pouˇzit´ı Thomas write rule algoritmu [Thomas]. Tyto ztracené operace mohou b´ yt nepodstatné, pokud je jejich poˇcet zanedbateln´ y nebo pokud se uˇzivatel tˇemto operac´ım dobrovolnˇe vyhne [Saito]. Dalˇs´ım moˇzn´ ym zp˚ usobem, kter´ y je moˇzné kombinovat s jin´ ymi, je poˇcet konflikt˚ u redukovat ˇcastou aktualizac´ı replik mezi sebou nebo rozdˇelen´ım operac´ı na menˇs´ı ˇcásti, ˇc´ımˇz se podstatnˇe sn´ıˇz´ı pravdˇepodobnost v´ yskytu konfliktn´ıch operac´ı [Saito]. Nejˇcastˇejˇs´ım zp˚ usobem zpracován´ı konflikt˚ u je vˇsak jejich vznik povolit a následnˇe je detekovat a odstranit. Takové systémy jsou daleko uˇzivatelsky hodnotnˇejˇs´ı, neˇz systémy, které konflikty ignoruj´ı, jelikoˇz nedocház´ı ke ztrátám konfliktn´ıch operac´ı. Metody pro detekci koliz´ı se stejnˇe jako u metod plánován´ı dˇel´ı do dvou skupin - syntaktické a sémantické. Syntaktické metody vyuˇz´ıvaj´ı happened-before relaci nebo nˇekterou jej´ı aproximaci k oznaˇcen´ı konflikt˚ u. Nejˇcastˇeji to znamená, ˇze pokud jsou operace soubˇeˇzné, jedna z nich je konfliktn´ı. Sémantick´ y pˇr´ıstup vyuˇz´ıvá znalosti sémantiky operac´ı k detekci koliz´ı. Napˇr´ıklad v pˇr´ıpadˇe souborového systému je vytvoˇren´ı dvou nezávisl´ ych soubor˚ u soubˇeˇznˇe nekonfliktn´ı, ale aktualizace stejného adresáˇre jiˇz konfliktn´ı je [Saito]. Opˇet ovˇsem plat´ı, ˇze sémantické metody jsou ˇcasto aplikaˇcnˇe specifické, protoˇze mus´ı znát sémantiku vˇsech operac´ı. C´ılem metod pro odstranˇen´ı konfliktu je pˇrepsán´ı nebo zruˇsen´ı konfliktn´ı operace tak, aby byl konflikt odstranˇen. Odstranˇen´ı konflikt˚ u m˚ uˇze b´ yt provedeno bud’ automaticky, nebo manuálnˇe. Manuáln´ı odstranˇen´ı konflikt˚ u jednoduˇse neprovede konfliktn´ı operaci, ale vytvoˇr´ı dvˇe nové verze objektu. Prvn´ı verze objektu bez provedené operace a druhá verze objektu s provedenou operac´ı. Uˇzivatel mus´ı následnˇe z tˇechto verz´ı jednu vybrat, konflikt vyˇreˇsit a odeslat správnou verzi na ostatn´ı repliky. Automatické vyˇreˇsen´ı konflikt˚ u je aplikaˇcnˇe specifické a jedná se v podstatˇe o shodn´ y postup jako v pˇr´ıpadˇe manuáln´ıho 21

Replikace

Synchronizace replik

odstranˇen´ı konfliktu. Metoda pˇrij´ımá dva objekty, které slouˇc´ı, a vrac´ı nov´ y objekt, kter´ y ˇ je odeslán na ostatn´ı repliky [Saito]. Casto jsou v systémech pouˇzity oba pˇr´ıstupy. Napˇr´ıklad systém SVN se snaˇz´ı automaticky vyˇreˇsit konflikty v souborech a pokud nem˚ uˇze rozhodnout, je vyzván uˇzivatel, aby konflikt vyˇreˇsil manuálnˇe.

3.6


V sekc´ıch 3.5 a 3.4 byly uvedeny kl´ıˇcové techniky v prostˇred´ı distribuovaného systému replik, nyn´ı je ˇcas uvést, jak se zm´ınˇené techniky vyuˇz´ıvaj´ı pro synchronizaci. Synchronizace se dˇel´ı podle typu systému do dvou skupin - state-transfer a operation-transfer. State-transfer systémy pˇrenáˇsej´ı mezi replikami celé pozmˇenˇené objekty, kdeˇzto operationtransfer systémy pˇrenáˇsej´ı pouze operace, které zmˇeny zp˚ usobily. Je moˇzné se na statetransfer systém d´ıvat jako na operation-transfer pouze se tˇremi operacemi - ˇcten´ı, zápis a smazán´ı celého objektu. State-transfer systémy jsou jednoduché, protoˇze udrˇzován´ı konzistence znamená odeslán´ı celého nového objektu na ostatn´ı repliky. Operation-transfer systém naproti tomu mus´ı udrˇzovat historii operac´ı a dohodnout se na jejich spoleˇcném poˇrad´ı s ostatn´ımi. Na druhou stranu tyto systémy jsou mnohem efektivnˇejˇs´ı, hlavnˇe v pˇr´ıpadˇe, kdy objekty jsou velké a operace vysoko´ urovˇ nové. State-transfer systém mus´ı pˇri zmˇenˇe jednoho bitu pˇrenést cel´ y objekt, operation-transfer pouze danou operaci [Saito]. WebDAV protokol je state-transfer systém, protoˇze se omezuje na tˇri operace s cel´ ymi objekty - zápis metodou PUT, ˇcten´ı metodou GET a smazán´ı metodou DELETE. Nebudeme se tedy dále zab´ yvat sloˇzit´ ymi operation-transfer, ale pouze jednoduch´ ymi state-transfer systémy.

3.6.1

Pomal´ a synchronizace

Pˇri prvotn´ım propojen´ı v´ıce replik do jednoho systému je nejdˇr´ıve nutné provést tzv. pomalou synchronizaci. Tedy pˇrenést vˇsechny objekty mezi vˇsemi replikami a spárovat je pro pozdˇejˇs´ı zmˇenovou synchronizaci. Pokud se jedná o vytvoˇren´ı prázdného systému, nen´ı pomalá synchronizace nutná, jelikoˇz nejsou ˇzádné objekty, které je nutné pˇrenést. Problém ovˇsem nastává, pokud se jedná o propojen´ı v´ıce replik po v´ ypadku nebo vynucen´ı pomalé synchronizace uˇzivatelem. Mˇejme objekt αi na replice i a jeho kopii βj na replice j. Oba tyto objekty jsou shodné a byly pˇred vynucen´ım pomalé synchronizace synchronizovány proti sobˇe. U naivn´ı implementace by se vytvoˇrili nové kopie αj na replice j a βi na repliace i, coˇz vede k nevyˇzádané duplikaci objekt˚ u. C´ılem je tedy tyto objekty i po v´ ypadku spárovat, aby se opˇet chovaly jako jeden objekt. Standardn´ı metodou je pouˇzit´ı unikátn´ıho identifikátoru pro oznaˇcen´ı objekt˚ u a následné spárován´ı stejn´ ych identifikátor˚ u. Pokud nen´ı moˇzné objekty oznaˇcit shodnˇe na r˚ uzn´ ych replikách, pˇricház´ı na ˇradu sémantické metody. Napˇr´ıklad pro souborové systémy je moˇzné vyuˇz´ıt absolutn´ı cesty k souboru. Pˇri párován´ı je samozˇrejmˇe nutné zpracovat pˇr´ıpadné konflikty.

3.6.2

Zmˇ enov´ a synchronizace

Zmˇenová synchronizace, nebo také rychlá synchronizace, se provád´ı opakovanˇe, jakmile jsou repliky spárovány. Je moˇzné pˇrenáˇset pouze zmˇenˇené objekty, coˇz je v´ yraznˇe efektivnˇejˇs´ı, neˇz proveden´ı pomalé synchronizace vˇsech objekt˚ u. U state-transfer systém˚ u se vˇet22

Replikace


ˇsinou pouˇz´ıvaj´ı pro detekci zmˇen syntaktické metody. V´ yhodou state-transfer systému je pro udrˇzen´ı konzistence nutnost pˇrenést pouze nejnovˇejˇs´ı stav objektu a vynechat vˇsechny pˇredchoz´ı. Thomas write rule Kaˇzdá replika uchovává pro kaˇzd´ y objekt ˇcasovou znaˇcku, která oznaˇcuje novost“ ob” jektu. Pˇri synchronizaci repliky i s replikou j je porovnána ˇcasová znaˇcka Ci a Cj a pokud je Cj novˇejˇs´ı, objekt je zkop´ırován z repliky j a ˇcasová znaˇcka je aktualizována. Tento algoritmus je velice jednoduch´ y a efektivn´ı, ale nedetekuje konflikty - moˇzn´ ym rozˇs´ıˇren´ım je two timestamps algoritmus [Thomas]. S pouˇzit´ım Thomas write rule algoritmu vyˇzaduje smazán´ı objektu speciáln´ı zacházen´ı. Jednoduché smazán´ı objektu z repliky i zp˚ usob´ı pˇri dalˇs´ı synchronizaci obnovu objektu z jiné repliky, jelikoˇz jej´ı ˇcasová znaˇcka, v porovnán´ı s neexistuj´ıc´ı ˇcasovou znaˇckou, je novˇejˇs´ı [Saito]. K ˇreˇsen´ı tohoto problému je moˇzné pouˇz´ıt napˇr´ıklad Culling tombstones algoritmus popsan´ y n´ıˇze. Two timestamps Two timestamps algoritmus je rozˇs´ıˇren´ım Thomas write rule umoˇzn ˇuj´ıc´ı detekci konflikt˚ u. Kaˇzdá replika uchovává u kaˇzdého objektu nav´ıc ˇcasovou znaˇcku posledn´ı aktualizace. Konflikt je jednoduˇse detekován, pokud pˇri synchronizaci dvou replik je ˇcas aktualizace rozd´ıln´ y. Nev´ yhodou této techniky je ovˇsem detekce tzv. faleˇsn´ ych konflikt˚ u pˇri synchronizaci v´ıce jak dvou replik, takˇze je vhodn´ y zejména pro systémy s malou frekvenc´ı konflikt˚ u a mal´ ym mnoˇzstv´ım replik [Saito]. Modified bits Modified bits algoritmus je zjednoduˇsen´ım two timestamps algoritmu. Tento algoritmus funguje správnˇe pouze pokud dvˇe repliky jsou synchronizovány opakovanˇe - je pouˇzit napˇr´ıklad pro synchronizaci Pocket PC se stoln´ım poˇc´ıtaˇcem [Saito]. Kaˇzd´ y objekt obsahuje modified bit. Pokud je objekt modifikován v PC i Pocket PC jsou bity na obou stranách nastaveny a objekt je oznaˇcen jako konfliktn´ı. Tento algoritmus je moˇzné pouˇz´ıt pouze pro zmˇenovou synchronizaci mezi dvˇema replikami. V pˇr´ıpadˇe pouˇzit´ı pˇri pomalé synchronizaci jsou bity ignorovány a veˇskeré spárované objekty jsou oznaˇceny jako konfliktn´ı. Hash histories Základn´ı myˇslenkou v Hash histories algoritmu je pouˇzit´ı otisku objektu m´ısto ˇcasové znaˇcky pro reprezentaci stavu objektu (napˇr´ıklad MD5 funkce). Je tak moˇzné sledovat nejen jak se objekt zmˇenil, ale i jeho vˇetven´ı a sluˇcován´ı v ˇcase. Tabulka historie otisk˚ u s poˇctem replik a zmˇen znaˇcnˇe roste, je proto nutné pouˇz´ıt algoritmus pro odstranˇen´ı star´ ych záznam˚ u [Saito]. Culling tombstones V pˇr´ıpadˇe algoritmu Thomas write rule bylo uvedeno, ˇze smazán´ı objektu nen´ı triviáln´ı záleˇzitost´ı, jelikoˇz docház´ı k jeho obnovˇe pˇri synchronizaci. Jednou z metod je po smazaném 23

Replikace

Replikace a WebDAV

objektu zanechat náhrobek“ s ˇcasovou znaˇckou objektu. Kdykoliv poté dojde k synchro” nizaci s jinou replikou je nalezen náhrobek a objekt je smazán. Nev´ yhodou algoritmu je nar˚ ustaj´ıc´ı poˇcet náhrobk˚ u po smazan´ ych objektech, které ovˇsem nen´ı moˇzné smazat pro pˇr´ıpad, kdy se pˇripoj´ı replika, která byla dlouho nedostupná [Saito].

3.6.3

Aktivn´ı synchronizace

V´ yˇse zm´ınˇené metody synchronizace se ˇrad´ı do skupiny pasivn´ıch synchronizac´ı (poll metody), kdy replika libovoln´ ym zp˚ usobem vyhodnot´ı, ˇze je nutné provést pomalou nebo zmˇenovou synchronizaci a ta je provedena. Spouˇstˇeˇcem m˚ uˇze b´ yt vynucen´ı uˇzivatelem nebo vnitˇrn´ı ˇcasovaˇc. Mnohem efektivnˇejˇs´ı metodou je aktivn´ı synchronizace (push metody). Replika zaˇcne novou zmˇenu okamˇzitˇe aktivnˇe propagovat na ostatn´ı repliky, coˇz znaˇcnˇe redukuje zpoˇzdˇen´ı pˇrenosu zmˇen a eliminuje zat´ıˇzen´ı pˇri propagaci mnoha zmˇen u pasivn´ı replikace.

3.7

Replikace a WebDAV

Komunikaˇcn´ı protokol WebDAV (viz kapitola 2.2) jiˇz ve svém základu [RFC4918] obsahuje nˇekolik vlastnost´ı pro podporu replikace. Spoleˇcnost Microsoft ve své implementaci pro Microsoft Exchange [MSDN] tento koncept rozˇs´ıˇrila o nˇekolik nov´ ych vlastnost´ı zdroj˚ u a jiˇz v´ yˇse zm´ınˇen´ y Manifest of collection: • UID je unikátn´ı identifikátor v kontextu celé repliky. Umoˇzn ˇuje tak identifikaci zdroje v procesu zmˇenové synchronizace. UID je automaticky generováno v sémantice serveru. • Resourcetag je nepr˚ uhledn´ y textov´ y ˇretˇezec obsahuj´ıc´ı aktuáln´ı stav zdroje. Pokud je zdroj jakkoliv modifikován, je spoleˇcnˇe s n´ım vygenerován nov´ y resourcetag, ˇc´ımˇz je moˇzné detekovat modifikované zdroje, pˇr´ıpadnˇe ho pouˇz´ıt pro historii zmˇen pro algoritmus Hash histories popsan´ y v sekci 3.6.2. • Last-Modified obsahuje ˇcasovou znaˇcku ve formátu ISO 8601 udávaj´ıc´ı ˇcas posledn´ı zmˇeny, coˇz je moˇzné pouˇz´ıt pro algoritmy Thomas write rule nebo Two timestamps popsané v sekci 3.6.2. • Metoda SUBSCRIBE umoˇzn ˇuje provádˇet aktivn´ı synchronizaci. Jednoduˇse je moˇzné pˇrihlásit se ke sledován´ı vzniku událost´ı a jakmile daná událost nastane, je moˇzné provést ihned synchronizaci modifikovan´ ych zdroj˚ u. • Manifest of collection umoˇzn ˇuje provádˇet zmˇenovou synchronizaci, jelikoˇz vrac´ı seznam modifikovan´ ych zdroj˚ u v kolekci od posledn´ıho manifestu. Seznam obsahuje nové, modifikované a smazané zdroje.

24

4 Návrh modelu synchronizace V pˇredchoz´ıch kapitolách byl pˇredstaven komunikaˇcn´ı protokol WebDAV, kter´ y umoˇzn ˇuje u ´plnou práci s datov´ ym u ´loˇziˇstˇem Kerio Connect serveru, a existuj´ıc´ı modely replikace distribuovan´ ych datov´ ych u ´loˇziˇst’, které je moˇzné pro synchronizaci mezi datov´ ymi u ´loˇziˇsti pouˇz´ıt. Nyn´ı je nutné navrhnout s pouˇzit´ım tˇechto znalost´ı funguj´ıc´ı model synchronizace, ˇc´ımˇz se zab´ yvá celá tato kapitola.

4.1

Poˇ zadavky a pˇ redpoklady

Pˇred zapoˇcet´ım návrhu modelu synchronizace je potˇreba stanovit základn´ı poˇzadavky na model synchronizace a mnoˇzinu pˇredpoklad˚ u, které je nutné pˇri jeho návrhu respektovat: • Prostˇ red´ı je nespolehliv´ e - Servery nebo komunikaˇcn´ı linky mohou kdykoliv vypadnout a to nejen mezi synchronizacemi, ale i v pr˚ ubˇehu synchronizace, kdy server nemus´ı na poˇzadavek odpovˇedˇet nebo odpov´ı chybovou odpovˇed´ı. • Servery o sobˇ e nev´ı - Jednotlivé servery jsou od sebe oddˇeleny, nev´ı o sobˇe a nekomunikuj´ı spolu. Nen´ı tedy moˇzné synchronizaci navrhnout jako rozˇs´ıˇren´ı Kerio Connect serveru, ale jako proces, kter´ y samostatnˇe pobˇeˇz´ı mimo prostˇred´ı Kerio Connect serveru a bude zprostˇredkovávat komunikaci mezi servery. • Synchronizace m˚ uˇ ze b´ yt pˇ reruˇ sena - Synchronizace m˚ uˇze b´ yt zásahem administrátora nebo operaˇcn´ıho systému pˇreruˇsena a poté opˇet spuˇstˇena. • Konflikty objekt˚ u - Objekt m˚ uˇze b´ yt v´ıcenásobnˇe zmˇenˇen na v´ıce serverech najednou, coˇz m˚ uˇze vést ke konfliktu, kter´ y je nutné dle povahy objektu korektnˇe vyˇreˇsit. • Objem dat - Kaˇzd´ y c´ılov´ y Kerio Connect server obsahuje ˇra´dovˇe des´ıtky sloˇzek, které mohou obsahovat tis´ıce zdroj˚ u. • Operace jsou state-transfer - Komunikaˇcn´ı protokol WebDAV umoˇzn ˇuje pˇrenáˇset pouze celé objekty. Synchronizaˇcn´ımu modelu tedy nepropaguje, v jaké ˇcásti objektu zmˇena nastala, ale pouze to, ˇze zmˇena v objektu nastala. • Uˇ zivatel nem˚ uˇ ze zas´ ahnout - Nen´ı moˇzné se jak´ ymkoliv zp˚ usobem spojit s uˇzivatelem a poˇza´dat ho o vyˇreˇsen´ı konfliktu, vˇsechny konflikty je nutné ˇreˇsit automaticky. • Servery nejsou ˇ casovˇ e synchronizov´ any - Jednotlivé Kerio Connect servery nejsou ˇcasovˇe synchronizovány a jejich reálné hodiny se mohou rozb´ıhat (viz sekce 3.4.1). • Konzistence - Zmˇeny mus´ı b´ yt propagovány v nejbliˇzˇs´ım moˇzném term´ınu synchronizace, ale nemus´ı b´ yt striktnˇe propagovány ihned a systém toleruje obˇcasná nekonzistentn´ı data.

25

Návrh modelu synchronizace

C´ıle synchronizace

• Dostupnost - Synchronizace nesm´ı omezit dostupnost server˚ u a mus´ı b´ yt dostateˇcnˇe optimáln´ı, aby nevytˇeˇzovala dostupné prostˇredky serveru naplno.

4.2


Kaˇzdé Kerio Connect datové u ´loˇziˇstˇe je, dle terminologie WebDAV, rozdˇeleno do stromové struktury kolekc´ı, které obsahuj´ı strukturované nebo nestrukturované zdroje. Kolekce jsou jednoznaˇcnˇe identifikovány prostˇrednictv´ım URI, na které se nacház´ı, a mohou b´ yt hierarchicky vnoˇreny do jiné kolekce. Kolekce nav´ıc obsahuje pˇr´ıstupová práva (tzv. security descriptor ), která definuj´ı, jak´ ymi právy uˇzivatelé vzhledem ke kolekci a jej´ım ˇclen˚ um disponuj´ı. Kolekce je moˇzné pouze vytváˇret, mazat nebo upravovat jejich pˇr´ıstupová práva. Kaˇzdá kolekce m˚ uˇze obsahovat jeden aˇz ˇra´dovˇe tis´ıce dokument˚ u. Dokumenty nemohou obsahovat dalˇs´ı dokumenty ani kolekce. Dokumenty jsou jednoznaˇcnˇe identifikovány prostˇrednictv´ım vlastnosti UID, která se na r˚ uzn´ ych replikách pro stejn´ y dokument liˇs´ı, a dˇel´ı se do dvou skupin - nestrukturované dokumenty, u kter´ ych nelze zjistit v´ yznam obsahu, a strukturované dokumenty, které maj´ı pˇresnˇe specifikovanou vnitˇrn´ı strukturu, a je tedy moˇzné urˇcit v´ yznam obsahu. V prostˇred´ı Kerio Connect se vyskytuje celkem ˇsest typ˚ u dokument˚ u - emailová zpráva, kalendáˇrová událost, u ´kol, kontakt, distribuˇcn´ı seznam a poznámka. Poznámka vˇsak nen´ı podporována pro replikaci a tud´ıˇz následuj´ıc´ı text se o n´ı nebude zmiˇ novat. Kolekce se podle typ˚ u vnitˇrn´ıch dokument˚ u dˇel´ı podobnˇe jako dokumenty do pˇeti typ˚ u - poˇstovn´ı schránka, kalendáˇr, u ´koly, kontakty a poznámky. Emailov´ a zpr´ ava Emailová zpráva je nestrukturovan´ y dokument, kter´ y je specifikován ve standardu [RFC2822]. Kromˇe obsahu jsou k dokumentu pˇridruˇzeny i aktivn´ı vlastnosti jako napˇr´ıklad pˇr´ıjemce nebo pˇredmˇet zprávy. ´ Kalend´ aˇ rov´ a ud´ alost a Ukol ´ Kalendáˇrová událost a Ukol jsou strukturované dokumenty ve formátu iCalendar verze 2.0 [RFC2445]. Kalendáˇrová událost obsahuje právˇe jednu kalendáˇrovou událost VEVENT au ´kol obsahuje právˇe jeden u ´kol VTODO. Následuj´ıc´ı dokument je ukázkou jednoduché kalendáˇrové události Marketingová porada“: ”

26


1 2 3 4 5 6 7 8 9 10 11 12 13 14


BEGIN:VCALENDAR BEGIN:VEVENT DTSTAMP:20120223T153700Z UID:503b1180−29cf−4f63−8898−38e633f8b06c ORGANIZER;CN=”Test User 3”:mailto:[email protected] SUMMARY:Marketingov´ a porada DTSTART:20120224T153000 DTEND:20120224T160000 BEGIN:VALARM ACTION:DISPLAY TRIGGER;RELATED=START:−PT15M END:VALARM END:VEVENT END:VCALENDAR

Kontakt a Distribuˇ cn´ı seznam Kontakt a Distribuˇcn´ı seznam jsou strukturované dokumenty ve formátu vCard verze 3.0 [RFC2426]. Distribuˇcn´ı seznam je standardn´ı kontakt rozˇs´ıˇren´ y o vlastnosti pro reprezentaci distribuˇcn´ıch seznam˚ u. Formát dokumentu je stejn´ y jako u [RFC2445], jen pouˇzité vlastnosti se mˇen´ı. Následuj´ıc´ı dokument je ukázkou jednoduchého kontaktu Bc. Jiˇr´ı ” Praus“: 1 2 3 4 5 6 7 8 9 10

BEGIN:VCARD N:Praus;Jiˇr´ı;;Bc.; FN:Bc. Jiˇr´ı Praus URL;TYPE=WORK:www.test.lab TITLE:Program´ ator ICQ:123456789 BDAY;VALUE=DATE:20120208 EMAIL;TYPE=PREF,HOME:[email protected] UID:60876c2e−3e7b−4678−9153−e133f893f47d END:VCARD

Vlastnosti Ke kaˇzdému zdroji jsou pˇriˇrazeny strukturované WebDAV vlastnosti, které pˇridávaj´ı dokumentu dalˇs´ı v´ yznam, jako napˇr´ıklad pˇreˇctená/nepˇreˇctená emailová zpráva. Kaˇzd´ y zdroj obsahuje velké mnoˇzstv´ı vlastnost´ı, ale vˇetˇsina z nich je urˇcena pouze ke ˇcten´ı nebo jejich obsah je duplicitn´ı s obsahem dokumentu a nen´ı je tak nutné synchronizovat. • Pro kolekce je moˇzné synchronizovat pouze vlatnost http://schemas.microsoft.com/ exchange/security/descriptor, ostatn´ı jsou urˇceny pouze pro ˇcten´ı. • Pro vˇsechny typy dokument˚ u je nutné replikovat podmnoˇzinu vlastnost´ı jmenného prostoru http://schemas.microsoft.com/mapi/proptag/: – x0e070003 speciáln´ı MS Outlook pˇr´ıznaky, – x0E2B0003 speciáln´ı v´ yznam, 27


Architektura

– x10900003 stav zprávy, – x10910040 ˇcas oznaˇcen´ı zprávy stavem, – x10950003 identifikátor ikony stavu, – x67aa000b oznaˇcen´ı skryté nebo normáln´ı zprávy. • Pro emailové zprávy je nav´ıc nutné replikovat celé mnoˇziny vlastnost´ı ze jmenn´ ych prostor˚ u: – urn:schemas:mailheader: pro hlaviˇcku emailu, – urn:schemas:httpmail: pro dalˇs´ı atributy emailu.

4.3

Architektura

Kerio Connect server je autonomn´ı datové u ´loˇziˇstˇe um´ıstˇené v libovolném m´ıstˇe v s´ıti. Jednotlivé servery o sobˇe navzájem nev´ı a nekomunikuj´ı spolu. Uˇzivatelé mohou na kaˇzdém datovém u ´loˇziˇsti vykonávat libovolné operace nezávisle na ostatn´ıch serverech, z ˇcehoˇz vypl´ yvá, ˇze model se bude zab´ yvat optimistickou replikac´ı bl´ıˇze popsanou v sekci 3.3. Jelikoˇz do server˚ u nen´ı moˇzné zasahovat a servery se neznaj´ı, synchronizace mezi u ´loˇziˇsti mus´ı prob´ıhat pomoc´ı extern´ıho procesu, kter´ y o serverech v´ı a bude vyuˇz´ıvat komunikaˇcn´ı rozhran´ı WebDAV. Kaˇzd´ y server m˚ uˇze pˇred zapoˇcet´ım synchronizace obsahovat libovolná data, která mus´ı b´ yt synchronizaˇcn´ım procesem korektnˇe zreplikována na ostatn´ı servery.

Obrázek 4.1: Architektura single-master Obrázek 4.1 ukazuje návrh architektury synchronizace pro tˇri Kerio Connect servery. Vˇsechny servery disponuj´ı komunikaˇcn´ım rozhran´ım WebDAV, kter´ ym jsou dotazovány procesem synchronizace. Proces synchronizace bˇeˇz´ı na jednom ze server˚ u a replikuje data mezi servery po naznaˇcen´ ych komunikaˇcn´ıch kanálech. Informace o synchronizaci je nutné ukládat do lokáln´ı databáze, jelikoˇz nen´ı moˇzné zasahovat do prostˇred´ı Kerio Connect server˚ u, které neposkytuj´ı dostateˇcné informace pro efektivn´ı synchronizaci. Celou architekturu m˚ uˇzeme tedy oznaˇcit jako optimistickou replikaci single-master.

28


Konzistence

Obrázek 4.2: Architektura multi-master Obrázek 4.2 naznaˇcuje, jak by komunikace mohla vypadat pˇri pouˇzit´ı architektury multi-master pro dva servery, kdy je kaˇzd´ y server obsluhován vlastn´ım synchronizaˇcn´ım procesem. Tato architektura je ovˇsem znaˇcnˇe nev´ yhodná. Stále mus´ıme k serveru pˇristupovat komunikaˇcn´ım rozhran´ım WebDAV, kdy je pˇri lokáln´ı komunikaci sice sn´ıˇzeno zpoˇzdˇen´ı, ale za cenu nutnosti implementace distribuovaného algoritmu shody a udrˇzován´ı vˇsech proces˚ u aktivn´ıch. Nav´ıc bychom ztratili v´ yhodu protokolu WebDAV - nen´ı blokován na firewallech. Toto ˇreˇsen´ı by mˇelo smysl, pokud by byla synchronizace pˇr´ımo uvnitˇr Kerio Connect serveru, kdy by odpadla lokáln´ı WebDAV komunikace. Závˇerem tedy je, ˇze pro návrh modelu synchronizace bude pouˇzita architektura optimistické replikace single-master.

4.4

Konzistence

D˚ uleˇzitou roli pˇri návrhu modelu synchronizace hraje zvolen´ y model konzistence. Volba modelu konzistence je vˇzdy kompromis mezi tˇremi ukazateli - dostupnost, striktn´ı konzistence a tolerance v´ ypadk˚ u s´ıtˇe - tzv. The CAP theorem [Gilbert].

Obrázek 4.3: The CAP theorem Obrázek 4.3 zobrazuje tˇri vyjmenované ukazatele vytváˇrej´ıc´ı moˇzné skupiny model˚ u 29


Pravdivostn´ı datab´ aze

konzistence. Zelené varianty jsou modely, které lze dosáhnout na u ´kor tˇret´ıho ukazatele. Systém splˇ nuj´ıc´ı vˇsechny tˇri ukazatele (oranˇzové pole) nen´ı moˇzné sestavit, jelikoˇz pokud toleruje v´ ypadky s´ıtˇe a je striktnˇe konzistentn´ı, nem˚ uˇze b´ yt pˇri v´ ypadku dostupn´ y. Ukazatel, ze kterého mus´ıme vycházet, je dostupnost, protoˇze d˚ uraz je kladen hlavnˇe na dostupnost Kerio Connect server˚ u. Nav´ıc ani nen´ı moˇzné do chodu serveru zasahovat, protoˇze komunikaˇcn´ı rozhran´ı WebDAV to neumoˇzn ˇuje. Je tedy moˇzné volit mezi striktn´ı konzistenc´ı a toleranc´ı v´ ypadk˚ u. Striktn´ı konzistence nen´ı poˇzadována a nav´ıc by j´ı nebylo moˇzné dosáhnout. Je proto mnohem optimálnˇejˇs´ı tolerovat v´ ypadky a dopustit, ˇze na v´ıce serverech nebudou aktuáln´ı data, neˇz ˇze na ˇza´dném serveru nebudou aktuáln´ı data. Jako druh´ y nejvhodnˇejˇs´ı ukazatel se proto jev´ı právˇe tolerance v´ ypadk˚ u. Z obrázku 4.3 je moˇzné vyˇc´ıst, ˇze jsme zvolili model AP a za tento model lze povaˇzovat eventual consistency. Synchronizace bude tedy dodrˇzovat eventual consistency, bude tolerovat obˇcasnou nekonzistenci, ale s v´ yhodami lepˇs´ı ˇskálovatelnosti a propustnosti celého systému.

4.5

Pravdivostn´ı datab´ aze

Jelikoˇz nen´ı moˇzné zasahovat do prostˇred´ı Kerio Connect server˚ u, které neposkytuj´ı dostateˇcné informace pro synchronizaci, je nutné informace ukládat do lokáln´ı databáze pravdivostn´ı databáze. Ukládán´ım pr˚ ubˇeˇzn´ ych informac´ı do perzistentn´ı databáze se zv´ yˇs´ı nejen efektivita, ale i spolehlivost synchronizace, protoˇze pˇri pˇreruˇsen´ı synchronizaˇcn´ıho procesu budou dostupné p˚ uvodn´ı informace o synchronizaci. Databáze slouˇz´ı zejména pro u ´ˇcely párován´ı. Kaˇzd´ y zdroj m˚ uˇze b´ yt na kaˇzdém serveru uloˇzen pod jin´ ym jménem a UID, je proto nutné párovat explicitnˇe s vyuˇzit´ım databáze (viz sekce 4.9).

Obrázek 4.4: Model databáze pro podporu synchronizace Model na obrázku 4.4 je relaˇcn´ı databáze o tˇrech tabulkách, které uchovávaj´ı dostateˇcné a pˇresto minimáln´ı mnoˇzstv´ı informac´ı pro efektivn´ı algoritmus synchronizace Kerio Connect server˚ u protokolem WebDAV. Cel´ y koncept databáze bude postupnˇe vysvˇetlen v následuj´ıc´ıch sekc´ıch.

30


4.5.1

Synchronizace

Lokace

V tabulce Location jsou uchovávány konfigurace vˇsech server˚ u, které budou mezi sebou replikovány. Server je identifikován základn´ı URI, na které se nacház´ı koˇrenová kolekce, a uˇzivatelsk´ ym jménem pro pˇr´ıstup na zabezpeˇcen´ y server.

4.5.2

Objekt

Tabulka Object obsahuje slouˇcenou stromovou reprezentaci vˇsech zdroj˚ u, které jsou na vˇsech replikách, tak jak by repliky mˇely vypadat v konzistentn´ım stavu. Kolekce jsou od ostaty je nastaven na hodnotu 1. n´ıch zdroj˚ u odliˇseny atributem is collection, kter´ Stromová reprezentace je zajiˇstˇena algoritmem pro reprezentaci stromu v databázi materializovanou cestou s atributy path udávaj´ıc´ı název rodiˇcovské kolekce a depth reprezentuj´ıc´ı hloubku vnoˇren´ı zdroje. Tento algoritmus má sloˇzitost v´ ybˇeru celého stromu O(1) a sloˇzitost u ´pravy stromu O(N ). Jelikoˇz operace move nen´ı detekována protokolem WebDAV, u ´pravu stromu stejnˇe nevyuˇzijeme, coˇz znamená, ˇze je velice efektivn´ı pro reprezentaci stromu oproti napˇr´ıklad adjacency list algoritmu.

4.5.3

Kopie

D´ıky eventual consistency a moˇznosti v´ ypadku server˚ u nem˚ uˇzeme vycházet z pˇredpokladu, ˇze obsah vˇsech replik je totoˇzn´ y. Nem˚ uˇzeme proto pouˇz´ıt pouze tabulku Object pro reprezentaci stavu synchronizace. Potˇrebujeme i informace o tom, na jakém serveru je jak´ y zdroj v jakém stavu pˇr´ıtomn´ y. K tomuto u ´ˇcelu slouˇz´ı tabulka Copy, která reprezentuje aktuáln´ı stav vˇsech server˚ u uloˇzen´ ych v tabulce Location v˚ uˇci celkové struktuˇre v tabulce Object. Záznamy jsou pevnˇe svázány se zdroji na serverech atributem UID, kter´ y je jednoznaˇcnˇe identifikuje na daném serveru. Pokud server neobsahuje záznam Copy, nen´ı dan´ y zdroj na serveru zreplikován.

4.6 4.6.1

Synchronizace Synchronizace kolekce

Základn´ım procesem synchronizace je synchronizace jedné kolekce mezi vˇsemi replikami. ´ Na zaˇcátku známe pouze URI kolekce, která existuje na vˇsech serverech. Ukolem synchronizace je kolekci prozkoumat na vˇsech replikách a zreplikovat jej´ı obsah. Následuj´ıc´ı pseudokód naznaˇcuje, jak synchronizace jedné kolekce prob´ıhá.

31


1 2 3 4 5 6 7 8 9 10 11 12

Synchronizace

Pro vˇsechny servery { Detekuj zmˇenˇené kolekce pro collblob hierarchical Detekuj zmˇenˇené dokumenty pro collblob shallow } Pokud je poˇcet detekovan´ ych zmˇen > 0 { Pro vˇsechny kopie s pˇr´ıznakem copy.is remove = 1 { Smaˇz kopii na serveru } Pro vˇsechny neaktu´ aln´ı objekty seˇrazené podle object.depth vzestupnˇe { Aktualizuj objekt na serverech } }

Algoritmus je rozdˇelen do dvou fáz´ı. Prvn´ı fáz´ı je detekce zmˇen a struktury kolekce na vˇsech serverech, abychom spárovali veˇsker´ y obsah a vyhnuli se tak nechtˇené duplikaci (viz sekce 3.6.1). Pokud bychom totiˇz prohledali nejprve jeden server, obsah zreplikovali a poté aˇz dalˇs´ı server, pˇri opakované pomalé synchronizaci bychom nechtˇenˇe duplikovali shodn´ y obsah mezi servery.

Obrázek 4.5: Detekce struktury kolekce koˇren Obrázek 4.5 naznaˇcuje, jak m˚ uˇze prob´ıhat slouˇcen´ı obsahu dvou stejn´ ych kolekc´ı na dvou replikách s rozd´ıln´ ym obsahem. Podrobnˇeji se detekc´ı zmˇen v kolekc´ıch zab´ yvá sekce 4.8. V druhé fázi algoritmu prob´ıhá aktualizace detekovan´ ych zmˇen na jednotlivé repliky. Prioritu maj´ı operace smazán´ı a po jejich dokonˇcen´ı následuj´ı operace pˇridán´ı nebo modifikace. Aktualizac´ı replik se zab´ yvá podrobnˇeji sekce 4.11. Data jsou v prvn´ı fázi perzistentnˇe uloˇzena do lokáln´ı pravdivostn´ı databáze tak, aby pˇri chybˇe nebo selhán´ı v dobˇe aktualizace obsahu nedoˇslo ke ztrátˇe detekovan´ ych zmˇen a tak ztrátˇe proveden´ ych operac´ı.

4.6.2

Pomal´ a synchronizace

Pˇri prvn´ım spuˇstˇen´ı synchronizace je databáze synchronizaˇcn´ıho procesu prázdná a známe pouze koˇrenovou kolekci celé synchronizace, je tedy nutné prozkoumat strukturu replik, které budeme synchronizovat. Následuj´ıc´ı pseudokód popisuje algoritmus pomalé synchronizace.

32


Synchronizace

1 Vytvoˇr objekt a kopie pro koˇrenov´ e sloˇzky vˇsech server˚ u 2 Dokud existuje kopie kolekce s copy.last searched at = −1 { 3 Vyber prvn´ı kolekci s nejniˇzˇs´ım object.depth 4 Synchronizuj kolekci 5 }

Algoritmus pracuje iterativnˇe a postupuje do hloubky stromu kolekc´ı. Nejprve jsou vytvoˇreny prázdné kopie pro koˇrenové sloˇzky server˚ u, jelikoˇz pˇredpokládáme, ˇze koˇrenové sloˇzky existuj´ı, jinak synchronizace nemá smysl. Následnˇe je vybrána kolekce na nejvyˇsˇs´ı u ´rovni, která jeˇstˇe nebyla synchronizována, jelikoˇz má neinicializovan´ y ˇcas posledn´ıho hledán´ı copy.last searched at = −1. Kolekce je synchronizována podle algoritmu v sekci 4.6.1 a pokud byly v kolekci nalezeny vnoˇrené kolekce, algoritmus je najde jako jeˇstˇe neprohledané a provede synchronizaci. T´ımto zp˚ usobem algoritmus pokraˇcuje, dokud vˇsechny kolekce na vˇsech replikách nejsou prohledány a sesynchronizovány, ˇc´ımˇz vytvoˇr´ı kompletn´ı strom zdroj˚ u a uvede repliky do konzistentn´ıho stavu.

4.6.3

Zmˇ enov´ a synchronizace

Po prvn´ım proveden´ı pomalé synchronizace je inicializována pravdivostn´ı databáze a je známa struktura vˇsech replik, staˇc´ı tedy provádˇet o poznán´ı rychlejˇs´ı zmˇenovou synchronizaci. 1 Nastav copy.last searched at := −1 pro vˇsechny kolekce 2 Dokud existuje kopie kolekce s copy.last searched at = −1 { 3 Vyber prvn´ı kolekci s nejniˇzˇs´ım object.depth 4 Synchronizuj kolekci 5 }

Algoritmus je v podstatˇe shodn´ y s pomalou synchronizac´ı s t´ım rozd´ılem, ˇze je na zaˇcátku m´ısto vytváˇren´ı koˇrenové kolekce resetován ˇcas posledn´ıho hledán´ı vˇsech kolekc´ı, tak aby doˇslo k prohledán´ı vˇsech kolekc´ı stromu. Rozd´ıl oproti pomalé synchronizaci je v tom, ˇze jiˇz známe stav replik a je moˇzné detekovat pouze nové zmˇeny oproti pˇredchoz´ı synchronizaci. V´ıce o detekci zmˇen v sekci 4.8.

4.6.4

Aktivn´ı synchronizace

Protokol WebDAV umoˇzn ˇuje provádˇet aktivn´ı synchronizaci metodou SUBSCRIBE, coˇz umoˇzn ˇuje efektivnˇe detekovat nové zmˇeny na replikách. Nejdˇr´ıve je nutné se k odbˇeru zmˇen pˇrihlásit metodou SUBSCRIBE a protoˇze je aktivn´ı synchronizace pomˇernˇe drahá, je nutné omezit kolekce, ke kter´ ym se budeme pˇrihlaˇsovat, na ty, u kter´ ych to má opravdu smysl: • Kolekce obsahuj´ıc´ı kalendáˇrové události a u ´koly, jelikoˇz tyto dokumenty jsou ˇcasto modifikovány a je vhodné pro nˇe zavést aktivn´ı synchronizaci. • Kolekce na prvn´ı u ´rovni, protoˇze je k nim ˇcasto pˇristupováno a jejich obsah je nejviditelnˇejˇs´ı.

33


Nedostupnost server˚ u

Pˇrihláˇsen´ı je jednoznaˇcnˇe identifikováno celoˇc´ıseln´ ym Subscription-ID, které je uloˇzeno ke kaˇzdé kopii kolekce v databázi. Pro detekci zmˇenˇen´ ych kolekc´ı je pouˇzita metoda POLL, jelikoˇz je podstatnˇe jednoduˇsˇs´ı na implementaci a nevyˇzaduje komunikaci smˇerem k synchronizaˇcn´ımu procesu. Umoˇzn ˇuje také aktivn´ı synchronizaci provést v dobˇe, kdy má synchronizaˇcn´ı proces dostatek zdroj˚ u k jej´ı obsluze. Synchronizaˇcn´ı proces jednoduˇse poˇsle poˇzadavek POLL se vˇsemi Subscription-ID, které má uloˇzeny v databázi, a server v odpovˇedi vrát´ı, které z nich byly zmˇenˇeny. Zmˇenˇené kolekce jsou synchronizovány tak, jak je popsáno v sekci 4.6.1.

4.7

Nedostupnost server˚ u

Jelikoˇz v pr˚ ubˇehu synchronizace m˚ uˇze doj´ıt k v´ ypadku nebo chybˇe na libovolném serveru, y nab´ yvá hodnoty obsahuje tabulka Location atribut location.temporary unavailable, kter´ 1, pokud je server momentálnˇe nedostupn´ y. Tento server je vynechán z jakékoliv aktivity synchronizaˇcn´ıho procesu a je otestován na dostupnost aˇz v dalˇs´ı iteraci synchronizace. T´ımto zp˚ usobem se sn´ıˇz´ı zátˇeˇz v podobˇe zbyteˇcn´ ych dotaz˚ u na nedostupn´ y server, které by stejnˇe skonˇcily ne´ uspˇeˇsnˇe. Tabulka nav´ıc obsahuje ˇc´ıtaˇc location.f ailures obsahuj´ıc´ı celkov´ y poˇcet v´ ypadk˚ u, d´ıky ˇcemuˇz je moˇzné zjistit, jak´ y server je nespolehliv´ y. K v´ ypadku serveru dojde kdykoliv, kdyˇz se nepodaˇr´ı se serverem spojit protokolem WebDAV, autorizace se nezdaˇr´ı nebo server odpov´ı neˇcekanou odpovˇed´ı (napˇr´ıklad koˇrenová kolekce neexistuje). Zabrán´ı se t´ım propagaci doˇcasnˇe chybné nekonzistence z nedostupného serveru na ostatn´ı repliky.

4.8

Detekce zmˇ en

K detekci zmˇen disponuje WebDAV metodou SEARCH, která d´ıky funkci Manifest of collection umoˇzn ˇuje detekovat zmˇeny v ˇclenech kolekce provedené od posledn´ı synchronizace. Implementace této metody produktem Kerio Connect má vˇsak jistá omezen´ı. Metoda umoˇzn ˇuje vyhledávat pouze oddˇelenˇe zmˇeny v kolekc´ıch nebo dokumentech a je moˇzné vyhledávat pouze v pˇr´ım´ ych ˇclenech kolekce. Pro detekci zmˇenˇen´ ych kolekc´ı pouˇzijeme metodu SEARCH s SQL dotazem 1 SELECT ∗ 2 FROM SCOPE (’SHALLOW TRAVERSAL OF ””’); 3 WHERE ”DAV:isfolder” = false

a pro detekci zmˇenˇen´ ych dokument˚ u pouˇzijeme metodu s SQL dotazem 1 SELECT ∗ 2 FROM SCOPE (’HIERARCHICAL TRAVERSAL OF ””’); 3 WHERE ”DAV:isfolder” = true AND ”DAV:ishidden” = false

Server v odpovˇedi vrac´ı seznam vˇsech zmˇenˇen´ ych zdroj˚ u oznaˇcen´ ych jedn´ım ze tˇr´ı pˇr´ıznak˚ u - new, change a delete. Nalezené zmˇeny jsou vráceny od posledn´ıho stavu collblob, kter´ y je pˇredán v poˇzadavku na hledán´ı metodou SEARCH. Pˇri pomalé synchronizaci je zˇrejmé, ˇze collblob je prázdn´ y, jelikoˇz neznáme stav datového u ´loˇziˇstˇe, takˇze vˇsechny poloˇzky seznamu maj´ı pˇr´ıznak new - zmˇena od vytvoˇren´ı u ´loˇziˇstˇe. Vˇsechny zmˇeny jsou 34


Detekce zmˇen

zpracovány a uloˇzeny do pravdivostn´ı databáze, ze které probˇehne v dalˇs´ı fázi synchronizace aktualizace server˚ u podle nalezen´ ych zmˇen. Obecnˇe pˇredpokládáme, ˇze nahláˇsené pˇr´ıznaky jsou nespolehlivé a jsou vˇzdy ovˇeˇreny v˚ uˇci lokáln´ı databázi. Po u ´spˇeˇsném prohledán´ı kolekce je uloˇzen vrácen´ y nov´ y stav kolekce collblob do atriych kolekc´ı a copy.collblob shallow butu copy.collblob hierarchical pro hledán´ı zmˇenˇen´ pro hledán´ı zmˇenˇen´ ych dokument˚ u tak, aby pˇri pˇr´ıˇst´ım hledán´ı byly nalezeny pouze nové neaplikované zmˇeny. Stejnˇe tak je aktualizována ˇcasová znaˇcka posledn´ıho u ´spˇeˇsného hledán´ı copy.last searched at.

4.8.1

Nov´ a kolekce

Pokud v odpovˇedi nalezneme kolekci s pˇr´ıznakem new, vyhledáme, zda jiˇz neexistuje objekt se stejnou URI - kolekce jsou jednoznaˇcnˇe identifikovány relativn´ı URI. Pokud tento objekt existuje, znamená to, ˇze kolekce jiˇz byla detekována na jiném serveru a jedná se o spárován´ı s jinou shodnou kolekc´ı. V opaˇcném pˇr´ıpadˇe, kdy objekt neexistuje, je vytvoˇren nov´ y objekt.

Obrázek 4.6: Stavov´ y diagram algoritmu zpracován´ı nové kolekce K objektu se poté vyhledá kopie pro server, na kterém probˇehlo hledán´ı. Pokud je kopie kolekce nalezena, je nejprve porovnán jej´ı resourcetag, znaˇc´ıc´ı verzi zdroje na serveru. Pokud se resourcetag zmˇenil, jedná se o ˇspatnˇe oznaˇcenou zmˇenu (new m´ısto change), napˇr´ıklad pˇri hledán´ı bez pouˇzit´ı collblob, a je vyvolána obsluha zmˇenˇené kolekce. Pokud se ovˇsem resourcetag nezmˇenil, jde o faleˇsnou zmˇenu popsanou v sekci 4.8.6. Posledn´ı variantou je neexistuj´ıc´ı kopie, kdy je vytvoˇrena nová kopie pro danou repliku. Obrázek 4.6 zobrazuje diagram pro v´ yˇse popsan´ y algoritmus.

4.8.2

Nov´ y dokument

Pro nov´ y dokument s pˇr´ıznakem new je na rozd´ıl od kolekc´ı nejprve hledána kopie objektu pro zdrojov´ y server podle UID - dokumenty jsou jednoznaˇcnˇe identifikovány prostˇrednic35


Detekce zmˇen

tv´ım UID. Jestliˇze tuto kopie nalezneme, jedná se stejnˇe jako u nové kolekce o ˇspatnˇe oznaˇcenou zmˇenu (new m´ısto change).

Obrázek 4.7: Stavov´ y diagram algoritmu zpracován´ı nového dokumentu Pokud se ovˇsem kopii nepodaˇr´ı naj´ıt, je nutné zjistit, zda jiˇz stejn´ y dokument nebyl nalezen na jiném serveru. Pokus´ıme se tedy spárovat dokument s objektem a pokud se nám to podaˇr´ı, vytvoˇr´ıme pro nˇej novou kopii. Pokud se dokument spárovat nepodaˇr´ı, je vytvoˇren nov´ y objekt i nová kopie, viz diagram na obrázku 4.7.

4.8.3

Zmˇ enˇ en´ a kolekce

Pˇri akci nad kolekc´ı s pˇr´ıznakem change by se mˇelo jednat o zmˇenu jiˇz existuj´ıc´ı kolekce. Pokus´ıme se tedy naj´ıt objekt i kopii kolekce a pokud alespoˇ n jeden záznam nen´ı nalezen, je akce pˇresmˇerována na akci nová kolekce, jelikoˇz nejsp´ıˇse doˇslo k dˇr´ıvˇejˇs´ımu vynechán´ı akce new nebo chybnému pˇr´ıznaku ze strany Kerio Connect serveru. Jestliˇze jsou ovˇsem objekt i kopie nalezeny, jedná se zcela jistˇe o modifikovanou kolekci. M˚ uˇze se ovˇsem stát, ˇze kolekce byla nahrazena jinou kolekc´ı se stejn´ ym URI. Zkontrolujeme tedy jeˇstˇe UID a pokud nejsou shodné, kolekci nejdˇr´ıve smaˇzeme pro ostatn´ı servery a poté ji opˇet pˇridáme ze zdrojového serveru s nov´ ymi vlastnostmi, ˇc´ımˇz je pˇresunutá kolekce propagována na ostatn´ı repliky. Pokud jsou UID shodné, nastav´ıme pouze novou verzi modifikace podle algoritmu popsaného v sekci 4.10. V´ yˇse zm´ınˇen´ y algoritmus je schématicky zobrazen na diagramu 4.8.

4.8.4

Zmˇ enˇ en´ y dokument

Pokud je detekována zmˇena dokumentu, je nalezena kopie dokument podle UID. Jestliˇze nen´ı kopie nalezena, je situace podobná jako u nenalezené zmˇenˇené kolekce a akce je pˇresmˇerována na nov´ y dokument. Pokud je ovˇsem dokument nalezen, je nutné porovnat URI v kopii a na serveru. M˚ uˇze se totiˇz stát, ˇze dokument byl pˇresunut do jiné kolekce a je tedy nutné ho pˇresunout i na ostatn´ıch replikách. Stejnˇe jako u kolekce je v takovém 36


Detekce zmˇen

Obrázek 4.8: Stavov´ y diagram algoritmu zpracován´ı zmˇenˇené kolekce pˇr´ıpadˇe dokument smazán pro ostatn´ı servery a vytvoˇren nov´ y ze zdrojového serveru, ˇc´ımˇz se zajist´ı jeho pˇresun na ostatn´ıch replikách. Na druhou stranu m˚ uˇze m´ıt dokument stejn´ y resourcetag, pˇriˇcemˇz se jedná o faleˇsnou zmˇenu popsanou v sekci 4.8.6. Posledn´ım pˇr´ıpadem je standardn´ı zmˇena, kdy URI je shodná a resourcetag jin´ y. Pro tento pˇr´ıpad nastav´ıme pouze novou verzi modifikace podle algoritmu popsaného v sekci 4.10. Popsan´ y algoritmus je schématicky zobrazen na diagramu 4.9.

Obrázek 4.9: Stavov´ y diagram algoritmu zpracován´ı zmˇenˇeného dokumentu

4.8.5

Smazan´ y zdroj

Algoritmus smazán´ı je pro kolekce i dokumenty shodn´ y. Vˇsem kopi´ım daného zdroje pro vˇsechny servery je v pravdivostn´ı databázi nastaven pˇr´ıznak copy.is remove na hodnotu 1. Akce smazán´ı je vyvolána i v pˇr´ıpadˇe, kdy metoda SEARCH vrac´ı odpovˇed´ı 404 Not found - kolekce nebyla nalezena, tud´ıˇz byla smazána. To ale plat´ı pouze v pˇr´ıpadˇe, kdy 37


Párován´ı zdroj˚ u

kolekce nen´ı koˇrenovou kolekc´ı pro dan´ y server, v takovém pˇr´ıpadˇe je server oznaˇcen jako doˇcasnˇe nedostupn´ y, protoˇze koˇrenová kolekce nem˚ uˇze b´ yt smazána.

4.8.6

Detekce faleˇ sn´ ych zmˇ en

V´ yznamnou komplikac´ı pˇri detekci zmˇen je tzv. faleˇsná zmˇena. Faleˇsná zmˇena nastane v pˇr´ıpadˇe, kdy je zdroj zmˇenˇen na replikách synchronizaˇcn´ım procesem. V dalˇs´ım zavolán´ı metody SEARCH je totiˇz tato zmˇena také nahláˇsena. V naivn´ı implementaci by to zp˚ usobilo nekoneˇcné aktualizace, protoˇze pˇri jakékoliv aktualizaci serveru by byla zmˇena nahláˇsená zpˇet a provedena na jiné replice a opˇet nahláˇsena. Je proto nutné faleˇsné zmˇeny detekovat. Pˇri kaˇzdé aktualizaci je z´ıskán resourcetag zmˇenˇeného zdroje a uloˇzen do databáze. Pˇri dalˇs´ım pouˇzit´ı metody SEARCH je resourcetag porovnán a pokud je shodn´ y, je daná zmˇena ignorována. U kolekc´ı je nutné detekovat faleˇsné zmˇeny pouze u nov´ ych kolekc´ı, zmˇenˇené kolekce nejsou nikdy faleˇsnˇe nahláˇseny. T´ımto jednoduch´ ym algoritmem jsou spolehlivˇe odliˇseny faleˇsné zmˇeny od skuteˇcn´ ych zmˇen.

4.9

P´ arov´ an´ı zdroj˚ u

Jak jiˇz bylo naznaˇceno v sekci 4.6.1, je nutné pˇri detekci zmˇen v kolekc´ıch párovat stejné zdroje z r˚ uzn´ ych replik, tak aby nedocházelo k nechtˇen´ ym duplikac´ım obsahu. Párován´ı stejn´ ych kolekc´ı je intuitivnˇe ˇreˇseno pouˇzit´ım URI kolekce, jelikoˇz stejné kolekce na r˚ uzn´ ych replikách maj´ı stejné URI - jsou um´ıstˇené na stejné pozici ve stromˇe a maj´ı shodn´ y název. Párován´ı dokument˚ u je sloˇzitˇejˇs´ı problém, jelikoˇz je nelze párovat intuitivnˇe jako kolekce. Stejné dokumenty mohou na r˚ uzn´ ych serverech b´ yt uloˇzeny pod jin´ ymi názvy a jejich UID se také liˇs´ı, jelikoˇz je pˇridˇelováno replikami a je urˇceno pouze pro ˇcten´ı. Pro dokumenty je tedy nutné navrhnout sofistikovanˇejˇs´ı algoritmus. Ideáln´ı je pouˇzit´ı obsahu dokumentu, jelikoˇz pokud jsou dokumenty stejné, je stejn´ y i jejich obsah. K tomuto u ´ˇcelu je pro kaˇzd´ y dokument poˇc´ıtán hash ˇretˇezec MD5 funkc´ı, kter´ y je následnˇe uloˇzen pod atribut object.hash, jelikoˇz je pro vˇsechny kopie zdroje stejn´ y. Hash ˇretˇezec je kompaktnˇejˇs´ı reprezentace obsahu neˇz cel´ y obsah, je mnohem rychleji porovnáván a pravdˇepodobnost shodného hashe je zanedbatelná. Hash ˇretˇezec je moˇzné jednoduˇse generovat u nestrukturovan´ ych dokument˚ u z celého obsahu, jelikoˇz je obsah dokumentu stál´ y. Situace se ovˇsem komplikuje u strukturovan´ ych dokument˚ u, které obsahuj´ı pro kaˇzdou repliku specifické identifikátory a ˇcasové znaˇcky. Následuj´ıc´ı seznam pˇredepisuje, jaké pouˇz´ıvané atributy je nutné ze strukturovan´ ych dokument˚ u vynechat pˇred generován´ım hashe: • UID - identifikátor dokumentu stejn´ y jako vlastnost UID, • REV - ˇcasová znaˇcka modifikace dokumentu, • X-NEXT-ALARM a blok VALARM - ˇcas upozornˇen´ı na u ´kol nebo kalendáˇrovou událost, kter´ y se ˇcasto mˇen´ı a je proto vhodné ho vynechat, aby nezp˚ usoboval faleˇsné duplikace,

38


Párován´ı zdroj˚ u

• PERCENT-COMPLETE a STATUS - speciáln´ı vlastnosti u ´kolu, které se ˇcasto mˇen´ı a je proto vhodné je vynechat. Pro sn´ıˇzen´ı pravdˇepodobnosti ˇspatného spárován´ı pˇri vygenerován´ı stejného hash ˇretˇezce pro r˚ uzné dokumenty, je nav´ıc párován´ı provádˇeno s pouˇzit´ım URI rodiˇcovské kolekce a typu dokumentu. Spárován´ı dokument˚ u t´ımto algoritmem je spolehlivé, má ovˇsem znaˇcnou nev´ yhodu. Pro v´ ypoˇcet hash ˇretˇezce je nutné stáhnout cel´ y obsah dokumentu na lokáln´ı disk, coˇz zp˚ usobuje zátˇeˇz jak na stranˇe serveru, tak na stranˇe synchronizaˇcn´ıho procesu. Ideáln´ım ˇreˇsen´ım by byla moˇznost uloˇzit na repliku vlastn´ı synchronizaˇcn´ı ID, kter´ ym by se dokumenty párovaly, nebo alespoˇ n poskytovat pasivn´ı vlastnost hash, kde by byl hash ˇretˇezec jiˇz spoˇc´ıtán a pˇrenesen pouze jako krátk´ y textov´ y ˇretˇezec. Bohuˇzel nen´ı moˇzné do Kerio Connect serveru zasahovat a tak v´ yˇse zm´ınˇen´ y algoritmus je nejlepˇs´ım spolehliv´ ym ˇreˇsen´ım.

4.9.1

Konflikt tˇ r´ıd kolekc´ı

Pˇri párován´ı kolekc´ı m˚ uˇze doj´ıt k tomu, ˇze kolekce se stejnou URI, a tud´ıˇz i stejn´ ym jménem, m˚ uˇze b´ yt detekována na v´ıce replikách s rozd´ılnou tˇr´ıdou. Rozd´ılné tˇr´ıdy kolekc´ı vyvolaj´ı konflikt, jelikoˇz zcela jistˇe kaˇzdá z kolekc´ı obsahuje r˚ uzné vnitˇrn´ı ˇcleny, a nen´ı tedy moˇzné tyto kolekce synchronizovat. Konflikt je nutné vyˇreˇsit automaticky, protoˇze nelze poˇzádat uˇzivatele o v´ ybˇer správné tˇr´ıdy kolekce. Prvn´ı nalezená kolekce je uznána jako správná a nekonfliktn´ı, coˇz znamená, ˇze tˇr´ıda objektu i kopie jsou shodné (object.container class = copy.class). Jakmile je s objektem spárována jiná kolekce, jej´ıˇz tˇr´ıda je rozd´ılná (object.container class 6= copy.class), je oznaˇcena pro synchronizaˇcn´ı proces jako konfliktn´ı: • V konfliktn´ıch kolekc´ıch se nehledaj´ı zmˇeny, protoˇze stejnˇe nen´ı moˇzné je replikovat do nekonfliktn´ıch kolekc´ı, • Do konfliktn´ıch kolekc´ı se nereplikuj´ı ˇclenové nekonfliktn´ıch kolekc´ı, protoˇze nen´ı jisté, zda tam patˇr´ı, • Operace odstranˇen´ı konfliktn´ı i nekonfliktn´ı kolekce se propaguje pouze na kopie stejné tˇr´ıdy, protoˇze se jedná o odstranˇen´ı konfliktu. Konflikt tˇr´ıd kolekc´ı je vyˇreˇsen, jakmile je odstranˇena kolekce s konfliktn´ı tˇr´ıdou. Odstranˇen´ı se nepropaguje na nekonfliktn´ı kolekce a tak je konfliktn´ı kolekce ihned po odstranˇen´ı nahrazena kolekc´ı nekonfliktn´ı. Pokud dojde k odstranˇen´ı nekonfliktn´ı kolekce a zároveˇ n existuj´ı konfliktn´ı kolekce, je tˇr´ıda objektu object.container class pˇrepsána tˇr´ıdou prvn´ı konfliktn´ı kolekce, ˇc´ımˇz je konflikt odstranˇen a kolekce zreplikována. Jin´ ym moˇzn´ ym ˇreˇsen´ım by bylo navrhnutou konfliktn´ı kolekci odstranit a nahradit nekonfliktn´ı, pˇr´ıpadnˇe konfliktn´ı kolekci pˇrejmenovat a t´ım uvolnit m´ısto pro kolekci nekonfliktn´ı. Obˇe ˇreˇsen´ı vˇsak zasahuj´ı do struktury server˚ u bez pˇriˇcinˇen´ı uˇzivatele, coˇz je nevhodné chován´ı, které m˚ uˇze p˚ usobit jako chybné. Navrˇzen´ y algoritmus poˇc´ıtá i se vznikem v´ıcenásobného konfliktu, kdy v´ıce jak dvˇe tˇr´ıdy jsou pˇr´ıtomny nad stejnou kolekc´ı, a um´ı jej vyˇreˇsit. Podobn´ y konflikt nen´ı u dokument˚ u moˇzn´ y, jelikoˇz párován´ı prob´ıhá i podle typu dokumentu. 39


4.10

Poˇrad´ı operac´ı

Poˇ rad´ı operac´ı

Servery u kaˇzdého zdroje ukládaj´ı reáln´ y ˇcas posledn´ı modifikace - vlastnost Last-modified je tedy moˇzné urˇcit happend-before relaci s pouˇzit´ım syntaktického plánován´ı reáln´ ymi hodinami, jak je popsáno v sekci 3.4.1. Servery ovˇsem nemus´ı b´ yt ˇcasovˇe synchronizovány a jejich reálné hodiny se mohou rozcházet. Neexistuje ovˇsem jiná metoda pro urˇcen´ı happend-before relace neˇz pouˇzit´ı reáln´ ych hodin, proto mus´ıme metodu pouˇz´ıt, i kdyˇz nemus´ı b´ yt vˇzdy pˇresná. I pˇresto je stále lepˇs´ı neˇz urˇcovat happend-before relaci náhodnˇe, coˇz v´ıme, ˇze pˇresné nebude nikdy. Pro plánován´ı m˚ uˇzeme pouˇzit´ı i sémantické plánován´ı popsané v sekci 3.4.2. Operace provedené nad r˚ uzn´ ymi zdroji jsou na sobˇe nezávislé, protoˇze zdroje se navzájem neovlivˇ nuj´ı. Tyto operace proto m˚ uˇzeme oznaˇcit za komutativn´ı a provádˇet je v libovolném poˇrad´ı. Operace je dále moˇzné ˇradit podle jejich sémantiky - vytvoˇren´ı, u ´prava a smazán´ı. Pro urˇcen´ı poˇrad´ı operac´ı definujeme z v´ yˇse zm´ınˇeného jednoduchá pravidla, kter´ ymi se bude synchronizaˇcn´ı algoritmus ˇr´ıdit: • Operace nad r˚ uzn´ ymi zdroji jsou komutativn´ı a je moˇzné je provést v libovolném poˇrad´ı. • Operace pˇridán´ı bude vˇzdy pˇredcházet operaci u ´pravy nad stejn´ ym zdrojem, protoˇze nen´ı moˇzné upravovat neexistuj´ıc´ı dokument. • Operace smazán´ı bude vˇzdy pˇredcházet operaci u ´pravy nad stejn´ ym zdrojem. Pokud totiˇz bude zdroj smazán, nemá smysl ho pˇredt´ım modifikovat a operace u ´pravy mohou b´ yt vynechány. • Stejné operace u ´pravy nad stejn´ ym zdrojem budou ˇrazeny podle ˇcasov´ ych znaˇcek provedené u ´pravy. • Operace se stejnou ˇcasovou znaˇckou u ´pravy budou seˇrazeny náhodnˇe, protoˇze nen´ı moˇzné dále urˇcit jejich poˇrad´ı. • Operace pˇridán´ı nad stejn´ ym zdrojem nen´ı nutné ˇradit, protoˇze systém je statetransfer a dovoluje provést pouze jednu operaci pˇridán´ı a ostatn´ı operace pˇridán´ı jsou operac´ı u ´pravy. • Operace smazán´ı nad stejn´ ym zdrojem nen´ı nutné ˇradit, protoˇze se opˇet jedná o state-transfer systém, ve kterém je operace smazán´ı provedena pouze jednou. Z v´ yˇse zm´ınˇen´ ych pravidel je moˇzné sestavit deterministické poˇrad´ı vˇsech operac´ı, které se v systému vyskytnou. Aby toto poˇrad´ı bylo persistentn´ı i pˇri v´ ypadku replik a nezdaˇrené aktualizaci, je nutné jej uloˇzit do databáze. A jelikoˇz staˇc´ı pouze ukládán´ı poˇrad´ı operac´ı u ´pravy, nebot’ ostatn´ı operace maj´ı pouze jedno pevné poˇrad´ı, je moˇzné k reprezentaci poˇrad´ı pouˇz´ıt inkrementáln´ı ˇc´ıselné ˇrady - verze, které uloˇz´ıme u kaˇzdé kopie objektu v databázi, ˇc´ımˇz ˇrekneme, v jaké verzi je daná kopie. Poˇrad´ı operac´ı u ´pravy je urˇceno poˇrad´ım verz´ı. Aby bylo moˇzné poznat, co se zmˇenilo od posledn´ı aktualizace, obsahuje objekt dalˇs´ı verzi, která oznaˇcuje posledn´ı zreplikovanou verzi na vˇsech replikách. Pro verze tedy plat´ı následuj´ıc´ı pravidla:

40


Poˇrad´ı operac´ı

• Pokud copyα .version = object.version, kopie zdroje na replice α je aktuáln´ı. • Pokud copyα .version < object.version, kopie zdroje na replice α je zastaralá, jelikoˇz nebyla z d˚ uvod˚ u v´ ypadku nahrána posledn´ı aktualizace. • Pokud copyα .version > object.version, nad kopi´ı zdroje na repliace α byla provedena operace u ´pravy. • Pokud copyα .version > copyβ .version, operace u ´pravy zdroje na replice α byla provedena po u ´pravˇe kopie na replice β. • Pokud ∀copy.version > object.version, ˇzádná z replik nemá aktuáln´ı verzi, jelikoˇz na vˇsech replikách byla provedena u ´prava. Tento jednoduch´ y a pr˚ uhledn´ y systém dvou verz´ı plnˇe pokryje poˇzadavky na poˇrad´ı operac´ı a vyhne se tak nutnosti sloˇzitého uchováván´ı vˇsech proveden´ ych operac´ı pro kaˇzdou repliku. Zacházen´ı s verzemi je názornˇe ukázáno na následuj´ıc´ıch pˇr´ıkladech.

Obrázek 4.10: Novˇe spárovan´ y zdroj pˇri pomalé synchronizaci Obrázek 4.10 ilustruje detekci a spárován´ı tˇr´ı stejn´ ych zdroj˚ u na tˇrech replikách pˇri pomalé synchronizaci pro dokument a kolekci. V horn´ı ˇca´sti obrázku, kde doˇslo ke správnému spárován´ı vˇsech tˇr´ı dokument˚ u, nen´ı nutné operace nijak ˇradit, protoˇze dokumenty mus´ı b´ yt stejné (viz sekce 4.9), a verze je nastavena na 1. Toto ovˇsem neplat´ı pro kolekce, kde nen´ı párován´ı provádˇeno podle obsahu a kolekce nemus´ı b´ yt stejné. Operace pˇridán´ı kolekce pˇri pomalé synchronizaci jsou proto ˇrazeny stejnˇe jako operace u ´pravy. Druhá ˇca´st obrázku 4.10 naznaˇcuje stejnou situaci pro kolekce, kdy verze kolekc´ı jsou seˇrazeny B, A a C podle ˇcas˚ u modifikace stejnˇe jako u operac´ı u ´pravy a na ˇza´dné replice nen´ı aktuáln´ı verze, aby doˇslo k aktualizaci vˇsech replik. Na dalˇs´ım pˇr´ıkladu na obrázku 4.11 je zdroj na vˇsech serverech ve shodné verzi 1. Verze posledn´ı aktualizace uloˇzená v synchronizaˇcn´ım procesu je také 1, tedy objekt je konzistentn´ı. Detekce zmˇen je provádˇena na serverech abecednˇe. Prvn´ı byla detekována zmˇena provedená v 13:01:05 na serveru A, je tedy nastavena verze kopie na hodnotu 2. Jako druhá je detekována zmˇena ze serveru B provedená v 13:01:02, ˇc´ımˇz se ˇrad´ı pˇred zmˇenu provedenou na serveru A. Verze jsou tedy pˇreplánovány tak, aby zmˇena na serveru A byla zaˇrazena za zmˇenu na serveru B. Nakonec je nutné reprezentovat persistentnˇe i operace pˇridán´ı a smazán´ı, které vˇzdy nastanou pouze jednou pro jeden zdroj. Operace pˇridán´ı je reprezentována neexistuj´ıc´ı 41


Aktualizace

Obrázek 4.11: V´ıcenásobná operace u ´pravy vazbou kopie mezi objektem a lokac´ı. Jakmile je tedy detekováno pˇridán´ı, je vytvoˇren objekt a kopie pouze pro lokaci, na které bylo pˇridán´ı detekováno. Operace smazán´ı je indikována nastaven´ım pˇr´ıznaku copy.is remove na hodnotu 1 - jedná se o pouˇzit´ı algoritmu Culling tombstones ze sekce 3.6.2. Jednoduˇse je tak zajiˇstˇena ochrana pˇri v´ ypadku bˇehem provádˇen´ı operac´ı.

4.11

Aktualizace

Po dokonˇcen´ı detekce proveden´ ych operac´ı a urˇcen´ı jejich poˇrad´ı je nutné tyto zmˇeny zreplikovat. Jako prvn´ı se provád´ı operace smazán´ı a po dokonˇcen´ı vˇsech operac´ı smazán´ı jsou provedeny operace pˇridán´ı a u ´pravy zdroj˚ u.

4.11.1

Operace smaz´ an´ı

Zdroj na replice má b´ yt smazán, pokud copy.is remove = 1. Pˇri smazán´ı zdroje na jednom serveru mus´ı doj´ıt ke smazán´ı stejného zdroje na vˇsech serverech. Pokud nav´ıc je zdroj kolekc´ı, je nutné smazat i vˇsechny jej´ı ˇcleny. Naˇstˇest´ı protokol WebDAV umoˇzn ˇuje smazat kolekci a vˇsechny jej´ı ˇcleny jedn´ım poˇzadavkem DELETE, nemus´ıme tedy smazat vˇzdy vˇsechny ˇcleny, ale pouze zdroj, kter´ y byl smazán. Jakmile je kopie s pˇr´ıznakem copy.is remove smazána fyzicky z repliky, je smazána i jej´ı kopie z databáze a pokud neexistuje jiˇz ˇzádná kopie zdroje, je smazán i objekt a zdroj pˇrestane existovat. T´ımto zp˚ usobem se pˇredejde situaci, kdy v dobˇe smazán´ı bude nˇekter´ y ze server˚ u nedostupn´ y a zdroj by se z tohoto serveru obnovil zpˇet na ostatn´ı servery.

4.11.2

Aktualizace zdroje

Zdroj copyα na replice α je povaˇzován za neaktuáln´ı, pokud je splnˇena alespoˇ n jedna z následuj´ıc´ıch podm´ınek: • Pokud neexistuje záznam o copyα , zdroj byl vytvoˇren na jiné replice a mus´ı b´ yt nahrán na repliku α v nejnovˇejˇs´ı verzi. • Pokud ∃copyi .version > object.version a copyi .version > copyα .version, existuje jiná novˇejˇs´ı verze zdroje neˇz copyα a je nutné zdroj na replice α aktualizovat. 42


Aktualizace

• Pokud copyα .version < object.version, je zdroj na replice α neaktuáln´ı kv˚ uli pˇredchoz´ımu v´ ypadku a nezdaˇrilé aktualizaci na verzi object.version.

Obrázek 4.12: Pouˇzit´ı Thomas Write Rule pro aktualizaci Aktualizace zdroj˚ u je provádˇena vˇzdy od koˇrene stromu po listy, aby se pˇredeˇslo pˇr´ıpad˚ um, kdy chceme nahrát na repliku zdroj, ale rodiˇcovská kolekce zat´ım neexistuje, coˇz by vyvolalo chybu a ne´ uspˇeˇsnou replikaci. Aktualizaci je jednoduˇse moˇzné provést s pouˇzit´ım Thomas Write Rule tak, ˇze nalezneme nejnovˇejˇs´ı verzi zdroje, kterou zreplikujeme na ostatn´ı repliky. Tento jednoduch´ y algoritmus je ovˇsem ˇcistˇe state-transfer a neˇreˇs´ı konflikty v operac´ıch, coˇz je v poˇra´dku napˇr´ıklad pro nestrukturované dokumenty, do kter´ ych nen´ı moˇzné zasahovat. Pokud bychom ovˇsem stejn´ y algoritmus pouˇzili pro strukturované dokumenty, napˇr´ıklad kontakt, tak by pˇri zmˇenˇe jména na replice α a telefonu na replice β byla na repliky propagována jen jedna zmˇena a druhá zmˇena by byla zahozena a navrácena do p˚ uvodn´ıho stavu jak zobrazuje obrázek 4.12.

4.11.3

Detekce konflikt˚ u

Abychom vylepˇsili algoritmus uveden´ y v sekci 4.11.2, je nutné implementovat zpracován´ı konflikt˚ u. Detekce konflikt˚ u je jiˇz vyˇreˇsena ukládan´ ymi verzemi. Konflikt nastává, jakmile existuje v´ıce jak jedna verze kopie copy.version vyˇsˇs´ı neˇz object.version, coˇz znamená, ˇze nastala v´ıce neˇz jedna operace u ´pravy zdroje. Obrázek 4.13 pˇredstavuje ˇctyˇri moˇzné pˇr´ıklady stavu verz´ı kopi´ı zdroje. V prvn´ım pˇr´ıpadˇe byla detekována pouze jedna zmˇena a operace nen´ı konfliktn´ı, je moˇzné provést klasick´ y state-transfer pˇrenos nejnovˇejˇs´ı verze. Pˇr´ıpad dvˇe zobrazuje dvˇe konfliktn´ı operace zmˇeny na serverech A a B, kdy je nutné konflikt vyˇreˇsit a zreplikovat slouˇcen´ y zdroj na vˇsechny repliky. Pˇr´ıklad tˇri obsahuje tˇri odliˇsné verze kopi´ı, ale pouze jedna je novˇejˇs´ı neˇz aktuáln´ı verze zdroje, jelikoˇz server C je neaktuáln´ı. V tomto pˇr´ıpadˇe je detekována jen jedna operace u ´pravy, tud´ıˇz nenastal konflikt. V posledn´ım pˇr´ıpadˇe nebyla provedena ˇzádná zmˇena, jen server A je neaktuáln´ı. Opˇet je tedy moˇzné pouˇz´ıt pˇr´ım´ y state-transfer pˇrenos. 43


Aktualizace

Obrázek 4.13: Moˇzné pˇr´ıpady aktualizace verz´ı

4.11.4

Zpracov´ an´ı konflikt˚ u

Jakmile je detekován konflikt, je nutné jej adekvátnˇe vyˇreˇsit, aby nedoˇslo k ˇzádné nebo k co nejmenˇs´ı ztrátˇe proveden´ ych operac´ı. Bohuˇzel WebDAV protokol je ˇcistˇe state-transfer a oznamuje pouze, ˇze zmˇena ve zdroji nastala, ale jiˇz neˇr´ıká, co pˇresnˇe se ve zdroji nebo vlastnostech zdroje zmˇenilo. Mus´ıme proto navrhnout vlastn´ı algoritmus, kter´ y bude umoˇzn ˇovat detekci zmˇen ve zdroj´ıch a bude plnˇe automatick´ y, jelikoˇz nen´ı moˇzné dotazovat se uˇzivatele. Aby bylo moˇzné zjistit, co se ve zdroji zmˇenilo, je nutné m´ıt k dispozici referenˇcn´ı verzi zdroje. Referenˇcn´ı verze je zdroj v p˚ uvodn´ı nezmˇenˇené verzi, neˇz byla na replice zmˇena provedena. Jako referenˇcn´ı zdroj je ideálnˇe moˇzné pouˇz´ıt libovolnou kopii, pro kterou plat´ı copy.version = object.version, ˇcili libovolnou aktuáln´ı a nezmˇenˇenou verzi zdroje. Jakmile je k dispozici referenˇcn´ı zdroj, je moˇzné zjistit, jaké vlastnosti a atributy jsou ve zdroji nové, zmˇenˇené nebo smazané. Vstupem do ˇreˇsitele konflikt˚ u je referenˇcn´ı zdroj a konfliktn´ı zmˇeny a v´ ystupem je slouˇcená verze zdroje. Slouˇcen´ı prob´ıhá iterativnˇe tak, ˇze konfliktn´ı zmˇeny jsou seˇrazeny vzestupnˇe dle verz´ı, a jsou porovnávány s referenˇcn´ı verz´ı zdroje. Na zaˇca´tku je nová verze zdroje stejná jako referenˇcn´ı verze zdroje a postupnˇe jsou detekované zmˇeny propagovány do slouˇcené verze. Mˇejme atribut α, referenˇcn´ı verzi zdroje R, zmˇenˇenou verzi zdroje A a novˇe vytváˇren´ y zdroj M . Nov´ y zdroj M je aktualizován bˇehem ˇreˇsen´ı konflikt˚ u podle následuj´ıc´ıch pravidel: • Pokud R.α = A.α, je atribut nezmˇenˇen a tud´ıˇz vynechán, aby nebyla pˇrepsána jiˇz provedená zmˇena v M . Jeho hodnota se jiˇz v novém zdroji M nacház´ı, jelikoˇz byla zkop´ırována z referenˇcn´ı verze pˇriˇrazen´ım na zaˇca´tku. • Pokud R.α 6= A.α, je atribut zmˇenˇen a pˇrepsán v novˇe vytváˇreném zdroji M.α := A.α. Pokud bude atribut zmˇenˇen i v dalˇs´ı verzi, bude hodnota opˇet pˇrepsána. • Pokud ∃R.α a @A.α, byl atribut odstranˇen a je odstranˇen i z vytváˇreného zdroje M . Pokud bude v dalˇs´ı verzi zdroje atribut zmˇenˇen, bude znovu pˇridán, jelikoˇz 44


Aktualizace

smazan´ y atribut znamená pro uˇzivatele nastaven´ı atributu na prázdnou hodnotu, coˇz je v podstatˇe typ zmˇeny. • Pokud @R.α a ∃A.α, byl atribut novˇe pˇridán a je pˇridán i do vytváˇreného zdroje M.α = A.α. Pokud bude pˇridán i v dalˇs´ı verzi, bude hodnota stejnˇe jako v pˇr´ıpadˇe zmˇeny pˇrepsána. Z pravidel vypl´ yvá, ˇze operace pˇridán´ı a operace smazán´ı jsou variacemi operace zmˇeny. Pokud je atribut smazán, byla provedena operace zmˇeny na prázdnou hodnotu, a pokud je atribut pˇridán, byla provedena operace zmˇeny na neprázdnou hodnotu. Obrázek 4.14 ilustruje v´ yˇse uvedená pravidla na pˇr´ıkladˇe slouˇcen´ı dvou konfliktn´ıch zmˇen na serverech A a B v˚ uˇci referenˇcn´ımu zdroji na serveru C do nového zdroje. Nov´ y zdroj, kter´ y vznikne slouˇcen´ım konfliktn´ıch zmˇen, je nutné oznaˇcit zcela novou verz´ı, aby byla splnˇena pravidla ze sekce 4.11.2.

Obrázek 4.14: Zpracován´ı konfliktu dvou zmˇen v˚ uˇci referenˇcn´ımu zdroji Problém ovˇsem nastává, pokud nemáme k dispozici referenˇcn´ı verzi zdroje. Takov´ y pˇr´ıpad nastane, pokud jsou zmˇeny detekovány na vˇsech replikách a tud´ıˇz ˇzádn´ y ze zdroj˚ u nen´ı v aktuáln´ı verzi. Pro tyto pˇr´ıpady by bylo nutné uchovávat vˇzdy aktuáln´ı verzi zdroje na lokáln´ım disku, jelikoˇz protokol WebDAV neumoˇzn ˇuje z´ıskat dokument v poˇzadované verzi, a je moˇzné si jednoduˇse pˇredstavit objem takto uchovávan´ ych dat. Vznik takového pˇr´ıpadu je ovˇsem velice nepravdˇepodobn´ y a kv˚ uli zanedbatelné pravdˇepodobnosti nemá smysl komplikovat a zvyˇsovat pamˇet’ovou nároˇcnost algoritmu. Tento problém je tedy zanedbán a i kdyˇz nastane, je uspokojivˇe vyˇreˇsen, jak naznaˇcuje obrázek 4.15. Zmˇena byla detekována na vˇsech serverech A, B i C a nen´ı tud´ıˇz moˇzné z´ıskat referenˇcn´ı verzi zdroje ve verzi 1. Je moˇzné si povˇsimnou, ˇze hodnoty se pokaˇzdé pˇrepisuj´ı novˇejˇs´ı verz´ı, jelikoˇz je vˇzdy detekováno pˇridán´ı nového atributu v˚ uˇci prázdnému referenˇcn´ımu zdroji. Operace zmˇeny ani odstranˇen´ı atribut˚ u nejsou detekovány. Algoritmus ˇreˇsen´ı konflikt˚ u bez referenˇcn´ıho objektu by bylo moˇzné vylepˇsit tak, ˇze by se nové atributy pˇridávali i do prázdného referenˇcn´ıho objektu. Bylo by tak moˇzné 45


Plánovaˇc

Obrázek 4.15: Zpracován´ı konfliktu tˇr´ı zmˇen bez referenˇcn´ıho zdroje detekovat v dalˇs´ıch sluˇcovan´ ych verz´ıch zmˇeny v hodnotách atribut˚ u. Problém by ovˇsem nastal, pokud by v dalˇs´ıch verz´ıch zdroje atribut chybˇel, jelikoˇz by bylo detekováno odstranˇen´ı atributu. Nen´ı totiˇz moˇzné automaticky urˇcit, zda je správnˇe operace odstranˇen´ı nebo pˇridán´ı. Nejlepˇs´ı je zvolit takov´ y kompromis, kter´ y bude co nejménˇe destruktuvn´ı, a takov´ ym je právˇe vypnut´ı detekce odstranˇen´ı. Uˇzivatel se snáz vyrovná s t´ım, ˇze data byla nechtˇenˇe vyplnˇena, neˇz ˇze data zmizela. Navrhnut´ y algoritmus je moˇzné pouˇz´ıt jak pro vlastnosti zdroje, tak pro strukturované dokumenty, u kter´ ych jsou vlastnosti nav´ıc hierarchicky vnoˇreny. Pro nestrukturované dokumenty nemá smysl, jelikoˇz nedokáˇzeme rozpoznat vnitˇrn´ı strukturu. Algoritmus by se dal dále rozˇs´ıˇrit o detekci operac´ı na u ´rovni textov´ ych hodnot jednotliv´ ych atribut˚ u, napˇr´ıklad odstranˇen´ı slova a zároveˇ n pˇridán´ı slova na jiné replice. Toto rozˇs´ıˇren´ı by vˇsak bylo pˇr´ıliˇs sloˇzité a nespolehlivé v komplikovan´ ych situac´ıch, coˇz by mohlo zp˚ usobit vznik nesmysln´ ych dat.

4.12

Pl´ anovaˇ c

Sekce 4.6 uvedla hned tˇri moˇzné zp˚ usoby synchronizace Kerio Connect server˚ u - pomalou synchronizaci, zmˇenovou synchronizaci a aktivn´ı synchronizaci. Jednotlivé metody synchronizace je nutné plánovat tak, aby byly vˇsechny zmˇeny dostateˇcnˇe rychle propagovány, ale servery nesm´ı b´ yt pˇret´ıˇzeny. Jelikoˇz nen´ı moˇzné protokolem WebDAV zjistit momentáln´ı zat´ıˇzen´ı server˚ u, je nutné synchronizaci plánovat intuitivnˇe a inteligentnˇe: • Pomalá synchronizace znaˇcnˇe zatˇeˇzuje jak server, tak synchronizaˇcn´ı proces, protoˇze mus´ı prohledat veˇskeré kolekce a dokumenty v nich a spárovat je mezi sebou. Naˇstˇest´ı je nutné ji spouˇstˇet pouze jednou, server totiˇz zmˇeny spolehlivˇe oznamuje pˇri kaˇzdé zmˇenové synchronizaci, protoˇze se vˇzdy ptáme oproti posledn´ımu u ´spˇeˇsnému stavu.

46


Plánovaˇc

• Zmˇenová synchronizace je oproti pomalé synchronizaci mnohem ménˇe nároˇcná, ale stále je nutné prohledat veˇskeré kolekce na vˇsech serverech. Pokud se nahromad´ı velké mnoˇzstv´ı zmˇen, je srovnatelná s pomalou synchronizac´ı. Je proto nutné ji spouˇstˇet dostateˇcnˇe ˇcasto, aby nedoˇslo k náhlému zahlcen´ı synchronizace, ale ne tak ˇcasto, aby doˇslo k pˇret´ıˇzen´ı serveru hledán´ım zmˇen. • Aktivn´ı synchronizace je nejménˇe nároˇcná ze vˇsech metod. Ale nen´ı moˇzné ji aplikovat na vˇsechny zdroje, jelikoˇz by dotazován´ı na zmˇeny vyvolalo pˇr´ıliˇsnou zátˇeˇz serveru. Je proto nutné ji kombinovat se zmˇenovou synchronizac´ı. Spouˇstˇen´ı tˇechto metod je potˇreba naˇcasovat tak, aby nedoˇslo k pˇr´ıliˇsnému zat´ıˇzen´ı serveru ˇcast´ ym spouˇstˇen´ım synchronizac´ı nebo naopak skokovému pˇret´ıˇzen´ı serveru pˇri nahromadˇen´ı operac´ı. Správné ˇcasován´ı je nutné zvolit dle konkrétn´ıho ˇreˇsen´ı a struktury synchronizaˇcn´ıho stromu.

4.12.1

Heuristick´ a synchronizace

Jelikoˇz zmˇenová synchronizace prohledává vˇsechny sloˇzky a je natolik nároˇcná, ˇze nejde spouˇstˇet ˇcasto, a aktivn´ı synchronizace je moˇzné aplikovat pouze na nˇekteré sloˇzky, je pˇridána nová synchronizaˇcn´ı metoda s inteligenc´ı. Heuristická metoda vybere nejpravdˇepodobnˇejˇs´ı kolekci, ve které mohlo doj´ıt ke zmˇenˇe, a provede synchronizaci této kolekce. Jelikoˇz docház´ı k hledán´ı zmˇen jen v jedné kolekci, je moˇzné tuto synchronizaci spouˇstˇet ˇcastˇeji a tud´ıˇz doc´ılit rychlé propagace zmˇen a rozloˇzen´ı zátˇeˇze. Vzorcem p = object.members ∗

time − copy.last searched at delay

z´ıskáme poˇrad´ı p ve v´ ysledku vyhledáván´ı pro kaˇzdou kolekci. Promˇenná time je aktuáln´ı ˇcasová znaˇcka a delay je poˇcet sekund mezi heuristick´ ymi synchronizacemi. Poˇcet ˇclen˚ u je pˇr´ımo u ´mˇern´ y poˇctu proveden´ ych heuristick´ ych synchronizac´ı od ˇcasu posledn´ı synchronizace v dané kolekci. Vzorec by bylo moˇzné doplnit o hodnotu object.depth hloubky ve stromˇe, ale tato hodnota nen´ı smˇerodatná, protoˇze hluboko vnoˇrená kolekce s velk´ ym mnoˇzstv´ım dokument˚ u m˚ uˇze b´ yt stejnˇe v´ yznamná, jako kolekce se stejn´ ym mnoˇzstv´ım na prvn´ı u ´rovni. V´ ypoˇcet klade d˚ uraz na to, aby pˇri pouˇzit´ı pouze heuristické synchronizace mohlo doj´ıt k synchronizaci vˇsech kolekc´ı a právˇe proto je u ´mˇernou hodnotou ˇcas posledn´ı synchronizace. Synchronizovány jsou kolekce s nejvyˇsˇs´ım poˇrad´ım.

4.12.2

Rychlost propagace zmˇ en

Rychlost propagace zmˇen je závislá na um´ıstˇen´ı zdroje, kter´ y byl zmˇenˇen, a na plánovaˇci operac´ı. Nejmenˇs´ım moˇzn´ ym ˇcasem propagace je zpoˇzdˇen´ı mez´ı heuristickou nebo aktivn´ı synchronizac´ı. Nejvyˇsˇs´ım moˇzn´ ym ˇcasem propagace je zpoˇzdˇen´ı mezi zmˇenovou synchronizac´ı, která detekuje veˇskeré zmˇeny. Pr˚ umˇernou rychlost propagace je vˇsak moˇzné urˇcit aˇz se znalost´ı konkrétn´ı struktury zdroj˚ u na serveru a jejich typ˚ u.

47

5 Implementace Závˇereˇcnou ˇca´st´ı této práce je navrˇzenou architekturu a algoritmus synchronizace z kapitoly 4 implementovat a otestovat v podobˇe spustitelného programu a ovˇeˇrit tak jeho funkˇcnost a efektivitu. Implementace prob´ıhá pˇr´ımo proti existuj´ıc´ım Kerio Connect server˚ um, na kter´ ych je moˇzné celou implementaci dostateˇcnˇe otestovat. Implementace mus´ı b´ yt pˇrenositelná mezi r˚ uzn´ ymi platformami jako Linux/UNIX, Windows a MAC OS. Bˇeh programu prob´ıhá vˇzdy na pozad´ı bez grafického rozhran´ı a pˇriˇcinˇen´ı uˇzivatele, do budoucna by totiˇz program mˇel b´ yt souˇca´st´ı Kerio Connect serveru.

5.1

Programov´ e prostˇ redky

Moˇzné programové prostˇredky splˇ nuj´ıc´ı v´ yˇse uvedené poˇzadavky jsou Java SE nebo C++. Oba programovac´ı jazyky jsou objektovˇe orientované. Java SE vˇsak vyniká svoj´ı jednoduchost´ı a vysoko´ urovˇ nov´ ymi prostˇredky, je také velice snadno pˇrenositelná na r˚ uzné platformy. Java SE je orientována na rapidn´ı v´ yvoj za cenu neefektivn´ıho pouˇzit´ı prostˇredk˚ u. Oproti tomu C++ programovac´ı jazyk je urˇcen pro implementaci kritick´ ych aplikac´ı s poˇzadavkem na v´ ykon. Nedostatek vysoko´ urovˇ nov´ ych prostˇredk˚ u kompenzuje efektivita a rychlost pouˇzit´ı n´ızko´ urovˇ nov´ ych prostˇredk˚ u. Nev´ yhodou C++ je ovˇsem zhorˇsená pˇrenositelnost d´ıky pˇr´ımému pouˇzit´ı prostˇredk˚ u operaˇcn´ıho systému. Pro u ´ˇcely implementace se pˇresto v´ıce hod´ı právˇe C++, jelikoˇz je moˇzné velice efektivnˇe vyuˇz´ıvat programové prostˇredky a vytvoˇrit tak v´ ykonn´ y synchronizaˇcn´ı program, coˇz je d˚ uleˇzit´ ym mˇeˇr´ıtkem. Nav´ıc Kerio Connect server je napsán také v C++.

5.2

Knihovny

Pˇri v´ yvoji modern´ıch aplikac´ı je kladen d˚ uraz na pouˇzit´ı jiˇz existuj´ıc´ıch ˇreˇsen´ı m´ısto vlastn´ı implementace. Existuj´ıc´ı knihovny jsou otestovány a odladˇeny mnoh´ ym pouˇz´ıván´ım a ˇcasto jsou multiplatformn´ı, je proto velice jednoduché je pouˇz´ıt v nové aplikaci. Poˇzadavky, které jsou kladeny na knihovny pro pouˇzit´ı v této práci, jsou: • Knihovna mus´ı b´ yt vydána pod licenc´ı LGPL, MIT, Apache nebo BSD, aby bylo moˇzné vyuˇz´ıt knihovnu pro komerˇcn´ı u ´ˇcely a nebylo nutné distribuovat zdrojové kódy programu, • Knihovna mus´ı b´ yt dobˇre zdokumentována. • V´ yvoj knihovny mus´ı b´ yt stále ˇziv´ y, aby bylo zaruˇceno, ˇze knihovna je stále pouˇz´ıvaná, odladˇená a nen´ı zastaralá. • Knihovna by mˇela b´ yt Thread-Safe, aby se pˇredeˇslo problém˚ um pˇri pˇr´ıpadném pouˇzit´ı v´ıcevláknového programu. • Knihovna mus´ı b´ yt multiplatformn´ı, aby bylo moˇzné program pˇreloˇzit pro operaˇcn´ı systémy UNIX/Linux, Windows a MAC OS. 48

Implementace

Knihovny

Sqlite 3.7.11 SQLite je C knihovna, která implementuje transakˇcn´ı SQL databázi bez nutnosti serveru a konfigurace. SQLite je nejrozˇs´ıˇrenˇejˇs´ı SQL databázov´ y systém na svˇetˇe. Tato knihovna se v´ ybornˇe hod´ı pro reprezentaci perzistentn´ı relaˇcn´ı databáze pˇredstavené v kapitole 4.5, pro podporu synchronizaˇcn´ıho procesu. SQLite verze 3 je vydávána bez licence. Neon 0.29.6 Neon je HTTP a WebDAV klientská knihovna pouˇz´ıvaj´ıc´ı rozhran´ı v jazyce C. Knihovna obsahuje jak n´ızko´ urovˇ nové funkce pro komunikaci protokolem HTTP tak vysoko´ urovˇ nové funkce pro komunikaci protokolem WebDAV. Knihovna je vydávána pod licenc´ı LGPL. Libxml 2.7.8 Jelikoˇz WebDAV pouˇz´ıvá XML technologii, je nutné naj´ıt knihovnu, která by umˇela jednoduˇse parsovat XML dokumenty. Takovou knihovnou je Libxml2, která obsahuje SAX parser pro ˇcten´ı obsahu XML dokument˚ u. V´ yhodou knihovny je také jej´ı pˇr´ımá podpora v knihovnˇe Neon. Libxml2 je vydávána pod licenc´ı MIT. OpenSSL 1.0.1 Knihovna OpenSSL implementuje Secure Sockets Layer (SSL v2/v3) a Transport Layer Security (TLS v1) protokoly a mimo jiné i vˇseobecné kryptografické algoritmy. Tuto knihovnu pˇr´ımo implementuje Neon pro komunikaci prostˇrednictv´ım HTTPS protokolu. OpenSSL je vydávána pod licenc´ı Apache. Log4cpp 0.3.4 Log4cpp je C++ knihovna pro flexibiln´ı logován´ı do soubor˚ u, standardn´ıho v´ ystupu a jin´ ych c´ıl˚ u. Jedná se o pˇrepsán´ı známé Log4j Java knihovny do C++ prostˇred´ı s d˚ urazem na zachován´ı rozhran´ı. Log4cpp umoˇzn ˇuje efektivn´ı logován´ı na r˚ uzn´ ych u ´rovn´ıch d´ıky konfiguraˇcn´ım soubor˚ um. Knihovna je pouˇz´ıvána pro veˇsker´ y v´ ystup do soubor˚ u nebo konzole. Log4cpp je vydávána pod licenc´ı BSD.

49

Implementace

5.3

Architektura

Architektura

Architektura aplikace je dekomponována do ˇctyˇr komponent, které jsou popsány v následuj´ıc´ıch sekc´ıch. Komponenty jsou popsány pouze z vnˇejˇsku a pˇresnou implementaci je moˇzné dohledat v dobˇre zdokumentovan´ ych zdrojov´ ych souborech. Celá aplikace je koncipována jako proces s jedn´ım vláknem s moˇznost´ı bˇehu na pozad´ı bez uˇzivatelského rozhran´ı.

5.3.1

WebDAV klient

Prvn´ı komponentou aplikace je nadstavba knihovny Neon implementuj´ıc´ı potˇrebné metody a funkce WebDAV protokolu a zapouzdˇruje je do jednoduch´ ych metod a objekt˚ u. Diagram na obrázku 5.1 pˇredstavuje objektov´ y model WebDAV komponenty.

Obrázek 5.1: Objektov´ y model WebDAV klienta Pˇri pouˇz´ıván´ı WebDAV klienta je nutné znát pouze tˇr´ıdu Connection, která obsahuje implementaci volán´ı vˇsech potˇrebn´ ych WebDAV metod. Tˇr´ıda se stará o vytváˇren´ı a udrˇzován´ı HTTP spojen´ı na server, jeho zruˇsen´ı pˇri ukonˇcen´ı volán´ı a také o autentifikaci a ovˇeˇren´ı certifikátu serveru. Zpracován´ı prob´ıhá ˇcistˇe proudovˇe, aby nemohlo doj´ıt k vyˇcerpán´ı operaˇcn´ı pamˇeti u rozsáhl´ ych poˇzadavk˚ u a odpovˇed´ı. Tˇr´ıda Connection definuje sadu v´ yjimek, které jsou vyvolány, jakmile nastane chyba uvnitˇr klienta: • UnauthorizedException - autentifikace se nezdaˇrila, • NotFoundException - zdroj nebyl nalezen, • ConnectionException - spojen´ı se nepodaˇrilo navázat nebo bylo zruˇseno. Pˇri volán´ı vˇetˇsiny metod je jako návratová hodnota vrácena instance tˇr´ıdy Response zapouzdˇruj´ıc´ı odpovˇed’ serveru - hlaviˇcky, návratov´ y kód a tˇelo odpovˇedi. Pokud je návratov´ y kód odpovˇedi 207 Multistatus, je odpovˇed’ dále zpracovávána tak, ˇze obsahuje instanci tˇr´ıdy MultiStatus reprezentuj´ıc´ı hromadnou odpovˇed’ serveru. Tˇr´ıda MultiStatus zajiˇst’uje zároveˇ n pˇreˇcten´ı XML tˇela odpovˇedi a vytvoˇren´ı ˇca´steˇcné odpovˇedi pro kaˇzd´ y jednotliv´ y vnitˇrn´ı stav hromadné odpovˇedi jako instanci tˇr´ıdy MultiStatusResponse.

50

Implementace

Architektura

Pokud maj´ı b´ yt v odpovˇedi vráceny vlastnosti zdroje, jsou vˇzdy uloˇzeny v ˇca´steˇcn´ ych odpovˇed´ıch 207 Multistatus návratového kódu. Instance tˇr´ıdy MultiStatusResponse se proto stará o dalˇs´ı zpracován´ı ˇca´steˇcné odpovˇedi a pˇreˇcten´ı vˇsech vlastnost´ı, které jsou nalezeny. Vlastnosti jsou uloˇzeny jako pár jméno a hodnota v datovém kontejneru PropertySet, kter´ y je moˇzné pouˇz´ıt i pro následn´ y zápis vlastnost´ı na server. Kolekce mohou obsahovat speciáln´ı strukturovanou vlastnost security descriptor, která je ve WebDAV klientu reprezentována jako instance tˇr´ıdy SecurityDescriptor. Transakˇcn´ı mechanismus je zapouzdˇren do tˇr´ıdy Lock, která se stará o zpracován´ı metod LOCK a UNLOCK se speciáln´ım tvarem XML odpovˇedi. Tˇr´ıda zároveˇ n uchovává veˇskeré transakce platné pro aktuáln´ı spojen´ı a automaticky pˇridává hlaviˇcku If do poˇzadavk˚ u vˇsech metod, které jsou volány v rámci transakce, dokud nen´ı transakce ukonˇcena metodou UNLOCK.

5.3.2

Objektov´ y model

Aby bylo moˇzné jednoduˇse pracovat s databáz´ı, která je nutná pro ukládán´ı perzistentn´ıch dat, jak bylo naznaˇceno v sekci 4.5, je pˇripojen´ı do databáze a práce s databáz´ı zapouzdˇreno do ORM tˇr´ıd. Instance tˇechto tˇr´ıd reprezentuj´ı jeden záznam v databázi a zapouzdˇruj´ı SQL dotazy ve sv´ ych metodách. Napˇr´ıklad pro uloˇzen´ı záznamu do databáze tak nen´ı nutné vytváˇret SQL dotaz, ale pˇr´ımo zavolat metodu save, která se o vˇse postará a vrát´ı návratov´ y kód proveden´ı operace nad databáz´ı. Naproti tomu statické metody pracuj´ı s celou databáz´ı a slouˇz´ı pro vyhledáván´ı a hromadné u ´pravy.

Obrázek 5.2: Objektov´ y model mapován´ı databáze na objekty ORM Komponenta se skládá ze tˇr´ı tˇr´ıd, které reprezentuj´ı kaˇzdá jednu z tabulek databáze, a jednoho spoleˇcného abstraktn´ıho pˇredka, kter´ y definuje obecné metody a základn´ı rozhran´ı ORM tˇr´ıd, jak zobrazuje objektov´ y model na obrázku 5.2. Vˇsechny potˇrebné SQL dotazy a volán´ı jsou takto uloˇzeny na jednom m´ıstˇe a je moˇzné je velice jednoduˇse a efektivnˇe spravovat nebo rozˇsiˇrovat. Pokud se zmˇen´ı schéma databáze, je nutné upravit pouze tyto tˇr´ıdy. Konzistence databáze je automaticky udrˇzována pˇri kaˇzdém vytvoˇren´ı ovladaˇce databáze. Pokud je zjiˇstˇeno, ˇze databáze je poˇskozena, je cel´ y proces synchronizace restartován a databáze vyprázdnˇena, ˇc´ımˇz docház´ı k vyvolán´ı pomalé synchronizace a obnoven´ı procesu synchronizace. Poˇskozen´ı databáze je nahláˇseno vyvolán´ım v´ yjimky DatabaseCorruptedException.

5.3.3

Reprezentace zdroj˚ u

Dalˇs´ı komponentou aplikace je mnoˇzina tˇr´ıd reprezentuj´ıc´ı zdroje WebDAV serveru - kolekce a strukturované i nestrukturované dokumenty. Zdroje jsou reprezentovány hierar51

Implementace

Architektura

chicky, jak ukazuje objektov´ y model na obrázku 5.3. Základem je obecné rozhran´ı Base, které definuje základn´ı metody vˇsech tˇr´ıd pro reprezentaci zdroj˚ u.

Obrázek 5.3: Objektov´ y model reprezentace zdroj˚ u D´ıky této architektuˇre je moˇzné jednoduˇse implementovat model synchronizace, kter´ y je pro vˇsechny zdroje naprosto shodn´ y, a pouˇz´ıt pouze metody rozhran´ı a specifické vlastnosti r˚ uzn´ ych zdroj˚ u pokr´ yt aˇz na u ´rovni implementace metod rozhran´ı v jednotliv´ ych tˇr´ıdách. Jedná se o vyuˇzit´ı polymorfismu z objektovˇe orientovaného programován´ı. Továrn´ı tˇr´ıda Factory rozhoduje o vytvoˇren´ı konkrétn´ı instance tˇr´ıdy na základˇe obdrˇzen´ ych vlastnost´ı zdroje. Pˇr´ıkladem m˚ uˇze b´ yt implementace nahrán´ı zdroje na serveru, kdy pˇri nahrán´ı kolekce je nutné pouˇz´ıt metodu MKCOL, kdeˇzto u dokumentu mus´ıme vytvoˇrit transakci a pouˇz´ıt metodu PUT. U klasické implementace by se algoritmus nepˇrehlednˇe vˇetvil pˇri kaˇzdé odliˇsnosti. Aplikace je nav´ıc snadno rozˇsiˇritelná o nové typy zdroj˚ u pˇridán´ım nové tˇr´ıdy a jej´ı implementace do stromu bez nutnosti zásahu do synchronizaˇcn´ıho algoritmu.

5.3.4

Synchronizace

Posledn´ı a také hlavn´ı komponentou je implementace synchronizaˇcn´ıho algoritmu z kapitoly 4. Komponenta vyuˇz´ıvá vˇsechny pˇredchoz´ı komponenty a logicky z nich skládá fináln´ı synchronizaˇcn´ı proces.

Obrázek 5.4: Objektov´ y model synchronizace Tˇr´ıda ChangeResolver implementuje algoritmy ze sekce 4.8, které se staraj´ı o detekci a zápis nalezen´ ych operac´ı do databáze. Nalezené zmˇeny jsou zpracovány tˇr´ıdou 52

Implementace

Testov´ an´ı

ChangeUpdater, která se postará o detekci a odstranˇen´ı konflikt˚ u s pouˇzit´ım komponenty reprezentace zdroj˚ u a aktualizuje neaktuáln´ı repliky. Zm´ınˇené dvˇe tˇr´ıdy logicky spojuje hlavn´ı tˇr´ıda Synchronizer implementuj´ıc´ı vˇsechny ˇctyˇri synchronizaˇcn´ı metody, jeˇz jsou plánovány ˇcasovaˇcem ve tˇr´ıdˇe Scheduler popsan´ ym bl´ıˇze v sekci 4.12. Objektov´ y model komponenty je zobrazen na obrázku 5.4.

5.4

Testov´ an´ı

Základn´ı testován´ı implementace prob´ıhalo mezi dvˇema Kerio Connect servery α a β na r˚ uzn´ ych m´ıstech s´ıtˇe propojené internetem. Následuj´ıc´ı seznam obsahuje v´ yˇcet vˇsech testovac´ıch pˇr´ıpad˚ u, které byly navrhnuty a pouˇzity pro ovˇeˇren´ı funkˇcnosti implementace: • Kolekce – – – – – – – – –

Pˇridán´ı nové kolekce Pˇrejmenován´ı kolekce ´ Uprava práv kolekce Pˇresunut´ı kolekce o u ´roveˇ n v´ yˇse Pˇresunut´ı kolekce o u ´roveˇ n n´ıˇze Pˇrejmenován´ı dvou kolekc´ı proti sobˇe na stejná jména Smazán´ı kolekce Smazán´ı a ihned pˇridán´ı stejné kolekce pˇred detekc´ı Jméno kolekce s pouˇzit´ım vˇsech povolen´ ych znak˚ u

• Konfliktn´ı kolekce – – – – – – – – – – – – –

Pˇridán´ı konfliktn´ı kolekce Vytvoˇren´ı ˇclenské kolekce v konfliktn´ı kolekci Vytvoˇren´ı ˇclenské kolekce v nekonfliktn´ı kolekci ´ Uprava práv konfliktn´ı kolekce ´ Uprava práv nekonfliktn´ı kolekce Pˇrejmenován´ı konfliktn´ı kolekce Pˇrejmenován´ı nekonfliktn´ı kolekce Pˇresunut´ı konfliktn´ı kolekce Pˇresunut´ı nekonfliktn´ı kolekce Pˇrejmenován´ı 2 konfliktn´ıch kolekc´ı proti sobˇe na stejná jména Smazán´ı konfliktn´ı a ihned pˇridán´ı nekonfliktn´ı kolekce pˇred detekc´ı Smazán´ı konfliktn´ı kolekce Smazán´ı nekonfliktn´ı kolekce

• Dokumenty – – – – – – –

Pˇridán´ı nového dokumentu Pˇresunut´ı dokumentu ´ Uprava dokumentu Konfliktn´ı u ´prava na v´ıce replikách Konfliktn´ı u ´prava na vˇsech replikách Zkop´ırován´ı dokumentu Smazán´ı dokumentu 53

Implementace

5.5

Zátˇeˇzový test

Z´ atˇ eˇ zov´ y test

Po ovˇeˇren´ı a doladˇen´ı funkˇcnosti mezi dvˇema servery byla aplikace nakonfigurována pro synchronizaci deseti Kerio Connect server˚ u, aby mohla b´ yt d˚ ukladnˇe otestována ˇskálovatelnost. V této konfiguraci bylo moˇzné ovˇeˇrit i odolnost v˚ uˇci v´ ypadk˚ um v s´ıti a doˇcasnˇe nedostupn´ ym server˚ um. Pro d˚ ukladné zátˇeˇzové otestován´ı byl jeden ze server˚ u naplnˇen 3.000 náhodn´ ymi testovac´ımi zdroji a byla provedena replikace mezi vˇsemi deseti servery. Synchronizaˇcn´ı proces byl spuˇstˇen na samostatné stanici oddˇelenˇe od server˚ u s hardwarovou konfigurac´ı uvedenou v tabulce 5.1. Komponenta Procesor Poˇcet vyuˇziteln´ ych jader Operaˇcn´ı pamˇet’ Pˇripojen´ı k internetu Klidové zat´ıˇzen´ı CPU

Synchronizaˇ cn´ı proces AMD Phenom X4 2.4 GHz 1 512 MB 1 GB Ethernet 0%

Kerio Connect server Intel Xeon 3.73 GHz 1 1024 MB 1 GB Ethernet 2%

Tabulka 5.1: Hardwarová konfigurace testovac´ıch stanic a server˚ u Profilován´ı prvn´ı pomalé synchronizace, která replikovala zdroje na devˇet dalˇs´ıch replik, je moˇzné vidˇet v tabulce 5.2. Je moˇzné si povˇsimnout alarmuj´ıc´ı hodnoty reálného ˇcasu, po kter´ y synchronizace bˇeˇzela. Ostatn´ı hodnoty jsou vˇsak velice uspokojivé. Synchronizace vyuˇz´ıvala procesor na maximálnˇe 42 % s pouˇzitou operaˇcn´ı pamˇet´ı do 40 ˇ stráven´ MB. Cas y na procesoru je také velice n´ızk´ y, je 83 krát niˇzˇs´ı neˇz reáln´ y ˇcas bˇehu synchronizace. Z namˇeˇren´ ych hodnot jednoduˇse vypl´ yvá, ˇze synchronizaˇcn´ı proces 98 % ˇcasu ˇcekal a nepracoval s procesorem. Sledovan´ a veliˇ cina nejmenˇ s´ı nejvˇ etˇ s´ı stˇ redn´ı Reáln´ y ˇcas 9h 20m Procesorov´ y ˇcas 6m 48s CPU zat´ıˇzen´ı 0% 28 % 1% Pamˇet’ 3,5 MB 39 MB 39 MB CPU zat´ıˇzen´ı serveru 2% 18 % 6% Tabulka 5.2: Profilován´ı prvn´ı pomalé synchronizace Prvn´ı podezˇren´ı samozˇrejmˇe padlo na komunikaci s Kerio Connect servery. Aby bylo moˇzné pˇresnˇe identifikovat u ´zké m´ısto synchronizace, byly vˇsechny ˇcasto pouˇz´ıvané WebDAV metody profilovány pro z´ıskán´ı pˇrehledu o jejich chován´ı, jak zachycuje tabulka 5.3. Stejné hodnoty byly zjiˇstˇeny i z log˚ u Kerio Connect serveru, coˇz vyvrac´ı moˇznost komunikaˇcn´ıho zpoˇzdˇen´ı. Na prvn´ı pohled je moˇzné odhalit u ´zké m´ısto synchronizace - metoda PUT. Metoda PUT se vyuˇz´ıvá pˇri vytváˇren´ı nebo u ´pravˇe dokument˚ u na replice, je to tedy nejv´ıce pouˇz´ıvaná metoda hned po metodˇe GET. Pˇri prvn´ı pomalé synchronizaci byla metoda pouˇzita pˇribliˇznˇe 27 tis´ıc krát (3.000 dokument˚ u * 9 replik), coˇz po vynásoben´ı pr˚ umˇern´ ym ˇcasem 54

Implementace

Urychlen´ı

Metoda SEARCH GET PUT MKCOL LOCK UNLOCK

Odezva nejmenˇ s´ı nejvˇ etˇ s´ı stˇ redn´ı 100ms 1,4s 500ms 10ms 40ms 20ms 0,7s 1,4s 1s 10ms 16ms 13ms 8ms 10ms 9ms 9ms 10ms 9ms

Tabulka 5.3: Profilován´ı ˇcasto pouˇz´ıvan´ ych WebDAV metod 1 sekunda na poˇzadavek ˇcin´ı 7,5 hodiny. Jednoduˇse tedy synchronizace 7,5 hodiny ˇcekala na proveden´ı metody PUT a pokud pˇriˇcteme pouˇzit´ı dalˇs´ıch metod, z´ıskáme zjiˇstˇen´ ych 98 % nevyuˇzitého ˇcasu. Sledovan´ a veliˇ cina nejmenˇ s´ı nejvˇ etˇ s´ı stˇ redn´ı Reáln´ y ˇcas 18m 13s Procesorov´ y ˇcas 2m 38s CPU zat´ıˇzen´ı 1% 28 % 22 % Pamˇet’ 3,5 MB 13 MB 11 MB CPU zat´ıˇzen´ı serveru 2% 18 % 3% Tabulka 5.4: Profilován´ı druhé pomalé synchronizace Po restartován´ı perzistentn´ı databáze a opˇetovném spuˇstˇen´ı pomalé synchronizace jiˇz byly dosaˇzeny mnohem pˇr´ıznivˇejˇs´ı hodnoty ˇcasu bˇehu aplikace, jak ukazuje tabulka 5.4. Niˇzˇs´ı hodnoty jsou samozˇrejmˇe zp˚ usobeny chybˇej´ıc´ımi replikacemi dokument˚ u, jelikoˇz vˇsechny dokumenty jiˇz na vˇsech replikách existuj´ı a dokumenty jsou pouze spárovány a shledány jako aktuáln´ı na vˇsech replikách. Server je v´ıce optimalizován pro stahován´ı dokument˚ u, coˇz je patrné ze zat´ıˇzen´ı serveru. Ostatn´ı synchronizaˇcn´ı metody, zmˇenová synchronizace, aktivn´ı synchronizace a heuristická synchronizace, jsou nenároˇcné d´ıky malému poˇctu replikuj´ıc´ıch dokument˚ u, pokud samozˇrejmˇe nedojde k nahrán´ı velkého objemu dat, coˇz u emailového serveru nen´ı typic´ ym m´ıstem celé synchronizace je tedy replikace novˇe vytvoˇreného k´ ym pˇr´ıpadem uˇzit´ı. Uzk´ nebo zmˇenˇeného dokumentu na ostatn´ı repliky pˇri velkém poˇctu replik nebo velkém poˇctu operac´ı.

5.6

Urychlen´ı

Synchronizaˇcn´ı proces je navrhnut jako jednovláknov´ y a to z d˚ uvodu, ˇze párován´ı pˇri detekci mus´ı prob´ıhat sekvenˇcnˇe, jinak by mohlo doj´ıt k nesprávnému spárován´ı a zaveden´ı nechtˇené duplikace. Pokud by párován´ı prob´ıhalo paralelnˇe, muselo by b´ yt kaˇzdé hledán´ı a následn´ y zápis do databáze uzavˇren do transakce, coˇz by zp˚ usobovalo exkluzivn´ı zamykán´ı tabulek a v podstatˇe sekvenˇcn´ı bˇeh. Urychlen´ı by zde samozˇrejmˇe bylo moˇzné, ale nebude m´ıt takov´ y efekt jako u druhé fáze synchronizace - aktualizace. 55

Implementace

Urychlen´ı

Urychlen´ı je moˇzné ideálnˇe dosáhnout zaveden´ım paralelizace pˇri replikaci stejného dokumentu mezi v´ıce replik, jelikoˇz repliky jsou nezávislé a na kaˇzdé m˚ uˇze b´ yt spuˇstˇena operace PUT bez jakéhokoliv zpomalen´ı nebo zv´ yˇsen´ı zátˇeˇze na stranˇe serveru. Dalˇs´ı prostor pro paralelizaci se nacház´ı pˇri sekvenˇcn´ım provádˇen´ı vˇsech operac´ı nad jednotliv´ ymi zdroji. Jelikoˇz jiˇz známe koncov´ y stav proveden´ı operac´ı, které byly detekovány v prvn´ı fázi synchronizace, m˚ uˇzeme vˇsechny nové nebo zmˇenˇené zdroje rozdˇelit mezi v´ıce paraleln´ıch proces˚ u.

Obrázek 5.5: Pˇr´ıklad urychlen´ı synchronizace 400 operac´ı mezi 5 replik Diagram na obrázku 5.5 ukazuje pˇr´ıklad urychlen´ı synchronizace pro 400 nov´ ych nebo zmˇenˇen´ ych zdroj˚ u. Detekce zdroj˚ u prob´ıhá opˇet sekvenˇcnˇe, aby se pˇredeˇslo chybnému spárován´ı. Ovˇsem seznam nalezen´ ych operac´ı je rozdˇelen mezi ˇctyˇri pracovn´ı vlákna, která je paralelnˇe vykonávaj´ı. Rozdˇelit seznam prac´ı je moˇzné aˇz ve chv´ıli, kdy je dokonˇcena detekce zmˇen ze vˇsech replik, jinak by mohlo doj´ıt k chybné replikaci operace, protoˇze by se napˇr´ıklad pˇrepsala nedetekovaná operace. Pro kaˇzdou jednotlivou operaci je po vyˇreˇsen´ı konflikt˚ u a pˇr´ıpravˇe zdroje k aktualizaci vytvoˇrena sada aktualizaˇcn´ıch vláken, která paralelnˇe provedou aktualizaci zdroje na vˇsechny servery souˇcasnˇe, ˇc´ımˇz dojde k eliminaci sekvenˇcn´ıho ˇcekán´ı na dokonˇcen´ı metody PUT. Nelze ovˇsem oˇcekávat, ˇze ˇc´ım v´ıce vláken vytvoˇr´ıme, t´ım vˇetˇs´ıho urychlen´ı dosáhneme, pro vlákna proto plat´ı následuj´ıc´ı pravidla: • Poˇcet pracovn´ıch vláken se odv´ıj´ı od velikosti práce, kterou je potˇreba provést. Nemá napˇr´ıklad smysl vytváˇret deset vláken pro deset operac´ı, kdy kaˇzdé provede pouze jednu operaci, jelikoˇz vytvoˇren´ı vláken má jistou reˇzii. Vlákno má smysl vytváˇret pro deset a v´ıce operac´ı. • Poˇcet pracovn´ıch vláken je limitován propustnost´ı databáze a Kerio Connect serveru, jelikoˇz pracovn´ı vlákna provád´ı v´ıce paraleln´ıch operac´ı PUT na jedné replice, coˇz m˚ uˇze zp˚ usobit nár˚ ust zátˇeˇze na serveru. Pracovn´ı vlákna také provád´ı zápis do sd´ılené databáze, která se pˇri zápisech zamyká. Pˇri velkém poˇctu vláken by doˇslo k zahlcen´ı systému a moˇznému zpomalen´ı. • Poˇcet aktualizaˇcn´ıch vláken je rovn´ y poˇctu replik, mezi které má b´ yt provedena replikace zdroje. Smysl má ovˇsem vytváˇret vlákno pouze pro dokumenty, u kter´ ych byl zmˇenˇen obsah a bude pouˇzita metoda PUT, která zp˚ usobuje nejvˇetˇs´ı zpomalen´ı. Jinak by reˇzie vytvoˇren´ı vlákna pˇrev´ yˇsila uˇziteˇcnou hodnotu vlákna.

56

Implementace

Dlouhodobý test

• Celkov´ y poˇcet vláken nen´ı omezen poˇctem procesor˚ u, jelikoˇz vlákna nejsou v´ ypoˇcetnˇe vázána, ale budou vyuˇz´ıvat ˇcas, ve kterém ostatn´ı vlákna ˇcekaj´ı na dokonˇcen´ı komunikace s WebDAV serverem. Je moˇzné oˇcekávat znaˇcné urychlen´ı zejména pˇri synchronizaci velkého mnoˇzstv´ı replik, jelikoˇz vˇsechny repliky budou aktualizovány paralelnˇe. V ideáln´ım pˇr´ıpadˇe je moˇzné oˇcekávat urychlen´ı rovné poˇctu replik, coˇz samozˇrejmˇe z d˚ uvod˚ u reˇzie a transakc´ı v databázi nen´ı reálné. Dalˇs´ı urychlen´ı zp˚ usob´ı pouˇzit´ı pracovn´ıch vláken, jelikoˇz servery nejsou plnˇe vyt´ıˇzeny pˇri pouˇzit´ı pouze jedné metody sekvenˇcnˇe. U pracovn´ıch vláken je vˇsak nutné dávat pozor na pˇret´ıˇzen´ı server˚ u. Po implementaci urychlen´ı byla spuˇstˇena opˇet pomalá synchronizace se stejn´ ymi daty jako v pˇr´ıpadˇe zátˇeˇzov´ ych test˚ u. V´ ysledky profilován´ı urychlené pomalé synchronizace s r˚ uzn´ ym poˇctem pracovn´ıch vláknem zobrazuje tabulka 5.5. Synchronizace byla d´ıky pouˇzit´ı paraleln´ıho nahráván´ı dokument˚ u urychlena 7 krát pro 10 Kerio Connect server˚ u, coˇz je pomˇernˇe znaˇcn´ y rozd´ıl oproti neurychlené variantˇe. Pˇri pouˇzit´ı v´ıce pracovn´ıch vláken je urychlen´ı dále zvyˇsováno, ale je moˇzné si povˇsimnout znaˇcného nár˚ ustu zat´ıˇzen´ı procesoru na stranˇe serveru. Poˇcet pracovn´ıch vláken by bylo moˇzné dále zvyˇsovat, ale urychlen´ı jiˇz nebude tak v´ yrazné a mus´ıme si uvˇedomit, ˇze nen´ı moˇzné Kerio Connect server plnˇe zat´ıˇzit jen provádˇen´ım synchronizace. Server mus´ı b´ yt stále schopn´ y vyˇrizovat poˇzadavky klient˚ u a pˇrij´ımat poˇstu. Poˇ cet pracovn´ıch vl´ aken Reáln´ y ˇcas Procesorov´ y ˇcas CPU zat´ıˇzen´ı CPU zat´ıˇzen´ı serveru Urychlen´ı

1 2 3 4 5 1h 20m 1h 5m 50m 59s 39m 25s 34m 32s 6m 38s 6m 43s 6m 48s 6m 51s 6m 59s 24 % 26 % 27 % 31 % 32 % 12 % 23 % 31 % 42 % 49 % 7 8,6 11 14,3 16,4

Tabulka 5.5: Profilován´ı urychlené pomalé synchronizace s r˚ uzn´ ym poˇctem pracovn´ıch vláken Urychlen´ı se projevilo i u vˇsech ostatn´ıch synchronizaˇcn´ıch metod, nejen u pomalé synchronizace. Pomalá synchronizace je vˇsak nejhorˇs´ım pˇr´ıpadem synchronizace a bylo nutné se na ni zamˇeˇrit.

5.7

Dlouhodob´ y test

Posledn´ım proveden´ ym testem byl dlouhodob´ y test pro ovˇeˇren´ı, zda synchronizaˇcn´ı proces dokáˇze bezproblémovˇe bˇeˇzet nˇekolik dn´ı bez pˇrestán´ı. Test byl spuˇstˇen oproti dvoum testovac´ım server˚ um ve stejné konfuguraci jako pˇri zátˇeˇzovém testu (viz sekce 5.5). Pro odzkouˇsen´ı ˇca´steˇcnˇe reálné záteˇze, byl vytvoˇren generátor náhodn´ ych dokument˚ u, kter´ y generoval kaˇzd´ ych 10 sekund jeden dokument na server, ˇc´ımˇz simuloval pouˇz´ıván´ı serveru. Synchronizaˇcn´ı proces tak po celou dobu bˇehu mohl detekovat a synchronizovat nové dokumenty mezi servery. Nastaven´ı ˇcas˚ u pro plánovaˇc synchronizaˇcn´ıch metod je uvedeno v tabulce 5.6. Jeden ze server˚ u byl pˇri spuˇstˇen´ı synchronizace prázdn´ y a druh´ y obsahoval 3000 náhodn´ ych dokument˚ u. 57

Implementace

Dlouhodobý test

Zmˇ enov´ a synchronizace Aktivn´ı synchronizace Heuristick´ a synchronizace 1 hodina 30 sekund 60 sekund Tabulka 5.6: Nastaven´ı plánovaˇce pro dlouhodob´ y test

Obrázek 5.6: Graf zátˇeˇze pˇri dlouhodobém testu Test byl spuˇstˇen po dobu 48 hodin a hlavn´ı sledovanou veliˇcinou bylo zat´ıˇzen´ı server˚ u jak uvád´ı graf na obrázku 5.6. Graf v prvn´ı hodinu naznaˇcuje pr˚ ubˇeh pomalé synchronizace, pˇri které se pˇreneslo 3000 dokument˚ u na prázdn´ y server. Pr˚ ubˇeh dalˇs´ıch 47 hodin je stál´ y a zat´ıˇzen´ı server˚ u se aˇz na v´ yjimky drˇz´ı pod hodnotou 0, 1, coˇz je velice dobr´ y v´ ysledek. Viditelné v´ ykyvy hodnot jsou zp˚ usobeny provádˇen´ım zmˇenové synchronizace. Hodnota zat´ıˇzen´ı znaˇc´ı na kolik je cel´ y server vyt´ıˇzen a kolik poˇzadavk˚ u je moˇzné jeˇstˇe vyˇr´ıdit (jedná se o ukazatel load z Unix systém˚ u). Obsah obou synchronizovan´ ych server˚ u byl po skonˇcen´ı synchronizaˇcn´ıho procesu shodn´ y, coˇz dokazuje správnost replikace. Generátor náhodn´ ych dokument˚ u vygeneroval po celou dobu testu dalˇs´ıch 2720 dokument˚ u.

58

6 Závˇer Navrˇzen´ y a implementovan´ y optimistick´ y replikaˇcn´ı algoritmus spolehlivˇe synchronizuje sd´ılen´ y obsah mezi servery vˇcetnˇe vˇsech jejich vlastnost´ı. Poˇrad´ı operac´ı pˇri replikaci se ˇr´ıd´ı kombinac´ı sémantické metody na základˇe povahy operac´ı a syntaktické metody reálného ˇcasu, kdy nen´ı moˇzné správnˇe ˇradit operace, pokud nejsou servery ˇcasovˇe synchronizovány. Algoritmus dále detekuje konflikty pˇri editaci stejného zdroje na v´ıce serverech souˇcasnˇe a automaticky je ˇreˇs´ı tak, aby nedoˇslo ke ztrátˇe proveden´ ych operac´ı, i kdyˇz se jedná o state-transfer protokol. Oˇsetˇreny jsou i r˚ uzné chybové stavy server˚ u, jako napˇr´ıklad konfliktn´ı kolekce nebo doˇcasnˇe nedostupn´ y server. Jak ukázal zátˇeˇzov´ y test, má synchronizace s pouˇzit´ım WebDAV rozhran´ı jisté v´ ykonnostn´ı problémy. Metoda PUT má pr˚ umˇernou dobu odpovˇedi 1 sekunda, coˇz pˇri potˇrebˇe replikovat velké mnoˇzstv´ı dokument˚ u znaˇcnˇe zpomaluje synchronizaci. Problém byl do jisté m´ıry vyˇreˇsen urychlen´ım aplikace pouˇzit´ım paraleln´ıch vláken, které spust´ı v´ıce metod PUT na serveru soubˇeˇznˇe, jelikoˇz server nen´ı jednou metodou plnˇe vyt´ıˇzen. Synchronizace je tak libovolnˇe ˇskálovatelná co se t´ yˇce mnoˇzstv´ı server˚ u, které m˚ uˇze synchronizovat. Zhorˇsen´ y v´ ykon se projev´ı aˇz pˇri nutnosti replikovat velk´ y poˇcet zdroj˚ u a proto je nutné správnˇe nastavit plánovaˇc tak, aby nedocházelo ke skokovému pˇret´ıˇzen´ı. Návrh algoritmu byl znaˇcnˇe omezen jak moˇznostmi WebDAV protokolu a jeho implementace Kerio Connect serverem, tak i nemoˇznost´ı zasahovat do implementace Kerio Connect serveru, coˇz by v nˇekter´ ych pˇr´ıpadech znaˇcnˇe zefektivnilo procesy. Algoritmus nedokáˇze pˇri pomalé synchronizaci spárovat dokument, kter´ y byl pˇred spárován´ım na jiné replice zmˇenˇen. Párován´ı prob´ıhá podle obsahu dokumentu a zmˇenˇen´ y dokument se od p˚ uvodn´ıho liˇs´ı, ˇc´ımˇz docház´ı k duplikaci obsahu. Pomalá synchronizace vˇsak má b´ yt spuˇstˇena pouze jednou pro inicializaci synchronizace, ˇc´ımˇz se dá problému jednoduˇse vyhnout. Pˇri velk´ ych objemech dat m˚ uˇze doj´ıt k v´ yraznému zpomalen´ı, jelikoˇz protokol WebDAV je state-transfer a je nutn´ y vˇzdy pˇrenos celého zmˇenˇeného dokumentu. Vlastnost state-transfer také zp˚ usobuje, ˇze server nev´ı a neoznamuje, kde pˇresnˇe v dokumentu zmˇena nastala. Navrˇzen´ y algoritmus vˇsak umoˇzn ˇuje lokalizovat zmˇeny v dokumentu pouˇzit´ım referenˇcn´ıho dokumentu a dokáˇze tak ˇreˇsit pˇr´ıpadné konflikty slouˇcen´ım nalezen´ ych zmˇen. Protokol WebDAV je vhodn´ y pro synchronizaci replik a to zejména d´ıky své jednoduchosti, moˇznostem zabezpeˇcen´ı a spolehlivosti v Kerio Connect serveru. V´ ykon synchronizaˇcn´ıho procesu je pˇritom pˇr´ımo u ´mˇern´ y rychlosti obsluhy WebDAV metod, je tedy moˇzné vylepˇsit Kerio Connect WebDAV rozhran´ı pro dosaˇzen´ı pˇr´ıznivˇejˇs´ıch v´ ysledk˚ u. Implementace algoritmu je provedená v programovac´ım jazyce C++ a efektivnˇe vyuˇz´ıvá pˇridˇelené programové prostˇredky. Aplikaci je moˇzné rozsáhle nastavit pro dosaˇzen´ı maximáln´ıho potenciálu dle konkrétn´ı instance distribuované domény. Synchronizace je tak i bez zásahu do Kerio Connect serveru v´ yznamn´ ym vylepˇsen´ım distribuované domény.

59

Seznam zkratek CVS DNS HTTP HTTPS HTTPU MIME NTP ORM RFC SAX SQL SVN TCP TLS URI URL WebDAV XML

Concurrent Versions System Domain Name System HyperText Transfer Protocol HyperText Transfer Protocol Secure HTTP protokolem UDP Multipurpose Internet Mail Extensions Network Time Protokol Object Relation Mapping Request for Comments Simple API for XML Structured Query Language Subversion Transmission Control Protocol Transport Layer Security Uniform Resource Identifier Uniform Resource Locator Web Distributed Authoring and Versioning Extensible Markup Language

60

Literatura [Connect] Kerio: Kerio Connect Dostupné na adrese: http://www.kerio.cz/cz/connect [Cormack] Gordon V. Cormack: A Calculus for Concurrent Update. Department of Computer Science, University of Waterloo, 1995 [Ghemawat] Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung: The Google File System, 2003 Google [Gilbert] Seth Gilbert, Nancy Lynch: Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, 2000 [Lamport] Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Massachusetts Computer Associates, Inc., 1978 [Log4cpp] Short introduction to Apache log4cx Dostupné na adrese: http://logging.apache.org/log4cxx/ [MSDN] Microsoft Developer Network: WebDAV Reference Dostupné na adrese: http://msdn.microsoft.com/en-us/library/aa486282%28v=exchg.65%29.aspx/ [Preguica] Nuno Preguic,a, Marc Shapiro, Caroline Matheson: Semantics-based reconciliation for collaborative and mobile environments. Dep. Informática, FCT, Universidade Nova de Lisboa, Portugal, Microsoft Research Ltd., Cambridge, UK, 2010 [Ramsey] Norman Ramsey, Elöd Csirmaz: An Algebraic Approach to File Synchronization. Foundations of Software Engineering, 2001 [RFC1945] RFC 1945: Hypertext Transfer Protocol – HTTP/1.0 Dostupné na adrese: https://tools.ietf.org/html/rfc1945 [RFC2426] RFC 2426: vCard MIME Directory Profile Dostupné na adrese: http://www.ietf.org/rfc/rfc2426.txt [RFC2445] RFC 2445: Internet Calendaring and Scheduling Core Object Specification (iCalendar) Dostupné na adrese: http://www.ietf.org/rfc/rfc2445.txt 61

LITERATURA

LITERATURA

[RFC2616] RFC 2616: Hypertext Transfer Protocol – HTTP/1.1 Dostupné na adrese: https://tools.ietf.org/html/rfc2616 [RFC2818] RFC 2818: HTTP Over TLS Dostupné na adrese: http://www.ietf.org/rfc/rfc2818.txt [RFC2822] RFC 2822: Internet Message Format Dostupné na adrese: http://www.ietf.org/rfc/rfc2822.txt [RFC4918] RFC 4918: HTTP Extensions for Distributed Authoring - WEBDAV Dostupné na adrese: http://www.ietf.org/rfc/rfc4918.txt [Saito] Yasushi Saito, Mark Shapiro: Optimistic Replication. ACM Computing Survey, Vol. V, No. N, 3 2005 [Thomas] Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. Bolt Beranek and Newman, Inc., 1979 [W3C] W3C: HTTP - Hypertext Transfer Protocol Dostupné na adrese: http://www.w3.org/Protocols/ Massachusetts Computer Associates, Inc.

62

A Uˇzivatelská pˇr´ıruˇcka Program je moˇzné pˇreloˇzit a spustit na platformách UNIX/Linux, Mac OS a Windows pro 32 i 64 bitové procesory. Minimáln´ı systémové poˇzadavky programu jsou: • procesor Intel Celeron 1,6 GHz nebo ekvivalentn´ı, • 512 MB RAM, • 100 MB voln´ ych na disku.

A.1

Instalace

Pˇred spuˇstˇen´ım instalace je nutné veˇskeré soubory a sloˇzky na pˇriloˇzeném CD zkop´ırovat na zapisovatelné médium, ideálnˇe pevn´ y disk, jelikoˇz jsou generovány soubory uvnitˇr sloˇzek.

A.1.1

UNIX/Linux

K instalaci a pˇrekladu synchronizaˇcn´ıho procesu pro systém Linux je nutné nainstalovat následuj´ıc´ı nástroje a bal´ıˇcky: • • • • •

g++ make libslite3-dev liblog4cpp5-dev libneon27-dev

Pˇredchoz´ı bal´ıˇcky je moˇzné jednoduˇse nainstalovat u Debian systém˚ u pˇr´ıkazem apt-get uvodu moˇzné nainstalovat install název bal´ıˇcku. Pokud nechcete nebo nen´ı z nˇejakého d˚ bal´ıˇcky knihoven lib*, je moˇzné pouˇz´ıt dodané zdrojové soubory a knihovny pˇreloˇzit. K pˇrekladu knihoven slouˇz´ı skript install-libraries.sh um´ıstˇen´ y v adresáˇri unix/. Skript spust´ıte jednoduˇse pˇr´ıkazem bash install-libraries.sh (pouˇzijte sudo, pokud nejste pˇrihláˇseni jako superuser) a automaticky jsou pˇreloˇzeny vˇsechny potˇrebné knihovny pro pˇreklad hlavn´ıho programu. Po u ´spˇeˇsné instalaci vˇsech potˇrebn´ ych knihoven program pˇreloˇz´ıte pˇr´ıkazem make proveden´ ym v adresáˇri unix/. Vznikne tak pˇreloˇzen´ y spustiteln´ y soubor unix/sync.

A.1.2

Windows

K instalaci a pˇrekladu na operaˇcn´ım systému Windows je pˇripraven projekt pro volnˇe dostupné Microsoft Visual Studio 2008 Express (dále jen VC8) um´ıstˇen´ y v adresáˇri windows/. Soubor projektu windows/KerioConnectSyncWin/KerioConnectSyncWin.vcproj jednoduˇse otevˇrete ve VC8 a dostanete projekt se vˇsemi potˇrebn´ ymi knihovnami. Projekt pˇreloˇz´ıte pˇr´ıkazem Build a vznikne nov´ y spustiteln´ y soubor v adresáˇri Release/ nebo Debug/, podle zvoleného profilu, s názvem KerioConnectSyncWin.exe vˇcetnˇe vˇsech potˇrebn´ ych knihoven pro spuˇstˇen´ı. 63

Uˇzivatelská pˇr´ıruˇcka

A.1.3

Nastaven´ı

MAC OS

Pˇreklad pro operaˇcn´ı systém MAC OS prob´ıhá obdobnˇe jako pro platformu Linux. Nejdˇr´ıve je nutné nainstalovat vˇsechny potˇrebné závislosti skriptem bash unix/install-libraries.sh (pouˇzijte sudo, pokud nejste pˇrihláˇseni jako superuser). Spustiteln´ y program unix/sync opˇet dostaneme spuˇstˇen´ım pˇr´ıkazu make v adresáˇri unix/.

A.2

Nastaven´ı

Pˇred prvn´ım spuˇstˇen´ım synchronizaˇcn´ıho procesu je nutné nastavit chován´ı procesu a hlavnˇe c´ılové servery, které maj´ı b´ yt procesem synchronizovány. K nastaven´ı programu slouˇc´ı XML konfiguraˇcn´ı soubor config.xml, kter´ y m˚ uˇze vypadat napˇr´ıklad následovnˇe: 1 2 3 database.sqlite 4 tmp/ 5 6 <enabled>1 7 <max nb workers>5 8 <min job worker>10 9 10 <delays> 11 60 12 20 13 <poll>20 14 15 <synchronize> 16 17 18 19 20 https://195.113.184.42:443/public 21 <user>u1 22 <password>∗∗∗ 23 cert/kerio−connect−42 24 25 26

kde • database - libovolná cesta k souboru, na které bude uloˇzena databáze synchronizaˇcn´ıho procesu. Databáze bude vytvoˇrena automaticky. • temporary storage - synchronizaˇcn´ı proces potˇrebuje pro svou ˇcinnost pr˚ ubˇeˇznˇe ukládat doˇcasné soubory na disk, tyto soubory vytváˇr´ı do nastavené sloˇzky. Sloˇzka mus´ı b´ yt pˇr´ıstupná pro zápis.

64


Spuˇstˇen´ı

• acceleration - synchronizaˇcn´ı proces je moˇzné urychlit, jak je popsáno v sekci 5.6, pouˇzit´ım vláken. Vlákna jsou ve v´ ychoz´ım nastaven´ı vypnuta, ale je moˇzné jejich pouˇzit´ı zapnout nastaven´ım enabled na hodnotu 1. Zapnut´ım urychlen´ı se budou automaticky vytváˇret aktualizaˇcn´ı vlákna. Pro vytváˇren´ı pracovn´ıch vláken slouˇz´ı nastaven´ı max nb workers pro urˇcen´ı nejvyˇsˇs´ıho poˇctu pracovn´ıch vláken a min job worker pro nastaven´ı nejmenˇs´ıho poˇctu operac´ı, které budou jednotlivá vlákna zpracovávat. • delays - pro optimalizaci plánovaˇce synchronizace je moˇzné nastavit jednotlivé ˇcasy v cel´ ych sekundách mezi spouˇstˇen´ım synchronizaˇcn´ıch metod. Pouˇzijte complete pro nastaven´ı ˇcasu mezi spuˇstˇen´ım kompletn´ı synchronizace, heuristic pro heuristickou metodu a poll pro aktivn´ı synchronizaci. • locations - proces m˚ uˇze synchronizovat libovolné mnoˇzstv´ı Kerio Connect server˚ u. Jednotlivé servery je moˇzné nastavit vloˇzen´ım elementu location. Nastaven´ı kaˇzdého serveru obsahuje: – uri - URI c´ılového serveru do koˇrenové kolekce synchronizace vˇcetnˇe protokolu a portu, – user - uˇzivatelské jméno pokud je vyˇzadována autentifikace, – password - heslo pro uˇzivatelské jméno, – certificate - soubor certifikátu, pokud je pouˇzit protokol HTTPS a certifikát serveru nen´ı ovˇeˇren certifikaˇcn´ı autoritou a je nutné jej ovˇeˇrit ruˇcnˇe. • synchronize - synchronizaˇcn´ı proces je moˇzné omezit na vybrané kolekce v koˇrenu synchronizace vˇsech server˚ u. Je moˇzné vloˇzit libovoln´ y poˇcet folder element˚ u s relativn´ı cestou ke kolekci, která má b´ yt v rámci procesu synchronizována.

A.3

Spuˇ stˇ en´ı

Jakmile je program nastaven XML konfigurac´ı, je moˇzné jej spustit pouˇzit´ım spustitelného souboru vytvoˇreného pˇri instalaci synchronizaˇcn´ıho procesu. Program je pouze konzolov´ y a je moˇzné jej spustit na pozad´ı. Pr˚ ubˇeˇzné v´ ystupy programu jsou zobrazovány na standardn´ı v´ ystup a zároveˇ n ukládány do log soubor˚ u. Pro vynucen´ı pomalé synchronizace pˇri existuj´ıc´ı databázi je moˇzné pouˇz´ıt pˇrep´ınaˇc -slow“ za pˇr´ıkazem pro spuˇstˇen´ı pro” gramu, napˇr´ıklad: 1 ./sync −slow

Log soubor zaznamenávaj´ıc´ı bˇeh aplikace je uloˇzen standardnˇe v log/run.log a statistiky synchronizace jsou uloˇzeny v souboru log/stats.log. Aplikace um´ı logovat r˚ uzné u ´rovnˇe hláˇsen´ı pro r˚ uzné kategorie, vˇse je moˇzné jednoduˇse nastavit u ´pravou souboru logging.properties, kter´ y lze libovolnˇe zmˇenit podle návodu pro Log4cpp [Log4cpp]. Pro bˇeˇzn´ y provoz aplikace je urˇcena u ´roveˇ n hláˇsen´ı NOTICE. Aplikace dˇel´ı hláˇsen´ı do ˇsesti kategori´ı: • sql - SQL dotazy a operace, • webdav - WebDAV klient, • sync - synchronizaˇcn´ı procesy, detekce a aktualizace zmˇen, 65


Spuˇstˇen´ı

• merge - ˇreˇsitel konflikt˚ u, • parse - ˇcten´ı strukturovan´ ych dokument˚ u, • stat - statistiky operac´ı.

66

Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Vícebodová synchronizace dat protokolem WebDAV

Recommend Documents