автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическое моделирование производительности файловых систем

На правах рукописи

НИЖНИК Екатерина Игоревна

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОИЗВОДИТЕЛЬНОСТИ ФАЙЛОВЫХ СИСТЕМ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2007

003159448

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)

Научный руководитель:

кандидат физико-математических наук ТОРМАСОВ Александр Геннадьевич

Официальные оппоненты:

доктор физико-математических наук, профессор ЛОБАНОВ Алексей Иванович

кандидат технических наук, ст н с ШИЛОВ Валерий Владимирович

Ведущая организация:

Институт автоматизации проектирования РАН

Защита состоится «О ¡С/У ¿Г 2007 года в ^^ часов на заседа-

Ъ&Л* .212

нии диссертационного совета К 212 156 02 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл , г Долгопрудный, Институтский пер , д 9, ауд 903 КПМ

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета)

Автореферат разослан » СМ^УУ&З^^ 2007 года

Ученый секретарь диссертационного совета К 212 156 02 кандидат физико-математических наук У^/

Федько О С

ОБЩЕЕ ОПИСАНИЕ РАБОТЫ Актуальность темы

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

Согласно проведенным исследованиям [Ramaknshnan et al, 1992, Smith, Seltzer, 1994, Kuenning et al, 1994, Roselli et al, 2000, и др ], оценку быстродействия файловых систем необходимо осуществлять в контексте нагрузок, генерируемых приложениями Под термином «нагрузка» обычно понимается способ обращения к данным, который использует та или иная программа Большинство существующих инструментов тестирования файловых систем имеет узкую специализацию, т е предназначено для оценки производительности при нагрузке, отражающей специфику конкретного приложения или класса приложений Кроме того, практически все эти инструменты предполагают непосредственное тестирование интересующих пользователя нагрузок Однако с точки зрения минимизации затрачиваемого времени и ресурсов (как программных, так и аппаратных) более важной является задача прогнозирования производительности Решение этой задачи позволило бы оценивать быстродействие той или иной файловой системы в условиях конкретной нагрузки без непосредственного тестирования при этой нагрузке и тем самым повысить эффективность проектирования вычислительных комплексов

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

Цель работы, объект и предмет исследования

Цель диссертационной работы - разработка методики математического моделирования производительности файловых систем

Задачи исследования

- Провести анализ типов нагрузок, а также существующих моделей оценки производительности файловых систем и систем хранения данных

- Разработать технологию создания математической модели прогнозирования производительности файловых систем

- Построить математическую модель прогнозирования производительности на примере широко распространенной файловой системы New Technology File System (NTFS)

- Выполнить практическую проверку работоспособности полученной модели

Объект исследования - компьютерные файловые системы

Предмет исследования - методы оценки производительности файловых систем

Методы исследования

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

Научная новизна

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

Практическая значимость

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

Предложенная технология моделирования производительности была применена при разработке и тестировании коммерческого программного комплекса Virtuozzo1 (Windows версия), являющегося мировым лидером в сфере виртуализации операционных систем

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

Публикации и апробация результатов работы

По теме диссертации опубликовано 11 работ, в том числе одна - в издании, рекомендованном ВАК РФ

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных семинарах и конференциях

- ХХХШ международная молодежная научная конференция «Гагаринские чтения» (Москва, 2007 г),

- 30-я конференция молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (Москва, 2007 г),

- XLVIII и XLIX научные конференции МФТИ (Москва, 2005-2006 гг),

- научные семинары кафедры информатики МФТИ

Структура и объем работы

Диссертация состоит из введения, трех глав, заключения и списка использованных источников, включающего 50 наименований

1 http //www swsoft com/products/virtuozzo/

Общий объем работы составляет 105 страниц машинописного текста, содержащего 10 таблиц и 46 рисунков

Положения, выносимые на защиту

На защиту выносятся следующие основные положения

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

2 Математическая модель прогнозирования производительности файловой системы NTFS при произвольных нагрузках, а также соответствующий комплекс программ для создания данной модели

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы, формулируется цель исследования и его основные задачи, а также приводится краткое содержание диссертации

В главе 1 содержится обзор публикаций по основным исследованиям, посвященным различным типам нагрузок Дается описание существующих инструментов для оценки производительности файловых систем (Andrew Benchmark, PostMark, Iozone, HBench-FS, SPEC SFS и др ), перечисляются их достоинства и недостатки

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

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

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

В главе 2 формулируется постановка основной задачи исследования, предлагается общая методика решения этой задачи, а также приводятся результаты применения методики для создания «высокоуровневой» математической модели прогнозирования производительности файловой системы ШТЭ при нагрузке, генерируемой ^^еЬ-сервером МБ ЕВ

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

Пусть х = (х1; ,хк) - вектор параметров нагрузки на файловую систему Ф, а Р - скалярная характеристика производительности Ф Необходимо найти зависимость Р = Р(х), поскольку, зная эту зависимость, пользователь сможет оценивать значение производительности Р в условиях произвольной нагрузки х' =(хр , х'к), даже не тестируя файловую систему Ф

Общая методика решения поставленной задачи может быть представлена в виде следующего алгоритма

1 Задать характеристику производительности Р

2 Основываясь на теоретических представлениях о внутренней архитектуре

файловой системы Ф и принципах работы дискового устройства, выдвинуть гипотезу касательно набора параметров нагрузки х,, i = l,k, влияющих на Р и, возможно, вида зависимости Р(х)

