Mercurial > hg > Papers > 2014 > nobuyasu-master

annotate paper/chapter1.tex @ 102:6f73e05d5024

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed chapter4.tex
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 15 Feb 2014 06:00:54 +0900
parents be9d52d3c424
children d116e59fc8a2
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
73
108b6336395d Fixed spell miss
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 71
diff changeset
1 \chapter{既存のデータベース}
25
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
2 % 分散データベースとはなんなのか。
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
3 % データベースはなんなのかをいれないと。
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
4 % NoSQL の説明も必要。
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
5 　本章では, まずデータベースの種類であるRelational DatabaseとNoSQL について述べる.
38
559589aec976 Writed how to use alice topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
6 次に, 分散データシステムにおいて重要な CAP 定理について触れる.
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
7 最後に, 既存の NoSQL データベースとしてmemcached, MongoDB, Neo4j, Cassandraの特徴について述べる.
25
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
8
57
39c2180b5719 Added log
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
9 \section{Relational Database}
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
10 Relational Database（RDB）は, 列と行からなる2次元のテーブルにより実装されるデータベースである.
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
11 データ型として文字列, 数値, 日付, BOOL型がありシステムによりデータに型が強制される.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
12 RDBはスキーマの決まったデータを扱うことに長けている.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
13 構造化言語問い合わせ言語としてSQLがある.
57
39c2180b5719 Added log
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 50
diff changeset
14
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
15 RDBはデータベースの中でも長年主要な立ち位置にあるデータベースだが, 苦手としている
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
16 ことがある.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
17 それは, スキーマレスなデータの扱いやマシンの台数を増やして処理速度
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
18 をあげることである.
68
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
19 垂直分割や水平分割といった方法によりデータを分けることはできるが, 分割を行うほど
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
20 データの扱いは複雑になっていく.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
21
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
22 \section{NoSQLデータベース}
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
23 NoSQLはNot Only SQLの略で, SQLを使わないデータベースのことを指す.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
24 NoSQLデータベースはRDBとは違いスキーマがない.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
25 そのため, 扱おうとしているデータの形が決まっていなくても気軽に使うことができる.
68
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
26
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
27 %また, スケーラビリティも持ちあわせており, 汎用的なマシンを集めることで性能をあげる
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
28 %ことができるといった特徴を持つ.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
29 後述するConsistency HashingやShardingといった方法で複数ノードでデータの分散を行うことで
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
30 スケーラビリティの確保を行う.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
31 単純なノードの追加により負荷分散を行うことができる.
25
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
32
68
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
33
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
34
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
35 \newpage
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
36 \section{CAP 定理}
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
37 分散データシステムにおいては, 次の3つを同時に保証することはできない.
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
38 \begin{itemize}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
39 \item 一貫性(Consistency)
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
40 全てのノードはクエリが同じならば同じデータを返す.
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
41 \item 可用性(Availability)
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
42 あるノードに障害が発生しても, 機能しているノードにより常にデータの読み書きが行える.
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
43 \item 分断耐性(Partition-tolerance)
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
44 ネットワーク障害によりノードの接続が切れてもデータベースは機能し続けることができる.
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
45 \end{itemize}
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
46 　これは CAP 定理\cite{cap}と呼ばれる.
50
faa708c2958b Added log
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
47 利用するデータベース選ぶ場合, このCAP定理を意識しなければならない.
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
48 一貫性と可用性を重視したデータベースがRDBである.
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
49 分断耐性を必要とする場合は NoSQL データベースとなる.
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
50 そしてNoSQLの場合, 分断耐性に加えて, 一貫性か可用性のどちらを重視しているかで用途が変わってくる.
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
51
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
52 分散データシステムを考える場合は, この CAP 定理を意識していなければならない.
25
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
53
13
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
54
68
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
55 \newpage
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
56
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
57 \section{既存のNoSQLデータベース}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
58 ここでは既存のNoSQLデータベースに説明する.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
59 それぞれの特徴を述べながら, どのような方法でスケーラビリティを確保しているのかについて述べる.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
60
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
61 \subsection{memcached}
63
d770a2b534b3 Writed description of persistent
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
62 memcachedは揮発性の分散型キャッシュである.
d770a2b534b3 Writed description of persistent
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
63 Key-Valueストアとなっている.
d770a2b534b3 Writed description of persistent
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
64 RDBとも連携して使うことができ, その場合メモリの中にデータを保持させることでディスクへのアクセスを減らし
d770a2b534b3 Writed description of persistent
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
65 処理性能を上げることができる.
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
66 LRU（Least Recently Used）のため, メモリの容量がなくなると一番古いデータはメモリから削除されてしまう.
64
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
67 memcachedは永続性は考慮していない.
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
68
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
69 また, 分散を行う機能はサーバ側に備わっておらず, クライアント側の実装に任せている.
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
70 クライアント側ではノードのリストを保持している.
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
71 データの読み書きの際には, クライアント側で実装されている分散アルゴリズムい従って
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
72 読み書きをするノードが決定される(図\ref{fig:memcached}).
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
73
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
74 \begin{figure}[htpb]
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
75 \begin{center}
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
76 \includegraphics[scale=0.7]{figures/memcached.pdf}
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
77 \caption{memchachedのデータ分散}
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
78 \label{fig:memcached}
64
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
79 \end{center}
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
80 \end{figure}
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
81
c06ec0269eba memcached
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 63
diff changeset
82
63
d770a2b534b3 Writed description of persistent
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 59
diff changeset
83
68
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
84 \newpage
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
85 \subsection{MongoDB}
13
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
86 MongoDB は2009年に公開された NoSQL のデータベースである.
15
7df3a9a13b22 Writed research
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
87 JSON フォーマットのドキュメントデータベースであり, これはスキーマが無い
13
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
88 リレーショナルテーブルに例えられる.
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
89 スキーマが無いため, 事前にデータの定義を行う必要がない.
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
90 そのためリレーショナルデータベースに比べてデータの追加・削除
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
91 が行いやすい.
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
92
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
93 MongoDB は保存したデータを複数のサーバに複製をとる.
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
94 これはReplicationと呼ばれる.
13
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
95 また, 1つのサーバが全てのデータを持つのでなく, ある範囲の値を別々の
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
96 サーバに分割させて保持する.
50
faa708c2958b Added log
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
97 これをShardingという.
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
98 MongoDB はReplicationとShardingにより分断耐性と一貫性を持つ(図\ref{fig:mongodb_sharding}).
13
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
99
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
100 % クエリ言語として JavaScript を採用しており, 演算子を自分作れるという利点を持つ.
22c48f2b344a chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
101 % スペルミスに弱い
14
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
102
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
103 \begin{figure}[htpb]
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
104 \begin{center}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
105 \includegraphics[scale=0.7]{figures/mongodb_sharding.pdf}
50
faa708c2958b Added log
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 39
diff changeset
106 \caption{Sharding}
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
107 \label{fig:mongodb_sharding}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
108 \end{center}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
109 \end{figure}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
110
59
81508c27228a Added log
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 58
diff changeset
111
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
112 \newpage
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
113
68
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
114 \subsection{Neo4j}
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
115 Neo4j は, グラフデータベースと呼ばれる NoSQL のデータベースである.
14
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
116 データをグラフとして保存する.
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
117 グラフはノードとRelationshipにより表され, それぞれがプロパティを持つことができる.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
118 Relationshipはグラフでいうところのエッジにあたる.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
119 ノードからRelationshipを辿り, 各プロパティをみることでデータの取得を行うことができる.
14
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
120 通常データベースでは, データの取り出しに価の結合や条件の判定を行う.
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
121 しかし, グラフデータベースグラフはどれだけデータが大きくなろうがノードからノードへの移動は1ステップですむ.
14
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
122 そのため, どれだけデータが大きくなろうと, データが小さい時と同じ計算量でデータの取得が行える.
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
123
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
124 Neo4j はマスターとスレーブの関係になるクラスタを構成することで分散データベースとして機能する.
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
125 マスターに書かれたデータはスレーブに書き込まれるが, すぐに全てのスレーブに書き込まれるわけではない.
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
126 したがって, データの整合性が失われる危険がある.
14
df59b2af84e6 chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
127 スレーブサーバは現在保持しているデータを返すことができる.
99
be9d52d3c424 Fixed chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 76
diff changeset
128 そのため Neo4j は高い読み取り性能の要求に答えることができる可用性と分断耐性を持つ(図\ref{fig:neo4j_replica}).
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
129
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
130 \begin{figure}[htpb]
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
131 \begin{center}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
132 \includegraphics[scale=0.7]{figures/neo4j_replica.pdf}
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
133 \caption{マスターとスレーブによるクラスタ}
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
134 \label{fig:neo4j_replica}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
135 \end{center}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
136 \end{figure}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
137
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
138 \newpage
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
139
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
140
68
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
141 \subsection{Cassandra}
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
142 Cassandra\cite{cassandra} は2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
143 AmazonのDynamo\cite{dynamo} という分散Key-Valueデータベースの影響を受けて作られている.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
144 スキーマレスな NoSQL データベースになる.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
145
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
146 Cassandraはサーバノードの配置にConsistent hashingアルゴリズムを用いる.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
147 Consistent hashingによりノードは論理的にリング上に配置される.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
148 リングには数値で表される位置がある.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
149 データを書き込む際には, キーとなるハッシュ値に従いそのリングの位置から時計回りに近いサーバノードへと書き込まれる.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
150 Consistent hashingを用いることで, ノードの数が増減した場合に, 再配置をしなくてもよいという利点がある.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
151 データの偏りにより少数のサーバへの負荷が大きい場合に, 負荷が高いハッシュ値が指すリング上に
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
152 新たなノードを追加することで負荷を下げるといった手段もとれる.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
153 Consistency Hashingによるリングの形成を図\ref{fig:cassandra_ring}に示す.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
154
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
155 \begin{figure}[htpb]
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
156 \begin{center}
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
157 \includegraphics[scale=0.7]{figures/cassandra_ring.pdf}
76
5c5d71d36c14 Added slides
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 73
diff changeset
158 \caption{Consisteyncy hashingによるring型トポロジーの形成}
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
159 \label{fig:cassandra_ring}
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
160 \end{center}
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
161 \end{figure}
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
162
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
163 Cassandraはデータを最大どれだけ配置するかを示すReplication factorと, データの読み書きをいくつのノードから
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
164 行うのかを決めるConsistency Levelの設定が行える.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
165 Consistency Levelには主に ONE, QUORAM, ALL がある.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
166 Replication factorの数値をNとした場合, ONE は1つのノード, QUORUMは N/2 + 1 のノード, ALLはNのノード
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
167 へと読み書きを行う.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
168 Replication factorとConsistentcy Levelの設定により, Cassandraは最新のデータを取得したいときと
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
169 そうでないときで読み込みと書き込みの速度をあげることができる.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
170 一貫性が重要なデータに関してはQUORUMにより書き込み読み込みを行うことで常に最新のデータを取得することができる.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
171 多少データが古くてもよい場合はONEなどを使用することでレスポンスを早くすることができる.
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
172 ConsisutencyLevel QUORUMの時のデータ書き込みと読み込みについて図\ref{fig:quorum_write}と図\ref{fig:quorum_read}に示す.
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
173 Consistencyハッシング, Replication factorとConsistencyレベルの設定により Cassandra は
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
174 高い可用性と分断耐性を持つ.
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
175
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
176 \begin{figure}[htpb]
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
177 \begin{center}
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
178 \includegraphics[scale=0.6]{figures/cassandra_quorum_write.pdf}
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
179 \caption{ConsisteyncyLevel QUORUMによる書き込み}
69
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
180 \label{fig:quorum_write}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
181 \end{center}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
182 \end{figure}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
183
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
184 \begin{figure}[htpb]
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
185 \begin{center}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
186 \includegraphics[scale=0.6]{figures/cassandra_quorum_read.pdf}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
187 \caption{ConsisteyncyLevel QUORUMによる読み込み}
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 68
diff changeset
188 \label{fig:quorum_read}
58
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
189 \end{center}
3c070028199b Added consistency_quorum
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 57
diff changeset
190 \end{figure}
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
191
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
192
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
193
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
194
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
195
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
196
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
197