Нерушимая память, нерушимые процессы

Прочитав недавно (1 ^[1], 2 ^[2], 3 ^[3]) с каким трудом даются “космические” процессоры, невольно задался мыслью, раз “цена” за устойчивое железо настолько высока, может быть стоит сделать шаг и с другой стороны — сделать устойчивый к спецфакторам “софт”? Но не прикладной софт, а скорее среду его выполнения: компилятор, ОС. Можно ли сделать так, чтобы выполнение программы в любой момент можно было оборвать, перезагрузить систему и продолжить с того же (или почти с того же) места. Существует же в конце концов гибернация ^[4].

Радиационные эффекты

Почти всё, что прилетает из космоса, способно нарушить работу микросхемы, дело лишь в количестве энергии, которое “это” принесло с собой. Даже фотон, если у него длина волны гамма-кванта, способен преодолеть несколько сантиметров алюминия и ионизировать атом(ы) или даже вызвать ядерный фотоэффект ^[5]. Электрон не может проникнуть через сколь-нибудь плотное препятствие, но, если его разогнать посильнее, при торможении испустит гамма-квант со всеми вытекающими последствиями. Учитывая, что период полураспада у свободного нейтрона около 10 минут, редкий (и очень быстрый) нейтрон долетает к нам от Солнца. А вот ядра всего чего угодно долетают и тоже способны натворить дел. Нейтрино разве что не замечены ни в чем подобном.

Как тут не вспомнить Пятачка с его: “трудно быть храбрым, когда ты всего лишь Очень Маленькое Существо”.

Последствия попадания космического излучения в полупроводник могут быть разными. Это и ионизация атомов и нарушение кристаллической решетки и ядерные реакции. Вот здесь ^[6] описывается легирование кремния тепловыми нейтронами в атомном реакторе, когда Si(30) превращается в P(31), при этом достигаются нужные полупроводниковые свойства. Не стоит пересказывать упомянутые замечательные статьи, отметим лишь следующее —

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

Отметим, что эффекты 2 и 3 типов, если их удалось купировать, приводят к постепенной деградации микросхемы. Например, если в суперскалярном процессоре “выгорел” один из (пусть 4) сумматоров, можно (по крайней мере умозрительно это не трудно) пострадавшему физически отключить питание и пользоваться оставшимися тремя, внешне будет заметно лишь падение производительности. Аналогично, если поврежден один из регистров внутреннего пула, он может быть помечен как “вечно-занятый” и не сможет участвовать в планировании операций. Блок памяти может стать недоступным. … Но вот если испортилось нечто невосполнимое, придётся поднимать холодный резерв. Если он есть.

«Пребывание в холодном резерве не предохраняет кстати микросхему от накопления дозы, и даже от накопления заряда в подзатворном диэлектрике. Более того, известны микросхемы, у которых дозовая деградация без подачи питания даже хуже, чем с ней. А вот все одиночные эффекты, вызывающие жесткие отказы, требуют включенности микросхемы. При отключенном питании могут быть эффекты смещения, но они для цифровой логики не важны». (amartology ^[7])

Таким образом действуют два фактора

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

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

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

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

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

Стоит упомянуть про подход, который называется Lock-step ^[8], когда два ядра выполняют одну и ту же задачу со сдвигом в один-два такта, и после этого результаты сравниваются. Если они не равны — какой-то кусок кода пере-выполняется. Это не срабатывает при ошибке в памяти или общем кэше, впрочем, там есть своя защита.

Также есть подход ^[9], где компилятор повторяет выполнение части команд и сравнивает результаты. Такой софтовый вариант Lock-step.

Оба этих подхода (спасибо amartology ^[7] за наводку) — попытка обнаружить сбой и попытаться исправить его “малой кровью”, без перезагрузки. Мы же далее скорее будем рассматривать ситуацию, когда произошел серьёзный сбой или некритичный отказ и перезагрузка неизбежна. Как сделать, чтобы программу без особых усилий с её стороны можно было прервать в любой момент, а потом продолжить без серьёзных потерь.

