Think Distributed

Database and Distributed Systems

distributedsystems

Erasure Coding による CPU, IO 負荷を下げる案

しばらく前から仕事で Erasure Coding を使って保存されたデータを復元する処理の負荷を下げる方法について考えている。なぜこんなことをしているかというと自社製のストレージのデータが EC を使うようになっているから。 すでに実装された機能として、 I/O…

Reading: GEMS: Gossip-Enabled Monitoring Service for Scalable Heterogeneous Distributed Systems

論文 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.2604 highscalability.com でおすすめされていた論文。 flat gossiping 主要なデータ構造は gossip list, suspect vector, suspect matrix, live list の4つ。 gossip list に他ノードか…

Reading: A Gossip-Style Failure Detection Service

https://www.cs.cornell.edu/home/rvr/papers/GossipFD.pdf 故障の誤検知の確率がクラスタ内のプロセス数に依存しない 小数の故障ノードやメッセージロスがある状態でも誤検知を起こしづらい ノードのローカルクロックがズレてもその影響を無視できる 検知時…

Reading: Frangipani: A Scalable Distributed File System

Frangipani: A Scalable Distributed File System システム構成 Petal 分散ストレージ。Frangipani が内部的にストレージとして使う。 Reading: Petal: Distributed Virtual Disks - Think Distributed Frangipani カーネルモジュールを提供する。 OS の Fil…

Reading: Petal: Distributed Virtual Disks

http://www.scs.stanford.edu/nyu/02fa/sched/petal.pdf モジュール構成 Global State Module 分散システムの機能を担う。 Liveness Module 分散システムの機能を担う。 Recovery Module クラッシュした時のためのリカバリ処理を担う。 Virtual to Physical …

Reading: Ω Meets Paxos: Leader Election and Stability without Eventual Timely Links

www.microsoft.com 今からやるなら Paxos より Raft の方をおすすめしたいわけですが、それはさておきこの論文の Abstract, Related work は survey として秀逸と感じました。ピュア(定義の列挙は読者にとっては自明として省略)な非同期システム(通称 FLP im…

Reading: Proving the Correctness of Multiprocess Programs

https://dl.acm.org/citation.cfm?id=1313439 この論文が safety と liveness の概念を非形式的に(formal な定義は Reading: Defining Liveness - Think Distributed で言及している論文を参照)導入したと私は認識していて、その点でよく参照されている論文…

Reading: Defining Liveness

https://www.cs.cornell.edu/fbs/publications/defliveness.pdf この論文では、 Safety と Liveness の形式的な定義 各性質(状態遷移の無限列の集合として定義される)は safety と liveness の intersection で表現できる を示した点で重要です。2 の結果は …

Reading: Unreliable failure detectors for reliable distributed systems

メモ eventual weak accuracy 全プロセスが障害状態とみなされてしまうタイミングが存在する。 eventual な性質により、ある時刻以降は正しく認識される。 weak completeness から strong completeness には還元可能 ローカルの failure detector module の…

Failure detector の構成

定義 en.wikipedia.org Perfect Failure Detector 同期システム上で timer を使う 故障していないプロセスに対して INQUIRY メッセージを投げる。 時間以内に応答してこなかったプロセスは"故障している"とマークする。 Fair Communication: 全プロセスのペ…

Reading: The Weakest Failure Detector for Solving Consensus*

https://dl.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=135451 ちょっと証明までは追いきれないですが、要旨だけをメモ。 Chandra and Toueg. Unreliable failure detectors for reliable distributed systems. JACM 43(2):225–267, 1996 で述べているよ…