СПОСОБ ОРГАНИЗАЦИИ ХРАНЕНИЯ ИСТОРИЧЕСКИХ ДЕЛЬТ ЗАПИСЕЙ Российский патент 2018 года по МПК G06F17/30 G06F7/00 

ОБЛАСТЬ ТЕХНИКИ

[1] Данное техническое решение относится к области вычислительной техники, в частности к способам хранения данных, и может быть использовано в системе управления базами данных (СУБД).

УРОВЕНЬ ТЕХНИКИ

[2] Из уровня техники известна заявка на патент на изобретение US 20150039559 A1 «Compressing a multi-version database», патентообладатель International Business Machines Corp, в котором предлагается размещать исторические дельты изменений (DELTA CHANGES) на отдельном твердотельном накопителе (SSD). Дельты записей при этом накапливаются в т.н. дельта-блоке (DELTA BLOCKS) и лишь после его наполнения преобразуются и сохраняются на страницу данных. Дельты не являются частью оригинальной записи.

[3] Также известна заявка на патент на изобретение US 20150046413 А1 «Delta store giving row-level versioning semantics to a non-row-level versioning underlying store», патентообладатель SAP SE, в котором предлагается обеспечивать конкурентный доступ к данным путем создания хранилища дельт (delta store) в ОЗУ, а основное хранилище (main store) не допускает параллельных транзакций на хранящихся данных и не хранит исторических дельт.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[4] Данное техническое решение направлено на устранение недостатков, присущих существующим решениям хранения данных.

[5] Технической задачей или проблемой, поставленной в данном решении, является организация хранения исторических дельт записи при модификации записи.

[6] Технический результат, проявляющий при решении вышеуказанной задачи, заключается в повышении производительности системы управления базами данных за счет уменьшения расхода емкости ЗУ и хранения дельт записи вместе с записью.

[7] Также дополнительным техническим результатом является повышение скорости операций, связанных с поиском, чтением и модификацией исторических дельт записи, хранящихся вместе с записью.

[8] Дополнительно при решении вышеуказанной задачи рационально используется оперативная память в техническом решении. Также хранение массива исторических дельт как части записи позволяет уменьшить накладные вычислительные расходы, связанные с адресацией и поиском исторической дельты по сравнению с конкурирующими решениями.

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

[10] В некоторых вариантах осуществления технического решения выбор страницы данных, в которую будет помещена запись, происходит с учетом соответствия совокупных размеров уже размещенных записей и/или их частей пороговым значениям.

[11] В некоторых вариантах осуществления технического решения осуществляют модификацию записи по запросу пользователя и/или служебной операции СУБД, и/или при выполнении хранимых процедур, и/или при срабатывании триггеров, и/или исполнении определенных пользователем функций (UDF).

[12] В некоторых вариантах осуществления технического решения при осуществлении модификации записи контролируют соответствие совокупных размеров записей и/или их частей на странице пороговым значениям.

[13] В некоторых вариантах осуществления технического решения дельта записи содержит атрибут или поле записи, и ее старое значение.

[14] В некоторых вариантах осуществления технического решения набор дельт записи упорядочен в хронологическом порядке.

[15] В некоторых вариантах осуществления технического решения запоминающим устройством является ОЗУ, и/или ПЗУ, и/или магнитная память, и/или флэш-память, и/или магнитный диск и/или оптический диск.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[16] Признаки и преимущества настоящего изобретения станут очевидными из приведенного ниже подробного описания изобретения и прилагаемых чертежей, на которых:

[17] На Фиг. 1 схематически изображена структура записи, где 101 - заголовок, 102 - тело записи, 103 - массив исторических дельт 104-106. 104 - последняя добавленная историческая дельта, а 106 - первая.

[18] На Фиг. 2 изображена страница данных (201) с заголовком (202) и областью данных (203), представлены пороги PDS (206), PDH (207) и записи (204, 205).

