Envision VM (часть 3), Атомы и хранение данных

Victor Nicollet

Эта статья — третья из четырех частей серии, посвященной внутреннему устройству виртуальной машины Envision: программного обеспечения, выполняющего скрипты Envision. См. часть 1, часть 2 и часть 4. В этой серии не рассматривается компилятор Envision (возможно, в другой раз), поэтому будем считать, что скрипт каким-то образом был преобразован в байт-код, который принимает на вход виртуальная машина Envision.

Во время выполнения, thunks считывают входные данные и записывают выходные данные, часто в больших объемах.

• Миллиард булевых значений (по одному биту на значение) занимают 125МБ.
• Миллиард чисел с плавающей запятой (32-битная точность) занимают 4ГБ.
• Миллиард минимальных записей продаж (дата, местоположение, EAN-13, количество) занимают от 14ГБ до 33ГБ (или больше!), в зависимости от способа кодирования значений.

Это создает две задачи: как сохранить эти данные с момента их создания до момента использования (часть ответа — на NVMe-дисках, распределенных по нескольким машинам), и как минимизировать объем данных, проходящих через каналы, медленнее оперативной памяти (сеть и постоянное хранилище).

Слой метаданных

Одна из частей решения заключается в том, чтобы иметь два отдельных уровня данных, при этом данные помещаются в один из них в зависимости от своей природы. Слой метаданных содержит информацию о фактических данных и о выполняемых скриптах:

• Когда thunk успешно возвращает данные, уникальный идентификатор этих данных сохраняется в этом слое.
• Когда thunk завершился с ошибкой, сообщения об ошибках, сгенерированные им, сохраняются в этом слое.
• Когда thunk возвращает новый thunk (и DAG его родителей), сериализованный DAG сохраняется в этом слое.
• Thunk может сохранять контрольные точки в слое метаданных (обычно состоящие из идентификатора блока данных); если выполнение thunk прерывается до завершения, он может загрузить свою контрольную точку из слоя метаданных и возобновить работу с этой позиции.

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

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

Существуют два ограничения для значений, хранящихся в слое метаданных: одна запись не может превышать 10МБ (то есть сериализованный DAG также не должен превышать этот объем!), и общий объем памяти для слоя метаданных составляет 1,5ГБ. Обычно в этом слое хранится около одного миллиона значений при среднем размере записи в 1,5КБ.

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

Каждый воркер в кластере хранит свою копию слоя метаданных. Воркер транслирует каждое изменение этого слоя (вызванное выполнением локальных thunks) всем другим воркерам в кластере, а также диспетчеру. Это делается по принципу «все усилия»: если сообщение трансляции не достигает адресата, оно отбрасывается¹ без повторной попытки.

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

Хранение больших баз данных в памяти

Как уже упоминалось, слой метаданных может содержать миллион записей. Каждый отдельный DAG может содержать сотни тысяч узлов. Все они имеют длительный срок жизни — от минут до часов. Хранение миллионов объектов с долгим временем жизни в памяти сильно нагружает сборщик мусора .NET.

Сборка мусора в .NET — сложная тема (хотя существует отличная серия материалов от Конрада Кокосы, подробно рассказывающая о низкоуровневых деталях), но общая проблема сводится к совокупности трех факторов:

• Затраты на выполнение одного прохода сборки мусора пропорциональны количеству живых объектов в области памяти, подвергаемой очистке. Обработка миллионов объектов, зачастую содержащих миллиарды ссылок между ними, может занять сборщику мусора несколько секунд.
• Чтобы избежать этих затрат, сборщик мусора .NET работает с отдельными областями памяти, называемыми поколениями, в зависимости от возраста объектов в них. Самое молодое поколение, Gen0, подвергается сборке мусора часто, но содержит лишь объекты, выделенные с последнего прохода (то есть, всего несколько). Самое старое поколение, Gen2, очищается только в случае, если и Gen1, и Gen0 были очищены, но не освободили достаточно памяти. Это случается достаточно редко, если большинство объектов выделяются малыми и кратковременными.
• Однако обычная операция thunk включает большие массивы значений, которые выделяются в куче для больших объектов, являющейся отдельной областью от Gen0, Gen1 и Gen2. Когда куча для больших объектов заканчивается по объему, производится полная сборка мусора, которая также очищает Gen2.

Именно в Gen2 располагаются миллионы объектов из DAG и слоя метаданных.

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

Каждый DAG состоит всего из двух выделений памяти — массива узлов и массива ребер, оба из которых являются unmanaged значениями, так что сборщику мусора даже не требуется обходить их содержимое для поиска ссылок. Когда требуется выполнить thunk, он десериализуется из бинарного представления DAG², которое хранится в слое метаданных.

Слой метаданных имеет содержимое переменной длины, поэтому он создается путем вырезания фрагментов из большого массива byte[] с использованием ref struct и MemoryMarshal.Cast для манипуляции данными без их копирования.

Временное хранилище

Кластер располагает от 512GiB до 1.5TiB оперативной памяти и от 15.36TB до 46.08TB NVMe-хранилища. Большая часть этого пространства отведена для хранения промежуточных результатов выполнения thunks.

Оперативная память — ценная территория: она составляет лишь 3% от общего объема доступного хранилища, но чтение и запись осуществляется в 100×–1000× быстрее. Существенное преимущество заключается в том, чтобы данные, которые собирается прочитать thunk, уже находились в памяти (или никогда не покидали её).

Кроме того, практически невозможно использовать 100% от доступной оперативной памяти в .NET — операционная система имеет переменные потребности в памяти и не имеет надежного способа сообщить .NET-процессу, что ему следует освободить часть памяти, что приводит к завершению процесса из-за недостатка памяти (oom-killed).

