[解決済み] Haskellプログラムにおけるガベージコレクションの一時停止時間の削減

質問

メッセージの履歴を一時的に保存し、要求があればメッセージの履歴を伝えることができるようにしながら、"メッセージを受信して転送するプログラムを開発しています。メッセージは数字で識別され、サイズは通常約 1 キロバイトで、これらのメッセージを数十万個保存する必要があります。

メッセージの送信と受信の間の時間が10ミリ秒以下である必要があります。

このプログラムはHaskellで書かれ、GHCでコンパイルされています。しかし、ガベージコレクションの休止時間は、私たちのレイテンシ要件に対して長すぎることがわかりました。

次のプログラムは、私たちのアプリケーションの簡略版です。これは Data.Map.Strict を使ってメッセージを保存しています。メッセージは ByteString で識別されます。 Int . 1,000,000のメッセージが数字の大きい順に挿入され、古いメッセージは削除され続け、履歴は最大200,000メッセージに保たれます。

module Main (main) where

import qualified Control.Exception as Exception
import qualified Control.Monad as Monad
import qualified Data.ByteString as ByteString
import qualified Data.Map.Strict as Map

data Msg = Msg !Int !ByteString.ByteString

type Chan = Map.Map Int ByteString.ByteString

message :: Int -> Msg
message n = Msg n (ByteString.replicate 1024 (fromIntegral n))

pushMsg :: Chan -> Msg -> IO Chan
pushMsg chan (Msg msgId msgContent) =
  Exception.evaluate $
    let
      inserted = Map.insert msgId msgContent chan
    in
      if 200000 < Map.size inserted
      then Map.deleteMin inserted
      else inserted

main :: IO ()
main = Monad.foldM_ pushMsg Map.empty (map message [1..1000000])

を使ってコンパイルし、実行しました。

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.10.3
$ ghc -O2 -optc-O3 Main.hs
$ ./Main +RTS -s
   3,116,460,096 bytes allocated in the heap
     385,101,600 bytes copied during GC
     235,234,800 bytes maximum residency (14 sample(s))
     124,137,808 bytes maximum slop
             600 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      6558 colls,     0 par    0.238s   0.280s     0.0000s    0.0012s
  Gen  1        14 colls,     0 par    0.179s   0.250s     0.0179s    0.0515s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.652s  (  0.745s elapsed)
  GC      time    0.417s  (  0.530s elapsed)
  EXIT    time    0.010s  (  0.052s elapsed)
  Total   time    1.079s  (  1.326s elapsed)

  %GC     time      38.6%  (40.0% elapsed)

  Alloc rate    4,780,213,353 bytes per MUT second

  Productivity  61.4% of total user, 49.9% of total elapsed

ここで重要な指標は、0.0515 秒、つまり 51 ミリ秒の最大休止時間です。私たちはこれを少なくとも 1 桁減らすことを望んでいます。

実験は、GC一時停止の長さが履歴のメッセージの数によって決定されることを示します。この関係は、ほぼ線形、またはおそらく超線形です。次の表は、この関係を示しています。( ベンチマークテストはこちらでご覧いただけます , および いくつかのグラフはこちら .)

msgs history length  max GC pause (ms)
===================  =================
12500                                3
25000                                6
50000                               13
100000                              30
200000                              56
400000                             104
800000                             199
1600000                            487
3200000                           1957
6400000                           5378

この遅延を減らすことができるかどうか、他のいくつかの変数で実験してみましたが、どれも大きな違いはありませんでした。これらの重要でない変数の中には、最適化 ( -O , -O2 ); RTS GCオプション ( -G , -H , -A , -c )、コア数( -N )、異なるデータ構造 ( Data.Sequence )、メッセージのサイズ、生成された短寿命のゴミの量などです。圧倒的な決定要因は、履歴のメッセージの数です。

私たちの作業理論は、各 GC サイクルがすべての作業アクセス可能なメモリを歩いてコピーしなければならないため、休止時間はメッセージの数に対して線形であるということです。

質問です。

• この線形時間理論は正しいのでしょうか？GCのポーズの長さはこのように単純な方法で表現できるのでしょうか、それとも現実はもっと複雑なのでしょうか？
• GCポーズがワーキングメモリで線形であるなら、関係する定数因子を減らす方法はないのでしょうか？
• インクリメンタルGCのオプション、みたいなものはないのでしょうか？研究論文を見ることしかできません。低レイテンシーのためにスループットを交換することは非常に厭わない。
• 複数のプロセスに分割する以外に、より小さい GC サイクルのためにメモリをパーティション化する方法はありますか?

どのように解決するのですか?

200Mb を超えるライブ データで 51ms の一時停止時間というのは、実際にはかなりうまくいっていますね。 私が作業しているシステムでは、その半分の量のライブ データで、より大きな最大一時停止時間があります。

あなたの仮定は正しいです。主要なGC一時停止時間はライブデータ量に正比例し、残念ながら現状のGHCではそれを回避する方法はないのです。 私たちは過去にインクリメンタル GC を実験しましたが、それは研究プロジェクトであり、リリースされた GHC に組み込むのに必要な成熟度には達しませんでした。

私たちが将来的にこれを助けることを期待していることの1つは、コンパクトリージョンです。 https://phabricator.haskell.org/D1264 . これは一種の手動メモリ管理で、ヒープ内の構造をコンパクトにすることで、GCはそれをトラバースする必要がありません。 これは長い間保存されるデータに対して最も効果的ですが、おそらくあなたの設定で個々のメッセージに使用するのに十分でしょう。 私たちは、GHC 8.2.0に搭載することを目標としています。

もしあなたが分散環境で、ある種のロードバランサーを持っているならば、一時停止の打撃を受けないようにするためにできるトリックがあります。