データ指向アプリケーションデザイン

概要

本

• データ指向アプリケーションデザイン

かかった時間

• 5.5 時間

読む前の状態

デザインについては実はあまり読んだことがないかも。現場での実践経験をもとにデザインしている。

この本を読んで達成したいことはなにか

読む前後の変化

読書メモ

第I部データシステムの基礎

1章 信頼性、スケーラビリティ、メンテナンス性に優れたアプリケーション

• 多くのアプリケーションは演算指向ではなく、データ指向

• 多くのアプリケーションで必要となる機能

  • データベース

  • キャッシュ

  • 検索インデックス

  • ストリーム処理

  • バッチ処理

• データシステムの原理と実用性、データ指向アプリケーションを構築するためにそれらを使う方法をたどる

• 信頼性とスケーラビリティを持ちながらメンテナンスしやすいデータシステムの基礎

1.1 データシステムに関する考察

• ツールの分類はあいまいになっている

• 単一のツールでは要求を満たせないことが増えている

  • 適切なツールを用いて効率よく処理する

image

• アプリケーションを設計することはデータシステムを設計すること

• ソフトウェアシステムにおける重要な3点

  • 信頼性

  • スケーラビリティ

  • メンテナンス性

1.2 信頼性

• 信頼性とは、何か問題が生じたとしても正しく動作し続けること

• フォールトとは問題を起こしうるもの

  • フォールトに耐性があるものを耐障害性を持つ(フォールトトレラント)であるという

• フォールトは仕様を満たしていないコンポーネント

• 障害はシステムが全体として必要なサービスのユーザーへの提供を止めてしまった場合

• ハードウェア

  • ハードウェアに冗長性をもたせる

  • ハードウェアの冗長化に加えて、ソフトウェアによる耐障害性の手法を使うことによって信頼性を高める

• ソフトウェア

  • システム内のシステマティックなエラーもフォールトの一つ

  • 汎用的な解決策はない

• ヒューマンエラー

  • 人間には信頼性がない

  • 複数のアプローチを組み合わせる

    • エラーの可能性が最小限になるようにシステムを設計する

    • ミスを犯しやすい部分を分離する

    • ユニットテストからマニュアルテストまでテストを徹底的に行う

    • 容易にリカバリできるようにする

    • モニタリングの仕組みを用意する

    • 優れた管理方法とトレーニングの実践

• 信頼性を犠牲にして開発コストを下げたりする場合があるが、信頼性を犠牲にしていることを強く意識するべき

1.3 スケーラビリティ

• 負荷の増大に対してシステムが対応できる能力のこと

• 負荷は負荷パラメータによって可視化できる

• 負荷が増大したときに起こることの調査方法

  • 負荷パラメータを増やしながら、システムのリソースを一定に保ったときにシステムのパフォーマンスにどのような影響があるか

  • 負荷パラメータを増やしたときに、パフォーマンスを一定に保つためにはリソースをどの程度増やす必要があるか

• システムのパフォーマンスの表現方法

  • バッチ処理の場合はスループット

  • オンラインシステムの場合はレスポンスタイム

  • 典型的なレスポンスタイムを知りたい場合は算術平均ではなく、パーセンタイルによる値を用いること

  • パーセンタイルは、SLAやSLOに用いられることがある

• 負荷への対処

  • スケールアップ

  • スケールアウト

    • 複数のマシンに負荷を分散させることあ、シェアードナッシングアーキテクチャと呼ばれる

  • エラスティック

    • 負荷の増大を検知して、自動的にコンピューティングリソースを追加できるシステム

  • システムのアーキテクチャはアプリケーションに固有の度合いが強い

    • 汎用的な技術を組み合わせる

• メンテナンス性

  • 運用性

    • 優れた運用性は定型のタスクを容易にし、運用チームが勝ちの大きな活動に集中して力を注げるようにしてくれる

  • 単純性

    • 単純にするということは偶発的な複雑さを除くということ

    • 抽象化によって、実装からのみくる偶発的な複雑さを除く

  • 進化性

    • データシステムにおいてアジリティを高めるための方法

1.4 メンテナンス性

まとめ

2章 データモデルとクエリ言語

2.1 リレーショナルモデルとドキュメントモデル

2.2 データのためのクエリ言語

2.3 グラフ型のデータモデル

まとめ

3章 ストレージと抽出

• アプリケーション開発者はアプリケーションに適したストレージエンジンを選択できる必要がある

• データの保存、取り出しに関するデータベースの内部動作に留意すべき

3.1 データベースを駆動するデータ構造

• ログとは追記のみが行われるデータファイル

• データベースから特定のキーの値を効率的に探索するためにはデータ構造=インデックスが必要

  • ナイーブにファイルに書く込む例の場合は探索のコストが O(N)

• メタデータとはデータを探索するために追加で置いておくもの

• インデックスはデータベースの内容には影響がなく、クエリのパフォーマンスに影響がある

  • 書き込みの場合はインデックスへのオーバヘッドがあるので書き込み速度が低下する

  • トレードオフ

3.1.1 ハッシュインデックス

• インメモリハッシュマップを用いたインデックスの例

  • ハッシュマップはすべてインメモリ上に存在する

image

(例にはキーのオフセットに対してREADする終端位置が書いていないが \n ということと想定)

• 追記のみの場合、いずれディスク領域を使い切る

• ログがあるサイズ以上になったらファイルをクローズして、ログをセグメントに分割する

• ログのクローズ後は新しいセグメントファイルに書き込みを行う

• それぞれのセグメントに対してマージとコンパクション処理を行う

  • ログ中で重複しているキーを捨てて、キーの最新の値のみを残す

  • マージ中も古いセグメントファイルを参照することでREADとマージを並行して行うことが可能

• 各セグメントごとにインメモリハッシュテーブルを持つ

• キーの値を探索するときは、最新のセグメントから探索して、存在しなければ2番目に新しいセグメントを探索。これを繰り返す

• 現実的なエンジンにするための検討事項

  • ファイルフォーマット

    • シーケンシャルに生の文字列が続くバイナリフォーマット

  • レコードの削除

    • 削除の用の特殊なレコードの追加

  • クラッシュのリカバリ

    • インメモリハッシュテーブルの再構築は、セグメントファイルをすべて読み直すことで可能

    • セグメントファイルが増大するにつれ時間がかかるので、ハッシュマップのスナップショットを保持することでリカバリを高速化する

  • 部分的に書き込まれたレコード

    • チェックサム

  • 並行性の制御

    • Writerは1プロセスのみ。Readerはイミュターブルなので複数のプロセスで並行して可能

• 追記のみの有効性

  • (ディスク上の)セグメントの追記とマージはシーケンシャルなWriteなので高速

  • 並行処理とクラッシュリカバリがシンプルになる

    • TODO: クラッシュに関しては中途半端な状態にならない、という意味かな？

  • フラグメンテーションを避けることができる

• 制約

  • ハッシュテーブルがメモリ上に存在する必要があるため、キーの数が(メモリに収まらないくらい)大きくなると使えない

  • 範囲に対するクエリの効率が良くない

3.1.2 SSTableとLSMツリー

3.1.2.1 SSTable

• SSTable(Sorted String Table)

• セグメントファイルのフォーマットに制約を追加する

  • (すべての)セグメントファイルは キーでソート済

  • 各セグメントファイルは キーで一意

• 利点

  • セグメントのマージがシンプルで効率的にできるようになる

  • すべてのキーをメモリ上に保持する必要がない

    • あるキーの値を知りたいときは、その前後キーのオフセットが分かれば、区間内を走査すればよいため

  • 範囲のキーをディスクにWriteする前に圧縮しておく

    • (TODO: 圧縮するタイミングはよくわからなかった。キーでソートされているのでRangeのクエリが得意なのはわかる)

  • SSTableの構築と管理方法

    • インメモリツリー(AV木や赤黒木)を用いる。memtableと呼ばれる

    • memtableのしきい値を超えた場合、memtableからセグメントファイルを生成。memtableはキーでソート済のためファイル生成は十分高速

    • Readはmemtable -> 最新のセグメントファイル -> ...

    • バックグラインドでマージとコンパクションを実施

