Перевод блог-поста главного автора сборщика мусора в Go, Ричарда Хадсона, изобретателя многих алгоритмов для GC в других языках, одного из ведущих инженеров Intel (сейчас работает в Google).

Go планирует свой сборщик мусора (GC) не только для 2015 года, но и для 2025 и дальше: это должен быть GC, который поддерживает современные принципы разработки программ и хорошо масштабируется вместе с появлением нового софта и железа в следующие десятилетия. В этом будущем нет места для пауз GC с «остановкой мира» (stop-the-world), которые были преградой для более широкого применения таких безопасных и надёжных языков, как Go.

Go 1.5, первый проблеск этого будущего, достиг цели уменьшить верхнюю планку пауз до 10мс, которую мы поставили перед собой год назад. Некоторые впечатляющие цифры вы можете посмотреть в докладе на GopherСon. Эти улучшения времени отклика привлекли много внимания; блог пост Робина Верлангена «Миллиарды запросов в день встречают Go 1.5» подтверждает наши расчеты реальными результатами. Отдельно нам понравились скриншоты графиков продакнш-сервера от Алана Шреве и его комментарий «Holy 85% reduction!».

Сегодня 16 гигабайт памяти стоят 100$ и все процессоры многоядерны, и поддерживают гипертрединг. Через 10 лет это железо будет выглядеть устаревшим, но программы написанные на Go сегодня должны будут уметь масштабироваться, чтобы работать на растущих ресурсах железа и быть готовыми к «следующему прорыву» (next big thing). Учитывая, что железо дает возможность наращивать пропускную способность, сборщик мусора Go разрабатывается так, чтобы отзывчивость и маленькие паузы были приоритетом, а тюнинг происходил одним ползунком. Go 1.5 это первый большой шаг в этом направлении, и эти первые шаги навсегда повлияют на дальнейшее развитие Go и на программы, написанные на нём. Этот пост даёт обзорную картинку того, что мы сделали в Go 1.5 сборщике.

Детали


Чтобы создать сборщик мусора для следующего десятилетия мы обратились к алгоритму, написанному несколько десятилетий назад. Новый сборщик мусора в Go является конкурентным (concurrent), трехцветным (tri-color), mark-sweep сборщиком, идея которого впервые была предложена Дейкстрой в 1978 году. Этот подход намеренно так сильно несоответствует большинству современных сборщиков мусора «энтерпрайз»-уровня, и мы считаем, что это наилучший подход для современного железа и требований к паузам на новом железе.

В трехцветном сборщике мусора, каждый объект может быть помечен, как белый, серый или чёрный, и мы рассматриваем кучу (heap) как граф связанных объектов. В начале каждого цикла GC все объекты белые. GC проходит всё корневые узлы (roots) графа, которые являются объектами, напрямую доступными программе — это глобальные переменные и переменные в стеке — и помечает их серыми. Затем GC выбирает серый объект, делает его чёрным, а затем сканирует его на наличие указателей и других объектов. Если скан обнаруживает указатель на белый объект, он делает его серым. Этот процесс повторяется, пока не останется серых объектов. В этот момент все белые объекты будут считаться недостижимыми и могут быть переиспользованы.

Это всё происходит параллельно с работой программы, также называемой мутатором (mutator), изменяющей указатели по мере того, как работает сборщик. Из этого следует, что мутатор должен поддерживать инвариант того, что ни один черный объект не указывает на белый, чтобы сборщик мусора не потерял след объекта в той части кучи, которую он уже обошел. Поддержка такого инварианта это задача для «барьеров записи» (write barrier), которая по сути является маленькой функцией, запускающейся каждый раз, когда мутатор меняет указатель в куче. Барьер записи в Go помечает серым объекты, которые были белыми, гарантируя, что сборщик мусора рано или поздно просканирует его.

