[Перевод] Инкрементальный сборщик мусора в Ruby 2.2

В этой статье рассматривается инкрементальный сборщик мусора (incremental GC), который был представлен в Ruby 2.2. Мы называем этот алгоритм RincGC. RincGC позволяет добиться более короткой паузы (GC pause time) по сравнению с Ruby 2.1.

Об авторе: Коичи Сасада (Koichi Sasada) работает в Heroku вместе с Nobu и Матц'ем над ядром ruby. Он написал YARV, сборщик мусора по поколениям (RgenGC) для Ruby 2.1, а также incremental GC для ruby 2.2 и данную статью.

Предпосылка

Ruby использует GC для автоматического коллекционирования неиспользуемых объектов. Благодаря сборщику мусора ruby-программисты не должны удалять объекты вручную и не должны волноваться о багах при таком удалении.

Первая версия Ruby уже использовала mark and sweep (M&S) алгоритм. M&S — это один из наиболее простых GC алгоритмов, который состоит из двух этапов:

1. Mark: пройтись по всем живым объектам и пометить их как «living object»

2. Sweep: утилизировать все непомеченные объекты, так как они больше не используются

M&S основан на том знании, что все найденные объекты из числа живых объектов являются живыми объектами. M&S алгоритм очень прост и из-за этого работает очень хорошо.

Mark & sweep GC алгоритм

Этот простой и эффективный алгоритм (и консервативный метод сборки мусора) позволяет писать расширения на языке С достаточно легко. В результате чего в Ruby есть много полезных расширений. Однако из-за этого алгоритма тяжело применить moving GC алгоритмы такие как уплотнение(compaction) и копирование(copying).

Сейчас написание С-расширений не так важно, потому что мы можем использовать FFI (foreign function interface). Но в начале, наличие большого количества расширений и предоставление множества фич через С-расширения было большим преимуществом, что и сделало интерпретатор Ruby более популярным.

Несмотря на то, что M&S алгоритм прост и замечательно работает, существует несколько проблем. Наиболее важные потенциальные проблемы — это производительность(throughput) и время пауз(pause time). GC замедляет вашу Ruby программу из-за накладных расходов при уборке мусора. Другими словами, низкая производительность GC увеличивает суммарное время выполнения вашего приложения. Каждая уборка мусора приостанавливает ваше приложение. Долгие паузы влияют на UI/UX веб приложений.

Чтобы решить проблему производительности, в Ruby 2.1 появился сборщик мусора на основе поколений (generational GC). Generational GC разбивает пространство кучи (heap space) на несколько частей для нескольких поколений (в Ruby мы разделяем пространство кучи на: молодое и старое пространство). Только что созданные объекты находятся в «молодом пространстве» и соответственно помечаются как «молодые объекты». После того, как молодые объекты переживут несколько сборок мусора (3 в Ruby 2.2), они переходят в разряд «старых объектов» и будут находится в «старом пространстве». Мы знаем, что в объектно-ориентированном программировании большинство объектов умирают молодыми. Поэтому нам нужно запустить сборку мусора только для «молодого пространства». Если места в молодом пространстве для создания объектов недостаточно, тогда запускается сборщик мусора для «старого пространства». Мы вызываем «Minor GC», когда сборщик мусора работает в молодом пространстве, и «Major GC» для всех: и для молодого и для старого пространств. Мы реализовали generational GC алгоритм с некоторыми изменениями и назвали наш алгоритм и реализацию сборки мусора «RGenGC». Вы можете узнать больше подробностей посмотрев мою презентацию и слайды на EuRuKo.

RGenGC значительно увеличивает производительность сборки мусора из-за очень быстрого Minor GC. Стоит заметить, что Major GC приостанавливает выполнение программы на долгое время и это время равно длительности паузы в Ruby 2.0 и более ранних версиях. Большинство же сборок мусора выполняет Minor GC.

Паузы в Major GC и Minor GC

Чтобы решить проблему с длительной паузой, лучше всего подходит инкрементальный сборщик мусора.

Инкрементальная сборка мусора

Алгоритм инкрементальной сборки мусора разделяет сам процесс сборки на несколько мелких процессов и чередует GC процессы и Ruby процессы. Вместо долгой паузы, инкрементальный сборщик мусора выдаёт множество коротких пауз. Суммарная длительность пауз останется такой же (или чуть больше из-за накладных расходов при использовании инкрементального сборщика мусора), но каждая отдельная пауза будет короче. Это позволяет получить более стабильную производительность.

В Ruby 1.9.3 появился «lazy sweep» GC, который уменьшает длительность пауз в sweep-фазе. Смысл laze sweep — запустить sweep-фазу не сразу, а пошагово. Lazy sweep уменьшает длительность отдельных пауз и является половиной incremental GC алгоритма. Теперь нам нужно сделать этап работы Major GC инкрементальным.