• 制約

  • クラッシュ時にmemtableに書き込まれているが、まだセグメントファイルに書き込まれていないデータを失う

    • すべてのmemtableに書き込まれたデータと同じデータをディスク上のログとして別に書き込んでおく(未ソート)

3.1.2.2 LSMツリー

• Log-Structureed Merge-Tree(LSMツリー)

  • TODO: SSTable(と同じような原理)をベースにしているデータ構造

• 全文検索エンジン(ElasticSearch, Solrなど)のApache Luceneも似たような原理

  • (転置インデックス)

3.1.2.3 パフォーマンスの最適化

• LSMツリーの最適化

  • 値がないことの探索

    • memtableから調べてすべてのセグメントファイルのハッシュテーブルを走査しないといけないため時間がかかる場合がある

    • bloom filterを用いると効率的

  • SSTableのコンパクションとマージ戦略

    • 最も一般的なのは サイズごと, 階層(Level)ごと のコンパクション

3.1.3 Bツリー

• 1970年代に登場した、多くのリレーショナルデータベースにおいて標準的なインデックスの実装

• 非リレーショナルデータベースにおいても多く使われている

• キーペアはソートされた状態で保持

  • log-structuredインデックスは、データベースを可変のセグメントに分割してセグメントにはシーケンシャルに書き込む

  • Bツリーはデータベースを固定サイズのブロックorページに分割

    • ブロックサイズは通常4KB

    • ハードウェア上のディスクも固定サイズのブロックを並べる

    • メモリではなくディスク上に存在する

image

• あるページを根として参照しているページをたどることで葉の値を取得する

• Bツリーへの操作

  • 更新: 葉を探索して、直接そのページの値を更新する

  • 追加: 範囲に合致する葉を見つけ、キーの値を追加する。追加するページが存在しない場合は上位のノードを分割

  • (削除: 書いていないけど、説明も大変)

• Bツリーの操作とディスク

  • 更新操作はディスク上のページの上書き

  • 追加操作で複数のページの上書きが必要になる場合もある

• 対クラッシュ

  • WAL(write-aheadログ, redoログ)をもたせる

    • 更新された内容をBツリーの反映させる前にWALログに書き込む

    • クラッシュ時はWALログを用いて整合性の取れた状態に戻す(ロールフォワード)

• 並行性

  • 複数のスレッドから同時に更新がある場合は、ラッチ(軽量なロック)を取得することで保護

• Bツリーの最適化

  • 細かいテクニックなので割愛

3.1.4 BツリーとLSMツリーの比較

• ワークロードによるが一般的にはLSMツリーはBツリーよりも書き込みが高速、読み込みが低速

• ストレージエンジンのパフォーマンス計測における考慮事項

• LSMツリーの長所

  • 書き込み負荷が高いアプリケーションでは、データベースへのディスクの書き込みがボトルネックになることがある

    • LSMツリーは一般的にBツリーよりもスループットを高く保つことができる

      • 書き込みの増幅度を抑えることができる場合がある

      • 複数のページを更新する必要がない

      • シーケンシャルに書き込めば良い

      • 圧縮率を高めることができる

• LSMツリーの短所

  • コンパクション処理が実行中のパフォーマンスに影響する場合がある

  • コンパクションにより書き込みのスループットが高くなってしまう

  • データベース量が大きくなり、コンパクションが間に合わなくなる場合がある

その他のインデックス構造

• セカンダリインデックス

  • キーはユニークでなくても良い

    • マッチする行のリストで保持

    • それぞれのキーに行の識別子を追加してキーをユニークとして扱う

3.1.5.1 インデックスへの値の保存

