The Go Blog

Getting to Go: The Journey of Go's Garbage Collector

Rick Hudson
12 July 2018

Это транскрипт ключевого выступления, которое было дано на Международной симпозиуме по управлению памятью (ISMM) 18 июня 2018 года. В течение последних 25 лет ISMM был главной площадкой для публикации статей по управлению памятью и сборке мусора, и было честью быть приглашённым выступить с ключевым докладом.

Аннотация

Особенности языка Go, его цели и сценарии использования заставили нас переосмыслить всю стек сборки мусора, что привело нас к неожиданному месту. Путь был захватывающим. В этом выступлении описывается наш путь. Это путешествие мотивировано открытым исходным кодом и требованиями Google в производственной среде. Включены отклонения в тупиковые каньоны, где нас вела числовая информация. Это выступление предоставит понимание того, как и почему мы начали этот путь, где мы находимся в 2018 году и как Go готовится к следующему этапу пути.

Биография

Ричард Л. Хадсон (Рик) наиболее известен своими работами в области управления памятью, включая изобретение алгоритмов Train, Sapphire и Mississippi Delta, а также GC stack maps, которые позволили реализовать сборку мусора в статически типизированных языках, таких как Modula-3, Java, C# и Go. Рик в настоящее время является членом команды Go в Google, где он работает над вопросами сборки мусора и среды выполнения.

Контакт: rlh@golang.org

Комментарии: См. обсуждение на golang-dev.

Транскрипт

Рик Хадсон здесь.

Это выступление о среде выполнения Go и, в частности, о сборщике мусора. У меня есть около 45 или 50 минут подготовленного материала, после чего будет время для обсуждения, и я останусь здесь, так что не стесняйтесь подходить после выступления.

Прежде чем начать, хочу поблагодарить некоторых людей.

Многое из хорошего в этом выступлении было сделано Оустином Клементсом. Другие люди из команды Go в Кембридже, Расс, Тан, Чери и Дэвид были увлекательной, захватывающей и веселой группой для работы.

Мы также хотим поблагодарить 1,6 миллиона пользователей Go по всему миру за то, что они дают нам интересные задачи для решения. Без них многие из этих проблем никогда бы не стали известны.

И, наконец, я хочу поблагодарить Рене Френч за все эти приятные Гоферы, которые она создавала на протяжении многих лет. Вы увидите несколько из них в этом выступлении.

Прежде чем мы начнем активную работу с этим материалом, нам действительно нужно показать, как выглядит представление о Go для сборщика мусора.

Первым делом, программы на Go содержат сотни тысяч стеков. Они управляются планировщиком Go и всегда прерываются в точках безопасного выполнения сборки мусора (GC safepoints). Планировщик Go мультиплексирует горутины на потоки операционной системы, которые, надеемся, работают по одному потоку ОС на аппаратный поток. Мы управляем стеками и их размерами путём копирования и обновления указателей в стеке. Это локальная операция, поэтому она масштабируется довольно хорошо.

Следующее важное обстоятельство заключается в том, что Go — это язык, ориентированный на значения, в традиции C-подобных системных языков, а не на ссылки, как большинство языков со средой выполнения. Например, здесь показано, как выглядит тип из пакета tar в памяти. Все поля встроены непосредственно в значение Reader. Это даёт программистам больше контроля над размещением памяти, когда это необходимо. Можно размещать поля с связанными значениями рядом, что улучшает локальность кэша.

Ориентация на значения также помогает с интерфейсами внешних функций. У нас есть быстрый FFI (Foreign Function Interface) с C и C++. Очевидно, что у Google имеется огромное количество различных систем, написанных на C++, но Go не мог ждать, чтобы переписать всё это на Go, поэтому Go должен был иметь доступ к этим системам через интерфейс внешних функций.

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

Конечно, у Go могут быть указатели, и даже внутренние указатели. Такие указатели делают всё значение живым и они довольно распространены.

У нас также есть система ahead-of-time компиляции, поэтому бинарный файл содержит всю среду выполнения.

Нет JIT-перекомпиляции. У этого есть свои плюсы и минусы. Во-первых, воспроизводимость выполнения программы намного проще, что делает развитие компилятора гораздо быстрее.

