Сокращение времени паузы сбора мусора в программе Haskell
Мы разрабатываем программу, которая получает и пересылает "сообщения", сохраняя при этом временную историю этих сообщений, чтобы она могла сообщать вам историю сообщений по запросу. Сообщения идентифицируются численно, обычно размером около 1 килобайта, и нам нужно хранить сотни тысяч этих сообщений.
Мы хотим оптимизировать эту программу для задержки: время между отправкой и получением сообщения должно быть ниже 10 миллисекунд.
Программа написана в Haskell и скомпилирована с GHC. Однако мы обнаружили, что паузы в сборке мусора слишком велики для наших требований к задержкам: более 100 миллисекунд в нашей реальной программе.
Следующая программа представляет собой упрощенную версию нашего приложения. Для хранения сообщений используется 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 миллисекунда. Мы хотим уменьшить это, по крайней мере, на порядок.
Эксперимент показывает, что длина паузы 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, кроме разделения на несколько процессов?
Ответы
Ответ 1
На самом деле вы довольно хорошо выполняете время паузы в 51 мс с более чем 200 МБ данных в реальном времени. Система, над которой я работаю, имеет большее максимальное время паузы с половиной объема данных в реальном времени.
Ваше предположение верно, основное время паузы GC прямо пропорционально количеству живых данных, и, к сожалению, нет никакого способа обойти это с GHC в том виде, в каком он стоит. Мы экспериментировали с инкрементным GC в прошлом, но это был исследовательский проект и не достиг уровня зрелости, необходимого для его сложения в выпущенный GHC.
Одна вещь, на которую мы надеемся, поможет в будущем - это компактные регионы: https://phabricator.haskell.org/D1264. Это своего рода ручное управление памятью, в котором вы уплотняете структуру в куче, и GC не должен пересекать ее. Он лучше всего подходит для долговечных данных, но, возможно, он будет достаточно хорош для использования для отдельных сообщений в настройках. Мы стремимся использовать его в GHC 8.2.0.
Если вы находитесь в распределенной настройке и имеете какой-либо балансировщик нагрузки, есть трюки, которые вы можете играть, чтобы избежать использования паузы, вы в основном убедитесь, что балансировщик нагрузки не отправляет запросы на машины, которые собираются сделать основной GC и, конечно же, убедиться, что машина по-прежнему завершает GC, даже если она не получает запросы.
Ответ 2
Я пробовал ваш фрагмент кода с помощью метода ringbuffer, используя IOVector
в качестве базовой структуры данных. В моей системе (GHC 7.10.3, такие же параметры компиляции) это привело к сокращению максимального времени (метрика, которую вы указали в вашем OP) на ~ 22%.
NB. Здесь я сделал два предположения:
- Изменчивая структура данных - это хорошо подходит для проблемы (я думаю, что передача сообщений подразумевает IO)
- Ваше сообщениеId непрерывно
С дополнительным параметром Int
и арифметикой (например, когда messageId reset назад к 0 или minBound
), тогда должно быть легко определить, остается ли какое-то сообщение в истории и извлекать его из соответствующей индекс в кольцевом буфере.
Для удовольствия от тестирования:
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])
Ответ 3
Я должен согласиться с остальными - если у вас жесткие ограничения в режиме реального времени, использование языка GC не является идеальным.
Однако вы можете подумать о том, чтобы экспериментировать с другими доступными структурами данных, а не только с Data.Map.
Я переписал его с использованием Data.Sequence и получил некоторые многообещающие улучшения:
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
Несмотря на то, что вы оптимизируете время ожидания, я заметил, что другие показатели также улучшаются. В случае 200000 время выполнения уменьшается с 1,5 до 0,2 с, а общее использование памяти падает с 600 МБ до 27 МБ.
Я должен отметить, что я обманул, изменив дизайн:
- Я удалил
Int
из Msg
, поэтому он не в двух местах.
- Вместо использования карты от
Int
до ByteString
s я использовал Sequence
из ByteString
s, а вместо одного Int
для сообщения, я думаю, это можно сделать с помощью одного Int
для всего Sequence
. Предполагая, что сообщения не могут быть переупорядочены, вы можете использовать одно смещение для перевода того сообщения, которое вы хотите, где оно находится в очереди.
(я включил дополнительную функцию getMsg
, чтобы продемонстрировать это.)
{-# 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])
Ответ 4
Ну, вы нашли ограничение на языки с GC: они не подходят для хардкорных систем реального времени.
У вас есть 2 варианта:
1. Увеличьте размер кучи и используйте систему кэширования уровня 2, самые старые сообщения отправляются на диск, и вы сохраняете самые новые сообщения в памяти, вы можете сделать это, используя подкачку ОС. Проблема, хотя с этим решением заключается в том, что пейджинг может быть дорогостоящим в зависимости от возможностей чтения используемого дополнительного блока памяти.
2-я программа, которая использует "C" и связывает ее с FFI с haskell. Таким образом, вы можете выполнять собственное управление памятью. Это было бы лучшим вариантом, так как вы можете самостоятельно контролировать нужную вам память.