• インデックスのキーの結果の値は実際の行か別の場所への参照

  • 葉からヒープファイルを参照することでデータが複製されることを防ぐ

  • クラスタ化インデックス

    • データをインデックス内に保存

  • 非クラスタ化インデックス

    • データへの参照のみをインデックス内に保存

    • ヒープ内のデータは非ソート

    • (TODO: 使い分けがよくわからない。というか非クラスタ化インデックス is 何？)

3.1.5.2 複合インデックス

• 連結インデックス

  • 複数の列を扱うインデックス

• 多次元インデックス

  • 複数の列を扱うより汎用的なインデックス

    • 地理情報など(応用はいろいろある)

      • 2次元の値を1次元に変換

      • 特化したインデックスの生成(Rツリー)

3.1.5.3 全文検索と曖昧インデックス

• 全文検索エンジン

• 曖昧なキーの検索

  • 編集距離

  • レーベンシュタインオートマトン

3.1.5.4 全データのメモリでの保持

• ディスクの良さ

  • 永続性

  • RAMよりもGBあたりの単価が低い

    • RAMも安くなっている

• インメモリデータベース

  • メモリ内のデータ構造をディスクに書き込める形式にエンコードするオーバヘッドを削減できることがメリット

  • プライオリティキューなどの様々なデータモデルを扱うことができる

• インメモリデータベースの拡張

  • アンチキャッシングアプローチ

    • メモリが不足しているときにディスクに逃がす

    • OSのメモリとスワップの関係に似ているが、ページ単位ではなく個々のレコード単位で扱うことができるので効率的

3.2 トランザクション処理か、分析処理か？

• オンライントランザクション処理(OLTP)

  • インタラクティブなトランザクション処理

• オンライン分析処理(OLAP)

  • データウェアハウス

image

• OLTP処理はビジネスにとって重要で分析目的とは分離する

• データウェアハウスを用いる

  • ETLを用いてOLTPのデータをデータウェアハウスに取り込む

image

• データウェアハウスの利点は、分析のユースケースにそってデータベースを最適化できること

• 分析用途のスキーマ設計はあまり多様性はない

  • スタースキーマ

    • ファクトテーブル(Futureでいうとトランテーブル)とディメンションテーブル(マスタテーブル)を用いた分析

  • スノーフレークスキーマ

    • ディメンションを更に細かく分けたケース

3.3 列指向ストレージ

• OLTPデータベースは行指向

• 列指向ストレージ

  • 列ごとの値をまとめて格納する

    • Parquetも列指向

  • 圧縮

    • 列に含まれる値は似た値が多いため、列指向ストレージは圧縮に適している

    • ビットマップエンコーディングやランレングス圧縮が効果的

  • メインメモリからのCPUキャッシュへの帯域の効率的な利用

  • CPUパイプラインの効率化

    • 分岐ミスなどの削減

    • SIMD

  • ベクトル化処理による効率化

  • ソート順序

    • よく使うクエリに基づいて最適化

    • ソートすることでランレングス圧縮がより効果的になる(似た値が並ぶため)

    • 同じデータをレプリケーションする際に異なる順序でソートしてくことで複数のクエリパターンに最適化することができる

      • Vertica

    • LSMツリーを用いてインメモリストアに書き込みをし、あるタイミングでファイルに書き出す

      • クエリはメモリとディスク上の列データを両方参照。オプティマイザが吸収

• マテリアライズドビュー

  • 仮想のビュー

  • 元のテーブルへの更新でマテリアライズドビューを更新しないといけないため、OLTPには向いていない

  • 読み取り専用のデータウェアハウス向け

まとめ

• オンライントランザクション処理と分析処理の最適化の違い

  • アクセスパターンの違い

  • OLTPのストレージエンジンの違い

    • log-structured

    • インプレース

• log-structuredストレージエンジン

  • ディスク上のランダムアクセスの書き込みをシーケンシャルな書き込みに変換し、書き込みのスループットを高める

• 分析系のワークロードはOLTPとは異なる

  • 列指向ストレージが有効

4章 エンコーディングと進化

