Интернет без серверов (Или все наоборот)

[watashiwa_daredeska]

ну и сколько из этого проиндексированно гуглом?

Это и есть то, что проиндексировано гуглом. По моим данным, это еще не всё, что есть в интернете, ибо часть выкинута гуглом из рассмотрения как полный треш и спам.

Вот если вы посчитаете, сколько _текстовой_ информации (пригодной для индексации) в интернете, это будет интереснее.

Это и есть текстовая информация. Ну, возможно, включая PDFы, DOCи и прочее, что гугл умеет текстово индексировать.

[drBatty]

Вот, похоже, Вы начинаете понимать. В вашем описании тоже нет конкретного описания выбора ближайших узлов.

эх...

Код: Выделить всё

int metrica(unit128 hash1, uint128 hash2)
{
 hash1 ^= hash2;
 int l = 0;
 while(hash1)
 {
  l += hash1 & 1;
  hash1 >>= 1;
 }
 return l;
}

вот так мы считаем расстояние. Чем оно меньше, тем узлы ближе. Достаточно строго?

Точно так же, как под приведенное мной описание подходит как пузырьковая сортировка, так и quicksort.

не. Для qsort не подходит - это что надо курить, что-бы считать "следующим" после любого элемента один и тот же срединный эл-т (медиану). Хотя для простых вставок с натяжкой подходит, если конечно постоянно подставлять след. эл-т к текущему... Но это уже надо какие-то детали додумывать, которые логически не вытекают из определения.

Не надо опускаться до детсадовских аналогий. Лучше наоборот, поднимитесь до нормального уровня обсуждения.

