Для начала я предполагаю, что вы знаете, как связывать задания MapReduce. Если нет, см. http://developer.yahoo.com/hadoop/tutorial/module4.html#chaining для получения подробной информации.
Во-вторых, я предполагаю, что у вас есть распределенное хранилище ключей/значений, такое как Cassandra.
В-третьих, ваша функция подсчета очков мне непонятна. Я бы не подумал, что «одна запись отсюда, одна запись оттуда» даст вам понять, что это один и тот же человек. Я мог бы поверить, что «записи отсюда по сравнению с записями оттуда = оценка того, один и тот же человек или нет». Поэтому я предполагаю, вопреки вашему описанию, что именно так работает ваша функция подсчета очков.
Теперь, что было бы теоретически хорошим способом решить вашу проблему?
Обработайте журналы, поместите в свой магазин карту уникального идентификатора машины (IP-адрес + cookie) + диапазон дат для всех зарегистрированных событий.
Извлеките список всех уникальных идентификаторов машин. Сохраните и это.
Выполните MapReduce, где карта берет идентификатор машины, захватывает список всех остальных и выдает все пары разных идентификаторов машин, где первый меньше второго. Запросы сокращения для зарегистрированных событий каждого из них вычисляют оценку, а затем, если оценка превышает пороговое значение, выдает точку данных, которую больший идентификатор машины сопоставляет с меньшим.
Вывод 3 передается по конвейеру в карту, чья карта ничего не делает, и чья карта находит для каждого идентификатора машины наименьший идентификатор машины, с которым он сопоставляется.
Вывод 4 перенаправляется на уменьшение карты, карта которого принимает пару (идентификатор машины, канонический идентификатор машины), захватывает события из хранилища в # 1 и переназначает их в (канонический идентификатор машины, остальная часть события), и чье сокращение хранит для канонического идентификатора машины (он же идентификатор группы) связанные события. (По дате, если хотите.)
Хорошо, это хорошая теория. Где это идет не так?
Проблема в том, что всех пар идентификаторов чертовски много. В этом списке может оказаться порядка 1018, для каждого из которых вы извлекаете журналы. Если у вас нет действительно феноменального оборудования, вам не хватит вычислительной мощности, чтобы вычислить это. Поэтому вам нужно найти эвристики, чтобы уменьшить его.
Первый и самый простой заключается в том, что любые идентифицированные «эти два идентификатора сопоставляются с одним и тем же» должны сохраняться и повторно использоваться везде, где это возможно.
Во-вторых, после большой первоначальной работы вы, вероятно, сойдете с рук: «Из всех недавно созданных идентификаторов, на что они сопоставляются?» Это кандидаты на добавление к вашему каноническому отображению, которое вы не хотите постоянно воссоздавать.
В-третьих, я уверен, что у вас есть понятие "подобная запись". Таким образом, сопоставьте записи с какой-то группой записей, а затем при сокращении все «достаточно маленькие» группы сопоставят все пары «возможно, одинаковыми». Отправьте эти пары в сокращение карты, которое захватывает «возможно, одни и те же» записи, а затем создает идентификатор машины сопоставления поиска для всех «появившихся, возможно, одинаковых более чем X раз». Сохраните это. Теперь повторите вышеописанное, за исключением того, что на шаге 2 вы отправляете идентификатор машины всем парам себя с «пришедшим, возможно, таким же» другим. Этот ярлык значительно сократит работу.
Это общая стратегия, которая требует много работы. Удачи.
person
btilly
schedule
18.07.2013