3 Провести ряд экспериментов по замеру значений Р при различных нагрузках xJ (j - номер эксперимента)

4 Построить экспериментальную зависимость Р(х) и аппроксимировать ее некоторым приближением с использованием известных математических методов

5 В случае если гипотеза не подтвердилась экспериментальными данными (не была достигнута требуемая точность модели), повторить шаги 1-5, взяв за основу другую гипотезу

Проверка разработанной методики выполнялась на примере New Technology File System (NTFS) v3 1 - широко распространенной файловой системы компании Microsoft Одним из наиболее показательных типов нагрузки является web-сервер Поэтому для создания нагрузки в экспериментах изначально использовался Microsoft Internet Information Server (MS IIS) v5 1 со статическим содержимым (имитировалась среда для просмотра пользователем гипертекстовых страниц в интернете)

1 Так как единственной характеристикой производительности web-сервера с точки зрения пользователя является скорость получения информации, в качестве характеристики производительности Р была выбрана скорость отправки потока данных клиенту Таким образом, исключаются возможные задержки при передаче одного запроса по сети, и оценивается производительность самого сервера

2 Согласно теории операционных систем, наиболее существенной оптимизацией, влияющей на производительность, является кэширование В работе показано, что соотношение количества оперативной памяти х0 в системе и объема запрашиваемой на web-cepeepe информации Х[ характеризует долю данных, считываемых непосредственно с диска (рис 1) Поскольку это может отразиться на производительности Р, х, следует считать параметром нагрузки при фик-

сированном х0 Далее, из общих соображений о работе файловой системы можно выделить параметр нагрузки х2 — средний размер файлов, запрашиваемых на сервере К примеру, практический опыт показывает, что большое количество маленьких файлов читается медленнее, чем малое количество больших файлов при одинаковом общем объеме данных Кроме того, на скорость доступа к содержимому web-сервера также может влиять число одновременно обращающихся к нему пользователей, поэтому в качестве третьего параметра нагрузки х3 было принято количество параллельных запросов к серверу

а) 5 КВЛ —►— Sand б) i кв,6

Dak Read

IxW 8x10' 6x10'

4x10' 2x10 О■

V

1x10' SxlO' 6x10' 4x10' 2x10' О

О

—*— Send * Dn,k Read

О

10 12

I, mm

Рис 1 Скорость отправки и чтения данных с диска (средняя за минуту) в зависимости от времени при объеме запрашиваемых данных а) в -10 раз меньшем объема RAM, б) сравнимом с объемом RAM2

3 Значения параметров нагрузки, используемые в экспериментах при генерировании запросов к web-cepeepy, приведены в таблице 1

Таб 1 Значения экспериментальных параметров нагрузки

Параметр Принимаемые значения Размерность

хо 512 МБ

Х1 1, 2, 3, 4, 5, 10, 20, 50, 80, 100, 150, 200, 250, 300, 350, 400,450, 500, 700, 1000, 1500, 2000, 2500, 3000 МБ

х2 1,8, 32, 128,512, 1024, 2048,4096, 5120,10240 КБ

хз 1,2,3,4, 5, 6,8 -

" RAM - Random Access Memory, оперативная память Кол-во RAM в данном эксперименте равнялось 1 ГБ

9

4 Пусть р,(Х)' ! = 1>3 - функция производительности от 1-го параметра нагрузки при фиксированных остальных На рис 2,3 и 4 представлены эмпирические зависимости р,(х,) и их линейные аппроксимации, выполненные по методу наименьших квадратов (МНК), для определенных интервалов нагрузки

В^-Р.Схда^тиЧ.О)

4500

1000 2000 Total data size [MB]

3000

Рис 2 Зависимость р,(х,) и ее линейные приближения, выполненные по МНК

2000 4000

Avaage fie sBe PCB]

Рис 3 Зависимость р2(х2) и ее линейные приближения, выполненные по МНК

где yJ - значение производительности в _)-м эксперименте, Р, е К2 -коэффициенты линейного приближения для х, Видно, что во всех случаях наблюдается определенный эффект насыщения, выраженный в том, что при увеличении параметра нагрузки производительность стремится к постоянному значению Полученные аппроксимации позволяют оценить коэффициенты модели Р, в заданных интервалах значений нагрузки Выбор тн критической точки, в которой одно приближение сменяется другим, обусловлен минимизацией суммы среднеквадратичных отклонений каждого из приближений

4 6 Parallel confections

Рис 4 Зависимость р3(х5) и ее линейные приближения, выполненные по МНК

f n N ^

\ H J=I1+1

где N - количество экспериментальных точек, р^ и Р" - коэффициенты каждого из приближений в зависимости от номера критической точки п 5 Дальнейшее исследование показало, что при изменении фиксированных параметров нагрузки в каждом случае коэффициенты модели р,, равно как и значения нагрузки в критической точке, не сохраняются Это означает, что зависимость производительности от выбранных параметров нельзя аппроксимировать линейно В таком случае необходимо использовать другие методы приближения либо менять набор параметров нагрузки и производительности Дополнительным недостатком является то, что выбранная характеристика производительности Р, вообще говоря, не характеризует быстродействие файловой системы непосредственно Кроме того, этот показатель применим только для нагрузок, предполагающих работу с сетью (web-, почтовый сервер и др )

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

