Группирование данных по цилиндрам диска

Поскольку время поиска отнимает около половины среднего времени считывания/записи блока, существует много разновидностей приложений, в которых целесообразно предусмотреть возможность размещения данных, обрабатываемых с определённой долей вероятности совместно, в пределах одного цилиндра. Если ёмкость одного цилиндра недостаточна, можно воспользоваться несколькими смежными цилиндрами.

Если все блоки одной дорожки или одного цилиндра считываются последовательно, можно пренебречь всеми составляющими времени чтения, кроме:

- первого периода поиска, необходимого для перемещения блока головок к нужному цилиндру;

- первого промежутка времени оборота до достижения начального сектора последовательности блоков;

- времени передачи.

Этот подход показывает прекрасные результаты для приложений, где порядок обращений к диску известен заранее и в каждый момент времени с диском работает только один процесс.

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

Исходные данные (системы):

Показатель	Значение
дисковый привод
размер буферов оперативной памяти (ОП)	100 Мб
размер блока данных	16 Кб
количество блоков, которые можно разместить в ОП	6 400
среднее время считывания и записи	11 млсек
скорость вращения	7 200 об./мин.
время поворота на один оборот	8,33 млсек
время старта	1 млсек
время перемещения на 1000 цилиндров	1 млсек
время на остановку	1 млсек
время перемещения к соседней дорожке	1 млсек
время перемещения от внутренней дорожки к внешней	17,38 млсек
время передачи	0,25 млсек
среднее время поиска данных	6,46 млсек.
число дорожек	16 384

Исходные данные (БД):

Показатель	Значение
число строк в отношении	10 000 000
длина строки	160 байт
размер блока	16 384 байта
количество записей в блоке (коэффициент блокирования)
количество блоков в отношении	100 000

Проанализируем производительность алгоритма сортировки двухфазным многокомпонентным слиянием, рассмотренного ранее. Процедура сортировки отношения, состоящего из 10 000 000 записей и занимающего около 1Гб дискового пространства, выполнялась за 74 мин. Это время делилось на 4 равных промежутка, необходимых для осуществления функций чтения и записи блоков для 2-х фаз алгоритма.

Первая фаза: чтение в оперативную память (ОП) 6 400 блоков 16 раз. При размещении отношения (100 000 блоков) на последовательных цилиндрах, каждый из которых содержит 512 блоков, нам потребуется 196 цилиндров. При этом однократно в буферы ОП можно считать содержимое 13 цилиндров (6400/512≈13).

Время, необходимое для однократного чтения исходных данных в ОП, складывается из следующих компонент:

- среднего времени одной операции поиска – 6,46 млсек.;

- времени поиска каждого из 12 соседних цилиндров – 12 млсек.;

- времени передачи 6 400 блоков – 1,6 сек.

Двумя первыми компонентами можно пренебречь. Поскольку заполнять ОП данными необходимо 16 раз, общее время считывания данных на первой фазе составит:

Для сохранения 16 отсортированных подсписков могут использоваться другие 196 соседних цилиндров, и временные параметры процесса записи окажутся аналогичными: один период «случайного» поиска цилиндра, 12 промежутков времени для перемещения головки от одного цилиндра к другому и время передачи 6 400 блоков для каждого из 16 отсортированных подсписков. Поэтому общее время записи данных на первой фазе также составит 26 сек., а время выполнения первой фазы целиком:

При «случайном» расположении блоков это время составляло около 37 мин.

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

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