вы просите конкретных цифр, но я не могу их дать. Причина совсем не в том, что я плохо знаю детали алгоритма, причина в том, что Сеть по определению не идеальна - например на пути шарика в _любой_ момент может оказаться дырка, и шарик провалится в небытие. ИЧСХ, это _нормальная_ ситуация для таких сетей. У вас любопытный документ, по которому вы очевидно пытаетесь познакомится с Kademlia, и я спешу вас расстроить простым примером - в данном документе ключевая нода выбирается _однозначно_, это конечно очень удобно для анализа, но что делать, если кабель для связи с Китаем случайно (или намеренно) повреждён? А ключевая нода как раз в Китае, или даже не она, а любая другая, на её пути? Что будет, если нода ключевая? А ничего - мы сможем доскакать до неё окольным путём через другие ноды, вот только ответа мы не дождёмся. В том же документе разрабы рекомендуют асинхронно отсылать несколько запросов по разным путям, проблема в том, что при таком выборе ключевого узла, пакеты к нему приедут, но ответа не будет всё равно, ибо прямая связь каждый-с-каждым отсутствует, и это опять-таки _нормальная_ ситуация. Выходит, что нам нужно иметь несколько ключевых нод, и мало того, равномерно разбросанных по всему земному шару. Kademlia из emule это обеспечивает, ваш концепт - нет. В вашем документе ключевая нода умирая делегирует свои полномочия соседке, но "умирает" она как раз с точки зрения этой соседки. Какая же для нас радость, что ключевая нода работает с т.з. своей соседки, если с нашей т.з. она мертва? Учитывая, что по Вашим словам, информация не сохраняется на транзитных нодах? (имеется ввиду, что соседку ключевой ноды мы видим, а сама ключевая то-ли сдохла, то-ли не видна, то-ли просто датаграмма с неё потерялась).
Ну и непонятен вопрос, каким образом происходит горячая замена умерших нод, если информация храниться только на уникальной ноде? Махнула моя котейка хвостиком, выдернула ethernet кабель, и миллионы китайских семилетних девочек остались без своих любимых мультиков (:

Неверно. Не транслируют.

а я ваш концепт посмотрел - там английским по белому написано, что таки транслируют. Да и в исходниках так же написано. Вы очень уж поверхностно смотрели. Да и не могут не транслировать - сама суть Kademlia в том, что она работает таки без связки каждый-с-каждым.

Неверно. Не сохраняется никакой информации кроме {IP, Port, ID} пира с целью добавить в список «соседей».

ну посмотрите в том месте, где сохраняется. добавление в список соседей это да, один из источников пополнения этого списка (nodes.dat), очевидно, что нашим соседом _может_ быть тот, кто считает нас своим соседом, и IRL так оно часто и бывает (хоть и не всегда).

Неверно. Одна из основных идей для быстрого поиска — подобрать соседей, которые максимально непохожи. Иначе при поиске получится обход сети маленькими шажками, O(n).

нет, верно. Хеш какого-то случайного поискового запроса отделён от нас примерно на 16, и хотя каждая из нод-соседок намного ближе _к нам_, но вот мат. ожидание расстояния до хеша также равно 16и, потому как _для них_ хеш также равномерно распределён в пространстве 32х битного хеша. Т.е. хеши нод соседок максимально непохожи на хеш _нашего_ поискового запроса, хотя наш хеш(нашей ноды) максимально похож на хеш наших соседок. При подходе запроса поближе к цели ситуация меняется - теперь хеш запроса уже ближе к хешу ноды (мы совсем близко), и мы естественно переходим к ноде-соседке, чей хеш ещё ближе к хешу запроса. Очевидно в конце поиска мы должны перейти к ноде, похожей на текущую ноду. Менее очевидно, что мы так должны делать и в начале поиска (и в середине), но это действительно так - вспомните шарик - любой его поворот из одной точки в другую, это переход в _близкую_ точку, Шарик катится плавно, между похожими друг на друга точками, а вовсе не мечется сумасшедшим зигзагом (а метался-бы, если-бы было-бы по вашему).
В итоге, мы действительно вынуждены двигаться мелкими шажками (в вашем примере вообще по 1 единице пространства, как по бинарному дереву), но это совсем не приводит к медленному движению. Ведь у нас, среди соседей, 1000 похожих _на нас_ узлов, и выбирая похожий на хеш узел, мы выбираем нужное направления, т.о. область поиска сужается (в идеале) в 1000 раз за один шаг. Если-бы сеть была-бы идеальной, и если бы ноды хранили только _свои_ данные, то за 3..4 прыжка мы нашли-бы нужный узел. Но это НЕ так, сеть рваная, и любая нода видит лишь часть других нод (даже без учёта постоянной смерти части узлов), потому путь составляет 5..15 скачков IRL, и мало того, даже такой путь часто приводит к фэйлу. Приходится повторять запрос, причём через некоторое время (что-бы соседка сфэйлившей ноды успела найти новую ноду взамен умершей, это вообще говоря с первой попытки получается не всегда, но и попытки нельзя производить без задержек - не у всех гигабитный анлим, и они тоже качать хотят, а не Kad поддерживать).

Неверно. Расстояние — это просто побитовый XOR. Т.е. 0000 «ближе» к 0011, чем к 0100, хотя 0011 отличается двумя битами, а 0100 — одним.

ну это я даже и комментировать не стану. Не отправлять-же вас в русскую вику?
хотя, раз уж вы настаиваете:
http://ru.wikipedia.org/wiki/Kademlia
http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%...%BD%D0%B3%D0%B0

Какой? Покажите мне ее.

amule/emule, файлы Kademlia.*, ЕМНИП. Ну или как-то так.

[drBatty]

Это и есть то, что проиндексировано гуглом. По моим данным, это еще не всё, что есть в интернете, ибо часть выкинута гуглом из рассмотрения как полный треш и спам.

это намного больше чем "всё". К тому же, IRL сети слишком разные, и сравнивать их нельзя в принципе, вы же понимаете, что сегодня Kademlia не может служить заменой гугла, она вообще web не индексирует, она индексирует только сама себя, потому и объём информации ниже на порядки. Вот если её допилить... Тогда и можно сравнивать. Да и про скорость вы не правы, вы думаете по каким таким причинам нужно несколько часов для поиска 1000 _хороших_ соседних нод? Да хотя-бы потому, что если вдруг понадобится для этого 10 сек, то Kad'ом народ будет пользоваться как гуглом - зайдут, возьмут, выйдут. И будем мы иметь не 1.5М узлов, а 3.5 узла. Как в альтернативных сетях. Именно потому все эти ваши альтернативные сети обречены на провал - им тупо негде работать. Kademlia жива исключительно из-за своей медлительности: давайте придумаем новый быстрый протокол, и никто не будет держать постоянно работающие узлы, ибо тупо не нужно.

[/dev/random]

ну это я даже и комментировать не стану. Не отправлять-же вас в русскую вику?
хотя, раз уж вы настаиваете:
http://ru.wikipedia.org/wiki/Kademlia
http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%...%BD%D0%B3%D0%B0

А вот в английской написано как раз то, что сказал w_d: "This distance is computed as the exclusive or of the two node IDs, taking the result as an integer number."

Upd: и в обсуждавшемся выше документе: "Kademlia defines the distance between them as their bitwise exclusive or (XOR) interpreted as an integer". Т.е. врут в русской вике. Впрочем, как всегда.

[/dev/random]

а я ваш концепт посмотрел - там английским по белому написано, что таки транслируют. Да и в исходниках так же написано. Вы очень уж поверхностно смотрели. Да и не могут не транслировать - сама суть Kademlia в том, что она работает таки без связки каждый-с-каждым.

Ни фига не транслируют.

Из упомянутого выше документа:

The lookup initiator starts by picking α nodes from its closest non-empty k-bucket
...
The initiator then sends parallel, asynchronous find node RPCs to the α nodes it has chosen.
...
In the recursive step, the initiator resends the find node to nodes it has learned about from previous RPCs.

[watashiwa_daredeska]

вот так мы считаем расстояние.

Вы — это кто?

// calc distance this result is to the target
CUInt128 distance(c->GetClientID() ^ m_target);

Вот так считает distanse aMule. Ну так и? Про какую сеть Вы говорите на самом деле?

в данном документе ключевая нода выбирается _однозначно_

В данном документе нет понятия «ключевая нода». Это во-первых. Во-вторых, исходно запрос можно слать любым из k узлов, находящихся в k-bucket'е, соответствующем искомому объекту. В-третьих, по этому документу одновременно шлется a запросов. В aMule a=3, ровно как по документу.

Хеш какого-то случайного поискового запроса отделён от нас примерно на 16, и хотя каждая из нод-соседок намного ближе _к нам_, но вот мат. ожидание расстояния до хеша также равно 16и, потому как _для них_ хеш также равномерно распределён в пространстве 32х битного хеша.

Какие 16? Какие 32? Вы о чем вообще? Чуть выше Вы говорили о 128. Да, это отличается от 160 из документа, но не принципиально, ибо при текущем размере сети значимыми являются бит 20.

[drBatty]

Ни фига не транслируют.
Из упомянутого выше документа:

яхз. А вот emule уже лет 5 показывает транзитные запросы... В принципе, вполне возможно и не посылать никаких транзитных запросов, один и тот же узел может последовательно обращаться ко всем узлам в цепочке, что-бы находить след. узлы. Вот только есть одна проблема: если узел A прекрасно видит узел B, а узел B узел C, то это совсем не означает, что узел A виден узлу C. А это вполне нормальная ситуация, особенно учитывая наличие ipfilter, которые банят по IP целые подсети в 64K узлов, просто потому, что в этих подсетях был замечен tor (какое отношение имеет tor к ed2k мне непонятно, но тем не менее, это факт), я просто уверен, что вероятность поиметь хотя бы один забаненный узел в цепочке из ~10 узлов практически равна 1, а значит такая сеть IRL неработоспособна. Да и зачем это? Для простоты понимания разве-что. Принципиально в идеальной сети без банлистов, где все узлы могут связаться со всеми это не играет роли.

Вот так считает distanse aMule. Ну так и? Про какую сеть Вы говорите на самом деле?

ага. "считает". А как проверяет? Вы не поверите, префиксами вида xxxxyyyyyyyy, считая yyyyyyyy эквивалентными, а xxxx любыми. Потом эти группы делятся пополам, на xxx0yyyyyyyy и xxx1yyyyyyyy, и берётся нужная группа, это и есть ветвление. А вот если получилось две группы xxx0yyyyyyyy (или две xxx1yyyyyyyy), ветвления НЕ будет. Таким образом, число ветвлений в точности равно числу разных битов, что и составляет метрику Хэмминга. Просто она явно не вычисляется, ибо нужна лишь для анализа поведения Сети Kad.

В данном документе нет понятия «ключевая нода». Это во-первых. Во-вторых, исходно запрос можно слать любым из k узлов, находящихся в k-bucket'е, соответствующем искомому объекту

это и есть "ключевые ноды"... Ну предложите лучший перевод... Вот гуглотранслятор пишет "А-ведро", ИМХО совсем коряво.

Какие 16? Какие 32?

да, ошибся. В emule 128 бит, в концепте 160. У меня вот 32 ;) Разница не принципиальна.

