Think Distributed

Database and Distributed Systems

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

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

#include <stdio.h>

unsigned long hashpjw(char *s) {
  char *p;
  unsigned long h = 0;
  for (p = s; *p; p++) {
    h = (h << 4) + (*p);
    unsigned long g = 0;
    if ((g = h) & 0xF0000000) {
      h ^= g >> 24;
      h ^= g;
    }
  }
  return h;
}

int main() {
  printf("%zd\n", hashpjw("abcd"));
  printf("%zd\n", hashpjw("abcdef"));
  printf("%zd\n", hashpjw("abcdefg"));
  printf("%zd\n", hashpjw("abcdefgh"));
  return 0;
}

DB Weekly #282

dbweekly.com

先週多忙により時間がなかったため 1 週遅れで DB Weekly #282 を読んでいくということで。

QuestDB · Always on time

Java で書かれた Time Series な DB とのこと。何が既存のものより良いのかは全く分からず。

www.youtube.com

2006 年頃は上から Oracle, MySQL, SQL Server という感じでまぁそうですよねという感想ですね。2012 年頃から PostgreSQL がシェアをのばしてきていて(それでも3%程度ですが)、MySQL はシェア 20% を切ってるのが興味深い点ですね。PostgreSQL が再評価されるきっかけになったのは Heroku の影響と思ってますがどうなんでしょう。

stevearc/dql: A SQL-ish language for DynamoDB

DynamoDB 向けの SQL インターフェースを提供するライブラリ。DynamoDB ってコストパフォーマンスが悪すぎる印象で真面目に使ったことないんですけど、確か独特なクエリー言語(というか JSON?)でクエリーを投げなければならず私も使いづらいなぁとは思いましたね。

というか、最近の SQL への回帰ってあんまり良くない印象で、SQL よりまともなクエリー言語を開発する方向に向かって欲しいです。

UUIDs are Popular, but Bad for Performance — Let’s Discuss - Percona Database Performance Blog

UUID を使うと MySQL の仕組み上 IOPS にも影響がありすぎるから、Pseudo random order になるようにするか、UUID を integer にマッピングするかした方が(まだ)良いよというお話。UUID を入れちゃうのって確かにやりがちですよねぇ。

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 を Beam SSA に(ほぼ)置き換えた。
    • OTP 22 からは Erlang AST -> Core Erlang -> Kernel Erlang -> Beam SSA -> Beam Asm こうなったとのこと。
    • bit syntax が強化されて、従来よりも2倍程度早くなった模様。
    • 同一モジュール内での型の受け渡し時に型チェックの最適化が入って、型チェックが省略できるケースが増えた。
      • BEAM のコードで ope が減る。
  • 実験的に socket API が追加された。
    • gen_tcp, gen_udp ではない低レベルなソケット通信が実装可能になる。
    • OTP 23 で高レベルな API も追加される予定。
  • ets の ordered_set で concurrent write ができるようになった
    • 複数プロセスからの書き込み時にスケーラビリティが向上した。
  • TLS の性能改善
  • 分散 erlang でのフラグメント化されたメッセージのサポート
    • デカいメッセージを分散 erlang で送ろうとするとブロッキングする問題があるので。
    • 従来のフラグメント化しないメッセージも引き続き使われる。
    • 番号順に相手に到達しなければならない、など色々制約はある。
  • counters, atomics, persistent_term モジュールが追加された。
  • メモリ最適化
    • メモリのキャリアが複数のアロケータータイプ間で移動することができるようになった(PR1854)
    • プールされているキャリアにある空きメモリブロックを OS に返せるようになった(PR2046)

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 倍スループットが上がっていた。
    • もともと port 上で動いていたのは dirty IO scheduler 上で IO を動かすためだった模様。
  • I/O polling options in OTP 21 – A Blog from the Erlang/OTP team – The Erlang/OTP team at Ericsson, the implementors and maintainers of Erlang/OTP.
    • +K option が消えてカーネル空間での poll 実装がデフォルトになった。
    • これまではユーザー空間(というか Erlang スケジューラー)での poll だった。
    • OTP 21 では --disable-kernel-poll を指定すれば OTP 20 までの挙動にできるらしいが、コンパイル時に指定する必要がある。
    • +IOt 3 とかで IO イベントを通知するためのスレッド数を指定できる。
    • +IOp 4 で pollset の数を指定できる。カーネル空間で複数スレッドからの pollset へのロック競合が起きている場合に増やすとよいが普通は 1 で良い。
  • プロセスへのシグナルの変更
    • link と monitor のシグナル通知が各プロセスに直接送られるようになった。
    • 従来は supervisor が connection (link や monitor される/するの関係)を一元管理していたためボトルネックになっていた。
  • logger が追加された
  • maps:iterator/0 and maps:next/1が追加された
  • io_lib:format/3 が追加された
    • ログ出力ライブラリを作る時に使える。

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.

  • 名前付き関数
    • 名前付き関数(関数内での名前を付けたクロージャー)の呼出をコンパイラは関数内に関数を定義する(make_fun2)挙動をしていたが、メモリ使用量とランタイムの実行コストで不利なので、直接関数を呼び出すようになった。
  • 巨大なリストに対する subtraction-
    • もともとはネストしたループとして処理するアルゴリズムだったが、最初に red-black tree を構築して処理するようになった。
    • 赤黒木を使うようになったため、最悪時 O(n^2) から O(logN) に計算量が改善された。
    • リストの引き算(subtraction)は ERTS のスケジューラーの協調処理を阻害する関数の1つなので、スケジューラーの専有時間が減って嬉しい。
  • ビットシンタックスの先読みでのマッチ
    • SSA(Static Single Assignment) ベースで OTP が書き直されていて、より多くのケースで先読みによるマッチの最適化が適用可能になった。
    • コンパイラはバイナリに対するマッチングで部分バイナリを生成するわけではなく "match context reuse" というテクニックを使って性能を上げているらしい。
      • match context はビットシンタックスに対するマッチを判定する時にコンパイラ内部で生成するマッチ用状態オブジェクトのこと。
      • たぶんバイナリに対するマッチの開始位置とかを保持しているのだと思う。

Rust 1.39 の変更点

blog.rust-lang.org

そろそろ 1.40 が出そうな気がしますが。

The .await is over, async fns are here

async が一部安定化されて async fn で future を返せるようになった。Result と組み合わせるのはどうやるの?と思ったけれど、 future.await? みたいに書けるらしい。

References to by-move bindings in match guards

去年から仕事でずっと Rust を書いていて、度々困っていたのが、"References to by-move bindings in match guards" で、match と if を組み合わせた時に if のせいで borrow checker に通らないというのがついに許容されるようになってありがたい。

Attributes on function parameters

関数の引数に対して attribute が書けるようになるやつ。環境に応じて定義を変えたりできるようになるけれど、これは欲しくなったことないですね。

Borrow check migration warnings are hard errors in Rust 2018

1.35 で NLL が edition 2015 にもすでに入っていて、NLL と互換性のないコードは warning を出していたけど、1.39 では古い borrow checker あったバグを回避するために warning ではなく error を出すようになったと。

ちなみに、私のよく触ってるコードでは NLL で migration が必要なコードはなかったはずで、この breaking change の影響は少ないかなという印象です。

More const fns in the standard library

色々 const になりましたよと。const fn って何に使うんだっけ?

Additions to the standard library

Instant::saturating_duration_since とか地味に便利だなぁ。

Cargo test --show-ouput flag

libtest: add --show-output flag to print stdout of successful tests by emmericp · Pull Request #62600 · rust-lang/rust

Rename --all to --workspace

Rename --all to --workspace by k-nasa · Pull Request #7241 · rust-lang/cargo

正直利用者側からするとどうでもいい変更だけど、ドキュメントの修正が必要だ。