С другой стороны, мы не имеем возможности делать оптимизации на основе обратной связи, как это обычно делается в JIT-системах.

Таким образом, есть плюсы и минусы.

Go поставляется с двумя параметрами для управления сборкой мусора. Первый — GCPercent. По сути, это параметр, который регулирует, сколько CPU вы хотите использовать и сколько памяти. По умолчанию значение 100, что означает, что половина кучи выделена под живую память, а другая половина — под выделение. Можно изменять это значение в обе стороны.

MaxHeap, который пока ещё не выпущен, но уже используется и оценивается внутри компании, позволяет программисту задать максимальный размер кучи. Превышение доступной памяти (OOM) — это проблема для Go; временные пики использования памяти должны обрабатываться увеличением стоимости CPU, а не прерыванием выполнения. По сути, если GC замечает давление памяти, он уведомляет приложение, что оно должно снизить нагрузку. Как только всё вернётся к нормальному состоянию, GC уведомляет приложение, что можно вернуться к обычной нагрузке. MaxHeap также даёт гораздо больше гибкости при планировании. Вместо постоянного беспокойства о том, сколько памяти доступно, среда выполнения может увеличивать размер кучи до значения MaxHeap.

Это завершает наш разговор о важных частях языка Go, связанных с垃圾收集器ом.

Итак, теперь давайте поговорим о среде выполнения Go и о том, как мы дошли до текущего состояния.

Итак, 2014 год. Если Go не решит проблему задержки GC каким-либо образом, то Go не будет успешным. Это было очевидно.

Другие новые языки сталкивались с той же проблемой. Языки, такие как Rust, пошли другим путем, но мы поговорим о пути, который выбрал Go.

Почему задержка так важна?

Математика здесь совершенно жестока.

Целевой уровень обслуживания (SLO) по изолированной задержке GC на перцентиле 99%, например, 99% времени цикл GC занимает менее 10 мс, просто не масштабируется. Важно — задержка в течение всего сеанса или в процессе использования приложения много раз в день. Предположим, что сеанс, при котором пользователь просматривает несколько веб-страниц, в результате совершает 100 серверных запросов в течение сеанса или совершает 20 запросов, и у вас есть 5 сеансов, упакованных в течение дня. В такой ситуации только 37% пользователей будут иметь последовательный опыт с задержкой менее 10 мс на протяжении всего сеанса.

Если вы хотите, чтобы 99% этих пользователей имели опыт с задержкой менее 10 мс, как мы предлагаем, математика говорит, что вам действительно нужно стремиться к 4 девяткам или перцентилю 99.99%.

Итак, 2014 год, и Джфф Дин только что опубликовал свою статью под названием «The Tail at Scale», которая углубляется в эту тему. Она была широко прочитана в Google, поскольку имела серьезные последствия для Google в будущем и попыток масштабирования на масштабах Google.

Мы называем эту проблему тиранией девяток.

Итак, как бороться с тиранией девяток?

В 2014 году было предпринято множество действий.

Если вы хотите 10 ответов, запросите несколько больше и возьмите первые 10, и это будут ответы, которые вы поместите на страницу поиска. Если запрос превышает 50-й перцентиль, повторно отправьте или перенаправьте запрос на другой сервер. Если GC вот-вот начнётся, отклоните новые запросы или перенаправьте запросы на другой сервер до завершения GC. И так далее и тому подобное.

Все эти решения пришли от очень умных людей с очень реальными проблемами, но они не решали корневую проблему задержки GC. На масштабах Google мы должны были решить корневую проблему. Почему?

Избыточность не будет масштабироваться, она стоит дорого. Она требует новых серверных ферм.

Мы надеялись решить эту проблему и рассматривали это как возможность улучшить экосистему серверов и, в процессе, спасти некоторые исчезающие кукурузные поля и дать семени кукурузы шанс стать колосом к четвёртому июля и достичь своего полного потенциала.

Итак, вот 2014 SLO. Да, было правдой, что я преуменьшал свои возможности, я был новым участником команды, для меня был новый процесс, и я не хотел давать чрезмерные обещания.