Т.е. врут в русской вике. Впрочем, как всегда.

не врут, как это не парадоксально. И этому есть простое объяснение...

[watashiwa_daredeska]

я просто уверен, что вероятность поиметь хотя бы один забаненный узел в цепочке из ~10 узлов практически равна 1, а значит такая сеть IRL неработоспособна.

Неверный вывод. Перечитайте еще раз документ, который Вы так не любите. В сети Kademlia предусмотрены иные средства для борьбы с недоступностью узлов. Что там наворачиватели в eMule наворотили — то мне неведомо, но в Kademlia этого нет.

ага. "считает". А как проверяет?

Что значит, проверяет? Сравнивает? "<", ">".

Потом эти группы делятся пополам, на xxx0yyyyyyyy и xxx1yyyyyyyy, и берётся нужная группа, это и есть ветвление.

Таким образом, число ветвлений в точности равно числу разных битов, что и составляет метрику Хэмминга.

А не подскажете, а нужная группа «берется», когда бит разный или когда одинаковый?

А вот если получилось две группы xxx0yyyyyyyy

Ик… У меня икота получилась. Ик… Две. Какие две группы? Откуда?

не врут, как это не парадоксально. И этому есть простое объяснение...

Её писали Вы? :)

Всё, дошли до финального аккорда. Дальше только в юмор.

[watashiwa_daredeska]

Так, к слову, название «Kademlia» и ее архитектуру придумали как раз те два мужика, которые написали ту статью, которая, как Вы говорите, «неправильная». Как по мне, эта статья неправильной быть не может по определению, ибо она и является определением Kademlia. Если кто-то реализовал p2p как-то по-другому, то это уже не Kademlia.

[drBatty]

