Mengurangi waktu jeda pengumpulan sampah di program Haskell

Kami sedang mengembangkan program yang menerima dan meneruskan "pesan", sambil menyimpan riwayat sementara pesan-pesan itu, sehingga dapat memberi tahu Anda riwayat pesan jika diminta. Pesan diidentifikasi secara numerik, biasanya berukuran sekitar 1 kilobyte, dan kita perlu menyimpan ratusan ribu pesan ini.

Kami ingin mengoptimalkan program ini untuk latensi: waktu antara mengirim dan menerima pesan harus di bawah 10 milidetik.

Program ini ditulis dalam Haskell dan dikompilasi dengan GHC. Namun, kami telah menemukan bahwa jeda pengumpulan sampah terlalu lama untuk persyaratan latensi kami: lebih dari 100 milidetik dalam program dunia nyata kami.

Program berikut adalah versi sederhana dari aplikasi kami. Ini menggunakan Data.Map.Strictuntuk menyimpan pesan. Pesan ByteStringdiidentifikasi oleh seorang Int. 1.000.000 pesan disisipkan dalam urutan numerik yang meningkat, dan pesan terlama terus dihapus untuk menjaga riwayat maksimum 200.000 pesan.

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])

Kami mengkompilasi dan menjalankan program ini menggunakan:

$ 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

Metrik penting di sini adalah "jeda maksimum" dari 0,0515 detik, atau 51 milidetik. Kami ingin mengurangi ini setidaknya dengan urutan besarnya.

Eksperimen menunjukkan bahwa panjang jeda GC ditentukan oleh jumlah pesan dalam riwayat. Hubungannya kira-kira linear, atau mungkin super-linear. Tabel berikut menunjukkan hubungan ini. ( Anda dapat melihat tes pembandingan kami di sini , dan beberapa grafik di sini .)

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

Kami telah bereksperimen dengan beberapa variabel lain untuk menemukan apakah mereka dapat mengurangi latensi ini, tidak ada yang membuat perbedaan besar. Di antara variabel-variabel yang tidak penting adalah: optimasi ( -O, -O2); Pilihan RTS GC ( -G, -H, -A, -c), jumlah core ( -N), struktur data yang berbeda ( Data.Sequence), ukuran pesan, dan jumlah yang dihasilkan sampah berumur pendek. Faktor penentu yang luar biasa adalah jumlah pesan dalam sejarah.

Teori kerja kami adalah bahwa jeda linear dalam jumlah pesan karena setiap siklus GC harus menelusuri semua memori yang dapat diakses dan menyalinnya, yang jelas merupakan operasi linear.

Pertanyaan:

• Apakah teori waktu linear ini benar? Bisakah panjang GC jeda diungkapkan dengan cara sederhana ini, atau apakah kenyataannya lebih kompleks?
• Jika jeda GC linier dalam memori kerja, apakah ada cara untuk mengurangi faktor konstan yang terlibat?
• Apakah ada opsi untuk GC tambahan, atau yang seperti itu? Kami hanya bisa melihat makalah penelitian. Kami sangat ingin memperdagangkan throughput untuk latensi yang lebih rendah.
• Apakah ada cara untuk "mempartisi" memori untuk siklus GC yang lebih kecil, selain membelah menjadi beberapa proses?

Anda sebenarnya melakukan cukup baik untuk memiliki jeda waktu 51ms dengan data langsung lebih dari 200Mb. Sistem yang saya kerjakan memiliki waktu jeda maks lebih besar dengan setengah dari jumlah data langsung.

Asumsi Anda benar, waktu jeda GC utama berbanding lurus dengan jumlah data langsung, dan sayangnya tidak ada cara lain untuk mengatasi GHC. Kami bereksperimen dengan GC tambahan di masa lalu, tetapi itu adalah proyek penelitian dan tidak mencapai tingkat kematangan yang diperlukan untuk melipatnya menjadi GHC yang dirilis.

Satu hal yang kami harap akan membantu dalam hal ini di masa depan adalah wilayah yang ringkas: https://phabricator.haskell.org/D1264 . Ini semacam manajemen memori manual tempat Anda memadatkan struktur di heap, dan GC tidak harus melewatinya. Ini berfungsi paling baik untuk data yang berumur panjang, tetapi mungkin itu akan cukup baik untuk digunakan untuk pesan individual di pengaturan Anda. Kami bertujuan untuk memilikinya di GHC 8.2.0.

