Проектирование системы хранения POSTGRES

Мы продолжаем праздновать 30-летие PostgreSQL и публикуем перевод второй фундаментальной статьи о СУБД. Перевод первого манифеста можно прочесть в этом посте.

Аннотация

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

1. Введение

Менеджер хранения POSTGRES — это набор модулей, обеспечивающих управление транзакциями и доступ к объектам базы данных. Проектирование этих модулей определялось тремя целями, которые мы рассмотрим ниже. Первая цель заключалась в том, чтобы обеспечить управление транзакциями без необходимости писать большой объём кода восстановления после сбоев. Такой код трудно отлаживать, трудно писать, и он не должен содержать ошибок. Если на важном клиенте менеджера данных случится сбой, эта новость, скорее всего, окажется на первых полосах, потому что клиент не сможет получить доступ к своей базе данных, а его бизнес понесет ущерб. Чтобы достичь первой цели, POSTGRES использует новую систему хранения, в которой данные никогда не перезаписываются, вместо этого все обновления превращаются во вставки.

Вторая цель менеджера хранения — размещать историческое состояние базы данных на оптическом диске write-once-read-many (WORM) или другом архивном носителе в дополнение к текущему состоянию на обычном магнитном диске. Поэтому мы спроектировали асинхронный процесс, который назвали очистителем (vacuum cleaner), который переносит архивные записи с магнитного диска в архивную систему хранения.

Третья цель системы хранения — использовать преимущества специализированного аппаратного обеспечения. В частности, мы предполагаем наличие энергонезависимой основной памяти в разумном объёме. Такая память может быть обеспечена с помощью методов коррекции ошибок и схемы резервного питания от батареи либо другими аппаратными средствами. Кроме того, мы ожидаем, что будут доступны несколько низкоуровневых машинных инструкций для специализированных задач, которые объясним ниже. Мы предполагаем, что архитектуры с несколькими процессорами будут становиться всё более популярными. В такой среде появится возможность применять несколько процессоров для работы СУБД, тогда как сейчас используется только один. Для этого СУБД POSTGRES должна перейти от распространённых сегодня монолитных архитектур с одним потоком управления к архитектуре, где множество асинхронных процессов одновременно выполняют функции СУБД. К процессорам такого типа относится Sequent Balance System [SEQU85], FIREFLY и SPUR [HILL85].

Статья организована следующим образом. В следующем разделе мы представляем проект системы хранения на магнитных дисках. В разделе 3 описываем структуру и концепции архивной системы. В разделе 4 высказываем некоторые соображения об эффективных индексах для архивного хранения. Наконец, в разделе 5 представляем сравнение производительности нашей системы с обычной системой хранения, использующей журнал упреждающей записи (WAL) [GRAY78].

2. Система магнитных дисков

2.1. Система транзакций

Дисковые записи изменяются транзакциями базы данных, каждой из которых присваивается уникальный идентификатор транзакции (XID). XID’ы — это 40-битные беззнаковые целые числа, последовательно назначаемые начиная с 1. При 100 транзакциях в секунду (TPS) POSTGRES располагает достаточным количеством XID примерно на 320 лет работы. Кроме того, оставшиеся 8 бит составного 48-битного идентификатора взаимодействия (IID) являются идентификатором команды (CID) для каждой команды внутри транзакции. Следовательно, транзакция ограничена выполнением не более чем 256 команд.

Кроме того, существует журнал транзакций, содержащий 2 бита на транзакцию, которые описывают её состояние как:

• committed (зафиксирована);

• aborted (прервана);

• in progress (выполняется).

Транзакция начинается с того, что увеличивается счётчик, содержащий первый неназначенный XID и его текущее значение используется как XID. Кодирование журнала задаёт для транзакции значение по умолчанию "in progress", поэтому в начале транзакции не требуется вносить в журнал специальное изменение. Транзакция фиксируется путём изменения её состояния в журнале с "in progress" на "committed" и помещения соответствующего дискового блока журнала в стабильное хранилище. Более того, все страницы данных, изменённые от имени транзакции, также должны быть помещены в стабильное хранилище. Эти страницы можно либо принудительно записать на диск, либо переместить в стабильную основную память, если она доступна. Аналогично транзакция прерывается путём изменения её состояния с "in progress" на "aborted".

Хвост журнала — это часть журнала от самой старой активной транзакции до текущего момента. Тело журнала — это оставшаяся часть журнала; транзакции в этой части не могут находиться в состоянии "in progress", поэтому для них требуется выделять только 1 бит. Тело журнала занимает отношение POSTGRES, для которого был построен специальный метод доступа. Этот метод доступа размещает статус 65536 транзакций в каждом 8K дисковом блоке POSTGRES. При одной транзакции в секунду тело увеличивается со скоростью 4 Мбайт в год. Поэтому для лёгких приложений журнал за всю историю операций не будет большим объектом и может поместиться в буферный пул большого размера. В обычных условиях для этой цели будет использоваться несколько мегабайтов памяти, и статус всех исторических транзакций можно будет быстро найти без чтения с диска.

В более тяжёлых приложениях, где тело журнала не помещается в основной памяти, POSTGRES применяет необязательную технику сжатия. Поскольку большинство транзакций фиксируется, тело журнала почти полностью состоит из битов commit. Поэтому в POSTGRES предусмотрен необязательный фильтр Блума [SEVR76] для прерванных транзакций. Эта тактика уменьшает буферное пространство, необходимое для журнала, примерно в 10 раз. Следовательно, фильтр Блума для тяжёлых приложений должен помещаться в основной памяти. И здесь системе времени выполнения не требуется читать дисковый блок, чтобы определить статус транзакции. Детали устройства фильтра Блума представлены в [STON86].

Хвост журнала — это небольшая структура данных. Если самая старая транзакция началась сутки назад, то при скорости обработки 1 транзакция в секунду в хвосте журнала будет около 86 400 транзакций. При 2 битах на запись хвост требует 21 600 байт на транзакцию в секунду. Следовательно, разумно разместить хвост журнала в стабильной основной памяти: это избавит страницы, содержащие хвост журнала, от многократной принудительной записи на диск за короткое время, когда фиксируются транзакции с близкими идентификаторами.

2.2. Хранение отношений