Кроме того, презентации о времени отклика GC в других языках просто пугали.

Первоначальный план заключался в реализации concurrent copying GC без read barrier. Это был долгосрочный план. Было много неопределенности относительно накладных расходов, связанных с read barriers, поэтому Go хотел избежать их использования.

Но в краткосрочной перспективе 2014 года нам нужно было собраться и действовать. Нам нужно было переписать весь runtime и компилятор на Go. В то время они были написаны на C. Больше не C, больше не будет проблем, связанных с тем, что программисты на C не понимали GC, но им пришла в голову крутая идея о том, как копировать строки.

Также нам нужно было что-то быстро реализовать, сосредоточившись на низком времени отклика, но при этом накладные расходы не должны были превышать ускорение, обеспечиваемое компилятором. Таким образом, мы были ограничены. У нас было примерно год улучшений производительности компилятора, который мы могли использовать, чтобы компенсировать параллелизм GC.

Но больше ничего. Мы не могли замедлить программы на Go. Это было бы неприемлемо в 2014 году.

Поэтому мы немного отступили. Мы не собирались реализовывать часть, связанную с копированием.

Решение заключалось в использовании три-цветного алгоритма параллелизма. Ранее в ходе своей карьеры Элиот Мосс и я проводили доказательства журналов, показывавшие, что алгоритм Дейкстры работает с несколькими потоками приложения.

Мы также показали, что можно избавиться от проблем STW, и у нас были доказательства, что это возможно.

Мы также беспокоились о скорости компилятора, то есть о коде, который генерирует компилятор. Если мы оставим write barrier отключённым большую часть времени, оптимизации компилятора будут минимально затронуты, и команда компилятора сможет быстро продвигаться вперёд.

Go также срочно нуждался в краткосрочном успехе в 2015 году.

Так что давайте рассмотрим некоторые из того, что мы сделали.

Мы выбрали size segregated span. Проблемой были внутренние указатели.

Сборщику мусора нужно эффективно находить начало объекта. Если он знает размер объектов в span, он просто округляет вниз до этого размера, и это будет начало объекта.

Конечно, size segregated spans имеют и другие преимущества.

Низкая фрагментация: Опыт работы с C, кроме TCMalloc и Hoard от Google, я был тесно связан с работой Intel Scalable Malloc, и эта работа дала нам уверенность, что фрагментация не будет проблемой для non-moving allocator.

Внутренние структуры: Мы полностью понимали их и имели опыт работы с ними. Мы знали, как реализовать size segregated spans, мы понимали, как реализовать пути выделения с низкой или нулевой конкуренцией.

Скорость: Non-copy нас не беспокоил, выделение, конечно, могло быть медленнее, но всё ещё в пределах C. Возможно, оно не будет таким быстрым, как bump pointer, но это было нормально.

У нас также была проблема с foreign function interface. Если мы не перемещаем наши объекты, нам не нужно было иметь дело с длинным хвостом ошибок, которые можно было бы столкнуться при использовании moving collector, когда вы пытаетесь закрепить объекты и вставлять уровни косвенности между C и объектом Go, с которым вы работаете.

Следующий вопрос проектирования касался того, где размещать метаданные объектов. Нам требовалась какая-то информация о объектах, поскольку у нас не было заголовков. Биты пометок хранятся отдельно и используются как для пометок, так и для выделения памяти. Каждое слово имеет 2 связанных с ним бита, которые указывают, является ли оно скалярным значением или указателем внутри этого слова. Также эти биты кодируют, есть ли в объекте дополнительные указатели, чтобы мы могли прекратить сканирование объектов раньше, чем позднее. У нас также был дополнительный бит, который можно было использовать как дополнительный бит пометки или для других целей отладки. Это действительно было полезно для запуска системы и поиска ошибок.

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

Другой частью этого кода является GC Pacer (планировщик сборки мусора). Это одна из великолепных работ Аустинa. Он основан на обратной связи, которая определяет, когда лучше начать цикл сборки мусора. Если система находится в стабильном состоянии и не переживает фазовый переход, то процесс пометки завершится примерно тогда, когда закончится память.

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