Глава 3 посвящена технологии «низкоуровневого» моделирования производительности файловых систем и применению данной технологии для создания модели прогнозирования производительности NTFS Нагрузка в «низкоуровневой» модели представляется последовательностью запросов к драйверу файловой системы Вектор нагрузки х = (хр ,хк) есть набор параметров, однозначно определяющих эту последовательность В качестве характеристики производительности было выбрано время выполнения последовательности Т Моделирование проводилось в три этапа путем независимых исследований запросов основных типов чтение данных, запись данных и обработка метаданных

Чтение

Поскольку NTFS оперирует двумя типами данных, кэшированными (присутствующими в файловом кэше) и не кэшированными (для доступа к которым необходимо обращение к диску), можно говорить о т н модели двух хранилищ информации быстрого (cache) и медленного (disk) Пусть С - множество запросов, при которых данные берутся только из кэша, a D - множество запросов, требующих обращения к диску Нагрузка представляет собой последовательность запросов из множества С U D, причем для чтения С П D = 0

Предположив, что скорость чтения данных из каждого хранилища постоянна и равна v^ и v), (\'с > vj,), можно записать время выполнения одного запроса

t;=ss/vj, (3)

где s^ и Sj — количество запрашиваемых байтов Тогда общее время выполнения последовательности запросов чтения равно

req.eD rcq^C reqjeC

v=r(s;,s:)=si/vrd+s;/vre, (4)

где SJ. и SJ, - общее число байтов, прочитанных за время Тг из кэша и с диска соответственно

Рис 5 Зависимость времени чтения от количества прочитанных данных а) с диска, б) из кэша

Гипотеза о линейности функции Т'^, Б^) подтвердилась экспериментально при контекстном поиске данных в выбранной директории (рис 5), что позволи-

ло вычислить коэффициенты v^ и vj, с помощью линейной аппроксимации по МНК Однако при смене директории поиска значение коэффициента vj изменялось, в отличие от величины v^, которая оставалась постоянной во всех опытах Это позволило заключить, что скорость чтения данных с диска не постоянна, а, возможно, зависит от некоторого дополнительного параметра

Предположим, что обработка запроса к диску происходит с некоторой задержкой t J, которая вызвана работой механических компонентов устройства

td =to +sd/v0 ' (5)

где tj, = const, Vq = const Обозначим через NJ, общее количество дисковых запросов Тогда время выполнения запросов чтения с диска есть

T^sx^t'o+si/v;.

(6)

а скорость Уд = Э^/Т^, которая вопреки первоначальному предположению оказалась не постоянной, равна

где ^ = Б^/КГ!, - средний размер запросов чтения с диска

На рис 6 представлена эмпирическая зависимость и ее аппроксимация

(7)

vj В/та

3-,

кривой вида f(x) = -

при помощи ал-

а + Ьх

горитма Левенберга-Марквардта3 Выбор данного метода в работе обусловлен главным образом быстротой сходимости и популярностью практического применения Гипотеза (7) получила эксперимен-

О WOO 10000 15000 20000

Рис б Скорость чтения данных с диска в зависимости от среднего размера запросов

1 http //www сс gatech edu/people/home/ananth/docs/imtut pdf

13

тальное подтверждение (коэффициент детерминации для выбранного приближения Б.2 = 0 9 ) Поэтому с учетом формул (4) и (6) время выполнения последовательности запросов чтения есть линейная функция трех переменных

г=г (м;, Б;)=+^+^ (8)

Графики зависимости экспериментального значения Тг и его оценки по формулам (4) и (8) от числа запросов п при нагрузке контекстного поиска в произвольной директории изображены на рис 7а и 76 соответственно Ясно, что модель, учитывающая три параметра нагрузки Ы',, и 8гс, более точно прогнозирует значение производительности Тг

Рис 7 Экспериментальное время Тг и его линейная оценка в зависимости от числа запросов п при разных наборах параметров нагрузки

a) r=T'(s;,s:),6; T'=T'(N;,S;,S:)

Замечание анализируя график, представленный на рис 6, можно предположить, что функция скорости vj имеет экспоненциальный, ступенчатый или иной вид Однако наилучшие результаты сравнения экспериментального значения Тг с его оценкой были получены именно при условии (7) (рис 76)

Тестирование NTFS на различных аппаратных конфигурациях позволило сделать ряд важнейших выводов касательно коэффициентов модели

- величина t„ характеризует степень фрагментации запрашиваемых данных математическое ожидание t|j совпадает со средним временем поиска по диску (average seek time), обозначаемым производителем в спецификации устройства,

- величина v'tl представляет собой скорость передачи данных с пластин диска

в его внутренний буфер (Internal Data Transfer Rate, IDTR), которая прямо пропорциональна скорости вращения пластин диска (Revolutions Per Minute, RPM), также указываемой производителем в спецификации устройства,

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

В системе (9) приведены точные значения коэффициентов, полученные при моделировании с использованием диска SAMSUNG SV4002H Коэффициенты tj, и l/ vj, полностью соответствуют физическим характеристикам устройства, указанным в спецификации среднее время поиска - 8 9 мс, скорость вращения

- 5400 RPM (1/IDTR «3 Ю^с/КБ)

'^ = 9 Ю-3 с,

• 1/4=3 10"4с/КБ, (9)

l/v^ = l 10~6 с/КБ