При создании отношения для хранения его записей выделяется файл. Для таких записей не задана максимальная длина, поэтому менеджер хранения готов обрабатывать записи, которые пересекают границы дисковых блоков. Для этого он выделяет записи-продолжения и связывает их между собой связным списком. Кроме того, порядок записи дисковых блоков для очень длинных записей должен тщательно контролироваться. Детали этой поддержки многоблочных записей достаточно просты, поэтому далее в статье мы их не рассматриваем. Изначально POSTGRES использует обычные файлы, предоставляемые ОС UNIX; однако мы можем пересмотреть это решение, когда вся система будет работоспособной. Если место в файле исчерпано, POSTGRES расширяет файл на величину, кратную размеру страницы 8 КБ.

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

cluster rel-name on {(field-name using operator)}

POSTGRES будет пытаться поддерживать записи приблизительно в порядке сортировки по указанным именам полей, используя заданные операторы для определения линейного порядка. Это позволит создавать кластеризующие вторичные индексы как в [ASTR76].

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

• OID — уникальный идентификатор записи, назначаемый системой;

• Xmin — идентификатор транзакции, вставившей запись;

• Tmin — время фиксации Xmin, то есть момент, когда запись стала действительной;

• Cmin — идентификатор команды в транзакции, вставившей запись;

• Xmax — идентификатор транзакции, удалившей запись;

• Tmax — время фиксации Xmax, то есть момент, когда запись перестала быть действительной;

• Cmax — идентификатор команды в транзакции, удалившей запись;

• PTR — прямой указатель.

При вставке записи ей назначается уникальный OID, а Xmin и Cmin устанавливаются в идентификатор текущего взаимодействия. Остальные пять полей остаются пустыми. Когда запись обновляется, выполняются две операции. Сначала Xmax и Cmax в заменяемой записи устанавливаются в идентификатор текущего взаимодействия, чтобы показать, что запись больше не действительна. Затем в базу данных вставляется новая запись с предлагаемыми заменяющими значениями для полей данных. Кроме того, OID устанавливается равным OID заменяемой записи, а Xmin и Cmin устанавливаются в идентификатор текущего взаимодействия. Когда запись удаляется, Xmax и Cmax в удаляемой записи устанавливаются в идентификатор текущего взаимодействия.

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

Будем надеяться, что большинство дельта-записей находится на той же странице операционной системы, что и опорная точка, поскольку обычно это небольшие объекты. Предполагается, что POSTGRES будет использоваться как локальный менеджер данных в распределённой системе баз данных. Ожидается, что такая распределённая система будет поддерживать несколько копий всех важных объектов POSTGRES. Восстановление после серьёзных сбоев, то есть таких, при которых диск нельзя прочитать, будет происходить путём переключения на другую копию объекта. В нераспределённой системе POSTGRES позволит пользователю указать, что он хочет иметь вторую копию конкретных объектов, с помощью команды mirror rel-name.

Некоторые операционные системы (например, VMS [DEC86] и Tandem [BART81]) уже поддерживают зеркалированные файлы, поэтому специальный код СУБД в этих средах не потребуется. Будем надеяться, что в будущем зеркалированные файлы станут стандартной службой операционных систем в большинстве сред.

2.3. Управление временем

Язык запросов POSTGRES, POSTQUEL, позволяет пользователю запросить, например, зарплату Майка с помощью следующего синтаксиса:

retrieve (EMP.salary) where EMP.name = "Mike"

Для поддержки доступа к историческим кортежам язык запросов расширяется следующим образом:

retrieve (EMP.salary) using EMP[T] where EMP.name = "Mike"

Область действия этой команды — отношение EMP на конкретный момент времени T — и зарплата Майка будут найдены именно на этот момент. Для T будут разрешены различные форматы, а для преобразования времени в 32-битные беззнаковые целые числа, используемые внутри системы, будет вызываться процедура преобразования. POSTGRES обычным образом строит план запроса для поиска подходящих записей. Однако каждый кортеж, к которому обращается запрос, нужно дополнительно проверить, был ли он действителен в нужный пользователю момент времени. В общем случае запись действительна в момент T, если выполняется следующее условие:

Tmin < T и Xmin — зафиксированная транзакция, и выполняется одно из условий:

• Xmax — незафиксированная транзакция

• Xmax равно null

• Tmax > T.

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

Xmin = my-transaction и Cmin != my-command and T = "now"

или

Tmin < T и Xmin — зафиксированная транзакция, и выполняется одно из условий:

• (Xmax — незафиксированная транзакция и Xmax != my-transaction)

• (Xmax = my-transaction и Cmax = my-command) 

• Xmax равен null

• Tmax > T

Если T не указано, то по умолчанию принимается T = "now", и запись действительна в момент "now", если выполняется условие:

Xmin = my-transaction и Cmin != my-command

или

Xmin — зафиксированная транзакция, и выполняется одно из условий:

• (Xmax — незафиксированная транзакция и Xmax != my-transaction)

• (Xmax = my-transaction и Cmax = my-command)

• Xmax равен null

В более общем виде историю зарплаты Майка за диапазон времени можно получить так:

retrieve (EMP.Tmin, EMP.Tmax, EMP.salary)
using EMP[T1,T2] where EMP.name = "Mike"

Эта команда найдёт все зарплаты Майка вместе с их начальными и конечными моментами времени, если соответствующая зарплата действительна в какой-либо момент интервала [T1, T2]. В общем случае запись действительна в интервале [T1,T2], если:

Xmin = my-transaction и Cmin != my-command and T2 >= "now"

или

Tmin < T2 и Xmin — зафиксированная транзакция, и выполняется одно из условий:

• (Xmax — незафиксированная транзакция и Xmax != my-transaction)

• (Xmax = my-transaction и Cmax = my-command)

• Xmax равен null

• Tmax > T1

Можно опустить либо T1, либо T2; значения по умолчанию соответственно T1 = 0 и T2 = +infinity.

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

retrieve (EMP.salary) using all-EMP[T] where EMP.name = "Mike"

Запись EMP находится в all-EMP в момент T, если Tmin < T и (Tmax > T или Tmax = null)

Интуитивно all-EMP[T] — это множество всех кортежей, зафиксированных, отменённых или находящихся в процессе выполнения в момент T.

