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 в нашем случае.

ARIES (7/8)

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

Наконец Фаза 3 — Undo. После исполнения первых двух фаз, таблица незавершённых транзакций TT может быть не пуста. Эти транзакции не успели сделать коммит. Значит они должны откатиться, чтобы сохранить свойство атомарности.

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

1. Выбирается запись с самым большим LSN.
2. Если запись update — эта запись откатывается при помощи CRL записи в WAL. Той самой записи, которая обычно записывается в WAL при роллбеках. Фактически ARIES подменяется неуспешные транзакции на успешные, которые просто сделали роллбек. В TT добавляется новая CLR запись для дальнейшего анализа.
3. Если эта запись CLR -> вместо неё добавляется её значение undoNextLSN. Если этого значения нет, запись удаляется из TT.

Посмотрим на примере выше. 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

Undo фаза смотрим в TT. Видит там запись 1, 32 и начинает её откатывать при помощи clr записи. После отката новое состояние 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"]
34. [32, 1, X, "clr", k-=9, 30]

А TT обновится до

1, 34

Добавление новой CLR записи в WAL следует такому же write-ahead протоколу, как и добавление обычных записей. Другими словами, эта запись не может попасть на диск, пока она не будет сохранена в журнал WAL.

При откате 32 записи видно, что эта транзакция связана с записью 30 (поле prevLSN). Это значение копируется в undoNextLSN CLR записи. Таким же образом undoData копируется в redoTheUndoData.

Пусть в этот момент происходит ещё 1 рестарт. ARIES же обещает, что всё будет работать и при рестартах. Посмотрим!

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"]
34. [32, 1, X, "clr", k-=9, 30]
-- RESTART 2

Снова запустим анализ. После анализа первых 4 записей (30-33) состояние TT и DPT такое же, как было и раньше в конце первого рестарта.

DPT:
X, 30
Y, 31
TT:
1, 32

Но анализ ещё не завершен, ведь есть запись под номером 34. После обработки этой записи DPT не изменится, а вот TT поменяется на

1, 34

Как видите это ровно такое же состояние, в котором был TT во время undo фазы предыдущего рестарта. ARIES пришёл ровно в тоже самое состояние, что и раньше.

Redo фаза снова обновит состояние буферов страниц. Останется только завершить процесс восстановления в undo фазе. Снова смотрим на запись с самым большим LSN — это запись 34. Пункт 3 алгоритма говорит, что если запись является CLR, значение в TT должно обновиться на undoNextLSN. Новое состояние TT:

1, 30

Снова ищем самый большой LSN по TT. Находим 30. Запись update, поэтому надо откатить при помощи CLR. У записи нет prevLSN, значит это последняя CLR запись. Теперь состояние 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"]
34. [32, 1, X, "clr", k-=9, 30]
35. [34, 1, X, "clr", k-=3, -]

А в TT получится:

1, 35

Остался последний шаг — вытаскиваем самый больше LSN из TT — 35. Это CLR, значит значение в TT для транзакции 1 в соответствии с пунктом 3 нужно обновить на undoNextLSN, но там "-". Это значит, мы произвели полный откат транзакции и запись можно удалить. Наконец-то в TT больше нет записей. Состояние базы данных успешно восстановлено.

ARIES (8/8)

Заключение.

ARIES — эффективный и достаточно простой алгоритм записи и восстановления. Он работает за счёт полного повтора истории. Как было показано на примере, он продолжает работать даже при множественных рестартах подряд. ARIES может работать в steal + no-force режиме buffer manager. Другими словами, он не требует чтобы коммиты записывали грязные страницы на диск, а также позволяет записывать страницы даже во время транзакций.

ARIES проводит восстановление в три шага.

Сначала происходит анализ записей в WAL. При анализе восстанавливается состояние таблицы грязных страниц DPT, а также таблицы незавершённных транзакций TT.

В следующей фазе — Redo, состояние буферов страниц в памяти приводится в полное соответствие с WAL. После исполнения Redo, внутреннее состояние страниц идентично тому, каким оно было до начала процесса восстановления.

