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

Авторы патента:

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

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

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

Известна «схема с одной версией» (https://www.acronis.com/ru-ru/support/documentation/ATIH2013/index.html#10804.html, Последнее изменение: 17.09.2010 13:37:07), в соответствии с которой сохраняется одна новая полная версия блока данных, а при сохранении новой версии блока данных предыдущая версия удаляется.

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

Известна «Схема с цепочкой версий» (https://www.acronis.com/ru-ru/support/documentation/ATIH2013/index.html#10805.html, Последнее изменение: 12.09.2011 18:47:37), в соответствии с которой сохраняются полные версии блока данных и по прошествии установленного периода времени и некоторого установленного минимального количества хранимых версий удаляются наиболее старые версии блока данных.

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

Также известны различные схемы, в которых задается некоторая периодичность сохранения версий блока данных («Примеры пользовательских схем», https://www.acronis.com/ru-ru/support/documentation/ATIH2013/index.html#16448.html, Последнее изменение: 25.11.2011 16:18:54). Такие схемы по сути просто задают периодичность сохранения версий, но не решают проблему занимаемого пространства. В результате, когда общий объем резервных копий превысит некоторую величину (в источнике - 100 Гб), система удаляет резервные копии.

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

в массив версий блока данных сохраняется новейшая версия блока данных;

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

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

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

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

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

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

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

вычислительный узел;

при этом

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

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

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

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

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

в массив версий блока данных сохраняется новейшая версия блока данных;

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

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

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

Фиг. 1 - блок-схема способа резервного сохранения версий блока данных;

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

ВАРИАНТЫ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

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

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

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

В результате определения значений функции длин интервалов мы получаем последовательность длин интервалов а(k), где k=1, 2, 3 … . Областью определения этой функции являются натуральные числа, значения ее аргумента фактически представляют собой порядковые номера интервалов при нумерации по направлению от самых новых версий множества версий блока данных к более ранним версиям. Областью значений функции длин интервалов (последовательности длин интервалов) являются натуральные числа.

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

При этом b(0)=0.

Необходимо понимать, что для удобства иллюстрации сущности изобретения версии блока данных на фигурах чертежей условно обозначаются номерами версий блока данных по порядку их сохранения (от 1 до N), но нумерация интервалов (k) и версий блока данных в агрегирующей последовательности (b(k)) в рамках способа выполняется, начиная от наиболее новой версии к более старой.

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

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

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

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

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

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

То есть, множество версий блока данных разбивается на последовательные интервалы:

[N-b(1)+1, N-b(0)], [N-b(2)+1, N-b(1)], [N-b(3)+1, N-b(2)] … [N-b(k)+1, N-b(k-1)] …

где литерой k=1, 2, 3 … обозначен номер интервала при нумерации от наиболее новой к наиболее старым версиям; N - это количество версий в множестве версий блока данных и номер наиболее новой версии.

Способ в соответствии с настоящим изобретением также включает в себя этап, на котором в случае наличия (6) интервалов, в которых содержится больше хранимых версий блока данных, чем соответствующее значение функции количества оставляемых в интервалах версий, в этих интервалах удаляются (7) версии блока данных таким образом, чтобы в каждом интервале осталось хранимых версий не больше, чем соответствующее значение функции количества оставляемых в интервалах версий. Этап может включать в себя промежуточные этапы и выполняться итеративно: для каждого интервала может выполняться определение количества хранимых версий блока данных до удаления; сравнение значения функции количества оставляемых версий блок данных с количеством хранимых версий блока данных в интервале до удаления; определение хранимых версий блока данных в интервале, подлежащих удалению; удаление версий блока данных, определенных подлежащими удалению. Удаление и предшествующие ему логические и/или математические операции могут выполняться вычислительным узлом, который выполнен с возможностью чтения и обработки информации, хранимой на узле сохранения данных. Непосредственно удаление версий блока данных на носителях может осуществляться узлом сохранения данных при поступлении соответствующих управляющих команд от вычислительного узла.

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

Выполнение способа резервного сохранения версий блока данных завершается (8) после выполнения удаления (7) версий или после отрицательного результата проверки (6).

Критерием эффективности способа сохранения является характер функции E(N), которая равна количеству сохраненных версий после N последовательных итераций способа сохранения (при последовательном добавлении версий 1, 2 … N).

Из условия положительности и монотонного возрастания последовательности а(k) при k=1, 2, 3 … следует:

а(k)≥k

Отсюда следует ограничение на b(k):

Допустим, числу версий N соответствует m покрывающих интервалов (то есть N версий разобьются на m интервалов в соответствии с логикой способа). Тогда из условия построения интервалов следует, что:

b(m-1)<N

Следовательно (учитывая полученное ранее ограничение на b(k)):

Так как количество версий E(N) не превосходит удвоенного количества интервалов (по условию алгоритма), то:

Таким образом получаем, что E(N)=o(N). Запись f(n)=o(g(n)) читается как последовательность f(n) является о-малым от другой последовательности g(n), что в свою очередь означает, что отношение последовательностей f(n)/g(n) стремится к нулю при n стремящемся к бесконечности. Здесь символ о-малое является обозначением бесконечно малой функции. Определение бесконечно малой функции известно из математики (например, Основы математического анализа. В 2-х ч. Ильин В.А., Позняк Э.Г. М.: Физматлит. Ч. 1 - 2005, 7-е изд., 648 с., страница 109 и остальные). Интуитивно это нужно понимать, что значения f(n) становится все меньше и меньше в проценте от g(n) при n стремящемся к бесконечности. Поэтому с ростом n можно пренебречь функцией f(n) по сравнению с g(n) в ряде случаев.

Это является обоснованием асимптотической эффективности алгоритма. Под асимптотической эффективностью следует понимать следующее. Алгоритм является асимптотически эффективным, если функция отношения количества физически оставляемых версий ко всем версиям стремится к нулю при стремлении общего количества версий к бесконечности. В терминах о-малого эквивалентное определение асимптотической эффективности: E(N)=o(N), где N - количество версий, E(N) - функция количества физически не удаленных версий.

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

В данном варианте осуществления предварительно была определена (установлена, задана) функция длин интервалов, имеющая вид:

а(k)=2^k-1+1

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

То есть в ходе выполнения способа определяются следующие значения функции длин интервалов

{а(k)}=2, 3, 5, 9, 17 …

Функция количества оставляемых версий в данном варианте осуществления определяется как

V(k)=2,

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

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

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

{b(k)}=2, 5, 10, 19, 36 …

b(m-1)<N

Следовательно:

Так как m≥1, то из вышезаписанного неравенства следует:

Так как Е(N)≤2m:

Так, мы получили зависимость количества сохраненных версий E(N) (а, следовательно, и занимаемой для хранения истории памяти) от глубины истории версий N.

Ниже приведен пример кода на Python алгоритма, реализующего способ резервного сохранения данных. Через функцию calc_В происходит подготовка алгоритма. Функция process state выполняет итерацию алгоритма и изменяет переданный ей в качестве аргумента список state, состоящий из 0 и 1. Последовательность элементов в списке соответствует последовательности версий, начиная с самой старой. 0 означает, что данная версия удалена и более не хранится в истории, 1 - версия физически существует и может быть использована.

На фиг. 2 показана работа способа в приведенном варианте осуществления в динамике. Способ выполняется для первой версии (номер 1), потом добавляется версия 2, далее - 3, и т.д. При каждом добавлении новой версии запускается итерация способа, и, если решается удалить какую-либо версию блока данных, она она удаляется, при этом ее номер заменяется на фиг. 2 на точку. Вертикальными чертами отмечены засечки, в соответствии с которыми алгоритм разбивает историю версий на интервалы. Можно увидеть, что как только в какой-либо интервал попадает более двух (2 значение функции количества оставляемых версий) версий, выполняется удаление версий в интервале, кроме двух (в представленном варианте осуществления - двух крайних).

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

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

Функция длин интервалов может быть предварительно определена (задана, установлена). Определение функции может быть выполнено путем задания этой функции вручную в наборе инструкций, под управлением которых вычислительный узел определяет значения функций; а также в ходе настройки работы алгоритма путем введения функции или ее значений через какой-либо интерфейс.

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

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

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

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

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

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

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

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

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

Машиночитаемый носитель, а также узел сохранения данных, могут каждый представлять собой любой пригодный носитель, к которому система или вычислительный узел могут осуществить доступ, причем такой носитель может включать в себя как энергозависимый, так и энергонезависимый носитель, а также съемный и несъемный носитель. В качестве примера, но не ограничения, машиночитаемый носитель или узел сохранения данных, могут содержать компьютерную запоминающую среду и среду связи. Компьютерная запоминающая среда включает в себя как энергозависимый, так и энергонезависимый, съемный и несъемный носитель, реализованный любым способом или по любой технологии, используемой для хранения такой информации, как машиночитаемые инструкции, структуры данных, программные модули или другие данные. Компьютерная запоминающая среда включает в себя, но не только, ОЗУ (RAM), ПЗУ (ROM), электрически стираемое программируемое ПЗУ (EEPROM), флэш-память либо другую технологию памяти, компакт-диск (CD-ROM), цифровой универсальный диск (DVD) либо другие оптические дисковые запоминающие устройства, магнитные кассеты, магнитную ленту, магнитное дисковое запоминающее устройство либо другие магнитные запоминающие устройства или любой другой носитель, который можно использовать для хранения требуемой информации и к которому система или устройство может осуществить доступ. Среда связи обычно воплощает машиночитаемые инструкции, структуры данных, программные модули или другие данные в модулированном сигнале данных, таком как сигнал несущей иди другой механизм транспортировки, и включает в себя любую среду для доставки информации. Термин «модулированный сигнал данных» означает сигнал, одна или несколько характеристик которого устанавливается или изменяется таким образом, чтобы закодировать информацию в этом сигнале. В качестве примера, но не исключения, среда связи включает в себя проводную среду, такую как проводная сеть или прямое проводное соединение, а также беспроводную среду, такую как акустическая, радиочастотная, инфракрасная и другая беспроводная среда. В состав машиночитаемых носителей и/или узла сохранения данных могут быть также включены комбинации из любых вышеуказанных носителей (сред).

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

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

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

в массив версий блока данных сохраняется новейшая версия блока данных;

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

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

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

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

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

при этом

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

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

в массив версий блока данных сохраняется новейшая версия блока данных;

Похожие патенты: