Главная » Хабрахабр » Как устроены базы данных

Как устроены базы данных

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

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

Этим мы, в том числе, и займемся. Тем не менее, теоретические знания иногда полезно освежить.

А кроме того, отвечает за продвижение Postgres-технологий, выступает на конференциях и рассказывает людям, как с ними работать. О спикере: Илья Космодемьянский CEO и консультант в компании Data Egret, специалист по базам данных PostgreSQL, Oracle, DB2.

Ниже материал по докладу Ильи на РИТ++ 2017, который не был связан с какой-то конкретной базой данных, но охватывал многие основные аспекты.

Для чeго это нужно знать?

Хранение и обработка данных — mission-critical задача любой компьютерной системы.

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

Один из докладчиков на конференции сказал: «20 лет назад я написал свою базу данных, только не знал, что это она!» Этот тренд в мире очень развит. Все пытаются изобрести базу данных. Все стараются так делать.

Многие базы данных — это очень старые технологии. Для работы с данными база данных — это очень удобная штука. Они разрабатываются последние полвека, в 70-х годах уже были базы данных, которые работали по схожим принципам, что и сейчас.

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

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

Если взять PostgreSQL или Oracle, то с некоторым бубном можно работать даже с очень старыми версиями из новых языков программирования — хорошо и здорово. В большинстве баз данных интерфейс очень консервативный.

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

Потом начнутся блокировки и прочие вещи, и в какой-то момент вы поймете: «Ой, зачем я все это делаю?» Если вы попробуете написать свое простенькое персистентное хранилище, все просто будет только первые 15 минут.

Об этом и поговорим.

Уровни работы с данными

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

  • Слой доступа к данным, который удобно использовать из языков программирования;
  • Слой хранения. Это отдельный слой, потому что обычно хранить данные удобно другими способами, чем использовать: эффективно по памяти, выравнивать, складывать на диск. Это к вопросу о schemaless: схема, которая удобна для хранения, не удобна для доступа.
  • «Железо» — слой, где лежат данные, причем там они организованы еще третьим способом, потому что дисками управляет операционная система, и общаются они только через драйвер. В этот уровень мы не будем сильно вникать.

Для слоя доступа к данным есть требования, в выполнении которых мы заинтересованы, чтобы было удобно работать:

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

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

То есть, если мы что-то записали в базу данных, мы должны быть уверены, что мы это получим обратно. В то же время они должны быть надежно сохранены и надежно воспроизведены.

В новых базах данных, типа MongoDB, Cassandra и прочих, такие проблемы тоже случаются. Если вы работали со старыми базами данных, например, FoxPro, то знаете, что там часто появляются битые данные. Может быть, просто их не всегда замечают, потому что данных уж очень много и заметить сложнее.

Это как бы допущение, поскольку мы все-таки будем говорить о теоретических вещах. Для «железа» на самом деле важна надежность. Как заменить вовремя диск в RAID — это сегодня для нас забота админов. В нашей модели, если что-то попало на диск, то мы считаем, что там все хорошо. Мы не будем глубоко погружаться в этот вопрос, и практически не будем касаться того, насколько эффективно хранилище организовано физически.

Чтобы решать эти проблемы, есть некоторые подходы, которые очень похожи у разных хранилищ данных — и новых, и классических.

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

Он высокоуровневый, декларативный, а нам хочется объектов, поэтому появилась идея, что SQL не нужен. Многие Key-value-storage в основном делались для того, чтобы из любимого языка программирования было проще ходить за данными, а SQL не очень хорошо вяжется с любимым языком программирования.

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

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

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

Опять же, если что-то пошло не так и база данных упала, нам нужно ее быстро поднять.

Наверное, вы знаете, что база данных надежно работает только тогда, когда есть механизм, чтобы ее быстро поднять, если она упала.
Как вы считаете, можно ли написать 100% надежное отказоустойчивое хранилище?

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

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

Слой хранения

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

Слой хранения обеспечивает:

 ✓ Параллелизм и эффективность.

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

 ✓ Надежность: восстановление после сбоев.

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

Конкурентный доступ

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

Ниже код на несуществующем языке программирования.

account_a {
balance = 1000,
curr = ’RUR’
} send_money(account_a, account_b, 100);
send_money(account_a, account_c, 200);
account_a->balance = ???

Допустим, у нас есть банковский счет с балансом в 1 000 рублей, и есть 2 функции. Как они устроены внутри, нам сейчас не важно, эти функции переводят с аккаунта a на другие банковские счета 100 и 200 рублей.

Скорее всего, вы ответите, что 700. Внимание, вопрос: сколько денег окажется в результате на балансе счета a?