Как научить железо и ОС адаптироваться к постепенной деградации — тема для отдельного разговора.

А что если.

Сама по себе идея устойчивой/персистентной памяти не нова, вот и уважаемый Дмитрий Завалишин (dzavalishin ^[10]) предложил свою концепцию персистентной памяти ^[11]. В его руках это породило целую персистентную ОС “Фантом” ^[12], фактически виртуальную машину с соответствующими накладными расходами.

Возможно, со временем созреют технологии MRAM ^[13] или FRAM ^[14], … пока они сырые.

Существует также легенда про бортовой вычислитель ракеты Р-36М ^[15] (15Л579 ?), которая умела стартовать сквозь радиоактивное облако непосредственно после близкого ядерного взрыва. Примененная память на ферритовых сердечниках невосприимчива к радиации. Цикл записи у такой памяти порядка единиц мксек ^[16], так что за время, пока ракета летит считанные дециметры, была физическая возможность сохранить контекст работы процессора — содержимое регистров и флагов. Проснувшись в безопасной обстановке, процессор продолжал работу.
Звучит правдоподобно.

Есть некоторые “но”:

1. Гибернация в существующем виде не годится т.к. требует определенных усилий и времени. Мы же стараемся защититься от внезапного сбоя. Не очевидно что после этого сбоя процессор физически в состоянии сделать хоть что-нибудь. Аналогично и в 15Л579, система получает предупреждение до того, как начались неприятности и имеет время на предохранение от них.
2. ОС “Фантом” задумана как смена парадигмы программирования — больше нет никаких дисков, есть сколько угодно памяти, пиши в неё — никуда не денется. В нашем случае революции не планируются, хочется оставить всё (почти) как было раньше, но чтоб персистентно было.
3. Расходы на персистентность желательно сделать явными, управляемыми прикладным программистом, а не получаемыми наложенным платежом. А если программист не предпринимает никаких усилий — всё остаётся по-прежнему.

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

Для начала о том, как это должно выглядеть со стороны прикладного программиста.

Взгляд извне ядра ОС

Раз восстановление после сбоев аналогично восстановлению после выброса исключения, то и работа с ним может выглядеть аналогично. Например, в С++ наследуем от std::exception класс std::tremendous_error, ловим его в обычном блоке try/catch и организуем обработку.

Впрочем, автору больше нравится семантика setjmp ^[17]/longjmp ^[18] (SJLJ) т.к.:

• это лаконично, просто вызываем аналог setjmp(&buf) и возобновляем работу с того же места
• даже никакой “&buf” не требуется, просто вызов системной функции, сохраняющей текущее состояние
• кроме С++ существуют и другие замечательные языки, не везде есть обработка исключений, но везде есть вызов системных функций
• да и незачем модифицировать язык, мы ведь изначально собирались действовать как можно менее инвазивно

В своё время SJLJ проиграла ^[19] технике DWARF ^[20] (строго говоря, dwarf это просто формат записи информации) в обработке исключений из-за худшей производительности, здесь производительность не столь важна. В любом случае сохранение состояния не будет дешевым, надо подходить к нему ответственно.

Взгляд изнутри ядра ОС

Что требуется сохранить, из чего состоит контекст выполнения процесса?

1. Для каждого потока, находящегося в пользовательском режиме — текущий “jmp_buf” с нужными регистрами, это означает что ОС должна остановить все потоки вызвавшего процесса перед сохранением данных
2. Для каждого потока, ждущего завершения блокирующего системного вызова — параметры этого вызова. Часть этих вызовов при восстановлении можно будет перезапустить (ех: ожидание внутрипроцессного мутекса), для остальных придётся вернуть ошибку (ex: чтение из сокета).
3. Список и состояние созданных процессом объектов ядра. Часть из них при восстановлении возможно воссоздать (ex: открытый файловый дескриптор), некоторые нет (ex: установленное TCP соединение). Отдельно отметим потоки как объекты ядра со всеми их атрибутами.
4. Карту виртуальной памяти, информацию о каждом выделенном сегменте. Не требуется записывать её каждый раз, но для восстановления потребуется её актуальное состояние
5. Снимок данных. Поскольку после сбоя состояние оперативной памяти станет неадекватным, содержимое памяти должно быть сохранено. Логично использовать то, что именно для этого и предназначено — механизм подкачки. Т.е. все измененные с момента последней записи состояния страницы должны быть записаны.

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

