Кратко

  • Sprite LFS Менделя Розенблюма и Джона Оустерхаута превратила множество мелких случайных записей в крупные последовательные передачи, но старые версии всё равно пришлось освобождать позднее.
  • Показатель write cost включал чтение и повторную запись живых блоков очистителем, поэтому быстрая передняя операция не могла выдать себя за итоговую стоимость.
  • Последующие реализации очертили границу: при реальном простое очистку можно закончить в фоне, а при высокой заполненности, случайных обновлениях и малом запасе она начинает конкурировать с полезной нагрузкой.

Что остаётся после подтверждения

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

Именно этот разрыв делает работу Менделя Розенблюма и Джона К. Оустерхаута 1992 года по-прежнему полезной. Команда Sprite в Беркли не ограничилась тезисом о последовательном вводе-выводе. Она построила и эксплуатировала систему, которая буферизовала изменения файловых данных и метаданных, а затем записывала их крупными последовательными порциями. Набор синхронных случайных операций превращался в асинхронный поток.

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

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

Очиститель завершает отложенную работу

Очиститель читает сегменты-кандидаты, находит ещё живые блоки, компактно переписывает их и освобождает исходные сегменты. Segment summary сохраняет файл и логическую позицию каждого блока, чтобы сопоставить запись с текущими метаданными. Та же информация помогает продвигаться от контрольной точки при восстановлении.

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

Розенблюм и Оустерхаут выразили это через write cost. В знаменателе находятся новые полезные байты, а в числителе — весь дисковый трафик, нужный для их приёма, включая работу очистителя. Значение один соответствует идеалу, где движутся только новые данные. Значение десять оставляет для них примерно десятую часть сырой полосы. Так будущая работа возвращается в сегодняшнюю смету.

Выбор сегмента требует гипотезы о температуре данных. Жадная политика брала наименее заполненный сегмент, но при локальности показывала неожиданные слабости: холодные данные застревали в частично пустых сегментах, а горячие копировались незадолго до нового изменения. Cost-benefit policy сочетала заполненность с возрастом самого молодого блока, приблизительно (1-u) × age / (1+u).

Возраст был лишь заменителем стабильности. Он позволял очистить холодный сегмент при большей доле живых данных и подождать, пока горячий освободится сильнее. В описанном моделировании разделение снижало write cost до двух раз относительно жадного выбора. Но смена режима нагрузки способна превратить вчерашний холод в сегодняшнее повторное копирование.

Граница исходных измерений

Микротесты первой статьи не включали очистку. Они показывали лучший случай переднего пути, а не устойчивый режим. Более весомым доказательством стали четыре месяца эксплуатации. В исследованной среде Sprite write cost находился примерно между 1,2 и 1,6, а долговременная скорость записи достигала около 70% максимальной последовательной полосы.

Это сильный результат работающего кода, но не универсальная константа для любой заполненности, нагрузки и технологии. Авторы прямо отмечали ограниченность опыта. Восстановление имело отдельный баланс: checkpoint задавал известное состояние inode map, затем система шла вперёд по более поздним сегментам. Частые точки увеличивают обычную работу, редкие — объём после сбоя.

Быстрый ответ, завершённый checkpoint и ограниченное время восстановления — связанные, но разные свидетельства.

Проверка в BSD

Марго Зельцер, Кит Бостик, Маршалл Кирк Маккьюзик и Карл Стейлин реализовали LFS для BSD. Результат не подтвердил безусловного превосходства. Улучшенное группирование позволило традиционной системе вернуть часть разницы. Сильнее всего LFS выглядела на метаданных и множестве мелких файлов; на крупных файлах показатели были сопоставимы.

В сравнении 1995 года очиститель снизил производительность транзакций более чем на 33% уже при наполовину заполненном тестовом диске. Работа также упоминала прежние потери до 40%. Другое исследование эвристик выполнило 97% очистки самого загруженного изученного узла в фоне.

Эти результаты совместимы. «Фон» означает время оплаты, а не отсутствие долга. При настоящем простое работу можно закончить до конкуренции с пользователями. Если поток не прекращается, резерв падает, а паузы исчезают, то же копирование появляется в пользовательской задержке.

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

Поэтому вклад Оустерхаута нельзя свести к фразе «последовательная запись быстрее». Вместе с Розенблюмом и командой Sprite он помог создать простой передний механизм и учёт отложенной работы. Журнал доказывает приём версии. Резерв, очистка и восстановление доказывают способность продолжать.

Источники