Библиотека сайта rus-linux.net
Архитектура приложений с открытым исходным кодом. Том 1. Глава 4. Berkeley DB
Оригинал: "Berkeley DB"Авторы: Margo Seltzer and Keith Bostic
Дата публикации: 2012 г.
Перевод: Н.Ромоданов
Дата перевода: октябрь 2012 г.
4.7. Менеджер блокировок: Lock
Точно также, как и Mpool, менеджер блокировок был разработан как компонент общего назначения: иерархический менеджер блокировок (смотрите [GLPT76]) создан для поддержки иерархии объектов, которые могут быть заблокированы (например, отдельные элементы данных) – страница, на которой размещен элемент данных, файл, в котором запомнен элемент данных или даже набор файлов. Поскольку мы описываем возможности менеджера блокировок, мы также объясним, как они используются в Berkeley DB. Но, как и с Mpool, важно запомнить, что другие приложения могут использовать менеджер блокировок совершенно по-другому и это нормально - он был разработан максимально гибко и поддерживает множество различных вариантов применений.
В менеджере блокировок есть три ключевые абстракции: «блокировка» («locker»), которая определяет, на действия какого объекта устанавливается блокировка, «объект блокировки» («lock_object»), который определяет блокируемый элемент, и «матрица конфликтов» («conflict matrix»).
Блокировки являются 32- разрядными целыми числами. Berkeley DB делит пространство имен 32-разрядных чисел на транзакционные и на нетранзакционные блокировки (хотя это различие является прозрачным для менеджера блокировок). Когда Berkeley DB использует менеджер блокировок, он назначает идентификаторы ID блокировок в диапазоне от 0 до 0x7fffffff для нетранзакционных блокировок и в диапазоне от 0x80000000 и до 0xffffffff — для транзакционных блокировок. Например, когда приложение открывает базу данных, Berkeley DB для того, чтобы обеспечить, чтобы никакой другой поток управления не удалил ее или не переименовал, пока она используется, устанавливает для этой базы долговременную блокировку чтения. Поскольку это долговременная блокировка, она не принадлежит какой-либо транзакции и объект "блокировка", осуществляющий эту блокировку, является нетранзакционным.
Необходимо, чтобы любое приложение, использующее менеджер
блокировок, назначало идентификаторы блокировок, поэтому в интерфейсе
API менеджера блокировок есть вызовы DB_ENV->lock_id и DB_ENV->lock_id_free, предназначенные для выделения и освобождения блокировок. Таким образом, приложениям не нужно реализовывать свои собственные механизмы выделения блокировок, хотя они, конечно, могут это делать.
4.7.1. Блокируемые объекты
Блокируемые объекты являются строками байтов произвольной длины и с любой внутренней структурой, представляющие блокируемые объекты. Когда две различных блокировки хотят заблокировать некоторый конкретный объект, они для ссылки на этот объект пользуются одной и той же строкой байтов. То есть, обязанность самих приложений соблюдать конвенции, касающиеся внутренней структуры блокируемых объектов.
Например, Berkeley DB использует структуру DB_LOCK_ILOCK для описания блокировок баз данных. В этой структуре есть три поля: идентификатор файла, номер страницы и тип.
Почти во всех случаях, Berkeley DB нужно описывать только конкретный файл и страницу, которую она хочет заблокировать. Berkeley DB назначает уникальный 32-разрядный номер каждой базе данных во время ее создания, записывает его в страницу метаданных базы данных, а затем использует его в качестве уникального идентификатора базы данных в подсистеме Mpool , подсистеме блокировок и журнальной подсистеме. Это идентификатор fileid, к которому мы ссылаемся в структуре DB_LOCK_ILOCK. Естественно, что номер страницы указывает, какую страницу из определенной базы данных мы хотим заблокировать. Когда мы обращаемся к блокировке страниц, мы задаем значение в поле типа в структуре DB_PAGE_LOCK. Но мы можем при необходимости блокировать также другие типы объектов. Как уже упоминалось ранее, мы иногда блокируем дескриптор базы данных, для которого нужно указать тип DB_HANDLE_LOCK. Тип DB_RECORD_LOCK позволяет нам в методе доступа к очереди выполнить блокировку уровня записи, а тип DB_DATABASE_LOCK позволяет нам блокировать всю базу данных.
Девятый урок конструирования
Решение в Berkeley DB использовать блокировку на уровне страниц было сделано по уважительным причинам, но мы обнаружили, что иногда из-за этого решения возникают проблемы. Блокировка на уровне страниц ограничивает возможность распараллеливания приложений, поскольку один поток, модифицирующий запись на странице базы данных, будет мешать другим потокам управления модифицировать другие записи на той же самой странице, тогда как при блокировке на уровне записей такое распараллеливание допускается до тех пор, пока два потока управления не будут модифицировать одну и ту же запись. Блокировка на уровне страниц повышает стабильность базы данных, поскольку она ограничивает количество возможных путей восстановления (во время восстановления страница всегда находится в одном из двух состояний, в отличие от бесконечного числа возможных состояний, в которых страница может быть в случае, если на странице добавляется или удаляется несколько записей). Поскольку Berkeley DB предназначалась для использования в качестве встроенной системы, когда нет администратора базы данных, который мог бы исправить ситуацию в случае возникновения повреждения, мы отдали предпочтение стабильности, а не возможности увеличения распараллеливания.
4.7.2. Матрица конфликтов
Последней абстракцией подсистемы блокировок, которую мы обсудим, является матрица конфликтов. В матрице конфликтов определяются различные типы блокировок, присутствующие в системе и их взаимодействие между собой. Давайте назовем сущность, удерживающую блокировку, владельцем блокировки, а сущность, пытающуюся выполнить блокировку, инициатором блокировки, и давайте считать, что владелец и инициатор имеют разные идентификаторы блокировок. Матрица конфликтов представляет собой массив, индексируемый с помощью пары [инициатор] [владелец], где каждый элемент содержит ноль в случае, если конфликта нет, что указывает, что запрашиваемая блокировка может быть выполнена, и содержит единицу в случае, если имеется конфликт, что указывает, что запрос не может быть выполнен.
В менеджере блокировок имеется матрица конфликтов, используемая по умолчанию, в которой указано именно то, что требуется для Berkeley DB, однако, приложение может использовать свои собственные режимы блокировок и матрицу конфликтов, соответствующие собственным целям приложения. Единственное требование к матрице конфликтов – чтобы она была квадратная (в ней одинаковое количество строк и столбцов) и чтобы в приложении для описания его собственных режимов блокировок (например, чтения, записи и т. д.) использовались последовательно идущие целые числа, начинающиеся с нуля. В таблице 4.2 показана матрица конфликтов для Berkeley DB.
| Владелец | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Инициатор | No-Lock | Read | Write | Wait | iWrite | iRead | iRW | uRead | wasWrite | |||||||
| No-Lock | ||||||||||||||||
| Read | ✓ | ✓ | ✓ | ✓ | ||||||||||||
| Write | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ||||||||
| Wait | ||||||||||||||||
| iWrite | ✓ | ✓ | ✓ | ✓ | ||||||||||||
| iRead | ✓ | ✓ | ||||||||||||||
| iRW | ✓ | ✓ | ✓ | ✓ | ||||||||||||
| uRead | ✓ | ✓ | ✓ | |||||||||||||
| iwasWrite | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ||||||||||
Таблица 4.2: Матрица конфликтов чтения-записи
4.7.3. Поддержка иерархической блокировки
Прежде чем объяснять различные режимы блокировок, указываемые в матрице конфликтов Berkeley DB, давайте поговорим о том, как в подсистеме блокировок поддерживаются иерархические блокировки. Иерархическая блокировки представляют собой возможность блокировать различные элементы в иерархии вложения. Например, файлы содержат страницы, а страницы содержат отдельные элементы. Когда в иерархической системе блокировок изменяется один элемент на странице, нам нужно блокировать только этот элемент; если мы изменили все элементы страницы, было бы более эффективным просто заблокировать страницу, и если мы изменили все страницы файла, было бы лучше заблокировать весь файл. Кроме того, иерархическая блокировка должна различать иерархию контейнеров, поскольку блокировка страницы также говорит о блокировке файлов: вы не можете изменить файл, содержащий страницу, в тот же самый момент, когда модифицируются страницы файла.
Тогда вопрос состоит в том, как разрешать различным блокировщикам выполнять блокировку на различных иерархических уровнях, но при этом не получить в результате хаос. Ответ кроется в конструкции, которая называется уведомлением о блокировке (intention lock). Блокировщик создает внутри контейнера уведомление о блокировке с тем, чтобы сообщить о намерении заблокировать объекты внутри этого контейнера. Поэтому получение блокировки чтения на странице подразумевает получение уведомления о блокировке файла. Аналогично, чтобы записать единственный элемент страницы, вы должны создать уведомление о блокировке записи, как для страницы, так и для файла. В матрице конфликтов, приведенной выше, блокировки iRead, iWrite и iWR являются уведомлениями о блокировках, которые указывают на намерение выполнить чтение, запись или и то и другое, соответственно.
Поэтому когда выполняется иерархическая блокировка, а не запрос на
отдельную блокировку, необходимо запрашивать потенциально много блокировок: блокировку на фактически блокируемый объект, а также
уведомления о блокировках на любой объект, в котором содержится блокируемый объект. В результате в Berkeley DB нужно обращаться к интерфейсу DB_ENV->lock_vec, который получает массив запросов на блокировку и атомарно реализует их (или отклоняет).
Хотя внутри самой Berkeley DB иерархическая блокировка не используется, она дает преимущество за счет возможности указывать различные матрицы конфликтов и возможности указывать за один раз сразу несколько запросов. Когда поддерживаются транзакции, мы используем матрицу конфликтов, предлагаемую по умолчанию, но с помощью другой матрицы конфликтов можно реализовать простой одновременный доступ без поддержки транзакций и восстановления. Чтобы подключить блокировки, мы пользуемся DB_ENV->lock_vec, методикой, которая улучшает распараллеливание при обходе дерева Btree [Com79]. Когда вы подключаете блокировку, вы ее сохраняете только в течение того времени, которое необходимо для получения следующей блокировки. То есть, вы блокируете внутреннюю страницу Btree только в течение того времени, которое нужно для чтения информации, позволяющей вам выбрать и заблокировать страницу на следующем уровне.
Десятый урок конструирования
Универсальная архитектура Berkeley DB принесла хорошие плоды, когда мы добавили функции параллельной работы с хранилищами данных. Первоначально в Berkeley DB предлагалось только два режима: либо вы, когда записывали данные, работали без какого-либо распараллеливания, либо - с полной поддержкой транзакций. Поддержка транзакций влечет за собой определенные сложности для разработчиков, и мы выяснили, что для некоторых приложений требовалась большая степень распараллеливания без накладных расходов, связанных с полной поддержкой транзакций. Чтобы реализовать эту возможность, мы добавили поддержку блокировок на уровне API, что позволяет пользоваться распараллеливанием при одновременной гарантии отсутствия тупиковых ситуаций. При использовании курсоров для этого потребовался новый и отличающийся режим блокировки. Вместо того, чтобы добавлять специальный код в менеджер блокировок, мы смогли создать альтернативную матрицу блокировок, в которой поддерживаются только режимы блокировок, необходимые для блокировки на уровне API. Таким образом, мы смогли получить необходимые нам режимы блокировок просто при помощи задания другой конфигурации менеджера блокировок. (К сожалению, изменить методы доступа оказалось не так легко; еще есть большие куски кода в методах доступа, в которых осуществляется обработка этого специального режима параллельного доступа).
| Назад | К оглавлению книги | Вперед |