Наконец, в фазе Undo откатываются транзакции, которые не успели сделать коммит до начала рестарта. Во время Undo каждой update записи WAL, относящейся к незавершённой транзакции, в обратном хронологическом порядке записывается CLR запись. Точно такая же запись обычно записывается в WAL при роллбеках в нормальном режиме работы. Такой подход позволяет с одной стороны, упростить алгоритм восстановления при повторных рестартах, а с другой, ограничить максимальное количество новых записей в WAL, которые будут созданы во время восстановления. При создании CLR использует протокол write-ahead, как и при обычной записи в нормальном режиме.

Я уже вышел за все мыслимые и немыслимые рамки размера поста, поэтому, пожалуй, закончу. Есть ещё пара вещей, о которых не рассказал.

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

Второе — каждая фаза ARIES может не только без проблем пережить рестарт, но также может запускаться параллельно и безопасно в несколько потоков. Это достигается за счёт локов на уровне страницы. Более того, во время каждой фазы БД может делать чекпоинты. Так к примеру чекпоинт после фазы анализа позволит не делать анализ повторно, если второй рестарт произойдёт сразу.

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

Четвёртое — есть распределёный ARIES! D-ARIES: A Distributed Version of the ARIES Recovery Algorithm (ссылка). А ещё ARIES (вернее WAL) оптимизирован под жёсткие диски. SSD последовательная запись нужна в меньшей степени, т.е. на них можно сделать более эффективный алгоритм. Пример такого алгоритма есть в работе From ARIES to MARS: transaction support for next-generation, solid-state drives (ссылка). Это всё добро тоже в беклоге.

Источники:

[1] ARIES whitepaper https://dl.acm.org/doi/10.1145/128765.128770
[2] Прекрасное youtube видео про ARIES от Dr. Jens Dittrich https://www.youtube.com/watch?v=S9nctHdkggk . Там целый университетский курс видео-лекций про базы данных.
[3] Ramakrishnan, Gehrke — Database Management System Third Edition (ссылка)
[4] Peter Bailis Joseph M. Hellerstein Michael Stonebraker — Readings in Database Systems Fifth Edition. Она же Red Book. (ссылка)

Ссылка на первый пост из 8.

Дедлоки (1/2)

Всех с наступившим! 🐌

Решил я тут почитать, что умные дядьки пишут про дедлоки. Как обычно оказалось, что поверхностное понимание уровня «пройти интервью» неверно от начала до конца, а в реальности всё супер интересно и конечно известно уже последние лет 50.

Дедлок или deadly embrace, как их называл товарищ Дейкстра (тот самый, который алгоритм) — ситуация бесконечного ожидания, при которой группа процессов не может продолжать работу, пока «внешние силы» не совершат определенные действия. Слово «процесс» здесь не имеет отношения к процессам в операционной системе. Процесс в дедлоке — некий автомат с набором состояний. Такими состояниями могут быть «процесс А не владеет ресурсами» или «процесс B владеет ресурсом alpha и пытается получить ресурс beta». На самом деле определение не совсем корректное в 100% ситуаций, но для обсуждения большинства подходов подойдёт.

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

Такой дедлок называется либо ресурсным, либо interleaved дедлоком. Первое более привычное и популярное название, второе я нашёл только в [4]. Для возможности его возникновения необходимо выполнение 3 условий:

1. Exclusive access. Только один процесс может захватить ресурс одновременно.
2. No-preemption. Процесс, захвативший ресурс, не может быть прерван.
3. Hold and wait condition. Должны разрешаться ситуация, при которой процесс захватил сначала один ресурс, а теперь ждёт пока освободится второй. Не отпуская при этом первый.

Наличие этих условий в системе ещё не гарантирует возникновение дедлока! Это только необходимые условия. Их наличие означает существование unsafe region[5] — такого набора состояний процессов, попав в которое, ни один из процессов не может завершить свою работу.

При наличии unsafe region достаточно найти лишь 1 набор состояний, чтобы обеспечить дедлок. Оно же последнее условие:

4. circular wait condition. Процессы и ресурсы должны иметь возможность собираться в «цепочку». К примеру: Процесс A владеет ресурсом a при этом хочет захватить ресурс b, которым владеет процесс B, который хочет завладеть ресурсом a. Если обозначить эти отношения стрелочками:

a -> A значит процесс A владеет ресурсом a.
A -> b значит процесс A хочет завладеть ресурсом b.

Схематично получится круг (ну или квадрат):

