Блочное хранилище

Question

Я хотел бы сохранить пару записей в файле (оптимизированном для чтения), и хорошей структурой данных для этого кажется дерево B +. Он предлагает время доступа O (log (n) / log (b)), где b - количество записей в одном блоке.

Есть много статей и т. Д., Описывающих деревья B +, но у меня все еще есть некоторые проблемы, связанные с системами хранения на основе блоков в целом. Может быть, кто-то может указать мне правильное направление или ответить на пару вопросов:

1. Создают ли (все распространенные) файловые системы новые файлы в начале нового блока? Итак, могу ли я быть уверен, что seek (0) установит головку чтения / записи, умноженную на размер блока устройства?
2. Правильно ли, что я должен использовать только вызовы типа pread(fd, buf, n * BLOCK_SIZE, p * BLOCK_SIZE) (где n, p - целые числа), чтобы всегда читать полные блоки?
3. Лучше ли читать () BLOCK_SIZE байтов в массив или mmap () вместо них? Или есть только разница, если я отображу много блоков и получу доступ только к нескольким? Что лучше?
4. Стоит ли пытаться избежать появления ключей в нескольких блоках, добавляя байты заполнения в конце каждого блока? Должен ли я сделать то же самое для конечных узлов, добавив байты заполнения между данными?

Большое спасибо,
Christoph

Answer 1

1. Файловые системы, которые поддерживают отложенное размещение, не создают новые файлы в любом месте на диске.Многие новые файловые системы поддерживают упаковку очень маленьких файлов на свои собственные страницы или совместное использование их с метаданными (например, reiser помещает очень маленькие файлы в inode?).Но для больших файлов, в основном, да.

2. Вы можете сделать это, но кэш страницы ОС всегда будет считывать весь блок и просто копировать запрошенные вами биты в память вашего приложения..

3. Это зависит от того, используете ли вы прямой или не прямой ввод-вывод.

Если вы используете прямой ввод-вывод, который обходит кеш ОС, вы не используете mmap.Большинство баз данных не используют mmap и используют прямой ввод-вывод.

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

Большинство баз данных, похоже, придерживаются мнения, что им следует самим управлять собственным кэшем страниц и использовать ОС только для физических операций чтения / записи.Поэтому они обычно используют прямой и синхронный ввод-вывод.

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

Answer 2

1. Как правило, файловые системы создают новые файлы в начале нового блока, потому что именно так работает базовое устройство. Жесткие диски являются блочными устройствами и поэтому не могут обрабатывать что-либо меньшее, чем «блок» или «сектор». Кроме того, операционные системы обрабатывают отображение памяти и памяти в терминах страниц, которые обычно даже больше (секторы часто составляют 512 или 1024 байта, страницы обычно 4096 байтов).
   Единственное исключение из этого правила, которое приходит на ум, - это ReiserFS, который помещает небольшие файлы непосредственно в структуру файловой системы (которая, если я правильно помню, является, по сути, деревом B +!). Для очень маленьких файлов это может быть жизнеспособной оптимизацией, поскольку данные уже находятся в оперативной памяти без повторного поиска, но в зависимости от ситуации это может быть и антиоптимизация.

2. Это на самом деле не имеет значения, потому что операционная система все равно будет считывать данные в полных страницах (обычно 4 КБ) в кеш страниц. Чтение одного байта передаст 4 КБ и вернет байт, чтение другого байта послужит вам из кеша страниц (если это та же страница или та, которая находилась в пределах диапазона чтения).

3. read реализуется путем копирования данных из кэша страниц, тогда как mmap просто переназначает страницы в ваше адресное пространство (возможно, помечая их как «копирование при записи», в зависимости от ваших флагов защиты). Следовательно, mmap всегда будет по крайней мере таким же быстрым и обычно быстрее. mmap также более удобен, но имеет недостаток, заключающийся в том, что он может блокироваться в неожиданные моменты времени, когда ему нужно извлечь больше страниц, которые не находятся в ОЗУ (хотя, как правило, это верно для любого приложения или данных, которые не заблокированы в памяти) , read с другой стороны блокирует, когда вы говорите это, не иначе.
   То же самое верно для Windows, за исключением того, что файлы с отображением в памяти в Windows до Windows Vista плохо масштабируются при высоком параллелизме, так как менеджер кэша сериализует все.

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

Answer 3

1. Да.В противном случае возникнут ненужные сложности в дизайне FS.
2. И варианты (в качестве альтернативы "only"): ...?
3. В Windows отображаемые в память файлы работают быстрее, чем файловый API(ReadFile).Я думаю, что в Linux это то же самое, но вы можете проводить свои собственные измерения