12 октября 2026Команда Сарнас

Три слоя оптимизации памяти и производительности: аллокатор, структуры распределения и файловый ввод-вывод

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

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

Аллокатор TCMalloc: три компонента

TCMalloc делится на front-end, middle-end и back-end. Front-end обслуживает запрос, если у него есть кэш подходящего размера. Если кэш для нужного размера пуст, front-end запрашивает партию памяти у middle-end, чтобы пополнить кэш. Middle-end состоит из CentralFreeList и TransferCache. Если middle-end исчерпан или запрошенный размер больше максимального размера, который обрабатывает кэш front-end, запрос уходит в back-end, который также называют PageHeap.

Объекты, размер которых превышает максимальный размер, обрабатываемый кэшем front-end, выделяются напрямую из back-end и не кэшируются ни во front-end, ни в middle-end. При освобождении объект, размер которого не превышает этот предел, возвращается в кэш front-end, а более крупный объект возвращается напрямую в pageheap.

Per-thread кэш в legacy-режиме

В per-thread режиме каждый поток получает thread-local кэш. Кэш содержит по одному односвязному списку свободных объектов на каждый size-class. При выделении объект удаляется из нужного size-class, при освобождении — добавляется в начало списка. Недостаток (underflow) и переполнение (overflow) обрабатываются обращением к middle-end: либо добрать объекты, либо вернуть часть.

Максимальное число объектов, которое может храниться, увеличивается вплоть до предела всякий раз, когда нужно добрать больше объектов из middle-end, и уменьшается, когда в кэше накопилось слишком много объектов. Размер кэша также сокращается, если суммарный размер закэшированных объектов превышает лимит на поток.

Возврат объектов в central free list устроен так: каждый объект отображается на свой span через pagemap и освобождается в этот span. Если все объекты, принадлежащие некоторому span, возвращены, весь span возвращается в back-end.

Per-CPU режим и restartable sequences

В per-CPU режиме TCMalloc опирается на restartable sequence. Благодаря этому код может забрать или вернуть элемент в per-CPU массив без блокировок: последовательность гарантирует, что массив обновится без прерывания потока либо будет перезапущена. Это достигается без блокировок и атомарных инструкций, что позволяет избежать конкуренции внутри самой последовательности.

Объём кэша на CPU ограничивается параметром MallocExtension::SetMaxPerCpuCacheSize, поэтому суммарный кэш зависит от числа активных per-CPU кэшей, а машины с большим числом CPU могут кэшировать больше памяти. Внутри CPU распределение памяти по всем size-classes управляется так, чтобы максимальный объём кэша не превышал лимит. При исчерпании объектов в size-class ёмкость увеличивается, в том числе за счёт заимствования у другого size-class на том же CPU, пока общий возможный объём не достигнет per-cpu лимита или жёсткого лимита size-class.

Страницы, спаны и pageheap

При возврате в central free list каждый объект сопоставляется со своим спаном через pagemap и затем освобождается в этот спан. Если спан управляет мелкими объектами, размерный класс записан в самом спане. Pagemap реализован как 2- или 3-уровневое radix-дерево для отображения всех адресов памяти на спаны. Размеры страниц TCMalloc задаются при сборке и составляют 4KiB, 8KiB, 32KiB и 256KiB. Когда для размерного класса нет доступных объектов, нужно получить новый спан из pageheap и заполнить его.

Legacy pageheap управляет памятью блоками размером со страницу TCMalloc, а hugepage-aware pageheap — блоками размером с hugepage, что снижает промахи TLB и повышает производительность. hugepage отличается от страницы TCMalloc тем, что страница TCMalloc — это единица управления внутри аллокатора, а hugepage — единица управления памятью на уровне процессора и ядра. Legacy pageheap — это массив списков свободных участков: для k < 256 k-й элемент хранит участки из k страниц TCMalloc, а 256-й — участки длиной >= 256 страниц. При выделении k страниц сначала проверяется k-й список, затем следующие; при нехватке память запрашивается у системы через mmap, а остаток от большего участка возвращается в подходящий список.

