http://m-takagi.github.io/aosa-ja/aosa.pdf http://aosabook.org/en/index.html
章を順番に読んでいません。
NoSQLのことはこの本を読んだら何となくつかめると思う。
13.2 NoSQLのデータモデルおよびクエリモデル
- データモデル データをどのような論理構造で管理するかを示すもの
- クエリモデル データの取得や更新をどのように行うのかを決定
NoSQLシステムはさまざまなデータモデルとクエリモデルの組み合わせでできており、アーキテクチャ上の検討事項もそれぞれ異なる
キーベースのNoSQLデータモデル
NoSQLはデータセットの検索を単一フィールドによるものだけに制限されたものが多い
- キー・バリューストア
- キー・データ構造ストア
- キー・ドキュメントストア
- BigTableカラムファミリーストア
キールックアップ方式のシステム
複雑な結合操作や複数キーによる同一データの取得などを実現しようとすると、キーの名前にちょっとした工夫を要する。社員を検索する際に「社員IDでの検索」「ある部署に所属する全社員の検索」の二通りを行いたい場合は、二種類のキーを作成することになる
アプリケーション側で結合操作を行う必要がある
- メリット データベースへの問い合わせのパターンが一貫したものになる
- デメリット データモデルのロジックと業務ロジックが密結合してしまい、抽象化は崩れてしまう
キー・バリューストア
- 値をキーで持っているだけ
- データベース内でのシンプルな絞り込み機能を追加する仕組みは持っていない
- Voldemort
キー・データ構造ストア
- 値として型を割り当て
- シンプルな、型ごとの機能を提供する一方で、集約や結合といった複数キーの操作はできない
- Redis
キー・ドキュメントストア
- 構造化された情報を含むドキュメントをキーにマップ
- アプリケーションの開発者はドキュメントのモデリングに関してかなりの自由を与えられているが、アプリケーション側での問い合わせのロジックは著しく複雑化する
- MongoDB
BigTableカラムファミリーストア
- ある形式(行ID、CF、列、タイムスタンプ)の複合キーを格納し、それをキーで並べ替えた複数の値にマップ
- 多くの機能をキー空間に持たせるというデータモデリング
- Cassandra
グラフストレージ
こんなのもあるよ、的な紹介
- データモデル、データの走査や問い合わせのパターン、ディスク上での物理的なデータ配置、複数マシンへの分散、クエリのトランザクション特性などがすべて異なる
- 説明にページ数が必要なのであんまり説明しない
- 電車の運賃計算とかはリレーショナルより楽(最短経路を算出する必要があるので、こっちのほうが楽)
- HyperGraphDB
複雑な問い合わせ(特殊な例外)
- MongoDBでは任意の数のプロパティを使った索引付けで比較的高レベルの問い合わせ言語を使って取得したいデータを指定することもできる
- CouchDBではテーブルに対してMapReduceタスクを実行させ、より複雑なルックアップや更新もできるようにしている
トランザクション
- SQLでは当たり前のACID特性よりもパフォーマンスを重視
- ただしキーのレベルではACIDを保証しており、同じキーに対する二つの操作があればそれは直列化され、キーと値のペアに深刻な被害が及ばないようにしている
- 例外はRedis MULTIコマンドで原子性と整合性を保証 WATCHコマンドで独立性を保証
スキーマフリーストレージ
- データベース内でスキーマを強要しない
- 各エンティティのプロパティが同じである必要はない
- スキーマをオンザフライで修正するときにもパフォーマンスの劣化はあまり起こらないということである。そのぶん、アプリケーションの開発者側にはより多くの責務が課せられる
- 入力がフリーになったぶんアプリケーション側でしっかり実装しないといけない
13.3 データの永続性(Durability)
- データに何か変更があったときにはそれをすぐに安全な場所に永続化させたい
- 複数の場所にレプリカを作るなどしてデータのロスを防ぎたい
Python ripple
データを失う場面にはさまざまなものがあるし、すべてのNoSQLシステムがこういった問題からあなたを守ってくれるというわけでもない
サーバの再起動や停電対策 データをメモリからハードディスクに移す。ハードディスクは、電源を落としてもデータを失わない
同一マシン上の別のハードディスク(RAIDミラー)だったりネットワーク上の別のマシン→それでもハリケーンなどでぶっこわれる可能性があるので、物理的に離れた場所に冗長化することもある
→データの永続性の保証とパフォーマンスを天秤
単一サーバーの永続化
一番シンプルな方法 単一サーバーの永続化で、サーバーを再起動したり電源を落としたりしても変更したデータが生き残ることを保証
http://linuxjm.sourceforge.jp/html/LDP_man-pages/man2/fsync.2.html (複数の書き込み操作を一括処理)
http://micassoc.blogspot.jp/2010/02/blog-post_4391.html
cf.ランダムアクセス
- 理想的には、一回のfsyncコールあたりの書き込み回数を最小化してシーケンシャルライトの回数を最大化
- 単一サーバーでの永続化を保証するときにパフォーマンスを改善するためのテクニック
fsyncの頻度の制御
- Memcached 永続化の保障を放棄する引き換えとして、極めて高速なインメモリでの操作を提供するシステム
- Redis どのタイミングでfsyncをコールするかについていくつかのオプションを選べるようになっている
fsyncをまったくコールしないようにもできる。適当なタイミングでOSがデータをディスクに書き込むだろうが、それがいつ発生するかはまったく保証しないという選択肢
ログ出力によるシーケンシャルライトの増加
- NoSQLシステムがディスクから高速にデータを取得するために、B+木などのデータ構造が使われている←ログを複数合わせてこねこねしてる←一回Treeを作るのになんのメリットがあるんだろう。実装が楽だからだろうか。中でキャッシュを持っていたら検索が早いのだろうか
- ランダムライトを減らすために、CassandraやHBase、Redis、そしてRiakといったシステムは、更新操作をlogというファイルにシーケンシャルに書き込んでいる
- NoSQLシステムの中には、MongoDBのようにその場でデータ構造に書き込みを行うものもあれば、さらにロギングを行うものもある
- 書き込みのスループットは向上するが、定期的にログの最適化をしないとログのサイズがどんどん膨れ上がってしまう
書き込みのグルーピングによるスループットの向上
Cassandraは、複数の更新を並行してまとめ、一回のfsyncコールの間に実行する
複数サーバーの永続化
複数のサーバーを使ってデータを永続化する仕組みが存在する
- Redis 伝統的なマスター/スレーブ型の手法でデータを複製
- MongoDB レプリカセットという仕組みがあり、何台かのサーバーで各ドキュメントの 格納にかかわる
- 他のDB データのマルチサーバーレプリケーションに対応
- Riak Cassandra Voldemort より細やかにレプリケーションを設定できる。それぞれ微妙な違いはあるが、これらのシステムではNとWのふたつの値を設定できる。Nは最終的にデータのコピーを保持することになるマシンの台数、そしてWはW<Nを満たす数で、少なくともこれだけの台数のマシンにデータが書き込まれた時点でユーザーに制御を戻す
- データセンター全体のサービスが停止してしまう事態に対応→複数のデータセンターにまたがるマルチサーバーのレプリケーション
13.4 パフォーマンス向上のためのスケーリング
データストアはそのコンポーネントのひとつとなり、それなりの負荷にさらされることになる
- スケールアップ(性能アップ)vsスケールアウト(サーバ台数増加)
- シャーディング 読み込みと書き込みを複数のマシンに分散させてストレージシステムをスケールアウトさせる
- シャーディングとパーティショニングを同じ意味で使う
- マシンやサーバーそしてノード 分割されたデータを格納する物理的な計算機を指す
- クラスタあるいはリング ストレージシステムを構成するマシン群
- データセット全体にまたがるような問い合わせはほとんどない→シャーディングもキーに基づいてやるのがよろしい
- ハッシュパーティショニングとレンジパーティショニング
必要になるまでシャーディングを避ける
シャーディングはシステムを複雑化させるものだから シャーディングを使わずにスケールさせる方法→リードレプリカ、キャッシュ
リードレプリカ
- リクエストはたいてい読み込みのほうが書き込みより多い
- 書き込みリクエストはすべてマスターノードに任せ、読み込みリクエストはデータのレプリカを持つマシンにまわす
キャッシュ
- システム上でよく使われるコンテンツをキャッシュする
- Memcachedは複数サーバー上にメモリブロックを確保してデータストアのデータをキャッシュ
リードレプリカやキャッシュを使えば、読み込み処理をスケールアップさせることができる。しかし、書き込みやデータ更新の頻度が上がり始めたら、最新状態を保持するマスターサーバーへの負荷が増加する
コーディネーターによるシャーディング
CouchDBプロジェクトは、単一サーバー上での挙動を重視している。LoungeとBigCouchのふたつのプロジェクトは外部のプロキシを通じてCouchDBへの負荷をシャーディング
コーディネーターが、リクエストされたドキュメントのキーに応じて個々のCoucdDBインスタンスにリクエストを分散
コンシステントハッシュリング
キーのセットを統一された形式で分散させる。これは、キー・バリューのペアを複数のサーバーに分散させるための便利なツールとして使える
ハッシュリングの実例
コンシステントハッシュリング
データのレプリケーション
複数サーバーでの永続化のためにレプリケーションをするには、あるサーバーの担当範囲に割り当てられたキーと値のペアをリング内でのその次のサーバーに渡せばよい
リングごとに担当サーバーが割り当てられており、サーバーが落ちたら別のサーバーが持ち場を負担する
よりよい振り分け
ハッシュはキー空間を均等分布させるという点では統計的に有効であるが、均等に分布さ せるには通常はある程度多くのサーバーを必要だが、大抵は少数のサーバからスタートする→担当するキーの範囲にばらつきが出てしまう問題を解決するために、Riakを含む多くのDHTは、物理マシン単位でいくつか`仮想'ノードを作成
レンジパーティショニング
レンジパーティショニング方式によるシャーディングでは、システム内の何台かのマシン が「どのサーバーがどのキー範囲を受け持つか」というメタ情報を保持
コンシステントハッシュ方式と違うところは、キーのソート順で隣同士になるキーがほぼ同じパーティションに収まるというところ
ルーティング用のメタデータのサイズを軽減できる。範囲を表すには単に[開始位置,終了位置]の印があればよい
リングにならないパーティショニング方法
BigTableの手法
階層化レンジパーティショニングでデータをタブレットにシャーディングする手法
タブレットサーバ
- マスターサーバーは、タブレットの割り当てをメタデータテーブルで管理
- クライアントは三階層の走査を経てキーの保存先のタブレットサーバーを知る(だいたい三段階で事足りる 理屈上はいくらでも増える)
- DNSの名前解決に似ている
http://ja.wikipedia.org/wiki/BigTable
障害の処理
BigTableの設計では、マスターが単一障害点になる。マスターが死んでいてもタブレットサーバに影響が無いように出来る
- HBase BigTableの階層方式を使ってレンジパーティショニングを行う
- MongoDB BigTableと同様の方法でレンジパーティショニングを処理
- Cassandra 順序を保持したパーティショニング機能を提供
- TwitterのGizzardフレームワーク 分割され、レプリケートされたデータをさまざまなバックエンドにまたがって管理するもので、レンジパーティショニングを使ってデータをシャーディング
どのパーティショニング方式を採用するか
ハッシュ方式とレンジ方式、シャーディングの手法としてどちらが適切なのか←それは状況による
- レンジパーティショニング たとえばキーによる検索よりも範囲指定による検索が多発するような場面がいい。ただしノードのルーティングや構成を管理するための事前コストが必要
- ハッシュパーティショニング データを複数のノードに適切に分散させることができる
- レンジパーティショニングで分割したデータは小さいチャンクで負荷分散できるようになり、負荷が高くなったときの調整も可能となる
まとめ1
データを複数マシンにレプリケートすれば永続化できるし負荷分散もできる
13.5 整合性
NoSQLの世界でデータの整合性を保つための方法
- 強整合性(strong consistency) これはすべてのレプリカを同期させる
- 結果整合性(eventual consistency) レプリカが同期されていなくてもかまわないが、最終的にはお互い相手側の状態に追いつけるようにしておかなければならない
結果整合性が選択肢に入る分散コンピューティングの本質
CAP
今どきのネットワーク機器上で構築された分散システムの特性=強整合性をとれない
分散システムの3つの特性、CAP
- 整合性(Consistency) あるデータのすべてのレプリカについて、どれを読んでも同じバージョンのデータを得られるか?(ここでいう整合性は、ACIDのCとは異なる)
- 可用性(Availability) アクセス不能なレプリカがいくつあっても、読み書きのリクエストに対応できるか
- 耐分断性(Partition tolerance) レプリカの一部が一時的にネットワーク上で他と分断されたときに、それでもシステムを稼働させ続けられるか
複数台のコンピュータで構成されるストレージシステムは、この三つのうちの二つまでしか達成できず、その二つを達成するためには残りの一つが犠牲になってしまう
すべてのNoSQLシステムで、耐分断性が必須となる。残された選択肢は、整合性と可用性のどちらを妥協するかである。両方を保証できるようなNoSQLシステムは存在しない
整合性を保証(すべてのレプリカに対する更新を確認)しようとすると、各データアイテムに対する24時間体制の可用性は保証できなくなる
可用性を保証するというのは、ユーザーが何らかの操作を実行したときには、他のレプリ カの状態がどうであるかにかかわらず自身が持つデータ上で操作を受け付けなければならな いということだ。これは、レプリカ間でのデータの整合性を失ってしまう
一貫性の原理(仮定)
- N レプリケートした数
- W 書き込みや更新に対して更新を処理し終えたことを確認出来る台数
- R 読み込みに対して同じ値を受け取ったことを確認出来る台数
このとき、R+W>Nであればシステムの強整合性を実証できるものとする
強整合性
多くの強整合性システムはW=NそしてR=1という設定を選んでいる。そうすれば、同期に失敗したノードをどうするかを考えずに済む
結果整合性
R + W <= N であってもかまわないが、W < Nだとレプリカを安心して使えない
同期プロセスを高速化するためのDynamoの影響を受けた方法
データのバージョン管理や衝突の検出が重要
http://funini.com/kei/logos/clock.shtml
- バージョニングと衝突
- ベクタークロック(プログラムの進捗)
- ベクタークロックがB(39,2,5)とC(39,1,6)みたいなのがあった場合は、矛盾する更新があったとサーバが判断する
- 衝突の解決
- 衝突の解決はストレージシステムを使うアプリケーション側に任せている
- Voldemortは、衝突の解決はストレージシステムを使うアプリケーション側に任せている(よろしくッッみたいな感じでアプリケーション側に丸投げする)
- Cassandraは、各キーのタイムスタンプを格納しており、二つのバージョンが衝突する場合は一番タイムスタンプの新しいバージョンを採用
- Riakは、このいずれかを選択出来る
- CouchDBは、衝突を検出したら、ユーザー側でそのキーを手動で修復させるよう問い合わせ、衝突が解決するまでは特定のバージョンを確定的に採用してユーザーに返す
- 直列化されてはいない
- リードリペア
- コーディネーターが読み込み時に衝突を検出すると、たとえ整合性のある結果をユーザーに返せたとしても、コーディネーターは衝突したレプリカの衝突解決プロトコルを開始
- DBが持ってる機能なのではないかと思われる
http://wiki.apache.org/cassandra/ReadRepair_JP
- Hinted Handoff
- どれか一つのノードが一時的に使えなくなっている状態での書き込みのパフォーマンスを向上させるテクニック
- データの伝搬が遅れているときに、反応しなかったノードへの書き込みは個別に続けられるやつ
- 一時的に書き込みを引き継がせる。復旧した時に書き込みを反映させる
- コーディネートノードが死んだら一巻の終わり
http://wiki.apache.org/cassandra/HintedHandoff_JP
- Anti-Entropy
- もしキー空間全体のハッシュが二つのレプリカで一致しなければ、レプリケートしているキー空間のより小さい部分のハッシュを順に交換していき、同期できていないキーが特定できるまでそれを続ける
http://wiki.apache.org/cassandra/AntiEntropy_JP
- Gossip
- 定期的(毎秒など)に、あるノードがランダムに別のノードを選んでお互いに通信し、自分が知っている他のノードの健康状態を交換する
http://wiki.apache.org/cassandra/ArchitectureGossip_JP
13.6 13.7 最後に & 謝辞
NoSQLはまだ成熟していないので、今回議論したシステムの多くもそのアーキテクチャや設計そしてインターフェイスを変えていくかもしれない
NoSQLは、設計作業の多くをアプリケーション側の設計に委ねた
第9章 Hadoop Distributed File System
P153(PDFだとP171)
Hadoop Distributed File System (HDFS)
- 大規模なデータセットを高い信頼性で格納するために作られたシステム
- データセットを広帯域でユーザーアプリケーションに流せる
- アーキテクチャとエンタープライズデータ
9.1 はじめに
- 大規模なデータセットをMapReduceのパラダイムで分析したり変換したりするフレームワークも用意
- データや計算処理を多数の(数千台もの)ホストに分散できる
- アプリケーションから実行した計算処理をデータ側で並列実行できる
9.2 アーキテクチャ
NameNode
- 名前空間は、ファイルとディレクトリの階層構造
- DataNodeへと個別にレプリケート
- DataNodeが複数のアプリケーションタスクを並列実行
イメージ及びジャーナル
- 名前システムのメタデータを定義するブロックのリスト
- イメージをRAMに保持
- 定期的にバックアップ(チェックポイント)
- 永続チェックポイントは別の場所
- トランザクションはジャーナルに記録
- NameNodeはチェックポイントから名前空間イメージを立ち上げる。そしてジャーナルの変更を再生していく
- 新たなチェックポイントと空のジャーナルをストレージのディレクトリに書き出したら、NameNodeはクライアントに対応できるようになる
- 永続性を向上させるため、チェックポイントやジャーナルの冗長なコピーをとっておくこ とが一般的(NameNodeが死んだら大変なので、複数のコピーを取っておく)
- リモートのNFSサーバーに置いておけばノード全体の障害からもデータを守れる
- ジャーナルを書いている最中にエラーが出たらそのストレージは除外する
- ボトルネックになりうるのでそのあたりは最適化している
DataNodes
ネイティブファイルシステム上では二つのファイル
- ひとつはデータそのものを含むファイル
- ブロックのメタデータを含むファイル
ブロックの中身が半分空っぽだった場合は、ローカルドライブ上で必要となる容量も半分で済む
- 各DataNodeは、開始時にNameNodeに接続してハンドシェイク
- 名前空間IDは、ファイルシステムのインスタンスに割り当てられる
- ハンドシェイクを終えると、DataNodeをNameNodeに登録する
- 通常の操作中は、DataNodesからNameNodeにハートビートを送信する
- 通常の監視は監視サーバが対象サーバにpingを送っているが、HDFSでは逆に対象サーバが監視サーバに生存確認のpingを送る
- NameNodeからDataNodeに直接リクエストを送ることはなく、ハートビートの返答として何かしらの指示を出す
- 秒間数千回の処理をさばくだけの処理能力をNameNodeは有する
HDFSクライアント
HDFSクライアント ユーザーアプリケーションからファイルシステムにアクセスするときに使う
CheckpointNode
- NameNodeの別モード
- NameNodeの主要な役割はクライアントからのリクエストに対応すること
- NameNodeはCheckpointNodeやBackupNodeなどを演じることも出来る
- 既存のチェックポイントとジャーナルを定期的に結合し、新しいチェックポイントと空のジャーナルを作る
- 通常はNameNodeとは別のノードで稼働する
- 実体はNameNode
- 現時点のチェックポイントとジャーナルファイルをNameNodeからダウンロードし、ローカルでそれをマージして、新たなチェックポイントをNameNodeに返す
- 送り返すだけのノード
- 定期的なチェックポイントの作成は、ファイルシステムのメタデータを守るひとつの方法(毎日チェックポイントを作るのがおすすめ)
- 大規模クラスタだと一週間のジャーナルを処理するのに一時間かかる
BackupNode
http://alpha-netzilla.blogspot.jp/2013/01/hadoop.html
- 最近導入されたやつ
- NameNodeの別モード
- BackupNodeにも定期的なチェックポイント作成機能
- インメモリで最新のファイルシステム名前空間のイメージを保持
- いろいろな選択肢
アップグレードおよびファイルシステムスナップショット
- スナップショットを使えば、管理者はファイルシステムの現状を永続的に保存できる。もしアップグレードしたせいでデータが消えてしまったり壊れてしまったりしても、アップグードを取り消して名前空間とストレージをスナップショット作成時の状態に戻すことができる
- 新たなチェックポイントと空のジャーナルを新しい場所に書き込む。古いチェックポイントとジャーナルを変更せずに済ませるため
- ハンドシェイクの際に、ローカルスナップショットを作るかどうかの指示をNameNodeからDataNodesに出す
- コピー・オン・ライト方式
スナップショット DataNodeの状態も保持するので、及ぶ規模が大きくなるので1つしか持てない チェックポイント DataNodeの状態は複製しないので、複数持てる
- DataNodeがブロックを削除するときにはハードリンクだけを削除
書き込み時にコピーする。書き込む前に一旦コピーして、コピーしたほうを書き込む
- クラスタ管理者は、システムを再起動するときにHDFSをスナップショットの状態に戻すことができる
- ロールバックを選択すると、ロールフォワードはできなくなる
- アップグレードするときに壊れたら怖いので、しくったらスナップショットを使う。成功したらスナップショットは破棄する
- 自動変換をするには、新しいレイアウトバージョンのソフトウェアにアップグレードしてシステムを立ち上げなおすときにスナップショットを作ることが必須
スナップショットは難しい 真面目に使われているのだろうか。あまりにデータ量が膨大になりそうだし、負荷もすごいかかりそうだし。
間違えて消したり上書きしたりすることはしょっちゅうあるので、毎朝6時にバックアップをとっているとか。
おわりに
分散処理システムをごにょごにょしたことがないので、とりあえずサンプルからさくっとやってみたいなと思ったり。 Hadoopの本は昔買ったけど完全に積読です
ほぼ12600文字ェ…