Jika Anda berada dalam pengaturan terdistribusi dan memiliki penyeimbang beban dari beberapa jenis ada trik yang dapat Anda mainkan untuk menghindari jeda, Anda pada dasarnya memastikan bahwa penyeimbang beban tidak mengirim permintaan ke mesin yang akan lakukan GC utama, dan tentu saja pastikan bahwa mesin masih menyelesaikan GC meskipun tidak mendapatkan permintaan.

Saya telah mencoba cuplikan kode Anda dengan menggunakan pendekatan ringbuffer IOVectorsebagai struktur data yang mendasarinya. Pada sistem saya (GHC 7.10.3, opsi kompilasi yang sama) ini menghasilkan pengurangan waktu maks (metrik yang Anda sebutkan dalam OP) sebesar ~ 22%.

NB. Saya membuat dua asumsi di sini:

1. Struktur data yang bisa berubah-ubah adalah cocok untuk masalah ini (saya kira lewat pesan menyiratkan IO bagaimanapun)
2. Pesan Anda Id terus menerus

Dengan beberapa Intparameter tambahan dan aritmatika (seperti ketika messageId direset kembali ke 0 atau minBound) maka harus langsung untuk menentukan apakah pesan tertentu masih dalam sejarah dan mengambilnya membentuk indeks yang sesuai di ringbuffer.

Untuk kesenangan pengujian Anda:

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

import qualified Data.Vector.Mutable as Vector

data Msg = Msg !Int !ByteString.ByteString

type Chan = Map.Map Int ByteString.ByteString

data Chan2 = Chan2
    { next          :: !Int
    , maxId         :: !Int
    , ringBuffer    :: !(Vector.IOVector ByteString.ByteString)
    }

chanSize :: Int
chanSize = 200000

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


newChan2 :: IO Chan2
newChan2 = Chan2 0 0 <$> Vector.unsafeNew chanSize

pushMsg2 :: Chan2 -> Msg -> IO Chan2
pushMsg2 (Chan2 ix _ store) (Msg msgId msgContent) =
    let ix' = if ix == chanSize then 0 else ix + 1
    in Vector.unsafeWrite store ix' msgContent >> return (Chan2 ix' msgId store)

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

main, main1, main2 :: IO ()

main = main2

main1 = Monad.foldM_ pushMsg Map.empty (map message [1..1000000])

main2 = newChan2 >>= \c -> Monad.foldM_ pushMsg2 c (map message [1..1000000])

Saya harus setuju dengan yang lain - jika Anda memiliki kendala waktu nyata, maka menggunakan bahasa GC tidak ideal.

Namun, Anda dapat mempertimbangkan bereksperimen dengan struktur data lain yang tersedia daripada hanya Data.Map.

Saya menulis ulang menggunakan Data.Sequence dan mendapat beberapa perbaikan yang menjanjikan:

msgs history length  max GC pause (ms)
===================  =================
12500                              0.7
25000                              1.4
50000                              2.8
100000                             5.4
200000                            10.9
400000                            21.8
800000                            46
1600000                           87
3200000                          175
6400000                          350

Meskipun Anda mengoptimalkan latensi, saya perhatikan metrik lainnya juga meningkat. Dalam kasus 200000, waktu eksekusi turun dari 1,5s ke 0,2s, dan total penggunaan memori turun dari 600MB ke 27MB.

Saya harus perhatikan bahwa saya menipu dengan mengutak-atik desain:

• Saya menghapus Intdari Msg, jadi tidak ada di dua tempat.
• Alih-alih menggunakan Peta dari Ints ke ByteStrings, saya menggunakan a Sequencedari ByteString, dan bukannya satu Intper pesan, saya pikir itu bisa dilakukan dengan satu Intuntuk keseluruhan Sequence. Dengan asumsi pesan tidak dapat disusun ulang, Anda dapat menggunakan satu offset untuk menerjemahkan pesan mana yang Anda inginkan di tempat pesan itu berada dalam antrian.

(Saya menyertakan fungsi tambahan getMsguntuk menunjukkan hal itu.)

{-# LANGUAGE BangPatterns #-}

import qualified Control.Exception as Exception
import qualified Control.Monad as Monad
import qualified Data.ByteString as ByteString
import Data.Sequence as S

newtype Msg = Msg ByteString.ByteString

data Chan = Chan Int (Seq ByteString.ByteString)

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

maxSize :: Int
maxSize = 200000

pushMsg :: Chan -> Msg -> IO Chan
pushMsg (Chan !offset sq) (Msg msgContent) =
    Exception.evaluate $
        let newSize = 1 + S.length sq
            newSq = sq |> msgContent
        in
        if newSize <= maxSize
            then Chan offset newSq
            else
                case S.viewl newSq of
                    (_ :< newSq') -> Chan (offset+1) newSq'
                    S.EmptyL -> error "Can't happen"

getMsg :: Chan -> Int -> Maybe Msg
getMsg (Chan offset sq) i_ = getMsg' (i_ - offset)
    where
    getMsg' i
        | i < 0            = Nothing
        | i >= S.length sq = Nothing
        | otherwise        = Just (Msg (S.index sq i))

main :: IO ()
main = Monad.foldM_ pushMsg (Chan 0 S.empty) (map message [1..5 * maxSize])

Seperti disebutkan dalam jawaban lain, pengumpul sampah di GHC melintasi data langsung, yang berarti semakin lama data yang Anda simpan dalam memori, semakin lama GC akan dijeda.

GHC 8.2

Untuk mengatasi masalah ini sebagian, fitur yang disebut wilayah kompak diperkenalkan di GHC-8.2. Ini adalah fitur sistem runtime GHC dan perpustakaan yang memperlihatkan antarmuka yang nyaman untuk bekerja dengannya. Fitur compact region memungkinkan menempatkan data Anda ke tempat yang terpisah di memori dan GC tidak akan melewatinya selama fase pengumpulan sampah. Jadi jika Anda memiliki struktur besar yang ingin Anda simpan dalam memori, pertimbangkan untuk menggunakan wilayah kompak. Namun, wilayah kompak itu sendiri tidak memiliki pengumpul sampah mini di dalamnya, ini berfungsi lebih baik untuk struktur data tambahan saja , bukan sesuatu seperti di HashMapmana Anda juga ingin menghapus barang-barang. Padahal Anda bisa mengatasi masalah ini. Untuk detail lihat posting blog berikut:

• Menggunakan wilayah kompak (oleh Alexander Vershilov)

GHC 8.10

Selain itu, sejak GHC-8.10, algoritma pengumpul sampah inkremental rendah latensi baru diimplementasikan. Ini adalah algoritme GC alternatif yang tidak diaktifkan secara default, tetapi Anda dapat mengikutinya jika mau. Jadi, Anda dapat mengganti GC default ke yang lebih baru untuk secara otomatis mendapatkan fitur yang disediakan oleh wilayah kompak tanpa perlu melakukan pembungkus dan pembungkus manual. Namun, GC baru bukan peluru perak dan tidak menyelesaikan semua masalah secara otomatis, dan memiliki trade-off. Untuk tolok ukur dari GC baru lihat repositori GitHub berikut:

• Benchmark GC inkremental latensi rendah

Yah Anda menemukan batasan bahasa dengan GC: Mereka tidak cocok untuk sistem real-time hardcore.

Anda memiliki 2 opsi:

1st Meningkatkan ukuran heap dan menggunakan sistem caching 2 level, pesan terlama dikirim ke disk dan Anda menyimpan pesan terbaru di memori, Anda dapat melakukan ini dengan menggunakan paging OS. Masalahnya, meskipun dengan solusi ini adalah paging bisa mahal tergantung pada kemampuan membaca unit memori sekunder yang digunakan.

Program ke-2 solusi yang menggunakan 'C' dan antarmuka dengan FFI untuk haskell. Dengan begitu Anda dapat melakukan manajemen memori Anda sendiri. Ini akan menjadi pilihan terbaik karena Anda dapat mengontrol memori yang Anda butuhkan sendiri.