Распределитель блоков Орлова - это алгоритм, определяющий, где конкретный файл будет находиться в данной файловой системе (поблочно), чтобы ускорить операции с диском.
Этимология
Схема названа в честь ее создателя Григория Орлова, который впервые опубликовал в 2000 году краткое описание и реализацию для OpenBSD [1] техники, которая позже была использована в вариантах ядра BSD Fast Filesystem .
Задний план
Производительность файловой системы зависит от многих факторов; одним из решающих факторов является то, как файловая система размещает файлы на диске. В общем, лучше хранить связанные элементы вместе. Файловые системы Linux ext2 и ext3 , например, попытались распределить каталоги по цилиндрам диска. Представьте себе настройку системы с домашними каталогами пользователей в / home: если все каталоги первого уровня в / home (то есть домашние каталоги для множества пользователей) расположены рядом друг с другом, может не остаться места для содержимого эти каталоги. Таким образом, пользовательские файлы оказываются далеко от каталогов, в которых они содержатся, что снижает производительность.
Распространение каталогов на диске позволяет файлам в одном каталоге оставаться более или менее смежными по мере увеличения их количества и / или размера, но бывают ситуации, когда это вызывает чрезмерное распространение данных по поверхности диска.
Как это работает
По сути, алгоритм Орлова пытается распределить каталоги «верхнего уровня» в предположении, что каждый из них не связан с другими. Каталоги, созданные в корневом каталоге файловой системы, считаются каталогами верхнего уровня; Теодор Ц'о добавил специальный флаг inode, который позволяет системному администратору отмечать и другие каталоги как каталоги верхнего уровня. Если он находится /home
в корневой файловой системе, простая chattr
команда заставит систему рассматривать его как каталог верхнего уровня.
При создании каталога, который не находится в каталоге верхнего уровня, алгоритм Орлова пытается поместить его в ту же группу цилиндров, что и его родительский элемент. Однако требуется немного больше внимания, чтобы гарантировать, что содержимое каталога также сможет поместиться в эту группу цилиндров; если в группе не так много inodes или блоков, каталог будет помещен в другую группу цилиндров, в которой доступно больше ресурсов. Надеемся, что результатом всего этого станет гораздо лучшая локализация файлов, которые действительно связаны друг с другом и, вероятно, будут доступны вместе.
Представление
Было показано, что распределитель блоков Орлова обеспечивает повышение производительности для рабочих нагрузок, которые проходят через деревья каталогов [2] во FreeBSD. По состоянию на октябрь 2007 г.[Обновить], похоже, был опубликован только один результат теста [3] для ext3 с использованием распределителя. Результаты многообещающие: время, необходимое для обхода дерева ядра Linux, сократилось примерно на 30%.
Эволюция
Схема Орлова требует более тщательного тестирования; он также нуждается в серьезном стресс-тестировании, чтобы продемонстрировать, что производительность не снижается при изменении файловой системы с течением времени.
Рекомендации
- ↑ Григорий Орлов. «Алгоритм распределения каталогов для FFS» . Архивировано из оригинала на 2008-01-31.
- ^ Последние оптимизации файловой системы в FreeBSD
- ^ Берт Хьюберт, Наивный, но впечатляющий тест ext3 HTREE + Orlov
Внешние ссылки
- Распределитель блоков Орлова
- Распределитель блоков Орлова для электронной почты ext3 от Теодора Цо Линусу Торвальдсу и Александру Виро