На практике время выполнения последовательности запросов меняется от эксперимента к эксперименту при одинаковых условиях тестирования Значит, характеристику производительности Тг необходимо рассматривать как случайную величину, зависящую от неслучайных переменных х", i = l,k В задаче оценки производительности файловой системы значения х[ играют роль переменных параметров нагрузки, входящих в распределение величины Тг, т е к = 3, х[ = Nj, Xj = Sj, Xj = S^ Таким образом, достоверность модели (8) можно проверить статистическим методом множественной регрессии

Е(Тг)=К+ЕРХ О«)

При помощи критерия согласия Пирсона с уровнем значимости 5% в работе было показано, что при фиксированных параметрах нагрузки Тг есть нормально распределенная случайная величина Для определения коэффициентов рег-

рессии использовалась выборка из п = 14 независимо наблюденных точек (Т^,х[у, х^,, х^), V = 1,п Каждый элемент выборки был получен в результате последовательного или произвольного чтения файлов из случайной директории Причем степень фрагментации диска, а также доля кэшированных данных были различными для всех экспериментов

Выяснилось, что при уровне значимости 5% значимыми являются только коэффициенты р[, \У2> причем их значения в точности совпадают с величинами I„, 1/ , полученными ранее и имеющими конкретный физический смысл Свободный член Рд оказался не значимым, что подтвердило предыдущие результаты Отсутствие влияния коэффициента Рз = 1/у^ можно объяснить небольшой размерностью выборки, а также тем, что чтение данных из кэша вносит сравнительно малый вклад в общее время выполнения последовательности запросов Тем не менее, из практических соображений не стоит пренебрегать параметром нагрузки Х3 В случае, когда большая часть данных закэширована (например, на \veb-cepBepe), время чтения будет мало, однако отлично от нуля

Резюмируя вышесказанное, математическую модель прогнозирования производительности файловой системы ЫТРв при нагрузке чтения можно записать в виде следующего линейного соотношения

тг=р;х[+р;хз+р^, (11)

где х' - параметры нагрузки, р[ - коэффициенты модели

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

при исследовании запросов других типов Запись

а

Анализ журналов запросов, полученных в результате записи кэшируемых данных на диск, показал, что поток нагрузочного приложения пишет данные в файловый кэш, а несколько системных потоков параллельно осуществляют сброс этих данных на диск, т е происходит т н отложенная запись Поэтому при оценке времени выполнения запросов записи Ти' необходимо принимать во внимание не только поток исполняемого приложения, но также системные потоки, осуществляющие копирование данных из кэша на диск В противном случае модель будет учитывать только время записи в кэш Т", которое мало по сравнению со временем записи на диск Т^

При открытии файлов на запись с флагом Р1ЬЕ_РЬАС_К0_ВиРРЕКП\0, системные потоки не участвуют в обработке данных Это позволило создать «однопоточную» модель по аналогии с моделью для нагрузки чтения, имеющую, тем не менее, ряд существенных отличий

- поскольку при записи С = 0 (данные всегда пишутся на диск), а Тс" Т", то Т™ можно не учитывать при оценке производительности Т™,

- при произвольной записи малыми (<32КБ) порциями данных на производительность влияет только один параметр нагрузки - количество запросов х",

- Р" = = 3 10-4 с/КБ, тогда как р™ = 0 6 мс, что меньше Р[ = 9 мс

Таким образом, «однопоточная» математическая модель прогнозирования файловой системы ЫТРБ при нагрузке записи дисковых данных, представима следующим соотношением

Т^РХ+РХ, (12)

где параметрами нагрузки являются х,у (количество запросов) и х'" (общий

объем данных), а коэффициент Р" = рг2 характеризует ГОТЯ диска

Рассмотрим физический смысл коэффициента р™ Поскольку запись данных

не предполагает их поиска на диске, логично предположить, что в этом случае

17

задержка при выполнении одного запроса минимальна Например, это может быть время, необходимое для перемещения головки на ближайшую незанятую дорожку Согласно спецификации диска SAMSUNG SV4002H, используемого в экспериментах, время перемещения головки на соседнюю дорожку (track to track seek time) составляет 0 8 мс, что близко к полученной оценке 0 6 мс Это позволило считать Р" физической характеристикой дискового устройства

Вернемся теперь к проблеме отложенной записи Как показало исследование, обработка параллельных запросов к диску происходит при помощи дисковой очереди, обслуживаемой одним системным потоком Каждый запрос, находясь в очереди, ждет окончания обработки предыдущих запросов, поэтому время его выполнения зависит от нагрузки на очередь или от «заполненности» очереди Пусть t" - общее время выполнения запроса к диску, t* - время нахождения запроса в очереди до того момента, когда он начнет обрабатываться системным потоком, t^ - время обработки запроса диском Тогда

tdw=t;+c (13)

Обозначив через N^ количество запросов в очереди при поступлении 1-го запроса, можно записать время нахождения в очереди данного запроса

(14)

J=1

где t^ - время обработки j-ro запроса в очереди Аналогично формуле (5),

tS=t-+s;/vj, (15)

где t" = Р", l/ v™ = Р", s^ - размер j-ro запроса. Тогда

t;=fx+i/vo fx=те+, (i6)

И J=1

где S^ — общий размер запросов в очереди в момент поступления 1-го запроса Ясно, что суммарное время обработки 1-го запроса

t:=t;+t-=t:(Nj+i)+i/vj (s;+Sd:) о?)

18

Отсюда время выполнения последовательности из Ы™ запросов записи на диск

(18)

'•41

где 8™ = ^^ - общий объем записываемых данных

1=1

Измерение и Б™ для каждого запроса представляется технически сложным Поэтому упростим полученную формулу (18) Предположив, что средний размер запросов в очереди равен среднему размеру запросов во всей последовательности, несложно показать, что

т;=(1+м;)(ргхг+рх), (19)

_

где Ы™ = - среднее количество запросов в очереди во время записи

1=1

данных на диск, т е нагрузка или «заполненность» очереди

Измерение Ы™ также является сложной технической задачей Однако можно

оценить эту величину, зная экспериментальное время Т" и его оценку (12)

К=т;/(рГхГ+Р2Х)-1 (20)

а)

