Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

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

Сибиряков Максим Андреевич

кандидат технических наук

руководитель, группа компьютерного обеспечения ГТРК Марий Эл

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
Другие публикации этого автора
 

 

DOI:

10.25136/2644-5522.2017.4.23799

Дата направления статьи в редакцию:

06-08-2017


Дата публикации:

17-09-2017


Аннотация: В данной статье рассматривается вопрос повышения производительности при обработке больших объемов информации в хранилищах данных. Основной целью является увеличение скорости выполнения процесса вытеснения информации в кэш-памяти хранилищ данных, и, следовательно, скорости обработки кэшируемых данных. В качестве предмета исследования выступают алгоритмы вытеснения данных LRU1 и LRU2 и структурная организация управляющей таблицы. В статье предлагается реализация алгоритмов вытеснения информации в кэш-памяти хранилища данных на основе ассоциативного массива данных. Приводятся результаты сравнительного анализа основных алгоритмов вытеснения информации, используемых в оперативной памяти вычислительных систем (LRU, LFU, FIFO, Random). Представлены результаты разработки алгоритмов ускоренного вытеснения информации в кэш-памяти хранилищ данных. Построены системы канонических уравнений для данных алгоритмов. Применяемая математическая модель является исполнимой формализованной спецификацией, которая позволяет осуществить непосредственный переход от СКУ (системы канонических уравнений) к дальнейшей аппаратной или программной реализации предложенных алгоритмов.


Ключевые слова:

хранение данных, обработка информации, хранилища данных, кэширование, алгоритмы вытеснения данных, алгоритм LRU, алгоритм MRU, алгоритм ARC, системы канонических уравнений, автоматные модели

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

Abstract: This article concerns the issue of improving performance when processing large amounts of information in data warehouses (storages). The main purpose is to increase the speed of the process of wiping out information in the cache of data warehouses, and, consequently to improve the processing speed of the cached data. The subject of research involves the algorithms of data extortion LRU1 and LRU2, as well as and structural organization of the control table. The article proposes the implementation of algorithms for wiping out information in the data warehouse cache on the basis of an associative data array. The results of a comparative analysis of the basic algorithms of information displacement used in the operational memory of computer systems (LRU, LFU, FIFO, Random) are presented in this article. The results of the development of algorithms for accelerated information extrusion in the cache of data warehouses are also presented. The author construes the systems of canonical equations for these algorithms are. The  mathematical model, which is used by the author,  is an executable formalized specification allowing for a direct transition from the DCS (the system of canonical equations) to the further hardware or software implementation of the proposed algorithms.


Keywords:

automatic models, data processing, ARC algorithm, MRU algorithm, LRU algorithm, data wiping algorithms, caching, storages, systems of canonical equations, data storage

Введение

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

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

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

Анализ алгоритмов вытеснения информации

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

Таблица 1

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

Алгоритмы

LRU (Last Recently Used - "Наиболее давно используемый")

LFU (Least Frequently Used - "Наиболее часто используемый")

FIFO (FIRST IN, FIRST OUT - "Первым пришел, первым ушел")

Random ("Случайный")

Принцип работы

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

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

Заменяется блок данных, дольше всего находившийся в кэш-памяти

Замещаемый блок данных выбирается случайным образом

Использование дополнительных бит

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

Используется счётчик обращений, обновляемый при каждом удачном запросе

Используется счётчик времени

Не предполагает каких-либо счётчиков

Недостатки

Требуется много времени на поиск нужного блока

Алгоритм вообще не учитывает «возраст» блоков

Много обращений к блоку за короткое время => зависание блока в кэше

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

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

В вычислительных системах чаще всего используется алгоритм вытеснения информации 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 представлена структура разработанной информационной управляющей таблицы.

67_05

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

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

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

68

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

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

Таблица 2

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

Вершина укрупненной ГСА, Si

Номера составляющих вершин

S0

Начало

S1

51 - 55

X1

56

S2

57

X2

58, 59

X3

60

S6

61, 62

S5

63

S7

64 - 67

S8

68 - 70

X4

71

S9

72

S10

73 - 75

S11

76, 77

Sk

Конец

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

69

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

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

S0(t+1) = S0(t)&Øx0(t) Ú xbegin(t);

