Сравнение производительности многомерных структур: файлов-решеток и хеширования PLOP

Размещено на http://www.allbest.ru/

СРАВНЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ МНОГОМЕРНЫХ СТРУКТУР: ФАЙЛОВ-РЕШЕТОК И ХЕШИРОВАНИЯ PLOP

В.К. Гулаков, А.О. Трубаков

Аннотация

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

Ключевые слова: многомерные структуры данных, хеширование, PLOP, индексирование данных.

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

В последнее время появились алгоритмы и структуры, способные непосредственно оперировать многомерными объектами без их упрощения [3]. Самыми распространенными среди них являются иерархические (древовидные) структуры и структуры на основе функций хеширования. В большинстве своем данные алгоритмы пришли из одномерного пространства. Однако, перейдя к многоключевым данным, они потеряли свою прозрачность и простоту в оценке сложности и эффективности. Для большей части подобных структур в литературе практически невозможно найти результаты сравнения производительности. Даже те данные, которые можно почерпнуть из зарубежных источников, являются неточными и расплывчатыми, описываются с большим количеством оговорок и условий. Подобное положение вещей объясняется объективным фактом: переход к многомерным данным привел к усложнению схемы оценки производительности. Теперь уже нельзя однозначно сказать, какая из структур окажется более эффективной. При сравнении обязательно должна быть привязка к ситуации и области применения.

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

Файл-решетка [1]. Файл-решетка (Grid File) впервые был описан Д. Нивергелтом, Г. Хинтербергом и К. Севчиком в 1981 г. Это был первый метод многоключевого доступа, основанный на принципах хеширования данных. В дальнейшем появилось множество модификаций, улучшающих те или иные показатели структуры. Однако общие принципы всех структур семейства остались неизменными.

Пусть дано пространство объектов с двумя ключами. Обозначим область ключей как оси Ox и Oy. Для получения решетки на каждую ось накладывается интервал:

X = [x₀, x₁, …, x_n],

Y = [y₀, y₁, …, y_m].

В результате получаем сетчатое деление пространства (рис. 1). Суть разбиения пространства решеткой заключается в получении такого распределения, при котором в каждой ячейке решетки будет не более N объектов. При этом число N является параметром структуры и выбирается таким образом, чтобы ровно N объектов помещались в одном блоке внешней памяти (например, в сегменте жесткого диска). Обычно N находится в диапазоне от 10 до 1000, в зависимости от размера внешнего блока и конечного объекта. Случаи, когда N мало (равно 1 или 2), для данной структуры плохо подходят, поскольку при этом есть вероятность нежелательных случайных эффектов, таких, как, например, «парадокс дней рождения» (высокая вероятность переполнения участка памяти при появлении всего двух записей).

а)

б)

Рис. 1. Пример деления пространства решеткой с N=3: а - решеточное деление; б - сопоставление с внешними блоками

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

При разработке данного метода поиска были заложены два принципа, наложившие отпечаток на большинство алгоритмов:

1) принцип двух дисковых запросов: запрос на точное совпадение по всем ключам должен вернуть запись или флаг ее отсутствия в индексе за два обращения к внешней памяти: первое - к нужной части директории, второе - к нужному блоку внешней памяти;

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

Принцип двух дисковых запросов подразумевает, что все записи из одной ячейки решетки должны быть расположены в одном внешнем блоке памяти (иначе для поиска понадобится более двух обращений к внешней памяти). Однако очень неэффективно было бы обратное требование. Если бы каждому внешнему блоку соответствовала единственная ячейка решетки, то использование памяти было бы низким. Например, на рис. 1 четыре ячейки, расположенные в правом нижнем углу, являются малозаполненными или даже пустыми. Если для каждой из них выделять отдельные внешние блоки, то использование памяти в структуре будет практически нулевым. Гораздо более эффективно с точки зрения памяти выделить для всех этих ячеек один внешний блок и поместить все записи в него. Таким образом, получается объединение ячеек решетки в один внешний блок. Совокупность всех ячеек решетки, сопоставленных с одним участком памяти (или, другими словами, пространство, занимаемое этими ячейками), называется объединенной ячейкой или группой. Форма этих объединений влияет на скорость как минимум двух операций:

1) диапазонного запроса;

2) обновления после изменений в разделении решетки.

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

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

Хеширование PLOP [2]. Данную структуру разработали Г.П. Кригел и Б.Сигер в 1988 г. Она также основана на решеточном делении пространства, но в ней не используется директория. Это позволяет сэкономить одно обращение к внешней памяти при поиске, но вносит дополнительные ограничения на организацию данных и процедуру хеширования.

