Этот материал давно просился на бумагу, однако, изложить его подтолкнули диалоги о фрагментации файлов с Д. Карповым (http://www.mi2.ru/prof). С другой стороны, статью можно рассматривать и как продолжение более ранних публикаций о файловых системах (см. статьи рубрики в июньском и июльском номерах 1999-го и в ноябрьском номере 2000 года).

Ясно, что вопрос фрагментации файлов является частью более общей темы о производительности. Именно о производительности дисковой подсистемы мы в этот раз и поговорим.

Корабль пустыни

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

Чем интересна такая тема, как производительность системы? Очень часто «здравый» смысл может не сработать. В, казалось бы, одинаковых конфигурациях одно и то же изменение в настройках может привести к падению производительности на одном и к повышению — на другом компьютере. В этом плане мираж — наиболее точная аналогия. Во-первых, иногда очень сложно понять, что лучше. Хороший пример попался мне в одной статье несколько лет назад. Группе пользователей предложили поработать на нескольких компьютерах и выбрать (опираясь, заметим, на субъективные «измерения») самый быстрый. Потом для сравнения провели объективные измерения. Оказалось, например, что, «брэндовость» дает прирост «производительности» по сравнению с реальной более 10%. Во-вторых, очень сложно иногда найти первопричину бед с производительностью. В-третьих, иногда трудно представить корректные шаги по настройке.

Снова в пустыне

Позволю себе повториться и напомню еще раз простой факт. В Unix обычно имеются устройства для работы с дисками двух типов. Одно из этих устройств (обычно в /dev/rdsk) называют символьным (иначе его называют raw device, «сырым» устройством), а другое (/dev/dsk...) — блочным. Чем они отличаются? Файловая система работает через блочное устройство. Это основной режим работы для файловой системы, хотя для специальных целей иногда используется и «непрогретый» вариант. Вне зависимости от того, используется ли устройство (раздел, секция, том) для файловой системы или находится в свободном плавании, система использует для работы с ним буферный кэш. Для работы с сырым устройством кэш не используется (или почти не используется, тут есть кое-какие нюансы; например, прежде чем данные попадут на носитель, буфер из процесса обычно переписывается в буфер ядра). Зачем нужен буферный кэш? Как и у любого другого кэша, его основная задача состоит в уменьшении числа обращений к более медленному носителю. Например, выполнение команды наподобие

dd if=/etc/passwd bs=1 of=/tmp/ogo 

потребовало бы массы повторных обращений к диску за каждым байтом в том случае, если бы блоки /etc/passwd не попали в буферный кэш. Еще «приятнее» была бы ситуация с операцией записи, так как, формально говоря, система должна прочесть блок из записываемого файла, вставить в него байт и вернуть модифицированный блок. В принципе, такая ситуация в некоторых диалектах Unix — при условии приложения определенных усилий со стороны администратора — достижима. Скорость, сами понимаете. Как ни странно, такой режим иногда полезен... для производительности. Вот так. Жизнь полна парадоксов.

Миражи

«Тривиальный» пример. В каком случае быстрее происходит копирование больших (превышающих размер оперативной памяти) порций данных:

  • копирование сырого устройства на сырое;
  • копирование блочного устройства на блочное?

Что говорит «здравый» смысл? Для работы с блочным устройством используется буферный кэш, кэш используется для ускорения операций, если операции ускоряются, то копирование должно быть быстрее. Пробубнили? Однако обычно это как раз не так.

Буферный кэш помогает «в среднем». Иногда он бывает даже чрезмерно активен. Однажды, например, выпросив у Solaris 24 байта с диска (эконом, однако), я обнаружил, что та «тащит» с носителя в буферный кэш за одну операцию более 100 Кбайт. Конечно, это обеспечило бы мои потребности надолго... Однако чтение было не последовательным и перемещать более 8 Кбайт разом попыток больше не было.

Что происходит с данными в кэше? Они там лежат. Долго лежат. Ждут своего звездного часа, когда они смогут сэкономить нам операцию-другую с диском. Для этого надо лежать достаточно долго (иногда десятки секунд). В графике заполненность кэша выглядит как гряда терриконов с массовыми сбросами, вызванными операциями sync. В каком случае буферный кэш действительно может помочь? Возможны варианты:

  • частое обращение к конкретному блоку;
  • возможность отложить запись и выполнить ее в более удобное время или в более удобном порядке («после-запись» write-behind);
  • возможность выполнения операций чтения заранее («пред-чтение» read-ahead).

В случае массовых операций переброса данных с размером буфера, существенно превышающим размер блока, нам может помочь только предварительное чтение, а в остальном... оптимизация будет мешать. У нас нет ни малейшего повода задерживать данные в буфере записи или чтения, раз мы не будем обращаться к ним снова. Аналогия с memcpy (смотри сентябрьский прошлого года выпуск рубрики) полная. Тот порядок, который формируется в самом процессе перезаписи, и будет оптимален. Различия в скорости зависят от конкретного варианта Unix, иногда они составляют десятки процентов, иногда разы. Конечно, сказывается и выбранный размер буфера. Например, из вышеприведенного замечания о Solaris ясно, что желательный размер буфера должен быть порядка 100 Кбайт. При увеличении буфера скорость работы с сырым устройством увеличивается до некоторого предела почти линейно, а с блочным почти не меняется. Если отбросить запись, то, вполне возможно, чтение с блочного устройства будет даже слегка опережать чтение с сырого; таким образом, основную проблему создает запись.

Еще один пример миража. Предположим, что программа хаотически пишет в файл, ну, абсолютно хаотически выбирает в файле блок и переписывает его. Пишет поблочно, например, 1 Гбайт (опять же главное, чтобы было относительно много по сравнению с размером памяти). В таком режиме можно, в принципе, писать и на блочное устройство, и на сырое, и даже в файл. Не обязательно даже в заполненный (этих самых гигабайтных размеров), можно писать и в пустой файл. Он, конечно, будет немного походить на дуршлаг или сито, но никто не запрещает нам это делать (см. «Мелочи жизни» за апрель 1999 года). В каком из названных случаев (запись на сырое устройство, блочное или заполненный/пустой файл) процесс будет быстрее? Пока вы изучаете горизонты собственного «здравого» смысла, посмотрим на диск подробнее.

Крутится, вертится

Что такое диск? Набор «блинов» (у каждого из них две поверхности), на которых по окружностям треков-дорожек записана информация. Каждый из треков представляет собой набор блоков-секторов. Все треки, которые можно прочитать без перемещения головки (т.е. дорожки всех блинов), составляют цилиндр. Что нужно проделать для того, чтобы записать или прочитать информацию в/из конкретного блока? Нужно переместить весь блок головок к позиции требуемого цилиндра, выбрать головку и, дождавшись чудного мгновения прохода нужного блока над головкой, прочитать или записать его. Производители дисков ради упрощения жизни пользователей скрывают эти детали за счет использования той или иной схемы адресации блоков. Что такое диск для системы? Набор логических блоков и не более. Не более? Диск перестал быть диском, его завязали узлом? Отнюдь. Если операционная система и другие программы не учитывают этого, то возможны неоправданные потери производительности.

Какая часть диска наиболее критична с точки зрения производительности? Естественно, головки. Механика... Это вам не банальное вращение с постоянной скоростью, тут приходится постоянно скакать то в одну, то в другую сторону и при этом попадать именно туда, куда нужно — перелет и недолет недопустимы. Типичные времена для «дальних» полетов — миллисекунды (6-10), ближние — их доли (0,8), среднее время ожидания блока (сектора) зависит от скорости вращения. Скажем, формула 5400RPM свидетельствует о том, что диск делает 90 оборотов в секунду, время оборота 11 мс, среднее время ожидания — 5,5 мс. А что будет происходить при достаточно хаотических запросах? Скорее всего, за один оборот мы будем прописывать/прочитывать один блок (обычно предпочитают минимум 1 Кбайт даже для секторов в 512 байт); поэтому даже без учета других эффектов скорость будет на уровне 90 Кбайт/с.

Чего стоит ожидать от хорошо буферизованного последовательного доступа? В этом случае мы могли бы потенциально читать/записывать целую дорожку за один оборот. Что получается? Предположим, скорость вращения шпинделя — 7200 оборотов в минуту, а на одной дорожке 100 секторов по 512 байт. Получаем, что в секунду можно забрать 7200/6051005512 = 6 Мбайт/с. Маловато. Что можно сделать для увеличения скорости? Основной путь здесь в увеличении количества секторов и, по возможности, в увеличении скорости вращения. Современные диски могут иметь порядка 400-800 секторов на дорожке. При тех же вводных это дает 24-48 Мбайт/с.

Можете сравнить этот результат с предыдущим и подумать о бренности всего живого. Заметим, что везде речь идет о реальных числах секторов на дорожке, количестве цилиндров и т.п., не надо сравнивать их с миражами, которые, например, создает BIOS. Согласитесь, 32 сектора на дорожку — перебор.

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

Часть читателей предпочитает примеры. Нет проблем. Попробуйте испытать следующую программу:

#include 
#include 
static int r=1;
/* Очень случайные числа */
#define next(X) ((((r*=625)
&0x0fffff)/
(double)0x100000)*X)

