Instagram создал собственную блестящую систему, которая анализирует около 85 миллионов новых фотографий и 700 миллионов хэштегов каждый день от более чем 500 миллионов пользователей, чтобы вычислять актуальный контент в реальном времени.

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

Что такое популярный хэштег?

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

Итак, они определили три основных элемента хорошего трендового хэштега:

1. Популярность. Популярный хэштег должен заинтересовать многих людей.

2. Новинка: это должно быть что-то новое. Значит, люди не писали об этом с такой же интенсивностью.

3. Своевременность: должна появиться во время соответствующего события.

Как определить трендовый хэштег?

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

Пример -

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

И наоборот, каждый день с тегом #love публикуется более 100 000 сообщений, так как это очень распространенный и популярный хэштег. Даже если каждый день будет наблюдаться 10 000 дополнительных постов (всего 110 000), этого будет недостаточно, чтобы считаться трендовым.

Как Instagram это реализовал?

Изначально для каждого хэштега Instagram сохранял счетчики публикаций, опубликованных с использованием хэштега, в каждом 5-минутном окне за последние 7 дней.

Счетчик для хэштега h для окна времени (t-5 -> t) = C(h,t)

После нормализации вероятность хэштега h в момент времени t = P(h,t)

На основе этих данных они построили модель ИИ, которая будет предсказывать ожидаемое количество счетчиков C’(h,t) и вероятность P’(h,t) в момент времени t.

Итак, показатель расхождения KL (это мера того, насколько одно распределение вероятностей отличается от другого распределения вероятностей) =

P(h,t) * ln (P(h,t) / P’(h,t))

Здесь,

P(h,t) -> Популярность

P(h,t) / P’(h,t) -> Новизна

т -› Своевременность

И на основе t они смогли показать популярные хэштеги в реальном времени.

Проблема точного прогнозирования

Это было не так просто, как кажется. Во время реализации Instagram столкнулся с множеством проблем.

1. Хранение счетчиков для всех хэштегов для каждого 5-минутного окна требовало большого объема памяти
2. Высокая вероятность случайных всплесков использования хэштегов, поскольку Instagram просматривал данные 5-минутного окна
3. Большинство хэштегов получили ~ 0 новых сообщений, поэтому они не смогли вычислить показатель расхождения KL (из-за деления на ноль)

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

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

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

Но, тем не менее, прогнозируемая базовая вероятность по-прежнему была нулевой для нескольких хэштегов, и вычисление расхождения KL было невозможно. Чтобы решить эту проблему, было замечено, что большинство хэштегов не получают более трех сообщений в час. Таким образом, для этих хэштегов они просто отметили это, как если бы они видели 3 сообщения за этот период времени, и сбросили счетчики для всех этих хэштегов. Это сократило использование памяти на ›90%.

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

Рейтинг популярных хэштегов

Следующей задачей было ранжировать все хэштеги на основе их модности.

Инстаграм-подход -

1. Совокупные хэштеги для данной страны/языка
2. Отсортируйте их по показателю расхождения KL
3. Установите нижнюю границу, чтобы избавиться от неинтересных популярных хэштегов
4. Возвращайте список интересные трендовые хэштеги

НО они столкнулись с одной интересной проблемой здесь. Допустим, проходит акция #hashnodeHappyHours и о ней много говорят. Как только событие завершится, количество новых постов с использованием этих хэштегов уменьшится. Следовательно, его показатель KL также быстро уменьшится, и хэштег больше не будет в тренде, НО людям обычно нравится смотреть посты с мероприятия в течение нескольких часов после его окончания.

Чтобы преодолеть это, для определения TTL для предыдущих трендов использовалась функция экспоненциального затухания.

Значение экспоненциального затухания

Sd(h, t) = SM(h) * (1/2)^((t — tmax)/период полураспада)

SM(h) — максимальный балл KL для хэштега.
tmax — время, когда показатель KL был максимальным

После установки *half-life* на два часа (SM(h) уменьшается вдвое каждые два часа), хэштег по-прежнему будет отображаться в трендах.

Группировка похожих трендовых хэштегов

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

Чтобы рассчитать матрицу сходства для каждой пары трендовых хэштегов, система группировки хэштегов опирается на совпадения, расстояние редактирования (используя алгоритм расстояния Левенштейна, который эффективно вычисляет минимальное количество односимвольных правок между двумя словами) и распределение тем (используя частоту терминов). обратная частота документа).

Серверная система

Бэкенд-система Trending спроектирована как приложение для обработки потоков с четырьмя узлами.

1. Препроцессор — взаимодействует со службой мультимедиа, извлекает метаданные публикации и подготавливает все данные для следующего шага.

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

3. Scorer. Он хранит в памяти агрегированные по времени счетчики для каждого качественного хэштега и вычисляет рейтинг тренда.

4. Ranker. Он собирает все хэштеги вместе с их рейтингом тенденций и ранжирует их на основе определенных правил.

Он собирает все хэштеги вместе с их рейтингами и ранжирует их на основе определенных правил.

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

Источник — инженерные блоги Instagram

Спасибо за чтение. Буду рад любым исправлениям и дополнениям!

Я пишу о системном дизайне, бэкэнд-инжиниринге и веб-технологиях по адресу: https://blog.pankajtanwar.in/