что такое персистентность в программировании

Персистентность — Веб-разработка на PHP

Среди сайтов выделяют такую категорию, как «статические». Их особенность в том, что такие сайты по сути представляют собой готовый набор HTML-страничек. Например, так сделаны наши руководства на https://guides.hexlet.io/. Удобно, быстро, дёшево. Статическим сайтам не нужно куда-то сохранять информацию, его данные хранятся прямо в HTML.

Для создания статических сайтов используют специальные генераторы сайтов, например, https://jekyllrb.com/

Остальным сайтам повезло меньше. Все что создаётся пользователем, нужно куда-то сохранять. Самый простой способ сохранять — использовать файлы. Насколько он простой, настолько же нерабочий. Блокировки файловой системы не позволят работать с файлом в конкурентной среде, какой является веб, когда с сайтом могут одновременно работать сотни тысяч пользователей.

Здесь мы снова приходим к необходимости понимать устройство операционных систем. https://ru.hexlet.io/pages/recommended-books

персистентность — возможность долговременного хранения состояния

Для постоянного (персистентного) хранения данных принято использовать специализированные программы — базы данных. Взаимодействие с ними строят двумя способами. Либо работая напрямую через библиотеку, предназначенную для данной базы данных. Либо через ORM, которая в большинстве случаев прячет базу данных за горой абстракций.

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

Открыть доступ

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

Наши выпускники работают в компаниях:

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

Источник

Персистентность

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

Это достигается путем хранения состояния как данных на устройстве длительного хранения, таком как жесткий диск или флэш-память.

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

Ортогональная или прозрачная персистентность

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

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

Способы реализации персистентности

Образы системы

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

Журналы

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

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

Журналы используются журнальными файловыми системами и СУБД, где они также называются логами транзакций или логами повторных действий.

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

Превалентность системы

Недостатки: Превалентна система должна иметь достаточно оперативной памяти для размещения всего состояния системы.

«Грязная» запись

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

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

Уровни персистентности

Любой уровень программного обеспечения (software layer), что помогает программе сохранить состояние, обобщенно называется уровнем персистентности. Большинство уровней персистентности не достигают персистентности непосредственно, а используют основную СУБД.

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

Персистентные операционные системы

Источник

Что такое персистентность в программировании

Некоторое время назад я наткнулся на персистентные структуры данных и, в частности, на описание персистентной очереди на вики-конспектах ИТМО. Всё бы хорошо, только как-то сложновато: чтобы реализовать одну маленькую очередь используется пять (в другом варианте — шесть) стеков.

Персистентность

Персистентность для структуры данных — возможность хранить несколько версий сразу. Другими словами, каждая изменяющая операция (например, у структуры данных «стек» есть операции push и pop) не меняет саму структуру, а возвращает новую стуктуру данных (обычно в виде ссылки на новую версию), в которой хранится то, что должно было появиться в старой после этой операции. Это эквивалентно тому, что можно (быстро) скопировать структуру данных целиком, а потом уже выполнять всякие операции.

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

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

Ловкость лап и дерево отрезков позволяют придумать структуру данных «персистентный массив» с операциями «увеличить длину массива на один» и «изменить элемент», однако каждая такая операция будет выполняться за O(log) (логарифм длины массива). Поскольку любую структуру данных можно представить как изменение каких-то значений на массиве, то казалось бы, любую структуру данных можно персистенизировать с добавлением лишнего O(log) в асимптотике. Однако не всё так просто (впрочем, это позволяет из очереди на массиве сделать персистеную очередь с O(log) на операцию).

Персистентная очередь

Как известно, очередь легко реализовать с помощью двух стеков: из одного забираем элементы, в другой кладём, при необходимости берём и перекидываем все элементы из второго в первый. Заменив оба стека на персистентные получается персистентная очередь, так зачем в статье на вики-конспектах сложности с шестью стеками? Дело в том, что можно реализовать очередь через два стека, это даст оценку O(1) на операцию, но эта оценка — амортизированная. А персистенизация, к сожалению, не сохраняет амортизированные оценки.

Четыре стека

Первый стек ( main ) будет хранить просто все элементы, которые когда-либо добавлялись в очередь. Операция put будет добавлять элемент в main (а потом пересчитывать какие-нибудь счётчики и делать нечто).

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

Чтобы не случилось так, что элементы брать неоткуда, нужен ещё один стек ( help2 ). В нём будут некоторые элементы очереди, он будет расти и когда help закончится (или раньше) придёт на замену.

