Druse

Crystal で書いた、ディスクベースの Redis 互換 KVS です。RESP2 で通信するので、redis-cli や既存の Redis クライアント（crystal-p2p-server の RedisClient など）からそのまま接続できます。

起動

crystal build --release src/main.cr -o bin/druse
bin/druse --dir ./data            # 127.0.0.1:6378
redis-cli -p 6378

Lua 5.4（pkg-config lua）にリンクします。

対応コマンド

• 文字列: GET SET(NX/XX/GET/EX/PX/EXAT/PXAT/KEEPTTL) SETNX SETEX PSETEX GETDEL GETSET MGET MSET MSETNX INCR DECR INCRBY DECRBY APPEND STRLEN
• キー: DEL UNLINK EXISTS EXPIRE PEXPIRE EXPIREAT PEXPIREAT(NX/XX/GT/LT) TTL PTTL EXPIRETIME PEXPIRETIME PERSIST TYPE RENAME KEYS SCAN(MATCH/COUNT/TYPE) DBSIZE FLUSHDB FLUSHALL
• ハッシュ: HSET HMSET HSETNX HGET HMGET HDEL HGETALL HKEYS HVALS HLEN HEXISTS HINCRBY HSTRLEN
• セット: SADD SREM SMEMBERS SISMEMBER SMISMEMBER SCARD
• スクリプト: EVAL EVALSHA SCRIPT LOAD/EXISTS/FLUSH
• 接続: PING ECHO AUTH HELLO(2) SELECT(0–15) QUIT CLIENT COMMAND INFO TIME

リスト、ソート済みセット、MULTI/EXEC、Pub/Sub、HSCAN/SSCAN は未実装です。

SCAN のカーソルは、サーバー側で「db と最後に返したキー」に対応づけた番号です。反復の最初から最後まで存在するキーは、途中に書き込みがあっても必ずちょうど 1 回返ります。カーソルは新しいものから 10 万個まで保持し、それより古いカーソルを使うと ERR invalid cursor になります。

構成

ストレージ（LSM ツリー）

• WAL: 1 コマンド（または 1 スクリプト）の書き込みを 1 レコード（CRC 付き）にまとめるので、クラッシュ後もコマンド単位で原子的に復元されます。末尾の壊れたレコードは起動時に切り詰めます。
• memtable: ソート済みのインメモリ表です。閾値を超えると immutable にし、バックグラウンドの fiber が SSTable に書き出します。
• SSTable: 4KiB のデータブロック、インデックス、Bloom フィルタで構成し、各セクションに CRC を付けます。読み込みは pread と LRU ブロックキャッシュを使います。
• compaction: サイズが近い新しい SSTable の連なりを、バックグラウンドの fiber がマージします。最古のテーブルを含むマージでは tombstone を捨てます。
• MANIFEST: 生きている WAL と SSTable の一覧です。tmp ファイルに書いてから rename で置き換えます。

キーの配置

Redis のデータ型は、1 本の順序付きキー空間に次のように載せています。

• 0x01 db key → メタデータ（型、有効期限、文字列の値または要素数）
• 0x02 db len(key) key field → ハッシュのフィールド、セットのメンバー
• 0x03 db expire_ms key → 有効期限インデックス（バックグラウンドで期限切れのキーを削除するのに使用）

期限切れのキーはアクセス時にも削除します。

並行性と Lua

Redis と違い、Lua スクリプトの実行中もサーバー全体は止まりません。

• 排他はキー単位です。各コマンドは触るキーだけをロックします（FLUSHDB と FLUSHALL だけは全体を排他します）。
• スクリプトは実行ごとに別の Lua state を使います（プールして再利用します）。命令数のフックでおよそ 1ms ごとに fiber を譲るので、ほかのクライアントは待たされません。待つのは、同じキーを使うコマンドだけです。
• KEYS で宣言されたキーは最初にロックします。宣言されていないキー（ARGV から組み立てたキーなど）は、触った時点で try-lock します。ほかのクライアントが使用中なら、そこまでの書き込みを捨て、そのキーも最初からロックしてスクリプトを実行し直します。ロックはソート順に取るので、デッドロックは起きません。
• スクリプトの書き込みは終了時に 1 つの WAL バッチとしてコミットします。実行時エラーが起きる前の書き込みは残します（Redis と同じ挙動です）。
• load はテキストチャンクのみ受け付けます。dofile、loadfile、string.dump、print は使えません。

シングルスレッドの fiber スケジューラ（Crystal の既定）を前提にしています。

テスト

crystal spec

druse