Think Distributed

Database and Distributed Systems

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

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

GF(2)上の原始多項式

次数 原始多項式 1 x + 1 2 x2 + x + 1 3 x3 + x + 1, x3 + x2 + 1 4 x4 + x + 1, x4 + x3 + 1 5 x5 + x2 + 1 6 x6 + x + 1 7 x7 + x + 1 8 x8 + x4 + x3 + x2 + 1

DB Weekly #282

dbweekly.com 先週多忙により時間がなかったため 1 週遅れで DB Weekly #282 を読んでいくということで。 QuestDB · Always on time Java で書かれた Time Series な DB とのこと。何が既存のものより良いのかは全く分からず。 www.youtube.com 2006 年頃は…

Erlang OTP 22 の変更点

OTP 22 Highlights – A Blog from the Erlang/OTP team – The Erlang/OTP team at Ericsson, the implementors and maintainers of Erlang/OTP. コンパイラが書き直された 従来は Erlang AST -> Core Erlang -> Kernel Erlang -> Beam Asm だったが、Kernel …

Erlang OTP 21 の変更点

My OTP 21 Highlights – A Blog from the Erlang/OTP team – The Erlang/OTP team at Ericsson, the implementors and maintainers of Erlang/OTP. IO で port ではなく nif を使うようになった。 ベンチマークでは read で 2.8 倍スループットが上がってい…

Erlang OTP 22 で性能改善された点

Retiring old performance pitfalls – A Blog from the Erlang/OTP team – The Erlang/OTP team at Ericsson, the implementors and maintainers of Erlang/OTP. 名前付き関数 名前付き関数(関数内での名前を付けたクロージャー)の呼出をコンパイラは関数内…

Rust 1.39 の変更点

blog.rust-lang.org そろそろ 1.40 が出そうな気がしますが。 The .await is over, async fns are here async が一部安定化されて async fn で future を返せるようになった。Result と組み合わせるのはどうやるの?と思ったけれど、 future.await? みたいに…

DB Weekly #281

dbweekly.com 率直に言って、今回の DB Weekly はおもしろくないです。 ksqlDB: The event streaming database purpose-built for stream processing applications. ksqlDB is primarily useful for three broad categories of applications: Building and s…

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 で言及している論文を参照)導入したと私は認識していて、その点でよく参照されている論文…

Erlang で書き捨てのスクリプトを実行する方法

以下のファイルをコマンドラインから実行したいとします。 -module(foo). -export([create_file_slow/2]). create_file_slow(Name, N) when is_integer(N), N >= 0 -> {ok, FD} = file:open(Name, [raw, write, delayed_write, binary]), if N > 256 -> ok =…

DB Weekly 280

dbweekly.com 久しぶりに DB Weekly を。 PostgreSQL: PostgreSQL 12.1, 11.6, 10.11, 9.6.16, 9.5.20, and 9.4.25 Released! bitshiftright() が入力のバイト列が 8 の倍数じゃない時に間違った結果になるという今さら?というバグフィックスがある模様…。 …

erlc の使い方

普段は rebar を使っていますが、稀に erlc をそのまま使いたくなる時があるので使い方をメモしておきます。 コンパイルする(beam を生成する) $ erlc -Wall -I include/ -o target/ -smp foo.erl こうすると、target/foo.beam が生成されます。-Wall はすべ…

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

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: Web API: The Good Parts

Web API: The Good Parts を読みました。Web API を作る際に考慮すべき点を概観するには良いけれど、A と B のどちらにすべきか?と悩みがちな点に答えを出してくれるわけではなく、そこが期待していたものとズレているという印象でした。 また、書かれたの…

Reading: Linuxシステムプログラミング

I/O に関係する部分だけ読みました。以下感想などを徒然と。 2 章 ファイルI/O API の使い方を説明しているだけなので、すでに libc のファイル I/O について知っていたら読み飛ばして問題ないです。唯一知らなかったのは ungetc を複数回呼んだ時の挙動は実…

MogileFS のファイルに対応するディレクトリ名の決め方

メモ。 # returns directory that a fid will be in # $fid may or may not have leading zeroes. sub dir { my $fid = shift; $fid =~ s!^0*!!; $fid = "0"x(10-length($fid)) . $fid if length($fid) < 10; my ($b, $mmm, $ttt) = $fid =~ m{^(\d)(\d{3})(…

erlang でモジュールロード時に関数を実行する

-on_load(do_something/0). で callback を登録しておけばモジュールのロード時に実行されます。 -module(boo_app). -behaviour(application). -on_load(print_usage/0). %% Application callbacks -export([start/2, stop/1]). %%=========================…

ByteBuffer の使い方とベストプラクティス

ByteBuffer の使い方をまとめます。 まず、基本的な設計と仕様について。ByteBuffer は以下の特徴を持ちます: 単に byte[] をラップしただけの場合とオフヒープにアロケートしたメモリを保持する場合がある position でメモリ領域の先頭位置から見た、現在の…

Erlang で atom を動的に作る

atom を生成できる数に上限があり、なおかつ GC 対象にはならないため Erlang で atom を動的に作るのは基本的に筋が悪いのですけど、動的に atom を作りたくなることがままあります。 そういう時は以下のようにします。 4> list_to_atom(lists:concat([hoge…

Erlang でファイルの読み書き

Erlang の file モジュールの使い方の簡単な紹介です。 ファイルを開く file:open を使います。第2引数にモードを指定する時は以下の方針が良いでしょう。 read/write ために開く場合 [raw, binary, read, write] read only で開く場合 [raw, binary, read] …