Оптимизация расположения данных на диске для последовательного доступа

Question

Мне нужно хранить большие объемы данных на диске примерно в 1 тыс. Блоков. Я буду обращаться к этим объектам способом, который трудно предсказать, но где шаблоны, вероятно, существуют.

Существует ли алгоритм или эвристика, которые я могу использовать, чтобы переставить объекты на диске на основе моих шаблонов доступа, чтобы попытаться максимально увеличить последовательный доступ и, таким образом, минимизировать время поиска на диске?

Answer 1

В современных операционных системах (Windows, Linux и т. Д.) Вы абсолютно ничего не можете сделать, чтобы оптимизировать время поиска! И вот почему:

1. Вы находитесь в упреждающей многозадачной системе. Ваше приложение и все его данные могут быть записаны на диск в любое время - пользователь переключает задание, запускается заставка, батарея разряжается и т. Д.
2. Вы не можете гарантировать непрерывность файла на диске. Выполнение первого пункта Аарона не обеспечит нефрагментированный файл. Когда вы начинаете писать файл, ОС не знает, насколько большим будет файл, поэтому она может поместить его в небольшое пространство, фрагментируя его, когда вы записываете в него больше данных.
3. Отображение памяти в файле работает только до тех пор, пока размер файла меньше доступного диапазона адресов в вашем приложении. На Win32 объем доступного адресного пространства составляет около 2 Гб - памяти, используемой приложением. Отображение больших файлов обычно включает в себя удаление и повторное сопоставление частей файла, что не будет лучшим решением.
4. Поместить данные в центр файла не поможет, поскольку, насколько вы знаете, центральная часть файла может быть самым фрагментированным битом.

Перефразируя Раймонд Чен , если вам нужно спросить об ограничениях ОС, вы, вероятно, делаете что-то не так. Относитесь к вашей файловой системе как к неизменному черному ящику, это просто то, чем она является (я знаю, вы можете использовать RAID и т. Д., Чтобы помочь).

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

Судя по вашему сообщению, вы на самом деле еще не написали никакого кода, или, если у вас есть, в данный момент проблем с производительностью нет.

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

Answer 2

В зависимости от того, что вы подразумеваете под «трудно предсказать», я могу придумать несколько вариантов:

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

Если вы ищете в разных полях блока, рассмотрите возможность сохранения внешнего индекса для каждого поля. A b-tree дает вам эффективность O (log n). Когда вы будете искать, возьмите соответствующий индекс, найдите в нем адрес файла данных вашего блока и перейдите к нему.

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

Answer 3

Используйте отображенный в памяти доступ к файлу, а не обычный шаблон «открытый поиск-чтение-запись / запись». Этот метод работает на платформах Windows и Unix.

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

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

Answer 4

Самый простой способ решить эту проблему - использовать ОС, которая решает эту проблему за вас, например, Linux. Дайте ему достаточно ОЗУ для хранения 10% объектов в ОЗУ, и он попытается сохранить как можно больше из них в кэше, сократив время загрузки до 0. Последние версии Windows server могут работать, тоже (некоторые из них не для меня, поэтому я упоминаю об этом).

Если это не пойдет, попробуйте этот алгоритм:

• Создать очень большой файл на жестком диске. Очень важно, чтобы вы записали это за один раз, чтобы ОС выделяла непрерывное пространство на диске.

• Запишите все ваши объекты в этот файл. Убедитесь, что каждый объект имеет одинаковый размер (или предоставьте каждому одинаковое пространство в файле и запишите длину в первых нескольких байтах каждого фрагмента). Используйте пустой жесткий диск или диск, который был только что дефрагментирован.

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

• [РЕДАКТИРОВАТЬ] Доступ к этому файлу осуществляется через API-интерфейс отображаемой памяти вашей ОС, позволяющий ОС эффективно кэшировать наиболее используемые компоненты для достижения максимальной производительности, пока вы не сможете оптимизировать структуру файла в следующий раз. 1022 *

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

Тем не менее, вы действительно должны полагаться на современных ОС, где много умных людей думали долго и упорно, чтобы решить эти вопросы для вас.

Answer 5

Это интересный вызов. К сожалению, я не знаю, как решить это из коробки, либо. Подход Корбина звучит для меня разумно.

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

Пожалуйста, дайте нам знать, если вы сами найдете решение.