『データ指向アプリケーションデザイン ――信頼性、拡張性、保守性の高い分散システム設計の原理』Part 1 データシステムの基礎

Part 1 データシステムの基礎

Ch01 信頼性,スケーラビリティ,メンテナンス性にすぐれたアプリケーション

目的

  • データ指向であり,演算指向でない
  • データ指向アプリケーションの機能
    • DB
      • cache
      • search idx
      • stream処理
      • batch処理
  • データシステムの原理と実用性,それらの適用.

考察

対応

  • !2 信頼性
    • フォールトトレラント ≒ レジリエント(リバウンドが語源.元に戻る力.)
      • 障害 @ システム全体 > フォールト @ 仕様を満たさないコンポーネント
      • エラー処理でフォールトを正しく作り出す.
    • !!1 hardwareの障害
      • MTTF: 10000台なら1日に1台はディスククラッシュ
      • 冗長化
        • hardwareのコンポーネント冗長化で十分(複数のマシンでの冗長化が要らない)ことが多かった.
        • → 規模増 + AWSなど単一マシンの信頼性down
        • → hardwareの冗長化 + softwareの対応も必要
        • rolling upgrade
    • !!2 softwareのエラー
      • softwareのシステマティックなフォールト
        • → テスト,検証,設計での積み重ねによる対処.
    • !!3 human error
      • sandbox env.
      • automatic test
      • telemetry
    • !!4 trustnessの重要度
      • userの責任
  • !3 scalability
    • !!1 負荷の表現
      • 負荷のパラメータ → 成長にかんする問い.
        • fanout(入力されたリクエストを処理するのに必要となるほかのサービスへのリクエスト数)
          • 図1-2: relational schema → twitterの初期バージョン
          • 図1-3: data pipeline, caching → 負荷が増えてこちらに切り替え.
            • followerの分布: 負荷のパラメータ
              • → ハイブリッドな取得.
    • !!2 performanceの表現
      • throughput, responce time @ online system
      • latency, responce timeの違い
        • responce time は クライアントから見た値
        • latencyは,処理を待つ時間.
      • △ mean(平均)を見る → ユーザの体験は説明できない
      • 〇 percentileを使う. → 〇median(a.c.a p50, 50 percentile値)を見る.
        • 外れ値: p95, p99, p999を見る
          • tail latency: service experienceに直にかかわる.重要.
      • responce time 100ms 大 → 売上1%down
      • 1 sec latency → customer satisfaction 16%down @ Amazon
      • p値はSLO(Service Level Objectives), SLAに使われる.
      • 大きなpのresponce値は,queuingのdelayによるものが大部分.
        • head-of-line blocking(HOL blocking)
          • Clientでのresponce timeの計測が重要
      • 図1-5: 1つのrequestの処理にbackendのcallが複数必要なパターン
        • tail latencyの増幅
      • 最小限のCPUとメモリのコスト下で,十分な室でpの概算値を計算するアルゴリズムがある.
      • responce timeのデータ集計: histgram同士を加算する.
    • !!3 負荷への対処のアプローチ
      • scale up: 垂直, scale out: 水平
      • shared-nothing archtecture: 複数マシンに負荷分散
      • elastic: 負荷増検知 → 自動でコンポーネントリソースを追加
        • → 手動の方がシンプル.
      • scalableなarchtecture: 負荷のパラメータの下に構築.
        • iterationが重要.
  • !4 maintenance性
    • 3つのdesign doctrine
      • 運用性
      • 単純性
      • 進化性: 拡張性,修正容易性,plasticity(可塑性,成形力,プラスチックと同じ)
    • !!1 運用性
      • 定型のタスクを容易にする @ datasystem
        • runtimeの挙動やシステム内部の可視化の機能を,優れたモニタリングとともに提供.
      • automationと標準ツールとの結合サポート
      • 個々のマシンへの依存性を持たせない.
      • 優れたドキュメンテーションと分かりやすい運用モデル
      • デフォルトの挙動を優れたものにする
        • 管理者のオーバーライド可
      • 自己回復 @ 正常なとき
      • 予期できる挙動
    • !!2 単純さ.複雑さの管理
      • 巨大な泥団子
      • 実装のみから生じる複雑さの除去
        • 偶発的な複雑さ
      • → 抽象化
    • !!3 進化性: 変更への配慮
      • アジャイル: TDD, refactor
        • 小さなローカルスケール
      • → より大規模なレベル
        • 単純性と抽象化が重要.
  • まとめ
    • 機能要求・日機能要求
    • !2, !3, !4の内容

