Нельзя сказать, что в этой статье вас ждут отборные потроха баз данных, но скорее рассказ про базы данных от самого начала, плюс небольшое углубление в некоторые подробности, которые Илье Космодемьянскому (@hydrobiont) кажутся важными. И есть все основания полагать, что так оно и есть.
Эта статья родилась не от хорошей жизни. Часто даже не то что начинающие разработчики, но и вполне продвинутые, не знают каких-то базовых вещей — может быть, давно учились в университете и с тех пор забыли, или им не приходилось углубляться в теорию, поскольку и так работалось нормально.
Тем не менее, теоретические знания иногда полезно освежить. Этим мы, в том числе, и займемся.
О спикере: Илья Космодемьянский CEO и консультант в компании Data Egret, специалист по базам данных PostgreSQL, Oracle, DB2. А кроме того, отвечает за продвижение Postgres-технологий, выступает на конференциях и рассказывает людям, как с ними работать.
Ниже материал по докладу Ильи на РИТ++ 2017, который не был связан с какой-то конкретной базой данных, но охватывал многие основные аспекты.
Для чeго это нужно знать?
Хранение и обработка данных — mission-critical задача любой компьютерной системы.
Даже если у вас уже 30 лет есть блог в интернете на текстовых файлах, как у некоторых создателей баз данных бывает, все равно на самом деле этот текстовый файлик — это база данных, только очень простенькая.
Все пытаются изобрести базу данных. Один из докладчиков на конференции сказал: «20 лет назад я написал свою базу данных, только не знал, что это она!» Этот тренд в мире очень развит. Все стараются так делать.
Для работы с данными база данных — это очень удобная штука. Многие базы данных — это очень старые технологии. Они разрабатываются последние полвека, в 70-х годах уже были базы данных, которые работали по схожим принципам, что и сейчас.
Эти базы очень хорошо и продуманно написаны, поэтому теперь мы можем выбрать язык программирования и использовать общий удобный интерфейс обработки данных. Таким образом можно стандартизованно обрабатывать данные, не боясь, что они будут обработаны как-то по-другому.
При этом полезно помнить, что языки программирования меняются: вчера был Python 2, сегодня Python 3, завтра все побежали писать на Go, послезавтра еще на чем-то. У вас может быть кусок кода, который эмулирует работу по манипуляции с данными, которую, по идее, должна делать база данных, а вы не будете знать, что дальше с этим делать.
В большинстве баз данных интерфейс очень консервативный. Если взять PostgreSQL или Oracle, то с некоторым бубном можно работать даже с очень старыми версиями из новых языков программирования — хорошо и здорово.
Но задача на самом деле не самая простая. Если мы начнем закапываться в глубины того, как нам не «побить» данные, как быстро, производительно и, главное так, чтобы потом можно было доверять результату, обрабатывать их, то окажется, что сложное это дело.
Если вы попробуете написать свое простенькое персистентное хранилище, все просто будет только первые 15 минут. Потом начнутся блокировки и прочие вещи, и в какой-то момент вы поймете: «Ой, зачем я все это делаю?»
Об этом и поговорим.
Уровни работы с данными
Итак, есть различные уровни работы с данными:
Для слоя доступа к данным есть требования, в выполнении которых мы заинтересованы, чтобы было удобно работать:
Для слоя хранения по-прежнему важно сохранение изначального параллелизма, чтобы все данные были не побиты, не перезаписаны, не перетерты и т.д.
В то же время они должны быть надежно сохранены и надежно воспроизведены. То есть, если мы что-то записали в базу данных, мы должны быть уверены, что мы это получим обратно.
Если вы работали со старыми базами данных, например, FoxPro, то знаете, что там часто появляются битые данные. В новых базах данных, типа MongoDB, Cassandra и прочих, такие проблемы тоже случаются. Может быть, просто их не всегда замечают, потому что данных уж очень много и заметить сложнее.
Для «железа» на самом деле важна надежность. Это как бы допущение, поскольку мы все-таки будем говорить о теоретических вещах. В нашей модели, если что-то попало на диск, то мы считаем, что там все хорошо. Как заменить вовремя диск в RAID — это сегодня для нас забота админов. Мы не будем глубоко погружаться в этот вопрос, и практически не будем касаться того, насколько эффективно хранилище организовано физически.
Чтобы решать эти проблемы, есть некоторые подходы, которые очень похожи у разных хранилищ данных — и новых, и классических.
Прежде всего для того, чтобы обеспечить универсальный и оптимальный доступ к данным, есть язык запросов. В большинстве случаев это SQL (почему именно он, мы подискутируем дальше), но сейчас просто хочу обратить внимание на тенденцию. Сначала достаточно долгое время был SQL — конечно, были времена и до него, но, тем не менее, SQL господствовал долго. Потом стали появляться всякие Key-value-storage, которые, дескать, работают без SQL и гораздо лучше.
Многие Key-value-storage в основном делались для того, чтобы из любимого языка программирования было проще ходить за данными, а SQL не очень хорошо вяжется с любимым языком программирования. Он высокоуровневый, декларативный, а нам хочется объектов, поэтому появилась идея, что SQL не нужен.
Но большинство этих технологий сейчас на самом деле придумывают какой-то свой язык запросов. В Hibernate очень развит свой собственный язык запросов, кто-то использует Lua. Даже те, кто раньше использовал Lua, делают свои реализации SQL. То есть сейчас тенденция такая: SQL опять возвращается, потому что удобный человеко-читаемый язык работы со множествами все равно нужен.
Плюс к тому по-прежнему удобно табличное представление. В той или иной степени во многих базах данных по-прежнему имеются таблички, и это далеко не случайно — таким образом легче оптимизировать запросы. Вся математика оптимизации завязана вокруг реляционной алгебры, и когда есть SQL и таблички, работать гораздо проще.
В слое хранения возникает такое понятие, как сериализация. Когда есть параллелизм и конкурентный доступ, нам нужно обеспечить, чтобы на процессор, на диск это приезжало в более-менее предсказуемом порядке. Для этого нужны алгоритмы сериализации, которые реализуются в слое хранения.
Опять же, если что-то пошло не так и база данных упала, нам нужно ее быстро поднять.
Для этого нужно восстановление, потому что, что ни делай, где-нибудь будет слабое звено и очень большие накладные расходы на синхронизацию. Мы можем сделать сотню копий на сотню серверов, а в результате сгорит питание или какой-то коммутатор, и будет плохо и больно.
Для «железа» на самом деле важно, чтобы база данных была хорошо интегрирована с ОС, работала производительно, вызывала правильные syscalls и поддерживала все фишки ядра по быстрой работе с данными.
Слой хранения
Начнем со слоя хранения. Понимание того, как он устроен, хорошо помогает понять, что происходит на более высоких слоях.
Слой хранения обеспечивает:
✓ Параллелизм и эффективность.
Другими словами, это конкурентный доступ. То есть, когда мы пытаемся получить пользу от параллелизма, неизбежно возникает проблема конкурентного доступа. Мы одновременно ходим за одним ресурсом, который может записаться не так, побиться при записи и, черт знает что еще, может при этом получиться.
✓ Надежность: восстановление после сбоев.
Вторая проблема — это внезапный сбой. Когда обеспечивается надежность, это означает, что мы не только максимально обеспечили катастрофоустойчивое решение, но важно и то, что мы умеем быстро восстановиться в случае чего.
Конкурентный доступ
Когда я говорю о целостности, внешних ключах и прочем, все как-то хмыкают и говорят, что все это они проверяют на уровне кода. Но как только предложишь: «А давайте пример на вашей зарплате! Вам переводят зарплату, а она не пришла», — почему-то сразу понятней становится. Не знаю почему, но сразу появляется блеск в глазах и интерес к теме внешних ключей, констрейнтов.
Ниже код на несуществующем языке программирования.
Допустим, у нас есть банковский счет с балансом в 1 000 рублей, и есть 2 функции. Как они устроены внутри, нам сейчас не важно, эти функции переводят с аккаунта a на другие банковские счета 100 и 200 рублей.
Внимание, вопрос: сколько денег окажется в результате на балансе счета a? Скорее всего, вы ответите, что 700.
Проблемы
Здесь начинаются проблемы с конкурентным доступом к данным, потому что язык у меня выдуманный, совершенно не понятно, как он реализован, одновременно ли исполняются эти функции и как они устроены внутри.
Мы, наверное, считаем, что операция send_money() — это не элементарное действие. Надо проверить баланс и куда переводится, выполнить контроль 1 и 2. Это не элементарные операции, которые занимают какое-то время. поэтому нам важен порядок выполнения элементарных операций внутри них.
В последовательности «прочитали значение на балансе», «записали на другой баланс», важен вопрос — когда мы читали этот баланс? Если мы это делаем одновременно, возникнет конфликт. Обе функции выполняются примерно параллельно: прочитали одно и то же значение баланса, перевели деньги, записали каждая свое.
Может возникнуть целое семейство конфликтов, в результате которых на балансе может оказаться 800 рублей, 700 рублей, как должно быть, или что-то побьется, и на балансе окажется null. Такое, к сожалению, бывает, если не относиться к этому с должным вниманием. Как с этим бороться, мы и поговорим.
В теории все просто — мы можем выполнить их одну за другой и все будет хорошо. На практике этих операций может быть очень много и делать их строго последовательно может быть проблематично.
Если помните, несколько лет назад была история, когда у Сбербанка упал Oracle и процессинг карточек остановился. Они тогда просили совета у общественности и примерно обозначили, сколько логов писала база данных писала. Это огромные количества и конкурентные проблемы.
Выполнять операции строго последовательно не очень хорошая идея еще и по той простой причине, что операций много, а мы ничего не выиграем от параллелизма. Можно, конечно, разбивать операции по группам, которые не будут конфликтовать друг с другом. Такие подходы тоже есть, но они не очень классические для современных баз данных.
В немецких правилах дорожного движения есть одна интересная история. Если дорога сужается, то правила предписывают доехать до конца, и только после этого перестраиваться по одному, а соседняя машина должна пропускать. Все перестраиваются строго друг за другом — такой знак об этом говорит.
Это живой пример возможной сериализации, когда общественность очень долго приучали к тому, что правила нужно соблюдать. Думаю, что все, кто ездит на машине по Москве понимают, насколько утопична эта картина.
В принципе, нам нужно то же самое сделать с данными, которые мы пишем на диск.
Как улучшить ситуацию?
● Операции должны быть независимы друг от друга — изолированость.
Чисто теоретически контролируемым образом операция должна знать, что происходит снаружи. Не может быть такого, что как только одна операция что-то изменила, результат сразу стал виден другой. Должны быть какие-то правила.
Это называется изолированностью транзакций. В самом простейшем случае транзакции вообще не знают, что происходит с соседними. Это действия сами в себе, в пределах одной функции никакого взаимодействия наружу нет, пока она не закончилась.
● Операция происходит по принципу «все или ничего» — атомарность.
То есть либо вся операция прошла, и тогда ее результат записался, либо, если что-то пошло не так, мы должны уметь вернуть статус-кво. Такая операция должна быть восстановима, а если она восстановима и изолирована, то она атомарна. Это элементарная операция, которая, как и результат, не делима. Она не может пройти наполовину, а только целиком проходит или целиком не проходит.
● Нужен механизм как проверить что все произошло правильно — консистентность.
Я спрашивал, сколько денег получилось на балансе в нашем примере, и вы почему-то сказали, что 700. Мы все знаем, что есть арифметика, здравый смысл и Уголовный Кодекс, который следит за банками и бухгалтерами, чтобы они не сделали чего-то противозаконного. Уголовный Кодекс — это одна из частных версий консистентности. Если мы говорим, о базах данных, там их гораздо больше: внешние ключи, констрейнты, все дела.
ACID-транзакция
Действия с данными, которые обладают свойствами атомарности, консистентности, изолированности и Durability — это определение ACID транзакции.
D — Durability — это та самая модель, про которую я говорил: если данные уже записали на диск, то мы считаем, что они там лежат, записались надежно и никуда не денутся. На самом деле это не так, например, данные нужно бэкапить, но для нашей модели это не важно.
Как ни печально, обеспечить эти свойства можно только с помощью блокировок. Есть 3 основных подхода к шедулингу транзакций:
Шедулер — это компонент, который обеспечивает сериализацию и правильное выполнение транзакции.
Про упорядочивание TimeStamp все знают: мы смотрим время одной транзакции, время другой транзакции, кто первый встал, того и тапки. На самом деле для большинства серьезных систем этот подход имеет кучу проблем, потому что, для начала, время на сервере может идти назад, может скакать или идти неправильно — и мы приедем.
Есть разные методы усовершенствовать это, но как один-единственный метод синхронизации транзакций, он не работает. Есть еще векторные часы, Лэмпортовы часы — наверняка слышали такие термины — но у них тоже есть свои ограничения.
Оптимистические подходы подразумевают, что у нас не будет конфликтов типа того, что я описал с банковским счетом. Но в реальной жизни они не очень успешно работают, хотя есть реализации, которые помогают проводить какие-то операции с помощью оптимистичных вариантов.
Как люди, работающие с базами данных, мы на самом деле всегда пессимисты. Мы ожидаем, что программисты напишут плохой код, поставщик поставит плохое железо, Марь Иванна выдернет из розетки сервер, когда будет мыть пол — чего только может не быть!
Поэтому мы любим пессимистичный шедулинг транзакций, а именно с помощью блокировок. Это единственный гарантированный способ обеспечить целостность баз данных. Есть соответствующие теоремы, которые можно доказать и продемонстрировать это.
Нужны эффективные алгоритмы взятия и снятия блокировок, потому что, если просто блокировать все, что нам нужно, скорее всего, мы придем к очень тупой версии, когда мы выполняем все операции строго последовательно. Как мы уже знаем, это не эффективно с точки зрения утилизации параллелелизма, современных ЦПУ, количества серверов и т.д.
Семантика Эрбрана
Небольшое лирическое отступление, которое поможет понять, что будет происходить дальше. Жак Эрбран — французский математик первой половины XX века, который, кстати, изобрел рекурсию. Он придумал еще в докомпьютерные времена обозначать транзакции следующим способом:
Здесь S — от слова schedule (расписание). Расписание транзакции включает в себя операцию — r (read — чтение) или w (write — запись). Еще бывает b (begin), с (commit) и т.п.
Что удобно — у нас есть 2 транзакции (цифры 1 и 2). Одна транзакция просто читает данные из какого-то ресурса (x), а вторая транзакция его тоже читает, делает какую-то математику на основе этих двух чтений x и записывает что-то в y.
Очень удобно — транзакции состоят из элементарных действий «чтение — запись, чтение — запись». Мы можем составить итоговое расписание, проверить его, есть ли в нем конфликты, с помощью всякой хитрой математики, и таким образом гарантировать, что все будет хорошо и целостно.
Для чего все это нужно?
Two Phase Locking
Один из основополагающих алгоритмов в современных базах данных — это так называемое двухфазное блокирование или 2PL (Two Phase Locking).
Двухфазное оно, потому что было подмечено, что для оптимизации взятия и снятия блокировок в базе данных удобно сделать это в 2 присеста:
Это позволяет более эффективно шедулить транзакции, чтобы они не ждали.
На рисунке 3 линейки обозначают транзакции и время их исполнения. Видно, что операция записи в первой транзакции ресурса x имеет ненулевое время, поскольку запись занимает какое-то время — пока диск повернется, пока странички туда уйдут и т.д.
Когда она начинается, в этой модели нет никаких других транзакций, поэтому запись началась и пишется. Но вторая транзакция тоже должна прочитать x. Эта транзакция не может взять блокировку на чтение x по той простой причине, что x в этот момент пишется другой транзакцией. Линия становится пунктирной — это означает, что транзакция ждет блокировки, которую выставила транзакция t1.
Как только транзакция t2 взяла все блокировки, которые ей были нужны для того, чтобы она выполнилась — ей еще нужна блокировка на y и блокировка на z — только тогда она может начать их отпускать. В этот момент разблокируется следующая транзакция, которая тоже выполняется до конца.
Эта идея повышает эффективность транзакций и позволяет одни и те же операции выстраивать в параллель только так, чтобы элементарные операции блокировались и ждали, только если они конфликтуют.
Что плохо в двухфазном блокировании?
Почему нельзя так просто решить всю проблему со всеми базами данных с помощью одного простого волшебного алгоритма?
✓ Во-первых, с такими блокировками неизбежно возникают дедлоки, когда непонятно, курица или яйцо.
Одной транзакции нужен ресурс x, другой y, они его блокируют, а дальше им нужны крест-накрест те же самые ресурсы, и непонятно, кто должен первый отпускать блокировку. Для этого в базах данных имеются специальные системы контроля дедлоков и так называемого отстрела дедлоков. Дедлок нельзя разрешить мирным способом, а только откатом одной из транзакций.
Обычно математика внутри детекции дедлоков — это граф дедлоков, где на вершинах обозначены transaction ID, а направленные ребра обозначают, какая ждет блокировки от какой. На этом графе выделяются небольшие подграфы от одной из этих вершин, смотрится, например, если одну транзакцию ждет очень большое количество транзакций, то эту транзакцию прибивают.
Но есть и другие красивые математические подходы, искать которые можно по теме deadlock-detection.
✓ Второй момент, это медленно — никто не хочет ждать блокировки.
Есть такие транзакции, которые занимают ресурс надолго, например, какой-то отчет считает, заняла ресурс, и все остальные вынуждены ждать. Чтобы этого не было, придумали некоторые усовершенствования, о которых расскажу чуть позже.
✓ Зато таким образом обеспечена сериализация.
Без двухфазного блокирования никакой сериализации нет. То есть надо придумывать, как улучшать двухфазное блокирование, чтобы сократить время на ожидание.
На самом деле бывают конфликты, которые 2PL разрулить не может в принципе и тогда одна из конфликтующих транзакций откатывается. Обычно в базах данных реализован механизм, когда база данных ждет некоторое время и понимает, что некоторая транзакция ждет блокировки слишком долго, и что нельзя никак разрешить конфликт, база данных просто убивает такую транзакцию. Это достаточно редкая ситуация и следующий алгоритм позволяет решить некоторые из этих конфликтов.
MVCC — MultiVersion Concurrency Control
Версионирование данных нужно не только для того, чтобы ускорить, но еще и для того, чтобы решить некоторые разновидности конфликтов, которые могут возникнуть.
✓ Интуитивно все понятно — чтобы не ждать блокировку, берем предыдущую версию.
Если какой-то ресурс заблокирован, мы можем посмотреть его старую версию и начать с ней работать. Если, например, блокировка была такая, что та транзакция, которая блокировала, не изменила ничего на этом ресурсе, то мы можем продолжить исполнение транзакции. Если было изменение и появилась новая, более свежая версия данных, наша транзакция будет вынуждена их еще раз перечитать.
В любом случае это обычно быстрее, чем долго ждать блокировку. Если помните старый MS SQL Server и старые версии DB2, страшное дело, то там, если там пошло много блокировок, дальше началась их эскалация — все работало плохо и жить с этим было тяжело.
✓ Все современные DBMS в той или иной степени «версионники»
Oracle, PostgreSQL, MySQL — все «версионники» в честном виде. DB2 немножко оригинальнее на эту тему, там есть свой механизм — хранят только одну предыдущую версию.
Это расписание, которое я рисовал раньше, но несколько более сложное. Здесь больше транзакций (3 штуки), больше ресурсов (есть еще z) и 2 коммита. То есть обе транзакции заканчиваются коммитом.
Как говорят в таких случаях математики: «Легко заметить...» — я это очень люблю, особенно когда на половину доски формула. Действительно, тут легко заметить одну штуку. В качестве домашнего задания попробуйте понять, почему это легко заметить.
Я вам подскажу. Это расписание никогда не сериализуется по той простой причине, что операция r1(y) вызовет конфликт, возможно, даже дедлок, если не будет доступна предыдущая версия y.
То есть, если здесь будет доступна предыдущая версия y, то транзакция нормально завершится, никаких проблем не будет. Если этой версии y не будет, то операции будут конфликтовать.
Как это работает?
Диаграмма более-менее такая же, как с двухфазным блокированием. Это разновидность версионного шедулинга транзакций, то есть это все равно алгоритм двухфазного блокирования, только мультиверсионный.
Добавляется еще такая фишка, как нижний индекс — 0, 1, 2 — это номер версии.
Если попробовать представить, что здесь нет предыдущих версий, то сразу начнутся длинные пунктиры. Когда нужно будет прочитать y, не начнется сплошная линия, а будет пунктир, потому что w2(y) будет ждать, пока она завершится t1. Соответственно, расписание разъедется в ширину и все будет сильно медленнее.
В этом большой плюс MVCC. Мультиверсионность на самом деле быстрее, чем блокировка, это не просто маркетинговая фича.
А что, если в момент транзакции, которая явно имеет ненулевую длительность, произойдет сбой, например, развалится жесткий диск под базой данных или выдернут провода из сервера?
На самом деле мы к этому готовы, потому что транзакции выполняются так. Рассмотрим абстрактную базу данных:
Есть некий объем памяти, который обобществлен между разными процессами или тредами, в которых обрабатываются клиентские подключения. У треда есть свой объем памяти, куда приходит SQL-запрос. В этом объеме памяти SQL запрос (или запрос на другом языке) прекомпилируется, интерпретируется, перестраивается каким-то образом.
Дальше он идет за данными, которые ему нужно прочитать и изменить. Эти данные на диске лежат специальным образом. Если заглянуть глубже в хранение, они лежат фиксированными кусками (страничками) в PostgreSQL это 8Кб, в Oracle можно разного размера использовать. В разных базах данных по-разному.
Эта страничка очень удобна тем, что в ней лежит куча разных данных (фактически в ней лежат tuple (кортежи) То есть есть табличка, а в ней строчки, эти строчки упакованы в большие странички.
Если запросу нужны данные с одной из страничек, он просто поднимает эту страничку себе в память и все воркеры, треды и процессы базы данных будут иметь к ней доступ. Если нужно много, то он поднимет несколько. Они будут закэшированы — это удобно, производительно — память быстрее, чем диски, все дела.
Если нужно поменять хотя бы одну запись хотя бы на одной страничке, вся страничка будет помечена, как так называемая «грязная». Это делается потому, что так удобнее. Мы рисовали на схеме ресурсы x и y — здесь это странички.
На самом деле база данных умеет блокировать и на более гранулярном уровне, в том числе единичную запись. Но сейчас мы рассуждаем о более теоретических вещах, а не о тонкостях глубокой реализации.
Соответственно, страничка помечена как «грязная», и у нас возникает проблема, которая заключается в том, что теперь слепок в памяти отличается от того, который на диске. Если мы сейчас упадем, память не персистентна, мы потеряем информацию о «грязных» страничках.
Поэтому нужно сделать следующую операцию: где-то на бумажке записать, какие изменения мы проделали, чтобы, когда поднимемся, прочитать эту бумажку и, используя информацию из нее, восстановить страничку до того состояния, в которое мы ее привели этим апдейтом.
Поэтому прежде, чем ответ от транзакции вернется снова к клиенту, происходит запись в так называемые Write Ahead Log. Это та самая бумажка, которая позволяет записывать быстро — запись в WAL последовательная, нам не надо искать, куда вставить в огромный data-файл это дело.
Мы записали в лог информацию о страничке и дальше вернули управление — все хорошо. Если в какой-то момент упали, то читаем назад Write Ahead Log и используя информацию об этих изменениях, можем чистые странички докатить до уровня «грязных». База данных у нас снова новая.
Это позволяет произвести то самое восстановление, которое нам нужно было обеспечить, исходя из проблем хранения данных, и позволяет восстановиться на самую последнюю транзакцию, на самое последнее действие, которое произошло перед тем, как Марь Иванна вытащила сервер из розетки.
С тех пор теории особо не добавилось — Write Ahead Log с тех пор остался Write Ahead Log. Они все используют концепцию страничек и концепцию записей изменений в лог. Лог может по-разному называться и в разных местах располагаться:
В принципе, все везде более-менее одинаково — чтобы восстановиться, мы используем WAL.
Важный момент состоит в том, что все это было бы очень непроизводительно, если бы мы просто от начала времен писали WAL. Он бы рос и рос, а мы потом очень бы долго накатывали эти изменения в базу данных.
Checkpoint
Поэтому в последней реинкарнации этого алгоритма имеются идея так называемых Checkpoint — периодически база данных выполняет синхронизацию «грязных» страниц на диск. Когда мы будем восстанавливаться, можно просто дойти только до предыдущего Checkpoint. Все остальное уже синхронизировано, мы, так сказать, замечаем до какого момента мы восстановили.
Это как в компьютерной игре — люди, когда ее проходят, сохраняются периодически. Или как в Word сохраняют периодически свои файлы, чтобы текст не пропал никуда.
База данных это все умеет делать внутри себя. Она так устроена. Помимо всего прочего, это немножко ускоряет процесс, потому что рано или поздно эти странички должны же попасть на диск.
Доступ к данным
Эти самые странички, конечно, хорошие, но нам нужно в каком-то более человеко-читаемом виде эти данные получить. Страничная модель удобна для хранения и транзакционных алгоритмов, но не удобна для доступа. Странички читать неудобно — по битам, поэтому нужен более удобный человеку эффективный метод доступа к данным в страницах.
Есть странички на диске, относящиеся к таблице A и B. Данные на диске ничего не знают, к какой табличке они относятся. Про это знает наш оптимизатор, то есть тот engine в базе данных, который исполняет наш запрос, написанный на нашем языке запросов.
Например, если рассмотреть традиционный SQL, то обычно такая штука будет называться планом запроса. С помощью последовательного sequential scan мы будем брать странички из таблицы A и из таблицы B — иногда синхронно, иногда по очереди — в зависимости от реализации.
Дальше будем накладывать на них, например, JOIN, а с результатом делать что-нибудь еще, и потом вернем ответ клиенту.
Чем это удобно? Представьте себе альтернативу: вы из какого-нибудь Python читаете все это к себе в приложение, а эти таблички могут быть на самом деле огромными, а условие JOIN может исключать 90% этих данных. Вытаскиваете в память — там соответственно ходите по ним циклами, сортируете, возвращаете. На самом деле на каждом из этих этапов планировщик может решить, как сделать выгоднее. Например, он может выбрать метод JOIN, который может или целиком состоять из циклов, или может закэшировать одну таблицу и присоединить к ней другую и т.д. В зависимости от метода, например, можно не делать full sequential scan, то есть не читать всю табличку, а из приложения, скорее всего, вам придется прочитать данные целиком.
Здесь все придумано до вас и реализовано эффективно.
Выводы
SQL и реляционная модель удобны для оптимизации и для человеко-читаемого представления, поэтому без языка запросов никуда. Смерть SQL как технологии предрекают долгие годы, но дедушка живее всех живых. Это во многом потому, что на реляционные модели и с помощью SQL проще всего производить оптимизации и выбирать алгоритмы.
Хранить данные удобней страницами. Есть разные базы данных: объектные, графовые, документо-ориентированные. В основном это все нишевые, неуниверсальные продукты, которые используются для своих целей. Просто поставить на такую базу огромный объем транзакций, чтобы они работали в универсальном виде, не особо получается. Шедулинг транзакций, которые мы рассматривали здесь, на объектах выглядит гораздо сложнее.
Фактически каждая транзакция представляет собой путь по графу. Граф может быть очень большим. Для нахождения конфликтов нужно заниматься очень тяжелой математикой на графах — поэтому в объектной модели возникают проблемы с шедулингом.
Неслучайно столько лет господствует база данных со страничной моделью, и поэтому все происходит так, как происходит. Хорошо ли, плохо ли, но этот метод доказал свою большую эффективность.
Транзакции, вопреки расхожему мнению, это не способ замедлить. Часто считают, что транзакции — это некий синтаксический сахар в базах данных с SQL, который просто все портит и бибикает, в смысле того, что все замедляет, потому что ждем блокировок.
На самом деле транзакции — это способ ускорения, поскольку позволяет параллельно обрабатывать больше данных без конфликтов, чтобы они не бились, чтобы получалось так, что операции выполнялись не строго одна за другой, а параллельно. Это позволяет эффективней расходовать вычислительные ресурсы и время.
Как говорил конструктор Туполев, когда его обвиняли в том, что он какую-нибудь модель самолета у кого-нибудь стянул: «Все самолеты одинаково устроены — чтобы летать, им нужно иметь крылья, фюзеляж и хвост!»
Все базы данных внутри похожи. Они либо устроены одинаково до той или иной степени, либо туда идут. Появился noSQL -без транзакций, без блокировок, без всего, абсолютно не похож ни на какую базу данных. Но мы наблюдаем, что постепенно и там появляются блокировки, схемы, язык запросов, оптимизация и т.д.
В некоторых даже, наверное, скоро появится параллелизм, и это будет большая победа сил разума.
Если посмотреть на современные Percona server, MariaDB, MySQL 8, видно, что они в значительной степени перенимают теоретические основы и сейчас гораздо больше похожи на классические базы данных по своему устройству.
Эта статья родилась не от хорошей жизни. Часто даже не то что начинающие разработчики, но и вполне продвинутые, не знают каких-то базовых вещей — может быть, давно учились в университете и с тех пор забыли, или им не приходилось углубляться в теорию, поскольку и так работалось нормально.
Тем не менее, теоретические знания иногда полезно освежить. Этим мы, в том числе, и займемся.
О спикере: Илья Космодемьянский CEO и консультант в компании Data Egret, специалист по базам данных PostgreSQL, Oracle, DB2. А кроме того, отвечает за продвижение Postgres-технологий, выступает на конференциях и рассказывает людям, как с ними работать.
Ниже материал по докладу Ильи на РИТ++ 2017, который не был связан с какой-то конкретной базой данных, но охватывал многие основные аспекты.
Для чeго это нужно знать?
Хранение и обработка данных — mission-critical задача любой компьютерной системы.
Даже если у вас уже 30 лет есть блог в интернете на текстовых файлах, как у некоторых создателей баз данных бывает, все равно на самом деле этот текстовый файлик — это база данных, только очень простенькая.
Все пытаются изобрести базу данных. Один из докладчиков на конференции сказал: «20 лет назад я написал свою базу данных, только не знал, что это она!» Этот тренд в мире очень развит. Все стараются так делать.
Для работы с данными база данных — это очень удобная штука. Многие базы данных — это очень старые технологии. Они разрабатываются последние полвека, в 70-х годах уже были базы данных, которые работали по схожим принципам, что и сейчас.
Эти базы очень хорошо и продуманно написаны, поэтому теперь мы можем выбрать язык программирования и использовать общий удобный интерфейс обработки данных. Таким образом можно стандартизованно обрабатывать данные, не боясь, что они будут обработаны как-то по-другому.
При этом полезно помнить, что языки программирования меняются: вчера был Python 2, сегодня Python 3, завтра все побежали писать на Go, послезавтра еще на чем-то. У вас может быть кусок кода, который эмулирует работу по манипуляции с данными, которую, по идее, должна делать база данных, а вы не будете знать, что дальше с этим делать.
В большинстве баз данных интерфейс очень консервативный. Если взять PostgreSQL или Oracle, то с некоторым бубном можно работать даже с очень старыми версиями из новых языков программирования — хорошо и здорово.
Но задача на самом деле не самая простая. Если мы начнем закапываться в глубины того, как нам не «побить» данные, как быстро, производительно и, главное так, чтобы потом можно было доверять результату, обрабатывать их, то окажется, что сложное это дело.
Если вы попробуете написать свое простенькое персистентное хранилище, все просто будет только первые 15 минут. Потом начнутся блокировки и прочие вещи, и в какой-то момент вы поймете: «Ой, зачем я все это делаю?»
Об этом и поговорим.
Уровни работы с данными
Итак, есть различные уровни работы с данными:
- Слой доступа к данным, который удобно использовать из языков программирования;
- Слой хранения. Это отдельный слой, потому что обычно хранить данные удобно другими способами, чем использовать: эффективно по памяти, выравнивать, складывать на диск. Это к вопросу о schemaless: схема, которая удобна для хранения, не удобна для доступа.
- «Железо» — слой, где лежат данные, причем там они организованы еще третьим способом, потому что дисками управляет операционная система, и общаются они только через драйвер. В этот уровень мы не будем сильно вникать.
Для слоя доступа к данным есть требования, в выполнении которых мы заинтересованы, чтобы было удобно работать:
- Универсальность, чтобы возможно было с помощью любой технологии запрашивать данные.
- Оптимальность этого запроса. Метод доступа должен быть такой, чтобы хорошо и удобно доставать данные из базы.
- Параллелизм, потому что сейчас все масштабируются, разные серверы одновременно обращаются к базу за одними и теми же данными. Надо сделать так, чтобы максимально использовать преимущества параллелизма и быстрее обрабатывать данные таким способом.
Для слоя хранения по-прежнему важно сохранение изначального параллелизма, чтобы все данные были не побиты, не перезаписаны, не перетерты и т.д.
В то же время они должны быть надежно сохранены и надежно воспроизведены. То есть, если мы что-то записали в базу данных, мы должны быть уверены, что мы это получим обратно.
Если вы работали со старыми базами данных, например, FoxPro, то знаете, что там часто появляются битые данные. В новых базах данных, типа MongoDB, Cassandra и прочих, такие проблемы тоже случаются. Может быть, просто их не всегда замечают, потому что данных уж очень много и заметить сложнее.
Для «железа» на самом деле важна надежность. Это как бы допущение, поскольку мы все-таки будем говорить о теоретических вещах. В нашей модели, если что-то попало на диск, то мы считаем, что там все хорошо. Как заменить вовремя диск в RAID — это сегодня для нас забота админов. Мы не будем глубоко погружаться в этот вопрос, и практически не будем касаться того, насколько эффективно хранилище организовано физически.
Чтобы решать эти проблемы, есть некоторые подходы, которые очень похожи у разных хранилищ данных — и новых, и классических.
Прежде всего для того, чтобы обеспечить универсальный и оптимальный доступ к данным, есть язык запросов. В большинстве случаев это SQL (почему именно он, мы подискутируем дальше), но сейчас просто хочу обратить внимание на тенденцию. Сначала достаточно долгое время был SQL — конечно, были времена и до него, но, тем не менее, SQL господствовал долго. Потом стали появляться всякие Key-value-storage, которые, дескать, работают без SQL и гораздо лучше.
Многие Key-value-storage в основном делались для того, чтобы из любимого языка программирования было проще ходить за данными, а SQL не очень хорошо вяжется с любимым языком программирования. Он высокоуровневый, декларативный, а нам хочется объектов, поэтому появилась идея, что SQL не нужен.
Но большинство этих технологий сейчас на самом деле придумывают какой-то свой язык запросов. В Hibernate очень развит свой собственный язык запросов, кто-то использует Lua. Даже те, кто раньше использовал Lua, делают свои реализации SQL. То есть сейчас тенденция такая: 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 рублей.
Внимание, вопрос: сколько денег окажется в результате на балансе счета a? Скорее всего, вы ответите, что 700.
Проблемы
Здесь начинаются проблемы с конкурентным доступом к данным, потому что язык у меня выдуманный, совершенно не понятно, как он реализован, одновременно ли исполняются эти функции и как они устроены внутри.
Мы, наверное, считаем, что операция send_money() — это не элементарное действие. Надо проверить баланс и куда переводится, выполнить контроль 1 и 2. Это не элементарные операции, которые занимают какое-то время. поэтому нам важен порядок выполнения элементарных операций внутри них.
В последовательности «прочитали значение на балансе», «записали на другой баланс», важен вопрос — когда мы читали этот баланс? Если мы это делаем одновременно, возникнет конфликт. Обе функции выполняются примерно параллельно: прочитали одно и то же значение баланса, перевели деньги, записали каждая свое.
Может возникнуть целое семейство конфликтов, в результате которых на балансе может оказаться 800 рублей, 700 рублей, как должно быть, или что-то побьется, и на балансе окажется null. Такое, к сожалению, бывает, если не относиться к этому с должным вниманием. Как с этим бороться, мы и поговорим.
В теории все просто — мы можем выполнить их одну за другой и все будет хорошо. На практике этих операций может быть очень много и делать их строго последовательно может быть проблематично.
Если помните, несколько лет назад была история, когда у Сбербанка упал Oracle и процессинг карточек остановился. Они тогда просили совета у общественности и примерно обозначили, сколько логов писала база данных писала. Это огромные количества и конкурентные проблемы.
Выполнять операции строго последовательно не очень хорошая идея еще и по той простой причине, что операций много, а мы ничего не выиграем от параллелизма. Можно, конечно, разбивать операции по группам, которые не будут конфликтовать друг с другом. Такие подходы тоже есть, но они не очень классические для современных баз данных.
В немецких правилах дорожного движения есть одна интересная история. Если дорога сужается, то правила предписывают доехать до конца, и только после этого перестраиваться по одному, а соседняя машина должна пропускать. Все перестраиваются строго друг за другом — такой знак об этом говорит.
Это живой пример возможной сериализации, когда общественность очень долго приучали к тому, что правила нужно соблюдать. Думаю, что все, кто ездит на машине по Москве понимают, насколько утопична эта картина.
В принципе, нам нужно то же самое сделать с данными, которые мы пишем на диск.
Как улучшить ситуацию?
● Операции должны быть независимы друг от друга — изолированость.
Чисто теоретически контролируемым образом операция должна знать, что происходит снаружи. Не может быть такого, что как только одна операция что-то изменила, результат сразу стал виден другой. Должны быть какие-то правила.
Это называется изолированностью транзакций. В самом простейшем случае транзакции вообще не знают, что происходит с соседними. Это действия сами в себе, в пределах одной функции никакого взаимодействия наружу нет, пока она не закончилась.
● Операция происходит по принципу «все или ничего» — атомарность.
То есть либо вся операция прошла, и тогда ее результат записался, либо, если что-то пошло не так, мы должны уметь вернуть статус-кво. Такая операция должна быть восстановима, а если она восстановима и изолирована, то она атомарна. Это элементарная операция, которая, как и результат, не делима. Она не может пройти наполовину, а только целиком проходит или целиком не проходит.
● Нужен механизм как проверить что все произошло правильно — консистентность.
Я спрашивал, сколько денег получилось на балансе в нашем примере, и вы почему-то сказали, что 700. Мы все знаем, что есть арифметика, здравый смысл и Уголовный Кодекс, который следит за банками и бухгалтерами, чтобы они не сделали чего-то противозаконного. Уголовный Кодекс — это одна из частных версий консистентности. Если мы говорим, о базах данных, там их гораздо больше: внешние ключи, констрейнты, все дела.
ACID-транзакция
Действия с данными, которые обладают свойствами атомарности, консистентности, изолированности и Durability — это определение ACID транзакции.
D — Durability — это та самая модель, про которую я говорил: если данные уже записали на диск, то мы считаем, что они там лежат, записались надежно и никуда не денутся. На самом деле это не так, например, данные нужно бэкапить, но для нашей модели это не важно.
Как ни печально, обеспечить эти свойства можно только с помощью блокировок. Есть 3 основных подхода к шедулингу транзакций:
- Пессимистические шедулеры;
- Оптимистичные шедулеры;
- Гибридные шедулеры и основанные на упорядочивании TimeStamp происходящей транзакции.
Шедулер — это компонент, который обеспечивает сериализацию и правильное выполнение транзакции.
Про упорядочивание TimeStamp все знают: мы смотрим время одной транзакции, время другой транзакции, кто первый встал, того и тапки. На самом деле для большинства серьезных систем этот подход имеет кучу проблем, потому что, для начала, время на сервере может идти назад, может скакать или идти неправильно — и мы приедем.
Есть разные методы усовершенствовать это, но как один-единственный метод синхронизации транзакций, он не работает. Есть еще векторные часы, Лэмпортовы часы — наверняка слышали такие термины — но у них тоже есть свои ограничения.
Оптимистические подходы подразумевают, что у нас не будет конфликтов типа того, что я описал с банковским счетом. Но в реальной жизни они не очень успешно работают, хотя есть реализации, которые помогают проводить какие-то операции с помощью оптимистичных вариантов.
Как люди, работающие с базами данных, мы на самом деле всегда пессимисты. Мы ожидаем, что программисты напишут плохой код, поставщик поставит плохое железо, Марь Иванна выдернет из розетки сервер, когда будет мыть пол — чего только может не быть!
Поэтому мы любим пессимистичный шедулинг транзакций, а именно с помощью блокировок. Это единственный гарантированный способ обеспечить целостность баз данных. Есть соответствующие теоремы, которые можно доказать и продемонстрировать это.
Нужны эффективные алгоритмы взятия и снятия блокировок, потому что, если просто блокировать все, что нам нужно, скорее всего, мы придем к очень тупой версии, когда мы выполняем все операции строго последовательно. Как мы уже знаем, это не эффективно с точки зрения утилизации параллелелизма, современных ЦПУ, количества серверов и т.д.
Семантика Эрбрана
Небольшое лирическое отступление, которое поможет понять, что будет происходить дальше. Жак Эрбран — французский математик первой половины XX века, который, кстати, изобрел рекурсию. Он придумал еще в докомпьютерные времена обозначать транзакции следующим способом:
Здесь S — от слова schedule (расписание). Расписание транзакции включает в себя операцию — r (read — чтение) или w (write — запись). Еще бывает b (begin), с (commit) и т.п.
Что удобно — у нас есть 2 транзакции (цифры 1 и 2). Одна транзакция просто читает данные из какого-то ресурса (x), а вторая транзакция его тоже читает, делает какую-то математику на основе этих двух чтений x и записывает что-то в y.
Очень удобно — транзакции состоят из элементарных действий «чтение — запись, чтение — запись». Мы можем составить итоговое расписание, проверить его, есть ли в нем конфликты, с помощью всякой хитрой математики, и таким образом гарантировать, что все будет хорошо и целостно.
Для чего все это нужно?
Two Phase Locking
Один из основополагающих алгоритмов в современных базах данных — это так называемое двухфазное блокирование или 2PL (Two Phase Locking).
Двухфазное оно, потому что было подмечено, что для оптимизации взятия и снятия блокировок в базе данных удобно сделать это в 2 присеста:
- Сначала выставляем блокировки на все ресурсы, которые нужно прочитать или записать тому скопу транзакций, которые в данный момент есть в базе данных.
- Ни одна блокировка не снимется, пока не выставлены все необходимые блокировки.
Это позволяет более эффективно шедулить транзакции, чтобы они не ждали.
На рисунке 3 линейки обозначают транзакции и время их исполнения. Видно, что операция записи в первой транзакции ресурса x имеет ненулевое время, поскольку запись занимает какое-то время — пока диск повернется, пока странички туда уйдут и т.д.
Когда она начинается, в этой модели нет никаких других транзакций, поэтому запись началась и пишется. Но вторая транзакция тоже должна прочитать x. Эта транзакция не может взять блокировку на чтение x по той простой причине, что x в этот момент пишется другой транзакцией. Линия становится пунктирной — это означает, что транзакция ждет блокировки, которую выставила транзакция t1.
Как только транзакция 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 в той или иной степени «версионники»
Oracle, PostgreSQL, MySQL — все «версионники» в честном виде. DB2 немножко оригинальнее на эту тему, там есть свой механизм — хранят только одну предыдущую версию.
Это расписание, которое я рисовал раньше, но несколько более сложное. Здесь больше транзакций (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 — здесь это странички.
На самом деле база данных умеет блокировать и на более гранулярном уровне, в том числе единичную запись. Но сейчас мы рассуждаем о более теоретических вещах, а не о тонкостях глубокой реализации.
Соответственно, страничка помечена как «грязная», и у нас возникает проблема, которая заключается в том, что теперь слепок в памяти отличается от того, который на диске. Если мы сейчас упадем, память не персистентна, мы потеряем информацию о «грязных» страничках.
Поэтому нужно сделать следующую операцию: где-то на бумажке записать, какие изменения мы проделали, чтобы, когда поднимемся, прочитать эту бумажку и, используя информацию из нее, восстановить страничку до того состояния, в которое мы ее привели этим апдейтом.
Поэтому прежде, чем ответ от транзакции вернется снова к клиенту, происходит запись в так называемые Write Ahead Log. Это та самая бумажка, которая позволяет записывать быстро — запись в WAL последовательная, нам не надо искать, куда вставить в огромный data-файл это дело.
Мы записали в лог информацию о страничке и дальше вернули управление — все хорошо. Если в какой-то момент упали, то читаем назад Write Ahead Log и используя информацию об этих изменениях, можем чистые странички докатить до уровня «грязных». База данных у нас снова новая.
Это позволяет произвести то самое восстановление, которое нам нужно было обеспечить, исходя из проблем хранения данных, и позволяет восстановиться на самую последнюю транзакцию, на самое последнее действие, которое произошло перед тем, как Марь Иванна вытащила сервер из розетки.
Этот алгоритм называется ARIES и в современном виде сделан достаточно давно. Фундаментальная статья по его устройству и способе восстановления в реляционных базах данных была опубликована Моханом в 1992 году.
С тех пор теории особо не добавилось — Write Ahead Log с тех пор остался Write Ahead Log. Они все используют концепцию страничек и концепцию записей изменений в лог. Лог может по-разному называться и в разных местах располагаться:
- В MySQL он внутри InnoDB,
- В PostgreSQL это отдельная директория, которая наконец в версии 10 стала называться WAL вместо PGX-Log;
- В Oracle это называется Redo Log;
- В DB2 — WAL.
В принципе, все везде более-менее одинаково — чтобы восстановиться, мы используем WAL.
Важный момент состоит в том, что все это было бы очень непроизводительно, если бы мы просто от начала времен писали WAL. Он бы рос и рос, а мы потом очень бы долго накатывали эти изменения в базу данных.
Checkpoint
Поэтому в последней реинкарнации этого алгоритма имеются идея так называемых Checkpoint — периодически база данных выполняет синхронизацию «грязных» страниц на диск. Когда мы будем восстанавливаться, можно просто дойти только до предыдущего Checkpoint. Все остальное уже синхронизировано, мы, так сказать, замечаем до какого момента мы восстановили.
Это как в компьютерной игре — люди, когда ее проходят, сохраняются периодически. Или как в Word сохраняют периодически свои файлы, чтобы текст не пропал никуда.
База данных это все умеет делать внутри себя. Она так устроена. Помимо всего прочего, это немножко ускоряет процесс, потому что рано или поздно эти странички должны же попасть на диск.
Доступ к данным
Эти самые странички, конечно, хорошие, но нам нужно в каком-то более человеко-читаемом виде эти данные получить. Страничная модель удобна для хранения и транзакционных алгоритмов, но не удобна для доступа. Странички читать неудобно — по битам, поэтому нужен более удобный человеку эффективный метод доступа к данным в страницах.
Есть странички на диске, относящиеся к таблице A и B. Данные на диске ничего не знают, к какой табличке они относятся. Про это знает наш оптимизатор, то есть тот engine в базе данных, который исполняет наш запрос, написанный на нашем языке запросов.
Например, если рассмотреть традиционный SQL, то обычно такая штука будет называться планом запроса. С помощью последовательного sequential scan мы будем брать странички из таблицы A и из таблицы B — иногда синхронно, иногда по очереди — в зависимости от реализации.
Дальше будем накладывать на них, например, JOIN, а с результатом делать что-нибудь еще, и потом вернем ответ клиенту.
Чем это удобно? Представьте себе альтернативу: вы из какого-нибудь Python читаете все это к себе в приложение, а эти таблички могут быть на самом деле огромными, а условие JOIN может исключать 90% этих данных. Вытаскиваете в память — там соответственно ходите по ним циклами, сортируете, возвращаете. На самом деле на каждом из этих этапов планировщик может решить, как сделать выгоднее. Например, он может выбрать метод JOIN, который может или целиком состоять из циклов, или может закэшировать одну таблицу и присоединить к ней другую и т.д. В зависимости от метода, например, можно не делать full sequential scan, то есть не читать всю табличку, а из приложения, скорее всего, вам придется прочитать данные целиком.
Здесь все придумано до вас и реализовано эффективно.
Выводы
SQL и реляционная модель удобны для оптимизации и для человеко-читаемого представления, поэтому без языка запросов никуда. Смерть SQL как технологии предрекают долгие годы, но дедушка живее всех живых. Это во многом потому, что на реляционные модели и с помощью SQL проще всего производить оптимизации и выбирать алгоритмы.
Хранить данные удобней страницами. Есть разные базы данных: объектные, графовые, документо-ориентированные. В основном это все нишевые, неуниверсальные продукты, которые используются для своих целей. Просто поставить на такую базу огромный объем транзакций, чтобы они работали в универсальном виде, не особо получается. Шедулинг транзакций, которые мы рассматривали здесь, на объектах выглядит гораздо сложнее.
Фактически каждая транзакция представляет собой путь по графу. Граф может быть очень большим. Для нахождения конфликтов нужно заниматься очень тяжелой математикой на графах — поэтому в объектной модели возникают проблемы с шедулингом.
Неслучайно столько лет господствует база данных со страничной моделью, и поэтому все происходит так, как происходит. Хорошо ли, плохо ли, но этот метод доказал свою большую эффективность.
Без транзакций никак!
Транзакции, вопреки расхожему мнению, это не способ замедлить. Часто считают, что транзакции — это некий синтаксический сахар в базах данных с SQL, который просто все портит и бибикает, в смысле того, что все замедляет, потому что ждем блокировок.
На самом деле транзакции — это способ ускорения, поскольку позволяет параллельно обрабатывать больше данных без конфликтов, чтобы они не бились, чтобы получалось так, что операции выполнялись не строго одна за другой, а параллельно. Это позволяет эффективней расходовать вычислительные ресурсы и время.
Как говорил конструктор Туполев, когда его обвиняли в том, что он какую-нибудь модель самолета у кого-нибудь стянул: «Все самолеты одинаково устроены — чтобы летать, им нужно иметь крылья, фюзеляж и хвост!»
Все базы данных внутри похожи. Они либо устроены одинаково до той или иной степени, либо туда идут. Появился noSQL -без транзакций, без блокировок, без всего, абсолютно не похож ни на какую базу данных. Но мы наблюдаем, что постепенно и там появляются блокировки, схемы, язык запросов, оптимизация и т.д.
В некоторых даже, наверное, скоро появится параллелизм, и это будет большая победа сил разума.
Если посмотреть на современные Percona server, MariaDB, MySQL 8, видно, что они в значительной степени перенимают теоретические основы и сейчас гораздо больше похожи на классические базы данных по своему устройству.
Ну что, убедились, что общие теоретические аспекты нужно знать?
Но не теорией единой… и на РИТ++, который успешно завершился, и на Highload++ Siberia уже через месяц, всегда много-много реального опыта и практических кейсов.
Например, про базы данных и системы хранения есть такие потрясающие заявки:
- Иван Шаров и Константин Полуэктов из ЦФТ расскажут, как работать с Oracle от 7-ми до 18-ти, то есть о длинной истории миграций.
- Владислав Клименко (Altinity) и Валерий Панов (Ivinco) поделятся способами репликации данных из MySQL в ClickHouse в реальном времени для плавной миграции аналитики.
- Алексей Миловидов (Яндекс) обещает поделиться приёмами ускорения разжатия LZ4.