Застосування дайджестів для контролю цілісності даних в розподілених мережах

Протягом останніх років з’явилися та набули значного поширення так звані пірінгові (peering) мережі, зокрема ті, застосування яких, практично, зводиться до обміну даних файлового характеру, хоча концепція розподілених мереж цим не обмежується.

Файлообмінні мережі формують розподілену систему, в рамках у рамках якої кожний файл і кожний вузол має свій унікальний ідентифікатор. Вузли мережі можуть надавати доступ до своїх файлів, ініціювати пошук файлів на інших вузлах тощо.

Файлообмінні мережі можуть бути як сервер-орієнтовані (такі як, наприклад, eDonkey2000), або без-серверні (Kademlia, Gnutella1, Gnutella2).

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

Інші клієнти, формуючи первинний запит на пошук файлу, оперують його іменем, а частіше — ключовими словами. Коли зі списку наявних в мережі джерел файлів з подібними іменами вибрано конкретні файли (з відомими ідентифікаторами) задається пошук джерел в мережі вже за ідентифікатором файлу. Таким чином, файл буде знайдено не зважаючи на те, що він, можливо, був перейменований на якомусь вузлі.

Цілком природно, що в якості унікального ідентифікатору розробники архітектури файлообмінних мереж вибрали алгоритми дайджестів — адже саме вони з високою імовірністю гарантують ідентичність змісту файлу незалежно від його імені. Наприклад, в якості первинних ідентифікаторів у мережі eDonkey2000 обрано дайджест MD4, а в мережах сімейства Gnutella — SHA1 та TigerHash.

Порівняно нечасто, але все ж таки трапляється ситуація, коли хеш отриманого по мережі файлу не співпадає з його задекларованим раніше хешем. У такому випадку файл відкидається і клієнт мережі намагається отримати його ще раз. З огляду на те, що пошкодження змісту файлу може бути як випадковим, так і навмисним, подібна техніка є не дуже ефективною. Тому розробники програмного забезпечення файлообмінних мереж використовують спеціальні алгоритми розподілених хешів.

Так, в мережі eDonkey2000 файл розбивається на частини по 9.28 мегабайт і хеш MD4 обчислюється для кожної з них окремо. Отримані хеші в свою чергу формують блок даних, від якого обчислюється вже первинний хеш, також MD4. Набір хешів разом з первинним надалі передається в мережі вузлом, який володіє повним файлом. Таким чином, клієнти які зустріли пошкодження файлу і не співпадання його хешу з декларованим, можуть знайти пошкоджену ділянку розміром 9.28 мегабайт і запросити повторне завантаження саме її, а не всього файлу цілком.

Інший, більш розвинений спосіб виявлення та виправлення пошкоджених при передачі файлів полягає в побудові так званого дерева хешів (hash tree). Цей спосіб використовується в алгоритмі AICH (Advanced Intelligent Corruption Handling) для мережі eDonkey2000 та в алгоритмі TigerTree для мереж сімейства Gnutella.

Спосіб полягає в тому, що файл розбивається на частини по 1 кілобайту (розмір залежить від реалізації) і для кожної обчислюється значення хешу. Далі хеші сусідніх ділянок попарно формують в свою чергу блок даних, для якого обчислюється хеш вищого рівня (їх кількість буде вже в 2 рази менша). І так до тих пір, поки не буде отримано одне значення хешу — первинного, за яким файл ідентифікується. Проте повне дерево хешів також зберігається.

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

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

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

Для підвищення надійності, клієнтами файлообмінних мереж також застосовується механізм довірених джерел — коли первинний хеш або дерево хешів вважається вірним, якщо його декларують більш ніж певна кількість (звичайно 10) незалежних вузлів.

Поиск по сайту: