Как исключить повторяющиеся записи из большого потока данных? - PullRequest
Новая
       26

Как исключить повторяющиеся записи из большого потока данных?

4 голосов
/ 12 сентября 2011

Я начал работать с большим набором данных, который поступает в формате JSON.К сожалению, служба, предоставляющая фид данных, предоставляет нетривиальное количество дубликатов записей.С другой стороны, каждая запись имеет уникальный номер Id, хранящийся в виде 64-разрядного положительного целого числа (Java long ).

Данные поступают один раз в неделю и составляют около 10M записей в каждойДоставка.Мне нужно исключить дубликаты из текущей поставки, а также записи, которые были в предыдущих пакетах.

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

Вопрос в том, есть ли лучший способ поиска дубликата long при импорте записей?

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

Ответы [ 3 ]

5 голосов
/ 13 сентября 2011

Не могли бы вы создать задачу MapReduce, в которой вывод карты имеет ключ с уникальным идентификационным номером? Таким образом, в вашей задаче сокращения вам будет передан итератор всех значений с этим идентификационным номером. Выведите только первое значение и ваш сокращенный вывод будет свободен от дубликатов.

1 голос
/ 12 сентября 2011

Дай мне посмотреть. Каждый java.lang.Long занимает 24 байта. Каждый HashMap$Entry также занимает 24 байта, а массив для HashMap занимает 4 байта. Таким образом, у вас есть 52 * 10M = 512M кучи для карты. Это для 10M записей одной недели.

Если вы работаете в 64-битной системе, вы можете просто установить размер кучи равным 5 ГБ и посмотреть, как далеко вы доберетесь.

Должны быть другие реализации java.util.Set, которые потребляют только около 16 байт на запись, поэтому вы можете обрабатывать данные в три раза больше, чем с java.util.HashSet. Я написал один сам, но я не могу поделиться этим. Вместо этого вы можете попробовать GNU Trove.

0 голосов
/ 11 декабря 2012

Вы должны хранить список уникальных идентификаторов в HDFS и перестраивать его после каждой пакетной загрузки.

Поскольку количество элементов в вашем случае довольно велико (вы можете ожидать> 1B уникальных записей за один год), ваш список уникальных идентификаторов должен быть разбит на несколько частей, скажем N. Алгоритм разделения зависит от домена. Общий подход заключается в преобразовании идентификатора в длинную строку хэша (16 байтов в порядке) и создает 2 ^ k сегментов:

Для k = 8, например:

сегмент # 1 содержит все идентификаторы, значение хеша которых начинается с 0 блок № 2 содержит все идентификаторы, значение хеша которых начинается с 1 ... сегмент # 256 содержит все идентификаторы, значение хеша которых начинается с 255

В каждом новом пакете вы сначала получаете задание на выполнение дедупликации: Карта считывает записи, получает идентификатор записи, хэширует ее и выдает Key = bucket # (в нашем случае 0..255) и Value = ID. Каждый редуктор получает все IDS для данного сегмента. Редуктор загружает ВСЕ уникальные идентификаторы для данного сегмента, известного в вашей системе, уже во внутренний набор и проверяет ВСЕ входящие идентификаторы записей с помощью этого внутреннего набора. Если у записи есть идентификатор, который еще не известен, вы обновляете внутренний Set и выводите запись.

При закрытии редуктора вы выводите внутренний набор уникальных идентификаторов обратно в HDFS.

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

...