S1(t+1) = S0(t)& x0(t) Ú S1(t)&Øz1(t);

S2(t+1) = S1(t)&z1(t)&x1(t) Ú S2(t)&z2(t)&x1(t) Ú S2(t)&Øz2(t);

S3(t+1) = S1(t)&z1(t)&Øx1(t) Ú S2(t)&z2 (t)&Øx1(t) Ú S3(t)&Øz3(t);

S4(t+1) = S3(t)&z3(t)&x2(t) Ú S4(t)&Øz4(t);

S5(t+1) = S4(t)&z4(t)&x3(t) Ú S5(t)&Øz5(t);

S6(t+1) = S4(t)&z4(t)&Øx3(t) Ú S6(t)&Øz6(t);

S7(t+1) = S5(t)&z5(t) Ú S6(t)&z6(t) Ú S7(t)&Øz7(t);

S8(t+1) = S3(t)&z3(t)Øx2(t) Ú S8(t)&Øz8(t);

S9(t+1) = S8(t)&z8(t)&x4(t) Ú S9(t)&z9(t)&x4(t) Ú S9(t)&Øz9(t);

S10(t+1) = S8(t)&z8(t)&Øx4(t) Ú S9(t)&z9(t)&Øx4(t) Ú S10(t)&Øz10(t);

S11(t+1) = S10(t)&z10(t) Ú S7(t)&z7(t) Ú S11(t)&Øz11(t);

Sk(t+1) = S11(t)&z11(t) Ú Sk(t)&Øzk(t),

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

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

Выводы

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