• 互換性

  • 後方互換性

    • 古いコードによって書かれたデータを新しいコードが読めること

  • 前方互換性

    • 新しいコードによって書かれたデータを古いコードが読めること

• 後方互換性を満たすのは難しくない(古いコードは既知だから)

• 前方互換性は新しいコードで追加された部分を無視する必要があるので難しい

• データをエンコードする様々なフォーマット

• スキーマの変更をどのように扱い、新旧のデータとコードが混在するシステムをどのようにサポートするか

• フォーマットがデータストレージと通信でどのように使われているか

• (TODO: スキーマってバージョン番号を含むメタデータのこと？)

4.1 データエンコードのフォーマット

• データの表現

  • メモリ内での表現

  • バイト列の並び

    • メモリ内での表現と異なり、エンコードする必要がある

• エンコーディング(シリアライゼーション、マーシャリング)

  • インメモリからバイト列への変換

• デコーディング(デシリアライズ、アンマーシャリング)

  • バイト列からインメモリへの変換

4.1.1 言語固有のフォーマット

• インメモリオブジェクトをバイト列にエンコードする機能が組み込まれている

  • 特定のプログラミング言語に固有

  • デコーディングする際のセキュリティの問題

  • 前方互換性や後方互換性が保たれない

  • 非効率

4.1.2 JSON、XML、様々なバイナリフォーマット

• JSON, XML, CSVなど存在する

  • 微妙な問題は存在する

  • 合意形成が重要

• JSONやXMLをバイナリフォーマットで扱うエンコーディングが開発されている

  • JSONであればMessagePack, ...

4.1.3 ThriftとProtocol Buffers

• バイナリエンコーディングライブラリ

  • Apache Thrift

    • BinaryProtocol

    • CompactProtocol

  • Protocol Buffers

  • スキーマあり

• スキーマの進化

  • フィールド

    • エンコードされたデータの意味にとってフィールドタグが極めて重要

    • 新しいタグ番号を用いることによって古いコードは新しい番号を無視することできる(前方互換性)

    • フィールドがユニークなタグ番号を持っていれば、タグ番号の意味は変わることなく古いコードを読むことができる

      • 制約としては、新しく追加するフィールドは必須にはできない(エラーになるため)

    • 削除の場合は同じタグ番号を使わなければOK

  • データ型

    • 切り捨てられる場合はあるが、互換性を保つことができる

4.1.4 Avro

• バイナリのエンコーディングフォーマット

• タグ番号がない

• エンコーディングとデコーディングで全く同じスキーマを使う必要がある(?)

• ライターのスキーマとリーダのスキーマは同じである必要はなく、互換性だけあれば良い

  • フィールドの順序が異なっていても良い

    • スキーマ解決の際にフィールド名でマッチさせるため

  • 前方互換性

    • デフォルト値ももっているフィールドの追加や削除が可能

• スキーマを知る方法

  • ファイルの先頭に含めておく

  • レコードの先頭にバージョンを含めておく

  • 双方向プロトコルを用いる

4.1.5 スキーマのメリット

• Thrift、Protocol Buffers、Avroのバイナリエンコーディングがシンプルで使いやすかったため、広範囲のプログラミング言語でサポートされた

• メリット

  • バイナリJSONよりもコンパクトになること

  • スキーマがドキュメンテーションとして価値がある

  • スキーマを管理することで互換性を保つことができる

  • スキーマからコードを生成することによってコンパイル時に型チェックができるようになる

4.2 データフローの形態

• データフローの形態

  • データベース経由

  • サービス呼び出し経由

  • 非同期のメッセージパッシング経由

4.2.1 データベース経由

• データベースの場合は前方互換性も後方互換性も求められることが多い

• 古いコードが新しく追加されたフィールドを更新してはいけない(nullになるので)

• データをスキーマに合わせて書き直すことはできる(マイグレーション)が多くの場合は負担になるのでやらない

• スキーマの進化が重要

4.2.2 サービス経由でのデータフロー:RESTとRPC