У hugepage-aware бэкенда три кэша. filler cache обслуживает запросы меньше hugepage, запрашивая дополнительные hugepages при нехватке. region cache позволяет выделениям пересекать несколько hugepages и упаковывает несколько таких выделений в непрерывную область — это полезно, например, для 2.1 MiB. hugepage cache пересекается по использованию с region cache, который включается только если во время выполнения определено, что шаблон выделений выиграет от этого.

Авторы явно указывают оговорки. TCMalloc резервирует память под метаданные при старте, объём которых растёт с ростом кучи: pagemap растёт с виртуальным адресным диапазоном, spans — с числом активных страниц. В per-CPU режиме резервируется слэб на каждый CPU (обычно 256 KiB), что на системах с большим числом логических CPU может дать многомебибайтный след. TCMalloc запрашивает память у ОС крупными блоками (обычно регионы по 1 GiB): адресное пространство резервируется, но не подкрепляется физической памятью до использования, поэтому VSS может быть существенно больше RSS, и попытка ограничить потребление памяти через VSS потерпит неудачу задолго до реального использования физической памяти. Кроме того, не следует загружать TCMalloc в уже работающий бинарник (например, через JNI в Java): объекты, выделенные системным malloc, могут быть переданы TCMalloc для освобождения, а он не сможет их обработать.

Consistent hashing: математика распределения

При N=100 серверах ожидаемая доля диапазона каждого сервера равна 1%, а стандартное отклонение — примерно 0.99% от общего диапазона. коэффициент вариации CV = SD/Exp при m=1 равен примерно 99%. Это означает, что одни серверы будут работать примерно на 99% интенсивнее, чем должны, обрабатывая вдвое больше запросов, а другие могут почти ничего не делать.

Добавление хешей на константу (например, 160 точек на сервер) снижает CV с ~99% до ~8%, потому что суммирование нескольких случайных сегментов выравнивает итоговый размер диапазона. Но это лишь уменьшает погрешность, а не устраняет её полностью. Константное увеличение числа хешей задаёт минимальный запас погрешности, который проявляется у серверов с наименьшими весами, поэтому оно не заменяет взвешивание, при котором число хешей на сервер пропорционально его весу.

Consistent hashing: экономия памяти на структурах

Переход от структуры с полями hash: u32 и index: u32 к структуре с hash: u32 и index: u16 сам по себе не уменьшает занимаемую память, потому что Rust требует, чтобы размер структуры был кратен размеру самого большого по выравниванию поля. В исходной структуре hash занимает четыре байта, и именно он задаёт выравнивание, поэтому структура обязана иметь размер, кратный четырём байтам, а минимальный размер — восемь байт.

Чтобы реально получить шесть байт, авторы заменяют структуру на обёртку над массивом из шести байт и вручную извлекают hash и index через u32::from_ne_bytes и u16::from_ne_bytes. Это позволяет упаковать данные без выравнивания, и оба подхода — ручная сериализация и repr(packed) — компилируются в одно и то же. Экономия получается за счёт того, что вместо восьми байт на точку используется шесть, что и даёт суммарно около 25% сокращения памяти.

Consistent hashing: миграция без «расплавления» origins

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

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

Для этого PBR какое-то время держал в памяти обе версии кеширующего балансировщика — старое ketama-кольцо и новое меньшее, — и каждый запрос через обычный фреймворк миграции решал, какое кольцо выбирает бэкенд, что давало стабильное решение на запрос и чистый путь отката. Миграцию раскатывали слоями: начинали с небольших проверочных локаций, переходили к всё большим группам дата-центров и лишь затем к остальному миру, а по достижении 100% временный путь старого кольца удалили.

Линкер Wild: ввод-вывод и mmap

file_pool хранится в статической переменной FILE_POOL. Функция file_pool() возвращает копию этого списка, отсортированную по имени, потому что файлы открываются параллельно и порядок меняется от запуска к запуску.

