Аналіз методів об’єднання таблиць у розподілених сховищах даних в оперативній пам’яті



Стаття | Article    

Download

Доповідь присвячена аналізу методів об’єднання розподілених таблиць з метою їх застосування в розподілених сховищах даних в оперативній пам’яті. Визначено фактори, що відрізняють об’єднання в розподілених сховищах даних в оперативній пам’яті від аналогічної операції в сховищах іншого класу. Розглянуті алгоритми порівнювались за об’ємом пересилок та часом виконання. Розроблено програмне середовище для моделювання операцій об’єднання в таких системах.

Ключові слова: розподілене сховище в оперативній пам’яті, розподілене об’єднання, об’єднання хешуванням, фільтри Блума, шляхове об’єднання, модифіковане шляхове об’єднання

Analysis of join methods in in-memory data grids

This report is devoted to the analysis of distributed join methods for their use in in-memory data grids. Identified factors that distinguish the join in IMDG comparatively to similar operation in the storage systems of another class. The algorithms were compared by transmission volume and computation time. Developed software environment for modelling of join operations in such systems.

Keywords: in-memory datagrid, distributed join, hash join, track join, bloom join, modified track join

Oleksandr Podrubailo (assistant at NTUU “KPI”)

Yaroslav Lukyanenko (student at NTUU “KPI”)

Kyiv, Ukraine

На сьогодні все більшої популярності набувають розподілені сховища даних в оперативній пам’яті (In-memory data grid, IMDG). Зберігаючи інформацію безпосередньо в основній пам’яті комп’ютерів, такі системи надають суттєву перевагу користувачам, оскільки забезпечують високу швидкість доступу до даних. Через особливості фізичної організації оперативної пам’яті, найвищої швидкодії сховища в оперативній пам’яті досягають при читанні інформації по асоціативному ключу. Однак для повноцінного застосування систем класу In-memory data grid виключно читання за ключем замало. Сценарії використання існуючих сховищ даних передбачають також об’єднання таблиць. Існуючі реалізації IMDG не мають такої функціональності, або вона реалізована дуже неефективно, щопризводить до суттєвого падіння швидкості доступу до даних у багатьох сценаріях. При цьому операція об’єднання виконується на стороні клієнта, що знижує швидкодію системи до швидкодії мережевого з’єднання.

Ця доповідь присвячена аналізу методів об’єднання розподілених таблиць з метою оцінки їх застосовності у розподілених сховищах даних в оперативній пам’яті. Дослідження зосереджено на внутрішньому симетричному об’єднанні за ознакою рівності ключа в розподілених таблицях.

IMDG являє собою набір розподілених асоціативних масивів (таблиць, регіонів), розміщених на певній множині серверів у мережі. Дані в таблицях представлені в об’єктно-орієнтованій формі. Зазвичай, для забезпечення надійності та відмовостійкості системи, застосовується реплікація даних на декілька вузлів кластеру. Тобто можна виділити наступні фактори, важливі для розподіленого об’єднання:

$1.$ Оскільки ключем об’єднання не є первинний ключ таблиці, відсутня можливість аналітично визначити множину вузлів системи, що зберігають певний ключ об’єднання.

$2.$ Записи у вигляді об’єктів не мають фіксовану довжину. Маючи довільний рівень вкладеності, розмір різних записів в одній таблиці може суттєво відрізнятися.

$3.$ Швидкість передачі даних мережею на декілька порядків менша, ніж швидкість читання даних з оперативної пам’яті. Тобто ефективнішим буде алгоритм, що зменшить кількість пересилок, навіть шляхом більшої кількості операцій читання\запису з основної пам’яті.

$4.$ Реплікація даних означає, що множини даних, які зберігають різні вузли сховища, мають ненульовий перетин. Це потенційно надає можливість обирати вузли, що прийматимуть участь в об’єднанні, і, таким чином, мінімізувати об’єм пересилок.

Виходячи з вищевказаного, аналіз методів об’єднання відбувався за наступними критеріями:

$1.$ Об’єм пересилок даних (байт)

$2.$ Найбільший час виконання алгоритму на окремому вузлі (мс)

$3.$ Складність реалізації алгоритму в існуючих розподілених сховищах (якісна характеристика)

