Think Distributed

Database and Distributed Systems

algorithm

文字列に対するハッシュ関数

UNIX プログラミングテクニックという本を10年ぶりぐらいに読み返していたら、文字列に対するハッシュ関数として以下の関数が紹介されていた。Wikipedia によるとどうもこれは ELF で使われているハッシュ関数でもあるらしい。 #include <stdio.h> unsigned long hash</stdio.h>…

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: Ω Meets Paxos: Leader Election and Stability without Eventual Timely Links

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

Reading: Epidemic Broadcast Trees

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

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

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

MPSC Queue in C

Non-intrusive MPSC node-based queue 上記 URL は multi producers and single consumer 向けの queue の実装で、akka の actor の実装でもこのアルゴリズムが利用されています1。この queue の良い点は記事内で説明されているのでそちらを読んでください。…

Quicksort Revisited

転職活動のコーディングインタビューに備えてクイックソートを勉強し直していました。 それで、クイックソートなんて実装することはまずないだろうと思って今まで適当にやっていたので、今さら気が付いたのですが、クイックソートは pivot を適当に選ぶと停…

Modulo Multiplication

たまに大きな数同士のかけ算をオーバーフローさせずに計算し、その modulo が取りたい時があります。 多倍長演算を実装すればいいわけですが、大変面倒なので何か簡単な方法はないかなーと調べていたらありました。 C++ で書くと以下のようになります。 #inc…

Type inference algorithm described in Modern Compiler Implementation in ML

Modern Compiler Implementation in ML で説明されている algorithm を実装したので、参考にしてください。 ocaml-typeinference

Reading: Stanford CS166 van Emde Boas Trees

CS166: DataStructures の van Emde Boas Trees を読みました。 Ordered Dictionaries(以下 OD = Ordered Dictionary) insert(x), is-empty(), lookup(x), delete(x), max(), min(), successor(x), predecessor(x) をサポートするデータ構造 BST は上記の操…

Reading: Stanford CS166 Cuckoo Hashing

CS166: DataStructures の Cuckoo Hashing を読みました。 Cuckoo Hashing lookup は worst-case で O(1) delete は worst-case で O(1) insert は amortized, expected で O(1) (高確率で実現可能) hash table の cuckoo graph が complex(後述) になる場合…

Reading: Stanford CS166 Disjoint Set Forest

CS166: DataStructures を読んだのでメモ。 Disjoint Set Forest というのは、いわゆる Union Find の話です。 dynamic connectivity にどう対処するか? Euler tour trees は forests で解決した。 今回は incremental に connectivity が追加される問題に…