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

Я хотел бы сохранить пару записей в файл (оптимизированный для чтения) и хорошую структуру данных для этого, похоже, дерево 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 () вместо этого? Или есть разница только в том, что я mmap много блоков и получаю доступ только к нескольким? Что лучше?
  4. Должен ли я пытаться избежать порождения ключей несколькими блоками, добавляя байты заполнения в конце каждого блока? Должен ли я сделать то же самое для листовых узлов, добавив байты заполнения между данными?

Большое спасибо,
Кристоф


linux filesystems io b-tree
person tux21b    schedule 20.06.2011    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

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

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

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

person Damon    schedule 20.06.2011

arrow_upward
3
arrow_downward

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

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

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

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

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

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

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

person MarkR    schedule 20.06.2011
comment
Да. Хотя самое циничное в этом (г-н Торвальдс не согласен...) заключается в том, что поставщики баз данных не имеют особого выбора, кроме как создавать потоки только для дискового ввода-вывода, поскольку madvise/msync намеренно нарушены в Linux, справочные страницы лгать вам, и KAIO возвращается к синхронной работе, если O_DIRECT не задан. - person Damon; 21.06.2011
comment
Большое спасибо за указание на Direct IO (и как определить размер блока). На мой взгляд, прямой ввод-вывод может быть полезен для СУБД, потому что он дает вам больше контроля и работает быстрее, если все сделано правильно, хотя вы теряете много комфорта (буферизация, опережающее чтение,...). - person tux21b; 21.06.2011

arrow_upward
1
arrow_downward

  1. Да. В противном случае возникнут ненужные сложности при проектировании FS.
  2. А варианты (как альтернатива "только") есть...?
  3. В Windows файлы с отображением памяти работают быстрее, чем файловый API (ReadFile). Я думаю, в Linux это то же самое, но вы можете провести свои собственные измерения.
person Eugene Mayevski 'Callback    schedule 20.06.2011