В случае необходимости Pacer замедляет выделение памяти, но ускоряет пометку. В целом, Pacer останавливает горутину, которая выполняет большую часть выделения памяти, и заставляет её выполнять работу по пометке. Объём работы пропорционален объёму выделения памяти горутины. Это ускоряет сборщик мусора, но замедляет мутатор.

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

Он делает гораздо больше, чем это, но именно такой является базовая концепция.

Математика абсолютно захватывающая, напишите мне, чтобы получить документацию по дизайну. Если вы занимаетесь параллельной сборкой мусора, вы обязаны посмотреть эту математику и сравнить её со своей. Если у вас есть какие-либо предложения, пожалуйста, дайте нам знать.

*Go 1.5 concurrent garbage collector pacing и Proposal: Separate soft and hard heap size goal

Да, у нас были успехи, множество таких успехов. Молодой и безумный Рик, скорее всего, взял бы одну из этих диаграмм и татуировал её на моей плече, я был так горд этими результатами.

Это серия графиков, сделанных для сервера production в Twitter. Мы, конечно, ничего не имеем общего с этим production сервером. Брайан Хэтфилд провёл эти измерения, и любопытно, что он твитнул об этом.

На оси Y мы имеем задержку GC в миллисекундах. На оси X — время. Каждая точка — это время остановки мира (stop the world pause) в ходе сборки мусора.

В нашем первом релизе, который вышел в августе 2015 года, мы наблюдали падение с примерно 300–400 миллисекунд до 30 или 40 миллисекунд. Это было хорошо, порядок величины улучшился.

Мы собираемся радикально изменить ось Y здесь — от 0 до 400 миллисекунд до 0 до 50 миллисекунд.

Это через 6 месяцев. Улучшение было в основном вызвано систематическим удалением всех операций, зависящих от размера кучи (O(heap)), которые мы выполняли во время остановки мира. Это была наша вторая по величине корректировка — мы снизили задержку с 40 миллисекунд до 4 или 5.

В этом были некоторые ошибки, которые нам пришлось исправить, и мы сделали это в рамках минорного релиза 1.6.3. Это снизило задержку до менее 10 миллисекунд, что соответствовало нашему SLO.

Мы собираемся снова изменить ось Y, на этот раз до 0–5 миллисекунд.

Итак, мы здесь — август 2016 года, через год после первого релиза. Опять же, мы продолжали устранять процессы остановки мира, зависящие от размера кучи (O(heap size)). Речь идёт о куче размером 18 Гбайт. У нас были ещё более крупные кучи, и по мере того как мы устраняли эти остановки мира, зависящие от размера кучи, размер кучи мог значительно увеличиваться без влияния на задержку. Это немного помогло в версии 1.7.

Следующий релиз вышел в марте 2017 года. Это была последняя значительная корректировка задержки, которая была вызвана тем, как избежать сканирования стека во время остановки мира в конце цикла GC. Это привело нас в подмиллисекундный диапазон. Опять же, ось Y вот-вот изменится до 1.5 миллисекунды, и мы видим третью корректировку порядка величины.

Релиз августа 2017 года показал незначительное улучшение. Мы знаем, что вызывает оставшиеся паузы. SLO whisper number здесь около 100–200 микросекунд, и мы стремимся к этому. Если вы видите что-то более пары сотен микросекунд, то мы действительно хотим поговорить с вами и выяснить, вписывается ли это в уже известные нам явления, или же это что-то новое, что мы ещё не рассматривали. В любом случае, похоже, нет большой потребности в ещё более низкой задержке. Важно отметить, что такие уровни задержек могут возникать по множеству причин, не связанных с GC, и как говорится: «Вы не обязаны быть быстрее медведя, вам просто нужно быть быстрее человека рядом с вами».

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

Таким образом, новый год и новый SLO. Это наш SLO на 2018 год.

Мы снизили общее потребление CPU до уровня, используемого во время цикла сборки мусора (GC).

Куча по-прежнему составляет 2x.

Теперь наша цель — 500 микросекунд паузы "stop the world" на один цикл GC. Возможно, немного завышены ожидания.

