-
Notifications
You must be signed in to change notification settings - Fork 0
/
Lenart-thesis-2011.tex
2214 lines (1607 loc) · 179 KB
/
Lenart-thesis-2011.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%% History:
% Pavel Tvrdik (26.12.2004)
% + initial version for PhD Report
%
% Daniel Sykora (27.01.2005)
%
% Michal Valenta (3.12.2008)
% rada zmen ve formatovani (diky M. Duškovi, J. Holubovi a J. Žďárkovi)
% sjednoceni zdrojoveho kodu pro anglickou, ceskou, bakalarskou a diplomovou praci
% One-page layout: (proof-)reading on display
%%%% \documentclass[11pt,oneside,a4paper]{book}
% Two-page layout: final printing
\documentclass[11pt,twoside,a4paper]{book}
%=-=-=-=-=-=-=-=-=-=-=-=--=%
% The user of this template may find useful to have an alternative to these
% officially suggested packages:
\usepackage[slovak, english]{babel}
% \selectlanguage{english}
%
% \hyphenation{NoSQL}
\selectlanguage{slovak}
\hyphenation{NoSQL}
\hyphenation{Cassandra}
%\usepackage[slovak]{babel}
\usepackage[T1]{fontenc} % pouzije EC fonty
\usepackage{longtable}
% pripadne pisete-li cesky, pak lze zkusit take:
% \usepackage[OT1]{fontenc}
\usepackage[utf8]{inputenc}
%=-=-=-=-=-=-=-=-=-=-=-=--=%
% In case of problems with PDF fonts, one may try to uncomment this line:
\usepackage{lmodern}
\usepackage{url}
%=-=-=-=-=-=-=-=-=-=-=-=--=%
%=-=-=-=-=-=-=-=-=-=-=-=--=%
% Depending on your particular TeX distribution and version of conversion tools
% (dvips/dvipdf/ps2pdf), some (advanced | desperate) users may prefer to use
% different settings.
% Please uncomment the following style and use your CSLaTeX (cslatex/pdfcslatex)
% to process your work. Note however, this file is in UTF-8 and a conversion to
% your native encoding may be required. Some settings below depend on babel
% macros and should also be modified. See \selectlanguage \iflanguage.
%\usepackage{czech} %%%%%\usepackage[T1]{czech} %%%%[IL2] [T1] [OT1]
%=-=-=-=-=-=-=-=-=-=-=-=--=%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Styles required in your work follow %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{graphicx}
%\usepackage{indentfirst} %1. odstavec jako v cestine.
\usepackage{k336_thesis_macros} % specialni makra pro formatovani DP a BP
% muzete si vytvorit i sva vlastni v souboru k336_thesis_macros.sty
% najdete radu jednoduchych definic, ktere zde ani nejsou pouzity
% napriklad:
% \newcommand{\bfig}{\begin{figure}\begin{center}}
% \newcommand{\efig}{\end{center}\end{figure}}
% umoznuje pouzit prikaz \bfig namisto \begin{figure}\begin{center} atd.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand\TypeOfWork{Diplomová práca} \typeout{Diplomova prace}
% \newcommand\TypeOfWork{Master's Thesis} \typeout{Master's Thesis}
% \newcommand\TypeOfWork{Bakalářská práce} \typeout{Bakalarska prace}
% \newcommand\TypeOfWork{Bachelor's Project} \typeout{Bachelor's Project}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% nabidky jsou z: http://www.fel.cvut.cz/cz/education/bk/prehled.html
%\newcommand\StudProgram{Elektrotechnika a informatika, dobíhající, Bakalářský}
%\newcommand\StudProgram{Elektrotechnika a informatika, dobíhající, Magisterský}
% \newcommand\StudProgram{Elektrotechnika a informatika, strukturovaný, Bakalářský}
\newcommand\StudProgram{Otvorená informatika, Magisterský}
% \newcommand\StudProgram{Softwarové technologie a management, Bakalářský}
% English study:
% \newcommand\StudProgram{Electrical Engineering and Information Technology} % bachelor programe
% \newcommand\StudProgram{Electrical Engineering and Information Technology} %master program
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% nabidky jsou z: http://www.fel.cvut.cz/cz/education/bk/prehled.html
%\newcommand\StudBranch{Výpočetní technika} % pro program EaI bak. (dobihajici i strukt.)
\newcommand\StudBranch{Softwarové inžinierstvo} % pro prgoram EaI mag. (dobihajici i strukt.)
%\newcommand\StudBranch{Softwarové inženýrství} %pro STM
%\newcommand\StudBranch{Web a multimedia} % pro STM
%\newcommand\StudBranch{Computer Engineering} % bachelor programe
%\newcommand\StudBranch{Computer Science and Engineering} % master programe
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Vyplnte nazev prace, autora a vedouciho
% Set up Work Title, Author and Supervisor
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand\WorkTitle{Veľkoobjemové úložisko emailov}
\newcommand\FirstandFamilyName{Bc. Patrik Lenárt}
\newcommand\Supervisor{Ing. Jan Šedivý, CSc.}
% Pouzijete-li pdflatex, tak je prijemne, kdyz bude mit vase prace
% funkcni odkazy i v pdf formatu
\usepackage[
pdftitle={\WorkTitle},
pdfauthor={\FirstandFamilyName},
bookmarks=true,
colorlinks=true,
breaklinks=true,
urlcolor=red,
citecolor=blue,
linkcolor=blue,
unicode=true,
]
{hyperref}
% Extension posted by Petr Dlouhy in order for better sources reference (\cite{} command) especially in Czech.
% April 2010
% See comment over \thebibliography command for details.
\usepackage[square, numbers]{natbib} % sazba pouzite literatury
\usepackage{enumerate}
\usepackage{multirow}
\usepackage{booktabs}
\usepackage{capt-of}
%\usepackage{url}
%\DeclareUrlCommand\url{\def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}} %rm/sf/tt
%\renewcommand{\emph}[1]{\textsl{#1}} % melo by byt kurziva nebo sklonene,
\let\oldUrl\url
\renewcommand\url[1]{<\texttt{\oldUrl{#1}}>}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zvolte jednu z moznosti
% Choose one of the following options
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\selectlanguage{slovak}
%\selectlanguage{english}
% prikaz \typeout vypise vyse uvedena nastaveni v prikazovem okne
% pro pohodlne ladeni prace
\iflanguage{slovak}{
\typeout{************************************************}
\typeout{Zvoleny jazyk: cestina}
\typeout{Typ prace: \TypeOfWork}
\typeout{Studijni program: \StudProgram}
\typeout{Obor: \StudBranch}
\typeout{Jmeno: \FirstandFamilyName}
\typeout{Nazev prace: \WorkTitle}
\typeout{Vedouci prace: \Supervisor}
\typeout{***************************************************}
\newcommand\Department{Katedra počítačové grafiky a interakce}
\newcommand\Faculty{Fakulta elektrotechnická}
\newcommand\University{České vysoké učení technické v~Praze}
\newcommand\labelSupervisor{Vedúci práce}
\newcommand\labelStudProgram{Študijný program}
\newcommand\labelStudBranch{Odbor}
\newcommand\Date{13. mája 2011}
}{
\typeout{************************************************}
\typeout{Language: english}
\typeout{Type of Work: \TypeOfWork}
\typeout{Study Program: \StudProgram}
\typeout{Study Branch: \StudBranch}
\typeout{Author: \FirstandFamilyName}
\typeout{Title: \WorkTitle}
\typeout{Supervisor: \Supervisor}
\typeout{***************************************************}
\newcommand\Department{Department of Computer Science and Engineering}
\newcommand\Faculty{Faculty of Electrical Engineering}
\newcommand\University{Czech Technical University in Prague}
\newcommand\labelSupervisor{Supervisor}
\newcommand\labelStudProgram{Study Programme}
\newcommand\labelStudBranch{Field of Study}
}
%%%%%%%%%%%%%%%%%%%%%%%%%% Poznamky ke kompletaci prace
% Nasledujici pasaz uzavrenou v {} ve sve praci samozrejme
% zakomentujte nebo odstrante.
% Ve vysledne svazane praci bude nahrazena skutecnym
% oficialnim zadanim vasi prace.
{
\pagenumbering{roman} \cleardoublepage \thispagestyle{empty}
\chapter*{Na tomto místě bude oficiální zadání vaší práce}
\begin{itemize}
\item Toto zadání je podepsané děkanem a vedoucím katedry,
\item musíte si ho vyzvednout na studiijním oddělení Katedry počítačů na Karlově náměstí,
\item v~jedné odevzdané práci bude originál tohoto zadání (originál zůstává po obhajobě na katedře),
\item ve druhé bude na stejném místě neověřená kopie tohoto dokumentu (tato se vám vrátí po obhajobě).
\end{itemize}
\newpage
}
%%%%%%%%%%%%%%%%%%%%%%%%%% Titulni stranka / Title page
\coverpagestarts
%%%%%%%%%%%%%%%%%%%%%%%%%%% Podekovani / Acknowledgements
\acknowledgements
\noindent
Rád by som poďakoval vedúcemu práce pánovi Ing. Janovi Šedivému, CSc. za konzultácie, cenné rady, pripomienky a návrhy, ktoré mi ochotne poskytol počas vypracovávania tejto práce.
Taktiež sa chcem sa poďakovať svojim najbližším, bez ktorých podpory by táto práca nevznikla. Poďakovanie ďalej patrí Mgr. Jánovi Slaninkovi a Mgr. Ondrejovi Šterbákovi za ich cenné rady a korektúru textu.
%%%%%%%%%%%%%%%%%%%%%%%%%%% Prohlaseni / Declaration
\declaration{V~Prahe dňa 10.\,5.\,2011}
%\declaration{In Kořenovice nad Bečvárkou on May 15, 2008}
%%%%%%%%%%%%%%%%%%%%%%%%%%%% Abstract
\abstractpage
% The topic of this thesis is focused on design of email archiving solution using distributed database systems, which are commonly known as NoSQL.
% We made strong analysis of requirements for the high capacity and reliable storage of email messages, using attachments deduplication to provide efficient space saving. We described basic concepts which are used by distributed database systems. The main criteria were identified for high level comparison of modern NoSQL systems, then we chose two possible candidates which comply the aplication criteria. Functions and architectures of Cassandra and HBase systems were described, subjects were thoroughly tested for performance. We modelled and implemented the application prototype using Cassandra.
% The system was filled with roughly milion of email messages from the real environment. We found that deduplication saves about 65\% of the space.
The aim of this thesis is to design an email archiving solution using a distributed database system, commonly known as NoSQL. We described the basic concepts that are used by distributed database systems. We made a strong analysis of requirements for the high capacity and fault tolerant storage of email messages, featuring attachment deduplication to provide an efficient space saving. We identified main criteria for high level comparison of modern NoSQL systems, then we chose two possible candidates that comply with requirements. Functions and architectures of Cassandra and HBase systems were described, subjects were thoroughly tested performance wise. We modeled and implemented the application prototype using Cassandra.
% The system was filled with roughly a million of email messages from the real environment.
% We found that deduplication saves around 65\% of the space.
% Prace v cestine musi krome abstraktu v anglictine obsahovat i
% abstrakt v cestine.
\vglue45mm
\noindent{\Huge \textbf{Abstrakt}}
\vskip 2.75\baselineskip
\noindent
Cieľom práce je návrh riešenia pre archiváciu elektronickej pošty s~využitím distribuovaných databázových systémov, označovaných pod spoločným názvom NoSQL. V~práci sú popísané základné koncepty, ktoré sa využívajú pri tvorbe distribuovaných databázových systémov. Analyzovali sme požiadavky na veľkoobjemový a vysokodostupný archív emailových správ, ktorý bude z~dôvodu úspory diskového priestoru využívať deduplikáciu príloh. Stanovili sme základné kritéria na porovnanie NoSQL systémov, z~ktorých sme následne vybrali dvoch kandidátov, spĺňajúcich požiadavky systému. Popísali sme funkcionalitu systémov Cassandra a HBase, ktoré sme podrobili výkonnostným testom. Navrhli sme model a implementovali prototyp aplikácie využívajúci systém Cassandra.
% Po naplnení systému približne miliónom emailových správ z~reálneho prostredia, sa vďaka použitiu deduplikácie dosiahlo cca 65\% úspory diskového priestoru.
%Navrhli sme model a pomocou systému Cassandra sme následne implemetovali prototyp aplikácie, u ktorého sme vďaka použitiu deduplikácie dosiahli 60\% úsporu diskového priestoru, pri naplnení systému približne miliónom emailových správ z reálneho prostredia.
%aktuálne problémy, ktoré vznikajú pri ukladaní a spracúvani neustále narastajúceho objemu dát pomocou relačných databázových systémov. Na ich riešenie
%Cieľom tejto práce je návrh riešenia pre archiváciu elektronickej pošty s využitím distribuovaných databázových systémov, ktoré sa označujú pod spoločným názvom NoSQL. Analyzujeme požiadavky na veľkoobjemový a vysokodostupný archív emailových správ, ktorý bude z dôvodu úspory diskového priestoru využívať deduplikáciu. Skúmaním relačných databázových technológii sme identifikovali kritické body, na základe ktorých tieto systémy nespĺňaju naše požiadavky. Ako alternatívne riešenie volíme použitie NoSQL systémov, ktoré sa snažíme kategorizovať a následne z nich vybrať najhodnejších kandidátov pre požiadavky nášho systému. Zaoberáme sa architektúrou systémov Cassandra a HBase, ktoré podrobíme výkonnostným testom. Navrhli sme model a pomocou systému Cassandra sme následne implemetovali prototyp aplikácie. Po naplnení systému približne miliónom emailových správ, z reálneho prostredia, sme vďaka použitiu deduplikácie dosiahli 60\% úsporu diskového priestoru.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Obsah / Table of Contents
\tableofcontents
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Seznam obrazku / List of Figures
\listoffigures
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Seznam tabulek / List of Tables
\listoftables
%**************************************************************
\mainbodystarts
% horizontalní mezera mezi dvema odstavci
%\parskip=5pt
%11.12.2008 parskip + tolerance
\normalfont
\parskip=0.2\baselineskip plus 0.2\baselineskip minus 0.1\baselineskip
% Odsazeni prvniho radku odstavce resi class book (neaplikuje se na prvni
% odstavce kapitol, sekci, podsekci atd.) Viz usepackage{indentfirst}.
% Chcete-li selektivne zamezit odsazeni 1. radku nektereho odstavce,
% pouzijte prikaz \noindent.
%**************************************************************
% Pro snadnejsi praci s vetsimi texty je rozumne tyto rozdelit
% do samostatnych souboru nejlepe dle kapitol a tyto potom vkladat
% pomoci prikazu \include{jmeno_souboru.tex} nebo \include{jmeno_souboru}.
% Napr.:
% \include{1_uvod}
% \include{2_teorie}
% atd...
%*****************************************************************************
\chapter{Úvod}
%Úvod charakterizující kontext zadání, případně motivace.
S~neustálym rozvojom informačných technológií súčasne narastá objem informácií, ktoré je potrebné spracúvať. Tento fakt podnietil vznik databázových systémov, ktoré slúžia na organizáciu, uchovávanie a spracovanie dát. V~dnešnej dobe existuje veľké množstvo databázových systémov, ktoré sa navzájom líšia napríklad architektúrou, dátovým modelom alebo výrobcom.
Od začiatku sedemdesiatych rokov 20. storočia sú v~tejto oblasti dominantou relačné databázové systémy (Relational Database Management Systems). Z~dôvodu rapídneho rastu dát v~digitálnom univerze \cite{Gantz_Mcarthur_Minton_2007} začínajú byť tieto systémy nepostačujúce. Medzi hlavné faktory pre výber relačného databázového systému doposiaľ patrili výrobca, cena a pod. Vznikajúce moderné webové aplikácie (napríklad sociálne siete) požadujú od týchto systémov vlastnosti ako vysoká dostupnosť, horizontálna rozšíriteľnosť a schopnosť pracovať s~obrovským objemom dát (PB, petabajt\footnote{$ 1PB = 10^{15} B$}). Novo vznikajúce databázové systémy, spĺňajúce tieto požiadavky sa spoločne označujú pod názvom NoSQL (Not Only SQL). Pri ich výbere je dôležité porozumenie architektúry, dátového modelu a dát, s~ktorými budú tieto systémy pracovať.
Táto práca si kladie za cieľ viacero úloh a je rozdelená do dvoch logických častí. V~kapitole~2 popisujeme koncepty využívané pri tvorbe distribuovaných databázových systémov, ktoré zabezpečujú vysokú dostupnosť, spoľahlivosť a škálovateľnosť. Kapitola 3 definuje požiadavky na systém, schopný archivovať milióny emailových správ a tieto dáta ďalej spracúvať. Prehľad systémov NoSQL a kritéria pre ich porovnanie popisuje kapitola 4, ktorá v~závere doporučuje výber dvoch vhodných kandidátov, systém Cassandra a HBase. Architektonické princípy a vlastnosti, z~ktorých tieto systémy vychádzajú, sú popísané pre systém Cassandra v~kapitole 5 a pre HBase v~kapitole 6.
%TODO: kapitola 8 + popis implementacie
V~druhej časti práce sme v~kapitole~7 opísali výkonnostné porovnanie týchto dvoch systémov zamerané na operáciu zápisu dát. Návrh modelu systému,
nástroje pre implementáciu prototypu aplikácie emailového úložiska a samotnú implementáciu popisuje kapitola 8. Záver kapitoly tvorí overenie návrhu a doporučenie najvhodnejšieho systému. Záverečná kapitola popisuje dosiahnuté výsledky a možné pokračovanie práce v~budúcnosti.
%TODO: pkokracovanie prace v buducnu
% Záverečná čast, ktorú tvorí kapitola 9, popisuje dosiahnuté výsledky a doporučuje systém pre riešenie danej úlohy.
%Výsledná struktura vaší práce a názvy a rozsahy jednotlivých kapitol se samozřejmě budou lišit podle typu práce a podle konkrétní povahy zpracovávaného tématu. Níže uvedená struktura práce odpovídá \textit{práci implementační}, viz \cite{infodp} respektive \cite{infobp}.
\chapter{Databázové systémy}
V~tejto časti stručne popíšeme históriu vzniku databázových systémov. Identifikujeme problémy spojené so škálovaním relačných databázových systémov a uvedieme možné spôsoby ich riešenia. Ďalej popíšeme základné koncepty využívané pri tvorbe distribuovaných databázových systémov a techniku MapReduce, ktorá slúži na paralelné spracovanie veľkého objemu dát (PB).
\section{História}
V~polovici šesťdesiatych rokov 20. storočia bol spoločnosťou IBM vytvorený informačný systém IMS (Information Management System), využívajúci hierarchický databázový model. IMS je po rokoch vývoja využívaný dodnes. Po krátkej dobe, v~roku 1970, publikoval zamestnanec IBM, Dr. Edger F. Codd článok pod názvom „A Relational Model of Data for Large Shared Data Banks“ \cite{Codd:1970:RMD:362384.362685}, ktorým uviedol relačný databázový model. Prvým databázovým systémom implementujúcim tento model bol System R od IBM. Systém používal jazyk pod názvom SEQUEL, ktorý je predchodca dnešného SQL (Structured Query Language) slúžiaceho na manipuláciu a definíciu dát v~relačných databázových systémoch. Tento koncept sa stal základom pre relačné databázové systémy, ktoré vďaka širokej škále vlastností (ako napríklad podpora transakcií a dotazovací jazyk SQL) patria v~dnešnej dobe medzi najpoužívanejšie riešenia na trhu.
V~minulosti boli objem dát, s~ktorým tieto systémy pracovali menší a výkon hardvéru mnohonásobne nižší. Dnes napriek tomu, že výkon procesorov a veľkosť pamäťových zariadení rapídne stúpa, je najväčšou slabinou počítačových systémov rýchlosť prenosu dát medzi pevným diskom a operačnou pamäťou. Tento fakt je kritický pre novovznikajúce webové aplikácie ako napríklad sociálne siete alebo \emph{cloudové systémy}, ktoré majú neustále vyššie nároky na spracovávaný objem dát v~reálnom čase a vyžadujú podporu škálovania, ktorá zabezpečuje vysokú dostupnosť a spoľahlivosť. Tieto požiadavky sa snažia efektívne riešiť novovznikajúce distribuované systémy pod spoločným názvom NoSQL, ktoré sú popísané v~štvrtej kapitole tejto práce. %\ref{chapter:NoSQL}.
%TODO ref na 4kap
%Novo vznikajúce webové aplikácie ako napríklad sociálne siete a zavádzanie \emph{cloud computingu} majú neustále vyššie nároky na spracovávaný objem dát, od systémov vyžadujú podporu škálovania, ktorá zabezpečuje vysokú dostupnosť a spoľahlivosť. Tieto nové požiadavky sa snažia efektívne riešiť distribuované systémy pod spoločným názvom NoSQL, ktoré sú popísané štvrtej kapitole tejto práce.
\section{Distribuované databázové systémy}
Distribuovaný databázový systém je tvorený pomocou viacerých samostatne pracujúcich databázových systémov, ktoré nazývame uzly a ich komunikácia sa vykonáva prostredníctvom počítačovej siete. Užívateľovi alebo aplikácii sa javia ako jeden celok \cite{hewitt2010cassandra}. Podľa konfigurácie jednotlivých uzlov v~systéme ich ďalej delíme na:
\begin{itemize}
\item distribuované databázové systémy typu \emph{\uv{master-slave}}
\item decentralizované distribuované databázové systémy
\end{itemize}
\subsection*{Systémy master-slave}
Táto konfigurácia obsahuje uzol \emph{master}, ktorý plní jedinečnú úlohu a všetky uzly typu \emph{slave} sú na ňom závislé. V~prípade jeho havárie je ohrozená funkčnosť celého systému, nazývame ho kritický bod výpadku (SPOF, single point of failure). Túto konfiguráciu využívajú napríklad relačné databázové systémy.
\subsection*{Decentralizované systémy}
Pod názvom decentralizácia sa myslí, že každý uzol v~distribuovanom databázovom systémy vykonáva tú istú úlohu a je kedykoľvek nahraditeľný. Táto konfigurácia neobsahuje SPOF.
\section{ACID}
Relačné databázové systémy poskytujú veľkú množinu operácií, ktoré je možné vykonávať nad dátami v~nich uloženými. Transakcie \cite{gray1981transaction, haerder1983principles} sú zodpovedné za korektné vykonanie operácií v~prípade, že spĺňajú množinu vlastností ACID. Význam jednotlivých vlastností akronymu ACID je následovný:
\begin{itemize}
\item \emph{Atomicita} (Atomicity) - zaisťuje, že sa vykonajú všetky operácie reprezentujúce transakciu, čo spôsobí korektný prechod systému do nového stavu. V~prípade zlyhania transakcie nemá daná operácia žiaden vplyv na výsledný stav systému a prechod do nového stavu sa nevykoná.
\item \emph{Konzistencia} (Consistency) - každá transakcia po svojom úspešnom ukončení garantuje korektnosť svojho výsledku a zabezpečí, že systém prejde z~jedného konzistentného stavu do druhého. Konzistentný stav zaručuje, že dáta v~systéme odpovedajú požadovanej hodnote. Systém sa musí nachádzať v~konzistentnom stave aj v~prípade zlyhania transakcie.
\item \emph{Izolácia} (Isolation) - operácie, ktoré prebiehajú počas vykonávania jednej transakcie nie sú viditeľné ostatným. Operácie tvoriace transakciu musia mať konzistentný prístup k~dátam a to aj v~prípade, že u~inej transakcie dôjde k~jej zlyhaniu.
\item \emph{Trvácnosť} (Durability) - v~prípade, že bola transakcia úspešne ukončená, systém musí garantovať trvácnosť jej výsledku aj v~prípade svojho zlyhania.
\end{itemize}
%http://en.wikipedia.org/wiki/Concurrency_control#Concurrency_control_mechanisms
%http://en.wikipedia.org/wiki/Multiversion_concurrency_control
%http://en.wikipedia.org/wiki/Timestamp-based_concurrency_control
Implementácia vlastností ACID, ktoré zaručujú konzistenciu, zvyčajne využíva u~relačných databázových systémov metódu zamykania. Transakcia uzamkne dáta pred ich spracovaním a spôsobí ich nedostupnosť až do jej úspešného ukončenia, poprípade zlyhania. Transakcie sú vykonávané sekvenčne. Pre databázový systém, od ktorého požadujeme vysokú dostupnosť tento model nie je vyhovujúci. Zámky spôsobujú stavy, kedy ostatné transakcie musia čakať na ich uvoľnenie. Náhradou je mechanizmus s~názvom \uv{riadenie súbežného spracovania s~viacerými verziami} (MVCC, Multiversion concurrency control), ktorý umožňuje paralelné vykonávanie operácií nad dátami, jeho popis obsahuje práca od P. Bernsteina a N. Goodmana \cite{bernstein1981concurrency}. Tento mechanizmus je zároveň využívaný systémami NoSQL.
%http://en.wikipedia.org/wiki/2-phase_commit
%http://en.wikipedia.org/wiki/Two-phase_locking
% a operácií spojenia (join)
Transakcie splňujúce vlastnosti ACID využívajú v~distribuovaných databázových systémoch dvojfázový potvrdzovací protokol (Two-phase commit protocol \cite{bernstein1987concurrency}). Systém využívajúci tento protokol, zaručuje konzistentnosť aj v~prípade výskytu sieťových prerušení (network partitioning). Vlastnosti ACID nekladú žiadnu záruku na dostupnosť systému, naopak stav spôsobujúci nedostupnosť je žiadaný v~prípade vykonania operácie, ktorá by mohla spôsobiť nekonzistenciu dát. Systémy garantujúce ACID sú vhodné pre aplikácie, v~ktorých sa vykonávajú platobné operácie a pod. Medzi aplikácie, u~ktorých sa uprednostňuje dostupnosť dát pre ich konzistenciou patria hlavne moderné webové aplikácie. Pri tvorbe distribuovaných databázových systémov je preto potrebné upustiť z~niektorých ACID vlastností. Riešenie poskytuje model pod názvom BASE.
%\ref{section:base}.
%ACID makes no guarantees regarding availability; indeed, it is preferable for an ACID service to be unavailable than to function in a way that relaxes the ACID constraints. ACID semantics are well suited for Internet commerce transactions, billing users, or maintaining user profile information for personalized services
\section{Škálovanie databázového systému} %scalepub04.pdf
Obecná definícia pojmu \emph{škálovateľnosť} \cite{bondi2000characteristics} je náročná bez vymedzenia kontextu, ku ktorému sa vzťahuje. V~tejto kapitole budeme pojem škálovateľnosť chápať v~kontexte webových aplikácií, ktorých dynamický vývoj kladie na databázové systémy viacero požiadaviek. Medzi hlavné z~týchto požiadavkov patrí vysoká dostupnosť, spoľahlivosť a odolnosť systému voči chybám. Definujme škálovateľnosť databázového systému ako vlastnosť, vďaka ktorej je systém schopný spracúvať požiadavky webovej aplikácie v~definovanom časovom intervale. Typicky sa táto vlasnosť realizuje pridaním nových uzlov do aktuálneho systému s~využitím replikácie. Aplikácia týchto mechanizmov má za následok využitie distribuovaného databázového systému. Škálovateľnosť delíme na vertikálnu, horizontálnu a systému dodáva ďalšie z~nasledujúcich vlastnosti \cite{hewitt2010cassandra}:
\begin{itemize}
\item umožňuje zväčšiť veľkosť celkovej kapacity databáze a táto zmena by mala byť transparentná z~pohľadu aplikácie na dáta
\item zvyšuje celkové množstvo operácií, pre čítanie a zápis dát, ktoré je systém schopný vykonať v~danú časovú jednotku
\item v~určitých prípadoch môže zaručiť, že systém neobsahuje kritický bod výpadku
\item zvyšuje celkovú dostupnosť a spoľahlivosť systému
\end{itemize}
Vertikálna škálovateľnosť je metóda, ktorá sa aplikuje pomocou zvyšovania výkonnosti hardvéru, do systému sa pridáva operačná pamäť, rýchlejšie viacjadrové procesory, zvyšuje sa kapacita diskov. Jednou z~nevýhod tohoto riešenia je jeho vysoká cena a možná nedostupnosť systému v~prípade jeho zlyhania.
Proces vertikálneho škálovania sa hlavne aplikuje v~prípade použitia relačných databázových systémov a obsahuje následujúce kroky:
\begin{itemize}
\item zámena hardvéru za výkonnejší
\item úprava súborového systému (napr. zrušenie žurnálu a uchovávania informácie o~poslednom prístupe k~súborom)
\item optimalizácia databázových dotazov, použitie indexov
\item pridanie vrstvy pre kešovanie (memcached, EHCache, atď.)
\item denormalizácia dát v~databáze, čo ma za následok porušenie databázovej normalizácie
\end{itemize}
V~tomto prípade je možné naraziť na výkonnostné hranice bežne dostupného hardvéru a na rad nastupuje horizontálna škálovateľnosť, ktorá je omnoho komplexnejšia. Horizontálnu škálovateľnosť je možné realizovať pomocou využitia replikácie alebo metódou \emph{\uv{rozdeľovania dát}} (sharding).
\subsection{Replikácia}
V~distribuovaných systémoch má použitie replikácie za následok, že sa daná informácia nachádza na viacerých uzloch\footnote{Pod pojmom uzol v~tomto prípade myslíme samostatný počítačový systém, ktorý je súčasťou distribuovaného systému} tohto systému. Táto technika zvyšuje dostupnosť, spoľahlivosť a odolnosť systému voči chybám. Replikácia nie je určená pre zálohu dát.
V~prípade distribuované databázového systému sa časť informácií uložených v~databáze nachádza na viacerých uzloch. Toto usporiadanie môže napríklad zvýšiť výkonnosť operácií, ktoré pristupujú k~dátam a to tak, že dochádza k~čítaniu dát z~databázy paralelne z~viacerých uzlov. V~systéme obsahujúcom repliku dát nedochádza k~strate informácií v~prípade poruchy uzla. Replikácia a propagácia zmien (pridanie alebo odstránenie uzla s~replikou) v~systéme sú z~pohľadu aplikácie transparentné. Použitie replikácie nezvyšuje pridávaním nových uzlov celkovú kapacitu databáze. Problémom tejto techniky je konzistencia dát. Dáta sa zapisujú na viacero fyzicky oddelených uzlov a zmena sa nemusí prejaviť okamžite vo všetkých replikách. Z~pohľadu klienta pristupujúceho k~replikovaným dátam, môže byť ich obsah nekonzistentný. Medzi metódy pomocou, ktorých je možné zabezpečiť konzistenciu patria:
\begin{itemize}
\item
\emph{Read one - Write all} - u~tejto metódy sa čítanie dát prevedie z~ľubovolného uzla obsahujúceho repliku. Zápis dát sa vykoná na všetky uzly s~replikou a až v~prípade, že každý z~nich potvrdí úspech tejto operácie je výsledok považovaný za korektný. Táto metóda nie je schopná pracovať v~prípade ak dôjde k~prerušeniu sieťového spojenia medzi uzlami alebo v~prípade poruchy jedného z~uzlov.
\item
\emph{metóda kvóra} - funguje na princípe hlasovania, podrobnejší popis je v~časti \ref{section:Consistency}
\end{itemize}
% - zápis na jeden uzol a následná asynchrónna propagácia repliky na ostatné uzly. Táto metóda je schopná zvládať stav pri ktorom dojde k prerušeniu sieťového toku alebo poruche uzlu. Implementácie využíva algoritmy pod názvom kôrum konsenzus (quorum consensus). ???
%Výber metódy replikácie určuje dvojicu vlastností distribuovaného databázového systému a to dostupnosť a konzistenciu. Poďla teórie s názvom CAP \ref{section:CAP} nie je možné, aby systém súčastne poskytoval obe vlastnosti v prípade, že medzi jeho uzlami môže dôjsť k chybe v sieťovej komunikácii.
V~relačných databázových systémoch sa replikácia rieši pomocou architektúry master - slave. Uzol pod názvom master slúži ako jediný databázový stroj, na ktorom sa vykonáva zápis dát a replika týchto dát je následne distribuovaná na zvyšné uzly pod názvom slave. Táto metóda umožňuje mnohonásobne zvýšiť počet operácií, ktoré slúžia pre čítanie dát z~databázového systému a v~prípade zlyhania niektorého zo systémov máme neustále k~dispozícii kópiu dát. Slabinou v~tomto systéme je uzol v~roli master, ktorý nezvyšuje výkonnosť v~prípade operácií vykonávajúcich zápis a zároveň jeho porucha môže spôsobiť celkovú nedostupnosť systému.
Druhým možným riešením je technika \uv{multi - master}, kde každý uzol obsahujúci repliku je schopný zápisu dát a následne tieto zmeny preposiela ostatným. Tento mechanizmus predpokladá distribuovanú správu zamykania a vyžaduje algoritmy pre riešenie konfliktov v~prípade nekonzistentných dát.
\subsection{Rozdeľovanie dát}
Rozdeľovanie dát (sharding) je metóda založená na princípe, kde dáta obsiahnuté v~databáze rozdeľujeme podľa stanovených pravidiel do menších celkov. Tieto celky môžeme následne umiestniť na navzájom rôzne uzly distribuovaného databázového systému. Táto metóda umožňuje zvýšiť výkonnosť operácií pre zápis a čítanie dát a zároveň pridávaním nových uzlov do systému zvyšuje celkovú kapacitu databáze. V~prípade, že
architektúra distribuovaného databázového systému je navrhnutá s~využitím tejto metódy, zvýšenie výkonu operácií a objem uložených dát sa realizuje automaticky bez nutnosti zásahu do užívateľskej aplikácie.
%Pri tejto metóde môže byť použitá metóda transformácie kľúčov (hashing), pre vhodný výber úseku do ktorého budú zapisané dáta.
Techniku rozdeľovania dát môžeme považovať za aplikáciu architektúry známej pod názvom \uv{zdieľanie ničoho} (shared nothing) \cite{stonebraker1986case}. Táto architektúra sa používa pre návrh systémov využívajúcich multiprocesory. V~takomto prípade sa medzi procesormi nezdieľa operačná ani disková pamäť. Architektúra zabezpečuje takmer neobmedzenú škálovateľnosť systému a využíva ju mnoho NoSQL systémov ako napríklad Google Bigtable \cite{chang2008bigtable}, Amazon Dynamo \cite{decandia2007dynamo} alebo technológia MapReduce \cite{dean2008mapreduce}.
Pri návrhu distribuovaných databázových systémov s~využitím tejto techniky patrí medzi kľúčový problém implementácia funkcie spojenia (JOIN) nad dátami, ktorá sa preto neimplementuje. V~prípade, že sa, dáta nad ktorými by sme chceli túto operáciu vykonať, nachádzajú na dvoch rozdielnych uzloch prepojených sieťou, takéto spojenie by značne znížilo celkovú výkonnosť systému a viedlo by k~zvýšeniu sieťového toku, záťaži systémových zdrojov a možným nekonzistentným výsledkom.
%TODO: ggl paper - kde piseme ze s poruchou uzlov pocitame a bereme ju za prirodzeny fakt
Keďže sa dáta nachádzajú na viacerých uzloch systému, hrozí zvýšená pravdepodobnosť hardvérového zlyhania, poprípade prerušenie sieťového spojenia a preto sa táto technika často kombinuje s~pomocou využitia replikácie.
V~prípade použitia tejto techniky v~relačných databázových systémoch, je nutný zásah do logiky aplikácie. Dáta uložené v~tabuľkách relačnej databáze zachytávajú vzájomné relácie a týmto spôsobom dochádza k~celkovému narušeniu tohto konceptu. Príkladom môže byť tabuľka obsahujúca zoznam zamestnancov, ktorú rozdelíme na samostatné celky. Každá tabuľka bude reprezentovať mená zamestnancov, ktorých priezvisko začína rovnakým písmenom abecedy a zároveň sa bude nachádzať na samostatnom databázovom systéme. Táto technika so sebou prináša problém, v~ktorom je potrebné nájsť vhodný kľúč, podľa ktorého budeme dáta rozdeľovať a zabezpečíme tak rovnomerné zaťaženie uzlov v~systéme. Existuje viacero metód, ktoré je možné použiť pre rozdeľovanie dát na úrovni aplikácie \cite{hewitt2010cassandra}:
\begin{itemize}
\item
segmentácia dát podľa funkcionality - dáta, ktoré je možné popísať spoločnou vlastnosťou ukladáme do samostatných databáz a tieto umiestňujeme na rozdielne uzly systému. Príkladom môže byť samostatný uzol spravujúci databázu pre užívateľov a iný uzol s~databázou pre produkty. Túto metódu spracoval Randy Shoup\footnote{“If you can’t split, you cant scale it.” -- Randy Shoup, Distinguished architect Ebay} \cite{ebayShard}, architekt spoločnosti eBay.
%www.freeshareworld.com/wordpress/wp.../10/ebay_arch_principles.pdf
%www.addsimplicity.com/downloads/eBaySDForum2006-11-29.pdf
\item
rozdeľovanie dát podľa kľúča - v~dátach identifikujeme kľúč, s~ktorého využitím ich rovnomerne rozdelíme. Následne sa na tento kľúč aplikuje hašovacia funkcia a na základe jej výsledku sa tieto dáta umiestňujú na jednotlivé uzly.
\item
vyhľadávacia tabuľka - jeden uzol v~systéme slúži ako katalóg, ktorý určuje, na ktorom uzle sa nachádzajú dané dáta. Tento uzol zároveň spôsobuje zníženie výkonu a v~prípade jeho havárie spôsobuje nedostupnosť celého systému (SPOF).
\end{itemize}
Replikácia a rozdeľovanie dát patria medzi kľúčové vlastnosti využívané v~NoSQL systémoch, ktoré popisuje kapitola \ref{chapter:NoSQL}.
% spotrebny HARDWARE !!! u distrib db
\section{BASE} %dostupnost?
\label{section:base}
Akronym BASE bol prvýkrát použitý v~roku 1997 na sympóziu SOSP (ACM Symposium on Operating Systems Principles) \cite{fox1997cluster}. Tento model poľavil na požiadavku zodpovednom za konzistenciu dát, ktorý je garantovaný vlastnosťami ACID. BASE tvoria nasledujúce slovné spojenia:
\begin{itemize}
\item \emph{\uv{bežne dostupný}} (Basically Available) - systém je schopný zvládať čiastočné zlyhanie za cenu nižšej komplexity.
\item \emph{\uv{zmiernený stav}} (Soft State) - systém nezaručuje trvácnosť dát s~cieľom zvýšenia výkonu. %TODO: z papru precitat
\item \emph{\uv{eventuálne konzistentný}} (Eventually Consistent) - je možné na určitú dobu tolerovať nekonzistentnosť dát, ktoré musia byť po uplynutí určitého časového intervalu znovu konzistentné.
\end{itemize}
Využitím tohto modelu v~distribuovanom databázovom systéme sa dosahuje vyššia dostupnosť
aj v~prípade čiastočného zlyhania alebo sieťového prerušenia. Distribuovaný databázový systém môžeme klasifikovať ako systém spĺňajúci vlastnosti ACID, BASE alebo oboje.
BASE umožňuje horizontálne škálovanie relačných databázových systémov bez nutnosti použitia distribuovaných transakcií. Pre implementáciu tejto techniky môžeme použiť rozdeľovanie dát s~metódou segmentácie dát podľa funkcionality \cite{Pritchett:2008:BAA:1394127.1394128}.
Bankomatový systém je príkladom systému obsahujúceho eventuálnu konzistenciu dát. Po vybraní určitej čiastky z~účtu, sa korektná informácia o~aktuálnom zostatku môže zobraziť až za niekoľko dní, kdežto transakcia ktorá túto zmenu vykonala musí spĺňať vlastnosti ACID. Medzi webové aplikácie, u~ktorých sa nepožadujú všetky vlastnosti ACID patria napríklad nákupný košík spoločnosti Amazon\footnote{http://www.amazon.com}, zobrazovanie časovej osi aplikácie Twitter, poprípade systémy spoločnosti Google\footnote{http://www.google.com} indexujúce obsah webu. Ich nedostupnosť by znamenala obrovské finančné straty (napríklad zlyhanie vyhľadávania pomocou systému Google by znamenalo zobrazenie nižšieho počtu reklám, nedostupnosť nákupného košíka Amazon by spôsobila pokles predaja atp).
Aplikácia vyššie popísaných techník na relačné databázové systémy môže byť netriviálnou úlohou. V~tomto prípade, môžeme uvažovať alternatívne riešenia, medzi ktoré patria systémy NoSQL.
%BASE mnohonasobne ulahcuje implementaciu fault=tolerant a dostupnosti. Base model dokaze spracovat ciastocne vypadky (partial failure) v klastrovom rieseni za cenu nizsej komplexity ako ACID.
%BASE semantics allow us to handle partial failure in clusters with less complexity and cost.
%In practice, it is simplistic to categorize every service as either
%ACID or BASE; instead, different components of services demand
%varying data semantics. Directories such as Yahoo! [64] maintain a
%database of soft state with BASE semantics, but keep user customi-
%zation profiles in an ACID database.
% • By scalability, we mean that when the load offered to the
% service increases, an incremental and linear increase in
% hardware can maintain the same per-user level of service.
% • By availability, we mean that the service as a whole must be
% available 24x7, despite transient partial hardware or software
% failures.
% • By cost effectiveness, we mean that the service must be
% economical to administer and expand, even though it
% potentially comprises many workstation nodes
%
% Vyhoda clustrov: incremental scalability, high availability, and the cost/per-formance and maintenance benefits of commodity PC’s
%Fundamentálne požiadavky škálovateľných sieťových aplikácií sú: inkremenalna škálovateľnosť, dostupnosť 24x7, schopnosť odolávať chybám a rentabilita.
%A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, and P. Gauthier. Cluster-Based Scalable Network Services. In Proceedings of the 16th ACM Symposium on Operating Sys-tems Principles, St.-Malo, France, October 1997.
\section{CAP}
\label{section:CAP}
% http://codahale.com/you-cant-sacrifice-partition-tolerance/#ft1
%http://www.cloudera.com/blog/2010/04/cap-confusion-problems-with-partition-tolerance/
%Z predchádzajúceho textu a práce \uv{Cluster-base scalable network services} \cite{BASE} vyplýva, že pre splnenie týchto požiadavkov je vhodné použiť distribuované systémy,ktoré sú tvorené zo spotrebného hardvéru namiesto superpočítačov.
Moderné webové aplikácie kladú na systémy požiadavky, medzi ktoré patrí vysoká dostupnosť, slabá konzistencia dát a schopnosť odolávať chybám. Dr. Brewerer v~roku 2000 nastolil myšlienku, dnes známu pod názvom teória CAP \cite{brewer2000towards}. U~distribuovaných databázových systémov, ktoré používajú pre vzájomnú komunikáciu sieť musíme predpokladať s~prítomnosťou sieťových prerušení. Táto teória tvrdí, že u~takýchto systémov je možné súčasne dosiahnuť len dvojicu z~vlastností CAP a to CP alebo AP. V~roku 2002 platnosť tejto teórie pre asynchrónnu sieť matematicky dokázali Lynch a Gilbert \cite{Gilbert:2002:BCF:564585.564601}. Modelu asynchrónnej siete svojimi vlastnosťami zodpovedá Internet. Akronym CAP tvoria následujúce vlastnosti:
\begin{itemize}
\item
\emph{Konzistencia} (Consistency) - distribuovaný systém je v~konzistentnom stave, ak každý jeho uzol v~prípade požiadavku dát vracia správnu odpoveď.
%ak sa zmena aplikuje na všetky relevantné uzly systému v rovnakom čase.
%??? def podla Lynch?
%Každá operácia musí byť kompletne vykonanná a to ako jedna inštancia (tj. operácia je atomická) Musi existovat moznost linearneho usporiadania vsetkych operacii aj napriek tomu ze su distribuovane.---- Kazda cast celkoveho systemu, v pripade, poziadavku hodnotu dat vracia tu istu odpoved.
\item
\emph{Tolerancia chýb} (Partition Tolerance) - uzly distribuovaného systému navzájom komunikujú pomocou siete, v~ktorej hrozí strata správ. V~prípade vzniku sieťového prerušenia dané uzly medzi sebou navzájom nedokážu komunikovať. Táto vlasnosť podľa definície (viď. Gilbert a Lynch) tvrdí, že v~prípade vzniku zlyhania sieťovej komunikácie medzi niektorými uzlami, musí byť systém schopný naďalej pracovať korektne. V~reálnych podmienkach neexistuje distribuovaný systém, ktorého uzly na vzájomnú komunikáciu využívajú sieť a nedochádza pri tom k~strate správ, teda k~poruchám sieťovej komunikácie.
\item
\emph{Dostupnosť} (Availability) - distribuovaný systém je dostupný, ak každý jeho uzol, ktorý pracuje korektne, je schopný pri prijatí požiadavku zaslať odpoveď. V~spojení s~toleranciou chýb, tato vlastnosť hovorí, že v~prípade ak nastane sieťový problém\footnote{týmto sa nemyslí porucha uzla}, každá požiadavka bude vykonaná.
\end{itemize}
\noindent
Pravdepodobnosť, že dôjde k~zlyhaniu ľubovoľného uzla v~distribuovanom systéme, exponenciálne narastá s~počtom pribúdajúcich uzlov.
$$P(A) = 1 - P(B)^{\textrm{počet uzlov}}$$
\\
P(A) - pravdepodobnosť zlyhania ľubovoľného uzla \\
P(B) - pravdepodobnosť, že individuálny uzol nezlyhá
\subsection{Konzistencia verzus dostupnosť}
V~distribuovanom systéme nie je možné súčasne zaručiť vlasnosť konzistencie a dostupnosti. Ako príklad si predstavme distribuovaný systém obsahujúci tri uzly A, B, C, ktorý zaručuje obe vlastnosti aj v~prípade vzniku sieťového prerušenia. Na všetkých uzloch sa nachádzajú identické (replikované) dáta. Ďalej uvažujme, že došlo k~sieťovému prerušeniu, ktoré rozdelilo uzly na dva samostatné celky \{A,B\} a \{C\}. V~prípade, že uzol C obdrží požiadavku pre zmenu dát má na výber z~dvoch možnosti:
\begin{enumerate}
\item vykonať zmenu dát čo spôsobí, že sa uzly A~a B o~tejto zmene dozvedia až vo chvíli ak bude sieťové spojenie obnovené
\item zamietnuť požiadavku na zmenu dát, z~dôvodu že uzly A~a B sa o~tejto zmene nedozvedia
\end{enumerate}
V~prípade výberu možnosti číslo 1 zabezpečíme neustálu dostupnosť systému, naopak v~prípade možnosti číslo 2 jeho konzistenciu. Nie je možný súčasný výber oboch možností.
\subsubsection*{CP}
Ak od daného systému tolerujúceho sieťové prerušenia požadujeme konzistenciu na úkor dostupnosti jedná sa o~alternatívu CP. Takýto systém zabezpečí konzistentnosť operácií pre zápis a čítanie dát a zároveň sa môže stať, že na určité požiadavky nebude schopný reagovať (v~prípade možnosti číslo 2). Medzi takéto systémy môžeme zaradiť distribuovaný databázový systém Google Bigtable alebo systém využívajúci dvojfázový potvrdzovací protokol.
\subsubsection*{AP}
V~prípade, že poľavíme na požiadavku konzistencie tak takýto systém bude vždy dostupný aj napriek sieťovým prerušeniam. V~tomto prípade sa jedná o~alternatívu AP. Je možné, že v~takomto systéme bude dochádzať ku konfliktným zápisom alebo operácie čítania budú po určitú dobu vracať nekonzistentné výsledky. Tieto problémy s~konzistenciou sa v~distribuovaných databázových systémoch riešia napríklad pomocou metódy \uv{vektorových hodín} (Vector clock) \cite{decandia2007dynamo} a na aplikačnej úrovni na strane klienta. Príkladom systému patriaceho do tejto kategórie je Amazon Dynamo.
\subsubsection*{CA}
Ak systém nebude tolerovať sieťové prerušenia, tak bude splňovať požiadavok konzistencie a dostupnosti, varianta CA. Jedná sa o~nedistribuované systémy pracujúce na jednom fyzickom hardvéri využívajúce databázové transakcie. Tieto vlastnosti splňuje napríklad relačný databázový systém MySQL.
% Vyššie popísané vlastnosti nám umožnia vhodný výber distribuovaného databázového systému podľa požiadavkov našej aplikácie.
Pri výbere distribuovaného databázového systému, môžeme vďaka vyššie popísaným vlastnostiam určiť vhodnosť jeho použitia, na základe požiadavkov aplikácie.
%
%P = tolerance to network partitions
%R + W > N popisat
%Je potrebne vhodne vybrat jednu z dvojic na zaklade poziadavkov na nase data a model aplikacie.
\section{Eventuálna konzistencia}
%http://horicky.blogspot.com/2009/01/design-pattern-for-eventual-consistency.html
% data nezdielaju ziadny stav, oproti ACID kde sa zdiela stav
V~distribuovaných systémoch sa pod pojmom konzistencie v~ideálnych podmienkach rozumie vlastnosť, ktorá zaručí, že zmena dát (zápis alebo aktualizácia dát) sa prejaví súčasne s~rovnakým výsledkom. Konzistencia je zároveň úzko spojená s~replikáciou. Väčšina NoSQL systémov poskytuje eventuálnu konzistenciu, poprípade dáva možnosť výberu medzi vlastnosťami CP a AP (napríklad systém Cassandra\footnote{http://cassandra.apache.org}). V~následujúcej časti popíšeme rôzne druhy konzistencie.
V~predchádzajúcom texte sme už spomínali, že v~dnešnej dobe existuje mnoho aplikácií, u~ktorých je možné poľaviť na požiadavku konzistencie. Ak sa určitá zmena prejaví s~miernym oneskorením funkčnosť systému nebude v~tomto prípade ohrozená. Táto konzistencia nie je totožná s~konzistenciou definovanou u~vlastností ACID, kde ukončenie transakcie zaručuje, že sa systém nachádza v~konzistentnom stave. Na konzistenciu sa môžeme pozerať z~dvoch pohľadov. Prvým, je klientský pohľad na strane zadávateľa problému resp. programátora, ktorý rozhodne aká je závažnosť zmien, ktoré sa budú vykonávať v~systéme. Druhý pohľad je systémový, zabezpečuje technické riešenie a implementáciu techník zodpovedných za správu konzistencie v~distribuovaných databázových systémoch.
\subsection{Konzistencia z~pohľadu klienta}
Pre potrebu následujúcich definícii uvažujme distribuovaný databázový systém, ktorý tvorí úložisko dát a tri nezávislé procesy \{A, B, C\}, ktoré môžu v~danom systéme zmeniť (vykonať zápis) a načítať hodnotu dátovej jednotky. Na základe toho ako jednotlivé nezávislé procesy pozorujú zmeny v~systéme delíme konzistenciu na \cite{vogels2009eventually}: \\
\noindent
\emph{Silná konzistencia} (Strong consistency) - proces A~vykoná zápis. Po jeho ukončení je nová hodnota dátovej jednotky dostupná všetkým procesom \{A, B, C\}, ktoré k~nej následne pristúpia (vykonajú operáciu čítania). Túto konzistenciu zabezpečujú transakcie s~vlastnosťami ACID.
\noindent
\\
\emph{Slabá konzistencia} (Weak consistency) - proces A~vykoná zápis novej hodnoty do dátovej jednotky. V~takomto prípade systém negarantuje, že následne pristupujúce procesy \{A, B, C\} k~tejto jednotke vrátia hodnotu zapísanú procesom A. Definujeme pojem \uv{nekonzistentné okno}, ktoré zabezpečí, že po uplynutí stanovenej časovej doby sa táto nová hodnota dátovej jednotky prejaví vo všetkých procesoch, ktoré k~nej pristúpia.
\noindent
\\
\emph{Eventuálna konzistencia} (Eventual consistency) - je to špecifická forma slabej konzistencie. V~tomto prípade systém garantuje, že ak sa nevykoná žiadna nová zmena hodnoty dátovej jednotky, po určitom čase budu všetky procesy pristupujúce k~tejto jednotke schopné vrátiť jej korektnú hodnotu. Tento model ma viacero variácií, niektoré z~nich popíšeme v~nasledujúcej časti textu.
\noindent
\\
Model eventuálnej konzistencie ma viacero variácií:\\
\noindent
\\
\emph{Read-your-write consistency} - v~prípade, že proces A~zapíše novú hodnotu do dátovej jednotky, žiadny z~jeho následujúcich prístupov k~tejto jednotke nevráti staršiu hodnotu ako naposledy zapísaná.
\noindent
\\
\emph{Session consistency} - v~tomto prípade pristupuje proces k~systému v~kontexte relácií. Po dobu trvania relácie platí predchádzajúci typ konzistencie. V~prípade zlyhania relácie sa vytvorí nová, v~ktorej môže systém vracať hodnotu dátovej jednotky, zapísanú pred vznikom predchádzajúcej relácie.
\noindent
\\
\emph{Monotonic read consistency} - v~prípade, že proces načítal hodnotu dátovej jednotky, tak pri každom následujúcom prístupe k~jednotke, už nemôže vrátiť jej staršiu hodnotu. \\
Tieto typy konzistencie je možné navzájom kombinovať a ich hlavným cieľom je zvýšiť dostupnosť distribuovaného systému na úkor toho, že poľavíme na požiadavkoch konzistencie. Príkladom systému s~eventuálnou konzistenciou je asynchrónna replikácia v~relačnom databázovom systéme využívajúca architektúru master-slave.
\subsection{Systémová konzistencia}
%http://web.mit.edu/6.033/2005/wwwdocs/quorum_note.html
%http://en.wikipedia.org/wiki/Quorum_%28distributed_computing%29
\label{section:Consistency}
Techniky založené na protokoloch kvóra (Quorum-based protocols \cite{gifford1979weighted}) je možné použiť pre zvýšenie dostupnosti a výkonu v~distribuovaných databázových systémoch s~garanciou silnej alebo eventuálnej konzistencie. Definujme nasledujúcu terminológiu:
\begin{itemize}
\item N - počet uzlov, ktoré obsahujú repliku dát
\item W - počet uzlov obsahujúcich repliku, na ktorých sa musí vykonať zápis, aby bola zmena úspešne potvrdená
\item R - počet uzlov s~replikou, ktoré musia vrátiť hodnotu dátového objektu v~prípade operácie čítanie
\end{itemize}
V~prípade, že platí $W + R > N$, operácie pre zápis a čítanie dát sa stále prekrývajú minimálne na jednom uzle, ktorý bude vždy obsahovať aktuálnu hodnotu danej operácie. Tento prípad, zabezpečuje silnú konzistenciu v~systéme. V~prípade $W + R <= N$, môže nastať situácia keď predchádzajúca podmienka neplatí a teda daná operácia je eventuálne konzistentná. Rôzna konfigurácia týchto parametrov zabezpečí rozdielnu dostupnosť a výkonnosť distribuovaného systému. Uvažujme následujúce príklady pre $N = 3$.
\begin{enumerate}
\item $R = 1$ a $W = N$, tento prípad zabezpečí, že systém bude optimalizovaný pre operácie čítania dát. Klient číta dáta z~ľubovoľnej repliky. Operácie budú konzistentné, pretože uzol z~ktorého dáta čítame sa prekrýva s~uzlami na ktorých vykonávame zápis. Nevýhodou tohoto modelu je, že nedostupnosť aspoň jednej repliky znemožní vykonanie zápisu. V~prípade systémov, u~ktorých požadujeme aby obsluhovali veľký počet požiadaviek pre čítanie sa môže hodnota $N$ pohybovať v~stovkách až tisícoch, závisí to od počtu uzlov v~systéme.
\item $W = 1$ a $R = N$, tento prípad je vhodný pre systémy u~ktorých požadujeme rýchly zápis. Tento model môže spôsobiť stratu dát v~prípade zlyhania uzla s~replikou, na ktorú bol vykonaný zápis.
\item $W = 2$ a $R = 2$, zabezpečí optimálne nastavenie, systém bude silne konzistentný. Tento prípad je využívaný v~aplikáciach spoločnosti Amazon využívajúcich systém Dynamo.
\end{enumerate}
%TODO obrazky
\section{MapReduce}
%http://horicky.blogspot.com/2008/11/hadoop-mapreduce-implementation.html
%http://horicky.blogspot.com/2009/11/what-hadoop-is-good-at.html
%Ako príklad si vezmime konfiguráciu počítačového systému, ktorá obsahuje pevný disk, na ktorom je uložených 640 GB dát a operačnú pamäť veľkosti 32 GB. Spracovanie dát procesorom uložených v operačnej pamati, je rýchlejšie ako v prípade ich uloženia na pevnom disku. Hlavnou brzdou je ich načitanie do operačnej pamäti, čo vyžaduje množstvo vstupno výstupných (V/V) diskových operácií. Pre rýchle spracúvanie dát je veľkosť 32 GB len zlomok celkovej veľkosti dát uložených na pevnom disku. Tento problém dokážeme efektívne riešiť pomocou využitia distribuovaných systémov.
Nárast diskových kapacít a množstva dát, ktoré na nich ukladáme spôsobuje jeden z~ďalších problémov, ktorým je analýza a spracovanie dát. Kapacita pevných diskov sa za posledné roky mnohonásobne zvýšila v~porovnaní s~dobou prístupu a prenosových rýchlosti pre čítanie a zápis dát na tieto zariadenia.
Pre jednoduchosť uvažujme nasledujúci príklad, v~ktorom chceme spracovať pomocou jedného počítačového systému 1 TB dát uložených na lokálnom súborovom systéme, pri priemernej prenosovej rýchlosti diskových zariadení 100 MB/s. Za ideálnych podmienok by čas na prečítanie týchto dát presahoval dve a pol hodiny. V~prípade, že by sme 1 TB dát rovnomerne rozdelili na sto počítačov a tieto úseky paralelne spracovali, celková doba by sa znížila za ideálnych podmienok na necelé dve minúty.
Spoločnosť Google v~roku 2004 zverejnila programovací model pod názvom MapReduce, ktorý slúži na paralelne spracovanie obrovského objemu dát (PB). Model využíva vlastnosti paralelných a distribuovaných systémov, je optimalizovaný pre beh na klastri tvorenom vysokým počtom (tisícky) spotrebných počítačov. Pred programátorom sa snaží zastrieť všetky problémy, ktoré prináša paralelizácia výpočtov, poruchovosť systémov, distribúcia dát vzhľadom na ich lokalitu a rovnomerné rozdeľovanie záťaže medzi systémami. MapReduce využíva informácie o~lokalite dát, výpočet nad danými dátami sa vykonáva priamo na uzle kde sú umiestnené, čo je hlavnou výhodou v~porovnaní s~inými aplikáciami pre distribuovaný výpočet (napr. \emph{Grid computing}, kde môžu byť dáta presúvané na uzly, ktoré nad nimi vykonajú výpočet).
MapReduce nie je vhodný na spracovanie dát v~reálnom čase. Je optimalizovaný na dávkový beh. Jeho implementácia spoločnosťou Google, ktorá zároveň využíva distribuovaný súborový systém Google File System (GFS) \cite{ghemawat2003google}, nie je k~dispozícii. V~rámci hnutia NoSQL vzniklo open source riešenie pod názvom Hadoop \cite{hadoopW}, ktoré implementuje tento model na vlastnom distribuovanom súborovom systéme Hadoop Distributed File System (HDFS). K~dispozícii sú aplikácie HIVE alebo PIG, ktoré sú nadstavbou modelu MapReduce a poskytujú vyššiu abstrakciu vo forme jazyka podobného SQL.
%TODO PRIKLAD?
% \subsection{Príklad}
% ? histogram slov
Pre použitie tohoto nástroja musí programátor zadefinovať dve funkcie pod názvom \emph{map} a \emph{reduce}. Funkcia \emph{map} na jednotlivých uzloch systému, transformuje vstupné dáta na základe zadefinovaného kľúča $k$ a k~nemu prináležiacim hodnotám $H$ na medzivýsledok, ktorý obsahuje nové kľúče $g_1,...,g_n$ a k~ním odpovedajúce hodnoty $I$. Tieto dáta sú zoskupené a zoradené podľa kľúčov a následne odoslané na uzly vykonávajúce užívateľom definovanú funkciu \emph{reduce}. Funkcia \emph{reduce} vykoná nad hodnotami priradenými ku kľúčom $g_1,...,g_n$ požadovanú operáciu, ktorej typickým výsledkom je jedna výsledná hodnota, poprípade viacero hodnôt $I$. Tieto operácie je možné popísať následovne:
\begin{verbatim}
map(k, H) -> list(g, I)
reduce(g, list(I)) -> list(I)
\end{verbatim}
\subsection*{Príklad}
Uvažujme vstupné dáta popísané v~tabuľke \ref{tab:mapred} Nad dátami chceme spočítať celkovú veľkosť emailových správ, ktoré prináležia jednotlivým doménam. V~tomto prípade bude vstupom do funkcie \emph{map} ako kľúč $k$ číslo riadku v~tabuľke, $H$ budú tvoriť jednotlivé hodnoty v~stĺpcoch odpovedajúce riadku. Aplikáciou funkcie \emph{map}, ktorá v~tomto prípade bude zabezpečovať výber hodnôt zo stĺpcov \emph{doména} a \emph{veľkosť} dostaneme následujúci možný výstup:
\begin{verbatim}
(d2.net, 80)
(d1.com, 12)
(d2.net, 65)
(d1.com, 3)
(d3.sk, 12)
(d2.net, 102)
\end{verbatim}
\noindent
Jednotlivé záznamy sú následne zoskupené a zotriedené interne aplikáciou Hadoop:
\begin{verbatim}
(d1.com, [12, 3])
(d2.net, [65, 80, 102])
(d3.sk, [12])
\end{verbatim}
\noindent
Výsledok je vstupom do funkcie \emph{reduce}, kde kľúč $g$ bude reprezentovaný názvom domény a $list(I)$ budú tvoriť jednotlivé veľkosti emailových správ. Výstupom budú dvojice:
\begin{verbatim}
(d1.com, 15)
(d2.net, 247)
(d3.sk, 12)
\end{verbatim}
Dáta obsiahnuté v~tabuľke sa môžu nachádzať na ľubovoľnom počte počítačov so systémom Hadoop, ktorý zabezpečí aby na jednotlivých uzloch bola vykonaná funkcia \emph{map} a jej výsledky sa pošlú na náhodné uzly vykonávajúce funkciu \emph{reduce}. Týmto sa zabezpečí plne distribuovaný výpočet bez nutnosti preposielania zdrojových dát, čo môže efektívne znížiť zaťaženie siete a zvýšiť spoľahlivosť výpočtu.
{\centering%
\label{tab:001}\par\bigskip
\begin{tabular}{llrl}\toprule
\multicolumn{1}{c}{doména} & \multicolumn{1}{c}{adresa} & \multicolumn{1}{c}{veľkosť} &\multicolumn{1}{c}{dátum}\\\midrule\addlinespace
d1.com & jan@d1.com & 12 & 02/01/2011\\\addlinespace
d3.sk & jan@d3.sk & 12 & 02/01/2011\\\addlinespace
d2.net & jeny@d2.net & 65 & 02/05/2011\\\addlinespace
d1.com & john@d1.com & 3 & 03/02/2011\\\addlinespace
d2.net & jenny@d2.net & 80 & 03/06/2011\\\addlinespace
d2.net & andre@d2.net & 102 & 21/02/2011\\\addlinespace
\hline
\end{tabular}\\}
\captionof{table}{Vstupné dáta pre funkciu \emph{map}}\label{tab:mapred}
\par\bigskip
%(s ktorými v tejto práci budeme pracovat?)
%
% [3]
% [4] http://www.google.com/trends?q=noSQL
% [6] http://storagemojo.com/2010/11/29/moores-wall-the-end-of-moores-law/
% 7 The Transaction Concept:Virtues and Limitations
% 8 THEO HAERDER Principles of Transaction-Oriented Database Recovery
% 10 Eric A. Brewer. Towards robust distributed systems. (Invited Talk) Principles of Distributed Computing, Portland, Oregon, July 2000.
% 11 Brewer’s Conjecture and the Feasibility of% Consistent, Available, Partition-Tolerant Web% Services
% 12 Eventually Consistent - Werner Vogels
% 13 C-Store: A Column-oriented DBMS
% 14 Column-Oriented Database Systems
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Definícia problému}
Množstvo digitálnych informácii každým rokom prudko narastá. Podľa štatistík spoločnosti IDC \cite{Gantz_Mcarthur_Minton_2007} v~roku 2006 dosahovala kapacita digitálneho univerza veľkosť 161 exabajtov\footnote{$1 EB = 10^{18}B$}(EB). Podiel elektronickej pošty (emailov) bez spamu, tvoril 3\% z~tohoto objemu. Predpoveď na rok 2011 \cite{Gantz_Chute_Manfrediz_Minton_Reinsel_Schlichting_Toncheva_2008} predpokladá celkovú kapacitu 1800 EB, čo je viac ako desaťnásobok nárastu pôvodnej kapacity v~období piatich rokov. V~rozmedzí rokov 1998 až 2006 sa mal počet schránok elektronickej pošty zvýšiť z~253 miliónov na 1.6 miliardy. Predpoveď IDC ďalej uvádzala, že po ukončení roku 2010 tento počet presiahne hodnotu dvoch miliard. Počas obdobia medzi rokmi 1998 až 2006 celkový počet odoslaných správ elektronickej pošty rástol trikrát rýchlejšie ako počet jej užívateľov, dôvodom tohoto prudkého nárastu bola nevyžiadaná elektronická pošta. Odhaduje sa, že až 85\% dát z~celkového predpokladaného objemu 1800 EB budú spracovávať, prenášať alebo zabezpečovať organizácie. Napriek tejto explózii digitálnych informácii je potrebné správne porozumieť hodnote týchto dát, nájsť vhodné metódy pre ich ukladanie do pamäti počítačových systémov, ich archiváciu a to tak, aby sme ich mohli ďalej spracúvať a efektívne využiť. Táto kapitola práce si kladie za cieľ analyzovať potreby pre archiváciu elektronickej pošty a definovať požiadavky pre vysokodostupný systém slúžiaci k~archivácii emailov.
%štruktúru dát, ktoré reprezentujú elektronickú poštu (tj. emaily) a v následujúich kapitolách následne pomocou využitia vhodných databázových technológií popísať a navrhnúť model systému pre ich archiváciu.
\section{Archivácia elektronickej pošty}
% S neustálym nárastom informácii obsiahnutých v digitálnom univerze, sa zároveň zvyšuje objem dát, ktorý reprezentuje elektronickú poštu.
S~narastajúcim objemom dát reprezentujúcim elektronickú poštu je potrebné porozumieť tejto štruktúre a následne tieto dáta vhodne spracovať. Cieľom je ukladať emailové správy tak aby sme dosiahli úsporu diskového priestoru, boli sme nad nimi schopný vykonávať operácie ako fulltextové vyhľadávanie, zber údajov pre tvorbu štatistík alebo umožnili ich opätovné sprístupnenie. Emaily obsahujú čoraz viac obchodných informácií a iný dôležitý obsah, z~tohto dôvodu musia byť organizácie všetkých rozmerov schopné uchovávať tento obsah pomocou vhodných archivačných nástrojov. S~problémom archivácie zároveň úzko súvisí problém bezpečnosti. Pod pojmom bezpečnosti v~tejto oblasti máme na mysli hlavne ochranu proti nevyžiadanej pošte tj. spam, spyware, malware a phishingu. Na boj proti týmto hrozbám využívajú organizácie antispamové a antivírusové systémy. Možné dôvody prečo archivovať elektronickú poštu sú následovné \cite{WhyArchiving}:
\begin{itemize}
\item
záloha dát a ich obnova v~prípade havárie systému
\item
vysoká dostupnosť dát
\item
sprístupnenie dát koncovému užívateľovi
\item
spĺňanie regulačných noriem a zákonov
\item
ochránia súkromia a e-Discovery
\item
vyťažovanie dát (data mining)
\item
efektívne využitie úložného priestoru (deduplikácia príloh)
\end{itemize}
\section{Požiadavky na systém}
V~následujúcej časti popíšeme požadované vlastnosti systému, ktorý bude slúžiť na archiváciu veľkého objemu emailových správ. Primárnou požiadavkou na systém je jeho neustála dostupnosť, rozšíriteľnosť a nízkonákladová administrácia. Predpokladané množstvo uložených dát v~tomto systéme bude dosahovať desiatky až stovky terabajtov\footnote{$1 TB = 10^{12} B$} (TB). Takúto kapacitu dát nie je možne uchovať na jednom počítačovom systéme tvorenom z~bežne dostupného hardvéru. Dáta uložené v~systéme musia byť replikované, v~prípade vzniku havárie niektorej z~jeho časti. Nad uloženými emailovými správami je potrebné vykonávať výpočtovo náročné operácie ako generovanie štatistík a fulltextové vyhľadávanie v~reálnom čase. Tieto požiadavky prirodzene implikujú využitie distribuovaného databázového systému. Medzi hlavných kandidátov, vďaka ktorým sme tieto požiadavky schopní vyriešiť patria NoSQL databázové systémy, ktoré popíšeme v~následujúcej kapitole.
\subsection{Funkcionálne požiadavky}
\subsubsection*{Ukladanie emailov}
Základnou jednotkou, ktorú budeme do systému ukladať je emailová správa. Graf na obrázku \ref{fig:emailHist} znázorňuje usporiadanie emailov podľa ich veľkosti nad vzorkom približne 1,000,000 emailových správ z~reálneho prostredia\footnote{Vzorok emailov pre analýzu bol sprístupnený spoločnosťou Excello.}. Z~daných dát vyplýva, že veľkosť cca 80\% emailov je do 50 kB. Tieto údaje sú hrubou aproximáciou a závisia na konkrétnych používateľoch.
Systém musí umožňovať uloženie emailu bez porušenia jeho integrity. V~prípade sprístupnenia emailu nemôže dôjsť k~zmene alebo porušeniu dát. Kľúčovým požiadavkom je ukladanie emailových príloh, kde požadujeme aby každá príloha bola jednoznačne identifikovaná a v~prípade jej duplicity nebola opakovane uložená v~systéme. Cieľom je dosiahnutie efektívnej úspory diskového priestoru. Ďalším požiadavkom je automatické zmazanie emailov uložených v~systéme, po predom špecifikovanej dobre, ktoré prináležia danej doméne.
\begin{figure}[h]
\centering
\includegraphics[width=12cm]{./figures/emailsHist.png}
% topologies802154.png: 722x407 pixel, 72dpi, 25.47x14.36 cm, bb=0 0 722 407
\caption{Približná distribúcia emailových správ. $\mu = 301\,\mathrm{kB}$, $\sigma = 1.3\,\mathrm{MB}$}
\label{fig:emailHist}
\end{figure}
\subsubsection*{Export emailov}
Systém musí umožňovať prístup k~ľubovoľnému uloženému emailu v~jeho pôvodnej podobe poprípade skupine všetkých emailov patriacej danému užívateľovi (inbox).
\subsubsection*{Vyhľadávanie emailov}
Vyhľadávanie je potrebné realizovať nad všetkými emailovými správami uloženými v~systéme, jednotlivo nad správami podľa názvu domény a nad správami, ktoré prináležia danému užívateľovi. Požadujeme fulltextové vyhľadávanie emailov podľa následujúcich údajov:
%nachádzajúcich sa v obálke, podľa hlavičiek (predmet správy, odosielateľ, príjemca), podľa textu obsiahnutom v tele správy a podľa názvu prílohy.
\begin{itemize}
\item
príjemca emailovej správy
\item
odosielateľ emailovej správy
\item
predmet správy
\item
dátum obsiahnutý v~hlavičke emailovej správy
\item
identifikátor emailu (\emph{MessageID})
\item
názvy príloh a ich veľkosti %TODO aj velkosti?
\item
veľkosť emailu
\item
vyhľadávanie v~tele emailu
\end{itemize}
\newpage
\noindent
Pre administrátorské účely požadujeme vyhľadávanie údajov podľa: %TODO ref na popis email struct
\begin{itemize}
\item originálny odosielateľ a príjemca
\item IP adresa odosielateľa
\item dátum a čas spracovania správy emailovým serverom
\end{itemize}
\subsubsection*{Štatistické údaje}
Nad uloženými dátami požadujeme výpočet štatistík pomocou využitia MapReduce. Pre emaily patriace do danej domény je potrebné spracovať následujúce štatistické ukazovatele:
\begin{itemize}
\item
počet emailov označených príznakom spam
\item
počet emailov bez príznaku spam
\item
celková veľkosť emailov pre danú doménu
\item
veľkosť najväčšieho emailu v~doméne
\item
celková dĺžka filtrácie emailov v~danej doméne %TODO>pod ciaru odkia a co to reprezentuje>doba spracovania emailu pomocou antivírových a antispamových aplikácií
\end{itemize}
\noindent
%TODO: v pigu doriesit statistiky - hodit do zaveru?
Nad celým úložiskom je ďalej potrebné spracovať tieto štatistiky:
\begin{itemize}
\item
počet všetkých emailov
\item
počet unikátnych domén
\item
počet unikátnych príloh
%\item
%počet deduplikácií
\end{itemize}
% \begin{itemize}
% \item
% vyhľadávanie emailov podľa údajov tvoriacich obálku, podľa hlavičiek (predmet, odosielateľ, príjemca), podľa textu obsiahnutom v tele správy a podľa názvu prílohy
% \item
% prístup koncových užívateľov k archívu, jeho prehľadávanie, export vybraných emailov
% \item
% tvorba štatistík (ich konkrétny popis)
% \item
% expirácia emailov uložených v databáze po predom určenej dobe
% \item
% unikátne ukladanie príloh emailov z dôvodu úspory diskového priestoru
% \end{itemize}
%Emailová správa je štruktúrovaný objekt, časť z našich funkcií systému bude s touto štruktúrou a jej časťami pracovať, rozhodli sme sa, že náš výber noSQL systému zúžime na tie systémy, ktoré využívajú stĺpcový dátový model.
\subsection{Nefunkcionálne požiadavky}
\subsubsection*{Dostupnosť}
%TODO:ref do slovnicka - def. network partiti
Systém musí byť neustále dostupný (99,9\%), schopný odolávať sieťovým prerušeniam spôsobujúcim nedostupnosť uzlov, úplným zlyhaniam jednotlivých uzlov a umožňovať spracúvať tok pre zápis dát v~rozmedzí 10 Mbit až 1 Gbit. Ďalším požiadavkom je aby sa dáta replikovali vo vnútri dátového centra (datacenter) na dva uzly a tretia replika bola umiestnená v~dátovom centre, ktoré sa bude nachádzať na geograficky odlišnom mieste. Vyžadujeme aby systém neobsahoval kritický bod výpadku, požadujeme vlastnosť decentralizácie.
\subsubsection*{Rozšíriteľnosť}
%TODO:ref do slovnicka - def. commodity hw
Predpokladáme použitie bežne dostupného spotrebného hardvéru\footnote{Komponenty sú štandardizované, bežne dostupné a ich cenu neurčuje výrobca (IBM, DELL,...) ale trh. Príkladom môže byť konfigurácia s~pevným diskom 2 x 250 GB SATA, 4-12 GB RAM, 8 jadrový CPU.} (commodity hardware), namiesto superpočítačov. Z~dôvodu neustalého nárastu objemu elektronickej pošty, musí systém podporovať horizontálne škálovanie, ktoré bude umožňovať zvýšenie celkovej kapacity dátového úložiska (desiatky petabajtov). Pridávanie nových uzlov do systému umožní zvýšiť celkový výpočtový výkon, ktorý sa využije na spracovanie dát pomocou metódy MapReduce. U~distribuovaného databázového systému je nutná podpora replikácie, ktorá zvýši výkonnosť operácií pre čítanie, zápis a vďaka nej nebude potrebné riešiť zálohovanie pomocou externých systémov.
\subsubsection*{Nízkonákladová administrácia}
Prevádzkovanie systému a jeho administrácia by mali byť čo najmenej závislé na zásahu ľudských zdrojov. Detekcia nefunkčných uzlov a automatické rozdeľovanie záťaže sa musí vykonávať automaticky. Pridanie poprípade odobranie nového uzla nesmie ovplyvniť beh celkového systému.
\subsubsection*{Bezpečnosť}
Osoby s~oprávnením pre prístup k~systému budú schopné manipulovať s~jeho celým obsahom. Predpokladáme beh systému v~bezpečnom prostredí a nekladieme žiadne požiadavky na užívateľské role v~kontexte prístupu k~dátam.
\subsubsection*{Implementačné požiadavky}
Cieľom je implementácia systému s~využitím dostupných open source technológií.
%TODO dalsie problemy - ako to odsadit?
\subsubsection*{}
Z~analýzy princípov, v~predchádzajúcej kapitole, ktoré využívajú relačné databázové systémy vyplýva, že použitie týchto systémov nie je vhodné pre riešenie zadefinovaného problému. Medzi základné problémy týchto systémov patrí náročné horizontálne škálovanie, čo negatívne ovplyvňuje primárny požiadavok vysokej dostupnosti. Ďalším problémom je realizácia replikácie dát, ktorá spôsobuje prítomnosť SPOF. V~nasledujúcej kapitole sa budeme zaoberať popisom NoSQL systémov a po ich analýze vyberieme vhodného kandidáta, ktorého použijeme k~implementácii prototypu, z~dôvodu vysokej komplexnosti riešeného problému.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{NoSQL}
\label{chapter:NoSQL}
Názov NoSQL bol prvýkrát použitý v~roku 1998 ako názov relačnej databáze\footnote{http://www.strozzi.it/cgi-bin/CSA/tw7/I/en\_US/nosql}, ktorej implementácia bola v~interpretovaných programovacích jazykoch a neobsahovala dotazovací jazyk SQL. V~druhej polovici roku 2009 sa názov NoSQL začal používať v~spojení s~databázovými systémami, ktoré nepoužívajú tradičný relačný model, dotazovací jazyk SQL, sú schopné horizontálneho škálovania, pracujú na spotrebných počítačových systémoch, vyznačujú sa vysokou dostupnosťou a používajú bezschémový dátový model.
Pôvodným cieľom hnutia NoSQL bolo vytvoriť koncept, pre tvorbu moderných databázových systémov, ktoré by boli schopné spracúvať požiadavky neustále sa rozvíjajúcich webových aplikácií. Filozofiou týchto systémov je nesnažiť sa za každú cenu prispôsobovať dáta, ktoré do nich ukladáme relačnému databázovému modelu. Cieľom je vybrať systém, ktorý bude čo najvhodnejšie zodpovedať požiadavkám pre uloženie a spracovanie dát. NoSQL nepopisuje žiaden konkrétny databázový systém, namiesto toho je to obecný názov pre nerelačné (non-relational) databázové systémy, ktoré disponujú odlišnými vlastnosťami a umožňujú prácu s~rôznymi dátovými modelmi. Medzi ich ďalšie znaky patrí napríklad eventuálna konzistencia, schopnosť spracúvať obrovské objemy dát (PB) a jednoduché programové rozhranie (API). Tieto systémy nepodporujú operáciu databázového spojenia a medzi dátami, ktoré do nich ukladáme je možné vytvárať vzájomné závislosti až na aplikačnej úrovni. Pre tieto databázové systémy ďalej platí, že sú distribuované, automaticky poskytujú replikáciu a rozdeľovanie dát. Jedná sa o~relatívne mladé systémy, ktoré sú neustále vo vývoji. Ideou tohto konceptu je riešiť spomínané novovznikajúce problémy a zároveň koexistovať s~relačnými databázovými systémami.
%v pripade relac db sa snazime navrhnut datovy model a nasledne na nom vytvorit vhodne poziadavky v SQL, u tychto systemov vsak plati, ze na zaklade toho ako budu vyzerat dotazy na data namodelujeme datovy model (scheme free)
\section{Dátové modely}
% \section{Dátové modely}
NoSQL systémy delíme na dokumentové, grafové, stĺpcové a systémy s~dátovým modelom typu \uv{kľúč-hodnota} (Key-value). V~následujúcej časti práce ich stručne popíšeme.
% \subsection{Relačný dátový model}
% %TODO: podla pokorneho opravit ? relacie
% Relačný databázový model reprezentuje dáta pomocou riadkov tabuliek. Tieto riadky reprezentujú relácie, ktoré modelujú závislosti medzi dátami. Popis stĺpcov určuje schému relácie.
%
%
%
% tvorené stĺpcami a ich štruktúra je popísaná schémou. Schéma definuje názvy tabuliek, stĺpcov a podlieha normalizácii aby sa predišlo duplikácii dát. Pre zabezpečenie referenčnej integrity jednotlivých entít sa využívajú cudzie kľúče.
% Každý riadok tabuľky reprezentuje dáta, ktoré sa nazývajú záznamy a tieto sú následne sekvenčne ukladané na pevný disk. Tento model, nazývaný aj ako riadkový, je vhodný pre systémy, u ktorých sú dominantné operácie vykonávajúce zápis. Relačné databázové systémy, využívajúce tento model sú teda optimalizované pre zápis. Pre efektívny prístup k dátam je možné použiť indexy.
%
% NoSQL systémy delíme na dokumentové, grafové, stĺpcové a systémy s dátovým modelom typu \uv{kľúč-hodnota} (Key-value). V následujúcej časti práce ich stručne popíšeme.
\subsection{Relačný model}
Pre porovnanie stručne popíšeme štandardný relačný model. Databázový model reprezentuje dáta pomocou relácií, ktoré tvoria riadky uložené v~tabuľkách. Štruktúra týchto záznamov je normalizovaná, aby sa predišlo ich duplikácii. Pre zabezpečenie referenčnej integrity jednotlivých entít sa využívajú cudzie kľúče. Tabuľky s~popisom názvov stĺpcov a vzťahy medzi nimi nazývame databázovou schémou. Záznamy sú sekvenčne ukladané na pevný disk. Tento model je vhodný pre systémy, u~ktorých sú dominantné operácie vykonávajúce zápis. Relačné databázové systémy sú teda optimalizované pre zápis. Pre efektívny prístup k~dátam je možné použiť indexy. Relačný model, je spôsob reprezentácie dát, ktorý umožňuje efektívne riešiť určité typy úloh, preto snaha prispôsobiť tento model každému problému môže byť neefektívna. Tabuľka \ref{tab:relacnyModel} zachytáva ukážku tabuľky v~relačnom databázovom systéme.
\begin{table}[hp]
\begin{center}
\begin{tabular}{l|l|l|l}
Kľúč & Meno & Adresa & Telefón\\ \hline
1&Ján Mak & Zikova, Praha & 773234512 \\
2&John Smith & Broodway, NYC & 14941234\\
3&Mary Novak & Vodickova, Praha & 603192301\\
\end{tabular}
\end{center}
\caption{Reprezentácia dát v~relačnom modeli}
\label{tab:relacnyModel}
\end{table}
%
% \begin{table}[hp]
% \begin{center}
% \begin{tabular}{l|l}
%
% Kľúč & Meno \\ \hline
%
% 1&Ján Mak \\
% 2&John Smith\\
% 3&Mary Novak \\
%
% \end{tabular}
% \end{center}
% \caption{Reprezentácia dát v stĺpcovom modely}
% \label{tab:Nosql}
% \end{table}
%
% \begin{table}[hp]
% \begin{center}
% \begin{tabular}{l|l}
%
% Kľúč & Adresa\\ \hline
%
% 1&Zikova, Praha \\
% 2&Broodway, NYC\\
% 3&Vodickova, Praha \\
%
% \end{tabular}
% \end{center}
% \caption{Reprezentácia dát v stĺpcovom modely}
% \label{tab:Nosql}
% \end{table}
%TODO: na vsetky DB ref??
\subsection{Kľúč-hodnota}
%http://ayende.com/Blog/archive/2010/03/29/that-no-sql-thing-keyvalue-stores.aspx
Tento model využíva pre ukladanie dát jednoduchý princíp. Blok dát s~ľubovoľnou štruktúrou je v~databáze uložený pod názvom kľúča, ktorý je často interne reprezentovaný ako pole bajtov a môže ním byť napríklad textový reťazec. Databázové systémy využívajúce tento dátový model majú jednoduché programové rozhranie:
\begin{verbatim}
void Put(string key, byte[] data);
byte[] Get(string key);
void Remove(string key);
\end{verbatim}
Výhodou tohto modelu je, že databázový systém je možné ľahko škálovať. V~tomto prípade prácu so štruktúrou uložených dát zabezpečuje klient, čo umožňuje dosahovať vysokú výkonnosť na strane databázového systému.
Jednou z~možných nevýhod v~porovnaní s~relačnými databázovými systémami je, že databázový systém nie je schopný medzi uloženými dátami zachytiť ich vzájomné vzťahy (relácie), čo môže byť jednou z~požiadaviek pri tvorbe komplexných modelov. Úložisko typu kľúč-hodnota nevyužíva normalizáciu dát, dáta sú často duplikované, vzťahy a integrita medzi nimi sa riešia až na aplikačnej úrovni. Na obsah vkladaných dát a k~nim asociovaným kľúčom sa nedefinujú žiadne obmedzenia.
Medzi databázové systémy využívajúce model kľúč-hodnota patria Amazon Dynamo, Tokyo Cabinet, Voldemort, Redis a iné.
\subsection{Stĺpcovo orientovaný model}
%10.1.1.151.2270.pdf
%obrazok?
%abadiph.pdf
V~dnešnej dobe existuje veľký počet aplikácií, u~ktorých prevládajú operácie čítania nad zápisom. Patria sem dátové sklady, systémy pre vyťažovanie dát alebo analytické aplikácie pracujúce s~obrovským objemom dát. Pre potreby týchto aplikácií a ich reprezentáciu dát je vhodné použiť stĺpcový model \cite{abadi2009column, abadi2009}, ktorý je optimalizovaný pre operácie čítania dát. Dáta reprezentujúce stĺpce sú uložené na pevnom disku v~samostatných a súvislých blokoch. Načítanie dát do pamäti a následná práca s~nimi je efektívnejšia ako u~relačných databázových systémoch, kde je potrebné načítať celý záznam obsahujúci aj hodnoty stĺpcov, ktoré sú v~daný moment irelevantné. Možný príklad reprezentácie tabuľky \emph{Zamestnanec} zachytáva tabuľka~\ref{tab:columnModel}, stĺpce \emph{Kľúč} je možne vynechať. V~tomto prípade budú v~logickej reprezentácii jednotlivé položky záznamov tvorené dátami na rovnakých pozíciach v~daných stĺpcoch.
% V~tomto prípade, v~logickej reprezentácii budú riadky uložené v~rovnakom poradí reprezentovať jeden záznam.
Relačný model obsahuje v~jednom zázname dáta z~rôznych domén, čo spôsobuje vyššiu entropiu v~porovnaní so stĺpcovým modelom, kde sa predpokladá, že dáta v~danom stĺpci pochádzajú z~totožnej domény a sú si preto podobné. Táto vlasnosť umožňuje efektívnu komprimáciu dát, ktorá znižuje počet diskových operácií. Nevýhodou tohto modelu je zápis dát, ktorý spôsobuje vyššiu záťaž diskových operácií, z~dôvodu že stĺpce môžu byť fyzicky reprezentované ako samostatné súbory. Pre optimalizáciu operácií vykonávajúcich zápis sa používa dávkový zápis.
% obrazok ?
%\subsubsection*{Stĺpcovo orientovaný model v NoSQL}
%http://ayende.com/Blog/archive/2010/05/14/that-no-sql-thing-column-family-databases.aspx
%Predchodcom tohto nového prístupu k stĺpcovému modelu v NoSQL systémoch je databázový systém Bigtable od spoločnosti Google. Detailnejšie tento model popíšeme v TODO následujúcej kapitole.
%-- a na dáta pozeráme ako na viacdimenzionálnu hešovú-mapu.
%??? obrazok
Tento model využívajú databázové systémy ako Google Bigtable, HBase \cite{hbaseW}, Hypertable \cite{hypertableW} alebo Cassandra.
\begin{table}[hp]
\begin{tabular}
{lll}
\begin{minipage}{4cm}