Библиография
1. Huawei OceanStor 6800-V3 SPC-1 executive summary [Electronic resource]. – URL: http://www.storageperformance.org/benchmark_results files/SPC-1/Huawei/A00149_Huawei_OceanStor-6800-V3/a00149_Huawei OceanStor_6800-V3_SPC-1_executive-summary.pdf (дата обращения 19.04.2017).
2. White paper: Storage is Still Not a Commodity: an Updated Comparison of High End Storage Subsystems of 9 August 2009 by Josh Krischer // Bensheim: Josh Krischer & Associates GmbH.-24p.
3. Палташев, Т.Т. Иерархия памяти в современных микропроцессорах / Т.Т. Палташев, М.В. Матвеев.-Санкт-Петербург: НИУ ИТМО, 2012.-133 с.
4. Meddigo, N. Outperforming LRU with an AdaptiveReplacement Cache Algorithm [Electronic resource] / N. MEddigo, S. Modha // Research feature.IEEE Computer Society. – 2004. – URL: http://www.cs.cmu.edu/~15-440/READINGS/megiddo-computer2004.pdf (дата обращения 19.02.2017).
5. Chenessy John, L. Computer Architecrure Quantitive Approach, fourth edition / L. Chennesy John, A. Patterson David. – Berkeley: Morgan Kaufmann Publishers, 2007. – 676 p.
6. Intel® 64 and IA-32 Architectures Software Developer’s Manual [Electronic resource]. – URL: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf (дата обращения 01.02.2017).
7. Qureshi, M.K. Utility-Based Cache Partitioning: A Low-Overhead, High-Performance, Runtime Mechanism to Partition SharedCaches / M.K. Qureshi, Y.N. Patt // Proc. of the 39th Annual IEEE/ ACM Intern. Symp. on Microarchitecture (MICRO 39). Washington, DC, USA:IEEE Comp. Soci., 2006. – Р. 423-432.
8. CacheCOW: QoS for storage system caches / P. Goyal, D. Jadav, D.S. Modha, R. Tewari // Proc. of the 11th Intern. Conf. on Quality of Service (IWQoS'03). – Berlin: Springer-Verlag, 2003. – Р. 498-515.
9. Сибиряков, М.А. Модификация и моделирование алгоритмов обработки данных в кэш-памяти систем хранения данных / М.А. Сибиряков, Е.С. Васяева // Кибернетика и программирование: электронный журнал. – М: NOTA BENE, 2016. – № 4. – С. 44-57.
10. Вашкевич Н.П. Выразительные возможности и эффективность формального языка, построенного на основе использования моделей недетерминированных автоматов // Известия высших учебных заведений. Поволжский регион. Технические науки.-2006.-№ 6.-С. 67-77.
11. Вашкевич Н.П., Зубков В.А. Алгоритм синтеза цифровых автоматов Мура с использованием языка исчисления предикатов // Вычислительная техника: Учебные записки. – Вып. 3. Пенза: Пенз. политехн. ин-т, 1969 – С. 25–36.
12. Вашкевич, Н.П. Формальные автоматные модели алгоритмов обработки кэшируемой информации / Н. П. Вашкевич, М.А. Сибиряков // Современные наукоемкие технологии. – М.: Академия Естествознания, 2016. – № 8. – Ч. 2. – С. 205-213.
References
1. Huawei OceanStor 6800-V3 SPC-1 executive summary [Electronic resource]. – URL: http://www.storageperformance.org/benchmark_results files/SPC-1/Huawei/A00149_Huawei_OceanStor-6800-V3/a00149_Huawei OceanStor_6800-V3_SPC-1_executive-summary.pdf (data obrashcheniya 19.04.2017).
2. White paper: Storage is Still Not a Commodity: an Updated Comparison of High End Storage Subsystems of 9 August 2009 by Josh Krischer // Bensheim: Josh Krischer & Associates GmbH.-24p.
3. Paltashev, T.T. Ierarkhiya pamyati v sovremennykh mikroprotsessorakh / T.T. Paltashev, M.V. Matveev.-Sankt-Peterburg: NIU ITMO, 2012.-133 s.
4. Meddigo, N. Outperforming LRU with an AdaptiveReplacement Cache Algorithm [Electronic resource] / N. MEddigo, S. Modha // Research feature.IEEE Computer Society. – 2004. – URL: http://www.cs.cmu.edu/~15-440/READINGS/megiddo-computer2004.pdf (data obrashcheniya 19.02.2017).
5. Chenessy John, L. Computer Architecrure Quantitive Approach, fourth edition / L. Chennesy John, A. Patterson David. – Berkeley: Morgan Kaufmann Publishers, 2007. – 676 p.
6. Intel® 64 and IA-32 Architectures Software Developer’s Manual [Electronic resource]. – URL: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf (data obrashcheniya 01.02.2017).
7. Qureshi, M.K. Utility-Based Cache Partitioning: A Low-Overhead, High-Performance, Runtime Mechanism to Partition SharedCaches / M.K. Qureshi, Y.N. Patt // Proc. of the 39th Annual IEEE/ ACM Intern. Symp. on Microarchitecture (MICRO 39). Washington, DC, USA:IEEE Comp. Soci., 2006. – R. 423-432.
8. CacheCOW: QoS for storage system caches / P. Goyal, D. Jadav, D.S. Modha, R. Tewari // Proc. of the 11th Intern. Conf. on Quality of Service (IWQoS'03). – Berlin: Springer-Verlag, 2003. – R. 498-515.
9. Sibiryakov, M.A. Modifikatsiya i modelirovanie algoritmov obrabotki dannykh v kesh-pamyati sistem khraneniya dannykh / M.A. Sibiryakov, E.S. Vasyaeva // Kibernetika i programmirovanie: elektronnyi zhurnal. – M: NOTA BENE, 2016. – № 4. – S. 44-57.
10. Vashkevich N.P. Vyrazitel'nye vozmozhnosti i effektivnost' formal'nogo yazyka, postroennogo na osnove ispol'zovaniya modelei nedeterminirovannykh avtomatov // Izvestiya vysshikh uchebnykh zavedenii. Povolzhskii region. Tekhnicheskie nauki.-2006.-№ 6.-S. 67-77.
11. Vashkevich N.P., Zubkov V.A. Algoritm sinteza tsifrovykh avtomatov Mura s ispol'zovaniem yazyka ischisleniya predikatov // Vychislitel'naya tekhnika: Uchebnye zapiski. – Vyp. 3. Penza: Penz. politekhn. in-t, 1969 – S. 25–36.
12. Vashkevich, N.P. Formal'nye avtomatnye modeli algoritmov obrabotki keshiruemoi informatsii / N. P. Vashkevich, M.A. Sibiryakov // Sovremennye naukoemkie tekhnologii. – M.: Akademiya Estestvoznaniya, 2016. – № 8. – Ch. 2. – S. 205-213.