Выделение памяти будет продолжать быть пропорциональным помощи GC.

Пасер (Pacer) стал намного лучше, поэтому мы посмотрели, какова минимальная помощь GC в стабильном состоянии.

Мы были довольны этим результатом. Опять же, это не SLA, а SLO, то есть цель, а не соглашение, поскольку мы не можем контролировать такие вещи, как ОС.

Это хорошие новости. Теперь давайте перейдём к нашим неудачам. Это наши шрамы; они похожи на татуировки, и у всех они есть. В любом случае, они приносят более интересные истории, поэтому давайте рассмотрим некоторые из них.

Наша первая попытка заключалась в реализации так называемого сборщика, ориентированного на запросы, или ROC (Request Oriented Collector). Гипотеза представлена здесь.

Что это значит?

Горутины — это легковесные потоки, которые выглядят как Гоферы, поэтому здесь у нас две горутины. Они разделяют некоторые данные, например, два синих объекта посередине. У них есть свои собственные приватные стеки и собственные наборы приватных объектов. Допустим, человек слева хочет поделиться зелёным объектом.

Горутина помещает его в общую область, чтобы другая горутина могла получить к нему доступ. Она может привязать его к чему-то в общей куче или присвоить глобальной переменной, и другая горутина сможет увидеть его.

Наконец, горутина слева подходит к своей смерти, она почти умирает, грустно.

Как вы знаете, вы не можете унести свои объекты с собой при смерти. Вы не можете унести и свой стек. В этот момент стек пуст, а объекты стали недоступны, поэтому их можно просто освободить.

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

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

Тем не менее, впечатляет, у нас были довольно хорошие успехи.

Это концевой тест производительности RPC. Неправильно помеченная ось Y изменяется от 0 до 5 миллисекунд (чем меньше, тем лучше), в любом случае, такова его природа. Ось X в основном отражает балласт или размер базы данных в памяти.

Как видно из графика, если ROC включён и не происходит большого совместного использования, вещи действительно масштабируются довольно хорошо. Если ROC выключен, результаты были намного хуже.

Но этого было недостаточно, нам также нужно было убедиться, что ROC не замедляет другие части системы. В этот момент возникли серьёзные опасения по поводу нашего компилятора, и мы не могли замедлить его работу. К сожалению, компиляторы были именно теми программами, в которых ROC работал плохо. Мы наблюдали замедления на уровне 30, 40, 50% и даже больше, что было неприемлемо. Go гордится тем, насколько быстро работает его компилятор, поэтому мы не могли замедлить компилятор, особенно настолько.

Затем мы посмотрели на другие программы. Это наши тесты производительности. У нас есть корпус из 200 или 300 тестов, и именно те, которые разработчики компилятора выбрали как важные для работы и улучшения. GC-разработчики ничего не выбирали. Числа были равномерно плохими, и ROC не мог стать победителем.

Правда, мы масштабировались, но у нас была только 4-12 потоковая аппаратная система, поэтому мы не смогли преодолеть затраты на write barrier. Возможно, в будущем, когда у нас будет 128-ядерная система и Go будет использовать её, свойства масштабирования ROC могут стать преимуществом. Когда это произойдёт, мы можем вернуться и пересмотреть это, но на данный момент ROC была проигрышной стратегией.

Что же мы собирались делать дальше? Давайте попробуем генерационную GC. Это старый, но хороший метод. ROC не сработал, поэтому вернёмся к тем методам, с которыми мы имеем гораздо больше опыта.

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

Можно ли было это сделать? Да, но с генерационной GC, write barrier всегда включён. Когда цикл GC запущен, мы используем тот же write barrier, который используем сегодня, но когда GC выключен, мы используем быстрый write barrier GC, который буферизует указатели и затем сбрасывает буфер в таблицу карточек при переполнении.

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

Затем вы обновляете текущий указатель на следующий 0.

Вы продолжаете, пока в какой-то момент не настанет время выполнить сборку мусора поколений (generation GC). Вы заметите, что если в векторе пометок/выделений есть единица, то этот объект был жив во время последней сборки мусора, следовательно, он зрелый. Если же значение ноль и вы до него дошли, то знаете, что он молодой.