[19] На Фиг. 3 изображены состояния записи (301, 301', 301'') в моменты времени t0 (312), t1 (313), t2 (314) в каждый из которых добавлялась новая историческая дельта (307, 308, 309 соответственно). В момент времени t0 и t1 запись (301, 301') целиком находится на странице (315) данных. Будем считать, что добавление следующей исторической дельты (309) привело бы к превышению порога PHL, следовательно, ранее добавленные исторические дельты (308', 307'') перенесены в сегмент исторических данных (316). Если в момент времени t3>t2 нет транзакций, заинтересованных в сохранении исторических дельт 308' и 307'', сегмент версионных данных (316) может быть освобожден.

[20] На Фиг. 4 переведена блок-схема, иллюстрирующая вариант реализации размещения новой записи на странице.

[21] На Фиг. 5 переведена блок-схема, иллюстрирующая вариант реализации обновления существующей записи.

[22] На Фиг. 6 переведена блок-схема, иллюстрирующая вариант реализации удаления существующей записи.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

[23] Ниже будут описаны понятия и определения, необходимые для подробного раскрытия осуществляемого изобретения.

[24] Запись - набор значений различных типов, предназначенный к хранению в ЗУ.

[25] База данных, database - представленная в объективной форме совокупность самостоятельных материалов (статей, расчетов, нормативных актов, судебных решений и иных подобных материалов), систематизированных таким образом, чтобы эти материалы могли быть найдены и обработаны с помощью электронной вычислительной машины (ЭВМ).

[26] Система управления базами данных, Database Management System, СУБД, DBMS - совокупность программных и лингвистических средств общего или специального назначения, обеспечивающих управление созданием и использованием баз данных.

[27] Управление конкурентным доступом с помощью многоверсионности, MultiVersion Concurrency Control, MVCC - механизм обеспечения одновременного конкурентного доступа к базе данных, заключающийся в предоставлении каждому пользователю т.н. снимка (snapshot) БД, обладающего тем свойством, что вносимые пользователем изменения в БД невидимы другим пользователям до момента фиксации транзакции.

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

[29] Историческая дельта записи или дельта записи (англ. delta record) - описание изменения записи, достаточное для восстановления ее исходного содержимого.

[30] Устаревшая историческая дельта записи - историческая дельта записи, предназначенная для восстановления содержимого записи в такое состояние, которое, согласно выбранной модели изоляции БД, не может быть больше востребовано ни одной неоконченной транзакцией.

[31] Согласно Фиг. 1, способ организации хранения исторических дельт записей осуществляется следующим образом.

[32] Шаг 101: формируют, по меньшей мере, одну запись базы данных, которая содержит данные и заголовок;

[33] Вновь созданная запись (Фиг. 1) состоит из данных (102') и заголовка (101') и не имеет ни одного элемента в массиве исторических дельт.

[34] Шаг 102: сохраняют сформированную выше, по меньшей мере, одну запись в странично-организованный файл на запоминающем устройстве, в котором каждая страница данных содержит заголовок и область данных для хранения записей;

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

[36] Выбор страницы данных, в которую будет помещена запись, происходит с учетом (Фиг. 4) соответствия совокупных размеров уже размещенных записей и/или их частей следующим пороговым значениям:

PDH (page data hard limit) - максимально допустимый совокупный размер всех записей на странице, при достижении данного значения запрещается (406) вставка новых записей на страницу;

PDS (page data soft limit) - максимально допустимый совокупный размер всех записей на странице без учета их исторических дельт, причем при достижении значения PDS запрещается (406) вставка новых записей на страницу.

[37] Осуществление добавления новой записи (Фиг. 4) производится только при условии, что не превышен ни порог PDH (402), ни порог PDS(403).

[38] При этом в отличие от модификации, для страниц, которые не выполняют условия порогов, не производится какая-либо оптимизация пространства, поиск и удаления устаревших записей. Данный подход применяется для минимизации времени вставки новой записи.

[39] Шаг 103: осуществляют модификацию, по меньшей мере, одной записи на странице на запоминающем устройстве;

[40] Причиной модификации записи могут являться: запросы пользователя, служебные операции СУБД, выполнение хранимых процедур, срабатывание триггеров, исполнение определенных пользователем функций (UDF) и пр.

[41] Пусть в момент времени Т=1 база данных имеет следующее состояние:

[42] Транзакция Т0 выполнила операции Объект1=«Foo» и Объект2=«Bar», после чего транзакция Т1 выполнила операцию Объект1=«Hello». Объект1 будет хранить свое старое значение «Foo» до тех пор, пока не завершатся все транзакции ТХ созданные в промежутке времени 0<Х<1, поскольку они «видят» только значение «Foo».

[43] В случае модификации записи для обеспечения управления конкурентным доступом с помощью MVCC необходимо обеспечить хранение как нового состояния и значения записи, так и информации о предыдущем ее [записи] состоянии и значении. Текущее значение записи хранится явно в теле записи (102), а для восстановления какого-либо из предыдущих состояний записи используются дельты из массива исторических дельт (103). Каждая новая дельта добавляется при модификации записи и содержит информацию достаточную для полного восстановления предыдущего состояния записи после применения к текущему значению записи. Формат хранения дельт не является ограничивающим фактором и может быть любым.

[44] При модификации записи в данном техническом решении производят контроль соответствия совокупных размеров записей и/или их частей на странице (Фиг. 2, Фиг. 5) пороговым значениям PDH (см. описание выше) и PDL.

[45] PHL (page history limit) - максимально допустимый совокупный размер всех исторических дельт всех записей на странице, при достижении этого порога на странице производится поиск устаревших исторических дельт (508) и их удаление (510) и/или перенос (509) части исторических дельт в отдельную область ЗУ - сегмент версионных данных.

[46] В случае превышения вышеуказанных порогов при модификации записи производится оптимизация использования свободного пространства на странице. Для этого, в случае превышения порога PDH (502), во всех массивах исторических дельт всех записей на странице производят поиск дельт, которые предназначены для восстановления состояний, которые не «нужны» ни одной незаконченной транзакции. Такие дельты называются устаревшими и могут быть удалены (510), что освободит некоторое пространство на странице.

[47] Если и после удаления всех устаревших дельт на странице пороговое значение PDH остается превышенным, то часть исторических дельт (самые «старые» из тех, что остались) переносятся (509) в специальную область на запоминающем устройстве - сегмент версионных данных.

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

[49] В случае удаления записи (Фиг. 6) непосредственно всю запись с данными и устаревшими дельтами можно удалять со страницы только в том случае, если не осталось ни одной транзакции, начавшейся раньше удаления, а все дельты являются устаревшими. Поскольку вероятность такой ситуации достаточно низкая при существовании большого числа одновременных транзакций в СУБД, то вместо удаления запись помечается (603) как удаленная. Физическое удаление записи произойдет при модификации записи в странице, и/или будет превышен один из порогов. В этом случае при поиске устаревших данных на странице запись будет найдена и удалена со страницы.

[50] Шаг 104: определяют дельту записи, достаточную для восстановления состояния записи до модификации;

[51] Формат хранения дельты записи может быть реализован различными способами. В простейшем случае в дельтах хранят указание атрибута (поля) записи и ее старого значения. Пусть, например, некий объект с атрибутами ID и STR менялся в ходе работы СУБД следующим образом:

тогда запись можно условно представить следующим образом:

{id:2,str:«Hello3»} [str:«Hello»→«Hello3»}][Id:{1->2}][str:{«Foo»}→«Hello»}][id:{->1}, id{->«Foo»}], где {id:2,str:«Hello3»} - последнее (текущее) значение объекта, а в скобках приведены исторические дельты. Самая первая дельта описывает создание записи, поэтому указано только добавленное значение, поскольку предыдущего не существовало на тот момент.

[52] Шаг 105: добавляют определенную на предыдущем шаге дельту записи в упорядоченный набор дельт записи, который хранится как часть записи.

[53] Упорядоченное хранение необходимо для упрощения освобождения (удаления) устаревших записей. Пусть запись

[54] {id:2,str:«Hello3»}[str:{«Hello»→«Hello3»}][Id:{1->2}][str:{«Foo»→«Hello»}][id:{->1},id{->«Foo»}]

[55] Описывает изменения последовательными (или сериализованными) транзакциями Т0, Т1, Т2, Т3 совершенными в моменты времени 0, 1, 2, 3 соответственно. Тогда, если на момент поиска и удаления устаревших дельт записи известно, что в системе нет незавершенных транзакций, созданных раньше момента времени 3, то дельты записи, описывающие более ранние состояния, уже не могут быть кем-либо затребованными, и являются устаревшими и будут удалены без каких-либо дополнительных проверок, после чего запись примет вид:

{id:2,str:«Hello3»}[str:{«Hello»→«Hello3»}][][][]

[56] Освободившееся пространство в «хвосте» записи будет повторно использовано для сдвига дельт при добавлении новой дельты записи:

{id:2,str:«NEW»}[str:{«Hello3»→«NEW»}][str:{«Hello»→«Hello3»}][][]