Ch02 data modelとquery lang

目的

  • data model: problemへの考え方についてとても重要
    • softwareにできること,できないことをとても大きく決定する.
    • → アプリケーションに適したdata model が重要
      • dataの保存とクエリのための汎用できdata modelを見る.
  • 各レイヤでの表現
    • clean data model ← 抽象化

2.1 Relational model, Document model

目的

  • dataをrelation(SQLではtable)として構成.
    • 各relationは,順序なしのタプル(SQLでの行)の集合.
  • 起源: business dataの処理
    • transaction 処理, batch処理
  • network modelや階層モデルを倒す @ 1970's - 80's
  • とても汎用的
    • 例: online publishing, discussion, sns, e-commerce, game, SaaSのためのアプリケーション

対応

  • !1 NoSQLの誕生
    • 実際には特定の技術を指していない
      • OSの非 relational distributed databaseのためのhashtag @ 2009
      • → Not Only SQLとなった
    • NoSQLの採用要因
      • 極大datasetや優れた書き込みthroughputなど,relational DBよりscalability実現用意
      • freeでopenなsoftwareが好まれる > 商用
      • relational DBにできない特殊なクエリ操作
      • relational DBのスキーマ制約へのフラストレーションと,よりダイナミックで表現力のあるdata modelへの欲求.
    • 併用.ポリグロットパーシステンス(複数モデルでの永続化).
  • !2 objectとrelationのmismatch
    • impedance mismatch
      • application code内のobjectと,テーブルなどのdb model間の不格好な変換レイヤが必要.
      • ActiveRecordHibernateなどのORM frameworkは定型コードを減らすが,完全には隠せない.
    • 図2-1: relational schemaでのLinkedInのプロフィール表現
      • 正規化
      • 構造data type, XML data type
      • JSON, XMLのドキュメントとして,エンコードしてテキスト型の列に保存.
        • applicationが解釈
      • 例2-1: ドキュメントのようなdata structureには,JSONで表現
      • MongoDB, RethinkDB, CouchDB, Espressoなどのdocument指向DBがサポート
    • JSONの問題もある.
    • JSONでの表現: localityに優れている
      • → 1度のクエリで取得〇.
      • 図2-2: 木構造を形作る1対多のrelationをJSONが明示.
  • !3 多対1と多対多のrelation
    • id, 文字列
    • copyの問題
      • id自体は意味なし → 〇変更不要
        • → 正規化で回避可能
      • 意味のある情報がコピー → ×書き込みのoverhead + 不整合リスク
    • 正規化: 多対1 → ドキュメントDBは非サポート
    • data同士のつながり
      • entity化.ユーザ間の関係.
      • 図2-4: 多対多の関係
        • 結合が必要
  • !4 document DBとhistory
    • IMS(Information Management System) @ 1990's
      • 階層モデル
      • → 多対多への対応×
      • → relational model(→ SQL)とnetwork model(→ 廃れた)が解決.
    • !!1 network model
      • conference on Data Systems Langs(CODASYL)
        • CODASYL model
          • access path
          • queryやupdateのcodeが複雑で柔軟でない
          • 変更に弱い.
    • !!2 relational model
      • query optimiserがクエリの実行順序やどのインデックスを使うか判断
        • → 新機能の追加容易
    • !!3 document DBとの比較
      • document DB: 階層モデルに回帰 + 多対1,多対多の関係の表現〇
        • ↑ 関係のあるアイテムはユニークな識別子で参照.
        • document reference @ document DB = foreign key @ relational DB
  • !5 今日のrelational DBとdocument DB
    • document data modelのメリット: schemaの柔軟性,localityによるパフォーマンス,データ構造がアプリケーションに近い.
    • relational DBのメリット: 結合や多対一および多対多の関係のサポート〇
    • !!1 applicationのコードをシンプルにするためのデータモデル
      • relationでの細分化 → スキーマが込み入ってapplication code複雑
      • 多対多の関係が必要 → 整合性のためにrelational modelが〇.
        • ↑ document modelはとても複雑.パフォーマンス大きくdown.
      • data item間のrelationの種類に依存 → dataの関係性強い → graph model > data model > document model
    • !!2 document modelでのschemaの柔軟性
      • Schema on read(Schemalessは誤用) ←→ Schema on write @ relational model
        • left: dynamic型check, script language
        • right: static型check, compile language
        • 大規模なテーブルへのupdateの回避: nullを設定して起き,読み取り時に内容を埋める.
      • Schema on readが有用なパターン
        • 数多くのオブジェクトを個別テーブルに保存するのが現実的でないとき
        • data structureが外部システムで決定される.変更を予期できないとき.
      • ←→ すべてのレコードが同じ構造であるべき → document化と構造の強制.
    • !!3 queryのためのdata locality
      • documentの保存形式
        • JSON, XML: encodeされた文字列
        • BSON(@MongoDB)など: binary型
      • storageのlocality: document全体にaccessする場合はmeritあり.
        • 1度にdocumentの大部分が必要なとき以外は不要.
        • → documentは小さく保つという制約がdocument dbにはある.
      • localityをいかすため,関連するデータ同士をグループ化.
        • document modelに限らない.e.g. GoogleのSpanner. OracleのMulti Table idx cluster table.
        • Bigtableのcolumnfamilyという概念も,localityの管理において同じ目的.
    • !!4 documentおよびrelational dbの融合
      • relational db
      • document db
        • RethinkDB: relational的な結合をquery languageでサポート.
        • MongoDB: driver内では,DBの参照を自動解決.
      • 非単純ドメイン: nestした関係を行の中に入れてよいという着想.
      • relational db, document dbの類似性アップ.
        • ⇔ 各data modelで補完し合う
        • → relational, documentのhybrid model

2.2 dataのためのquery language

目的

  • SQL: 宣言的query language ←→ IMS, CODASYL: 命令的code
    • programming language: 多くは命令的
    • e.g. sharks = σfamily(σ: シグマ.selectionのs. 選択演算子) = "Sharks"(animals)
      • SQL
      • 宣言的: どのように達成するかは指定しない.
        • → query optimiserが判断
        • 簡潔(> 命令型), 扱いやすい
          • 実装の詳細を隠蔽 → queryを書き換えずにパフォーマンスを改善.
        • SQL: 機能的制約多い → DBによる自動最適化の余地大.
        • 宣言的: 並列実行容易 ←→ 命令型.

対応

  • !1 Web上での宣言的query
    • CSS, XSLとも宣言的
    • JSのDOM(Document Object Model): 命令的
      • 問題多い
    • Web browserでは,宣言的なCSSのstyle指定 >> JSで命令的操作
    • → DBでも,SQLのような宣言的language. >> 命令的query API : e.g. IMS, CODASYL by COBOL
  • !2 MapReduceでのquery
    • 大量dataを多くのマシンにまたがってまとめて処理.by Google
      • e.g. MongoDB, Couch DBなどのNoSQLが限定的にサポート.
    • 宣言的と命令的の間のどこか.
    • map, reduceはpure function: parameterのみがinput
      • 任意の場所と順序〇.
    • cluster上のdistributed processingのための,とても低レベルなprogramming model.
      • SQLなどの高レベルのprogramming languageをMapReduceのprocessingのpipelineとして実装可.
        • ただし,MapReduceを使わないSQLのdistributed processingの実装系も多くある.
    • query中のJSのcodeもMapReduce以外でもOK
    • MapReduceの問題: codeの整合を取るのが難しい
      • → MongoDB 2.2: aggregation pipelineという,宣言的なquery languageをサポート.

2.3 Graph型のdata model

目的

  • 一対多(tree structure)や,record同士が関係弱い
    • → document modelが〇
  • 多対多 → Graph としてdataをmodelingが〇
  • Graph: 頂点(a.c.a. node, entity)と辺(a.c.a. edge, relation, 弧)という2つのObjectで構成.
    • e.g. Social graph, Web graph, 道路や電車のnetwork
  • 一貫性を保ちながらまったく異なる種類のobjectを単一のdata structureに保存するのにもGraphは〇
    • e.g. 図2-5(Graph structureのデータの例)
  • property graph modelと,triple store model
  • query: Cypher, SPARQL, Datalog, Gremlin, Pregel

