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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ВЗАИМНЫХ БЛОКИРОВОК ТРАНЗАКЦИЙ В СИСТЕМЕ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ(57) 1. Устройство для обнаружения взаимных блокировок транзакций в системе управления базами данных, содержащее модуль хранения информации, модуль обнаружения взаимных блокировок, модуль записи информации и модуль обновления информации,выполненные с возможностью использования информации о каждой исполняемой транзакции при этом модуль записи информации выполнен с возможностью записи информации о текущих отношениях ожидания между различными транзакциями в модуль хранения информации модуль хранения информации выполнен с возможностью хранения записанной в него информации об отношениях ожидания в виде данных предварительно созданной матрицы смежности, соответствующей построенному методом операций в узлах сетевому графику всех исполняемых транзакций модуль обновления информации выполнен с возможностью обновления подлежащих записи в указанную матрицу данных при каждом запросе блокировки или разблокировки какого-либо объекта блокировки 18522 1 2014.08.30 модуль обнаружения взаимных блокировок выполнен с возможностью обнаружения взаимных блокировок транзакций по алгоритму с операциями в узлах сетевого анализа данных, взятых из указанной матрицы, после каждого их изменения. 2. Устройство по п. 1, отличающееся тем, что модуль записи информации выполнен с возможностью, в случае получения от блокирующей транзакции нового запроса блокировки какого-либо объекта при условии несовместимости типа этой блокировки с типом блокировки, уже предоставленной этим объектом другим транзакциям, записи в указанную матрицу данных об изменившихся отношениях ожидания, характеризующих указанную несовместимость, для приостановления блокирующей транзакции. 3. Устройство по п. 2, отличающееся тем, что модуль обновления информации выполнен с возможностью, в случае получения от разблокирующей транзакции нового запроса разблокировки указанного объекта, определения совместимости типа блокировки,запрашиваемой транзакциями, ранее приостановленными указанным выше образом, с типом блокировки, еще остающейся в распоряжении разблокирующей транзакции, а также с возможностью в случае их несовместимости - сохранения подлежащих записи данных об отношениях ожидания между приостановленными транзакциями и разблокирующей транзакцией в неизменном виде, а в случае их совместимости - определения совместимости типа блокировки, запрашиваемой приостановленными транзакциями, с типом блокировки, находящейся в данный момент в распоряжении по меньшей мере одной посторонней транзакции,и в случае их совместимости - удаления из подлежащих записи данных информации об отношениях ожидания между приостановленными транзакциями и разблокирующей транзакцией, а в случае их несовместимости - добавление в подлежащие записи данные информации об изменившихся отношениях ожидания между приостановленными транзакциями, разблокирующей транзакцией и указанной посторонней транзакцией. 4. Устройство по п. 1, отличающееся тем, что модуль обнаружения взаимных блокировок выполнен с возможностью создания в модуле хранения информации резервной копии указанной матрицы, поиска петель взаимных блокировок транзакций путем анализа указанной копии методом топологической сортировки сети с операциями в узлах, а также с возможностью, в случае обнаружения петли взаимной блокировки, выбора в соответствии с заданной стратегией транзакции-жертвы из числа блокированных, подлежащей отмене с последующим перезапуском для снятия взаимной блокировки. Настоящее изобретение относится к базам данных, в частности к способу и устройству обнаружения взаимных блокировок в механизме блокировки транзакций в базе данных. Транзакция является одной из базовых и самых важных функций, обеспечиваемой системой управления базой данных (СУБД), и функция транзакции совершается с использованием одной из двух основных технологий, а именно механизма блокировки и функции системного журнала /. Механизм блокировки является основной технологией, с помощью которой реализуется функция транзакции, и он определяет, может ли быть выполнена данная транзакция или нет, и от него зависят эффективность, производительность и устойчивость системы. В основе механизмов блокировки, используемых в различных системах управления базами данных, лежит одна и та же теория, но реализованы они по-разному. В настоящее время в каждой из наиболее широко используемых систем управления базами данных, таких как , ,,и им подобные, используется свой механизм блокировки, и каждый из таких механизмов имеет свои преимущества и недостатки. 18522 1 2014.08.30 Одной из важнейших составляющих механизма блокировки является технология обнаружения взаимных блокировок. С помощью определенных методов частота возникновения взаимных блокировок в некоторых случаях может быть уменьшена или их можно совсем избежать, но в других случаях избежать их возникновения бывает очень трудно,поэтому поиск взаимных блокировок является неотъемлемой частью механизма блокировки. Обнаружение взаимных блокировок требует больших ресурсов вычислительной системы, и поэтому от эффективности поиска взаимных блокировок сильно зависит общая эффективность работы системы. Так, например, в системе 2008 используется следующий способ обнаружения взаимных блокировок для некоторой цепочки задач диспетчер блокировки помечает ресурс, который ожидает цепочка задач и после этого диспетчер блокировки ищет цепочку задач, которая использует данный ресурс в настоящее время, и так далее, то есть продолжает рекурсивно искать взаимную блокировку среди выполняемых цепочек задач до тех пор, пока не увидит наличие замкнутой цепи поиска. Замкнутая цепь, определенная таким образом, представляет собой взаимную блокировку. Такой способ обнаружения взаимных блокировок называется обнаружением постфактум (после события). В качестве еще одного примера можно привести способ поиска взаимных блокировок в системе . В данной системе также используется рекурсивный алгоритм, а именно если транзакция Т 1 (цепочка задач или инициатор запроса) вот-вот заблокирует определенный объект(которым может быть таблица или запись) и при этом требуется ожидание, сначала создается объект блокировки , а затем заранее проводится проверка, не произойдет ли при этом взаимной блокировки. Вызывается само-рекурсивная функция(Т 1, ), которая определяет, нет ли какой-либо блокирующей транзакции, ожидающей транзакции Т 1 до . Далее алгоритм обнаружения взаимных блокировок состоит в следующем 1) если предшествующей блокировки, которая приведет к блокировке объекта , не существует, то принимается заключение, что взаимной блокировки не произойдет, и поиск прекращается 2) определение, требует ли исполнение блокировкиожидания предшествующей блокировки, а блокировка находится в распоряжении Т 2, которая равняется Т 1, и если да, то считается, что возникла ситуация взаимной блокировки, и поиск прекращается и 3) получение блокировки 2, которой ждет операция Т 2, рекурсивный вызов функция(Т 1, 2). Можно видеть, чтотакже использует рекурсивный способ тестирования, с помощью которого определяется, образуется ли замкнутая петля ожидания из выполняемых транзакций или нет. В обеих системахииспользуется рекурсивный способ обнаружения взаимных блокировок, особенно в системе , в которой используется двунаправленный связный список, с помощью которого создается список блокировок,которые вызовет тестируемая блокировка, и список блокировок, находящихся в распоряжении транзакции. С помощью алгоритма поиска взаимных блокировок производится перекрестная проверка двухмерного связного списка и обнаружение существующих замкнутых петель ожидания. Эффективность такого способа поиска достаточно низка кроме того, за один раз может быть обнаружена только одна замкнутая петля ожидания и сам процесс обнаружения значительно замедляет выполнение текущей цепочки задач(транзакции). В итоге можно утверждать, что в настоящее время как в способе предварительного поиска, так и в способе поиска постфактум, используемых системами управления базам данных, большинство таких систем обнаруживают взаимные блокировки в основном используя карты ресурсов (карты распределенных ресурсов или карты запрашиваемых ресурсов). Недостатком таких способов является то, что информация, вырабатываемая в процессах выполнения блокировок и разблокировок, которая очень полезна для обнаружения взаимных блокировок, теряется, и поэтому в процессе поиска взаимных блокировок 3 18522 1 2014.08.30 может потребоваться многократный пересчет такой информации заново, что усложняет процесс обнаружения взаимных блокировок и ведет к напрасной трате вычислительных ресурсов. Исходя из вышесказанного, в настоящем изобретении предлагается устройство обнаружения взаимных блокировок в механизме блокировки транзакций базы данных, которые позволяют решить проблемы, связанные со сложностью обнаружения взаимных блокировок и напрасной тратой вычислительных ресурсов. В другом воплощении изобретения обеспечивается устройство для обнаружения взаимных блокировок в механизме блокировок транзакций базы данных. Устройство включает модуль хранения информации, модуль обнаружения взаимных блокировок, а также модуль записи информации и модуль обновления информации, причем оба последних модуля выполнены с возможностью участия в исполнении каждой цепочки задач причем модуль записи информации предназначен для записи информации об отношениях ожидания между цепочками задач, вырабатываемой в процессе выполнения блокировок, в модуле хранения информации модуль обновления информации предназначен для обновления соответствующей информации об отношениях ожидания в матрице смежности в процессе выполнения разблокировок в соответствии с имеющимися запросами модуль хранения информации предназначен для хранения информации об отношениях ожидания между цепочками задач в форме предварительно созданной матрицы смежности и модуль обнаружения взаимных блокировок предназначен для проведения расчетов и обнаружения соответствующих цепочек задач на основе информации об отношениях ожидания между цепочками задач, хранящейся в модуле хранения информации, содержащейся в резервной копии матрицы смежности, и с помощью принципов сети с операциями в узлах, с целью обнаружить, существует ли взаимная блокировка. Кроме того, модуль записи информации при блокировках может быть дополнительно предназначен, при выполнении блокировки, для записи информации об отношениях ожидания, а именно информации о том, что блокирующая цепочка задач ожидает выполнения прочих цепочек задач, в модуле хранения информации, когда блокировка, запрашиваемая блокирующей цепочкой задач, является несовместимой с типом блокировки, предоставленным объектом блокировки другим цепочкам задач, и после этого - для приостановки блокирующей цепочки и ожидания разблокировки имеющих к ней отношение прочих цепочек. Кроме того, модуль обновления информации может быть дополнительно предназначен для определения, является ли тип блокировки, запрашиваемый каждой из цепочек задач, в текущий момент запрашивающих блокировки, и записанный в модуле хранения информации, совместимым с типом блокировки, еще остающимся в распоряжении разблокирующей цепочки задач, и если он является несовместимым - для сохранения информации об отношениях ожидания неизменной а если он является совместимым - для продолжающегося определения, является ли тип блокировки, который собирается запросить каждая из текущих блокирующих цепочек задач, несовместимым с типом блокировки, находящимся в распоряжении по меньшей мере одной из других цепочек задач, и если он является несовместимым - для передачи очередности ожидания блокировок и обновления соответствующей информации об отношениях ожидания в матрице смежности а если он является совместимым - только для удаления исходной информации об отношениях ожидания между цепочками задач. Кроме того, модуль обнаружения взаимных блокировок может быть дополнительно предназначен для создания резервной копии матрицы смежности в модуле хранения информации проведения расчетов и обнаружения соответствующих цепочек задач на основании информации, содержащейся в резервной копии матрицы смежности, и с помощью метода топологической сортировки сетей с операциями в узлах, с целью определить, су 4 18522 1 2014.08.30 ществует ли петля взаимной блокировки между цепочками задач и если подтверждается наличие петли взаимной блокировки между цепочками задач - для выбора из петли взаимной блокировки цепочки задач - жертвы в соответствии с заданной стратегией, и после этого - для выхода из состояния взаимной блокировки путем снятия цепочки задач - жертвы и возврата к началу. Изобретение обеспечивает следующие преимущества. Предлагаемое в соответствии с изобретением техническое решение обеспечивает очень высокую скорость обнаружения взаимных блокировок за счет наиболее полного использования полезной информации, получаемой в процессах блокировки и разблокировки, что обеспечивает экономию вычислительных ресурсов. Прочие характеристики и преимущества изобретения будут представлены ниже в подробном его описании, и часть из них станет очевидной непосредственно из подробного описания, а еще какая-то часть - при реализации настоящего изобретения. Цели и преимущества настоящего изобретения могут быть достигнуты с помощью составляющих его предмет структур, изложенных и представленных в настоящем описании, в формуле изобретения и на фигуре. Основной концепцией настоящего изобретения является то, что во время процессов выполнения блокировок и разблокировок цепочками задач вырабатывается и обновляется информация, предназначенная для обнаружения взаимных блокировок, и на основе информации, предназначенной для обнаружения взаимных блокировок, производится топологическая сортировка сетевых графиков операция-узел цепочек задач, в результате чего определяется, существует ли взаимная блокировка. Ниже представлено подробное описание предпочтительного воплощения изобретения,сопровождаемое прилагаемой фигурой, которая используется для иллюстрации принципа работы настоящего изобретения. Ниже подробно описано устройство в соответствии с воплощением настоящего изобретения, схематически представленное на фигуре. Предлагаемое в соответствии с воплощением настоящего изобретения устройство,структура которого изображена на фигуре, содержит модуль хранения информации, модуль обнаружения взаимных блокировок, а также модуль записи информации и модуль обновления информации (оба последних модуля содержатся в каждой цепочке задач). Ниже данные модули будут описаны более подробно. Модуль хранения информации предназначен для хранения информации об отношениях ожидания между цепочками задач, которая вырабатывается, когда блокирующая цепочка задач должна ждать выполнения других цепочек задач в процессе выполнения блокировки. В соответствии с воплощением настоящего изобретения, модуль хранения информации имеет вид матрицы смежности . Модуль записи информации может участвовать в исполнении цепочки задач. Цепочка задач, осуществляющая блокировку, именуется блокирующей цепочкой в процессе выполнения блокировки, когда тип блокировки, запрашиваемый блокирующей цепочкой задач, несовместим с типом блокировки, который объект блокировки предоставил прочим цепочкам задач, модуль записи информации записывает информацию об отношениях ожидания, а именно, что блокирующая цепочка задач ожидает выполнения прочих цепочек задач, после чего блокирующая цепочка задач приостанавливается и ожидает разблокировки имеющих к ней отношение цепочек задач. Так, например, в процессе блокировки определенного объекта блокировки (например, объекта ), если тип блокировки, запрошенный блокирующей цепочкой задач , несовместим с типом блокировки, который объектпредоставил другим цепочкам задач (например, цепочке задач ), тогда модуль записи информации блокирующей цепочки задачзаписывает информацию об отношениях ожидания (значение , означающее, что цепочка задачожидает выполнения цепочки задач ) в строкеи столбцематрицы смежности , и стирает данную 5 18522 1 2014.08.30 информацию после того, как выполнение цепочки задачвозобновляется, и данная цепочка получает запрошенную блокировку. Модуль обновления информации также может участвовать в исполнении цепочки задач. Цепочка, выполняющая снятие блокировки, называется разблокирующей цепочкой в процессе снятия блокировки, выполняемом разблокирующей цепочкой, определяются типы блокировки, запрашиваемые в настоящее время какой-либо цепочкой (из всех, что запрашивают блокировку) и записанные в модуле хранения информации, и определяются,являются ли они совместимыми с типами блокировок, все еще используемыми разблокирующей цепочкой задач если они несовместимы, информация об отношениях ожидания остается неизменной если же они совместимы, далее определяется, является ли данный тип блокировки несовместимым по меньшей мере с одним из типов блокировки, находящихся в распоряжении по меньшей мере одной из прочих цепочек задач, и если он является несовместимым, проводится передача очередности блокировок, и в матрице смежности обновляется соответствующая информация об отношениях ожидания, в противном случае проводится только удаление исходной информации об отношениях ожидания. Так,например, когда разблокирующая цепочка задачразблокирует определенный объектблокировки, для цепочки задач , соответствующей каждой непустой ячейке в столбцематрицы смежности , модуль информации разблокирующей цепочкиопределяет, является блокировка, которую ожидает цепочка , блокировкой , и является ли блокировка, запрашиваемая цепочкой задач , совместимой с блокировкой, все еще находящейся в распоряжении разблокирующей цепочки , и если нет, значение ячейкиоставляется неизменным, а если да - производится поиск цепочки задач , в распоряжении которой находится тип блокировки, несовместимый с типом блокировки, запрашиваемым цепочкой задач , после чего значениестирается, а значениюприсваивается значение , в противном случае производится только стирание значения . Следует отметить, что каждая цепочка сама по себе может использовать модуль записи информации, предназначенный для записи информации об отношениях ожидания между данной цепочкой задач и другими цепочками в модуле хранения информации всякий раз, когда данная цепочка работает как блокирующая цепочка, а также модуль обновления информации, предназначенный для обновления соответствующей информации об отношениях ожидания в модуле хранения информации, в соответствии с имеющимися запросами, когда данная цепочка работает как разблокирующая. Данное воплощение изобретения было описано выше на примере только двух цепочек, однако сведущим в данной области техники известно, что в системе управления базой данными может выполняться множество цепочек задач, и соответственно, может вырабатываться несколько массивов информации об отношениях ожидания между цепочками задач. В соответствии с воплощением настоящего изобретения, обнаружение взаимных блокировок проводится фон-независимой цепочкой задач (цепочка задач обнаружения взаимных блокировок) периодически (обнаружение постфактум) или в реальном времени при каждой блокировке (заблаговременное обнаружение). Цепочка задач обнаружения взаимных блокировок сначала создает резервную копию матрицы смежности(матрица смежностипредставляет собой ориентированный граф ), затем производит вычислительную обработку данных, содержащихся в резервной копии матрицы с использованием алгоритма, с целью поиска в ней замкнутых петель ожидания. Такая обработка проводится путем удаления всех узлов, не имеющих предшественников, то есть входящих в них стрелок, а также стрелок, исходящих из таких узлов. Если с помощью данной процедуры все узлы могут быть удалены, делается заключение, что взаимной блокировки нет, и поиск заканчивается в противном случае делается заключение, что петля взаимной блокировки существует, и в данной петле выбирается узел, соответствующий цепочке задач, которая будет принесена в жертву в соответствии с заданной стратегией. 18522 1 2014.08.30 Прочие подробности основных и промежуточных этапов поиска взаимных блокировок, реализованных в предлагаемом устройстве в соответствии с настоящим изобретением, были объяснены выше при описании способа поиска взаимных блокировок в соответствии с настоящим изобретением, поэтому нет необходимости подробно описывать их снова. В заключение отметим, что в воплощении настоящего изобретения предлагается устройство для обнаружения взаимных блокировок в механизме блокировок транзакций базы данных, обеспечивающее следующие преимущества за счет записи отношений ожидания между цепочками задач с использованием матрицы смежности все замкнутые петли ожидания могут быть обнаружены с использованием лишь простых расчетов, совершаемых с данной матрицей, для каждой петли в соответствии с заданной стратегией выбирается цепочка-жертва, и взаимная блокировка может быть разорвана путем снятия цепочки задач - жертвы и возврата к началу, в результате чего может быть достигнута очень высокая эффективность обнаружения взаимных блокировок для облегчения обнаружения взаимных блокировок обеспечивается максимальное использование информации, получаемой при каждой блокировке и разблокировке, что позволяет избежать многократного пересчета одной и той же информации в ходе обнаружения взаимных блокировок, что в свою очередь позволяет уменьшить нагрузку на вычислительные ресурсы системы (в то время как в большинстве механизмов блокировки,используемых сегодня, процессы блокировки и разблокировки, с одной стороны, и процессы обнаружения взаимных блокировок, с другой стороны, полностью отделены друг от друга, в результате чего значительное количество полезной информации теряется, производятся многократные расчеты одной и той же информации, что в конечном итоге приводит к напрасному расходованию вычислительных ресурсов) использование резервной копии матрицы смежностидля обнаружения взаимных блокировок делает цепочку задач обнаружения взаимных блокировок практически не влияющей на процессы блокировки и разблокировки, выполняемые обычными цепочками задач, и практически не может привести к их остановке (в то время как процесс обнаружения взаимных блокировок в большинстве механизмов блокировки, используемых сегодня, требует обращения к картам ресурсов и данным, содержащимся в объектах блокировки, в результате чего процесс обнаружения взаимных блокировок неизбежно будет останавливать процессы блокировки и разблокировки, совершаемые основными цепочками задач) расчеты, проводимые для обнаружения взаимных блокировок, для которых используются резервные копии данных, не вмешиваются в процессы блокировки и разблокировки,совершаемые основными цепочками задач, в результате чего повышается общая эффективность вычислительной системы. Выше было представлено только лишь предпочтительное воплощение настоящего изобретения, и его не следует рассматривать как воплощение, ограничивающее настоящее изобретение. Сведущим в данной области техники будет понятно, что возможные очевидные изменения и модификации, не нарушающие идею и назначение изобретения, также находятся в пределах защищаемого масштаба настоящего изобретения. Поэтому защищаемым масштабом настоящего изобретения следует считать масштаб, устанавливаемый формулой настоящего изобретения. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 7