Кіріспе

Іздеу қызметі бар орталықтандырылмаған, үлестірілген жүйе. Таратылған хэш-кесте (DHT) – хэш-кестеге ұқсас іздеу қызметін ұсынатын үлестірілген жүйе. Кілт-мәнді жұптар DHT-де сақталады, және кез келген қатысушы түйін берілген кілтке сәйкес мәнді тиімді түрде ала алады. DHT-нің басты артықшылығы – түйіндерді кілттерді қайта үлестіру бойынша минимал жұмыспен қосуға немесе алып тастауға болады. Кілттер – бұл нақты мәндерге сәйкес келетін бірегей идентификаторлар, ал мәндер мекенжайлар, құжаттар, немесе кез келген деректер болуы мүмкін. Кілттерден мәндерге сәйкестікті сақтау жауапкершілігі түйіндер арасында бөлінеді, сондықтан қатысушылар жиынтығының өзгеруі ең аз бұзылуға әкеледі. Бұл DHT-ге өте көп түйіндерге дейін кеңейтуге және түйіндердің үнемі қосылуын, кетуін және істен шығуын басқаруға мүмкіндік береді. DHT-лер күрделірек қызметтерді құруға арналған инфрақұрылымды құрайды, мысалы, anycast, бірлескен веб-кеш, үлестірілген файлдық жүйелер, домендік атаулар қызметі, жылдам хабар алмасу, көп тарату, сондай-ақ файлдарды бөлісу және мазмұнды тарату жүйелері. DHT-ді пайдаланатын белгілі үлестірілген желілерге BitTorrent-тің үлестірілген трекері, Kad желісі, Storm ботнеті, Tox жылдам хабаршысы, Freenet, YaCy іздеу жүйесі және Планетааралық файлдық жүйе кіреді.

Тарих

DHT зерттеулері бастапқыда Freenet, Gnutella, BitTorrent және Napster сияқты P2P жүйелерімен негізделген, олар Интернет арқылы таралған ресурстарды пайдаланып, бір пайдалы қолданбаны ұсынды. Олар, әсіресе, файлдарды бөлісу қызметін ұсыну үшін жолақтың енінің және қатты дискінің сыйымдылығының артуын пайдаланды. Бұл жүйелер өздерінің әріптестері ұсынған деректерді қалай табуымен ерекшеленді. Napster, алғашқы кең ауқымды P2P мазмұн жеткізу жүйесі, орталық индекс серверін қажет етті: әрбір түйін қосылғаннан кейін жергілікті сақталған файлдардың тізімін серверге жіберетін болды, ол іздеуді жүргізіп, сұраныстарды нәтижелерді ұстап тұрған түйіндерге бағыттайтын. Бұл орталық компонент жүйені шабуылдар мен сот процестеріне осал қылды. Gnutella және ұқсас желілер сұранысты тарату моделіне көшті, нәтижесінде әрбір іздеу желідегі барлық машинаға хабарлама таратумен аяқталды. Бір сәтсіздік нүктесін болдырмаса да, бұл әдіс Napster-ге қарағанда әлдеқайда тиімсіз болды. Gnutella клиенттерінің кейінгі нұсқалары тиімділікті едәуір жақсартқан динамикалық сұрау моделіне көшті. Freenet толыққанды таратылған, бірақ әрбір файл кілтпен байланысты болатын эвристикалық кілт негізінде маршруттауды қолданады, ал ұқсас кілттері бар файлдар ұқсас түйіндер жиынтығында шоғырланады. Сұраулар көбінесе осындай кластерге, көптеген әріптестерді аралау қажеттілігінсіз бағытталады. Дегенмен, Freenet деректердің табылатынына кепілдік бермейді. Таратылған хэш-кестелер Freenet және Gnutella-ның орталықтандырылмағандығын, сондай-ақ Napster-дің тиімділігі мен кепілдік берілген нәтижелерін қамтамасыз ету үшін кілт негізінде маршруттауды тиімдірек пайдаланады. Бір кемшілігі, Freenet сияқты, DHT тек нақты сәйкестік іздеуді тікелей қолдайды, бірақ Freenet-тің маршруттау алгоритмі жақындық операциясы анықталатын кез келген кілт түріне жалпыландыруға болады. 2001 жылы CAN, Chord, Pastry және Tapestry жүйелері DHT-ні танымал зерттеу тақырыбы ретінде серпіліс тудырды. 2002 жылы АҚШ Ұлттық ғылым қорынан 12 миллион долларлық грантпен "Төзімді интернет жүйелері үшін инфрақұрылым" (IRIS) жобасы қаржыландырылды. Зерттеушілердің қатарында Сильвия Ратнасами, Ион Стойка, Хари Балакришнан және Скотт Шенкер болды. Академиялық емес салаларда DHT технологиясы BitTorrent құрамы ретінде және PlanetLab жобаларында, мысалы Coral Content Distribution Network ретінде қабылданды.