При открытии файла решается, отображать его или копировать: если размер равен нулю — берётся пустой срез; если размер не больше READ_THRESHOLD (32 КиБ) и это обычный файл — содержимое читается в память и утекает, иначе файл отображается приватно через map_copy и флаг is_mmapped становится true. Отображённые файлы дополнительно складываются в MMAPPED_FILES (для drop_mappings) и, вне Windows, в MMAPPED_INODES вместе с парой (dev, ino) — именно по ней is_mmapped(path) проверяет, что путь указывает на уже отображённый входной файл.

drop_mappings забирает список MMAPPED_FILES и параллельно вызывает madvise с MADV_DONTNEED по всему диапазону каждого отображения, чтобы ядро быстрее освободило записи таблицы страниц при выходе; на Windows список просто игнорируется. На Windows путь никогда не считается уже отображённым, и в комментарии прямо сказано: «Output files are never written in place on Windows.», поэтому проверка на отображение в output_file.rs там никогда не срабатывает и повторное использование существующего файла не происходит.

Линкер Wild: тонкие архивы и --chroot

open_thin_member создаёт новый MappedFile для члена тонкого архива: он открывает файл по пути, копирует имя и данные, ставит given_fullpath: true, parent: None, thin_parent: Some(self) и is_dependency: AtomicBool::new(true). Байты такого члена хранятся в его собственном поле data, полученном из открытого внешнего файла, а не в родительском архиве.

offset() для члена с parent вычисляется как разность указателей data и parent.data плюс parent.offset(), а при отсутствии parent возвращает 0; для тонкого члена parent равен None, поэтому offset() даёт 0. identifier() при наличии parent формирует имя как имя родителя плюс ':' плюс offset, при наличии thin_parent — имя родителя плюс ':' плюс собственное имя, иначе возвращает собственное имя. set_dependency сохраняет переданное значение в AtomicBool is_dependency через store(Ordering::Relaxed), а is_dependency читает его через load(Ordering::Relaxed).

open_file применяет apply_chroot к пути и вызывает MappedFile::open, а must_open_file делает то же через MappedFile::open_impl и при ошибке завершает процесс. apply_chroot для абсолютного пути при непустом chroot возвращает chroot.join(clean_path(path).strip_prefix("/").unwrap_or(path)), иначе возвращает путь без изменений.

Линкер Wild: запись выходного файла

set_tmpfile регистрирует путь временного файла, который cleanup() удаляет при фатальной ошибке: на не-Windows он сохраняет C-строку в статический AtomicPtr, а на Windows — в Mutex<Option<PathBuf>>. set_output_buffer_range публикует диапазон адресов буфера вывода через два AtomicUsize (сначала обнуляя конец, затем записывая начало и конец), чтобы output_buffer_contains мог проверять принадлежность адреса буферу. publish_output_buffer вызывает set_output_buffer_range с адресом и длиной mmap-отображения, если хранилище — Storage::File с Some(map), иначе публикует (0, 0).

preallocate на Linux/Android через fstatfs проверяет, что файловая система не tmpfs, и только тогда вызывает fallocate для ускорения последующих проходов линковки; на tmpfs fallocate не вызывается, так как там он сильно замедляет работу. map_file при нулевой длине ничего не отображает, иначе отображает файл на память: на не-Windows сначала пытается отобразить вдвое больше адресного пространства, чем размер файла, чтобы extend() мог вырастить файл в отображение на месте, при неудаче — обычное отображение, затем вызывает madvise_hugepage. buffer_len проверяет, что size помещается в isize (иначе завершает процесс с сообщением «output file is too large for this host»), и возвращает size как usize — то есть размер буфера равен запрошенному размеру файла.

