Think Distributed

Database and Distributed Systems

paper

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 の…

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 で述べているよ…

Reading: The Design and Implementation of a Log-Structured File System

https://web.stanford.edu/~ouster/cgi-bin/papers/lfs.pdf を読みました。この論文は Sprite LFS というファイルシステムについて説明している論文となります。 従来のファイルシステムの問題点 小さいデータをバラバラな場所に書いているため、HDD のシー…

Reading: AlphaSort

AlphaSort 概要 CPU cache-sensitive なソート方法について論じた論文。 内部的には (key-prefix, the pointer to a record) のタプルをキーにした QuickSort を使う。 何が新しいか cache locality を考慮に入れてソート方法を選択している点。 quick sort …

Reading: Epidemic Broadcast Trees

1. Introduction tree-based and gossip based primitives. メッセージの伝送に unreliable IP multicast を使う。欠点として IP-multicast に依存していること、2 つの異なる protocol が必要で複雑であること。 この論文で説明するのは、tree-based で gos…

Reading: Ceph: A Scalable, High-Performance Distributed File System

1. Introduction Ceph は peta-byte スケールに対応するための file system(と Object Storage) Object Storage Device(OSD), Metadata Server(MDS)があって、クライアントは中央集権的な MDS とやり取りした後に実際のデータは各 OSD から取得するというモ…

Reading: HyParView: A Membership Protocol for Reliable Gossip-Based Broadcast

HyParView を読んだのでメモ。 前提 transport protocol は信頼できるものが必要。 failure detector には TCP を使う。 well known server から contact node を教えてもらえる必要がある。 well known server の詳細はこの論文では説明されない。 概要 gos…

Reading: In Search of an Understandable Consensus Algorithm(Raft)

In Search of an Understandable Consensus Algorithm を読んだのでざっくりとメモ。 Paxos のよくなかった点 アルゴリズムに曖昧な部分がある。 Lamport が論文で説明しているのは single-decree なアルゴリズムで、multi-decree への拡張方法が不明瞭。 ゆ…

Reading: Space/Time Trade-offs in Hash Coding with Allowable Errors

Space/time trade-offs in hash coding with allowable errors 概要 新しい hash conding の手法(つまり Bloom Filter のこと)は以下に特徴がある。 reject time and space (判定速度とメモリ空間効率が高い) 誤りを許容する (第一種過誤つまり偽陽性がある)…

Reading: Performance in Practice of String Hashing Functions

Performance in Practice of String Hashing Functions は boost の hash function を決める際の根拠となっている論文みたいなので読んでみました。 Conclusions shift-add-xor string hashing functions の class から hashing function をランダムに選ぶと…

Reading Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems

TL;DR Event-Driven から coroutine ベースの実装にするとメモリーオーバーヘッドが下がって、コードも短かく書ける。 以下論文の内容です。 Abstract Event-Driven programming でメモリオーバーヘッドは下がるけど、state machine プログラミングを求めら…