Модификация и моделирование алгоритмов обработки данных в кэш-памяти систем хранения данных

Сибиряков Максим Андреевич кандидат технических наук руководитель, группа компьютерного обеспечения ГТРК Марий Эл 424033, Россия, Республика Марий Эл, г. Йошкар-Ола, ул. Эшкинина, 2 Sibiryakov Maksim Andreevich PhD in Technical Science The head of the computer support group of GTRK Mari El 424033, Russia, respublika Marii El, g. Ioshkar-Ola, ul. Eshkinina, 2 maxover777@bk.ru Другие публикации этого автора

Васяева Елена Семеновна кандидат технических наук доцент, кафедра информационно-вычислительных систем, ФГБОУ ВПО "Поволжский государственный технологический университет" 424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3 Vasyaeva Elena Semenovna PhD in Technical Science associate professor of the Department of Information Computation Systems at Volga State University of Technology 424000, Russia, Republic of Mari El, Yoshkar-Ola, str. Lenin's prospect, 3 vasjaeva@mail.ru

Работа выполнена при поддержке гранта РФФИ: №16-37-00153 мол_а

Системы хранения данных (СХД) в настоящее время являются неотъемлемой частью практически любой информационно-вычислительной сети. Их разделяют на низкопроизводительные; среднепроизводительные и высокопроизводительные системы, обеспечивающие очень высокую надежность, доступность и скорость доступа к хранимым данным ^[1]. Однако не смотря на мощность вычислительной аппаратуры современных систем хранения, существует проблема эффективного использования ее ресурсов. Для обеспечения высокой производительности в системах применяются сложнейшие алгоритмы обработки данных.

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

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

- модифицированы алгоритмы обработки данных и структура управляющих индексных таблиц;

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

- проведено имитационное моделирование операции поиска данных с целью доказательства целесообразности применения хеш-таблицы для ускорения выполнения алгоритмов обработки данных.

Анализ известных методов управления кэш-памятью показал наличие проблем эффективного использования ресурсов кэш-памяти в связи с постоянным ростом объемов кэш-памяти систем хранения данных ^[2-5]. Основным недостатком этих методов является низкая эффективность поиска данных при большом числе хранимых блоков данных в кэш-памяти. За основу детального анализа был взят наиболее современный метод, разработанный в компании Hitachi ^[3]. Он основан на особенностях предшествующих ему методов и лишен их недостатков. В этом методе реализован механизм использования одного блока данных несколькими хост-узлами, что не было реализовано ранее. Также в этом методе реализована совокупность взаимосвязанных управляющих индексных таблиц (индекс), позволяющая более эффективно распределять ресурсы кэш-памяти между хост-узами.

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

В рамках исследований метода были детально проанализированы алгоритмы обработки данных (чтения/записи и вытеснения данных), выполняемые на основе индекса. Всего индекс содержит семь базовых управляющих индексных таблиц, часть которых реализована в виде связных структур:

- таблица управления секторами дискового кэша (ТУСДК)содержит информацию о размерах секторов кэша, выделенных соответствующим хост-узлам;

- таблица управления дисковым кэшем (ТУДК) описывает соответствие трекам жестких дисков сегментов кэш-памяти;

- таблица, хранящая управляющую информацию о секторах дискового кэша» (УИОСДК), описывает принадлежность сегментов секторам. Таблица организована в виде двусвязного кольцевого списка, она формируется для каждого сектора.

- таблица управления совместно используемыми секторами (ТУСИС) содержит ссылку (указатель списка) на таблицу УИОСИС для каждого сегмента;

- таблица, содержащая управляющую информацию о совместно используемых сегментах» (УИОСИС), позволяет определить, какими секторами используется тот или иной сегмент. Таблица организована в виде двусвязного кольцевого списка, она создается для каждого сегмента.

- таблица управления свободными сегментами (ТУСС) содержит информацию о наличии свободных сегментов в кэше. Организована в виде двусвязного кольцевого списка.

- таблица атрибутов жестких дисков (ТАЖД). Данная таблица регулирует режим доступа к трекам.

На рисунках 1 и 2 представлены блок-схемы алгоритмов чтения (обработки команды чтения) и вытеснения данных. Алгоритм обработки команды записи практически идентичен алгоритму чтения, за исключением необходимости записи данных из кэш-памяти на жесткий диск. В случае алгоритма чтения данные из кэш-памяти передаются хост-узлу.