Құрылымы

ДГТ құрылымын бірнеше негізгі компонентке бөлуге болады. Негізі – абстрактілі кілттік кеңістік, мысалы, 160 биттік тізбектер жиынтығы. Кілттік кеңістікті бөлу схемасы осы кеңістіктің иелігін қатысушы түйіндер арасында бөледі. Содан кейін, жабын желісі түйіндерді байланыстырады, оларға кілттік кеңістіктегі кез келген кілттің иесін табуға мүмкіндік береді. Осы компоненттер орналасқаннан кейін, ДГТ-ны сақтау және алу үшін пайдалану мынадай болуы мүмкін. Мысалы, кілттік кеңістік 160 биттік тізбектер жиынтығы болсын. ДГТ-дегі белгілі бір файлды және деректерді индекстеу үшін файл атауының SHA-1 хэші жасалады, нәтижесінде 160 биттік k кілті пайда болады, және put(k, data) хабары ДГТ-ға қатысатын кез келген түйінге жіберіледі. Хабар түйінден түйінге, жабын желісі арқылы, кілттік кеңістікті бөлу бойынша k кілтіне жауапты жалғыз түйінге жеткенше жіберіледі. Бұл түйін кілтті және деректерді сақтайды. Кез келген басқа клиент файлдың мазмұнын алу үшін файл атауын қайтадан хэштеу арқылы k кілтін жасап, кез келген ДГТ түйінінен k кілтімен байланысты деректерді get(k) хабарымен табуды сұрай алады. Хабар қайтадан жабын желісі арқылы k кілтіне жауапты түйінге бағытталады, ол сақталған деректермен жауап береді. Кілттік кеңістікті бөлу және жабын желісі компоненттері төменде сипатталған, мақсаты – көптеген ДГТ-лерге ортақ негізгі идеяларды түсіру. Көптеген жобалар егжей-тегжейлі ерекшеленеді.

Кілттер кеңістігін бөлу

Көптеген DHT жүйелері кілттерді түйіндерге бейімдеу үшін біркелкі хэштеудің немесе кездесу хэштеуінің бірнеше нұсқаларын пайдаланады. Екі алгоритм де таратылған хэш-кесте мәселесін шешу үшін дербес және бір уақытта жасалғандай көрінеді. Біркелкі хэштеудің де, кездесу хэштеуінің де маңызды қасиеті – бір түйіннің қосылуы немесе алынып тасталуы тек жақын ID-лері бар түйіндерге тиесілі кілттер жиынтығын өзгертеді, ал қалған түйіндерге ешқандай әсер етпейді. Бұл, дәстүрлі хэш-кестеден өзгеше, онда бір бөліктің қосылуы немесе алынып тасталуы бүкіл кілттер кеңістігін қайта бейімдеуге алып келеді. Меншік құқығының кез келген өзгеруі көбінесе DHT жүйесінде сақталған нысандардың бір түйінен екіншісіне ауысуымен байланысты, сондықтан мұндай қайта ұйымдастыруды барынша азайту түйіндердің жиі ауысуын (түйіндердің қосылуын және істен шығуын) тиімді қолдау үшін қажет.

Тұрақты хэштеу

Тұрақты хэштеу кілттер мен арасындағы қашықтықтың абстрактілік ұғымын анықтайтын функцияны қолданады, бұл қашықтық географиялық қашықтыққа немесе желілік кешігуге байланысты емес. Әрбір түйінге оның идентификаторы (ID) деп аталатын бір кілт тағайындалады. ID-сы бар түйінге барлық кілттер тиесілі, олар үшін ID ең жақын болып табылады, бұл сәйкес өлшем бойынша анықталады. Мысалы, Chord DHT жүйесі тұрақты хэштеуді қолданады, ол түйіндерді шеңбердегі нүктелер ретінде қарастырады, ал – дегеніміз, шеңбер бойында сағат тілімен жүру арқылы еденнен дейінгі қашықтық. Осылайша, дөңгелек кілттік кеңістік түйін идентификаторларының соңғы нүктелері болатын үзділіссіз сегменттерге бөлінеді. Егер және екі жақын ID болса, онда ID-сы бар түйін және аралығындағы барлық кілттерге ие болады.