6. Информация, необходимая для сопоставления виртуального адреса с местом страницы на диске.

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

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

Из всего вышеперечисленного наибольшие вопросы вызывает именно сохранение содержимого памяти, объем всего остального по сравнению с этим незначителен.
Например, runtime ^[21] библиотека буферизирует выделения памяти, просит их у системы относительно большими кусками и сама занимается раздачей. Поэтому созданий/удалений сегментов относительно немного.

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

Сохранение содержимого памяти.

Желаемое поведение близко к базам данных — СУБД в любой момент может “упасть”, но проделанная работа сохранится вплоть до последнего коммита. Достигается это за счет ведения лога транзакций, попадание в который записи о коммите легализует все изменения, сделанные в транзакции.
Но, поскольку термин “транзакционная память ^[22]” занят, мы введем другой — “нерушимая память”.

Навскидку видны два метода, которыми эту нерушимую память можно реализовать

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

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

Однако, в таком режиме невозможно, например, выделить calloc ^[23]-ом массив размером больше доступной памяти (malloc ^[24]-ом, кстати, можно). Впрочем, это в любом случае была бы не очень хорошая идея.

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

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

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

Вариант второй, “теневой”
Чтобы действовать как менеджер транзакций, нужно быть менеджером транзакций.
Определимся с сущностями:

1. Файл подкачки содержит страницы данных, поэтому размер кратен размеру страницы. Мы говорим файл, подразумеваем скорее раздел, т.к. фиксированный размер способствует повышению стабильности системы.
2. Аллокатор страниц файла подкачки. Нужен для выделения страницы не только под пользовательские данные, но и, например, для записи состояния самого аллокатора. А также всего того, что было упомянуто выше.
3. Лог транзакций. Сюда попадают все изменения, которые должны быть атомарными в масштабах своих транзакций. Начинается транзакция с записи записи, прошу прощения за каламбур,
   (тег=старт транзакции, номер процесса).
4. Реестр памяти. Логически — это упорядоченный массив записей
   • ID процесса
   • Виртуальный адрес
   • Сдвиг от начала сегмента (в страницах)
   • ID первой страницы в файле подкачки.

   Реестр памяти расположен где-то недалеко от TLB ^[25], т.к. информация в них частично перекрывается.

   С точки зрения производительности было бы хорошо иметь для сегментов (по возможности) непрерывные области в файле подкачки. Хорошо и с точки зрения производительности и с точки зрения компактности реестра памяти. Но для этого придётся прибегнуть к аллокатору страниц не склонному к фрагментации, ex: методу близнецов (Buddy Allocator ^[26]) и заплатить за это перерасходом дискового пространства.

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

5. Теневые ^[27] страницы. В отличие от СУБД мы не знаем что конкретно изменилось в странице памяти и потому вынуждены применять COW ^[28] (copy on write) для всей страницы. При рождении сегмента памяти, рождается и номер каждой страницы из этого сегмента. Но когда происходит COW, мы приписываем странице какой-то новый номер, который не может быть получен из реестра памяти ибо там хранится номер оригинальный. Поэтому нам нужен механизм связи между старыми и новыми номерами страниц.

   Стоит отметить — пока программа просто меняет что-то в памяти, ничего не происходит кроме аппаратного взведения у измененных страниц флага “dirty ^[29]”. Необходимость в порождении теневой страницы возникает лишь при вытеснении её в файл подкачки.

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

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

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

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

   Коммит транзакции порождает запись в логе транзакций
   (тег=коммит, номер транзакции). Эту запись можно считать атомарной операцией.

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

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

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

7. Общий рекодер. Теневая страница, чей номер попал в общий рекодер, становится новой нормой — именно её содержимое будет далее считаться достоверным при восстановлении после сбоя. Но как поступить со старой страницей и что делать, если эту же страницу изменят в другой транзакции?

   Самое простое и неправильное решение — давайте просто освободим старую страницу а информацию о новой внесём в реестр памяти. Общий рекодер в данном случае вообще не нужен, его функцию будет исполнять реестр памяти. Решение неправильное, потому что приведёт к тотальной фрагментации файла подкачки. Ранее мы голосовали за непрерывные интервалы страниц для сегментов, про это можно забыть т.к. очень быстро число интервалов сегмента будет равно числу страниц.
   Можно сказать — подумаешь, в наш век SSD дисков фрагментация больше не имеет значения! На самом деле, непрерывное чтение и для SSD дисков (пусть и не настолько драматично как для “дисковых” дисков) заметно быстрее чтения с произвольным доступом.
   Кроме того, распухнет реестр памяти и работа с ним изрядно замедлится.

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

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

8. Checkpoint.
   Итак, на данный момент у нас есть всё, чтобы восстановить после сбоя корректное состояние реестра памяти, аллокатора страниц, рекодера и собственно данных. Есть одна проблема — неограниченный рост размера лога. Это выливается еще и в то, что на восстановление будет требоваться всё больше и больше усилий. Чтобы решить эту проблему в СУБД существует механизм checkpoint ^[30]. Он фиксирует текущее актуальное состояние всех сущностей и обнуляет лог транзакций.

   Сложности две. Первая. Надо что-то делать с активными на момент checkpoint-а транзакциями. Разберем на примере.

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

   И вот наступает момент checkpoint-а. И реестр памяти и аллокатор страниц должны сериализовать своё актуальное состояние без учета открытых транзакций, иначе после вероятного сбоя/восстановления возникнет утечка.
   По-видимому, и реестр памяти и аллокатор страниц должны каким-то образом помечать захваченные/освобожденные, но не подтвержденные коммитом ресурсы. Это же касается и других хранителей ресурсов, которые появятся (объектов ядра...). Теперь для сохранения актуального состояния нет преград.

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

Хранение файла подкачки и лога транзакций.

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

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

Ранее упоминалось, что для работы с ненадёжными элементами используется троирование, здесь достаточно RAID1 ^[32] т.к. при ошибке записи благодаря контрольным значениям известно какая из двух страниц записалась некорректно и подлежит перезаписи.

Итого.

Ну вот, теперь у нас на руках все четыре буквы слова ACID ^[33].
A — атомарность, достигнута
C — согласованность, налицо
I — изоляция, достигается естественным образом. Если не рассматривать случай разделяемой памяти. А мы на данный момент его не рассматриваем.
D — стойкость, единственный раз мы попытались смухлевать, когда отпустили процесс после коммита не дожидаясь физической записи на диск всех данных его памяти. В худшем случае это приведёт к откату на предыдущую транзакцию. Непонятно, насколько это критично, и для производительности и для стойкости.

PS. Просто на заметку. У нас не предусмотрен механизм отката транзакций, откатом может быть только неустранимая ошибка работы. Технически (кажется) нетрудно реализовать программный откат транзакции как аналог longjmp. Но это гораздо более продвинутый вариант longjmp т.к. полностью восстанавливает внутреннее состояние процесса на момент “setjmp”, не допуская утечек памяти, разрешает переход не только снизу вверх по стеку …

PPS. Прототипом менеджера транзакций, пожалуй, можно считать DBMS сервер OpenLink Virtouso ^[34], доступный и как free software.

PPPS. Спасибо Валерию Шункову (amartology ^[7]) и Антону Бондареву (abondarev ^[35]) за содержательное и весьма полезное обсуждение.

PPPPS. Автор иллюстрации Анна Русакова ^[36].

Автор: Борис Муратшин

Источник ^[37]