open_locked открывает файл для записи на месте (in place), а не через rename: он берёт эксклюзивную блокировку flock, сразу пишет 256 нулевых байт, чтобы файл нельзя было случайно использовать, и хранит Storage::File с map: None и len: 0; размер задаётся позже через resize, который делает ftruncate и mmap. extend увеличивает файл на заданный размер: для Storage::Memory расширяет вектор нулями, для Storage::File делает set_len, preallocate только для добавленного диапазона, и при необходимости пересоздаёт mapping, если новый размер не помещается в старый.

close снимает mapping и удерживает файл (и блокировку) до публикации; для Storage::Memory с путём "-" пишет в stdout и закрывает STDOUT_FILENO, иначе пишет во временный файл и затем rename. umask() читает текущую маску процесса через libc::umask(0) и сразу восстанавливает её, а set_permissions применяет perm & !umask() к файлу. Mapping снимается в close именно потому, что close завершает запись и публикует результат, не дожидаясь, пока данные дойдут до диска.

Линкер Wild: файловая система и кэши

verify_unchanged у входного файла проверяет, что файл не изменился с момента открытия: сравнивается время модификации с сохранённым modification_time. release_memory — подсказка, что файл больше не будет читаться; у OsInputFile она освобождает память, занятую содержимым. invalidate у выходного файла сбрасывает OS-кэши, которые могли видеть частично записанный вывод: у OsOutputFile она срабатывает только если буфер — Mmap. Инвалидация нужна потому, что запись идёт через mmap-буфер, и после частичной записи кэши могли наблюдать неполные данные; сброс кэшей гарантирует, что дальнейшее чтение увидит актуальное содержимое.

При открытии выходного файла, если возникает ошибка ETXTBSY (ErrorKind::ExecutableFileBusy) и разрешён откат к замене файла, выполняется unlink_and_recreate: сначала remove_file, затем OpenOptions с create_new(true). Retry выполняется в порядке: сначала попытка open с read/write/create; при ETXTBSY и разрешённом fallback вызывается unlink_and_recreate; затем, если файл имеет несколько ссылок, файл закрывается и снова вызывается unlink_and_recreate.

advise_huge_pages_if_requested вызывает advise_huge_pages только если requested=true; для BTRFS при kernel_version < 7.2 или None по умолчанию write_mode = BufferThenWrite и madvise_huge_pages = false, что отключает huge pages и использует буферизацию в памяти вместо mmap.

Линкер Wild: параллельная обработка входных данных

Открытие, mmap и определение типа файлов выполняются параллельно: после формирования TemporaryState с inputs_by_path, next_file_load_index, files и inputs_arena запускается rayon::scope, в котором initial_work.into_par_iter().for_each вызывает temporary_state.process_and_record_open_file_request(request, scope). Затем файлы упорядочиваются по FileLoadIndex: создаётся files_by_index, куда по file.index.0 кладётся file.state, после чего вызывается self.extract_all(&mut files_by_index, plugin).

Извлечение идёт в порядке исходной командной строки: extract_all перебирает i от 0 до files.len() и вызывает extract_file(FileLoadIndex(i), ...). Для LinkerScript extract_file сначала добавляет сам скрипт в loaded.linker_scripts, а затем рекурсивно извлекает файлы скрипта по loaded_linker_script_state.file_indexes, поэтому файлы линкер-скрипта появляются в позиции скрипта, хотя их FileLoadIndex больше.

load_input под мьютексом inputs_by_path проверяет paths.absolute: при Occupied обновляет info.as_needed &= input.modifiers.as_needed и возвращает info.index, при Vacant выделяет new_index через next_file_load_index.fetch_add(1, Ordering::Relaxed), вставляет InputLoadInfo и порождает задачу в scope. process_input по kind решает, что делать: для compiler IR возвращает InputRecord::LtoInput, для archive entry вне P::is_allowed_in_archive выдаёт ошибку, иначе создаёт InputBytes и ParsedInputObject, а для динамического объекта без allow_shared — ошибку.

Линкер Wild: layout и релаксация

Обход графа ссылок выполняет traverse_reference_graph: она запускается из compute параллельно с merge_strings и выполняет сборку мусора неиспользуемого, если он включён; даже когда GC выключен, обход всё равно выполняется, поскольку во время этой фазы считаются размеры. Обход идёт параллельно по группам: queue_initial_group_processing создаёт worker-слоты и для каждой группы вызывает activate_group, а GroupState::do_pending_work в цикле забирает work_item из локальной очереди и вызывает file.do_work, пока очередь не опустеет.

relaxation scan — это relaxation_scan_pass, который для каждой группы и каждого объектного файла сканирует секции, собирает дельты релаксации, уменьшает размер секции и накапливает кандидатов на повторное сканирование. Максимальное число итераций задано константой MAX_RELAXATION_ITERATIONS: usize = 5, при этом в комментарии сказано, что на практике сходимость наступает за 2–3 прохода. Момент сходимости определяется по результату прохода: relaxation_scan_pass возвращает суммарное число удалённых байт и RescanCandidates, а RescanCandidates затем фильтруется по total_deleted, чтобы получить RescanSections для следующей итерации; если новых удалений и кандидатов нет, повторное сканирование прекращается.

Линкер Wild: зависимости размеров

finalise_sizes (в контексте MergedStrings) проходит по всем merged-секциям и для непустых выделяет место с выравниванием alignment::MIN и размером merged.len(). apply_late_size_adjustments — это место, где определяются размеры, зависящие от других размеров; он сначала вызывает determine_header_sizes, затем P::apply_late_size_adjustments_prelude, затем allocate_symbol_table_sizes, а все дополнительные размеры накапливает в extra_sizes, который в конце сливается в common.mem_sizes и total_sizes.

determine_header_sizes решает, какие секции оставить: изначально берёт must_keep_sections, добавляет секции с ненулевым размером из total_sizes, добавляет секции, которые P::apply_force_keep_sections требует сохранить, и секции, у которых есть referenced start/stop символ. Затем он переносит флаг keep с secondary-секций на primary через merge_target, убирает встроенные секции без типа кроме FILE_HEADER (кастомным назначает тип по умолчанию), считает num_sections, при необходимости включает SYMTAB_SHNDX, вычисляет output_section_indexes по output_order и определяет keep_segments для программных сегментов.

allocate_symbol_table_sizes при should_strip_all сразу возвращает Ok, иначе вызывает self.internal_symbols.allocate_symbol_table_sizes с предикатом: символ пропускается при пустом имени, сохраняется при наличии resolution, при SymbolPlacement::ForceUndefined, либо если его секция будет эмититься (в partial-link режиме — через will_emit_section_symbol_for_partial_objects, иначе will_emit_section); сохраняемые символы помечаются флагом ValueFlags::DIRECT. Для partial objects дополнительно инкрементируется размер SYMTAB_LOCAL_SECTION_ID на num_section_syms * entry_size, где entry_size = size_of::<P::SymtabEntry>().

Линкер Wild: ELF writer и relocation

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

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

Для байтовых и битовых релокаций достаточно модифицировать не более восьми байт: для байтовых размер записи равен заданному размеру в байтах, а для битовых берётся размер 64-битного слова. Отдельное ограничение в десять байт применяется только к парным ULEB128-релокациям.

Линкер Wild: проверка диапазонов релокаций

Функция debug_relocation_shard_ranges_parallel делит диапазон релокаций на шарды; если шардов получается меньше двух, разбиение не выполняется. Тест preflight_splits_sorted_non_overlapping_relocations подаёт отсортированные смещения и размер записи 4, ожидая разбиение на диапазоны вида relocations: 0..2, output: 0..8. Тест preflight_rejects_unsorted_or_overlapping_ranges проверяет, что для неотсортированных или перекрывающихся наборов смещений разбиение не выполняется, а также что пересечение границы шарда (размер 8 у элемента с индексом 1 при границе 16) его отменяет. Тест preflight_falls_back_when_relocation_size_cannot_be_decoded подаёт write_size_at, всегда возвращающий Err, и ожидает отказа от разбиения. Размер записи вычисляется в debug_relocation_write_size: для PairSubtractionULEB128RiscV и PairSubtractionULEB128LoongArch возвращается MAX_DEBUG_RELOCATION_WRITE_SIZE, для ByteSize — usize::from(size), для BitMasking — size_of::<u64>().

