今回は, 少しずつ読み進めていた『データ指向アプリケーションデザイン』を読了したので備忘録を残しておきます。本書は分散システムの入門書・ガイドとしてオススメです。600 ページを超える書籍のため, 読書メモを整理した備忘録もそれなりの規模になります。
データ分析基盤や機械学習基盤の構築や運用 (MLOps) は大規模データを対象とすることが一般的であり, スケーラビリティの要件から Hadoop/Spark のような OSS, または SaaS の DWH である Redshift や BigQuery など分散システムをコンポーネントとして選択することが増えています。
これらは利用しやすいように抽象化されており, 手軽に利用することができますが, 分散処理が必要となった背景や, 抱える課題, これまでの課題に対する研究について体系的に知り, 一般的な分散システムの内部でどのようにデータが処理されているかをイメージした上で, 適切なツールを選択できるようになりたいという動機から, 本書を読み始めました。
本書は3部構成となっている。
- 第I部 データシステムの基礎
- 第II部 分散データ
- 第III部 導出データ
大まかに各部を紹介すると, 第I部では, データシステムが考慮すべき信頼性・スケーラビリティ・メンテナンス性について整理し, 様々なデータモデルやストレージエンジン, データのエンコーディングについて取り上げている。
第II部は, 単一のマシンから複数のマシンへと視野を広げ, 一般的な分散方法 (レプリケーション・パーティショニング) やトランザクションとその分離レベル, 分散システムが抱える問題, そして分散システムにおける一貫性と合意について取り上げている。
最後の第III部では, データからインデックスやキャッシュ, 機械学習モデルによる予測結果といった別のデータへと変換 (導出) するための方法論 (バッチ処理・ストリーム処理) やアーキテクチャ, そして将来の展望について論じている。
本書のタイトルでもあるデータ指向アプリケーションの “データ指向” とは, データの量や複雑さ, 変化の速度が課題となるアプリケーションを指している。
第I部 データシステムの基礎
信頼性、スケーラビリティ、メンテナンス性
昨今, データ処理やストレージに対する要求が幅広くなり, 単一のツールではなく処理を複数のタスクに分割した上でタスクに合ったツールを選択し組み合わせることが多くなっている。これを包括的にデータシステムと呼ぶ。データシステム設計の課題として以下に焦点を当てている。
- 信頼性: ハードウェア, ソフトウェアの故障やヒューマンエラーへの耐性.
- スケーラビリティ: データ量, トラフィック量, 複雑性の増大に対して対応可能であること.
- メンテナンス性: 運用性が高くシンプルであり, 時間が経過して要求が変化しても対応できる拡張性. (運用性・単純性・進化性)
これらの課題を解決する簡単な方法はないが, 繰り返し現れるパターンやテクニックは存在する。
データモデル
多くのアプリケーションはデータモデルのレイヤを積み重ねることで実現している。 開発者は現実世界を反映したデータ構造をモデリングする。データ構造の保存は JSON, XML などのドキュメント, RDB のテーブルなどの表現で, メモリ, ディスク, ネットワーク上にバイト列として保存される。
- リレーショナルモデル: データはリレーション (SQL のテーブル) として構成され, 各リレーションはタプル (SQL の行) の集合.
- ドキュメントモデル (NoSQL): 1対多関係の木構造 (階層モデル) を明示的に表現. 自己完結性.
- グラフベースモデル (NoSQL): ノード (頂点) と, ノード間を結ぶエッジ (辺) で関係性を表現.
リレーショナルモデルのユースケースはトランザクション処理とバッチ処理で, ドキュメントモデルはアプリケーションのデータがドキュメントのような構造を持つ場合やローカリティ, スキーマの柔軟性を重視する場合である。
2つのモデルの DB は時間の経過と共に類似性が高まっており, PostgreSQL や MySQL が JSON をサポートする一方, RethinkDB が結合クエリをサポートするなどハイブリッド化が進んでいる。また, 両者はアプリケーションではデータが特定の構造を持つと考えるなら, スキーマが明示的か暗黙的かの違いでしかない。
ストレージ
開発者はアプリケーションに適したストレージエンジンを選択する必要がある。(e.g. OLTP か OLAP)
DB から特定のキーの値を効率的に見つけるには, インデックスが必要となる。インデックスは追加のデータ構造であり, メタデータである。あらゆるインデックスは読み出し速度の向上と引き換えに書き込みを遅くする。
インデックス構造として, Bツリーや Log-Structured Merge-Trees (LSM), 緯度経度を扱う地理空間インデックスとして R ツリーなどが挙げられている。
このようなデータ構造は多くの場合, ディスクの限界に基づくものであり, RAM が安価になるにつれ Memcached や Redis, VoltDB のようなインメモリデータベースの発展に繋がった。インメモリデータベースが高速であるのは, 直感に反してメモリ内のデータ構造をディスクに書き込む際のエンコーディングのオーバーヘッドを回避できるためである。
OLTP 型の RDB と OLAP 型の DWH は SQL インターフェイスを有している点では似ているが, ワークロードの違いから最適化されているクエリのパターンは大きく異なる。また, OLTP ではストレージが行指向でレイアウトされるが, DHW ではファクトテーブルの行数は膨大で大量の列を持つため, 多くの場合, 列指向でレイアウトされる。 列指向ストレージは列圧縮で効率的に保存できるが B ツリーのような in-place な更新はできない。DWH では集計結果に対する特定のクエリの読み取り性能の向上のためマテリアライズドビューがサポートされることが多い。
エンコーディング
通常, プログラムはデータを大きく2つの表現で扱う
- メモリ内でデータをオブジェクト, 構造体, リスト, 配列, ハッシュテーブルなどのデータ構造で保持する
- ファイルへの書き込みやネットワーク経由での送信時にバイト列としてエンコードする
インメモリの表現からバイト列への変換をエンコーディング (シリアライゼーション, マーシャリング), その逆をデコーディング (デシリアライゼーション, アンマーシャリング) と言う。
データエンコードのフォーマットは大きく2つに分類される。
- テキストフォーマット: JSON, XML, CSV etc.
- バイナリフォーマット: Thrift, Protocol Buffers, Avro etc.
上記のバイナリフォーマットはいずれもスキーマを持っている。 Avro はスキーマの進化に対応しており, 柔軟性を持ちながらデータに関する保証を高めることができる。ちなみに, 1984年に初めて標準化されたスキーマ定義言語の ASN.1 はネットワークプロトコルに利用され, そのバイナリエンコーディングは SSL 証明書の X.509 のエンコードでも使われているとのこと。
ネットワーク経由のデータフローは, 現在の主流である HTTP の原理の上に構築された REST や, リモートのネットワークサービスに対して同一プロセス内での関数呼び出しのように見せる RPC の方向性 (場所の透過性) がある。(RPC は後に gRPC に発展)
第II部 分散データ
第I部は単一マシンの場合でも当てはまる内容であった。複数のマシンにデータを分散したい理由はいくつかある。
- スケーラビリティ: データ量, 読み込み/書き込み負荷を分散したい
- 耐障害性/高可用性: あるマシンに障害が発生しても他のマシンで代理したい
- レイテンシ: 地理的に近いデータセンターからレスポンスを返したい
複数のノードにデータを分散させる一般的な方法は2種類ある。
- レプリケーション: 同じデータのコピーを複数ノードで保持する.
- パーティショニング (シャーディング): 大きなデータをパーティションに分割する. パーティションは別々のノードに割り当てられる.
レプリケーション
レプリケーションの構成は大きく3つのパターンがある。
- シングルリーダーレプリケーション: 単一のリーダーからフォロワーに対して変更イベントの書き込みを同期的/非同期的に行う.
- マルチリーダーレプリケーション: 複数のリーダーが書き込みを受け付ける. シングルと比べ性能や障害耐性が向上する可能性もあるが書き込みの衝突など複雑性が増すデメリットが大きい.
- リーダーレスレプリケーション: リーダーの概念がなくどのレプリカも書き込みを受け付ける. (Dynamo スタイル)
シングルリーダーレプリケーションは衝突の解決を気にする必要がないため広く使われている。衝突とは, 2つの書き込みが並行して同じレコードの同じフィールドを変更することである。マルチリーダーまたはリーダーレスは並行性の問題を本質的に抱えている。ただ, 並行書き込みの衝突の順序判定アルゴリズムや並行する更新をマージすることで回避する方法がある。リーダーを立てるレプリケーションではフォロワーの障害はキャッチアップリカバリ, リーダーの障害はフェイルオーバーで対処されることが多い。
パーティショニング
非常に大きなデータセットに対してスケーラビリティが要求される場合は, データセットを部分集合に分けるパーティショニングを用いる。 シェアードナッシング (水平スケーリング) はデータを別々のノードに配置し, クエリ負荷を分散する方法。パーティショニングのスキーム選択はレプリケーションと, ほぼ独立して考えられる。一部のノードにデータやクエリが集中してしまうとホットスポットとなりパーティションの効果は薄れてしまうため均等化することが重要となる。
キー範囲によるパーティショニングはキーがソートされるため, 範囲に基づくクエリを効率化できるがホットスポットが生じやすい。ハッシュパーティショニングはホットスポットを防げるが, 近接するキーがバラバラに分散されるため範囲に対するクエリの効率性が低下する。折衷案として Cassandra の複合プライマリキーなどハイブリッドなアプローチがある。
パーティショニングではCPUやメモリのリソース追加や障害時には, リバランシングが必要となる。リバランシング戦略のシンプルな方法は事前に1つのノードに対して多くのパーティションを割り当てておく方法である。(ハッシュの剰余は頻繁に移動が発生しリバランシング負荷が大きくなるので避ける)
リクエストのルーティング (キーと保持するノードの対応関係) は一般的なサービスディスカバリの問題として捉えられる。
パーティショニングは自動化することもできるが, 予想外の事態とその波及 (カスケード障害) を防ぐためには手動で行うことも視野に入れる。
トランザクション
データシステムはハードウェアやソフトウェアの障害, ネットワークの断絶などの原因で常にフォールトが発生する可能性がある。その中で, できるだけ信頼性を保つ手助けをする方法のひとつにトランザクションがある。トランザクションはアプリケーションが複数のR/Wを論理的な単位としてまとめる方法である。 トランザクションは全体として成功 (commit) と失敗 (rollback) の2つの結果だけであり, 部分的な失敗がないため安全にリトライをしやすくなる。(ただし, 完璧ではない)
トランザクションのリトライは通常, リトライ回数の制限や指数的バックオフを伴う。
トランザクションがない場合, 複雑なアクセスによって DB に生じる影響を把握することは難しくなってしまう。トランザクションにより アプリケーションのプログラミングをシンプルにすることができる。
トランザクションによる安全性は ACID で説明されることが多い。 複数のトランザクションが同じデータにアクセスする場合, 並行性 (レース条件) の問題を考える必要がある。DB は並行性の問題に対して分離性 (isolation) を提供することで隠そうとしてきた。分離性にはいくつかのレベルがある。
- Read Committed: ダーティリード/ダーティライトが発生しないことを行レベルロックなどの方法で保証.
- スナップショット分離: nonrepeatable read (read skew) による一時的な不整合に対する保証. (単純なファントムリードの回避)
- 直列化可能分離 (serializable): 完全に順次実行することで並行性を排除する最もシンプルな方法. (2PL, 順次実行, SSI)
スナップショット分離は性能という観点でも, 読み取りが書き込みをブロックすることはなく, また書き込みが読み込みをブロックすることもないのでロックを競合なく処理できる。SQL標準にはスナップショット分離という概念がないので, DB ごとに別々の名前で呼ばれ定義や実装方法も異なっている。
直列化可能分離レベルは最も強い保証である。2PL はこれまで広く使われてきたアルゴリズムで, マルチスレッド制御の相互排除に似ている。(悲観的な並行性制御)
直列化可能スナップショット分離 (SSI) は, 直列化可能分離レベルを提供しながら 2PL やスナップショット分離より性能のペナルティが少ない。
分散システムの問題
単一マシン上で動作するプログラムと比較して, 複数のマシンで動作するプログラムはネットワークの障害やクロックずれ問題を含む幅広い問題 (非決定性と部分障害) に直面する。
これに対処するには, 部分障害の可能性を受け入れ, ソフトウェアで耐障害性の仕組みを組み込むことである。まずは, フォールトを検出することであるが, 多くの分散システムはフォールト検出をネットワークの障害とノードの障害を区別できないタイムアウトに頼っている。
分散システムにおける全体としての判断は合意が必要となる。合意は分散コンピューティングの重要な基本問題であり, 一様同意, 整合性, 妥当性, 終了性の性質を満たさないといけない。クオラム (ノード群による投票で必要な最小数) による合意に至るには, そのためのプロトコル (アルゴリズム) が必要となる。合意形成において意図せず誤った動作をする誠実的なノードはフェンシングトークンで検出・ブロックできるが, 意図した妨害に対してはビザンチン耐性が必要となる。また, 複数のノードが自身をリーダーと思い込むことを split brain と呼び, これはデータの損失に繋がることが多い。
分散システムには難しい点も多いが, スケーラビリティや耐障害性で利点がある。
一貫性と合意
線形化可能性 (linearizable) の考え方のベースは, システムにデータのコピーがひとつしかないように見せることである。1つのクライアントの書き込みが成功した場合, 即座に読み取りを行う全てのクライアントがその値を見ることができないとならない。これは言い換えると, 最新性の保証 (recency guarantee) であり, ユーザ登録や銀行口座管理のケースで考慮すべき性質である。
前述のレプリケーションの構成では, シングルリーダーレプリケーションのみ線形化可能で, マルチリーダーレプリケーションは線形化可能ではなく, リーダーレスレプリケーションはほぼ線形化不可能となる。
シングルリーダーレプリケーションはリーダーが単一であるためリーダーの障害発生時には, 回復するまで待機, 手動フェイルオーバ, 合意アルゴリズムによるリーダー選出の3つの選択肢がある。合意アルゴリズムを用いる場合, 2PC でなく耐障害性を持つ Viewstamped Replication (VSR), Paxos, Raft, Zab などを用いると良い。また, 合意アルゴリズムはネットワークの問題に敏感なため, 性能への影響とデータ損失のリスクを天秤にかけた上で判断する必要がある。
CAP 定理は対象範囲が線形化可能性とネットワーク分断と狭く, ネットワーク遅延, ノードダウンなどのフォールトは考慮されないため, 歴史的には影響が大きかったもののシステム設計における価値は薄くなっている。
第III部 分散データ
システム内でのデータフローを明確化するために, システム内のアーキテクチャを大まかに以下の2つに分類する。
- 記録のシステム (system of record): 信頼できるデータを厳密に一度だけ記録しバージョンを保持するシステム (一般的に正規化されたデータ)
- 導出データ (derived data): 他のシステムのデータを何らかの方法で変換または処理した結果 (検索インデックス, マテリアライズドビュー, 機械学習モデルの予測 etc.) を保持するシステム (一般的に非正規化されたデータ)
バッチ処理システム
バッチ処理システムでは, 大量の入力データを受け取り, ジョブとして処理を実行, 出力データ (導出データ) を生成する。
UNIXは, ひとつのことを上手く行うツールを組み合わせるという設計原則のもと, ファイルディスクリプタ (ファイル) を入出力インターフェイスとして, パイプによるコマンド (処理) の連鎖が可能である。
2004年に登場した MapReduce も UNIX と似たような仕組みを持ち入出力は分散ファイルシステム (HDFS) 上のファイル, MapReduce ジョブをパイプのように連鎖させてワークフローにまとめる。また, MapReduce ではユーザは明示的に並列化のコードを書く必要はない。高優先度のジョブによるプリエンプションを想定しディスクに頻繁に書き込むことで, クラスタの利用率を高めるように設計されており, 結果としてオーバーヘッドとなる側面もある。
MapReduce と比較して massively parallel processing (MPP) DB ではクラスタ上での分析的な SQL クエリの並列実行に焦点を当てている。MapReduce における任意のコードを実行できる自由 (プログラミングのし易さ) と MPP DB における宣言的なクエリは両者の特徴の差異であったが, 徐々にその違いは小さくなりつつある。
ストリーム処理システム
ストリーム処理システムは時間の経過と共に徐々にやってくるデータ (ストリーム) を扱う準リアルタイムシステムである。イベント (ある時点で生じたレコード) はプロデューサ (パブリッシャ) により一度生成され, 1つ以上のコンシューマ (サブクライバ) により消費される。
イベントをコンシューマに通知するアプローチにメッセージングシステムがある。コンシューマ側の処理を非同期にする場合, メッセージブローカ (メッセージキュー) が利用される。
近年, DB への書き込みの変更ログを他のシステムへレプリケーションする目的で利用する change data capture (CDC) への関心が高まっている。これにより, DB への変更をキャプチャし, 変更の順序を保ちながら検索インデックスやキャッシュを更新することができる。これは, 記録のシステムの変更を導出データシステムにも素早く反映する仕組みである。イベントソーシングも CDC と似た仕組みで, アプリケーションの変更イベントをキャプチャするが, イベントはイミュータブルで追記のみを扱う。
大量のイベントに対してメトリクスの集計を行うストリーム分析では, Bloom filter やカーディナリティ推定を行う HypterLogLog などのアルゴリズムが用いられる。
ストリーム分析フレームワークとしては, OSS では Apache Storm や Spark Streaming, クラウドサービスとして Google Cloud Dataflow や Azure Streaming Analytics などがある。
ストリーム分析では一般的にウィンドウが用いられる。以下の種類のウィンドウがあり, ユースケースによって使い分ける。
- タンブリングウィンドウ (Tumbling window)
- ホッピングウィンドウ (Hopping window)
- スライディングウィンドウ (Sliding Window)
- セッションウィンドウ (Session Window)
また, ストリーム処理に対する結合は以下の3つに分類される。
- ストリーム – ストリーム結合
- ストリーム – テーブル結合 (ストリームのエンリッチ)
- テーブル – テーブル結合 (e.g. マテリアライズドビュー)
データシステムの将来
本書の締め括りは, データシステムの今後の展望についてである。
全てのユースケースに効率的に対応できる単一のツールは存在しないので, 目標を達成するために複数のソフトウェアを組み合わせるという見方を基本軸として, 以下のような方向性やデータ指向アプリケーションを構築する上での倫理性や自己規制について論じている。
- ラムダアーキテクチャ: バッチ処理とストリーム処理の統合化
- メタデータベース: データフローの視点から DB をコンポーネントに解体し, それらを疎結合しアプリケーションを構築 (unbunding database)
- E2E のイベントストリームと非同期的な制約チェック
- 自己検証や自己監査を行うデータシステム
[1] 分散システムについて語らせてくれ
[2] 本当は恐ろしい分散システムの話