Chord: Знаходження будь-якого ключа в мережі P2P за O(log n) хопів

Проблема: знайти один ключ серед мільйонів учасників, без каталогу

P2P мережа не має центрального сервера для запиту "хто володіє ключем X?" — це просто відтворювало б єдину точку відмови, яку P2P намагається уникнути. Розподілена хеш-таблиця вирішує цю проблему, надаючи кожному вузлу та кожному ключу позицію в одному адресного простору та детерміноване правило щодо того, хто відповідає за певні ключі, щоб будь-який вузол міг знайти власника будь-якого ключа без каталогу, використовуючи лише локальні знання та обмежену кількість хопів.

Chord, опублікований Stoica, Morris, Karger, Kaashoek і Balakrishnan в MIT у 2001 році, є найчистішим з класичних дизайнів DHT (разом із Pastry, Kademlia та CAN). Вся його структура базується на одній ідеї: хешуйте все — IP-адреси вузлів і назви ключів тощо — за допомогою послідовної хеш-функції (SHA-1 у початковій статті) на одному круговому ідентифікаційному кільці розміром 2^m.

Кількість та правило наступника

Після того, як кожен вузол і ключ мають m-бітове ідентифікатор на кільці 0..2^m-1, володіння слідує за одним правилом: ключ k належить до першого вузла, чий ідентифікатор дорівнює або йде безпосередньо після k, рухаючись за годинниковою стрілкою — це називається наступником ключа k, позначений successor(k). Це єдине детерміноване правило є всією специфікацією «хто володіє чим»; немає необхідності вести переговори або досягати згоди.

ring size = 2^m               (m = 160 with SHA-1, in the original paper)
nodeID    = hash(IP address)
keyID     = hash(key name)
owner(key) = the first node whose ID >= keyID, walking clockwise around the ring
             (wrapping past 2^m-1 back to 0 if necessary)

Базовий маршрут правильний, але повільний

Якщо кожен вузол знав лише свого безпосереднього наступника на кільці, ви могли б знайти будь-який ключ — просто йти по колу, від вузла до вузла, запитуючи «Чи володієте ви цим ключем?» — але це O(n) переміщень для n вузлів, що марно в реальних масштабах: мережа з мільйону вузлів потребувала б до мільйона повідомлень для вирішення одного пошуку.

Пальцеві таблиці: трюк O(log n)

Внесок Chord полягає в пальцевій таблиці: кожен вузол підтримує до m покажчиків, де i-й палець вказує на наступника (nodeID + 2^(i-1)) mod 2^m. Простіше кажучи, вузол зберігає спрощений доступ приблизно до чверті кола, восьмі частини, шістнадцять та так далі вниз до свого безпосереднього сусіда — подвоюючи відстані, точно як покажчики в skip list або рівні бінарного пошуку.

finger[i] = successor( (nodeID + 2^(i-1)) mod 2^m ) для i = 1..m // lookup(ключ) у вузлі n: якщо ключ знаходиться між n та наступником n: повертати наступника n // знайдено інакше: відправити запит до пальця, найдалі попереду ключа // найбільший стрибок, який не перемахне (цей вузол повторює той самий принцип) Кожен стрибок принаймні вдвічі зменшує залишкову відстань навколо кола до цільового ключа, оскільки обраний палець є найближчим попередільним вузлом до цільового серед усіх O(log n) кандидатів — отже, кількість стрибків для вирішення будь-якого пошуку становить O(log n), і кожен вузол повинен зберігати лише O(log n) стан маршрутизації замість того, щоб знати про всі інші вузли в мережі. Для мережі з мільйоном вузлів це приблизно 20 стрибків замість до мільйона — різниця між пошуком, який вирішується за мілісекунди, та тим, що не вирішується протягом людського життя.

finger[i] = successor( (nodeID + 2^(i-1)) mod 2^m )   for i = 1..m

// lookup(key) at node n:
if key is between n and n.successor:  return n.successor        // found it
else:  forward the query to the finger farthest before key      // biggest jump that doesn't overshoot
        (that node repeats the same rule)

Ноди постійно приєднуються та покидають мережу — це нормальний випадок, а не виняток

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

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

Послідовне хешування: чому лише O(1/n) ключів змінюється при додаванні вузла

Властивість, яка робить Chord (та послідовне хешування загалом) привабливою порівняно з простим хеш-табличним представленням, розбитими на n серверів, полягає в тому, що відбувається, коли n змінюється. З звичайним модульним хешем — server = hash(key) mod n — додавання або видалення одного сервера змінює цільову адресу майже кожного ключа, оскільки n змінилося в знаменнику. У послідовному хеш-кілі, вузол, що додається, лише бере на себе безперервний сегмент ключів між собою та своїм новим поперемінцем — всі інші не змінюють володіння. Очікувана зміна ключа при додаванні або видаленні вузла становить O(1/n) від загального простору ключів, а не O(всі), що є основною причиною придатності DHT для систем, які регулярно додають і видаляють обсяг.

Де знаходиться це, крім обміну файлами

Ідеї Chord є прямим предком виробничих систем, які використовують більшість інженерів без урахування DHT; Amazon Dynamo (і, як наслідок, Cassandra та Riak) використовує узгоджене хешування на основі кільця для розподілу даних; бібліотеки клієнтів memcached використовують узгоджене хешування для визначення, який сервер кешу володіє певною ключовою інформацією; режим відстеження BitTorrent без відстежувача працює на Kademlia, сестринській DHT з дещо іншою (XOR) метрикою відстані, але однаковою ідеєю O(log n) маршрутизації. Конкретні механіки кільця та таблиці пальців варіюються, але основна компромісна частина — обмежена маршрутна стадія, логарифмічні стрибки, мінімальний збої при змінах членства — це одна й та сама проблема, яку спочатку вирішив Chord чисто і зрозуміло.

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

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

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