Во-первых, количество статей и пользователей заголовка очень велико, а количество кликов еще ужаснее. Простите, если популярные статьи отображаются в режиме реального времени, например топ 100 статей с наибольшим количеством кликов за последние 8 часов. Если бы вам нужно было разработать эту функцию, как бы вы это сделали?
С этим легко справиться, redis можно сделать с помощью отсортированного набора, подсчета очков, ключ — это идентификатор статьи, не так ли?
Хороший ответ, можешь идти!
Чтобы четко услышать вопрос, 8-часовое динамическое временное окно, счет истечет. Кроме того, настолько ли мало заголовков, что это может сделать один редис? Одноклассники, подскажите, количество статей должно оцениваться как минимум в несколько сотен тысяч, количество пользователей должно оцениваться в сотни миллионов, а количество кликов должно быть не менее 1М/с.
прием данных
Параллелизм кликов 1M/s определенно должен быть распределен. Клиенты могут отложить запросы на слияние кликов для пакетной отправки, чтобы снизить нагрузку на сервер. Для простоты воспользуемся здесь протоколом HTTP. Не будем рассматривать поведение злоумышленников, смахивающих клики.
На сервере определенно будет несколько компьютеров и несколько процессов, развернутых для приема запроса клика, и полученный запрос будет отправлен в хранилище после анализа параметров. Чтобы уменьшить нагрузку на хранилище, каждый процесс может использовать небольшое окно для агрегирования данных, а данные в этом окне агрегируются и отправляются в единицу хранения через короткие интервалы времени.
хранилище данных
Данные о кликах — очень важные данные, и от них зависят интересы и предпочтения пользователя. Если такие большие данные о кликах хранятся в памяти, стоимость слишком высока. Так что не рассчитывайте вообще использовать Redis.
Использование хранилища kafka — хороший способ, поскольку механизм ZeroCopy обеспечивает высокий уровень параллелизма и низкую стоимость сохранения данных на диске. Однако данные kafka обычно имеют срок годности.Если вы хотите полностью запомнить клик пользователя для долгосрочного анализа данных, вы должны использовать hdfs.
Однако из-за потребности в статистике квазиреального времени hdfs для этого не подходит, а hdfs подходит в качестве источника данных для офлайн-статистики. Следовательно, необходимо полагаться на Kafka для получения данных, а затем потребители делают статистику в реальном времени при входе в hdfs.
Для статистики в реальном времени вы можете использовать поток искры и шторм, чтобы принять ввод kafka, или вы можете написать это самостоятельно.
Распределенный алгоритм TopN
Слишком много пользователей, и таблица пользователей разделена на 1024 подтаблицы в соответствии с хешем идентификатора пользователя. В таблице пользователей есть поле score, в котором указано количество баллов данного пользователя. Теперь мы хотим рассчитать 100 лучших пользователей с наибольшим количеством баллов и количеством баллов Как сделать запрос?
Если это одна таблица, это сделает один SQL.
select id, score from user order by score desc limit 100
Если имеется несколько подтаблиц, необходимо выполнить запрос TopN для каждой подтаблицы, а затем выполнить еще один запрос TopN для агрегированных результатов. Ниже псевдокод
candidates = []
for k in range(1024):
# 每个表都取topn
rows = select id, score from user_${k} order by score desc limit 100
# 聚合结果
candidates.extend(rows)
# 根据score倒排
candidates = sorted(candidates, key=lambda t: t[1], reverse=True)
# 再取topn
candidates[:100]
Запросы к подтаблицам могут быть распараллелены несколькими потоками для повышения эффективности агрегирования.
раздвижное окно
8-часовое скользящее окно означает, что новые данные поступают непрерывно, а старые данные постоянно удаляются. Строго говоря, точное 8-часовое скользящее окно требует, чтобы каждый фрагмент данных был строго просрочен, даже если он меньше 1 секунды, и он будет устранен сразу же, как только достигнет точки.
Плата за точность заключается в том, что нам нужно установить время истечения для каждой записи клика, само время истечения необходимо хранить, а также регулярно проверять политику истечения срока действия.куча временичтобы подтвердить, какие записи просрочены. В больших количествах это бремя, которое нельзя недооценивать.
Однако, с точки зрения бизнеса, нет необходимости быть столь точным в версии ранжирования, и отклониться на несколько минут не проблема.
Деловые компромиссы открывают возможности для оптимизации ресурсов услуг. Мы разделяем квант времени, по одному слоту в минуту для подсчета. Ниже псевдокод
class HitSlot {
long timestamp; # earlies timestamp
map[int]int hits; # post_id => hits
void onHit(int postId, int hits) {
this.hits[postId] += hits;
}
}
class WindowSlots {
HitSlot currentSlot; # current active slots
LinkedList<HitSlot> historySlots; # history unactive slots
map[int]int topHits; # topn posts
void onHit(int postId, int hits) { # 因为上游有合并点击，所以有了hits参数
long ts = System.currentTimeMillis();
if(this.currentSlot == null) { # 创建第一个槽
this.currentSlot == new HitSlot(ts);
} elif(ts - this.currentSlot.timestamp > 60 * 1000) { # 创建下一个槽，一分钟一个槽
this.historySlots.add(this.currentSlot);
this.currentSlot = new HitSlot(ts);
}
this.currentSlot.onHit(postId, hits);
}
void onBeat() { # 维护窗口，移除过期的槽，然后统计topn，30s~60s调用一次
if(historySlots.isEmpty()) {
return;
}
HitSlot slot = historySlots[0];
long ts = System.currentTimeMillis();
if(ts - slot.timestamp > 8 * 60 * 60 * 1000) { # 过期了8小时，移掉第一个
historySlots.remove(0);
topHits = topn(aggregateSlots(historySlots)); # 计算topn的帖子
}
}
}
Вышеприведенный код представляет собой логику каждого распределенного подузла.Поскольку это псевдокод, проблема блокировки не будет подробно описана. Его цель — регулярно поддерживать 8-часовое статистическое окно и собирать в памяти горячие посты topn. Данные для этого топа не в реальном времени, с коротким временным окном около 1 минуты.
задача на время
У каждого дочернего узла будет запланированная задача, отвечающая за ведение статистического окна, просроченные и просроченные статистические данные, а также подсчет локальных топовых горячих сообщений.
Теперь, когда каждый дочерний узел имеет свои собственные локальные горячие сообщения topn, необходим главный узел для суммирования этих локальных горячих сообщений, а затем для вычисления глобальных горячих сообщений.
Мастер-узел не обязательно должен быть особенно в режиме реального времени, достаточно периодически извлекать данные topn из дочерних узлов или позволить байтовой точке активно сообщать.
class HotPostsAggregator {
map[int]map[int]int localTopnPosts; # nodeId => topn posts
map[int]int globalTopnPosts;
void onBeat() {
// do aggregate
// save globalTopnPosts to redis
}
void onLocalReport(int nodeId, map[int]int topnPosts) {
// 子节点上报局部热帖
}
}
хэш
Судя по заголовкам, статей не меньше сотни тысяч.Если каждому дочернему узлу нужно считать количество кликов по всем статьям, то кажется, что это займет много памяти, и будет много расчет для агрегирования и сортировки горячих постов. Лучше всего, чтобы каждый дочерний узел отвечал только за статистику части статьи, что позволяет значительно сэкономить вычислительные ресурсы.
Мы устанавливаем количество разделов в kafka равным количеству байтов, чтобы каждая нода отвечала за потребление данных для одного раздела. На производственной стороне kafka идентификатор сообщения записи о клике хэшируется, чтобы гарантировать, что поток кликов с тем же идентификатором сообщения входит в тот же раздел и, наконец, поступает в один и тот же статистический подузел.
потребитель повесил трубку
При увеличении количества машин увеличивается и вероятность отказа узла. Оборудование может быть повреждено, питание может быть отключено, а также может произойти человеческая ошибка. Если не принять никаких мер предосторожности, когда узел умирает, статистика за 8-часовой временной интервал на этом узле будет потеряна. Локальные горячие статьи, управляемые этим узлом, теряют возможность попасть в глобальные горячие публикации.
Это может не нанести большого вреда продукту и опыту, а нода полностью восстановится через 8 часов перезапуска. Более того, в течение этих 8 часов потеря прав горячего голосования по некоторым статьям не окажет огромного влияния на бизнес в целом.
Но все мы хотим, чтобы система была более совершенной, не так ли? При зависании ноды надеемся, что состояние можно быстро восстановить, это тоже возможно, и сложность не очень большая, но это обычная контрольная точка для сохранения текущего состояния в локальный файл или базу данных. Поскольку не будет слишком много статей, управляемых каждым дочерним узлом, контент, который необходимо сериализовать, не будет слишком большим. При перезапуске узла восстанавливается предыдущее состояние из постоянной контрольной точки, а затем потребление и статистика продолжаются.
Если вы используете spark-stream, его встроенная функция контрольных точек сделает резервное копирование и восстановление проще и безопаснее.
Если вы не хотите делать контрольную точку, есть еще способы, но это может занять много времени. То есть выполнить mapreduce для всех данных потока кликов, хранящихся в hdfs, подсчитать клики потока кликов в 8-часовом окне, а затем найти способ импортировать их в процесс байтовой точки.
Для этого требуется, чтобы данные hdfs также хранились в хэше, соответствующем kafka, чтобы можно было быстро обвести диапазон данных, которые необходимо подсчитать. Может быть из-за того, что сам mapreduce занимает немного времени, восстановленные данные не такие точные, но это не имеет большого значения Мы можем использовать такой грубый метод, чтобы быть достойными 9,5% данных, которые были сделаны очень хорошо.
Нажмите, чтобы дедуплицировать
Вышеупомянутое много говорит, и код выбивает много картинок, что, кажется, имеет смысл. Но есть еще одна важная вещь, о которой не упоминается, а именно о дедупликации щелчком мыши. Если пользователь неоднократно нажимает много раз, как разумно подсчитывать.
Хорошая статья, если она не слишком короткая, как правило, побуждает читателей перечитывать ее много раз. Кажется неразумным, если этот счетчик полностью дедуплицирован и записан как один раз. Но это явно нехорошо, если по нему намеренно многократно нажимают и записывают слишком много раз. Итак, как выбрать?
Первое, что нужно сделать, это начать с клиента, который сам может фильтровать некоторые недействительные клики. Текущий пользователь неоднократно нажимает на одну и ту же статью за слишком короткий промежуток времени, и эту закономерность все еще легко обнаружить. Если интервал относительно длинный, это щелчок послевкусия читателя, который относится к положительному отзыву о статье и должен быть записан.
Клиент делается, а потом запускать со стороны сервера, сложнее запустить со стороны сервера. Обнаружение модели поведения пользователя означает установление поведения пользователя, что значительно увеличивает нагрузку на сервер.
Сервер также должен предотвращать поведение пользователя, препятствующее пролистыванию. При отсутствии контроля антибраширования заголовок может использовать эту лазейку, чтобы нелегально получить большое количество кликов по собственной статье, попасть в список популярных статей, поставить популярный тег и быть увиденным большим количеством пользователей, она получит большую экономическую выгоду, даже если само содержание этой статьи недостаточно привлекательно.
Когда пользователи обнаружат, что такой плохой контент также может быть в списке популярных, у них, несомненно, возникнут сомнения относительно продукта. Распространение такого поведения может иметь фатальные негативные последствия для продукта.
Антибраш — это масштабная тема, и в этой статье мы не будем ее подробно раскрывать, автор не является специалистом в этой области. Проще говоря, очистка по существу извлекает характеристики злонамеренного поведения. Распространенная стратегия заключается в том, что одна и та же статья часто нажимается с одного и того же IP-адреса или с ограниченного количества IP-адресов. Механизмы обратной связи с пользователями также могут использоваться для выявления ненормального популярного контента, а затем вмешательства человека и т. д. Есть также несколько более продвинутых методов, таких как машинное обучение и глубокое обучение в отрасли, чтобы предотвратить чистку, и эти читатели могут искать и исследовать самостоятельно.
Читайте статьи по теме, обратите внимание на общедоступный номер [кодовая дыра]