Неверный вывод. Перечитайте еще раз документ, который Вы так не любите. В сети Kademlia предусмотрены иные средства для борьбы с недоступностью узлов. Что там наворачиватели в eMule наворотили — то мне неведомо, но в Kademlia этого нет.

та я прочитал уже. на самом деле, этот документ я уже читал несколько лет назад. ну вот сегодня перечитал, оно конечно полезно.
А в [ea]mule единственная _рабочая_ IRL реализация, нравится вам это, или нет...

Что значит, проверяет? Сравнивает? "<", ">".

не. Сначала &= mask, потом <>0. эту самую mask постоянно сдвигает влево, можете сами почитать свой концепт, или сырцы мула. Может и не маску влево, а сам хеш вправо, не помню... Какая разница-то?

А не подскажете, а нужная группа «берется», когда бит разный или когда одинаковый?

конечно. в вашем же любимом (: документе прямо сказано, что делится, когда биты разные, если биты одинаковые, то это один и тот же bucket. Разными биты будут только если приращение к метрике Хэмминга равно 1, в противном случае приращение равно нулю, и ничего делить не нужно. В этом посте я уже привёл алгоритм поиска метрики, ессно он избыточен, ведь нам придётся вычислить метрику для всех нод, и отобрать наименьшие, это можно сделать и быстрее, если явно не считать метрику, а брать просто XOR, но учитывать только младшие биты, начиная с нулевого. Результат будет эквивалентный, а именно искомый k-bucket или проще - список ближайших нод. Когда мы встречаемся с неоднозначностью, нам надо совершить прыжок к одному из bucket, очевидно, это можно сделать двумя способами:
1. прочитать список одной из найденных нод (неважно какой из них, важно, что-бы выбор был однозначным, например старшие биты(xxxx) образовывали-ли минимальное число).
2. делегировать выбор направления одной из найденных нод.
Лично мне очевидно, что второй способ лучше, ибо
а) меньше трафик - достаточно отправить лишь один запрос, а не качать весь список.
б) третья нода доступна с т.з. второй ноды, и эта доступнось _уже_ проверялась (и регулярно проверяется), иначе бы третья нода была-бы исключена из списка второй. Для второй ноды относительно первой это тоже верно, но для третьей относительно первой - нет. Мало того, третья нода заведомо _не ближе_ второй с т.з. первой, ибо, если бы это было-бы не так, то первая нода захавала-бы третью в свой список(если конечно третья доступна для первой), в этом случае транзитной стала-бы третья, а не вторая. Но мы вышли на третью через вторую.
Однако, с т.з. алгоритма, нет никакой разницы, кто принимает решения о роутинге пакетов, это может быть и некий абстрактный вселенский разум^W^Wнекий центральный сервер, просто устойчивость и живучесть сети будет значительно выше, если каждая нода сама принимает решение о роутинге пакетов среди _своих_ соседок. Оно ей виднее же.

Ик… У меня икота получилась. Ик… Две. Какие две группы? Откуда?

про резку k-bucket перечитаем? Ещё раз для полного понимания?

Её писали Вы? :)

нет конечно. Вы же знаете, я терпеть не могу википедию. Как обычно: статью правил человек, который общался с человеком, с которым общался я... как-то так...

Так, к слову, название «Kademlia» и ее архитектуру придумали как раз те два мужика, которые написали ту статью, которая, как Вы говорите, «неправильная». Как по мне, эта статья неправильной быть не может по определению, ибо она и является определением Kademlia. Если кто-то реализовал p2p как-то по-другому, то это уже не Kademlia.

Когда придумали BWT, придумщики тоже смеялись: 1000Гб оперативной памяти в 1994 году было смешно. В 2012ом тоже. И тем не менее, именно этот алгоритм работает в bzip2, причём жрёт он совсем не 1000Гб, а всего лишь

Код: Выделить всё

                  Compress   Decompress   Decompress   Corpus
           Flag     usage      usage       -s usage     Size

            -1      1200k       500k         350k      914704
            -2      2000k       900k         600k      877703
            -3      2800k      1300k         850k      860338
            -4      3600k      1700k        1100k      846899
            -5      4400k      2100k        1350k      845160
            -6      5200k      2500k        1600k      838626
            -7      6100k      2900k        1850k      834096
            -8      6800k      3300k        2100k      828642
            -9      7600k      3700k        2350k      828642

вот идите и почитайте про этот алгоритм, и подумайте, что там упоминается квадратная матрица N*N в оперативной памяти.

Повторяю ещё раз: алгоритмы от математиков IRL не приживаются as is, их нужно менять...

[Crazy]

т.е. в качестве сервера будут выступать клиентские системы, возможно организованные в облако.

Чье облако и кто будет платить за электричество? Смотрим на тот же OpenStack и видим те же сервера.

[watashiwa_daredeska]

не. Сначала &= mask, потом <>0. эту самую mask постоянно сдвигает влево, можете сами почитать свой концепт, или сырцы мула.

