Введение в семейство алгоритмов Gossip (1/4)

#shark_whitepaper

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

Семейство протоколов gossip — это специфичный набор алгоритмов по обмену данными в сети узлов. Идея в следующем: пусть каждый узел раз в промежуток времени находит один из случайных соседних узлов и направляет ему некоторое сообщение. Так делает каждый узел, который уже получил обновления. Когда все узлы направили сообщение, завершается первый раунд обмена. Раунды проходят до тех пор, пока обновление «не потеряет актуальность». Сообщения содержат не только полезные данные, но и информацию о сети, которой обладает узел. Если проще — каждая нода направляет список соседей, о которых знает она сама. Если долго передавать такую информацию, рано или поздно все ноды сети будут знать о существовании всех узлов. Удобно. В некоторых вариантах gossip информация о других нодах сети — это и есть вся полезная нагрузка.

Киллер фича алгоритмов именно в случайном выборе соседней ноды. Именно случайность позволят gossip алгоритму работать даже при отказах значительной части сети. Почему используется слово «протокол», а не «алгоритм» определить сложно. Возможно это связано с тем, что исторически gossip использовался как низкоуровневый подход для обнаружения топологий в огромных сетях. Сетевики вообще любят всё вокруг называть протоколами.

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

- Периодический, попарной обмен данными между узлами сети.
- При обмене данных передаётся небольшое количество информации. Gossip протокол в идеальном мире не должен съедать всю пропускную способность сети.
- Обмен данными происходит редко. «Редко» в данном случае значит сильно реже чем средние задержки (latency) в сети. Идеальный gossip не создаёт значимой нагрузки на сеть узлов. Это позволяет использовать gossip, как дополнение к другим алгоритмам обмена данными.
- Надежный канал связи не требуется. Более того, новые узлы могут вступать в сеть даже во время работы алгоритма.
- При взаимодействии между узлами A и B, либо один из них, либо оба сразу меняют своё состояние. Кинуть пинг другому узлу это ещё не gossip.
- Соседние ноды выбираются случайным образом. В идеальном мире с равномерно распределенной вероятностью. В реальности правда достичь её всё равно не удастся, об этом тоже ниже.
- Время распространения обновления по всем узлам сопоставимо с O(log(n)).

Обмен данными между случайными нодами приводит к тому, что gossip протоколы дают только вероятностью консистентность. Здесь речь идёт не столько о вероятности того, что система перейдёт в консистентное состояния, сколько о времени, когда это произойдет — большинство вариаций практически гарантированно смогут распространить данные по сети когда-нибудь. В случае с gossip консистентность можно объяснить фразой на подобии «с вероятностью 99%, через 30 раундов каждая нода в сети получит обновления». Так сказать, how eventual is eventually consistent?

Введение в семейство алгоритмов Gossip (2/4)

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

Работать алгоритмы могут не только в push режиме, когда ноды направляют свои сообщения соседям, но также и в pull, когда узлы наоборот «затягивают» сообщения от соседей. Может быть также и pull-push модель, когда один узёл делает и то, и другое. Очень упрощенно, алгоритм выглядит так:

Активный тред:
1. Выбрать соседний узел
2. Если push
    2.1. выбрать сообщения для отправки
    2.2. направить в выбранный узел
3. Если pull 
    3.1. получить сообщения от узла
    3.2. обработать сообщения

Пассивный тред:
1. Получить сообщение
2. Если pull
    2.1. выбрать сообщения для отправки
    2.2. направить в выбранный узел
3. обработать сообщения.

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

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

Введение в семейство алгоритмов Gossip (3/4)

Для решения всех этих проблем часто используется абстракция под названием peer sampling service. Идея такая: давайте хранить только некое число c «соседних узлов». Тогда при получении нового сообщения со списком узлов, нужно проводить некую агрегацию двух состояний — того, которое есть на ноде приёмнике и того, которое пришло с ноды передатчика. Наличия ограничения в c также значит, что фраза «отправить случайно ноде» меняет свой смысла. Случайных всего c и из них нужно выбрать какую-то из нод.

Более формально, с peer sampling service алгоритмы gossip разделяются по трём параметрам.

1. Peer selection. Периодически узел берёт из своего списка c одного соседа, с которым он обменяется состоянием. Можно выделить 3 основные способа, как это делается:
--- rand. Выбор случайного узла.
--- head. Выбор самого близкого узла.
--- tail. Выбор самого дальнего узла.
2. View selection. После обмена информацией о соседях, на узле находятся два списка соседей. Один, который был на узле изначально, и второй, пришедший от соседа. Их нужно соединить, учитывая ограничение в c соседей. Делается это тоже одним из трёх способов:
--- rand. Общий список c соседей формируется из произвольных узлов.
--- head. Списки объединяются, а затем остаются только c самых близких к текущему узлу соседей.
--- tail. Списки объединятся, а затем остаются только c самых дальних от текущего узла соседа.
3. View propagation. Определяет алгоритм, которым обмениваются узлы обмениваются информацией. Об этом уже было выше. Есть 3 способа:
--- push. Узел направляет свое состояние соседям.
--- pull. Узел забирает состояние от соседей.
--- push-pull. Объединение двух способов. Например сначала направляет, потом забирает.

Таким образом, работу peer sampling service можно описать кортежем из трёх элементов (ps, vs, vp). Разумеется можно придумать и другие, гибридные алгоритмы для ps и vs, например, но пока нам хватит самых простых. Реальные алгоритмы это к примеру (head, tail, push-pull) или (rand, rand, push).

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

Больше половины алгоритмов можно отбросить сразу, поскольку они стабильно приводят к нежелательным ситуациям:

- (head, *, *). Если выбирать для отправки только ближайшие ноды, в сети узлов будут образовываться кластеры. Это нежелательно, так как кластеры нод менее устойчивы к разделению. К тому же любые не-случайные топологии ухудшают вероятностные гарантии gossip.
- (*, tail, *). Если при отбрасывании нод из списка соседей всегда оставлять только самые дальние, новые ноды попросту не смогут стать частью топологии. Я очень долго думал, почему это так, но всё-таки дошло. Понадобилось всего 2 страницы рисования картинок...
- (*, *, pull). Проблема с этими вариантами очень похожа на первый, но немного по-другому. Модель pull приводит к образованию звездообразных топологий. Такая же проблема с гарантиями, как в первом пункте.

Из хороших алгоритмом можно выделить следующие:

- (*, *, push) хуже со сходимостью, чем у аналогов, но push протоколы лучше всего восстанавливаются при массовых отказах сети. При чём для ненормального математика отказ — это сразу -50% нод или больше. Кстати, процент узлов, при отключении которого практически гарантировано произойдёт разделение сети, ведёт себя в случае со случайными алгоритмами как percolation threshold. Больше математики!
- (*, *, pushpull) в среднем лучше по всем показателям, кроме восстановления при отказах.
- (rand, head, *) создают полное покрытие быстрее и равномернее, чем аналоги. Сеть, построенная такие алгоритмом, сложнее всего располовинить.
- (tail, *, *) немного больше случайности и немного медленнее сходимость чем другие. Но с tail надо быть осторожным, так как например (tail, rand, push) медленно увеличивает количество мёртвых нод, потому что рано или поздно в списке соседей остаются только самые дальние ноды.

Введение в семейство алгоритмов Gossip (4/4)

Кажется осталось только поговорить о самом главном... Где, собственно, gossip используется, а где лучше не стоит. Для начала практические применения:

- Распространение обновления данных по сети (data dissemination). Самое банальное и логичное применение. Ещё когда слова gossip не было, эпидемические алгоритмы использовались как раз для распространения данных.
- Создание топологий. Один из интересных подходов — сначала построить по сети случайное дерево, и пускать обновления уже по нему. Наличие фиксированной структуры резко увеличивает скорость сходимости, так как алгоритм фактически может стать детерминированным, вместо вероятностного. В некоторых сетях важно просто иметь более-менее актуальную информацию о топологии, например в сети маломощных устройств, коммуницирующих через какой-нибудь wifi. Для слабых устройств gossip очень хорошо подходит ещё и из-за малого размера сообщений и нагрузок на сеть.
- Мониторинг доступности. Gossip можно использовать для пресловутого failure detection. Вообще мониторинг доступности в распределенных системах — это большая тема, в которой не всё так однозначно. Отложим её до одного из следующих циклов.
- Подсчёт агрегатов. Внезапно, gossip подходит и для поиска сумм, средних и прочих агрегатов. Работает это за счёт немного хитрых алгоритмов и передаваемой в сообщении полезной нагрузки. Снизу приложу статью почитать поподробнее.
- Resource allocation. Gossip можно применять, чтобы отсортировать всё узлы в большой сети по некоторому показателю (например cpu, memory, network). Такая сортировка подходит для решения задачи: «как разделить X задач по Y машинам, чтобы всем хватило ресурсов»

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

⁃ Большое количество изменений, каждое из которых распространяется по протоколу. Всё дело в том, что полное распространение происходит за O(log(n)). Если в системе живут одновременно несколько событий, они и распространяются одновременно. Либо сразу все вместе. В первом случае, это много трафика, во втором, сообщения большого размера. И то, и другое — вещи, которых gossip пытается избежать.
⁃ Не подходит для быстрой синхронизации данных, так как сама суть gossip в том, что раунды происходят редко, по сравнению со временем сетевых задержек.
⁃ Любые гарантии в gossip имеют вероятностный характер. Иногда таких гарантий может быть недостаточно, особенно когда важна производительность высоких процентилей задержек.
⁃ Мало информации о том, как gossip работает в системе, предполагающей Byzantine fault. Всё-таки это система, основанная на том, что соседние ноды не пытаются вредить.
⁃ В маленьких сетях с редкой сменой количества участников броадкаст/алгоритмы консенсуса могут работать и быстрее, и эффективнее.
⁃ Если gossip используется в качестве механизма уменьшения энтропии, нужно всегда отдавать себе отчёт, почему энтропия возникла. Бороться нужно с причиной, а не следствием. Gossip подходит как механизм для обхода редких отказов детерминированного алгоритма. Как магическая пуля для исправления любых отказов даже он не справиться.

Источники:
- Про плюсы и минусы: Birman, Ken. 2007. "The promise, and limitations, of gossip protocols"
- Про peer sampling service: Mark Jelasity, Rachid Guerraoui, Anne-Marie Kermarrec, and Maarten van Steen. "The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations".
- Где используется gossip: Kermarrec, Anne-Marie, and Maarten van Steen. "Gossiping in distributed systems."
- Про агрегаты на gossip: David Kempe, Alin Dobra, and Johannes Gehrke. "Gossip-Based Computation of Aggregate Information."

Введение в семейство алгоритмов Gossip -> первый из четырёх постов
https://xn--r1a.website/shark_in_it/79

Впервые в жизни зарегистрировался на серьёзное мероприятие с кучей статей: https://www.hotstorage.org/2021/attend.html

Программа тут. Всё бесплатно, приходите тоже!

Ожидание: ничего не пойму.

Как минимум один пейпер будет не адово хардкорный. Почему важно измерять не только абсолютную производительность, но и эффективность на примере алгоритмов консенсуса. Краткое содержание есть в статье: http://charap.co/scalable-but-wasteful-or-why-fast-replication-protocols-are-actually-slow/

FoundationDB: A Distributed Unbundled Transactional Key Value Store

#shark_whitepaper

Пока я пытаюсь осилить ARIES, немного ненапряжного и очень свежего case-study от июня 2021 года. Работа про распределенное KV хранилище FoundationDB. Всех авторов перечислять не буду, так как это 21 человек. Оригинал можно почитать по первой ссылке здесь.

FoundationDB (FDB) была разработана более 10 лет назад, и с тех пор используется в Apple, как одно из основных хранилищ данных, а с 2017 года проект доступен на github. Это NewSQL хранилище, т.е. помимо гибкости и средств для масштабирование, свойственных NoSQL решениям, FDB также поддерживает транзакционность аж до strict serializability, но не без ограничений, конечно же.

Обычно базы данных предоставляют все свои компоненты в виде одного процесса. Т.е. условный инстанс postgres — это одновременно и транспортный слой, и оптимизатор запросов, и execution engine, и storage engine. FDB идёт другим путем, используя опыт современных cloud-first подходов к созданию хранилищ данных. Она основана на unbundled architecture, т.е. база данных — это не один процесс, а несколько взаимодействующих процессов, каждый из которых может быть запущен на отдельном сервере и масштабироваться независимо. Такой подход позволяет подстраивать БД под профиль нагрузки по чтению и записи.

FoundationDB позиционирует себя, как фундамент, поверх которого можно реализовать дополнительную логику. Например, на основе FDB работает и графовый движок JanusGraph, и record-layer — очень упрощенный вариант реляционной БД, и даже прямо сейчас происходят попытки перевести CouchDB на FDB.