a  -> A
^     |
|     v
B <-  b

Дедлоки (2/2)

Первый инсайт: дедлоки не возникают просто так, для них необходимо 3 условия: exclusive access, no-preemption, hold-and-wait + одно достаточное: circular wait.

Второй инсайт: чтобы побороть дедлок, достаточно избавить от одного из условий!

Пункт 2 особенно интересен, и позволяет другими глазами взглянуть на работу с ресурсами и привычные «программистские трюки». Например: почему часто разделяют локи на read-only и write-only локи? Для перформанса, конечно. Но ещё и потому что в read-only локе не может возникнуть дедлок, так как он не эксклюзивный (первое условие)!

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

С hold-and-wait тоже интересно. А что если бы процесс сразу же запрашивал все ресурсы, которые ему требуются? Или по крайней мере захватывал бы их постепенно, но при не успехе отпускал бы все уже захваченные. Такой подход, оказывается, тоже убирает проблему дедлоков. К сожалению, не каждый процесс знает наперёд ни все нужные ему ресурсы, ни порядок, в котором они будут захватываться. Опять в общем случае решить тяжело, в частном вполне. Например обычно заранее известно, сколько памяти и CPU нужной новой виртуалке/контейнеру, а это тоже ресурсы, за которые тоже может быть конкуренция. Там правда ситуация не обязательно завершиться дедлоком, а скорее перемещением одного из процессов, но это детали. Раскидывать задачи по компьютерам — очень сложная задача, поэтому в как-нибудь в следующий раз.

Наконец, circular-wait. А пусть все ресурсы должны захватывать только в определенном порядке. К примеру, перечислим все ресурсы в системе от 1 до n. И добавим условие: если процесс захватил ресурс 1 <= k <= n, он может захватить только любой другой ресурс с номером m, где m < k. Другими словами, процессу сначала нужно захватить самый «высокоуровневый» ресурс, а дальше все ресурсы пониже. Наличие нумерованных ресурсов и одного условия на их захватывание также позволяет избавиться от дедлоков. Полный пруф есть в [5].

Все эти подходы можно широкими мазками разделить на 3 категории:

- Detection. Подходы, которые по графу ресурсов и их зависимостей позволяют обнаружить дедлок. Для борьбы используется preemption.
- Prevention. Цель: задизайнить систему таким образом, чтобы дедлок был невозможен. Например: пронумеровать ресурсы и ввести условие их захвата. Или запретить захватить ресурс, а затем ждать второй.
- Avoidance. Подходы, при которых система переходит только из одного «безопасного» состояния в другое. Решение о выдаче ресурса принимается динамически, к примеру во время запроса. Самый популярный алгоритм: алгоритм банкира. К сожалению для него необходимо, чтобы процессы сразу знали, какие ресурсы им нужны.
- Алгоритм страуса. Или ничего не делать. Стратегия при которой программист сажается на on-call и ему выдаётся кнопка «отмена».

Ресурсы:
1. E.G. Coffman, M. Elphick, A. Shoshani. System Deadlocks.
2. Richard C. Holt. Some deadlock properties of computer systems.
3. S.S. Isloor, T.A. Marsland. The Deadlock Problem: An Overview.
4. Gertrude Neuman Levine. Defining deadlocks.
5. Charles M. Shub. A Unified Treatment of Deadlock.

Классификация масштабируемости (1/2)

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

Начнём с самой очевидной ситуации — масштабируемость численных показателей. Этот пункт включает не только вертикальную масштабируемость (серверы пухнут), и горизонтальную (серверов становится больше), но и другие интересные проблемы. Раньше IPv4 хватало всем, а теперь приходится выкручиваться. Раньше все наши 3 nginx'а можно было запихнуть в DNS, а теперь тысячи их, не лезут! Некоторые решения ещё можно запихнуть под гребёнку «горизонтальной масштабируемости», как к примеру использование хранилищ, оптимизированных на запись или разделение читателей и писателей. Но некоторые компании делают совершенно безумные вещи!

Зачем фейсбук пропускает запрос через L4+L7 балансировщик, а затем делает это внутри ДЦ ещё раз? [1] Это не просто «горизонтальная масштабируемость». Это совершенно другой уровень борьбы с физическими ограничениями интернета и старых протоколов.

