Содержание

среда, 25 июля 2012 г.

Azul C4

Наконец-то появилась статья на русском как работает сборщик мусора Azul JVM, и за счет чего достигается полное отсутствие stop-the-world фаз. Полное официальное описание на английском доступно тут. Я же приведу краткое описание на русском, которое donjenya опубликовал в своей статье GC и большой heap: друзья или враги? на хабре.
По-настоящему полностью фоновый, одновременный сборщик мусора, использующий свой собственный алгоритм C4 (Continuously Concurrent Compacting Collector), эксплуатируемый в Azul JVM. С4 одновременно дефрагментирует оба поколения, молодое и старшее. В отличии от других алгоритмов, он не «в большинстве случаев одновременный», а действительно работает с потоками приложения всегда одновременно, т.е. stop-the-world не вызывается никогда. С4 использует Loaded Value Barrier (LVB) для проверки каждой ссылки, а каждая модифицированная ссылка отлавливается с помощью “self-healing” метода. С4 гарантирует, что все ссылки будут маркированы за один проход GC. Также гарантируется, что объекты будут перемещены, а ссылки на них модифицированы одновременно с работой приложения, не препятствуя его работе и не вызывая «stop-the-world»
Две основные причины, приводящие к возникновению "stop-the-world" пауз. Это фрагментация области памяти со старшим поколением и маркировка живых объектов. Если мы не будем дефрагментировать память, то рано или поздно получим “Out of memory”, если дефрагментировать память одновременно с работой приложения, то получим неправильные данные. В случае же с маркировкой есть опасность удалить «живые» объекты из памяти, что потом приведет к сообщениям об их недоступности. 

Для разрешения этих проблем в алгоритме сборщика мусора Azul C4 используется аппаратная эмуляция так называемого «барьера на чтение» (read barrier). В Azul C4 он имеет название LVB (Load Value Barrier), и именно он помогает гарантировать работу сборщика мусора и приложения в параллельном режиме.

Azul C4 также использует два поколения – молодое и старшее, память занимаемая этими поколениями, дефрагментируются одновременно с выполнением приложения. На рисунке ниже представлены основные этапы очистки мусора. Всего их три – Mark, Relocate, Remap. Хотелось бы заметить, что Remap и Mark могут выполняться в одно и то же время. Что же происходить на каждом этапе?

Azul C4 также использует два поколения – молодое и старшее, память занимаемая этими поколениями, дефрагментируются одновременно с выполнением приложения. На рисунке ниже представлены основные этапы очистки мусора. Всего их три – Mark, Relocate, Remap. Хотелось бы заметить, что Remap и Mark могут выполняться в одно и то же время. Что же происходить на каждом этапе?



Mark


На этом этапе происходит маркировка всех объектов, достижимых из корневых объектов, в памяти. Такие объекты помечаются, как «живые», все прочие подразумеваются, как «мертвые» и могут быть очищены. Он проходит одновременно с работой приложения и не вызывает «stop-the-world» паузу. В целом, он похож на стадию «concurrent mark» для CMS, но имеет несколько важных отличий. Во-первых, в дополнение к маркировке, Azul C4 также подсчитывает количество «живых» объектов в каждой странице памяти. Эта информация используется в дальнейшем для выбора страниц для переноса и дефрагментации в памяти. Во-вторых, алгоритм Azul C4 отслеживает все ссылки «живых» объектов с помощью архитектурно зарезервированного бита NMT в 64-битных ссылках. Этот бит, NMT (Not Marked Through), предназначен для отметки ссылки, как "marked through" в случае, если GC «прошел» её или, в противном случае, “not marked through”. Таким образом, Azul C4 отмечает все достижимые объекты, как «живые», и также, все ссылки, которые он «прошел», как «marked through». Как только этап Mark начался, потоки приложения, пытающиеся «пройти» по ссылке с битом NMT, выставленным в «not marked through», будут перехвачены «барьером на чтение» LVB. Аппаратная эмуляция этого барьера знает о функции бита NMT и может гарантировать, что потоки приложения никогда не получат доступ к ссылке, отмеченной как «not marked through». Если какой-либо из потоков приложения попробует сделать это, то процессор вызовет прерывание(trap) GC. Прерывание обработает ситуацию, вызвавшую его, следующим образом: поместит ссылку в список GC, поставит бит NMT в положение «marked through» и проверит бит NMT для объекта, откуда была загружена ссылка на правильность (должен иметь состояние “marked through”). После того, как прерывание будет обработано, работа потоков приложения возобновится. Использование этого механизма позволяет отметить все «живые» объекты за один проход, не вызывая повторную маркировку (как это делает CMS) и «stop-the-world» паузу. Также, устранение причины, вызвавшей прерывание, при обработке этого самого прерывания, оказывает эффект «самолечения», т.е. не позволяет этой же причине вызвать прерывание еще раз, что гарантирует конечный и предсказуемый объем работ по маркировке.

В целом, механизм прерываний позволяет проводить маркировку «живых» объектов за один проход, и при этом не вызывать «stop-the-world» паузу.

Relocate


