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

\section{Relational Database}
Relational Database（RDB）は, 列と行からなる2次元のテーブルにより実装されるデータベースである.
データ型として文字列, 数値, 日付, BOOL型がありシステムによりデータに型が強制される.
RDBはスキーマの決まったデータを扱うことに長けている.
構造化言語問い合わせ言語としてSQLがある.

RDBはデータベースの中でも長年主要な立ち位置にあるデータベースだが, 苦手としている
ことがある.
それは, スキーマレスなデータの扱いやマシンの台数を増やして処理速度
をあげることである.
垂直分割や水平分割といった方法によりデータを分けることはできるが, 分割を行うほど
データの扱いは複雑になっていく.

\section{NoSQLデータベース}
NoSQLはNot Only SQLの略で, SQLを使わないデータベースのことを指す.
NoSQLデータベースはRDBとは違いスキーマがない.
そのため, 扱おうとしているデータの形が決まっていなくても気軽に使うことができる.

%また, スケーラビリティも持ちあわせており, 汎用的なマシンを集めることで性能をあげる
%ことができるといった特徴を持つ.
後述するConsistency HashingやShardingといった方法で複数ノードでデータの分散を行うことで
スケーラビリティの確保を行う.
単純なノードの追加により負荷分散を行うことができる.



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

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


\newpage

\section{既存のNoSQLデータベース}
ここでは既存のNoSQLデータベースに説明する.
それぞれの特徴を述べながら, どのような方法でスケーラビリティを確保しているのかについて述べる.

\subsection{memcached}
memcachedは揮発性の分散型キャッシュである.
Key-Valueストアとなっている.
RDBとも連携して使うことができ, その場合メモリの中にデータを保持させることでディスクへのアクセスを減らし
処理性能を上げることができる.
 LRU（Least Recently Used）のため, メモリの容量がなくなると一番古いデータはメモリから削除されてしまう.
memcachedは永続性は考慮していない.

また, 分散を行う機能はサーバ側に備わっておらず, クライアント側の実装に任せている.
クライアント側ではノードのリストを保持している.
データの読み書きの際には, クライアント側で実装されている分散アルゴリズムい従って
読み書きをするノードが決定される(図\ref{fig:memcached}).

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/memcached.pdf}
    \caption{memchachedのデータ分散}
    \label{fig:memcached}
  \end{center}
\end{figure}



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

MongoDB は保存したデータを複数のサーバに複製をとる.
これはReplicationと呼ばれる.
また, 1つのサーバが全てのデータを持つのでなく, ある範囲の値を別々の
サーバに分割させて保持する.
これをShardingという.
MongoDB はReplicationとShardingにより分断耐性と一貫性を持つ(図\ref{fig:mongodb_sharding}).

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/mongodb_sharding.pdf}
    \caption{Sharding}
    \label{fig:mongodb_sharding}
  \end{center}
\end{figure}


\newpage

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

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

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

\newpage


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

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/cassandra_ring.pdf}
    \caption{Consisteyncy hashingによるring型トポロジーの形成}
    \label{fig:cassandra_ring}
  \end{center}
\end{figure}

Cassandraはデータを最大どれだけ配置するかを示すReplication factorと, データの読み書きをいくつのノードから
行うのかを決めるConsistency Levelの設定が行える.
Consistency Levelには主に ONE, QUORAM, ALL がある.
Replication factorの数値をNとした場合, ONE は1つのノード, QUORUMは N/2 + 1 のノード, ALLはNのノード
へと読み書きを行う.
Replication factorとConsistentcy Levelの設定により, Cassandraは最新のデータを取得したいときと
そうでないときで読み込みと書き込みの速度をあげることができる.
一貫性が重要なデータに関してはQUORUMにより書き込み読み込みを行うことで常に最新のデータを取得することができる.
多少データが古くてもよい場合はONEなどを使用することでレスポンスを早くすることができる.
ConsisutencyLevel QUORUMの時のデータ書き込みと読み込みについて図\ref{fig:quorum_write}と図\ref{fig:quorum_read}に示す.
Consistencyハッシング, Replication factorとConsistencyレベルの設定により Cassandra は
高い可用性と分断耐性を持つ.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.6]{figures/cassandra_quorum_write.pdf}
    \caption{ConsisteyncyLevel QUORUMによる書き込み}
    \label{fig:quorum_write}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.6]{figures/cassandra_quorum_read.pdf}
    \caption{ConsisteyncyLevel QUORUMによる読み込み}
    \label{fig:quorum_read}
  \end{center}
\end{figure}