Давайте введём три понятия, чтобы объяснить процесс инкрементальной пометки объектов: «белый объект»(white object) — непомеченные объекты, «серый объект»(grey object) — помеченные, но могут ссылаться на белые объекты, «чёрный объект»(black object) — помеченные, но не указывают на какой-либо белый объект.

Используя эти три цвета мы можем объяснить «mark and sweep» алгоритм так:

1. Все существующие объекты помечены как белые

2. Явные живые объекты, такие как объекты в стеке, помечены как серые.

3. Выбираем любой серый объект и помечаем объект на который он ссылается тоже серым. Изменяем цвет оригинального объекта на чёрный. Повторяем пока не останется серых объектов, а будут только чёрные и белые.

4. Собираем белые объекты, так как все живые объекты окрашены в чёрный.

Чтобы сделать весь процесс инкрементальным, необходимо сделать шаг (3) инкрементальным. План такой: выбираем некоторые серые объекты и помечаем также серым объекты на которые они ссылаются, потом переключаемся на выполнение Ruby кода, затем возвращаемся к процессу пометки, и т.д.

Обычный процесс пометки (STW: stop the world) в сравнении с инкрементальным

При инкрементальном процессе пометки (incremental marking) объектов существует одна проблема. Черные объекты могут указывать на белые в процессе выполнения Ruby кода. Это является проблемой, так как чёрный объект по определению не может ссылаться на белые объекты. Чтобы предотвратить этот случай, мы используем «барьер записи» (write-barrier), чтобы выявить создание такой ссылки чёрного объекта на белый.

Например, объект массива 'ary' уже помечен как чёрный.

ary = []
# GC запускается и помечает чёрным

Объект 'obj = Object.new' будет белым, если мы выполним этот код.

ary << obj
# после создания obj GC не запускается

Теперь чёрный объект ссылается на белый объект. Если нет серых объектов ссылающихся на 'obj', то 'obj' будет белым в конце этапа пометки объектов и соответственно утилизирован по ошибке. Коллекционирование всех живых объектов — это грубая ошибка и необходимо этого избежать.

Барьер записи вызывается каждый раз, когда объект начинает ссылаться на новый объект. Барьер записи определяет, когда была создана ссылка с чёрного объекта на белый. Когда это происходит, чёрный объект меняет свой цвет на серый (или серый с указателем на белый объект). Барьеры записи полностью решают проблему коллекционирования всех живых объектов.

Это и есть основной смысл инкрементального алгоритма. Как видите, это не так сложно. Возможно у вас возникнет вопрос: «почему Ruby всё еще не использует этот простой GC алгоритм?»

Инкрементальный сборщик мусора в Ruby 2.2

При реализации инкрементального процесса пометки в интерпретаторе Ruby (CRuby) возникает серьезная проблема — недостаток барьеров записи.

Generational GC, который был реализован в Ruby 2.1, также нуждался в барьерах записи. Чтобы реализовать generational GC мы изобрели новый метод — «барьер записи незащищенных объектов» (write barrier unprotected objects). Это означает, что мы разделили все объекты на защищённые и незащищённые. Таким образом, мы можем гарантировать, что все ссылающиеся защищённые объекты находятся под контролем. Мы не можем контролировать ссылки с незащищённых объектов. С введением понятия незащищённый объект (unprotected object), можно реализовать generational GC в Ruby 2.1

Мы также можем должным образом реализовать incremental GC используя незащищённые объекты:

1. Окрасим все существующие объекты в белый

2. Окрасим все явно живые объекты в серый, включая объекты в стеке

3. Берём один серый объект и красим в серый все объекты, на которые он ссылается. Изменяем его цвет на чёрный. Повторяем до тех пор, пока не останется серых объектов. Только черные и белые. Эта фаза выполняется поэтапно.

4. Собираем белые объекты, т.к. все живые объекты имеют чёрный цвет

Так мы можем гарантировать, что у нас нет белых живых объектов.

Повторное сканирование от барьера записи незащищённых объектов(WB unp.) в конце процесса пометки.

К сожалению, 4-ый этап может создавать длительную паузу, чего мы надеемся избежать. Однако суммарное время пауз связано с количеством барьеров записи живых незащищенных объектов. Большинство объектов в Ruby это String, Array, Hash или же простые(pure) объекты созданные программистом. Они представляют собой защищённые объекты. На практике, паузы для барьера записи незащищённых объектов не создаёт каких-либо проблем в большинстве случаев.

Мы сделали инкрементальный процесс пометки только для major GC, т.к. никто не жалуется на паузы в minor GC. Максимальная длительность паузы в нашем инкрементальном GC меньше чем в minor GC. Если вас устраивает время пауз в minor GC, то вам не надо волноваться о времени пауз в major GC.

Я также применил хитрость, чтобы реализовать инкрементальный GC в Ruby. У нас есть набор «черных и незащищённых» объектов. Чтобы сборщик мусора работал быстро, мы создали «незащищённый» bitmap, который представляет собой незащищённые объекты, и отдельный «помеченный» bitmap, который показывает какие объекты были помечены. Используя логическое произведение мы можем найти «черные и незащищённые» объекты.