Использование секторов позволило реализовать механизм, при котором ни один из хост-узлов не сможет использовать больше ресурсов кэш-памяти, чем ему назначено. В исследуемом методе появилась возможность использования одного сегмента кэш-памяти несколькими хост-узлами, что исключает проблему дублирования данных. В этом случае используется понятие совместно используемого сегмента. Соответственно, один и тот же сегмент может принадлежать нескольким секторам. В случае использования сегмента одним из хост-узлов он блокируется для изменения другими. Это реализуется с помощью установки статусов разрешения на запись и чтение в таблице ТАЖД.

Рис. 1. Блок-схема алгоритма обработки команды чтения данных

Рис. 2. Блок-схема алгоритма вытеснения данных

Управляющие индексные таблицы реализованы на основе 2-х типов структур: таблиц (массивов) и двусвязных кольцевых списков. При возрастании числа элементов в данных индексных таблицах линейно увеличивается время поиска данных. Современные системы хранения данных имеют очень большие объемы кэш-памяти, соответственно размер управляющих индексных таблиц также очень большой. Очевидно, что чем больше число хранимых элементов, тем больше время поиска.

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

Дадим новой индексной таблице название «Хеш-таблица управления дисковым кэшем» (ХТУДК, рис. 3). Она представляет собой совокупность связных списков, которые являются цепочками коллизий. В качестве ключа используется номер трека. Указателем на начало каждого списка выступает хеш-значение для номера трека кэш-памяти. Для разрешения коллизий в данном случае целесообразно использовать метод цепочек.

Рис. 3. Хеш-таблица управления дисковым кэшем (ХТУДК)

Поскольку записи таблицы ТУДК дублируются в таблицу ТУСИС, то есть возможность убрать таблицу ТУСИС из индекса, перенеся управляющее поле «Указатель на УИОСИС» в новую структуру ХТУДК, без нарушения работы алгоритмов обработки данных. Это позволит за одно обращение к таблице одновременно получить информацию о соответствии сегментов трекам и получить ссылку на таблицу УИОСИС. Объединение таблиц также позволяет сэкономить ресурсы системной памяти, хранящей управляющие индексные таблицы.

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

В связи с предложенными модификациями общий алгоритм обращения к кэш-памяти изменяется незначительно. Изменения касаются только обращения к новой структуре ХТУДК. Построение нового индекса с таблицей ХТУДК позволяет существенно уменьшить количество шагов выполнения алгоритмов.

Для оценки средней трудоемкости выполнения исходных и модифицированных алгоритмов использовался метод цепей Маркова ^[6-8]. Для этих алгоритмов были построены граф-схемы (ГСА). Для примера, на рисунке 4 представлены обобщенные ГСА для алгоритмов чтения и вытеснения данных для исходной организации индекса.

Рис. 4. ГСА алгоритма обработки чтения данных (а) и алгоритма вытеснения данных (б) для исходной организации индекса

Для построения ГСА все алгоритмы были представлены в детализованном виде, в элементарных операциях. Например, на рисунке 5 показана блок-схема детализованного алгоритма вытеснения данных для новой организации индекса.

Рис. 5. Детализованный алгоритм вытеснения данных для модифицированной организации индекса

Средняя трудоемкость алгоритма, т.е. среднее число процессорных операций, выполняемых при одном прогоне алгоритма, вычисляется следующим образом ^[7].

где – трудоемкость операторной вершины, n_i – среднее число обращений к i-му оператору.

Трудоемкость каждой конкретной операции алгоритма определяется количеством условных машинных тактов процессора. Например, команда чтения и записи из регистра в регистр выполняется за 1 такт. При расчете средней трудоемкости алгоритмов учитывалось, что трудоемкости некоторых вершин графа (вершин циклов) зависят от размера управляющих индексных таблиц (j, p, y, i, t ).

В результате были рассчитаны значения средней трудоемкости выполнения алгоритма обработки команды чтения данных с учетом выполнения алгоритма вытеснения данных при одном прогоне для исходной организации индекса () и средней трудоемкости выполнения этих алгоритмов, реализуемых с учетом предложенного модифицированного индекса () (параметры a, b, c ,d ,e – трудоемкости элементарных операций алгоритмов не зависящих от размера таблиц индекса):

Анализируя полученные значения можно сделать вывод, что трудоемкости зависят от размерности управляющих индексных таблиц. Таблица ТУДК исходного индекса имеет i записей, хеш-таблица ХТУДК – t записей в цепочке коллизий. С учетом того, что наибольшее количество записей содержится именно в этих индексных таблицах, и соотношение трудоемкости остальных таблиц примерно одинаково, пренебрегая трудоемкостями малозначимых операций a, b, c, d, e, получим следующее соотношение

Можно видеть, что средняя трудоемкость выполнения алгоритмов обработки команды чтения в значительной степени зависит от скорости выполнения операции поиска записей в таблице ТУДК (или ХТУДК). Следовательно, трудоемкость модифицированного алгоритма значительно меньше трудоемкости исходного алгоритма. Этот выигрыш тем больше, чем меньше длина цепочки коллизий.

В рамках исследований было проведено имитационное моделирование операции поиска данных (номеров треков) для двух типов структур (таблицы и хеш-таблицы) и подтверждена целесообразность применения хеш-таблицы для построения индексных таблиц с большим числом записей, путем сравнения и оценки трудоемкости операции поиска блока данных.

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

Наличие цепочек коллизий и их длины напрямую зависят от функции хеширования, если подобрать идеальную функцию хеширования, то коллизий можно избежать совсем ^{[9, 10]}. Однако чаще всего такую функцию достаточно трудно подобрать. Нужно стараться выбрать такую функцию, которая бы минимизировала число цепочек коллизий, и в среднем длины цепочек коллизий были бы приблизительно равны.

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

Хорошая хеш-функция должна удовлетворять двум свойствам:

• быстро вычисляться;
• минимизировать число коллизий.

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

В качестве хеш-полинома выбраны неприводимые полиномы на поле Галуа GF(2), поскольку операция деления на них может быть легко реализована аппаратурно с использованием логических схем И/ИЛИ.

Для имитационного моделирования разработана программа на языке С++ (рис. 6).

Рис. 6. Интерфейс моделирующей программы

Для моделирования использовался 25-битный адрес из расчета того, что размер кэш-памяти составляет 1 Тбайт, а стандартный размер сегмента – 64 Кбайта. В качестве делимых полиномов использовались неприводимые полиномы GF(2) от 4-й до 8-й степени.

В результате имитационного моделирования были получены следующие результаты:

А. Для сравнения средней трудоемкости поиска номера трека сначала рассматривался худший случай для хеш-таблицы. Получается, что чем ниже степень делимого полинома, тем меньше уникальных хеш-значений. Соответственно, увеличиваются длины цепочек коллизий и время поиска в хеш-таблице. Для оценки трудоемкости был взят полином меньшей степени, в данном случае - 4-й степени, h(x) = x⁴+x³+1 (11001). Существуют другие полиномы этой же степени, однако в данном случае вид полинома не важен. В таблице 1 представлены результаты расчета программой средней трудоемкости поиска номера трека для таблицы и хеш-таблицы, показано их соотношение (T_сред./T_{сред.х.-т.}). В процессе моделирования изменялся параметр количества уникальных номеров треков кэш-памяти.

Таблица 1 – Значения трудоемкости поиска номера трека в таблице и хеш-таблице

На рисунке 7 представлены графики зависимости трудоемкости поиска номера трека от числа сгенерированных уникальных номеров треков для таблицы и хеш-таблицы.

Рис. 7. График зависимости средней трудоемкости поиска номера трека от числа номеров треков

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

Б. Увеличение степени полинома позволяет увеличить количество уникальных хеш-ключей. В таблице 2 представлены значения средней трудоемкости поиска номера сегмента для полиномов (4-й) и (8-й) степеней.

Таблица 2 – Значения средней трудоемкости поиска номера трека в хеш-таблицы для полиномов разной степени

На рисунке 8 представлены графики зависимости средней трудоемкости поиска номера трека от числа сгенерированных уникальных номеров треков в хеш-таблице для полиномов 4-й и 8-й степени. Они показывают, что степень полинома значительно влияет на длину цепочек коллизий. По графикам видно, что при более высокой степени полинома трудоемкость поиска номера трека значительно ниже.

Рис. 8. График зависимости средней трудоемкости поиска номеров треков в хеш-таблице от количества номеров треков для полиномов 4-й и 8-й степени

В. Средняя трудоемкость поиска номера трека зависит от его разрядности. Для моделирования было взято фиксированное число уникальных номеров треков равное 100000.

При меняющейся разрядности адреса были получены значения средней трудоемкости поиска номера трека (таблица 3).

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

Таблица 3 - Трудоемкость поиска номера трека в кэш-памяти

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

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

Для оценки целесообразности замены таблицы на хеш-таблицу была проведена оценка средней трудоемкости выполнения алгоритмов обработки данных с помощью марковского метода.

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

Также было проведено имитационное моделирование, подтверждающее, что применение хеш-таблицы при большом количестве записей ускоряет поиск. К примеру, для 25-разрядного ключа (номера трека) и 4-разрядного полинома соотношение трудоемкости операции поиска для таблицы и хеш-таблицы для 500 элементов равно 15,62; для 50000 – 16,8; для 100000 – 17,64. Эти соотношения показывают во сколько раз быстрее в среднем выполняется операция поиска записи в хеш-таблице относительно таблицы. При увеличении числа записей это соотношение только возрастает.

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