Самый быстрый способ сделать много маленьких, слепых записей на огромном файле (в C++)?
У меня есть некоторые очень большие (> 4 ГБ) файлы, содержащие (миллионы) двоичные записи фиксированной длины. Я хочу (эффективно) соединить их с записями в других файлах путем записи указателей (т.е. 64-разрядные рекордные числа) в те записи при определенных смещениях.
Для разработки у меня есть пара списков (ключ, рекордное число) кортежи, отсортированные по ключу для каждого соединения, которое я хочу выполнить на данной паре файлов, скажем, A и B. Итерация через пару списка и совпадение ключей приводят к списку (ключ, рекордное число A, рекордное число B) кортежи, представляющие записи, к которым присоединяются (принимающий 1:1 отображающийся для простоты). Для завершения соединения я концептуально должен искать на каждого запись в списке и записать соответствующее рекордное число B при соответствующем смещении, и наоборот. Мой вопрос - то, что самый быстрый путь состоит в том, чтобы на самом деле сделать это?
Так как список записей, к которым присоединяются, отсортирован по ключу, связанные рекордные числа чрезвычайно случайны. Принятие файла намного больше, чем дисковый кэш ОС, делая набор случайных ищет, и записи кажется чрезвычайно неэффективным. Я попытался частично сортировать рекордные числа путем помещения A-> B и B-> отображения в разреженном массиве и сбрасывания самых плотных кластеров записей в диск каждый раз, когда у меня заканчивается память. Это обладает преимуществом большого увеличения возможностей, что соответствующие записи будут кэшироваться для кластера после обновления его первого указателя. Однако даже в этой точке, обычно лучше сделать, набор ищет и слепые записи, или считать блоки файла вручную, обновить соответствующие указатели и записать блоки обратно? В то время как бывший метод намного более прост и мог быть оптимизирован ОС, чтобы сделать абсолютный минимум чтений сектора (так как это знает размер сектора), и копии (это может избежать копий путем чтения непосредственно в правильно выровненные буферы), кажется, что это подвергнется чрезвычайно высокому syscall наверху.
В то время как я любил бы портативное решение (даже если оно включает зависимость от библиотеки, которой широко пользуются, такой как Повышение), современный Windows и Linux являются единственными необходимыми вещами, таким образом, я могу использовать определенные для ОС API (например, подсказки CreateFile или рассеяться/собрать ввод-вывод). Однако это может включить большую работу для ровного испытания, таким образом, я задаюсь вопросом, может ли кто-либо сказать мне, если это вероятно стоящий усилия.
4 ответа
Я попытался частично отсортировать номера записей, поместив сопоставления A-> B и B-> A в разреженный массив и сбрасывая самые плотные кластеры записей на диск всякий раз, когда у меня заканчиваются памяти. похоже, что это повлечет за собой чрезвычайно высокие накладные расходы на системные вызовы.
Вы можете использовать доступ к файлу с отображением памяти, чтобы избежать накладных расходов на системные вызовы. mmap () в * NIX и CreateFileMapping () в Windows .
Логически разбить файл на блоки, например 32 МБ. Если что-то нужно изменить в блоке, используйте mmap () it, измените данные, при желании - msync (), munmap () и затем перейдите к следующему блоку.
Это было бы то, что я попробовал в первую очередь. ОС будет автоматически читать все, что нужно прочитать (при первом доступе к данным), и будет ставить в очередь ввод-вывод в любом случае.
Важно помнить, что на самом деле ввод-вывод происходит не так быстро. Факторами, ограничивающими производительность для произвольного доступа, являются (1) количество операций ввода-вывода в секунду (IOPS), которое может обрабатывать хранилище, и (2) количество обращений к диску. (Обычный IOPS находится в диапазоне сотен. Обычная задержка поиска составляет 3-5 мсек.) Например, хранилище может читать / писать со скоростью 50 МБ / с: один непрерывный блок размером 50 МБ за одну секунду.Но если вы попытаетесь исправить побайтный файл размером 50 МБ, время поиска просто убьет производительность. До некоторого предела нормально читать и писать больше, даже если обновлять только несколько байтов.
Еще одно ограничение, которое следует соблюдать, - это максимальный размер операции ввода-вывода ОС: он зависит от хранилища, но большинство ОС разделяют задачи ввода-вывода размером более 128 КБ. Лимит можно изменить, и лучше всего, если он будет синхронизирован с аналогичным лимитом в хранилище.
Также не забывайте о хранилище. Многие забывают, что хранилище часто бывает только одно. Я пытаюсь здесь сказать, что запуск множества потоков не помогает вводу-выводу, если у вас нет нескольких хранилищ. Даже один процессор / ядро способен легко насыщать RAID10 с его пределами 800 операций ввода-вывода в секунду при чтении и 400 операций ввода-вывода в секунду при записи. (Но выделенный поток для каждого хранилища, по крайней мере, теоретически имеет смысл.)
Надеюсь, что это поможет. Другие люди здесь часто упоминают Boost.Asio, с которым у меня нет опыта, но это стоит проверить.
P.S. Честно говоря, мне бы очень хотелось услышать другие (более информативные) ответы на ваш вопрос. Я был в лодке уже несколько раз, но у меня не было возможности по-настоящему добраться до нее. Приветствуются книги / ссылки и т. Д., Относящиеся к оптимизации ввода-вывода (независимо от платформы);)
Вместо построения списка (ключ, запись номер A, запись номер B) я бы опустил ключ для экономии места и просто построил (запись номер A, запись номер B). Я бы отсортировал эту таблицу или файл по А, последовательно просмотрел каждую запись А, записал номер В, затем отсортировал список по В, последовательно просмотрел каждую запись В, записал номер А.
Я делаю очень похожие манипуляции с большими файлами, и эти новые машины настолько чертовски быстры, что это не занимает много времени:
На дешевом HP Pavilion 2.4gHz с 3gb ram и 32-bit Vista, запись 3 миллионов последовательных 1,008-байтовых записей в новый файл занимает 56 секунд, используя библиотечные процедуры Delphi (в отличие от Win API).
Последовательный поиск каждой записи в файле и запись 8 байт с помощью Win API FileSeek/FileWrite на загруженной машине занимает 136 секунд. Это 3 миллиона обновлений. Немедленный повторный запуск того же кода занимает 108 секунд, поскольку операционная система кэширует некоторые вещи.
Сначала сортировка смещений записей, а затем последовательное обновление файлов - вот путь, который нужно пройти.
Похоже, вы можете решить эту проблему, используя структуры данных. У вас есть три ограничения:
- Время доступа должно быть достаточно быстрым
- Данные должны храниться отсортированными
- Вы находитесь на вращающемся диске
B + Trees были созданы специально для решения данной задачи вы здесь имеете дело. Есть несколько ссылок на реализации в связанной статье в Википедии.
По сути, дерево B + представляет собой двоичное дерево поиска, за исключением того, что группы узлов хранятся вместе в группах. Таким образом, вместо того, чтобы искать каждый узел, дерево B + загружает за раз только кусок. И он хранит немного информации, чтобы знать, какой фрагмент потребуется при поиске.
РЕДАКТИРОВАТЬ: Если вам нужно отсортировать более чем по одному элементу, вы можете сделать что-то вроде:
+--------+-------------+-------------+---------+
| Header | B+Tree by A | B+Tree by B | Records |
+--------+-------------+-------------+---------+
|| ^ | ^ | ^
|\------/ | | | |
\-------------------/ | |
| | |
\----------+----------/
То есть. у вас есть отдельные деревья B + для каждого ключа и отдельный список записей, указатели на которые хранятся в деревьях B +.
Произвольный доступ к диску обычно на порядки медленнее, чем последовательный доступ к диску. Настолько, что может быть полезно выбирать алгоритмы, которые на первый взгляд могут показаться ужасно неэффективными. Например, вы можете попробовать следующее:
Создайте свой индекс соединения, но вместо его использования просто запишите список пар (индекс A, индекс B) в файл на диске.
Отсортируйте этот новый файл пар по индексу A. Используйте алгоритм сортировки, предназначенный для внешней сортировки (хотя я сам не пробовал, библиотека STXXL из stxxl.sourceforge.net выглядела многообещающей, когда я исследовал аналогичную проблему)
Последовательно пройдитесь по файлу записи A и отсортированному список пар. Прочтите огромный кусок, внесите все необходимые изменения в память, запишите этот кусок. Никогда больше не касайтесь этой части файла записи A (поскольку изменения, которые вы планировали внести, идут в последовательном порядке)
Вернитесь, отсортируйте файл пары по индексу B (опять же, используя внешнюю сортировку). Используйте это для обновления файла записи B таким же образом.