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

Ответ 1

Используйте Bloom filter: таблица одновременных хэшей. Согласно Википедии, оптимальное количество хэшей ln(2) * 2^32 / 2^30 ≈ 2.77 ≈ 3. (Hmm, включение 4 дает меньше ложных срабатываний, но 3 для этого приложения еще лучше). Это означает, что у вас есть таблица размером 512 мегабайт или 4 гигабита, и обработка каждой записи устанавливает три новых бита в этом огромном море. Если все три бита уже установлены, это потенциальное совпадение. Запишите три хэш-значения в файл. В противном случае запишите их в другой файл. Обратите внимание на индекс записи вместе с каждым соответствием.

(Если вероятность ошибки 5% допустима, опустите большой файл и используйте небольшой файл в качестве результатов.)

Когда закончите, у вас должен быть файл примерно 49M возможных положительных совпадений и файл с отрицательными значениями 975M, которые еще могут совпадать с позитивами. Прочитайте его в vector<pair<vector<uint32_t>,vector<uint32_t> > > (индексы в последнем vector, первый может быть array) и отсортировать его. Поместите индексы в другой vector<uint32_t>; они уже отсортированы. Прочитайте большой файл, но вместо того, чтобы устанавливать биты в таблицу, найдите значения хэша в vector. (Например, используйте equal_range.) Используйте список индексов положительных файлов для отслеживания индекса текущей записи в отрицательном файле. Если совпадение не найдено, игнорируйте. В противном случае добавьте индекс записи match->second.push_back(current_negative_record_index).

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

Общий синхронный дисковый ввод-вывод: (один проход = 1 TiB) + (96 хэш-бит на запись = 12 GiB) + (32 бита индекса на положительный = ~ 200 MiB).

Окончательное редактирование (серьезно): с другой стороны, особенность Bloom Filter, возможно, не очень помогает здесь. Количество хеш-данных является более ограничивающим фактором, чем количество ложных срабатываний. С помощью только одной хеш-функции общее количество хеш-данных будет составлять 4 гигабайта, а индексы 124 млн ожидаемых ложных срабатываний будут ~ 500 Мбайт. Это должно глобально оптимизировать эту стратегию.

Разъяснение (получило нижний предел): существует различие между ложным положительным эффектом от фильтра Блума и столкновением хэшей. Хеш-конфликт не может быть разрешен, кроме как путем возврата к исходным записям и сравнения, что дорого. Флуктуал Bloom может быть разрешен путем возврата к исходным значениям хэша и их сравнения, что и делает второй проход этого алгоритма. Итак, с другой стороны, одноходовой фильтр, описанный в "окончательном" редактировании, будет чрезмерно вызывать обращения к диску. Два-хэш-фильтр Bloom увеличил бы количество ложных срабатываний, оканчивающихся в одном ведре карты match, и привел бы количество ложных срабатываний обратно к десяткам миллионов.

Ответ 2

Предлагаемые решения пока слишком сложны. A Bloom filter, будучи структурой данных du jour в течение последних нескольких лет, не рекомендуется применять в такой ситуации: потому что no данные могут быть связаны с хешированным контентом, вы должны не только поддерживать фильтр Bloom, но вы все равно должны записывать каждое (только 6-битное!) значение хэша и записывать на диск, разрушая преимущество фильтра цветка и имея нелепо высокий скорость столкновения.

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

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

Информация, полезная в индексе, будет:

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

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

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

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

Ответ 7

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

Ответ 8

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