Проблемы

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

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

Если мы это делаем одновременно, возникнет конфликт. В последовательности «прочитали значение на балансе», «записали на другой баланс», важен вопрос — когда мы читали этот баланс? Обе функции выполняются примерно параллельно: прочитали одно и то же значение баланса, перевели деньги, записали каждая свое.

Такое, к сожалению, бывает, если не относиться к этому с должным вниманием. Может возникнуть целое семейство конфликтов, в результате которых на балансе может оказаться 800 рублей, 700 рублей, как должно быть, или что-то побьется, и на балансе окажется null. Как с этим бороться, мы и поговорим.

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

Они тогда просили совета у общественности и примерно обозначили, сколько логов писала база данных писала. Если помните, несколько лет назад была история, когда у Сбербанка упал Oracle и процессинг карточек остановился. Это огромные количества и конкурентные проблемы.

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

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

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

В принципе, нам нужно то же самое сделать с данными, которые мы пишем на диск.

Как улучшить ситуацию?

 ● Операции должны быть независимы друг от друга — изолированость.

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

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

 ● Операция происходит по принципу «все или ничего» — атомарность.

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

 ● Нужен механизм как проверить что все произошло правильно — консистентность.

Мы все знаем, что есть арифметика, здравый смысл и Уголовный Кодекс, который следит за банками и бухгалтерами, чтобы они не сделали чего-то противозаконного. Я спрашивал, сколько денег получилось на балансе в нашем примере, и вы почему-то сказали, что 700. Если мы говорим, о базах данных, там их гораздо больше: внешние ключи, констрейнты, все дела. Уголовный Кодекс — это одна из частных версий консистентности.

ACID-транзакция

Действия с данными, которые обладают свойствами атомарности, консистентности, изолированности и Durability — это определение ACID транзакции.

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

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

  1. Пессимистические шедулеры;
  2. Оптимистичные шедулеры;
  3. Гибридные шедулеры и основанные на упорядочивании TimeStamp происходящей транзакции.

Шедулер — это компонент, который обеспечивает сериализацию и правильное выполнение транзакции.

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

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

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

Мы ожидаем, что программисты напишут плохой код, поставщик поставит плохое железо, Марь Иванна выдернет из розетки сервер, когда будет мыть пол — чего только может не быть! Как люди, работающие с базами данных, мы на самом деле всегда пессимисты.

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

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

Семантика Эрбрана

Небольшое лирическое отступление, которое поможет понять, что будет происходить дальше. Жак Эрбран — французский математик первой половины XX века, который, кстати, изобрел рекурсию. Он придумал еще в докомпьютерные времена обозначать транзакции следующим способом:

Расписание транзакции включает в себя операцию — r (read — чтение) или w (write — запись). Здесь S — от слова schedule (расписание). Еще бывает b (begin), с (commit) и т.п.

Одна транзакция просто читает данные из какого-то ресурса (x), а вторая транзакция его тоже читает, делает какую-то математику на основе этих двух чтений x и записывает что-то в y. Что удобно — у нас есть 2 транзакции (цифры 1 и 2).

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

Для чего все это нужно?

Two Phase Locking

Один из основополагающих алгоритмов в современных базах данных — это так называемое двухфазное блокирование или 2PL (Two Phase Locking).

Двухфазное оно, потому что было подмечено, что для оптимизации взятия и снятия блокировок в базе данных удобно сделать это в 2 присеста:

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

Это позволяет более эффективно шедулить транзакции, чтобы они не ждали.

Видно, что операция записи в первой транзакции ресурса x имеет ненулевое время, поскольку запись занимает какое-то время — пока диск повернется, пока странички туда уйдут и т.д. На рисунке 3 линейки обозначают транзакции и время их исполнения.

Но вторая транзакция тоже должна прочитать x. Когда она начинается, в этой модели нет никаких других транзакций, поэтому запись началась и пишется. Линия становится пунктирной — это означает, что транзакция ждет блокировки, которую выставила транзакция t1. Эта транзакция не может взять блокировку на чтение x по той простой причине, что x в этот момент пишется другой транзакцией.

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

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

Рекомендую книгу «Transactional Information Systems» (Gerhard Weikum, Gottfried Vossen) — это фундаментальный учебник по теории транзакций.

Что плохо в двухфазном блокировании?

Почему нельзя так просто решить всю проблему со всеми базами данных с помощью одного простого волшебного алгоритма?

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