В концепте нет никаких mask. Там это слово даже не упоминается.

В сырцах aMule поиск ведется не так. Просто сравнивается префикс. Функция Kademlia::CRoutingZone::GetClosestTo, src/kademlia/routing/RoutingZone.cpp:552.

Да Вы, блин, издеваетесь. Постоянно указываете, что где-то что-то реализовано так, как Вы говорите, я Вам перечитываю, и оказывается, что оно и в документе описано не так, и реализовано не так. Подите к черту, учитесь читать сами.

[drBatty]

Чье облако и кто будет платить за электричество?

клиенты, понятное дело...

В концепте нет никаких mask. Там это слово даже не упоминается.

ага. ну до названий переменных конечно необходимо доковыряться... :(

В сырцах aMule поиск ведется не так. Просто сравнивается префикс.

ну и как-же можно "сравнить префикс"? расскажите тупому? Я всю жизнь думал, что, для сравнения первых 5и бит числа (и только их) нужно выполнить (для байтов)
x &= 0b11111000;
y &= 0b11111000;
а потом сравнивать x и y.
У вас есть другой способ?

Да Вы, блин, издеваетесь.

я? не...

Постоянно указываете, что где-то что-то реализовано так, как Вы говорите, я Вам перечитываю, и оказывается, что оно и в документе описано не так, и реализованио не так. Подите к черту, учитесь читать сами.

и может таки вам научится понимать прочитанное, а не подлавливать меня на разных подробностях реализации, типа того, что вы в тексте слово "mask" не нашли? Или, что дескать в тексте взяли для примера 160 бит, в emule взяли 128 бит, а я вот зачем-то взял 32 бита. Да какая разница собственно, как это именно всё считается? Алгоритм-то один и тот же, и не зависит от числа бит и названия переменных.

Хотя вам этого видимо не понять. Потому лучше закроем эту тему...

[Crazy]

Чье облако и кто будет платить за электричество?

клиенты, понятное дело...

Сейчас сижу и слушаю Баха с http://music.yandex.ru/ совершенно бесплатно.
Теперь ты предлагаешь платить? Я не хочу платить!

[sash-kan]

Сейчас сижу и слушаю Баха с http://music.yandex.ru/ совершенно бесплатно.

а кто за интернет и электричество платит?

[watashiwa_daredeska]

может таки вам научится понимать прочитанное

Понимаете ли, я приводил Вам цитаты, которые подтверждают мою точку зрения. Эти цитаты можно найти в статье и в исходниках. Теперь Ваша очередь. Приведите мне цитату, которая подтверждает Ваши слова о расчете метрики указанным Вами способом и особенно про Хэмминга.

ну и как-же можно "сравнить префикс"?

Итак, приведу алгоритм, описанный в статье и реализованный в aMule.

Определения.
k-bucket — список длиной ≤ k, хранит {IP, Port, ID} узлов.
N — число узлов в сети.
Prefix(ID1, ID2) = длина общего префикса ID1 и ID2.
Distance(ID1, ID2) = ID1^ID2.

Состояние узла.
1. Каждый узел имеет ID. ID нашего узла обозначим OurID.
2. Узел хранит динамический массив k-bucket'ов, B. Длина Blen массива меняется с течением времени. k-bucket'ы B[i] для i < Blen-1 хранят узлы с ID: Prefix(ID, OurID) = i. B[Blen-1] хранит узлы с ID: Prefix(ID, OurID) ≥ Blen-1.

Обновление массива B.
Массив обновляется не только при получении информации о новом узле, но и при практически любой успешной коммуникации с некоторым узлом.
0. Исходное состояние — один k-bucket, содержащий единственный «затравочный» узел.
1. Допустим, мы получаем информацию об узле {NewIP, NewPort, NewID}.
2. Plen = Prefix(NewID, OurID).
3. Если Plen ≥ Blen-1, то Plen=Blen-1, goto our-0, иначе goto update-0.

update-0. Если B[Plen] содержит меньше, чем k элементов, добавляем новый узел в конец k-bucket'а, return.
Иначе (если B[Plen] полностью заполнен):
update-1. Если NewID уже содержится в k-bucket'е, перемещаем его в конец. return.
Иначе (B[Plen] не содержит NewID):
update-2. Посылаем PING узлу B[Plen][0].
update-3. Если B[Plen][0] не ответил, выкидываем его, помещаем новый узел в конец k-bucket'а, return.
update-4. Если B[Plen][0] ответил, перемещаем его в конец k-bucket'а, новый узел выбрасываем, return.

our-0. Если B[Plen] содержит меньше, чем k элементов, добавляем новый узел в конец k-bucket'а, return.
Иначе (если B[Plen] полностью заполнен):
our-1. Если NewID уже содержится в k-bucket'е, перемещаем его в конец. return.
Иначе (B[Plen] не содержит NewID):
our-2. Посылаем PING узлу B[Plen][0].
our-3. Если B[Plen][0] не ответил, выкидываем его, помещаем новый узел в конец k-bucket'а, return.
our-4. Если B[Plen][0] ответил, добавляем новый k-bucket B[Blen], и раскладываем элементы, включая новый узел, по B[Blen-1] и B[Blen] в соответствии с их префиксами. return.

Таким образом, очевидно, что в пределе Blen ~ O(log_2 N). По построению ясно, что bucket'ы из B полностью и без пересечений покрывают всё пространство ключей.

RPC-вызов FIND_VALUE(ID).
0. Если наша нода хранит объект с заданным ID, возвращаем его.
1. Plen = Prefix(ID, OurID).
2. Если Plen ≥ Blen-1, то Plen = Blen-1.
3. Результат = B[Plen]. Если набралось меньше k, дополняем результат узлами из B[i], где Plen < i ≤ Blen-1, по возрастанию. Если набралось меньше k, дополняем узлами из B[i], где 0 ≤ i < Plen, по убыванию. Возвращаем результат, даже если его длина < k.

Поиск объекта с ключом ID.
0. Делаем локальный вызов FIND_VALUE(ID). Если объект найден, return. Если нет, инициализируем массив C возвращенным списком узлов. Сортируем C по Distance(C[i], ID).
1. Вызываем FIND_VALUE(ID) на alpha ближайших к ID узлах из C. Параллельно.
2. Если вызов FIND_VALUE вернул значение, return.
3. Если вызов FIND_VALUE вернул список узлов, объединяем этот список с C (сортируем по Distance(C[i], ID), оставляем k элементов с наименьшей метрикой).
4. Вызываем FIND_VALUE у ближайшего к ID узла из C, который еще не опрашивали. Goto 2. Если же таких узлов не осталось, возвращаем «не найдено».

По построению массива B очевидно, что для узлов из B[Plen], для Plen < Blen-1, выполняется Prefix(B[Plen][i], ID) = Plen+1 и, рассуждая аналогично, они возвращают узлы, которые имеют общий префикс Plen+2. Т.е. длина общего префикса увеличивается на 1 на каждом шаге. Т.е. число вызовов RPC для поиска ~ O(log_2 N).


Вопросы и задания.
0. Всё ли правильно?
1. Где здесь подсчет числа единичных битов?
2. Где здесь расстояние Хэмминга?
3. В принципе, для каждого B[i] можно установить диапазон IDmin, IDmax ключей, которые попадают в этот bucket и искать нужный bucket обчными сравнениями. Где здесь маски и <<, >>?

[Crazy]

Сейчас сижу и слушаю Баха с http://music.yandex.ru/ совершенно бесплатно.

а кто за интернет и электричество платит?

Раз трафик идет с сервера yandex, то логично, что за электричество которое потребляет сервер раздающий мне музыку платит yandex.

[watashiwa_daredeska]

а не подлавливать меня на разных подробностях реализации

Закапываться в подробности пришлось, т.к. Вы совершенно не в состоянии озвучить оценки трудоемкости, но при этом безапелляционно заявляете, что Kademlia может заменить Google. Собственно, приведенное мной выше описание части функционирования Kademlia показывает, что latency для простого поиска объекта по ключу зависит от размера сети как O(log_2 N). Т.е. растет с ростом числа узлов. Но сама Kademlia — это лишь примитивный key-value storage. На этом хранилище еще нужно построить полнотекстовую поисковую систему. Это уже будет следующий вопрос к Вам: как построить полнотекстовую систему масштабов всего интернета на key-value storage со временем поиска в несколько секунд?

[Ism]

Это уже будет следующий вопрос к Вам: как построить полнотекстовую систему масштабов всего интернета на key-value storage со временем поиска в несколько секунд?

Вот мы и возвращаемся к теме избыточности данных, поисковые системы нужно научить забывать неактуальные данные. Нужно ввести уровни хранения данных.
При попытке решить проблему возвращаемся к схеме работы DNS

[watashiwa_daredeska]

поисковые системы нужно научить забывать неактуальные данные.

А неактуальные — это какие? Сейчас поисковые системы тоже не особо помнят исторические версии страниц, а пока страница в интернете присутствует — она актуальна. Нет?

При попытке решить проблему возвращаемся к схеме работы DNS

DNS — плохо распределенная система с небольшим числом points of failure. Кроме того, DNS не занимается полнотекстовым поиском. А полнотекстовые поисковые системы построены на иных инструментах, нежели распределенный по ненадежным узлам key-value storage.

[drBatty]

Сейчас сижу и слушаю Баха с http://music.yandex.ru/ совершенно бесплатно.
Теперь ты предлагаешь платить? Я не хочу платить!

ты УЖЕ платишь 100%. Идея в том, что ты будешь платить 101%, получая взамен систему поиска/хранения информации. Фишка в том, что тебе не нужны 100% твоих ресурсов, за которые ты тем не менее платишь, так почему-бы не отдать 1% из них в общее пользование, но так, что-бы при необходимости ты использовал-бы 100500%?

сам посчитай:
1. загрузка канала связи?
2. загрузка CPU?
3. загрузка RAM?
4. загрузка HDD?
всё это у тебя <<100%, но платишь ты как раз за ВСЕ 100%. Тебе не жалко своих денег?

имеют общий префикс Plen+2. Т.е. длина общего префикса увеличивается на 1 на каждом шаге.

1. Где здесь подсчет числа единичных битов?
2. Где здесь расстояние Хэмминга?

а что такое в вашей схеме "префикс"?
судя по этому описанию:

Prefix(ID1, ID2) = длина общего префикса ID1 и ID2.

мы его считаем так:

Код: Выделить всё

uint128 prefix_length(uint128 id1, uint128 id2)
{
 lp = 0;// все переменные uint128
 p = 0;
 do{
  p |= (1<<127);
  if(((id1 ^ id2) & p) == 0)
   return lp;
  lp++;
  pp = p;
  p >>= 1;
 }while(p != pp);
 return 128;
}

или я ошибаюсь, и длинна общего префикса вычисляется иначе?

3. В принципе, для каждого B[i] можно установить диапазон IDmin, IDmax ключей, которые попадают в этот bucket и искать нужный bucket обчными сравнениями. Где здесь маски и <<, >>?

их нет в явном виде. как и метрики.
вы не поверите, но никакого бинарного дерева в коде тоже нет. А вот в статье есть...

Закапываться в подробности пришлось, т.к. Вы совершенно не в состоянии озвучить оценки трудоемкости,

да, не в состоянии. Kademlia для этого не подходит, а некая "улучшенная Kademlia" существует только в моей голове...

но при этом безапелляционно заявляете, что Kademlia может заменить Google.

нет. я такого не заявлял. я лишь указал на то, что сеть, с числом узлов как в Kad'е, и работающая как Kad, _может_ в теории заменить Google для _некоторого_ класса запросов. Этот класс запросов будет пересекаться с тем, что умеет google, а вопрос о том "что лучше, что хуже" - я и не подымал, что делить шкуру не убитого медведя? Я лишь предложил пойти, и его пристрелить, для начала. А делить начали вы...

latency для простого поиска объекта по ключу зависит от размера сети как O(log_2 N). Т.е. растет с ростом числа узлов.

ну вот тут вы ошибаетесь, смешивая пространство имеющихся в сети id и пространство имеющихся узлов. А самое главное, вы забываете о том, что Kad строился с расчётом на очень слабые каналы связи, и очень слабые компьютеры, потому каждый узел kad'а имеет ничтожную мощность, и соответственно огромную latency. Потому и время поиска такое большое. И выше я уже говорил о том, что это характеристика самой сети, и о том, почему никто не хочет эту latency снижать.

Это уже будет следующий вопрос к Вам: как построить полнотекстовую систему масштабов всего интернета на key-value storage со временем поиска в несколько секунд?

это уже будет следующий вопрос...

[drBatty]

Вот мы и возвращаемся к теме избыточности данных, поисковые системы нужно научить забывать неактуальные данные. Нужно ввести уровни хранения данных.

не нужно. одноранговые сети типа када уже вполне себе умеют забывать данные, т.е. если есть в Сети некий файл, то Сеть знает, где его искать. Но если искать его негде, то через некоторое время, Сеть о нём забывает.

Ещё быстрее Сеть забывает об источнике, который перестал быть источником некого файла (при этом остался участником Сети), это делает невозможным выяснение того, кто и когда вбросил этот файл.

При попытке решить проблему возвращаемся к схеме работы DNS

решите пожалуйста проблему корневых серверов: кто их будет контролировать, и кто будет платить за их работу?

А полнотекстовые поисковые системы построены на иных инструментах, нежели распределенный по ненадежным узлам key-value storage.

т.е. тупик? NoWay?

[Crazy]

Сейчас сижу и слушаю Баха с http://music.yandex.ru/ совершенно бесплатно.
Теперь ты предлагаешь платить? Я не хочу платить!

ты УЖЕ платишь 100%. Идея в том, что ты будешь платить 101%, получая взамен систему поиска/хранения информации.

В случае music.yandex.ru я не плачу за: музыкальный контент, за сервер на котором находиться этот контент, за надежность и обслуживания этого сервера.

Фишка в том, что тебе не нужны 100% твоих ресурсов, за которые ты тем не менее платишь, так почему-бы не отдать 1% из них в общее пользование, но так, что-бы при необходимости ты использовал-бы 100500%?

Я живу в Питере и у меня канал данных асинхронный, когда я запускаю TES V то использую все 100% своих ресурсов.
Всякие torrent не плохо убивают HDD.

[watashiwa_daredeska]

а что такое в вашей схеме "префикс"?

Общий префикс двух id — это старшие биты, которые равны у id1 и id2. Не единичные, любые — хоть 1, хоть 0. К расстоянию Хэмминга и подсчету единичных битов префикс не имеет ровно никакого отношения.

их нет в явном виде. как и метрики.

Метрика есть в явном виде. А вот префиксов может не быть совсем. Как я уже сказал, можно переформулировать поиск в B так, что останется только сравнение метрик <, >. Потому что очевидно, что Distance(B[i][j], OurID) > Distance(B[i+1][k], OurID), для любых i, j, k. Так что можно обойтись банальной дихотомией и слово Prefix исчезнет совсем. И хотя это будет абсолютно эквивалентная замена, связь с описанием Kademlia будет уже не так очевидна.

вы не поверите, но никакого бинарного дерева в коде тоже нет. А вот в статье есть...

Да, оно не выражено в явном виде, но оно есть. Точно так же, как heap обычно хранится в массиве, хотя это дерево :) Собственно, префиксы в данном описании и есть потому, что дерево и спуск по дереву. В коде aMule дерево присутствует в совсем явном и совершенно полном виде — с внутренними узлами и листьями, что на мой взгляд совершенно избыточно, но это их проблемы.

