Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter1.tex @ 58:3c070028199b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added consistency_quorum
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 01 Feb 2014 02:12:17 +0900
parents 39c2180b5719
children 81508c27228a
comparison
equal deleted inserted replaced
57:39c2180b5719 58:3c070028199b
5 本章ではまずデータベースの種類であるRelational DatabaseとNoSQL について述べる. 5 本章ではまずデータベースの種類であるRelational DatabaseとNoSQL について述べる.
6 次に, 分散データシステムにおいて重要な CAP 定理について触れる. 6 次に, 分散データシステムにおいて重要な CAP 定理について触れる.
7 最後に既存の NoSQL データベースとして Cassandra, MongoDB, Neo4j の特徴について述べる. 7 最後に既存の NoSQL データベースとして Cassandra, MongoDB, Neo4j の特徴について述べる.
8 8
9 \section{Relational Database} 9 \section{Relational Database}
10 Relational Database（RDB）は最も長く広く使われているデータベースである. 10 RDBは列と行からなる2次元のテーブルにより実装されるデータベースである.
11 列と行からなる2次元のテーブルによるスキーマは 11 データ型として文字列, 数値, 日付, BOOL型がありシステムによりデータに型が強制される.
12 RDBはスキーマの決まったデータを扱うことに長けている.
13 構造化言語問い合わせ言語としてSQLがある.
12 14
15 RDBはデータベースの中でも長年主要な立ち位置にあるデータベースだが, 苦手としている
16 ことがある.
17 それは, スキーマレスなデータの扱いやマシンの台数を増やして処理速度
18 をあげることである.
19 それらRDBが苦手としていることを得意とするNoSQLと呼ばれるデータベースがある.
13 20
14 \section{RDB と NoSQL} 21 \section{NoSQLデータベース}
15 データベースは大別するとRDBとNoSQLに分けられる. 22 NoSQLはNot Only SQLの略で, SQLを使わないデータベースのことを指す.
16 RDBとは行と列からなる2次元のテーブルによりデータを保持するデータベースである. 23 NoSQLデータベースはRDBとは違いスキーマがない.
17 RDBはデータベースアクセス言語としてSQL言語を持ち, 一台のマシンでデータを扱う分には最適である. 24 そのため, 扱おうとしているデータの形が決まっていなくても気軽に使うことができる.
18 しかし, RDB はマシン単体以上の処理性能をだすことができない. 25 また, スケーラビリティも持ちあわせており, 汎用的なマシンを集めることで性能をあげる
19 そこで, 汎用的なPCをいくつも用意しデータや処理を分散して管理できるデータベースが求められた. 26 ことができるといった特徴を持つ.
20 それらのデータベースはNoSQL（Not Only SQL） と呼ばれSQLを使用しないデータベースのことを指す. 27
21 2次元のテーブルでは無く, Key-Value, ドキュメント, グラフといった表現形式でデータの保持を行う.
22 NoSQLは, RDBには向いていない処理を行うことを目的にしている. 28 NoSQLは, RDBには向いていない処理を行うことを目的にしている.
23
24 % 分散データベースは, NoSQL に分けられる.
25 29
26 \section{CAP 定理} 30 \section{CAP 定理}
27 分散データシステムにおいて次の3つを同時に保証することはできない 31 分散データシステムにおいて次の3つを同時に保証することはできない
28 \begin{itemize} 32 \begin{itemize}
29 \item 一貫性(Consistency) 33 \item 一貫性(Consistency)
39 分断耐性を必要とする場合は NoSQL データベースとなる. 43 分断耐性を必要とする場合は NoSQL データベースとなる.
40 そしてNoSQLの場合, 分断耐性と後もう一つ, 一貫性か可用性のどちらを保証しているかで用途が変わってくる. 44 そしてNoSQLの場合, 分断耐性と後もう一つ, 一貫性か可用性のどちらを保証しているかで用途が変わってくる.
41 45
42 分散データシステムを考える場合は, この CAP 定理を意識していなければならない. 46 分散データシステムを考える場合は, この CAP 定理を意識していなければならない.
43 47
44
45 \section{Cassandra}
46 Cassandra\cite{cassandra} は2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである.
47 AmazonのDynamo\cite{dynamo} という分散Key-Valueデータベースの影響を受けて作られている.
48 スキーマレスな NoSQL データベースになる.
49
50 Cassandraはサーバノードの配置にConsistent hashingアルゴリズムを用いる.
51 Consistent hashingによりノードは論理的にリング上に配置される.
52 リングには数値で表される位置がある.
53 データを書き込む際には, キーとなるハッシュ値に従いそのリングの位置から時計回りに近いサーバノードへと書き込まれる.
54 Consistent hashingを用いることで, ノードの数が増減した場合に, 再配置をしなくてもよいという利点がある.
55 データの偏りにより少数のサーバへの負荷が大きい場合に, 負荷が高いハッシュ値が指すリング上に
56 新たなノードを追加することで負荷を下げるといった手段もとれる.
57
58 データを最大どれだけ配置するかを示すReplication factorと, データの読み書きをいくつのノードから
59 行うのかを決めるConsistencyレベルを設定できる.
60 Consistencyレベルには主に ONE, QUORAM, ALL がある.
61 Replication factorの数値を N とした場合, ONE は1つのノード, QUORUM は N/2 + 1 のノード, ALL は N のノード
62 へと読み書きを行う.
63 Consistencyハッシング, Replication factorとConsistencyレベルの設定により Cassandra は
64 高い可用性と分断耐性を持つ.
65
66 % keyspace, super column といったデータの表現についても述べるべきか？
67 % Replication factorはkeyspace毎に設定できる
68 \begin{figure}[htpb]
69 \begin{center}
70 \includegraphics[scale=0.7]{figures/cassandra_ring.pdf}
71 \caption{Consistency・ハッシング}
72 \label{fig:cassandra_ring}
73 \end{center}
74 \end{figure}
75 48
76 \newpage 49 \newpage
77 50
78 \section{MongoDB} 51 \section{MongoDB}
79 MongoDB は2009年に公開された NoSQL のデータベースである. 52 MongoDB は2009年に公開された NoSQL のデータベースである.
125 \caption{マスターとスレーブによるクラスタ} 98 \caption{マスターとスレーブによるクラスタ}
126 \label{fig:neo4j_replica} 99 \label{fig:neo4j_replica}
127 \end{center} 100 \end{center}
128 \end{figure} 101 \end{figure}
129 102
103 \newpage
104 \section{memcached}
105
106
107
108
109
110 \section{Cassandra}
111 Cassandra\cite{cassandra} は2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである.
112 AmazonのDynamo\cite{dynamo} という分散Key-Valueデータベースの影響を受けて作られている.
113 スキーマレスな NoSQL データベースになる.
114
115 Cassandraはサーバノードの配置にConsistent hashingアルゴリズムを用いる.
116 Consistent hashingによりノードは論理的にリング上に配置される.
117 リングには数値で表される位置がある.
118 データを書き込む際には, キーとなるハッシュ値に従いそのリングの位置から時計回りに近いサーバノードへと書き込まれる.
119 Consistent hashingを用いることで, ノードの数が増減した場合に, 再配置をしなくてもよいという利点がある.
120 データの偏りにより少数のサーバへの負荷が大きい場合に, 負荷が高いハッシュ値が指すリング上に
121 新たなノードを追加することで負荷を下げるといった手段もとれる.
122 Consistency Hashingによるリングの形成を図\ref{fig:cassandra_ring}に示す.
123
124 \begin{figure}[htpb]
125 \begin{center}
126 \includegraphics[scale=0.7]{figures/cassandra_ring.pdf}
127 \caption{ConsisteyncyLevel QUORUMによる書き込み}
128 \label{fig:cassandra_ring}
129 \end{center}
130 \end{figure}
131
132 Cassandraはデータを最大どれだけ配置するかを示すReplication factorと, データの読み書きをいくつのノードから
133 行うのかを決めるConsistency Levelの設定が行える.
134 Consistency Levelには主に ONE, QUORAM, ALL がある.
135 Replication factorの数値をNとした場合, ONE は1つのノード, QUORUMは N/2 + 1 のノード, ALLはNのノード
136 へと読み書きを行う.
137 Replication factorとConsistentcy Levelの設定により, Cassandraは最新のデータを取得したいときと
138 そうでないときで読み込みと書き込みの速度をあげることができる.
139 一貫性が重要なデータに関してはQUORUMにより書き込み読み込みを行うことで常に最新のデータを取得することができる.
140 多少データが古くてもよい場合はONEなどを使用することでレスポンスを早くすることができる.
141 ConsisutencyLevel QUORUMの時のデータ書き込みについて図\ref{fig:cassandra_quorum}に示す.
142 Consistencyハッシング, Replication factorとConsistencyレベルの設定により Cassandra は
143 高い可用性と分断耐性を持つ.
144
145 \begin{figure}[htpb]
146 \begin{center}
147 \includegraphics[scale=0.6]{figures/consistency_quorum.pdf}
148 \caption{ConsisteyncyLevel QUORUMによる書き込み}
149 \label{fig:cassandra_quorum}
150 \end{center}
151 \end{figure}
130 152
131 153
132 154
133 155
134 156
135 157
136 158
137