Для каждой записи на магнитном диске, к которой выполняется доступ, должна быть применена одна из приведённых выше проверок. Хотя каждая проверка потенциально требует значительных затрат ресурсов процессора (CPU) и ввода-вывода (I/O), ресурсы CPU нас не слишком беспокоят: мы не ожидаем, что в системах следующего поколения именно CPU будет серьёзным узким местом (этот вопрос подробнее обсудим в разделе 5). Кроме того, CPU-часть этих проверок можно легко перенести в специализированную логику, микрокод или даже сопроцессор, если она станет узким местом.

Доступ к статусу любой транзакции будет почти или совсем не связан с I/O, поскольку мы ожидаем, что журнал транзакций (или связанный с ним фильтр Блума) будет находиться в основной памяти. В следующем подразделе мы рассмотрим, как избежать операций I/O при вычислении остальных частей этих предикатов.

2.4. Управление конкурентным доступом и временными метками

Было бы естественно назначать транзакции временную метку в момент её запуска, а затем заполнять поле временной метки каждой записи по мере того, как транзакция её обновляет. К сожалению, это потребовало бы от POSTGRES логической обработки транзакций в порядке временных меток, чтобы избежать аномального поведения. Фактически это означало бы, что POSTGRES должен использовать механизм управления параллельным доступом, основанный на упорядочении транзакций по временным меткам, например предложенный в [BERN80]. Поскольку результаты моделирования показали преимущество классического механизма блокировок [AGRA85], в POSTGRES вместо этого используется стандартный протокол двухфазной блокировки, реализованный с помощью традиционной таблицы блокировок, размещённой в оперативной памяти.

Следовательно, Tmin и Tmax должны быть установлены равными времени фиксации каждой транзакции (то есть моменту, когда обновления логически вступают в силу), чтобы избежать аномального поведения. Так как момент фиксации транзакции неизвестен заранее, значения Tmin и Tmax не могут быть установлены в тот момент, когда запись создаётся.

Мы используем следующий приём, чтобы заполнять эти поля асинхронно. В POSTGRES есть отношение TIME, в котором хранится время фиксации каждой транзакции. Поскольку временные метки являются 32-битными беззнаковыми целыми числами, байтовые позиции с 4j по 4j + 3 зарезервированы для времени фиксации транзакции j. В момент фиксации транзакции считывается текущее значение системных часов, которое затем сохраняется в соответствующей ячейке TIME. Хвостовую часть отношения TIME можно хранить в энергонезависимой памяти, чтобы избежать операций ввода-вывода, которые в противном случае потребовались бы для выполнения этого обновления.

Кроме того, каждое отношение в базе данных POSTGRES при создании помечается одним из трех обозначений: 

• no archive — исторический доступ к отношениям не требуется; 

• light archive — архив желателен, но доступ к нему ожидается нечастый; 

• heavy archive — архив будет интенсивно использоваться.

Для отношений со статусом "no archive" Tmin и Tmax никогда не заполняются, поскольку доступ к историческим кортежам никогда не требуется. Для таких отношений могут обрабатываться только команды POSTQUEL, заданные для T = "now". При проверке корректности для T = "now" требуется доступ только к отношению POSTGRES LOG, которое должно находиться в буферном пуле. Поэтому такая проверка не требует операций ввода-вывода.

Если указан "light archive", то доступ к историческим кортежам разрешён. Всякий раз, когда Tmin или Tmax нужно сравнить с некоторым конкретным значением, время фиксации соответствующей транзакции извлекается из отношения TIME, чтобы выполнить сравнение. В ситуации "light archive" доступ к историческим записям будет замедлен из-за необходимости выполнять ввод-вывод к отношению TIME для каждого требуемого значения временной метки. Эти накладные расходы будут приемлемы только в том случае, если к архивным записям за время их жизни обращаются очень редко (примерно 2–3 раза).

В режиме "heavy archive" система времени выполнения должна найти время фиксации транзакции так же, как в случае "light archive". Однако затем найденное значение записывается в поле Tmin или Tmax, тем самым превращая чтение исторической записи в её модификацию. Любые последующие обращения к этой записи затем можно будет проверять без дополнительного доступа к отношению TIME. Поэтому первый доступ к архивной записи в случае "heavy archive" будет дорогим, но последующие обращения не будут привносить дополнительных накладных расходов.

Кроме того, мы рассчитываем исследовать полезность запуска еще одного системного демона в фоновом режиме для асинхронного заполнения временных меток у отношений "heavy archive".

2.5. Доступ к записям

К записям можно обращаться с помощью последовательного сканирования отношения. В этом случае страницы соответствующего файла читаются в порядке, определяемом POSTGRES. Каждая страница содержит указатель на следующую и предыдущую логические страницы; поэтому POSTGRES может сканировать отношение, следуя по прямому связному списку. Обратные указатели требуются потому, что POSTGRES может выполнять планы запросов как в прямом, так и в обратном направлении. Кроме того, каждая страница содержит таблицу строк, аналогичную описанной в [STON76], в которой хранятся указатели на начальный байт каждой опорной записи, расположенной на этой странице.

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

Для любого базового отношения может быть создано произвольное число вторичных индексов. Каждый индекс поддерживается соответствующим методом доступа и обеспечивает доступ по ключу к одному полю или совокупности полей. Каждый метод доступа должен реализовывать полный набор процедур, предусмотренных абстракцией методов доступа, определённой в POSTGRES. К таким процедурам относятся, в частности, получение записи по ключу (get-record-by-key), вставка записи (insert-record), удаление записи (delete-record) и другие. Во время выполнения запросов среда исполнения POSTGRES при необходимости вызывает процедуры выбранного метода доступа.

Каждый метод доступа поддерживает эффективный доступ для набора операторов, как отмечено в [STON86a]. Например, B-trees могут обеспечивать быстрый доступ для любого из операторов:

{=, <=, <, >, >=}

Поскольку каждому методу доступа может потребоваться работа с различными типами данных, набор операторов, который он должен использовать для конкретного типа данных, необходимо зарегистрировать в виде класса операторов (operator class). Следовательно, синтаксис создания индекса таков:

index on rel-name is index-name ({key-i with operator-class-i})
using access-method-name and performance-parameters

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

index on EMP is EMP-INDEX (age with integer-ops, salary with float-ops)
using B-tree and fill-factor = .8

Во время выполнения запросов POSTGRES работает со вторичными индексами несколько необычным образом. При вставке записи для неё создаётся опорная запись, а также записи во всех вторичных индексах. Каждая запись индекса содержит ключ (или составной ключ) и указатель на запись в таблице строк страницы, на которой находится индексируемая запись. Эта запись таблицы строк, в свою очередь, указывает на смещение в байтах до начала самой записи. Такой единственный уровень косвенной адресации позволяет перемещать опорные записи внутри страницы данных без необходимости обновлять вторичные индексы.

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

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

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

Некоторые вторичные индексы, имеющие иерархическую структуру, требуют записи страниц на стабильный носитель в строго определённом порядке (например, от листьев к корню при расщеплении страниц в B+-деревьях). Для поддержки таких требований в POSTGRES предусмотрена низкоуровневая команда order block-1 block-2, задающая необходимый порядок записи блоков. Эта команда используется в дополнение к обязательным командам pin и unpin, предоставляемым менеджером буферов.

3. Архивная система

3.1. Очистка диска

Асинхронный демон отвечает за перемещение в архив записей, которые больше не являются действительными. Этот демон, называемый очистителем (vacuum cleaner), получает инструкции с помощью следующей команды vacuum rel-name after T. Здесь T — время, заданное относительно текущего ("now"). Например, следующая команда vacuum задаёт очистку записей старше 30 дней: vacuum EMP after "30 days".

Очиститель находит записи-кандидаты для архивации, которые удовлетворяют одному из следующих условий:

• Xmax непустое и содержит идентификатор зафиксированной транзакции и "now" - Tmax >= T;

• Xmax не пусто и содержит идентификатор прерванной транзакции;

• Xmin не пусто и содержит идентификатор прерванной транзакции.

Во втором и третьем случаях очиститель просто освобождает пространство, занятое такими записями. В первом случае запись должна быть скопирована в архив, если для этого отношения не установлен статус "no archive". Кроме того, если задан режим "heavy archive", очиститель во время архивации должен заполнить Tmin и Tmax, если эти значения ещё не были установлены при предыдущем обращении к записи. Более того, если опорную запись и несколько дельта-записей можно обработать одновременно, процесс очистки будет эффективнее. Поэтому очиститель обычно переносит в архив сразу цепочку из нескольких записей.

Такое перемещение должно выполняться очень осторожно, чтобы данные не были безвозвратно потеряны. Сначала мы рассмотрим формат архивного носителя, а затем перейдём к алгоритму очистки и обсуждению его стоимости.

3.2. Архивный носитель

Архивная подсистема хранения совместима с устройствами класса WORM (Write Once, Read Many — «однократная запись, многократное чтение»), однако не ограничивается только такими устройствами. Для архива используется обычная файловая система, основанная на экстентах (extent-based file system), при этом каждому отношению выделяется отдельный файл. Пространство выделяется крупными экстентами, а следующий экстент выделяется после исчерпания предыдущего. Карта распределения пространства архива хранится в отношении на магнитном диске. Поэтому последовательный просмотр исторической части отношения возможен, хотя и требует очень больших затрат.

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

index on {archive} rel-name is index-name ({key-i with operator-class-i})
using access-method-name and performance-parameters

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

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

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

3.3. Процесс очистки

Очистка выполняется в три этапа:

• Этап 1: запись архивной записи и соответствующих ей записей индексов.

• Этап 2: запись новой опорной записи в текущую базу данных.

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

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

После того как запись надежно сохранена в архиве и для неё созданы все необходимые индексные записи, начинается второй этап очистки. На этом этапе формируется новая опорная запись для отношения, расположенного на магнитном диске, и создаются новые записи во всех соответствующих индексах. Новая опорная запись определяется следующим образом: начиная со старой опорной записи, система последовательно проходит по цепочке дельта-записей и вычисляет значение последней дельта-записи, удовлетворяющей условию "now" - Tmax >= T.

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

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

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

Теперь перейдём к оценке стоимости работы процесса очистки.

3.4. Стоимость процесса очистки

Рассмотрим два различных сценария очистки. В первом случае предполагается, что запись вставляется, затем обновляется K раз, после чего удаляется. После этого вся цепочка версий записи — от первоначальной вставки до удаления — очищается за один проход. Во втором случае предполагается, что процесс очистки запускается после K обновлений, вследствие чего требуется создать новую опорную запись. В обоих случаях предполагается, что для архивного отношения и отношения, расположенного на магнитном диске, существует по Z вторичных индексов; в ходе этих K обновлений значения индексируемых ключей не изменяются; опорная запись и все связанные с ней дельта-записи располагаются на одной странице. В таблице 1 приведены затраты на выполнение очистки для каждого из этих случаев. Обратите внимание, что стоимость очистки остаётся постоянной. Этот на первый взгляд неожиданный результат объясняется тем, что новую опорную запись можно разместить на той же странице, с которой удаляется старая опорная запись, без сохранения промежуточного состояния страницы на стабильный носитель. Аналогично новые записи индексов могут быть добавлены на ту же страницу, с которой удаляются прежние записи индекса, также без промежуточной операции ввода-вывода. Следовательно, затраты процесса очистки в расчёте на одну запись уменьшаются по мере увеличения длины цепочки, K. Если опорная запись и несколько связанных с ней дельта-записей очищаются одновременно, накладные расходы оказываются незначительными.

Таблица 1. Число операций ввода-вывода при очистке

	Вся цепочка	K обновлений
записи в архив	(1 + Z)	(1 + Z)
чтения с диска	1	1
записи на диск	(1 + Z)	(1 + Z)

4. Индексирование архива

4.1. Индексы на магнитном диске

Архив может индексироваться с помощью обычных индексов, размещённых на магнитном диске. Например, для архива можно построить индекс по полю salary, который будет полезен при выполнении запросов вида:

retrieve (EMP.name) using EMP [,] where EMP.salary = 10000

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

retrieve (EMP.name) using EMP [1/1/87,] where EMP.salary = 10000

обычный индекс по полю salary окажется малоэффективным, поскольку он вернёт все исторические значения зарплаты, равные 10000, тогда как запросу требуется лишь небольшое их подмножество. Поэтому, помимо обычных индексов, мы ожидаем, что для архивных отношений особенно полезными окажутся индексы, ориентированные на время. С этой целью поля Tmin и Tmax в архиве объединяются в одно поле I типа интервал (interval). Для индексирования этого поля можно использовать метод доступа R-дерево (R-tree)[GUTM84]. Операторы, для которых R-дерево обеспечивает эффективный поиск, включают overlaps («пересекается с») и contained-in («содержится в»). Поэтому после определения этих операторов для типа данных interval индекс для отношения EMP можно создать следующим образом:

index on archive EMP is EMP-INDEX (I with interval-ops)
using R-tree and fill-factor = .8

Такой индекс обеспечивает быстрый доступ к историческому состоянию отношения EMP как на конкретный момент времени, так и за некоторый интервал времени.

Для использования подобных индексов планировщик запросов POSTGRES необходимо лишь слегка модифицировать. Заметим, что POSTGRES обращается к архивному отношению только тогда, когда область действия запроса включает исторические данные. Поэтому обращение к архивному отношению имеет одну из следующих форм: ...using EMP[T] или ...using EMP[T1,T2]. Планировщик преобразует первую конструкцию в ...where T contained-in EMP.I, а вторую — в ...where interval(T1,T2) overlaps EMP.I.

Поскольку все записи архива гарантированно являются действительными, эти условия могут заменить весь низкоуровневый код проверки корректности записей на магнитном диске, описанный в разделе 2.3.

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

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

index on archive EMP is EMP-INDEX
(I with interval-ops, salary with float-ops)
using R-tree and fill-factor = .8

Поскольку R-дерево представляет собой многомерный индекс, такой индекс описывает интервалы в двумерном пространстве, образованном временем и значением заработной платы. Например, запрос:

retrieve (EMP.name) using EMP[T1,T2] where EMP.salary = 10000

будет преобразован в

retrieve (EMP.name) where EMP.salary = 10000
and interval(T1,T2) overlaps EMP.I

Оба условия отбора совместно определяют интервал в двумерном пространстве, поэтому стандартные алгоритмы поиска R-дерева могут эффективно использовать их одновременно.

Хотя записи попадают в архив тогда, когда это сочтёт необходимым процесс очистки, в общем случае они будут добавляться в порядке возрастания времени. Поэтому низкая производительность R-деревьев, описанная в работе [ROUS85], вероятно, не проявится благодаря почти упорядоченному порядку вставки записей. Для проверки этого предположения планируется провести специальные эксперименты.

Теперь перейдём к рассмотрению R-деревьев, часть которых располагается на магнитном диске, а часть — на архивном носителе.

4.2. Индексы, распределённые между двумя носителями

Покажем, зачем нужны индексы, распределённые между двумя носителями, на небольшой оценке требуемого объёма памяти. Предположим, существует отношение, содержащее 10⁶ кортежей, причём каждый кортеж за время существования приложения изменяется 30 раз. Предположим также, что как для архивного отношения, так и для отношения на магнитном диске существует по два вторичных индекса, а обновления никогда не изменяют значения индексируемых полей. Кроме того, будем считать, что очистка выполняется после записи пятой дельта-записи, так что на каждую опорную запись в среднем приходится три дельта-записи. Предположим также, что размер опорной записи составляет 200 байт, размер дельта-записи — 40 байт, а длина ключа индекса — 10 байт.

Размеры каждого типа объектов в байтах с учётом этих предположений приведены в таблице 2. Очевидно, что 10⁶ записей займут 200 Мбайт, тогда как 3×10⁶ дельта-записей потребуют 120 Мбайт. Предполагается, что каждая индексная запись помимо 10-байтового ключа содержит 4-байтовый указатель; следовательно, каждый из двух индексов займёт 14 Мбайт. Для каждой из 10⁶ записей в архиве хранится 6 записей опорных точек, причём каждая из них конкатенируется с 4 дельта-записями. Поэтому архивные записи будут иметь длину 360 байт и в сумме потребуют 2160 Мбайт. Наконец, для каждой архивной опорной точки существует индексная запись; следовательно, архивные индексы в 6 раз больше индексов на магнитном диске.

Таблица 2. Размеры различных объектов

Объект	Мбайт
Отношение на магнитном диске
опорные точки	200
дельта-записи	120
вторичные индексы	28
Архив	2160
архивные индексы	168

Из таблицы 2 следуют два важных вывода. Во-первых, архив может достигать весьма больших размеров. Поэтому очистку целесообразно выполнять как можно реже, чтобы уменьшить число опорных записей, попадающих в архив. Кроме того, для экономии места может оказаться полезным дифференциальное кодирование опорных записей. Во-вторых, архивные индексы занимают значительный объем пространства на магнитном диске. Если бы рассматриваемое отношение имело три индекса вместо двух, архивные индексы занимали бы больше места, чем само отношение, расположенное на магнитном диске. Поэтому в этом разделе рассматриваются структуры данных, позволяющие перенести часть индекса на архивный носитель. Хотя можно было бы использовать индексные структуры, полностью размещённые в архиве, подобные предложенным в [VITT85], мы полагаем, что структуры, распределённые между двумя носителями, будут работать значительно эффективнее. Для проверки этой гипотезы планируется провести сравнительные испытания.

Рассмотрим структуру хранения на основе R-дерева, в которой каждый указатель во внутреннем, то есть нелистовом, узле R-дерева помечается как указатель либо на страницу магнитного диска, либо на страницу архива. Если указатели имеют размер 32 бита, то для этой цели можно использовать старший бит, оставляя остальные 31 бит для адресации 2³¹ страниц на магнитном диске или в архивном хранилище. Если размер страницы составляет 8 Кбайт, то максимальный размер архивного индекса равен 2⁴⁴ байт, то есть примерно 1,75×10¹³ байт, чего явно достаточно почти для любого приложения. Кроме того, страницы листового уровня R-дерева содержат значения ключей и указатели на соответствующие записи данных. Эти указатели на данные могут иметь длину 48 бит, что позволяет файлу данных, соответствующему одному историческому отношению, иметь размер до 2⁴⁸ байт, то есть примерно 3,0×10¹⁴ байт; этого также достаточно для большинства приложений.

Предполагается, что архив представляет собой устройство класса WORM (write-once-read-many), позволяющее записывать страницы только один раз без последующей перезаписи. При таком предположении динамически добавлять записи можно только на страницы, расположенные на магнитном диске. В таблице 3 предложены две разумные стратегии размещения новых записей в случаях, когда они не полностью помещаются в некоторую область R-дерева, соответствующую странице магнитного диска.

Таблица 3. Стратегии вставки записей

Стратегия	Описание
P1	поместить в область, которую потребуется расширить меньше всего
P2	поместить в область, у которой максимальное время потребуется расширить меньше всего

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

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