FDB логически состоит из двух слоёв: управляющий слой (Control Plane) и слой данных (Data Plane). Слой данных дополнительно делится ещё на три компонента: Transaction System (TS), Log System (LS) и Storage System (SS).

При чтении, клиент запрашивает версию записи в TS, а потом идёт напрямую в Storage System. При записи, запрос попадает в TS, который обеспечивает транзакционность через сочетание optimistic concurrency control (OCC) и multi-version concurrent control (MVCC). Всё происходит lock-free прямо в памяти. Далее запрос записывается в Log System, где хранится Write-Ahead Log (WAL), после чего ответ возвращается клиенту. Обновления WAL затем агрессивно считываются компонентами Storage System. Сейчас SS представляет собой инстансы SQLite (а я думал она нигде не используется...), но в планах заменить их на RocksDB. Кстати период MVCC насильно установлен в пять секунд. По словам авторов, это заставляет клиентов больше думать над тем, как правильно составлять запросы, что в целом звучит как правильный путь для OLTP хранилищ. Скалировать много маленьких запросов проще, чем подстраиваться и под тяжёлые, и под легкие запросы одновременно.

Ещё одной особенностью FDB является процесс восстановления при сбоях, называемый реконфигурацией. Когда Control Plane обнаруживает ошибки в TS/LS или просто попытку развернуть новую версию БД, он просто останавливает старые инстансы и запускает новые. Весь процесс занимает до пяти секунд. Это позволяет использовать реконфигурацию как для обновлений, так и для восстановления при ошибках. Более того, настолько быстрый процесс восстановления — то что доктор прописал для нестабильной cloud-based среды.

И последняя убер фича FDB — это simulation фреймворк, который писался ещё до начала работы над самой БД. Дело в том, что тестировать базы данных довольно тяжело. Здесь часто не помогают просто «юнит-тесты», так как проверить, что база всегда выполняет свои гарантии консистентности или durability очень сложно. Количество кейсов практически неограниченно. Симуляционный фреймворк позволяет производить сотни запусков компонентов БД в минуту, вносить произвольные ошибки на разных уровнях (сеть, диски, запросы и т.д.) и проверять, работает ли FDB, как ожидается. Более того, неудачные запуски всегда можно переиграть, так как сам фреймворк детерминированный.

Спасибо https://xn--r1a.website/lilfunctor за репост и привет всем новоприбывшим! Приятно проснуться знаменитым 😎 Небольшой пост про ожидания и что ещё почитать.

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

Дисклеймер: я не эксперт в распределённых системах. В обычной жизни я перекладываю XML'ки и реже JSON'ы на Java. Поэтому ничто здесь не является советом! Всегда рад любым уточнениям, исправлениям или дополнительному материалу. Велком в комментарии.

Из интересных постов, пока можно почитать что-нибудь из списка:

- История CAP теоремы. Гайд на 18к символов, как перестать называть БД AP/CP и начать жить.
- Эпидемические алгоритмы и их развитие — протокол/алгоритм Gossip. Госсипов сотни вариаций, здесь разбор основных идей.
- Алгоритм кэширования TinyLFU. Кеширование это не только «положить данные поближе». Иногда нужно знать, что класть.
- Немного токсичный пост про понятие Real-Time. Спойлер: «Быстро» != "Real Time"

HotStorage 2021

Сходил я тут месяц недели назад на HotStorage 2021. Так сходил, что IT пузырь вокруг в очередной раз надорвался. В мире снова интересного сильно больше, чем можно выучить за одну жизнь. В первой части личный опыт о том, чем «конференции с пейперами» отличаются от обычных IT конференции, почему это безумно интересно, а также как их найти. Далее большая часть про то, как работают SSD. Это здоровенный кусок, поэтому с подборкой крутейших докладов с конфы я приду через несколько дней. Всё равно чтобы понять градус безумия нужно сначала прочитать про SSD.

Для начала программа и сами работы. Конференция в основном про новинки в области SDD и способов хранения. Удивительное отличие от обычных IT конференций — 10-15 минутные записи выступлений. Записи можно объяснить ковидом, но 10 минут на довольно сложные работы? Что ещё интереснее, за эти 10 минут в принципе удаётся что-то понять.

Вторая удивительная вещь. Представленные работы это не теоретический бред магов в башнях из слоновой кости, которые JSON в своей жизни не видели, а совершенно наоборот. Чуть ли не главный вопрос после любой работы — что там с использованием / adoption фичей и технологий, так как у SSD с этим проблемы.

SSD — технология молодая, развивается стремительно, но индустрия софта подстраивается под эти новинки за пару тройку лет, а за это время появляется уже что-нибудь новенькое и нужно подстраиваться заново. Не помогает и тот факт, что в Software индустрии как-то принято пихать везде вариации "Computer As A Service" подхода, когда компьютер это какое-то количество процессоров, объём RAM и объём дисков, а не конкретные характеристики оборудования. SSD же наоборот сложная железяка, с которой нужен особый подход, но и прирост производительности от них можно получить на порядок, а то и больше.

Если всё ещё не убедил, то очень рекомендую посмотреть час кейноута (или полчаса на х2 скорости!). Это самый крутой кейноут, который я видел. Называется он I/O Acceleration from the Bottom Up, а рассказывает SVP storage в Samsung, а так же доктор CS Sangyeun Cho. Ссылка.

Топ 4 забавных факта с этого выступления:
- Количество памяти, которое можно впихнуть на 1 квадратный миллиметр SSD (Areal Density) растёт на 80% в год. Тренд продолжается последние 20 лет.
- Некоторые SSD настолько быстрые, что для них бутылочным горлышком выступает скорость PCI / SAS / SATA интерфейса.
- В 2017 году Samsung выпустил SSD на 16 TB под названием PM1633a. На момент выпуска это самый объёмный диск среди одновременно и SSD, и HDD в мире. Стоил в то время он дороже, чем слиток золота такой же массы.
- За счёт обработки данных ближе к SSD (Для гугления это называется Near-data processing) можно иногда получить х166 к скорости выполнения сложных join'ов на MariaDB. Подробнее о том как это работает в пейпере.

В целом, мне очень понравился формат, буду ходить ещё. На HotStorage 2021 я вышел через блог Aleksey Charapko, у которого там был пейпер в соавторстве. У него, кстати, есть еженедельная reading group, очень рекомендую, если интересно. Там часто выступают сами авторы работ, например как в работе про FoundationDB, о которой я писал тут. Можно просто читать, если ходить нет сил.

К сожалению, я не нашёл единый сайт со всеми конференциями такого рода, скажите, если знаете. Пока работает только магия твиттера, поскольку почти у всех конференций есть там профили. На кого подписаться: во-первых, профили ассоциаций-организаторов конференций USENIX и ACM как правило репостят что-то новенькое. Во-вторых, можно найти конкретные конференции, например тот же HotStorage или вот недавно прошёл ESEC/FSE.

Как работают SSD (1/3)

Структура SSD и особенности работы.

Теперь о том, как SSD в принципе работают. Здесь самое понятное «объяснение для программистов», которое я только находил. Если хочется посмотреть на более хардкорный материал про внутренности, то здесь есть ещё один очень хороший пост. Что первая ссылка, что вторая — посты из шести частей. В каждом огромное количество ссылок на работы и другие посты, читать не перечитать.

SSD состоят из нескольких компонентов. Само хранилище основано на flash-памяти, т.е. набора определенным образом соединенных транзисторов, которое можно программировать и стирать. «Программировать» в данном случае значит «записывать», но так уж устоялась терминология. По-английски это называется Program/Erase cycle или просто P/E цикл.

Биты памяти хранятся в ячейках, которые, собственно, состоят из транзисторов. Есть две схемы подключения транзисторов — NOR и NAND. Про отличия можно почитать тут, главное запомнить, что большая часть SSD в компьютерах и серверах построены по технологии NAND. Ячейки в NAND flash памяти не вечные, и их ресурс стремительно уменьшается с каждым P/E циклом, об этом будет ещё ниже.

Самый простой вид ячеек это SLC — Single level cell. Хранят 1 бит, очень быстрый доступ (latency), живут долго. Level здесь обозначает уровень зарядка. Здесь либо заряд есть, либо его нет.

Следующий тип это MLC — Multi level cell. "Multi-level" здесь говорит о том, что такая ячейка не просто хранит или не хранит заряд. Она может хранить один из «определенных уровней заряда». Условно — не заряжена, немного заряжена, средне заряжена, полностью заряжена. Таких определенных уровней может быть 4 — тогда можно представить 2 бита. А может быть 8 — тогда ячейка называется TLC — Triple-level cell и хранит она 3 бита.

Чем больше уровней, тем сложнее доступ к информации, т.е. растёт latency и уменьшается время жизни ячейки. При этом чем больше уровень, тем больший объём информации можно запихнуть в одно и тоже количество транзисторов, т.е. есть трейдофф. Либо быстрые, долговечные и малообъёмные SLC, либо медленные и менее долговечные, но зато большие MLC/TLC. Большая часть современных компьютеров и значительная часть серверов использует SSD с ячейками MLC/TLC. SLC применяются в ентрепрайзных серверах и стоят астрономические деньги.

Вне зависимости от типа ячейки, следующим уровнем иерархии является страница, состоящая из ячеек. Страницы бывают разного размера в разных моделях SSD от 2 КБ до 16 КБ. Несколько страниц объединяются в блок. В одном блоке как правило 128 или 256 страниц. Таким образом в зависимости от объёма страницы, объём блока будет как правило от 256 КБ до 4 МБ.

Иерархия ячейка < страница < блок очень важна для SSD из-за фундаментальных особенностей их работы:

- Во-первых, считать или записать можно только страницу целиком. Надо вам прочитать 2 байта — читаете всю страницу на 16 КБ. Неприятно, но что делать.
- Во-вторых, удаление данных (E — erase в P/E цикле) происходит по-блочно. Нельзя удалить только одну страницу, только все 128/256 страниц в блоке целиком.
- В-третьих, страницы нельзя перезаписывать. Однажды записанная страница остаётся неизменной, пока блок (со всеми страница) не будем удалён. Отсюда, собственно и P/E цикл.

Как работают SSD (2/3)

Сборка мусора и не верь бенчмаркам своим.

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

1. Скажем SSD записать любое значение, например X=5. Оно попадает в первую страницу первого блока.
2. Затем скажем записать X=6. Запись X=5 не может поменяться, она остаётся, но рядом появится ещё одна запись X=6 уже на второй странице первого блока, которая и будет актуальной. Таким образом у вас как бы тратиться в два раза больше места на хранение «мусора».
3. Наконец скажем записать X=7. SSD запишет её на первую страницу уже второго блока, а первый блок полностью очиститься от данных. Мусор удалён.

Программистам на memory managed языках этот алгоритм может показаться очень похожим. В действительности, в SSD происходит процесс «сборки мусора». Мусор накапливается, а значит его нужно удалять. В хорошей ситуации он удаляется где-нибудь в бекграунд процессе, в плохой — перед вставкой данных.

Есть и ещё одна особенность. У данных в SSD нет никаких «областей видимости» или количества ссылок, как в языках программирования. В общем случае, SSD даже не знает, что данные перестали использоваться. Он может это узнать, если поверх тех же данных пойдёт новая запись. Для решения этой проблемы используется два подхода. Во-первых, многие операционные системы поддерживают команду TRIM, задача которой — сообщить SSD, о том что блок памяти больше не нужен, а значит его можно отчистить. Во-вторых, на многих SSD выделяют физически доступной памяти на 15-25% больше, чем логически адресуемой. Это называется over-provisioning. Поскольку эту память не видит операционная система, но видит SSD, её можно иногда использовать при повышении нагрузок для временного хранения блоков, например.

Плохие новости для программист здесь заключаются в том, что из-за сборки мусора бенчмарки производительности SSD несут очень спорную информацию. Просто замерить, как там новенький диск записывает 20 минут данные — недостаточно. Нужно понагружать его хотя бы пару часов под нагрузкой из и чтений, и записей, чтобы вообще увидеть эффект от сборки мусора, особенно когда там агрегат на 16 ТБ. При этом паттерн нагрузки от производителя может вообще не соответствовать данным реального приложения.

Вторая опасность бенчей SSD — замер только одного показателя, как правило общей производительности (throughput). Это, конечно, не то что нам нужно при наличии сборки мусора, потому что процесс сборки может случиться внезапно, что влияет на задержки (latency). А ещё есть такой показатель, как количество операций чтения/записи в секунду IOPS (Input/Output Operations Per Second). Он тоже не какая-то фундаментальная характеристика, а параметр, зависящий от нагрузки. Конечно, чем больше IOPS тем лучше, но зависит от данных. 10к IOPS где каждая операция передаёт 1 КБ дают меньшую производительность, чем 5к IOPS с 4 КБ данных в каждом запросе.

Как обычно бывает с бенчмарками, лучший вариант — делать бенчи самому на своих данных.

Как работают SSD (3/3)

FTL и старение.

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

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

- Ячейки в SSD «стареют» с каждым P/E циклом, поэтому по-хорошему перезаписей должно быть настолько мало, насколько это возможно.
- Некоторые данные изменяются часто, а другие практически никогда. Опять-таки со стороны «старения» ячеек это нежелательная характеристика. Нам бы хотелось, чтобы диск устаревал более-менее равномерно. А значит... данные нужно периодически передвигать.
- Очистка данных происходит по-блочно. Если в блоке есть часть нужных и часть ненужных данных, нужные сначала придётся переместить, а лишь затем очистить блок. Если операционная система будет писать данные как попало, таких перезаписей будет слишком много. Одновременно с этим, отчистка данных — долгая операция. Она в несколько раз медленнее записи.
- Чтение и запись возможна только по странице. Запись исправить довольно просто — вставить буфер размера, равного размеру страницы, а вот с чтением тяжелее. Кажется здесь магии особой нет и нужно просто записывать «похожие» данные рядом.

Поэтому в SSD в качестве алгоритма для FTL часто применяет подход под названием log-block mapping, даже пейпер есть. По своей сути он немного напоминает алгоритмы работы LSM хранилищ. Идея в том, чтобы хранить записи в виде «лога», а затем сливать данные нескольких блоков в один.

Алгоритм приблизительно следующий:

1. На SSD заводится таблица маппинга логических блоков в физические. Помимо маппинга блоков, внутри каждого блока отдельно заводится по таблице маппинга страниц в физические страницы. Один блок помечается как log, остальные как data блоки.
2. Операционная система выдаёт записи по произвольным адресам. Например сначала 3, потом 7, потом 13 и так далее.
3. Записи по этим адресам, возможно, уже существуют в каких-то других data блоках. Это всегда можно определить по таблице маппинга страниц внутри блока.
4. SSD записывает новые записи последовательно в log блок.
5. Когда log блок заполняется, его содержимое сливается (merge) вместе с каким-нибудь из data блоков, а результат записывается в свободный блок. Таким образом создаётся новый data блок, и возможно, удаляется старый.
6. На место log блока назначается новый.

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

В заключении, ещё несколько слов:

- SSD — удивительная технология. Например они поддерживают просто невероятный уровень параллелизма для практически всех операций. Подробнее можно почитать в Design Tradeoffs for SSD Performance (ссылка). Или в ссылках тут. Я лишь поскрёб вершину айсберга.
- Оптимизация программ под SSD — это фактически выбор конкретных объёмов на чтение/запись в зависимости от размера составных блоков SSD, таких как страницы и блоки. Проблема в том, что просто подобрать размер страницы тут не получится, всё сильно сложнее.
- Бенчмарки это всё ещё сложно. Особенно бенчмарки SSD.
- В мире за пределами software пузыря происходят удивительные вещи.

Конфиги будущего (1/2)

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

- Во-первых, параметры самого приложения. К примеру postgresql.conf для посгри или несколько десятков, а то и сотен конфигов для kafka.
- Во-вторых, если приложение работает на VM — ещё сотня-другая параметров сверху. Даже если VM нет, часто разные флажки конфигурации, компиляции или самого процесса могут влиять на производительность.
- В-третьих, в любом случае запускать процесс придётся поверх операционной системы. Очередная сотня конфигурируемых параметров на нетворкинг, на работу с памятью и на файловую систему.

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

Даже если каким-то образом всё-таки положить себе в голову абсолютно все параметры системы, задача не решится. Замеры производительности никогда не бывают однозначными. Всё есть тредофф. В одном месте выиграл, в другом проиграл. Проверить все кейсы просто невозможно за обозримый промежуток времени.

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

Первый шаг — перестать конфигурировать каждую систему руками. Пусть сами себя конфигурируют! Это можно сделать, например, при помощи достаточно быстрого алгоритма машинного обучения в ядре ОС, как в работе A Machine Learning Framework to Improve Storage System Performance (acm). Называется этот ML фреймворк KML и на некоторых нагрузка с RocksDB он показывает х2 производительности... правда из работы не совсем понятно по сравнению с чем. Думаю верно предположить, что сравнение идёт с ОС без каких-либо ручных изменений конфигурации. Здесь рассматривается только абсолютное количество операций с KML, и например ни слова не говорится про средние задержки, но надо же с чего-то начинать.

Идея следующая: оптимизировать I/O нагрузку можно за счёт правильных вызовов и конфигурации readahead. Трассировку, сбор данных и выделение памяти можно оставить в kernel space, там же реализовать примитивы для построения ML алгоритмов, нейросетей и работы с плавающей точкой. Для удобства, обучать модель можно как в kernel space, так и в user space. Можно обучить на известной заранее нагрузке, а затем положить модель в ядро. Обучение и переобучение также по последнему слову техники: хоть онлайн, хоть офлайн, синхронно, асинхронно, в общем, как угодно. Работа не зря называется фреймворк для улучшение производительности. Ещё бы ссылку на гитхаб приложили, но видимо не всё сразу.

Если KML запущен в kernel space, он гипотетически может переобучаться под нагрузку прямо в режиме онлайн, но в работе рассматривается немного другой путь. Авторы сначала замеряют четыре разные вида нагрузки на RocksDB (различаются по количеству чтений и записей), а затем строят классификатор. Его задача — проанализировать текущую неизвестную нагрузку и найти похожую из четырёх уже известных конфигураций.

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

Конфиги будущего (2/2).

Идея применять машинное обучение для оптимизации хранения и выпиливания всяких сложных эвристик довольно популярная, и в последнее время исследований становится всё больше. Вот ещё работа: Automatic I/O stream management based on file characteristics (acm). Здесь рассматривается, как при помощи ML в SSD можно уменьшить write amplification — «лишние» операции записи, необходимые из-за особенностей организации SSD. По замерам получилось в среднем улучшение на 21.6%. Немного магии, и ваш SSD работает на 1/5 дольше и чуть-чуть быстрее.

А в From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees (usenix) оптимизируются LSM деревья, которые являются одной из базовых структур данных для построения хранилищ. Здесь прирост составляет 23% - 78%.

