Самый быстрый способ сделать много маленьких слепых записей на огромном файле (в C ++)?

Question

У меня есть несколько очень больших (> 4 ГБ) файлов, содержащих (миллионы) двоичных записей фиксированной длины. Я хочу (эффективно) объединить их с записями в других файлах, записав указатели (т.е. 64-битные номера записей) в эти записи с определенными смещениями.

Чтобы уточнить, у меня есть пара списков (ключ, номер записи), отсортированных по ключу для каждого объединения, которое я хочу выполнить для данной пары файлов, скажем, A и B. Итерация по паре списков и сопоставление up the keys - список кортежей (ключ, номер записи A, номер записи B), представляющих объединенные записи (для простоты предполагается отображение 1: 1). Чтобы завершить объединение, мне концептуально необходимо найти каждую запись A в списке и записать соответствующий номер записи B с соответствующим смещением, и наоборот. У меня вопрос, какой самый быстрый способ сделать это?

Поскольку список объединенных записей отсортирован по ключу, связанные номера записей по существу случайные. Предполагая, что файл намного больше, чем кеш диска ОС, выполнение случайных операций поиска и записи кажется крайне неэффективным. Я попытался частично отсортировать номера записей, помещая сопоставления A-> B и B-> A в разреженный массив и сбрасывая самые плотные кластеры записей на диск всякий раз, когда у меня заканчивается память. Преимущество этого заключается в значительном увеличении вероятности кэширования соответствующих записей для кластера после обновления его первого указателя. Тем не менее, даже в этот момент, как правило, лучше выполнить несколько операций поиска и слепой записи или прочитать фрагменты файла вручную, обновить соответствующие указатели и записать фрагменты обратно? Хотя первый метод намного проще и может быть оптимизирован ОС для выполнения минимального чтения секторов (так как он знает размер сектора) и копий (он может избежать копий, читая непосредственно в правильно выровненные буферы), кажется, что он Это приведет к чрезмерно высоким системным вызовам.

Хотя я бы хотел портативное решение (даже если оно предполагает зависимость от широко используемой библиотеки, такой как Boost), современные Windows и Linux являются единственными необходимыми компонентами, поэтому я могу использовать API-интерфейсы для конкретных ОС. (например, подсказки CreateFile или разброс / сбор данных ввода / вывода). Тем не менее, это может потребовать много работы, чтобы даже попробовать, поэтому мне интересно, если кто-нибудь может сказать мне, если это стоит усилий.

Answer 1

Похоже, вы можете решить эту проблему с помощью структур данных. У вас есть три ограничения:

• Время доступа должно быть достаточно быстрым
• Данные должны храниться отсортированными
• Вы на вращающемся диске

B + Деревья были созданы специально для решения той рабочей нагрузки, с которой вы здесь работаете. В связанной статье Википедии есть несколько ссылок на реализации.

По сути, дерево B + - это двоичное дерево поиска, за исключением того, что группы узлов объединяются в группы. Таким образом, вместо того, чтобы искать каждый узел, дерево B + загружает только порцию за раз. И он хранит немного информации, чтобы знать, какой блок ему понадобится при поиске.

РЕДАКТИРОВАТЬ: Если вам нужно отсортировать по более чем одному элементу, вы можете сделать что-то вроде:

+--------+-------------+-------------+---------+
| Header | B+Tree by A | B+Tree by B | Records |
+--------+-------------+-------------+---------+
      ||      ^     |     ^    |          ^
      |\------/     |     |    |          |
      \-------------------/    |          |
                    |          |          |
                    \----------+----------/

т.е. у вас есть отдельные деревья B + для каждого ключа и отдельный список записей, указатели на которые хранятся в деревьях B +.

Answer 2

Я попытался частично отсортировать номера записей, поместив отображения A-> B и B-> A в разреженный массив, и сбрасывал самые плотные кластеры записей на диск всякий раз, когда мне не хватало памяти.похоже, что это приведет к чрезмерно высоким издержкам syscall.