対応

  • !1 property graph
    • important 3 points
      • 関連付けは任意
      • 任意の頂点への入出力の辺をeffectiveに見つけられる
        • → graphを検索できる
      • 関係の種類ごとに異なるラベル → cleanなdata modelを保ち,単一のgraph内に様々な種類の情報.
    • 構成
      • 頂点
        • id, 外への辺集合, propertyのcollection(K, V)
        • id, 始点,終点,2頂点間の関係を示すラベル,propertyのcollection
    • 柔軟,進化性〇.
  • !2 Cypher query language
    • property graph用のquery language
      • e.g.
    • query optimiser ← 宣言的language
  • !3 SQLでのgraph query
    • 結合の数が事前に決まらない.困難.
    • 再帰共通テーブル式 → 例2-5
    • query language: 4 Lines, ほかのlanguage: 29 Lines
      • UCごとに適した設計のdata modelも異なる
  • !4 triple store, SPARQL
    • ほぼproperty graph modelと同じ
    • application構築のために価値ある様々なtoolsやlanguagesある
    • 3部分からの言明(主語,術後,目的語). e.g. (Jim, likes, bananas)
      • 目的語は,primitiveなdata 型の値 or 別の頂点.
      • 記法: 例2-7
    • !!1 semantic web
      • RDF(Resource Description Framework)
        • → "web of data", internet規模での「あらゆる情報のDB」
      • tripleは,applicationの内部的なデータモデルとして優れる.
    • !!2 RDF data model
      • Turtle/N3: 読みやすい.Apache Jenaなどのtoolで自動変換可能.
      • tripleがURIになる.
      • URIは単なるnamespace
    • !!3 SPARQL
      • Cypherの元となったもの(about pattern matching)
      • 変数が?から始まる
      • 優れたquery language
    • !!4
      • graph dbとnetwork modelの比較
        • graph >>> network
    • !!5 礎となったもの: Data log
      • のちのquery languageの礎.SPARQLやCypherよりはるかに古い.
      • e.g. DatomicはDatalogをqueryとして使用.CascalogはHadoop内のbig datasetへのqueryのためのData logの実装
      • predicate(subject, object) ←→ tripleでは(subject, predicate, object)
      • 複雑なデータには有用
      • 図2-6: processing

まとめ

  • document db: dataが自己完結しているdocument群.document間の関係がそれほどないUCがターゲット.
  • graph db: あらゆるもの同士が関係するようなUCがターゲット.
  • どちらも,保存するデータにスキーマを強制しない.
  • 各モデルには独自のquery languageやframeworkあり.
  • その他のmodel

Ch03 storageを抽出

目的

  • dbの根本task: dataの保存とrequestへのresponce
  • 保存と取り出しのDBの内部動作を見る.
    • → 自分のapplicationに適当なengineの選択
    • transactionと分析のためのoptimiseの各engineは大きく異なる
    • log-structured storage engineと,B木のようなpage指向のstorage engine

3.1 dbを駆動するdata structure

目的

  • log: 追記のみできるrecordの並び.
  • index
    • metadataを追加で横に置いておく
    • 追加のdata structure
    • dataの書き込みのoverhead. 合わせて更新必要.
    • → 要選択
    • ↑ 書き込みは低速

対応

  • !1 hash index
    • K=V store: dict型に似ている
    • 図3-1: inmemory hash mapでindexづけ
    • e.g. Bitcask
    • 図3-2: K-V更新ログのcompaction
    • 図3-3: compactionとsegmentationのマージを同時実施
    • 詳細
      • fileformat
      • recordのdelete
        • tombstone
      • crashのrecovery
      • 部分レコードへの対応
        • checksum
      • concurrency control
    • 追記のみの利点
      • 書き込みの高速化 ← 追記とマージはsequencial
        • SSDでもあるていどsequencialの方が〇.HDDなら◎.
      • 平衡処理とcrash recovery の単純化
    • hash table indexの制約
      • key数多いとメモリ内に収まらない. → disk上は遅い.
      • 範囲へのquery効率×.
  • !2 SSTableとLSMTree
    • keyでsort
      • → Sorted String Table. → SSTable
    • SSTableのメリット
      • 図3-4: merge容易.merge sortと似ている.
      • indexが疎でよい.
      • 圧縮可能.disc領域とI/O band削減
    • !!1 SSTableの構築と管理
      • inmemory tree: memorytable
    • !!2 SSTableからLSMTreeの作成
      • e.g. LevelDB, RocksDB
        • LevelDB: Riak, Bitcaskの代替〇.
        • Cassandra, HBaseでも使われている.
        • GoogleBigtableの論文からアイデアを得た.
      • Log-Structured Merge-Tree → LSMTree
        • 以前の成果のfilesystem
      • ElasticsearchやSolrが使うLuceneもterm dictionary(語の辞書)という同様の手法を使う @ 全文検索
    • !!3 performanceのoptimise
      • bloom filter: 集合の内容の概要を保持.メモリ効率〇.
      • sizeごと,levelごとのcompaction.
      • SSTableをバックグラウンドでマージ.: simple and effective.
      • memory両の制約なし
      • 範囲へのquery〇
      • 書き込み: sequencial
  • !3 B Tree
    • log-structuredよりgeneral(ほとんどのDBの標準)で,全く異なる
    • K-V pairをsortして保持することのみ似ている.
    • log-structuredはsegmentに分割 ←→ B Treeは固定サイズのブロックやページに分割
    • 図3-6: B Tree indexのkeyのlookup
    • root, leaf page
    • baranching factor: 子ページへの参照数.一般的には数百.
    • 図3-7: ページ分割
    • treeはbalanced → n個のkeyのB Treeの深さは常にO(logn).
      • およそ3から4の深さで収まる.
    • !!1 B Treeのtrustnessを高める
      • その場でファイル変更 ←→ LSMTreeなどlog型の構造のインデックス
      • crash耐性のため,write-ahead log (a.c.a. WAL, redo log)
      • concurrency control ← latch(軽量ロック)で保護
        • → log-structuredのapproachの方がシンプル
    • !!2 B Treeのoptimise
      • crachのrecovery
      • keyの短縮
      • disc上の場所 ←→ LSMTreeはsequencial
      • 追加のポインタ: 隣接ページ
      • fractal treeなど,B Treeの変種
  • !4 BTreeとLSMTreeの比較
    • 大まかにはBTreeの方が成熟している.
    • LSMTreeはperformance特性〇.
      • writeが高速 ←→ BTreeはreadが高速
    • !!1 LSMTreeのメリット
      • 書き込みの増幅度合いが低くなりうる + tree内の複数ページの書き込み不要.
      • → 書き込み速い.特に磁器HardDiscにおいて.
      • 圧縮率〇 → ファイル小さい.
      • 多くのSSDはfarmwareが内部でlog-structuredなアルゴリズムを使う.
      • → 書き込みへの影響小さいが,dataがコンパクト.
      • → I/O 帯域幅内でのread/write request回数増える.
    • !!2 LSMTreeのデメリット
      • compactionがrunningのread/writeに影響しうる.←→ BTreeは高percentileも予測しやすい.
        • 高p値が極めて高くなりうる.
      • compactionでwriteのthroughput増大しうる
      • writeのペースとcompactionのペースの不一致への対応 → 明示的にモニタリング
      • BTreeは,keyがindex中の1か所のみある.
      • → 強いtransactionのsemanticsに〇
      • ↑ keyの範囲でロック.
  • !5 その他のindex構造
    • ここまでのK-V indexは,PKのindexのようなもの
    • secondary indexも使われている.
      • 同じkeyをもつ行への対応
      • BTreeやlog-structuredなindexをsecondaryにも使える
    • !!1 indexへの値の保存
      • heap file: 行が保存されている場所.非cluster化index
        • data のコピーを回避
      • cluster化index: index内に行を直保存
      • 中間: covering index. a.c.a. 付加列を持つindex
        • 一部の列のみindexに持つ.
      • clusterかindexやcovering indexは,読み取り高速,書き込み中速
        • transaction保証の負担もある.
    • !!2 複合index
      • 連結index: 複数フィールドを1つのkeyとする
        • keyの部分の検索には使えない
      • 多次元index
        • 2次元を単一数値に変換
        • RTree
          • e.g. PostGISは,PostgreSQLのGiST(Generalized Search Tree) indexの機能を使ったRTree.
          • → 地理空間index
        • 地理に限らず,多parameterなほかの例にも使える.
    • !!3 全文検索とあいまいなindex
      • 特定の編集距離にある語の検索
      • LuceneはSSTableに似た構造
      • レーベンシュタインオートマトン
    • !!4 全データのメモリでの保持
      • discはdataの配置が重要 for performance
        • 永続性,容量あたりコスト安が〇
      • → RAMが安くなり,コストのメリットが薄れている
      • → inmemory db
        • 複数マシンへの分散も〇
        • e.g.
          • VoltDB, MemSQL, Oracle TimesTen
            • relational modelのinmemory db
          • RAMCloud: OSSのinmemory K-V store.永続性あり.
          • Redis, Couchbase: discへの非同期書き込み.→ 弱い耐久性.
      • inmemoryのperformanceのメリット
        • memory内のdata structureをディスクに書く形式にエンコードするoverheadを回避できること.
      • performance以外のメリット
        • disc baseでは実装困難なデータモデルの提供
          • e.g. Redis: priority queueや集合などのdata structureに対するDBのようなインターフェースを提供
      • anti caching approach
        • 使えるメモリより大きなdatasetをサポート.
          • swapfile @ OS よりeffectiveにmemoryを管理 by db
          • indexはすべてmemoryに収まる必要
      • 不揮発性memory(Non-Volatile Memory, NVM)が広まれば,さらなる変化が見込まれる.

