『パーフェクトRuby on Rails』学習メモ

Part1 Rails overview

Ch01 Ruby on Railsの概要

  • Rakefile
    • rake -T : タスク一覧
    • rake (taskname) : タスク実行
  • bundle
    • gem packageを束ねる
    • Gemfileが作られる.
  • Railsの思想
    • Web application開発のためのframework
    • CoC(Convention over Configuration)
      • 設定より規約
      • 規約により設定が不要になる.
    • DRY
    • REST(REpresentational State Transfer)
      • すべてのリソースに一意となる識別子(URI)があるという思想.
      • URIを通してリソースを操作する手段を提供
      • リソースを操作するための動詞を中心に考え,機能追加しやすい自然な設計にする
    • 自動テスト
    • まとめ
      • Web applicationをRailsが語る思想に沿ったarchitectureで作成することを,The Rails Way, レールに乗ると表現する.
  • Railsをはじめよう
    • rails new (project name)
      • 重要なファイルなど
    • binstubファイルとして,binにbundle exec省略可能なコマンドを置いている.
    • MVC architectureとして,appディレクトリ以下にmodels, views, controllers + Viewで使うhelpers + assets for frontend + others
    • rails s: Web applicationを起動. s: server
    • libは,独自に実装したRakeタスクなどを配置するのみ.かつては,独立性の高いコードを置く運用もあった.
    • よく使うrailsコマンド
      • routes: display routing information
      • runner: 処理を明確にするため,Rakeとは個別のコマンドとして用意された単体スクリプトの実行
  • scaffold(足場)
    • CRUD操作を行うMVCそれぞれのコードと,テストやDBのテーブル定義を行うmigration fileなどを生成.
    • project作成→scaffold実行
    • DBの変更をmigrationファイルで管理
    • routesでURL設計を確認.
    • RESTfulな考え方がベースとなり作られる.
    • controller, routing
    • routingでURLとコントローラ内のメソッドを紐づけることでURLに対応するアクションを定義.アクションの中で,モデルを通じてデータを取得.そのデータをもとにテンプレートファイルを通じてHTMLを作成・描画している.

Ch02 Ruby on RailsMVC

目的

  • MVCの各要素に対してどのようなコードを書けばよいか見る.
  • MVCのそれぞれの基本的な機能を学ぶ.

内容

  • MVC architecture
    • Model
    • View
      • Modelの内容を参照し,視覚表現を行う
    • Controller
      • Modelのロジック呼び出し,必要なViewの選択など,ModelとViewをつなぐ部分
    • モデルの基礎と考え方
      • modeling: システムを作ることは,解決する問題に対して必要な概念を探して,命名・関係性の整理を行うこと.
      • ActiveRecordでのmodelのimplementation
      • modelとCRUDとの対応.
  • modelを扱う
    • modelを通じた検索
      • ActiveRecord::Relationクラスについて
        • ActiveRecordのQuery Interfaceによる操作結果をオブジェクトとして表現するもの
        • SQLの情報を保持し,実際に必要になったときのみDBにアクセス.
          • 明示的にSQLを発行するときは,to_a method
        • Scopeで,よく使う検索条件をまとめて命名
          • nilを返す必要があるときはクラスメソッドで定義する方が〇
        • default_scopeは安易には使えない
    • model同士のrelation
      • 関連付け
        • SQLite3のための対応必要.
      • has_many, has_one, belong_to
      • 多対多
        • 中間テーブルが必要.
    • dataの更新
      • create, save
      • validation
      • !をつけるとvalidation失敗時に例外発生
    • callback
      • callbackpoint
    • enum
      • !, ?
  • controllerの役割
    • hook
    • CSRF(Cross Site Request Forgeries)対策
    • resources routing
    • exception
      • rescue_from
    • StrongParameters
      • Mass Assignmentで利用できるHashのkeyの許可リストを定義する
      • 権限の扱いなど
  • controllerとviewの協調と,view templateの基本
    • renderingまでの流れ
    • contentsのtypeに合わせる
      • respond_to
    • redirect_to
    • 部分テンプレート, layout
      • variantsによるtemplateの切り替え
  • about view template
    • Prefixの値 + _path で,routingで定義したpathを取得できる
    • helper methodの活用例
      • url_for
      • link_to
      • form_with
      • stylesheet_link_tag, javascript_pack_tag
      • その他
      • 独自メソッド定義
        • app/helpers
    • escape 処理
      • XSS対応
        • そのまま表示 → raw
    • template engine
      • ERB
        • \%を使ってRubyのコードを評価
      • Haml
        • indentでHTMLの構造を表現できる
        • gem packageとして取得する
      • Slim
    • API server として振る舞うときのviewについて

まとめ

  • Model層について,ActiveRecordの基本的な操作,validation,callback
  • Controller層について,ModelとViewをつなぐこと,request objectやaction callback,脆弱性への対処
  • View層について,受け取ったModelを表示すること,template engine, helper method,様々なformatでの表示

  • applicationの主要なlogicはなるべくModelに書くべき

    • Fat Modelへの対応必要.
  • API専用のRails application

    • frontendのinportance高まり,描画を完全にJSに任せるケースあり.
    • rails new my_api --api

Ch03 Railsのbasic機能

  • testの種類と実行方法
    • 各ファイル・ディレクトリごとにテスト対象がある.
    • testの実行
      • bin/rails test (-v)
      • directory単位,ファイル単位,特定の行,テスト名の指定ができる
    • minitestをRailsで扱う
    • fixtureでテストデータを定義
      • modelname(:fixturename)
    • setup, teardown
    • Rails 6.0から,並列テスト可能になる
      • test/test_helper.rb
        • parallelize(workers: 1)とすると並列度が1になる
        • with::threadsとすると,processでなくthreadで並列実行できる
  • RackとRailsの関係
    • Rack: Web application serverとWeb application frameworkの中間において,interfaceを共通化した仕様・実装
      • 疎結合なやり取りを行えるようにするもの
    • Rack application: call methodから受け取ったHTTP request dataなどを元にresponceとして返す内容を決定し,call methodの戻り値とするもの
    • Rack middleware
      • middlewareは,initializeで後続として処理していくapplication(or middleware)のオブジェクトを受け取り,自身のcall methodが呼ばれたときにinitializeで受け取ったオブジェクトのcall methodを呼ぶことで,後続処理を行うという流れ.
      • Pylonsの説明にある玉ねぎの図
      • config内で,使用の有無を管理
        • middlewareの上下関係の設定もできる
  • DBの管理
    • DB関連task
      • RAILS_ENV=productionで製品環境を指定できる
    • 定義の反映
      • db:rollback STEP=1
    • schema fileの取り扱い
    • 用意したデータを読み込む
      • db/seeds.rb
      • !をつけて,エラー発生にすぐに気づけるようにする.
    • table stateを扱う
      • reset = drop + setup
      • prepare: migration, or setup
    • 複数DBを扱う
      • config/database.yml
      • --database=sub
      • 書き込みと読み込みの分離
        • config/environments/production.rb
  • 秘密情報の管理
    • versionごとに管理方法が異なる
    • より開発プロセスにあった形になっている.
  • HTTPとRails application
    • Early Hints
      • 200 OKの前に,103 Early Hints
        • HTMLのパース中にアセットのロード可能
    • CSP(Contents Security Policy)
      • config/initializers/content_security_policy.rb
      • nonce
      • strict-dynamic

Part 2 Railsの周辺知識

Ch04 frontendの開発手法

  • Railsで利用するエコシステムの軸をfrontend開発の標準的な仕組みに移している.
  • JSを管理
    • CSSや画像の管理
    • 自動ビルド
    • ビルド方法の切り替え
    • libraryの統合
    • plugin, loaderの追加
  • CSSの管理
    • CSSを拡張した言語をCSSコンパイル,リクエスト数削減のために1つのファイルへ結合する処理など.
    • 本番環境向けビルド
      • file size削減
    • JSの機能 built in Rails
      • 画面の制御
      • Ajax通信
      • 画面遷移の高速化
        • body tagの中身を入れ替える
        • event の発火
        • Turbolinks
  • 控えめなJS framework
    • Stimulus: 規約をもたらすframework
      • server sideにbusiness logicの実装が寄る
        • HTMLはサーバから返す
        • server sideとfrontendを合わせたトータルの工数が少ない
        • frontendで表現できる幅が狭まる

Ch05 Rails標準の機能を活用して素早く機能実装する

  • Active Jobによる非同期実行
    • mail sending, data集計→CSVファイル作成などの時間がかかる処理に使う
    • 実装,キュー,引数,バックエンドの設定,複数キューの管理,ジョブの例外処理,ジョブのテスト
  • Active Storageによるファイルアップロード
    • 動作,設定
    • サムネイルの生成
    • access制限
    • direct upload
    • helperの不足
    • cacheの不足
  • Action Mailerによるメール送信
    • 使い方,動作確認
    • 設定
    • test
  • Action Mailerによるメール受信
    • 対応サービス
    • 事前準備
    • projectの作成
    • 処理の流れと実装手順
    • test
  • Action TextによるRich text 機能
    • 使い方
    • N+1問題
    • customize
  • Action Cableによるreal time通信
    • web socketを使ったリアルタイム処理
    • chat serviceの作成
    • config
    • 認証
    • worker数の設定
    • UT

Part3 Web Application development

Ch06 Rails application development

  • Railsの機能をいつどのように使うか,一般的なWeb applicationを開発する際に気を付けるべきポイントを見る
  • event notify applicationを作る
  • applicationの作成と下準備
    • applicationの作成
    • Hamlの導入
    • 独自のtop pageの表示
      • top page用のcontrollerの作成
    • gemのversion up 戦略について
    • Bootstrapの導入
      • CSSの記述を最小限にしつつ,デザインを調整しながら開発できるようにする
  • OAuthを利用して「GitHubでログイン」機能を作る
    • GitHub applicationの登録
    • ログインのための機能の作成
    • user model作成
    • ログイン処理の作成
    • ログアウト処理の作成
  • event registration機能の作成
    • time zoneの設定
    • event用のmodelの作成
      • 文字数の制限
        • 正しいデザインで表示するため
    • ログイン状態を管理する処理の作成
    • event registration用のフォームの作成
    • validation error時の設定
      • SJR(Server-generated JS Responses)
    • i18nの設定をする
  • eventの閲覧機能を作る
    • l: localize
  • eventの編集・削除機能を作る
    • 関連を利用する
  • 登録されたeventへの参加機能,参加キャンセル機能を作る
    • N+1問題
    • helperの使い方.オブジェクト指向的な書き方にならない.多いときはプレゼンター.
    • 必ずredirect→インスタンス変数をビューに渡す必要なし→インスタンス変数を使わず可読性を上げる
    • has_manyにdependent: :destroyで,親オブジェクトのレコード削除時に子のレコードも削除.
  • 退会機能を作る
    • 基本の7つ以外のアクションを作りたくなったら別のコントローラを作る.
  • おわりに
    • なぜこのような機能があるのかが重要

Ch07 Rails applicationの test

  • test codeをどう書いていくか
    • システムテストから書く
      • reasons
        • 概要をつかんだ時点でテストを書き始められる
        • すべてを通るのでカバレッジを効率よく広げられる
        • applicationに対する理解が深まる
      • problems
        • ブラウザを使うためスピード遅い
        • モデルなどの部品ごとの仕様の検証は不可能
  • minitest, RSpec
  • test data作成
    • factory_bot
      • sequenceで,固定値を回避
      • 乱数を同じにする場合はseedをオプションで指定する.
  • system test
    • 環境の問題の解決が必要@wsl2
  • controller test
  • model test
    • stub, mock
    • ランダムな値で都合のいいデータを回避
    • validationのテストの扱い

Part4 Rails applicationの拡張・運用

Ch08 Rails application 拡張

  • file upload機能の作成
    • libvipsを使う
    • direct upload時のvalidationは注意点アリ
  • gemで機能拡張する
  • その他の機能
    • error handling
      • rescue_fromは後に登録したものから順番に判定
      • Rack Middlewareを使ったerror handling
        • 独自の例外でpublic/500.html以外を表示したい場合に設定する
        • dynamic error pageのdemerit
      • routingの制限
  • gemの選定

Ch09 コードの品質を上げる

  • CI
    • GitHub actions
      • Elasticsearchとplugin
  • gemの定期更新
    • Dependabot
  • static analysis
  • coverage測定
    • SimpleCov
    • Coveralls
  • Application Performance Measure(APM)
    • Skylight
    • rack-mini-profiler
      • localで手軽に動かせる

Ch10 containerを利用したRails applicationの運用

  • Rails applicationのinfrastructure概要
    • Infrastructure as Code → Docker
    • Disposable
  • 基本的なDocker imageの構築
  • 開発環境におけるDockerの活用
    • ホストマシン上のdirectoryをコンテナ上にマウント
    • docker-compose
  • 環境によって可変する設定値や秘匿情報の管理
  • log出力
    • stdout
    • error tracking
      • 外部サービスをuse
  • HTTP serverとの通信
    • nginxなど,速さ,扱いやすさなどで必要
    • Herokuのガイドなど
    • kubernetesについて

Part5 expert Rails

Ch11 複雑なドメインを表現する

  • architecture patternから見るRails
    • domain modelとActiveRecord
      • RailsではデータストアにRDBを想定
        • ActiveRecordというarchitecture patternを用いて,DBのレコードとオブジェクトを対応付け
    • what's ActiveRecord
    • 単一table継承
      • あるクラスから派生するすべてのサブクラスを1つのtableに対応させる
        • type columnで,各レコードがどのクラスに属するか識別
          • 扱いがほかのカラムと異なる
      • 継承の是非の検討が必要
  • value object
    • entity: 属性の値にかかわらず一意に識別
    • 値objectに切り出す
      • composed_of
  • service object
    • 複数のobjectを組み合わせて表現するとき
    • eventで表現できる場合はeventで表現する
      • test doubleを使えないdemeritあり
    • 実装rule, interface

Ch12 複雑なUCを実現

  • UCとmodel
    • UC @ Rails
      • resources methodによるresource baseのroutingが基本
        • RESTに沿ったroutingを定義
      • URLで表されるresourceをDBのtableと1対1で対応させ,これらのCRUDの操作を通じてUserとやり取り
      • 1つまたは複数のCRUD操作によって,1つのUCを構成
    • Railsのレールの正体
      • modelのCRUD操作の前後に実行される処理を追加することでUCを実現するというapproach
        • e.g. validation, callback
      • UCのlogic: 対象のUCがなければ存在しない,付随するもの
        • domain logicとは異なる
    • レールの限界
  • DBと紐づかないmodelを作る
    • UCのlogic の分離
    • ActiveModel
      • DBに紐づかないmodel
      • Attributes, Callback
      • Serialization
        • attributes
      • Validations
      • Model
        • controller, viewのメソッドでobjectを使えるようにする
  • form object
    • UC logicを実装するobject, application serviceやInteractor, にform_withとの連携に必要なIFを持たせたもの
      • Userとのやり取りに用いるformを簡単に実装できる
    • 共通のvalidation ruleの定義
  • presenter
    • view helperの問題点への対応
    • a.c.a. Decorator
    • ActiveDecorator

Ch13 複雑なデータ操作を実装する

  • Concern
    • data 操作に関するlogicの実装と関連付けの宣言を行うlayer
    • ActiveSupport::Concern
      • included, class_methods, module間の依存関係解決
    • @routing
  • Callback Object
    • 実装方針
      • 更新系はCallback Object
        • for test
      • 参照系には利用できない

VSCodeでGitを使うときに覚えておくこと

VSCodeでGitを使うときに覚えておくこと。

https://qiita.com/y-tsutsu/items/2ba96b16b220fb5913be

コマンドパレット:ctrl+shift+P

リポジトリの初期化 or clone

ファイル追加→ステージング

コミット

コミットログの確認

ブランチの作成

画面の左下のブランチ名(master)が表示されている個所をクリックし,新しいブランチを作成

マージ

まずはmasterに切り替え

Git Historyでマージ元となるnew-branchの右にあるアイコンをクリックしてMerge this commit into current branch

マージ後のブランチの削除

リモートリポジトリの作成

git remote add origin (remote URL)

origin:リモートリポジトリの識別子

リモートへのプッシュ

git push -u origin master

ログからのブランチの作成

競合、部分コミット

(フェッチ→)プル

gitignore

GitHub実践入門はP200から読む。 GitよりもGitHubの方がメインとなっていると思う。 ワークフローについて。

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

Part3 導出data

目的

  • 複数の異なるdata systemを結合
  • → 一貫したapplication archtectureにすることのproblemを検証

  • ⅲ-1 Systems of Recordと導出data

    • dataを保存し処理するsystemの2分類
      • Systems of Record (a.c.a. Source of truth)
        • normalized(正規化)
      • 導出data system
        • cacheなど
        • 非正規化 value, index, materialized viewも
        • original sourceから再生成可能のもの
        • 冗長.but, readのperformanceのために必要
        • denormalized
    • system内のdata flowの明確のために,区別はvery beneficial
      • systemの各部のI/Oと依存関係の明確化
    • dbは単なるtool
      • → application内でどう使うかで分類が決まる

Ch10 batch processing

目的

  • Part 1, 2で,request, query, responce, resultを議論
    • 多くのrecent data systemのpreposition
    • online system: responce timeが重要
      • Web, HTTP/REST baseのAPIで,request/responce styleがgeneral
      • ↑→ ほかのapproachにもメリットあり
    • 3つのsystem type
      • Service(Online System)
        • requestとresponce
        • responce time, 可用性が重要
      • batch processing System(Offline System)
        • 大量の入力dataをprocessingするJobをregular実行
        • throughput で測る
      • stream processing system(near line processing, 準real time system)
        • 入力から出力生成.online processingとbatch processingの中間
        • not request/responce
        • eventはすぐprocessing ←→ batch jobは固定集合に実行
        • → latency低い than batch system
    • trusted scalable(maintainable) systemのために,batch processingは重要なbuilding block
      • e.g. MapReduce ( → Hadoop, CouchDB, MongoDBなど多くのOSS DBに使用)
      • MapReduce: DWHのためのconcurrency systemよりきわめて低levelなprogramming model
        • but, commodity hardware上でのprocessingのscaleという点で,大きな進歩
          • ただし,今では重要性が下がった.だが,batch processingのbenefitを明確に描く.

10.1 Unixのtoolによるbatch processing

目的

  • simpleなe.g.
    • request, processingのたびにlog fileに行を追記

対応

  • !1 simple logのanalyze
    • basical toolでの出力のe.g.
    • !!1 commandの連鎖とcustomのprogram
    • !!2 sortとinmemory集計
      • jobのworking set(jobがrandom accessが必要なメモリの量)の大きさにより,大きい→sort/小さい→inmemoryを使い分け
      • Unix commandの連鎖に容易にscale
  • !2 Unixの哲学
    • 「programをpipeでつなぐ」
    • automation, rapid prototyping, incremental iteration, experiment(実験)への親和性, 大規模projectの管理可能なchunkへの分割
    • !!1 一様なinterface
      • 全programが同じinterface
        • @Unix: file(file descripter) ← orderを持つbyteの並び
      • ASCII textのinterfaceはnot beautiful
        • e.g. △{print $7}より,〇{print $request-url}
      • 結合性が重要
    • !!2 logicと結線の分離
      • stdin, stdout
      • 疎結合(loose coupling), late binding, inversion of controlの1形態
        • → 入出力の結線をlogicから分離
          • → 小さいtoolから大きいsystemを合成
    • !!3 transparencyとexperiment
      • Unixのtool: what happenがとても分かりやすい
        • commandへの入力file: immutable
          • → 何度でも実行OK
        • lessで任意のpointを確認OK
        • 途中でfileにwrite可能 → stageを分割〇
      • 単一マシンでしか動かないという大きな制約あり → Hadoopなどのtoolsで解決

10.2 MapReduceとdistributed file system

目的

  • MapReduceUnix toolsは似ている
  • MapReduceのJobは,distributed file system上のfileをread/write
    • Hadoopでは,HDFS(Hadoop Distributed File System)という,Google File System(GFS)のOpenSourceの再実装
    • GlusterFSや,Quantcast File System(QFS)もある
    • Amazon S3, Azure Blob Storage, Open Stack SwiftなどのObject Storage Serviceも似ている
    • HDFSは,shared nothingの原則に基づく
      • ↑→ NAS(Network Attach Storage), SAN(Storage Area Network)のarchtectureでの共有discのapproachと対照的
        • customのhardwareや,fiber channelなどの特殊なnetwork infra必要
      • ↑→ 特別なhardware不要.datacenter内のnetworkでつながったcomputer群があればOK
    • HDFS: network serviceを公開
      • name nodeという中央Serverが,file blockingのmachineへの保存状況を追跡
      • → 全machineのdisc領域から,1つの巨大なfile systemを生成
    • リードソロモンcodeのようなerasure codingで,完全なreplicationによりoverheadを抑える
      • RAIDのようなものを,特別なhardwareなしに実現
      • HDFS: scalable〇
        • → data storageとaccessのcostはるかに低い.

対応

  • !1 MapReduce Jobのexecution
    • MapReduce: programming framework
      • MapperとReducerをcodingする.
        • Mapper: dataをsortし易くする
        • Reducer: sorted dataのprocessing
    • !!1 MapReduceの分散実行
      • MapReduceは,大量マシンでの演算処理の並列化〇 ←→ Unix commandline
      • 図10-1: MapReduce jobのdata flow
        • Hadoop MapReduceのconcurrencyは,partitioningをbase
        • dataの近くに計算を持っていく
          • → network burden少,locality up
        • MapReduce frameworkが,codeをtarget machineにcopy
        • Mapperが,出力をReducerごとにpartitioning
        • Reducerは受け取ったfileをmerge
    • !!2 MapReduceのworkflow
      • 単一のMapReduce jobで解決できる問題は限定的
        • → jobの連鎖 → workflow
          • @Hadoop: directory名で連鎖する
          • jobのexecution間の依存関係を扱うためのsoftware(scheduler)
            • Oozie, Azkaban, Luigi, Airflow, Pinball
            • → batch jobの大規模部分集合を管理
          • ほかの高レベルtools for Hadoop: Pig, Hive, Cascading, Clunch, FlumeJava
  • !2 Reduce側での結合とgroup化
    • 結合: {foreign key, document reference, 辺}の両端のrecordにaccessしなければならないcodeで必要
    • MapReduceのjobはfull table scan
      • analytic queryでは〇
        • especially, 複数マシンにわたってconcurr
      • → dataset中の何らかの関連をすべて見出す
    • !!1 事例: userのactivity analyze
      • 図10-2: batch jobでの結合の例
      • MapReduceを使って関連するrecordsをすべて同じところにまとめ,effectiveにprocessing
    • !!2 sortmerge 結合
      • 図10-3: flow
        • secondary sort: reducer内でさらにsort
      • mapperの出力がkeyでsort → reducerがmerge
    • !!3 関連するdataを同じ場所にまとめる
      • keyは送信先(を決定)
      • mapperがreducerにmessageを送る
      • MapReduceのprogramming modelで,演算processingでの物理的なnetwork communicationのproblemは,applicationのlogicからisolation
        • MapReduceがapplication codeからnetworkのproblemを隠蔽
    • !!4 GROUP BY
      • e.g. sessionization
      • mapperがgroup化のためのkeyを使う
    • !!5 skewのprocessing
      • linchpin object: 不均衡なactive db record
        • a.c.a. hot key
        • → skew(hot spot)が生じる
        • → 対応
          • e.g. Pigでのskewed join method
            • hot keyを扱うprocessを複数reducerに分散
              • → concurr度up
            • crunchでのsharded joinも同様だが,explicitなhot keyの指定必要
            • hotspotの緩和のためのrandom化と似ている
            • Hiveでは別の方法
              • map-side join
          • hot keyでのgroup化では,2つのstageに分割
  • !3 map-side join
    • joinを高速化
    • reducerなし.sortなし
    • !!1 broadcast hash join
      • 小さい入力が大きな入力のすべてのpartitionにbroadcast
      • hash: 小さい入力をinmemory hashtableにloadする
        • local disc上のread onlyのindexにstoreも〇
      • Pig, Hive, Cascading, Crunchで使える
      • Impaleなどの,DWH query engineでも使われている
    • !!2 partition化 hash join
      • joinのinputがどちらも同じkey, 同じhash functionに基づいて同じ数のpartitionを持っているときのみ使える
        • Hiveでのbucketed map join
        • e.g. 先行するMapReduce jobでinput data generationのcase
    • !!3 map-side merge join
      • partition化を同じkeyでsortedのcase
      • 先行するManagement jobがproceededのcase
    • !!4 map側でのjoinを行うMapReduceのworkflow
      • map-side joinでは,distributed file system中のdatasetのphysical なlayoutが重要 ← preposition 名詞のため
      • Hadoopのecosystem中では,これらのmetadataをHCatalogやHiveのmetastoreで管理
  • !4 batch workflowのoutput
    • batch processingは,OLTPでもOLAPでもない
      • input datasetの大部分のscanはOLAP的だが,MapReduce jobのworkflowはOLAPのSQL queryとは異なる
      • → outputは,×report(@OLAP), 〇別のstructure
    • !!1 search indexの構築
      • 固定されたdocument群への全文検索には,index作成のためのbatch processingはeffective
    • !!2 batch processingのoutputとしてのK=V store
      • search index以外のe.g. of batch processing workflowのoutput
        • classifyerのようなmachine learning systemや,reccommendation systemの構築
      • batch processingからのoutputのapplicationが使うDBへの適用方法
        • 全く新しいDBをbatch job内部で作成
          • Voldemort, Terrapin, ElephantDB, Hoosebulk loadingなどでsupported
          • → distributed file system中のjobのoutput directoryにwrite out
            • → read onlyのqueryをprocessするServiceへbulk load 〇
          • こういったDB fileの構築: MapReduceの良い利用法
            • WAL(Write-Ahead Log)も不要
    • !!3batch processingのoutputでの哲学
      • Unixの哲学と同じ
        • inputはimmuteで副作用を避け,batch jobのperformance up + maintenanceはるかに楽
          • human fault toleranceあり ← ↓rollback 容易
          • minimizing irreversibility (回復不能性の最小化)
          • automatic retryが安全
          • 同じfile集合を多様なjobのinputに使える
          • logicを結線(in/out directory)からisolation
          • 関心の分離. codeのreuse〇
      • Unixとは異なる点
        • Hadoopでは,よりstructuredなfile formatを使い,parse processingを省略可能
        • ↑ effectiveなschema baseのencodingを提供
          • schemaを進化させられる → Avro, Parquetがよく使われる
  • !5 Hadoopとdistributed datacenterの比較
    • Hadoop: Unixのdistributed versionのよう
      • HDFS: file system, MapReduce: Unixのprocessingの実装
        • ある意味,MPP(Massively Parallel Processing)と同じ
          • e.g. Gamma db machine, Teradata, Tandem NonStop SQL
        • 異なるのは,MPPはAnalytic SQL queryのconcurrencyにfocusだが,MapReduceとdistributed filesystemのペアは,任意のprogramを実行できる.
          • よりgeneralなOSのようなものを提供 @ 複数machineからのcluster上
    • !!1 storageの多様性
      • Hadoopは,無差別にdataをHDFSに書き込み,後からprocessingの方法を見つければよいという可能性を打ち出した
      • ↑→ MPP DBでは,db originalのstorage formatにインポートするため,あらかじめdataとquery patternをmodeling要
        • DWHと似た考え.: data を生のままcollect
          • 全く異なるdatasetのcollection speed高い: Datalake, enterprise data hub
      • dataの解釈は,consumerのproblem ← schema on read
        • → 任意の変換可能
          • → sushi principle: dataは生が〇
        • Hadoopは,ETL(Extract-Transform-Load) processingの実装に使われてきた
          • ↑ distributed file systemが任意のformatでのdata encodingをサポート.
    • !!2 processing modelの多様性
      • MPP db: monolithic(一枚岩: monolith)
        • software同士が密結合
      • ↑→ MapReduce: 任意のcodeを大規模datasetに実行簡単
        • HiveのようにSQL Query engineも作れるし,SQL queryが不適当なときは,batch processingも〇
        • Hadoop上で他のprocessing modelがdeveloped(for performance)
      • various processing modelは,いずれも複数machineからの単一のshared cluster上で,distributed file system上の同じfile軍にaccessして動かせる: important
      • Hadoop eco system
        • HBaseなどのrandom access OLTP db
        • Im palaのようなMPP Styleのanalytic db
        • ↑ どちらもある
        • いずれもHDFSを使う
    • !!3 often faultに備えた設計
      • MapReduce とMPP dbの違い
        • faultのprocessingとmemory and discの使い方
          • MapReduceは,3つのタスクの粒度で再試行
          • → often write to disc
            • for fault tolerance, and because dataset sizeがmemoryより大きい
          • → より大きいjobに対して適切
          • → 低priority and 低costのjobのprocessingに適当 → processingをいつでもpreemptionできるようにする
            • → preemptionがなければ,MapReduceの設計上のjudgeの妥当性低い

