?

Log in

No account? Create an account

Сб, 2 июн, 2012, 02:17
История SQL. 7. System R, Phase One (RSS)

Начало: 1. Необходимая предыстория, назад: История SQL. 6. System R, Phase Zero.

На следующей фазе проекта, названной Фазой 1 (условно с 1976 по 1977 год), код протопита был выброшен в соответствии с заветами Брукса и полнофункциональную систему переделали с нуля, уже лучше понимая, что нужно:

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

Интересно посмотреть на возможности, реализованные в System R и проследить их судьбу в современной базе данных — в моем случае, в Оракле. Сначала посмотрим на низкоуровневый компонент доступа к данным RSS — Research Storage System.

Организация данных. Вся информация, с которой имеет дело System R, содержится в страницах размером в несколько килобайт (аналог в Оракле — блок). Страницы, в свою очередь, располагаются в сегментах (по сути, во внешних файлах). В основной массе сегментов хранятся, конечно, строки таблиц.

На этапе Фазы 0 в XRM отдельно хранились значения атрибутов и отдельно — объединяющие их ссылки. За счет этого экономилось место (можно ставить много ссылок на единожды записанное значение), но для считывания всей строки могло потребоваться много обращений к диску. Приоритеты оптимизации пересмотрели: стало понятно, что вместо подсчета строк надо считать ввод-вывод. Поэтому в новом механизме RSS большое внимание было уделено кластеризации. Строки стали хранить целиком, чтобы считывать их полностью за одно обращение к диску. Более того, один сегмент мог быть выделен сразу под несколько таблиц — это позволило еще больше увеличить кластеризацию, если таблицы часто использовались совместно.

Были предусмотрены и другие типы сегментов, например, сегмент журнала, временные сегменты.

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

Чтение данных по любому пути доступа осуществлялось с помощью команды RSS open_scan и последовательного вызова next для получения данных строка за строкой. Дополнительно могло указываться выражение (называемое search argument или SARG), которому должны были удовлетворять прочитанные данные. У разработчиков System R даже родилось прилагательное, приводившее непосвященных в замешательство: sargable predicate, то есть предикат SEQUEL, который может напрямую использоваться RSS. В Оракле sargable predicates называются предикатами доступа (access), а те условия, которые в System R проверялись уже на уровне RDS, называются предикатами фильтрации (filter). Но аналогия эта не вполне корректная, поскольку исторически в Оракле не было четко разделенных компонент, аналогичных RSS и RDS.

Точечные обращения к данным организованы в System R на основе уникальных идентификаторов строк TID (tuple id; в Оракле это rowid), составленных из указания сегмента, страницы и смещения внутри страницы. С помощью TID над строками таблиц строились вспомогательные структуры данных (например, индексы). Отсюда следует, что TID должен быть неизменным, а это приводит к проблеме миграции строк: если при изменении данных строка перестает помещаться в своей странице, то ее приходится переносить в другую и для сохранения TID устраивать косвенную адресацию. Ровно то же видим и в Оракле.

RSS поддерживал несколько различных структур, позволяющих адресно обращаться к строкам. Во-первых, это индексы, построенные — впервые в базах данных — на основе B-деревьев. Индексы хранились в виде многостраничной иерархической структуры в том же сегменте, что и таблица, и автоматически поддерживались RSS в актуальном состоянии. Сбалансированность и небольшая глубина оказались очень удобными и сейчас такие индексы являются стандартом для СУБД (в Оракле индексы на B-деревьях появились только в 1988 году в шестой версии).

Во-вторых, RSS предоставлял ссылки (links), связывающие строки, принадлежащие одной или разным таблицам. С помощью ссылок можно было связать «родительскую» строку с «дочерними» строками другой таблицы. При этом актуальность и упорядоченность ссылок нужно было поддерживать явно с помощью операций connect и disconnect. Сканирование данных по ссылкам позволяло перебирать дочерние строки или переходить от дочерней строки к ее родителю.

Пытливый ум немедленно узнает в ссылках наследие навигационных СУБД в духе CODASYL. Что они делают в реляционной базе данных? Дело в том, что у авторов RSS была идея построить универсальный механизм, на котором можно было бы реализовать любую СУБД, хоть реляционную, хоть сетевую. По воспоминаниям Франко Путцолу, он потратил массу времени, отображая все конструкции СУБД IMS в команды RSS. Идея, по-видимому, была обусловлена тем, что в то время активно развивался гигантский — в духе IBM — проект FS (Future System), частью которого была поддержка всевозможных типов баз данных. FS со временем рухнул под тяжестью собственной сложности; этот проект считается самым дорогим провалом в истории IBM. А ссылки в итоге убрали и из System R.

Транзакции в System R были реализованы в полной мере даже по сегодняшним меркам. RSS начинал транзакцию по команде start_transaction и либо фиксировал изменения по end_transaction, либо откатывал их по restore_transaction. Откатывались как изменения в данных и установленные блокировки, так и (в отличие от Оракла) операции создания новых таблиц или индексов. Интересно, что в статьях того времени термин commit употребляется редко, а вместо rollback используется backout или просто undo.