3.2 transaction? analyze?

目的

  • transaction ← commercial transactionから
    • 必ずしもACIDという意味ではない
    • Clientが低latencyでr/wをするということのみ意味する
    • ↑→ batch処理
    • OLTP: OnLine Transaction Processing
      • interactive
    • ↑→ data analyze: OLTPとはaccess patternが大きく異なる.
      • 大量レコードのスキャン.要約統計(レコード数,合計,平均など)を計算.
      • → Business Intelligenceの向上のためのレポートに含まれる.
      • a.c.a. OLAP(onLine Analytic Processing)
    • 表3-1: OLTP, OLAPの違い
    • 別個のDB: Data Ware House, DWH

対応

  • !1 DWH
    • OLAPがOLTPに負荷をかけないようにしたいという要件
    • ETL(Extract-Transform-Load)で,OLTP dbからOLAP dbにロードする.
      • 図3-8: 概略
    • 大企業,多くのOLTP systemをもつ, でDWHをもつ
    • DWHを分析的なaccess patternにoptimise
    • !!1 OLTP dbとDWHの違い
      • DWH: relational model
        • SQLはanalyticなqueryに〇 ^ drilldownやslice, diceでデータを探索
      • SQL Server, SAP HANAなどは,SQL IFのみ共通.内部は異なる.
      • 高価な商用License: Teradata, Vertica, SAP HANA, ParAccel
        • Amazon RedShift; ParAccelのhosted version
      • OSS: SQL-on-Hadoop proj.
    • !!2 Star, Snowflake
      • 多くはStar schema(a.c.a. dimension model)
        • 中心はfact table
        • 図3-9: e.g.
        • dimension table
        • table同士のrelationの可視化 → factをdimensionが加工 → Star
        • snow flakeの方が正規化だが,Starの方がシンプルで〇

3.3 列指向storage

目的

  • 例3-1: analytic query
  • OLTP: 行指向 ←→ OLAP: 列指向
    • 図3-10
    • 非relational modelでも使える
      • e.g. Parquet ← GoogleのDremelが元.
        • document data model

対応

  • !1 列の圧縮
    • 図3-11: bitmap encode
    • Big Tableの列familyは行指向
    • !!1 memoryの帯域とベクトル化処理
      • vectorized processing ← AND, OR
      • compaction → 効率〇
  • !2 列storageでの sort order
    • sort → 圧縮〇
    • !!1 複数sort order
      • 異なる方法でstore e.g. Vertica
      • 列のみが値を持つ ←→ secondary index
  • !3 列指向storageへの書き込み
    • LSMTreeで書き込み.× BTree
  • !4 集計.data cube, materialized view
    • materialized aggregates(実体化された集計)
    • data cube, OLAP cube: materialized viewに特化したケースで広く利用
      • 図3-12: 2次元data cube
    • 計算済みにしておく
    • 柔軟なqueryには使えない.

まとめ

  • OLTP
    • discのseekがbottle neck
  • OLAP
    • discの帯域がbottle neck → 列指向 storage
  • OLTPのstorage engine
    • log-structured(fileへの追記と古いfileのdeleteのみ), LSMTree
    • BTree
      • update可の固定サイズのページ集合
    • log-structuredはrecent developed.
      • sequencialな書き込みに変換 from discへのrandom access
    • OLTPのindex構造, inmemory db
    • OLAPのarchtecture
  • tuning parameterの増減の影響の理解

Ch04 encodingと進化

