Эффективные операции с множеством в 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

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

я бы что-то вроде этого (псевдокод) вместо: раствор

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); 

Answer 2

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