Вы можете использовать доступ к файлу с отображением в памяти, чтобы избежать издержек syscall. mmap () в * NIX и CreateFileMapping () в Windows .

Логически разбить файл на блоки, например, 32 МБ.Если что-то нужно изменить в блоке, mmap (), измените данные, при необходимости, msync (), munmap (), а затем перейдите к следующему блоку.

Это было бы то, что я пробовалпервый.ОС будет автоматически читать все, что нужно (при первом доступе к данным), и она будет ставить в очередь ввод-вывод в любом случае.

Важно помнить, что реальный ввод-вывод не такой быстрый.Факторами, ограничивающими производительность для произвольного доступа, являются (1) количество операций ввода-вывода в секунду (IOPS), которые может обрабатывать хранилище, и (2) количество обращений к диску.(Обычный IOPS находится в диапазоне сотен. Обычная задержка поиска составляет 3-5 мс.) Например, хранилище может считывать / записывать 50 МБ / с: один непрерывный блок 50 МБ в секунду.Но если вы попытаетесь пропатчить байтовый файл размером 50 МБ, то время поиска просто снизит производительность.До некоторого предела можно читать больше и писать больше, даже если обновлять только несколько байтов.

Другим ограничением, которое необходимо соблюдать, является максимальный размер операции ввода-вывода в ОС: он зависит от хранилища, но большинствоОС будут разделять задачи ввода-вывода размером более 128K.Предел может быть изменен и лучше всего, если он синхронизирован с аналогичным пределом в хранилище.

Также имейте в виду хранилище.Многие люди забывают, что хранилище часто только одно.Здесь я пытаюсь сказать, что начальная загрузка потоков не помогает IO, если у вас нет нескольких хранилищ.Даже один процессор / ядро ​​может легко насыщать RAID10 с его 800 IOPS чтения и 400 IOPS записи лимитами.(Но выделенный поток для хранилища по крайней мере теоретически имеет смысл.)

Надеюсь, это поможет.Другие люди часто упоминают Boost.Asio, с которым у меня нет опыта, но это стоит проверить.

PS Честно говоря, я хотел бы услышать другие (более информативные) ответы на ваш вопрос.Я был в лодке уже несколько раз, но у меня не было шансов действительно спуститься к ней.Книги / ссылки / и т.д., связанные с оптимизацией ввода-вывода (независимо от платформы), приветствуются;)

Answer 3

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

Создайте свой индекс соединения, но вместо того, чтобы его использовать, просто запишите список пар (индекс A, индекс B) в файл на диске.

Сортировать этот новый файл пар по индексу А. Используйте алгоритм сортировки, предназначенный для внешней сортировки (хотя я сам не пробовал, библиотека STXXL из stxxl.sourceforge.net выглядела многообещающе, когда я исследовал подобную проблему)

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

Вернитесь назад, отсортируйте файл пары по индексу B (опять же, используя внешнюю сортировку). Используйте это для обновления файла записи B таким же образом.

Answer 4

Вместо построения списка (ключ, номер записи A, номер записи B) я бы не указывал ключ, чтобы сэкономить место и просто построить (номер записи A, номер записи B). Я сортировал бы эту таблицу или файл по A, последовательно просматривал каждую запись A, записывал номер B, затем сортировал список по B, последовательно просматривал каждую запись B, записывал число A.

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

В дешевом HP Pavilion 2,4 ГГц с оперативной памятью 3 ГБ и 32-разрядной Vista запись 3 миллионов последовательных 1 008-байтовых записей в новый файл занимает 56 секунд с использованием подпрограмм библиотеки Delphi (в отличие от Win API).

Последовательный поиск каждой записи в файле и запись 8 байтов с использованием Win API FileSeek / FileWrite на загруженной машине занимает 136 секунд. Это 3 миллиона обновлений. Немедленное повторное выполнение одного и того же кода занимает 108 секунд, поскольку в O / S некоторые вещи кэшируются.

Сортировка смещений записей, а затем последовательное обновление файлов - вот путь.