Для этого в базах данных имеются специальные системы контроля дедлоков и так называемого отстрела дедлоков. Одной транзакции нужен ресурс x, другой y, они его блокируют, а дальше им нужны крест-накрест те же самые ресурсы, и непонятно, кто должен первый отпускать блокировку. Дедлок нельзя разрешить мирным способом, а только откатом одной из транзакций.

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

Но есть и другие красивые математические подходы, искать которые можно по теме deadlock-detection.

 ✓ Второй момент, это медленно — никто не хочет ждать блокировки.

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

 ✓ Зато таким образом обеспечена сериализация.

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

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

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

MVCC — MultiVersion Concurrency Control

Версионирование данных нужно не только для того, чтобы ускорить, но еще и для того, чтобы решить некоторые разновидности конфликтов, которые могут возникнуть.

 ✓ Интуитивно все понятно — чтобы не ждать блокировку, берем предыдущую версию.

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

Если помните старый MS SQL Server и старые версии DB2, страшное дело, то там, если там пошло много блокировок, дальше началась их эскалация — все работало плохо и жить с этим было тяжело. В любом случае это обычно быстрее, чем долго ждать блокировку.

 ✓ Все современные DBMS в той или иной степени «версионники»

DB2 немножко оригинальнее на эту тему, там есть свой механизм — хранят только одну предыдущую версию. Oracle, PostgreSQL, MySQL — все «версионники» в честном виде.

Здесь больше транзакций (3 штуки), больше ресурсов (есть еще z) и 2 коммита. Это расписание, которое я рисовал раньше, но несколько более сложное. То есть обе транзакции заканчиваются коммитом.

Действительно, тут легко заметить одну штуку. Как говорят в таких случаях математики: «Легко заметить...» — я это очень люблю, особенно когда на половину доски формула. В качестве домашнего задания попробуйте понять, почему это легко заметить.

Это расписание никогда не сериализуется по той простой причине, что операция r1(y) вызовет конфликт, возможно, даже дедлок, если не будет доступна предыдущая версия y. Я вам подскажу.

Если этой версии y не будет, то операции будут конфликтовать. То есть, если здесь будет доступна предыдущая версия y, то транзакция нормально завершится, никаких проблем не будет.

Как это работает?

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

Добавляется еще такая фишка, как нижний индекс — 0, 1, 2 — это номер версии.

  • Когда мы пошли исполнять транзакцию t1, имеется чтение x0, т.е. самой изначальной версии.
  • Дальше в t2 мы начинаем записывать y другой версии, потому что он был изменен.
  • В транзакции t1, которая началась раньше, чем мы начали записывать y, до сих пор видно предыдущую версию y0, поскольку t2 еще не завершилась, и мы и спокойно начать с ней работать.
  • Поскольку транзакция t1 заканчивается раньше, чем w2(y2), то произойдет перечитываниеy,и после этого в транзакции t 2 выполнится нормальная работа, а другая транзакция просто нормально завершится.

Если попробовать представить, что здесь нет предыдущих версий, то сразу начнутся длинные пунктиры. Когда нужно будет прочитать y, не начнется сплошная линия, а будет пунктир, потому что w2(y) будет ждать, пока она завершится t1. Соответственно, расписание разъедется в ширину и все будет сильно медленнее.

Мультиверсионность на самом деле быстрее, чем блокировка, это не просто маркетинговая фича. В этом большой плюс MVCC.

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

Рассмотрим абстрактную базу данных: На самом деле мы к этому готовы, потому что транзакции выполняются так.

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

Эти данные на диске лежат специальным образом. Дальше он идет за данными, которые ему нужно прочитать и изменить. В разных базах данных по-разному. Если заглянуть глубже в хранение, они лежат фиксированными кусками (страничками) в PostgreSQL это 8Кб, в Oracle можно разного размера использовать.