Итак, как осуществляется продвижение (promoting)? Если вы находите что-то, помеченное единицей, указывающее на что-то, помеченное нулём, то вы продвигаете ссылку, просто устанавливая ноль в единицу.

Необходимо выполнить транзитный обход (transitive walk), чтобы убедиться, что все достижимые объекты были продвинуты.

Когда все достижимые объекты были продвинуты, минорная сборка мусора завершается.

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

Как выглядела производительность? Для больших куч она была неплохой. Это были те бенчмарки, на которых GC должен был хорошо себя показывать. Всё было хорошо.

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

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

У нас также была анализатор утечек (escape analysis), который становился всё лучше и лучше. Помните о том, что мы обсуждали в контексте ориентации на значения? Вместо того чтобы передавать указатель в функцию, мы передавали саму значение. Поскольку мы передавали значение, анализатор утечек мог выполнять только внутренний (intraprocedural) анализ утечек, а не межпроцедурный (interprocedural).

Конечно, если указатель на локальный объект утекает, объект будет выделен на куче.

Не то чтобы гипотеза о поколениях не работала в Go, а просто молодые объекты живут и умирают на стеке. В результате, сборка мусора по поколениям оказывается гораздо менее эффективной, чем можно было бы ожидать в других управляемых средах выполнения.

Итак, силы, противодействующие барьеру записи, начали накапливаться. Сегодня наш компилятор намного лучше, чем в 2014 году. Анализ выхода за пределы (escape analysis) выявляет множество таких объектов и размещает их на стеке — объектов, с которыми помог бы генерационный сборщик. Мы начали создавать инструменты, чтобы помочь пользователям находить объекты, выходящие за пределы, и если это небольшое количество, они могут внести изменения в код и помочь компилятору размещать их на стеке.

Пользователи становятся более изобретательными в применении подходов, основанных на значениях, и количество указателей уменьшается. Массивы и карты содержат значения, а не указатели на структуры. Всё хорошо.

Но это не главная убедительная причина, по которой барьеры записи в Go сталкиваются с трудностями в будущем.

Рассмотрим эту диаграмму. Это просто аналитическая диаграмма затрат на пометку. Каждая линия представляет собой разное приложение, которое может иметь разные затраты на пометку. Допустим, ваши затраты на пометку составляют 20%, что довольно высокий уровень, но возможно. Красная линия — 10%, что всё ещё высокий уровень. Нижняя линия — 5%, что примерно соответствует текущим затратам барьера записи. Что произойдет, если вы удвоите размер кучи? Это точка справа. Суммарные затраты на фазу пометки значительно снижаются, поскольку циклы GC происходят реже. Затраты барьера записи остаются постоянными, поэтому рост размера кучи приведёт к тому, что затраты на пометку окажутся ниже затрат на барьер записи.

Вот более типичная стоимость барьера записи — 4%, и мы видим, что даже при такой стоимости можно снизить затраты на барьер пометки ниже стоимости барьера записи, просто увеличив размер кучи.

Истинная ценность генерационной сборки мусора заключается в том, что, при рассмотрении времени сборки мусора, затраты барьера записи игнорируются, поскольку они распределены между мутатором. Это большая выгода генерационной сборки мусора: она значительно уменьшает продолжительность STW-циклов полной сборки мусора, но не обязательно повышает пропускную способность. Go не имеет проблемы остановки мира (stop the world), поэтому ей пришлось более внимательно рассмотреть проблемы пропускной способности, и именно это мы и сделали.

Это много неудач, и с такими неудачами приходит еда и обед. Я обычно жалуюсь: «Ну почему бы не было так, если бы не барьер записи».

Тем временем Эустин только что провёл час в разговоре с некоторыми специалистами по GC в Google и сказал, что мы должны поговорить с ними и попытаться выяснить, как реализовать поддержку аппаратной сборки мусора, которая могла бы помочь. Затем я начал рассказывать войны о заполнении нулями строк кэша, перезапускаемых атомарных последовательностей и других вещах, которые не удавались, когда я работал в крупной компании по производству аппаратных средств. Конечно, мы добились некоторых результатов в чипе под названием Itanium, но не смогли внедрить их в более популярные чипы современности. Итак, мораль истории проста: используйте имеющееся оборудование.