Немного перпендикулярная, но связанная ситуация — оптимизация затрат, важность которой растёт линейно с ростом, собственно, затрат. На уровне стартапа с 5 людьми со стоимостью всей инфраструктуры в пару тысяч в год, экономия 1% процессорного времени скорее всего копейки. Для какого-нибудь гугла 1% — это десятки миллионов долларов.

Далее идёт географическая масштабируемость, которая приносит за собой а) задержки б) прекрасные возможности для оптимизации. К примеру, так ли сервису такси в Москве важно знать, что точно такой же сервис такси доступен в Нью-Йорке? Явно никто в здравом уме на закажет такси из Нью-Йорка в Москву. Значит ли это, что их можно разделить, тем самым упростив поддержку локальных серверов? Ответы совершенно неочевидны. Для бизнес-анализа данные от разных частей одного приложения собрать всё равно придётся, но для непосредственно оперирования системы вроде как нет.

Гео-распределённость приносит за собой ещё одну проблему — необходимость в административной масштабируемости. «Административный» не самое удачное слово с миллионом смыслов, но я его краду из [2], так что оставим как есть. Речь идёт про особенности роста большого бизнеса, оказывающие влияние на техническую составляющую. Например, как в техническом плане происходит поглощение одной компании другой? Каким образом мега-корпорация интегрирует продукты от сотни других компаний, так сказать "at scale"? Здесь есть большая часть юридических вопросов, но от чисто технических проблем всё равно не убежать.

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

Часть 2 🔽.

Классификация масштабируемости (2/2)

Наконец, моё любимое — масштабируемость кадров [3]. Как сделать так, чтобы 10 разработчиков не перессорились, пока пишут вместе код? А когда их станет 100? А как в такой толпе ещё бы сделать так, чтобы а) все придерживались одних стандартов и б) количество коммуникаций росло медленнее, чем линейно? Линейный рост коммуникаций быстро перестаёт работать. Люди не машины, и постоянно общение даже с десятком коллег — уже тяжело. Куда уж там ещё расти. Связанная вещь: какой должен быть процесс найма, чтобы нанять 15 разработчиков за год? А пять тысяч? И насколько они отличаются.

Ещё более интересная проблема: как безопасно менять код, которые пишут несколько тысяч человек в день? А как его разворачивать? Гугл вот для этого живет в самописном монорепозитории, в который несколько десятков тысяч коммитов в месяц делает робот[3]. Но самое-то интересно: другие компании не сильно меньше не живут в монорепе, не пользуются роботами (или скрывают) и нормально себя чувствуют. Кто более прав? 🤷‍♂️

Отдельная, но связанная тема: как поддерживать продукты, которым уже по 10+ лет? Разработчики редко столько работают в одной компании, т.е. эти знания каким-то образом нужно передавать. В [4] есть глава про это, и про другую интересную тему: deprecation продуктов, ака как правильно выводить что-то из эксплуатации.

Здесь ещё можно было бы припомнить и безопасность, ведь когда становится больше «всего», становится и больше дыр. И R&D с инновациями в больших компаниях. Когда разработка чего-нибудь новенького переходит из разряда «приятный бонус», в необходимое конкурентное преимущество. И про организацию роста сотрудников и стратегий удержания. Как обычно, чем дальше в лес, тем больше дров.

Источники:

1. Usama Naseer, Luca Niccolini, Udip Pant, Alan Frindell, Ranjeeth Dasineni, Theophilus A. Benson Zero Downtime Release: Disruption-free Load Balancing of a Multi-Billion User Website.
2. B. Clifford Neuman. Scale in Distributed Systems.
3. Rachel Potvin Josh Levenberg. Why Google Stores Billions of Lines of Code in a Single Repository
4. Titus Winters, Tom Manshreck, Hyrum Wright. Software Engineering at Google. Не знаю на что дать ссылку, но официальная бесплатная PDFка точно где-то есть.

Ссылка на часть 1.

Scaling Memcache at Facebook

За последние 4.5 месяца я успел эмигрировать в Дубай, получить лычку Staff Engineer, попасть под сокращение (потерять лычку :D), пройти 22 собеса за 2 недели и найти ещё одну работу. Если кто-то хочет в Дубае найти финтех или перевезти сюда котов, пишите. Я походу стал экспертом.