На этом этапе GC освобождает память, занимаемую «мертвыми» объектами. При этом «живые» объекты он переносит в другую область памяти, тем самым дефрагментируя и уплотняя её. Для большей эффективности Azul C4 использует количество подсчитанных объектов на прошлом этапе (Mark) для того, чтобы первыми очистить страницы, в которых количество «мертвых» объектов сравнительно велико. Так как «живых» объектов в этих страницах мало, то их перенос занимает небольшой промежуток времени, в то же время, позволяя освобождать бОльшие объемы памяти в первую очередь, делая их доступными для приложения. Этап заканчивается, когда память, занимаемая «мертвые» объектами, будет полностью очищена. При этом «живые» объекты переносятся только из сильно фрагментированных страниц.



В начале этапа, используя механизм защиты памяти для того, чтобы ограничить доступ к определенным страницам памяти, сборщик мусора начинает перенос «живых» объектов в другие страницы памяти. Информация о начальном и новом адресе храниться в специальном массиве с «переадресацией указателей» (Forwarding Pointers), вынесенном отдельно от “From” пространства. Как только все «живые» объекты будут перенесены, физическая память становиться доступной для потоков приложения. LVB используется для определения попыток доступа потоков к страницам памяти, в которых происходит процесс переноса «живых» объектов или переопределения адресов для этого объекта. Он перехватывает обращения потоков и сравнивает значение ссылки с имеющимися у него ссылками в буфере Translation Look-aside Buffer (TLS). Если значение совпадает со ссылкой, для которой сейчас происходит процесс перемещения, то вызывается прерывание. Это прерывание выполняет следующие действия: при помощи информации, находящейся в массиве Forwarding Pointers, определяется, перемещен ли уже объект или нет. Если объект уже перемещен в новую страницу памяти, то потоку возвращается новая ссылка на объект, а также переопределяется адрес для ссылки на объект, из которого он был загружен, для того, чтобы в дальнейшем он использовал новую ссылку. В случае, если объект еще не перемещен, то прерывание перемещает этот объект, не ожидая пока сборщик мусора обработает страницу памяти, где этот объект находиться. После этого работа потока возобновляется. Использование того же эффекта «самолечения», что и на предыдущем этапе, дает возможность закончить этап перемещения в детерминированные сроки. Также, этап перемещения может быть завершен принудительно, если сборщик мусора решит, что сейчас выполнить этап маркирования будет эффективнее, чем продолжать этап перемещения объектов в памяти.

При рассмотрении этого этапа можно сказать, что такое поведение алгоритма и механизм прерываний гарантирует, что потоки не будут ожидать момента, пока сборщик мусора закончит работу с перемещением и переопределением адресов, тем самым позволяя сборщику мусора работать действительно одновременно с потоками и не вызывать «stop-the-world» паузу.

Remap


Этот этап завершает переопределение адресов для всех перемещенных объектных ссылок и гарантирует отсутствие ссылок на старое расположение в heap-е для перемещенных объектов. Эти ссылки могут существовать в начале этапа переопределения, так как heap может содержать ссылки на объекты, которые не посещались потоками после их перемещения. Когда этап переопределения адресов завершается, механизм защиты памяти отключается, а массив Forwarding Pointers становиться больше не нужен. Переопределение адресов выполняется следующим образом: сканируются все «живые» объекты в heap-e и переопределяются для них ссылки, если они указывают на объекты, перемещенные в новые страницы памяти. Этот этап совпадает с этапом маркировки, они выполняются одновременно, т.е. процесс маркировки находит живые объекты и помечает их, а также выставляет бит NMT, как «marked through». В то же время, процесс переназначения адресов находит ссылки на перемещенные объекты и переопределяет их соответственно новым адресам. На протяжении всего времени выполнения процессов маркировки и переопределения адресов механизм «барьера на чтение» продолжает «отлавливать» потоки приложения, обращающиеся к перенесенным объектам, вызывая прерывание, возвращающее потоку новый адрес расположения объекта.

Таким образом, Azul C4 может проводить одновременную маркировку, а также переопределение адресов, не вызывая «stop-the-world» паузу.

Подводя итог теоретическому описанию алгоритма Azul C4 можно сказать, что он действительно позволяет работать приложению одновременно со сборщиком мусора. Механизм LVB несколько понижает общую пропускную способность JVM, но стабилизирует время отклика на минимальном уровне, исключая паузы «stop-the-world» полностью. Для компаний, специализирующихся на предоставлении услуг через Интернет и приложений, где время отклика критично для бизнеса, Azul C4 выглядит наиболее привлекательной JVM.

Несмотря на всё это, теория должна подтверждаться практикой. В жизни Azul JVM поставляется как в виде «железки», так и в виде виртуальной машины. Аппаратная платформа Azul Vega 3 уже хорошо себя зарекомендована в финансовых компаниях. Виртуальная реализация Azul JVM приобретает всё большую популярность в мире, отчасти из-за того, что её можно развернуть на любом x86 железе, отчасти из-за того, что задачи, ставящиеся перед Java-приложениями, становятся серьезнее. Кстати, Azul C4 является не единственным преимуществом в Azul JVM, есть еще несколько отличий, выгодно отличающих Azul от конкурентов. Подробное описание этих достоинств займет столько же место, сколько занимает эта статья – поэтому лучше их оставить для отдельной статьи, где можно рассмотреть Azul JVM в общем виде. Если по названиям – то это DirectPathVMTM, Optimistic Thread Concurrency, мониторинг и профилирование выполнения приложений.