Кездесудің хэші

Кездесу хэштегі, сонымен қатар ең жоғары кездейсоқ салмақ (HRW) хэштегі деп аталады, барлық клиенттер бір кілтті n қолжетімді серверлердің бірімен байланыстыру үшін бірдей хэш функциясын (алдын ала таңдалған) пайдаланады. Әрбір клиенттің әр сервер үшін бір идентификаторы бар. Белгілі бір k кілті үшін клиент n хэш салмағын есептейді: w1 = h(S1, k), w2 = h(S2, k), ..., wn = h(Sn, k). Клиент осы кілтті ең жоғары хэш салмағына ие сервермен байланыстырады. ID-сы бар сервер, осы кілт үшін кез келген басқа сервердің хэш салмағынан жоғары хэш салмағына ие барлық кілттерге жатады.

Жергілікті жерді сақтайтын хэштеу

Жергілікті сақтаулы хэштеу ұқсас кілттердің ұқсас нысандарға тағайындалуын қамтамасыз етеді. Бұл ауқымдық сұраныстарды тиімдірек орындауға мүмкіндік береді, бірақ дәйекті хэштеуді пайдаланудан өзгеше, кілттердің (және осымен жүктеме) кілт кеңістігінде және қатысушы түйіндерде біркелкі кездейсоқ түрде таралуына кепілдік жоқ. Self Chord және Oscar сияқты DHT протоколдары мұндай мәселелерді шешеді. Self Chord нысан кілттерін түйін идентификаторларынан бөліп, кілттерді сақина бойынша статистикалық тәсілмен реттейді, бұл әрекеттерді үйлестіру парадигмасына негізделген. Реттеу ұқсас кілттердің көрші түйіндерде сақталуын қамтамасыз етеді және іздеу процедураларын, соның ішінде ауқымдық сұраныстарды, логарифмдік уақытта орындауға мүмкіндік береді. Oscar кездейсоқ серуендеу үлгілерін пайдаланып, іздеу уақытын логарифмдік деңгейде сақтайтын, өтетін кіші әлем желісін құрайды.

Үстіне жабылатын желі

Әрбір түйін басқа түйіндерге (өзінің көршілеріне немесе маршрут кестесіне) сілтемелер жиынтығын сақтайды. Бұл сілтемелер бірігіп, жапсырма желісін құрайды. Түйін өзінің көршілерін белгілі бір құрылымға сәйкес таңдайды, бұл желі топологиясы деп аталады. Барлық DHT топологияларында ең маңызды қасиеттің бірнеше түрі бар: кез келген k кілті үшін, әрбір түйіннің k кілтіне ие түйін идентификаторы болады немесе жоғарыда анықталған кілттік кеңістік қашықтығы бойынша k кілтіне жақын түйін идентификаторы бар түйінге сілтемесі болады. Осыдан кейін, кез келген k кілтінің иесіне келесі ашкөз алгоритмді (бұл міндетті түрде жаһандық оптималдық емес) қолдану арқылы хабарламаны бағыттау оңай: әр қадамда хабарламаны k кілтіне ең жақын идентификаторы бар көршіге жіберіңіз. Егер мұндай көрші болмаса, онда біз жоғарыда анықталғандай k кілтінің иесі болып табылатын ең жақын түйінге келгеніміз деп санауға болады. Мұндай бағыттау стилі кейде кілт негізіндегі бағыттау деп аталады. Бағыттаудың негізгі дұрыстығынан басқа, топологияның екі маңызды шектеуі бар: кез келген маршруттағы (маршруттың ұзындығы) секірулердің максималды санының төмен болуын қамтамасыз ету, соның салдарынан сұраулар жылдам орындалады; және кез келген түйіннің көршілерінің максималды санының (максималды түйін дәрежесі) төмен болуын қамтамасыз ету, соның салдарынан техникалық қызмет көрсетуге кететін шығын артық болмайды. Әрине, қысқа маршруттар үшін жоғары максималды дәреже қажет. Максималды дәреже және маршрут ұзындығы үшін кейбір жалпы таңдаулар төменде келтірілген, мұнда n – DHT-дегі түйіндер саны, Big O нотациясын пайдалана отырып:

