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

XOR Відстань як Метрика

Основою Kademlia є функція відстаней, визначена над ідентифікаторами вузлів, які зазвичай становлять 160 або 256 біт, згенеровані випадковим чином або похідні від публічного ключа. Відстань між двома ідентифікаторами A та B просто дорівнює A XOR B, інтерпретованому як незмінне ціле число. Ця одна операція дає Kademlia все необхідне: вона симетрична, тобто відстань від A до B завжди дорівнює відстані від B до A, оскільки XOR також є симетричним. Вона також задовольняє нерівність трикутника, що означає, що відстань від A до C ніколи не перевищує суму відстані від A до B плюс відстань від B до C. Ці дві властивості мають величезне значення в практиці. Симетрія означає, що коли вузол дізнається про контакт через вхідне запит, зв'язок є значущим у обох напрямках, що і дозволяє правильно працювати пасивним оновленням таблиць маршрутизації. Нерівність трикутника означає, що простір відстаней поводиться досить як звичайна геометрична відстань, щоб вузли могли розумно міркувати про те, які контакти наближають їх до цілі, без жодного контакту, який здається оманливо неправдоподібним. На відміну від таких методів, як порівняння ID чи кількісне використання відстаней по колу, як у деяких інших дизайнах DHT, XOR відстань є односторонньою та унікальною: для будь-якого вузла A та будь-якої цільової відстані d існує лише один вузол B, такий що A XOR B дорівнює d. Ця унікальність дозволяє чітко розділити простір ідентифікаторів на діапазони відстаней без двозначності. Кожен вузол ефективно бачить себе як центр всього простору ідентифікаторів, з усіма іншими вузлами та ключами розташованими на певній, добре визначеній XOR відстані від нього. Оскільки ідентифікатори призначаються практично випадковим чином у величезному просторі, більшість пар вузлів знаходяться далеко один від одного, а лише невелика частина випадково знаходиться близько до будь-якого заданого вузла або ключа, що є точно тією властивістю, яку використовують для побудови k-bucketів.

K-Buckets і маршрутний план

Клієнт Кадельмії не намагається запам'ятати кожен інший вузол у мережі. Замість цього він підтримує маршрутну таблицю, побудовану як список k-buckets, один для кожного положення біта в просторі ідентифікаторів. Bucket i містить контакти, чий XOR-відстань від цього вузла знаходиться між двома степенями числа i та двома степенями числа i+1, а кожен bucket зберігає до k контактів, зазвичай 20 у реальних розгортаннях. Оскільки ідентифікатори є в основному випадковими, приблизно половина всіх інших вузлів потрапляє в дуже останній bucket, чверть - у другий з останніх, восьма - в той, що попереду, і так далі, тому buckets, які охоплюють великі відстані, потребували б величезної кількості контактів, якщо не було б обмеження. Обмеження k підтримує межі пам'яті: вузол радісно заповнює bucket 159 лише 20 з мільярдів потенційно відомих йому далеких вузлів, тоді як bucket 0 або bucket 1, які охоплюють вузли, що розташовані надзвичайно близько в просторі ID, можуть мати лише один або два запису просто тому, що існує так мало вузлів, які знаходяться так близько. Ця асиметрична структура є серцем ефективності Кадельмії. Вузол знає багато деталей про своє безпосереднє оточення та поступово менше деталей про регіони, що знаходяться далі, що є точною інформаційною формою, необхідною для ефективної відповіді на запити «хто найближчий до цього ключа» без глобальних знань. Buckets підтримуються в актуальному стані за допомогою політики виселення з найменшою нещодавно використаною: коли новий контакт приходить у повний bucket, вузол ping'є найстаріший запис і замінює його лише тоді, коли цей старий контакт не відповідає. Це схиляється до надійних вузлів, які давно перебувають у мережі, а не до новачків, оскільки вузли, які були онлайн протягом тривалого часу, статистично ймовірно залишаться онлайн, що природним чином спотворює мережу проти певних атак потоку, де зловмисник намагається вводити багато свіжих шкідливих контактів.

Ітеративні пошуки та логістичні стрибки

Пошук вузлів, відповідальних за ключ, передбачає ітераційний процес, який іноді називають пошуком вузла. Пошуковий вузол починається з вибору alpha найближчих контактів, які він вже знає для цільового ключа (зазвичай alpha дорівнює 3), та запитує їх паралельно, просячи кожного повернути контакти, які він знає, що є найближчими до цього ключа. Від цих відповідей пошуковий вузол будує оновлений список найкращих вузлів, які були знайдені, і повторює процес, завжди запитуючи не запрошені раніше вузли з поточного найкращого набору, поки не буде досягнуто певного результату. У цьому випадку найближчі k вузлів, знайдених, вважаються авторитетними для цього ключа. Що робить цей процес швидким, це структура, яка створюється за допомогою k-корзин: оскільки знання вузла поступово стає більш розсіяним на більших відстанях, кожен стрибок у пошуку має тенденцію перестрибувати в область корзини приблизно вдвічі меншого розміру, ніж попередня, що приблизно зменшує залишок до цільового ключа вдвічі на кожному кроці. Це забезпечує очікувану вартість пошуку, яка масштабується з логарифмом розміру мережі, а не самим розміром, тому мережа з одного мільйона учасників зазвичай вирішує пошук протягом приблизно 20 стрибків, і подвоєння розміру мережі додає лише один стрибок у середньому. Це логістичне поведінка дозволяє Kademlia масштабуватися до величезних мереж peer-to-peer, таких як BitTorrent mainline DHT, які регулярно мають мільйони одночасних учасників, при цьому підтримуючи низьку та передбачувану затримку пошуку. Паралельне запитування alpha вузлів одночасно також підвищує стійкість: якщо один контакт повільний, не в мережі або зловмисний, пошук не зупиняється, чекаючи на нього, оскільки інші паралельні гілки продовжують прогресувати до цільового ключа.

