Эффективные операции над множествами в mapreduce

Question

Я унаследовал кодовую базу mapreduce, которая в основном рассчитывает количество уникальных идентификаторов пользователей, видимых с течением времени для разных объявлений.Для меня это не похоже, что это делается очень эффективно, и я хотел бы знать, есть ли у кого-нибудь какие-либо советы или предложения о том, как сделать этот вид расчета максимально эффективно в mapreduce.

Мыиспользуйте Hadoop, но я приведу пример в псевдокоде, без всякой лжи:

map(key, value):
  ad_id = .. // extract from value
  user_id = ... // extract from value
  collect(ad_id, user_id)

reduce(ad_id, user_ids):
  uniqe_user_ids = new Set()
  foreach (user_id in user_ids):
    unique_user_ids.add(user_id)
  collect(ad_id, unique_user_ids.size)

Это не много кода, и это не очень сложно понять, но это не очень эффективно.Каждый день мы получаем больше данных, и поэтому каждый день нам нужно просматривать все показы объявлений с самого начала, чтобы рассчитать количество уникальных идентификаторов пользователей для этого объявления, поэтому каждый день это занимает больше времени и использует больше памяти.Более того, без фактического профилирования кода (не знаю, как это сделать в Hadoop) я почти уверен, что почти вся работа заключается в создании набора уникальных идентификаторов.Он также потребляет огромное количество памяти.

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

Как эффективно реализовать подсчет уникальных идентификаторов с помощью mapreduce?

Answer 1

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

Answer 2

Проблема в том, что код, который вы унаследовали, был написан с помощью мышления «Я сам определю уникальный набор» вместо «Давайте использовать фреймворк, чтобы сделать это для меня».

Я хотел бы что-то вроде этого (псевдокод) вместо:

map(key, value):
  ad_id = .. // extract from value
  user_id = ... // extract from value
  collect(ad_id & user_id , unused dummy value) 

reduce(ad_id & user_id , unused dummy value):
  output (ad_id , 1); // one unique userid.

map(ad_id , 1): --> identity mapper!
  collect(ad_id , 1 ) 

reduce(ad_id , set of a lot of '1's):
  summarize ;
  output (ad_id , unique_user_ids);