動的配列の無難なHaskell実装

qiita.com

C++、Rust、Pythonなど、他の言語では当たり前のように多用される動的配列だが、Haskell実装は(開発を始めた時点では)見当たらなかったので作ってみたお話*1。

動的配列とはミュータブルな配列の一種で、通常の配列操作だけでなく、末尾への要素の追加・削除が定数時間で行える構造である。確保しておいた領域がいっぱいになったら、その2倍の大きさの領域を確保するという方法によって、漸近的には要素の追加は定数時間となる。

内部の配列には、デファクトスタンダードであるvectorパッケージを用いる。Vectorには無印(boxed)、Unboxed、Storableの三種類の変種があり、それぞれ以下のように使い分ける。

• 無印(Data.Vector): サンク含め、任意のHaskellのオブジェクトを格納できる。Traversableなどのインスタンスであり、汎用性が高い
• Unboxed (Data.Vector.Unboxed): ポインタを経由せず、要素がメモリ上に連続的に配置される。タプルはfst側の配列とsnd側の配列の二つが内部で作られる。効率が求められるときに使う
• Storable (Data.Vector.Storable): Storableクラスを通してメモリ上の表現と対応させる。外部のライブラリと連携したい際に有用

それぞれにミュータブル版(.Mutable)のモジュールも存在する。幸運なことに、これらのAPIを共通化するData.Vector.Genericというモジュールがあるので、それを土台として実装していく。完成したのがこれだ。

github.com

hackage.haskell.org

実装のポイント

vectorのAPIは、primitiveパッケージによって抽象化されており、IOとSTの違いを吸収できる。こちらもそれに合わせて設計する。

data GVState v s a = GVState !Int !(v s a)

-- | 'Growable' is a dynamic vector based on mutable vector @v@.
newtype Growable v s a = Growable (MutVar s (GVState v s a))

Vectorの実装を表すパラメータv、世界の型を表すパラメータs、要素の型aを引数に持つGrowableを定義する。IORefの一般化であるMutVarに格納し、配列を入れ替える挙動を可能にする。 配列の末尾に要素を追加する操作pushを定義してみよう。

-- | Append an element to the vector (not atomic).
push :: (PrimMonad m, MVector v a) => Growable v (PrimState m) a -> a -> m ()
push (Growable ref) val = do
  GVState len vec <- readMutVar ref
  vec' <- if MV.length vec == len
    then MV.unsafeGrow vec (max 1 len)
    else pure vec
  writeMutVar ref $ GVState (len + 1) vec'
  MV.write vec' len val
{-# INLINE push #-}

定義について特筆すべきことはないが、ここではINLINE化が重要になってくる。インライン化しないと、PrimMonadもMVectorも辞書渡しになってしまい、実行時のパフォーマンスに大きな影響を及ぼす。プリミティブな動作を定義するコードでは特に影響を受けやすいため、辞書渡しされないようしっかり対策を忘れないようにしたい。

まとめ

Haskellのエコシステムは、ありそうなものがないということが多々ある。自作する際も、ベストプラクティスをしっかりと押さえ丁寧に実装していきたい。

なお、当初はアトミック(複数のスレッドが同時に実行しても干渉せず正しく動く)なpushを実装する予定だった。アルゴリズムはさほど難しいものではないが*2、BoxedおよびUnboxed Vectorに対するCASを実装する必要があり、時間がなかったため断念した。しかし、役に立つ場面は必ず出てくるはずなのでいずれ実装したい。

追記 バージョン0.0.1で、ロックフリー版のatomicPushとatomicPopを追加した。

*1:改めて確認すると、grow-vector: Mutable vector with efficient appendsというパッケージが最近アップロードされたようだ

*2:Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup - Lock-free Dynamically Resizable Arrays

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

adventar.org

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

動機

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

fumieval.hatenablog.com

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

ログしたいデータは大きく分けてスナップショットとイベントの二種類あり、内容に応じて20本程度のチャネルに分ける。それぞれのチャネルは、ペイロードのリストからなる。つまり、構造としてはMap Key [Value]のような感じとなる。 これらの点を総合し、Skew binary random access listを2-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なDBMSはhttps://couchdb.apache.org/という先例がある(cf. The Power of B-trees)。あちらはかなりリッチなAPIを用意しており、実装の複雑さは計り知れない(少なくとも、私一人では実装できる気がしない)。DBというのは往々にしてそういうものなのかもしれない。

自動printfデバッグ

関数をデバッグするために、引数と戻り値をそれぞれ表示するというのを誰しもやったことがあると思う。今回はそれを自動化するからくりをHaskellで実装してみる。

目標となるのは、関数が与えられたとき、その引数と結果をターミナルに出力する関数に変換する高階関数、probe :: Traceable a => String -> a -> aである。

testDelay :: Double -> Double -> IO ()
testDelay dur dur' = threadDelay $ round $ (dur + dur') * 1000000

*Probe> probe "testDelay" testDelay 1 2
testDelay 1.0 2.0: ()

これは型クラスを活用すればお茶の子さいさいである。以下のように型によって挙動を切り替える関数withTraceDataを定義すればよい。

• 関数r -> aは、rの値を文字列にしてリストに積み、aについても再帰的にwithTraceDataを適用する。
• IOアクションからは結果が返されるとみなし、与えられた引数のリストと結果を表示する。

