『データ指向アプリケーションデザイン ――信頼性、拡張性、保守性の高い分散システム設計の原理』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
- Systems of Record (a.c.a. Source of truth)
- system内のdata flowの明確のために,区別はvery beneficial
- systemの各部のI/Oと依存関係の明確化
- dbは単なるtool
- → application内でどう使うかで分類が決まる
- dataを保存し処理するsystemの2分類
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
- Service(Online System)
- trusted scalable(maintainable) systemのために,batch processingは重要なbuilding block
10.1 Unixのtoolによるbatch processing
目的
- simpleなe.g.
- request, processingのたびにlog fileに行を追記
対応
- !1 simple logのanalyze
- !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}
- 結合性が重要
- 全programが同じinterface
- !!2 logicと結線の分離
- stdin, stdout
- 疎結合(loose coupling), late binding, inversion of controlの1形態
- → 入出力の結線をlogicから分離
- → 小さいtoolから大きいsystemを合成
- → 入出力の結線をlogicから分離
- !!3 transparencyとexperiment
10.2 MapReduceとdistributed file system
目的
- MapReduceとUnix 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
- ↑→ NAS(Network Attach Storage), SAN(Storage Area Network)のarchtectureでの共有discのapproachと対照的
- HDFS: network serviceを公開
- name nodeという中央Serverが,file blockingのmachineへの保存状況を追跡
- → 全machineのdisc領域から,1つの巨大なfile systemを生成
- リードソロモンcodeのようなerasure codingで,完全なreplicationによりoverheadを抑える
対応
- !1 MapReduce Jobのexecution
- !2 Reduce側での結合とgroup化
- 結合: {foreign key, document reference, 辺}の両端のrecordにaccessしなければならないcodeで必要
- MapReduceのjobはfull table scan
- analytic queryでは〇
- especially, 複数マシンにわたってconcurr
- → dataset中の何らかの関連をすべて見出す
- analytic queryでは〇
- !!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
- 図10-3: flow
- !!3 関連するdataを同じ場所にまとめる
- !!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を扱うprocessを複数reducerに分散
- hot keyでのgroup化では,2つのstageに分割
- e.g. Pigでのskewed join method
- linchpin object: 不均衡なactive db record
- !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
- joinのinputがどちらも同じkey, 同じhash functionに基づいて同じ数のpartitionを持っているときのみ使える
- !!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でもない
- !!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)も不要
- 全く新しいDBをbatch job内部で作成
- search index以外のe.g. of batch processing workflowのoutput
- !!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〇
- inputはimmuteで副作用を避け,batch jobのperformance up + maintenanceはるかに楽
- Unixとは異なる点
- Hadoopでは,よりstructuredなfile formatを使い,parse processingを省略可能
- ↑ effectiveなschema baseのencodingを提供
- schemaを進化させられる → Avro, Parquetがよく使われる
- Unixの哲学と同じ
- !5 Hadoopとdistributed datacenterの比較
- Hadoop: Unixのdistributed versionのよう
- !!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
- DWHと似た考え.: data を生のままcollect
- dataの解釈は,consumerのproblem ← schema on read
- → 任意の変換可能
- → sushi principle: dataは生が〇
- → Hadoopは,ETL(Extract-Transform-Load) processingの実装に使われてきた
- ↑ distributed file systemが任意のformatでのdata encodingをサポート.
- → 任意の変換可能
- !!2 processing modelの多様性
- !!3 often faultに備えた設計
- MapReduce とMPP dbの違い
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
- map, reduceと同じ処理のcodeは,修正鳴くほかのengineでも使える
- MapReduceのproblemに対応
- !!2 fault tolerance
- !!3 実体化についての議論
- !2 graphとiterativeなprocessing
- graph全体へのoffline processingやanalyze
- → recommendation engineやranking systemといったmachinelearningのapplicationで生じる
- e.g. PageRank
- 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が広がる
- ある頂点がほかの頂点に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
- Pregel jobのperformance高い: messageをbatch化して通信待ち時間削減
- !!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との違い
- relationalなoperatorの指定 → frameworkがjoinのinputの性質を分析
- !!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に過ぎない
- e.g. 統計,数値処理のalgorithm for classificationやrecommendation systemといったmachine learningのapplication
- programming modelの改善, processing effectivityの改善
まとめ
- batch processing について
- distributed batch processing frameworkで解決する問題
- partitioning
- 関連するdataをすべて同じ場所にまとめる
- fault tolerance
- 中間stateの扱い.影響
- partitioning
- 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
- stream processing
- input dataは有限.既知のサイズ. → 官僚のjudge可能
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などは限定的
- これまでのdbにない機能のためのtoolがdeveloped
対応
- !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
- どれか1つのconsumerに配信
- 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の利用
- !!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が◎
- → JMS/AMQP styleのmessage brokerが望ましい
- log baseのapproach → fanout型のmessaging support easy〇
- !!3 consumerのoffset
- brokerはacknowledgementの追跡不要: 管理のoverhead少ない
- → batchやpipelineといった手法を取るchanceが生まれる → throughput高い @ log base system
- 5.1.2のlog sequence numberと似ている
- brokerはacknowledgementの追跡不要: 管理のoverhead少ない
- !!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する
- e.g. replication log
対応
- !1 systemのsyncの保持
- 複雑なapplicationの要求は,異なる技術の組み合わせで解決
- それぞれの目的にoptimiseした形式で各々がcopyをもつ
- → syncが必要
- e.g. ETL process @DWH(3.2.1): batch processing
- → syncが必要
- dual writesの重大なproblem ← dual writesは,dumpが低速なcaseの代替案
- 図11-4: race condition
- version vector(5.4.4)などが必要
- fault-toleranceのproblem
- 2 system間不整合
- 図11-4: race condition
- それぞれの目的にoptimiseした形式で各々がcopyをもつ
- 複雑なapplicationの要求は,異なる技術の組み合わせで解決
- !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
- change stream: first classのinterfaceとしてDBでsupport
- 図11-5: flow. 変更のstreamをproducerとconsumerで扱う
- !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
- 決定的なlogでlog → state
- !!2 commandとevent
- commandがvalidated → event
- event: fact. logのimmutableな一部
- → commandのvalidationはsync 必要
- serializableなtransactionの利用
- or, eventの分割
- → commandのvalidationはsync 必要
- event: fact. logのimmutableな一部
- commandがvalidated → event
- event sourcingとCDCの違い
- !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)
- !!2 stream analyze
- !!3 materialized viewの管理
- applicationのstateもmaterialized viewの1つ
- ただし,全event必要.log compactionも必要
- applicationのstateもmaterialized viewの1つ
- !!4 streamでのsearch
- streamのsearch: queryをstore → CEPのようにdocumentがqueryを通る
- queryのindexづけ
- !!5 message passingとRPC
- RPC的systemとstream processing間は重なる領域もあるが,そもそもは異なる
- stream processing は,monitorのために使われてきた
- !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
- はぐれ(straggler) event のproblem
- !!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に使う
- Tumbling window
- localのsystem clockでwindowを決定
- !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
- stream processorがもつdbのlocal copyの最新化が必要
- !!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不可能
- → joinするrecordのversionごとにidを使う
- stream processing: data pipelineを限度ないdatasetのincrementalなprocessingに一般化したもの
- !4 fault-tolerance
- exactly-once semantics(事実上effectively-onceがより正しい) @batch job
- streamはより複雑な対処必要
- !!1 micro batch processingとcheckponit processing
- !!2 atomicなcommit再び
- !!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特性に依存
- exactly-once semantics(事実上effectively-onceがより正しい) @batch job
まとめ
- 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の有用性は限定的
- XAのfault-toleranceとperformance特性は貧弱
- 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
- simpleなanswerなし
- !2 batch processingとstream processing
- data joinの目標: dataを適切なところに適切なformatでおく
- これを達成のためのtool: batch/stream processor
- extract datasetを出力
- これを達成のためのtool: batch/stream processor
- 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の統合
- data joinの目標: dataを適切なところに適切なformatでおく
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)
- 組織全体にわたるdata flow: 1つの巨大なdb
- !!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が研究中
- dbの機能,動作
- !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の集合に機能を分割
- → 疎結合で組織的scalability〇
- streamのoperatorを合成は,同じ特徴あり〇
- ただし,layerのcommunicationの仕組みは大きく異なる: 1方向のasync message stream
- fault-tolerance + performance 高い〇
- RPCの代わりに,stream joinが◎
- ただし,いずれにせよ時間への依存性の対応が必要
- RPCの代わりに,stream joinが◎
- application development style: serviceの集合に機能を分割
- database insideout approachというdesign patternの中身
- !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)をずらしている
- 全文検索indexのe.g.
- !!2 statefulでoffline動作できるclient
- clientがstateを持つapplicationの出現
- offline firstのapplication
- device上のstate: server上のstateのcache
- offline firstのapplication
- clientがstateを持つapplicationの出現
- !!3 clientへのstateの変化のpush
- !!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の向上〇
- stateを持つclientやUIをdevelopするためのtools
- !!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
- e.g. Stormのdistributed RPC機能
- MPP dbでのinner query execution graphも似た特徴あり
- queryをstreamとして扱う: 大規模applicationの実装の選択肢の1つ
- readのevent化は,複雑なqueryのdistributed executionの可能性になる
- write path: extracted datasetを最新のstateに保つprocess
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
- networkのcommunicationを複数hop 経由する操作を冪等にする
- !!4 e2e論
- duplicationの抑制は,communication system自体の機能では不可能
- → transaction IDが,end userのclientからdbまで渡される必要
- e2eはnetworkでのdataの整合性にも必要
- encryption
- 低レベルの機能の上に成り立つ
- duplicationの抑制は,communication system自体の機能では不可能
- !!5 data systemへのe2eのapply
- 高levelのabstractionにenoughな方法まだない
- transactionもnot enough
- 高levelのabstractionにenoughな方法まだない
- applicationのbugのcase
- !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を利用可能
- log: total order broadcast = consentと等価
- !!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: 弱制約
- userが,systemの最新のstateの観察を保証
- timeliness
- integrity
- dataに矛盾や間違いがないこと
- especially 正しいextract data
- 明示的なcheckとrepair必要
- ACID transactionでは,consistencyはある種のapplication固有のintegrityの表現
- atomicityとeternityが整合性を保持するための重要なtools
- dataに矛盾や間違いがないこと
- 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可能
- → 高performance, fault-tolerance〇
- serializable transactionは一部の使用で有益
- 2つの所見
- !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は決定的で再現可能
- → stateの更新はeventからextracted
- data flowの明確化 → dataの系統(provenance)も明確化
- → integrityのcheckはるかにeasy
- event logはhashでevent storageのcheck〇
- extracted stateは,batchやstream processorのreprocessingでevent logからstate extract〇
- → integrityのcheckはるかにeasy
- userのinputは単一のimmutable event
- → data flowがdecisiveで十分にdefined
- → systemの行いの理由のためのdebugやtraceがeasy
- bug検出時の環境再現も〇
- !!5 e2e論再び
- dataのintegrity checkはregularに必要
- e2eでのcheckが〇 → 内部もimplicitにcheck〇
- systemの変更や新storage technologyのrisk減
- → applicationの進化〇
- systemの変更や新storage technologyのrisk減
- e2eでのcheckが〇 → 内部もimplicitにcheck〇
- dataのintegrity checkはregularに必要
- !!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 ×)
- このtechnologyはたいていMerkle treesに依存
- integrityのcheckや監査のalgorithmを使うsystemが,scalableでperformanceのpenalty少となるように研究必要
- encryptionのtoolsで,hardware, softwareのproblemやcrackingへのtoleranceをもつようにsystemのintegrityを証明する方法あり
12.4 正しいことを行う
目的
- すべてのsystemはある目的のために構築される
- → 目的をこえた影響もあり.これにも責任必要
- dataを,人間性とrespectをもって扱う
- 今日は,倫理的選択が一層含まれる
- → 目的をこえた影響もあり.これにも責任必要
対応
- !1 予測分析(predictive analytics)
- !!1 biasと差別
- algorithmのinputのbiasに気づけない
- machinelearningは,biasをmoneyロンダリング
- algorithmのinputのbiasに気づけない
- !!2 責任と説明責任
- dataに基づく意思決定の間違いを正す方法必要
- !!3 feedbackloop
- system thinkingでriskyなfeedbackloopを避ける
- !!1 biasと差別
- !2 privacyと追跡
まとめ
- 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に制限
- 共有memory archtecture
- !!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.
- simple: scale up(vertical)
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
- snapshot
- !3 nodeのfaultへの対処
- !!1 followerの障害: catchup recovery
- !!2 leaderの障害: fail over
- !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
- !!1 statement baseのreplica
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での運用
- !!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
- !!5 Whats's Conflict?
- → Ch07, Ch12
- !3 multi leader replicationのtopology
5.4 leaderless replication
目的
対応
- !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
- leaderless replicationも〇
- !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
まとめ
- 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がとても高い
- 目的: 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
- !2 keyのhashにもとづくpartitioning
- !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.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の合計サイズに大きな変動があると,設定が難しい
- 図6-6: balancingの前後
- !!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法の元々の定義に近い
- !!1 取るべきでない方法: 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で〇.
- OLAPで使われるMassively Parallel Processing: MPP(大規模並列処理)
まとめ
- 大規模なdatasetを小さな部分集合にPartitioning
- dataに適したPartitionのschemaを選択 + rebalancing
- 2つのPartitioningのapproach
- keyのrangeによるPartitioning
- rebalancingはdynamic
- hash Partitioning
- 固定数のPartitionがgeneral. dynamicなPartitioningも使える〇.
- hybridなapproachも可能
- keyのrangeによるPartitioning
- secondary index のPartitioningの2つの方法
- documentによりPartされたindex(local index)
- scatter/gather必要
- WordによってPartitioningされたindex(global index)
- writeで複数Partitionをupdate, readは単一Partitionで処理〇.
- documentによりPartされたindex(local index)
- 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
- especially, concurrency control
- 単一ノードの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定理では,線形化可能性の意味
- dataについて常に真でなければならない何らかの言明・不変性がある
- !!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
- !!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)は回避不可能
- いくつかのconcurrency problem回避
- !!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つの保証
- !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
- !!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を設けられる
- Transactionの順次実行がserializable isolation level実現のための制約
- 単一threadでTransactionを処理 → serializable isolation level
- !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の検知アルゴリズム
- pessimistic: 相互排他(multithread programmingでdata structureを保護)に似ている.
- !!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の影響なし
- reader, writer間はブロックなし
まとめ
- 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は,この間のどこか
- HPC(High Performance Computing)
- → フォールトへのapproach異なる
- softwareにフォールトtoleranceの組込必要
- 信頼性のないcomponentからtrustnessあるsystemを構築
- 様々なフォールトへのテスト必要
- 大規模なcomputing systemの構築方法の哲学のスペクトラム
8.2 低trust network
目的
- shared nothing system by network
- internetとdatacenter内の大部分の内部network(Ethernet)は,async packet network
- 図8-1
- 各problem ^ timeoutでの対応
- internetとdatacenter内の大部分の内部network(Ethernet)は,async packet network
対応
- !1 networkのfaultの実際
- networkの分断: network partition, netsplitと呼ぶ
- 必ずしもtolerantである必要はない
- networkのproblemへの反応の認識が重要
- networkの分断: network partition, netsplitと呼ぶ
- !2 faultのdetect
- requestのsuccessは,applicationからのproperなresponce以外確認不可能
- errorはtimeoutでjudge
- requestのsuccessは,applicationからのproperなresponce以外確認不可能
- !3 timeoutと限度のない遅延(unbounded delay)
- !4 sync networkとasync network
- sync networkでは,bounded delay by 回線,connection
- !!1 network 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の期間計測に使える.
- !!1 時刻のclock
- !2 clockの動機とaccuracy
- !3 sync clockへの依存
- softwareがclockのずれをmonirtor要
- !!1 順序relationをもつeventのtimestamp
- 図8-3: e.g.
- LWWのproblem
- → logical clockの使用が〇
- 相対順序の決定.単調increment
- ≠ physical clock: 時刻のclockや経過時間を観測する単調increment のclock
- → logical clockの使用が〇
- !!2 clockの値の信頼区間
- !!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
- leaderがleaseを取得
- !!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
- hard real time system. RTOS(Real Time OS)
- !!2 GCによるimpactの制限 → 有益
- distributed systemにおけるleaderの扱い
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
- 制約強い
- sync 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は等しく重要
- 3つのmodel
まとめ
- 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: 合意
- 可不可の限度の認識が重要
- abstractionでproblemを隠蔽が重要
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: 反例
- recency guarantee(最新性の保証)
- dataのcopyが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
- 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と類似
- unique制約を保証するためのlinearizability
- !!3 cross channel timing依存relation
- 図9-5: e.g. cross channel
- → linearizability 必要
- !!1 lockとleader election
- !3 linearizable systemの実装
- replication for fault-tolerance
- !!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のため
- 実際にlinearizableなsystemはほとんどない
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
- → causually consistencyがnetwork delayで速度が落ちないconsistencyの中でstrongest
- linearizabilityは因果関係を暗に含む
- !!3 因果律における依存関係の補足
- 操作の先行を知る必要: 半order
- nodeのacknowledgeを記述する必要
- version vectorの利用 ← 5.4.4と似ている
- dbがread dataのversionを知ることが必要
- nodeのacknowledgeを記述する必要
- 操作の先行を知る必要: 半order
- Orderは因果関係
- !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補足不可能
- 個別のsequencial number発行は,因果律のconsistencyなし
- 単一leaderなし → sequencial numberの発行は,不透明
- !!2 Lamport timestamp
- !!3 timestampでのorderづけでは不十分
- Lamport timestampは,distributed systemのgeneral な多くの問題の解決には不十分
- ↑ 操作の全orderは,すべての操作がcollectできたあと
- → unique制約には,操作の全orderでは不十分
- → いつまでに確定するかが重要
- sequencial number( or timestamp)でのeventの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
- 2つの安全性の保障
- !!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
- → writeのcommitとabortの合意
- !!3 linearizableなstorageを使ったtotal order broadcastの実装
- linearizable sequencial number generatorを使う ← 合意のalgorithm
- linearizable (increment) compare-and-set registerと,total order broadcastはどちらも合意と等価
- → どちらかをresolve → もう一方にも変換〇
- problem
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
- !!3 約束のsystem
- commit point
- 2つのpoint of no return
- !!4 coordinatorのfault
- in doubt, uncertain
- 図9-10
- coordinatorのrecoveryを待つ必要
- in doubt, uncertain
- !!5 3PC
- 2PC: blocking atomic commit protocol
- 3PC: nonblocking
- but, 制限あり.現実にはnot atomic
- non blocking. atomic commitはperfect failure detector必要
- 実際は難しい
- non blocking. atomic commitはperfect failure detector必要
- but, 制限あり.現実にはnot atomic
- !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
- 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を増幅
- distributed transactionへの2つの評価
- !3 耐障害性をもつconsent
- consent: 非形式的には,複数nodeが何かについて同意すること.
- 形式的には,1つ以上のnodeがpropose → 合意algorithmがそれらの値から1つを決定
- uniform consent
- 4つの性質
- uniform agreement
- integrity(整合性)
- validity(妥当性) (ここまで3つが合意の核.安全性)
- termination(終了性): 耐障害性.(live性)
- 4つの性質
- いかなる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
- 耐障害性のconsent algorithm
- !!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では過半数
- epoch: a.c.a. ballot, view, term
- !!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は研究中
- consent algorithm: distributed systemの大きなbreakthrough
- consent: 非形式的には,複数nodeが何かについて同意すること.
- !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
- processing/ serviceの複数インスタンスからleader, primaryをelect
- ZooKeeperのatomic操作, ephemeral node, 通知により達成可能
- Apache Curatorのようなlibraryあるが,簡単ではない
- ZooKeeperはnode間協調作業をoutsourcing
- applicationのstateをnode間でreplication → Apache BookKeeper
- ZooKeeper/ Chubbyがeffectiveなcase
- !!2 service discovery
- ZooKeeper, etcd, Consul
- linearizability不要なread requestにresponceできる
- !!3 membership service
- consentとfault detectの組み合わせ
- どういったnode群でmembershipが構成されているか.Systemでconsent生成は有益
- ZooKeeperやetcd: distributed key-value store, 協調および設定service
まとめ
- 一貫性と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の状況に対処必要証明
- leaderのrecovery待ち
- 耐障害性をもつconsentのためのalgorithm system
- ZooKeeper
- consent不要なcase
- multi leader replication system
- 単にlinearizabilityなしに対処.分岐や合流を伴うversion historyをもつdataを扱えばよい.
- multi leader replication system
『データ指向アプリケーションデザイン ――信頼性、拡張性、保守性の高い分散システム設計の原理』Part 1 データシステムの基礎
Part 1 データシステムの基礎
Ch01 信頼性,スケーラビリティ,メンテナンス性にすぐれたアプリケーション
目的
- データ指向であり,演算指向でない
- データ指向アプリケーションの機能
- DB
- cache
- search idx
- stream処理
- batch処理
- DB
- データシステムの原理と実用性,それらの適用.
考察
対応
- !2 信頼性
- フォールトトレラント ≒ レジリエント(リバウンドが語源.元に戻る力.)
- 障害 @ システム全体 > フォールト @ 仕様を満たさないコンポーネント
- エラー処理でフォールトを正しく作り出す.
- !!1 hardwareの障害
- !!2 softwareのエラー
- softwareのシステマティックなフォールト
- → テスト,検証,設計での積み重ねによる対処.
- softwareのシステマティックなフォールト
- !!3 human error
- sandbox env.
- automatic test
- telemetry
- !!4 trustnessの重要度
- userの責任
- フォールトトレラント ≒ レジリエント(リバウンドが語源.元に戻る力.)
- !3 scalability
- !!1 負荷の表現
- !!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に直にかかわる.重要.
- 外れ値: p95, p99, p999を見る
- 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の計測が重要
- head-of-line blocking(HOL blocking)
- 図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と標準ツールとの結合サポート
- 個々のマシンへの依存性を持たせない.
- 優れたドキュメンテーションと分かりやすい運用モデル
- デフォルトの挙動を優れたものにする
- 管理者のオーバーライド可
- 自己回復 @ 正常なとき
- 管理者の手動コントロール
- 予期できる挙動
- 定型のタスクを容易にする @ datasystem
- !!2 単純さ.複雑さの管理
- 巨大な泥団子
- 実装のみから生じる複雑さの除去
- 偶発的な複雑さ
- → 抽象化
- !!3 進化性: 変更への配慮
- アジャイル: TDD, refactor
- 小さなローカルスケール
- → より大規模なレベル
- 単純性と抽象化が重要.
- アジャイル: TDD, refactor
- 3つのdesign doctrine
- まとめ
- 機能要求・日機能要求
- !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
- とても汎用的
対応
- !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間の不格好な変換レイヤが必要.
- ActiveRecordやHibernateなどのORM frameworkは定型コードを減らすが,完全には隠せない.
- 図2-1: relational schemaでのLinkedInのプロフィール表現
- JSONの問題もある.
- JSONでの表現: localityに優れている
- impedance mismatch
- !3 多対1と多対多のrelation
- id, 文字列
- copyの問題
- id自体は意味なし → 〇変更不要
- → 正規化で回避可能
- 意味のある情報がコピー → ×書き込みのoverhead + 不整合リスク
- id自体は意味なし → 〇変更不要
- 正規化: 多対1 → ドキュメントDBは非サポート
- 1対多の木構造には結合不要.
- 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が複雑で柔軟でない
- 変更に弱い.
- CODASYL model
- conference on Data Systems Langs(CODASYL)
- !!2 relational model
- query optimiserがクエリの実行順序やどのインデックスを使うか判断
- → 新機能の追加容易
- query optimiserがクエリの実行順序やどのインデックスを使うか判断
- !!3 document DBとの比較
- document DB: 階層モデルに回帰 + 多対1,多対多の関係の表現〇
- ↑ 関係のあるアイテムはユニークな識別子で参照.
- document reference @ document DB = foreign key @ relational DB
- document DB: 階層モデルに回帰 + 多対1,多対多の関係の表現〇
- IMS(Information Management System) @ 1990's
- !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化と構造の強制.
- Schema on read(Schemalessは誤用) ←→ Schema on write @ relational model
- !!3 queryのためのdata locality
- documentの保存形式
- storageのlocality: document全体にaccessする場合はmeritあり.
- 1度にdocumentの大部分が必要なとき以外は不要.
- → documentは小さく保つという制約がdocument dbにはある.
- localityをいかすため,関連するデータ同士をグループ化.
- !!4 documentおよびrelational dbの融合
2.2 dataのためのquery language
目的
- SQL: 宣言的query language ←→ IMS, CODASYL: 命令的code
対応
- !1 Web上での宣言的query
- !2 MapReduceでのquery
- 大量dataを多くのマシンにまたがってまとめて処理.by Google
- e.g. MongoDB, Couch DBなどのNoSQLが限定的にサポート.
- 宣言的と命令的の間のどこか.
- map, reduceはpure function: parameterのみがinput
- 任意の場所と順序〇.
- cluster上のdistributed processingのための,とても低レベルなprogramming model.
- query中のJSのcodeもMapReduce以外でもOK
- MapReduceの問題: codeの整合を取るのが難しい
- → MongoDB 2.2: aggregation pipelineという,宣言的なquery languageをサポート.
- 大量dataを多くのマシンにまたがってまとめて処理.by Google
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
- 頂点
- 柔軟,進化性〇.
- important 3 points
- !2 Cypher query language
- property graph用のquery language
- e.g.
- query optimiser ← 宣言的language
- property graph用のquery language
- !3 SQLでのgraph query
- !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の内部的なデータモデルとして優れる.
- RDF(Resource Description Framework)
- !!2 RDF data model
- !!3 SPARQL
- Cypherの元となったもの(about pattern matching)
- 変数が?から始まる
- 優れたquery language
- !!4
- graph dbとnetwork modelの比較
- graph >>> network
- graph dbとnetwork modelの比較
- !!5 礎となったもの: Data log
まとめ
- 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
- 追記のみの利点
- 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の作成
- !!3 performanceのoptimise
- bloom filter: 集合の内容の概要を保持.メモリ効率〇.
- sizeごと,levelごとのcompaction.
- SSTableをバックグラウンドでマージ.: simple and effective.
- memory両の制約なし
- 範囲へのquery〇
- 書き込み: sequencial
- keyでsort
- !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のメリット
- !!2 LSMTreeのデメリット
- compactionがrunningのread/writeに影響しうる.←→ BTreeは高percentileも予測しやすい.
- 高p値が極めて高くなりうる.
- compactionでwriteのthroughput増大しうる
- writeのペースとcompactionのペースの不一致への対応 → 明示的にモニタリング
- BTreeは,keyがindex中の1か所のみある.
- → 強いtransactionのsemanticsに〇
- ↑ keyの範囲でロック.
- compactionがrunningのread/writeに影響しうる.←→ BTreeは高percentileも予測しやすい.
- !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内に行を直保存
- PKに使われる. @ MySQL, SQL Server
- 中間: covering index. a.c.a. 付加列を持つindex
- 一部の列のみindexに持つ.
- clusterかindexやcovering indexは,読み取り高速,書き込み中速
- transaction保証の負担もある.
- heap file: 行が保存されている場所.非cluster化index
- !!2 複合index
- 連結index: 複数フィールドを1つのkeyとする
- keyの部分の検索には使えない
- 多次元index
- 2次元を単一数値に変換
- RTree
- e.g. PostGISは,PostgreSQLのGiST(Generalized Search Tree) indexの機能を使ったRTree.
- → 地理空間index
- 地理に限らず,多parameterなほかの例にも使える.
- 連結index: 複数フィールドを1つのkeyとする
- !!3 全文検索とあいまいなindex
- !!4 全データのメモリでの保持
- discはdataの配置が重要 for performance
- 永続性,容量あたりコスト安が〇
- → RAMが安くなり,コストのメリットが薄れている
- → inmemory db
- inmemoryのperformanceのメリット
- memory内のdata structureをディスクに書く形式にエンコードするoverheadを回避できること.
- performance以外のメリット
- disc baseでは実装困難なデータモデルの提供
- e.g. Redis: priority queueや集合などのdata structureに対するDBのようなインターフェースを提供
- disc baseでは実装困難なデータモデルの提供
- anti caching approach
- 使えるメモリより大きなdatasetをサポート.
- swapfile @ OS よりeffectiveにmemoryを管理 by db
- indexはすべてmemoryに収まる必要
- 使えるメモリより大きなdatasetをサポート.
- 不揮発性memory(Non-Volatile Memory, NVM)が広まれば,さらなる変化が見込まれる.
- discはdataの配置が重要 for performance
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の違い
- !!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の方がシンプルで〇
- 多くはStar schema(a.c.a. dimension model)
3.3 列指向storage
目的
- 例3-1: analytic query
- OLTP: 行指向 ←→ OLAP: 列指向
- 図3-10
- 非relational modelでも使える
- e.g. Parquet ← GoogleのDremelが元.
- document data model
- e.g. Parquet ← GoogleのDremelが元.
対応
- !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には多様な選択肢
- memory内: Object, struct, list, array, hashtable, tree
対応
- !1 Language固有のformat
- !2 JSON, XML, various binary format
- !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
- どうreaderが知るか
- !!4 dynamicに生成されたschema
- Avro: dynamic生成 schemaと相性〇
- relationalなschemaからAvroのschema生成容易.
- → dbの内容をAvroのobject Container fileにdamp可
- db schemaの変更 → Avroでは自動変換.ThriftやPBでは手動にtag割り当て必要.
- relationalなschemaからAvroのschema生成容易.
- Avro: dynamic生成 schemaと相性〇
- !!5 code generationとdynamic変換
- !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
- !2 service経由でのdata flow: REST, RPC
- 大規模なapplicationを機能の領域ごとに小さいserviceに分割: micro service archtecture(古くはSOA)
- → 各serviceが独立
- !!1 Web Service
- !!2 RPCのproblem
- 場所の透過性の抽象化における根本のproblem
- remote serviceとlocal objectは根本から異なる
- → RESTはnetwork protocolであることを明示していて〇.
- !!3 現在のRPCの方向性
- !!4 RPCのdata encodingとevolution
- !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
- !!2 distributed actor framework
- actor model: 単一のprocessing内での並行処理
- actorにカプセル化するprogramming model
- → distributed actor framework: applicationを複数ノードにscale.
- 場所の透過性〇
- ↑ 単一processingですらlossを考えているため
- message brokerとactor modelを1つのframeworkに統合
- e.g.
- actor model: 単一のprocessing内での並行処理
まとめ
- 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広告配信、レコメンドシステム、マッチングアプリ、シフトスケジューリングなどで使える
- 2 category間のつながりの問題
章末問題
- 1.4: 九九で2桁の和が6になるものに目をつけるといいのかもしれない
- 1.6: BFS。地図上の最短経路を求める。
Ch02 計算量とオーダー記法
- 調べるべき組み合わせをマトリックスで考える→ 図2.3
- 一般的なパソコンで1秒間に処理できる計算ステップの回数: 109
- 各オーダーでの入力サイズと計算ステップ回数の関係→ 表2.2
- 指数時間: O(N!), O(2N)
- 多項式時間: Ndの定数倍で上から抑えられるもの
- 定数時間: O(1)
- 計算量: 以降は最悪計算時間量を指す
- ランダウのO記法の詳細
- オメガ、シータ
- 章末問題
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でプラスの位置を表せば〇
- 3.3
Ch04 設計技法(2): 再帰と分割統治法
- 様々な問題に対して、簡潔かつ明快なアルゴリズムを記述できる。
- 再帰関数のテンプレート: basecaseでreturn。その他は再帰。
- basecaseに対する処理が重要。
- 引数がbasecaseに近づくようにする。
- 再帰の例
- ユークリッドの互除法
- フィボナッチ数列
- 呼び出しの流れ: 図4.2
- → メモ化, キャッシュ
- 再帰関数を用いる全探索
- 部分和問題
- N番目について場合分け: 図4.4, code4.9
- メモ化
- 部分和問題
- 分割統治法
- まとめ
- 章末問題
- 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 問題
- グラフの問題としてとらえる。
- 過程をメモの値に集約
- 部分構造最適性: 元の問題の最適性を考えるときに、小さな部分問題についても最適性が要請される
- → このような構造を利用して最適値を順に決定していく手法が、動的計画法
- Frog 問題
- 動的計画法に関連する諸概念
- ナップサック問題
- 動的計画法以外にも解法がある。
- 動的計画法の部分問題の作り方の基本的なパターン: N個の対象物{0,1,...,N-1}に関する問題に対して、最初のi個の対象物{0,1,...,i-1}に関する問題を部分問題として考える。
- 各段階においていくつかの選択肢が存在するという状況は、動的計画法を有効に適用できそうだということを示す。
- 考えたテーブル設計でうまく遷移が作れなかった場合に、添え字を付け加えることで遷移が成立するようにする作業がよくある。
- 添え字を追加する作業: 選択肢をまとめ上げる粒度を細かくすることに対応。
- 動的計画法: 考えられる場合をグループごとにまとめるイメージの手法。グループの個数とグループ間の遷移の個数が最終的な計算量。
- 選ぶときと選ばないときの遷移を式にする。
- 図5-10: テーブル更新の様子。選ばなかった場合の同じウェイトの値と比較している。
- 編集距離
- 応用: diff command, spell checker, 空間認識・画像認識・音声認識などのパターンマッチング, バイオインフォマティクス(系列アラインメント)
- テーブル定義: dp[i][j]←Sの最初のi文字分と、Tの最初のj文字分との間の編集距離
- 編集距離: 対応を作る/ 最小コスト弾性マッチング問題: マッチさせる
- 区間分割の仕方を最適化
- まとめ
- 動的計画法は多くの問題に有効
- テーブルの設計パターンは意外と少ない。
- 固有の問題に対して、大局的なパターンと、その問題に固有の事情とを分けて考えられるようになることが大事。
- 章末問題
- 全体として: 値の定義と、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 各区間の平均値は別で求める必要あり。
- 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側
- プログラムのデバッグでも使っている考え方
- (整数ではなく)実数上の二分探索法(二分法ともいう)も可能。求めたい精度によって終了条件を規定する。
- 各整数xに対してtrue/falseの2値で判定される条件Pが与えられていて、ある整数l. r(l < r)が存在して、以下が成立しているとする。
- さらに一般化した二分探索法
- 応用例(1): 年齢当てゲーム
- 応用例(2): std::lower_bound()の活用例
- ペア和のK以上の中での最小値
- a[i]を固定して、bについて二分探索。O(NlogN)。
- ペア和のK以上の中での最小値
- 応用例(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を入れる。
- 条件は、midに対して指定の処理が可能かどうかのみ。
- 最小値の最大化。ソート+二分探索。
- Mはただ与えられた値に過ぎない。
- https://hcpc-hokudai.github.io/archive/algorithm_binary_search_001.pdf
- 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先のことのみを考えて、最善の選択を繰り返す方法論。
- 後先を考えず、その場での最善を選択することを繰り返す方法論。
- 1step先のことのみを考えて、最善の選択を繰り返す方法論。
- 貪欲法が最適解を導くとは限らない
- 貪欲法によって最適解が導ける問題は、その構造自体によい性質が内包されている可能性が高い。
- e.g. 最小全域木問題
- マトロイド性、離散凸性
- 貪欲法パターン(1): 交換しても悪化しない
- 最適化問題は、「探索範囲を予め絞れないか」の考察がきわめて有効
- f(x') >= f(x)が成立する、ある性質Pを満たすx'を、xを変形して得る。
- 最適化問題は、「探索範囲を予め絞れないか」の考察がきわめて有効
- 貪欲法パターン(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
- 配列
- 連結リスト
- 〇: 挿入、削除
- × : ランダムアクセス×
- 各要素をポインタでつなげる
- ダミーノード: 番兵
- 自己参照構造体を用いる。自分自身の型へのポインタをメンバに持つ構造体のこと。
- 連結リストの挿入操作と削除操作
- 挿入の実装
- 削除の実装
- 双方向連結リスト
- 配列と連結リストの比較
- 連結リストは限られた場面で大きな力。
- 連結リストは、単体ではなく、様々なデータ構造の部品として活用されることが多い。
- 要素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)の計算量を達成できる
- ハッシュテーブルの各要素にアクセスする計算量は、平均的にO(1+N/M)となる。
- 単純一様ハッシュの仮定
- C++, Pythonにおけるハッシュテーブル
- std::unordered_set, set
- set(C++)は、いずれのクエリもO(logN)で十分高速。平衡二分探索木の一種である赤黒木を用いて実現されている
- 連想配列
- まとめ
- 配列、連結リスト、ハッシュテーブルについて、「挿入」「削除」「検索」といったクエリに対するパフォーマンスを比較
- 処理したいクエリに応じて、適切なデータ構造を用いることが肝要。→ 表8.5
- 章末問題
- 8.5 ハッシュテーブルを使えばいけると思う
- 8.7 片方はハッシュテーブルを使って、もう片方でループ。K - b[i] = a[j]となるaがあるかどうかハッシュテーブルで判定する
Ch09 データ構造(2): スタックとキュー
- stack, queueの概念
- stack, queueの動作と実装
- いずれも配列を用いて簡単に実現
- queueはメモリ管理を効率よく行いながら実装することが大変 → 実践的にはstd::queueの使用が〇
- stackの動作と実装
- top(: 最後に挿入された要素の添え字の次の添え字) を用いる
- 「スタックに格納されている要素数」も表す
- top(: 最後に挿入された要素の添え字の次の添え字) を用いる
- queueの動作と実装
- 両端が開いている
- リングバッファ
- まとめ
- stack, queueは、コンピュータサイエンス全域で登場する基本的な考え方。
- 重要な応用例: グラフ探索。DFSやBFSという重要なグラフ探索技法を設計できる。
- 章末問題
- https://qiita.com/drken/items/6a95b57d2e374a3d3292
- 9.3 (をスタックに入れて、)でpopすればよさそう。
- 9.2 被演算子をpush, 演算子でpop
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分木という
- 二分木において、左側の子頂点を根とした部分木を左部分木、右は右部分木
- 二分木は、計算量解析において好都合な形状→様々なデータ構造において二分木の構造を採用
- ヒープ、二分探索木
- 根付き木において、各頂点vの子頂点の順序を考慮するとき、特に順序木という
- 強平衡二分木
- 根付き木の構造を持つデータ構造は、多くの場面で、各クエリを処理する計算量がO(h)(hは木の高さ) → 高さをできるだけ抑える
- → 強平衡二分木: 二分木であり、すべての葉の深さが高々1しか違わないもの
- 頂点数をNとして、高さがO(logN)
- すべての葉の深さが等しい二分木: 完全二分木
- 根付き木の構造を用いて、多彩なデータ構造を考えられる
- 二分木を用いるデータ構造の例(1): ヒープ
- 正確には二分ヒープを扱う
- ヒープとは
- 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
- 頂点vの親頂点をpとしたとき、key[p] >= key[v]が成立する
- 木の高さをhとしたとき、木の深さh-1以下の部分については、完全二分木を形成している
- 木の高さをhとしたとき、木の深さhの部分については、頂点が左詰めされている
- → ヒープは特に強平衡二分木となっている → 様々なクエリをO(logN)で処理できる
- 挿入、最大値の取得、最大値の削除が〇
- 値の検索は× → 平衡二分探索木を使う
- 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
- ヒープの実現方法
- 配列を用いて実現
- ヒープの深さ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記法で省略される定数部分が大きいので、ヒープで足りればヒープが簡便で〇
- 各頂点vがキーと呼ばれる値key[v]を持つ二分木であり、以下を満たすもの
- まとめ
- グラフは、対象物の関係性を表すことができる強力な数理科学的ツール
- グラフとして定式化して、問題を見通す
- 特殊なグラフとしての木
- 順序木は、連結リストの構造をより豊かにしたもの
- → ヒープや二分探索木などの多彩なデータ構造を設計
- 章末問題
- 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を使う
- https://qiita.com/drken/items/cce6fc5c579051e64fab#abc-087-d-people-on-a-line
- 直接つなげるのではなく、連結成分同士をつなげる
- rootまでの重みを持つ。差が重みになる
- 差が合わなかったらfalse、マージし切れたら(連結し切れたら)〇
Ch12 ソート
- 分割統治法、ヒープなどのデータ構造、乱択アルゴリズムの考え方など、さまざまなアルゴリズム技法を学ぶことができる題材
- ソートアルゴリズムに用いられるアルゴリズム技法を学ぶ
- ソートとは
- 与えられたデータの列を、所定の順序に従って整列
- 実用上とても重要な処理
- 前処理としても使われる
- 実用的にも理論的にも重要な処理 → 多数のアルゴリズムがある
- ソートアルゴリズムの良し悪し
- in-place性と安定性
- どのソートアルゴリズムがよいか
- ほとんどの場面で、各言語の標準ライブラリを用いれば十分
- ソートの使いどころの習熟が重要
- 挿入ソート
- マージソート
- 動作と実装
- 計算量と性質
- O(NlogN)
- not in-place
- → 組込系など、ソフトウェアの移植性を重視しつつアルゴリズムを常に高速に動作させたい場合には採用されにくい
- ただし、必要なメモリ容量は入力受け取りに要するメモリ容量の高々定数倍なので、問題ない場面も多い
- 安定〇
- 計算量解析の詳細
- クイックソート
- ヒープソート
- ソートの計算量の下界
- 比較ソートアルゴリズム: ソート順序が入力要素の比較にのみ基づいて決定される
- 最悪の場合は、Ω(NlogN)回の比較が必要
- 2h >= N!から求めていく
- 比較ソートアルゴリズム: ソート順序が入力要素の比較にのみ基づいて決定される
- バケットソート
- まとめ
- 章末問題
- 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回同じ問題に当たったら考えよう
- 12.1 インデックスと値の組を配列で持つ。値でソート。ソート後のインデックスを入れる。元のインデックスでソート。
Ch13 グラフ(1): グラフ探索
- グラフ探索を学ぶ意義
- あらゆるグラフアルゴリズムの基礎
- 単にグラフに関する問題を解決できるだけでなく、さまざまな対象物に対する探索を見通しよく扱えるようになる
- ウォーク、サイクル、パスや連結性も自在に扱える
- DFS,BFS
- グラフ探索の基本形
- 問題設定: グラフ上の代表的な1つの頂点s∈Vを指定して、sから辺をたどって到達できる各頂点を探索する
- stack(DFS), queue(BFS)を用いて実現
- todo, seenを管理する
- seen[x] = trueならばその頂点xを飛ばすのが重要
- グラフ探索の基本形
- 再帰関数を用いるDFS
- 簡潔に実装できる
- 再帰関数を用いることで、「行きがけ順」「帰りがけ順」という重要な概念も明快なものになる
- 「行きがけ順」と「帰りがけ順」
- 最短路アルゴリズムとしてのBFS
- 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): トポロジカルソート
- グラフ探索例(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|)
- 各頂点vに対して以下の値を求める
- 各頂点の深さ: 行きがけ時に求めた
- 各頂点を根としたときの部分木のサイズ: 帰りがけ時に求めた
- 行きがけ順を意識した処理は「親頂点についての情報を子頂点に配る」のに適していて、帰りがけ順を意識した処理は「子頂点の情報を集めて親頂点の情報を更新する」のに適している
- 根なし木に対しても便宜的に根をどれか1つ決めて根付き木とすることで、しばしば見通しが良くなる
- まとめ
- 章末問題
- 13.6 https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-6-%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E6%A4%9C%E5%87%BA
- 与えられたグラフがサイクルを含むということは、ある頂点 v に対して、頂点 v から出発した探索が、v から行くことのできる全頂点の探索を終えるよりも先に (すなわち帰りがけの状態になる前に)、v に戻って来てしまうということ
- 13.6 https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-6-%E3%82%B5%E3%82%A4%E3%82%AF%E3%83%AB%E6%A4%9C%E5%87%BA
Ch14 グラフ(2): 最短路問題
- グラフの各辺に重みがある場合の最短路問題に対する解法を見る
- → 現実世界の問題への応用範囲が飛躍的に広がる
- DPや貪欲法の応用がある
- 最短路問題とは
- グラフ上で長さが最小の路(ウォーク)を求める問題
- l(e): 各辺の重み
- l(W): 路W(walk)の長さ
- l(C): 閉路(cycle)Cの長さ
- l(P): 道P(path)の長さ
- カーナビや鉄道の乗換案内サービスという応用が広いだけでなく、理論的にも重要な問題
- 重み付き有向グラフ
- 一般性が高い考察対象
- 単一始点最短路問題
- 各頂点への最短路を重ね合わせると頂点s(=0)を根とした根付き木になる
- 負辺と負閉路
- 負閉路はいくらでも路長を小さくできる
- 負閉路を持たないか、始点から負閉路に到達できない、または負閉路から頂点vに到達できない場合は、最短路を求められる
- 最短路問題の整理
- 緩和
- DAG上の最短路問題: 動的計画法
- DAGにおける緩和処理の順序のポイント
- 各辺e=(u, v)に対して緩和処理を実施するときには、頂点uに対するd[u]が真の最短路長に収束している
- ↑ トポロジカルソートで担保。緩和すべき辺の順序を明らかにできる
- DAGにおける緩和処理の順序のポイント
- 単一始点最短路問題: ベルマン・フォード法
- 有効閉路を含む有向グラフに対しても最短路を求めることのできるアルゴリズムを考える
- もし始点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
- 要素の型、内部コンテナ、昇順降順を指定する
- 全点対間最短路問題: フロイド・ワーシャル法
- 参考: ポテンシャルと差分制約系
- ポテンシャル: 各節点間がピンと張られているとは限らない場合において、各節点の位置関係としてあり得るもの
- 各頂点vに対して値p[v]が定まっているとき、任意の辺e=(u, v)に対して、p[v]-p[u]<=l(e)を満たすようなp
- 最短路問題の最適性の証拠
- ポテンシャル: 各節点間がピンと張られているとは限らない場合において、各節点の位置関係としてあり得るもの
- まとめ
- グラフ上の最短路を求める問題の解放として、古典的によく知られているものをまとめた章。
- DP、貪欲法、グラフ探索、ヒープなどの、アルゴリズム設計技法・データ構造が活躍
- 最短路問題は実用上重要な問題なだけでなく、理論的に重要な位置づけ
- 章末問題
- 14.1 トポロジカルソート→DP
- 14.2 https://drken1215.hatenablog.com/entry/2019/02/16/075900
- 14.3 https://drken1215.hatenablog.com/entry/2019/07/01/111500
- 頂点vを(v, 0), (v, 1), (v, 2)に拡張する
- 14.4 https://betrue12.hateblo.jp/entry/2018/12/08/000020
- 0-1BFS.両端に挿入できるキューを使う.
- 14.5 http://fluffyowl.hatenablog.com/entry/2017/11/07/194832
- https://img.atcoder.jp/arc084/editorial.pdf
- 全ての正整数は,1から始めて,以下の2つの操作の繰り返しで作れる
- 1足す.各桁の和は1増える.
- 10倍する.各桁の和は変わらない.
- 各頂点をmodKで同一視することで,頂点を0からK-1のK個で考えることができる.
- 1から0への最短路を求める.
- 0-1BFSを用いる
- modKで0の集合 = Kの倍数の集合
Ch15 グラフ(3): 最小全域木問題
- ネットワーク設計において基本的な問題の1つ
- いくつかの通信拠点をすべて通信用ケーブルでつなぎ,すべての建物間で通信できるようにしたいとする.これを最小コストで実現する方法を問う問題.
- クラスカル法で解く.
- 貪欲法に基づく.
- 構造自体によい性質が内包されている.
- きわめて深淵で美しい理論が背後にある問題.
- 貪欲法に基づく.
- 最小全域木問題とは
- w(e): グラフの各辺の重み
- Gの部分グラフであって木であるもののうち,Gの全頂点をつなぐものを全域木(T)と呼ぶ.
- w(T): 重みは,w(e)の総和.
- 最小全域木問題とは,重みが最小の全域木を求める問題.
- 最小の長さのケーブルで全地点を接続する問題.
- クラスカル法
- クラスカル法の実装
- グラフGの各辺を,辺の重みが小さい順にソート.
- Union-Findを用いることで,効率的に実現.
- 開始時点では,Union-Findの各頂点が単独で別々のグループを形成している状態とする.
- 新たな辺e=(u,v)を追加するとき,Union-Find上の点u',v'について,unite(u',v')を実施する
- サイクルが形成されてしまうかどうかを,u'とv'が同じグループに属するかで判定できる
- O(|E|log|V|)
- 全域木の構造
- クラスカル法の正当性
- 最小全域木の最適性条件
- 局所最適解
- 全域木間での辺の交換
- 連結な重み付きグラフ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凸集合を考えることもできる.
- → 離散凸解析
- まとめ
- 章末問題
Ch16 グラフ(4): ネットワークフロー
- ネットワークフロー理論: 「きれいに解ける」問題の代表
- ネットワークフローを学ぶ意義
- 「効率よく多項式時間で解ける問題」を象徴する存在.
- 興味深い性質や構造がある.
- 多彩な応用
- 連結度,二部マッチング,プロジェクト選択
- ある程度の制約条件までは表現できる柔軟性もある.
- ネットワークフローで解ける問題を見逃すのはもったいない.
- 最大流問題と最小カット問題を見る.
- グラフの連結度
- 最大流問題において,各辺の容量を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|)
- フォード・ファルカーソン法の実装
- 難所:各辺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]と表せる
- 難所:各辺e=(u,v)に対して,逆向きの辺e'=(v,u)を取得できるようにする
- 応用例(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
- このグラフ上で最小カット問題を解くことで,ボタンの押し方の最適解を求められる.
- {s,t.0,1}を頂点集合に持つグラフであって,以下の条件を満たすものを構成したい
- N個のボタンとM個の制約条件に対しても自然に拡張できる.
- プロジェクト選択問題で考慮する制約条件
- まとめ
- 章末問題
- 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
- EXP: 指数時間アルゴリズムで解ける問題のクラス
- P≠NP予想
- NPに属するがPに属さないという問題が見つかっていない.
- NP完全
- 多項式時間帰着の例
- 点被覆問題
- 部分和問題
- NP困難
- 停止性問題
- NPに属さないがNP困難
- コンピュータプログラムPと,そのプログラムへの入力Iが与えられる.Iを入力としてPを実行したとき,Pが有限時間で停止するかどうかを判定する.
- まとめ
- 現実に解決できそうもない難問Xと出くわしたときは,知られているNP困難問題Yをどれか1つ持ってきて,YをXに帰着できないか考えることが有効.
- 章末問題
- (メモなし)
Ch18 難問対策
- NP困難問題との対峙
- 個別な入力ケースに対しては,現実的な時間で解を導ける可能性がある.
- 特殊ケースで解ける場合
- 貪欲法
- 局所探索と焼きなまし法
- 近傍: 「ほんの少し変更を加えたもの」
- 局所最適解が全体の最適解とは限らない.
- → 焼きなまし法.f(x)の値が改善されないような近傍への移行も確率的に許す.
- 温度と呼ばれるパラメータでその確率を制御する.
- 分岐限定法
- 枝刈り
- 「これから探索しようとしているノード以降がそれまでの最良解Lより良い解を導く可能性がない」と判断できたら,そのノード以下の探索を打ち切る.
- 理論的な計算量は下げないが,現実世界の実際の問題に対しては極めて高速に動作することが多々ある.
- 整数計画問題への定式化
- 近似アルゴリズム
- まとめ
- 章末問題
『コンピュータネットワーク 第5版』 第1章(以降は未書き起こし)
ch01 序論
- computer network: 単一の技術で相互接続された自律的コンピュータ(複数)として扱う。
- 分散システム: ユーザには単一の均一なシステムに見える。単一のモデル、パラダイムを持つ。ネットワークで実現される。ネットワークとの違いは、ハードウェアではなくソフトウェアにある。
- 例: www
1.1 computer networkの目的
- 資源シェアリング
- VPN
- クラサバモデル
- 例: ウェブアプリケーション
- 2つのプロセスがかかわる
- 通信媒体、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
- broadcast, point-to-point
- 規模
- Personal Area Network ~ Inter Network → 惑星間Inter Network
- PAN
- bluetooth
- master-slave
- bluetooth
- Local Area Network(LAN)
- Metropolitan Area Network(MAN)
- cable TV systemから
- WiMAX
- Wide Area Network(WAN)
- 1つの国や大陸
- subnetがホスト間でメッセージを送る。
- 伝送回線、交換要素(switch)
- switch: 2本以上の伝送回線の接続に特化したコンピュータ。ルータなど
- 伝送回線、交換要素(switch)
- 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交換
- packet: network layer のmessage
- 高信頼connection指向の例: ファイル転送
- 境界あり:message列(本)/ 境界なし:byte-stream(映画)
- 低信頼(=確認通知) connectionless サービス(電報のよう)
- データグラムサービス
- e.g. VoIP
- 確認通知データグラム → 信頼性要
- e.g. ケータイのテキストメッセージ
- request-reply service
- e.g. クラサバモデルの通信の実現
- connection指向: 管のように振る舞う。
- サービスの一覧
- Ethernetは高信頼通信なし
- サービス・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
- application layer
- OSI: modelそのもの
- TCP/IP: protocol
- application layer
- transport layer
- network layer
- link layer
- physical layer
- OSIとTCP/IPの比較
- OSIの中心概念: service/ interface/ protocol
- connection指向/ connectionlessへのサポートの違い
- OSI modelとprotocolの批評
1.5 networkの例
- internet
- ARPANET
- NSFNET
- wwwの出現で爆発的に大きくなった
- internetのarchitecture
- 従来の異なるnetworkが用いられていた用途に対して、1つのnetworkが用いられる電気通信の収束
- → 激変の推進力
- internet access/ connectivityをISPから買う
- Internet eXchange Point(IXP)で、ISPはトラフィックを交換するためにnetworkを接続する
- 接続したISPは互いにピアしているという
- 小さなISPがtransit(より遠くのISP)にお金を払う
- tier 1のISP: e.g. AT&T, Sprint
- data center with Server farm
- 従来の異なるnetworkが用いられていた用途に対して、1つのnetworkが用いられる電気通信の収束
- 「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容量増大
- cellular network
- UMTSのarchitecture
- UMTSのnetwork内で、Public Switched Telephone Network(PSTN)のような回線交換core network上にconnectionを設定する
- General Packet Radio Service(GPRS) @ data service
- 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
- 無線は本質的に放送型の媒体
- 同時に送った複数の伝送が衝突して受信の干渉するという問題がある
- ←→ CSMA(Carrier Sense Multiple Access)方式: 実用上うまく動く
- 移動性の問題
- ↑ APをもった複数セルを接続する分配システムを構成
- 同時に送った複数の伝送が衝突して受信の干渉するという問題がある
- Security
- 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
- Industrial, Scientific, and Medical(ISM)帯
1.6 networkの標準化
目的: 異なるコンピュータが通信 + 製品市場を拡大
- → 大量生産、製造規模の経済性、より良い実装、価格低下と普及
標準: 相互運用性に何が必要か定義する。
- WiFi Alliance
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)
- DIS(Draft International Standard)
- CD(Committee Draft: 委員会草案)
- ISOのITU-Tの構成員。
- 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
- → Draft Standard
- World Wide Web Consortium(W3C) @Web
1.7 メートル法の単位
- m: ミリ。μ: マイクロ。
- 1より大きいと大文字
- B: byte, b: bit
- K: 210 @ memory
1.8 本書の概要
- 原理と実践
- architectureの観点に限定
1.9 まとめ
- (メモなし)
『継続的デリバリー』 第15章 学習メモ
継続的デリバリーの管理の概観
1.はじめに
継続的デリバリーにおける、継続的デリバリーの管理についての調査記録です。
継続的デリバリーの中での、継続的デリバリーの管理についての概観を記載します。
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』の第15章に対応します。
2.概要・目的
継続的デリバリーの管理の観点は以下の通り。
- 継続的デリバリーはソフトウェアビジネスを前進させるための新しいパラダイム
- コーポレートガバナンス(適合性)とビジネスガバナンス(パフォーマンス・業績)の対立
- デプロイメントパイプラインの作用
- コーポレートガバナンスのための透過性
- ビジネスガバナンスのためのフィードバック
- インクリメンタルなデリバリー
- 自動化による信頼性の向上
- 素早く信頼できるリリース
- リスクやコストの削減
3.対応概要
構成管理とリリース管理のためのステータスモデルは以下を示す。
- プロジェクトの検証の方法、検証のための観点
ソフトウェアデリバリーのライフサイクルの観点は以下の通り。
- 発見期
- ステークホルダーの特定
- 開始期
- 問題解決をステークホルダー間で共有
- 構築期
- 最もシンプルなストーリーに対して、以下を実証
- バージョン管理
- CIでのテスト
- 手動テスト
- 環境へのデプロイ
- 最もシンプルなストーリーに対して、以下を実証
- 開発・リリース期
- イテレーティブでインクリメンタルなプロセスの規範の適用とそれによる作用
- 運用期
- 開発・リリース期と同じく、新たな機能の追加でも、分析・開発・テスト・リリースのプロセスとする
- データ管理のみ異なる
4.対応詳細
(1)リスク管理プロセス
リスク管理プロセスの観点は以下の通り。
(2)デリバリーによくある問題
デリバリーによくある問題として以下が挙げられる。
- 頻度の低いデプロイメント・バグのあるデプロイメント
- 貧弱な品質
- 管理が貧弱なCIプロセス
- 貧弱な構成管理
(3)コンプライアンスと監査
デプロイメントパイプラインの規制への準拠の観点は以下の通り。
- 自動化
- トレーサビリティ
- 観察・分析の共有
- 変更の管理
- 承認プロセス
5.影響・作用
管理作業により、ソフトウェアのデリバリーを効率的に行いつつリスク管理も適切に行い、規制制度にも準拠できる。
6.おわりに
以上が、継続的デリバリーの中での、継続的デリバリーの管理についての概観です。
7.参考文献
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』 第15章 継続的デリバリーを管理する
『継続的デリバリー』 第14章 学習メモ
バージョン管理の概観
1.はじめに
継続的デリバリーにおける、バージョン管理についての調査記録です。
継続的デリバリーの中での、バージョン管理についての概観を記載します。
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』の第14章に対応します。
2.概要・目的
バージョン管理は、すべての変更の履歴を管理し、複数チームで開発するアプリケーション全体のコードベースを管理する。
3.背景
リビジョンとは、ディレクトリ群の中にある変更されたファイルのセットで構成されたもの。チェンジセットとも言う。 各リビジョンにはリポジトリ内の全ファイルの、ある特定の時点のスナップショットが含まれている。 リビジョン管理システムの歴史についての観点は以下の通り。
- CVSにあった問題
- SVNによる解決
- 商用のバージョン管理システム
- 〇楽観的ロック/×悲観的ロック
- 衝突の解消
4.対応概要
(1)ブランチとマージ
ブランチとマージの分析の観点は以下の通り。
- コードラインポリシー
- マージの問題
- リリースブランチ以外を作らないことの作用→CI
(2)メインラインでの開発
メインライン上での開発の観点は以下の通り。
- 高速フィードバックによりほぼ常にリリース可能な状態。
- メインライン上での開発のCIへの作用
- 不要ブランチの回避
- 抽象化によるブランチパターンの適用
5.対応詳細
(1)分散バージョン管理システム
分散バージョン管理システムの観点は以下の通り。
- 分散バージョン管理システムの作用
- コミット権のボトルネックの解消
- 分散バージョン管理システムの歴史
- 分散バージョン管理システムのCIへの対応
- 企業環境にも対応するための多くの機能を持つ
- 分散バージョン管理システムの使い方と作用
(2)ストリームベースのバージョン管理システム
ストリームベースのバージョン管理システムの観点は以下の通り。
- 「継承」が可能
- 問題:CI・CDへの違反
- Gitなどの分散バージョン管理システムで解決可能
- 静的ビューと動的ビュー
- 問題:速度とロールバック
(3)ブランチ
ブランチの観点は以下の通り。
- リリース用のブランチが解決する問題
- フィーチャーブランチのCIに対する問題と対応
- オープンソースソフトウェアで十分に制約を満たしたときのみ機能する
- チームブランチ≒フィーチャーブランチ
- 以下のような条件が揃って初めて、疎結合なコンポーネントへの移行に使える
- 分散バージョン管理システムの機能
- インクリメンタルな開発
- カプセル化
- 以下のような条件が揃って初めて、疎結合なコンポーネントへの移行に使える
6.影響・作用
バージョン管理のパターンがデプロイメントパイプラインの設計の重要なポイントとなる。
バージョン管理によって素早くローリスクなリリースが可能となる。
7.おわりに
以上が、継続的デリバリーの中での、コミットステージについての概観です。
8.参考文献
『継続的デリバリー 信頼できるソフトウェアリリースのためのビルド・テスト・デプロイメントの自動化』 第14章 高度なバージョン管理