liszt: Append onlyでリーダーとライターが分離されたKVS

adventar.org

以前仕事で使おうとして没になったアイデアを改めて記事にまとめる。

動機

以前書いた記事で説明したものとほとんど一緒である。

fumieval.hatenablog.com

プログラムのログをリアルタイムに監視する仕組みが欲しいが、その仕組みがダウンしても監視対象には影響を及ぼさないようにしたいというのポイントだ。 そのため、ライター側はファイルに書き込み、リーダーはinotifyなどでファイルを監視するという、書き込みにサーバーを必要としない仕組みにした。 さらに、途中でクラッシュしても問題ないよう、ファイルはappend-onlyとし、ファイルの最後にページを書き込む。そのため、ページはなるべく小さくしたい。

ログしたいデータは大きく分けてスナップショットとイベントの二種類あり、内容に応じて20本程度のチャネルに分ける。それぞれのチャネルは、ペイロードのリストからなる。つまり、構造としてはMap Key [Value]のような感じとなる。 これらの点を総合し、Skew binary random access list2-3木に格納することにした。

  • Skew binary random access listは、完全二分木のリストからなる構造で、consは常に定数時間、任意の要素の取り出しが対数時間という特徴がある。
  • 2-3木はB木の特殊な場合で、ノードは2つか3つの子を持つ。

どちらも分岐が少ないため、append-onlyにしたときの空間的なオーバーヘッドが少ない(ただし、読み込むときのシーク回数が多く、パフォーマンスは悪い)。物は試し、さっそく実装してみた。

実装

github.com

バイナリ表現は以下のようになった。KeyおよびPayloadはバイト列で、ファイルに直に書き込む。アスタリスクはポインタを表す。

Node:
    Empty node: 0x00
    1-leaf: 0x01 *Key Spine
    2-leaf: 0x02 *Key Spine *Key Spine
    2-node: 0x12 *Node *Key Spine *Node
    3-node: 0x13 *Node *Key Spine *Node *Key Spine *Node

Spine: Int [Int *Tree]

Tree:
    Tip: 0x80 *Payload
    Bin: 0x81 *Payload *Tree *Tree

ライターのAPIは、モナドを活用したシンプルなものになった。Transactionモナドは、まだ書き込まれていないノードなどを管理しており、commitFileを実行すると内容を一斉に書き込む。

commitFile :: FilePath -> Transaction a -> IO a
insert :: Key -> Builder -> Transaction ()

ノードを表すデータ型を多相化し、各要素は「既にファイルに書き込まれたノード」「まだ書き込んでいないノード」のどちらかを含むStagePointer型で表した。コミットする際に再帰的にStagePointerをファイルのオフセットに変換するというHaskellらしいアプローチができた。

data StagePointer = Commited !RawPointer | Uncommited !(Node StagePointer) deriving Eq

data TransactionState = TS
  { dbHandle :: !LisztHandle
  , currentRoot :: !(Node StagePointer)
  , currentPos :: !Int
  }

type Transaction = StateT TransactionState IO

なお、insertの引数はByteStringではなくBuilderになっているため、アロケーションを抑えながらデータを書き込める。これは標準のBuilderではなく、最強にして最速のビルダー、mason - モナドとわたしとコモナドで紹介した自作のビルダーを使っている。標準にはないhPutBuilderLen関数が書き込んだペイロードのバイト数の取得を可能にしている。

リーダー(サーバー)側の実装には、クロスプラットフォームなファイル監視ライブラリのfsnotify: Cross platform library for file change notification.を使った。 クライアントとサーバーのコミュニケーションのプロトコルにはJSONを採用した。DerivingViaを使ってFromJSONとToJSONのインスタンスを導出するライブラリ、deriving-aesonで簡単に実装できる。 なお、レスポンス部分に関しては、sendfile(ユーザランドを介さずにファイルデスクリプタ同士でデータを転送するシステムコール)を使う都合上単純なバイナリフォーマットにした。

data Offset = SeqNo !Int
  | FromEnd !Int
  deriving (Show, Generic)
  deriving (FromJSON, ToJSON) via CustomJSON '[SumObjectWithSingleField] Offset

data Request = Request
  { reqKey :: !Key
  , reqTimeout :: !Int
  , reqLimit :: !Int
  , reqFrom :: !Offset
  , reqTo :: !Offset
  } deriving (Show, Generic)
  deriving (FromJSON, ToJSON) via PrefixedSnake "req" Request

実際に動かしてみるとこんな感じだ。まず、ライターのAPIを使ってデータベースに書き込む。

*Database.Liszt> :set -XOverloadedStrings
*Database.Liszt> commitFile "msg.liszt" $ insert "message" "hello" >> insert "message" "world" 
*Database.Liszt>

次にサーバーを立ち上げる。

$ cabal run lisztd

雑な作りだがコマンドラインツールも用意している。0番目から1番目までのペイロードを読み出し、改行区切りでターミナルに出力する。

$ cabal run liszt -- msg.liszt message -r 0:1 -f "%p\n"
Up to date
hello
world

無事動作が確認できた。

所感

凝った木構造全般に言えることだが、最も簡単であるはずの2-3木への挿入ですら分岐が多く(https://github.com/fumieval/liszt/blob/master/src/Database/Liszt/Internal.hs#L291)、実装するのに手間がかかった。QuickCheckを活用しながらまずは純粋に実装し、のちに本実装に書き換えるというアプローチをした。 Append onlyなDBMShttps://couchdb.apache.org/という先例がある(cf. The Power of B-trees)。あちらはかなりリッチなAPIを用意しており、実装の複雑さは計り知れない(少なくとも、私一人では実装できる気がしない)。DBというのは往々にしてそういうものなのかもしれない。