RSSリーダ BazQux と DNS キャッシュ

BazQux(バズクックス)は、Google Reader の代替として密かに注目されている RSS リーダです。実装と運用を一人でやっている Vladimir Shabanov さんによると、BazQux のウリは、

• 高速である
• ブログのコメントも表示できる
• 複数のビューがある
• モバイルに対応している

などらしいです。

BazQux のフロントエンドは、Ur/Web で記述されたコードから生成された JavaScript、バックエンドは Haskell だそうです。高速なのは、Haskell のおかげであると Vladimir さんは言っています。我々が開発している HTTP エンジンの Warp も使われているそうです。

現在、僕は Haskell 用の HTTP/2 ライブラリの作成に取り組んでおり、必要な技術を調べている過程で、redditでの議論のことを思い出しました。今回、よくよく読んでみると、僕が実装している DNS ライブラリを使っているが、ADNS (のラッパーである hsdns)と比べて安定しているものの、ドメインを検索できないことがあると書かれていました。

僕がDNSライブラリを書いたのは、不安定なADNSを見限ったためなので、安定しているのは当然として、ドメインの検索率が悪い点は気になりました。そこで、Vladimir さんにメールを書いたところ、すぐに返事が返ってきました。彼のコードと実際のドメインリストを見せてもらったところ、

• DNSライブラリの使い方が間違っている
• MVarを多用していて性能が悪そう (Vladimir は、そこはボトルネックではないと言っている)
• HashMapで持っているキャッシュを定期的に枝刈りしてないのでメモリをたくさん使いそう

ということが分かりました。

奮い立ってしまった僕は、使ってもらえるか分かりませんでしたが、おもむろに concurrent-dns-cache というライブラリを作り始めました。設計のポイントは以下の通り。

• DNSライブラリを正しく使う
• セマフォを STM で実装する
  • 高並行な状況では MVar よりよいはず
• キャッシュは Priority Search Queue で持つ
  • 優先度に指定した時刻で枝刈りできる。もちろん、ドメイン名で検索もできる。
• ドメイン名を ShortByteString として扱う
  • ByteString は pinned オブジェクトなので、メモリが断片化する。このため Vladimir さんは Text を使っていたが、ShortByteString の方がメモり利用効率がよい
• 高速な検索を実現するためにキーの第一要素としてハッシュ値を持つ

concurrent-dns-cache は、めでたく BazQux に採用され、以前よりもドメインの検索率が高く、少ないメモリで安定して動いているようです。高性能で高並列で安定しているネットワークコードをすばやく実装できるのが Haskell のよい点の一つですね。

今回の経験は HTTP/2 の実装にも役立ちそうでよかったし、現場の人と議論できたのはのは楽しい経験でした。

今少し悩んでいることは2つ。

一つ目：キーの定義は以下のようになっています。

type Hash = Int

data Key = Key !Hash            -- making lookup faster
               !ShortByteString -- avoiding memory fragmentation
               -- Haskell 2010 says: Derived comparisons always
               -- traverse constructors from left to right.
               deriving (Eq,Ord,Show)

実際のキーをハッシュ値と一緒にくるむことで、(MapからHashMapへの変更とは違って)コンテナの構造を変えることなく、検索速度を高速にします。みんな使いたいとは思いますが、ライブラリにするには小さすぎるので、どうしようかなぁという感じです。まだベンチマークを取っていないのですが、本当に有用そうなら小さくてもライブラリにするかもしれません。

二つ目：Priority Search Queue の本家本元のライブラリである PSQueueには、ある優先順位以上の要素を取り出す API はあるのですが、要素を取りさらった木を返す API はありません。そこで、僕は GHC のソースコードから PSQ.hs をコピーしました。PSQueue の API はあまりよくないし、PSQ.hs はキーと優先順位の型が固定です。両者の API はまっく違うので、PSQueue を PSQ.hs で置き換えてバージョンアップするということもできません。

そもそも、Priority Queue がヒープの別名であることを知らない人は多く混乱の元なので、search-heap という名の別ライブラリでリリースしようかなぁ、どうしようかなぁ、という感じです。