Даже в среде распределенных алгоритмов кеширования ML находит себе место, как в Stacker: an autonomic data movement engine for extreme-scale data staging-based in-situ workflows (acm). Здесь речь про кеш, а значит в качестве важнейшней характеристики используют среднее время ответа (latency). Прирост составляет в среднем ~27%.

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

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

Ещё интересные, какие новые подводные камни и уязвимости мы получим от запихивания ML алгоритмов прямо в ядро. Не перерастёт ли проблема «выучить 500 параметров конфигурации ОС и БД» в проблему «выучить 500 параметров конфигурации ML алгоритма».

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

ARIES (1/8)

Введение.

ARIES — алгоритм записи и восстановления данных в транзакционных системах, основанный на write-ahead logging (WAL). Он поддерживает как полный, так и частичный роллбек транзакций, подходит для разных политик buffer manager (часть БД, отвечающая за запись данных с памяти в диск и обратно. Подробнее — ниже), а также позволяет использовать гранулярные блокировки вплоть до блокировки отдельных строк. ARIES основан на полном повторе истории при восстановлении. Другими словами, он не делает разницы между транзакциям, которые успели сделать коммит до начала рестарта, и теми что не успели. ARIES сначала всегда восстанавливает состояние базы до того, каким оно было перед рестартом, а лишь затем откатывает неуспешные транзакции. Такой подход позволяет значительно упростить алгоритм восстановления, особенно если первый его запуск завершился неуспешно. ARIES работает даже при множественных рестартах.

Довольно сложно найти 100% подтверждения, какие базы и когда использовали ARIES. В разных источниках к ним добавляют и Oracle DBMS, и Microsoft SQL server, и IBM DB2. Часто в документациях не пишут, что БД использует ARIES напрямую, но похожие идеи всё равно просачиваются.

ACID и ARIES.

ARIES частично связан с понятием ACID — четырьмя важными свойствами любой транзакционной системы. Поскольку ARIES отвечает за запись и восстановление, он является частью A — Atomicity и D — Durability из ACID. Опосредованно ARIES позволяет делать гранулярные локи, т.е. влияет и на I — Isolation.

Если на чистоту, акроним ACID не особо-то и удачный, в основном из-за путаницы в определениях, которую он создает. К примеру, atomicity здесь не имеет отношение к атомарным операциям в языках программирования и ОС. В ACID, A — это возможность прервать транзакции в любой момент до её полного окончания. Consistency часто не относится к самой БД, а скорее к тому, как данные внутри неё используются приложением. И уж точно consistency в БД и consistency в CAP к примеру — совершенно разные вещи. С Isolation ещё сложнее. Изоляция говорит о том, как БД работает с конкурентными операциями. Фактически, уровень изоляции задаёт, какие ошибки и ситуации можно, а какие нельзя считать корректными. Это определение очень похоже на модели консистентности, но C в ACID уже есть... Хоть c durability вроде как проблем не возникает.

Ещё одна причина, почему ACID несёт больше семантики, чем настоящего смысла заключается в том, что в БД все эти свойства обеспечиваются одновременно. Нет отдельной подсистемы, отвечающий только за durability или только за atomicity, это всё алгоритмы и структуры данных.

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) — один из самых влиятельных и дремучих алгоритмов записи и восстановления данных. Работа (пдф) датируется 1992 годом, но похожие алгоритмы существуют примерно с 60-70-ых, когда первые базы данных только появились. Идеи из ARIES всё ещё используются повсеместно, а сама работа уже цитировалась более 1500 раз (по google scholar)! Практически любой другой труд про транзакционность или восстановление упоминает ARIES.

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

Вторая-третья часть поста посвящена работе памяти и дисков в БД и подходу write-ahead logging. Само описание ARIES начинается с четвёртого поста и продолжается до конца.

ARIES (2/8)

БД с высоты птичьего полёта. Работа с памятью и диском.

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

Как и в любом другом процесс, часть данных БД находится в энергозависимой памяти, она же RAM, она же просто «память». При этом основная задача базы данных — сохранять данные в энергонезависимую память: на HDD, SDD, ленточные накопители (tape drive) в зависимости от того, что у вас там есть под рукой и какой сейчас год. Энергонезависимые устройства обычно сильно медленнее читают, и уж тем более записывают данные, чем память. Настолько медленно, что у БД нет совершенно никакой возможности транслировать запросы на чтения и записи напрямую в диск. Получается дилемма. С одной стороны, БД должна всё сохранять в диск, чтобы данные не терялись. С другой, часть данных нужно хранить в памяти, потому что диски слишком медленные. А информация из памяти пропадает сразу, как только выключается свет или умирает процесс с БД.

Самый прямолинейный выход из такой ситуации: хранить в БД буфер памяти (memory buffer), отображаемый периодически один-к-одному на диск. Решение не идеальное, поскольку объём дисков обычно многократно больше объёма памяти, всё хранить не получится. К тому же записывать и читать прямо весь буфер сразу — затратно. Не синхронизировать же в самом деле по 32+ ГБ RAM за раз. Но выход есть: хранить только какое-то количество страниц (page) в памяти. Страницы обычно делают одинакового размера — так с ними проще работать. Здесь мы исходит из предложения, что все данные разом скорее всего не нужны, поэтому можно хранить только ту часть, с которой сейчас идёт работа.

Выходит, в БД хранится некий набор страниц, отображаемых 1-к-1 на участки диска. А теперь финт ушами. Вот мы вытащили страницу из диска и храним её в памяти. Поскольку единственный способ поменять содержимое диска — записать страницу, пока этого не произошло, наша страница — это точное отображение данных на диске. И она хранится в памяти. Значит любой запрос к данным на диске можно адресовать к этой самой странице в памяти. Это от нескольких раз до нескольких порядков быстрее!

Теперь про запись. Пока данные на странице не поменялись, т.е. пока страница остаётся «чистой» — можно даже не ходить в диск, так как данные есть в памяти. Как только данные на странице поменялись, она становится «грязной» (dirty page). Такую страницу нужно запись на жёсткий диск, чтобы она снова стала чистой. Записью и чтением страниц из памяти и наоборот в БД занимается компонент под названием buffer manager (Далее — BM). Кстати, если вам кажется, что вы что-то такое про страницы и синхронизации уже слышали, то как оно и есть! Виртуальная память в ОС работает довольно похожим образом, правда у ОС не стоит задачи все данные впихнуть в диск, а ещё есть аппаратная поддержка. Тем не менее, подходы и даже терминология очень схожи.

ARIES (3/8)

