Граф Пропусків: Децентралізований Пошук із Впорядкуванням для Мереж P2P

Від списків пропуска до графів пропуска

Класичний список пропуска – це структура даних на одній машині: один процес утримує відсортований зв’язний список елементів і випадково підвищує деякі елементи на вищі ‘швидкісні смуги’, щоб пошук міг пропустити великі частини списку замість того, щоб проходити по одному вузлу за раз. Висота вежі кожного елемента обирається випадковим чином, зазвичай шляхом підкидання монетки та зупинки на першому хвостику, що дає очікувану логарифмічну кількість рівнів загалом і очікуваний логарифмічний пошуковий витрат. Граф пропуска ставить складніше питання: що, якщо немає жодної машини, яка утримує список, а кожен елемент – окремий комп’ютер у мережі, який відповідає лише за себе? Немає центрального будівельника, який вирішує висоти веж або з’єднує рівні. Замість цього кожен вузол незалежно генерує свій власний випадковий вектор членства – рядок випадкових цифр (часто біт), повністю самостійно, без координації чи комунікації для його створення. Ця одна випадкова величина локального джерела визначає всю роль вузла в щойно виниклій глобальній структурі. Два вузли, які випадково мають спільний префікс у своїх векторах членства, будуть з’єднані на багатьох рівнях; два вузли з повністю різними векторами зустрінуться лише на рівні нуль. Оскільки процес є симетричним і локальним, графи пропуска успадковують логарифмічні гарантії пошуку та вставки списку пропуска, одночасно усуваючи вимогу того, щоб будь-яка одна сторона бачила повну картину. Це концептуальний стрибок, який робить графи пропуска справді розподіленою структурою, а не просто мережевою реалізацією послідовної. Топологія є емергентною властивістю багатьох незалежних випадкових виборів, а не результатом центрального планування, що саме потрібно системі з тисячами ненадійних та постійно змінюваних однолітків.”]} 2024-05-17T13:08:46Z --> {

heading

paragraphs

Рівні, Вектори Членства та Шлях Пошуку

Структура графа пропусків визначається повністю тим, як вектори членства розділяють вузли на перекриваються зв’язні списки. На рівні 0 кожен окремий вузол у мережі належить одному великому подвійному зв’язуванню списку, відсортованому за ключем, точно так само, як і нижня ступінь у графі пропусків. Це гарантує, що в найгіршому випадку ви завжди можете знайти будь-який ключ, просто повільно переміщуючись по рівню 0. На рівні i для i більше за нуль, вузол належить лише до зв’язного списку, який містить інші вузли, чий вектор членства має ті ж перші i цифр, що й його власний, і всередині цього списку вузли все ще відсортовані за ключем. Отже, вузол із вектором членства, що починається з '010...', з’являється у списку рівня 1 з усіма іншими вузлами, які починаються з '0', і у списку рівня 2 лише з вузлами, які починаються з '01', і так далі, поки зрештою він не є ймовірним самотнім або з дуже малою кількістю партнерів на своєму особистому максимальному рівні. Оскільки вектори членства випадкові та приблизно половина всіх вузлів ділять будь-який заданий перший символ, списки рівня 1 приблизно вдвічі менші за список рівня 0, списки рівня 2 приблизно чверті, і так далі, експоненційне витончення, яке відображає експоненційний розподіл висоти вежі у простому графі пропусків. Пошук цільового ключа починається на найвищому рівні вузла запитувача, де сусідні списки короткі, але кожен стрибок покриває значну відстань простору ключів, і рухається до цілі, опускаючись на рівень, коли сусіди поточного рівня перестрибують або вичерпуються, що призводить до очікуваного часу пошуку O(log n) стрибків у графі пропусків, оскільки на кожному рівні приблизно половина решти кандидатів виключається, але кожен окремий стрибок у графі пропусків також є реальним мережевим повідомленням між двома незалежними фізично відокремленими машинами, а не розірванням покажчика в локальній пам’яті.

Чому порядок кращий за хешування для запитів у діапазоні

Найбільш важливе дизайнерське рішення, яке відрізняє графік пропусків від класичної розподіленої таблиці хешів (DHT), – це те, що відбувається з ключем перед його розміщенням в мережі. DHT, така як Chord або Kademlia, використовує кожен ключ через хешування перед тим, як вирішити, де він живе, що чудово для балансування навантаження: хешування рівномірно розподіляє ключі по простору ідентифікаторів, щоб жоден вузол не став гарячим точкою, і робить точні пошуки збіжних та передбачуваними. Але хешування – це одностороння операція перемішування, і перемішування руйнує саме те, що зробило початкові ключі значущими для багатьох застосунків, їх відносний порядок. Коли ключі 42 та 43 були обгорнуті в хеш, їхні хеш-значення могли опинитися будь-де в просторі ідентифікаторів, поруч або на великій відстані один від одного, без жодного зв’язку з тим фактом, що ключі 42 та 43 були сусідами у вихідному порядку. Це означає, що DHT може ефективно відповідати на запитання «де вузол, відповідальний за цей точний ключ», але не може ефективно відповідати на запитання «дайте мені всі ключі між 42 та 100» без фактично перевірки кожного вузла. Графік пропусків ніколи не хешує ключ; вузли впорядковані та з’єднані за допомогою їхніх фактичних, реальних значень ключа на кожному рівні. Це саме тому структура підтримує справжні запити діапазону та відсортований обхід: запит може розпочинатися будь-де в мережі, використовувати багаторівневі зв’язані списки для переходу до сусідства цільового діапазону, а потім йти по рівню 0 у відсортованому порядку, щоб перерахувати всі відповідні ключі, працюючи пропорційно кількості знайдених результатів плюс логарифмійний витрат на пошук там, а не повний сканування мережі. Ця властивість має величезне значення для застосунків, таких як розподілені бази даних, сенсорні мережі, які повідомляють про безперервні вимірювання, або файлові системи, яким потрібні пошуки префіксів і діапазонів, саме ті навантаження, де точний пошук лише DHT не виправдовується.

Гнучке поводження з відтоком

Реальні мережі P2P не є статичними; машини приєднуються, виходять з ладу, відключаються та знову приєднуються постійно, явище, яке дослідники називають відтоком. Хороша розподілена структура даних повинна продовжувати працювати та підтримувати свої гарантії продуктивності, тоді як цей безперервний потік відбувається під нею. Skip-графи гнучко поводяться з відтоком з структурної причини: оскільки позиція кожного вузла в ієрархії визначається виключно його власним незалежним вектором членства, приєднання або від'єднання вузла впливає лише на невеликий набір сусідів, з якими він ділить список членства на кожному рівні, ніколи на глобальну структуру та ніколи на центрально підтримуваний індекс. Прибувши новий вузол, він генерує вектор членства, використовує існуючий вузол як точку входу, виконує пошук з логарифмічною довжиною ходу, щоб знайти своє правильне відсортоване положення на рівні 0, а потім працює вгору, вставляючи себе у список зв’язків кожного рівня, де його префікс вектора відповідає, що займає очікуваний час O(log n) і торкається лише невеликого локалізованого набору існуючих вузлів. Відхилення обробляються симетрично: сусіди виявляють, що вузол зник, зазвичай через періодичні перевірки активності або невдалі ходи під час пошуку, та ремонтують власні покажчики у списках зв’язків, щоб обійти проміжок, знову ж таки, це локальна, обмежена робота з відновлення, а не глобальне перебудовування. Порівняйте це зі структурами, які залежать від глобально узгодженого, центрально обчисленого макету, де одне зміна може вимагати повторного обчислення великих частин структури. Оскільки skip-графи розподіляють генерацію випадковості самі по собі, існує також гнучке зниження навантаження під час перевантажень: навіть якщо відновлення трохи відстає від спалаху відтоку, пошуки плавно деградують до надійного списку рівня 0, а не виходять з ладу повністю, оскільки надлишок перекриваючих рівнів зазвичай означає, що існує кілька незалежних шляхів до будь-якого заданого ключа.

Де використовують графіки пропусків на практиці

Графіки пропусків були введені Джеймсом Аспеномсом та Гуарі Шах у першій половині 2000-х як відповідь на конкретну прогалину в тодішній швидкозростаючій літературі DHT: ніхто не мав повністю децентралізованої структури, яка б підтримувала логарифмічну вартість пошуку та можливість здійснювати запити діапазонів і упорядковані запити. Це робило графіки пропусків привабливими для індексування розподілених баз даних, де програми регулярно потребують запитів «між» значеннями, а не лише точних пошуків, і для систем відкриття ресурсів, де клієнти шукають служби, що відповідають діапазону критеріїв, таких як доступна пам'ять або пропускна здатність. Вони вплинули на дизайн структурованих надлишкових мереж, розподілених файлових систем, які потребують пошуку за префіксами стилю каталогу, і систем публікації-підписки P2P, де підписники реєструють інтерес до діапазонів тем або значень. Подібний та впливовий родич, SkipNet, прослідковував подібні цілі з акцентом на локальність контенту та адміністративний контроль, демонструючи, що основна ідея – багатошарове рандомізоване зв’язке списки, відсортовані за спільними префіксами незалежно генерованих ідентифікаторів – є гнучким шаблоном, а не єдиним жорстким протоколом. Варто бути чесним щодо компромісів: підтримка кількох рівнів на вузлі коштує більше стану та більше повідомлень про обслуговування, ніж деякі DHT, і графіки пропусків зазвичай припускають відносно кооперативну мережу, а не активно вороже середовище, на відміну від деяких DHT-варіантів, які були зміцнені проти зловмисного маршрутизації. Проте, для будь-якої системи, де збереження порядку ключів і відповідь на запити діапазонів має таку ж важливість, як швидкість точного пошуку, графік пропусків залишається одним із найчистіших ілюстрацій того, як локальний, незалежний випадковий розподіл на кожному учаснику може скластися в цілісну, ефективну, справді лідерську глобальну структуру.

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

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

Усе, що вище, працює прямо у вашому браузері — відкрийте Skip Graph: Decentralized Ordered Search for Peer-to-Peer Networks і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.