目的

  • 進化性
    • data formatやschemaの変更
    • rolling upgrade a.c.a. 段階的rollout
    • Clientのupdateはuserのtiming
    • → 新旧バージョンのコードと新旧バージョンのdata formatがsystem内で共存
    • → 後/前方互換性ともに必要
  • dataをencodeする多様なformatを見る
    • → 新旧dataとcodeが混在するシステムのサポート
    • → data storageとの通信でどう使われるか
    • e.g. REST, RPC, Message Passing System

4.1 data encodeのformat

目的

  • dataを2つのdifferent表現で扱う by program
    • memory内: Object, struct, list, array, hashtable, tree
      • CPUでのaccessや操作がeffectiveなため
    • fileへの書き込み,ネットワークでの送信: 自己完結したbyteの並びとしてencodeが必要
      • e.g. JSON documentとしてのencode
      • pointerは同一プロセスのためのみ有用
    • inmemoryからbyte列への変換: encoding(a.c.a. serialization, marshalling)
      • 逆はdecoding(a.c.a. parse, deserialization, unmarshalling)
      • serializationにはtransactionにて別の意味もある
    • libraryやencode formatには多様な選択肢

対応

  • !1 Language固有のformat
    • Javaの Serializable, RubyのMarshal, Pythonのpickle
    • problem
      • ほかのlanguageで扱うのが難しい
      • decodingで任意のクラスのインスタンス化できる必要
        • security上の問題 ← 任意のコードをリモートで実行可能
      • dataのversioningが弱い
      • effectivenessも弱い(time, size)
    • → このため,一時的な時以外は,languageのbuiltin encodingは避けるべき.
  • !2 JSON, XML, various binary format
    • XML: 冗長,無駄に複雑.
    • JSON: Web browserで初めからサポート.(JSのSubsetという長所アリ) + XMLより単純で人気.
    • CSV: あまり協力でない
    • 共通の問題
      • 数値のencodeのあいまいさ → 大きな数値の扱いが難しい
      • JSON, XMLはbinary stringを非サポート
        • Base 64 でencode → いくらか手が込む + data size 1.33
      • XMLJSONにはschemaあり
        • 学習コスト, encode, decodeのためのhard codi when schemaなど
      • CSVはschemaなくまたあいまい
    • これらの問題があるが,いずれの多くの目的を十分に満たす
    • !!1 binary encoding
      • binaryは領域消費小さい
      • JSONXMLようにbinary encodeが開発されている
        • e.g. MessagePack, BSON, BJSON, UBJSON, BISON, Smile @ JSON. WBXML, Fast Infoset @ XML
      • MessagePackでは,textの81byteがbinaryで66byteになる程度
  • !3 Thrift(Facebook)とProtocol Buffers(Google)
    • 同じ原理のbinary encode
    • encodeするdataへのschema要
      • IDL(If Def. Lang.)
    • 図4-2: ThriftのBinary Protocolでencodeしたレコード
      • field tagの使用
    • → 図4-3: Compact Protocol → わずか34byte
    • 図4-4: Protocol Buffers
    • !!1 field tagとschemaの進化
      • schema: 時とともに変化は避けられない → schema evolution
      • → 互換性のため,field tag が必要
      • 新しいfieldは初期値などの必須は不可.
    • !!2 data typeとschemaのevolution
      • Protocol Buffersのrepeated → 図4-4
      • Thriftには専用のlistdata typeあり
        • nested listをサポート.
  • !4 Avro(Apache Avro)
    • ThriftがHadoopのUCに合わなかったことで開発.
    • Avro IDLとJSON baseの2つのschema language
    • tag no. なし
    • decodeは書き込みと全く同じschemaが必要
    • !!1 writerのschemaとreaderのschema
      • writerとreaderの同一性不要.互換性あればOK
      • → libraryが2つを並べて writer → reader変換
        • 図4-6: 解決
    • !!2 schemaの進化の規則
      • union型: null含めた型指定.
      • fieldの変更
    • !!3 writerのschemaとは
      • どうreaderが知るか
        • 大量レコードなら戦闘で1度渡す
        • schemaのバージョンのリスト
        • networkでのnegotiation
    • !!4 dynamicに生成されたschema
      • Avro: dynamic生成 schemaと相性〇
        • relationalなschemaからAvroのschema生成容易.
          • → dbの内容をAvroのobject Container fileにdamp可
        • db schemaの変更 → Avroでは自動変換.ThriftやPBでは手動にtag割り当て必要.
    • !!5 code generationとdynamic変換
      • ThriftとPB → Code generationに依存.型つきlanguage
        • Java, C++, C#などのstaticなlanguageに〇 ←→ dynamicなlanguageにはcode generation不要
      • Avroはcode generationなしもOK
      • AvroのObject Container file: 自己記述型 → Apache Pigなどのdynamic type languageに〇
  • !5 schemaのmerit
    • Thrift, PB, Avro: 実装や使い方が単純なのが◎.
    • DBのnetwork protocolからのresponceをdecodeしてinmemoryのdata structureに変換するdriverの例: ODBC, JDBC,API
    • binary encodeの長所
      • binary: JSONよりはるかにcompact
      • schema: documentとしての価値.常に最新
      • schemaの互換性をデプロイ前にチェック
      • compile時にtypecheck〇 ← code generation
    • → schemaのevolution: schema less/ onreadのJSON dbと同様に,ある種の柔軟性を提供しながら,dataへの保証up.より優れたtoolを提供.