БД с высоты птичьего полёта. Политики buffer manager и write-ahead logging.

Buffer manager в транзакционной системе может работать в разных режимах, которые иногда называют политиками. Одна из таких политик — steal / no steal. Суть такая: внутри транзакционной системы исполняются... транзакции. Они меняют содержимое чистых страниц из-за чего те становятся грязными. Одна транзакция может одновременно менять содержимое нескольких страниц. Протекать транзакция тоже может относительно долго, вплоть до коммита или полного роллбека. Здесь встаёт вопрос — а можно ли записать грязную страницу на диск, сделав её чистой, до того, как все транзакции, использующие эту страницу, завершатся. Если так можно делать, BM придерживается steal политики. Если нельзя, т.е. записать можно только страницы, над которыми сейчас не происходит изменения, используется no steal политика.

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

Другая важная политика BM — force / no-force. При force политике транзакция не может завершиться коммитом, пока все её изменения не будут записаны на энергонезависимое хранилище. Другими словами, каждая транзакция всегда синхронизирует свои изменения на диск. Force политика очень упрощает процесс восстановления, потому что если транзакция успела сделать коммит до отказа БД, данные точно есть в хранилище. С другой стороны, при force политике про производительность можно забыть. Синзронизировать вообще каждое изменение в диск — супер затратно.

ARIES позволяет работать с самым мягким набором политик — steal + no-force, и всё ещё обеспечивать «гарантированное» сохранение данных. В кавычках, потому что нельзя взять и отбросить все мириады особенностей OS, дисков, SSD и их драйверов из-за которых вроде запись гарантируется, но не всегда. Прежде чем перейти к ARIES, осталось сказать про алгоритм/протокол write-ahead logging. Протоколом он называется в самой работе.

Write-ahead logging использует в системах, в которых страницы с изменениями перезаписываются. Другими словами, существует одна копия страницы на диске и её клон в памяти в виде чистой или грязной страницы. Никаких вторых версий в другом месте, только одна копия. Такой подход накладывает некоторые ограничения, а именно: при использовании WAL, перед тем как грязная страница в памяти получит право перезаписать страницу на диске, сначала на диск обязательно должен быть сохранён лог, содержащий изменения. Сначала лог с информации об обновлении, потом само обновление. Поэтому подход и называется write-ahead logging.

WAL в общем случае — это привычный всем лог. Как и любой лог, пишется он только вперёд. Синхронизация такого лога также происходит достаточно быстро, поскольку старые данные не могут меняться. Слово «синхронизация» здесь используется не случайно, потому что WAL это очередной буфер, который живет в памяти БД и гипотетически может не дожить до записи на диск. Чтобы этого не происходило, как правило БД синхронизирует WAL при коммитах/прерываниях транзакций. Ещё одна причина для синхронизации WAL — превышение размер буфера или просто по времени. В постгресе к примеру размер буфера и время после которого произойдёт запись можно даже настроить.

Замечу ещё, что протокол write-ahead logging и сам журнал с логами часто в литературе называется одним словом — WAL. Обычно это не приводит к путанице, так как по контексту понятно, идёт ли речь о протоколе или о файле. В общем случае, протокол WAL — это правило, из-за которого обновление страницы в диск может попасть только после того, как в этот же диск попадёт обновление журнала. А лог WAL — это файл с записями о транзакциях.

ARIES (4/8)

Содержание WAL в ARIES.

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

Поскольку запись в WAL идёт последовательно, каждой записи в нём можно присвоить некий монотонно возрастающий номер. Он называется log sequence number или LSN. В некоторых ситуациях LSN даже не нужно присваивать, так как запись идёт последовательно, т.е. в качестве LSN подойдет адрес на диске. Это работает до тех пор, пока лог не перестанет помещаться на диске. Чтобы избежать уже этой проблемы, если свои хаки, например диск можно рассматривать как циклический буфер, а LSN будет записываться как адрес + количество циклов, но это детали реализации. Важно одно — каждая запись в WAL содержит LSN, по которому можно построить историю обновлений БД.

Помимо LSN каждая запись также содержит 3 другие поля: prevLSN, TrId и type. PrevLSN указывает на предыдущую запись в лог, созданную транзакцией под номером TrId. Другими словами, набор записей с одинаковым TrId образуют связный список, где предыдущую запись всегда можно найти по prevLSN.

Type указывает на тип записи. Типов в разных источниках выделяют разное количество, но нам хватит трёх. От типа зависит, какие ещё поля содержатся в одной записи в WAL.

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

Далее идёт запись, отвечающая за изменения или создание новых данных, а именно "update". Каждое обновление содержит помимо prevLSN, TrId и type="update" ещё 3 новых поля. Первое pageId — страница, на которой происходит обновление, а второе и третье — redoData и undoData. Redo — это непосредственно те изменения, которые вносятся в рамках транзакции. Там может быть какой-нибудь инкремент значения или новое значение для колонки. Undo — обратная операция. Если Redo — инкремент, Redo — декремент. Если Redo — новое значение, в Undo будет содержаться старое. Не так важно, лежит ли в undo/redo изменение в логическом виде или результат после его применения — оба подхода работают, важно что в одной update записи в WAL написано и как применить изменение, и как его откатить.

Последний интересный вид лога — это компенсирующие логи, они же compensation log records они же CLR. Такие логи записываются базой при роллбеках. На каждую запись с типом update при полном роллбеке будет по одной записи с типом CLR, только применяться они будут в обратно порядке. Сначала откатиться самый старый апдейт, потом тот что был перед ним и так далее. Каждый CLR Помимо prevLSN, TrId и type="compensations" содержит pageId, который как и в update логах обозначает номер страницы, а ещё два поля, которые я назвал особым образом, чтобы стало понятнее, но не уверен что получилось.

Первое поле: redoTheUndoData. CRL используется при роллбеках, т.е. он откатывает транзакцию. Информация об откатывании находится в связанном "update" логе в поле undoData. CRL как раз таки и содержит эту undoData в поле redoTheUndoData. Иными словами, CRL говорит о том, какую операцию нужно исполнить, чтобы откатить связанную запись.

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

ARIES (5/8)

Пример WAL, прочие структуры данных.

Настало время привести пример. Для упрощения я опущу работу со страницами, полями pageId и покажу как связаны все записи в WAL.

