Все началось спонтанно из-за банального любопытства, стало интересно сколько всего пользователей в ВК.
Оказалось есть открытый каталог https://vk.com/catalog.php и сейчас их 493 000 000 человека, интересно, а сколько из них более менее реальных. Открытая статистика говорит о 93 000 000 в месяц. Если проверять по одному человеку в день, то получается нам нужно около 15 лет, хм вряд ли тогда данные будут актуальны.
Скрытые друзья ВКонатке.
В далеком 2011 году, Дуров заявил, что социальная сеть со скрытыми друзьями, а на тот момент 90% пользователей скрыли список друзей в своих настройках, похожа на какую-то аську (о боже кто еще помнить сейчас что это) и открыл списки всех пользователей, добавив возможность скрыть 15 человек, потом увеличили до 30.
Интересно, а реально найти этих скрытых друзей, логично что, если взять списки друзей двух людей, которые дружат, и не найдя там кого-то из них, мы можем сделать вывод, что один из них, у кого другого друга нет – скрывает его. Фух слишком сложно, допустим есть друг 1:2,5,8,10 и друг 2:5,4,87,49 (после двоеточия друзья) – это говорит о том, что пользователь 2 скрывает пользователя 1.
Задача довольно простая просканировать списки друзей 490 000 000 пользователей и найти все упоминания определенного id и затем сравнить получившийся список со списком друзей этого самого id. Ах да, 15 лет.
Другие сервисы поиска скрытых друзей
Прошерстив интернет я нашел несколько сервисов которые получают эту информацию, алгоритм как я понял такой, часто вы даете свой токен этому сервису, и ява скрипт с помощью ресурсов вашего компьютера собирает списки друзей друзей, тех кто поставил лайки, оставил комментарии, то есть берутся не все пользователи ВК, а только определенная выборка. Если скрытый друг никак не спалился на странице, то его можно и не найти. Запустив сканирование на компе одного пользователя трафик перевалил за 100 мегабайт, так что, если у вас ограниченный интернет пользуйтесь с осторожностью такого рода сервисами.
Скачиваем списки друзей всех пользователей
Сразу скажу, что образования программиста у меня нет и все учиться в процессе, информации в инете море.
Прикинув что 15 лет — это многовато, установил для себя границу в минимум 800 пользователей в секунду для того чтобы уложится в 7 дней.
В итоге на php был написан скрипт дающий производительность в 57 пользователей в секунду и 15 потоков давали нужную скорость, укладываясь в ресурсы сети и компьютера.
Оказывается, все это занимает место и причем не малое, если бы все пользователи были с друзьями, то база была бы в 382 гигабайта.
Асоциальная сеть
Ну буду вас долго томить процесс сбора завершился без эксцессов, и я получил 200 359 065 id, которые имеют друзей, в итоге более чем у половины друзей нет. Вся эта информация заняла 156 гигабайт. Эмпирических путем было выявлено что в среднем 107 друзей у пользователя.
База msql в 156 ГИГОВ!!!!
Оказывается, это много, поиск по алгоритму выше вызывает сканирование таблицы, то есть все 156 гигов, а если скорость винчестера даже 200 мегабайт в секунду это 13 минут на одного пользователя, а их блин 200 миллионов.
Немного подумав было решено перевернуть задачу и искать не скрытых друзей, а скрывающих, а потом полученные данные опять перевернуть, и мы получим то что нам нужно. Давайте посчитаем (откинем тот момент что писать быстрые алгоритмы на php и msql когда ты не знаешь как писать что то вообще, не так то легко и количество вариантов которые пришлось оттестировать). Нужно выполнить 200 000 000 *107 запросов к базе вида SELECT id FROM `2` where id='$hideid' and LOCATE(',$id,', friends), понятно что мы получим лишние варианты, но отсеивать мы будем их в процессе выдачи, все равно надо будет это делать, пока собиралась база 7 дней происходили изменения.
С помощью ноутбука и компьютера удалось добиться производительности в 100 000 000 запрос в час.
Проц грузился почти на 100%, нагрузка на диск суммарно более 300 магабайт в секунду.
За ноут было конечно страшно, временами температура на проце прыгала до 95 градусов, а ниже 70 и не опускалась, в итоге стресс тест в 8 дней он прошел.
Результаты вы можете посмотреть на сайте https://online-vk.ru/