Що таке Distributed Hash Table?
Сьогодні ми поговоримо про таку цікаву структуру даних, як розподілена хеш-таблиця (distributed hash table або коротко - DHT).
Для тих, хто хоче нагадати собі, що таке hashing - тут можна знайти корисну інформацію.
Що таке DHT? Навіщо вона потрібна?
Які задачі вирішує DHT?
- Пошук даних у розподіленій системі
- Захист даних від атаки на єдину точку відмови
В яких умовах працює DHT?
- дані розподілені між вузлами в розподіленій системі
- кількість вузлів потенційно не обмежена
- вузли не довіряють один одному
- кожен вузол може підтримувати зв'язок з обмеженою кількістю інших вузлів
З чого складається DHT?
Кожен вузол в системі має унікальний ідентифікатор (nodeId) та адресу (address) в мережі. Крім того, на вузлі зберігаються дані, доступні для пошуку в системі.
Доступні дані та адреси інших вузлів зберігаються у вигляді таблиці на кожному вузлі. Ключами є хеш значення від nodeId або самого контенту.
Перед тим, як почати роботу, новий вузол повинен мати необхідну програму для роботи з DHT та адресу хоча б одного вузла в системі. Тільки-но програма починає свою роботу, на новому вузлі створюється таблиця з хешами та даними.
Крім того, коли вузол починає комунікувати з іншим новим вузлом в системі - від nodeId обчислюється хеш значення та вноситься у таблицю. Теж саме стосується кожного нового контенту.
З часом, таблиця на вузлі автоматично оптимізується (коли її розмір наближається до максимального). Після оптимізації - на вузлі будуть зберігатися дані, хеши який максимально схожі.
Як виконується пошук даних у DHT?
Для пошуку контенту, потрібно знати тільки його хеш.
- Пошук контенту виконується на одному вузлі.
- Якщо контенту не знайдено - з таблиці обирається хеш вузла, який найбільш наближений до того, що ми шукаємо.
- Далі пошук по хешу виконується на вузлі, який ми обрали на кроці 2.
Таким чином. пошук даних виконується досить ефективно та швидко.