Пусть есть некая страница X с двумя поля k и n. Есть также две параллельные транзакции, одна увеличивает k на 2, а вторая уменьшает n на 3. Затем первая транзакция снова увеличивает k на 9. Пока ни одна не успела сделать коммит. Каждая запись в WAL я обозначу числом, которое равно LSN, но как вы помните, писать LSN не обязательно — для этого подойдёт и адрес лога. Начну писать лог с середине, чтобы тоже лишний раз не путаться. Вместо "update" будет просто "u", "commit" — "c", а "compensation" заменю на "clr"

Напомню, что запись с типом update содержит поля prevLSN, TrId, pageId (опустим), redoData и undoData:

77. [-, 1, "u", k+=2, k-=2]
78. [-, 2, "u", n-=3, n+=3]
79. [77, 1, "u", k+=9, k-=9]

Первые две записи содержат "-" вместо поля prevLSN, поскольку они являются первыми изменениями в своих транзакциях. Запись 3 (LSN = 79) в поле prevLSN содержит 77 — это указание на LSN предыдущей записи, сделанной этой транзакцией, т.е. записи с LSN = 77.

Теперь пусть транзакция 2 сделать коммит, а транзакция 1 сделает полный роллбек предыдущих обновлений, затем увеличивать k на 13, а затем сделает коммит. Получится следующая ситуация:

77. [-, 1, "u", k+=2, k-=2]
78. [-, 2, "u", n-=3, n+=3]
79. [77, 1, "u", k+=9, k-=9]
...
88. [78, 2, "c"]
89. [79, 1, "clr", k-=9, 77]
90. [89, 1, "clr", k-=2, -]
91. [90, 1, "u", k+=13, k-=13]
92. [91, 1, "c"]

Для начала посмотрим на запись 89. В поле redoTheUndoData содержится k-=9 — ровно тоже самое, что содержалось в предыдущей записи 79 с типом update в поле undoData. Фактически здесь при создании CLR записи происходит копирование данных. В поле undoNextLSN содержится 77, т.е. указатель на следующая запись, которую нужно откатить во время этого роллбека. Оно скопировано из prevLSN той записи, которая откатывается. У записи с LSN 79 в поле prevLSN записано 77.

Если бы в undoNextLSN не было бы данных, это означало бы, что роллбек частичный, т.е. откатывается только одна запись из двух. Другими словами, наличие записи в undoNextLSN означает, что роллбек ещё не завершён. Когда роллбек откатит последнюю запись в CRL в undoNextLSN не будет ссылки. Именно этот случай показан в записи под номером 90. Здесь тоже CLR запись, но следующий за ней записи нет, поэтому в поле undoNextLSN стоит "-".

Помимо особого способа заполнения WAL, ARIES ещё нужно поддерживать рядом с журналом две таблицы. Их можно собрать по WAL, поэтому достаточно держать их в памяти.

Первая — это таблица грязных страниц dirty pages table (DPT). В ней содержится всего два поля: pageId для номера страницы и указатель на первую запись в WAL, после которой страница стала грязной. Это поле называется recoveryLSN и оно используется для поиска той записи, с которой нужно начинать восстановление. Таблица меняется в двух случаях. Если очередная запись в WAL изменила страницу, которая была чистой — сюда добавляется номер этой страницы и номер LSN записи. Если же страница синхронизируется на диск, запись из DPT удаляется.

Вторая нужная для работы ARIES структура — это таблица транзакций transactions table (TT). В ней находятся все незавершённые транзакции с указанием их идентификатора TrID, а также последнего изменения, произошедшего в рамках этой транзакции lastLSN. У каждой записи в WAL есть указатель на предыдущую запись в поле prevLSN, т.е. все записи объединены в связный список. В TT указывается транзакция и её последнее изменение, т.е. фактически запись здесь — это указатель на голову связного списка. Записи в TT обновляются всякий раз когда в рамках транзакции происходит изменение. Запись удаляется при коммите или полном роллбеке.

ARIES (6/8)

Алгоритм восстановления. Фаза анализа и redo.

Алгоритм восстановления в ARIES состоит из трёх шагов: анализ, redo-фаза, undo-фаза. Фазы всегда исполняются в такой последовательности даже если рестарт завершился неуспешно и его надо перезапустить.

Фазы рассматривать будем на примере WAL, в котором на момент восстановления находятся 4 записи, после которых произошёл рестарт. Здесь мы добавим поле pageId, чтобы показать, как меняется таблица грязных страниц DPT. Пусть есть две транзакции, одна исполняется на странице X, а другая на странице Y. WAL будет выглядеть следующим образом.

30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
-- RESTART

Здесь есть транзакция 2 (начинается с записи 31), которая завершилась коммитом и транзакция 1, в которой произошло 2 обновление, которые попали в WAL, но коммита не произошло. Так как транзакции должны происходить атомарно, вторая транзакция после восстановления должна откатиться.

В фазе первой фазе — анализе, ARIES проходится по записям в WAL и восстанавливает состояние таблицы грязных страниц DPT и таблицы незавершенных транзакций TT.

К примеру после анализа первых двух записей 30 и 31, в DPT будут записи:

X, 30
Y, 31

После анализа всех записей до 33, DPT содержит:

X, 30
Y, 31

Как видите, после анализа двух последних записей ничего не поменялось. DPT говорит о грязных страницах. Этой таблице важна лишь первая запись, которая сделала страницу грязной. Коммиты не имеют никакого значения для DPT, поскольку ARIES может работать в no-force режиме, т.е. коммит не означает, что страница записалась в диск.

Теперь к таблице завершённых транзакций. После анализа записей 30 и 31, TT выглядит так:

1, 30
2, 31

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

После анализа последних двух записей TT превратится в:

1, 32

Как видите, транзакция 2 исчезла из TT, поскольку та успела сделать коммит. Последнее изменение в транзакции 1 произошло в строке с LSN 32, поэтому она всё ещё находится в TT.

Последняя вещь которая происходит в фазе анализа — это поиск LSN, с которого нужно начать Redo фазу. Для этого просто берётся минимум из записей в таблице грязных транзакций DTP. В нашем случае это запись c LSN 30.

Фаза 2 — это Redo. Во время исполнения Redo буферы страниц приводятся в то же самое состояние, в котором они были до рестарта. Если анализ только создал таблицу DTP и TT, во время redo фазы та часть данных о страницах, которая хранится в памяти, приведётся в полное соответствие с информацией в WAL. Другими словами грязные страницы действительно станут грязными в памяти. Во время Redo фазы исполняются даже обновления транзакций, которые завершились неуспешно, как транзакция 1 в нашем случае.