Определение момента, когда все объекты просканированы — тонкая задача и может быть очень дорогостоящей и сложной, если мы хотим избежать блокировок мутатора. Для простоты Go 1.5 делает максимум возможного в фоне, а потом приостанавливает программу на совсем короткое время, чтобы проверить все потенциально серые объекты. Найти идеальное соотношение для времени необходимого для этой паузы и для всей работы GC является одной из главных задач для Go 1.6.

Конечно же, дьявол кроется в деталях. Когда начинать очередной цикл GC? Какую метрику использовать для принятия этого решения? Как должны взаимодействовать GC и планировщик Go? Как останавливать потоки мутатора так, чтобы хватило времени на сканирование их стеков? Как мы представляем белые, серые и черные объекты, чтобы максимально эффективно искать и сканировать серые объекты? Как мы узнаём, где их корневые узлы? Как мы узнаём, где находятся указатели в объекте? Как мы минимизируем фрагментацию памяти? Как мы решаем вопросы производительности кешей? Насколько большой должна быть куча? И так далее, и тому подобное, кое-что относящееся к аллокациям, кое-что к поиску достижимых объектов, кое-что к планированию, но основные вопросы затрагивают производительность. Дискуссии о более низкоуровневых деталях каждой из этих областей выходят за рамки этого поста.

На более высоком уровне, один из подходов решения этих проблем для GC является добавление в GC ползунков (knobs), по одному на каждую задачу. Разработчик тогда может тюнить GC под себя, настраивая множество параметров. Минус тут в том, что через 10 лет с одним или двумя новыми ползунками каждый год, вы в итоге заканчиваете Трудовым Договором Об Использовании Переключателей GC. Go не пойдёт этим путём. Вместо этого мы даём лишь один ползунок, называемый GOGC. Его значение контролирует общий размер кучи относительно размера достижимых объектов. Дефолтное значение «100» означает, что общий размер кучи сейчас на 100% больше (тоесть, вдвое) размера реально достижимых объектов после последнего цикла GC. «200» означает, что общий размер кучи на 200% больше (тоесть, в три раза), чем размер реально используемых объектов. Если вы хотите уменьшить общее количество времени работы GC, увеличьте GOGC. Если вы хотите отдать больше времени GC, и выиграть себе память — уменьшайте GOGC.

Важно понимать, что по мере того, как количество памяти удвоится со следующим поколением железа, простое увеличение GOGC вдвое уменьшит количество циклов GC вдвое. С другой стороны, так как GOGC оперирует понятием достижимых объектов, увеличение нагрузки и сопутствующее увеличение количества достижимых объектов не нуждается в ретюнинге. Приложение просто масштабируется. Более того, необременённая поддержкой дюжин ползунков, команда, пишущая рантайм языка может сфокусироваться на улучшении рантайма, основываясь на фидбеке от реальных программ в продакшене.

Заключение


Сборщик мусора Go 1.5 вводит нас в будущее, где паузы с остановкой мира более не являются преградой для безопасного и надежного языка. Это будущее, где приложения масштабируются без усилий вместе с новым железом, и, по мере того, как железо становится всё более мощным, сборщик мусора не будет помехой для ещё лучшего, и ещё более масштабирующегося софта. Это хорошее место для следующего десятилетия и того, что будет за ним. Если вы хотите узнать подробности, как мы убрали проблемы с паузами, посмотрите доклад Go GC: Latency Problem Solved presentation или слайды доклада.

