\chapter{既存の分散データベース}
% 分散データベースとはなんなのか。
% データベースはなんなのかをいれないと。
% NoSQL の説明も必要。
本章ではまずデータベースの種類であるリレーショナルデータベース（RDB） と NoSQL について述べる.
次に, 分散データシステムにおいて重要な CAP 定理について触れる.
最後に既存の NoSQL データベースとして Cassandra, MongoDB, Neo4j の特徴について述べる.

\section{RDB と NoSQL}
データベースは大別すると RDB と NoSQL に分けられる.
RDB とは行と列からなる2次元のテーブルによりデータを保持するデータベースである.
RDB はデータベースアクセス言語として SQL 言語を持ち, 一台のマシンでデータを扱う分には最適である.
しかし, RDB はマシン単体以上の処理性能をだすことができない.
そこで, 汎用的な PC をいくつも用意しデータや処理を分散して管理できるデータベースが求められた.
それらのデータベースは NoSQL(Not Only SQL) と呼ばれる.
2次元のテーブルでは無く, Key-Value, ドキュメント, グラフといった表現形式でデータの保持を行う.
NoSQL は, SQL を使用するデータベースには向いていない処理を行うことを目的にしている.

% 分散データベースは, NoSQL に分けられる.

\section{CAP 定理}
分散データシステムにおいて次の3つを同時に保証することはできない
\begin{itemize}
\item 一貫性(Consistency)
全てのノードはクエリが同じならば同じデータを返す.
\item 可用性(Availability)
あるノードに障害が発生しても機能しているノードにより常にデータの読み書きが行える. 
\item 分断耐性(Partition-tolerance)
ネットワーク障害によりノードの接続が切れてもデータベースは機能し続けることができる.
\end{itemize}
これは CAP 定理\cite{cap}と呼ばれる.
利用するデータベース選ぶ場合, この CAP 定理を意識しなければならない.
一貫性と可用性を重視したデータベースが, RDB である.
分断耐性を必要とする場合は NoSQL データベースとなる.
そして NoSQL の場合, 分断耐性と後もう一つ, 一貫性か可用性のどちらを保証しているかで用途が変わってくる.

分散データシステムを考える場合は, この CAP 定理を意識していなければならない.


\section{Cassandra}
Cassandra\cite{cassandra} は2008年7月に Facebook によってオープンソースとして公開された Key-Value なデータベースである.
Amazon の Dynamo\cite{dynamo} という分散キーバリューデータベースの影響を受けて作られている.
スキーマレスな NoSQL データベースになる.

Cassandra はサーバノードの配置にコンシステント・ハッシングアルゴリズムを用いる.
コンシステント・ハッシングによりノードは論理的にリング上に配置される.
リングには数値で表される位置がある.
データを書き込む際には, キーとなるハッシュ値に従いそのリングの位置から時計回りに近いサーバノードへと書き込まれる.
コンシステント・ハッシングを用いることで, ノードの数が増減した場合に, 再配置をしなくてもよいという利点がある.
データの偏りにより少数のサーバへの負荷が大きい場合に, 負荷が高いハッシュ値が指すリング上に
新たなノードを追加することで負荷を下げるといった手段もとれる.

データを最大どれだけ配置するかを示すレプリケーションファクタと, データの読み書きをいくつのノードから
行うのかを決めるコンシステンシーレベルを設定できる.
コンシステンシーレベルには主に ONE, QUORAM, ALL がある.
レプリケーションファクタの数値を N とした場合, ONE は1つのノード, QUORUM は N/2 + 1 のノード, ALL は N のノード
へと読み書きを行う.
コンシステンシーハッシング, レプリケーションファクタとコンシステンシーレベルの設定により Cassandra は
高い可用性と分断耐性を持つ.

% keyspace, super column といったデータの表現についても述べるべきか？
% レプリケーションファクタはkeyspace毎に設定できる
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/cassandra_ring.pdf}
    \caption{コンシステンシー・ハッシング}
    \label{fig:cassandra_ring}
  \end{center}
\end{figure}

\newpage

\section{MongoDB}
MongoDB は2009年に公開された NoSQL のデータベースである.
JSON フォーマットのドキュメントデータベースであり, これはスキーマが無い
リレーショナルテーブルに例えられる.
スキーマが無いため, 事前にデータの定義を行う必要がない.
そのためリレーショナルデータベースに比べてデータの追加・削除
が行いやすい.

MongoDB は保存したデータを複数のサーバに複製をとる.
これはレプリケーション(replication)と呼ばれる.
また, 1つのサーバが全てのデータを持つのでなく, ある範囲の値を別々の
サーバに分割させて保持する.
これをシャーディング(sharding)という.
MongoDB はレプリケーションとシャーディングにより分断耐性と一貫性を持つ.

% クエリ言語として JavaScript を採用しており, 演算子を自分作れるという利点を持つ.
% スペルミスに弱い

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/mongodb_sharding.pdf}
    \caption{シャーディング}
    \label{fig:mongodb_sharding}
  \end{center}
\end{figure}

\newpage

\section{Neo4j}
Neo4j は, グラフデータベースと呼ばれる NoSQL のデータベースである.
データをグラフとして保存する.
グラフはノードとリレーションシップにより表され, それぞれがプロパティを持つことができる.
リレーションシップはグラフでいうところのエッジにあたる.
ノードからリレーションシップを辿り, 各プロパティをみることでデータの取得を行うことができる.
通常データベースでは, データの取り出しに価の結合や条件の判定を行う.
だが, グラフデータベースグラフはどれだけデータが大きくなろうがノードからノードへの移動は1ステップですむ.
そのため, どれだけデータが大きくなろうと, データが小さい時と同じ計算量でデータの取得が行える.

Neo4j はマスターとスレーブの関係になるクラスタを構成することで分散データベースとして機能する.
マスターに書かれたデータはスレーブに書き込まれるが, すぐに全てのスレーブに書き込まれるわけではない.
したがってデータの整合性が失われる危険がある.
スレーブサーバは現在保持しているデータを返すことができる.
そのため Neo4j は高い読み取り性能の要求に答えることができる可用性と分断耐性を持つ.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/neo4j_replica.pdf}
    \caption{マスターとスレーブによるクラスタ}
    \label{fig:neo4j_replica}
  \end{center}
\end{figure}