Теперь рассмотрим несколько стратегий переноса страниц с магнитного диска в архив. В дальнейшем будем использовать параметры, приведённые в таблице 4. Самая простая стратегия заключается в том, чтобы создать системный демон, который будет выполнять «очистку» индекса, перенося в архив ту листовую страницу, для которой значение Tmax (то есть левая граница соответствующего временного интервала) минимально. Такая очистка выполняется всякий раз, когда размер R-дерева достигает некоторого порогового значения, близкого к максимальному числу страниц магнитного диска F. Другая стратегия заключается в выборе страницы для архивации с учётом не только значения Tmax, но и степени заполнения страницы. В обоих случаях новые записи будут вставляться в R-дерево в нижней левой части, тогда как демон будет архивировать страницы в его нижней правой части. Когда все потомки некоторого внутреннего узла R-дерева уже находятся в архиве, этот узел также может быть перенесён в архив.

Таблица 4. Параметры, определяющие перемещение страниц

Параметр	Описание
F	число блоков магнитного диска, доступных для индекса
U	частота обновления индексируемого отношения
L	размер записи в создаваемом индексе
B	размер блока страниц магнитного диска

Например, если размер страницы B равен 8192 байт, размер индексной записи L — 50 байт, архив хранит изменения за пять лет, а частота обновлений U составляет одно обновление в секунду, то потребуется 1,4 × 10⁶ индексных страниц, что приведёт к построению четырёхуровневого R-дерева. Из них F страниц будут находиться на магнитном диске, а остальные — в архиве. Любая операция вставки или поиска потребует не менее четырёх обращений к тому или иному носителю.

Третья стратегия, обладающая несколько иными характеристиками производительности, основана на пакетном переносе (batch movement). В этом случае сначала на магнитном диске строится R-дерево, пока его размер не достигнет F страниц. Затем все страницы этого дерева, кроме корневой, копируются в архив, а для корневой страницы на магнитном диске создаётся специальный «верхний узел» (top node). После этого начинается построение второго R-дерева размером F−1 страниц. Пока строится второе дерево, при выполнении любого поискового запроса просматриваются как новое дерево, так и дерево, уже находящееся в архиве. Все операции вставки, разумеется, выполняются только в R-дереве на магнитном диске. Когда второе дерево достигает предельного размера, оно архивируется тем же способом, а его корневой узел добавляется к существующему верхнему узлу. Это может привести к переполнению верхнего узла, после чего выполняется обычное расщепление узла R-дерева. В результате верхний узел превращается в обычное R-дерево, состоящее уже из трёх узлов. После этого начинается заполнение третьего R-дерева размером F−3 страниц. Когда оно будет полностью сформировано, его также перенесут в архив, а его корневой узел будет добавлен в крайнюю левую страницу двухузлового R-дерева.

Со временем продолжат существовать два R-дерева. Первое дерево полностью располагается на магнитном диске и периодически архивируется. Если к моменту архивации его высота остаётся постоянной и равна H, то второе дерево высотой H1 будет иметь нижние H−1 уровней, расположенных в архиве. Кроме того, вставка новых записей в магнитодисковую часть второго дерева всегда происходит в крайнюю левую страницу. Поэтому изменяются только страницы вдоль левого края дерева, а остальные можно переносить в архив, если они содержат ссылки исключительно на архивные страницы. Таким образом, лишь часть страниц верхних H1 − H + 1 уровней остаётся на магнитном диске. Все операции вставки выполняются только в первом R-дереве, тогда как поиск производится одновременно в обоих деревьях. Разумеется, операции удаления при этом отсутствуют.

Снова рассмотрим пример. Если B = 8192 байт, L = 50 байт и F = 6000 страниц, то высота H будет равна 3, а каждая операция вставки потребует трёх обращений к магнитному диску. Кроме того, при частоте одно обновление в секунду пятилетний архив потребует четырёхуровневого R-дерева, у которого два нижних уровня будут находиться в архиве, а часть двух верхних уровней (от 100-й до 161-й страницы) останется на магнитном диске. Следовательно, поиск будет выполняться одновременно по двум R-деревьям общей глубиной 7 уровней и окажется примерно на 40 % медленнее, чем в любой из двух ранее предложенных схем с одним R-деревом. Зато наиболее распространённая операция — вставка новых записей — будет выполняться примерно на 25 % быстрее.

5. Сравнение производительности

5.1. Предположения

Чтобы сравнить нашу систему хранения с традиционной системой, основанной на журналировании с упреждающей записью (WAL), мы принимаем следующие предположения.

1. Части буферного пула могут размещаться в энергонезависимой основной памяти.

2. Команды процессора не являются критически важным ресурсом, поэтому учитываются только операции ввода-вывода.

Второе предположение требует некоторого пояснения. Современные процессорные технологии снижают стоимость одного MIP примерно вдвое каждые пару лет. Поэтому современные рабочие станции нижнего ценового диапазона обладают вычислительной мощностью в несколько MIP. С другой стороны, диски становятся более плотными и дешёвыми. Однако их скорость существенно не растёт. Поэтому от стандартного дискового накопителя по-прежнему можно ожидать чтения лишь порядка 30 блоков в секунду. Современные реализации систем баз данных требуют нескольких тысяч инструкций, чтобы извлечь страницу с диска, а затем ещё 1000–3000 инструкций на каждую запись данных, просматриваемую на этой странице. В качестве простой оценки эффективности предположим, что для обработки одного дискового блока требуется 30 000 инструкций. Следовательно, процессор производительностью 1 MIP приблизительно уравновешивает один диск. Сейчас доступны рабочие станции с производительностью 3–5 MIP, однако маловероятно, что они будут сконфигурированы с 3–5 дисками. Более того, будущие рабочие станции, такие как SPUR и FIREFLY, будут иметь производительность 10–30 MIP. Очевидно, что они не будут иметь 10–30 дисков, если только дисковые системы не перейдут от нынешних SMD-дисков к большому числу однопластинных дисков с интерфейсом SCSI.

Иными словами, SUN 3/280 стоит около 5000 долларов за MIP, тогда как SMD-диск с контроллером стоит около 12 000 долларов. Следовательно, стоимость процессорных ресурсов, необходимых для поддержки одного диска, значительно меньше стоимости самого диска, и можно ожидать, что основные затраты на аппаратное обеспечение баз данных будут приходиться на дисковую систему. Поэтому, если окажется, что установка ограничена производительностью процессора, дополнительные процессорные ресурсы можно будет недорого добавлять до тех пор, пока система не станет сбалансированной.

