Розподілена хеш-таблиця

Стиль цієї статті неенціклопедічен або порушує норми російської мови.

DHT (англ. D istributed h ash t able - «розподілена хеш-таблиця») - це клас децентралізованих розподілених систем, які забезпечують пошуковий сервіс, схожий за принципом роботи на таблицю хешів, яка має структуру асоціативного масиву. (Ключ і значення), що зберігаються в DHT, а кожен бере участь вузол може раціонально шукати значення, асоційоване з даними ключем. Відповідальність за підтримку зв'язку між ім'ям і значенням розподіляється між вузлами, таким чином зміна набору учасників є причиною мінімальної кількості розривів. Це дозволяє легко масштабувати DHT і постійно відстежувати додавання / видалення вузлів і помилки в їх роботі.

Вишукування в області DHT спочатку були мотивовані зокрема пірінговимі системами, такими, як I2P. Napster. Gnutella. Freenet. які використовували розподілені в інтернеті ресурси для створення одного єдиного додатка. Зокрема вони використовували широкосмуговий інтернет і простір на жорстких дисках для надання сервісу поширення файлів. Ці системи різняться тим, як вони знаходили дані бенкетів:

Napster мав центральний індексний сервер: кожен вузол, після приєднання, повинен відправити список локально зберігаються файлів на сервер, який повинен провести пошук і направити запит до вузлів, що містить результати. Цей центральний компонент робив систему вразливою для атак і ризиків.
Gnutella і схожі мережі рушили до моделі лавинних запитів - в основному, кожен пошук привів би до повідомлення, переданому на будь-яку машину в мережі. Уникаючи централізованого відмови, цей метод був значно менш ефективним, ніж Napster.
Нарешті, Freenet був також повністю розподіленим, але маршрутизація працює на базі евристичного ключа, в якому кожен файл має асоційований з ним ключ, а файли зі схожими ключами мали тенденцію до об'єднання в кластери на схожому наборі вузлів. Запит, швидше за все, прямував таким кластерам без потреби опитувати всіх бенкетів. Однак Freenet не міг гарантувати, що дані будуть знайдені.

DHT використовують маршрутизацію на базі більш структурованого ключа, щоб досягти децентралізації I2P. Gnutella і Freenet. а також ефективності і гарантованих результатів Napster. Один з недоліків в тому, що, як Freenet. DHT підтримує тільки пошук за точним збігом, а не за ключовими словами, хоча ці можливості можуть нашаровуватися поверх DHT.

DHT характеризується наступними властивостями:

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

Ключова методика досягнення мети полягає в тому, що будь-який вузол повинен скоординуватися тільки з декількома вузлами в системі - як правило, О (logn), де n - кількість учасників (дивись нижче) - так, щоб тільки обмежений обсяг роботи був зроблений для кожного зміни кількості учасників.

Деякі DHT-проекти прагнуть забезпечити захист від шкідливих користувачів і дозволяти учасникам залишатися анонімними, хоча це менше поширене, ніж у багатьох інших P2P-системах (особливо при поширенні файлів); см. Анонімні мережі.

Нарешті, DHT доводиться мати справу з більш традиційними розподіленими системами, такими як розподіл навантаження, цілісність даних і продуктивність (зокрема, гарантуючи, що операції, такі як маршрутизація і зберігання даних або пошук, завершуються швидко).

Структура DHT може бути розбита на кілька основних компонентів. Вона грунтується на абстрактному просторі ключів (keyspace), такому як набір 160-бітних рядків (кількість біт може варіюватися). Схема розбиття простору ключів розподіляє приналежність ключів серед беруть участь вузлів. Потім оверлейная мережа з'єднує вузли, допомагаючи знайти власника будь-якого ключа в просторі ключів.

Компоненти розбиття простору ключів і оверлейной мережі описані нижче з метою представлення основних ідей звичайних для більшості DHT систем. Багато розробок відрізняються в деталях.

Розбиття простору ключів

Більшість DHT використовують різні варіанти консистентного хеширования для відображення ключів в вузли. В основі цього способу розбиття лежить функція $\ Delta (k_1, k_2)$ , визначальна абстрактне поняття відстані між ключами $k_1$ і $k_2$ , яке не має ніякого відношення до географічної віддалі або до мережевої затримки. Кожному вузлу привласнюється одиничний ключ, званий його ідентифікатором (ID). Вузол з ID $i_n$ володіє всіма ключами $k_m$ , для яких $i_n$ - найближчий ID, обчислений за допомогою $\ Delta (k_m, i_n)$ .

Приклад. Chord DHT розглядає ключі як точки на колі, а $\ Delta (k_1, k_2)$ - це відстань, пройдену за годинниковою стрілкою по колу від ключа $k_1$ до $k_2$ . Таким чином коло простору ключів розділений на суміжні сегменти, чиї кінці є ідентифікаторами вузлів. якщо $i_1$ і $i_2$ суміжні ID, то вузол з ID $i_2$ містить всі ключі, які знаходяться між $i_1$ і $i_2$ .

Консистентні хешування має основну властивість: видалення або додавання тільки одного набору ключів, що належать вузлів суміжних ID, не впливає на інші вузли.

DHT і BitTorrent

Карта мережі BitTorrent DHT

І DHT, і PEX фактично виконують основну функцію BitTorrent-трекера - допомагають учасникам файлообміну дізнатися один про одного. Вони можуть:

Private key

У публічних (відкритих) трекерах, де кожен бажаючий може скачати торрент і брати участь в роздачі, DHT і PEX служать на благо всіх учасників.

Тоді розробники клієнтів запропонували новий ключ всередині торрент-файлу: private. Якщо він дорівнює 1, то клієнт зобов'язаний для цього торрента автоматично відключати DHT / PEX незалежно від бажання користувача. Такий торрент називають Secure Torrent.

Практично всі сучасні приватні трекери самі примусово вставляють private: 1 в усі торренти, що викладаються на трекері, а також забороняють кілька застарілих версій клієнтів, що підтримують DHT або PEX, але ще не знають про private key. Вважається, що користувачі трекера просто не можуть на роздачах використовувати DHT / PEX, і проблеми немає. Насправді ж для того, щоб не враховувався рейтинг, досить замінити свій passkey на будь-який інший. І навіть не треба його красти. Досить зареєструвати ще один обліковий запис, щоб взяти з неї passkey.

DHT і статистика

Цей розділ стосується лише закритих трекерів, на яких private key в торренти примусово вставляєте. і на деяких роздачах (в залежності від того, вставив чи роздає сам в торрент private key) можна використовувати DHT і PEX.

Часто зустрічається думка, що включений в клієнті DHT впливає на облік статистики клієнта трекером, наприклад «роздавав через DHT, значить статистика йшла повз трекера». Це не вірно.

Тобто «роздавав через DHT» фактично означає «про деякі (або про всіх) бенкетах отримав інформацію по DHT, і ймовірно деякі бенкети теж знайшли мене через DHT»

Клієнт рапортує трекеру сумарні дані про об'єми ним завантаженого і відданого всім бенкетів, з якими він спілкувався. незалежно від того, дізнався клієнт про окремі бенкетах через трекер, DHT або PEX, або той бенкет взагалі почав з'єднання сам. Тобто навіть якщо через DHT / PEX на роздачі з'являться «ліві» користувачі (що не звертаються до трекера), клієнт все одно повідомить на трекер все, що у них скачав і віддав.

Правильний облік статистики залежить тільки від стану трекера: працює трекер - статистика враховується, не працює - не враховується. Тільки в разі тривало непрацюючого трекера DHT / PEX може грати непряму роль, не даючи поступово згаснути файлообміну на такій «роздачі без урахування статистики».

Механізм роботи DHT

Реалізація розподіленої мережі в BitTorrent-клієнтах заснована на варіанті DHT, званому Kademlia. А взагалі кажучи, DHT (Distributed hash table) означає децентралізовану розподілену систему для об'єднання великої кількості постійно зникаючих вузлів і ефективної передачі повідомлень між ними. На основі структур DHT будують різні складніші системи, такі як файлообмін P2P, кооперативне веб-кешування, служби DNS і т. П.

DHT використовує протокол UDP. Клієнти BitTorrent «слухають» той же номер порту UDP, який вони використовують для вхідних TCP-з'єднання. Якщо ви активно використовуєте DHT, то відкриття цього UDP-порта для доступу зовні бажано, але не обов'язково - DHT буде працювати і так.

Кожен підключений клієнт є в мережі DHT окремим вузлом. У нього є свій унікальний ID (ідентифікатор), випадково обираний з того ж 160-бітного простору, що і infohash'і торрентів.

Кожен вузол зберігає таблицю маршрутизації, що містить контактну інформацію про багато «найближчих» до нього вузлів, і про декілька далеких. «Близькість» двох вузлів обчислюється з «подібності» їх ID, і не має ніякого відношення до їх географічної близькості.

недоліки

Існує кілька несумісних між собою протоколів, які обслуговують різні мережі.
Робота клієнта, як DHT-вузла, створює велике навантаження на маршрутизатор (роутер).
Хеші публікуються відкрито, що дозволяє інтерактивно відстежувати роздачі (чим і користуються правовласники).Researchers spy on BitTorrent users in real-time DHT Protocol Extension for Peers to Send Metadata Files
В наявної реалізації DHT створює сильний паразитний трафік на комп'ютер клієнта, оскільки повідомлення DHT продолжаютШаблон: Citation needed надсилатися клієнту навіть в тому випадку, якщо комп'ютер клієнта більше не приймає такий трафік (коли програма вимкнена).

пов'язані статті

Примітки

Схожі статті

Створення розподілених архівів