|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Pokrovskij 2:5020/400 02 May 2003 20:31:54
To : Vitaly Polikarpov
Subject : Re: Журналирование
--------------------------------------------------------------------------------
> Встраиваемые MCU нередко задействованны в системах управления (в тч и
> реал-таймовых), и для них зачастую важны не только восстановление
> контекста выч.процесса, но и компенсация отклонения состояния объекта
> управления от заданного профиля за recovery time, c учетом предистории
> объекта, нередко (например, для исключения потери управляемости объектом)
> по совершенно иным критериям управления.
Это кажется мне двумя разными задачами. Восстановить контекст (данные) и
установив состояние объекта, подправить контекст так чтобы непотерять
управляемость.
> RP> Можно поискать в Интернете на тему Crash recovery.
> RP> Алгоритм ARIES
> Можно, но эти кейворды "в большом почете" совсем по другим темам ;)
В смысле ? Если сам алогоритм совсем не в тему, то я прошу прощения, я думал
что он хоть чуть-чуть в тему. Если о том, что я слишком краток то я просто
боюсь ужать 20 страниц в нечитабельную кашу. Вот опишу просто требуемую
инфраструктуру. А ты доходчиво расскажи, почему она не применима в embdded.
Т.е. что она в чистом виде не применима понятно, но во-первых можно и
видоизменять, а во-вторых мне будет полезно в терминах embded это услышать.
Я же пока буду в терминах DB, если можно ... иначе запутаюсь.
Есть два типа памяти - защищенная (от crash'ей) и не защищенная (ОЗУ).
Есть база данных, она же набор страничек в защищенной памяти. Есть механизм
переноса странички из защищенной памяти в основную и есть обратный механизм
сохранения странички в защищенную. Перенесенные, измененные странички (но не
сохраненные) называются dirty и учитываются в DIRTY TABLE (при помощи
recLSN - указателя на _первое_ изменение, после которого табличка стала
dirty);
Есть TRANSACTION TABLE где учитываются активные транзакции: id, status(in
progress|commited|aborted) и lastLSN - указателя на последнее изменение в
рамках этой транзации.
DIRTY TABLE и TRANSACTION TABLE это таблички в основной памяти, в случае
crash'а они воссаздаются алгоритмом ARIES.
В защищенной памяти есть журнальный файл и есть хвост журнала (LOGTAIL) в
основной памяти. id записи в журнал называется LSN. LSN уникален и всегда
возрастает, например LSN'ом может быть просто аддресс по которому находится
запись в журнале.
Запись журнала состоит из полей transID, prevLSN (указывает на предыдущию
запись относящуюся к данной транзакиции), type и др.
Типы записей следующие:
1)UPDATing a page - Для UPDATING есть дополнительные поля: pageID, length,
offset, before-image, after-image. Hаличие before-image и after-image нужно
для undo, redo оппераций.
2)Commit
3)Abort - стадия до запуска Undo процедуры
4)End - фиксирует что закончились все действия транзакции начатые после
abort и commit
5)UNDOing an update - фиксирует что произошел откат, сохраняет CLR
(compensation log recorg) CLR это дополнительные поля: undoNextLSN
(следующая запись для Undo), length, offset, before-image
Подчеркну, что изменения страничек нормальным образом фиксируется "UPDATE"
типом, а откат "UNDO". Фактически это оптимизация будующего "crash
recovery" -- восстанавливаемых данных будет меньше.
Sic! если происходит Сrash когда СLR cохранена в защищенную память, а сами
странички DB еще нет, то во время, восстановления, UNDO будет обрабатываться
как UPDATE, заэтим и сохраняется "before image".
Каждая страничка базы данных хранит pageLSN - указатель на последнее
изменение произошедший (LSN именно UPDATE типа).
В общем это вся инфраструктура. Осталось описать протокол ее использования -
WAL (write ahead log). Правило таково:
перед записью странички в защищенную память, все UPDATE записи должны быть
сохраненны. Это достигается полным сохранением LOGTAIL. Фактически
такое происходит всегда по завершению транзакции, а завершенной транзакцией
является та, которой все записи лога (включая commit) успешно сохраненны в
защищенной памяти. Для баз данных хорошим моментом является то, что журнал
проще сохронять поскольку это последовательный файл.
ARIES описывает механизм конрольных точек который помогает уменьшить объем
работ при crash recovery, но мы его опустим.
Этой инфраструктуры полностью достаточно что бы база данных смогла
максимально восстанавиться после любых Crash'ов, в произошедших в любой
фазе, включая саму процедуру Recovery.
P.S. Если это полезно, я могу и далее продолжить, описать процедуру
восстановления.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