10.3 MapReduceを超えて

目的

  • batch processingのMapReduce以外の選択肢を見る

対応

  • !1 中間的なstateの実体化
    • 実体化 ←→ streaming(: unixのpipe)
    • 実体化のproblem(MapReduceのproblem)
      • タスクの待ち
      • mapperは冗長
      • temporary dataのreplicationは無駄
    • !!1 data flow engine
      • MapReduceのproblemに対応
        • e.g. Spark, Tez, Flink
        • workflow全体を1つのjobとして扱う
        • 複数stageのdata flowをexplicitにmodel化: data flow engine
          • 入力をpartitioning → taskをconcurr
          • mapやreduceはなく,operatorを使う
          • operatorの接続のchoicesとmerit
            • sortのように高負荷processingを,必要なところでのみ実行
            • 不要なmap taskなし
            • joinと依存関係の明示
              • → localityのoptimise
            • HDFSへのwriteの回避 → i/O少ない
            • operatorはinputのprepare氏だい実行〇
            • JVMのprocessの再利用〇 → 起動のoverhead少ない
          • map, reduceと同じ処理のcodeは,修正鳴くほかのengineでも使える
    • !!2 fault tolerance
      • MapReduceは中間stateが永続 → 〇
      • Spark, Flink, Texは再計算
        • 追跡必要(e.g. SparkのRDD, Flinkのcheckpoint)
        • 決定的かどうかが重要
          • 非決定的のとき: 下流のoperatorもおとす
          • → 決定的にするための対処必要
      • 再計算より,実体化〇のcase: 中間data極小,演算処理が極めてCPU集中型のとき
    • !!3 実体化についての議論
      • data flow engineは,よりUnixのpipeに似ている
        • especially Flinkはpipeline化された実行が中心の考え
      • sortは中間stateを蓄積必要
      • 最終出力はHDFS上(data flow engineでも)
  • !2 graphとiterativeなprocessing
    • graph全体へのoffline processingやanalyze
    • → recommendation engineやranking systemといったmachinelearningのapplicationで生じる
    • data flow wngは,directed acyclic graph(DAG)内にoperatorを置くが,operator間のdataglowのみgraph化していて,data事態はrelational styleのtaple
    • 図2-6: transitive slosure(推移的閉包)のようなalgorithm
      • → iterativeなstyleで実装
      • Managementで実装はnot effective
    • !!1 Pregelのprocessing model
      • batch processing graphのoptimise: 演算processingのbulk sync parallel (BSP) modelが広がる
        • e.g. Apache Giraph, SparkのGraph X API, FlinkのGelly APIで実装
        • GoogleのPregel論文から有名になる → Pregel model
      • ある頂点がほかの頂点にmessageを送信
        • 頂点が自分のstateをiteration内でmemoryに記憶する
        • → functionは,新しいmessageのみproceedでOK
      • actor modelとの違い 0 頂点のstateと頂点間のmessageにfault-toleranceと永続性あり
    • !!2 fault-tolerance
      • Pregel jobのperformance高い: messageをbatch化して通信待ち時間削減
        • → iteration間でのみ末
      • 透過的なfaultからのrecovery
        • ↑ iterationの終わりに全頂点のstateのcheckpoint processing ← regularly
    • !!3 concurrency
      • Pregelのprogramming model: 1度に1つの頂点のみ扱う
      • graphのalgorithm: 大量マシン間の通信のoverheadあり → distributed graph algorithmのspeed 大きく減少
        • → 単一machine上のalgorithm > distributed batch processing @ performance
      • GraphChiなどのframeworkを使う単一machineでのprocessingが〇
      • Graph algorithmのconcurrencyは研究中
  • !3 高レベルAPIと様々なlanguages
    • programming modelの改善, processing effectivityの改善
      • これらの技術が扱えるproblem領域の拡大に目が向く
    • Hive, Pig, Cascading, Crunchといった高レベル languageやAPIの登場
      • Tezにより移行〇
    • SparkSQL, Flink ← Flume Javaから
    • これらのdataflow APIは,relational styleのbuilding blockで演算処理を表現
      • code少ない + interactive
    • !!1 宣言的なquery languageへの移行
      • relationalなoperatorの指定 → frameworkがjoinのinputの性質を分析
        • → タスクにとっていずれのjoin algorithmが良いかautomatic judge〇
        • e.g. Hive, Spark, Flink
      • ↑→ joinを宣言的に指定 → query optimiserがjudge
      • ほかのSQLの完全な宣言的query modelとの違い
        • 任意のコード実行可能
          • MPP DBとMapReduce系譜のbatch processing systemの違い
        • simpleな操作を宣言的に表現
          • → 必要な列のみread. 実行のベクトル化
          • → CPU cacheを有効活用, function callなし
            • このために,SparkはJVMのbytecodeを生成.ImpalaはLLVMでnotice codeを生成
        • 任意のcode formatの柔軟性〇
    • !!2 various領域への特化
      • e.g. 統計,数値処理のalgorithm for classificationやrecommendation systemといったmachine learningのapplication
        • reuse〇な実装の出現
        • e.g. Mahout, MADlib
      • e.g. 空間algorithm
        • e.g. k近傍鳳(k-nearest neighbors), 近似(approximate) search for genome analyze
      • → algorithmのdistributed executionのために,batch processing engineが使われる領域は広がっている
      • batch processing systemの機能や高レベルの宣言的operatorが増え,MPPdb がprogrammingし易く柔軟になることで,似てきている.
      • どちらも単なるdataを保存し処理するsystemに過ぎない

まとめ

  • batch processing について
    • Unix tools: e.g. awk, grep, sort
    • MapReduceやdataflow engineに哲学伝わる
      • immutableなinput
      • outputは次のinput
      • 1つのことをこなすtoolsのcombination
    • interfaceについて
  • distributed batch processing frameworkで解決する問題
    • partitioning
      • 関連するdataをすべて同じ場所にまとめる
    • fault tolerance
      • 中間stateの扱い.影響
  • MapReduceでのjoinのalgorithmは,MPP DBやdata flow engineの内部でも使われている.
    • sortmerge join
    • broadcast hash join
    • partitionかhash join
  • distributed batch processing engine(framework): 制限あるprogramming model
    • → 副作用minimum
    • → distributed systemのproblemを隠蔽〇
      • → retry安全
      • frameworkにより,fault-tolerance〇
        • 完治不要.強力なtrustnessのsemantics
  • especially important: inputdataを変更しない
    • input dataは有限.既知のサイズ. → 官僚のjudge可能
      • stream processing
        • 非限定stream

Ch11 Stream processing

目的

  • data managementの仕組みとして,event streamを見る
    • incrementalにprocessされるdata

11.1 event streamの転送

目的

  • event: recordを指す
    • 自己完結したimmutableなobject
    • producer(a.c.a. publisher)が1回生成し,複数consumer(subscriber)が扱う
    • file名ではなく,topic, streamとしてgroup化
    • fileかdbがあれば,producerやconsumerとconnect可能
    • pollingではなくpublishが〇
      • これまでのdbにない機能のためのtoolがdeveloped
        • triggerなどは限定的

対応

  • !1 messaging system
    • eventの通知に使う
    • UnixのpipeやTCP connectionにより拡張
      • → ・複数producerが同じtopicにmessage 送信
      • ・複数consumerが同じtopicにmessage 受信 → publish/subscribe model
      • 送信 > 受信のprocessing @speedのcase
        • messaging systemがdrop/queueでのbuffering/ back pressure(flow control)
      • node crashやofflineのcase
        • messaging lost okか,applicationに依存
        • batch processing systemでは,強いtrust〇
        • → streamingでも提供する
    • !!1 producerからconsumerへのdirect messaging
      • latencyの低さがimportantな金融 → UDP + applicationでのrecovery
      • ZeroMQやnano messageなど,brokerなしのmessaging library: TCP/IP multicast上でproducer/consumer messagingを実装
      • StatsDやBrubeck: UDP messaging
      • consumerがnetwork上にservice公開 → producerはHTTPやRPC requestを発行して,messageをpush
        • webhooksのbackground
      • これらのdirect messaging systemは,message lostの可能性を, applicationのcodeが関知する必要ある
        • fault-toleranceは限定的
    • !!2 message broker(a.c.a. message queue)
      • a type of DB
      • Server, producerやconsumerがClient
        • → clientの出入りに耐えられる.永続性の問題も隠蔽〇
        • consumerはasync by queuing
    • !!3 message broker とdbのcompare
      • consumerへの配信官僚 → message(data)をdelete
      • working set 小さい, queue短いという前提
        • → 大量messageのbufferingは全体のthroughput down
      • secondary indexなどではなく,pattern matchのtopic 部分集合を取得
      • dataに変化があれば,clientに通知 ←→ snapshot
      • ここまでは旧来のmessage broker. JMS, AMQPといったstandard
      • e.g. RabbitMQ, ActiveMQ, HornetQ, Qpid, TIBCO Enterprise, IBMMQ, Azure Services Bus, Google Cloud Pub/Sub, Message Service
    • !!4 複数consumer
      • 図11-1: load balancingとfanout: messagingの2つのpattern
      • load balancing
        • どれか1つのconsumerに配信
          • a.c.a. shared subscription
      • fanout
        • 全consumerにdeliver.独立した複数consumer
      • 2 patternの組み合わせも〇
    • !!5 承認と再deliver
      • 承認(acknowledgement) → messageのdelete @ broker
      • 図11-2: order変化 @ load balancing
        • → consumerごとにqueuingが必要なpattern
  • !2 partition化されたlog
    • dbでの複数のあるstorageというapproachと,messagingでの低latencyのnotify機能のcombine
    • → log base message broker
    • !!1 message storageへのlogの利用
      • 高throughput & fault-toleranceのため,logをpartition化
        • topic: 同typeのmessageを扱うpartitionのgroup
          • 図11-3: flow
          • partition内ではmessageに全order
        • e.g. Apache Kafka, Amazon Kinesis Streams, TwitterのDistributedLog
    • !!2 従来のmessagingとlogの比較
      • log baseのapproach → fanout型のmessaging support easy〇
        • load balancingは欠点アリ
      • → message processing負担大きいことあり, message単位でparallel processing, messageのorder not importantなら
        • → JMS/AMQP styleのmessage brokerが望ましい
          • ↑→ message processingのthroughput高い必要がある,1つのmessageは高速, orderがimportantなら,log base applicationが◎
    • !!3 consumerのoffset
      • brokerはacknowledgementの追跡不要: 管理のoverhead少ない
        • → batchやpipelineといった手法を取るchanceが生まれる → throughput高い @ log base system
        • 5.1.2のlog sequence numberと似ている
    • !!4 disc領域の利用
      • 循環buffer, ring bufferingを使う
      • throughputはhistoryの量による
    • !!5 producerにconsumerが追い付かないcase
      • consumerのdelayが大きくなったら警告
      • 各consumerは独立
    • !!6 古いmessageのreplay
      • AMQPやJMS styleのmessage brokerは破壊的
      • ↑→ log baseのmessage brokerはread only
        • → 繰り返し可能
          • → maintenance〇. 組織内のdata flowとの組み合わせのためのtoolとして log baseのmessagingは〇

11.2 dbとstream

目的

  • DBとstreamのつながりはdisc上のlogのphysical storageをこえて,本質的なもの
    • e.g. replication log
      • e.g. state machine replication(9.3.3)
    • heterogeneousなdata systemのproblemを,streamの着想でresolveする

