У меня есть большой файл json с более чем 20 ГБ метаданных в формате json. Он содержит простые пользовательские метаданные в каком-то приложении, и я хотел бы просмотреть их, чтобы обнаружить дубликаты. Вот пример того, как выглядят данные:
{"created": "2015-08-04", "created_at": "2010-03-15", "username": "koleslawrulez333"}
{"created": "2016-01-19", "created_at": "2012-05-25", "name": "arthurking231"}
{"created": "2016-07-23", "type": "Username", "created_at": "2011-08-27", "name": "starklord1943"}
{"created": "2015-11-08", "created_at": "2010-01-19", "name": "Assasinator5827"}
Файл json содержит построчно объекты json, которые очень похожи на этот. Дубликат возникает, когда поле "name"
двух объектов json совпадает. Итак, это дубликат:
{"created": "2016-07-23", "type": "Username", "created_at": "2011-08-27", "name": "Assasinator5827"}
{"created": "2015-11-08", "created_at": "2010-01-19", "name": "Assasinator5827"}
Ровно столько же, сколько два одинаковых объекта json.
Теперь я хочу просмотреть весь файл json, который слишком велик для того, чтобы поместиться в память, и, используя лучший стандарт, выяснить все дубликаты и то, что они являются дубликатами, а затем сделать некоторые логика - логическая часть тривиальна, но я несколько не уверен, как найти дубликаты.
О чем я думал:
Первое, что я решил использовать, это фильтр Блума. Они не такие запутанные и работают довольно хорошо и быстро, и я думаю, что они по существу сводятся к O (n). Однако фильтры Блума не дадут мне знать, что является дубликатом строки-дубликата, что для меня недопустимо.
Я думал об использовании внешней сортировки слиянием. Я бы в основном разделил файл на несколько файлов меньшего размера, которые поместились бы в памяти, отсортировал бы каждый фрагмент и искал дубликаты (которые теперь сгруппированы вместе). Но я не очень уверен, что эта реализация - то, что я хочу.
Следующим, с чем я столкнулся, было хеширование по разделам, и я подозреваю, что это то, что я хочу. Хеширование — это, по сути, лучший способ найти дубликаты при работе с данными, которые помещаются в память, так почему бы не использовать его для чего-то, что не помещается? Я немного смущен тем, как хэшировать по разделам. Я не уверен, что это то, что я ищу.
Итак, я думаю, что должен использовать вариант 3, хэширование по разделам, и я знаю, что в Spark он есть. Я надеялся, что кто-нибудь может дать мне знать, на правильном ли я пути, и, возможно, дать мне некоторые инструкции о том, прав ли я или нет. У меня есть пара конкретных вопросов, концептуально:
Допустим, я создаю 100 разделов, которые идеально вписываются в память (так что в моем случае каждый раздел будет иметь размер 100 МБ). Допустим, я хеширую первые
x
элемента в моем json-файле в один раздел и не нахожу дубликатов нет. Допустим, у меня есть другой раздел со вторыми 100 МБ данных, которые также не содержат дубликатов. Если я могу загружать только 100 МБ данных за раз, как мне проверить, что раздел 1 и раздел 2 не имеют дубликатов друг от друга? Чтобы уточнить, если в разделе 1 есть элемент, а в разделе 2 есть один и тот же элемент, как мне это понять? Я предполагаю, что мне нужно будет загрузить оба в память, верно? А если я не могу... то что мне делать? Может я неправильно понимаю...Что приводит к моему второму вопросу - кажется, что разбиение на разделы работает не так, и когда вы хешируете по разделам, элементы с похожим хэшем или диапазоном хэшей попадают в определенный файл. Поэтому, если два элемента являются дубликатами, я бы знал, потому что алгоритм попытается поместить их в файл, где хэш уже существует. Так ли это?
Я знаю, что у меня есть еще вопросы, я просто не могу их придумать. У кого-нибудь есть советы? Особенно в отношении pyspark и как лучше всего это использовать? Или pyspark не то, что я ищу?