Когда-то давно у меня был план сделать цикл с разбором работ по алгоритмам консенсуса, но этот план теперь там же где российская экономика и мои нервишки, поэтому ближайшие пару постов будут более расслабленными. А именно: несколько работ о том, как компания X сделала Y. Такие пейперы легко читать, а состоят они в основном из практичных советов и цифр, нежели зубодробительной математики и фундаментальных доказательств. Сегодня поговорю о Scaling Memcache at Facebook от 2013 года (ПДФ на usenix). Формат тоже попроще: больше повествования и меньше тягомотины, но ничего не обещаю. Поехали!

Итак Фейсбук решил доработать и так неплохо работающий memcached, потому что могут. В работе memcached — это сам кеш, а memcache (без d) — кластер, на котором крутятся memcached. Первая интересная находка — использовать UDP для get запросов вместо TCP. Set и delete всё ещё по TCP. Результат: теряются 0.25% запросов, зато -20% latency в среднем. В работе -20% на графике average of medians. Я не очень понимаю этот оборот, но походу это в районе 50% процентиля, потому что медианы...? В любом случае, в 95-ом процентиле прироста почти нет, т.е. быстрее становятся медленные запросы, что хорошо. Правда 0.25% потерь — это всё-таки много, поэтому имплементация оборачивает потерянные пакеты и out-of-order delivery в клиентские ошибки, а клиент там сам уже ретраит. Фейсбуку норм, потому что некоторые страницы делают тысячи обращений в memcache, и сделать пару ретраев недорого.

Кстати о ретраях и ошибках. Фейсбук использует отдельный пул под названием gutter, размером 1% от общего размера memcache для обработки запросов с ошибкой. Клиент делает запрос, не получает ответа (т.е. не cache miss, а прямо Connection Error), далее делает повторный запрос в gutter. Если в gutter данных тоже нет, они добавляются туда. Данные в gutter устаревают быстро, чтобы часто не инвалидировать. Такой подход мало того что защищает от 99% ошибок при доступе к memcache, так ещё и превращает 10-25% промахов в попадания. К тому же дополнительный слой защиты бекенда от запросов. В идеальном мире данные есть в memcahce, если тот умер, то в gutter, только если и в нём нет, запрос идёт в бекенд. Правда трейдофф тоже есть, данные в gutter могут быть старыми. Потому и время жизни записей в gutter короткое.

Ещё пара фишек с удалением и записью. Во-первых, при cache miss, клиенту выдаётся lease token на ~10 секунд (дефолт) на конкретный ID для записи данных. Другие клиенты не могут обновить запись, пока у кого-то есть токен. Это позволяет бороться с циклами запись-перезапись при конкурентном доступе. Во-вторых, lease token помогает в борьбе с thundering herds — ситуации, когда много клиентов пытаются получить один и те же данные. Если клиент пытается получить запись, на которую выпущен lease token, клиент самостоятельно уйдёт в небольшое ожидание и повторит запрос ещё раз, потому что обычно между захватом lease token и самой записью проходит несколько милисекунд. Так запрос не попадёт в cache miss, а вернётся с более долгой задержкой.

Связанная, но немного отдельная проблема — это конкурентные удаления. При удалении, записи какое-то время ещё хранятся в особой структуре данных (какой — не написано) При промахе, клиент может по своему усмотрению либо получить lease token для дальнейшей записи, либо получить устаревшие данные. Опять cache miss превращается в hit, но со старыми данными. Удобно.

В работе есть ещё пара интересных моментов с разогревом нового инстанса из соседнего, а не из бекенда, батчинг запросов, и как решить read-your-writes (спойлер: помечать записи и читать с мастера), но для первого поста за 4.5 месяцев я думаю достаточно.

Dynamo: Amazon’s Highly Available Key-value Store (1/3)

Сегодня две работы. Первая: та самая статья про Dynamo из 2007 года (pdf), когда она ещё не была частью AWS и не называлась DynamoDB. "Та самая" эта работа, поскольку это редкий случай, когда куча разных идей по построению хранилищ были объединены в единое решение, которое не только работало, но и обеспечивало очень большой сайт. И о котором написали. В те далекие времени Amazon был e-commerce в первую очередь, AWS появился всего годом ранее, а DynamoDB так вообще вошла в сервисы AWS только к 2012 году. Вторая — свежий пирожок, опубликованный буквально пару дней назад спустя 10 лет эксплуатации сервиса DynamoDB (usenix pdf).

