Плохая производительность для Dedupe 2 миллионов записей с использованием mapreduce на Appengine

Question

У меня около 2 миллионов записей, каждая из которых содержит около 4 строковых полей, которые необходимо проверить на наличие дубликатов. Чтобы быть более точным, у меня есть имя, телефон, адрес и имя отца в качестве полей, и я должен проверить наличие дедупликации, используя все эти поля с остальными данными. Полученные уникальные записи должны быть записаны в БД.

Мне удалось реализовать mapreduce, перебрать все записи. Частота выполнения заданий равна 100 / с, а размер сегмента - 100. Тарификация включена.

В настоящее время все работает, но производительность очень и очень низкая. Мне удалось выполнить только 1000 дедупликации записей среди тестового набора данных из 10000 записей за 6 часов.

Текущий дизайн в Java:

1. В каждой итерации карты я сравниваю текущую запись с предыдущая запись
2. Предыдущая запись - это отдельная запись в БД, которая действует как глобальная переменная, которую я перезаписываю другой предыдущей записью в каждой карте итерация
3. Сравнение выполняется с использованием алгоритма, а результат записывается в виде новая сущность в db
4. В конце одного задания Mapreduce я программно создаю другое работа
5. Предыдущая переменная записи помогает сравнить работу со следующей запись кандидата с остальными данными

Я готов увеличить любое количество ресурсов GAE, чтобы добиться этого в кратчайшие сроки.

Мои вопросы:

1. Повлияет ли точность дедупликации (проверка на дубликаты) из-за параллельные задания / задачи?
2. Как улучшить этот дизайн?
3. Будет ли этот масштаб до 20 миллионов записей
4. Какой самый быстрый способ чтения / записи переменных (не только счетчиков) во время итерации карты, которую можно использовать для одного задания mapreduce.

Фрилансерам всегда рады помочь в этом.

Спасибо за вашу помощь.

Answer 1

Вы должны воспользоваться Редуктором, чтобы сделать эквивалент сортировки -u для каждого поля.Вам нужно будет сделать одну работу M / R на поле.Вы должны сделать поле сопоставления ключа в маппере, затем в редукторе вы получите все записи с одинаковым именем, сгруппированные вместе, и сможете пометить их.Второй проход будет для телефона и т. Д. В зависимости от размера вашего кластера каждый проход должен быть очень быстрым.

Edit : @Olaf указал, что OP, вероятно, хочет абсолютно уникальные записи.Используя составной ключ, это может быть однострочная команда потоковой передачи hadoop для получения уникального набора.Я добавлю это в ближайшее время.

Edit2 : Обещанная потоковая команда, которая выполнит сортировку -u для всего файла.Предполагается, что у вас есть файл с записями с каждым полем (имя, отчество, номер телефона и адрес), по одной на каждой строке табуляции, разделенных одним или несколькими файлами в директории hdfs: // example / dedup / input /.Фактический путь hdfs может быть любым, или вы можете использовать один файл.Выводом будет несколько файлов part- * в hdfs: // example / dedup / output /.Вам также может понадобиться изменить команду, так как ваш hadoop-streaming.jar может находиться в немного другом месте.Если у вас более 4 полей, измените значение stream.num.map.output.key.fields.

   $HADOOP_HOME/bin/hadoop jar $HADOOP_HOME/hadoop-streaming.jar \
-input hdfs://example/dedup/input/ -output hdfs://example/dedup/output/ \
-mapper org.apache.hadoop.mapred.lib.IdentityMapper \
-reducer /usr/bin/uniq \
-D stream.num.map.output.key.fields=4

Чтобы извлечь уникальные результаты в файл в файле локальной файловой системы, запустите:поэтому каждая строка будет иметь дополнительную вкладку в конце.Это легко сдирать.

Если вы хотите сделать больше, чем просто получить вывод uniq, вы можете поместить свой собственный класс Java или программу командной строки вместо использования / usr / bin / uniq.Этот класс может, например, обновить все записи, которые вы найдете, дублируя, добавив пятый столбец в ваш ввод, который является идентификатором БД записей.Hadoop по умолчанию создает разделы по всему ключу, поэтому каждая группа повторяющихся записей будет передаваться вместе по редуктору, и все это будет происходить параллельно.Пожалуйста, ознакомьтесь с потоковой документацией для получения дополнительной информации.

Answer 2

Я вижу 2 способа решения этой проблемы:

1. (Если вам нужно сделать это только один раз) AppEngine создает индекс свойства для каждого свойства в вашей сущности (если только вы не попросите его этого не делать). Создайте серверную часть, выполните запрос «SELECT * FROM ORDER BY» в пакетах, используя курсоры, определите дублированные свойства и исправьте / удалите их. Возможно, вы сможете распараллелить это, но это сложно на границах осколков, и вам, вероятно, придется написать весь код самостоятельно.

2. Вы можете использовать Mapper Framework, чтобы сделать это медленнее, но работать параллельно. Этот подход также позволяет эффективно дедуплицировать данные при вставке. Введите новый объект для хранения уникальных значений свойств. Скажите «Уникальный номер телефона». Объект должен иметь номер телефона в качестве ключа и ссылку на объект с этим номером телефона. Теперь запустите карту и выполните поиск UniquePhoneNumber. Если он найден и его ссылка действительна, удалите дубликат. Если нет, создайте новый с правильной ссылкой. Таким образом, даже можно переписать ссылку на другую, если вам нужно. Обязательно прочитайте UniquePhoneNumber и создайте новый / обновите новый внутри одной транзакции. В противном случае дубликаты не будут обнаружены.

Answer 3

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

На данный момент, ваш лучший вариант - это, вероятно, создать собственное решение. Используя курсоры, выполните запрос по типу, отсортированному по полю, которое вы хотите дедуплицировать, и отсканируйте его, проверяя наличие дубликатов и удаляя их (в пакетном режиме, чтобы уменьшить RPC) при их обнаружении. Когда вам нужно объединить в цепочку другую задачу (из-за 10-минутного лимита задачи), используйте курсор, чтобы убедиться, что новое задание начинается там, где вы остановились.

Если вы хотите распараллелить это, вы можете, запустив каждый осколок, пропуская записи до тех пор, пока он не обнаружит изменение значения, на которое вы дедуплицируете, и начнете оттуда. В конце осколка дождитесь конца группы, прежде чем остановиться. Таким образом, вы убедитесь, что не пропустите удаление дубликатов, расположенных на краю границы осколка.

Answer 4

Создание хэш-кода для каждой записи. Просмотрите ваши записи и вставьте каждую в Set на основе хеш-кода. Set теперь является дедуплицированным списком в O (N).

Answer 5

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

https://pkghosh.wordpress.com/2013/09/09/identifying-duplicate-records-with-fuzzy-matching/