Министерство образования российской федерации московский государственный институт электроники и математики (Технический университет)
 Скачать 1.02 Mb.
|
|
коллизией. Наличие коллизий снижает эффективность хеширования. Разрешение коллизий достигается путём рехеширования – специального алгоритма, который используется при размещении новой записи или при поис- ке существующей. В системах баз данных рехеширование выполняется одним из следующих способов: 1. Открытая адресация: новая запись размещается вслед за последней запи- сью на данной странице или на следующей, если страница заполнена. (Для последней страницы памяти следующей является первая страница). Поиск записи осуществляется также последовательно, откуда следует, что записи нельзя удалять физически (с освобождением памяти), иначе цепочка рехе- шированных записей прервётся, и часть записей может быть "потеряна". – 56 – 2. Использование коллизионных страниц: новая запись размещается на одной из коллизионных страниц, относящихся к таблице (в области переполнения). Для ускорения поиска рехешированных записей может использоваться свя- занная область переполнения, для которой на странице хранится ссылка на коллизионную страницу. Нулевое значение такой ссылки говорит об отсут- ствии коллизий для данных, размещённых на этой странице. 3. Многократное хеширование. Заключается в том, что при возникновении коллизии для поиска другого адреса (возможно, на коллизионных страни- цах) применяется другая функция хеширования. Примечание: существуют и более сложные стратегии рехеширования; но их рассмотрение выходит за рамки данного пособия. 6.3.2. Использование хеширования Хеширование таблицы полезно в следующих случаях: Большинство запросов обращаются по значению уникального ключа, на- пример: SELECT … WHERE unique_key = …; Значение, указанное в предикате, хешируется; по этому хеш-значению про- исходит прямой доступ к соответствующему блоку данных (обычно, одно физическое чтение). В случае обыкновенной индексированной таблицы про- исходит сначала обращение к индексу (несколько физических операций чте- ния), затем уже считывается сама строка. Таблица практически статична (редко обновляется) Число строк и требуемое физическое пространство можно определить заранее и зафиксировать. Если впоследствии таблица вырастет и придётся отводить ей дополнительные блоки, это может сильно ухудшить производительность. Хеширование не рекомендуется в следующих случаях: Нельзя заранее выделить столько пространства памяти, сколько потребуется таблице в будущем. Большинство запросов выбирают строки в некотором интервале. Хеширова- ние не даёт здесь преимуществ, т.к. строки не упорядочены (в отличие от индекса). Таблица быстро меняется и постоянно растёт. Эффективность использования хеширования не в последней степени оп- ределяется качеством хеш-функции. Системы, поддерживающие возможность хеширования данных, обычно имеют встроенную хеш-функцию, но и позволя- ют пользователю задавать свою. Это может понадобиться тогда, когда встроен- ная хеш-функция не даёт хороших результатов, а пользовательская может учесть особенности распределения значений конкретного ключа. Если же ключ является уникальным и распределение его значений равномерно, то сами зна- чения могут быть использованы в качестве хеш-значений. – 57 – 6.4. Кластеризация данных 6.4.1. Принцип организации кластеров Кластеризация является методом совместного хранения родственных данных (таблиц). Кластер – это структура памяти, в которой хранится набор таблиц (в одних и тех же блоках памяти). Эти таблицы должны иметь общие столбцы, используемые для соединения (например, первичный ключ таблицы ТОВАРЫ и внешний ключ таблицы ПОСТАВКИ, рис. 6.6,б). 20 Zoom А4 1002 Комус 1003 Партия 2070 Комус 3000 Комус 1002 Комус 20 1100 Партия 10 1003 Партия 20 3000 Комус 20 2070 Комус 20 2080 Комус 10 1200 Партия 10 20 Zoom A4 10 Восход А4 б) а) 1100 Партия 2080 Комус 1200 Партия 10 Восход А4 Рис. 6.6. Некластеризованные (а) и кластеризованные (б) данные Кластерный ключ – это столбец или набор столбцов (полей записи), общих для всех кластеризуемых таблиц. Каждая таблица, созданная в кластере, должна иметь столбцы, соответствующие типам и размерам столбцов кластер- ного ключа. Количество столбцов в кластерном ключе ограничено (например, для Oracle8 это ограничение равно 16). Совместное хранение означает, что на одной странице или в одном блоке памяти хранятся данные из всех кластеризованных таблиц, имеющие одинако- вое значение кластерного ключа. Физически это обычно реализуется так: в на- чале страницы (блока) хранится запись из таблицы, для которой кластерный ключ является первичным (или уникальным), а вслед за ней располагаются за- писи из другой таблицы (таблиц), имеющие те же значения кластерного ключа. Фактически, данные хранятся в виде соединения таблиц по значениям кластер- ного ключа. В этом случае выигрыш по времени для выполнения соединения таблиц по сравнению с раздельно хранимыми таблицами составляет 3-6 раз. Если все данные, относящиеся к одному значению кластерного ключа, не помещаются в одном блоке, то выделяется новый блок памяти и предыдущий блок хранит ссылку на него. Но если система позволяет изменять размер блока (в частности, СУБД Oracle), при создании кластера желательно установить раз- мер блока, исходя из оценки среднего количества записей с одинаковыми зна- чения кластерного ключа. Значения кластерного ключа таблицы могут обновляться, но, так как рас- положение записи зависит от этого значения, обновление может вызвать физи- – 58 – ческое перемещение записи. Поэтому часто обновляющиеся атрибуты не явля- ются хорошими кандидатами на вхождение в кластерный ключ. Два основных преимущества кластеров: Уменьшается обмен с диском, улучшается время доступа к кластеризован- ным таблицам и их соединение. Значение кластерного ключа хранится только один раз для кластера, за счёт чего достигается экономия памяти. С другой стороны, наличие кластеров обычно увеличивает время выпол- нения операции добавления записи (INSERT), т.к. требует от системы дополни- тельных временных затрат на просмотр блоков данных для поиска того блока, куда нужно поместить новую запись. (Наличие кластеров прозрачно для поль- зователей и приложений.) 6.4.2. Использование кластеров Кластеры обычно строятся для таблиц, часто используемых в соединении друг с другом, например, связанных отношением "один-ко-многим". Не стоит создавать кластер: если данные в кластерном ключе этих таблиц часто обновляются; если часто требуется полный просмотр отдельной таблицы. если суммарные данные таблиц с одним и тем же значением кластерного ключа занимают больше одного блока данных. Изменение столбцов кластера требует гораздо больше системных ресур- сов, чем обновление некластеризованных данных, так что выигрыш от ускоре- ния поиска данных оказывается меньше, чем затраты на физическое перемеще- ние строк. Полный просмотр индивидуальных таблиц кластера требует больше вре- мени, чем просмотр некластеризованных таблиц, т.к. физически требуется об- ратиться к большему числу блоков. Если по отдельности некластеризованные таблицы занимают n1 и n2 блока соответственно, то вместе они будут занимать (n1+n2) блоков, и для полного просмотра каждой из них придётся обращаться к диску (n1+n2) раз. Часто для окончательного определения целесообразности создания кла- стера в конкретной ситуации ставят эксперименты и измеряют производитель- ность БД. 7. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНОГО ДОСТУПА К ДАННЫМ Параллельный (многопользовательский) доступ к данным подразумевает одновременное выполнение двух и более запросов к одним и тем же объектам данных (таблицам, блокам и т.п.). Для организации одновременного доступа не обязательно наличие многопроцессорной системы. На однопроцессорной ЭВМ запросы выполняются не одновременно, а параллельно. Обычно для каждого запроса выделяется некоторое количество процессорного времени (квант вре- мени), по истечении которого выполнение запроса приостанавливается, он ста- вится в очередь запросов, а на выполнение запускается следующий (по очере- – 59 – ди) запрос. Таким образом, процессорное время делится между запросами, и создаётся иллюзия, что запросы выполняются одновременно. При параллельном доступе к данным проблемы возникают в том случае, если доступ подразумевает внесение изменений. Для того чтобы исключить на- рушения логической целостности данных при многопользовательском доступе, используется механизм транзакций. 7.1. Механизм транзакций Транзакция – это последовательность операторов обработки данных, кото- рая рассматривается как логически неделимая единица работы с базой дан- ных. Транзакция обладает следующими свойствами: 1. Логическая неделимость (атомарность) означает, что выполняются либо все операции, входящие в транзакцию, либо ни одной. (Логическая неделимость не подразумевает физической неделимости). Система гарантирует невозможность фиксации части изменений, произве- дённых транзакцией. До тех пор, пока транзакция не зафиксирована, её можно "откатить", т.е. отменить все сделанные операторами из транзакции изменения в БД. Успешное выполнение транзакции означает, что все опера- торы транзакции проанализированы, интерпретированы как правильные и безошибочно исполнены. 2. Согласованность: транзакция начинается на согласованном множестве дан- ных и после её завершения множество данных также согласовано. 3. Изолированность, т.е. отсутствие влияния транзакций друг на друга. (На самом деле это влияние существует и регламентируется стандартом: см. раз- дел 7.2. "Взаимовлияние транзакций"). 4. Продолжительность: результаты зафиксированной транзакции не могут быть потеряны. Возврат БД в предыдущее состояние может быть достигнут только путём запуска компенсирующей транзакции. Для управления транзакциями в системах, поддерживающих механизм транзакций и язык SQL, используются следующие операторы: – фиксация транзакции: COMMIT [WORK]; – откат транзакции: ROLLBACK [WORK]; – точка сохранения: SAVEPOINT <имя_точки_сохранения>; (Ключевое слово WORK необязательно). Предложение SAVEPOINT запомина- ет промежуточную "текущую копию" состояния базы данных для того, чтобы впоследствии, при необходимости, можно было вернуться к состоянию БД в точке сохранения: откатить работу от текущего момента до точки сохранения (rollback to <имя_точки>) или зафиксировать работу от начала транзакции до точки сохранения (commit to <имя_точки>). Начало транзакции соответствует появлению первого исполняемого SQL- оператора. Транзакция завершается при наступлении одного из следующих со- бытий: – 60 – Поступила команда COMMIT или ROLLBACK (результаты транзакции со- ответственно зафиксируются или откатываются). Выдана и успешно проанализирована одна из команд языка описания дан- ных (DDL, Data Definition Language), таких как CREATE, DROP или ALTER. При этом фиксируется предыдущая транзакция. Завершилась команда DDL. Таким образом, транзакция, содержащая опера- тор языка описания данных фиксируется автоматически. Пользователь завершил сеанс работы с системой (последняя транзакция фиксируется автоматически). Процесс пользователя аварийно завершен (последняя транзакция автомати- чески откатывается). Фиксация транзакции заключается в следующем: 1. Изменения, внесённые транзакцией, делаются постоянными. 2. Уничтожаются все точки сохранения для данной транзакции. 3. Завершается транзакция (уничтожаются системные записи о транзакции в оперативной памяти). 4. Если выполнение транзакций осуществляется с помощью блокировок, то ос- вобождаются объекты, заблокированные транзакцией. Для организации отката СУБД во время выполнения транзакции произво- дит запись в сегменты отката всех внесённых изменений. Все изменения вы- полняются в оперативной памяти (ОП), затем фиксируются в журнале транзак- ций и периодически (при выполнении контрольной точки) переписываются на диск. Процесс формирования контрольной точки заключается в синхрониза- ции данных, находящихся на диске (т.е. во вторичной памяти) с теми данными, которые находятся в ОП: все модифицированные данные из ОП переписывают- ся во вторичную память. 7.2. Взаимовлияние транзакций Транзакции в многопользовательской БД должны быть изолированы друг от друга, т.е. в идеале каждая из них должна выполняться так, как будто выпол- няется только она одна. В реальности транзакции выполняются одновременно и могут влиять на результаты друг друга. Взаимовлияние транзакций может проявляться в виде: потери изменений; чернового чтения; неповторяемого чтения; фантомов. Потеря изменений может происходить при одновременном обновлении двумя и более транзакциями одного и того же набора данных. Транзакция, за- кончившаяся последней, перезапишет результаты изменений, внесённых пре- дыдущими транзакциями, и они будут потеряны. Например, почти одновременно начали выполняться две транзакции: транзакция 1 – UPDATE СОТРУДНИКИ SET Оклад = 9200 WHERE Номер = 1123 – 61 – транзакция 2 – UPDATE СОТРУДНИКИ SET Должность = " старший экономист ", ЕТС = 14 WHERE Номер = 1123 Обе транзакции считали одну и ту же запись (1123, "Рудин В.П.", "экономист", 12, 8300) и внесли каждая свои изменения: в бухгалтерии изменили оклад (транзакция 1), в отделе кадров – должность и ставку по ЕТС (транзакция 2). Результаты транзакции 1 будут потеряны (рис. 7.1). Отношение "Сотрудники" Номер ФИО Должность ЕТС Оклад 1123 Рудин В.П. экономист 13 8300 Транзакция 1 Транзакция 2 1123 Рудин В.П. экономист 13 9200 1123 Рудин В.П. старший экономист 14 8300 Рис. 7.1. Взаимовлияние транзакций: потеря изменений СУБД не допускает такого взаимовлияния транзакций, при котором воз- можна потеря изменений. Ситуация чернового чтения возникает, когда транзакция считывает из- менения, вносимые другой (незавершенной) транзакцией. Если эта вторая тран- закция не будет зафиксирована, то данные, полученные в результате чернового чтения, будут некорректными. Транзакции, осуществляющие черновое чтение, могут использоваться только при невысоких требованиях к согласованности данных: например, если транзакция считает статистические показатели, когда отклонения отдельных значений данных слабо влияют на результат. При повторяемом чтении один и тот же запрос, повторно выполняемый одной транзакцией, возвращает один и тот же набор данных (т.е. игнорирует изменения, вносимые другими завершёнными и незавершёнными транзакция- ми). Неповторяемое чтение является противоположностью повторяемого, т.е. транзакция "видит" изменения, внесённые другими (завершёнными!) транзак- циями. Следствием этого может быть несогласованность результатов запроса, когда часть данных запроса соответствует состоянию БД до внесения измене- ний, а часть – состоянию БД после внесения и фиксации изменений. Фантомы – это особый тип неповторяемого чтения. Возникновение фан- томов может происходить в ситуации, когда одна и та же транзакция сначала производит обновление набора данных, а затем считывание этого же набора. Если считывание данных начинается раньше, чем закончится их обновление, то в результате чтения можно получить несогласованный (не обновлённый или частично обновлённый) набор данных. 7.3. Уровни изоляции транзакций Стандарт ANSI/ISO для SQL устанавливает различные уровни изоляции для операций, выполняемых над базами данных, которые работают в много- пользовательском режиме. Уровень изоляции определяет, может ли транзак- – 62 – ция считывать результаты работы других одновременно выполняемых завер- шённых и/или незавершённых транзакций (табл. 7.1). Использование этих уровней изоляции обеспечивает предсказуемость работы приложений. Уровень изоляции позволяет транзакциям в большей или меньшей степе- ни влиять друг на друга: при повышении уровня изоляции повышается согласо- ванность данных, но снижается степень параллельности работы и, следователь- но, производительность системы. Таблица 7.1. Уровни изоляции по стандарту ANSI / ISO Уровень изоляции Черновое чтение Неповторяемое чтение Фантомы Read Uncommited – чтение незавер- шённых транзакций да да да Read Commited – чтение завершённых транзакций нет да да Repeatable Read – повторяемое чтение нет нет да Serializable – последовательное чтение нет нет нет По умолчанию обычно используется уровень Read Commited. Наиболее распространённый механизм разграничения транзакций – ис- пользование блокировок. 7.4. Блокировки Блокировка – это временное ограничение доступа к данным, участвующим в транзакции, со стороны других транзакций. Различают следующие типы блокировок: по степени доступности данных: разделяемые и исключающие; по множеству блокируемых данных: строчные, страничные, табличные; по способу установки: автоматические и явные. Строчные, страничные и табличные блокировки накладываются соот- ветственно на строку таблицы, страницу (блок) памяти и на всю таблицу цели- ком. Табличная блокировка приводит к неоправданным задержкам исполнения запросов и сводит на нет параллельность работы. Другие виды блокировки уве- личивают параллелизм работы, но требуют накладных расходов на поддержа- ние блокировок. Разделяемая блокировка, установленная на определённый ресурс, пре- доставляет транзакциям право коллективного доступа к этому ресурсу. Обычно этот вид блокировок используется для того, чтобы запретить другим транзак- циям производить необратимые изменения. Например, если на таблицу цели- ком наложена разделяемая блокировка, то ни одна транзакция не сможет уда- лить эту таблицу или изменить её структуру до тех пор, пока эта блокировка не будет снята. (При выполнении запросов на чтение обычно накладывается раз- деляемая блокировка на таблицу.) Исключающая блокировка предоставляет право на монопольный дос- туп к ресурсу. Такие блокировки накладываются, обычно, на отдельные записи – 63 – (блоки), которые подвергаются модификации в процессе выполнения транзак- ции. Но в том случае, если модификация затрагивает большую часть записей таблицы (более 1000 записей или более 20% от объёма таблицы), целесообраз- нее заблокировать всё отношение, а не тратить время на построчную блокиров- ку таблицы, при которой увеличивается количество требуемых системных ре- сурсов и время выполнения. Кроме того, при большом количестве построчных блокировок транзакция может не завершиться (из-за истечения тайм-аута, на- пример), и тогда все сделанные изменения придётся откатить, что снизит про- изводительность системы. Блокировка может быть |