Аналіз виконувався на основі експериментальних досліджень. Для виконання експериментів була розроблена програмна модель розподіленого сховища даних в оперативній пам’яті, що дозволяє оцінити швидкодію різних методів розподіленого об’єднання. Алгоритми реалізовані у вигляді окремих класів. Система легко розширюється шляхом додавання нових класів з реалізаціями алгоритмів об’єднання.

Для моделювання були виділені наступні параметри:

$1.$ Відношення об’ємів даних у таблицях, що приймають участьв об’єднанні. (У кількостях записів)

$2.$ Закон розподілення розмірів записів у таблицях (константний, лінійний, Гауса, Ерланга). Різний розмір запису зумовлений кількістю рекурсивних вкладень в об’єкт-запис.

$3.$ Пропускна здатність мережі (біт\с)

$4.$ Затримка мережі (мс)

$5.$ Кількість вузлів

$6.$ Ступінь реплікації

Приклад роботи програми моделювання представлений на рис.1

Рис. 1 Результат роботи системи моделювання

В даній роботі аналізувалися наступні алгоритми розподіленого об’єднання:

$1.$ Hash join

Хеш-з'єднання виконується в дві стадії: компоновка та проба. Під час компонування здійснюється читання всіх рядків першого вхідного потоку (часто, його називають лівим потоком або потоком компонування), хешування рядків по ключам з'єднання еквівалентності і створення в оперативній пам'яті хеш-таблиці. [1] Під час проби здійснюється читання всіх рядків другого вхідного потоку (часто його називають правим потоком або пробним потоком), хешування рядків цього потоку по тим же ключам з'єднання еквівалентності, а потім здійснюється перегляд або пошук відповідників рядків в хеш-таблиці. Так як хеш-функції можуть бути схильні до колізій (два різних значення ключа мають однаковий хеш), доводиться перевіряти кожне потенційне відповідність, що необхідно для гарантії того, що в цьому випадку дійсно схожість зумовлена з'єднанням, а не колізією.

$2.$ Bloomjoin

Цей алгоритм традиційно використовується для ефективного обміну даними між вузлами кластера.[2] Ймовірнісна структура даних, котра називається фільтр Блума, дозволяє перевірити належність елемента множині. При цьому існує можливість отримати хибнопозитивні спрацьовування (елемента в множині немає, але структура даних повідомляє, що він є), але не псевдонегативні. Фільтр Блума може використовувати будь-який обсяг пам'яті, заздалегідь заданий користувачем, причому чим він більший, тим менша ймовірність помилкового спрацьовування.

$3.$ Trackjoin

Метод шляхового об'єднання (track-join), мінімізує кількість пересилань кортежів помережі. [3] Основна ідея цього методу полягає у визначенні мети відправки кожного конкретного кортежу. Метод шляхового об'єднання істотно знижує використання мережевих ресурсів у порівнянні з іншими відомими методами виконання об'єднань розподілених таблиць. Однак він орієнтований на використання в традиційних базах даних, де зберігаються кортежі строго типізовані і фактичний обсяг збережених даних в різних рядках однієї таблиці відрізняється несуттєво.

$4.$ Modifiedtrack join

Модифікований алгоритм шляхового об’єднання приймає до уваги розмір кожного запису у сховищі [4], підвищуючи ефективність об’єднання в умовах, коли розміри записів в одній таблиці сильно відрізняються один від одного.

Перелік посилань

$1.$ C. Balkesen et al. Multicore, main-memory joins: Sort vshash revisited.// PVLDB, 7(1)­– Sept. 2013 ­– p.85-96.

$2.$ M.-C. Albutiu, A. Kemper, and T. Neumann. Massively parallel sort-merge joins in main memory multi-core database systems. // PVLDB, 5(10) –2012 – p.1064-1075.

$3.$ O. Polychroniou, R. Sen and K. Ross. Track join: distributed joins with minimal network traffic. // SIGMOD Conference – 2014 – p. 1483-1494.

$4.$ Бузовский О.В., Подрубайло А.А. Методы и алгоритмы объединения таблиц для распределенных хранилищ данных в оперативной памяти. // Вісник НТУУ «КПІ». Інформатика, управління та обчислювальна техніка: Зб. наук. пр. – К.: Век+, – 2014. – № 60.C.74-83

May 18, 2017