На другом конце провода стоял невообразимый гвалт.
Кто-то во всю мочь надрывался, подзывая администратора: «Докинь десятку на третий терминал в зоне Си!» Соседний стол со стуком содрогнулся от удара кулака: «Ты сдурел, что ли? Зачем слепишь?» Этот хаос то и дело разбавлялся кашлем и чирканьем зажигалок.
Чэнь Чжо чуть отодвинул трубку стационарного телефона от уха.
— Погоди секунду.
Донеслось крикливое эхо голоса Чу Гэ, после чего посхрипывал стул, который волокли по полу. Шум заметно стих, словно собеседник отошел в какой-то угол.
— Так, я на связи. Ручку нашел.
Чу Гэ прижал трубку плечом к уху, зажав во рту леденец. Правая рука шарила по клутку сплетенных проводов от клавиатуры, пока не нащупала шариковую ручку.
Бумаги на столе не оказалось. Оглядевшись, он схватил пустую коробочку из-под лапши быстрого приготовления и оторвал картонную крышку, испачканную капельками красного чили-масла. Перевернув ее обратной стороной...
Изнанка крышки слегка отсырела, но писать на ней все еще было можно.
Чэнь Чжо стоял у окна в гостиной, разглядывая тонкую корку льда на стекле. Протянув руку, он провел по нему пальцем, оставляя чистую черту.
— Как они спроектировали базу данных в Столице? — поинтересовался Чэнь Чжо.
— Реляционную. Обычная древовидная структура.
Чу Гэ пару раз с хрустом надкусил леденец.
— Они хотят запустить социальную сеть по принципу «шести рукопожатий». Базовая логика проста: если я — А, и знаком с Б, база создает между нами связь. Запросить список моих друзей — плевое дело. А вот друзей моих друзей... система еще кое-как переваривает.
Голос Чу Гэ звучал хрипло — сказывалась бессонная ночь.
— Но стоит копнуть до связей третьего или четвертого порядка, и если нагрузка переваливает за 200 пользователей, база начинает штамповать бесконечные вложенные соединения. Таблица с какими-то жалкими сотнями тысяч юзеров мгновенно раздувается до десятков миллионов избыточных строк.
— Тот тип из Столицы говорил, что они только что прогнали стресс-тест. 200 виртуальных аккаунтов одновременно нажали на функцию «Возможно, вы знакомы». Кулеры на сервере взвыли, как вертолетные винты, нагрузка на процессор подскочила до 100 процентов, и спустя 3 секунды база данных выпала в мертвую блокировку.
Чу Гэ вздохнул.
— Так что теперь мы в тупике. Чтобы все летало, нужно заранее просчитывать все связи и складывать их в кэш. Но для этого требуются огромные объемы памяти, а столько серверов им не потянуть. Если не предрассчитывать, а молотить запросы на лету, база падает в тот же миг, как туда заглядывает пара человек одновременно.
Выслушав его, Чэнь Чжо не спешил с ответом.
Он подошел к дивану, опустился на него, взял из фруктовницы арахис в скорлупе и легко щелкнул его в пальцах.
— Вы, компьютерщики... неужели всегда мыслите столь прямолинейно?
Стряхнув с ореха сухую шелуху, Чэнь Чжо усмехнулся.
— В каком смысле?
Чу Гэ на секунду опешил.
— Это же чистая теория графов. С чего вы пытаетесь решить задачу так, будто проводите перепись населения?
Чэнь Чжо закинул орех в рот.
— Забудь про свои вложенные запросы. Представь всех пользователей точками в многомерном пространстве. А связи между ними — соединяющие их линии.
Чу Гэ замолк, а кончик его ручки замер над крышкой от лапши.
— Построй матрицу смежности.
Голос Чэнь Чжо звучал ровно и спокойно — так, будто он объяснял первокурснику домашку по матану в университетской читалке.
— Допустим, у тебя 100 000 пользователей. Получается матрица 100 000 на 100 000, назовем ее А. Если пользователь i и пользователь j — друзья, на пересечении (i, j) стоит единица. В противном случае — ноль.
— Погоди-ка.
Чу Гэ перебил его.
— Сто тысяч на сто тысяч... это же 10 000 000 000 точек данных. Ты вообще прикидывал, сколько под это уйдет памяти? Сервер тут же загнется.
— Чу Гэ.
Чэнь Чжо тихо хмыкнул в трубку.
— У тебя в реальной жизни есть 100 000 друзей?
— Нет. Даже 10 не наберется.
честно ответил Чу Гэ.
— Ни у одного нормального человека столько нет.
отозвался Чэнь Чжо.
— Выходит, 99,99 процента ячеек в этой матрице — нули. невероятно разреженная матрица.
Пальцы Чу Гэ судорожно сжали ручку.
— В оперативной памяти не нужно хранить все эти 10 000 000 000 точек. Достаточно записать одни лишь координаты единиц.
продолжил Чэнь Чжо.
— Простейшее проецирование координат. А теперь подумай: как математически выразить поиск друзей твоих друзей — связи второго порядка?
В голове Чу Гэ завертелись мысли. Полузабытые на первом курсе понятия линейной алгебры вдруг полоснули по мозгу яркой вспышкой, прорезая туман.
— Умножение матриц,.
выпалил Чу Гэ.
— Матрица А на матрицу А. А в квадрате.
— Именно.
Чэнь Чжо поднялся, подошел к журнальному столику и налил себе стакан теплой воды.
— А в квадрате. Ненулевые значения в этой матрице и есть твои связи второго порядка. А в кубе дает связи третьего.
Чу Гэ уставился на крышку из-под лапши, а ручка в его пальцах машинально выводила круги. Дыхание участилось.
— Но вычислительная сложность матричного умножения огромна, особенно для старших степеней. Процессор все равно не вытянет.
озвучил суть проблемы Чу Гэ.
— Все потому, что ты замахнулся на слишком многое. Пытаешься просчитать всю социальную сеть разом для каждого пользователя.
Чэнь Чжо сделал глоток, смачивая горло.
— Серверу ни к чему знать, кто с кем знаком. Ему нужно ответить лишь на запрос пользователя, который сейчас находится в системе. А раз так, перемножать матрицы между собой не требуется.
Голос Чэнь Чжо звучал тихо, но для Чу Гэ эти слова прозвучали раскатом грома.
— Пользователь в сети — это вовсе не матрица. Это вектор.
Чэнь Чжо предоставил заключительную часть решения.
— Вектор, у которого на месте самого пользователя стоит единица, а всюду дальше — нули. Берешь этот одномерный вектор и умножаешь на разреженную матрицу. Одно умножение — и готов вектор его прямых друзей. Умножаешь полученный результат на матрицу снова — получаешь друзей второго порядка.

Комментарии

Загрузка...