char buffer[4096];
void Usage(void)
{
	printf«Usage: stest mode 
bnum volume
»);
	exit(0);
}

main(int argc, char **argv)
{
	int id, bnum=1000000,
 size, mode=0,
 rblock, n;
	if(argc!=4)Usage();
	if((id = open(argv[3],
O_RDONLY))<0)
 {perror(argv[4]);exit(1);}
	sscanf(argv[1],»%i»,&mode);
	sscanf(argv[2],»%i»,&bnum);
	size = bnum;
	for(;size>0;size—){
n = next(bnum);
rblock = mode?n:(rblock+1);
if(lseek(id,rblock*4096,0)<0)
{perror(«lseek»);exit(1);}
		if(read(id,buffer,
4096)!=4096) 
{perror(«read»);exit(1);}
	}
	close(id);
}

Эта программа в зависимости от заданного режима (0 — последовательный, 1 — случайный) читает данные. Данные читаются порциями по 4 Кбайт, количество этих порций задается вторым параметром. Попробуйте предположить, какова будет скорость чтения этой программой «случайных» данных при скорости вращения 7200 оборотов в минуту на не слишком большом (пара-тройка размеров памяти) пространстве: не более 7200/6054Кб = 480 Кбайт/с. Разница с последовательным доступом — даже не разы (последовательный доступ обеспечивает, естественно, мегабайты в секунду, а если еще увеличить буфер...).

Именно отсюда проистекает желание дефрагментации файлов. Если все лежит очаровательно подряд, то, очевидно, скорость будет выше. Ура дефрагментации!

Другой пример может быть интересен для представления эффектов разбиения данных на разделы. Попробуйте испытать следующий скрипт (предположим, его имя shtest):

dd if=/dev/hda9 skip=$1 bs=4k
 count=20000 of=/dev/null &
dd if=/dev/hda9 bs=4k count=20000
 of=/dev/null &
wait

запустим:

time shtest 20000

Значение count и носитель вы можете выбрать по вкусу (если два последовательных старта при одинаковом параметре дают существенную разницу по времени, то count мал, и буфер все берет на себя). Единственный параметр, который хотелось бы иметь больше 20 тыс., обеспечивает отсутствие пересечения между областями работы dd. Заметим, что мы dd запускаем одинаково с «&», это существенно, так как shell любит менять значение nice, а нам хотелось бы стартовать программы с одинаковым приоритетом. Что мы получим? Даже в рамках одного раздела разница может исчисляться процентами. Если же второе вхождение hda9 заменить на что-то другое (типа hda2 и т.п.), а параметр сбросить в ноль (итак гарантируется не пересечение), то различие может составить десятки процентов. Ну а чего же вы ожидали? Деление на разделы та же самая фрагментация, что и в файловой системе, только фрагментируется не файловая система, а диск в целом. Вся разница только в явном запрещении перехода через границу. Можно, конечно, сказать, что я передергиваю, что в жизни так не бывает, но это неправда, в данном примере ОС еще может оптимизировать работу (все очень последовательно), а в общей-то ситуации, когда программы менее тривиальны? Впрочем, нельзя не отметить, что с уменьшением среднего времени доступа, которое почти равно среднему времени ожидания, эффекты все более смазываются.

Есть и другой эффект. Особенно он сказывается на дисках с малыми форм-факторами. Внешние дорожки (нулевые) существенно больше внутренних. При приблизительно одинаковой допустимой плотности записи просто невозможно разместить на внешних и внутренних дорожках одинаковый объем информации. Соответственно, на внутренних дорожках приходится уменьшать количество секторов и в результате возникает эффект уменьшения скорости работы диска. Размеры дисков уменьшаются, разница растет. Лет пять назад соотношение было порядка 1,3 (в результате для некоторых видов приложений, требующих гарантированной потоковой производительности, «диск заканчивался посредине»), сейчас же у некоторых производителей соотношение бывает порядка 1,7.

Археологические раскопки

Как были ранее устроены файловые системы в Unix? Приблизительная картинка может быть следующей:

блоки для загрузки
суперблок
иноды
каталоги
данные файлов
свободное место

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

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

Что плохого в этой схеме? Все великолепно дефрагментировано. Управляющая информация в одном месте, каталоги в другом, файлы в третьем. Вот именно этим и было плохо. По любому поводу головка должна была бежать в самое начало диска. Что было сделано для того, чтобы файловая система стала FFS или HPFS? Была сделана фрагментация данных. Все пространство было поделено на одинаковые группы цилиндров (и эти группы для оптимизации по возможности создавали совпадающими именно с физическими цилиндрами), каждая из которых содержала все для работы: свою таблицу описателей файлов inode, свою схему управления свободного пространства. При этом, как правило, файл лежит в той же группе, что и каталог, в котором он упомянут. Ясно, что это удается не всегда, но система старается. В результате операции класса grep, компиляция и т.п. выполняются в рамках одной группы, минимум перемещений головок. Более того, специально для того чтобы большие файлы не нарушали идиллию группы, можно ограничить выделение места под один файл в рамках одной группы, т.е. потребовать от системы фрагментировать его. Да здравствует фрагментация?

Еще примеры: попробуйте вызвать команду debugfs /dev/hda... и в ответ на приглашение выдать stat. Результат может оказаться сродни следующему:

debugfs:  Filesystem is read-only
Volume name = (none)
...
Last mount time = Tue Mar
 13 14:27:09 2001
Last write time = Tue Mar
 13 14:27:14 2001
Mount counts = 6 (maximal = 20)
Filesystem OS type = Linux
Superblock size = 1024
Block size = 4096,
 fragment size = 4096
Inode size = 128
263296 inodes, 196714 free
526120 blocks, 299261 free, 
26306 reserved, first block = 0
32768 blocks per group
32768 fragments per group
15488 inodes per group
17 groups (1 descriptors block)
 Group  0: block bitmap at 2, 
inode bitmap at 3, 
inode table at 4
14553 free blocks, 
11564 free inodes, 
232 used directories
...
0 free blocks, 
12430 free inodes, 
348 used directories
debugfs:  debugfs:

Как видите, ext2 тоже пользует группы. Под тем или иным названием группы блоков можно найти во многих файловых системах. Да, потеряна связь с физическими цилиндрами, однако принцип локальности остался.

Конечно, кричать «Ура фрагментации» рано. Просто мы оторвались от тривиального понимания дефрагментации файлов и перешли к «дефрагментации процессов». Нам стало мало того, что, открыв конкретный файл, мы можем его шустро прочитать. Нашей целью стала оптимизация процессов, которые работают с группами файлов (например, с файлами каталогами) в целом. И с этой точки зрения фрагментация может быть благом. Например, оказывается, выгодно размазать свободное пространство по всему носителю (это не означает, что оно должно быть сильно фрагментировано в рамках группы), просто потому, что тогда всегда найдется место именно там, где нужно проделать изменения.

Что же тогда должна делать дефрагментация? Ее роль становится несколько более локальной, что не исключает переноса данных между группами. Важно, чтобы в каждой группе все было достаточно пристойно. Соответственно в работу входит:

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

Оазис

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

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

Ну и, наконец, на последнем месте будет запись на сырое устройство.

Вот такая вот обидная ситуация. Нет в мире совершенства. Если одно хорошо, так другое просто из рук вон.

Тысяча и одна сказка

Следует ли из всего сказанного выше, что данные лучше хранить в одной большой файловой системе? Нет. Есть тысяча и один повод разделить их. Вот только некоторые из них: лучшая управляемость системы; повышение надежности; обеспечение требований загрузки системы; обеспечение безопасности; повышение производительности конкретных приложений или системы в целом.

Впрочем, это уже совершенно иная тема. Главное же — помнить, что процессом оптимизации можно заниматься вечно. Так что, погоняя верблюда, не забывайте о своей Шахразаде.

Согласны ли вы с тем, что работающая программа лучше оптимизированной, или вам просто нужна сказка? Пишите по адресу oblakov@bigfoot.com

Поделитесь материалом с коллегами и друзьями