В любом случае, это нас завело в разговор, а что насчёт чего-нибудь безумного?

А что если помечать карты без барьера записи? Оказывается, у Эустин есть такие файлы, и он записывает туда все свои безумные идеи, по какой-то причине он не рассказывает мне о них. Я думаю, это своего рода терапевтический процесс. Раньше я делал то же самое с Элиотом. Новые идеи легко разрушаются, и нужно защищать их и делать сильнее, прежде чем выпускать в мир. Ну, в любом случае, он вытаскивает эту идею.

Идея заключается в том, чтобы поддерживать хэш зрелых указателей в каждой карте. Если указатели записываются в карту, хэш изменится, и карта будет считаться помеченной. Это будет менять стоимость барьера записи на стоимость хэширования.

Но более важно то, что это аппаратно выровнено.

Современные архитектуры имеют инструкции AES (Advanced Encryption Standard). Одна из этих инструкций может выполнять хэширование на уровне шифрования, и при использовании такого хэширования, при соблюдении стандартных политик шифрования, нам не нужно беспокоиться о коллизиях. Таким образом, хэширование не будет стоить нам много, но нам нужно будет загрузить то, что мы собираемся хэшировать. К счастью, мы последовательно проходим по памяти, поэтому получаем отличную производительность памяти и кэша. Если у вас DIMM и вы обращаетесь к последовательным адресам, то это преимущество, потому что они будут быстрее, чем обращение к случайным адресам. Префетчеры аппаратуры включатся, и это тоже поможет. В любом случае, у нас есть 50–60 лет проектирования аппаратуры для запуска Fortran, для запуска C и для запуска SPECint бенчмарков. Неудивительно, что результатом стала аппаратура, которая быстро выполняет подобные задачи.

Мы провели измерения. Это довольно хорошо. Это набор бенчмарков для больших куч, который должен быть хорош.

Затем мы спросили, как это выглядит для бенчмарка производительности? Не очень хорошо, несколько выбросов. Но теперь мы переместили барьер записи из постоянного включения в мутаторе в работу как части цикла GC. Теперь принятие решения о том, будет ли использоваться генерационная GC, откладывается до начала цикла GC. У нас теперь больше контроля, поскольку мы локализовали работу с картами. Теперь, когда у нас есть инструменты, мы можем передать управление Pacer, который сможет хорошо справляться с динамическим отсечением программ, которые попадают в правую сторону и не получают выгоды от генерационной GC. Но будет ли это работать в будущем? Нужно знать или, по крайней мере, подумать о том, как будет выглядеть будущая аппаратура.

Какие будут запоминающие устройства будущего?

Посмотрим на эту диаграмму. Это классическая диаграмма Закона Мура. На оси Y логарифмический масштаб показывает количество транзисторов на одном чипе. Ось X — это годы с 1971 по 2016. Замечу, что это годы, когда кто-то где-то предсказывал, что Закон Мура умер.

Масштабирование Dennard завершилось примерно десять лет назад. Улучшения частоты больше не происходят. Новые технологии производства затягиваются. Вместо двух лет теперь требуется четыре года или больше. Таким образом, довольно очевидно, что мы входим в эпоху замедления закона Мура.

Рассмотрим просто чипы в красном круге. Это чипы, которые лучше всего поддерживают закон Мура.

Это чипы, где логика всё больше упрощается и дублируется множество раз. Много одинаковых ядер, несколько контроллеров памяти и кэшей, графические процессоры (GPUs), TPU и так далее.

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

Другими словами, мы считаем, что удвоение объёма памяти будет более выгодным, чем удвоение ядер.

Оригинальная диаграмма на www.kurzweilai.net/ask-ray-the-future-of-moores-law.

Рассмотрим ещё одну диаграмму, сосредоточенную на DRAM. Эти данные взяты из недавней диссертации PhD из CMU. Если мы посмотрим на эту диаграмму, то увидим, что закон Мура — это синяя линия. Красная линия — это ёмкость, и она, похоже, следует за законом Мура. Странно, но я видел диаграмму, которая начинается с 1939 года, когда использовалась барабанная память, и ёмкость и закон Мура шли вместе, поэтому эта диаграмма существует уже давно, наверное, дольше, чем любой из присутствующих в этом зале.

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

Задержка, зелёная линия, растёт очень плохо, хотя я отмечу, что задержка для последовательного доступа лучше, чем для случайного доступа.

(Данные из «Understanding and Improving the Latency of DRAM-Based Memory Systems Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Electrical and Computer Engineering Kevin K. Chang M.S., Electrical & Computer Engineering, Carnegie Mellon University B.S., Electrical & Computer Engineering, Carnegie Mellon University Carnegie Mellon University Pittsburgh, PA May, 2017». См. диссертацию Кевина К. Чанга. Оригинальная диаграмма в введении не была в форме, удобной для построения линии закона Мура, поэтому я изменил ось X, чтобы она была более равномерной.)

Перейдем к тому месту, где теория встречается с практикой. Это реальные цены на DRAM, и они в целом снизились с 2005 по 2016 год. Я выбрал 2005 год, поскольку именно тогда закончилось явление Dennard scaling, а вместе с ним и улучшения частоты.

Если посмотреть на красный круг, который соответствует периоду наших усилий по снижению задержек сборщика мусора в Go, то видно, что в первые пару лет цены шли хорошо. Недавно же ситуация ухудшилась, так как спрос превысил предложение, что привело к росту цен за последние два года. Конечно, транзисторы не стали больше, а в некоторых случаях мощность чипов даже возросла, поэтому это вызвано рыночными силами. Производители памяти, такие как Rambus и другие, утверждают, что в будущем мы увидим следующее сокращение процесса в период 2019–2020 годов.

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

В долгосрочной перспективе мы считаем, что цены на память будут снижаться быстрее, чем цены на процессоры.

(Источники https://hblok.net/blog/ и https://hblok.net/storage_data/storage_memory_prices_2005-2017-12.png)

Рассмотрим еще одну линию. Хотелось бы быть на этой линии. Это линия SSD. Она лучше справляется с сохранением низких цен. Физика материалов этих чипов намного сложнее, чем у DRAM. Логика более сложная: вместо одного транзистора на ячейку имеется около полудюжины.

В будущем между DRAM и SSD будет существовать линия, где будет находиться NVRAM, такая как 3D XPoint от Intel и Phase Change Memory (PCM). В течение следующего десятилетия увеличение доступности этого типа памяти, вероятно, станет более массовым, и это только подтвердит идею о том, что добавление памяти — это дешевый способ повышения ценности наших серверов.

Более важно то, что можно ожидать появления других конкурирующих альтернатив DRAM. Я не буду притворяться, что знаю, какая из них будет предпочтительной через пять или десять лет, но конкуренция будет жесткой, и куча памяти будет приближаться к выделенной синей линии SSD.

Все это подтверждает наше решение избегать всегда включенных барьеров в пользу увеличения объема памяти.

Что это значит для Go в будущем?

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

Мы также не собираемся расширять API сборщика мусора. У нас уже почти десять лет, и у нас есть всего две настройки, и это кажется разумным. Нет приложения, которое было бы достаточно важным, чтобы мы добавили новый флаг.

Также мы планируем изучить, как улучшить уже довольно хорошую анализатор эскейпа и оптимизировать для программирования, ориентированного на значения в Go. Не только в самом языке программирования, но и в инструментах, которые мы предоставляем нашим пользователям.

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

Наконец, и самое главное, мы надеемся воспользоваться тенденцией закона Мура, согласно которому RAM имеет преимущество перед CPU, по крайней мере, в течение следующих 5 лет и, возможно, на протяжении следующего десятилетия.

Вот и всё. Спасибо.

P.S. Команда Go ищет инженеров для разработки и поддержки среды выполнения и инструментария компилятора Go.

Заинтересованы? Ознакомьтесь с нашими открытыми вакансиями.