• サービス指向/マイクロサービスアーキテクチャにおいて鍵となる設計目標は、それぞれのサービスを独立してデプロイして、進化させられるようにすることでアプリケーションの変更とメンテナンスを容易にすること

• サーバーとクライアントが使用するデータのエンコーディングはサービスAPI間で互換性を保つ必要がある

• WebサービスのアプローチにはRESTとSOAPがある

  • RESTはプロトコルではなく、HTTPの原理の上に構築された設計哲学

    • リソースの識別にURLを用いるシンプルなデータフォーマット

    • キャッシュの制御、認証、コンテントタイプのネゴシエーションにHTTPの機能を使う

  • SOAPはネットワークAPIのリクエストを発行するためのXMLベースのプロトコル

    • SOAPメッセージは手作業で構築するには複雑

• RPC

  • リモートにあるネットワークサービスへのリクエストの発行を、同一プロセス内でのプログラミング言語における関数やメソッドの呼び出しと同じように見せる

  • リモート呼び出しとローカルの呼び出しは異なる

    • ネットワークのリクエストの予測は不可能。リトライなどは必要

    • タイムアウトによって結果を返さずに制御が戻ることがある

    • 冪等性

    • ネットワークリクエストはレイテンシが大きくなるし、ばらつきが出る

    • パラメータはバイト列に変換する必要がある

    • クライアントとサーバー間の言語は異なる可能性があるため、データ型を変換する必要があるかもしれない

4.2.3 メッセージパッシングによるデータフロー

• 非同期メッセージパッシングシステム

  • バッファとしての機能

  • メッセージの再配信

  • 送信側と受信側が素結合になる

  • あるメッセージを複数のプロセスで受信できる

• メッセージブローカーは特定のデータモデルを強制しないため、任意のエンコーディングフォーマットを利用できる

  • 前方互換性、後方互換性が保ちやすい

第II部分散データ

• 複数のマシンにデータベースを分散させたい理由

  • スケーラビリティ

  • 耐障害性/高可用性

  • レイテンシ

II.1 高負荷に対応するスケーリング

II.1.1 シェアードナッシングアーキテクチャ

• 水平スケーリング

• ノード間の調整は、通常のネットワークを通じてソフトウェアで制御

• データを分散させたときに生じる問題

II.2 レプリケーションとパーティショニング

• 複数のノードにデータを分散させる方法

  • レプリケーション

    • 同じデータのコピーを複数のノードに保持する方法

    • 冗長性を提供

  • パーティショニング

    • パーティションというサブセットに分割する方法

5章 レプリケーション

5.1 リーダーとフォロワー

5.2 レプリケーションラグにまつわる問題

5.3 マルチリーダーレプリケーション

5.4 リーダーレスレプリケーション

まとめ

6章 パーティショニング

6.1 パーティショニングとレプリケーション

6.2 キー‐バリューデータのパーティショニング

6.3 パーティショニングとセカンダリインデックス

6.4 パーティションのリバランシング

6.5 リクエストのルーティング

まとめ

7章 トランザクション

7.1 トランザクションというとらえどころのない概念

7.2 弱い分離レベル

7.3 直列化可能性

まとめ

8章 分散システムの問題

8.1 フォールトと部分障害

8.2 信頼性の低いネットワーク

8.3 信頼性の低いクロック

8.4 知識、真実、虚偽

まとめ

9章 一貫性と合意

9.1 一貫性の保証

9.2 線形化可能性

9.3 順序の保証

9.4 分散トランザクションと合意

まとめ

第III部導出データ

III.1 記録のシステム（Systems of Record）と導出データ

III.2 各章の概要

10章 バッチ処理

10.1 Unixのツールによるバッチ処理

10.2 MapReduceと分散ファイルシステム

10.3 MapReduceを超えて

まとめ

11章 ストリーム処理

11.1 イベントストリームの転送

11.2 データベースとストリーム

11.3 ストリームの処理

まとめ

12章 データシステムの将来

12.1 データのインテグレーション

12.2 データベースを解きほぐす

12.3 正確性を求めて

12.4 正しいことを行う

まとめ