Envision решает эту проблему, поручая управление передачей данных между ОЗУ и NVMe операционной системе. Мы открыли исходный код этой реализации как Lokad.ScratchSpace. Эта библиотека отображает в память всё доступное пространство NVMe-дисков и предоставляет его в виде хранилища blob’ов, которое приложение может использовать для:

1. записи блоков данных (до 2ГБ каждый) во временное хранилище, либо напрямую, либо посредством сериализации из управляемого объекта. Эта операция возвращает идентификатор блока.
2. чтения блоков данных по их идентификаторам. Эта операция закрепляет блок и предоставляет его приложению в виде ReadOnlySpan<byte>, который затем приложение должно скопировать (или десериализовать) в управляемую память.

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

Ключевым моментом при использовании отображаемого в память временного хранилища является то, что доступная оперативная память распределяется между тремя видами страниц³: память, принадлежащая процессам (например, .NET-процессу Envision), память, представляющая собой точную посимвольную копию части файла на диске, и память, предназначенная для записи в файл на диске.

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

Память, предназначенная для записи на диск, в конечном итоге будет записана и станет копией того участка, куда она была записана. Это преобразование ограничено скоростью записи NVMe-дисков (примерно 1ГБ/с).

Память, выделенная для процесса, не может быть преобразована обратно в эти два типа без освобождения самим процессом (что .NET GC иногда делает после того, как сборка освободила большое количество памяти). Вся память, выделенная через .NET, включая все управляемые объекты и всё, что отслеживается сборщиком мусора, должна относиться к этому типу памяти.

В типичном воркере 25% памяти выделяется непосредственно для .NET-процесса, 70% представляет собой копию участков файлов только для чтения, и 5% находится в процессе записи на диск.

Слой атомов

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

Название «Атом» было выбрано потому, что невозможно прочитать только часть атома: их можно получить лишь целиком. Если структура данных должна поддерживать выборку лишь части своего содержимого, мы сохраняем её в виде нескольких атомов, которые затем можно извлекать независимо.

Некоторые атомы сжаты; например, большинство булевых векторов не представлены в виде bool[], который потребляет по одному байту на элемент, а упакованы до 1 бита на значение, а затем сжаты для устранения длинных последовательностей одинаковых значений.

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

Когда атом исчезает, выполнение thunk, который его запрашивал, прерывается и переходит в режим восстановления:

1. Система проверяет наличие (но не контрольные суммы) всех остальных атомов, на которые ссылаются входные данные thunk. Это связано с тем, что атомы, как правило, генерируются одновременно и на одном воркере, и исчезновение одного атома коррелирует с исчезновением других атомов из того же времени и места.
2. Система тщательно проверяет слой метаданных на наличие ссылок на любые атомы, обнаруженные как отсутствующие на предыдущем шаге. Это приведет к тому, что некоторые thunks перейдут из состояния “выполнен” в состояние “ещё не выполнен”, поскольку их результат был отброшен. Затем ядро обнаружит это и повторно запланирует их выполнение.

Повторно выполненные thunks затем вновь создадут атом, и выполнение может продолжиться.

Массивы атомов

Особенностью слоя атомов является способ выполнения перемешивания — первый слой из $M$ thunks, каждый из которых генерирует несколько миллионов строк данных, затем второй слой из $N$ thunks считывает вывод предыдущего слоя для выполнения другой операции (обычно некой формы редукции), при этом каждая строка из первого слоя считывается только одним thunk из второго.

Было бы крайне неэффективно, если бы каждый thunk из второго слоя считывал все данные из первого (каждая строка читалась бы $N$ раз, из которых $N-1$ были бы избыточными), но именно это и произошло бы, если бы каждый thunk из первого слоя создавал ровно один атом.

С другой стороны, если каждый thunk в первом слое генерирует по одному атому для каждого thunk во втором слое, то операция перемешивания будет включать в себя всего $M\cdot N$ атомов — миллион атомов при $M = N = 1000$. Несмотря на то, что накладные расходы на атомы не чрезмерны — если сложить идентификатор атома, идентификатор арендатора, тип данных атома, размер и небольшие затраты на управление, они всё же могут достигать нескольких сотен байт на атом. Хотя 100МБ может показаться небольшой ценой за перемешивание 4ГБ фактических данных, эти данные находятся в слое атомов (который предназначен для работы с большими объёмами данных), в то время как 100МБ представляют значительную часть общего бюджета метаданных в 1,5ГБ.

Чтобы обойти эту проблему, Envision поддерживает массивы атомов:

• Все атомы в массиве атомов записываются одновременно и хранятся вместе как в памяти, так и на диске.
• Имея идентификатор массива атомов, легко определить идентификатор i-го атома в массиве.

Благодаря этому массив атомов имеет такие же накладные расходы, как и один атом. При перемешивании thunk-и первого слоя создадут $M$ массивов по $N$ атомов каждый. Thunk-и второго слоя для каждого запроса выберут по одному атому из каждого массива, в позиции, соответствующей рангу данного thunk-а в процессе перемешивания.

В заключение, несколько статистических данных из производственной эксплуатации! За один час типичный работник выполнит 150 000 thunk-ов и запишет 200 000 атомов (массивы атомов учитываются только один раз), что составляет 750GiB промежуточных данных.

В следующей и последней статье этой серии мы обсудим слои, которые обеспечивают выполнение распределённых вычислений.

Бесстыдная реклама: мы нанимаем инженеров-программистов. Возможна удалённая работа.