0 7060504030 2010 0-

б)

кв

О 50 100 150 200 250 300

50 ¡00 150 200 250 300

Рис 8 Зависимость нагрузки на очередь от размера запросов при а) последовательной записи, б) произвольной записи

При последовательном доступе сброс кэшируемых данных на диск выполняется по 64 КБ, независимо от изначально задаваемого размера запросов в Т е при малых в интенсивность записи данных в кэш гораздо выше интенсивности сброса этих данных на диск, и нагрузка на очередь невелика С увеличением же

19

s скорость генерирования дисковых запросов повышается, нагрузка на очередь растет и, в конце концов, достигает некоторого предельного значения Все запросы, размер которых превышает 64 КБ, при записи на диск разбиваются на несколько запросов по 64 КБ каждый Значит, предельное значение N* должно достигаться при s > 64 КБ, что в целом подтверждается графически (рис 8а)

Аналогично, при произвольном доступе данные накапливаются в кэше и периодически сбрасываются на диск Однако в этом случае размер запросов к диску совпадает с первоначальным размером запросов s (вплоть до 64 КБ) Поэтому при записи данных малыми порциями диск вынужден обрабатывать большое количество маленьких запросов (т е часто перемещать головки и передавать информацию), а это означает, что нагрузка на очередь высока С увеличением s размер запросов к диску увеличивается, а нагрузка на очередь уменьшается, также стремясь к некоторому предельному значению (рис 86) Видно, что предельные значения N™ для последовательного и произвольного

доступа примерно совпадают Отсюда можно сделать вывод, что при больших s производительность NTFS не зависит от способа доступа к данным

Так как дисковая очередь в конечном итоге обслуживается одним потоком, линейная «однопоточная» модель (12) является, по-видимому, наиболее объективной оценкой производительности файловой системы при нагрузке записи дисковых данных Единственное ограничение данного подхода заключается в необходимости преобразования параметров нагрузки х" перед использованием модели Те количество запросов к диску х" = х™/64 (х™ - общий объем данных в КБ) при

— последовательной кэшируемой записи порциями < 64 КБ,

- любой записи порциями > 64 КБ Обработка метаданных

Помимо операций чтения и записи вклад в производительность файловой

системы вносит обработка тн метаданных, которая подразумевает чтение и

изменение информации в главной файловой таблице (Master File Table, MFT) и

20

служебных файлах В работе исследовались основные запросы обработки метаданных - открытие и закрытие файлов По результатам экспериментов были определены три параметра нагрузки количество запросов открытия существующих файлов х™, количество запросов открытия несуществующих (или создания) файлов х™ и количество запросов закрытия файлов х" Среднее время выполнения одного запроса каждого типа представлено в модели соответствующим коэффициентом р™, 1 = 1,3 Экспериментально было установлено, что значения р™ не зависят от физических характеристик диска Это объясняется тем, что при модификации МЕГ и служебных файлов также используется механизм отложенной записи Сброс метаданных на диск происходит в произвольные моменты времени, когда операционная система загружена минимально, поэтому он может не учитываться в текущей нагрузке (Б = 0 )

Принимая во внимание формулы (11) и (12), можно записать математическую модель прогнозирования производительности файловой системы ЭТРБ при произвольных нагрузках в следующем виде

Т = Тг + Г" + Тт = ¿рх +ЕРХ +ЕРГХГ > (21)

»1 1=1 1=1

где Т - общее время работы ШТБ при заданной нагрузке, Тг(хг) и Т"(х"') -время чтения и записи соответственно, Тш(хт) - время обработки метаданных

Проверка соотношения (21) проводилась путем создания реальных нагрузок на файловую систему ТчГТРБ К примеру, сравнение экспериментального и прогнозируемого значений Т при компиляции программ (рис 9а) и просмотре видео (рис 96) в целом подтвердило справедливость модели (коэффициенты детерминации Я2 равны 0 99 и 0 98 соответственно)

Таким образом, вычисленные однажды коэффициенты модели Р', (3™, р™ могут быть использованы в дальнейшем для оценки производительности файловой системы ТЯТРБ при заданной нагрузке без непосредственного тестирования при этой нагрузке

б) J

20

experimental predicted

/

r

/

и

lxlO4 2x10' 3x10' 4x10'

0 2x10s 4x10? 6x10' 8x10s 1x10'

Рис 9 Экспериментальное время Т и его линейная оценка в зависимости от числа запросов п при а) компиляции, б) просмотре видео

В разделе «Практическое применение» главы 3 описывается использование разработанной технологии моделирования на практике Основные результаты, полученные в ходе исследования, приводятся в заключении диссертации

1 Разработаны общая универсальная методика и технология математического моделирования производительности файловых систем, главной особенностью которой является представление нагрузки в виде последовательности низкоуровневых запросов

