Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter1.tex @ 50:faa708c2958b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added log
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Fri, 31 Jan 2014 17:13:59 +0900
parents 63eca978482f
children 39c2180b5719
comparison
equal deleted inserted replaced
49:7b595f4b341e 50:faa708c2958b
5 本章ではまずデータベースの種類であるリレーショナルデータベース（RDB） と NoSQL について述べる. 5 本章ではまずデータベースの種類であるリレーショナルデータベース（RDB） と NoSQL について述べる.
6 次に, 分散データシステムにおいて重要な CAP 定理について触れる. 6 次に, 分散データシステムにおいて重要な CAP 定理について触れる.
7 最後に既存の NoSQL データベースとして Cassandra, MongoDB, Neo4j の特徴について述べる. 7 最後に既存の NoSQL データベースとして Cassandra, MongoDB, Neo4j の特徴について述べる.
8 8
9 \section{RDB と NoSQL} 9 \section{RDB と NoSQL}
10 データベースは大別すると RDB と NoSQL に分けられる. 10 データベースは大別するとRDBとNoSQLに分けられる.
11 RDB とは行と列からなる2次元のテーブルによりデータを保持するデータベースである. 11 RDBとは行と列からなる2次元のテーブルによりデータを保持するデータベースである.
12 RDB はデータベースアクセス言語として SQL 言語を持ち, 一台のマシンでデータを扱う分には最適である. 12 RDBはデータベースアクセス言語としてSQL言語を持ち, 一台のマシンでデータを扱う分には最適である.
13 しかし, RDB はマシン単体以上の処理性能をだすことができない. 13 しかし, RDB はマシン単体以上の処理性能をだすことができない.
14 そこで, 汎用的な PC をいくつも用意しデータや処理を分散して管理できるデータベースが求められた. 14 そこで, 汎用的なPCをいくつも用意しデータや処理を分散して管理できるデータベースが求められた.
15 それらのデータベースは NoSQL(Not Only SQL) と呼ばれる. 15 それらのデータベースはNoSQL（Not Only SQL） と呼ばれSQLを使用しないデータベースのことを指す.
16 2次元のテーブルでは無く, Key-Value, ドキュメント, グラフといった表現形式でデータの保持を行う. 16 2次元のテーブルでは無く, Key-Value, ドキュメント, グラフといった表現形式でデータの保持を行う.
17 NoSQL は, SQL を使用するデータベースには向いていない処理を行うことを目的にしている. 17 NoSQLは, RDBには向いていない処理を行うことを目的にしている.
18 18
19 % 分散データベースは, NoSQL に分けられる. 19 % 分散データベースは, NoSQL に分けられる.
20 20
21 \section{CAP 定理} 21 \section{CAP 定理}
22 分散データシステムにおいて次の3つを同時に保証することはできない 22 分散データシステムにおいて次の3つを同時に保証することはできない
27 あるノードに障害が発生しても機能しているノードにより常にデータの読み書きが行える. 27 あるノードに障害が発生しても機能しているノードにより常にデータの読み書きが行える.
28 \item 分断耐性(Partition-tolerance) 28 \item 分断耐性(Partition-tolerance)
29 ネットワーク障害によりノードの接続が切れてもデータベースは機能し続けることができる. 29 ネットワーク障害によりノードの接続が切れてもデータベースは機能し続けることができる.
30 \end{itemize} 30 \end{itemize}
31 これは CAP 定理\cite{cap}と呼ばれる. 31 これは CAP 定理\cite{cap}と呼ばれる.
32 利用するデータベース選ぶ場合, この CAP 定理を意識しなければならない. 32 利用するデータベース選ぶ場合, このCAP定理を意識しなければならない.
33 一貫性と可用性を重視したデータベースが, RDB である. 33 一貫性と可用性を重視したデータベースが, RDBである.
34 分断耐性を必要とする場合は NoSQL データベースとなる. 34 分断耐性を必要とする場合は NoSQL データベースとなる.
35 そして NoSQL の場合, 分断耐性と後もう一つ, 一貫性か可用性のどちらを保証しているかで用途が変わってくる. 35 そしてNoSQLの場合, 分断耐性と後もう一つ, 一貫性か可用性のどちらを保証しているかで用途が変わってくる.
36 36
37 分散データシステムを考える場合は, この CAP 定理を意識していなければならない. 37 分散データシステムを考える場合は, この CAP 定理を意識していなければならない.
38 38
39 39
40 \section{Cassandra} 40 \section{Cassandra}
41 Cassandra\cite{cassandra} は2008年7月に Facebook によってオープンソースとして公開された Key-Value なデータベースである. 41 Cassandra\cite{cassandra} は2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである.
42 Amazon の Dynamo\cite{dynamo} という分散キーバリューデータベースの影響を受けて作られている. 42 AmazonのDynamo\cite{dynamo} という分散Key-Valueデータベースの影響を受けて作られている.
43 スキーマレスな NoSQL データベースになる. 43 スキーマレスな NoSQL データベースになる.
44 44
45 Cassandra はサーバノードの配置にコンシステント・ハッシングアルゴリズムを用いる. 45 Cassandraはサーバノードの配置にConsistent hashingアルゴリズムを用いる.
46 コンシステント・ハッシングによりノードは論理的にリング上に配置される. 46 Consistent hashingによりノードは論理的にリング上に配置される.
47 リングには数値で表される位置がある. 47 リングには数値で表される位置がある.
48 データを書き込む際には, キーとなるハッシュ値に従いそのリングの位置から時計回りに近いサーバノードへと書き込まれる. 48 データを書き込む際には, キーとなるハッシュ値に従いそのリングの位置から時計回りに近いサーバノードへと書き込まれる.
49 コンシステント・ハッシングを用いることで, ノードの数が増減した場合に, 再配置をしなくてもよいという利点がある. 49 Consistent hashingを用いることで, ノードの数が増減した場合に, 再配置をしなくてもよいという利点がある.
50 データの偏りにより少数のサーバへの負荷が大きい場合に, 負荷が高いハッシュ値が指すリング上に 50 データの偏りにより少数のサーバへの負荷が大きい場合に, 負荷が高いハッシュ値が指すリング上に
51 新たなノードを追加することで負荷を下げるといった手段もとれる. 51 新たなノードを追加することで負荷を下げるといった手段もとれる.
52 52
53 データを最大どれだけ配置するかを示すレプリケーションファクタと, データの読み書きをいくつのノードから 53 データを最大どれだけ配置するかを示すReplication factorと, データの読み書きをいくつのノードから
54 行うのかを決めるコンシステンシーレベルを設定できる. 54 行うのかを決めるConsistencyレベルを設定できる.
55 コンシステンシーレベルには主に ONE, QUORAM, ALL がある. 55 Consistencyレベルには主に ONE, QUORAM, ALL がある.
56 レプリケーションファクタの数値を N とした場合, ONE は1つのノード, QUORUM は N/2 + 1 のノード, ALL は N のノード 56 Replication factorの数値を N とした場合, ONE は1つのノード, QUORUM は N/2 + 1 のノード, ALL は N のノード
57 へと読み書きを行う. 57 へと読み書きを行う.
58 コンシステンシーハッシング, レプリケーションファクタとコンシステンシーレベルの設定により Cassandra は 58 Consistencyハッシング, Replication factorとConsistencyレベルの設定により Cassandra は
59 高い可用性と分断耐性を持つ. 59 高い可用性と分断耐性を持つ.
60 60
61 % keyspace, super column といったデータの表現についても述べるべきか？ 61 % keyspace, super column といったデータの表現についても述べるべきか？
62 % レプリケーションファクタはkeyspace毎に設定できる 62 % Replication factorはkeyspace毎に設定できる
63 \begin{figure}[htpb] 63 \begin{figure}[htpb]
64 \begin{center} 64 \begin{center}
65 \includegraphics[scale=0.7]{figures/cassandra_ring.pdf} 65 \includegraphics[scale=0.7]{figures/cassandra_ring.pdf}
66 \caption{コンシステンシー・ハッシング} 66 \caption{Consistency・ハッシング}
67 \label{fig:cassandra_ring} 67 \label{fig:cassandra_ring}
68 \end{center} 68 \end{center}
69 \end{figure} 69 \end{figure}
70 70
71 \newpage 71 \newpage
80 80
81 MongoDB は保存したデータを複数のサーバに複製をとる. 81 MongoDB は保存したデータを複数のサーバに複製をとる.
82 これはレプリケーション(replication)と呼ばれる. 82 これはレプリケーション(replication)と呼ばれる.
83 また, 1つのサーバが全てのデータを持つのでなく, ある範囲の値を別々の 83 また, 1つのサーバが全てのデータを持つのでなく, ある範囲の値を別々の
84 サーバに分割させて保持する. 84 サーバに分割させて保持する.
85 これをシャーディング(sharding)という. 85 これをShardingという.
86 MongoDB はレプリケーションとシャーディングにより分断耐性と一貫性を持つ. 86 MongoDB はレプリケーションとShardingにより分断耐性と一貫性を持つ.
87 87
88 % クエリ言語として JavaScript を採用しており, 演算子を自分作れるという利点を持つ. 88 % クエリ言語として JavaScript を採用しており, 演算子を自分作れるという利点を持つ.
89 % スペルミスに弱い 89 % スペルミスに弱い
90 90
91 \begin{figure}[htpb] 91 \begin{figure}[htpb]
92 \begin{center} 92 \begin{center}
93 \includegraphics[scale=0.7]{figures/mongodb_sharding.pdf} 93 \includegraphics[scale=0.7]{figures/mongodb_sharding.pdf}
94 \caption{シャーディング} 94 \caption{Sharding}
95 \label{fig:mongodb_sharding} 95 \label{fig:mongodb_sharding}
96 \end{center} 96 \end{center}
97 \end{figure} 97 \end{figure}
98 98
99 \newpage 99 \newpage