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

Traversable API

与えられたConnectionを通じて、指定したKeyに対応するByteStringを取り出すような、シンプルなKey-ValueストアのAPIを考えてみよう。

type Key = ByteString
fetchOne :: Connection -> Key -> IO ByteString

ネットワーク越しにたくさんのデータを取得したいとき、何度もこれを呼び出していては効率が悪い。一度にまとめて取り出せるように拡張するなら、このように書ける。

fetchMany :: Connection -> [Key] -> IO [ByteString]

悪くはないが、この型はたとえば「["foo", "bar"]を要求したのに返ってきたのは[]」のような振る舞いを許してしまうため、使い手に不必要なパターンマッチを強いる。だが、リスト[]にちょっとした一般化を施すだけでそれを防ぐことが可能だ。

fetch :: Traversable t
  => Connection -> t Key -> IO (t ByteString)

リストが任意のTraversableになっているのがミソだ。TraversableはFunctorとFoldableのサブクラスで、各要素に対して作用を伴って関数適用し、元の構造を保ったまま返すような関数、traverseを持つ。パラメトリシティのおかげで、勝手に要素を追加したり減らしたりするような振る舞いは許されない*1。Identity、Maybe、[]のような型はもちろん、data V3 a = V3 a a aのような固定長のコンテナもインスタンスになる。

class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  ...

これだけでもfetchOneとfetchManyの一般化になるが、最近流行りのHKD(higher kinded datatype)とのコンボでさらなる力を発揮する。HKDは、パラメータとして与えられた型で各フィールドを包むことによって、同じデータ型に複数の役割を与えられるような手法である。例えばConst Stringで包んで各フィールドの名前を表したり、Parserで各フィールド用のパーサーを定義することができ、Identityなら当然通常のデータ型と同型になる。

data User h = User
  { userId :: h Int
  , userName :: h Text
  }

userFields :: User (Const Key)
userFields = User (Const "userId") (Const "userName")

barbiesのData.Barbie.Containerは、このパラメータがConstな場合にTraversableとして使えるようにする。

newtype Container b a = Container
  { getContainer :: b (Const a) }

userFieldsをContainerで包めばfetchに渡せて、形を保ったままByteStringのレコードが返ってくるので、あとは煮るなり焼くなり好きにすればいい。

Container result :: Container User ByteString <- fetch conn $ Container userFields
let user :: Maybe (User Identity)
     user = btraverseC @FromJSON
       (fmap Identity . decode . getConst) result 

リクエストと同じ形のレスポンスが得られるという性質はGraphQLにも通じる。このような関手ライクなインターフェイスは、今後のAPI設計の鍵を握っているかもしれない。

*1:厳密には順番を入れ替えることは可能だが、そのような使い方はまずありえない

楽園へ行きたい

楽園へ行きたい。

森と平原に囲まれた、街のはずれの小屋に住みたい。

朝は、小鳥たちのさえずりと窓から射し込む陽の光で目覚めたい。
昼は、コーヒーと焼き菓子を用意して一服したい。
夜は、天の河の向こうに思いを馳せながら眠りたい。

月曜日は大学に行き、エルフの先生の下で言語学を学びたい。
火曜日は研究室にこもり、ドラゴンの教授と研究に没頭したい。
水、木曜日は道具鍛治と修繕の仕事をしたい。
金曜日は都に向かい、品を売って食材と情報を仕入れたい。
土曜日は酒場に集まり、仲間たちと杯を交わしたい。
日曜日は使い魔を連れ、公園をゆったり散歩したい。

春は、花々を眺めながら、渡り鳥たちにしばしの別れを告げたい。
夏は、祭りの企画に参加し、市民を楽しませたい。
秋は、旬のものでご馳走をたくさん作りたい。
冬は、客を呼んで鍋をつつきながら新年を迎えたい。

そんな楽園で私は暮らしたい。

特級シリアライズライブラリ、winery 1.0解禁

fumieval.hatenablog.com

あれから9ヶ月…wineryのバージョン1.0をついにリリースした。

前回までのあらすじ

データの保存や通信に直列化は不可欠の概念である。 binaryなどの直列化ライブラリは、レコードのフィールド名などの情報が欠けており、構造が変わると互換性を持たせることができない。 一方、JSONやCBORなどのフォーマットで愚直にフィールド名などを残すと極めて冗長になり、時間・空間効率が悪い。 コード生成が前提のProtobufなどはHaskellの既存のデータ構造との相性がよくない。 そんな現状に殴り込みをかけたのがwineryだ。値を「スキーマ」と「データ」に分割して保存することによって、冗長性を避けつつ、メタデータを保持させることができる。wineryは最強のライブラリとなりうるか…？

特徴と特長

JSON, MessagePack, CBORなど、多くのフォーマットでは値にフィールド名などの情報を付属させる。

[{"id": 0, "name": "Alice"}, {"id": 1, "name": "Bob"}]

wineryが違うのは、それらメタデータをデータ本体から分離し、一箇所にまとめて保存することにある。これにより、冗長性はなくなり、しかも要素がwell-typedであることを保証する。