Оценка длительности пауз инкрементального GC

Для того чтобы измерить длительность пауз в процессе сборок мусора, будем использовать gc_tracer. В gc_tracer есть модуль GC:Tracer, который позволяет отслеживать параметры, относящиеся к процессу сборки мусора. gc_tracer выводит каждый такой параметр в файл.

Сборка мусора включает в себя следующие события:

start

end_mark

end_sweep

newobj

freeobj

enter

exit

Как я описал выше, GC в Ruby имеет две фазы: «mark» и «sweep». Событие «start» означает старт mark-фазы, а «end_mark» — её завершение. Событие «end_mark» также означает начало sweep-фазы. Очевидно, что «end_sweep» говорит о конце sweep-фазы и также значит завершения процесса сборки мусора.

«newobj» и «freeobj» — это события при выделении памяти для объекта и её освобождении.

Мы используем «enter» и «exit» события для измерения длительности пауз. Incremental GC (incremental marking and lazy sweeping) использует приостановку mark-фазы и sweep-фазы. «enter» означает «entering GC related event». И наконец «exit» означает «exitting GC related event»

Следующий рисунок показывает распределение событий во времени в текущем инкрементальном GC.

Мы можем измерить текущее время ( в Линуксе текущее время — это результат вызова gettimeofday()) для каждого события. Таким образом, мы можем измерить длительность пауз в GC используя события «enter» и «exit».

Я использую ko1-test-app для сравнения производительности. ko1-test-app — это простое Rails приложение написанное для меня Аароном Паттерсоном (Aaron Patterson).

Чтобы использовать джем gc_tracer, я добавил rake rule «test_gc_tracer»:

diff --git a/perf.rake b/perf.rake
index f336e33..7f4f1bd 100644
--- a/perf.rake
+++ b/perf.rake
@@ -54,7 +54,7 @@ def do_test_task app
   body.close
 end

-task :test do
+def test_run
   app = Ko1TestApp::Application.instance
   app.app

@@ -67,6 +67,22 @@ task :test do
   }
 end

+task :test do
+  test_run
+end
+
+task :test_gc_tracer do
+  require 'gc_tracer'
+  require 'pp'
+  pp GC.stat
+  file = "log.#{Process.pid}"
+  GC::Tracer.start_logging(file, events: %i(enter exit), gc_stat: false) do
+ test_run
+  end
+  pp GC.stat
+  puts "GC tracer log: #{file}"
+end
+
 task :once do
   app = Ko1TestApp::Application.instance
   app.app

И запустил bundle exec rake test_gc_tracer KO1TEST_CNT=30000. Значение «30000» означает что мы будем симулировать 30,000 запросов. Результаты будут писаться в файл «log.xxxx», где xxxx — это id процесса приложения. Файл должен выклядеть примерно так:

type  tick  major_by      gc_by   have_finalizer  immediate_sweep state
enter   1419489706840147      0     newobj  0     0     sweeping
exit  1419489706840157      0     newobj  0     0     sweeping
enter   1419489706840184      0     newobj  0     0     sweeping
exit  1419489706840195      0     newobj  0     0     sweeping
enter   1419489706840306      0     newobj  0     0     sweeping
exit  1419489706840313      0     newobj  0     0     sweeping
enter   1419489706840612      0     newobj  0     0     sweeping
...

У меня файл насчитывает 1,142,907 строк.

Колонка «type» содержит имя события, «tick» — текущее время (результат gettimeofday(), количество микросекунд с начала эпохи). Мы можем увидеть длительность паузы используя эту информацию. Используя первые две строки выше, мы можем измерить длительность паузы: 10 μs (1419489706840157 — 1419489706840147).

Следующий небольшой скрипт показывает длительность каждой паузы.

enter_tick = 0
open(ARGV.shift){|f|
  f.each_line{|line|
  e, tick, * = line.split(/\s/)
  case e
  when 'enter'
    enter_tick = tick.to_i
  when 'exit'
    st = tick.to_i - enter_tick
    puts st if st > 100 # over 100 μs
  else
    # puts line
  end
  }
}

В лог файле будет много строк, так как этот скрипт печатает длительность пауз каждые 100μs.

Следующий рисунок показывает результат измерений.

Мы видим, что у generational GC есть 7 огромных пауз. Это должно быть паузы вызванные запуском major GC. Максимальное время пауз примерно 15ms(15Kμs). Однако, инкрементальный GC уменьшает максимальное время пауз до 2ms (2Kμs). Отлично.

Заключение

Ruby 2.2 использует инкрементальный алгоритм сборки мусора для уменьшения времени паузы при сборке мусора.

Учтите, что incremental GC — это не «серебрянная пуля». Как я уже описал, incremental GC не влияет на производительность. Это никак не повлияет на время ответа, если запрос слишком долгий и вызывает несколько раз major GC. Суммарное время сборки мусора не будет уменьшено за счёт инкрементального GC.

Recommended article: Chomsky: We Are All – Fill in the Blank.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.