Как сравнивали и что получилось

Замеры Mold проводились на двух машинах: 64-ядерном (128 потоков) Threadripper под Ubuntu 24.04 и Apple M1 Ultra (16 производительных ядер) под Asahi Linux; замеры Wild — на 16-ядерном (32 потока) Ryzen 9955hx под Ubuntu 26.04. Воспроизведение результатов выполнялось на 16-ядерном Apple M1 с релизными сборками обоих линкеров по состоянию на 2026-08-28, при этом выходной файл размещался на ext4, удалялся между запусками и передавался флаг --no-fork. Использовались программы blender-debug, godot-debug, blender-release и clang-release; для последующего сравнения версий применялся clang-release с собственной релизной сборкой clang и флагом --discard-section=.sframe для mold. Конфигурации различались по файловой системе и поведению с выходным файлом: ext4+delete+no-fork, ext4+no-delete+no-fork, tmpfs+delete+no-fork, tmpfs+no-delete+no-fork и tmpfs+no-delete+fork. Упомянуты объёмы ОЗУ: 92GiB RAM у 16-ядерного Ryzen 9955hx и 384GiB у 64-ядерного Threadripper.

В сводной таблице Mold benchmark для blender-debug указано 1.2x, для godot-debug 1.3x, для blender-release 0.8x, для clang-release 1.0x; в столбце This benchmark те же бенчмарки дают 1.2x, 1.2x, 0.9x и 1.0x соответственно. Точные времена в секундах приведены отдельно.

Бенчмарк	Wild (Mold benchmark)	Mold (Mold benchmark)	Отношение
blender-debug	1.81	1.56	1.2x
godot-debug	0.81	0.62	1.3x
blender-release	0.20	0.25	0.8x
clang-release	0.15	0.14	1.0x

Бенчмарк	Wild (This benchmark)	Mold (This benchmark)	Отношение
blender-debug	2.23	1.79	1.2x
godot-debug	1.11	0.89	1.2x
blender-release	0.30	0.33	0.9x
clang-release	0.21	0.20	1.0x

Для clang-release в разных конфигурациях: ext4-delete-no-fork 0.21 и 0.20 (1.0x), ext4-no-delete-no-fork 0.14 и 0.20 (0.7x), tmpfs-delete-no-fork 0.16 и 0.20 (0.8x), tmpfs-no-delete-no-fork 0.14 и 0.19 (0.7x), tmpfs-no-delete-fork 0.11 и 0.19 (0.6x).

Замеры Wild от 4 августа отличаются потому, что они были сделаны до релизов Mold 2.42.0 и 2.42.1, в которых Mold стал существенно быстрее. Кроме того, конфигурации замеров различались: бенчмарки Mold удаляют выходной файл между запусками линкера и используют ext4, тогда как Wild исторически запускался на tmpfs без удаления файла; также Mold передаёт --no-fork, а Wild по умолчанию форкается при замере времени. Автор объясняет разницу тем, что Wild не хватает OS-специфичных оптимизаций для быстрого создания и записи нового файла на не-tmpfs файловых системах. Эти изменения — использование fallocate для предварительного выделения места и hugepages для отображения файла — уже внесены в Wild и войдут в следующий релиз. Автор оговаривает, что не смог воспроизвести результаты на Threadripper, и предполагает, что большая разница может быть связана с тем, что Wild работает со 128 потоками, а Mold — с 32, но называет это догадкой. Также он отмечает, что для clang-release использовал собственную сборку clang, поскольку Wild 0.6.0 не поддерживал смешивание argument-фай