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

Сибиряков Максим Андреевич кандидат технических наук руководитель, группа компьютерного обеспечения ГТРК Марий Эл 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 Другие публикации этого автора

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

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

1) Анализ существующих алгоритмов вытеснения информации, в том числе, применяемых в хранилищах данных.

2) Разработка алгоритмов ускоренного вытеснения информации в больших хранилищах данных.

Эффективность работы кэш-памяти определяет процент кэш-промахов ^[3]. На уменьшение данного показателя влияет применяемый в памяти алгоритм вытеснения информации. В таблице 1 представлены основные алгоритмы вытеснения информации ^{[3, 4]}. Существуют и другие алгоритмы, однако, они являются их модификациями и гибридами.

Таблица 1

Сравнительные характеристики алгоритмов вытеснения информации

В вычислительных системах чаще всего используется алгоритм вытеснения информации LRU ^[4]. Например, он применяется в современных процессорах семейства x86 ^{[5, 6]}. Алгоритм LRU эффективен и прост в реализации, в эффективности уступает только адаптивным гибридным алгоритмам ARC и его модификации SARC ^{[7, 8]}. Существует множество модификаций алгоритмов LRU: таких как MRU, SLRU, CLOCK, LRU-L, CAR и др.

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

1) LRU.

2) ARC.

3) SARC.

В большинстве случаев применяется алгоритм LRU, как наиболее эффективный и простой в реализации. Однако в некоторых системах применяются адаптивные гибридные алгоритмы вытеснения информации. Алгоритм ARC – гибридный алгоритм, содержащий в себе свойства алгоритмов LFU и LRU, а SARC – свойства алгоритмов MRU и LRU. Однако данные алгоритмы значительно сложнее в реализации. Они работают с двумя списковыми структурами, содержащими информацию о кэшируемых данных и, как следствие, требуют больше памяти для хранения управляющей информации. К тому же, при увеличении объемов кэш-памяти разница в проценте кэш-промахов с применением алгоритмов LRU и ARC снижается.

В рамках исследования существующих алгоритмов вытеснения информации в хранилищах данных с большими объемами кэш-памяти предложен подход построения организационной структуры управляющих информационных таблиц с использованием ассоциативного массива ^[9]. Это позволило уменьшить трудоемкость выполнения применяемых алгоритмов вытеснения информации в кэш-памяти хранилищ данных на i(1-1/j) операций последовательного перебора при поиске данных (j- количество цепочек коллизий т.е. уникальных хеш-значений ассоциативного массива, i-общее количество записей таблицы). На рисунке 1 представлена структура разработанной информационной управляющей таблицы.

Рис.1. Разработанная структурная организация ассоциативного массива для построения информационной управляющей таблицы кэш-памяти хранилища данных ^[9]

На основе предложенного подхода разработаны алгоритмы вытеснения информации LRU1 и LRU2. Первый алгоритм используется при вытеснении информации, когда в отдельной области кэш-памяти – секторе, нет места. Второй алгоритм является модификацией первого и используется для случая переполнения всей кэш-памяти. Они формализованы путем применения математического аппарата, связанного с их представлением на основе модели конечных автоматов с использованием рекуррентных бескванторных предикатных уравнений, или систем канонических уравнений, предложенных Н. П. Вашкевичем для последовательных ^[10] и параллельных ^[11] алгоритмов. СКУ позволяет формировать компактные представления алгоритмов с описанием функций переходов в терминах частных событий. Данные события реализуются в частичных детерминированных автоматах Мура, в которых соблюдаются условия однозначности переходов, то есть под воздействием одного частичного входного сигнала или комбинации таких сигналов возможен переход от некоторого исходного события только к одному событию.

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

Рис. 2. Блок-схема разработанного алгоритма ускоренного вытеснения информации LRU1 ^[9]

Для примера на рис. 2 представлена блок-схема алгоритма ускоренного вытеснения информации LRU1. Для него разработана укрупненная граф-схема алгоритма (ГСА, рис. 3), на основе которой построены СКУ ^[12].

Таблица 2

Вершины разработанного алгоритма ускоренного вытеснения информации LRU1, составляющие операторы укрупненных ГСА ^[12]

Примечание. События S₃, S₄ – разделительные.

Рис. 3. Граф-схема алгоритма ускоренного вытеснения информации LRU1 (ГСА₁) ^[12]

СКУ₁дляГСА₁:

S₀(t+1) = S₀(t)&Øx₀(t) Ú x_begin(t);

S₁(t+1) = S₀(t)& x₀(t) Ú S₁(t)&Øz₁(t);

S₂(t+1) = S₁(t)&z₁(t)&x₁(t) Ú S₂(t)&z₂(t)&x₁(t) Ú S₂(t)&Øz₂(t);

S₃(t+1) = S₁(t)&z₁(t)&Øx₁(t) Ú S₂(t)&z₂ (t)&Øx₁(t) Ú S₃(t)&Øz₃(t);

S₄(t+1) = S₃(t)&z₃(t)&x₂(t) Ú S₄(t)&Øz₄(t);

S₅(t+1) = S₄(t)&z₄(t)&x₃(t) Ú S₅(t)&Øz₅(t);

S₆(t+1) = S₄(t)&z₄(t)&Øx₃(t) Ú S₆(t)&Øz₆(t);

S₇(t+1) = S₅(t)&z₅(t) Ú S₆(t)&z₆(t) Ú S₇(t)&Øz₇(t);

S₈(t+1) = S₃(t)&z₃(t)Øx₂(t) Ú S₈(t)&Øz₈(t);

S₉(t+1) = S₈(t)&z₈(t)&x₄(t) Ú S₉(t)&z₉(t)&x₄(t) Ú S₉(t)&Øz₉(t);

S₁₀(t+1) = S₈(t)&z₈(t)&Øx₄(t) Ú S₉(t)&z₉(t)&Øx₄(t) Ú S₁₀(t)&Øz₁₀(t);

S₁₁(t+1) = S₁₀(t)&z₁₀(t) Ú S₇(t)&z₇(t) Ú S₁₁(t)&Øz₁₁(t);

S_k(t+1) = S₁₁(t)&z₁₁(t) Ú S_k(t)&Øz_k(t),

где S_i(t) – унарный предикат, определенный на множестве значений дискретного времени t. Истинность S_i(t) означает, что автомат находится в состоянии S_i в момент времени t, или в автомате реализуется частное событие S_i в момент времени t. Входные сигналы x_j(t) – частичные, т. е. на переход влияет сам сигнал, а не комбинация всех сигналов, как в случае полного автомата; x_begin(t) – сигнал установки автомата в начальное состояние. Входные сигналы x_j(t) представлены унарными предикатами.

Исходя из того, что времена работы операторов различные, необходимо учесть условия окончания работы операторов, то есть каждый оператор по окончании своей работы должен выдать сигнал окончания. Тогда примем, что z_i(t) – условие сохранения события S_i при z_i(t)=0 («false»); при z_i(t)=1 («true») событие S_iне сохраняется и происходит переход к следующему событию. Сигнал, или условие z_i(t) формируется при выполнении события S_i (условие z_i(t) может быть истинным только после выполнения события S_i). Использование условия сохранения позволяет событию S_i выполняться за необходимое количество тактов.

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