Откат мог происходить не только к началу транзакции, но и к установленной с помощью save_transaction точке сохранения. Внутренне точки сохранения использовались, чтобы обеспечить атомарность команд SQL, отображаемых на множество команд RSS. Но в SEQUEL точек сохранения не было, поэтому извне эта возможность была недоступна.

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

Журнал был организован как циклический буфер (на диске). Старые данные, не относящиеся к активным транзакциям, переносились в архивные журналы (на ленту) — в этом плане журнал Оракла организован точно также. Замечу, что именно в System R впервые применили журнализацию на жесткий диск. До этого журналы писали сразу на магнитную ленту; конечно, при этом журнал невозможно использовать для отката транзакций.

Многопользовательский режим и поддержка согласованности данных в System R обеспечивались блокировками, что само по себе вполне очевидно. Интересный вопрос состоял в том, на каком уровне их устанавливать. В проекте был период, когда казалось, что лучший вариант — это идея Раймонда Лори о блокировке предикатов. Например, если транзакция изменяет данные, то имеется предикат, описывающий диапазон изменений, который и логично было бы заблокировать. Сложности с этим подходом возникают, когда надо определить, конфликтуют ли блокировки, то есть пересекаются ли диапазоны, определенные двумя предикатами. В общем случае это вообще алгоритмически неразрешимая задача; в итоге разработчики не решились даже на реализацию для предикатов простого вида. Вместо этого было решено блокировать такие объекты, как строки, таблицы, страницы, сегменты.

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

При блокировках неизбежно приходится искать компромисс между изолированностью транзакций друг от друга и масштабируемостью системы. Поддерживались три уровня изоляции:

  1. Транзакция видит незафиксированные изменения других транзакции. В этом режиме блокируются только изменяемые данные, а при чтении блокировки не нужны. В Оракле такого режима нет в принципе.
  2. Транзакция видит только зафиксированные изменения, но последовательные чтения могут вернуть разные данные. Здесь при чтении ставится блокировка на время выполнения запроса. В Оракле аналогом является стандартный режим read committed, но за счет механизма мультиверсионности он обходится без блокировок (если верить Кайту, он появился в 1983 году в третьей версии).
  3. Транзакция видит только зафиксированные изменения и в пределах транзакции чтения дают одинаковый результат. Для этого при чтении ставится блокировка на время всей транзакции. В Оракле аналогом является режим serialized.
По опыту разработчиков, в реальной работе в основном использовался третий уровень.

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

Восстановление после сбоев использовало механизм теневых страниц. Для каждого сегмента поддерживалось два списка принадлежащих ему страниц — текущий и теневой. В начале работы оба списка совпадали. При изменении какой-либо страницы сегмента новые данные записывались в физически другую страницу, которая включалась в текущий список; теневой список оставался без изменений. Периодически специальная программа-монитор инициировала контрольную точку (check point, аналог видим и в Оракле), при достижении которой по на диск сбрасывались все страницы из кэша, теневой список приравнивался текущему, а ненужные более теневые страницы освобождались. Выбор частоты контрольных точек — это баланс между дополнительной нагрузкой и скоростью восстановления; типичное время — раз в несколько минут.

Таким образом, при «мягком» сбое (отказ оперативной памяти) достаточно откатиться к последней контрольной точке (приравнять текущий список теневому и освободить ненужные страницы) и позаботиться о согласованности данных с помощью журнала (повторить завершенные с момента контрольной точки транзакции и откатить незавершенные). Журнал записывался как минимум в конце транзакции и обязательно перед записью самих данных (для надежности обычно на два диска). Собственно, признаком зафиксированной транзакции считается запись об этом в журнале. Аналогичный write ahead log использует и Оракл. При «жестких» сбоях (отказ диска) информация и журнал восстановливаются из бэкапа (инкрементального, с магнитной ленты), после чего выполняется обычная процедура «мягкого» восстановления.

Пытливый ум может заметить, что Оракл, используя ту же технику восстановления, основанную на журнале, обходится без механизма теневых страниц. К этому же выводу пришли в конце концов и авторы System R. Теневые страницы появились в качестве «исторического наследия» XRM. Они, безусловно, ускоряют процедуру восстановления, но дорогой ценой: необходимо поддерживать два длинных списка страниц для каждого сегмента, а это и дополнительный ввод-вывод, и время процессора. В итоге при больших объемах данных недостатки начинают перевешивать достоинства. Но когда это стало понятно, менять механизм было уже слишком поздно.

Любопытно взглянуть на абсолютные цифры, относящиеся к восстановлению. Типичными для инсталляций System R на 1981 год являются такие показатели:

  • общая производительность — транзакция в секунду;
  • откат транзакции — несколько раз в минуту (занимает миллисекунды);
  • мягкий сбой — несколько раз в месяц (восстановление занимает около минуты);
  • жесткий сбой — раз-два в год (около часа).

Продолжение: 8. System R, Phase One (RDS).

Почитать и посмотреть: