Существует 1 Данные ТБ на диске с примерно 1 КБ на запись данных. Как найти дубликаты, используя 512 МБ ОЗУ и бесконечное дисковое пространство?Учитывая набор данных на 1 ТБ на диске объемом около 1 КБ на запись данных, как я могу найти дубликаты с использованием ОЗУ 512 МБ и бесконечного дискового пространства?
Использование таблицы Bloom filter: таблица одновременных хэшей. Согласно Википедии, оптимальное количество хешей составляет ln(2) * 2^32/2^30 ≈ 2.77 ≈ 3. (Hmm, включение 4 дает меньше ложных срабатываний, но 3 для этого приложения еще лучше). Это означает, что у вас есть таблица размером 512 мегабайт или 4 гигабита, и обработка каждой записи устанавливает три новых бита в этом огромном море. Если все три бита уже установлены, это потенциальное совпадение. Запишите три хэш-значения в файл. В противном случае запишите их в другой файл. Обратите внимание на индекс записи вместе с каждым совпадением.
(Если частота ошибок 5% терпима, опускает большой файл и использовать небольшой файл, как ваши результаты.)
Когда закончите, вы должны иметь файл около 49й возможных положительных совпадений и файл 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 и привел бы количество ложных срабатываний к десяткам миллионов.
@Potatocom: Помните, что если фильтр цветения имеет правильный размер, то ложная положительная вероятность наихудшего случая будет возникать только после того, как будет вставлен последний уникальный элемент. До тех пор ложная положительная вероятность запроса может быть меньше порядков величин - но постепенно увеличивается с увеличением количества элементов. – 2010-04-04 11:11:20
@Monomer: Это что-то меняет? – Potatoswatter
@Potatocom: Конечно, это требует только одного прохода. Представьте, что вы создали BF с ложноположительной вероятностью 1/2n, где n - количество элементов, которые вы будете вставлять в BF. Во втором вопросе, который вы запрашиваете, будет наблюдаться слабая положительная проблема ~ 1/(2n^e * delta_0), третья будет видеть 1/(2n^e * delta_1), где delta_i = m * i + c с пределом в сторону 1/e , Дело в том, что только когда вы вставляете/запрашиваете последний уникальный элемент, вы действительно видите ожидаемую ложноположительную вероятность, все остальные запросы имели удовольствие от ложноположительной проблемы примерно по крайней мере на порядок меньше ... – 2010-04-04 19:25:12
Загрузите данные в память 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)
Если вы пытаетесь найти дубликаты, сортировка всего 1 Тбайта данных будет чрезмерной. –
Действительно? Мне кажется, что повторный тест несортированного набора данных - O (n * n), тогда как любой приличный сорт будет больше похож на O (n log n). Если у вас есть лучший способ, я бы хотел его увидеть. – paxdiablo
Если вы загружаете данные в ОЗУ 512 Мбайт за один раз, вам не хватает места в ОЗУ для вашего кода и не будет стекового пространства для запуска вашего кода. Даже если у вас нет нерекурсивного алгоритма сортировки, вы по-прежнему будете складывать пространство для своих локальных переменных и, вероятно, некоторую память для вашей кучи и, возможно, любые глобальные переменные. – Ants
Найти подходящую хэш-функцию и хэш каждую запись, хранение списка хэшей с индексами в файл. Теперь отсортируйте хэш-файл с помощью хэша. Наконец, проверьте все записи хэшей соответствия для реальных дубликатов.
Конечно, это зависит от того, сколько дубликатов вы ожидаете найти и что вы собираетесь делать с информацией после этого.
Это похоже на алгоритм Рабина-Карпа, но для записей, а не для поиска строк. Кроме того, почему вы сортируете хэш-файл? У вас уже есть набор ведер, содержащих возможные дубликаты. Почему бы просто не проверить ведра? –
@Alex Вы думаете, что я поместил записи в хэш-таблицу, которая, возможно, является вариантом. –
Создать хэш каждой записи; записывать номер записи и хеш в памяти, разливая файл в случае необходимости (сортировать данные в хэш-порядке до записи в файл). Когда вы придумаете новый хеш, проверьте, существует ли он в памяти - это раннее обнаружение. (Это может быть или не быть основным преимуществом.).
Когда вы прочтете все данные, у вас будет несколько файлов хэшей, а также номера записей, уже отсортированные. Объедините эти файлы вместе, обнаруживая дубликаты по мере продвижения. Вам даже не нужно делать больше, чем записывать дубликаты для этого приложения, поэтому вы можете отказаться от хэшей, как только они станут уникальными.
Учитывая размеры - 0,5 ГБ памяти, данные 1000 ГБ, 1 КБ на запись, поэтому около 1 млрд записей - при условии 256-битного хэша (хотя 128-бит вполне может быть адекватным), мы будем использовать 32 байты для хэша и 4 байта для номера записи и около 1 миллиарда записей, нам нужно около 36 ГБ для файлов сортировки, сгенерированных в 500 МБ файлах (соответствующих доступной памяти), поэтому было бы 70-80 файлы для объединения в конце, что кажется довольно управляемым. В списке вам будут указаны номера записей - вам нужно будет получить доступ к файлу 1 ТБ для чтения записей. Вам нужно подумать о том, что вы собираетесь делать с дубликатами; вам нужна информация об исходной записи и дополнительных данных, и не имеет значения, какой из дубликатов вы храните и которые вы отклоняете. И т.д.
Справа. Моя точка зрения заключалась в том, что с длиной хэша 128 бит нет достоверной коллекции данных, достаточно большой, чтобы сделать конфликт даже отдаленно вероятным. –
Это много записей ;-) в порядке 1 000 000 000. лучше подумать об этом ...
Характер записей не указан: мы просто открываем их, по одному вовремя, читаем их последовательно или есть какой-то индекс, или, может быть, они хранятся как файлы в разных каталогах? Также неопределенный в вопросе - это наличие dbms, которое мы можем использовать для индексных данных (вместо того, чтобы сортировать его с помощью нашего собственного кода).Также [даже приблизительная] идея о количестве дубликатов поможет направить некоторые из вариантов на эффективный процесс.
Если индекс не существует, мы можем/должны его создать; это может быть сделано как первый проход данных. Тот же самый проход будет использоваться для создания дайджеста сообщений (хеш) для каждой записи (или, возможно, для целей эффективности для первых нескольких сотен байт записи).
Общая идея заключается в том, чтобы быстро произвести индекс, который может быть использован для выявления возможных дубликатов и завершить список фактического дубликата, возможно, через параллельную обработку.
Информационный полезной для индекса будет:
Выбор хеша критический: следует использовать быстрый алгоритм за счет того, что он отлично распределен; количество байтов, хэшированных для каждой записи, также является компромиссом, возможно, от 100 до 200 байтов (т. е. примерно от 10 до 20% от среднего размера записи) является хорошим значением в зависимости от ожидаемого коэффициента дублирования и в зависимости от экономии времени это обеспечивает (по сравнению с хэшированием всей записи). (см. править ниже)
Как только такой индекс доступен, мы можем [относительно быстро/без усилий] получить количество возможных дубликатов; на основе этого результата может быть сделан второй проход, направленный на повышение качества индекса, если он не считается достаточно избирательным, (без учета записей, которые считаются уникальными). Этот второй проход может вычислять другой хеш, в целом записи (исключая первые x байтов первого хэша) или на еще одном подмножестве записи. Обратите внимание, что благодаря индексу этот второй проход может быть многопоточным, если это возможно.
Второй или последний проход требует сортировки записей в пределах группы возможных совпадений (одинаковая длина, один и тот же хэш-код (ы), одни и те же первые байты). Это может быть достигнуто как описано Pax Diablo, преимущество индекса заключается в том, что такая операция может снова быть многопотоковой и включает в себя гораздо меньшие множества (многие из них). Добавлено: Здесь снова Ник Джонсон делает отличную мысль о том, что второй проход может оказаться ненужным, если бы мы использовали длинный хеш-код (он предлагает 128-байтовый SHA1). Предполагая, что нет никакого преимущества в частичном хэшировании записей, это очень правдоподобное решение, так как индекс может находиться на диске и, тем не менее, быстрее сортироваться и храниться, чем если бы мы сортировали/сохраняли все записи.
Редактировать: Ник Джонсон делает отличную точку, что латентность изыскивает в дисковом хранилище может быть такой, простой последовательного чтения быстрее и, что узким местом является дискового ввода/вывода связаны, быстро хеш-функция одновременно может быть быстрее, чем последовательное чтение, и, следовательно, не добавлять к общему процессу. Это вероятная возможность (особенно если последовательное чтение, если оно действительно необходимо для обнаружения каждого начала/конца записи и т. Д.), И именно поэтому я «обрезал свою ставку», написав «в зависимости от экономии времени, это обеспечивает ...» ,Это говорит о том, что фактическая структура записей на диске является одним из открытых параметров вопроса (например, если мы просто читаем отдельные файлы в каталогах, следовательно, накладываем не последовательное чтение), а также хранилище размера TeraByte поддерживаемый причудливым RAID, где латентность поиска, оставаясь проблемой, как правило, значительно улучшается.
Я согласен с тем, что два подхода подходит к может быть более эффективным, чем один, где каждая запись полностью хэшируется, но я бы хотел подчеркнуть возможность и преимущества подхода с одним проходом. Как и во многих интервью, некоторые характеристики ситуации были неуточнены; идея заключается не столько в том, чтобы видеть, что заявитель дает абсолютный правильный ответ (хотя некоторые ответы могут быть совершенно неправильными!), а вместо этого, чтобы получить представление о его мыслительном процессе и способности определять варианты и точки принятия решений.
Как правило, хорошая стратегия, но я думаю, вы недооцениваете отношение времени процессора к задержке поиска диска. Учитывая характеристики хранения прядения ржавчины, определенно нет смысла только хешировать некоторые из каждой записи - вам нужно прочитать всю запись, чтобы перейти к следующей в любом случае - и поскольку ваш процессор намного быстрее вашего диска , вы также можете использовать хорошо распределенную хэш-функцию, такую как SHA1. –
Кроме того, если вы столкнулись со всей проблемой написания такого индекса на диске, вы можете включить хэш достаточно долго, чтобы быть достаточно уверенным, что если H (a) == H (b), то == b - например, не менее 128 байт, что позволяет пропустить последующие проходы. –
@Alex: Мне было бы интересно, если бы вы могли квалифицировать свой комментарий. Насколько я могу судить об этом конкретном решении, это так же хуже, как и другие (за исключением Potatocorn), и я не могу понять, почему люди голосуют за это ответьте. – 2010-04-04 11:42:25
Во-первых, настроить компьютер с бесконечно большой файл подкачки на бесконечно большом диске ...
Решения, предлагаемые до сих пор кажутся слишком сложными. A Bloom filter, будучи структурой данных du jour в течение последних нескольких лет, не рекомендуется применять в такой ситуации: поскольку данные не могут быть связаны с хешированным контентом, вы должны не только поддерживать фильтр Bloom, но и вы все равно должны записывать каждое (только 6-битное!) значение хэша и записывать на диск, уничтожая преимущество фильтра цветения и имея неистово высокий уровень столкновений.
С другой стороны, слияние сортировки по всему терабайту не только будет проводить сравнения O(n log n), но и O(n log n) дискового трафика, так как большинство промежуточных файлов необходимо будет объединить с диска, а не из памяти. Любое реальное решение должно стараться максимально сократить трафик на диске, поскольку это наше основное узкое место.
Мое решение прост, если принять одно предположение: терабайт данных записывается в том, что фактически является одним файлом.
Итерации по записям файла терабайта и их хэш. Криптографический хеш здесь лишний, дорогостоящий и слишком большой; вместо этого используйте что-то вроде 64-bit version of murmurhash. Он может хэш более 2 GiB/sec (гораздо быстрее, чем мы, вероятно, понадобятся, учитывая скорость хранения в эти дни) и обладает отличным (хотя и не криптографически безопасным) сопротивлением столкновению. С 64-битным хешем, we would expect our first collision at 2^32, так что вполне вероятно, что у наших примерно одного миллиарда записей вообще не будет никаких столкновений.
Напишите хэши и связанные с ними записи смещения в другой файл. Поскольку записи содержат произвольные двоичные данные, мы не можем полагаться на сортировку Unix (1), так как некоторые хеши и смещения могут содержать то, что sort (1) будет интерпретировать как новые строки. Мы просто напишем записи как фиксированную ширину (возможно, 16 байт: 8 байтов для 64-битного хеша murmur2 и 8 байтов для сдвига в файле терабайтного файла). Полученный файл должен быть около 16 ГБ, учитывая наш номер записей.
Мы можем сортировать этот файл, читая количество записей, которые будут безопасно вписываться в память и сортировать их, промывая отсортированные куски обратно на диск. Мы можем поместить больше записей в память с помощью heapsort (он использует пространство O(1)), чем с быстрой сортировкой (которая использует память O(log n) для стека вызовов), но в большинстве реализаций quicksort выигрывает в силу своей локальности памяти и более низкого количества команд. Эти промежуточные файлы (их должно быть 35-40) будут записаны на диск.
Последний шаг - объединить эти файлы (в памяти, нет необходимости хранить результат на диске для этого), собирая все хэш-коллизии и просматривая связанные записи в терабайтном файле, сравнивая записи для дублирования и испускания записи (или их смещения) каким бы то ни было образом указывает проблема.
Насколько я могу судить, эта задача попадает на диск значительно меньше, чем любое другое предлагаемое решение, и это очень концептуально просто: хешировать записи, искать дубликаты в хэшах и проверять в реальных записях.
Для диска I/O было бы прочитать файл данных терабайт, запись 16 Гб на диск, прочитал, что 16 Гб с диска и записать его обратно сортируют, а затем прочитать его и вернуть дубликаты.В качестве оптимизации процесс хэширования записей мог накапливать их в памяти, прежде чем вымывать их на диск, сортируя их до этого: он вырезает промежуточный файл 16 ГБ и позволяет процессу перемещаться из хэширования непосредственно в слияние и отчетность дубликаты.
Это не 6-битный хеш. Каждая запись устанавливает шесть бит в пределах 4-гигабитного вектора, и вы будете хранить индексы этих бит в случае столкновения. В более традиционных хэш-терминах он ближе к 6 * 32 = 192 бит. – Boojum
У вас есть 10^9 блоков, и вы ожидаете своего первого столкновения при 2^32 (это действительно так? Я считаю, что вы недооцениваете скорость столкновения murmurhash, но я этого не проверял). Как вы можете заключить, что у вас вообще не будет столкновения? Фактически, у вас есть вероятность столкновения 1 в 4: 2^32 ≈ 4e9. –
@ Рыжий единорог: Вы прочитали статью, которую я связал с парадоксом дня рождения? Это охватывает математику, участвующую в моей претензии, и имеет специальный раздел, посвященный столкновениям в хеш-функциях. Как правило, учитывая равномерно распределенный хеш с N битами, вы должны ожидать (под которым я имею в виду «вероятность более 50%) столкновения вокруг 2^(N/2) -го объекта. бит хэша я рекомендую, скорее всего, вы не увидите столкновения (кроме подлинного дубликата) в миллиардах вещей, хэшированных. В любом случае столкновения будут маловероятными, и мой алгоритм их учитывает. – jemfinch
Вы можете использовать хэш, чтобы уменьшить размер проблемы. Например, если у вас есть 1 ТБ данных, то вы определяете хеш-функцию, и данные делятся на десять файлов (размер каждого файла меньше 1 TB). После этого, если один файл все еще слишком велик, повторите процедуру, пока файл не будет сохранен в памяти. Наконец, вы можете подсчитать время появления по своему усмотрению.
Для блоков ~ 1.76e9, цветной фильтр размером примерно 7e8 бит или 700MB с 5 хэш-функциями должен дать вам ложную положительную вероятность около 1/8.0e9, что должно быть * больше *, чем достаточно. – 2010-04-04 07:08:51
@ Мономер: может быть, это ответ? Я не вижу никого другого, кто его получил. Создайте это сообщество wiki, если вы хотите, чтобы другие детализировали детали. – Potatoswatter
@Potatocorn: не стесняйтесь ответить на него. Кстати, я бы предположил, что статья митценмахера о необходимости только двух хэш-функций может быть интересной. – 2010-04-04 09:07:48