ну вот тут вы ошибаетесь, смешивая пространство имеющихся в сети id и пространство имеющихся узлов.

Не смешиваю. Трудоемкость поиска действительно зависит только от размера сети. Если, конечно, число объектов, хранящихся на одном узле не будет настолько гигантским, что поиск на одном узле станет сопоставим с сетевыми задержками.

Или Вы имеете в виду «недоступные» узлы за всякими NAT'ами? Это, совершенно отдельная песня, сама Kademlia не предлагает никакого решения. Даже если предположить, что сеть умеет каким-либо образом «проксировать» запросы к «недоступным» узлам, то:
1. Это чисто техническое дополнение и никак не сказывается на трудоемкости.
2. Это вызывает определенные дополнительные трудности, которые надо решать. Например, DDoS, да и вообще балансировка «моего» трафика и транзитного.

Kad строился с расчётом на очень слабые каналы связи, и очень слабые компьютеры, потому каждый узел kad'а имеет ничтожную мощность, и соответственно огромную latency.

Простите, этого я не понял. Звучит как «Digger писался для машин с ничтожной мощностью, поэтому на современных мощных компах он безбожно тормозит».

т.е. тупик? NoWay?

Про распределенные поисковые системы — скорее всего способ есть. У YaCy, конечно, отстойное качество результатов, но это лишь первая ласточка. Однако Kademlia не будет настолько важной его составляющей, чтобы кому-нибудь пришло в голову сказать, что поиск построен на Kademlia, как никому не приходит в голову сказать, что поиск гугла построен на BigTable.