Самостійне відновлення через пасивні оновлення

Одним із найелегантніших аспектів Kademlia є те, що його таблиці маршрутизації покращуються просто як побічний ефект звичайного мережевого трафіку, без жоджої окремої процедури обслуговування. Коли вузол отримує будь-який повідомлення від іншого вузла – чи то запит, який він ініціював, відповідь на свій запит або навіть вхідний запит від іншої сторони – він використовує цю інформацію про контакт для оновлення відповідного k-bucket. Оскільки метрика XOR відстані є симетричною, повідомлення, отримане від вузла X, точно говорить отримуючому вузлу, до якого bucket належить X, і отримуючий вузол може негайно вставити або освіжити цей запис. Це означає, що популярні, часто контактувані вузли природно залишаються на передньому краї своїх bucket-ів, оскільки кожен взаємодія оновлює їхнє положення, а вузли, які мовчать, поступово старіють у часі виключення при заповненні bucket-у і необхідності його перевірки. Практичний ефект – це вид самостійного відновлення: коли вузли приєднуються, їх адреси поширюються по мережі лише завдяки запитам і відповідям, які природним чином відбуваються, а коли вузли відключаються або виходять з ладу, застарілі записи поступово видаляються, коли bucket-и отримують регулярне використання. Жодному вузлу не потрібно запускати періосний глобальний перепис, і немає координатора, який вирішує, коли оновлювати що. Для обробки bucket-ів, які рідко отримують трафік, наприклад тих, що охоплюють віддалені регіони простору ID, з якими вузол рідко має причину запитувати, Kademlia додає легку процедуру оновлення bucket-у: якщо bucket не торкався протягом певного інтервалу часу, вузол випадковим чином обирає ID в межах діапазону цього bucket-у та виконує для нього пошук, що змушує свіжу інформацію про контакт поширюватися. У поєднанні з пасивними оновленнями від звичайного трафіку це підтримує кожну частину таблиці маршрутизації відносно актуальною навіть за постійних змін, що є необхідним для реальних розгортань, таких як BitTorrent DHT, де вузли приєднуються та відключаються безперервно і непередбачувано.

Kademlia у реальному світі

Kademlia було представлено в 2002 році Петаром Маймуновіком та Девідом Мазієром, і його дизайн виявився достатньо стійким, щоб живити кілька найбільших систем peer-to-peer, що використовуються сьогодні. Основний DHT BitTorrent mainline використовує варіант Kademlia, щоб дозволити клієнтам знаходити піарів, які діляться певним torrent, не звертаючись до централізованого трекера, що робить можливими торренти без трекеру та забезпечує виявлення зграї навіть якщо трекер припиняє роботу назавжди. IPFS, InterPlanetary File System, використовує DHT на основі Kademlia під назвою libp2p Kademlia для відображення ідентифікаторів контенту – криптографічні хеші вмісту файлів – на піарів, які зараз зберігають та обслуговують цей вміст, дозволяючи мережі маршрутизувати запити «хто має цей вміст» без будь-якого центрального індексу. Ethereum використовує протокол Node Discovery Protocol (discv4/discv5), щоб піари, що приєднуються до peer-to-peer мережі, могли ефективно знаходити інших піарів для підключення та обміну блоками та транзакціями, запускаючи gossip-шар, який синхронізує блокчейн. Кожна з цих систем адаптує основні ідеї Kademlia до своїх потреб, іноді змінюючи розмір ідентифікатора, значення k або точну стратегію розділення кошика, але основна XOR-відстань маршрутизації та самовідновлювані k-кошики залишаються впізнаваними. У порівнянні з більш ранніми дизайнами DHT, такими як Chord, який організовує піари на логічному кільці та використовує таблиці пальців, або Pastry та Tapestry, які використовують дерева префіксного зіставлення, Kademlia часто віддають перевагу через його симетричну метрику, яка дозволяє елегантному пасивному навчанню, описаному раніше: звичайний трафік пошуку подвоюється як підтримка таблиці маршрутизації, що важче досягти чисто за допомогою спрямованої або несимметричної функції відстані. Це поєднання математичної простоти та практичного самовідновлення є однією з причин, чому Kademlia стала домінуючою DHT-дизайном у виробничих peer-to-peer системах програмного забезпечення.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Kademlia Distributed Hash Table і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.