2 На основе предложенной технологии построена математическая модель прогнозирования производительности файловой системы NTFS, а также разработан комплекс программ для создания данной модели

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

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

5 Предложенная технология моделирования и соответствующий комплекс программ использованы при разработке и тестировании коммерческого программного комплекса Virtuozzo (Windows версия)

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1 НижникЕИ, ТормасовАГ Обзор проблем тестирования производительности файловых систем // Проблемы выч математики, мат моделирования и информатики Сб науч тр /М МЗПресс,2006 -С 89-113

2 НижникЕИ, ТормасовАГ Тестирование производительности файловых систем на основе прогнозирующей модели // Проблемы выч математики, мат моделирования и информатики Сб науч тр /М МЗ Пресс, 2006 - С 114-135

3 НижникЕИ, ТормасовАГ Проблемы тестирования производительности web-сервера на основе прогнозирующей модели // Процессы и методы обработки информации Сб науч тр / М Моек физ -тех инст, 2006 - С 249-257

4 Нижник ЕИ Математическая модель нагрузки файловой системы NTFS при активном поиске дисковых данных // Моделирование процессов обработки информации Сб науч тр / М Моек физ -тех инст, 2007 - С 276-285

5 Нижник Е И Роль нагрузки процессора и фрагментации диска в моделировании производительности файловой системы NTFS // Системы управления и информационные технологии -2007, №2 1(28) -С 181-186

6 Нижник ЕИ Особенности исследования нагрузки процессора и фрагментации диска в моделировании производительности файловой системы NTFS // Информационные технологии моделирования и управления - 2007, №4(38) -С 475-482

7 Нижник Е И Оценка производительности файловой системы NTFS как задача множественной регрессии // Объединенный научный журнал - 2007, №11(199) - С 57-62

8 Нижник Е И Обзор проблем тестирования производительности файловых систем // Совр проблемы фундаментальных и прикладных наук Часть VII Управление и прикладная математика Труды XLVIII научной конференции / МФТИ, - М - Долгопрудный, 2005 -С 57-58

9 Нижник Е И Оценка параметров в прогнозирующей модели тестирования производительности файловых систем // Совр проблемы фундаментальных и прикладных наук Часть VII Управление и прикладная математика Труды XLIX научной конференции / МФТИ - М - Долгопрудный, 2006 - С 58-59

10 Нижник ЕИ Основные проблемы реализации прогнозирующей модели тестирования производительности файловых систем // XXXIII Гагаринские чтения Научные труды Международной молодежной научной конференции в 8-ми томах / Москва, 2007 -Т 6, С 245-246

11 Нижник Е И, Тормасов А Г Статистическая оценка параметров в моделировании производительности файловой системы NTFS // Информационные технологии и системы Труды 30-й конференции молодых ученых и специалистов ИППИ РАН / Москва, 2007 - С 88-91

Нижник Екатерина Игоревна

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОИЗВОДИТЕЛЬНОСТИ ФАЙЛОВЫХ СИСТЕМ

Автореферат

Подписано в печать 18 09 07 Формат 60x90/16 Уел печ л 1 5 Тираж 80 экз Заказ №36

Московский физико-технический институт (государственный университет)

Печать на аппарате Rex-Rotary Copy Printer 1280 НИЧ МФТИ

141700, г Долгопрудный, Московская обл , Институтский пер , 9 тел (095) 4088430, факс (095)5766582

Основные обозначения и сокращения.

Введение.

Глава 1. Обзор моделей оценки производительности файловых систем.

1.1. Типы нагрузок.

1.2. Пакеты тестирования.

1.2.1. Andrew Benchmark.

1.2.2. PostMark.

1.2.3. Iozone.

1.2.4. HBench-FS.

1.2.5. Другие.

1.3. Резюме.

Глава 2. Общая методика моделирования производительности файловых систем.

2.1. Постановка задачи.

2.2. Модель для нагрузки web-сервера.

2.2.1. Файловый кэш.

2.2.2. Нагрузка web-сервера со статическим содержимым.

2.3. Требования к модели.

Глава 3. Низкоуровневое моделирование производительности NTFS.

3.1. Технология.

3.2. Чтение.

3.2.1. Модель двух хранилищ.-.

3.2.2. Фрагментация.

3.2.3. Множественная регрессия.

3.3. Запись.

3.4. Обработка метаданных.

3.5. Проверка результатов.

3.6. Практическое применение.

Файловая система - это неотъемлемая часть операционной среды, которая отвечает за работу с данными, хранящимися во внешней памяти [Карпов, Коньков, 2004]. Для конечного пользователя одной из наиболее важных характеристик файловой системы является производительность, поскольку от нее зависит скорость работы того или иного приложения, а также операционной среды в целом.

Многочисленные исследования показали, что оценку быстродействия файловых систем необходимо осуществлять в контексте нагрузок, генерируемых приложениями [Нижник и др., 2006, С. 89-113]. Под термином «нагрузка» обычно понимается способ обращения к данным, который использует та или иная программа. Большинство существующих инструментов тестирования файловых систем имеет узкую специализацию, т.е. предназначено для оценки производительности при нагрузке, отражающей специфику конкретного приложения или класса приложений. Кроме того, практически все эти инструменты предполагают непосредственное тестирование интересующих пользователя нагрузок. Однако с точки зрения минимизации затрачиваемого времени и ресурсов (как программных, так и аппаратных) более важной является задача прогнозирования производительности. Решение этой задачи позволило бы оценивать быстродействие той или иной файловой системы на основе предварительно выведенной зависимости характеристики производительности от параметров нагрузки и тем самым ускорить процесс планирования вычислительной нагрузки в центрах данных предприятий.

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