Мы анализируем три возможные ситуации:

• large-SM: доступен большой объем энергонезависимой основной памяти;

• small-SM: доступен умеренный объем энергонезависимой основной памяти;

• no-SM: энергонезависимая основная память отсутствует.

В первом случае мы предполагаем, что и POSTGRES, и система на основе WAL располагают достаточным объёмом энергонезависимой основной памяти, так что ни одна из систем не обязана принудительно записывать дисковые страницы во вторичное хранилище в момент их обновления. Поэтому каждая система выполнит некоторое число операций ввода-вывода, которые могут быть буферизованы в энергонезависимой памяти и записаны на диск в удобный момент. Мы подсчитываем число таких непринудительных операций ввода-вывода, выполняемых каждой системой, предполагая, что все операции записи имеют одинаковую стоимость. Для обеих систем мы предполагаем, что записи не пересекают границы страниц, так что каждое обновление приводит к записи одной страницы. Кроме того, мы предполагаем, что каждая дельта-запись POSTGRES может быть размещена на той же странице, что и её опорная запись. Далее мы предполагаем, что транзакции представляют собой вставку одной записи, обновление одной записи, удаление одной записи или прерванное обновление. Кроме того, мы предполагаем, что у затрагиваемого отношения есть два вторичных индекса и что обновления не изменяют ни одно из ключевых полей. Наконец, мы предполагаем, что журнал с упреждающей записью потребует три журнальные записи: начало транзакции, модификацию данных и завершение транзакции; их суммарная длина составляет 400 байт. При этом операции со вторичными индексами не журналируются, поэтому журнальные записи для 10 транзакций помещаются на обычную журнальную страницу размером 4 Кбайт.

Во второй ситуации мы предполагаем, что доступен умеренный объем энергонезависимой основной памяти. Мы считаем, что этого объёма достаточно только для хранения хвоста журнала POSTGRES и хвоста отношения TIME. В системе на основе WAL мы предполагаем, что энергонезависимая память может буферизовать обычный журнал, превращая каждую запись в журнал в такую запись, которую не нужно синхронно принудительно сбрасывать на диск. Эту ситуацию (small-SM) следует сопоставить с третьим случаем, когда энергонезависимая память полностью отсутствует (no-SM). В последнем случае оба типа систем хранения должны принудительно записывать некоторые данные на диск.

В последующих результатах мы игнорируем затраты, которые любая из систем понесла бы на зеркалирование данных для обеспечения высокой доступности. Кроме того, мы также игнорируем затраты WAL, связанные с контрольными точками. Помимо этого, мы предполагаем, что системе WAL никогда не требуется чтение с диска для доступа к соответствующей журнальной записи отмены. Мы также игнорируем затраты на очистку диска в архитектуре POSTGRES.

5.2. Результаты производительности

В таблице 5 показано число операций ввода-вывода, которое должен выполнить каждый из четырёх типов транзакций для предполагаемой конфигурации large-SM. Поскольку имеется большой объём энергонезависимой основной памяти, ни одна из систем не обязана принудительно записывать страницы данных на диск, и выполняться должны только непринудительные операции ввода-вывода. Вставка требует, чтобы любая из систем записывала одну запись данных и две индексные записи. Кроме того, в традиционной системе при этом будет заполнена одна десятая журнальной страницы, так что на каждые 10 транзакций будет приходиться ещё одна журнальная страница, которую в конечном счёте нужно будет записать на диск. В POSTGRES вставки в отношение LOG и отношение TIME порождают одну операцию ввода-вывода на каждые 65 536 и 2048 транзакций соответственно, и в таблице 5 мы этим малым числом пренебрегаем. Поэтому в POSTGRES требуется 3 непринудительные операции ввода-вывода, а в традиционной системе — 3,1. Следующие два столбца в таблице 5 могут быть вычислены аналогичным образом. Последний столбец суммирует операции ввода-вывода для прерванной транзакции. В POSTGRES обновлённую страницу не нужно повторно записывать на диск. Следовательно, строго говоря, операции ввода-вывода не обязательны; однако, скорее всего, такая оптимизация не будет реализована. Система WAL обновит данные и сформирует журнальную запись. Затем журнальную запись нужно будет прочитать, а страницу данных вернуть к исходному значению. И снова очень хитроумная система могла бы избежать записи страницы на диск, поскольку она идентична дисковой копии. Поэтому для обеих систем мы указываем как оптимизированное число записей, так и неоптимизированное. Обратите внимание, что в таблице 5 POSTGRES лишь незначительно лучше системы WAL, за исключением удалений, где он оказывается существенно лучше, поскольку не удаляет две индексные записи.

Таблица 5. Количество операций ввода-вывода для базовых операций в конфигурации large-SM

	Insert	Update	Delete	Abort
WAL-force	0	0	0	0
WAL-no-force	3.1	1.1	3.1	0.1 или 1.1
POSTGRES-force	0	0	0	0
POSTGRES-non-force	3	1	1	0 или 1

Теперь перейдём к случаям, в которых POSTGRES выглядит менее привлекательно.

Таблица 6 повторяет подсчёт операций ввода-вывода для конфигурации small-SM. Конфигурация WAL ведёт себя точно так же, как в таблице 5, тогда как страницы данных POSTGRES теперь должны принудительно записываться на диск, поскольку предполагается, что энергонезависимой основной памяти недостаточно для их хранения. Обратите внимание, что POSTGRES всё ещё лучше по общему числу операций ввода-вывода; однако требование выполнять их синхронно будет серьёзным недостатком.

Таблица 6. Количество операций ввода-вывода для базовых операций в конфигурации small-SM

	Insert	Update	Delete	Abort
WAL-force	0	0	0	0
WAL-no-force	3.1	1.1	3.1	0.1 или 1.1
POSTGRES-force	3	1	1	0 или 1
POSTGRES-non-force	0	0	0	0

Затем таблица 7 показывает число операций ввода-вывода, при условии что энергонезависимая основная память полностью отсутствует. В этом случае журнальная запись традиционной системы WAL должна быть принудительно записана на диск во время фиксации транзакции. Остальные записи могут оставаться в буферном пуле и быть записаны позднее. В POSTGRES бит LOG должен быть принудительно записан на диск вместе со вставкой в отношение TIME. Кроме того, страницы данных должны принудительно записываться, как в таблице 6. В этом случае POSTGRES оказывается немного хуже по общему числу операций; и снова синхронный характер этих обновлений будет существенным недостатком.

Таблица 7. Количество операций ввода-вывода для базовых операций в конфигурации no-SM

	Insert	Update	Delete	Abort
WAL-force	1	1	1	1
WAL-no-force	3	1	3	0 или 1
POSTGRES-force	5	3	3	1
POSTGRES-non-force	0	0	0	0 или 1

В итоге решение POSTGRES предпочтительно в конфигурации large-SM, поскольку все операции требуют меньшего числа операций ввода-вывода. В таблице 6 общее число операций ввода-вывода для POSTGRES меньше, однако требуется синхронный ввод-вывод. Таблица 7 показывает ситуацию, в которой POSTGRES обычно оказывается более дорогим. Однако групповые фиксации транзакций [DEWI84] могли бы эффективно преобразовать результаты для систем обоих типов в результаты, приведённые в таблице 6. Следовательно, POSTGRES следует считать вполне конкурентоспособным по отношению к современным архитектурам хранения. Более того, он имеет значительное преимущество перед системами WAL: время восстановления будет мгновенным, тогда как в архитектуре WAL восстановление потребует существенного времени.

6. Выводы

В этой статье был описан менеджер хранения, создаваемый для POSTGRES. Основные положения, определяющие проектирование системы:

1. мгновенное восстановление после сбоев;

2. возможность хранить архивные записи на архивном носителе;

3. служебные задачи должны выполняться асинхронно;

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

Первый пункт следует противопоставить стандартным менеджерам хранения с журналированием с упреждающей записью (WAL), которые сегодня широко используются. 

В инженерных приложениях часто требуется прошлая история базы данных. Более того, даже в бизнес-приложениях эта возможность иногда необходима, а теперь уже знаменитый тест TP1 предполагает, что приложение будет поддерживать архив. Для приложений, которым нужна такая услуга, более разумно, чтобы менеджер данных выполнял эту задачу внутри системы.

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

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

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

В настоящее время менеджер хранения для магнитного диска уже работает, продолжается работа над очистителем и организацией архива. POSTGRES спроектирован так, чтобы поддерживать расширяемые методы доступа; мы уже реализовали код B-дерева и в ближайшем будущем предоставим R-деревья. Дополнительные методы доступа могут быть созданы сторонними разработчиками для удовлетворения их специальных потребностей. Когда оставшиеся части менеджера хранения будут завершены, мы планируем провести сравнительное испытание производительности — как с традиционными менеджерами хранения, так и с другими менеджерами хранения, обладающими интересными свойствами, например [CARE86, COPE84].

Литература

1. [AGRA85] Agrawal, R. et. al., ‘‘Models for Studying Concurrency Control Perfor- mance Alternatives and Implications,’’ Proc. 1985 ACM-SIGMOD Conference on Management of Data, Austin, Tx., May 1985.

2. [ASTR76] Astrahan, M. et. al., ‘‘System R: A Relational Approach to Data,’’ ACM-TODS, June 1976.

3. [BART81] Bartlett, J., ‘‘A Non-STOP Kernel,’’ Proc. Eighth Symposium on Operating System Principles,’’ Pacific Grove, Ca., Dec. 1981.

4. [BERN80] Bernstein, P. at. al., ‘‘Concurrency Control in a System for Distributed Databases (SDD-1),’’ ACM-TODS, March 1980.

5. [BHID87] Bhide, A., ‘‘Query Processing in Shared Memory Multiprocessor Sys- tems,’’ (in preparation).

6. [CARE86] Carey, M. et. al., "Object and File Management in the EXODUS Data- base System,’’ Proc. 1986 VLDB Conference, Kyoto, Japan, August 1986.

7. [COPE84] Copeland, G. and D. Maier, ‘‘Making Smalltalk a Database System,’’ Proc. 1984 ACM-SIGMOD Conference on Management of Data, Bos- ton, Mass. June 1984.

8. [DEC86] Digital Equipment Corp., ‘‘VAX/VMS V4.0 Reference Manual,’’ Digi- tal Equipment Corp., Maynard, Mass., June 1986.

9. [DEWI84] Dewitt, D. et. al., ‘‘Implementation Techniques for Main Memory Data- base Systems,’’ Proc. 1984 ACM-SIGMOD Conference on Management of Data, Boston, Mass., June 1984.

10. [GRAY78] Gray, J., ‘‘Notes on Data Base Operating Systems,’’ IBM Research, San Jose, Ca., RJ1879, June 1978.

11. [GUTM84] Gutman, A., ‘‘R-trees: A Dynamic Index Structure for Spatial Search- ing,’’ Proc. 1984 ACM-SIGMOD Conference on Management of Data, Boston, Mass. June 1984.

12. [HILL86] Hill, M., et al. ‘‘Design Decisions in SPUR,’’ Computer Magazine, vol.19, no.11, November 1986.

13. [ROUS85] Roussoupoulis, N. and Leifker, D., ‘‘Direct Spatial Search on Pictorial Databases Using Packed R-trees,’’ Proc. 1985 ACM-SIGMOD Confer- ence on Management of Data, Austin, Tx., May 1985.

14. [SEQU85] Sequent Computer Co., ‘‘The SEQUENT Balance Reference Manual,’’ Sequent Computers, Portland, Ore., 1985.

15. [SEVR76] Severence, D., and Lohman, G., ‘‘Differential Files: Their Application to the Maintenance of large Databases,’’ ACM-TODS, June 1976.

16. [STON76] Stonebraker, M., et. al. ‘‘The Design and Implementation of INGRES,’’ ACM-TODS, September 1976.

17. [STON86] Stonebraker, M. and Rowe, L., ‘‘The Design of POSTGRES,’’ Proc. 1986ACM-SIGMOD Conference on Management of Data, Washington, D.C., May 1986.

18. [STON86a] Stonebraker, M., ‘‘Inclusion of New Types in Relational Data Base Sys- tems,’’ Proc. Second International Conference on Data Base Engineer- ing, Los Angeles, Ca., Feb. 1986.

19. [VITT85] Vitter, J., ‘‘An Efficient I/O Interface for Optical Disks,’’ ACM-TODS, June 1985.