Размещено на http://www.allbest.ru/

Как и в случае файла-решетки, на каждую ось пространства накладывается некоторая шкала, которая позволяет получить решетку. Однако с целью увеличения скорости поиска интервала в шкале разработчики предложили сделать ее в виде обычного бинарного дерева. Подобный подход, помимо увеличения скорости поиска, позволил индексировать неоднородные распределения данных, которые плохо подходили для хеширования MOLHPE (MOLHPE и PLOP используют практически идентичные функции хеширования). Пример разбиения пространства с помощью иерархических шкал показан на рис. 2. В данном примере индексируются объекты, имеющие два ключа. Область определения каждого ключа находится в диапазоне от 0 до 1.

Каждый внутренний узел дерева, образующего шкалу, содержит некоторое значение, разбивающее всю область определения ключа на две группы: объекты, меньшие по данному ключу указанного значения, помещаются в левое поддерево, а те, которые больше, - в правое. Листовые узлы шкал соответствуют некоторым столбцам или строкам решетки. Они содержат индекс данного столбца/строки. В качестве индекса выступает некоторое целое число, по сути являющееся номером деления пространства по данной оси, в результате которого появилась эта строка/столбец. Индекс не совпадает с номером в решетке, поэтому его обязательно нужно хранить в листовых узлах. Кроме индекса каждый лист содержит еще количество точек в области. Эта информация используется для расширения файла линейным способом.

Всё пространство данных представляет собой объединение d-мерных прямоугольников, которые разделены гиперплоскостями. Эти области называются ячейками. Все d-мерные точки, находящиеся в одной ячейке, хранятся в одной странице. Адрес этой страницы вычисляется с использованием индексов (i₀, i₁, …, i_d-1), полученных из иерархических шкал. Непосредственно номер внешнего блока, содержащего объекты той или иной ячейки, вычисляется с помощью хеш-функции G(i₀, i₁, …, i_d-1), где i_j - индекс j-й оси. Для наглядности на рис. 2 показаны адреса страниц пространства данных, полученные с помощью хеш-функции G с использованием массива индексов (i₀, i₁).

Сначала файл состоял из 4 страниц с адресами 0, 1, 2, 3. После удвоения файла добавились страницы с адресами 4, 5, 6, 7 в лексикографическом порядке в соответствии с (i₀, i₁). При дальнейшем увеличении файла добавились страницы с адресами 8-15, которые также расположены в лексикографическом порядке, но теперь уже в соответствии с (i₁, i₀).

Чтобы получить подобное распределение, необходимо ввести некоторую функцию, которая будет зависеть от L - уровня файла. Уровень файла показывает, сколько раз файл был увеличен в 2 раза в результате полных расширений. Нетрудно заметить, что если расширения по осям чередуются, то значение L всегда больше числа расширений по конкретным осям пространства. Для вычисления числа полных расширений по некоторому j-му измерению можно воспользоваться следующей формулой:

Здесь s - текущая ось пространства, вдоль которой происходит расширение в настоящий момент времени. Как было показано, ее легко определить с помощью формулы

.

Сама же функция хеширования выражается следующим образом:

гдеz - максимальный уровень по ключам записи,

M - весь набор измерений, кроме z, J_j - количество блоков до искомого в j-м измерении,

t - уровень измерения z для хешируемой записи, с_j - количество дополнительных блоков в j-м измерении,

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

Количество обращений к внешней памяти. Самым первым показателем, на который обращают внимание при выборе структуры индексирования большого объема данных, является количество обращений к внешней памяти при запросе объектов на точное сопоставление всех ключевых полей. Это связано с тем, что за последние десятилетия быстродействие процессоров выросло в сотни раз. В то же время производительность устройств хранения увеличилась не так значительно. Поэтому программы, которые раньше в основном зависели от быстродействия CPU, теперь больше зависят от устройств хранения данных. Такая разница в производительности делает подсистему ввода/вывода узким местом во многих программах, мощности CPU остаются неиспользованными. Поэтому вопрос количества обращений к внешней памяти в процессе выполнения типовых задач является очень важным при оценке быстродействия структуры в целом. Улучшенная организация хранения файлов способствует сокращению числа обращений к устройству хранения, а также снижает время выполнения операции доступа. Например, использование индексированного файла сокращает число запросов к подсистеме ввода/вывода, необходимых для получения некоторого количества данных, сужая область поиска со всего файла до его небольшого участка.

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

Для хеширования PLOP все не так однозначно. В данной схеме нет массива решетки, а номер внешнего блока определяется с помощью специальной адресной функции. Это позволяет избавиться от одного обращения к внешней памяти. Схема поиска также состоит из трех шагов. На первом шаге с помощью иерархических шкал (деревьев деления по осям пространства) определяются индексы решетки. Как и в файлах-решетках, шкалы расположены в оперативной памяти и не требуют обращений к внешней памяти. Таким образом, первый шаг у обеих структур практически идентичен, за исключением только формы представления шкал в памяти (сортированный массив или бинарное дерево). На втором шаге полученные индексы подставляются в адресную функцию, которая возвращает номер внешнего блока. Данный шаг также не требует обращений к внешней памяти. И только на третьем шаге нужный блок загружается в оперативную память, из него извлекаются записи поиска. Однако из-за отказа от массива решетки и необходимости поддерживать заданный коэффициент наполнения в хешировании PLOP коллизии и переполнение блоков приводят к появлению цепочек. Поэтому при поиске на последнем шаге, возможно, придется загружать не один внешний блок, а целую цепочку подобных блоков. Хотя первые два шага и не требуют обращений к внешней памяти, последний шаг может привести к нескольким таким обращениям.

Для оценки количества обращений была смоделирована ситуация равномерного распределения записей в пространстве. Количество записей в файле варьировалось от 1 000 до 100 000. Каждая операция и тест проверялись несколько раз, и данные этих проверок усреднялись.

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

В тестировании участвовало несколько последовательностей записей. Самыми показательными оказались следующие варианты: случайная вставка; вставка записей, отсортированных по одному из ключей; вставка записей с одновременным возрастанием всех ключей. Файл-решетка работает одинаково со всеми тремя типами последовательностей, т.е. данная структура не зависит от последовательности подаваемых на индексирование данных, что является несомненным плюсом.

Размещено на http://www.allbest.ru/

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

В статье представлена только серия опытов со случайными последовательностями равномерно распределенных данных, так как этот вариант является наиболее часто встречающимся на практике.

Хеширование PLOP показало среднее количество обращений от 1,5 до 1,85 (рис. 3). При небольшом наполнении файла число обращений к внешней памяти близко к 1,5, что значительно превосходит аналогичный показатель файлов-решеток. Но с ростом объема данных (особенно если данные подаются в отсортированном виде) этот показатель падает, что связано с появлением длинных цепочек внешних блоков в файле. Однако при равномерном распределении PLOP-хеширование по этому показателю дало лучшие результаты во всех экспериментах.

Коэффициент заполнения. Еще одним важным показателем структуры является коэффициент заполнения, который рассчитывается по следующей формуле:

где N - количество проиндексированных записей; Size - размер одной записи; V - общий размер структуры.

Данный показатель является мерой эффективности использования внешней памяти структурой. Чем он ближе к 100%, тем более бережно расходуется память.

Размещено на http://www.allbest.ru/

На рис. 4 показаны вычисленные зависимости коэффициента заполнения от количества записей в файле. Коэффициент заполнения в хешировании PLOP падает с ростом числа записей, тогда как у файла-решётки он практически не изменяется. Это объясняется тем, что в PLOP-хешировании каждой ячейке пространства данных соответствует не менее одного внешнего блока (даже если в ней нет ни одной записи). Данный эффект усугубляется с ростом количества индексированных записей. При малом объеме данных количество пустых или полупустых блоков не сильно влияет на общую картину. Однако с ростом размера решетки каждое деление ячеек приводит к появлению подобных блоков.

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

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

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

Выбирать порог расщепления нужно с большой осторожностью. Чем больше будет выбранная величина, тем более длинные цепочки будут образовываться при коллизиях и переполнениях. Это негативно скажется на количестве обращений к внешней памяти, что приведет к снижению производительности. Так, выбор коэффициента заполнения 95-100% приведет к тому, что средняя длина цепочек в файле будет намного больше 2, а следовательно, производительность файла-решетки на тех же данных окажется выше. По результатам экспериментирования предлагается использовать пороговое значение коэффициента в пределах 70%.

Список литературы

Nievergelt, L. The Grid File: an Adaptable, Symmetric Multi-Key File Structure / L. Nievergelt, H. Hinterberger, K.D. Sevcik // ACM Transactions on Database Systems. - 1984. -Vol. 9. - №1. - P. 38-71.

Kriegel, H.-P. PLOP-Hashing: A Grid File without Directory / H.-P. Kriegel, B. Seeger // Praktsche Informatik. - University of Bremen, 1988.

Gaede, V. Multidimensional Access Methods / V. Gaede, O. Gunther // ACM Computing Surveys. - 1998. -Vol. 30. - №2.

Размещено на Allbest.ru