Эта страничка очень удобна тем, что в ней лежит куча разных данных (фактически в ней лежат tuple (кортежи) То есть есть табличка, а в ней строчки, эти строчки упакованы в большие странички.

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

Это делается потому, что так удобнее. Если нужно поменять хотя бы одну запись хотя бы на одной страничке, вся страничка будет помечена, как так называемая «грязная». Мы рисовали на схеме ресурсы x и y — здесь это странички.

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

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

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

Это та самая бумажка, которая позволяет записывать быстро — запись в WAL последовательная, нам не надо искать, куда вставить в огромный data-файл это дело. Поэтому прежде, чем ответ от транзакции вернется снова к клиенту, происходит запись в так называемые Write Ahead Log.

Если в какой-то момент упали, то читаем назад Write Ahead Log и используя информацию об этих изменениях, можем чистые странички докатить до уровня «грязных». Мы записали в лог информацию о страничке и дальше вернули управление — все хорошо. База данных у нас снова новая.

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

Фундаментальная статья по его устройству и способе восстановления в реляционных базах данных была опубликована Моханом в 1992 году.
Этот алгоритм называется ARIES и в современном виде сделан достаточно давно.

С тех пор теории особо не добавилось — Write Ahead Log с тех пор остался Write Ahead Log. Они все используют концепцию страничек и концепцию записей изменений в лог. Лог может по-разному называться и в разных местах располагаться:

  • В MySQL он внутри InnoDB,
  • В PostgreSQL это отдельная директория, которая наконец в версии 10 стала называться WAL вместо PGX-Log;
  • В Oracle это называется Redo Log;
  • В DB2 — WAL.

В принципе, все везде более-менее одинаково — чтобы восстановиться, мы используем WAL.

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

Checkpoint

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

Или как в Word сохраняют периодически свои файлы, чтобы текст не пропал никуда. Это как в компьютерной игре — люди, когда ее проходят, сохраняются периодически.

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

Доступ к данным

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

Про это знает наш оптимизатор, то есть тот engine в базе данных, который исполняет наш запрос, написанный на нашем языке запросов. Есть странички на диске, относящиеся к таблице A и B. Данные на диске ничего не знают, к какой табличке они относятся.

С помощью последовательного sequential scan мы будем брать странички из таблицы A и из таблицы B — иногда синхронно, иногда по очереди — в зависимости от реализации. Например, если рассмотреть традиционный SQL, то обычно такая штука будет называться планом запроса.

Дальше будем накладывать на них, например, JOIN, а с результатом делать что-нибудь еще, и потом вернем ответ клиенту.

Представьте себе альтернативу: вы из какого-нибудь Python читаете все это к себе в приложение, а эти таблички могут быть на самом деле огромными, а условие JOIN может исключать 90% этих данных. Чем это удобно? На самом деле на каждом из этих этапов планировщик может решить, как сделать выгоднее. Вытаскиваете в память — там соответственно ходите по ним циклами, сортируете, возвращаете. В зависимости от метода, например, можно не делать full sequential scan, то есть не читать всю табличку, а из приложения, скорее всего, вам придется прочитать данные целиком. Например, он может выбрать метод JOIN, который может или целиком состоять из циклов, или может закэшировать одну таблицу и присоединить к ней другую и т.д.

Здесь все придумано до вас и реализовано эффективно.

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

Есть разные базы данных: объектные, графовые, документо-ориентированные. Хранить данные удобней страницами. Просто поставить на такую базу огромный объем транзакций, чтобы они работали в универсальном виде, не особо получается. В основном это все нишевые, неуниверсальные продукты, которые используются для своих целей. Шедулинг транзакций, которые мы рассматривали здесь, на объектах выглядит гораздо сложнее.

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

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

Без транзакций никак!

Транзакции, вопреки расхожему мнению, это не способ замедлить. Часто считают, что транзакции — это некий синтаксический сахар в базах данных с SQL, который просто все портит и бибикает, в смысле того, что все замедляет, потому что ждем блокировок.

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

Как говорил конструктор Туполев, когда его обвиняли в том, что он какую-нибудь модель самолета у кого-нибудь стянул: «Все самолеты одинаково устроены — чтобы летать, им нужно иметь крылья, фюзеляж и хвост!»

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

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

Если посмотреть на современные Percona server, MariaDB, MySQL 8, видно, что они в значительной степени перенимают теоретические основы и сейчас гораздо больше похожи на классические базы данных по своему устройству.

Ну что, убедились, что общие теоретические аспекты нужно знать?

Но не теорией единой… и на РИТ++, который успешно завершился, и на Highload++ Siberia уже через месяц, всегда много-много реального опыта и практических кейсов.

Например, про базы данных и системы хранения есть такие потрясающие заявки:


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Смешные и грустные истории про разработку компьютерных игр

Только через смех можно рассказывать, как плоды долгой и упорной работы распространяются по всем компьютерам страны, но не приносят ни капли дохода. Только улыбка поможет принять хорошее, честное предложение распределения прибыли 1 к 12, где 1 — разработчику, а остальное агрегатору. И трудно слегка не загрустить, слушая о том удивительном времени ...

Борщевик Сосновского. В МО ввели штрафы за распространение

1 ноября 2018 года Московская Область, без объявления войны (объявленной парой лет ранее), ввела финансовые санкции. Против собственников территорий, предоставляющих плацдарм для распространения борщевика Сосновского. Ура! Плантацию, встречающую гостей и жителей Москву сразу по прилёту в белокаменную. Мне, правда, интересно, ...