実装するとこのようになる。

module Probe (Traceable(..), probe) where

import System.IO
class Traceable a where
    withTraceData :: String -- 名前
      -> [String] -- 文字列化した引数
      -> a -> a

instance (Show r, Traceable a) => Traceable (r -> a) where
    withTraceData name args cont arg = withTraceData name
      (showsPrec 11 arg "" : args) -- showsPrecを使うことで適切に括弧を表示する
      (cont arg)

instance Show a => Traceable (IO a) where
    withTraceData name args m = do
        hPutStr stderr $ unwords (name : args) ++ ": "
        hFlush stderr
        a <- m
        hPrint stderr a
        pure a

probe :: Traceable a => String -> a -> a
probe name = withTraceData name []

このままでは純粋な関数には使えないので、unsafePerformIOを使ったインスタンスも作っておこう。

newtype Result a = Result { unResult :: a }
instance Show a => Traceable (Result a) where
    withTraceData name args (Result a) = Result $ unsafePerformIO $ withTraceData name args $ pure a

Traceable Intなどを直接定義せず、まずnewtypeへのインスタンスとして定義するのには理由がある。 Haskellの多引数関数はカリー化されており、「a -> b -> cはb -> cを結果として返す関数」でもあるため、どこで区切るかがwell-definedではない。そのため、明示的な型によって区別することは理にかなっている。 さらに、他のプリミティブ型の定義をDerivingViaとStandaloneDerivingによって簡潔に書けるという最近のGHCならではの利点もある。

deriving via Result Bool instance Traceable Bool
deriving via Result Int instance Traceable Int
deriving via Result Double instance Traceable Double
...

小さなコードではあるが、ここで紹介したテクニックは日常で役に立つに違いない。 この手法は色々と応用が利く。例えば、printする代わりにシリアライズして外部のファイルに書き込めば、probe関数を刺して動かすだけでテストケースを抽出できる道具にもなる。

最近やる気が出てきたので、これらのアイデアをそのうちライブラリにまとめるかもしれない。

barbies-thで気軽にHKDを堪能しよう [Haskell AdC 14]

