СПОСОБ И СИСТЕМА АДАПТИВНОГО УПРАВЛЕНИЯ СВОБОДНЫМ ПРОСТРАНСТВОМ ПАМЯТИ НА ЗАПОМИНАЮЩЕМ УСТРОЙСТВЕ ПРИ РАБОТЕ С БАЗАМИ ДАННЫХ Российский патент 2018 года по МПК G06F12/1009 G06F7/00 

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

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

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

Из уровня техники известны следующие системы управлениями базами данных: Oracle Database, PostgreSQL, Microsoft SQL Server.

Oracle Database или Oracle RDBMS - объектно-реляционная система управления базами данных компании Oracle, в которой реализованы автоматическое и ручное управление табличным пространством

PostgreSQL - объектно-реляционная система управления базами данных (СУБД) с открытым исходным кодом, которая отслеживает и управляет свободным пространством с помощью карты свободного пространства (Free Space Map, FSM).

Microsoft SQL Server - система управления реляционными базами данных (РСУБД), разработанная корпорацией Microsoft. СУБД использует т.н. страницы page free fpace (PFS)) для управления свободным пространством страниц.

Из уровня техники известно US 9519649 B2 «Free space management in a database», патентообладатель International Business Machines Corp., в котором резервируются пространства на страницах для расширения записей и добавления новых. Управление пространством производится с помощью порогов PCTFREE, которые могут быть скорректированы по результатам работы модуля статистики реального времени (real time operating statistics). Способ предполагает хранить только состояние заполненности страницы относительно порогового значения, а не значения метрик заполненности. Из уровня техники известно US 7693875 B2 «Method for searching a data page for inserting a data record», патентообладатель International Business Machines Corp., в котором рассматривается способ группировки таблиц для оптимизации операций вставки. Способ никак не рассматривает метрику и ее изменение в зависимости от собранной статистики.

Из уровня техники известно US 20140279849 A1 «Hierarchical tablespace space management)). Заявлены способ, устройство и система для иерархической организации метаданных табличного свободного пространства в базе данных. Иерархия разделена по меньшей мере на два уровня: блоки битовых карт 1-го уровня или L1 хранятся как общая структура данных и отображают свободное пространство в табличном пространстве, тогда как блоки битовых карт 2-го уровня или L2 хранятся в виде отдельных локальных копий в каждом экземпляре базы данных и карте L1 блоков битовых карт. Интегрируя иерархическую организацию как часть стекового уровня табличного пространства в систему управления базами данных (СУБД), реализации могут быть прозрачно предоставлены конечным пользователям базы данных, не требуя дополнительных административных, эксплуатационных затрат или затрат на разработку.

СУЩНОСТЬ ТЕХНИЧЕСКОГО РЕШЕНИЯ

Данное техническое решение направлено на устранение недостатков, присущих существующим аналогам.

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

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

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

Замена типа метрики может быть произведена СУБД по заданным при создании таблицы правилам.

Замена типа метрики может быть произведена пользователем, обладающим определенными правами доступа.

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

Замена типа метрики может быть произведена СУБД по заданным при создании таблицы правилам.

Замена типа метрики может быть произведена пользователем, обладающим определенными правами доступа.

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

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

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

Фиг. 3 - схема наложения логарифмических и линейных шкал оценки свободного пространства на странице;

Фиг. 4 - система для реализации способа адаптивного управления свободным пространством памяти на запоминающем устройстве при работе с базами данных.

ПОДРОБНОЕ ОПИСАНИЕ ТЕХНИЧЕСКОГО РЕШЕНИЯ

В данном устройстве под системой подразумевается компьютерная система, ЭВМ (электронно-вычислительная машина), ЧПУ (числовое программное управление), ПЛК (программируемый логический контроллер), компьютеризированные системы управления и любые другие устройства, способные выполнять заданную, четко определенную последовательность операций (действий, инструкций).

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

Устройство обработки команд считывает и выполняет машинные инструкции (программы) с одного или более устройства хранения данных. В роли устройства хранения данных могут выступать, но, не ограничиваясь, жесткие диски (HDD), флеш-память, ПЗУ (постоянное запоминающее устройство), твердотельные накопители (SSD), оптические приводы.

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

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

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

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

Запоминающее устройство, ЗУ - устройство, предназначенное для записи и хранения данных.

Страницы запоминающего устройства - блоки фиксированного размера, на которые делится память ЗУ.

Метрика - мера, позволяющая получить численное значение некоторого свойства объекта, в том числе объекта БД и СУБД.

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

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

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

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

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

Актуализируют значение метрики при каждом обращении на запись к странице.

Рассмотрим практические примеры использования способа на основе частных случаев:

1) Пусть некая СУБД имеет порог заполнения страницы (fill factor) равный 75% от размера страницы, все страницы превышающий этот порог помечаются в соответствующей битовой карте как занятые.

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

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

2) Пусть на метрику заполненности выделено по четыре бита на страницу, тогда метрика будет соответствовать следующей таблице:

Затем, по мере наполнения страниц и сбора статистики, если среднее значение длины записи меньше погрешности метрики в оценке свободного пространства, то для вновь создаваемых страниц метрику меняют на заранее определенную таким образом, чтобы точнее указывать размер свободного пространства на странице. Примером такого изменения может служить логарифмическая метрика. Изменения отображают в типе метрики. На Фиг. 1 изображены страницы с данными (101, 102, 103), которым поставлены (106, 107, 108) в соответствия значения (111, 112, 113) линейной метрики (105), значения хранятся в массиве (104). Страница 102 не имеет (112) но текущей метрике свободного пространства.

3) Пусть для ситуации описанной в 1) собрана статистика о среднем размере записи в 15% от страницы, тогда вновь создаваемые страницы вместо описанной в 2) линейной метрики будут использовать логарифмическую. Пусть это будет безопасное логарифмическое представление по основанию 2:

sign(x) * 1b(1+abs(x))

Тогда метрика этого типа будет соответствовать следующей таблице:

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

На Фиг. 2 изображены страницы с данными (201, 202, 303), которым поставлены (206, 207, 208) в соответствия значения (211, 212, 213) логарифмической метрики (205), значения хранятся в массиве (204).

Странице 202 поставлено значение (212), описывающее, что не менее 1/8 страницы свободно.

4) Пусть для ситуации описанной в 2) и 3) в ходе эксплуатации собрана статистика о среднем размере записи в 10% от размера страницы. Тогда значение метрики 3 (занято 87,5%-100% страницы) будет не достаточным и возможно применить для следующих страниц логарифмическую метрику по основанию 4. Тогда:

На Фиг. 3 изображены страницы (301, 311) заполненные в равной мере записями (302, 303, 304, 312, 313, 314). На странице 311 отмечены условные границы (315, 316, 317) значений метрик по линейной шкале при использовании 4 бита на значение. На странице 301 отмечены условные границы (305, 306, 307) значений метрик по логарифмической шкале при использовании 4 бита на значение.

Согласно Фиг. 4, примерная система для реализации технического решения включает в себя устройство обработки данных 400. Устройство обработки данных 400 может быть сконфигурировано как клиент, сервер, мобильное устройство или любое другое вычислительное устройство, которое взаимодействует с данными в системе совместной работы, основанной на сети. В самой базовой конфигурации устройство обработки данных 400, как правило, включает в себя, по меньшей мере, один процессор 401 и устройство хранения данных 402. В зависимости от точной конфигурации и типа вычислительного устройства системная память 402 может быть энергозависимой (например, оперативное запоминающее устройство (ОЗУ, RAM)), энергонезависимой (например, постоянное запоминающее устройство (ПЗУ, ROM)) или некоторой их комбинацией. Устройство хранения данных 402, как правило, включает в себя одну или более прикладных программ 403 и может включать в себя данные 404 программ. Настоящее техническое решение как способ, описанное в деталях выше, реализовано в прикладных программах 403.

Устройство обработки данных 400 может иметь дополнительные особенности или функциональные возможности. Например, устройство обработки данных 400 может также включать в себя дополнительные устройства хранения данных (съемные и несъемные), такие как, например, магнитные диски, оптические диски или лента. Такие дополнительные хранилища проиллюстрированы на Фиг. 4 посредством несъемного хранилища 407 и съемного хранилища 408. Компьютерные носители данных могут включать в себя энергозависимые и энергонезависимые, съемные и несъемные носители, реализованные любым способом или при помощи любой технологии для хранения информации. Устройство хранения данных 402, несъемное хранилище 407 и съемное хранилище 408 являются примерами компьютерных носителей данных. Компьютерные носители данных включают в себя, но не в ограничительном смысле, оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), электрически стираемое программируемое ПЗУ (EEPROM), флэш-память или память, выполненную по другой технологии, ПЗУ на компакт-диске (CD-ROM), универсальные цифровые диски (DVD) или другие оптические запоминающие устройства, магнитные кассеты, магнитные ленты, хранилища на магнитных дисках или другие магнитные запоминающие устройства, или любую другую среду, которая может быть использована для хранения желаемой информации и к которой может получить доступ устройство обработки данных 400. Любой такой компьютерный носитель данных может быть частью устройства 400. Устройство обработки данных 400 может также включать в себя устройство(а) 405 ввода, такие как клавиатура, мышь, перо, устройство с речевым вводом, устройство сенсорного ввода, и так далее. Устройство (а) 406 вывода, такие как дисплей, динамики, принтер и тому подобное, также могут быть включены в состав устройства.

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

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

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

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

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

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

- собирают данные по средней длине записей каждой таблицы;

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

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

- актуализируют значение метрики при каждом обращении на запись к странице.

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

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

4. Система адаптивного управления свободным пространством памяти на запоминающем устройстве при работе с базами данных, содержащая:

- по крайней мере одно устройство обработки команд;

- по крайней мере одно устройство хранения данных;

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

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