В главе 1 содержится обзор основных исследований, посвященных различным типам нагрузок. Дается описание существующих инструментов для оценки производительности файловых систем, перечисляются их достоинства и недостатки. В главе 2 формулируется постановка задачи, предлагается общая методика ее решения, а также приводятся результаты применения методики для создания «высокоуровневой» (уровня пользовательских приложений) математической модели прогнозирования производительности файловой системы ШТЗ при нагрузке, генерируемой \уеЬ-сервером. Глава 3 посвящена «низкоуровневому» (уровня драйвера файловой системы) моделированию производительности ШТЗ при нагрузках чтения, записи и обработки метаданных. Также в этой главе приводятся результаты практических экспериментов, подтверждающие состоятельность модели, а также описываются примеры ее практического применения.

ЗАКЛЮЧЕНИЕ

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

На реальных программных комплексах проведен ряд сравнительных экспериментов, результаты которых подтверждают адекватность предложенной модели решаемым с ее помощью задачам. Предложенная технология моделирования и соответствующий комплекс программ использованы при разработке и тестировании коммерческого программного комплекса Virtuozzo (Windows версия).

Дальнейшее развитие математической модели прогнозирования производительности NTFS может включать исследование влияния следующих факторов на быстродействие данной файловой системы:

- размер кластера;

- дополнительные возможности NTFS, такие как сжатие и шифрование файлов;

- тип контроллера дискового устройства (IDE, SATA, SCSI);

- дисковые алгоритмы работы с данными, такие как замещение дефектных секторов, контроль циклическим избыточным кодом (CRC) и др.

БЛАГОДАРНОСТИ

Хочу выразить глубокую признательность моему научному руководителю А.Г. Тормасову за постановку задачи и руководство выполнением научной работы. Трудно переоценить влияние Александра Геннадьевича на формирование моих научных взглядов.

Искреннюю благодарность приношу Д.И. Дядечко за неоценимую помощь в проведении исследования, И.В. Нижнику за обсуждение работы и помощь в подготовке рукописи, A.A. Енакиеву за технические консультации, С.С. Протасову и коллективу компании ООО «СВСофт МФТИ» за предоставление вычислительных ресурсов, понимание и поддержку, A.A. Алябьеву за советы по оформлению работы, Е.А. Катрухе и A.C. Осипенко за стимулирующие дискуссии и ценные замечания.

Я признательна преподавателям кафедры информатики МФТИ (заведующий кафедрой профессор И.Б. Петров), в особенности В.Е. Карпову, за проявленное внимание к моей работе. Также благодарю заведующую аспирантурой В.И. Демину за помощь при поступлении в аспирантуру МФТИ.

1. Bonnie File System Benchmark Электронный ресурс. - Режим дост.: http://www.textuality.com/bonnie/

2. CHS Conversion Электронный ресурс. Режим дост.: http://en.wikipedia.org/wiki/CHSconversion

3. Gaede S.L. Perspectives on the SPEC SDET Benchmark Электронный ресурс. -1999. Режим дост.: http://www.spec.org/sdm91/sdet/SDETPerspectives.pdf

4. How NTFS Works 2003. - Электронный ресурс. - Режим дост.: http://technet2.microsofit.com/windowsserver/en/library/81cc8a8a-bd32-4786-a849-03245d68d8e41033 .mspx

5. S Kit Installable File System Kit Электронный ресурс. - Режим дост.: http://www.microsoft.com/whdc/DevTools/IFSKit/default.mspx

6. Katcher J. PostMark: a New File System Benchmark Technical Report TR-3022, Network Appliance Inc., 1997.

7. Kozierok C. The PC Guide Электронный ресурс. 2001. - Режим дост.: http://www.pcguide.com/

8. Kuenning G.H., Рорек G.J., Reiher P.L. An Analysis of Trace Data for Predictive File Caching in Mobile Computing Proceedings of the Summer USENIX Conference-1994.-P. 291-303.

9. Norcott fV.D. Iozone Filesystem Benchmark 2003. - Электронный ресурс. -Режим дост.: http://www.iozone.org/docs/IOzonemsword98.pdf

10. OriginLab Электронный ресурс. Режим дост.: http://www.originlab.com/

11. Ousterhout J. Why aren't Operating Systems Getting Faster as Fast as Hardware -WRL Technical Note, TN-11, 1989.

12. Park A., Becker J.C., Lipton R.J. IOStone: a Synthetic File System Benchmark-SIGARCH Computer Architecture News 1990. - V.l8, N.2, P. 45-52.

13. Pentakalos O., Friedman M. Windows 2000 Performance Guide, First Edition. -Publisher: O'Reilly, 2002. 718 p.

14. Peterson W. W., Brown D. T. Cyclic Codes for Error Detection Proceedings of the IRE-1961.-P. 228-235.

15. Ramakrishnan К.К., Biswas P., Karedla R. Analysis of File I/O Traces in Commercial Computing Environments Proceedings of ACM Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) - 1992. P. 78-90.