Комментарии (31)


  1. leventov
    01.09.2015 10:29
    -1

    Пустой пост. Реальный инетерес только в одном слайде по ссылке:

    И то, непонятно, как именно особенности Go-рантайма позволяют написать более быстрый сборщик мусора


    1. divan0
      01.09.2015 17:20
      +2

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


      1. leventov
        01.09.2015 23:51
        +4

        Создатель GC (очевидно, человек на переднем краю прогресса) не должен рассказывать такие вот «101». Что стоит за решениями, да более того, что это за решения (если вы не рассматриваете «использовать mark-sweep» как содержательное решение) — этого нет вообще. Сравнение с Java чисто назывное, как я собственно и написал выше — сравнение вроде есть, но все равно ничерта непонятно, почему в Go такие маленькие паузы (или почему в Java — такие большие). Приоритеты и планы на будущие — чистый маркетинг в плане «жить станет лучше, жить станет веселее».

        Так что да, пост пустой.


        1. M0sTH8
          02.09.2015 00:42
          -2

          Мне кажется Хадсон никому ничего не должен, тем более вам. Если вам действительно интересны технические детали, то все они описаны в различных драфтах и документах, с которыми работают разработчики. К примеру вот этот docs.google.com/document/d/1kBx98ulj5V5M9Zdeamy7v6ofZXX3yPziAf0V27A64Mo/preview?sle=true

          Ожидать что в блоге, рассчитанном на массовую аудиторию будут глубокие технические подробности, мне кажется, не верно.


          1. leventov
            02.09.2015 00:50

            «Массовая аудитория» уже такие посты не хавает, потому что их может штамповать пачками любая технология (и штампует). Все такие high-performant, low latency, что я прям не знаю. Хочется уже «диффы» видеть.

            — В Go нет тяжелых потоков, синхронизация такая-то и такая-то, что, с одной стороны, позволяет ускорить сборщик, за счет того-то и того-то, а, с другой, не ограничивает вас как программистов, потому что можно применять такие-то и такие-то шаблоны.

            — Сборщик работает регулярно, каждые 50 миллисекунд, что позволяет сократить паузы, но впустую тратит ресурсы в приложениях, которые вообще не создают мусора.


            Так я представляю себе не пустой пост по теме (пусть и без особых деталей)


            1. divan0
              02.09.2015 01:57
              -1

              Вы так пишете, будто вам и прямо кто-то «должен» писать посты специально под ваш интерес. Я понимаю ваш поинт, но он называется не «пустой пост» и не «разрабочик GC не должен», а «я интересуюсь подробно внутренностями и хочу найти подробные бенчмарки и научные работы по теме».


              1. leventov
                02.09.2015 02:11
                +3

                Отнюдь. Я умею ставить себя на место пользователя технологий, клиента таких компаний как Google и Oracle. Они наперебой твердят, что у них все самое лучшее, самое быстрое. Как я должен выбирать стек?

                Вот приходит разработчик Go весь в белом и рассказывает, что у них паузы до 10 ms, что даже как-то неудобно сравнивать с Java, по отношению к последней.

                Как говориться, «если я просыпаюсь и понимаю, что меня никто не обманывает, я очень сильно напрягаюсь — видимо кто–то обманывает меня так, что я этого не понимаю.» В чем магия? Разработчики Java тупые? Они выбрали для своего рантайма другой набор компромиссов, затачиваются на другие сценарии использования? Тогда четко это обозначьте, чтобы я мог сравнить со своим сценарием и выбрать технологию.

                Заметьте, выше звучали не слова «внутренности» и «научные работы», а «приложение», «сценарий использования», «выбор стека».


                1. divan0
                  02.09.2015 02:21

                  Как говориться, «если я просыпаюсь и понимаю, что меня никто не обманывает, я очень сильно напрягаюсь»

                  Ужас какой )

                  Вы же понимаете, что дизайн языка влияет на почти любой аспект — от скорости парсера кода до выбора алгоритмов GC. Я не настолько глубоко разбираюсь во внутренностях, но более чем уверен, что простота дизайна Go, отсутствие очень многих сложных концепций, привела ко многим решениями, которые в Java просто не возможны. Это разные языки, у них разная система типов, разные подходы, они по разному решают многие компромиссы — отсюда и разница.


                  1. leventov
                    02.09.2015 02:28
                    +1

                    Отлично. Тогда если бы написали пост «мы рвем Java, потому что у нас нет сложных концепций» — причем конкретно указывая, каких именно концепций нет, и почему их наличие делает Java тормознутой — это вызвало бы у меня гораздо больше доверия, и было бы полезнее. Я бы поставил заметочку: «так, если на следующем проекте мне будут не нужны вот эти концепции, возьму Go, а не Java».

                    А так — какой-то универсальный позитивчик про «светлое настоящее и еще более светлое будущее», который автоматически вызывает скепсис


      1. Zelgadis
        05.09.2015 00:30
        +1

        Нормальному програмисту достаточно сказать, что в Пщ GC вот такой: concurrent tri-color mark-sweet, а так же дать ссылку на академическую работу. Сотый раз рассказывать как работает tri-color mark-sweet с write barrier нет никакого смысла.


        1. divan0
          05.09.2015 00:38

          «Нормальный программист» = «который знает наизусть все виды GC».
          Ок )


          1. Zelgadis
            05.09.2015 01:10

            Нормальная программист знает как находить определения тех или иных терминов.


            1. divan0
              05.09.2015 01:16

              Ок.


    1. dmbreaker
      01.09.2015 22:24

      А как в Java победили StopTheWorld?


      1. xhumanoid
        01.09.2015 22:43
        +3

        в общем виде никак, по крайней мере в oracle jdk
        1) pauseless gc в azule, то habrahabr.ru/post/148322 пачка магии с защитой страниц памяти от чтения, исправление указателей во время выполнения и остальная магия
        2) проект Shenandoah (который пилит RedHat, но в 9ку он точно не войдет), то там использовали Brooks forwarding pointer (JEP 189). в нете находится несколько докладов от разработчиков.

        базовые вещи в виде CMS коллектора уже давно есть, в 8ке сделали параллельную initialmark, что значительно ускорило данную фазу.
        также g1 имеется, но там тоже есть нюансы в виде stw на эвакуации и разрастания rememberset таблиц, но он уже дефолтом будет в jkd9.


      1. leventov
        01.09.2015 23:46

        В том-то и дело, что в Java вроде как все сильно хуже, какие там «10 миллисекунд (а в среднем — микросекунды)», про которые говорят в связи с Go, в Java секунды в порядке вещей. Поэтому возникает вопрос

        как именно особенности Go-рантайма позволяют написать более быстрый сборщик мусора


        (версию о том что Java просто пишут люди тупее, чем те, кто пишут Go, я не особо рассматриваю).


        1. xhumanoid
          02.09.2015 00:30

          было бы желание, а 10ms для многих задач и в java достижимы, особенно если ставить условиями:
          1) вы отдаете 25% ресурсных мощностей под gc
          2) вы отдаете под gc удвоенный хип

          golang.org/s/go14gc

          небольшая цитата
          The goal of the Go 1.5 (June 2015) Garbage Collector (GC) is to reduce GC latency, making Go acceptable for implementing a broad spectrum of systems requiring low response times. Quantitatively this means that for adequately provisioned machines limiting GC latency to less than 10 milliseconds (10ms), with mutator (Go application code) availability of more than 40 ms out of every 50 ms. Hardware provisioning should allow for in-memory heap sizes twice as large as reachable memory and 25% of CPU cycles, typically one out of 4 hardware threads, available for GC tasks. These goals align with a future with ever-increasing numbers of hardware threads and an ever-increasing amount of memory, all within an ever-decreasing power and expense budget.

          Tactically, we will use a hybrid stop the world (STW) / concurrent garbage collector (CGC). The STW piece will limit the amount of time goroutines are stopped to less than 10 milliseconds out of every 50 milliseconds. If the GC completes a cycle in this time frame, great. If not, the GC will transition into a concurrent GC for the remainder of the 50 millisecond block. This process will repeat until the GC cycle completes. As a practical matter if one has a 50 millisecond response quality of service (QOS) requirement one should expect to have 40 milliseconds in which to do mutator tasks. These numbers assume hardware equivalent to a generic $1000 desktop box running Linux.


          1. M0sTH8
            02.09.2015 00:37
            +2

            1) 25 процентов только на время сборки, во всё остальное время все 100% ваши
            2) Размером хипа вы можете управлять сами. Для большинства сборщиков идеален размер в 2.2 от активного хипа.


            1. xhumanoid
              02.09.2015 11:58
              +1

              что значит «на время сборки», которая в некоторых приложениях может быть перманентной?

              отлично, открываем слайд 15:
              1) нарисовано, что stw у нас 1 и 3 ms и там все стоит
              2) между этими моментами у нас 25% это GC, 20% приложение, остальное… 55% assist. WTF??? почему про это нигде не сказано? ведь обещали 25% gc и остальное приложению.
              3) красиво нарисовано расстояние между сборками, там можно хоть один столбик оставить и сказать что мы не мусорим, но какое поведение будет если столбики эти будут идти один за одним, что легко случается при активном создании-удалении объектов? приложение получит 20% ресурсов???

              я понимаю, что управлять приходиться самому, просто «размер в 2.2 от активного хипа» когда у тебя хип на 1-2GB это нормально, но когда у тебя он на 64GB и ты чтобы не просесть используешь только половину, то это немного странно (да это один из пунктов критиков azul jvm, он требует удвоенного хипа).

              p.s. я внимательно читаю и слайды и отдельные доклады и по go и по другим языкам, так как хочется следить за направлением развитий gc особенно для больших хипов, но пока в go я вижу стандартные маркетинговые заявления не подкрепленные ничем (был один глобальный сборщик STW и перешли на CMS и сразу вброс про то что мы победили паузы, на практике лишь сделать очевидный для всех небольшой шажок в правильном направлении)


  1. xhumanoid
    01.09.2015 18:07
    +4

    >> достиг цели уменьшить верхнюю планку пауз до 10мс

    то есть 10мс это не STW, а просто постоим покурим?

    наезды на java о том, что для работы с разными потоками ничего кроме локов не имеется тоже безосновательны, акка тут в помощь

    >> Этот подход намеренно так сильно несоответствует большинству современных сборщиков мусора «энтерпрайз»-уровня

    то есть CMS в jvm несуществует? там и STW на initialmark фазе и фаза remark которая проходит по вновь созданным объектам и тд

    >> В трехцветном сборщике мусора, каждый объект может быть помечен, как белый, серый или чёрный, и мы рассматриваем кучу (heap) как граф связанных объектов. В начале каждого цикла GC все объекты белые. GC проходит всё корневые узлы (roots) графа, которые являются объектами, напрямую доступными программе — это глобальные переменные и переменные в стеке — и помечает их серыми. Затем GC выбирает серый объект, делает его чёрным, а затем сканирует его на наличие указателей и других объектов. Если скан обнаруживает указатель на белый объект, он делает его серым. Этот процесс повторяется, пока не останется серых объектов. В этот момент все белые объекты будут считаться недостижимыми и могут быть переиспользованы.

    docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/cms.html смотрим секцию Incremental Mode и пытаемся найти отличия

    если пихать везде write barrier, то и производительность можно просадить.

    примеры сборок с ультранизкими паузами можно посмотреть у azul и java Shenandoah

    поэтому резюмируя: ничего не понял как же они собираются достичь pauseless сборщика используя классический CMS

    p.s. доклад и pdf смотрел, но там лишь рассказы как мы с блокирующего режима перешли на конкурентную сборку и все


    1. divan0
      01.09.2015 18:29
      +1

      то есть 10мс это не STW, а просто постоим покурим?

      10ms это верхняя граница STW при критических нагрузках. На самом деле, при совсем пиковых нагрузках пауза таки может быть больше, но в 99.9% она будет ниже 10ms. Обычно это микросекунды, конечно.

      если пихать везде write barrier, то и производительность можно просадить.

      Уверен, Хадсону об этом не нужно рассказывать. scholar.google.com/citations?user=FejSLgQAAAAJ&hl=en

      поэтому резюмируя: ничего не понял как же они собираются достичь pauseless сборщика используя классический CMS

      Не видел в статье утверждений, что они пытаются достичь pauseless сборщика.


      1. xhumanoid
        01.09.2015 22:34
        +3

        >> В этом будущем нет места для пауз GC с «остановкой мира» (stop-the-world), которые были преградой для более широкого применения таких безопасных и надёжных языков, как Go.

        кроме как с pauseless этого достичь нельзя =) ну или как выше было сказано один раз не пи... 10ms не STW.

        >> но в 99.9% она будет ниже 10ms

        а тут все зависит от приложения, чем больше потоков/горутин, тем больше у тебя точек root, тем по большему объему памяти это все размазано, то есть все больше random access в память нужно делать, который значительно медленней линейного сканирования.

        >> Уверен, Хадсону об этом не нужно рассказывать.

        Я же не говорю, что сомневаюсь в компетенции, но на данный момент нигде нету технических деталей почему это не скажется на производительности, а если вы ещё посмотрите на слайды 17 и 18, то там уже видно, что хоть 1.5 и обладает более предсказуемой производительностью для json, но на малых объемах хипа он сливает по скорости 1.4, а для splay на любых объемах немного медленней.

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

        конечно удачи в разработке, но и заявлять о великой победе супер gc тоже не стоит ;)


        1. neolink
          01.09.2015 22:46

          write barriers на указатели добавили как раз в 1.4 (чтобы собрать фитбек как оно на реальных приложениях), разница в скорости скорее связана с тем что рантайм теперь тоже на go и он тоже под gc


          1. xhumanoid
            01.09.2015 22:59

            да, извиняюсь, действительно в 1.4 уже появились, как часть подготовки к конкурентному gc.


        1. M0sTH8
          02.09.2015 00:46
          +1

          Возможно вы просто не искали технические детали??

          Про pacing в 1.5 и как собираются добиться паузы в 10мс — docs.google.com/document/d/1wmjrocXIWTr1JxU-3EQBI6BK6KgtiFArkG47XK73xIQ/edit#heading=h.q556xotjblu6

          Как планируется улучшить в 1.6 docs.google.com/document/d/1kBx98ulj5V5M9Zdeamy7v6ofZXX3yPziAf0V27A64Mo/preview?sle=true


          1. xhumanoid
            02.09.2015 12:18

            я читал, но пока вижу вот это:

            1)
            github.com/golang/go/issues/11485
            On multi-gigabyte heaps, about half of our mark termination time (~5ms of ~10ms at 4GB) is spent in the loop over all spans in the _RootSpans case of markroot. We should fix this for 1.6.

            то есть только финализаторы на 4GB не считая всего остального уже могут вызвать больше 10ms в STW

            2) отсутсвует возможность compaction, следовательно привет фрагментированная куча, а для long running приложений эта проблема существует

            и еще несколько пунктов, но пока я не видел ни одного, которого уже не сделали в других VM, пилятся вещи обязательные для любого CMS который не хочет быть совсем уж тормозным, поэтому и хочется узнать великий секрет почему на хипе в 64GB у них не будет пауз больше 10ms


    1. miolini
      02.09.2015 01:59

      Azul и Shenandoah не мейнстрим. Сравнивайте, пожалуйста, jvm, которая бесплатно раздается.


      1. xhumanoid
        02.09.2015 12:10
        -1

        azul mainstream в своей нише, пускай и платный
        Shenandoah не мейнстрим, но бесплатный, качай-собирай-используй

        CMS в jvm vs CMS в GO и вторые заявляют, что у них сделано не как у всех, хотя по описанию у них отсутствуют даже многие необходимые вещи


  1. uvelichitel
    01.09.2015 23:28

    У Дмитрия Вьюкова помнится свои были идеи на предмет GC на уровне эскизов и pull request, а вот Ричард Хадсон… Его, Хадсона, вроде и не было раньше в core-team. Специально для GC что ли пригласили, guest star?


    1. M0sTH8
      02.09.2015 00:38
      +1

      Для работы над сборщиком мусора пригласили человека, который работает над сборщиками уже 20 лет. Вы находите это странным?


  1. ingrysty
    02.09.2015 01:06
    -1

    В расте вообще без GC можно писать программы, слишком тускло.