Blog de Basile | Think, work, live

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

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

Допустим, вам надо разработать большую полностью децентрализованную P2P сеть, работающую в интернете. Например, аналог Скайпа, но совсем без серверов, с полностью равноправными участниками. Основная задача, которую вам надо решить изначально, если узлов много, например, несколько миллиардов, то как узлам найти друг друга быстро?

Допустим, узлу № 5 надо найти в сети IP-адрес узла № 8 589 934 592, как это сделать? Серверов нет, а значит нельзя обратиться к централизованному списку, в котором каждому номеру соответствует IP адрес. Обратиться ко всей сети тоже нельзя, если каждый узел начнет спрашивать у всех, то каждому узлу придется обрабатывать тысячи или даже миллионы обращений в секунду.

Выручит нас простой алгоритм деления на два. Принцип его легко понять. Представьте, что все четные узлы знают адреса друг друга и адрес одного нечетного узла, также все нечетные узлы знают адреса всех нечетных узлов и адрес одного четного числа.  Таким образом, №5 связан со всеми нечетными узлами и с одним четным. Значит, если ему надо найти № 8 589 934 592, он обращается к известному ему четному узлу, а тот ищет искомый узел среди только четных чисел, а их столько же сколько нечетных, которые мы отбросили. То есть мы сделали один шаг и уменьшили область поисков в два раза.

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

Предположим, у нас есть всего два узла на прямой линии, они связаны друг с другом напрямую, то есть знают IP-адреса друг друга, обозначим их 0 и 1. Теперь добавим второе симметричное  измерение, в котором существуют такие же 0 и 1. Добавим к их номерам по 1 на втором месте справа, обозначив таким образом, что они оба из второго измерения: 10 и 11. К номерам узлов из первого измерения мы автоматически добавляем по нулю на вторую справа позицию, чтобы обозначить, что они не из второго измерения. Свяжем каждый номер первого измерения с одним симметричным ему номером второго измерения. Теперь повторим все операции, добавив еще одно симметричное измерение, еще раз удвоив количество узлов. В итоге получим следующую картину.

Связь означает, что узлы знают IP адреса друг друга. У нас три измерения, и каждый узел может найти любой узел максимум за три шага, потому что он по номеру узла знает к узлу из какого измерения ему надо обращаться, чтобы приблизиться к искомому узлу. Если добавить еще одно измерение, то мы еще раз удвоим количество узлов, увеличим каждому узлу количество связей на одну, и увеличим макисмальное количество шагов на единицу. Но представить четырехмерное сооружение становится уже сложно. Допустим, это выглядит как-то так.

Таким образом, получаем простую формулу: два в степени “количество шагов” = “количество узлов”:

Если дано 8 589 934 592 узлов, то любой из узлов найдет любой другой узел за максимум 33 шага, поскольку 8 589 934 592 равно 2 в степени 33. При этом каждый узел будет связан только с 33 другими узлами.

Остается только вообразить себе эту роскошную 33-мерную фигуру и полюбоваться ее изяществом.

Можно поиграть и построить другие варианты фигур. Например, в первом измерении может быть не два узла, а 3, или 5, связанных друг с другом – очень мощная звезда получается, и поиск становится гораздо устойчивее. То есть, если часть узлов отключена, есть запасные пути к искомому узлу.

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

Итак, мы создали P2P сеть. Каждая вершина для нас – это IP адрес. Но это может быть и другая информация, то есть наша  звезда может представлять собой большую базу данных, которыми мы можем легко манипулировать. Координаты вершин и фигура точек в первом измерении -  это структура организации данных. Структуру мы можем задать самостоятельно, а можем скопировать уже существующую.

Например, представим, что  количество измерений у звезды – это количество страниц, которые посещает человек на определенном сайте. Цифры в номера узла отражают страницы, которые человек посетил и время, которое провел на странице. Например, 019 может означать, что человек быстро прошелся по странице 2 и задержался на странице 3 надолго. Можно немного усложнить структуру и добавить порядок посещения страниц.

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