Макс. дәреже Макс. маршрут ұзындығы Пайдаланылатын жағдай Ескерту Ең нашар іздеу ұзындығы, іздеу уақытының айтарлықтай баяулауы мүмкін Koorde (тұрақты дәрежеде) Қолдануға күрделі, бірақ белгілі бір байланыс санымен қолайлы іздеу уақытын табуға болады Chord Kademlia Pastry Tapestry Ең көп таралған, бірақ оңтайлы емес (дәреже/маршрут ұзындығы). Chord – ең қарапайым нұсқа, ал Kademlia – ең танымал оңтайландырылған нұсқа (орташа іздеуді жақсарту керек) Koorde (оптималды іздеумен) Орындау күрделірек, бірақ іздеулер жылдамдатылуы мүмкін (ең нашар жағдайда жақсы нәтиже) Ең нашар жергілікті сақтау қажеттілігі, кез келген түйін қосылғаннан немесе ажыратылғаннан кейін көп байланыс қажет.

Ең көп таралған таңдау, дәреже/маршрут ұзындығы, дәреже/маршрут ұзындығы арасындағы қатынас бойынша оңтайлы емес, бірақ мұндай топологиялар көбінесе көршілерді таңдауда көбірек икемділікке мүмкіндік береді. Көптеген DHT-лер бұл икемділікті физикалық желідегі кідіріс уақыты бойынша жақын көршілерді таңдау үшін пайдаланады. Жалпы, барлық DHT-лер маршрут ұзындығы мен желі дәрежесін теңгеріп, кеме жүретін шағын әлем желі топологиясын құрастырады. Максималды маршрут ұзындығы диаметрмен тығыз байланысты: түйіндер арасындағы ең қысқа жолдағы секірулердің максималды саны. Әрине, желідегі ең нашар жағдайдың маршрут ұзындығы оның диаметрінен кем болмауы керек, сондықтан DHT-лер граф теориясындағы негізгі дәреже/диаметр арақатынасымен шектеледі. Маршрут ұзындығы диаметрден үлкен болуы мүмкін, өйткені ашкөз бағыттау алгоритмі ең қысқа жолдарды таба алмайды.

Үстіне жабылатын желілер үшін алгоритмдер

Маршрутизациядан басқа, DHT-дегі барлық түйіндерге немесе түйіндердің белгілі бір тобына хабар жіберу үшін жапсырма желісінің құрылымын пайдаланатын көптеген алгоритмдер бар. Бұл алгоритмдер қолданбаларға жапсырма көптүрлі таратуды, диапазондық сұрауларды жүргізуді немесе статистика жинауды жүзеге асыруға мүмкіндік береді. Осы тәсілге негізделген екі жүйе – Structella, ол Pastry жапсырма желісінде топан су және кездейсоқ іздеулерді іске асырады, және DQ DHT, ол Chord желісінде динамикалық сұрау іздеу алгоритмін қолданады.

Қауіпсіздік

Децентрализациясы, қатеге төзімділігі және кеңейтілу мүмкіндігінің арқасында DHT-лер орталықтандырылған жүйеге қарағанда жаулық шабуылға қарсы әлдеқайда төзімді. Жаудың күшті шабуылдарына қарсы тұра алатын, таратылған деректерді сақтауға арналған ашық жүйелер мүмкін. Византиялық қателерге төзімділікпен мұқият жобаланған DHT жүйесі, қазіргі көптеген DHT жобаларына әсер ететін Сибил шабуылы деп аталатын қауіпсіздік әлсіздігіне қарсы қорғанысқа ие болады. Whanau – Sybil шабуылдарына төзімді болу үшін жобаланған DHT. Kademlia-ның бастапқы авторларының бірі Петар Маймунков, жүйелік жобаға әлеуметтік сенім қарым-қатынастарын енгізу арқылы Сибил шабуылының әлсіздігін айналып өтудің жолын ұсынды. Тоника немесе 5ttt деп аталатын жаңа жүйе "электрлік маршрутизация" деп аталатын алгоритм негізінде құрылған және математик Джонатан Келнермен бірлесіп жасалған. Маймунков қазір осы жаңа жүйені толыққанды іске асыру жұмыстарын жүргізіп жатыр. Дегенмен, Сибил шабуылдарына қарсы тиімді қорғанысқа қатысты зерттеулер әлі де ашық мәселе болып саналады және әр түрлі қорғаныс ұсыныстары жыл сайын қауіпсіздік саласындағы маңызды конференцияларда талқыланады.