Чтобы выращивать стек help2 нужна (внимание) персистентная копия стека main, из которой мы будет брать элементы и перекидывать элементы в help2. Эта копия у меня называется main2.

Выглядит это всё примерно так:

Ну а нечто стало быть должно делать следующее:

Ещё следует доказать, что не будет ситуации, когда очередь не пуста, а стек help пуст, но я оставлю это читателю. У себя ВКонтакте я выкладывал код, который у меня получился на эту тему.

Минусы

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

Первый минус — это использование памяти. Если извне есть информация, что использовать надо не все версии, а только какие-то конкретные, то можно собирать мусор и экономить память. У меня же старые элементы так и будут висеть в хвосте main.

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

Источник

Персистентность

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

Это достигается путем хранения состояния как данных на устройстве длительного хранения, таком как жесткий диск или флэш-память.

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

Ортогональная или прозрачная персистентность

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

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

Способы реализации персистентности

Образы системы

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

Журналы

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

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

Журналы используются журнальными файловыми системами и СУБД, где они также называются логами транзакций или логами повторных действий.

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

Превалентность системы

Недостатки: Превалентна система должна иметь достаточно оперативной памяти для размещения всего состояния системы.

«Грязная» запись

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

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

Уровни персистентности

Любой уровень программного обеспечения (software layer), что помогает программе сохранить состояние, обобщенно называется уровнем персистентности. Большинство уровней персистентности не достигают персистентности непосредственно, а используют основную СУБД.

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

Персистентные операционные системы

Источник

Персистентные структуры данных

Содержание

Уровни персистентности [ править ]

Есть несколько уровней персистентности:

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

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

Конфлюэнтные структуры данных позволяют объединять две структуры данных в одну (деревья поиска, которые можно сливать).

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

Способы преобразования структур данных в персистентные [ править ]

Есть несколько способов сделать любую структуру персистентной:

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

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

Метод копирование пути [ править ]

Так как рассматривается сбалансированное дерево поиска, то поднимая вершину вверх при балансировке, нужно делать копии всех вершин, участвующих во вращениях, у которых изменились ссылки на детей. Таких всегда не более трех, поэтому ассимптотика [math]O[/math] [math]( \log n)[/math] не пострадает. Когда балансировка закончится, нужно дойти вверх до корня, делая копии вершин на пути.

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

Реализация на основе дерева отрезков [ править ]

На основе дерева отрезков можно построить полностью персистентную структуру данных.

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

Метод «толстых» узлов [ править ]

Преобразование списка в персистентный за O(1) [ править ]

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

Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, изменять можно только ее последнюю версию. Примем функцию потенциала [math]\Phi[/math] равной числу полных узлов в последней версии.

Общий метод построения частично персистентных структур данных [ править ]

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

Получение полностью персистентных структур данных [ править ]

Для полностью персистентных структур данных применить описанный выше метод преобразования не получится, так как история создания версий не линейна и нельзя отсортировать изменения по версиям, как в частично персистентных структурах данных. Пусть мы храним историю изменения версий в виде дерева. Сделаем обход этого дерева в глубину. В порядке этого обхода запишем, когда мы входим, а когда выходим из каждой версии. Эта последовательность действий полностью задает дерево, сделаем из нее список. Когда после какой-то версии (на рисунке ниже это версия [math]6[/math] ) добавляется новая версия структуры данных (на рисунке версия [math]8[/math] ), мы вставляем два элемента в список (на рисунке это [math]+8[/math] и [math]-8[/math] ) после входа, но до выхода из той версии, когда произошло изменение (то есть между элементами [math]+6[/math] и [math]-6[/math] ). Первый элемент вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.

В change log «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в change log не по номерам версий, а по их порядку в списке версий List Order Maintenance.

В какой-то момент change log «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в change log склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.

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

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

Персистентные структуры данных используются при решении геометрических задач. Примером может служить Point location problem — задача о местоположении точки. Задачи такого рода решаются в offline и online. В offline-задачах все запросы даны заранее и можно обрабатывать их одновременно. В online-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.

При решении offline-задачи данный планарный граф разбивается на полосы вертикальными прямыми, проходящими через вершины многоугольников. Затем в этих полосах при помощи техники заметающей прямой (sweep line) ищется местоположение точки-запроса. При переходе из одной полосы в другую изменяется сбалансированное дерево поиска. Если использовать частично персистентную структуру данных, то для каждой полосы будет своя версия дерева и сохранится возможность делать к ней запросы. Тогда Point location problem может быть решена в online.

Источник