Kademlia XOR метрические свойства цели
В работе Kademlia Петара Маймункова и Давида Мазьера говорится, что расстояние XOR является действительной неевклидовой метрикой с ограниченными объяснениями того, почему каждое из свойств действительной метрики необходимо или интересно, а именно:
- д (х, х) = 0
- d (x, y)> 0, если x!= y
- для x,y: d(x,y) = d(y,x) - симметрия
- d(x,z) <= d(x,y) + d(y,z) - неравенство треугольника
Почему для метрики важно иметь эти свойства вообще? Почему каждое из этих свойств необходимо в контексте запросов маршрутизации в реализации распределенной хэш-таблицы Kademlia?
Кроме того, в статье упоминается, что однонаправленность (для данного x и расстояния l существует только один y, для которого d(x,y) = l) гарантирует, что все запросы будут сходиться по одному и тому же пути. Почему это так?
3 ответа
Я могу говорить только за Kademlia, может быть, кто-то другой может дать более общий ответ. В это время...
- д (х, х) = 0
- d (x, y)> 0, если x!= y
Эти две точки вместе означают, что самая близкая точка к x является x сам; любая другая точка находится дальше. (Это может показаться интуитивно понятным, но другие аспекты метрики XOR - нет.)
В контексте Kademlia это важно, так как поиск узла с идентификатором x даст этот узел как ближайший. Было бы неловко, если бы это было не так, поскольку поиск сходился к x может не найти узел x,
- в целом x,y: d(x,y) = d(y,x)
Структура таблицы маршрутизации Kademlia такова, что узлы поддерживают детальное знание ближайшего к ним адресного пространства и экспоненциально уменьшают знание более удаленного адресного пространства. Короче говоря, узел пытается сохранить все k самые близкие контакты, о которых он слышит.
Симметрия полезна, поскольку она означает, что каждый из этих ближайших контактов будет поддерживать подробные знания о подобной части адресного пространства, а не об удаленной части.
Если бы у нас не было этого свойства, было бы полезно думать о поиске как о стрелках часов, движущихся в одном направлении по часовой стрелке. Узел в 1 час (Узел 1) находится близко к Узлу 2 в 2 часа (30°), но Узел2 находится далеко от Узла 1 (330°). Итак, представьте, что мы ищем два ближайших к 3 часам (то есть Node1 и Node2). Если поиск достигает Node2, он не будет знать о Node1, так как он далеко. Весь поиск и топология должны были бы измениться.
- d (x, z) <= d (x, y) + d (y, z)
Если бы это было не так, для узла было бы невозможно узнать, какие контакты из его таблицы маршрутизации вернуть во время поиска. Было бы знать k ближе к цели, но не было бы никакой гарантии, что один из других более отдаленных контактов не приведет к более короткому общему пути.
Из-за этого свойства и однонаправленности различные поиски, начиная с сильно разнесенных точек, будут стремиться сходиться по одному и тому же пути.
Однонаправленность означает, что никакие два узла не могут иметь одинаковое расстояние от заданной точки. Если бы это было не так, то целевая точка могла бы быть окружена группой узлов на одинаковом расстоянии от нее. Тогда различные различные поиски будут свободно выбирать любой из них, чтобы пройти. Тем не менее, однонаправленность гарантирует, что именно один из этих наборов будет самым близким, и любой поиск, который выбирается между этой группой, всегда будет выбирать один и тот же.
Я довольно долго ломал голову над этим: как XOR - как по количеству различных битов, правильному расстоянию Хэмминга - может быть основой общего порядка?
Ну, это не может, такой метрики самой по себе недостаточно для сопоставимых отношений, все, что он может сделать, это сбросить узлы в кругах вокруг точки.
Затем я прочитал статью более внимательно и заметил, что в ней написано "XOR как целочисленное значение", и меня осенило: суть не в "метрике XOR", а в длине общего префикса идентификатора (из которого XOR механизм деривации.)
Возьмем два узла с одинаковым расстоянием Хэмминга от "я" и длиной их префикса, общего с "я": тот, у которого самый короткий общий префикс, является самым дальним узлом.
В статье используется "Метрика расстояния XOR", но на самом деле она должна гласить "Порядок длины префикса ID"
Я думаю, что это может объяснить это немного, дайте мне знать http://metaquestions.me/2014/08/01/shortest-distance-between-two-points-is-not-always-a-straight-line/
По сути, каждый скачок, если бы он был только один бит за раз в полностью заполненной сети (экстремальный), имел бы в два раза больше знаний о предыдущем скачке. По мере того, как вы сходитесь, знания увеличиваются, пока не дойдете до ближайших узлов, чьи знания являются максимальными в сети.