Тартылған кесте протоколы: Chord алгоритмі

Кіріспе

Таратылған хэш-кесте протоколы

Есептеуде Chord – бұл өзара байланысқан хэш-кесте протоколы және алгоритмі. Таратылған хэш-кесте кілт-мәнді жұптарды кілттерді әртүрлі компьютерлерге (немесе «түйіндер» деп аталатын) тағайындау арқылы сақтайды; түйін өзі жауапты кілттердің барлық мәндерін сақтайды. Chord кілттердің түйіндерге қалай тағайындалатынын және түйіннің берілген кілтке жауапты түйінді алдымен іздеп тауып, сол кілттің мәнін қалай анықтай алатынын көрсетеді. Chord – CAN, Tapestry және Pastry протоколдарымен қатар төрт бастапқы таратылған хэш-кесте протоколының бірі. Оны 2001 жылы Ион Стойка, Роберт Моррис, Дэвид Каргер, Франс Каашоек және Хари Балакришнан ұсынды және MIT-де жасалды. 2001 жылғы Chord мақаласы.

Памела Заве жүргізген келесі зерттеулер бастапқы Chord алгоритмінің (SIGCOMM 2001 жылғы мақаласында, 2002 жылғы PODC мақаласында және 2003 жылғы TON мақаласында сипатталғандай) сақинаны дұрыс реттемей, бірнеше сақина жасап, сақинаны бұзуы мүмкін екенін көрсетті.

Шолу

Түйіндер мен кілттерге биттік идентификатор тұрақты хэштеу арқылы тағайындалады. SHA 1 алгоритмі – тұрақты хэштеу үшін негізгі хэштеу функциясы. Тұрақты хэштеу – Chord жүйесінің сенімділігі мен өнімділігінің маңызды бөлігі, себебі кілттер мен түйіндер (әрине, олардың IP-адрестері) бір идентификатор кеңістігінде біркелкі таратылады, соқтығысу ықтималдығы өте төмен. Сондықтан, бұл түйіндерге желіге қосылуға және одан үзіліссіз шығуға мүмкіндік береді. Протокол ішінде «түйін» термині түйіннің өзіне де, оның идентификаторына (ID) да ешқандай күмәндік тудырмай қолданылады. «Кілт» термині де осылай. Chord іздеу протоколын пайдаланып, түйіндер мен кілттер идентификатор шеңберінде орналасады, онда түйіндердің максималды саны (соқтығысуды болдырмау үшін жеткілікті үлкен болуы керек). Бұл түйіндердің кейбіреулері машиналарға немесе кілттерге сәйкес келеді, ал қалғандары (көбінесе) бос болады. Әрбір түйіннің ізбасары және алдастыры бар. Түйіннің ізбасары – идентификатор шеңберінде сағат тілі бойынша келесі түйін. Алдастыры – сағат тіліне қарсы бағытта. Егер әрбір мүмкін ID үшін түйін болса, 0 түйіннің ізбасары 1 түйін, ал 0 түйіннің алдастыры – түйін болар еді; алайда, әдетте тізбекте «бос орындар» кездеседі. Мысалы, 153-түйіннің ізбасары 167-түйін болуы мүмкін (және 154-тен 166-ға дейінгі түйіндер жоқ); бұл жағдайда 167-түйіннің алдастыры 153-түйін болады. Ізбасар тұжырымы кілттерге де қолданылады. Кілттің ізбасары – идентификатор шеңберінде кілтке тең немесе одан кейін келетін бірінші түйін, оны былай белгілейді. Әрбір кілт өзінің ізбасар түйініне тағайындалады (сақталады), сондықтан кілтті іздеу – сұрау салуды білдіреді. Түйіннің ізбасары (немесе алдастыры) желіден жоғалуы мүмкін (бұзылу немесе шығу салдарынан), сондықтан әрбір түйін өзі орналасқан түйіндердің аралығын жазады, яғни, өзінен бұрынғы және кейінгі түйіндердің тізімін. Бұл тізім түйіннің өзінің ізбасарын немесе алдастырын дұрыс табу ықтималдығын арттырады, тіпті егер желі жоғары деңгейдегі бұзушылықтарға ұшыраса да.

Nodes and keys are assigned an bit identifier using consistent hashing. The SHA 1 algorithm is the base hashing function for consistent hashing. Consistent hashing is integral to the robustness and performance of Chord because both keys and nodes (in fact, their IP addresses) are uniformly distributed in the same identifier space with a negligible possibility of collision. Thus, it also allows nodes to join and leave the network without disruption. In the protocol, the term node is used to refer to both a node itself and its identifier (ID) without ambiguity. So is the term key. Using the Chord lookup protocol, nodes and keys are arranged in an identifier circle that has at most nodes, ranging from to ( should be large enough to avoid collision.) Some of these nodes will map to machines or keys while others (most) will be empty. Each node has a successor and a predecessor. The successor to a node is the next node in the identifier circle in a clockwise direction. The predecessor is counter clockwise. If there is a node for each possible ID, the successor of node 0 is node 1, and the predecessor of node 0 is node ; however, normally there are "holes" in the sequence. For example, the successor of node 153 may be node 167 (and nodes from 154 to 166 do not exist); in this case, the predecessor of node 167 will be node 153. The concept of successor can be used for keys as well. The successor node of a key is the first node whose ID equals to or follows in the identifier circle, denoted by Every key is assigned to (stored at) its successor node, so looking up a key is to query
Since the successor (or predecessor) of a node may disappear from the network (because of failure or departure), each node records an arc of nodes in the middle of which it stands, i. e., the list of nodes preceding it and nodes following it. This list results in a high probability that a node is able to correctly locate its successor or predecessor, even if the network in question suffers from a high failure rate.

Негізгі сұраныс

Chord протоколының негізгі қолданылуы – клиенттен (көбінесе басқа да түйінден) кілтті сұрау, яғни оны табу. Негізгі тәсіл – егер түйін кілтті жергілікті түрде таба алмаса, сұрауды оның ізбасарына жіберу. Бұл сақинадағы машиналар санына пропорционал сұрау уақытына әкеледі.

Жеңіс үстелі

Сызықтық іздеуді болдырмау үшін, Chord әрбір түйінге бармақ кестесін сақтауды талап етеді, бұл жылдам іздеу әдісін іске асырады. Бармақ кестесіндегі жазбалар саны хеш кілтіндегі биттер санына тең болады. Түйіннің бірінші жазбасы – түйіннің тікелей ізбасары (сондықтан қосымша ізбасар өрісі қажет емес). Кез келген түйін кілтті іздегісі келгенде, сұранысты өзінің бармақ кестесіндегі кілтке ең жақын ізбасарға немесе алдыңғы түйінге (бармақ кестесіне байланысты) жібереді (шеңберде кілттің идентификаторынан кіші "ең үлкен" идентификатор). Түйін кілттің өзінің тікелей ізбасарында сақталғанын анықтағанша іздеу жалғасады. Мұндай бармақ кестесімен N түйіннен тұратын желіде ізбасарды табу үшін байланыс жасау қажет түйіндердің саны (төмендегі дәлелді қараңыз).