[57] Кроме того, как было указано выше - самые старые дельты записи при определенных условиях могут быть перенесены на другую страницу в сегмент версионных данных. Обращение к дополнительной странице несет определенные накладные расходы, но, как показывает практика, чем «старее» дельта, тем ниже вероятность того, что она кому-либо будет необходима, а значит целесообразно более «востребованные» дельты хранить на той же странице, что и запись, а более старые - переносить при необходимости. Это еще один аргумент хранить дельты упорядоченно по времени добавления.

[58] Каждая запись, к которой осуществляется конкурентный доступ, помимо непосредственно данных и заголовков (Фиг. 1, позиции 101 и 102) на данном шаге дополнительно содержит массив исторических дельт записи - набор исторических дельт записи (Фиг. 1, позиции 104, 105 и 106), упорядоченный в обратном хронологическом порядке: первый элемент содержит дельту, полученную последней, а последний элемент - полученную первой.

Пусть Объект1 менялся в ходе работы СУБД следующим образом:

тогда согласно осуществлению изобретения запись можно условно представить как «Hello3»[«2»→«3»][«o»→«o2»][«Foo»→«Hello»][→«Foo»],

т.е. хранится последнее значение («Hello3») и цепочка изменений в обратном хронологическом порядке от Т3 к Т0.

[59] Пусть для записи из вышеописанного примера выполняется условие, что нет ни одной транзакции Tn, для которой выполнялось бы условие Т0<Tn<Т3, то запись можно упростить до следующей: «Hello3»[→«Foo»].

Изобретение относится к вычислительной технике, в частности к способам хранения данных, и может быть использовано в системе управления базами данных (СУБД). Технический результат заключается в повышении производительности СУБД за счет хранения дельт записи вместе с записью. Способ организации хранения исторических дельт записей, в котором формируют, по меньшей мере, одну запись базы данных, которая содержит данные и заголовок; сохраняют сформированную выше, по меньшей мере, одну запись в странично-организованный файл на запоминающем устройстве, в котором каждая страница данных содержит заголовок и область данных для хранения записей; осуществляют модификацию, по меньшей мере, одной записи на странице на запоминающем устройстве; определяют дельту записи, достаточную для восстановления состояния записи до модификации; добавляют определенную на предыдущем шаге дельту записи в упорядоченный набор дельт записи, который хранится как часть записи. 6 з.п. ф-лы, 6 ил., 3 табл.

1. Способ организации хранения исторических дельт записей, включающий следующие шаги:

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

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

- осуществляют модификацию, по меньшей мере, одной записи на странице на запоминающем устройстве;

- определяют дельту записи, достаточную для восстановления состояния записи до модификации;

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

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

3. Способ по п. 1, характеризующийся тем, что осуществляют модификацию записи по запросу пользователя и/или служебной операции СУБД, и/или при выполнении хранимых процедур, и/или при срабатывании триггеров, и/или исполнении определенных пользователем функций (UDF).

4. Способ по п. 1, характеризующийся тем, что при осуществлении модификации записи контролируют соответствие совокупных размеров записей и/или их частей на странице пороговым значениям.

5. Способ по п. 1, характеризующийся тем, что дельта записи содержит атрибут или поле записи и ее старое значение.

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

7. Способ по п. 1, характеризующийся тем, что запоминающим устройством является ОЗУ, и/или ПЗУ, и/или магнитная память, и/или флэш-память, и/или магнитный диск, и/или оптический диск.