16. Ranganathan A. The Levenberg-Marquardt Algorithm Электронный ресурс. -2004. Режим дост.:http://www.cc.gatech.edu/people/home/ananth/docs/lmtut.pdf

17. RoselliD., Lorch J., Anderson T. A Comparison of File System Workloads Proceedings of the San Diego USENIX Conference - 2000. - P. 41-54.

18. Rosenblum M., Ousterhout J. The Design and Implementation of a Log-Structured File System // ACM Transactions on Computer Systems 1992. - V.10, N.l. -P. 26-52.

19. Rosenblum M., Ousterhout J. The LFS Storage Manager Proceedings of the Summer USENIX Conference - 1990. - P. 315-324.

20. Samsung SpinPoint V40 Product Manual 2001. - Электронный ресурс. - Режим дост.: http://personal.inet.fi/cool/lwgt/myoldvdr/V40ProductManual.pdf

21. Seltzer М., Bostic К., McKusick М., Staelin С. An Implementation of a Log-Structured File System for UNIX Proceedings of the San Diego USENIX Conference-1993.-P. 201-218.

22. Smith K., Seltzer M. File Layout and File System Performance Harvard University Technical Report, TR-35-94, 1994.

23. Smith K.A. Workload-Specific File System Benchmark: Ph.D. Thesis Harvard University, 2001.- 159 p.

24. TangD.L. Benchmarking Filesystems Harvard University Computer Science Technical Report, TR-19-95, 1995.

25. Wittle M., Keith B. LADDIS: the Next Generation in NFS File Server Benchmarking Proceedings of the Summer USENIX Conference - 1993. - P. 111-128.

26. Джонсон H., Лион Ф. Статистика и планирование эксперимента в технике и науке. М.: Мир, 1980. - 610 с.

27. Карпов В.Е., Коньков КА. Основы операционных систем. М.: Интернет-университет информационных технологий - ИНТУИТ.ру, 2004. - 536 с.

28. Крамер Г. Математические методы статистики. М.: Мир, 1975. - 648 с.

29. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений. JL: Физматгиз, 1962. -352 е.: ил.

30. Манита А.Д. Теория вероятностей и математическая статистика: Учебное пособие. Издат. отдел УНЦ ДО, 2001. - 120 с.

31. Нижник Е.И Математическая модель нагрузки файловой системы NTFS при активном поиске дисковых данных // Моделирование процессов обработки информации: Сб. науч. тр. / М.: Моск. физ.-тех. инст., 2007. С. 276-285.

32. Нижник Е.И. Основные проблемы реализации прогнозирующей модели тестирования производительности файловых систем // XXXIII Гагаринские чтения. Научные труды Международной молодежной научной конференции в 8-ми томах. / Москва, 2007. Т. 6, С. 245-246.

33. Нижник Е.И. Особенности исследования нагрузки процессора и фрагментации диска в моделировании производительности файловой системы NTFS // Информационные технологии моделирования и управления 2007, №4(38). -С. 475-482.

34. Нижник Е.И. Оценка производительности файловой системы NTFS как задача множественной регрессии // Объединенный научный журнал 2007, №11(199).-С. 57-62.

35. Нижник Е.И. Роль нагрузки процессора и фрагментации диска в моделировании производительности файловой системы NTFS // Системы управления и информационные технологии 2007, №2.1 (28). - С. 181-186.

36. Нижник Е.И, Тормасов А.Г. Статистическая оценка параметров в моделировании производительности файловой системы NTFS // Информационные технологии и системы. Труды 30-й конференции молодых ученых и специалистов ИППИ РАН. / Москва, 2007. С. 88-91.

37. Нижник Е.И, Тормасов А.Г. Тестирование производительности файловых систем на основе прогнозирующей модели // Проблемы вычислительной математики, математического моделирования и информатики: Сб. науч. тр. / М.: МЗ Пресс, 2006.-С. 114-135.

38. Нижник Е.И, Тормасов А.Г., Луковников ИВ. Обзор проблем тестирования производительности файловых систем // Проблемы вычислительной математики, математического моделирования и информатики: Сб. науч. тр. / М.: МЗ Пресс, 2006.-С. 89-113.

39. Нижник Е.И, Тормасов А.Г., Луковников ИВ. Проблемы тестирования производительности web-сервера на основе прогнозирующей модели // Процессы иметоды обработки информации: Сб. науч. тр. /М.: Моск. физ.-тех. инст., 2006.-С. 249-257.

40. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ: Учебное пособие. М.: Высш. школа, 1989. - 367 с.

41. Рао С.Р. Линейные статистические методы и их применения. М.: Наука, 1968.-548 с.

42. Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows. 4-е изд. -СПб.: Питер, М.: Издательско-торговый дом «Русская Редакция», 2001. -752 е.: ил.

43. Руссинович М., Соломон Д. Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP и Windows 2000. Мастер-класс. Пер. с англ. 4-е изд. - М.: Издательско-торговый дом «Русская Редакция»; СПб.: Питер; 2005. - 992 е.: ил.

44. Солдатов В.П. Программирование драйверов Windows. Изд. 2-е, перераб. и доп. М.: ООО «Бином-Пресс», 2004. - 480 е.: ил.

45. Таненбаум Э. Архитектура компьютера. 4-е изд. СПб.: Питер, 2002. - 704 е.: ил.

46. Таненбаум Э. Современные операционные системы. 2-е изд. СПб.: Питер, 2004.- 1040 е.: ил.