В случае music.yandex.ru я не плачу за: музыкальный контент, за сервер на котором находиться этот контент, за надежность и обслуживания этого сервера.

Платите, только косвенно. Яндексу платят рекламодатели, а рекламодателям платят их покупатели. Т.е. это такая интересная схема — ты платишь независимо от того, пользуешься или нет, но те, кто пользуются, делают это якобы бесплатно. Как советская медицина.

[Crazy]

В случае music.yandex.ru я не плачу за: музыкальный контент, за сервер на котором находиться этот контент, за надежность и обслуживания этого сервера.

Платите, только косвенно. Яндексу платят рекламодатели, а рекламодателям платят их покупатели. Т.е. это такая интересная схема — ты платишь независимо от того, пользуешься или нет, но те, кто пользуются, делают это якобы бесплатно. Как советская медицина.

Ты видишь тут рекламу?

[watashiwa_daredeska]

Ты видишь тут рекламу?

А при чем тут это?

[Crazy]

Ты видишь тут рекламу?

А при чем тут это?

Рекламодатели платят либо за показ, либо за клик по баннеру. Ни того и ни другого там нет.

[watashiwa_daredeska]

Рекламодатели платят либо за показ, либо за клик по баннеру. Ни того и ни другого там нет.

Дополнительный уровень косвенности. Сервис music повышает общую посещаемость и привлекательность yandex.ru, завлекая пользователей в другие сервисы на этом ресурсе, повышая таким образом общие показы рекламы.

[Crazy]

Дополнительный уровень косвенности. Сервис music повышает общую посещаемость и привлекательность yandex.ru, завлекая пользователей в другие сервисы на этом ресурсе, повышая таким образом общие показы рекламы.

Рекламу режет adblock. Кроме рекламы можно те же сервисы, но с другими условиями, предоставлять за $$$.

[watashiwa_daredeska]

Рекламу режет adblock.

Платите Вы не в момент просмотра рекламы, а в момент покупки товаров. Любых. Причем, платите не только за рекламу в Яндексе, но в зависимости от товара и за рекламу на ОРТ, НТВ, … Даже если телевизор не смотрите.

Кроме рекламы можно те же сервисы, но с другими условиями, предоставлять за $$$.

Можно. Но это не значит, что Вы перестанете платить за рекламу :)