Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Хэш-ке негізделген деректер құрылымы
Hash based data structure
Kademlia – 2002 жылы Петар Маймунков және Дэвид Мазьер жасаған, таратылған хэш-кесте, орталықтандырылмаған компьютерлік желілер үшін арналған. Ол желінің құрылымын және түйіндерді іздеу арқылы ақпарат алмасуды анықтайды. Kademlia түйіндері UDP арқылы бір-бірімен байланысады. Қатысушы түйіндер виртуалды немесе жабын желі құрайды. Әрбір түйін нөмірмен немесе түйін ID-мен сәйкестендіріледі. Түйін ID тек сәйкестендіру үшін ғана емес, Kademlia алгоритмі түйін ID-ді мәндерді (әдетте файлдың хэштері немесе кілт сөздер) табу үшін пайдаланады. Белгілі бір кілтпен байланысты мәнді іздеу үшін алгоритм бірнеше қадаммен желіні зерттейді. Әрбір қадам кілтқа жақын түйіндерді табады, содан кейін байланысқан түйін мәнді қайтарады немесе жақын түйіндер табылмайды. Бұл өте тиімді: көптеген басқа жүйелер сияқты, Kademlia іздеу кезінде жүйедегі түйіндердің барлығынан тек түйіндермен байланысады. Басқа да артықшылықтары бар, әсіресе орталықтандырылмаған құрылым, ол қызметтен бас тарту шабуылдарына қарсы тұруды арттырады. Тіпті түйіндердің толық жиынтығына шабуыл жасалса да, бұл желінің қолжетімділігіне шектеулі әсер етеді, өйткені желі осы «бұрыштардың» айналасына желіні тігіп, өзін-өзі қалпына келтіреді. I2P-тің Kademlia-ны іске асыруы Sybil шабуылдары сияқты Kademlia-ның осалдықтарын азайту үшін өзгертілген.
Kademlia is a distributed hash table for decentralized peer to peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A virtual or overlay network is formed by the participant nodes. Each node is identified by a number or node ID. The node ID serves not only as identification, but the Kademlia algorithm uses the node ID to locate values (usually file hashes or keywords). In order to look up the value associated with a given key, the algorithm explores the network in several steps. Each step will find nodes that are closer to the key until the contacted node returns the value or no more closer nodes are found. This is very efficient: like many other s, Kademlia contacts only nodes during the search out of a total of nodes in the system. Further advantages are found particularly in the decentralized structure, which increases the resistance against a denial of service attack. Even if a whole set of nodes is flooded, this will have limited effect on network availability, since the network will recover itself by knitting the network around these "holes". I2P's implementation of Kademlia is modified to mitigate Kademlia's vulnerabilities, such as Sybil attacks.
Хаттамалық хабарламалар
Кадемлияда төрт түрлі хабарлама бар. PING – Түйінің әлі де жұмыс істеп тұрғанын тексеру үшін қолданылады. STORE – Бір түйінде (кілт, мән) жұбын сақтайды. FIND NODE – Сұрауды алған түйін өзінің тізімінен сұраныш бойынша кілтке ең жақын k түйінді қайтарады. FIND VALUE – FIND NODE сияқты, бірақ егер сұрауды алған түйінде сұралған кілт болса, ол сәйкес мәнді қайтарады. Әрбір RPC хабарламасында бастаушының кездейсоқ мәні болады. Бұл жауап алынғанда, ол бұрын жіберілген сұранысқа сәйкес келетінін қамтамасыз етеді (магиялық cookie-ге қараңыз).
Kademlia has four messages. PING — Used to verify that a node is still alive. STORE — Stores a (key, value) pair in one node. FIND NODE — The recipient of the request will return the k nodes in its own buckets that are the closest ones to the requested key. FIND VALUE — Same as FIND NODE, but if the recipient of the request has the requested key in its store, it will return the corresponding value. Each RPC message includes a random value from the initiator. This ensures that when the response is received it corresponds to the request previously sent (see magic cookie).
Тораптарды анықтау
Түйіндерді іздеу асинхронды түрде жүзеге асырылуы мүмкін. Бір мезгілдегі іздеулер саны α арқылы белгіленеді және әдетте үшке тең болады. Түйін, қажетті кілтке ең жақын α түйінін өзінің k шұңқырында іздеу арқылы FIND NODE сұранысын бастайды. Бұл түйіндер сұранысты алғанда, өздерінің k шұңқырында іздеп, қажетті кілтке ең жақын k түйінді, білетін болса, қайтарады. Сұрау жіберуші нәтижелер тізімін алған нәтижелермен (түйін ID-лері) жаңартады, сұранысқа жауап берген k ең жақсы түйінді (ізделген кілтке жақын k түйінді) сақтайды. Содан кейін сұрау жіберуші осы k ең жақсы нәтижелерді таңдап, оларға сұрау жібереді және осы процесті қайта-қайта қайталайды. Әрбір түйін өзінің айналасын басқа түйіндерге қарағанда жақсы біледі, сондықтан алынған нәтижелер ізделіп жатқан кілтке үнемі жақындап келетін басқа түйіндер болады. Итерациялар, бұрынғы нәтижелерден жақын түйіндер табылмағанша жалғасады. Итерациялар тоқтағанда, нәтижелер тізіміндегі ең жақсы k түйін бүкіл желідегі ізделіп жатқан кілтке ең жақын түйіндер болып табылады. Түйін туралы ақпаратты сапар уақытымен немесе RTT арқылы толықтыруға болады. Бұл ақпарат әрбір сұралған түйін үшін нақты уақыт шегін таңдау үшін қолданылады. Сұрау уақыты біткен жағдайда, тағы бір сұрау жіберілуі мүмкін, бірақ бір уақытта α сұраудан аспауы керек.
Node lookups can proceed asynchronously. The quantity of simultaneous lookups is denoted by α and is typically three. A node initiates a FIND NODE request by querying to the α nodes in its own k buckets that are the closest ones to the desired key. When these recipient nodes receive the request, they will look in their k buckets and return the k closest nodes to the desired key that they know. The requester will update a results list with the results (node IDs) it receives, keeping the k best ones (the k nodes that are closer to the searched key) that respond to queries. Then the requester will select these k best results and issue the request to them, and iterate this process again and again. Because every node has a better knowledge of its own surroundings than any other node has, the received results will be other nodes that are every time closer and closer to the searched key. The iterations continue until no nodes are returned that are closer than the best previous results. When the iterations stop, the best k nodes in the results list are the ones in the whole network that are the closest to the desired key. The node information can be augmented with round trip times, or RTT. This information will be used to choose a time out specific for every consulted node. When a query times out, another query can be initiated, never surpassing α queries at the same time.
Ресурстарды анықтау
Ақпарат кілтпен байланыстыру арқылы ізделеді. Карта үшін әдетте хэш қолданылады. Сақтаушы түйіндерде бұрынғы STORE хабары арқылы алынған ақпарат болады. Құнды іздеу кілтке ең жақын түйіндерді іздеумен ұқсас процедураны орындайды, бірақ түйін сұралған құнды өзінің қорында сақтап, оны қайтарғанда іздеу тоқтатылады. Құндылықтар бірнеше түйіндерде (олардың саны k) сақталады, бұл түйіндердің келіп-кетуіне және құндылықтың кейбір түйіндерде сақталуын қамтамасыз етеді. Мерзімді түрде құнды сақтайтын түйін желіде кілт құндылығына жақын k түйінді іздеп, оларға құнды көшіреді. Бұл жоғалған түйіндердің орнын толтырады. Сонымен қатар, жиі сұралатын мәндер үшін сақтаушы түйіндердегі жүктеме азайтылады, осы мәнді іздеушіге кілтке жақын, бірақ k ең жақын түйіндерден тыс түйінде сақтау арқылы. Бұл жаңа сақтау кеш деп аталады. Осылайша, құндылық сұраныстар санына байланысты кілттен алшақтатады. Бұл танымал іздеулерге сақтаушыны жылдамырақ табуға мүмкіндік береді. Құндылық кілтке қарағанда алыс орналасқан түйіндерден қайтарылады, бұл ықтимал "қызыл нүктелерді" азайтады. Кэш түйіндері кілттен қашықтығына байланысты белгілі бір уақыттан кейін мәнді жояды. Кейбір жүзеге асыруларда (мысалы, Kad) көшірме жасау да, кеш те болмайды. Мұның мақсаты – ескі ақпаратты жүйеден жылдам жою. Файлды ұсынатын түйін жүйеде ақпаратты мерзімді түрде жаңартып отырады (FIND NODE және STORE хабарламаларын орындайды). Файлға ие барлық түйіндер желіден шыққан кезде, оның мәндерін (көздер мен кілт сөздерді) жаңартатын ешкім болмайды және ақпарат желіден жоғалады.
Information is located by mapping it to a key. A hash is typically used for the map. The storer nodes will have information due to a previous STORE message. Locating a value follows the same procedure as locating the closest nodes to a key, except the search terminates when a node has the requested value in its store and returns this value. The values are stored at several nodes (k of them) to allow for nodes to come and go and still have the value available in some node. Periodically, a node that stores a value will explore the network to find the k nodes that are close to the key value and replicate the value onto them. This compensates for disappeared nodes. Also, for popular values that might have many requests, the load in the storer nodes is diminished by having a retriever store this value in some node near, but outside of, the k closest ones. This new storing is called a cache. In this way the value is stored farther and farther away from the key, depending on the quantity of requests. This allows popular searches to find a storer more quickly. Because the value is returned from nodes farther away from the key, this alleviates possible "hot spots". Caching nodes will drop the value after a certain time depending on their distance from the key. Some implementations (e. g. Kad) have neither replication nor caching. The purpose of this is to remove old information quickly from the system. The node that is providing the file will periodically refresh the information onto the network (perform FIND NODE and STORE messages). When all of the nodes having the file go offline, nobody will be refreshing its values (sources and keywords) and the information will eventually disappear from the network.
Желіге қосылу
Желіге қосылуды қалаған түйін алдымен бастапқы орнату процесінен өтуі керек. Осы кезеңде қосылатын түйінге басқа түйіннің IP-мекенжайы мен порты қажет – бастапқы орнату түйіні (пайдаланушыдан немесе сақталған тізімнен алынған), ол Kademlia желісіне қатысады. Егер қосылатын түйін бұрын желіге қатыспаса, ол кездейсоқ ID нөмірін есептейді, бұл өте үлкен кездейсоқ сан болғандықтан, басқа түйіндерге бұрын тағайындалмауы ықтимал. Ол осы ID-ны желіден шыққанға дейін пайдаланады. Қосылатын түйін бастапқы орнату түйінін өзінің k-кешіктерінің біріне қосады. Содан кейін қосылатын түйін өзінің ID-сын бастапқы орнату түйініне қарсы іздейді (оның білетін жалғыз басқа түйіні). «Өзін-өзі іздеу» басқа түйіндердің k-кешіктерін жаңа түйін ID-сымен толтырады және қосылатын түйіннің k-кешіктерін оның және бастапқы орнату түйіні арасындағы жолдағы түйіндермен толтырады. Осыдан кейін қосылатын түйін бастапқы орнату түйіні орналасқан k-кешіктен алысрақ орналасқан барлық k-кешіктерін жаңартады. Бұл жаңарту – сол k-кешік диапазонындағы кездейсоқ кілтті іздеу. Бастапқыда түйіндерде бір k-кешік болады. K-кешік толғанда, оны бөлуге болады. Егер k-кешіктегі түйіндер диапазоны түйіннің өзінің ID-сын (бинарлық ағашта сол және оң жақтағы мәндер) қамтитын болса, бөліну орын алады. Kademlia тіпті «ең жақын түйіндер» k-кешігі үшін осы ережені де жеңілдетеді, себебі әдетте бір кешік осы түйінге ең жақын барлық түйіндер орналасқан қашықтыққа сәйкес келеді, олардың саны k-дан көп болуы мүмкін, және біз олардың бәрін білуді қалаймыз. Бұл түйіннің жанында теңгерімсіз екілік кіші ағаш болуына әкелуі мүмкін. Егер k 20-ға тең болса және «xxx0011» префиксі бар 21-ден астам түйін болса, ал жаңа түйін «xxx000011001» болса, жаңа түйінде басқа 21-ден астам түйін үшін бірнеше k-кешік болуы мүмкін. Бұл желіге ең жақын аймақтағы барлық түйіндер туралы ақпараттың болуын қамтамасыз етеді.
A node that would like to join the net must first go through a bootstrap process. In this phase, the joining node needs to know the IP address and port of another node—a bootstrap node (obtained from the user, or from a stored list)—that is already participating in the Kademlia network. If the joining node has not yet participated in the network it computes a random ID number, which by virtue of being a very large random number is extremely likely not to be already assigned to any other node. It uses this ID until leaving the network. The joining node inserts the bootstrap node into one of its k buckets. The joining node then performs a node lookup of its own ID against the bootstrap node (the only other node it knows). The "self lookup" will populate other nodes' k buckets with the new node ID, and will populate the joining node's k buckets with the nodes in the path between it and the bootstrap node. After this, the joining node refreshes all k buckets further away than the k bucket the bootstrap node falls in. This refresh is just a lookup of a random key that is within that k bucket range. Initially, nodes have one k bucket. When the k bucket becomes full, it can be split. The split occurs if the range of nodes in the k bucket spans the node's own id (values to the left and right in a binary tree). Kademlia relaxes even this rule for the one "closest nodes" k bucket, because typically one single bucket will correspond to the distance where all the nodes that are the closest to this node are, they may be more than k, and we want it to know them all. It may turn out that a highly unbalanced binary sub tree exists near the node. If k is 20, and there are 21+ nodes with a prefix "xxx0011 " and the new node is "xxx000011001", the new node can contain multiple k buckets for the other 21+ nodes. This is to guarantee that the network knows about all nodes in the closest region.
Жедел іздеулер
Кадемлия қашықтықты анықтау үшін XOR метрикасын қолданады. Екі түйін идентификаторы немесе түйін идентификаторы мен кілт XOR операциясынан өтеді және нәтиже олардың арасындағы қашықтықты көрсетеді. Әр бит үшін XOR функциясы екі бит бірдей болса нөлді, ал екі бит әртүрлі болса бірді қайтарады. XOR метрикасындағы қашықтықтар үшбұрыш теңсіздігін қанағаттандырады: егер A, B және C үшбұрыштың төбелері (нүктелері) болса, онда A-дан B-ге дейінгі қашықтық A-дан C-ге және C-дан B-ге дейінгі қашықтықтардың қосындысынан кем (немесе тең) болады. XOR метрикасы Kademlia-ға маршрут кестелерін бір биттен асырып кеңейтуге мүмкіндік береді. Биттердің топтары k бөшкеге орналастырылуы мүмкін. Биттер тобы префикс деп аталады. m биттік префикс үшін 2m - 1 k бөшке болады. Қолданылмаған k бөшке – бұл түйін идентификаторын қамтитын маршруттау ағашының одан әрі кеңейтімі. m биттік префикс іздеулердің максималды санын log2 n-ден log2m n-ге дейін азайтады. Бұл максималды мәндер, ал орташа мән одан әлдеқайда төмен болады, бұл k бөшкеде префикстен басқа да биттерді мақсатты кілтпен ортақтайтын түйін табу ықтималдығын арттырады. Түйіндер маршрут кестесінде префикстердің қоспаларын пайдалана алады, мысалы, eMule қолданатын Kad желісі. Kademlia желісі тіпті маршрут кестесін жүзеге асыруда әртүрлі болуы мүмкін, бірақ бұл іздеулерді талдауды қиындатады.
Kademlia uses an XOR metric to define distance. Two node IDs or a node ID and a key are XORed and the result is the distance between them. For each bit, the XOR function returns zero if the two bits are equal and one if the two bits are different. Distances in the XOR metric satisfy the triangle inequality: given A, B and C are vertices (points) of a triangle, then the distance from A to B is shorter than (or equal to) the sum of the distances from A to C and from C to B. The XOR metric allows Kademlia to extend routing tables beyond single bits. Groups of bits can be placed in k buckets. The group of bits are termed a prefix. For an m bit prefix, there will be 2m 1 k buckets. The missing k bucket is a further extension of the routing tree that contains the node ID. An m bit prefix reduces the maximum number of lookups from log2 n to log2m n. These are maximum values and the average value will be far less, increasing the chance of finding a node in a k bucket that shares more bits than just the prefix with the target key. Nodes can use mixtures of prefixes in their routing table, such as the Kad Network used by eMule. The Kademlia network could even be heterogeneous in routing table implementations, at the expense of complicating the analysis of lookups.
Академиялық маңызы
XOR метрикасы Kademlia-ны түсіну үшін қажет болмаса да, протоколды талдау үшін маңызды рөл атқарады. XOR арифметикасы жабық талдауға мүмкіндік беретін абельдік топ құрайды. Басқа DHT протоколдары мен алгоритмдер желінің қалай жұмыс істейтінін және дұрыстығын болжау үшін көбінесе симуляциялау немесе күрделі формалды талдау талап етеді. Биттер тобын маршруттау ақпараты ретінде қолдану алгоритмдерді оңайлатуға көмектеседі.
While the XOR metric is not needed to understand Kademlia, it is critical in the analysis of the protocol. The XOR arithmetic forms an abelian group allowing closed analysis. Other DHT protocols and algorithms require simulation or complicated formal analysis in order to predict network behavior and correctness. Using groups of bits as routing information also simplifies the algorithms.
Файл ортақтастыру желілерінде пайдалану
Kademlia файл алмасу желілерінде қолданылады. Kademlia-да түйін сөздерді іздеу арқылы файл алмасу желісінен ақпаратты табуға болады, содан кейін оны жүктеуге болады. Файлдардың индексін сақтауға арналған орталық сервер болмағандықтан, бұл міндет барлық клиенттер арасында тең бөлінеді: егер түйін файлды бөліскісі келсе, ол файлдың мазмұнын өңдейді және одан файлды файл алмасу желісінде анықтайтын сан (хэш) есептейді. Файл хэштері мен түйін идентификаторлары (ID) бірдей ұзындықты болғандықтан, клиент XOR қашықтық функциясын пайдаланып, хэшке жақын ID-і бар бірнеше түйінді іздейді және осы түйіндерге жариялаушының IP-адресін белгілі бір тәсілмен сақтауға нұсқау береді. Сондықтан, файл хэшіне ең жақын ID-і бар түйіндер осы файлдың көздерінің/жариялаушыларының IP-адрестерінің тізіміне ие болады, одан клиент файлды белгілі бір тәсілмен жүктей алады. Бұл жариялаушыдан файлды жүктегісі келетін клиенттерге жариялаушының IP-адресін білудің қажеті жоқ (жариялаушылар көп болуы мүмкін), тек файлдың хэші ғана қажет. Іздеуші клиент Kademlia-ны пайдаланып, файл хэшіне ең жақын қашықтықтағы ID-і бар түйінді желіде іздейді, содан кейін сол түйінде сақталған көздер тізімін алады. Бір кілт көптеген мәндерге сәйкес келуі мүмкін, мысалы, бір файлдың көптеген көздері, сондықтан әр сақтау түйіні әртүрлі ақпаратқа ие болуы мүмкін. Содан кейін, көздер кілтке жақын орналасқан барлық k түйінден сұралады, мұнда k – бұкеттің (bucket) көлемі. Файл хэші әдетте басқа жерден табылған, арнайы құрылған Интернеттегі магнит сілтемесі арқылы немесе басқа көздерден алынған индекстеу файлынан алынады. Файл атауларын іздеу түйін сөздерді пайдаланып жүзеге асырылады. Файл атауы құрамына кіретін сөздерге бөлінеді. Осы түйін сөздердің әрқайсысы сәйкес файл атауымен және файл хэшімен бірге желіде сақталады. Іздеу түйін сөздердің бірін таңдап, түйін сөз хэшіне ең жақын ID-і бар түйінмен байланысып, түйін сөзді қамтитын файл атауларының тізімін алуды қамтиды. Тізімдегі әрбір файл атауының хэші болғандықтан, таңдалған файлды әдеттегідей алуға болады.
Kademlia is used in file sharing networks. By making Kademlia keyword searches, one can find information in the file sharing network so it can be downloaded. Since there is no central instance to store an index of existing files, this task is divided evenly among all clients: If a node wants to share a file, it processes the contents of the file, calculating from it a number (hash) that will identify this file within the file sharing network. Since file hashes and node IDs have the same length, the client can use the XOR distance function to search for several nodes whose ID is close to the hash, and instructs those nodes to store the publisher's IP address in an implementation defined manner. Nodes with IDs closest to the file hash will therefore have a list of IP addresses of peers/publishers of this file, from which a client may in an implementation defined manner download the file. Clients that wish to download the file from this publisher do not have to know the publisher's IP address (there can be many publishers), but only the hash of the file. A searching client will use Kademlia to search the network for the node whose ID has the smallest distance to the file hash, then will retrieve the sources list that is stored in that node. Since a key can correspond to many values, e. g. many sources of the same file, every storing node may have different information. Then, the sources are requested from all k nodes close to the key, k being the size of the bucket. The file hash is usually obtained from a specially formed Internet magnet link found elsewhere, or included within an indexing file obtained from other sources. Filename searches are implemented using keywords. The filename is divided into its constituent words. Each of these keywords is hashed and stored in the network, together with the corresponding filename and file hash. A search involves choosing one of the keywords, contacting the node with an ID closest to that keyword hash, and retrieving the list of filenames that contain the keyword. Since every filename in the list has its hash attached, the chosen file can then be obtained in the normal way.