При создании Dynamo Amazon исходил из нескольких ограничений:

- key-value. Логика большинства сервисов, к примеру корзины товаров, достаточно простая, и реляционная модель не принесёт значительного успеха.
- Heterogeneity & Symmetry. Все узлы выполняют одну и ту же работу. Но узлы разные, значит они могут выдерживать разную нагрузку.
- Запись всегда должна быть успешной. Пусть и с конфликтами.
- Variable consistency. Клиент сам может выбрать соотношение читателей и писателей в кворуме R+W > N.

Теперь как это всё добро работало.

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

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

Следующая проблема — репликация. При факторе репликации N, данные нужно забросить ещё на N - 1 ноду. Как их выбрать? Решение гениальное: просто пихать данные на следующие N - 1 нод в кольце 🤷‍♂️. Если кольцо состоит из A -> B -> C -> D -> A, и фактор репликации 3, то данные на узле A также будут на узлах B и C. С виртуальными узлами чуть сложнее, потому что нет гарантии что следующий виртуальный узел находится на другой физической машине. Но это решается чуть более умным программированием.

Dynamo: Amazon’s Highly Available Key-value Store (2/3)

Теперь к главное проблеме: как сделать так, чтобы запись всегда была успешной? Несколько трюков. Во-первых, при факторе репликации N, каждый узел содержит preference list, состоящий из более чем N узлов. В идеальном мире, запись будет идти в один из N узлов, но если какая-то часть из них недоступна, запись пойдёт через hinted handoff в другой узел. Hinted Handoff — это такая особая запись на "чужую" ноду с хинтом. Допустим, если обычно запись идёт в A, B, C, но запись нужно сделать в D, можно сообщить узлу "вот данные, но они вообще были для узла A`". Тогда `D сохранит данные, но также будет периодически проверять, не поднялся ли A. Как только это произойдёт, D перельёт свои данные в A, где им и место, и удалит их у себя.

Во-вторых, для записи используется vector clock. Каждая запись содержит не только данные, но также номер сервера и значение монотонно растущего счётчика. Сервер, который записывает данные, обновит значение счётчика или добавит в список новый счётчик. По двум таким записям очевидно, можно ли автоматически разрешить конфликт. К примеру, если есть две записи (node: 1, version: 5) и (node: 1, version: 2), очевидно, что вторую можно отбросить, так как она старая, по сравнению с новой записью того же сервера. Именно таким образом работает read repair в Dynamo. Когда при чтении какой-то из узлов возвращает устарелые данные, они обновляются. Но если запись будет (node: 1, version: 4) и (node: 2, version: 5), просто разрешение конфликтов уже не сработает.

И здесь ребята из Amazon поднимают довольно важную проблему. База данных редко знает семантику данных. Для базы это всё просто наборы бит, поэтому на уровне хранилищ редко можно получить хорошую тактику разрешения конфликтов. Можно использовать к примеру last-write-wins. Для некоторых видов данных можно даже наворотить CRDT, которые не факт что разрешат конфликт семантически правильно, но точно разрешат его одинаковым образом на всех нодах.

Решение: отдавать конфликты клиенту! Уж программист то точно знает, что две конфликтные записи семантически — это две версии корзины товаров, с вполне понятным алгоритмом их слияния. Немного странно из get запроса получить гипотетически 2 версии данных, зато конфликты будут разрешаться правильно.

Теперь про failure detection и добавление новых нод в кластер. На момент 2007 года у Amazon каждый отдельный сервис сам поднимает и менеджерит кластер Dynamo. Это значит, что общее количество узлов обычно измеряется в сотнях, а не тысячах. В такой ситуации при добавлении новых узлов, хорошо себя показывают gossip алгоритмы (Про gossip писал здесь). Каждый узел самостоятельно строит картину кластера как раз основываясь на сообщениях, полученных по gossip. Интересный момент: тот же gossip не используется для передачи информации о неработающих узлах. Т.е. у Dynamo фактически отсутствовал global failure detection механизм, ноды содержали информацию о неработающих узлах локально (не можешь достучаться — не работает), но не делились ей. Одна из причин: операции по добавлению и удалению узлов делаются в ручном режиме, такой алгоритм просто не нужен.

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

И последний интересный кусочек про перформанс. Задержка при записи в кворум из W узлов определяется задержкой самого медленного узла. А что если при записи в W узлом писать только в буфер в памяти, а в остальные N-W узлов писать в диск? Тогда задержки меньше, при этом запись скорее всего будет в других узлах. Этот хак позволяет Dynamo в 5 раз уменьшить задержки в 99.9 процентиле в пиковые загрузки.

Dynamo: Amazon’s Highly Available Key-value Store (3/3)

Совсем чуть-чуть про работу 2022 года (usenix pdf).

Что не сработало: Symetry подход с preference list. В Dynamo запись может быть через любую из N нод. Выбираться скорее всего будет первая, но не обязательно. В DynamoDB реплики выбирают лидера через Multi-Paxos и только он отвечает за запись и за "консистентные" чтения. Лидер же записывает WAL и реплицирует его follower-узлам.

Интересная особенность произошла с hinted handoff. Не написано что он НЕ используется, но появился новый хак. Обычно узел хранит данные в виде B-Tree + WAL с лидера. Хак: Лидер может создать специальную Log replica — ноду, в которой только WAL. Такой узел создать быстрее, так как с ним не нужно делиться всем B-Tree, при этом он помогает со сбором кворума.

Что всё ещё работает: ноды и раньше не поддерживали global failure state. Но теперь есть Paxos, в котором ноды сами могут начинать голосование за нового лидера, если посчитают, что старый умер. Иногда ноде только кажется, что лидер умер, что редко, но приводит к ошибкам с двумя лидерами. Такое поведение называют gray failure. Причины: лагающая сеть, медленные машины, да куча всего. Чтобы этого избежать, узел сначала опрашивает соседей, чтобы узнать у них, видят ли они мастера. Если соседи мастера видят, то нода отказывается от идеи попытаться начать раунд голосования за нового лидера.

Что совершенно отвал башки: для проверки алгоритма репликации, как и для S3, в DynamoDB Amazon использует TLA+ модели. Говорят, что парочку неочевидных багов они уже нашли. Кстати, если хотите познакомиться в TLA+ поближе, тут недавно запустился https://learntla.com!

No updates update

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

- Нашел работу Staff инженером и переехал в Дубай в маленький стартап,
- Попал под сокращение 30% сотрудников через 2.5 месяца. Fun fact: за два дня до сокращения согласовал с CTO + CPO "стратегию" на следующий год. Плохая была стратегия 🤔
- Нашел новую работу за 10 дней, но снова Senior, потому что стремно в панике запускать ещё один поиск на Staff позицию,
- За следующие полгода прочитал 0 "технических" книг, 0 пейперов, сбил режим сна, прошёл десятка два игр, начал носить очки, восстановил режим сна...

И вот только сейчас почувствовал силы что-то снова писать. Всем привет! План такой:

Во-первых, никаких "публичных обещаний" и графиков постов, которые я ни разу и не соблюдал. Я понял что физически не могу повторять за principle инженерами из Google и AWS с двумя лонгридами в неделю.

Во-вторых, разборы статей. Мне очень нравится как получились разборы целых тем, как в случае с CAP теоремой, дедлоками или Gossip'ом. Сам даже перечитываю. Но понять одну статью — это квест на 6-20 часов, а писать такие посты даже тяжелее, чем читать. Они будут, но скорее всего поменьше.

В-третьих, хочу начать ковырять базы данных руками. В этой печальной экономике звучит как очень плохой план, но я не закончил даже с четвертью своей карьеры (10/10 пост), поэтому времени ещё вагон. Готов убить на потенциальную ошибку пару лет. Плюсы: будет интересно. Минусы: может быть не будет.

В-четвертых, у меня скопился беклог из десятка постов на отвлечённые темы от отзывов на нетехнические книжки до баек про внедрение Observability. Так что легкое чтение снова вернётся. Ура.

Observability (1/2)

Последний месяц я внедряю в компании Observability с DataDog взамен старых добрых Prometheus & Grafana. Пока команды в восторге, MTTD (mean time to detect) упал с часов до минут, operations теперь могут заниматься планами на будущее, а не тушением пожаров. Сплошной успех, поэтому расскажу что это такое, и почему классические дашборды должны умереть.

Observability — это способность понимать поведение системы при взгляде снаружи, без знания того, как система работает изнутри. Система с observability позволяет разобраться в причинах неизвестных ранее проблем (unknown unknown). Она предоставляет достаточно данных, чтобы ответить на вопрос "что происходит?" на любом уровне: от единичного запроса до региона или системы в целом. И самое главное — она уже хранит все необходимые данные. Если вам нужно сделать ещё 1 дашборд или дописать кусочек кода, чтобы собрать ещё одну метрику — это не observability.

Основной инструмент observability это распределённые трейсы , но с несколькими особенностями, в основном приходящимися на хранилище для этих трейсов.

Поддержка high-cardinality. Cardinality — это мощность. Как мощность множества. High-cardinality — данные, у которых может быть много возможных значений. Например уникальный ID пользователя имеет максимальную cardinality, потому что он никогда не повториться для другого пользователя. Год заказа — низкую cardinality, потому что он всегда одинаковый в течение года.

Трейс и хранилище трейсов должны содержать не только базовую информацию, такую как ID сервера, регион, время исполнения, тип запроса, но также и специфичные для конкретного запроса и конкретной команды (разработки) параметры: ID пользователя, номер заказа, дата регистрации, идентификатор сессии и т.д. Именно high-cardinality данные позволяют отвечать на специфичные запросы, например "какая средняя latency на запросы в Германии для серверов, развернутых на AMI amzn2-ami-hvm-x86_64-gp2 для пользователей, делающих первый заказ?". Ответ на такие вопросы без изменения системы — вся суть observability.

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

Быстрый поиск. Observability нужна чтобы отвечать на вопросы здесь и сейчас. Это значит: 1) данные должны быстро попадать в систему, 2) данные можно быстро вытащить из системы, что сложно, из-за high-dimensionality и high-cardinality, но 3) данные довольно быстро теряют полезность, а значит их довольно скоро можно удалить. Главная полезность в том, чтобы решить текущую проблему, а не анализировать трейсы спустя год или два, хотя технически такое тоже возможно.

Observability (2/2)

Цель быстрого поиска в поддержке core analysis loop — подхода к решению "любой" проблемы:

0. Получить алерт или другое оповещение о том, что что-то идёт не так
1. Посмотреть визуализацию трейсов: есть ли явные outliners? Прослеживается ли корреляция между разными данными?
2. Просмотреть данные по разным dimensions, к примеру сгруппировать по статусу запроса, региону, номеру дата центра. Цель: убрать максимум данных, чтобы outliners всё ещё были видны, другими словами — сузить область в которой скорее всего находится проблема.
3. Применить фильтр из 2 и вернуться к пункту 1. Повторять до того, как проблема не станет очевидной. Для примера: на первом шаге смотреть на весь регион, на второй на одну availability zone, на один ДЦ, на одну стойку в ДЦ и т.д.

Чтобы получить мощный инструмент Observability, достаточно просто устроиться в Meta  или Google, которые свой шарманки сделали лет эдак 10 назад. Для всех остальных есть вендоры: Honeycomb, Datadog, Lightstep и пр. Но можно начать играться и бесплатно через OpenTelemetry — это стандарт, которому пытаются соответствовать все вендоры с разной степенью успеха. Первый шаг — инструментация кода, чтобы начать собирать трейсы + отправлять их куда-то. Второй — добавление кастомных business-specific тегов или целых трейсов. Технически всё достаточно просто, а про "социальную" сторону я расскажу в следующий раз.

Источники:
- Observability Primer от OpenTelemetry
- Charity Majors, Liz Fong-Jones, George Miranda Observability Engineering

Вспомнил, что у меня завалялся substack и начал потихоньку переводить в него свои посты из внутреннего блога компании, скопившиеся за последний год. Первый просто — что вообще такое ваши эти Service Level Indicators.

https://open.substack.com/pub/sharkinit/p/service-level-what-part-1-defining?r=36tm5&utm_campaign=post&utm_medium=web

Параллельно, я кажется стал немного понимать, почему сложно что-либо менять одновременно в 5-6 инженерных командах, но пока не совсем понимаю, как это переложить в слова. Что-нибудь придумаю :D