ミーハーな読者なら、barbiesというライブラリをご存知の方も多いと思う。そう、HKDを扱う定番ライブラリだ。HKDは、同アドベントカレンダーにも寄稿されている他、Haskell Dayでも紹介された(https://assets.adobe.com/public/b93f214d-58c2-482f-5528-a939d3e83660)注目の技法だ。Higher-Kinded Data (HKD) について - Qiita

HKDは、一番簡単な場合であるはずのIdentityを使うと着脱が面倒になるという問題がよく知られている。Data.Barbie.BareモジュールのWearという型族を使って定義すれば、それを簡単にはがせ、普通のレコードと全く同じように使える。

data Barbie t f = Barbie
      { name :: Wear t f String
      , age  :: Wear t f Int
      }
instance BareB Barbie
instance FunctorB (Barbie Covered)
instance TraversableB (Barbie Covered)
instance ProductB (Barbie Covered)
instance ConstraintsB (Barbie Covered)
instance ProductBC (Barbie Covered)

bstrip :: b Covered Identity -> b Bare Identity
bcover :: b Bare Identity -> b Covered Identity

とても便利だが、いくつかの不満点が残っている。まずフィールド1つにつきWear t fを被せないといけないのは面倒で、可読性の面でもよくないし、ジェネリクスとはいえインスタンス宣言をずらずら書くのも面倒極まりない。また、Bare関係なしに、フィールドの数が多いとコンパイル時間が増えるばかりか、インライン化に失敗して実行時の効率まで悪化する可能性も高い。20個程度のフィールドを扱うコードで2分以上かかる例もあり、インスタンス定義だけでなくメソッドを使っている場所にも影響する。

こんなことで消耗するくらいなら、全部Template Haskellという爆弾で解決してしまえば良い、というコンセプトで作ったのがbarbies-thだ。使い方は簡単、Template Haskellを有効にし、declareBareBを普通のデータ型の定義に被せればよい。

import Data.Barbie.TH

declareBareB [d|
  data Barbie = Barbie
      { name :: String
      , age  :: Int
      }
  |]

すると、あら不思議、何もかもいい感じに揃えてくれる。

data Barbie sw h = Barbie
    { name :: Wear sw h String,
    , age :: Wear sw h Int
    } deriving Generic
instance BareB Foo
instance FieldNamesB (Barbie Covered) where
  bfieldNames = Foo (Const "name") (Const "age")
instance ProductB (Barbie Covered) where ...
instance FunctorB (Foo Covered) where ...
instance TraversableB (Foo Covered)where ...
instance ConstraintsB (Foo Covered)
instance ProductBC (Foo Covered)

主要なインスタンスについても、ジェネリクスではなくTemplate Haskellによって実装を導出しているため、コンパイル時間や最適化に対する心配もいらない。HKD(barbies)を実用する上での障害を一通り解決するというわけだ。おまけとして、全フィールド名をt (Const String)の形で取得できるFieldNamesBというクラスも用意しており、FromJSONなどのインスタンスを定義するのに役立つ。

これからは、ジェネリックプログラミングやテンプレートメタプログラミングを活用し、仕事の半分はデータ型を書くだけで終わらせてしまおう。それでは、Happy higher-kinded holiday!

hackage.haskell.org

最強にして最速のビルダー、mason

Haskell Advent Calendar 2019 5日目

この冬、神速のサンタクロースがやってくる——

Haskellにおいて、バイト列の表現はByteStringが定番である。ByteStringはPinned領域に直接格納され、空間効率はリストに比べればはるかに良い。しかし、Pinned領域にあるとヒープフラグメンテーションが起こりやすくなるということでもあり、細かい文字列をつなぎ合わせるような使い方はパフォーマンスに悪影響が及ぶ。そのような問題を避けるため、ビルダーと呼ばれる構造が用意されている。 Data.ByteString.Builderは、word8 42 <> byteString "hello" <> doubleLE 42のように細かいプリミティブを連結し、toLazyByteStringを呼ぶと最後にByteStringを一気に鋳出せるという仕組みである。ByteStringをちまちま結合するよりも格段に高速であり、waiなどのインターフェイスにも利用されている。

しかし、各パーツをバッファに書き込んでポインタをずらすだけで済む処理にしてはやたら遅い。Builderの実体は、Freeモナドのような再帰的なADTにコンストラクタを重ねる関数であり、構築・分解するオーバーヘッドが大きいのだろう——結局、中間構造を作らないという目的を完全に達成したわけではないのだ。

type BuildStep a = BufferRange -> IO (BuildSignal a)

-- | 'BuildSignal's abstract signals to the caller of a 'BuildStep'. There are
-- three signals: 'done', 'bufferFull', or 'insertChunks signals
data BuildSignal a =
    Done {-# UNPACK #-} !(Ptr Word8) a
  | BufferFull {-# UNPACK #-} !Int {-# UNPACK #-} !(Ptr Word8) (BuildStep a)
  | InsertChunk {-# UNPACK #-} !(Ptr Word8) S.ByteString (BuildStep a)

そのパフォーマンスの問題に目を付けたのがfast-builderで、ポインタやRealWorld(IOモナドの実装に使われるステートトークン)をUnboxedタプルに格納するという徹底的な最適化を施した。

newtype Builder = Builder { unBuilder :: DataSink -> BuilderState -> BuilderState }
type BuilderState = (# Addr#, Addr#, State# RealWorld #)

その結果、標準のビルダーの数倍もの高速化を達成した。fast-builderは、バッファに直接データを書き込むという動作を基本とし、3つのモードをサポートしている。

• toStrictByteString: 指数関数的に大きくなるバッファにデータを書き込み、StrictなByteStringとして取り出す。
• toLazyByteString: スレッドを立ち上げ、バッファが満タンになるたびに新しいチャンクを生成することによって、LazyなByteStringを作り出す。
• hPutBuilder: バッファがいっぱいになるたびに、ハンドルにその内容を書き込む。

3つのモードを実現するために、内部のDataSinkというデータ型に必要な情報をまとめているため、拡張性に乏しいという難点がある。ローレベルな内部構造も拡張の難しさに拍車をかけている。

-- | Specifies where bytes generated by a builder go.
data DataSink
  = DynamicSink !(IORef DynamicSink)
    -- ^ The destination of data changes while the builder is running.
  | GrowingBuffer !(IORef (ForeignPtr Word8))
    -- ^ Bytes are accumulated in a contiguous buffer.
  | HandleSink !IO.Handle !Int{-next buffer size-} !(IORef Queue)
    -- ^ Bytes are first accumulated in the 'Queue', then flushed to the
    -- 'IO.Handle'.

そんな問題を解決するため、新たにmasonというライブラリを作った。

github.com

masonは、ビルダーを実行する手段として4つの関数を提供する。Strict、LazyなByteStringと、ハンドルおよびソケットへの書き込みだ。StrictなByteStringやソケットに使えるというだけでもオリジナルよりかなり便利になったが、ライブラリに変更を加えずとも新しい使い道を定義することもできる。

toStrictByteString :: BuilderFor GrowingBuffer -> B.ByteString
toLazyByteString :: BuilderFor Channel -> BL.ByteString
hPutBuilderLen :: Handle -> BuilderFor PutBuilderEnv -> IO Int
sendBuilder :: S.Socket -> BuilderFor SocketEnv -> IO Int

そのからくりは型パラメータにある。Builderの中身は、バックエンドに応じた値と、バッファへのポインタをBuffer型として受け取り、何らかのアクションを実行して返すという至極単純なものだ。

data BuilderFor s = Builder { unBuilder :: s -> Buffer -> IO Buffer }

data Buffer = Buffer
  { bEnd :: {-# UNPACK #-} !(Ptr Word8) -- ^ end of the buffer (next to the last byte)
  , bCur :: {-# UNPACK #-} !(Ptr Word8) -- ^ current position
  }

type Builder = forall s. Buildable s => BuilderFor s

Buildableクラスを通して、目的に合わせた処理を具現化している。

class Buildable s where
  byteString :: B.ByteString -> BuilderFor s
  flush :: BuilderFor s
  allocate :: Int -> BuilderFor s

StrictなByteStringを生成する場合、allocate nは現在の倍以上かつn以上の長さのバッファを作るアクションで、flushは何もしない。byteStringは与えられたバイト列をバッファにコピーする関数となる。ハンドルに書き込む場合、flushは現在のバッファの中身をハンドルに落とし、byteStringの引数が大きい場合はバッファを介さずに直接書き込む——というように、バックエンドに合わせた処理を実装している。

これらのメソッドが与えられると、ensureという関数が定義できる。ensure nは、バッファにnバイト以上の余裕があることを保証して関数を呼び出し、足りない場合はその前に領域を確保する。実質的にはこれがBuilderのスマートコンストラクタであり、新たな部品を作ることを容易にしている。

ensure :: Int -> (Buffer -> IO Buffer) -> Builder
ensure mlen cont = Builder $ \env buf@(Buffer end ptr) ->
  if ptr `plusPtr` mlen >= end -- 現在のバッファに収まらない？
    then do
      buf'@(Buffer end' ptr') <- unBuilder flush env buf -- 一度バッファを流してみる
      if mlen <= minusPtr end' ptr' -- それでも収まらない？
        then cont buf'
        else unBuilder (allocate mlen) env buf' >>= cont -- 新たな領域を確保する
    else cont buf

このようなチェックをいちいち実行するのは無駄だが、ensureはモノイドの準同型写像であるため、融合変換によって一つにまとめることができる。最適化が理想的に回れば、可変長の要素がある時だけ空きがチェックされるようにコンパイルされるはずだ。flushやallocateなどが呼ばれるタイミングが変わってしまう半グレ的な最適化だが、まさに必要な振る舞いなので仕方がない。

{-# INLINE[1] ensure #-}
{-# RULES "<>/ensure" forall m n f g.
  ensure m f <> ensure n g = ensure (m + n) (f >=> g) #-}

masonは基本的に最適化が鬼回りする前提で設計されているので、インライン化を怠ったり、中途半端な場所に保存したりすると最高のパフォーマンスが発揮できない点には注意する必要がある。

ベンチマーク

長々とテクニックをひけらかしたところで、実際遅かったら意味がない。fast-builderのJSONデータを扱うベンチマークを拝借し、Textのエンコード方法などを少し改良して比較してみた*1。

mason/hPutBuilder                        mean 187.6 μs  ( +- 14.02 μs  )
fast-builder/hPutBuilder                 mean 366.5 μs  ( +- 50.78 μs  )
bytestring/hPutBuilder                   mean 294.3 μs  ( +- 83.62 μs  )
mason/toStrictByteString                 mean 105.1 μs  ( +- 23.33 μs  )
fast-builder/toStrictByteString          mean 223.1 μs  ( +- 7.506 μs  )
bytestring/toLazyByteString              mean 249.3 μs  ( +- 16.76 μs  )
mason/toLazyByteString                   mean 101.9 μs  ( +- 4.787 μs  )
fast-builder/toLazyByteString            mean 226.4 μs  ( +- 10.56 μs  )

圧勝である。bytestringやfast-builderの倍以上と、大変満足のいく結果だ。元のベンチマークのようにTextを一旦Data.Text.Encoding.encodeUtf8で変換すると差は若干縮まるが、それでも最速であることに変わりはない。

fast-builder/hPutBuilder                 mean 372.2 μs  ( +- 68.48 μs  )
bytestring/hPutBuilder                   mean 603.6 μs  ( +- 641.7 μs  )
mason/toStrictByteString                 mean 215.4 μs  ( +- 71.29 μs  )
fast-builder/toStrictByteString          mean 302.2 μs  ( +- 78.57 μs  )
bytestring/toLazyByteString              mean 498.3 μs  ( +- 154.5 μs  )
mason/toLazyByteString                   mean 196.2 μs  ( +- 10.76 μs  )
fast-builder/toLazyByteString            mean 230.7 μs  ( +- 17.19 μs  )
bytestring/toLazyByteString              mean 381.3 μs  ( +- 18.35 μs  )

fumieval.hatenablog.com

wineryのビルダーをfast-builderからmasonに差し替え、ベンチマークを実行した。

serialise/list/winery/old                    mean 223.2 μs  ( +- 16.28 μs  )
serialise/list/winery/new              mean 119.8 μs  ( +- 21.57 μs  )
serialise/list/binary                    mean 1.597 ms  ( +- 394.7 μs  )
serialise/list/cereal                    mean 747.0 μs  ( +- 196.5 μs  )
serialise/list/serialise                 mean 494.4 μs  ( +- 126.2 μs  )
serialise/list/store                     mean 50.83 μs  ( +- 4.517 μs  )
serialise/list/aeson                     mean 7.403 ms  ( +- 1.628 ms  )
serialise/item/winery/old               mean 234.3 ns  ( +- 18.57 ns  )
serialise/item/winery/new                mean 62.61 ns  ( +- 4.216 ns  )
serialise/item/binary                    mean 1.738 μs  ( +- 383.9 ns  )
serialise/item/cereal                    mean 709.8 ns  ( +- 223.7 ns  )
serialise/item/serialise                 mean 583.1 ns  ( +- 132.6 ns  )
serialise/item/store                     mean 60.91 ns  ( +- 14.96 ns  )
serialise/item/aeson                     mean 8.440 μs  ( +- 5.778 μs  )

圧倒的に速い！Textをメモリ表現のまま扱うstoreと比較すると、UTF-8でエンコードするwineryには幾らかのハンデがあるが、各要素のエンコードに関してはstoreと同等の記録を出している。

bytestringにも包括的なベンチマークが付属しているので現在取り組んでいる。まだ作業中だが、ぶっちぎりで速いことに疑いの余地はない。

ここからはおまけ。Grisu3というアルゴリズムで浮動小数点数の表示を高速化するプルリクエストがbytestringに送られていたが、長年放置されていた(Reimplement floatDec/doubleDec by winterland1989 · Pull Request #115 · haskell/bytestring · GitHub)のでどのくらい速くなるか試してみた。その差、実に22倍である。

mason/double                             mean 138.0 ns  ( +- 58.45 ns  )
fast-builder/double                      mean 2.379 μs  ( +- 231.6 ns  )
bytestring/double                        mean 3.033 μs  ( +- 813.4 ns  )

また、文字列リテラルをStringを介さずに扱う変更([RFC] Builder: Efficiently handle literal strings by bgamari · Pull Request #132 · haskell/bytestring · GitHub)も放置されていたので、同等のものをこちらで実装した。派手な差はないが確実に速くなっている。

mason/literal                            mean 599.2 ns  ( +- 249.7 ns  )
fast-builder/literal                     mean 759.4 ns  ( +- 165.2 ns  )
bytestring/literal                       mean 640.1 ns  ( +- 16.93 ns  )

まとめ

masonは、高い抽象度を保ちつつも効率がよく、拡張性も確保されている、ある意味Haskellらしいライブラリだ。2020年の世界標準を目指し、さらに磨きをかけていきたい。

hackage.haskell.org

*1:https://github.com/fumieval/mason/tree/master/benchmarks/aeson

単純で頑強なメッセージングシステム、franz

Haskell製の新しいメッセージングシステムfranz(フランツ)の紹介。

github.com

背景

取引所にあるマシンで取引プログラムを実行するのが我々の仕事だが、朝8時に起動したらあとは昼寝したり酒を飲んだりというわけにはいかない。モニタリングしたり、分析のためにデータを残しておく必要がある。そのため、プログラムによって解析しやすい形でログを出力する。 今までは複数の種類のレコードをシリアライズし、一つのファイルに連結させる独自のフォーマットを10年近く使っていたが、書いていて恥ずかしくなるような多数の問題を抱えていた。

• 柔軟性が乏しい: 32bit整数や文字列などの単純な値しか格納できず、例えばレコードを含むレコードなどを表現できない。その結果、複雑なデータは一旦文字列に変換するような運用がされており、そのプリティプリンタやパーサは十分にテストされていない。
• コードがまとまっていない: シリアライザとデシリアライザが非対称的に実装されており、メンテナンスが難しい。どちらも取引関連アプリケーションのための特別な処理がハードコードされている。
• シークできない: n番目の要素に素早くアクセスする方法、ましてやタイムスタンプなどを元にシークする方法がない。
• 読み込みが遅い: 書き込みはチューニングされているが、読み込み処理が非常に遅い。さらに実際に使うAPIはFRPベースなのでさらにオーバーヘッドがある。
• 配信に適さない: 帯域幅の理由でログの全てをオフィスに送ることはできないため、あらかじめダウンサンプリングする必要がある。しかし上述の問題からログからログへの変換としては実装されておらず、オフィスでログを再構築するための配信専用プロトコルが実装されている。結果としてコードが非常に冗長になっているほか、本来のログとの互換性も不完全であり、アプリケーションの振る舞いも一貫性がない。

Kafkaの誘惑

Apache Kafkaでシークの非効率性を解決できるのではという提案があり、本格的に取り組み始めた。Kafkaは、文字列のリストを永続化し、任意の要素を高速に取り出せるようなサーバーを提供する。例の独自フォーマットの断片をKafkaのペイロードにするという仕組みで、私は独自フォーマットを使い続けるのには反対だったが、プロジェクトは進行した。現在では以下のようになっている。

• 配信専用プロトコルから再構築したログをスライスし、Kafkaに送るアプリケーションを実行する。
• GUIのクライアントなど、シークを要求する一部のアプリケーションはKafkaからデータを読み出す。

しかし、Kafkaにも問題点があった。

• 異常終了するとインデックスが壊れ、再起動に非常に長い(トピック数に比例した)時間がかかる。取引プログラムがログを送信する相手としては致命的だ。
• 要素のインデックスや、Kafkaブローカー(サーバー)のタイムスタンプによるアクセスはできるが、自分で決めたタイムスタンプは使えない。そのため、検索には二分探索や割線法のために複数回の送受信が必要になり、クライアントのレイテンシが大きいと極めて効率が悪い。

醸造家と音楽家

データ表現の柔軟性、実装の対称性の課題は、wineryというライブラリによって解決した。Haskell上の表現からディスク上の表現を簡単に導出できるため、ソースコードの量を大幅に削減でき、バグも発生しにくい。

fumieval.hatenablog.com

残りの問題は、以下の要件を満たす新しいシステムによって実現すべきという結論に至った。

• 書き込みにはサーバーが不要で、サーバーは読み出しのみを行う。万が一サーバーがダウンしても取引プログラムに影響しない。
• サーバーが新たなアイテムを検出し次第、クライアントに送信するようなクエリを表現できる。
• システムもそのAPIも、チームがメンテナンスできる言語(Haskell)で実装されている。
• ブロックするようなクエリは、好きなタイミングで中断できる。
• 連番の他、任意のタイムスタンプによって望んだ要素にアクセスできる。

私はLisztという新たなコンテナフォーマットを開発した。LisztはCouchDBのモデルをただのリストのマップに簡略化したような設計で、フッターにポインタを並べることで木構造を表現する。一つのファイルのみを扱うので理論上の効率と信頼性は高いが、フォーマットの複雑さを理由にチームの合意は得られず没となった。

github.com

代わりに、Kafkaと同様、ペイロードのみを連結したファイル(ペイロードファイル)と、64ビット整数で表されるペイロードのポインタのみを連結したファイル(インデックスファイル)を二つ作るのがFranzだ(ファイルシステムの実装を考えれば、本質的にはLisztとやっていることは変わらないとも言える)。サーバー側はinotifyなどを用いてインデックスファイルを監視し、sendfileでペイロードをクライアントに送る。ペイロードが連結されているため、sendfileでまとめて効率よく送れるのは一つの利点だ。

各要件を満たすため、決して高度なものではないが様々な技法が用いられている。

ビルダーの本気

HaskellでIOというとByteStringが定番ではあるが、ここではfast-builderのビルダーを採用した。ビルダーはByteStringに効率よく変換できるモノイドとしてよく知られた構造だが、ByteStringを介さずにファイルなどに書き込むこともできる。

-- Data.ByteString.FastBuilder
byteString :: ByteString -> Builder
word8 :: Word8 -> Builder
word64LE :: Word64 -> Builder

toStrictByteString :: Builder -> ByteString
hPutBuilder :: Handle -> Builder -> IO ()

ByteStringにするまで出力される文字列の長さがわからないのが唯一の欠点だったが、書き込んだ文字列の長さを返すhPutBuilderLen :: Handle -> Builder -> IO Intを追加したため、この問題も解消された。

つまり、要素の追加は「ペイロードファイルにhPutBuilderLenでバイト列を書き込み、その結果を用いてインデックスファイルにペイロードのオフセットを書き込む」という極めて単純な処理である。要素を1つ追加するたびにwrite(2)をそれぞれ呼ぶのは非効率的なので、可能な限りHandle内部のバッファを活用したいが、ペイロードよりも先にインデックスファイルが書き込まれてしまうとおかしなことになる。もちろんインデックスファイルのバッファは明示的に実装しており、安心してナイスバルクインサートできる。

なお、openFileを使うと、GHCはファイルデスクリプタをノンブロッキングモードとして作成する。これは内部でunsafeなforeign callを使うため、hFlushなどの実行中に他のスレッドがGCを要求するとプログラム全体がストップする危険性がある。それを避けるため、openFileBlockingを代わりに使っている。

色々なテクニックを盛り込んだが、基本のインターフェイスは3つの関数にうまくまとめることができた。謎のfパラメータについては後述する。

-- Database.Franz
withWriter :: Foldable f => f String -> FilePath -> (WriterHandle f -> IO r) -> IO r 
write :: WriterHandle f -> f Int64 -> Builder -> IO Int
flush :: WriterHandle f -> IO ()

n種類のタイムスタンプ

稀なユースケースかもしれないが、本体のタイムスタンプと、取引所から送られてきたタイムスタンプの両方を記録したい。特に過去のデータでシミュレーションする際は両者は大きく異なる。そこで、シークなどのために任意の個数の値を付随させられるようにしてある——それが型パラメータfだ。

data Timestamps a = Timestamps a a deriving Foldable

あらかじめ上のようなデータ型を定義しておき、withWriter (Timestamps "MarketTime" "LocalTime")のように名前を指定する。writeには具体的な値をTimestamps Int64型で与えればよい。これらが不要な場合、Data.ProxyのProxyを渡せばOKだ(忘れがちだが、MonadやTraversableなどのインスタンスがついた0要素のリストとして使える)。

継続は力なり

リアルタイムでメッセージを配信する以上、クライアントは最新の要素が来るまで待つ必要がある。プログラミングにおいて、ブロックする、つまり何かができるまで待つような振る舞いはコントロールが難しくなりがちだが、franzは高い柔軟性を持つ革新的なアプローチを採用した––継続とSTMのコンボである。

awaitResponse :: STM Response -> STM Contents
data Contents
data Item = Item
  { seqNo :: !Int 
    indices :: !(Vector Int64) 
    payload :: !ByteString
  }

toList :: Contents -> [Item]

fetch :: Connection
  -> Query -- ^ リクエスト
  -> (STM Response -> IO r) -- ^ 「レスポンスを受け取るトランザクション」を受け取る継続
  -> IO r

以下のコードは、stm-delayを利用してタイムアウトを実現する。動きを細かく追ってみよう。

fetch conn q $ \t -> do
  d <- newDelay 1000000
  atomically
     $ Just <$> awaitResponse t
     <|> Nothing <$ waitDelay d

• まずサーバーにクエリqを送信する。
• 返信を待たずにトランザクションを作成し、継続に渡す。
• newDelay 1000000でディレイdを作成する。waitDelay dを呼ぶと、作成してから1秒経つまでブロックする。
• 以下のどちらかが可能になるまで待つ。
  • awaitResponseでレスポンスを受信し終えたら、Justに包んで返す。
  • 1秒経過したら、Nothingを返す。
• サーバーに処理が完了した旨を通知する。
• クエリは破棄され、仮にレスポンスが既に送られたとしてもクライアントはそれを捨てる。

継続に与えたトランザクションtは、atomicallyによって実行して初めて結果を待つ。STMであるがゆえに、タイムアウトなどの理由で待つのを諦めるような振る舞いを合成できるというわけだ。継続が終了すれば、その旨もサーバーに送信されるため、待機処理がサーバーに溜まることもない。ContTなどで全体を合成すれば一度にたくさんのリクエストを送ることもでき、当然Traversable APIのようなテクニックも使える。このコンボはブロッキングAPIの新定番としてのポテンシャルを秘めていると考えている。

そこまで柔軟性が要求されない場合のために、タイムアウトのみを指定するクラシックなAPIも用意した。クエリの具体的な構造も以下に示す。

fetchSimple :: Connection
  -> Int -- ^ timeout in microseconds
  -> Query
  -> IO Contents

data ItemRef = BySeqNum !Int -- ^ sequential number
  | ByIndex !B.ByteString !Int -- ^ index name and value
data Query = Query
  { reqStream :: !B.ByteString
  , reqFrom :: !ItemRef -- ^ name of the index to search
  , reqTo :: !ItemRef -- ^ name of the index to search
  , reqType :: !RequestType
  }
data RequestType = AllItems | LastItem

ConnectionはwithConnection関数を用いて作成する。

withConnection :: String -- ^ ホスト
  -> PortNumber -- ^ ポート
  -> ByteString -- ^ ストリームプレフィクス
  -> (Connection -> IO r) -> IO r

サーバーを立ち上げるのは簡単で、データが格納されているパスを指定すればよい。

franzd .

圧縮

書き込み終わった1日分のログをまとめて圧縮する手段としてSquashFSを採用した。指定されたプレフィクスと同名のイメージがある場合、サーバーはそれをFUSEでマウントするという機能がある。サーバーを起動する際、アーカイブを格納するパスをオプションとして指定することで利用できる。

franzd --live ./live --archive ./archive

適切なオプションなら高い圧縮率を実現できる一方、パフォーマンスも意外に良好で、むしろ圧縮してある方が読み込みが速いのではないかと感じるほどだ。当初はあまり期待していなかったが、複数のファイルにまたがるフォーマットは取り回しが悪いという欠点をうまく克服できている。

今後の展開

ロギングの構成を完全に置き換える前段階として、分析用データの格納のために運用している。大きなバグもなく好感触だが、並行処理やIOをふんだんに使ったこの手のプログラムは細部の動きが怪しくなりがちだ。どんな状況でもきっちり動くように煮詰めていきたい。

Minecraft 1.14サーバーを運用してみた

Minecraft 1.14 "Village and Pillage"は、サブタイトルの通り村人と略奪者をテーマにしたアップデートだ。

主な楽しみ方

村人の取引システムが一新され、以前よりもバリエーションに富み、かつリーズナブルな取引ができるようになった。余ったアイテムを換金したり、有益なアイテムを入手できるようになるだろう。 ランタン、焚火などの新たな光源や、壁や階段の変種、さらには鐘なども追加され、建築の楽しみも大きく増した。だが、良いことばかりではない――新たなイリジャー(邪悪な村人)、ピリジャーが出現するようになったのだ。条件を満たすと発生する襲撃から村を守る死闘、そして安全な拠点づくりという課題が生まれた。これを乗り越えれば、村の英雄としての賞賛が待っている。

注目のアイテム

砥石

装備につけられたエンチャントを剥がし、経験値として回収することができる。今まで、中途半端なエンチャントのついたアイテムはゴミ扱いだったが、これがあればエンチャントが気にくわなくても再利用できる。

石切台

今までは階段を4つ作るのに6ブロックが必要だったが、石切台を使えば1:1の比率でクラフトできる。模様付きの石レンガなども原料から一発で得られるのも嬉しい。

コンポスター

植物関係のアイテムを、わずかではあるが骨粉に変換できる。余りがちな種子や木の葉などを処分するのに便利だ。

クロスボウ

エンチャントを考慮すると弓よりも攻撃力は低いが、速射・拡散のエンチャントを与えれば高いDPSを叩き込める新たな武器。花火の玉をガン積みしたロケット花火を打ち出すことで恐ろしいダメージが出せる。

足場

竹と糸でクラフトできる新たなブロック。好きなだけ高く積み上げることができ、自在に上り下り可能で、一番下を壊せばすべて回収できるという、建築に非常に便利なブロック。

主な設備

自宅

3LDKの比較的簡素な住宅。住民がほとんどの資材をここに置いているため、実質的にここがメインの拠点となっている。

フォーラム

名目上はギルドの本拠地。村人たちが働く場所で、かつては交易の拠点として賑わっていたが今は最小限の村人しか通っていない。武器や弾薬などが格納されている。

昆布・竹自動栽培機

昆布も竹も、ピストンで押し出せば刈り取れるので収穫の自動化が容易だ。この装置のポイントは燃料の供給にある。

昆布をかまどで焼くと乾燥昆布になり、それを9つまとめると昆布ブロックになる。昆布ブロックは20アイテム分を焼くことができる燃料になり、これは溶岩バケツ、石炭ブロックに次ぐ効率で *1、再生可能資源としては最高である。街に響くガシャコンという作動音と共に、世界のエネルギーをまかなっている。

自動釣り堀

最凶クラスの装置。右クリックを押しっぱなしにすることで、以下のようなサイクルによって釣りを繰り返す。

• 感圧版により、釣り竿を使用している間鉄のトラップドアが開く
• 音符ブロックにカーソルを合わせている間、釣りを維持する
• 獲物が引っ掛かると感圧版が解除され、鉄のトラップドアが閉じる
• 鉄のトラップドアを右クリックしても何も起こらないため、釣り竿のアクションが優先されて釣り上げる

魚やゴミが大量に釣れるだけでなく、Fishing – Official Minecraft Wiki に書かれている通り、強力なエンチャントを伴った弓や本なども得られ、その質はエンチャントテーブルによるエンチャントを上回る。パワー4耐久3が付いた弓はザラで、通常のエンチャントでは得られない《束縛の呪い》や《修繕》も入手できる。 一晩放置すれば40くらいまでレベルアップするだけでなく、使い道に困るほどの量のエンチャント本が得られるだろう。食料、経験値、エンチャントを無限に供給できる設備としては、あまりにも簡易かつ低コストすぎる。不要なものを砥石で削れば、さらに莫大な経験値と本などの資源が回収できる。

栽培プラットフォーム

汎用作物収穫プラットフォーム「エミュー壱号」のおかげで安定した収入が得られるようになった pic.twitter.com/xIMNU3YesM

— ふみ (@fumieval) May 15, 2019

ピストンとオブザーバーによるフライングマシンを往復させ、サトウキビなどを自動で収穫する。地下にはホッパー付きトロッコが走っており、刈り取ったアイテムが収穫される。竹やカボチャ、スイカにも使える。

天空TT

虹色の超高層ビルの最上階には、ゾンビ、スケルトン、クリーパー、ウィッチを対象としたトラップタワーが存在する。いわゆる24-32式のクラシックな構成だが効率は申し分ない。村人を何人か住まわせており、アイテムをすぐに交換できるようになっている。

羊毛工場

土を循環させることで効率よく草を再生させる羊毛工場 pic.twitter.com/8ESc8APEGc

— ふみ (@fumieval) 2019年6月14日

ハサミを入れたディスペンサーによって羊毛を刈り取り、ピストンで一辺11ブロックの土を循環させる。隣接する草ブロックを増やすことで草の再生を加速させ、羊毛を効率よく取り出せる。機構はレッドストーンリピータとトーチを用いた簡単なもので、土が来ると通電(?)してピストンで押し出される。 注意点として、この機構がチャンクをまたいでいると、一部だけが読み込まれておかしな状態になることがあるので、1チャンクに収まるような場所に設置すべきである。

丸石工場

溶岩流と水没した階段から生成された丸石をピストンで押し出し、複製したTNTで破壊する。Minecraft 1.14から、TNTで破壊されたブロックは100%ドロップするようになったため、極めて効率がよい。

全自動丸石製造機 pic.twitter.com/UTNpWW9TU7

— ふみ (@fumieval) August 15, 2019

精錬・集積・取引所

以上の設備で生産したアイテムを地下水路に流し、精錬可能なものは精錬しつつ仕分ける。そしてアイテムをその場で村人に売却することで莫大な利益を得る。忘れられがちだが、自動化してもかまどには経験値が溜まるため、時々かまどのレバーを下げてアイテムを取り出すことでレベル上げもできる。

サーバーの構成

レイヤー低い順に以下の通り。

• さくらのVPS(v4) SSD 4G TK02
• Ubuntu 18.04
• openjdk 11.0.2
• PaperMC 163

当初はRAMは2GBだったが、かなりパフォーマンス面に難があったためスケールアップした。5人ほどのプレイヤーがいてもそれなりに快適に動作する。

起動スクリプト

#!/bin/sh                                                                                                                                                                                                                                                                                                                    
java -Xms2G -Xmx2G -XX:+UseG1GC -XX:+UnlockExperimentalVMOptions -XX:MaxGCPauseMillis=100 -XX:+DisableExplicitGC -XX:TargetSurvivorRatio=90 -XX:G1NewSizePercent=50 -XX:G1MaxNewSizePercent=80 -XX:G1MixedGCLiveThresholdPercent=35 -XX:+AlwaysPreTouch -XX:+ParallelRefProcEnabled -Dusing.aikars.flags=mcflags.emc.gs -jar paperclip-163.jar

所感

村人関係の機能が非常に充実したため、より多くのエメラルドを稼ぐという目的でもなかなかやりがいがあり、Villager Trade Generator (Java Edition 1.14)などでコマンドを使えば、独自の取引メニューを持った村人も作れる。トライデントがあまりにも入手困難だったため、エメラルド64個で販売する村人を作った。

装飾関係のブロックが数多く追加されたため建築もはかどり、足場ブロックがそれを後押しする形となった。今のところほとんど遊びつくした感はあるが、Minecraftは次々と新しい要素を追加しているため、次のバージョンでも楽しめると期待している。

*1: https://minecraft.gamepedia.com/Smelting#Fuel