4.2 data flowの形態

目的

  • processing間でのdata flowを見る

対応

  • !1 db経由のdata flow
    • 後方互換重要.前方もしばしば重要.
    • 図4-7: 古いバージョンのコードでの扱い.
    • !!1 異なる値が異なる時間で書き込みとなるケース
      • migrationを極力回避.
      • db全体が単一のschemaでエンコードされているように扱える
    • !!2 archive storage
      • dataのdampはAvroのObject Connection fileのようなformatが〇.
      • または,Parquetなどのanalyticな列指向formatも〇.
  • !2 service経由でのdata flow: REST, RPC
    • 大規模なapplicationを機能の領域ごとに小さいserviceに分割: micro service archtecture(古くはSOA)
    • → 各serviceが独立
    • !!1 Web Service
      • RESTful API: simpleなapproach.code generationや自動化tool不要
      • ↑→ SOAP
    • !!2 RPCのproblem
      • 場所の透過性の抽象化における根本のproblem
      • remote serviceとlocal objectは根本から異なる
      • → RESTはnetwork protocolであることを明示していて〇.
    • !!3 現在のRPCの方向性
      • FinagleはThriftを,Rest.liはHTTP上でJSONを使う.PBではgRPC.
        • future(promise)で非同期の動作をカプセル化
        • gRPC: streamをサポート.futureは複数serviceの並列requestの単純化
        • service discovery
      • custom RPC protocol(binaryのencode formatを使う)は,REST上のJSONのように汎用的なものよりperformance良い.
      • また,RESTfulなAPIはperformance以外のメリットも多い.
      • → RESTは公開APIでdominant.RPC frameworkは,同一組織内のservice間のrequestに使われる.
    • !!4 RPCのdata encodingとevolution
      • Serverのupdateが先.Clientが後.
      • → requestの後方互換とresponceの前方互換が重要
      • APIのversion 管理の問題あり
  • !3 非同期のMessage Passingによるdata flow
    • RPCとdbの中間
    • message broker(a.c.a. message queue, message try middleware)
      • db的
    • messageが低latencyでdeliver: RPC的
    • RPCに比べたmessage brokerのメリット
      • 信頼性up by buffering
      • messageのロスの回避 by resend
      • 宛先の完治不要
      • 複数宛先に送信可能
      • 送信と受信を論理的に分離
    • 一方,RPCとことなり単方向communication ← 非同期
    • !!1 message broker
      • e.g.(OSS) RabbitMQ, Active MQ, HornetQ, NATS, Apache Kafka
      • queue(or topic)にmessageを送る
      • → brokerがconsumer(or subscriber)にmessageの配達を保証.
      • 単方向data flow
      • messageは多少のmetadataをもつbyte列
      • → 任意のencode format
      • 図4-7のようなケースに注意
    • !!2 distributed actor framework
      • actor model: 単一のprocessing内での並行処理
      • → distributed actor framework: applicationを複数ノードにscale.
        • 場所の透過性〇
        • ↑ 単一processingですらlossを考えているため
        • message brokerとactor modelを1つのframeworkに統合
      • e.g.
        • Akka: Serialization(def: Java)をPBなどに換えられる.
        • Orleans: Akkaと同じくserializationのpluginをつかえる
        • Erlang OTP: mapsがrolling upgradeを容易にするかもしれない.

まとめ

  • encodingが効率性, archtecture, deployの選択に影響
  • 進化性のためのrolling upgrade
  • 互換性
  • data encode formatと互換性についての特性
  • data flowの携帯
    • ↑ data のencodeが重要な多くのケース