Учитывая набор данных на 1 ТБ на диске приблизительно с 1 КБ за запись данных, как я могу найти дубликаты с помощью 512 МБ RAM и бесконечного дискового пространства?

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

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

Сгенерировать хэш каждой записи; записать номер записи и хэш в памяти, при необходимости перенаправив их в файл (отсортируйте данные в порядке хеширования перед записью в файл). Когда вы придумываете новый хеш, проверьте, существует ли он уже в памяти - это раннее обнаружение. (Это может быть, а может и не быть основным преимуществом.)

Когда вы прочитаете все данные, у вас будет несколько файлов хэшей плюс номера записей, уже отсортированных. Объедините эти файлы вместе, обнаруживая дубликаты по ходу дела. Вам даже не нужно делать больше, чем записывать дубликаты для этого приложения, поэтому вы можете отбросить хэши, как только они окажутся уникальными.

Учитывая размеры - 0,5 ГБ памяти, 1000 ГБ данных, 1 КБ на запись, то есть около 1 миллиарда записей - предполагая 256-битный хэш (хотя 128-битного вполне может быть достаточно), мы будем использовать 32 байта. для хэша и 4 байта для номера записи и около 1 миллиарда записей нам нужно около 36 ГБ для файлов сортировки, сгенерированных в файлах размером 500 МБ (что соответствует доступной памяти), так что будет 70-80 файлов слиться в конце, что кажется довольно управляемым. В списке будут указаны номера записей - тогда вам нужно будет получить доступ к файлу размером 1 ТБ, чтобы прочитать записи. Вам нужно подумать, что вы собираетесь делать с дубликатами; нужна ли вам информация об исходной записи и дополнениях, и имеет ли значение, какие из дубликатов вы сохраняете, а какие отклоняете. И т.д.

Загружать данные в память 512 МБ за раз, затем отсортировать этот фрагмент и записать его на диск (как отдельный файл). После того, как весь 1T будет выполнен таким образом, объедините-отсортируйте отдельные файлы в один большой файл, затем последовательно прочитайте этот большой (отсортированный) файл, записывая его в окончательный файл, удаляя повторяющиеся записи.

1T, 512M за раз, будет примерно 2,1 миллиона файлов (если принять двоичное определение единиц СИ, а не десятичное). 512M из 1K записей позволят разместить в памяти только 524 288 записей, поэтому вам, вероятно, придется выполнять сортировку слиянием в два этапа. Другими словами, объедините 2,1 миллиона файлов в четыре группы, чтобы создать четыре больших файла, а затем объедините эти четыре файла в большой отсортированный файл. Затем это тот, который вы обрабатываете последовательно, чтобы удалить дубликаты.

Сортировка слиянием - это просто слияние нескольких уже отсортированных файлов путем простого выбора первой оставшейся записи из каждого файла и выбора «самого низкого». Например, два файла a и b :

a   b
7   6
3   5
1   4
    2
 \_/
  1 (a)
  2 (b)
  3 (a)
  4 (b)
  5 (b)
  6 (b)
  7 (a)

предлагаемые до сих пор решения кажутся слишком сложными. Фильтр Блума , являясь структурой данных в течение последних нескольких лет , не лучше всего применять в такой ситуации: потому что никакие данные не могут быть связаны с хешированным содержимым. , вы должны не только поддерживать фильтр Блума, но и записывать каждое (только 6-битное!) значение хеш-функции и записывать на диск, сводя на нет преимущества фильтра Блума и создавая абсурдно высокую частоту конфликтов.

С другой стороны, сортировка слиянием всего терабайта потребует не только O (n log n) сравнений, но и O (n log n) дискового трафика, поскольку большинство промежуточных файлов нужно будет объединить с диска, а не из памяти.Любое реальное решение должно стараться максимально уменьшить дисковый трафик, поскольку это наше основное узкое место.

Мое решение простое, я делаю одно предположение: терабайт данных записывается в один файл.

Перебирать записи терабайтного файла и хешировать их. Криптографический хеш здесь не нужен, дорог и слишком велик; вместо этого используйте что-то вроде 64-битной версии murmurhash . Он может хэшировать более 2 ГиБ / сек (намного быстрее, чем нам, вероятно, понадобится, учитывая скорость хранения в наши дни) и имеет отличную (хотя и не криптографически безопасную) устойчивость к столкновениям. С 64-битным хешем мы ожидаем, что наша первая коллизия будет на уровне 2 ^ 32 , поэтому вполне вероятно, что наши приблизительно миллиард записей вообще не будут иметь коллизий.

Записать хэши и связанные с ними смещения записей в другой файл. Поскольку записи содержат произвольные двоичные данные, мы не можем полагаться на сортировку (1) Unix для их сортировки, потому что некоторые хэши и смещения могут содержать то, что sort (1) будет интерпретировать как символы новой строки. Мы просто запишем записи как записи фиксированной ширины (вероятно, 16 байтов: 8 байтов для 64-битного хэша murmur2 и 8 байтов для смещения в терабайтном файле). Полученный файл должен быть около 16 ГБ с учетом нашего количества записей.

Мы можем отсортировать этот файл, считывая количество записей, которые безопасно помещаются в память, и сортируя их, сбрасывая отсортированные фрагменты обратно на диск.Мы можем разместить больше записей в памяти с помощью heapsort (он использует пространство O (1) ), чем с помощью quicksort (который использует память O (log n) для стека вызовов), но в большинстве реализаций быстрая сортировка выигрывает благодаря расположению в памяти и меньшему количеству команд. Эти промежуточные файлы (их должно быть 35-40) будут записаны на диск.

Последним шагом является объединение этих файлов (в памяти; для этого нет необходимости сохранять результат на диске), сбор всех хеш-коллизий и поиск связанных записей в терабайтном файле, сравнение записей на предмет дублирования и выдача записи (или их смещения) любым способом, указанным в задаче.

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

Для диска ввода-вывода он считывал терабайтный файл данных, записывал 16 ГБ на диск, считывал эти 16 ГБ с диска и записывал обратно отсортированными, затем считывал его и возвращал дубликаты. В качестве оптимизации процесс хеширования записей может накапливать их в памяти перед сбросом на диск, сортируя их перед этим: это вырезает промежуточный файл размером 16 ГБ и позволяет процессу перейти от хеширования напрямую к слиянию и сообщению о дубликатах. .

Это много записей ;-) порядка 1 000 000 000. Лучше подумайте об этом ...

Природа записей не определена: мы просто обнаруживаем их, по одной, читая их последовательно, или есть какой-то индекс, или, может быть, они хранятся как файлы в разных каталогах? Также в вопросе не указывается наличие базы данных, которую мы можем использовать для индексных данных (вместо того, чтобы сортировать их с помощью нашего собственного кода). Также [даже приблизительное] представление о количестве дубликатов поможет направить некоторые варианты выбора в сторону эффективного процесса.

Если индекса не существует, мы можем / должны создать его; это можно сделать как первый проход через данные.Тот же самый проход будет использоваться для создания своего рода дайджеста сообщения (хэша) для каждой записи (или, возможно, в целях повышения эффективности, для первых нескольких сотен байтов записи).

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

Полезная информация в индексе:

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

Выбор хэша имеет решающее значение: следует отдавать предпочтение быстрому алгоритму за счет идеально распределенного; количество байтов, хэшированных для каждой записи, также является компромиссом, возможно, от 100 до 200 байтов (то есть примерно от 10 до 20% от среднего размера записи) - хорошее значение, в зависимости от ожидаемого соотношения дубликатов и в зависимости от экономии времени это обеспечивает (по сравнению с хешированием всей записи). (см. правку ниже)

Когда такой индекс доступен, мы можем [относительно быстро / легко] получить количество возможных дубликатов; на основе этого результата может быть выполнен второй проход, направленный на улучшение качества индекса, если он не считается достаточно избирательным (исключая записи, которые легко считаются уникальными). Этот второй проход может вычислить другой хэш для всей записи (за исключением первых x байтов первого хеша) или еще одного подмножества записи.Обратите внимание, что благодаря индексу этот второй проход может быть многопоточным, если это возможно.

Второй или последний проход требует сортировки записей в группе возможных совпадений (одинаковой длины, одинаковых хэш-кодов, одинаковых первых x байтов). Это может быть достигнуто, как описано в Pax Diablo, преимущество индекса в том, что такая операция может быть многопоточной и включает гораздо меньшие наборы (многие из них). Добавлено : Здесь снова Ник Джонсон подчеркивает, что второй проход, возможно, был бы ненужным, если бы мы использовали длинный хэш-код (он предлагает 128 байтов SHA1). Предполагая, что частичное хеширование записей не дает никакого преимущества, это очень правдоподобное решение, поскольку индекс может находиться на диске, но при этом его можно сортировать и хранить быстрее, чем если бы мы сортируем / сохраняем все записи.

Правка : Ник Джонсон отлично замечает, что задержка поиска в дисковом хранилище может быть такой, что обычное последовательное чтение будет быстрее, а узким местом является ограничение дискового ввода-вывода, Быстрая хеш-функция, выполняемая одновременно, может быть быстрее, чем последовательное чтение, и, следовательно, не добавлять к общему процессу. Это вероятная возможность (особенно если последовательное чтение, если эффективно требуется для обнаружения начала / конца каждой записи и т. Д.), И поэтому я «уменьшил свою ставку», написав «, в зависимости от экономии времени, которую это дает ... ".Это говорит о том, что фактическая структура записей на диске является одним из открытых параметров вопроса (например, если мы просто читаем из отдельных файлов в каталогах, следовательно, накладываем непоследовательное чтение), а также, вероятно, хранилище размером с терабайт. поддерживаются причудливым RAID, где задержка поиска, оставаясь при этом проблемой, обычно значительно улучшается.
Я поддерживаю свое предположение о том, что двухпроходный подход может быть более эффективным, чем тот, при котором каждая запись полностью хешируется, но мне хотелось бы подчеркнуть возможность и преимущества однопроходного подхода. Как и во многих вопросах интервью, некоторые характеристики данной ситуации не были указаны; идея состоит не столько в том, чтобы увидеть, как кандидат дает абсолютно правильный ответ (хотя некоторые ответы могут быть совершенно неправильными!), а в том, чтобы получить представление о его / ее мыслительном процессе и способности определять варианты и точки принятия решений.

Сначала настройте компьютер с бесконечно большим файлом подкачки на бесконечно большом диске ...