0402 0402 0269 6410 046e 616d 6514  [{ id :: Integer, name :: Text }]
0200 0541 6c69 6365 0103 426f 62    [(0, "Alice"), (1, "Bob")]

メタデータのおかげでデシリアライザに互換性を持たせることも可能となる。もちろん、目的に応じてメタデータを省き、binaryやcerealと同じように使うこともできる。 整数のエンコードにはVLQを採用しているため、binaryやcerealよりも短くなりやすい。

使い方

まずSerialiseのインスタンスを定義する。DerivingViaを使って簡単にインスタンスを導出できる。この導出機構は再帰的なデータ型にも対応している。

{-# LANGUAGE DerivingVia, DeriveGeneric, OverloadedStrings, ApplicativeDo #-}
import Control.Applicative
import Data.Winery
import Data.Text (Text)
import qualified Data.Text as T
import GHC.Generics (Generic)

data User = User
  { first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  } deriving (Show, Generic)
  deriving Serialise via WineryRecord User

WineryRecordはどのようなインスタンスにするか選ぶためのラッパーだ。目的に応じてWineryProduct (フィールド名なし), WineryVariant(コンストラクタ名あり)と使い分けよう。

あとはserialise :: Serialise a => a -> ByteStringとdeserialise :: Serialise a => ByteString -> Either WineryException aで自由にシリアライズ・デシリアライズができる。

> serialise (User "Fumiaki" "Kinoshita" "fumiexcel@gmail.com")
"\EOT\EOT\ETX\nfirst_name\NAK\tlast_name\NAK\ENQemail\NAK\aFumiaki\tKinoshita\DC3fumiexcel@gmail.com"

> deserialise @User "\EOT\EOT\ETX\nfirst_name\NAK\tlast_name\NAK\ENQemail\NAK\aFumiaki\tKinoshita\DC3fumiexcel@gmail.com"
Right (User {first_name = "Fumiaki", last_name = "Kinoshita", email = "fumiexcel@gmail.com"})

互換性

レコードにフィールドを追加したときや、バリアントからコンストラクタを削除したときなどに古いデータとの互換性が失われる。そんな場合のための処理をコンポーザブルに記述できる仕組みがwineryには備わっている。

UserにRoleというフィールドを追加したい場合を考えよう。

data Role = Admin | Moderator | Member
  deriving (Show, Generic)
  deriving Serialise via WineryVariant Role

data User = User
  { first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  , role :: !Role
  } deriving (Show, Generic)

データにroleが欠けている場合の振る舞いも、ApplicativeDo記法を用いてカスタマイズができる。なんとメールアドレスがexample.comで終わっていれば自動で昇格するといった芸当も可能だ。

instance Serialise User where
  bundleSerialise = bundleRecord $ const $ buildExtractor $ do
    f <- extractField "first_name"
    l <- extractField "last_name"
    e <- extractField "email"
    r <- const <$> extractField "role"
      <|> pure (\x -> if T.isSuffixOf "example.com" x then Moderator else Member)
    return $ User f l e (r e)

RoleからModeratorを削除した場合も簡単に対応できる。

instance Serialise Role where
  bundleSerialise = bundleVia WineryVariant
  extractor = buildVariantExtractor $ HM.fromList
    [ ("Admin", pure Rice)
    , ("Moderator", pure Member)
    , ("Member",  pure Member)
    ]

パフォーマンス

どんなに便利でも遅くては仕方がない。広く使われているbinary, cereal, aeson, serialiseと比較するためのテイスティング・セッションを行った。

課題となるのは以下のデータ型だ。それぞれの方法でインスタンスを導出し、1000要素のリストのシリアライズ・デシリアライズをする。

data Gender = Male | Female deriving (Show, Generic)

data TestRec = TestRec
  { id_ :: !Int
  , first_name :: !Text
  , last_name :: !Text
  , email :: !Text
  , gender :: !Gender
  , num :: !Int
  , latitude :: !Double
  , longitude :: !Double
  } deriving (Show, Generic)

{-
1,Shane,Plett,splett0@free.fr,Male,-222,53.3928271,18.3836801
2,Mata,Snead,msnead1@biblegateway.com,Male,-816,51.5141668,-0.1331854
3,Levon,Sammes,lsammes2@woothemes.com,Male,485,51.6561,35.9314
...
-}

結果は以下の通りだ。wineryがダントツで速いだけでなく、生成されるバイト列も最も短い。

	encode 1	encode 1000	decode	length
winery	0.28 μs	0.26 ms	0.81 ms	58662
cereal	0.82 μs	0.78 ms	0.90 ms	91709
binary	1.7 μs	1.7 ms	2.0 ms	125709
serialise	0.61 μs	0.50 ms	1.4 ms	65437
aeson	9.9 μs	9.7 ms	17 ms	160558

総評

互換性と拡張性、あらゆるデータ型に対応できる柔軟な導出メカニズム、そして卓越したパフォーマンスと簡潔な表現を提供するwinery 1.0は、ここ数年で最高の出来栄えと言えるだろう。Hackageへ急げ！

報告はGitHubもしくはHaskell-jp Slackまで。