対応

  • !1 systemのsyncの保持
    • 複雑なapplicationの要求は,異なる技術の組み合わせで解決
      • それぞれの目的にoptimiseした形式で各々がcopyをもつ
        • → syncが必要
          • e.g. ETL process @DWH(3.2.1): batch processing
      • dual writesの重大なproblem ← dual writesは,dumpが低速なcaseの代替案
        • 図11-4: race condition
          • version vector(5.4.4)などが必要
        • fault-toleranceのproblem
          • 2 system間不整合
  • !2 変更dataのcapture(Change Data Capture, CDC)
    • 図11-5: flow. 変更のstreamをproducerとconsumerで扱う
      • producerは記録するsystemのdb, consumerはsearch indexやDWH
    • !!1 CDCのimplement
      • logのconsumerは導出data system
      • ↑ CDCはconsumerが正確なcopyとなることを保証
      • dbのtriggerが使える
        • ただし,triggerは壊れやすく,performanceでの大きなoverhead
      • implementのe.g. → p.498
      • CDCはasync
    • !!2 初期のsnapshot
      • dbのsnapshotと変更ログの対応必要
    • !!3 logのcompaction
      • snapshotの代替
      • log baseのmessage brokerやCDCでも〇
      • e.g. Apache Kafka
      • message brokerを一過的messagingのみならず,永続性あるstorageとしても使える
    • !!4 change streamのためのAPI support
      • change stream: first classのinterfaceとしてDBでsupport
        • e.g. RethinkDB, Firebase, CouchDB, Meteor, VoltDB, Kafka Connect
  • !3 event sourcing
    • event sourcingとCDCの違い
      • (event streamingはDDDのcommunityでdeveloped)
      • event sourcingでは,event storeには追記のみ
      • ↑→ CDCはapplicationのdbをmutableに使う
      • eventは低レベルの変化でなく,application levelで起きたことを反映
      • event sourcingは, applicationの進化に〇. bugからguard
      • event sourcingはchronicle data modelとsimilar. star schemaのevent logとfact tableにも掃除
      • event sourcingのstreaming systemとの関連を見る
    • !!1 event logからのnow のstateの導出
      • 決定的なlogでlog → state
        • logのstoreのproblem
    • !!2 commandとevent
      • commandがvalidated → event
        • event: fact. logのimmutableな一部
          • → commandのvalidationはsync 必要
            • serializableなtransactionの利用
            • or, eventの分割
  • !4 state, stream, immutability
    • immutabilityの原則: event sourcingやCDCの強さ
    • dbはapplicationの現在のstateをstore
      • readにoptimise
      • stateの変化とimmutabilityとの折り合い
      • stateの変化: eventのresult
      • mutableなstateとimmutableなeventからなる追記飲みのchange log
        • log が矛盾しないことがimportant
        • → change log: stateの進化の表現
      • 図11-6: applicationのstateとevent streamのrelation
    • log: fact
    • db: logのcache
    • !!1 immutableなeventのmerit
      • 監査制,problemのrecovery,分析
    • !!2 event log からの複数viewの導出
      • mutableなstateをimmutableなevent log からisolation
      • event logからdbへのexplicitなconvert step
        • → 時間とともにapplicationの進化〇.新旧共存
      • dataのwrite formatとread formatのisolation → 大きな柔軟性
        • ⇔ CQRS(Command Query Responsibility Segregation
        • → 正規化,非正規化はほぼ無意味
        • ↑ convert processがreadにoptimiseされたviewとevent logと整合性を保てば,viewでdataを非正規化〇
    • !!3 concurrency control
      • event sourcingとCDCのasyncの欠点
      • → 5.2.1(p.173)で解決
      • or → stateをevent logから生成
        • event sourcingでは,user actionの自己完結した記述: event
        • 同じpartitionなら,single threadで処理〇
    • !!4 immutabilityのbound
      • Datomicのexcision(切除)や,Fossilのshunning(回避)が必要なcaseあり.

11.3 streamのprocessing

目的

  • streamをprocessして,new導出streamをgenerate
    • operator, job
    • streamは終わりなし
      • → sort merge join×.fault toleranceの仕組み別に必要. ← crash時に初めからは×

対応

  • !1 stream processingの利用.
    • stream processing は,monitorのために使われてきた
      • alertのnotify
    • 洗練されたpattern matchingとの関連付け必要
    • ほかの使い方の出現
    • !!1 複合event processing(Complex Event Processing, CEP)
      • event streamのanalyzeが目的
        • 特定のevent patternの検出がneeded
        • stream中の特定のpatternのeventをsearchするrule
        • CEを出力
        • queryは長期保存される ←→ normal db processingはdataが長期保存
        • e.g. Esper, IBM InfoSphere Streams, Apama, TIBCO Stream Base, SQL Stream
    • !!2 stream analyze
      • 大量eventの集計や統計
      • 集計のtarget: windowとcall
      • 確率的algorithmの使用
        • cost少ない
      • e.g. Apache Storm, Spark Streaming, Flink, Concord, Samza, Kafka Streams: OpenSourceのdistributed stream processing frameworkの多くは,analyzeのための設計
        • hosted service: Google Cloud Dataflow, Azure Stream Analytics
    • !!3 materialized viewの管理
      • applicationのstateもmaterialized viewの1つ
        • ただし,全event必要.log compactionも必要
    • !!4 streamでのsearch
      • streamのsearch: queryをstore → CEPのようにdocumentがqueryを通る
      • queryのindexづけ
    • !!5 message passingとRPC
      • RPC的systemとstream processing間は重なる領域もあるが,そもそもは異なる
  • !2 timeに対する考察
    • localのsystem clockでwindowを決定
      • simple
      • but, eventのgenerationとprocessingの間が小さいときに限る
    • !!1 event timeとprocessing time
      • 図11-7: processing timeでwondow processしたときのproblem
    • !!2 preparedのcheck
      • はぐれ(straggler) event のproblem
        • 虫 or correction
    • !!3 結局,どのclock?
      • 3つのtimestampをlogging
      • eventが実際に起きたtimeの推定必要
    • !!4 windowのtype
      • Tumbling window
        • 固定長,全eventがいずれか1つのwindowにのみbelong
      • Hopping window
        • smoothingのためにwindow同士が重なる
      • sliding window
        • ある期間が動く.長さのみ決まっている
      • session window
        • 期間非固定
        • 時間的近さ
        • web siteのanalyzeに使う
  • !3 stream のjoin
    • stream processing: data pipelineを限度ないdatasetのincrementalなprocessingに一般化したもの
      • → joinが同じく必要
    • !!1 stream-stream join(window join)
      • stream processorがstateを管理する必要
    • !!2 stream-table join(streamのenrich)
      • stream processorがもつdbのlocal copyの最新化が必要
        • → CDCでresolve〇
      • stream-stream joinとの違い: stream-table joinでは,tableのchange log streamに対して,新versionのrecordで旧recordをoverwrite. with 「時間の始まり」までのwindow
    • !!3 table-table join(materialized viewのmaintenance)
      • cacheの使用が例
    • !!4 joinのtimeに対する依存
      • いずれのjoinもstream processorがjoinへのinputの1つに基づくstateを管理
      • → stateを管理するeventのorderがimportant
      • Slownly Changing Dimension(SCD)のproblem
        • → joinするrecordのversionごとにidを使う
          • joinはdecisive, but logのcompaction不可能
  • !4 fault-tolerance
    • exactly-once semantics(事実上effectively-onceがより正しい) @batch job
      • streamはより複雑な対処必要
    • !!1 micro batch processingとcheckponit processing
      • e.g. Spark Streaming, Apache Flink
        • 出力がstream processorを離れてからの失敗には対応×
    • !!2 atomicなcommit再び
      • e.g. Google Cloud Dataflow, VoltDB, Apache Kafka
        • stream processingのframework内で,stateの変更とmessagingをともに管理
          • → heterogeneousなtechnologyにわたるtransactionを内部にとどめる
    • !!3 冪等性(idempotence)
      • e.g. Kafka, StormのTrident
      • いくつかの前提必要
      • わずかなoverheadでexactly-once semanticsをrealized〇
    • !!4 fault後のstateのrebuild
      • stateをstream processorのlocalにstore, and regularly replication
      • e.g. FlumeJava, Samza, Kafka Streams, VoltDB
      • infraのperformance特性に依存

まとめ

  • event streamについての目的とprocessing方法
    • unboarder streamをprocessing ←→ batch processing
    • message brokerとevent logの使用
    • AMQP/JMS styleのmessage broker
    • log baseのmessage broker
  • Streamとしての表現〇のe.g.
    • change log, CDC, event sourcing, log compaction
  • dbをstreamとして表現
    • index, cache, analysis systemのような導出data system
  • streamとしてstateをmanagement, messageをreplayする機能
    • stream のjoinやvarious stream processingのframeworkのfault-tolerance実現のための手法の基礎
    • stream processingの目的
      • event pathのsearch(CEP), Window集計の演算(Stream analysis), materialized view
  • stream processorのtimeの扱い
  • stream processingでのjoin
    • stream-stream join
    • stream-table join
    • table-table join
  • stream processorでのfault-toleranceとexactly-once semanticsの実現

Ch12 data systemの将来

目的

  • Ch11まで: 現在の姿.Ch12: あるべき姿
  • 本書の目標: trusted, scalable, maintainableなapplicationやsystemの構築方法を見る
    • Ch12の目標: 頑健性,正確性,進化性,人類への貢献において,よりよいapplicationを設計する方法の発見

12.1 data のintegration

目的

  • software productsと,適した環境の対応付けを見出す
  • 複数softwareのcombine

対応

  • !1 dataの導出による特化したtooldのcombination
    • data joinの必要性は,組織全体のdata flowを考える必要あり
    • !!1 data flowについての考慮
      • 入出力の明示
      • 全てのwriteのorderを決定する単一system
        • 全order決定の原理がより重要.than which CDC or event sourcing log
      • 導出data systemをevent logにもとづいてupdate: 決定的で冪等〇
        • faultからのrecovery容易
    • !!2 導出dataとdistributed transaction
      • various data system間で一貫性を保つための古典的approach: distributed transaction
      • distributed transactionと導出data systemのcost comparing
        • lockかlogか
        • atomic commit or 決定的retryと冪等性
        • transaction: linearizabilityを提供 ←→ 導出data system: timingの保証なし
        • ただし,transactionのコスト大きい
          • XAのfault-toleranceとperformance特性は貧弱
            • → distributed transactionの有用性は限定的
      • various data systemのjoinは,導出data system(log based)が〇
    • !!3 全orderのboarder
      • 小さなsystemのみ,全orderのevent log 〇
      • 全order broadcast(consentと等価)は,orderingを単一のcodeで行う
      • 複数nodesでのconsent algorithmのdesignは未解決
    • !!4 因果律の把握のためのeventのordering
      • simpleなanswerなし
        • logical timestamp
        • systemのstateをlogにwrite
        • conflict resolveのalgorithm
  • !2 batch processingとstream processing
    • data joinの目標: dataを適切なところに適切なformatでおく
      • これを達成のためのtool: batch/stream processor
        • extract datasetを出力
    • Sparkはstreamをmicrobatchに分割して,batch processing engine上でstream processing
    • Apache Flinkは,batch processingをstream processing engine上でexecution
      • → 違いがぼやけてきている
    • !!1 extracted stateの管理
      • batch processing: function型programmingと同じにおい
      • stream processingは,operatorがfault-tolerantな管理されたstateを扱う
      • I/Oがdefinedな決定的functionの原則
        • fault-tolerant〇
        • 組織内のdata flowの考慮をsimplize〇
      • search index, statistics model, cacheなど,extracted data systemを考えるときに考えること
        • dataset extractionのpipeline, function型application codeを使ったsystemからのstateの変更のpush, extract systemへの変更の適用
      • asyncな管理 → fault-tolerance〇,trusted, scalable
    • !!2 applicationの進化に伴うdataのreprocessing
      • reprocessing: datasetを全く異なるmodelにrebuild〇,新しい要求への対応〇
      • 比喩: dual gage
      • 段階的進化〇 → systemの改善speed up
    • !!3 lambda archtecture
      • batch processingとstream processingのcombine
      • 核の着想: input data はevent sourcingのようにimmutableなeventを常に成長し続けるdatasystemに追加することで記録すべき
      • Hadoop MapReduceのようなbatch processing systemと,Stormのようなstream processing systemという2つの異なるシステムをconcurr〇
        • eventからは,readにoptimiseされたviewをextract
      • batch,とstreamのいいとこどり,but 現実的なproblemあり
        • batch/stream processingともに,logicのmaintenance必要
        • stream pipelineとbatch pipelineの各出力のマージ難しい
        • batch layerが複雑化
    • !!4 batch processingとstream processingの統合
      • batch 演算とstream演算を同じsystem上で実装〇
        • → lambda archtectureの欠点解消〇
      • 統合のために必要な機能
        • eventのreplay
        • stream processorのexactly-once semantics
        • eventの発生時刻でwindow processingを行うtool

12.2 databaseをときほぐす

目的

  • db Hadoop OSはいずれもinfo management system
  • Unix: especially 低レベルなhardwareのabstraction
  • ≠ relational db: disc上のdata structure, concurrency, crashからのrecoveryなどの複雑さを隠蔽する,高レベルのabstraction
    • 両者の良い部分をcombineする: 目標

対応

  • !1 data storage technologyのcombination
    • dbの機能,動作
      • secondary index, materialized viwe, replication log, 全文検索index
    • !!1 indexのgeneration
      • 既存のdataに対する新しいviewとしてindexをextract
    • !!2 すべてにかんするmeta db
      • 組織全体にわたるdata flow: 1つの巨大なdb
        • batch stream, ETL のprocess
      • federated db: readのintegration(a.c.a. polystore)
        • 統一されたquery interfaceの提供
        • e.g. PostgreSQLのforeign data wrapper
      • unbundled db: writeの結合
        • 機能の解体(unbundle)
    • !!3 processingのunbundle
      • 複数system間のwriteの動機は要考慮.technology的にdifficult
      • 冪等なwriteのasync event log >>> distributed transaction
        • はるかに頑健で実践的
        • transaction protocolがnot standarizedで統合とても難しい
      • log baseの結合: 疎結合なcomponentsにできる〇
        • @system level, @human level共に
    • !!4 unbundled systemとjoined system
      • 解体と合成が必要なのは,すべてのrequireを満たす単一のsoftwareがないときのみ
    • !!5 欠けているものは何か?
      • Unixのshellのようなものがない
      • update cacheの事前calculation
        • differential data flowが研究中
  • !2 data flow 中心のapplication design
    • database insideout approachというdesign patternの中身
      • O2やJuttleなどのdata flow language
      • FRP(Elmなど)
      • BloomのようなLogical Programming Language
      • Unbundlingは,Jey Krepsが提唱
    • !!1 extract functionとしてのapplication code
      • custom codeは多くのdbで苦労を伴う
    • !!2 application codeとstateのisolation
      • dbはapplication developmentのrequireを満たさない
      • systemの一部として永続性あるdata storageに特化した部分を持ち,ほかはapplication codeの実行に特化が〇
      • web applicationは,stateをもたないserviceとしてdeploy
        • → stateはdb
        • → stateのないapplication logicをdb(state management)からisolation
        • applicationからはsubscribeがdifficult. (e.g. observer pattern)
        • dbでもpolling必要
    • !!3 data flow: stateの変化とapplicationのcodeとの相互作用
      • 1980's のtaple 空間 model: stateの変化の監視と藩王のprocess
      • dbのunbundle
        • e.g. cache, 全文検索index, machinelearning, analysis system
      • extracted dataの管理は,async jobのexecutionとはdifferent
        • stateの変更のorderがimportant
        • fault-toleranceがimportant
        • → stream processorで実現可能
          • applicationのcodeはstreamのoperatorとして動く
      • stream processorを,data flow周りに大規模systemをつくるために合成〇 ←→ dbでは不可能. about 任意のcode execution
    • !!4 stream processorとservice
      • application development style: serviceの集合に機能を分割
      • streamのoperatorを合成は,同じ特徴あり〇
        • ただし,layerのcommunicationの仕組みは大きく異なる: 1方向のasync message stream
      • fault-tolerance + performance 高い〇
        • RPCの代わりに,stream joinが◎
          • ただし,いずれにせよ時間への依存性の対応が必要
  • !3 extracted stateの監視
    • write path: extracted datasetを最新のstateに保つprocess
      • e.g. 図12-1 ← 先行evaluation
      • 後にread pathがくる ← 遅延evaluation
      • extracted dataset: write/read pathの接点
    • !!1 materialized viewとcache
      • 全文検索indexのe.g.
        • 頻出queryの有限集合にのみ,事前calculation: cache, materialized view
        • → cache, materialized, indexは,extracted datasetの位置(path間のboarder)をずらしている
    • !!2 statefulでoffline動作できるclient
      • clientがstateを持つapplicationの出現
        • offline firstのapplication
          • device上のstate: server上のstateのcache
    • !!3 clientへのstateの変化のpush
      • server送信event(Event Source API)やWebSocketsが,Web browserがserverへのTCP connectionをopenに保つcommunication channelを提供
        • write pathをend userにまで広げる
        • log based message brokerが,offlineに対応
    • !!4 e2eのevent stream
      • stateを持つclientやUIをdevelopするためのtools
        • e.g. Elm Language, FacebookのReact toold, Reduxなど
        • 内部的なclientのstateをmanagement, with event stream の subscribe
      • instant messagingやonline gameなどで,このような「realtime」archtectureを使っているが,ほかのapplicationにも使える
      • → request/responceのinteractionではなく,data flowのpublish/subscribeに移行必要
        • → 反応性の良いUIとoffline supportの向上〇
    • !!5 readもevent
      • requestのprocessingと,joinは本質的に似ている
      • userのactionまでのreadのrebuild可能〇
        • → 因果関係の追跡〇
          • but, storageとI/O cost増
    • !!6 複数 partitionにわたるdataのprocessing
      • readのevent化は,複雑なqueryのdistributed executionの可能性になる
        • e.g. Stormのdistributed RPC機能
          • e.g. twitterであるURLを見た人数の計算,不正detection
      • MPP dbでのinner query execution graphも似た特徴あり
      • queryをstreamとして扱う: 大規模applicationの実装の選択肢の1つ

12.3 正確性を求めて

目的

  • trustedで正確なapplication構築
    • consistencyのdefineは不明瞭
    • transactionは最後の手段ではない
    • applicationのcodeがdbの機能を正しく使う必要あり
      • weak isolation levelやquorumなど,間違い起き易い

対応

  • !1 dbのe2e論
    • applicationのbugのcase
      • → immutableが〇
    • !!1 exactly-once
      • 冪等〇
        • with metadata, fencing
    • !!2 duplicationの抑制
      • 2PCはnot enough
    • !!3 操作id
      • networkのcommunicationを複数hop 経由する操作を冪等にする
        • ↑requestのe2eのflowを考える必要
      • not serializableなisolation levelでは,unique(→ 7.2.4, p.266)性checkに難あり
      • event logとしてのrequest table → 例12-2
    • !!4 e2e論
      • duplicationの抑制は,communication system自体の機能では不可能
        • → transaction IDが,end userのclientからdbまで渡される必要
      • e2eはnetworkでのdataの整合性にも必要
        • encryption
      • 低レベルの機能の上に成り立つ
    • !!5 data systemへのe2eのapply
      • 高levelのabstractionにenoughな方法まだない
        • transactionもnot enough
  • !2 制約の強制
    • unique性などの制約を守らせる
    • !!1 unique 制約にはconsent必要
      • unique必要なvalueをpartitionに分ける
      • async のmulti master replicationは例外
    • !!2 log baseのmessagingでのuniqueness
      • log: total order broadcast = consentと等価
        • partition数を増でscale〇
        • いずれの制約にもsequencialにprocess可能
      • basic 原則: conflictable writeは同じpartitionに送られ,sequencialにproceedされる
      • conflictのdefineはapplicationに依存しうるが,stream processorは任意のlogicを利用可能
    • !!3 multi partitionのrequest processing
      • partitioningされたlogを使い,atomicなcommitなしで同等のaccuracy〇
      • 単一objectへのwriteは,ほぼすべてのdata systemでatomic
        • → 複数partitionにまたがるatomic commit不要
      • 「複数partitionにわたるtransactionを,partitioningの方法が異なる2stageに分割し,e2eのrequest idを用いる」ことで,faultがあっても,atomicなcommit protocolを用いずに同じaccuracy達成〇 → p.563, 12.2.3.6と似る
  • !3 timeliness(適時性), integrity(整合性)
    • transactionのよい性質: linearizable
    • 複数stageのstream processorではasyncだが,出力streamのmessageをclientがwait 可能
    • → syncの通知 ← 待機の目的
    • consistency(一貫性)の2つの要求
      • timeliness
        • userが,systemの最新のstateの観察を保証
          • CAP定理: 強制約,read-after-write: 弱制約
    • integrity
      • dataに矛盾や間違いがないこと
        • especially 正しいextract data
      • 明示的なcheckとrepair必要
      • ACID transactionでは,consistencyはある種のapplication固有のintegrityの表現
        • atomicityとeternityが整合性を保持するための重要なtools
    • timelinessの違反: 結果整合性
    • integrityの違反: 恒久的なnot consistency
    • importance: integrity >>>> timeliness
    • !!1 data flow systemのaccuracy
      • ACID transactionはtimeline(linearizability)とintegrity(atomicなcommit)を共に保証
      • event baseのdata flow systemは,timelinessとintegrityをisolate
        • streaming systemの中核はintegrity
        • exactly-onceは,integrityのための仕組み
          • atomic commit不要
        • integrityのための複数仕組みのcombination
          • writeを単一のmessageで表す
          • 決定的なextract function(SPのようなもの)
          • clientがgenerateしたrequest idを全levelで渡す
            • → e2eのduplication抑制・冪等性
          • messageをimmutableにし,extracted dataをあとからreprocessing可能
            • → recovery easy
    • !!2 制約のゆるやかな解釈
      • unique制約の強制: consistency必要
      • より弱いuniquenessでenoughなcase
        • compensating(補正) transaction
        • linearizability不要なcase
      • 謝罪のコストはbusiness上のjudge
        • 許容, → 弱い制約
        • → integrityは必要,but timelinessは不要
    • !!3 調整を回避するsystem(coordination-avoidance system)
      • 2つの所見
        • data flow system: extracted data でのintegrityの管理をatomicなcommit, linearizability, partition間syncなしに達成〇
        • 弱制約でも,integrityが〇ならok
        • → coordination不要
          • → 高performance, fault-tolerance〇
            • e.g. multi leader構成で複数datacenterにまたがり,region間でのsync replication可能
        • serializable transactionは一部の使用で有益
  • !4 信頼しつつ検証も
    • system modelでの仮定
    • 現実における確率的problem
      • e.g. rowhammer
    • !!1 softwareのbugがあってもintegrityを保つ
    • !!2 約束を盲信は×
      • auditing(監査): dataのintegrity check必要
      • 速いうちの検出が〇
    • !!3 検証の文化
      • systemの自己検証・自己監査必要
      • 監査性のdesign必要
      • ↑weak consistencyが普通になった
    • !!4 監査性のためのdesign
      • transactionは, transactionの意味・理由が不明
      • ↑→ event based system: よりよい監査性
        • userのinputは単一のimmutable event
          • → stateの更新はeventからextracted
            • extractは決定的で再現可能
        • data flowの明確化 → dataの系統(provenance)も明確化
          • → integrityのcheckはるかにeasy
            • event logはhashでevent storageのcheck〇
            • extracted stateは,batchやstream processorのreprocessingでevent logからstate extract〇
      • → data flowがdecisiveで十分にdefined
        • → systemの行いの理由のためのdebugやtraceがeasy
        • bug検出時の環境再現も〇
    • !!5 e2e論再び
      • dataのintegrity checkはregularに必要
        • e2eでのcheckが〇 → 内部もimplicitにcheck〇
          • systemの変更や新storage technologyのrisk減
            • → applicationの進化〇
    • !!6 監査可能なdata systemのためのtools
      • encryptionのtoolsで,hardware, softwareのproblemやcrackingへのtoleranceをもつようにsystemのintegrityを証明する方法あり
        • e.g. Bitcoin, Ethereum, Ripple, Stellerのような暗号通貨, block chain, distributed台帳のtechnology
        • ただし,Byzantine fault体制は△(or ×)
          • proof of workの手法(e.g. bitcoinのmining)はespecially especially 無駄
          • bitcoinのthroughputはむしろ低い
        • このtechnologyはたいていMerkle treesに依存
          • hash tree
          • certificate(証明) transparencyのsecurity technologyにも,TLS/SSL certificate(証明書)の正当性checkに使われている
      • integrityのcheckや監査のalgorithmを使うsystemが,scalableでperformanceのpenalty少となるように研究必要

12.4 正しいことを行う

目的

  • すべてのsystemはある目的のために構築される
    • → 目的をこえた影響もあり.これにも責任必要
      • dataを,人間性とrespectをもって扱う
      • 今日は,倫理的選択が一層含まれる

対応

  • !1 予測分析(predictive analytics)
    • !!1 biasと差別
      • algorithmのinputのbiasに気づけない
    • !!2 責任と説明責任
      • dataに基づく意思決定の間違いを正す方法必要
    • !!3 feedbackloop
      • system thinkingでriskyなfeedbackloopを避ける
  • !2 privacyと追跡
    • !!1 監視
      • IoTのsecurity risk
    • !!2 承諾と選択の自由
      • 非対称で一方的な関係
    • !!3 privacyとdataの利用
      • privacy: 判断のright
        • → 個人の自由と自律性
      • 適当さは人間の判断
    • !!4 資産や権力としてのデータ
      • dataはrisky なしさん
    • !!5 産業革命を忘れない
      • dataは公害問題
    • !!6 法律と自己規制
      • dataの破棄必要
      • cypher protocolを通じてaccess control
      • 個人のdataにかんする文化的変化必要

まとめ

  • applicationは目標を満たすため,複数のvarious softwareをcombine必要
    • このdata integrationのproblemを,batch processingとevent streamingで解決
    • index, materialized view, machinelearningのmodel, 統計summaryなどを管理〇
    • asyncで疎結合
      • → 頑健,fault-tolerant〇
      • → applicationの進化〇
    • ↑ dbをcomponentsにunbundle. → dataflow applicationを構築
    • offlineでも動くinterface
    • e2eの操作ID → 冪等
    • asyncなevent processing
      • 制約をasyncにcheck → 強いintegrityの保証を実装
    • 多くのbusiness processにadapt
      • 制約の対応(e.g. compensation)
  • applicationをdataflowを中心において構成し,制約をasyncにcheck
    • → ほとんどの調整回避〇
    • → 地理的にdistributedなenvironmentで,faultを考えながらも,integrityを保ち,高performanceでsystemが動く
    • 監査でdata integrity check
  • data指向applicationの倫理的問題

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

Part 2 distributed data

目的

  • Part 1: 単一のマシンにデータを保存.
  • Part 2: 複数マシンにデータを保存.
  • 複数マシン保存の目的
    • scalability: 負荷分散
    • 耐障害性,高可用性
    • latency
  • !1 高負荷へのscaling
    • simple: scale up(vertical)
      • 共有memory archtecture
        • problem: cost upが性能upに対して比例以上.
      • 共有disc archtecture
        • problem: 競合.ロックのoverheadでscalabilityに制限
    • !!1 shared nothing archtecture(a.c.a. horizontal scaling, scaleout)
      • 利用広がる
      • node ← 独立
      • bestな費用対効果のマシンを自由に選択
      • 地域分散 → latency down, 高可用
      • 小企業でも可能
      • 制約やトレードオフの認識必要
      • merit多いが,applicationが複雑化
      • → data modelの表現力に制約生じる
    • !!2 replicationとpartitioning
      • replication: 冗長性,performance良化
      • partitioning(a.c.a. sharding)
      • 図Ⅱ-1: e.g.

Ch05 replication

目的

  • 目的
    • 地理的近さ → latency down
    • 高可用性
    • read queryを処理するmachineをscale out → throughputを高める
  • dataへの変更の扱いが重要
    • single leader, multi leader, leaderless
    • tradeoff
      • sync, async
      • 障害中のreplicaの扱い
    • 結果整合性について
      • read-your-write, monotonic reads

5.1 leader, follower

目的

  • 図5-1 leader base(a.c.a. active-passive, master-slave) replication
    • replication log, or 変更streamの一部としてleaderがfollowerに送信
    • e.g.
      • PostgreSQL, MySQL, Oracle Data Guard, SQL Server AlwaysOn可用性groupなどのrelational db
      • MongoDB, RethinkDB, Espressoなど非relational db
      • KafkaやRabbitMQ高可用性queueなどのdistributed message brokerもこのarchtectureを利用
      • DRDBなどnetwork filesystemやreplicationを行うblock deviceにも同様のものある

対応

  • !1 sync/asyncのreplication
    • 図5-2: sync/asyncのfollower各1つ
    • 通常は1つのみsync, 他はasync
    • semi-synchronous
    • 完全asyncも多い
    • sync型の変種: chain replication @ Azure Storage
  • !2 新しいfollowerのset up
    • snapshot
      • snapshotのreplication log上の位置: log sequence no.(@PostgreSQL), binlog coordinates(@MySQL)
      • → catchup
  • !3 nodeのfaultへの対処
    • !!1 followerの障害: catchup recovery
    • !!2 leaderの障害: fail over
      • ①leaderのfault check
        • timeout
      • ②新leaderの選出
      • ③新leaderを使うためのsystemのreconfigulation
      • fail overのproblem
        • Clientからの永続性の期待
        • ほかのstorage systemとのdbの内容の連携による問題(e.g. GitHub)
        • split brain
        • timeout値の設定難しい
      • nodeのfault, 低信頼のnetwork replicaの一貫性についてのトレードオフ,永続性,可用性,latencyといったproblem
  • !4 replication logの実装
    • !!1 statement baseのreplica
      • problem多い,compact〇
      • e.g. MySQL, VoltDB
    • !!2 Write-Ahead Log(WAL)の転送
      • e.g. PostgreSQL, Oracle
      • 欠点: logはとても低レベル → storage engineとの結合強い
      • → version mismatchがよくない → upgradeにdowntime必要
    • !!3 login(行base) log replication
      • logic log ←→(独立) storage engineの(physical) log
      • e.g. MySQLのbinlog
      • 互換性〇.外部applicationのparse〇 → DWHや,custom indexやcacheの構築に〇
      • → 変更データのキャプチャ → Ch11
    • !!4 trigger base replication
      • triggerやStored Procedureの利用.またはOracle GoldenGateのようにlogをread
      • → より柔軟なreplication
      • e.g. OracleのDatabusや,PostgresのBucardo
      • overhead大,bug起きやすい,組込のreplicationより制約大きい

5.2 replication lagにまつわるproblem

目的

  • 読み取りscaling archtecture
    • async replicationのみ
  • 「eventual consistency(結果整合性)」と非一貫性のproblem

対応

  • !1 自分が書いた内容のread
    • 図5-3: read-after-writeの必要性(a.c.a. read-your-write)
    • 多くの方法
      • userが変更しうるものはleaderから,他はfollowerから
      • 更新時刻の追跡.@user, replica
      • logicalなtimestampもreal system clockも使える
    • cross-device read-after-write 一貫性
      • metadataの集中配置
      • routing
  • !2 monotonicなread
    • 図5-4: より過去の情報の取得
    • eventual consistencyよりは強い一貫性を保証
    • 各userが各々同じreplicaからread
  • !3 一貫性のあるprefix read
    • 図5-5: e.g.
  • !4 replication logへの対処
    • dbがreplicationのproblemに対処 → transactionの意義.→ 強い保証を提供

5.3 multi leader replication

目的

  • multi leader(a.c.ca. master-master, active-active replication)
    • leader base replicationの自然な拡張

対応

  • !1 multi leader replicationのUseCase
    • !!1 multi datacenterでの運用
      • 各datacenterにleaderを置く
      • 図5-6: archtecture
      • multi datacenterでのdeployのcompare
        • performance: multi datacenterの方が〇
        • 耐障害性: 各datacenterは独立
        • networkのproblemへの耐性: asyncのmulti leader(syncのsimple leader) → 耐性〇
      • e.g. MySQL, Postgres, Oracleの外部tool
      • 大きな欠点
        • Conflict resolution
        • → 可能背あれば避けるべき危険領域
    • !!2 offlineで運用されるClient
      • 各deviceがleaderとしてactするlocal dbを持つ
      • → 全device上でasyncのmulti leader replication processingあり
      • 実装が困難
      • CouchDBは,このような運用に応じたdesign
    • !!3 collaborativeなedit
      • !!2のoffline editと多くの点で共通
  • !2 writeのconflictのprocessing
    • 図5-7: e.g.
    • !!1 syncのconflict detectとasyncのconflict detect
    • !!2 conflictの回避
      • あるrecordへのwriteは同じleader
      • 多くのケースで推奨
    • !!3 一貫したstateへの収束(convergent)
      • 各writeにunique ID → Last Write Wins(LWW)
      • → 損失リスク大の手法
      • replicaにunique ID →↑
      • 値のマージ
        • 全ての情報をstoreするdata struct → conflictを記録
        • → application codeで解決. ← userに確認要求
    • !!4 customのconflict resolution logic
      • onwrite: e.g. BucardoでPerlを使う
      • onread: e.g. CouchDB
      • transaction全体ではなく,行やdocument単位でresolveする
      • 〇auto conflict resolve → 将来性〇
        • problemのe.g. : Amazon
        • 〇Conflict-free replicated datatypes: CRDTs ← 2way merge
        • 〇Mergeable persistent(永続) data structures
          • e.g. Git ← 3way merge
        • 〇Operational transformation
    • !!5 Whats's Conflict?
      • → Ch07, Ch12
  • !3 multi leader replicationのtopology
    • 図5-8: 構成のe.g.
      • most general: all to all → 耐障害性で他より〇
      • 循環topology: e.g. MySQL
      • star topologyも広く使用
    • all to allのproblem
    • 多くのmulti leader replicationのconflict detect手法の実装は貧弱.
    • → dbで徹底的にテスト必要.

5.4 leaderless replication

目的

  • AmazonDynamoで利用してから流行
  • OSSのdata store: Riak, Cassandra, Voldemort
  • Dynamo Style
  • → dbの利用方法に大きな違い

対応

  • !1 when a node is down, write to db
    • 図5-10
    • read requestも複数nodeに送る
    • !!1 read repairと反entropy
      • read repair: readがoftenなとき〇.ただし耐久性低い.
      • Anti-entropy処理.
        • background processing.遅延あり・
    • !!2 writeのためのQuorum
      • w + r > n を満たすwrite, read → Quorum read(or write)
      • ingeneral: nはodd, w=r=(n+1)/2
      • 図5-11: e.g.
  • !2 Quorumの一貫性の限界
    • w + r <= n → 低latency, 可用性up
    • w + r > nでもoldなvalueが返るケース
    • → 絶対的な保証ではない.結果整合性〇
    • → transactionや合意が必要
    • !!1 delayのmonitoring
      • replicaのhealthnessについてのalert要
      • leaderlessでは難しいmonitoring
      • 結果整合性の「結果」の数値化が重要
  • !3 sloppy quorum, hintつきhandoff
    • leaderless replication: 高可用性と低latencyがdesire
    • sloppy quorum: writeの可用性upに重要
      • optionとなる
    • !!1 multi datacenterでの運用
      • leaderless replicationも〇
        • e.g. Cassandra, Voldemort
  • !4 並行writeのdetect
    • 図5-12: case e.g.
    • !!1 LWW
      • Cassandra, Riakのoption
      • 耐久性のコスト
      • data lossが×なら不十分
      • keyがimmutableなときのみ安全
    • !!2 happens-before relationと並行性
      • happens-before(因果関係あり) ←→ 並行
      • 2者間不関知 → 並行
    • !!3 happens-before relationの補足
      • version no.の使用
    • !!4 並行で書き込まれた値のマージ
      • 並行の値: sibling
      • tombstone for delete
      • siblingのmergeは複雑
      • → 自動でmergeできるdata structureがdeveloped
        • e.g. RiakのCRDT
    • !!5 version vector
      • replicaごとのversion no.
        • e.g. Riak 2.0のdotつきversion vectorized
        • Riakでは,version vectorをcausal(因果) contextというstringでencode
      • vector clockとは微妙に異なる.

まとめ

  • replicationの目的
    • 高可用性
    • 切断stateでのmanupulation
    • latency
    • scalability
  • 難しい問題多い
  • replicationの3つのapproach
    • single leader replication
    • multi leader replication
    • leaderless replication
  • replication logへの対応
    • read-after-write一貫性
    • monotonicなread
    • 一貫性あるprefix read
  • multi leaderやleaderlessでの並行性のproblem

Ch06 Partitioning

目的

  • 非常に大規模なdatasetやqueryのthroughputがとても高い
    • → Partitioning(a.c.a. Sharding)
    • partitionの別名
      • Shard: MongoDB, Elasticsearch, Solr Cloud
      • resion: HBase
      • tablet: Bigtable
      • vnode: Cassandra, Riak
      • vBucket: Couchbase
  • 目的: scalability

6.1 Partitioning, replication

目的

  • 図6-1: replicationとpartitioningのcombination

6.2 K-V dataのpartitioning

目的

  • 目標: dataとqueryの負荷をノード間で均等に分散
    • 一部の負荷大: skewなstate, 一部: hotspot
    • → hotspotを避ける.

対応

  • !1 keyのrangeにもとづくpartitioning
    • 図6-2: e.g.
    • e.g.: HBase(OSS) (refers to Bigtable), RethinkDB, MongoDB(ver ~2.4)
    • access patternによってはhotspotが生じる決定ん
    • → keyに工夫が必要
  • !2 keyのhashにもとづくpartitioning
    • Cassandra, MongoDBはMD5, VoldemortはFowler-Noll-Vo
    • 同じkeyで同じhash値はmust
    • 図6-3: keyのhashによるpartitioning
    • 境界も疑似時乱数的に選択: Consistent hash法
      • CDNのようなcache systemで使われる.DBではあまり使われない
    • 均等分散は〇.しかし範囲へのクエリの効率悪い
    • Cassandraでは,先頭列以外ならrange search〇
      • 複合PK
      • 連結indexのapproach: 一対多のrelationに対してelegantなdatamodel
  • !3 workloadのskewとhotspotの軽減
    • applicationがskewを抑える必要
    • 負荷が集中する少数のkeyに限定 → n倍のkeyをreadなど,管理のための処理増
      • 分割されたkeyの追跡必要
      • 将来的には,datasystemが自動でskew workloadを検知 → 対処

6.3 Partitioning, Secondary index

目的

  • secondary indexは,SolrやElasticsearchなどの検索serverの存在意義(レーゾンデートル
  • secondary indexとpartitioningの対応づけのproblemに対応

対応

  • !1 documentによるsecondary indexでのpartitioning
    • 図6-4: e.g.
    • documentでpartitioningされたindex: local index
    • queryはすべてのPartitionに送る必要: scatter/gather
      • 負荷極大のケースアリ
    • e.g. MongoDB, Riak, Cassandra, Elasticsearch, Solr Cloud, VoltDB
  • !2 語によるsecondary indexでのpartitioning
    • 図6-5: e.g.
    • 「Word」 ← 全文検索indexから
    • range scanに有利になりうる
    • global index
      • readがeffective, writeが低速で複雑
      • ↑ scatter/gatherが不要
      • ↑ 1つのdocumentが複数Partitionに影響しうる
      • globalなsecondary indexの更新はasync
      • e.g. Riakのsearch機能や,local/global indexを選択できる OracleのDWH

6.4 Partition のrebalancing

目的

  • 負荷をcluster内のあるnodeから別のnodeに移行: rebalancing
    • 要求
      • 負荷がcluster内node間でfairに分配
      • rebalancing中も,dbはread/writeを受け付ける
      • node間のdataの移動は最小限.rebalancingは高速でnetworkやdisc I/Oの負荷を最小にする.

対応

  • !1 rebalancingの戦略
    • !!1 取るべきでない方法: hashの剰余
      • node数に場所が依存
    • !!2 Partition数の固定
      • 図6-6: balancingの前後
        • Partitionのnodeへのアサインのみ変わる
        • e.g. Riak, Elasticsearch, Couchbase, Voldemort
        • Partitionの数は固定が多い
        • → datasetの合計サイズに大きな変動があると,設定が難しい
    • !!3 dynamicなPartitioning
      • HBaseやRethinkDBなど,keyのrangeによってPartitioningされたDBは,dynamicにPartitionを作成
      • BTreeのtop level と似た処理
        • 固定 number (Partition)と同じく,各nodeは複数Partitionを扱える
        • dynamic Partitioningのメリット
          • Partitionの数をdataの総量に適合
        • 事前分割も可能
        • keyのrangeとhash Partitioningどちらにも〇
          • e.g. MongoDB
    • !!4 node数に比例するPartitioning
      • metadataのoverheadを低く抑える by 新しいhash function
      • e.g. Cassandra, Ketama
      • nodeあたりのPartition数を固定
      • hash baseのPartitioning → Partitionの境界をランダムに選択
      • ↑ context hash法の元々の定義に近い
  • !2 運用: 児童のrebalancingと手動のrebalancing
    • 自動化と児童のフォールト検知の組み合わせ
      • → カスケード フォールトのリスクあり
    • どこかで人の処理があった方が〇

6.5 requestのrouting

目的

  • service discoveryのproblem
  • 図6-7: 3つの方法
  • routingのjudgeを行うcomponentがどのようにしてPartitionのnodeへのアサインの変化を知るか
    • 図6-8: ZooKeeperを使った,Partitionからnodeへのアサインの追跡
    • e.g.
      • LinkedInのEspressoは,Helix(relys on ZooKeeper)を使用.routing層あり.
      • HBase, SolrCloud, KafkaもZooKeeper
      • MongoDBはoriginalのconfig serverとrouting layer: mongos
    • CassandraとRiakは,node間でgossip protocol
    • Couchbaseは,moxiというrouting層で構成
      • auto rebalancingなしのため単純
  • connect先IP addressはDNSで十分なこと多い

対応

  • !1 parallel queryの実行
    • OLAPで使われるMassively Parallel Processing: MPP(大規模並列処理)
      • relational dbは複雑なqueryをサポート.
      • ↑→ NoSQL distributed datastore: 単一のkeyのread/write
    • especially, datasetの大部分へのscanをするqueryで〇.

まとめ

  • 大規模なdatasetを小さな部分集合にPartitioning
  • dataに適したPartitionのschemaを選択 + rebalancing
  • 2つのPartitioningのapproach
    • keyのrangeによるPartitioning
      • rebalancingはdynamic
    • hash Partitioning
      • 固定数のPartitionがgeneral. dynamicなPartitioningも使える〇.
    • hybridなapproachも可能
  • secondary index のPartitioningの2つの方法
    • documentによりPartされたindex(local index)
      • scatter/gather必要
    • WordによってPartitioningされたindex(global index)
      • writeで複数Partitionをupdate, readは単一Partitionで処理〇.
  • routing
  • 全てのPartitionはほぼ独立に動くようdesign

Ch07 Transaction

目的

  • Transaction: 複数read/writeをlogicalな単位にまとめる
    • → systemの様々なフォールトへの対処 → 信頼性
  • commit/abort/rollback
  • Transactionの目的: dbにaccessするapplicationのためのprogramming modelを単純にする
    • → 安全性の保証
  • あらゆるapplicationがTransactionを要するわけではない
    • Transactionを弱めると,performanceや可用性が上がりうる
  • どのような安全性の保障と,それらに伴うcostを見る
    • especially, concurrency control
      • race condition, read committed, snapshot isolation, serializability
  • 単一ノードのdbにも分散dbにもあてはまるproblemを見る

7.1 Transactionというとらえどころのない概念

目的

  • MySQL, PostgreSQL, Oracle, SQL Serverとも,IBMがSystem R(1975)に導入したものに似ている
  • 非relational dbは,Transactionをはるかに弱い保証群として再定義
  • Transactionにはどちらでもないメリットと制限がある

対応

  • !1 ACIDの意味
    • Atomicity, Consistency, Isolation, Durability
    • 実情は,ただのマーケティングワード
    • ACID ←→ BASE(Basically Available, Soft state, Eventual consistency)
      • BASE: 「ACIDでない」という意味のみ
    • !!1 Atomicity
      • concurrencyとは無関係
      • commit or abort・rollback
      • → abortabilityが本来の意味をよくとらえる語
    • !!2 Consistency
      • dataについて常に真でなければならない何らかの言明・不変性がある
        • e.g. 貸借一致
      • → applicationの特性でありdbの特性ではない
      • CAP定理では,線形化可能性の意味
    • !!3 Isolation
      • concurrencyのproblem, race condition
      • 図7-1: e.g.
      • a.c.a. serializability(直列化可能性)
      • performanceのproblemのため,実際は使われない
      • snapshot分離というserializabilityより弱い保証もある
    • !!4 Durability
      • written dataはlostしないことを保証(完全はありえない)
      • discへのwriteとreplication → 多くの手法を併用すべき
  • !2 単一Objectと複数Objectの操作
    • multi Object Transaction
      • 図7-2: e.g. to Isolation
      • 図7-3: e.g. to Atomicity
      • 同じTransactionの判定: ClientからDB ServerへのTCP接続による
        • ↑ 望ましくない.TCP接続によらないuniqueなidを使う方法ある
      • 多くの非relational dbでは,操作のグループ化する方法なし
    • !!1 単一のObjectへのwrite
      • storage engineは,単一nodeにおける単一Objectのレベルで,Atomicity(← log), Isolation(← ロック@ Object)を提供
      • 一部: increment操作などのさらに複雑なatomic操作
      • 広く使用: compare-and-set
      • 複数Clientが並行に同じObjectにwriteしたときの更新lossを防ぐ
      • 通常,Transactionとは,複数Objectへの複数操作を1つの実行単位としてグループ化する仕組み
    • !!2 複数ObjectのTransactionの必要性
      • 多くの分散データストアでは放棄
      • relational data model, document data model, secondary indexでの必要性
    • !!3 errorとabortの処理
      • Transactionの重要な機能: error時にabort.安全にretry
      • aborted Transactionのretry: simple & effectiveなerror処理の仕組み.ただし完全でない
        • 別途重複排除必要
        • 過負荷へのexponential backoffが必要
        • eternal errorへのretryは×
        • 2相コミットが必要なケース ← DB外副作用
        • Clientのprocessing downは×

7.2 弱いisolation level

目的

  • ある種(not all)concurrency problemへの保護のみのsystemがgeneral
    • ↑→ serializableなisolation: performance重い
    • → bugもありうる
    • → concurrencyのproblemの種類と回避策をし折る
      • → 信頼でき正しく動くapplicationを,手の届くtoolsで構築

対応

  • !1 read committed
    • 2つの保証
      • ①dirty readなし
      • ②dirty writeなし
    • most basical levelのTransaction isolation
    • !!1 dirty readなし
      • 図7-4: e.g.
      • dirty read回避のメリット
        • 複数Objectの更新
        • rollback
    • !!2 dirty writeなし
      • いくつかのconcurrency problem回避
        • 図7-5: e.g.
        • counterのincrementのproblem(図7-1)は回避不可能
    • !!3 read committedの実装
      • e.g. Oracle11g, PostgreSQL, SQL Server 2012, MemSQL etc.
      • 行levelロックが一般的
      • ほとんどのDBでは,図7-4のようなapproach ← 旧新2つを保持
      • read committed isolation levelのためのロックは,IBM DB2と,read-committed snapshot=offのSQL Serverのみ
  • !2 snapshot isolationとrepeatable code
    • 図7-6: read-committedで生じるbug
    • non repeatable read(a.c.a. read skew)
      • skew: timingの異常. ≠ hotspotによるskew
    • temporary not consistencyが×なケース
      • backup
      • Analytic queryとconsistency check
    • → snapshot isolationで対処
      • 各Transactionがconsistentなsnapshotからread
      • 長時間のreadだけのqueryに有益
      • e.g. PostgreSQL, Storage engineとしてInno DBを使うMySQL, Oracle, SQL Server etc.
    • !!1 snapshot isolationの実装
      • readはwriteをnot block, writeもreadをnot block
      • MVCC(Multi-Version Concurrency Control)と呼ぶ
      • 図7-7: PostgreSQLでのsnapshot isolation by MVCC
    • !!2 Consistent snapshotを見るためのvisualize rule
      • Objectが見えるcondition
      • overheadを小さく抑える.一貫したsnapshotを提供
    • !!3 indexとsnapshot isolation
      • append-only/copy-on-writeなど,実装の細部
    • !!4 repeatable readとnameの混乱
      • readのみのTransactionに特に有益
      • 別名多い @Oracle → SERIALIZABLE, @MySQL,PostgreSQL → Repeatable Read
      • SQL Standardのisolation levelの定義は欠陥
      • Repeatable Readの正式な定義を満たす実装はほぼない
  • !3 更新のlostの回避
    • clobber(ひっぱたく)
    • !!1 atomicなwrite
      • 最もよい選択肢
      • 排他ロック,カーソル固定(stability)

      • ORM frameworkでは,unsafeなread-modify-write cycleが起こりうる

    • !!2 explicit lock
      • applicationによるlock
      • 例7-1
      • 実装複雑
    • !!3 更新のlostの自動検知
      • snapshot isolationとの併用が効率的
      • Transaction Managerが検知 → abort → retry
      • applicationが特別な処理の呼び出し不要 → 素晴らしい.
    • !!4 compare-and-set
      • snapshotからのreadがあるときは注意
    • !!5 conflictのresolutionとreplication
      • compare-and-setは×
      • siblingを生成〇 → 事後にconflictのresolutionやマージする
      • 交換可能な操作 → atomicな操作〇 @ replication
      • LWWは×だが,多くのDBでdefaultになっている
  • !4 write skewとphantom
    • 図7-8: e.g.
    • serializationかexplicit lock(→ !!1 what's write skew)
    • !!2 write skewのほかの例
      • 例7-2: 会議室予約システム
      • e.g. multiplayer game.利用するusernameの要求.2重支払いの防止
    • !!3 write skewを生じさせるphantom
      • phantom: あるTransactionのwriteがほかのTransactionのreadに影響
    • !!4 conflictの実体化
      • lock集合のtable作成: 最後の手段
      • → serializable isolation levelの方がはるかに◎

7.3 serializability

目的

  • race conditionに弱いTransactionにかんするproblem
    • isolation levelの理解難しい.DBごとに非一貫
    • safeかどうか判定が難しい
    • race condition detectのためのtoolなし
  • serializable isolation: 最も強いisolation level
    • → 考えられる全race conditionを回避
  • implementとperformanceのproblem

対応

  • !1 完全な順次実行
    • 単一threadでTransactionを処理 → serializable isolation level
      • RAM price down
      • OLTP Transactionは短く少ないread/writeしかない
    • e.g. VoltDB/H-Store, Redis, Datomic
    • lockによる調整のoverheadなく,高性能たりうる
    • !!1 SPへのTransactionのencapsulate
      • Transactionは1つのhttp request内でcommit
      • 単一threadで順処理では,外部とのやり取りを行う複数文を含むTransactionをprohibit
      • → 代わりにSPとして登録 → dataがmemoryにあれば極めて高速
      • 図7-9
    • !!2 SPのmerit, demerit
      • 現代的なSPの実装は,既存の汎用programming languageをつかえる
        • e.g. VoltDB - Java or Groovy, Data - Java or Clofare, Redis - Lua
      • SPとメモリにあるデータを使えれば,単一threadで全Transaction実行が現実的
        • → 良いthroughput
      • VoltDBは,replicationでもSPを使う → SPは決定的がmust
    • !!3 Partitioning
      • 複数PartitionにまたがるTransactionでは,SPのthroughputは数桁down
    • !!4 順次実行のまとめ
      • Transactionの順次実行がserializable isolation level実現のための制約
        • 全Transactionが小さくて高速
        • activeなdatasystemがメモリに収まるUseCase → or, anti caching
        • write throughputが,単一のCPU coreで十分処理できる程度には低い
        • or Partitionをまたぐ調整なしにTransactionをPartitioningできる
        • PartitionをまたがるTransactionでは,hard limitを設けられる
  • !2 two phase lock(2PL)
    • 30年間唯一のserializable isolation levelのための2PL ← 特にSS2L(Strong Strict Two-phase Locking)と呼ぶ
    • 2PL ≠ 2PC(Commit)
    • writerはほかのwriterに加えてreaderをブロック
    • readerもwriterをブロック
      • ↑→ snapshot isolation level
    • → すべてのrace conditionへのguardを提供
    • !!1 2PLの実装
      • e.g. MySQL(InnoDB), SQL Serverのserializable isolation level, DB2のrepeatable read isolation level
      • shared modeとexclusice mode
      • deadlockのproblemと対応
        • 自動の対応
    • !!2 2PLのperformance
      • performanceはbad
      • ↑ 多くのlockのoverheadと,concurrencyの低下
      • latency不安定 → 高p値の速度低い
    • !!3 predicate(述語) lock
      • phantomに対しても適用可能
    • !!4 index range lock(a.c.a. next-key lock)
      • preciseではないが,overheadははるかに低い
  • !3 serializableなsnapshot isolation(SSI)
    • 完全なserializableかつsnapshot isolationよりperformance〇
    • 2008~
    • e.g.
      • 単一node: PostgreSQL 9.1~
      • 分散DB: FoundationDB
    • !!1 pessimisticなconcurrency controlとoptimisticなconcurrency control
      • pessimistic: 相互排他(multithread programmingでdata structureを保護)に似ている.
        • ↑ 順次実行
      • optimistic ← SSI
        • 十分な要領でtransaction environmentの競合がそれほど高くない → performance〇
        • 競合: 交換可能なatomicな操作で減らせる
      • snapshot isolationの上に,write間のserializableのconflictの検知アルゴリズム
    • !!2 古くなったpremiseにもとづくjudge
      • premise: transactionのstart時は真だったfact
      • readとwriteの因果を示す必要
      • 要考慮点
        • 古いversionのMVCC Objectのreadのdetect(!!3)
        • 前のreadに影響sるwriteがあるときのdetect(!!4)
    • !!3
      • snapshot isolation level ← MVCCで実装
      • 図7-10: e.g.
    • !!4
      • 図7-11: e.g.
    • !!5 SSIのperformance
      • reader, writer間はブロックなし
        • latency予測〇, 変動小さい
        • readのみのqueryはロック不要
      • 単一CPU coreのthroughputにunlimited
        • 複数マシンのPartitioningにも対応
      • read/write transactionは極短がneeded
        • 2PLや順次実行ほどは,低速なtransactionの影響なし

まとめ

  • Transaction: abstractionのlayer
    • concurrencyやhardware, softwareのproblemを隠す
    • → simpleなtransactionのabortにまとめる → retryのみでOK
    • concurrency controlのlevel
      • read committed
      • snapshot isolation(a.c.a. repeatable read)
      • serializable
    • race conditionとisolation level
      • dirty read/write
      • non repeatable read(a.c.a. read skew)
        • MVCC
      • 更新のlost
      • write skew
      • phantom read
    • 全てをresolveはserializable isolation levelのみ
      • 〇順次実行
      • ×2PL
      • 〇SSI

Ch08 distributed systemのproblem

目的

  • distributed systemと単一マシンsystemの根本的違い

8.1 faultと部分fault

目的

  • 単一マシン: 決定的
  • distributed system: 部分fault → 非決定的
    • 成功したか分からない

対応

  • !1 Cloud computingとsuper computing
    • 大規模なcomputing systemの構築方法の哲学のスペクトラム
      • HPC(High Performance Computing)
        • 演算中心型のscientific calculation task
      • cloud computing
        • traditionalな企業datacenterは,この間のどこか
    • → フォールトへのapproach異なる
      • super computingは単一ノードのcomputingに近い
      • 本書の焦点は,internet上のserviceを実装するsystem
        • online → 低latency必要
          • hardware
          • network
            • 大規模datacenterのnetworkはIPとEthernetがベース
              • → 高2分割帯域幅のために,Clos topology
            • super computingのnetwork: 多次元メッシュやトーラス
          • 何かが常にフォールト
          • rolling upgradeなど
          • 地理分散 → (network) internetに依存
    • softwareにフォールトtoleranceの組込必要
      • 信頼性のないcomponentからtrustnessあるsystemを構築
      • 様々なフォールトへのテスト必要

8.2 低trust network

目的

  • shared nothing system by network
    • internetとdatacenter内の大部分の内部network(Ethernet)は,async packet network
      • 図8-1
      • 各problem ^ timeoutでの対応

対応

  • !1 networkのfaultの実際
    • networkの分断: network partition, netsplitと呼ぶ
      • 必ずしもtolerantである必要はない
      • networkのproblemへの反応の認識が重要
  • !2 faultのdetect
    • requestのsuccessは,applicationからのproperなresponce以外確認不可能
      • errorはtimeoutでjudge
  • !3 timeoutと限度のない遅延(unbounded delay)
    • 保証なし@networkのdeliveryとrequestの処理のtime
    • !!1 networkのcongestionとqueuing
      • 図8-2: queuing
        • TCP, UDP
        • timeoutは経験的に決定 @public cloudやmultitenant datacenter
          • auto timeout 調整も◎
            • e.g. AkkaやCassandraで利用されているPhi Accural failure detector
            • TCPのresendのtimeoutと同様
  • !4 sync networkとasync network
    • sync networkでは,bounded delay by 回線,connection
    • !!1 network delayの予測
      • burst性のあるtrafficにoptimiseされたnetwork: packet 交換方式
      • QoSやadmission control(受付control)を使うと,packet network上で回路交換をemulate. 統計的にdelayのbound課すこと可能
      • latencyとresourceの活用: tradeoff
      • このQoSは,multitenant datacenterやpublishing cloudにはない
      • → networkのcongestion queuing, unbounded delayは不可避

8.3 低trust clock

目的

  • 期間と時点
  • 時間の複雑さ
  • clockのsync

対応

  • !1 単調increment clockと時刻のclock
    • !!1 時刻のclock
      • a.c.a. wall-clock time, real time
      • NTPとsync
      • 解像度のproblem @ 旧マシン
    • !!2 単調incrementのclock
      • 期間の計測に〇
      • 絶対値はno mean
      • 各CPU timerは必ずしも同期でない
      • slewing: 進ませる頻度の調整
      • distributed systemの期間計測に使える.
  • !2 clockの動機とaccuracy
    • ずれが生じるe.g.
    • 精度の実現
      • GPS受信マシン, Precision Time Protocol(PTP), 注意深いdeployとmonitoring
      • コスト莫大
  • !3 sync clockへの依存
    • softwareがclockのずれをmonirtor要
    • !!1 順序relationをもつeventのtimestamp
      • 図8-3: e.g.
      • LWWのproblem
        • → logical clockの使用が〇
          • 相対順序の決定.単調increment
        • ≠ physical clock: 時刻のclockや経過時間を観測する単調increment のclock
    • !!2 clockの値の信頼区間
      • 精度より小さい桁はno mead
      • ふつうは非公開
    • !!3 globalなsnapshotのためのsync clock
      • distributed system(machine), 複数datacenterなどでのDBにおけるsnapshot isolation levelのproblem @transaction idの生成
      • SpannerはTrueTime APIを使い,clockのtimestampをTransaction IDとして用いる
      • distributed transactionでのclockのsyncは重要
  • !4 processingの一時停止
    • distributed systemにおけるleaderの扱い
      • leaderがleaseを取得
        • lease: timeoutつきlockのようなもの
      • leaseについてのclockのproblem
        • ずれ
        • 処理時間
          • especially, processing(thread)の一時停止
            • processingが止まる例
              • GC(Garbage Collector)
              • VMのsuspend→ resume e.g. for host間live migration
              • VMがCPUを使うsteal time
              • discへのswapping(paging) → thrashing
              • UNIXでのCtrl-z(: SIGSTOP) (→ SIGCONTでrestart)
            • preemption(一時的中断)に気づけない
            • multithread codeをthread safeにするproblemと同様
    • !!1 responce timeの保証
      • hard real time system. RTOS(Real Time OS)
        • 組込systemのreal time ←→ Webのreal time
        • physicalなものをcontrolするsystem
        • worst proceed timeの保証
          • cost 極大.performance 悪い
          • safetyが極めてimportantな組込deviceを使う
          • ↑→ 多くのServer side data proceed system
    • !!2 GCによるimpactの制限 → 有益
      • GCの一時停止を事前に計画された短時間のnodeの停止として扱う
      • processingのregular restart
        • GCは短命Objectのみ

8.4 知識・真実・虚偽

目的

  • system model(仮定)を設定して設計する
  • distributed systemでの知識と真実を見る

対応

  • !1 真実(truth)は多数決で決まる
    • 多くのdistributed algorithmはquorumに依存
    • !!1 leader とlock
      • 図8-4: bugのe.g.
    • !!2 フェンシングtoken
      • 図8-5: e.g.
      • e.g.: ZooKeeperでのzxid, cversion
      • Server sideでのtoken chack: 〇
  • !2 ビザンチンフォールト(Byzantine)
    • nodeはuntrust, but誠実がpreposition
    • Byzantine fault-tolerant: attackerへも耐性
      • complicate protocol必要.hardware levelでのsupportに依存
      • P2P networkでは考慮必要
    • !!1 weakなうそからの保護
  • !3 system modelと現実
    • 3つのmodel
      • sync model
        • ほとんどのcaseで現実的でない.上限は現実ではないこと多い
      • 部分 sync model
        • 多くのsystemで現実的
      • async model
        • 制約強い
    • nodeについての3つのmodel
      • crash stop fault
      • crash recovery fault
      • Byzantine fault
    • 部分sync modelとcrash record faultのペアが一番beneficial
    • !!1 algorithmの正しさ
      • 性質(properties)によって正しさを定義
      • e.g. unique性,単調increment sequence(→ ここまで安全性), 可用性(→ live性)
    • !!2 安全性とlive性
      • live性: 「eventual」 ←→ 安全性: いつも起こらない
    • !!3 現実世界へのsystem modelのmapping
      • 実際の実装では,起こりえないことへの対処のcodeが必要
      • 理論的分析と実践的testは等しく重要

まとめ

  • distributed systemでの幅広いproblem
    • 部分fault
    • faultのdetect
      • quorumが合意するためのprotocolで耐性付け
  • distributed systemの目的: scalability, fault-tolerance, low latency
    • ↑→ 単一node

Ch09 一貫性と合意

目的

  • fault-tolerantなdistributed systemの構築のためのalgorithmとprotocol
    • abstractionでproblemを隠蔽が重要
      • 重要なabstraction: 合意
    • 可不可の限度の認識が重要

9.1 一貫性の保証

目的

  • eventual consistency(convergence(収束性)の方が良い表現) @replicationをするdb
    • とてもweakな保証
    • boundの認識が重要
    • edge case: systemのfaultや,並列性極高のときに生じる
    • → より強い一貫性modelを見る
      • 対価: performance, tolerance down
  • distributed 一貫性modelと,transactionのisolation levelの階層は,focusがそれぞれ独立.
    • transactionは,race conditionの回避
    • distributedの一貫性は,delayやfaultに際してのreplicaの調整
    • ただし,両社は深くrelationあり
      • linearizability(線形化可能性): the strongest
      • distributed systemでのeventの順序付けの問題
        • especially 因果律と全順序(total ordering)のproblem
      • atomicityを保ちつつcommit @ distributed transaction
      • → 合意のproblemの解決方法

9.2 linearizability

目的

  • linearizability: a.c.a. atomic consistency, strong consistency, immediate consistency, external consistency
    • dataのcopyが1つしかないように見せる
      • recency guarantee(最新性の保証)
        • 図9-1: 反例

対応

  • !1 systemをlinearizableにするcondition?
    • 図9-2: xはregister. read, write, concurrのe.g.
    • 図9-3: concurrencyでの制約.新旧どちらか不明な登録(regular register)
    • 図9-4: complicate case ← compare and set
    • linearizabilityとserializability
      • linearizability
        • 個々のObjectに関すること.registerのread/writeでのrecency保証
      • serializability
        • transactionのisolation.複数Objectを扱う.transactionの実際の順序とは関係なし.
      • 共に提供: strict serializability(a.c.a. strong-1SR, strongest one-copy serializability)
      • SSIはnot linearizability
  • !2 linearizabilityへの依存
    • !!1 lockとleader election
      • lockはlinearizability must
      • e.g. Apache ZooKeeperやetcd. for distributed lock, leader election
        • 合意algorithmを使い,fault tolerantを保って,linearizableな操作を実装
        • Apache Curatorのようなlibraryが,ZooKeeper上で高レベルの処方を提供. to 多くの繊細なproblem
        • → 協調taskの基盤になる
      • distributed lockは,Oracle Real Application Clustors(RAC)のようなdistributed db 中で極小levelで使用
        • RAC: lockをdiscのpageごとに使う
        • linearizable lockは,transaction実行のcritical path
        • → db node間communicationに,専用のcluster inter connection networkを使う
    • !!2 制約およびuniqueの保証
      • unique制約を保証するためのlinearizability
        • lockと類似
    • !!3 cross channel timing依存relation
      • 図9-5: e.g. cross channel
      • → linearizability 必要
  • !3 linearizable systemの実装
    • replication for fault-tolerance
      • single leader replication (潜在的にlinearizable)
      • 合意algorithm ( linearizable)
        • e.g. ZooKeeper, etcd
      • multileader ( not linearizable)
      • leaderless replication(maybe not linearizable)
    • !!1 linearizabilityとquorum
      • 図9-6: quorumでのrace condition
      • performanceを代償にすれば,linearizableにできる
        • compare-and-setは×
      • → 不可能と考えてよい
  • !4 linearizableにするコスト
    • 図9-7: linearizability or availabilityのselection
    • !!1 CAP定理
      • linearizabilityとavailabilityのtradeoffの議論の出発点
      • CAP 3つから2つではなく,C(Consistency: linearizability)かAvailabilityの一方をselect when network fault
      • Availabilityには矛盾した複数の定義アリ → CAPは使えない
      • linearizabilityとnetwork分断のみを扱うもの
        • → historicalなinterestのみある
    • !!2 linearizabilityとnetwork delay
      • 実際にlinearizableなsystemはほとんどない
        • e.g. multi core CPUのRAMも not linearizable. without memori barrier or fence
      • performanceとのtradeoffのため

9.3 Orderの保証

目的

  • 順序付け: important basic concept(概念)
    • Ch05, 07, 08
  • 順序とlinearizability合意の間の深い関係

対応

  • !1 Orderと因果関係
    • Orderは因果関係
      • e.g. request/responce, 事前発生(Ch05), Consistency, skew(Ch07), 図9-1
    • 因果律からのorderに従う: 因果律において「causually consistent」
      • e.g. snapshot isolation
    • !!1 因果律にもとづくorderと全orderの違い
      • incomparable: {a,b}, {b,c}
      • → partially ordered(単順序) → {a} ⊂ {a,b}など
      • linearizable systemは全order
      • 因果律: 半orderを定義
        • concurrencyはincomparable
      • → linearizable systemにはconcurrencyなし
      • concurrency: 枝分かれ.別々の分岐はincomparable
    • !!2 因果律の一貫性より強いlinearizability
      • linearizabilityは因果関係を暗に含む
        • しかし,performanceやavailabilityの大小アリ
      • linearizability以外でも因果律は実現可能
        • → causually consistencyがnetwork delayで速度が落ちないconsistencyの中でstrongest
          • network faultがあっても利用〇
        • → ごく最近の研究で扱われている. about causually consistency
    • !!3 因果律における依存関係の補足
      • 操作の先行を知る必要: 半order
        • nodeのacknowledgeを記述する必要
          • version vectorの利用 ← 5.4.4と似ている
          • dbがread dataのversionを知ることが必要
  • !2 sequencial numberのorder
    • sequencial number( or timestamp)でのeventのorderづけ
      • timestampはlogical clockで〇
    • compactで全orderを提供
      • especially, sequencial numberは因果律とのconsistencyをもつ全orderを持たせて生成〇
      • e.g. single leader replicationのdbは,replication logがwriteの全orderを規定
    • !!1 因果的でないsequencial number生成器
      • 単一leaderなし → sequencial numberの発行は,不透明
        • 個別のsequencial number発行は,因果律のconsistencyなし
          • ↑ 複数nodeでの操作のorder補足不可能
    • !!2 Lamport timestamp
      • 図9-8: e.g. ← {counter, nodeID}のpair 「max」が重要
      • readed max counterを追跡 by all nodes, Clients
      • version vector: 並行か因果律の依存関係か判断
      • Lamport timestamp: 常に全orderが決まるようにする
      • 上の2つは目的がdifferent
    • !!3 timestampでのorderづけでは不十分
      • Lamport timestampは,distributed systemのgeneral な多くの問題の解決には不十分
      • ↑ 操作の全orderは,すべての操作がcollectできたあと
      • → unique制約には,操作の全orderでは不十分
        • → いつまでに確定するかが重要
  • !3 全orderのbroadcast
    • problem
      • 操作のthroughputが単一leaderでproceedできる以上のもののときのsystem scale 方法
      • leaderのfail over
      • (↑2つ)→ total order broadcast ( or, atomic broadcast)と呼ぶ
    • Partitionごとのleaderのときは,total order broadcastよりさらにcomplicate processingが必要
    • total order broadcast: node間のmessage交換protocolとして記述
      • 2つの安全性の保障
        • trusted cast(配信)
        • total ordered cast
    • !!1 total order broadcastの利用
      • ZooKeeperやetcdのような合意serviceは,total order broadcastを実装
      • total order broadcast: dbのreplicationに必要なもの
        • ↑ state machine replication
        • serializable transactionの実装にも使われる
      • messageがcastされた時点で順序確定
        • → timestampでのorderingよりstrong
      • logの生成とみることも〇
        • fencing serviceをserveするlock serviceの実装にも使える
        • @ZooKeeperのzxid
    • !!2 total order broadcastを使ったserializable storageの実装
      • serializabilityとtotal order broadcast(合意のproblem)は密な関係
      • total order broadcast: async ←→ linearizabilityは最新性
      • but, total order broadcast可能 → linearizable storage構築〇
      • linearizable compare-and-set操作は,total order broadcastを,追記のみ行われるlogとして使う
      • 全てのnodeが,どれが初めか合意
        • → writeのcommitとabortの合意
          • → log baseのserializable multi object transactionの実装にも使える
        • → writeはlinearizable, readはnot linearizable
        • → sequencial consistency(a.c.a. timeline consistency) <(わずかに) linearizability
        • readもlinearizableにする方法,approach
    • !!3 linearizableなstorageを使ったtotal order broadcastの実装
      • linearizable sequencial number generatorを使う ← 合意のalgorithm
      • linearizable (increment) compare-and-set registerと,total order broadcastはどちらも合意と等価
        • → どちらかをresolve → もう一方にも変換〇

9.4 distributed Transactionと合意

目的

  • consent: distributed computingで,most importantでbasicalなproblemの1つ
  • replication, transaction, system model, linearizabilityとtotal order broadcastの上に立つproblem
  • node群のconsentがimportantなcase
    • leader elegant
    • atomic commit
    • → atomic commit problem
  • consent の不可能性
    • FLP帰結(consent不可)は,async system modelでの証明
    • 通常のdistributed systemはconsent可能

対応

  • !1 atomic commit と2PC
    • transactionのatomicity
    • !!1 単一nodeからdistributed atomic commitへ
      • 単一nodeでのtransactionのcommitは,dataが永続性をもってdiscにwriteされるorderに完全に依存
      • data のwrite → commit recordのorder
      • read commit isolationのため,commitは消せない
    • !!2 2PC
      • applicationからはXA Transactionや,SOAP Web servicesのWA-Atomic Transaction経由で利用
      • 図9-9: e.g.
      • 2PC: distributed systemでatomic commit ≠ 2PL: serializable isolationを提供
        • coordinator(a.c.a. transaction manager)
          • e.g. Narayan, JOTM, BTM, MSDTC
        • db node: 参加者
    • !!3 約束のsystem
    • !!4 coordinatorのfault
      • in doubt, uncertain
        • 図9-10
      • coordinatorのrecoveryを待つ必要
    • !!5 3PC
      • 2PC: blocking atomic commit protocol
      • 3PC: nonblocking
        • but, 制限あり.現実にはnot atomic
          • non blocking. atomic commitはperfect failure detector必要
            • 実際は難しい
  • !2 distributed transactionの実際
    • distributed transactionへの2つの評価
      • ほかのwayでは提供できない重要なsafenessの保証を提供
      • ↑→運用上のproblemの原因.performanceを損ない提供可能以上の約束をしている.
      • → 実際は,多くのcloud serviceで,distributed transactionは実装していない
    • 2つのdistributed transaction
      • db内部のdistributed transaction → 特定の技術固有のoptimise〇
      • heterogeneous(不均一な,hetero: other)なdistributed transaction → 特定の技術固有のoptimise×
        • 参加者は2つ以上の異なる技術を使う
    • !!1 exactly-onceなmessage proceed
    • !!2 XA transaction
      • X/Open XA (eXtended Architectureの略): heterogeneous technologyでの2PCのstandard
        • 多くのrelational dbやmessage brokerで旧来サポート.
        • XA: transaction coordinatorへのCのAPI
          • Javaでは,Java Transaction API(JTA)で実装
            • JTAは,Java DB Connectivity(JDBC)を使うDBの多くのdriverや,Java Message Service(JMS) APIを使うmessage broker用のAPIでサポート
      • transaction coordinatorがXA APIを実装
    • !!3 in doubt下のlockの保持
      • lockのproblemあり
    • !!4 coordinatorのfaultからのrecovery
      • orphaned(孤立) in doubt transaction
      • heuristic decisions を緊急避難ハッチとする実装
        • atomicityを破る決定を回避
    • !!5 distributed transactionのboarder
      • XA transaction: 複数参加者のdata system間consistencyを保つという,realで重要なproblemを解決
      • but 運用上の大きなproblemあり
      • → transaction coordinator自体が一種のDB
        • replication必要
        • application serverのstateのproblem
        • SSIとともにはXAは×
        • db内部のdistributed transactionは制限小さい
          • → SSIのdistributed versionはrealizable
          • but, distributed transactionはfaultを増幅
  • !3 耐障害性をもつconsent
    • consent: 非形式的には,複数nodeが何かについて同意すること.
      • 形式的には,1つ以上のnodeがpropose → 合意algorithmがそれらの値から1つを決定
    • uniform consent
      • 4つの性質
        • uniform agreement
        • integrity(整合性)
        • validity(妥当性) (ここまで3つが合意の核.安全性)
        • termination(終了性): 耐障害性.(live性)
    • いかなるalgorithmも,terminationの保証にはat least 過半数のnodeが正常であることが必要
    • 安全性は,ほとんどのnodeが×でも保証できる
    • Byzantine faultはないことを前提
    • !!1 consent algorithmと total order broadcast
      • 耐障害性のconsent algorithm
        • e.g. ViewStamped Replication(VSR), Raft, Paxos, 2ab
        • 形式的modelでなく,値の並びに決定 → total order broadcast
          • → × 1つの値ごと, 〇 各orderでconsent → effective
    • !!2 single leader replicationとconsent
      • leader electionのためにleader必要
    • !!3 epoch numberとquorum
      • epoch: a.c.a. ballot, view, term
        • 2 roundのvote(ballot)
        • electionと2PCの違い → consent algorithmの正しさと耐障害性のkey
          • coordinatorは2PCではnot elect
          • 2PCではすべての参加者 ←→ 耐障害algorithmでは過半数
    • !!4 consentのbound
      • consent algorithm: distributed systemの大きなbreakthrough
        • すべてが不確定なsystemに,強い安全性(3つ)と耐障害性を与える
        • total order broadcastを提供.耐障害性を保ちつつlinearizable and atomicな操作を実装
      • performanceとcostのproblem → 使われないcaseあり
        • 非固定集合では,sync membership extention必要
      • timeout依存 → network delay大のcase → performance×
        • e.g. Raftなど
        • → 低trust networkに対する耐性アリのalgorithmは研究中
  • !4 membershipと強調service
    • ZooKeeperやetcd: distributed key-value store, 協調および設定service
      • 完全にmember内に収まる少量のdataを保持
      • 耐障害total order broadcastを使って全nodeにreplication
      • ZooKeeper ← GoogleのChubby
      • total order broadcast 以外の機能群あり
        • linearizable and atomicな操作
        • 操作の全順序
          • fencing token
    • fault detect
      • ephemeral node ← sessionがもつ任意ロック
    • 変更通知
      • 通知をsubscribe
    • !!1 nodeへの処理のassign
      • ZooKeeper/ Chubbyがeffectiveなcase
        • processing/ serviceの複数インスタンスからleader, primaryをelect
          • Job Schedulerやほあkのstateful systemでも〇
        • partitioningされたresource(db, message system, filestorage, distributed actor system etc.)
          • どのnodeにどのpartitionをassignかjudge
      • ZooKeeperのatomic操作, ephemeral node, 通知により達成可能
        • Apache Curatorのようなlibraryあるが,簡単ではない
      • ZooKeeperはnode間協調作業をoutsourcing
      • applicationのstateをnode間でreplication → Apache BookKeeper
    • !!2 service discovery
      • ZooKeeper, etcd, Consul
      • linearizability不要なread requestにresponceできる
    • !!3 membership service
      • consentとfault detectの組み合わせ
      • どういったnode群でmembershipが構成されているか.Systemでconsent生成は有益

まとめ

  • 一貫性とconsent
    • linearizability ← 一貫性model
  • 因果律
    • 全eventのorder
    • 弱い一貫性model
    • 分岐と合流のversion history
    • → consentのproblem
  • 合意のproblemと等価なもの
    • linearizable compare-and-set register
    • atomicなtransactionのcommit
    • total order broadcast
    • lockとlease
    • membership/ 協調service
    • unique制約
  • single leaderがin faultのcase
    • leaderのrecovery待ち
      • XA/JTA transaction coordinator
      • 終了性なし → consentを解決しない
    • 手動fail over
      • 低速
    • algorithmで自動に新leader elect
      • consent algorithm
      • networkの状況に対処必要証明
  • 耐障害性をもつconsentのためのalgorithm system
    • ZooKeeper
  • consent不要なcase
    • multi leader replication system
      • 単にlinearizabilityなしに対処.分岐や合流を伴うversion historyをもつdataを扱えばよい.

『データ指向アプリケーションデザイン ――信頼性、拡張性、保守性の高い分散システム設計の原理』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が重要な多くのケース

『問題解決力を鍛える アルゴリズムとデータ構造』

Ch01 what's algorithm

  • algorithm: 問題を解くための方法、手順
  • binary searchとlinear search
  • どんなケースも同じやり方で答えを導ける
  • Depth-First Search(DFS)
    • とりあえず突き進むを行き詰るまで繰り返す
    • 探索順序を工夫すると劇的な性能差になるのが魅力。
  • Breadth-First Search(BFS)
    • 出発点に近いところから順に探索
    • 何かを達成するための最小手順を知るために使える
  • DFS, BFSとも、グラフ上の探索と考えると見通しがよくなる
  • matching

    • 2 category間のつながりの問題
      • internet広告配信、レコメンドシステム、マッチングアプリ、シフトスケジューリングなどで使える
  • 章末問題

    • 1.4: 九九で2桁の和が6になるものに目をつけるといいのかもしれない
    • 1.6: BFS。地図上の最短経路を求める。

Ch02 計算量とオーダー記法

  • 調べるべき組み合わせをマトリックスで考える→ 図2.3
  • 一般的なパソコンで1秒間に処理できる計算ステップの回数: 109
  • 各オーダーでの入力サイズと計算ステップ回数の関係→ 表2.2
  • 指数時間: O(N!), O(2N)
  • 多項式時間: Ndの定数倍で上から抑えられるもの
  • 定数時間: O(1)
  • 計算量: 以降は最悪計算時間量を指す
  • ランダウのO記法の詳細
    • オメガ、シータ
  • 章末問題
    • 2.1 N1/2 > logN
    • 2.2 処理の意味が書いてある。それでも答えられる。
    • 2.3 素数でない数は2からN1/2までのいずれかを約数に持つ。
    • 2.4 証明なら数学的帰納法がよい。選択肢の数の推移をみる。
    • 2.5 N = 2kとして考え、対数を扱う。
    • 2.6 分数を積分して対数を出す。

Ch03 設計技法(1): 全探索

  • 意義
    • 全探索アルゴリズムを考案することで、解きたい問題の構造に対する深い理解を獲得できることがある。
    • → 結果的に高速なアルゴリズムの設計に結び付くこともある。
  • 線形探索
    • 全ての基礎となる重要なアルゴリズム
    • 多量のデータから特定のデータを探し出す。
    • 条件を満たすものの場所も求める
    • 最小値を求める
    • ペアの全探索
    • 組み合わせの全探索
      • N個の整数からなる集合の部分集合は2N通りある
      • 部分集合に整数の二進法表現を用いる。
        • code3.5, 表3.2 bit演算で判定する
        • 1 << i: 二進法表現で右からi桁目のみが0であるような値を表す(最も右を0桁目とする)。
  • まとめ

    • 全探索は、解きたい問題に対して、考えられるすべての可能性を調べ上げることで解決する手法
    • すべての基礎となる重要なもの。
  • 章末問題

    • 3.3
      • worst, second(変数の名前づけについて)
      • 共にINFで初期化で〇
    • 3.4
      • max, minを求めればOK
    • 3.5
      • それぞれの値を2で何回割れるか求める。
      • なんかor演算でも行けたりしないかな
    • 3.6
      • z = N - x - yでok
    • 3.7
      • bitでプラスの位置を表せば〇

Ch04 設計技法(2): 再帰と分割統治法

  • 様々な問題に対して、簡潔かつ明快なアルゴリズムを記述できる。
  • 再帰関数のテンプレート: basecaseでreturn。その他は再帰
    • basecaseに対する処理が重要。
    • 引数がbasecaseに近づくようにする。
  • 再帰の例
  • → メモ化, キャッシュ
  • 再帰関数を用いる全探索
    • 部分和問題
      • N番目について場合分け: 図4.4, code4.9
      • メモ化
  • 分割統治法
    • 与えられた問題をいくつかの部分問題に分解し、各部分問題を再帰的に解き、それらの解を組み合わせて元の問題の解を構成するアルゴリズム技法。
    • 基礎的な考え方。
    • 真価を発揮するとき: すでに多項式時間のアルゴリズムが得られている問題に対して、より高速なアルゴリズムを設計するために、分割統治法を意識的に用いるとき
    • 入力サイズNに関する計算時間T(N)についての漸化式を考える。
  • まとめ
    • 再帰関数を用いる本来の目的: 問題をより小さな問題に分割して解く
  • 章末問題
    • 4.1 basecaseと、basecaseに近づく処理を考える。
    • 4.3 三項間漸化式を特性方程式を用いて解く。等比数列を作る。
    • 4.4 T(N)についての漸化式を考える。フィボナッチ数列と同様の増加。-51/2の方は0に収束する。
    • 4.5
      • 753それぞれの有無を判定するフラグを使う。フラグは二進法表現が〇。
      • 753だけ使えるのをちゃんと読む。753いずれかを付け足していくことで列挙できる。
      • counterは共有する。
    • 4.6 メモ化。再帰の前で計算済みか確認。計算済みならメモをreturn。

Ch05 設計技法(3): 動的計画法

  • 動的計画法
    • 与えられた問題全体を一連の部分問題に上手に分解し、各部分問題に対する解をメモ化しながら、小さな部分問題から大きな部分問題へと順に解を求めていく手法。
    • 分野横断的に適用できる
    • 一連の部分問題への分解の仕方のパターンは多くない。
  • 例題
    • Frog 問題
      • グラフの問題としてとらえる。
      • 過程をメモの値に集約
      • 部分構造最適性: 元の問題の最適性を考えるときに、小さな部分問題についても最適性が要請される
        • → このような構造を利用して最適値を順に決定していく手法が、動的計画法
  • 動的計画法に関連する諸概念
    • 緩和
      • テンプレート関数の使用
    • pull-based, push-based
    • 緩和処理の順序のポイントは、頂点uから頂点vへと遷移する辺に関する緩和処理を成立させるためには、dp[u]が確定している必要があること。
    • 全探索のメモ化としての動的計画法
  • ナップサック問題
    • 動的計画法以外にも解法がある。
    • 動的計画法の部分問題の作り方の基本的なパターン: N個の対象物{0,1,...,N-1}に関する問題に対して、最初のi個の対象物{0,1,...,i-1}に関する問題を部分問題として考える。
    • 各段階においていくつかの選択肢が存在するという状況は、動的計画法を有効に適用できそうだということを示す。
    • 考えたテーブル設計でうまく遷移が作れなかった場合に、添え字を付け加えることで遷移が成立するようにする作業がよくある。
      • 添え字を追加する作業: 選択肢をまとめ上げる粒度を細かくすることに対応。
    • 動的計画法: 考えられる場合をグループごとにまとめるイメージの手法。グループの個数とグループ間の遷移の個数が最終的な計算量。
    • 選ぶときと選ばないときの遷移を式にする。
      • 図5-10: テーブル更新の様子。選ばなかった場合の同じウェイトの値と比較している。
  • 編集距離
    • 応用: diff command, spell checker, 空間認識・画像認識・音声認識などのパターンマッチング, バイオインフォマティクス(系列アラインメント)
    • テーブル定義: dp[i][j]←Sの最初のi文字分と、Tの最初のj文字分との間の編集距離
    • 編集距離: 対応を作る/ 最小コスト弾性マッチング問題: マッチさせる
  • 区間分割の仕方を最適化
    • 区間の表し方。要素の両端と間に番号を振る。[l, r)
    • K: 区間の数。N: 要素の数。t: 0からNまでの区切り。
    • dpのサイズ*緩和処理の対象となる遷移の個数に計算量が依存する。
  • まとめ
    • 動的計画法は多くの問題に有効
    • テーブルの設計パターンは意外と少ない。
    • 固有の問題に対して、大局的なパターンと、その問題に固有の事情とを分けて考えられるようになることが大事。
  • 章末問題
    • 全体として: 値の定義と、chmax/ chminによって、ループ間の比較は必要なくなる。
    • 5.1 a,b,cについて添え字を加えると、chmax(dp[i+1][k], dp[i][j] + a[i][k])と表すことができる。
      • ↑ a[i],b[i],c[i]とも添え字でまとめてしまうと1行で書くことができる。
      • chmaxは選択肢の数分呼ぶ。次のdpの値を選択肢の数分だけ比較して最大にする。
    • 5.2 dpには値ではなくboolを入れればOK
    • 5.3 5.2と同じ
    • 5.4 boolではなく個数を値として持たせる
    • 5.5 毎回のa[i]について、Wを超えない範囲で足し続けてよい。
      • ただし、Wに対してループしているので、1度足せばよい。
      • 同じi(またはi+1)内で遷移できるパターン
    • 5.6 値で最後の整数の使用回数の最小値を保持する
    • 5.7 dpに文字数を入れる。i, jのとき、S[i], T[j]はカウントされていないため、これらが一致するかどうかで増えるか決まる。
    • 5.8 各区間の平均値は別で求める必要あり。
      • 区間は、要素数の間では遷移がない。区間数でのみ遷移する。追加する区間は場合分けが必要なため、区間追加のためのループが必要になる。これがもう1回分のNとなる。
    • 5.9 (以降解答なし)start, endが必要だが、endは要素数で表せる。dp[要素数(終了位置)][開始位置]のテーブルを持つ。
      • chmin(dp[i][j], dp[i-s][j] + dp[i][j+s])で求められそう。sは区切りで、要素数の分だけ1つずつ繰り返し試す。

Ch06 設計技法(4): 二分探索法

  • 配列の二分探索
    • 配列がソート済みであることが必要。
    • O(logN)
  • C++のstd::lower_bound()
    • 値keyが属する区間を特定
  • 一般化した二分探索法
    • 各整数xに対してtrue/falseの2値で判定される条件Pが与えられていて、ある整数l. r(l < r)が存在して、以下が成立しているとする。
      • P(l) = false
      • P(r) = true
      • ある整数M(l < M <= r)が存在して、x<Mなるxに対してP(x) = falseであり、x>=Mなるxに対してP(x) = trueである。
    • このとき、D = r - lとして、二分探索法はMをO(logD)の計算量で求めることができるアルゴリズムといえる。
    • leftは常にfalse側、rightは常にtrue側
    • プログラムのデバッグでも使っている考え方
    • (整数ではなく)実数上の二分探索法(二分法ともいう)も可能。求めたい精度によって終了条件を規定する。
  • さらに一般化した二分探索法
    • 単調性の仮定を外した二分探索法
    • 一般化した実数上の二分探索法: ある実数区間において連続な関数f(x)が与えられ、その区間に属する2点l, r(l < r)に対して、f(l), f(r)のうちの一方が正で一方が負であるとする。このとき二分探索法(二分法)によって、f(x)=0を満たす実数x(l < x < r)のうち1つを、いくらでも高い精度で求めることができる。
      • 単調性の仮定を外す代わりに関数fに連続性を課す。中間値の定理がxの存在を保証。
  • 応用例(1): 年齢当てゲーム
  • 応用例(2): std::lower_bound()の活用例
    • ペア和のK以上の中での最小値
      • a[i]を固定して、bについて二分探索。O(NlogN)。
  • 応用例(3): 最適化問題を判定問題に
    • 「~という条件を満たす最小値を求めよ」→「xが条件を満たすかどうかを判定せよ」。
    • 最大値の最小化。
      • 「N個すべての値をx以下にできるかどうかを判定してください。」
  • 応用例(4): medianを求める
    • median: 小さい順に(N-1)/2番目の値のこと
    • 「N個の非負整数a[0],..,a[N-1]のうち、x未満の整数が(N-1)/2個あるかどうかを判定してください。」
  • まとめ
    • 二分探索法をより汎用性の高い手法として捉える。
      • 特に、最適化問題を判定問題に帰着させる考え方は、実用的にも有力な手法
  • 章末問題
    • 6.1 まずはソートが必要。あとは、a[i]より大きいことを条件として、right, leftの範囲を絞って要素が1つになるよう、二分探索をすればOK。
    • 6.2 3つ配列があるときは、真ん中を固定することで、ループを1重で済ませられる。あとはただの二分探索。
    • 6.3 O(N3logN)までしかできなかった。4組のときは、2組ずつ処理することでN2のオーダーで処理できる。
    • 6.4 条件の関数をまず書く。条件に渡すのは、二分探索でのmid。条件判定によって左端か右端にmidを入れる。
    • 6.5 2重の二分探索。a[0]b[0]..a[N-1]b[N-1]の中間を条件に渡し、さらにa[0]..a[N-1]のループ中で、それぞれb[0]..b[N-1]について二分探索をする。(確認していないけどたぶんあってると思う)
    • 6.6 さらに一般化した二分探索法(ある実数区間において連続な関数f(x)が与えられ、二分探索法(二分法)によって、f(x)=0を満たす実数x(l\<x\<r)のうち1つを、いくらでも高い精度で求めることができる。)の例。
      • sinとかなんか計算は言語に任せてしまえばよい。関数の連続性が重要。
      • すべての解ではなく、ある範囲の1つの解を求めたいときに二分探索法を使える。
    • 6.7 累積和を使うように思うが、分からない。問題の内容も少し違うような。

Ch07 設計技法(5): 貪欲法

  • 貪欲法とは
    • 1step先のことのみを考えて、最善の選択を繰り返す方法論。
      • 後先を考えず、その場での最善を選択することを繰り返す方法論。
  • 貪欲法が最適解を導くとは限らない
    • 貪欲法によって最適解が導ける問題は、その構造自体によい性質が内包されている可能性が高い。
    • e.g. 最小全域木問題
      • マトロイド性、離散凸性
  • 貪欲法パターン(1): 交換しても悪化しない
    • 最適化問題は、「探索範囲を予め絞れないか」の考察がきわめて有効
      • f(x') >= f(x)が成立する、ある性質Pを満たすx'を、xを変形して得る。
        • e.g. 区間スケジューリング問題
          • 与えられたN個の区間に対して、どの順序で「選ぶ」「選ばない」の選択をしていくかを上手に定めることが肝要
          • 一般に、区間に関する問題に取り組むときは、まず区間の終端時間でソートすると考えやすくなることが多い。
          • 任意の区間の選び方に対し、終端時刻が最も早い区間を選ぶように変更できる→区間スケジューリング問題の解として、「p(終端時刻が最も早い区間)を含むもの」のみに探索候補を絞ってよいことがわかる。
          • 処理
            • A: 残っている区間のうち、終端時刻が最も早いものを選ぶ(貪欲法)
            • B: その選んだ区間と重なる区間を消す
  • 貪欲法パターン(2): 現在がよいほど未来もよい
    • 貪欲法が成立するための単調性
    • Multiple Array
      • 後ろから1ステップずつ考えればよい。
  • まとめ
    • 貪欲法:「後先のことを考えず、次のステップのことのみを考えた場合の最善の選択を繰り返す」
    • 問題の構造に関する考察のポイント
      • 探索範囲を絞ることで、現実的な計算時間で全探索が可能になる
      • 意思決定の順序をある基準にそって固定してよいことがわかるので、その順序に沿ったDPによって最適解が求められる
    • 問題の構造をしっかり考察したうえで、その構造を活かしたアルゴリズムを設計することの面白さ
  • 章末問題
    • 7.1 a[0]..a[N-1]について繰り返す。その中で、b[0]..b[N-1]に対して二分探索でよさそう。
    • 7.2 青の点のx座標を常に最小を選ぶことで、y座標についてのみ考えれば済むようになる。y座標のmaxとなる点rAは、rが選ばれなかった場合や、よりy座標が小さいrA'に対して常に交換できる。そのため、貪欲法を使用できる。
      • 別のものを使うか、使わなかった場合に対してかならず交換できるとき、貪欲法を使用できる。
    • 7.3 締め切り順にソート。あとは各締め切りを使った時間の合計と比較していけばokと思う。

Ch08 データ構造(1): 配列、連結リスト、ハッシュテーブル

  • データ構造を学ぶ意義
    • data structure: データの持ち方
    • クエリ: データ構造に値を挿入して管理したり、データ構造から所望の値を取り出したりするような要求
      • 挿入、削除、含むか判定
    • どのようなデータ構造を用いるかによって、計算時間に大きな差が生じる: 表8.1
  • 配列
    • 大量のデータに対し、1つ1つの要素に気軽にアクセスできるようにするためのデータ構造
    • std::vector, list(Python)
    • 〇: 「データa[i]にアクセスする処理」を高速に行える。ランダムアクセス〇。
    • × : 末尾以外の挿入、削除
    • zero-based: 添え字について
  • 連結リスト
    • 〇: 挿入、削除
    • × : ランダムアクセス×
    • 各要素をポインタでつなげる
    • ダミーノード: 番兵
    • 自己参照構造体を用いる。自分自身の型へのポインタをメンバに持つ構造体のこと。
  • 連結リストの挿入操作と削除操作
    • 挿入の実装
    • 削除の実装
      • 双方向連結リスト
  • 配列と連結リストの比較
    • 連結リストは限られた場面で大きな力。
    • 連結リストは、単体ではなく、様々なデータ構造の部品として活用されることが多い。
    • 要素xの検索処理は、いずれもO(N)
      • → ハッシュテーブル: 平均的にO(1)で検索
      • → 平衡二分探索木: O(logN)で検索
    • ハッシュテーブルは、「i番目の要素」や「次の要素」といった、各要素間の順序に関する情報を持たないデータ構造であることに注意が必要。
  • ハッシュテーブル
    • T[x]: データ構造中に値xが存在するかを表す値(true/false)
    • バケットを汎用化したものがハッシュテーブル。
    • 整数とは限らない一般的なデータ集合Sの各要素に対し、0 <= h(x) < Mを満たす整数h(x)に対応させる。
    • 完全ハッシュ関数を設計し、配列Tを用意することで、「挿入」「削除」「検索」といったクエリそれぞれをO(1)で実行できる。
    • O(M)のメモリ容量を必要とする
    • 文字列の集合に対するハッシュ関数: ローリングハッシュ
    • ハッシュの衝突対策
    • ハッシュテーブルの計算量
      • 単純一様ハッシュの仮定
        • ハッシュテーブルの各要素にアクセスする計算量は、平均的にO(1+N/M)となる。
          • α = N/M: 負荷率
          • α = 1/2程度とすれば、十分にO(1)の計算量を達成できる
    • C++, Pythonにおけるハッシュテーブル
      • std::unordered_set, set
      • set(C++)は、いずれのクエリもO(logN)で十分高速。平衡二分探索木の一種である赤黒木を用いて実現されている
    • 連想配列
      • 連想配列を実現するデータ構造として、ハッシュテーブルを使うことができる
      • 連想配列中の各要素へのアクセスをすべて平均的にO(1)で実行できる
      • e.g. std::unordered_map, dict
      • std::mapは、std::setと同じく多くの場合は赤黒木で実現
  • まとめ
    • 配列、連結リスト、ハッシュテーブルについて、「挿入」「削除」「検索」といったクエリに対するパフォーマンスを比較
    • 処理したいクエリに応じて、適切なデータ構造を用いることが肝要。→ 表8.5
  • 章末問題
    • 8.5 ハッシュテーブルを使えばいけると思う
    • 8.7 片方はハッシュテーブルを使って、もう片方でループ。K - b[i] = a[j]となるaがあるかどうかハッシュテーブルで判定する

Ch09 データ構造(2): スタックとキュー

  • stack, queueの概念
    • 「次々と降ってくるタスクをどのような順序で処理していくか」についての考え方を表現するデータ構造
    • push(x): xを挿入
    • pop(): データ構造から要素を1つ取り出す
    • isEmpty(): データ構造が空か調べる
    • pop時にどの要素を選ぶかにおいて、さまざまなデータ構造を設計する
    • queueではenqueue, dequeue
    • stack: ものが積みあがった状態
      • LIFO
      • e.g. web browserの訪問履歴, text editorのundo系列
    • queue: 古いデータから先に処理。
      • FIFO
      • e.g. 航空券予約のキャンセル待ち処理、印刷機のジョブスケジューリング
  • stack, queueの動作と実装
    • いずれも配列を用いて簡単に実現
    • queueはメモリ管理を効率よく行いながら実装することが大変 → 実践的にはstd::queueの使用が〇
    • stackの動作と実装
      • top(: 最後に挿入された要素の添え字の次の添え字) を用いる
        • 「スタックに格納されている要素数」も表す
    • queueの動作と実装
      • 両端が開いている
      • リングバッファ
  • まとめ
    • stack, queueは、コンピュータサイエンス全域で登場する基本的な考え方。
    • 重要な応用例: グラフ探索。DFSやBFSという重要なグラフ探索技法を設計できる。
  • 章末問題

Ch10 データ構造(3): グラフと木

  • グラフ: 対象物の関係性を数理的に表すもの
    • 連結でサイクルを持たないものは木
    • 木の形状を用いたデータ構造として有用なものを見る
  • グラフ
    • グラフの考え方
      • 対象物の関係性を表す
      • 対象物を〇(頂点、vertex)、対象物間の関係を線(辺、edge)で表す
      • グラフの描画は一意ではない
      • グラフGを、頂点の集合Vと、辺の集合Eの組として定義する
        • G = (V, E)
        • 各辺e ∈ E を2つの頂点vi, vj ∈ Vの組と定義して、e = (vi, vj)と表す
      • 隣接(adjacent): 辺eで結ばれていること。隣接した両端は端点(end)という。
      • 接続(incident): 辺eは両endに接続しているという。
      • 重み付きグラフ: 各辺eに実数値または整数値をとる重みが付随したグラフ
      • 多重辺: 複数本の辺が同一頂点間を結ぶ
      • 自己ループ: 両endが同じとなる辺e
      • 単純グラフ: 多重辺も自己ループも持たないグラフ
    • 有向グラフと無向グラフ
      • 有向グラフ: 一方通行の道路といったものをモデル化するのに有効
        • (vi, vj)と(vj, vi)を区別する
    • ウォーク、サイクル、パス
      • いずれも部分グラフ(subgraph)の一種であり、重要
      • ウォーク(walk): sからtへと隣接する頂点をたどっていくことで到達できるとき、s-t walk(s-t路)という。
        • s: 始点、t: 終点
      • サイクル(閉路): 始点と終点が同じウォーク
      • パス(道): 同じ頂点を2度以上通らないウォーク
      • 有向グラフにおいては、始点から終点への方向に沿っている必要がある
      • 長さ: 重み付きグラフでは、それらに含まれる辺の重みの総和。重みなしグラフでは辺の本数。
    • 連結性
      • 連結: 無向グラフGの任意の2頂点s, tに対してs-tパスが存在するとき、Gは連結であるという。
      • 図10-7: 2つのグラフではなく、全体で1つの連結でないグラフが描かれている
      • 連結成分: Gを構成するそれぞれの連結グラフ
      • 連結とは限らないグラフに関する問題を解くときに、まず連結グラフに対する結果を求めてから、それを各連結成分に対して適用するとうまくいくことが多々ある。
        • e.g. 二部グラフ判定
  • グラフを用いる定式化の例
    • グラフは非常に強力な数理科学的ツール
    • グラフを用いてモデル化することで、グラフに関する問題として捉えなおすことができる
    • 対象物をグラフを用いて定式化する
    • ソーシャルネットワーク
      • small world現象
      • コミュニティの検出、影響力の高い人を検出、ネットワークの情報伝播力を解析
    • 交通ネットワーク
      • 道路: 交差点がグラフの頂点、鉄道: 駅が頂点
      • 各頂点間の長さは平均的に大きい
      • 平面的。平面グラフ: どの2本の辺も交差しないように平面上に描くことができる
    • ゲームの局面遷移
      • グラフの探索で、必勝法がわかる
    • タスクの依存関係
      • タスクの依存関係をグラフとして整理→適切なタスク順序を決定、クリティカルパスを求める
  • グラフの実装
    • コンピュータ上でグラフを扱うためのデータの持ち方、データ構造
      • 隣接リスト表現と隣接行列表現。隣接リスト表現を扱う
    • 隣接リスト表現
      • 各頂点について、辺でつながる頂点をリストアップ
      • G[v]がvの隣接頂点を表す
      • 入力
        • N(頂点数) M(辺数) と、各辺が渡される
  • 重み付きグラフの実装
    • 重み付きの辺を表す構造体Edgeを用意
    • G[v]がvに接続している辺の集合を表す
    • 最短路問題に使う
    • 無向グラフG=(V, E)が木である: Gが連結で、かつサイクルを持たない
    • 根付き木(rooted tree) ←→ 根なし木(unrooted tree)
      • 特定の1つの頂点を根(root)
      • 頂点に接続している辺が1本のみのもの: 葉(leaf)
      • 親、子、兄弟
    • 部分木と、木の高さ
      • 部分木のroot以外の頂点を子孫
    • 根付き木上の2頂点のパスはただ1つに決まる(根なしも同様)
      • 根とvを結ぶパスの長さ: vの深さ。根の深さは0
      • 根付き木の各頂点の深さの最大値: 木の高さ
  • 順序木と二分木
    • 根付き木の構造を用いて、多彩なデータ構造を考えられる
      • ヒープ、二分探索木、Union-Find
    • 順序木と二分木
      • 根付き木において、各頂点vの子頂点の順序を考慮するとき、特に順序木という
        • 兄と弟を区別
        • 表現方法
          • 親頂点へのポインタ、{各子頂点へのポインタを格納した可変長配列/ 「第1子」を表す頂点へのポインタ、「次の弟」を表す頂点へのポインタ}
        • すべての頂点に対して高々k個の子頂点しか持たないものをk分木という
          • 二分木において、左側の子頂点を根とした部分木を左部分木、右は右部分木
          • 二分木は、計算量解析において好都合な形状→様々なデータ構造において二分木の構造を採用
            • ヒープ、二分探索木
    • 強平衡二分木
      • 根付き木の構造を持つデータ構造は、多くの場面で、各クエリを処理する計算量がO(h)(hは木の高さ) → 高さをできるだけ抑える
      • → 強平衡二分木: 二分木であり、すべての葉の深さが高々1しか違わないもの
      • 頂点数をNとして、高さがO(logN)
      • すべての葉の深さが等しい二分木: 完全二分木
  • 二分木を用いるデータ構造の例(1): ヒープ
    • 正確には二分ヒープを扱う
    • ヒープとは
      • 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
        • 頂点vの親頂点をpとしたとき、key[p] >= key[v]が成立する
        • 木の高さをhとしたとき、木の深さh-1以下の部分については、完全二分木を形成している
        • 木の高さをhとしたとき、木の深さhの部分については、頂点が左詰めされている
      • → ヒープは特に強平衡二分木となっている → 様々なクエリをO(logN)で処理できる
        • 挿入、最大値の取得、最大値の削除が〇
        • 値の検索は× → 平衡二分探索木を使う
    • ヒープの実現方法
      • 配列を用いて実現
      • ヒープの深さdの各頂点を配列の2d-1,...,2d+1-2番目に対応
      • 関係性
        • 配列中の添字がkである頂点の左右の子頂点の、配列中の添字がそれぞれ2k+1, 2k+2
        • 配列中の添字がkである頂点の親頂点の、配列中の添字が[(k-1)/2]
    • ヒープのクエリ処理
      • 挿入
        • 挿入した値をキー値にもつ頂点とその親である頂点との間でヒープの条件を満たした状態になるまでキー値の交換を繰り返す
      • 削除
        • 最後尾の頂点を根に持ってくる。その後は挿入と同様、ヒープの条件を満たすまで子の大きい値と交換していく。
    • ヒープの実装例
    • O(N)時間でヒープの構築ができる
  • 二分木を用いるデータ構造の例(2): 二分探索木
    • 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
      • 任意の頂点vに対し、vの左部分木に含まれるすべての頂点v'に対して、key[v]>=key[v']が成立し、vの右部分木に含まれるすべての頂点v'に対して、key[v]<=key[v']が成立する
    • いずれのクエリ処理も、木の高さ分の計算量
    • 平衡二分探索木にすることで、O(logN)でクエリを処理できる。ヒープの機能の1つである最大値を取得する処理もO(logN)となる。
      • 実際はO記法で省略される定数部分が大きいので、ヒープで足りればヒープが簡便で〇
  • まとめ
    • グラフは、対象物の関係性を表すことができる強力な数理科学的ツール
    • グラフとして定式化して、問題を見通す
    • 特殊なグラフとしての木
      • 順序木は、連結リストの構造をより豊かにしたもの
      • → ヒープや二分探索木などの多彩なデータ構造を設計
  • 章末問題
    • 10.5 サイクルを持たないのが木

Ch11 データ構造(4): Union-Find

  • グループ分けを効率的に管理するデータ構造
  • 根付き木の構造を用いる
  • Union-Findとは
    • グループ分けを管理するデータ構造
    • 以下のクエリを高速に処理する
      • issame(x, y): 要素x, yが同じグループに属するかどうか調べる
      • unite(x, y): 要素xを含むグループと、要素yを含むグループとを併合する
  • Union-Findの仕組み
    • 1つ1つのグループが根付き木を構成するようにして実現
    • ヒープや二分探索木とは異なり、二分木である必要はない
    • root(x)
      • 要素xを含むグループ(根付き木)の根を返す
      • O(h)
      • issame(), unite()を実現
  • Union-Findの計算量を削減する工夫
    • union by size(or union by rank)
    • 経路圧縮
    • 実際上はO(1)とみなせる
  • union by size
    • 頂点数の小さい方の根付き木を、大きい方に併合する
    • → 各根付き木の高さをO(logN)で抑えられる
    • 頂点xの深さが1増加するときは、頂点xを含む根付き木の頂点数も2倍以上になる
    • サイズの小さいほうのデータ構造を大きいほうに併合するという手法は、データ構造を併合する場面で一般的に使える
  • 経路圧縮
    • xから上へと進んでいって根に到達するまで経路中の各頂点に対し、その親を根に張り替える
  • Union-Findの実装
    • 構造体として実装
    • par, siz
  • Union-Findの応用: グラフの連結成分の個数
    • 連結成分をグループとして扱う
    • root(x) == xを満たすxを数える
    • O(|E|α(|V|))
  • まとめ
    • Union-Findはグループ分けを効率的に管理するデータ構造
    • シンプルな実現方法、奥が深い
    • 適用範囲が広い
    • グラフに関する問題は、Union-Findによっても解くことができる
    • クラスカル法の高速化のためにも使う
  • 章末問題
    • 11.1 各辺でループ。各辺のみつながないUnion-Findで、連結成分の個数が2つになればその辺が橋となる
    • 11.2 https://drken1215.hatenablog.com/entry/2019/03/03/224600
      • グラフのクエリ問題で辺を削除するのはとても扱いづらい
      • 辺を追加すると読み替える
      • 求める値が異なる
      • issame(a, b)=trueだったらcontinue, falseなら連結成分の個数が減る
      • グループ分けの問題なので、Union-Findが使える
    • 11.3 道路についてと鉄道についてそれぞれのUnion-Findを持つ
      • サイズを求めればそれぞれのみで行ける頂点の個数が分かる
    • 11.4 重み付きUnion-Findを使う

Ch12 ソート

  • 分割統治法、ヒープなどのデータ構造、乱択アルゴリズムの考え方など、さまざまなアルゴリズム技法を学ぶことができる題材
  • ソートアルゴリズムに用いられるアルゴリズム技法を学ぶ
  • ソートとは
    • 与えられたデータの列を、所定の順序に従って整列
    • 実用上とても重要な処理
    • 前処理としても使われる
    • 実用的にも理論的にも重要な処理 → 多数のアルゴリズムがある
  • ソートアルゴリズムの良し悪し
    • in-place性と安定性
      • 以下の尺度で良し悪しを評価
        • 計算量
        • in-place性(追加で必要な外部メモリ容量)
        • 安定性(安定ソートかどうか)
      • 基本的なアルゴリズムのため使用機会が多い&使用時のコンピュータの環境も多岐にわたる特徴がある
        • → 計算量だけでは評価しきれない
      • in-place
        • 外部メモリをほとんど必要とせず、与えられた配列内部のswap操作でソート処理を実現
        • e.g. 挿入ソート、ヒープソート
        • 組込系などのコンピュータ資源の限られた環境では〇
      • 安定
    • どのソートアルゴリズムがよいか
      • ほとんどの場面で、各言語の標準ライブラリを用いれば十分
      • ソートの使いどころの習熟が重要
  • 挿入ソート
    • 動作と実装
      • 左からi枚がソートされている状態から、i+1枚目がソートされている状態にする
    • 計算量と性質
  • マージソート
    • 動作と実装
      • 分割統治法を活用したソートアルゴリズム
        • 配列を半分に分割し、左右それぞれを再帰的にソートしておき、その両者を併合する
      • 右側の外部配列を降順にして左側の外部配列とつなげることで、つなげた配列の両端を比較して小さい方を抜き出すことを繰り返すだけで済むようになる。
        • → 左右の外部配列が空かどうか確認不要になって〇
    • 計算量と性質
      • O(NlogN)
      • not in-place
        • → 組込系など、ソフトウェアの移植性を重視しつつアルゴリズムを常に高速に動作させたい場合には採用されにくい
        • ただし、必要なメモリ容量は入力受け取りに要するメモリ容量の高々定数倍なので、問題ない場面も多い
      • 安定〇
    • 計算量解析の詳細
      • bk = N
      • マージソートではa=b=2なのでO(NlogN)
      • 分割統治法の計算量を分解して考えられる
        • 再帰の根の部分において、併合作業に要する計算量O(N) ← a < b
          • 再帰の分岐数が小さくなることで最終的に根の部分が支配的になるため。
        • 再帰の根からの深さが1の部分において、併合作業に要する計算時間 ← a = b
          • 両者が均衡することで、木の各深さにおける計算量がすべてO(N)。それに木の高さO(logN)をかける。
        • 再帰の葉の部分に要する計算時間の総和のオーダーO(Nlogba) ← a > b
          • 再帰の分岐数が大きくなることで最終的に葉の部分が支配的になるため。
        • 図12-5
  • クイックソート
    • 動作と実装
      • 配列の中から適当な要素pivotを選び出し、配列全体をpivot未満のグループとpivot以上のグループに分割して、それぞれを再帰的に解く
      • 添え字を2つ使って、いったん選んだpivotを右端に移し、配列を左から順に走査
      • a[j]がpivotより小さかったら、a[i]とa[j]をswapしてiを進める
      • 最後にa[i]とpivotをswap
      • 外部配列を必要とせずin-place
    • 計算量と性質
      • 最悪時間計算量はθ(N2)
        • ただし、1:99でも、常に1:99ならO(NlogN)になる程度
      • 実用上はマージソートより高速に動作
      • ヒープソートとのハイブリッド方式であるイントロソートをベースとした実装がC++にある
    • 乱択クイックソート
      • ここまでのクイックソートは、平均的なケースには高速だが、悪意あるケースに弱い
      • → 乱択クイックソート
      • 入力分布に偏りがある場面では、乱択化をする
      • → O(NlogN)
      • 1 + 1/2 + ... + 1/N = O(logN)を用いて解析
        • i, i+1, ... , j-1, j番目の要素の中でi, j番目のどちらかの要素が最初に選択される確率を使う
  • ヒープソート
    • 最悪でも計算量はO(NlogN)
    • 安定ではなく、平均的な速度ではクイックソートに劣る
    • ただし、ヒープ自体が重要なデータ構造
    • ソートしたい配列自体をヒープにすることで、in-placeになる
  • ソートの計算量の下界
    • 比較ソートアルゴリズム: ソート順序が入力要素の比較にのみ基づいて決定される
      • 最悪の場合は、Ω(NlogN)回の比較が必要
    • 2h >= N!から求めていく
  • バケットソート
    • 比較ソートアルゴリズムではない
    • ソートしたい配列aの各要素値は0以上A未満の整数値であるという仮定の下で、O(N+A)
    • バケットソートのアイディアを示す配列
      • num[x]←配列a中に値xを持つ要素が何個存在するか
    • AがA=O(N)であると考えられる程度の小ささである場合に限られる
    • 累積和を取り、値a[i]が全体の中で何番目に小さいかを求める
  • まとめ
    • 分割統治法、その計算量解析、乱択アルゴリズムの考え方など、さまざまなアルゴリズム技法を扱った
      • ソートに限らず、数多くの問題の解決に役立てられる
    • ソート自体もさまざまなアルゴリズムの前処理としてしばしば有効
      • e.g. 配列の二分探索、貪欲法、コンピュータグラフィックス
    • ソートは数多くのアルゴリズム設計において基本的な役割を果たす
  • 章末問題
    • 12.1 インデックスと値の組を配列で持つ。値でソート。ソート後のインデックスを入れる。元のインデックスでソート。
      • ソートする。それぞれの値で二分探索する。どちらもO(NlogN)。
    • 12.2 金額と本数の組を配列で持つ。金額でソートして足していけばOK。
    • 12.5 http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-06.pdf
      • たぶんこれ
      • 軸要素の選び方を工夫することで、次の反復での要素数を3/4n以下とできる
    • 12.6 もう1回同じ問題に当たったら考えよう

Ch13 グラフ(1): グラフ探索

  • グラフ探索を学ぶ意義
    • あらゆるグラフアルゴリズムの基礎
    • 単にグラフに関する問題を解決できるだけでなく、さまざまな対象物に対する探索を見通しよく扱えるようになる
    • ウォーク、サイクル、パスや連結性も自在に扱える
  • DFS,BFS
    • グラフ探索の基本形
      • 問題設定: グラフ上の代表的な1つの頂点s∈Vを指定して、sから辺をたどって到達できる各頂点を探索する
      • stack(DFS), queue(BFS)を用いて実現
      • todo, seenを管理する
      • seen[x] = trueならばその頂点xを飛ばすのが重要
  • 再帰関数を用いるDFS
    • 簡潔に実装できる
    • 再帰関数を用いることで、「行きがけ順」「帰りがけ順」という重要な概念も明快なものになる
  • 「行きがけ順」と「帰りがけ順」
    • 頂点vをtodoから取り出すタイミングと、再帰関数dfs(G, v)を呼び出すタイミングが同じ ← これが行きがけ順
    • 再帰関数dfs(G, v)を抜けるタイミング ← 帰りがけ順
    • 行きがけ順では、vの子孫となる頂点はすべてvよりも後に登場
    • 帰りがけ順では、vの子孫となる頂点はすべてvよりも前に登場
      • DAGのトポロジカルソート順を求める際にも重要
  • 最短路アルゴリズムとしてのBFS
    • 探索の始点となる頂点sから、各頂点への最短路を求めるアルゴリズムともみなせる
    • dist, queで管理
    • グラフGの任意の辺E=(u, v)について、dist[u]とdist[v]の差は1以下
    • BFSはdistの値が小さくなるところから順に探索するアルゴリズム
  • DFS, BFSの計算量
    • グラフG=(V, E)に対するアルゴリズムの計算量を述べるときは、通常は、頂点数|V|, 変数|E|の2つを入力サイズとする
    • 密グラフ: |E|=θ(|V|^2)
      • e.g. 完全グラフ: すべての頂点間に辺があるような単純グラフ
    • 疎グラフ: |E|=O(|V|)
      • e.g. 各頂点について接続している辺の本数が高々k本であるようなグラフ
    • DFS, BFSとも、O(|V| + |E|)
    • グラフを入力として受け取るのと同等の計算量で探索可能
  • グラフ探索例(1): s-tパスを求める
    • 頂点sを始点としたグラフ探索。その過程で頂点tを訪問したかどうかを調べることで解ける
  • グラフ探索例(2): 二部グラフ判定
    • 二部グラフ: グラフを左右のカテゴリに分割して、同じカテゴリ内の頂点間には辺がない状態にできること
    • 白に隣接した頂点はすべて黒に塗る。逆も同じ。
    • 両端点が同色であるような辺が検出されたら、二部グラフでないことが確定する ←→ 探索が終了すれば二部グラフ
  • グラフ探索例(3): トポロジカルソート
    • 与えられた有向グラフに対し、各頂点を辺の向きに沿うように順序づけて並び替えること
    • 応用例: makeの依存関係解決処理
    • 与えられるグラフGが有向サイクルを持たないことが必要十分条件 ← このような有向グラフをDAG(Directed Acyclic Graph)と呼ぶ
    • トポロジカルソート順は一般には一意ではなく、複数通り考えられる
    • 再帰関数を用いるDFSに、ほんの少し手を加えるだけで実現可能
    • idea: DFSにおける再帰関数を抜けた順序に頂点を並べ、それを逆順に並べ直すことでトポロジカルソート順が得られる
  • グラフ探索例(4): 木上の動的計画法
    • 根なし木に対しても便宜的に根をどれか1つ決めて根付き木とすることで、しばしば見通しが良くなる
      • 木に根を指定することで、「系統樹」としての構造が生まれる
    • ある1つの頂点を決めて根にすることで形成される根付き木の形状を求める問題を考える
      • 各頂点vに対して以下の値を求める
        • 頂点vの深さ
        • 頂点vを根とした部分木のサイズ(部分木に含まれる頂点数)
      • 子情報をまとめる処理のため、BFSよりDFS
      • 木がサイクルを持たないことを利用して、実装を簡潔にする
        • 根なし木を根付き木としたときの各頂点の深さを求める
      • 部分木サイズの漸化式
        • subtree_size[v] = 1 + Σc:(vの子頂点)subtree_size[c]
        • 1は頂点v自身
        • 頂点vの各子頂点cに対してsubtree_size[c]が確定している必要がある
        • → 帰りがけ時に実行する必要がある
      • 子頂点についての情報を用いて、親頂点についての情報を更新する: DPを木に対して適用
      • O(|V|)
    • 各頂点の深さ: 行きがけ時に求めた
    • 各頂点を根としたときの部分木のサイズ: 帰りがけ時に求めた
    • 行きがけ順を意識した処理は「親頂点についての情報を子頂点に配る」のに適していて、帰りがけ順を意識した処理は「子頂点の情報を集めて親頂点の情報を更新する」のに適している
  • まとめ
    • グラフ探索の技法として、DFS, BFS。あらゆるグラフアルゴリズムの基礎となる重要なもの。
      • 最短路アルゴリズムはBFSを一般化したもの
      • ネットワークフローでは、サブルーチンとしてグラフ探索技法
  • 章末問題

Ch14 グラフ(2): 最短路問題

  • グラフの各辺に重みがある場合の最短路問題に対する解法を見る
  • → 現実世界の問題への応用範囲が飛躍的に広がる
  • DPや貪欲法の応用がある
  • 最短路問題とは
    • グラフ上で長さが最小の路(ウォーク)を求める問題
    • l(e): 各辺の重み
    • l(W): 路W(walk)の長さ
    • l(C): 閉路(cycle)Cの長さ
    • l(P): 道P(path)の長さ
    • カーナビや鉄道の乗換案内サービスという応用が広いだけでなく、理論的にも重要な問題
    • 重み付き有向グラフ
      • 一般性が高い考察対象
    • 単一始点最短路問題
      • 各頂点への最短路を重ね合わせると頂点s(=0)を根とした根付き木になる
    • 負辺と負閉路
      • 負閉路はいくらでも路長を小さくできる
      • 負閉路を持たないか、始点から負閉路に到達できない、または負閉路から頂点vに到達できない場合は、最短路を求められる
  • 最短路問題の整理
    • DAG上の最短路問題を考えるときは、「どの辺から順に緩和していけばよいか」があらかじめ自明であった
    • 閉路を持つグラフでは、どの辺から順に緩和していけばよいかが明らかでない → より高度なアルゴリズムが必要
      • ベルマン・フォード法: 負の重みの辺も含むグラフ
      • ダイクストラ法: 辺の重みがすべて非負なグラフ
      • DP: DAG
      • 重みなしグラフ: BFS
  • 緩和
    • DPで導入した緩和。chmin。
    • 更新したかどうかをboolで返すようにする
    • いずれの最短路アルゴリズムも、始点sから各頂点vへの最短路長を推定する値d[v]を管理し、各辺についての緩和を繰り返していくもの
    • 図14-4: 最短路を求めることを、ひもをピンと張ることと解釈する
    • 緩和の持つ意味
      • 図14-5: 数直線上にプロット
      • 各節点を少しずつ節点s方向へと引き寄せていくアルゴリズム
      • 「どの辺に対して緩和を行っても節点の位置が更新されない状態」となったならば、アルゴリズムを終了できる
  • DAG上の最短路問題: 動的計画法
    • DAGにおける緩和処理の順序のポイント
      • 各辺e=(u, v)に対して緩和処理を実施するときには、頂点uに対するd[u]が真の最短路長に収束している
      • ↑ トポロジカルソートで担保。緩和すべき辺の順序を明らかにできる
  • 単一始点最短路問題: ベルマン・フォード法
    • 有効閉路を含む有向グラフに対しても最短路を求めることのできるアルゴリズムを考える
    • もし始点sから到達できる負閉路が存在するならばその旨を報告し、負閉路が存在しないならば各頂点vへの最短路を求めるアルゴリズム
    • 辺の重みがすべて非負であることが保証されている場合は、ダイクストラ法が〇
    • アイディア
      • 「各辺に対して一通り緩和する(順序は不問)」という操作を、最短路長推定値d[v]が更新されなくなるまで反復する
      • 高々|V|-1回の反復で、d[v]の値が真の最短路長d[v]に収束する
      • → 各辺に対する緩和をO(|V|)回反復するため、O(|V||E|)
      • |V|回目の反復時にある辺e=(u, v)が存在して、辺eに関する緩和によってd[v]の値が更新されるとき、始点sから到達可能な負閉路がある
    • 実装
      • 更新が発生しなければ反復を打ち切る
    • 正当性
      • 路を道にしても長さは減少しない
  • 単一始点最短路問題: ダイクストラ
    • すべての辺が非負であることが分かっている場合には、より効率的
    • 2種類のダイクストラ
      • 実現するためのデータ構造として何を用いるかによって、計算量が変わる
        • 単純に実装した場合の、計算量O(|V|^2)の方法
        • ヒープを用いる場合の、計算量O(|E|log|V|)の方法
      • 密グラフでは前者が〇、疎グラフでは後者が〇
    • 単純なダイクストラ
      • 貪欲法に基づいたアルゴリズム
      • 各辺が非負と分かっている場合は、最短路長推定値d[v]を動的に更新していく過程で、緩和を行うべき頂点順序が自動的に決まる構造になる
      • 「すでに最短路が求められていることが確定している頂点の集合S」を管理する
        • 「まだSに含まれていない頂点vのうち、d[v]の値が最小の頂点」に着目(始点とする頂点を探す)
        • → 頂点vをSに挿入し、頂点vを始点とする各辺について緩和
    • 直感的なイメージ
      • 「各節点を左から順にひもをピンと張っていく動作」をアルゴリズムとして実現したもの
      • 右手のつまみを選び、節点vとほかの節点間のひもをピンと張っていく
    • 正当性
    • 疎グラフの場合: ヒープを用いた高速化
      • 疎グラフであればO(|V|log|V|)
      • ダイクストラ法の高速化を目指す部分
        • 使用済みでない頂点vのうち、d[v]の値が最小の頂点vを求める部分
      • ヒープの各要素
        • 使用済みでない頂点v
        • その頂点vにおけるd[v]
      • 更新後のd[v]の値を新たにヒープに挿入する
        • 古いd[v]はごみとして残るだけなので問題ない
        • ヒープサイズは高々|E|
      • 最良優先探索
      • 取り出したdよりdist[v]が小さいときは、(d, v)はごみ
      • https://cpprefjp.github.io/reference/queue/priority_queue.html
        • 要素の型、内部コンテナ、昇順降順を指定する
  • 全点対間最短路問題: フロイド・ワーシャル法
    • DPに基づいて解く
    • O(|V|^3)
    • フロイド・ワーシャル法におけるDP
      • dp[k][i][j]←頂点0,1,...,k-1のみを中継地点として通ってよいとした場合の、頂点iから頂点jへの最短路長
      • dp[k][i][j]の値を用いて、dp[k+1][i][j]の値を更新することを考える
      • 実際はdpは2次元でよく、kからk+1の更新はin-place
      • dp[v][v]<0となる頂点vが存在すれば、負閉路がある
    • for文の構造は、トロピカル線形代数と呼ばれる分野で、ある種の行列の累乗計算を実現したものとみなせる
  • 参考: ポテンシャルと差分制約系
    • ポテンシャル: 各節点間がピンと張られているとは限らない場合において、各節点の位置関係としてあり得るもの
      • 各頂点vに対して値p[v]が定まっているとき、任意の辺e=(u, v)に対して、p[v]-p[u]<=l(e)を満たすようなp
    • 最短路問題の最適性の証拠
      • 頂点sから頂点vへ到達可能であるとする。このとき、d*[v]=max{p[v]-p[s]|pはポテンシャル}が成立する
        • pをポテンシャルとしてp[v]-p[s]のmaxを求める問題が、sを始点としてvへの最短路長を求める問題の双対問題となっていることを表す
      • → 差分制約系の最適化問題に対し、適切なグラフを構築して最短路アルゴリズムを適用して解くことができることがわかる
  • まとめ
    • グラフ上の最短路を求める問題の解放として、古典的によく知られているものをまとめた章。
    • DP、貪欲法、グラフ探索、ヒープなどの、アルゴリズム設計技法・データ構造が活躍
    • 最短路問題は実用上重要な問題なだけでなく、理論的に重要な位置づけ
  • 章末問題

Ch15 グラフ(3): 最小全域木問題

  • ネットワーク設計において基本的な問題の1つ
  • いくつかの通信拠点をすべて通信用ケーブルでつなぎ,すべての建物間で通信できるようにしたいとする.これを最小コストで実現する方法を問う問題.
  • クラスカル法で解く.
    • 貪欲法に基づく.
      • 構造自体によい性質が内包されている.
      • きわめて深淵で美しい理論が背後にある問題.
  • 最小全域木問題とは
    • w(e): グラフの各辺の重み
    • Gの部分グラフであって木であるもののうち,Gの全頂点をつなぐものを全域木(T)と呼ぶ.
      • w(T): 重みは,w(e)の総和.
    • 最小全域木問題とは,重みが最小の全域木を求める問題
      • 最小の長さのケーブルで全地点を接続する問題.
  • クラスカル
    • 最小全域木を求めるクラスカル
      • 辺集合Tを空集合とする.
      • 各辺を重みが小さい順にソートして,e0,e1,...,eM-1とする.
      • 各i=0,1,...,M-1に対して:
        • Tに辺eiを追加したときに,サイクルが形成されるならば:
          • 辺eiを破棄
        • サイクルが形成されないならば:
          • Tにeiを追加
      • Tが求める最小全域木となる.
  • クラスカル法の実装
    • グラフGの各辺を,辺の重みが小さい順にソート.
    • Union-Findを用いることで,効率的に実現.
      • 開始時点では,Union-Findの各頂点が単独で別々のグループを形成している状態とする.
      • 新たな辺e=(u,v)を追加するとき,Union-Find上の点u',v'について,unite(u',v')を実施する
        • サイクルが形成されてしまうかどうかを,u'とv'が同じグループに属するかで判定できる
      • O(|E|log|V|)
  • 全域木の構造
    • クラスカル法は,自然な貪欲法に基づくアルゴリズムだが,最適解が求められる理由・正当性を見る.
    • カット
      • グラフG=(V,E)のカットとは,頂点集合Vの分割(X,Y)
      • X,Yはともに非空集合
      • X∪Y=V, X∩Y=∅を満たす必要がある.
      • Xに含まれる頂点とYに含まれる頂点を結ぶ辺をカット辺
      • カット辺全体の集合をカットセット
    • 基本サイクル
      • 全域木TとTに含まれない辺eで形成されるサイクル
      • 基本サイクル上の別の辺fを1つ取って新たな全域木T'を作る.
        • fは(基本)サイクル上なので,T'も全域木となる.
      • 最小全域木の基本サイクルに関する性質
        • 連結な重み付き無向グラフGにおいて,Tを最小全域木とする.Tに含まれない辺eを1つとって,Tとeに関する基本サイクルをCとする.このとき,Cに含まれる辺のうち,辺eは重みが最大の辺となっている.
    • 基本カットセット
      • Tに含まれる辺eを1つとり,eを取り除くことによって分割される2つの部分木の頂点集合をX,Yとする.
      • (X,Y)のカットに伴うカットセットを,Tとeに関する基本カットセットと呼ぶ.
      • 最小全域木の基本カットセットに関する性質
        • 連結な重み付き無向グラフGにおいて,Tを最小全域木とする.Tに含まれる辺eを1つとって,T,eに関する基本カットセットをCとする.このとき,Cに含まれる辺のうち,辺eは重みが最小の辺となる.
  • クラスカル法の正当性
    • 最小全域木の最適性条件
      • 以下の2条件が同値
        • Tは最小全域木である
        • Tに含まれない任意の辺eに対して,Tとeに関する基本サイクルにおいてeの重みは最大
      • クラスカル法によって求められる全域木はBを満たすので,最小全域木
    • 局所最適解
    • 全域木間での辺の交換
      • 連結な重み付きグラフG=(V,E)において,2つの相異なる全域木をS,Tとする.Sには含まれるがTには含まれないeを1つとる.このとき,Tに含まれるがSには含まれない辺fが存在して,S'=S-e+fも全域木となる.
      • S,eに関する基本カットセットと,T,eに関する基本サイクルにともに含まれる辺のうちeでない辺がf.
    • → SをS’とすることでTに近づく
    • w(S)>=w(S')>=w(S'')>=...>=s(T)
    • ここまでの議論はマトロイドに一般化できる.
      • マトロイド: 離散的な凸集合を表すもの
      • マトロイドの概念をさらに拡張したM凸集合を考えることもできる.
      • → 離散凸解析
  • まとめ
    • ネットワーク設計において最も基本的な問題の1つである最小全域木問題を解いた.
    • 最小全域木問題は,背後に非常に深淵で美しい理論を持つ.
      • 最小全域木の最適性条件を,全域木の局所的な性質のみを用いて記述できることが,最小全域木問題の持つ構造の豊かさを示す.
  • 章末問題

Ch16 グラフ(4): ネットワークフロー

  • ネットワークフロー理論: 「きれいに解ける」問題の代表
    • グラフアルゴリズムの中でも特に流麗で鮮やかな体系を持つ.
    • 輸送ネットワークにおけるトラフィックを考える問題を1つの動機として発展したが,さまざまな分野の問題に応用され,豊かな成果.
  • ネットワークフローを学ぶ意義
    • 「効率よく多項式時間で解ける問題」を象徴する存在.
    • 興味深い性質や構造がある.
    • 多彩な応用
      • 連結度,二部マッチング,プロジェクト選択
    • ある程度の制約条件までは表現できる柔軟性もある.
    • ネットワークフローで解ける問題を見逃すのはもったいない.
    • 最大流問題と最小カット問題を見る.
  • グラフの連結度
    • 最大流問題において,各辺の容量を1とした特殊なケース.
    • 辺連結度
      • 頂点sから頂点tに対して互いに辺を共有しないs-tパスの本数の最大値が,グラフの2頂点s,tに関する辺連結度.
      • グラフネットワークの頑健性を評価するもの.
      • 互いに辺を共有しないこと: 辺素(edge-disjoint).
      • カットセットの辺の本数: カットの容量→辺連結度になる.
    • 最小カット問題
      • (辺の容量が1の場合)有向グラフG=(V,E)と2頂点s,t∈Vが与えられる.s-tカットのうち,容量が最小のものを求める.
      • 辺連結度に関する問題の弱双対性
        • 辺素なs-tパスの最大本数<=s-tカットの最小容量.
        • 任意のs-tカットを考えて,c(S,T)>=kであることを見る.
        • 意味(s-tカットの容量がちょうどkのとき)
          • 辺素なs-tパスの最大本数=k
          • s-tカットの最小容量=k
      • → 辺連結度に関する問題の強双対性
        • 辺素なs-tパスの最大本数=s-tカットの最小容量
        • 辺連結度を求める問題と最小カット問題は双対
    • 辺連結度を求めるアルゴリズムと強双対性の証明
      • フォード・ファルカーソン法を,各辺の容量が1のグラフに対して適用したものを見る
      • 「s-tパスを追加でとれるならとる」という処理を繰り返す,という貪欲法に基づいたアルゴリズムによって求められる.
      • 残余グラフを考える
        • 残余グラフ: s-tパスをとったとき,パス上の各辺に対して逆向きの辺を張りなおしたグラフ
      • 2頂点s-t間の辺連結度を求めるアルゴリズム
        • パスの本数を表す変数をf(←0)と初期化する.
        • 残余グラフG'をもとのグラフGで初期化する.
        • while G'において,s-tパスPが存在するならば:
          • f++
          • G'をPに関する残余グラフに更新
        • fが求める連結度
      • 図16-6: k本の辺素なs-tパスを得るとき,容量kのカットを構成できることを示す.
        • →c(S,T)=k
      • kが最大でもO(|V|)であり,各反復においてs-tパスを見つける処理はO(|E|)→全体でO(|V||E|)
  • 最大流問題と最小カット問題
    • 各辺eが容量c(e)をもつ一般の場合の最大流問題を考える
    • 各辺eに対して流量を表す値x(e)があって,以下の条件を満たすとき,xをフロー(許容フロー)という.
      • 任意の辺eに対して,0<=x(e)<=c(e).
      • 任意のs,t以外の頂点vにおいて,vに入る辺eに対するx(e)の総和と,vから出ていく辺eに対するx(e)との総和が等しい.
    • 各辺eに対するx(e)を辺eの流量
    • 頂点sから出ていく辺eに対するx(e)の総和を,フローxの総流量
    • 総流量が最大のフローを最大フロー
    • 最大フローを求める問題を最大流問題
    • フローの性質
      • 辺素: 容量が1の辺に2以上の流量を流せないことを意味する
      • 任意のカット(S,T)に対し,SからTへ出ていく各辺eの流量x(e)の総和から,TからSへ入ってくる各辺eの流量x(e)の総和を引いた値が,フローxの総流量に一致する.
        • どこを観察しても流量が一定
    • 最小カット問題との双対性
      • c(S,T): s-tカット(S,T)に含まれる辺eの容量c(e)の総和(s-tカット(S,T)の容量).
      • 最小カット問題
        • 容量つき有向グラフG=(V,E)と2頂点s,t∈Vが与えられる.s-tカットのうち,容量が最小のものを求める.
      • 最大流最小カット定理
        • 最大フローの総流量=s-tカットの最小容量
        • 「残余グラフ上で見つけたs-tパス上にフローを流せるだけ流す」という処理を,残余グラフ上にs-tパスがなくなるまで繰り返すことで証明する.
    • フォード・ファルカーソン法
      • 残余グラフでは,uからvへはc(e)-x(e)の容量を持つ辺を張る
      • vからuへはc(e')+x(e')の容量の辺を張る
      • 残余グラフ上のs-tパスPを1つ見つけて,Pに含まれる辺の容量の最小値fのフローをP上に流す.
      • 最大流を求めるフォード・ファルカーソン法
        • フロー流量を表す変数FをF←0で初期化
        • 残余グラフG'を元のグラフGで初期化
        • while 残余グラフG'においてs-tパスPが存在するならば:
          • fをパスP上の各辺の容量の最小値
          • F+=f
          • パスP上に大きさfのフローを流す
          • 残余グラフG'を更新
        • Fが求める最大流量
      • 証明は辺連結度と同様
      • O(F|E|)
        • Fは「個数」ではなく「数値」なので,多項式時間ではない
        • 多項式時間: 数値に関して多項式であるが実際には多項式でない計算量
    • フォード・ファルカーソン法の実装
      • 難所:各辺e=(u,v)に対して,逆向きの辺e'=(v,u)を取得できるようにする
        • グラフGの入力受け取り時に,辺e=(u,v)を,配列G[u]の最後尾に挿入するときに,同時に配列G[v]に対しても,容量0の逆辺e'=(v,u)を最後尾に挿入する.「e'がG[v]のなかで何番目の要素に相当するかを示す変数rev」を辺eにもたせ,同様の変数をe'にも持たせる.
        • 辺e=(u,v)の逆辺はG[v][e.rev]と表せる
  • 応用例(1): 二部マッチング
    • 新たに頂点s,tを用意してグラフネットワークを作ることで,最大流問題に帰着させられる.
  • 応用例(2): 点連結度
    • 辺連結度: 「ネットワークの破壊は「辺」で発生する」という辺故障モデルでネットワークの耐故障性を評価
    • 点連結度: 「ネットワークの破壊は「頂点」で発生する」という点故障モデルでネットワークの耐故障性を評価
    • 点素: 2本のパスが点素であるとは,頂点を共有しないこと
    • 点素なs-tパスの最大本数と,s-t間を分断するために破壊する必要のある頂点数の最小値とが等しいという強双対性.この値を点連結度.
    • 各頂点vを2頂点vin, voutに分裂させることで,辺連結度を求める問題に帰着
  • 応用例(3): プロジェクト選択問題
    • プロジェクト選択問題で考慮する制約条件
      • u番目のボタンを押すならば,v番目のボタンを押さなければならない.
    • この制約下で得られる総利得を最大にする問題を考える.
    • 露天採鉱問題
    • コストを最小化する問題に読み替える
    • プロジェクト選択を,カットに帰着するアイディア
      • {s,t.0,1}を頂点集合に持つグラフであって,以下の条件を満たすものを構成したい
        • ボタン0,1をともに押すときのコストが,S={s,0,1},T=V-Sのカットの容量に一致
        • ボタン0のみ→S={s,0}
        • ボタン1のみ→S={s,1}
        • ボタンをともに押さない→S={s}
      • →図16.19
      • このグラフ上で最小カット問題を解くことで,ボタンの押し方の最適解を求められる.
    • N個のボタンとM個の制約条件に対しても自然に拡張できる.
  • まとめ
    • ネットワークフロー理論はとても美しい理論体系.
    • 1956年に最大流最小カット定理がフォード・ファルカーソンによって示されてから,爆発的に研究が進んだ.
    • ある問題に対して考案したアルゴリズムで得られた解の最適性を示すために,双対問題の実行可能解を構成し,それをもって「最適性の証拠」とする論法は,組み合わせ最適化問題において典型的な手法として定着.
      • → 豊かな組み合わせ構造が次々と明らかとなった.
    • 多項式時間で解けない問題が浮き彫りになった.
  • 章末問題
    • 16.1 M頂点の先に頂点tを設定し,最小のs-tカットを求める.
    • 16.2 https://drken1215.hatenablog.com/entry/2019/02/15/190700
      • s-t間の最短路それぞれについて,距離を1伸ばす必要がある.
      • 最短路が複数ありうるため,1つの辺を伸ばせばよいということではない.
      • それぞれのカットの容量が,最短路を1伸ばすためのコストとなる.
      • → 最小カット問題を解けばよい.
    • 16.3 https://jag-icpc.org/?plugin=attach&refer=2014%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=F.pdf
      • 最大流を流した後の残余グラフを考える.
      • 残余グラフで使っていないすべての辺について,sから行ける頂点集合Xにvが含まれ,tから行ける頂点集合Yにuが含まれているか調べて,カウントする.
    • 16.4 互いに素でないカード間に辺を張り,s,tを用意して最大流問題に帰着させればよさそう.
    • 16.5 https://qiita.com/drken/items/7f98315b56c95a6181a4
      • 最大安定集合問題
      • 点被覆と安定集合の関係
        • 一般の無向グラフにおいて,点被覆の補集合は安定集合をなし,安定集合の補集合は点被覆をなす.
      • 最小辺被覆と最大マッチングの関係
        • 孤立点のない一般の無向グラフで最大マッチングが得られているとする.マッチングの端点となっていない頂点それぞれにつき1本ずつ枝を追加すると,それが最小辺被覆となる.
      • https://drken1215.hatenablog.com/entry/2019/06/17/221400
      • https://www.slideshare.net/drken1215/ss-86894312
        • 最小点被覆の補集合は最大安定集合
        • 補助グラフを作る
          • マッチング枝は右から左,それ以外は左から右
          • 左側の頂点のうち,マッチングの端点でない頂点を赤く塗る
          • 赤く塗った頂点から矢印の向きに進んでいって到達できる頂点を赤く塗る
          • 左側の白い頂点と右側の赤い頂点が最小点被覆
      • 上記のように,二部マッチング,最小点被覆を求めて,その補集合が答え
    • 16.6 https://img.atcoder.jp/arc085/editorial.pdf
      • 最小カット問題の解法は,以下のような問題を解くことができる
        • 変数q[s],q[t],q[1],...,q[v]を考える
        • 罰金条件(x,y,z)がたくさん与えられる.q[x]=0,q[y]=1なら罰金z円.
        • 変数に0,1のどちらかを割り当て,罰金を最小化する.a[s]=0,a[t]=1は固定.
        • 変数が頂点,罰金条件が辺
      • まず,iを壊してjを壊さないケースについて,(i,j,∞)を追加する.
      • a[i]<=0→(S,i,-a[i]), a[i]>0→(i,T,a[i])
        • 左と右それぞれに罰金の辺を張る.
        • 左は処理をする頂点,右は処理をしない頂点の集合を作るための辺となる.
      • 処理をした場合の集合と処理をしない場合の集合の2つを作った時の,最小カットを求める.
      • https://betrue12.hateblo.jp/entry/2019/07/05/012450

Ch17 PとNP

  • 問題の難しさの測り方
  • PとNP
    • 判定問題と最適化問題
    • P, NPは判定問題の集合
    • クラスP: 多項式時間アルゴリズムが存在する判定問題の全体
    • 安定集合問題
      • 無向グラフG=(V,E)において,頂点集合の部分集合S⊂Vが安定集合であるとは,Sのどの2頂点も辺で結ばれないこと.
      • 正の整数kが与えられたとき,サイズがk以上の安定集合が存在するかどうか判定する.
    • ハミルトンサイクル問題
      • 有向グラフG=(V,E)において,各頂点をちょうど1度ずつ含むサイクル.
      • グラフGがハミルトンサイクルを持つか判定する.
    • クラスNP: 判定問題の答えがYesである場合において,そのYesである証拠が存在して,それをYesであることを多項式時間で検証できるもの.
      • PはNPに属する.
    • P⊂NP⊂EXP
  • P≠NP予想
    • NPに属するがPに属さないという問題が見つかっていない.
  • NP完全
    • 判定問題Xが以下の条件を満たすとき,クラスNP完全に属するという
      • X∈NPである
      • NPに属するすべての問題Yに対し,YをXに多項式時間帰着可能である.
    • 充足可能性問題(SAT)
    • それぞれは互いに同等に難しい.
  • 多項式時間帰着の例
    • 点被覆問題
    • 部分和問題
  • NP困難
    • 問題Xに対し,あるNP完全問題Yが存在して,Xが多項式時間アルゴリズムで解けるならばYも多項式時間アルゴリズムで解けるとき,XはクラスNP困難に属するという.また,NP困難に属する問題をNP困難問題という.
    • 最大安定集合問題
    • 最小点被覆問題
    • 巡回セールスマン問題(TSP)
  • 停止性問題
    • NPに属さないがNP困難
    • コンピュータプログラムPと,そのプログラムへの入力Iが与えられる.Iを入力としてPを実行したとき,Pが有限時間で停止するかどうかを判定する.
  • まとめ
    • 現実に解決できそうもない難問Xと出くわしたときは,知られているNP困難問題Yをどれか1つ持ってきて,YをXに帰着できないか考えることが有効.
  • 章末問題
    • (メモなし)

Ch18 難問対策

  • NP困難問題との対峙
    • 個別な入力ケースに対しては,現実的な時間で解を導ける可能性がある.
  • 特殊ケースで解ける場合
    • 区間スケジューリング問題を,特殊なグラフに対する最大安定集合問題とみなせる.
    • 最大安定集合問題を多項式時間で解くことができるグラフのクラス
      • 二部グラフ
    • 重み付き最大安定集合問題
      • 各頂点v∈Vに重みw(t)のついた木G=(V,E)が与えられる.木Gの安定集合としてさまざまなものを考えたときの,安定集合に含まれる頂点の重みの総和の最大値を求める.
    • 重み付き最大安定集合問題に対する木上のDP
      • dp1[v]: 頂点vを根とする部分木内での安定習合の重みのmax(頂点vを選ばない場合)
      • dp2[v]: 頂点vを根とする部分木内での安定習合の重みのmax(頂点vを選ぶ場合)
    • DPによる解法は,「木っぽさが強いグラフ」に対する解法へと自然につながるため重要.
      • 木幅: グラフが木にどれくらい近いか.
  • 貪欲法
    • 緩和: 問題の条件を少し緩めて扱いやすくする. → 緩和問題.
      • 連続緩和: 特に,整数値しか取りえない変数に対して連続値もとりうるようにする緩和
    • ナップサック問題に対する貪欲法の改良
    • 根本的に近似アルゴリズムとしての性能も改善.
  • 局所探索と焼きなまし法
    • 近傍: 「ほんの少し変更を加えたもの」
    • 局所最適解が全体の最適解とは限らない.
    • 焼きなまし法.f(x)の値が改善されないような近傍への移行も確率的に許す.
      • 温度と呼ばれるパラメータでその確率を制御する.
  • 分岐限定法
    • 枝刈り
    • 「これから探索しようとしているノード以降がそれまでの最良解Lより良い解を導く可能性がない」と判断できたら,そのノード以下の探索を打ち切る.
    • 理論的な計算量は下げないが,現実世界の実際の問題に対しては極めて高速に動作することが多々ある.
  • 整数計画問題への定式化
    • 最適化問題において
      • f: 目的関数
      • 条件x∈S: 制約
      • 制約をみたすx: 実行可能解
      • fを最小にするx: 最適解
      • 最適解xに対するfの値: 最適値
    • 整数変数を用いて,目的関数と制約条件がともに1次式で表せるような最適化問題を,整数計画問題という.
    • ナップサック問題を含むため,NP困難.
    • 高性能な整数計画ソルバーが開発されているため,大きなサイズの問題も解けうる.
  • 近似アルゴリズム
  • まとめ
    • 本全体としてのまとめ
    • 「実践的なアルゴリズム設計技能を磨く」
    • 既存のアルゴリズムの成り立ちの理解と,問題解決への実践.
    • 効率的に解けない問題を知ることも,重要な技能.
    • 部分的に発生する小問題の解決のために,グラフ探索,DP,貪欲法などを使える.
  • 章末問題

『コンピュータネットワーク 第5版』 第1章

ch01 序論

  • computer network: 単一の技術で相互接続された自律的コンピュータ(複数)として扱う。
  • 分散システム: ユーザには単一の均一なシステムに見える。単一のモデル、パラダイムを持つ。ネットワークで実現される。ネットワークとの違いは、ハードウェアではなくソフトウェアにある。
    • 例: www

1.1 computer networkの目的

  • 資源シェアリング
  • 通信媒体、communication medium
  • IP telephone, VoIP
  • desktop sharing
  • e-commerce
  • internet accessがconnectivityを与える

  • P2P vs クラサバ

    • 例: メール
  • instant messaging
  • social network
  • IPTV
  • ubiquitous computing
  • 測定・通信
  • Radio Frequency IDentification(RFID): 無線自動識別 → IoT
    • 受動チップ(電池なし)
  • internetへの接続がモバイル化を可能にする
  • 固定/移動無線
  • texting, SMS
  • GPS
  • m-commerce
  • NFC: Near Field Communication
  • sensor network
  • socail problem

1.2 network hardware

  • 伝送技術
    • broadcast, point-to-point
      • radio network
      • address fieldで全ての宛先を指定
      • multicast: すべてではなく一部
    • point-to-point
      • unicast
      • best-way-search
  • 規模
    • Personal Area Network ~ Inter Network → 惑星間Inter Network
    • PAN
    • Local Area Network(LAN)
      • 企業ネットワーク
      • Access Point(AP)やwireless router, base station(基地局)
      • 有線LAN point-to-point
        • e.g. Ethernet, switched Ethernet
          • switch: ポートを持ち、各ポートで1つのコンピュータと接続
        • protocolがルートを選択
      • Virtual LAN: Logicalに分ける
        • 各ポートは色で区別
      • classic Ethernet
      • 電力線ネットワーク@家庭
    • Metropolitan Area Network(MAN)
      • cable TV systemから
      • WiMAX
    • Wide Area Network(WAN)
      • 1つの国や大陸
      • subnetがホスト間でメッセージを送る。
        • 伝送回線、交換要素(switch)
          • switch: 2本以上の伝送回線の接続に特化したコンピュータ。ルータなど
      • subnet: 通信回線とルータの集合 ←→ network address の subnetとは違う
      • WANでは、ホストとサブネットは別々の人が所有・運用
      • 多くのWANはinternetworks(複数のnetwork)から構成される。ルータは異なるnetwork 技術をつなぐ。
      • subnetにはLAN全体も接続〇
      • VPN
        • 資源の柔軟な再利用
      • Network Service Provider: NSP
      • Internet Service Provider: ISP
        • このsubnetがISP network
      • routing algorithm, 転送algorithm
      • 衛星network: 本質的にbroadcast system
      • 携帯のnetwork
    • 相互接続した異なるnetworkの集合: internetwork
      • Internet(世界規模の1つの特定のinternet)
      • ISP networkを用いる
    • subnet: network operatorが所有する回線やルータの集合
    • network: 単一のテクノロジーで相互接続されたコンピュータの集合
    • internetwork: networkの異なる部分を異なる組織が担う or 用いている技術が異なる
    • 2つ以上のnetworkをつなげ、hardware, software両方の観点から必要な変換を提供: gateway
      • router: network層でパケットを交換するgateway

1.3 network software

  • network softwareは高度に構造化
  • layer, level: encapsulation
  • protocol: あるマシンの第n layerが、他のマシンの第n layerと会話するときの規則や習慣を第n layer protocol
    • peer: 異なるコンピュータ上で対応するlayerを構成する主体。プロトコルを用いて互いに通信し合うもの
    • 第1層の下に、実際に通信する物理媒体(physical medium)がある
    • IF: 隣り合った層の間。層間のIFを明確に定めることが、network設計の最重要考慮点の1つ
  • 層とprotocolの組み合わせ: network architectureと呼ぶ
  • protocol stack: あるシステムで用いることができる層ごとに1つずつあるprotocolのリスト
  • network architecture, protocol stack, protocolそのものが主題となる
    • 多層通信の類推
    • 各層のprotocolは完全に独立
    • 各プロセスは、自分のピアだけへの情報を付加できる
      • e.g. header @第3,4 layer, trailer@第2 layer
  • 各layerの設計課題
    • error detection/ correction + routing: 信頼性
    • protocol 階層化: networkの進化を支援
    • 送受信識別: addressing @下位層、 naming @上位層
    • internetworking: 異なるnetwork technologyは異なる制限を持つ
    • scalable @大network
    • 資源割り当て
      • 統計的多重化
      • フローコントロール: 受信側から送信側へのフィードバック
      • congestion: 定員超過
      • サービス品質: realtime配送など
    • 秘密性
      • 認証、完全性(messageの不正な変更を防ぐ) by cipher
  • connection指向サービスとconnectionless サービス
    • connection指向: 管のように振る舞う。
      • 交渉。例: 回線(circuit)。固定的な帯域のような資源を伴うconnection
    • connection less: ← 郵便システムのよう。
      • packet: network layer のmessage
        • 蓄積交換/cut-through交換
    • 高信頼connection指向の例: ファイル転送
      • 境界あり:message列(本)/ 境界なし:byte-stream(映画)
    • 低信頼(=確認通知) connectionless サービス(電報のよう)
      • データグラムサービス
      • e.g. VoIP
    • 確認通知データグラム → 信頼性要
      • e.g. ケータイのテキストメッセージ
    • request-reply service
      • e.g. クラサバモデルの通信の実現
  • サービスの一覧
  • サービス・primitive(操作)
    • service ←→ protocol: 1つの層の中の同位entity間で交換されるpacketやmessageなどのformatの意味を決める規則の集合
    • サービスは、サービスにアクセスするユーザープロセスから利用できるprimitiveの集合として定義できる
    • primitive(の集合)は、システムコール。サービスの性質に依存。
      • e.g. LISTEN, CONNECT, ..., DISCONNECT
      • e.g. クラサバでのrequest-replyのやりとり with acknowledged datagram
      • client, server間のやり取りの図がある
      • 第k+1 layerは第k layerの提供するサービスを使う。第k layer 間はプロトコルを共有。
  • →サービスとプロトコルは完全に分離
    • service: object
    • protocol: implement

1.4 参照モデル

  • OSI(Open System間 Interconnection) 参照モデル
    • 各layerのサービスやプロトコルは指定していないので、network architectureとはいえない
    • 7層である理由
    • 物理layer: 1のbitが反対にも1で確実に受信されることが重要
    • datalink layer: 送信側が入力データをデータ・フレームに分割。受信側は各フレームを正しく受信したことをacknowledged frameを送り返して確認
      • 役割: 生の伝送設備を未検出の伝送誤りのない回線と見える回線に変換
    • 媒体アクセス制御(medium access control)副層
    • network layer: subnetの動作をcontrol。送信元から宛先へパケットをどのような経路で通すか決定。異質なnetworkの相互接続のための問題解決。ブロードキャストでは、network layerはないか単純なもののみ。
    • transport layer: 送信元から宛先へデータを送るという意味で、真のe2e layer
      • 第1~第3 layerは数珠つなぎ。第4~第7はe2e。
    • session layer: 対話control, token management(2者が同一の重要な操作を同時に行わないようにする)。同期など(長い伝送にチェックポイント。中断ポイントからリスタート)。
    • presentation layer: 転送される情報の文法や意味を取り扱う。(交換するデータ構造を定義。回線上で用いる標準の符号化方式も定義する)。中小データ構造を管理して、より高レベルのデータ構造を定義、交換したりできるようにする。
    • application layer: 利用者から一般に必要とされるいろいろなprotocolを含む。
      • e.g. HTTP。ブラウザはHTTPでページの名前をサーバに送る。
  • TCP/IP参照モデル
    • 送信元と宛先のマシンが無事ならconnectionに影響がない
      • ファイル転送
      • リアルタイム音声転送などの要求
    • link layer
    • internet layer: network layerに対応
      • internet protocol(IP)とinternet control message protocol(ICMP)を定めている
      • IP packetを行先に配達する役割
        • ルーティング、congestion回避が問題
    • transport layer
      • 2種類のe2e protocol
        • Transmission Control Protocol(TCP)
          • connection指向の高信頼protocol
          • byte streamの分割・組み立て。+ フローコントロール
        • User Diagram Protocol(UDP)
          • TCPの順序コントロールやフローコントロールを使わず、独自のものを使う
          • 低信頼connectionless protocol
          • e.g. 1回きりのクラサバのrequest-reply, query, 音声やビデオの伝送など、早い伝達>正確な伝達であるアプリケーションで使う。
      • IPとTCP/UDPの関係について
    • application layer
      • 高位のprotocolをすべて含む。
        • e.g. old) TELNET, FTP, SMTP, new) DNS, NNTP(Network News Transfer Protocol), HTTP, RTP
      • session, presentation, layerは多くのアプリケーションで不要。
        • → 必要なもののみapplication layerが含む。
    • OSI: modelそのもの
    • TCP/IP: protocol
        1. application layer
        1. transport layer
        1. network layer
        1. link layer
        1. physical layer
  • OSITCP/IPの比較
    • OSIの中心概念: service/ interface/ protocol
    • connection指向/ connectionlessへのサポートの違い
  • OSI modelとprotocolの批評
    • OSI modelの失敗の理由
        1. 時期が悪かった
        2. 標準は、研究と何十億ドルもの投資の波の間で書かれることが重要
          • OSIは実現しなかった
        1. technologyが悪かった
        2. model, protocolともに欠陥があった
        3. ↑ 理解しづらい & 繰り返しあり
        1. implementが悪かった
        1. 駆け引きが悪かった
    • TCP/IPの批評
      • service, interface, protocolの概念の区別が不明
        • 仕様と実装の区別がない
      • 一般性がない。ブルートゥースなどには使えない。
      • link layerはlayerではない。ただのinterface
      • physical layerとdata link layerの違いがない
      • IPとTCP以外のprotocolが粗野かつ置換困難

1.5 networkの例

  • internet
    • ARPANET
      • Advanced Research Projects Agency
      • Interface Message Processor(IMP)
      • software: subnetとhostの2つ
      • 実験networkへの発展
      • 異なるnetworkをまたいだ運用のため → TCP/IP: internetwork通信を扱う
      • socket: 新しいprogramming interfaceでTCP/IPを書き直した
      • 規模の拡大 → DNSの作成: マシンをドメインに組織化。ホスト名とIPアドレスの対応付け。
    • NSFNET
      • ARPANETの後継
      • fuzzball: 最初のTCP/IP WAN
      • Advanced Networks and Services(ANS): 非営利組織
        • ANSNET
      • Network Access Point(NAP)の設立
        • NAP間のバックボーン通信事業者を選択可能
        • 単一のバックボーンではなくなり、商業的競争が可能となyys
  • wwwの出現で爆発的に大きくなった
  • internetのarchitecture
    • 従来の異なるnetworkが用いられていた用途に対して、1つのnetworkが用いられる電気通信の収束
      • → 激変の推進力
    • internet access/ connectivityをISPから買う
      • e.g. Digital Subscriber Line(DSL)
      • modem: 変調器復調器(modulator demodulator)
        • digital/analog変換をするあらゆる装置を指す
      • broadband: dial-upより大きく速いもの
      • 伝達の最後の区間帯域幅で制限
      • ISPのPoP(Point of Presence)
        • clientのpacketがISPのnetworkに入る地点
        • PoP間は完全にdigital。packet交換型
      • backbone: PoPのルータを相互接続する長距離伝送回線
    • Internet eXchange Point(IXP)で、ISPトラフィックを交換するためにnetworkを接続する
      • 接続したISPは互いにピアしているという
    • 小さなISPがtransit(より遠くのISP)にお金を払う
    • tier 1のISP: e.g. AT&T, Sprint
    • data center with Server farm
      • data centerにcolocation/ hostingすることで、サーバとISPバックボーン間に短く高速な接続を作る
      • → サーバファームの仮想マシンを借りる
  • 「Internetにある」の条件
  • intranet: 内部networkをinternetと同じ技術で相互接続

  • 第3世代モバイルフォン network

    • Advanced Mobile telePhone System(AMPS): 第1世代
    • Global System for Mobile Communications(GSM): 第2世代
    • Wideband Code Division Multiple Access(WCDMA)とも呼ばれるUniversal Mobile Telecommunication System(UMTS): 第3世代の3Gシステム
      • 希少資源: 無線スペクトル
        • cellular network
          • となりのセル間で周波数再利用という良い再利用をする。
          • → network容量増大
      • UMTSのarchitecture
        • air interface: mobile装置とセルラー基地局間の空中無線通信protocol
          • この進歩が無線データ速度を大きく増加
          • CDMAに基づく
          • セルラー基地局+コントロール装置 → 無線接続ネットワーク
          • Radio Network Controller(RNC)が、スペクトルの使い方をコントロールする
            • air interfaceを実現。Node B
        • core network: radio accessトラフィックを運ぶ
          • packet network: connectionless subnet
            • サービス品質△ → オーディオやビデオには×
          • 回線network: connection指向 subnet
            • サービス品質〇、耐障害性△
          • core networkはサービス品質と耐障害性どちらも〇
      • UMTSのnetwork内で、Public Switched Telephone Network(PSTN)のような回線交換core network上にconnectionを設定する
        • Mobile Switching Center(MSC)
        • Gateway MSC(GMSC)
        • Media GateWay(MGW) ― 上の3つの要素がある。
      • General Packet Radio Service(GPRS) @ data service
        • Servicing GPRS Support Node(SGSN)とGateway GPRS Support Node(GGSN)が、モバイルフォンから/へのデータパケットを届けInternetのような外部のpacket networkと橋渡しする
          • UMTS core networkのnodeはpacket通信網と直に接続
      • cellular 基地局の経路変更: handover: soft/ handoff: hard
      • Home Subscriber Server(HSS) in core networkが、一夜認証・許可に用いるprofile 情報を知っている
      • Subscriber Identity Module(SIM)カードが、セキュリティの基盤+不正防止+正当なnetworkへの交信のチェック
        • privacy: SIMカード上の暗号キーが伝送を暗号化
      • Long Term Evolution(LTE): 4G technology, WiMAX
  • 1.5.3 無線LAN: 802.11(俗にいうWi-Fi)
    • Industrial, Scientific, and Medical(ISM)帯
      • 902~928 MHz, 2/4 ~ 2.5 GHz, 5.725~5.825Ghzなどの、免許不要の周波数帯
      • codeless phoneや電子レンジなどと競合するのはこのため。
    • AP(Access Point) = base station(基地局)
      • 有線networkとconnection
      • or client間がAPなしに交信〇 = ad hoc network
    • multipath fading
      • path diversity
      • Orthogonal Frequency Division Multiplexing(OFDM): 直交周波数分割多重
      • 802.11b std → 11Mbps
      • 802.11n: 450Mbps
    • 無線は本質的に放送型の媒体
      • 同時に送った複数の伝送が衝突して受信の干渉するという問題がある
        • ←→ CSMA(Carrier Sense Multiple Access)方式: 実用上うまく動く
      • 移動性の問題
        • ↑ APをもった複数セルを接続する分配システムを構成
    • Security
      • Wired Equivalent Privacy(WEP): 暗号化方式
      • WiFi Protected Access(WPA(2)): WEPは破られた。
    • RFIDとセンサーnetwork
      • Radio Frequency IDentification
      • 〇passive RFID ←→ △active RFID
      • Ultra-High Frequency RFID(UHF RFID)
        • 902~928MHz
        • backscatter: 反射をひろう
      • High Frequency RFID(HF RFID)
        • 13.56MHz, 範囲1m以下 ← backscatterではないため。
      • Low Frequency RFID(LF RFID)
      • 範囲内の複数タグを読み取るという問題
      • Security: password(弱い)。タグのメモリがウイルスになる。
      • sensor network
        • multihop network

1.6 networkの標準化

  • 目的: 異なるコンピュータが通信 + 製品市場を拡大

    • → 大量生産、製造規模の経済性、より良い実装、価格低下と普及
  • 標準: 相互運用性に何が必要か定義する。

  • de facto: from the fact

  • de jure; by law
    • de facto → de jureに発展
    • 3GPP(Third Generation Partnership Project): 団体間の連携
  • 国営電気通信企業: PTT(Post, Telegraph & Telephone administration)
    • 民営化。自由化。競争。
  • ITU(International Telecommunication Union)
  • 国際標準はISO(International Organization for Standardization)で作成・出版されている。
    • ISOのITU-Tの構成員。
      • CD(Committee Draft: 委員会草案)
        • DIS(Draft International Standard)
          • IS(International Standard)
  • NIST(National Institute of Standards and Technology): 米国商務省の一部
  • IEEE(Institute of Electrical and Electonics Engineers)
  • Internet の標準
    • 「大まかな合意と走るコード:
    • 委員会: IAB(Internet Activities Board) @ ARPANET
      • Activities → Architecture
    • RFC(Request For Comments)での情報伝達
    • IRTF(Internet Research Task Force) + IETF(Internet Engineering Task Force)
    • Internet Society(学会)が作成
    • Proposed standard ← RFC
      • → Draft Standard
        • → Internet Standard
    • World Wide Web Consortium(W3C) @Web

1.7 メートル法の単位

  • m: ミリ。μ: マイクロ。
  • 1より大きいと大文字
  • B: byte, b: bit
  • K: 210 @ memory

1.8 本書の概要

  • 原理と実践
  • architectureの観点に限定

1.9 まとめ

  • (メモなし)