АСПЕКТЫ РЕАЛИЗАЦИИ РАСПРЕДЕЛЕННЫХ ХРАНИЛИЩ ДАННЫХ В ОПЕРАТИВНОЙ ПАМЯТИ

ASPECTS OF IN-MEMORY DATA GRIDS IMPLEMENTATION

Oleh Buzovskyi

master of Science, Professor of National technical university of Ukraine

“Kyiv polytechnic institute”,

Ukraine, Kyiv

Oleksandr Podrubailo

assistant of National technical university of Ukraine

“Kyiv polytechnic institute”,

Ukraine, Kyiv

Oleksii Lypnytskyi

student of National technical university of Ukraine

“Kyiv polytechnic institute”,

Ukraine, Kyiv

АННОТАЦИЯ

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

ABSTRACT

This article provides an overview of in-memory data grid technology, as well as an analysis of the shortcomings of existing implementations of such systems. Approaches to address deficiencies are considered.

Ключевые слова: база данных; распределенное хранилище данных в оперативной памяти; распределенное объединение таблиц; транзакционная память.

Keywords: database; in-memory data grid; distributed join; transactional memory.

Современные информационные технологии требуют наличия надежных, быстрых и удобных, при этом достаточно емких, средств хранения информации. Распределенные хранилища данных в оперативной памяти (In-memory data grid, IMDG) потенциально способны удовлетворить этим требованиям.

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

Однако, в силу своей относительной новизны, технология распределенных хранилищ в оперативной памяти обладает рядом недостатков [1]. В частности, к ним относятся энергозависимость, возможность переполнения памяти в силу ее ограниченного объема, отсутствие поддержки распределённых объединений таблиц. Указанные недостатки существенно ограничивают функциональные возможности хранилищ по поиску данных. Кроме того, использование механизма транзакций в IMDG существенно снижает скорость выполнения операций с хранилищем.

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

Отсутствие поддержки механизма распределенных объединений таблиц в IMDG является актуальной проблемой. В большинстве распределенных баз данных на долговременных запоминающих устройствах для соединения таблиц используется Grace-алгоритм соединения хэшированием [6; 8]. Особенностью этого алгоритма является разбиение входных таблиц на части (партиции) с последующей записью их на диск, и последовательным чтением. Очевидно, что данный алгоритм неэффективен для хранилищ в оперативной памяти. Применительно к IMDG, за основу можно взять алгоритм гибридного соединения хэшированием, являющийся модификацией Grace-алгоритма. Гибридное соединение предусматривает хранение партиций в оперативной памяти, причем, во избежание переполнения памяти предусмотрена запись части партиций на диск. Такой подход позволяет, при наличии достаточного количества свободной памяти, выполнять соединение таблиц без использования медленных устройств. С другой стороны, при высокой интенсивности операций соединения или при дефиците памяти будет использовано устройство долговременного хранения, что позволит обработать запрос даже при недостатке ресурсов. Однако соединение хэшированием далеко от оптимального использования сетевых ресурсов, так как при этом способе обе таблицы-операнда передаются по сети практически полностью [9]. Использование предопределенных хэш-функций гарантирует балансировку нагрузки, но ограничивает вероятность того, что хэшированный кортеж не будет передан по сети до 1/N, где N – количество узлов распределенного хранилища. О. Полихрониу, Р. Сен и К. Росс в [9] представили алгоритм путевого соединения (track join), минимизирующий количество пересылок кортежей по сети. Основная идея этого алгоритма состоит в определении цели отправки каждого конкретного кортежа. Алгоритм путевого соединения существенно снижает использование сетевых ресурсов по сравнению с другими известными методами выполнения соединений распределенных таблиц. Однако он ориентирован на использование в традиционных базах данных, где хранимые кортежи строго типизированы и фактический объем хранимых данных в разных строках одной таблицы отличается несущественно. В отличие от них, IMDG хранят объекты, способные, в свою очередь, содержать другие объекты. Таким образом, объем хранимых данных в разных кортежах одной таблицы может отличаться на несколько порядков (а, теоретически, эта разница может быть и больше). Поэтому простой подсчет количества пересылаемых кортежей, используемый алгоритмом путевого соединения для оценки использования сетевых ресурсов, применительно к распределенным хранилищам в оперативной памяти не дает объективной количественной оценки объема пересылаемых данных. В [2] описан алгоритм модифицированного путевого соединения, позволяющий количественно оценить и минимизировать фактический объем пересылаемых по сети данных при выполнении соединения распределенных таблиц IMDG.

Снизить подверженность теореме Брюэра в распределенных документ-ориентированных хранилищах можно путем модификации механизма индексирования, как это описано, например, в [3].

Падение производительности при использовании транзакций в современных IMDG обусловлено использованием блокировок. Их применение накладывает существенные ограничения на многопоточную работу с данными.

Альтернативой блокировкам в этом случае может выступить использование транзакционной памяти (transactional memory, TM). Так как к IMDG выдвигаются требования по устойчивой работе в гетерогенных распределенных системах, целесообразнее рассматривать программную транзакционную память (software transactional memory, STM), т. к. прочие подходы к реализации ТМ накладывают существенные ограничения на аппаратную составляющую системы.

Концепция транзакционной памяти близка к принципам ACID (atomicity, consistency, isolation, durability), лежащим в основе большинства современных баз данных. Тем не менее, ТМ не применяется в современных реализациях распределенных хранилищ в оперативной памяти. Напротив, трудности с использованием транзакций привели к появлению новой идеологии BASE (basically available, soft-state, eventually consistent) [10], предлагающей считать временную недоступность данных и частичную неконсистентность информации в распределенной системе нормальным поведением такого класса систем.

Традиционной областью применения транзакционной памяти считаются системы с общей памятью, но в [5] и [11] предложены распределенные модели STM, демонстрирующие применимость этой технологии в распределенных системах.

В современных IMDG не используется транзакционная память, однако в некоторых простейших системах кеширования (MemC3) реализован оптимистичный подход к изменению данных [12]. В [7] предложено вынести контроль над транзакциями на уровень промежуточного приложения (middleware) с использованием STM, однако такой подход имеет ряд существенных ограничений, как-то низкая отказоустойчивость, ограниченная доступность и высокие накладные расходы на работу промежуточного слоя. Исследование влияния программной транзакционной памяти на производительность хранилищ класса IMDG выполнено в [4].

Вывод

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

Список литературы:

1. Бузовский О.В., Подрубайло А.А. Актуальные проблемы распределенных хранилищ данных в оперативной памяти. // Вісник Національного авіаційного університету. Проблеми інформатизації та управління. – 2015 – № 2 (50) 2015 – С. 36–43.
2. Бузовский О.В., Подрубайло А.А. Методы и алгоритмы объединения таблиц для распределенных хранилищ данных в оперативной памяти. // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. – К.: Век+, – 2014. – № 60. C. 74–83.
3. Бузовский О.В., Подрубайло А.А. Частичное преодоление САР-теоремы в распределенном документ-ориентированном хранилище данных // Вісник Національного технічного університету «ХПІ». Серія: Механіко-технологічні системи та комплекси. – 2015. – № 22. С. 38–42.
4. Подрубайло А.А. Повышение производительности хранилищ данных в оперативной памяти посредством использования программной транзакционной памяти / А.А. Подрубайло // Восточно-Европейский журнал передовых технологий. – 2015. – № 4(2). – С. 9–14.
5. Carvalho N., Romano P.A generic framework for replicated software transactional memories. // 2011 IEEE 10th International Symposium on Network Computing and Applications – 2011 – P. 271–274.
6. DeWitt D.J. et al. The Gamma database machine project. // IEEE Trans. Knowl. Data Engin., 2 (1) – 1990 – P. 44–62.
7. Fernandes S. Strongly Consistent Transactions for Enterprise Applications. Using Software Transactional Memory to Improve Consistency and Performance of Read-Dominated Workloads [Text] PhD dissertation / S. Fernandes. – Lisbon, 2014 – 208 p.
8. Kitsuregawa M., Tanaka H., and Moto-Oka T.. Application of hash to data base machine and its architecture. // New Generation Computing – 1983 – P. 63–74.
9. Polychroniou O., Sen R. and Ross K. Track join: distributed joins with minimal network traffic. // SIGMOD Conference – 2014 – P. 1483–1494.
10. Pritchett D. Base: an acid alternative.// Queue, 6 (3), – 2008 – P. 48–55.
11. Saad M., Ravindran B. HyFlow: a high performance distributed software transactional memory framework. // Proceedings of the 20th international symposium on High performance distributed computing – HPDC '11 – 2011 – P. 265–266.
12. Zhang H., Chen G., Ooi B. C., Tan K.-L., Zhang M. In-Memory Big Data Management and Processing: A Survey. // IEEE Transactions on Knowledge and Data Engineering, 27 (7) – 2015 – P. 1920–1948. doi: 10.1109/tkde.2015.2427795.