Как создать свою СУБД с нуля и не сойти с ума. Практическое пособие начинающему некроманту. Часть первая

Наступил Апокалипсис.

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

Так родился учебный проект SicQL, реляционная СУБД, чей символ — сова — это олицетворение силы знаний и мудрости. Олицетворение тех знаний и той мудрости, которые мы получим, создав с нуля то, чем мы пользуемся каждый день, может, не осознавая всей сложности таких инструментов.

Приглашаю присоединиться к увлекательному путешествию!

Содержание

• Как создать свою СУБД с нуля и не сойти с ума. Практическое пособие некроманту. Часть первая (данная статья)

  • Предисловие

  • Глава 0. Новое начало истории

  • Глава 1. Архитектура. Noctua ex machina

  • Глава 2. Транзакции, или как остаться без копейки в кармане

  • Глава 3. Деревья. Сбалансированные. Страшно

  • Глава 4. Профессиональный переводчик на совиный — как довериться пользователю и не сломать базу

  • Глава 5. Заверитель транзакций. Виртуальный нотариус собственной персоной

  • Послесловие

  • Полезные ссылки

  • Постскриптум

Предисловие

То, что я не могу создать, я не понимаю.

Ричард Фейнман, 1988 г.

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

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

Глава 0. Новое начало истории

Итак — мы немного отвлеклись — грянул Судный день. Его часы оттикали полночь и снова пошли по кругу. В новом мире постапокалипсиса не существует ни того количества дистрибутивов Линукса, ни новых версий Айфона каждый год — в общем, всего того разнообразия любимых (или не очень) плодов существовавшей ранее цивилизации.

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

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

• Структура статьи составлена таким образом, чтобы даже в мире постапокалипсиса по её тексту можно было воссоздать без особых других знаний эту СУБД. Пусть даже не с помощью языка Rust, а с помощью какого-нибудь новоизобретённого Rusty или C**.

• Процесс создания SicQL продолжается и по сей день — сначала создавалась статья, а затем уже начались работы по воплощению СУБД, притом она, как и сама статья, неоднократно переписывалась в виду особенностей как меня, автора, так и Rust — прототипы за две недельки не напишешь. Так что советую заглянуть через пару месяцев в исходный код и увидеть если не бета-релиз, то хотя бы альфу, которую можно будет полноценно потыкать. И где-то там будет вторая часть статьи с ревизией положений, изложенных ниже, хе-хе.

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

Ну что ж, мы зашли уже слишком далеко, чтобы останавливаться! В путь!

Глава 1. Архитектура. Noctua ex machina

Что-что делаем?

Начнём с определения абстрактного класса BasedTable… Эй, погоди! А что делаем-то?

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

Всякий инженерный проект — это решение конкретной задачи. В частности, поэтому так желанная серебряная пуля невозможна — не существует универсального решения. В конце концов, мы учим железку действовать определённым образом в определённом контексте. Осуществляется ли это условными конструкциями if … else или определённым датасетом, который мы скармливаем нейронке, — не так важно. Важно то, что учителя, в итоге, — это мы. Поэтому от того, насколько мы сможем увидеть решение задачи заранее, и зависит успешность проекта.

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

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

Перепридумываем перепридуманное

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

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

Отлично! Значит, взаимодействовать будем с помощью текста — тем самым нужен какой-то определённый язык… И тут в игру вступают ограничения, заданные изначально, то есть вроде наступивший постапокалипсис. Давайте условимся о том, что переизобретать SQL (к его сущности мы перейдём немного позже) мы не будем. Свою NoSQL базу данных сделаем как-нибудь в следующий раз.

Но так просто мы не отделаемся. Потому что под словами «переизобретение» в абзаце выше могут скрываться две вещи: переизобретение спецификации языка и переизобретение самого языка. Что это за странная игра слов? Смотрим ниже:

Допустим, в гипотетическом языке программирования под фирменным названием Language™ существуют две конструкции:

выражение + выражение?
выражение - выражение? 

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

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

Можно написать хоть сотни стандартов, описывающих синтаксис языка, но кто-то на этом языке должен говорить — собственно сама СУБД. Точнее сказать, вталдычивать программе о нужных нам записях в базе данных будем мы, но только таким образом, чтобы это понимала программа. Следовательно мы, авторы этой программы, должны каким-то магическим образом научить её понимать некоторое подмножество языка SQL. Именно это, я считаю, тоже можно считать за изобретение языка — хоть уже и по имеющимся стандартам, и всему прочему.

Дружим запрос с процессором

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

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

Но долой эту лирику — давайте строить мост между процессором и человеком с двух концов:

За какой конец взяться?

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

Ответ кроется в разборе проблемы выше — чтобы знать, во что стоит перевести запрос, мы должны знать, как процессор работает с данными. Поэтому первый компонент нашей архитектуры должен быть тем, кто будет заботиться о правильном расположении данных в хранилище, то есть первым делом будем браться за бэкэнд нашей СУБД.

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

Далее — вот мы храним данные, но в каком формате? Записать белиберду — просто, а как её считать и преобразить обратно?

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

То есть в данный момент база представляет из себя один текстовый файл с последовательностью записей, предварённых заголовком с метаданными: какие поля есть в записях, какого они типа.

Из-за данного формата данных перед нами встали следующие проблемы:

• Перед тем, как начинать операции с данными на диске, мы должны выгрузить их в оперативную память — иначе скорость работы будет неимоверно низкой. Но, допустим, нам нужна запись под номером 100500 — нам что, придётся загрузить все записи с 1-ой по 100500-ую? А если там хранятся гигабайты данных?

• А как мы будем доставать 100500-ую запись? Как видно выше, каждая новая запись начинается на новой строке, то есть они разделяются символом переноса строки (в зависимости от платформы — CRLF/LF/…). Нам придётся считывать символ за символом, строку за строкой — звучит так же плохо, как и в предыдущим примере.

• Текстовый формат данных — ну слишком жирно! Каждый символ (в том числе и пробелы, и переносы строк, и запятые) занимает 1 байт при кодировке UTF-8 или 2 байта при UTF-16. Звучит не так страшно? Представим 100000 записей всего лишь с одним знаковым целочисленным полем, хранящем максимальное число, которое можно уместить в 32 битах — 2147483647. В UTF-8 это поле занимает 10 байт, а бинарный формат, то есть запись, как есть — 4 байта, 0x7f 0xff 0xff 0xff при шестнадцатеричном формате записи. 6 байтов разницы, плёвое дело? Ну-ну — в итоге вместо ~390 килобайт данная таблица будем занимать весь мегабайт! В два с половиной раза больше!

Как мы можем решить эти проблемы?

• Мысль первая: почему бы не разделить этот файл — но не на отдельные файлы, а на сегменты, чей размер будет известен заранее?
  Размер должен быть определён заранее и желательно не должен меняться. Если размер сегментов будет зависеть от количества строк (например, 100 записей в одном сегменте), то нам так же придётся считывать строку за строкой, пока не насчитываем достаточное количество для перевода страницы. Непорядок…

• Мысль вторая: а если мы отойдём от текстового формата данных и перейдём к бинарному?

Если принять оба этих решения, то мы получим следующий формат файла:

Примечание

Так как теперь у нас нет знаков CRLF/LF, которые бы указывали на начало новой записи, то нам нужно либо располагать записи на странице особым образом, либо перед началом поля данных хранить тип, некоторый байт, чьё значение бы указывало на то, сколько байтов, за ним следующих, считать, и что они значат (строка, номер записи, целое число, число с плавающей запятой...).

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

В СУБД такие сегменты обычно именуются страницами, но могут встречаться и другие названия. Поэтому будем называть их именно страницами.

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

В английской литературе его зовут просто — pager. Пейджер, то есть страничник. Диспетчер, оператор страниц. Звучит во всех случаях глупо, но ради сохранения консистентности текста будем называть его оператором страниц.

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

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

Как вы заметили в примере с упрощённым бинарным представлением файла, в странице под номером Почему 0, а не 1, хотя страница первая? Страницы в нашей СУБД нумеруются по смещению от начала файла. Страница 0 находится в смещении 0 от начала файла, страница 1 смещена от начала на одну страницу и т. д.</p>" data-abbr="0">0 расположены названия таблицы вместе с номером той страницы, на которой таблица начинается; а в самой странице, в конце, указывается номер следующей страницы, на которой следуют данные, которые не поместились в странице предыдущей.

Следите за руками — если одной страницы не хватает для расположения всех данных таблицы, то мы берём любую попавшуюся под руку свободную страницу (пусть она даже не будет последующей!), вписываем указатель в последнюю страницу таблицы, продолжаем записывать данные в новую страницу.

---

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

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

---

«Берём любую попавшуюся под руку» — хе-хе, а руки-то вот они, не уследили! Такие вещи кто-то должен делать — но точно не оператор страниц. У него цель одна — паковать данные в страницы. Что там дальше — это, извините, не его ответственность. Пусть мир перевернётся уже во второй раз — но внутрь страницы не заглянет!

Значит нам нужен ещё один оператор… Если страницы соединить в продиктованном указателями порядке, то мы получим таблицу. Значит это… оператор таблиц! Как всё легко, оказывается!

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

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

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

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

Какие уровни анализа текста мы знаем из школьного курса русского языка?

Лексический анализ: на данном уровне предложение представляет из себя набор лексем, то есть характеристик слова на основе его происхождения, назначения, употребления в речи… Также могут включаться и отношения данного слова с другими в предложении, но для нас это уже перебор. Строка после проведения этого анализа переводится в массив лексем, которые точно присутствуют в языке SQL. Если пользователь ввёл SELECT …, то такая лексема существует, и мы передаём её дальше. Если же, по чистой случайности, в строке находится SLECT …, то ни о каком правильном запросе не может идти и речи, мы всё-таки просматриваем всю строку, и отдаём массив ошибок обратно пользователю. Почему не остановиться на первой ошибке? Да вы только представьте адские муки того, кто допустил множество ошибок в запросе на несколько строк! Переделывать запрос и опять скармливать СУБД… User experience first, как говорится.

Синтаксический анализ: предложение есть взаимосвязанный набор слов, представляющий из себя определённую структуру. Анализ данного уровня должен выявить эту структуру, и найти ошибки, если структура не удовлетворяет языку. Чаще всего эта структура называется абстрактным синтаксическим деревом, о чём мы поговорим в отдельной главе. Мы получаем набор лексем, не заботимся о том, правильные ли это слова (практически, так как всю такую грязную работу совершили на прошлом этапе), и выстраиваем отражающую взаимоотношения слов структуру.

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

Дальше логика начинает расходиться, поэтому продолжим мыслить только в понятиях SQL. Этот язык в своей логике опирается на реляционную алгебру. Операции в этой алгебре представляют собой, если говорить упрощённо, навороченные логические операции. Множества, связи, перемножения, различные проекции… Что если семантически верное синтаксическое дерево (простите!) перевести в операции реляционной алгебры, раз уж в конце концов всё к ней и сводится? Таким образом мы облегчим сложность строения бэкэнда нашей СУБД, обеспечим будущую расширяемость функциональности — реляционная алгебра проще по строению, чем ветвистые и глубокие синтаксические деревья.

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

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

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

Мы оформили фронтэнд и бэкэнд. Компилятор предоставляет в бэкэнд план, записанный в формате реляционной алгебры, а оператор таблиц предоставляет, собственно, таблицы с записями в них, скрывая все страшные подробности хранения данных.

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

То, что мы упустили из анализа ранее, — и есть ключевой компонент СУБД, её сердце. Движок. Он-то и будет по высокоуровневым инструкциям (плану) производить вычисления над записями, которые предоставляет оператор таблиц.

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

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

Такой компонент уже можно называть не просто движком, а целой виртуальной машиной, со своим набором инструкций, регистрами и другими страшными вещами. Итого в строение компилятора (не просто так же он называется компилятором!) мы добавляем генератор кода для виртуальной машины, и этот код будет тем минимальным уровнем инструкций, которые может произвести ввод пользователя.

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

Скрываем реализацию — кто, что и кому должен?

Мы проделали долгий путь по общему анализу «подкапотной» нашей СУБД, с целью сохранения как простоты, так и концептуального содержания, чтобы не отбросить учебные (и немножко покрупнее — у нас всё-таки постапокалипсис за бортом) цели в угоду создания собственных велосипедов!

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

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

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

Глава 2. Транзакции, или как остаться без копейки в кармане

Кислотный ACID

СУБД должна поддерживать несколько подключений к одной и той же базе данных. Несколько процессов, приложений, или несколько потоков в одном процессе должны иметь возможность взаимодействовать с одним файлом базы данных.

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

Нам пришла ещё одна помощь из прошлого мира — это ACID. Странная аббревиатура, с моей точки зрения, так как переводится как «кислотный». Возможно, что она так называется потому, что СУБД должна работать, даже если случится кислотный дождь — что я имею в виду под этой аналогией? Рассмотрим, собственно, сами принципы, скрывающиеся за этими словами, правда, не очень последовательно:

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

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

Вот одно соединение может выполнить один запрос. И точно понятно, что никто иной в этот запрос не должен вмешиваться. Ну, по крайней мере, желательно. Тогда данный запрос можно рассматривать как отдельную транзакцию — но что, если мы несколько расширим границы невмешательства с одного запроса на несколько? Мы предварительно скажем СУБД: «Вот слушай, сейчас я начну транзакцию, и я хочу, чтобы запросы внутри неё представляли нечто единое и неразделимое». Сделаем все наши грязные дела с данными, а потом завершим транзакцию. И нас вообще не беспокоит, что во время выполнения этой транзакции делают другие приложения — дай мне, наконец, уже мои данные, база!

Вот и транзакция — это несколько запросов, которые должны с точки зрения СУБД представлять нечто единое. Это понятие поможет нам в будущем.

A, Atomicity — либо да, либо нет: транзакция или произошла, или была отменена, и все изменения, которые были произведены этой транзакцией, не произошли. Довольно простое понятие с точки зрения пользователя, так как «ну а как что-то может произойти наполовину?», но разработчики СУБД уже не одно поколение ломают головы о том, как это можно поддерживать. Но кто думает о разработчиках?.. Разберутся!

На то транзакция — это набор единых запросов и команд, которые не могут произойти только на половину. Если СУБД сказала, что транзакция исполнена — значит должна быть исполнена! Ну, или отменена, об этом тоже стоит помнить.

Вот, кстати, почему СУБД называется SicQL — от латинского слова sic! — что сказано, то сказано — и сделано! А то, что оно там связано с совами да сычами, — это вы надумали, ничего такого, хе-хе.

C, Consistency — база данных должна остаться согласованной, или хотя бы целостной (и это два разных понятия, разберём чуть ниже), до и после заверения транзакции. Здесь мы вводим понятия «заверения» транзакции, от английского commit (в контексте СУБД получается именно заверение, хотя перевести можно и иначе). Мы просим базу данных заверить выполнение транзакции — и или принять её, или отклонить. Но это разговор про Atomicity, здесь же вводится требование, что база данных не только должна поддерживать атомарность, но и согласованность данных.

Примечание

По слову commit кстати есть интересная история про наименования commit messages в системе контроля версий Git. Идут споры о том, в каком времени писать сообщения – в прошедшем, допустим, Added smth, или в настоящем, Add smth. Традиционным считается второй подход, хотя более логичным звучит первый. Бытует мнение, что вот, создатель Git, Linux и просто хороший человек Линус Торвальдс плохо владел английским, и поэтому сообщения к коммитам писал с ошибкой. Но это не так. Commit есть глагол «заверь», «подтверди», и сообщение должно правильно расшифровываться как «добавь что-то», а не «добавил...».

D, Durability — устойчивость. СУБД заверила транзакцию, но, вот те на, сервер потух. И устойчивая СУБД должна гарантировать то, что заверенная транзакция не будет потеряна даже в том случае, если случится апокалипсис, или, в локальном случае, если операционная система отдаст концы.

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

Первая встреча с монстром конкуренции

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

Процесс A хочет перевести на другой кошелёк 100 рублей. Он считывает данные из записи и получает 100 рублей — отлично, значит можно перевести — организовываем соединение с другим кошельком…

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

Но вот процесс А организовал соединение, произвёл все вычисления и даёт задание СУБД записать баланс в те же 0 рублей. «Ну что, процесс — не дурак, делаем, как сказано», — и что же мы получаем в итоге?

Было 100 рублей. Перевели 200. Получили баланс в 0 рублей. Некрасиво получилось…

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

Что такое согласованные данные — вопрос хороший, так как в рамках СУБД мы определить это не можем. Целостность данных — можем (например, что данные в ячейке не должны равняться NULL), так как понятие целостности полностью лежит в поле управления СУБД. Согласованность данных же определяется приложением, пользующимся СУБД.

Оставлять это так, как сейчас, нельзя — мы переносим заботу о правильном порядке выполнения транзакций на пользователя — а что это тогда за СУБД, которая не может (или не хочет) исполнять контракт по слежению за данными? Я даю СУБД данные, а она заставляет меня ещё и следить, чтобы они случайно не перемешались?

Нужно искать решение. И оно есть — в самом SQL.

Кладём болт на аномалии в реальном времени

Стандартом SQL (SQL92) определяются некоторые из известных аномалий, которые могут происходить в рамках одной транзакции: потерянное обновление (с которым мы столкнулись выше), грязное чтение (получение данных из ещё не заверенной транзакции), неповторяющееся чтение (получение данных из заверенной транзакции), фантомное чтение (получение новых записей из заверенной транзакции). Ещё есть известные, но не описанные стандартом аномалии, и неизвестные, то есть ещё не обнаруженные, аномалии. Но мы усложнять ситуацию ещё крепче не будем, так что примем за правило, что действия СУБД при других аномалиях — это неописанное поведение (unspecified behaviour).

Далее стандарт определяет степени изоляции транзакций, каждая из которых описывает список тех аномалий, которые могут произойти:

• Read uncommited:

  • грязное чтение,

• Read commited:

  • неповторяющееся чтение,

• Repeateble read:

  • фантомное чтение,

• Serializable:

  • полное отсутствие аномалий!

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

А вот Serializable — это отдельная история: СУБД должна заверить приложение, что транзакции, выполненные параллельно, выполнятся и повлияют на данные так же, как если бы они выполнялись последовательно. Про это сразу забываем — это сладкие мечты параллельного вычисления. Но…

Может быть сможем?

Или нет? Вдруг самая сладкая мечта — отсутствие семантических багов и обеспечение согласованности — лежит прямо у нас под носом?

Давайте попробуем придумать такую систему параллельного вычисления, которая позволит исполнить требования Serializable.

Представим два соединения к базе данных, X и Y. База данных состоит из трёх страниц — мастер-страницы и двух страниц таблицы T.

X начинает транзакцию чтения, читает страницу 2. Y начинает транзакцию по записи новых данных в страницу 2, СУБД заверяет эту транзакцию. Для удовлетворения ограничений по изоляции транзакций новое чтение страницы 2 транзакцией в X должно выдать те же данные, что и при первом чтении.

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

Ох, вот это да! Вот это условие… Хотя подождите — ведь мы уже всё нужное описали! Стоит просто накинуть на неизменённые данные и изменённые данные страшные и непонятные названия, как мы получим вполне рабочее решение, которое нужно просто обличить в код.

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

Но мы видим ситуацию с точки зрения транзакции записи. Как же она выглядит с точки зрения другой транзакции?

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

Однако здесь кроется две детали:

• Деталь первая. А что если в журнал после открытия транзакции занесли ещё одну, ту же самую страницу?

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

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

Какая же красота! Как лаконично и понятно — однако стойте, а что же делать с двумя транзакциями записи?

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

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

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

А чтобы посмотреть количество колбасы на складе — да ради бога, смотрите, сколько хотите — хоть один, хоть два, хоть миллион раз одновременно. Можно даже смотреть количество колбасы по тем моментам, как кто-то её купил. А там наверно ещё и хлебушек есть…

А колбасой-то придётся делиться!

Ну что ж — после таких примеров обязательно нужно подкрепиться. Да, простите, не удержался, больше такого не будет. Я вас завер… Всё-всё, закончили!

С первой деталью всё решили. Осталась вторая — как считывать журнал эффективно?

Есть давняя история о том, как хранить данные о данных — индексы.

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

Но этот индекс могут считывать и транзакции чтения — неужто мы сбросим весь наш прогресс и начнём сначала?

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

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

Понятие алгоритмической сложности для тех, кто с ней не знаком, хоть и кроется под ореолом тайного и проклятого знания, но кто запрещает нам не вдаваться в подробности? Алгоритмическая сложность «о-большое» представляет из себя скорость роста времени выполнения алгоритма от увеличения количества элементов, к которому применяется этот самый алгоритм, в худшем случае (для обозначения лучшего случая есть нотация «омега-большое»). — скорость линейна: если количество элементов выросло в тысячу раз, то во столько же раз вырастет время выполнения алгоритма. Если на одном элементе скорость равняется 1 мс, то на двух элементах — 2 мс, на тысяче элементов — 1 с. И та же логика на всех других зависимостях.

Но где и каким образом будет храниться этот индекс?

Нам нужно сообщаться с другими процессами — а как можно обратиться к чужой памяти? Эту вещь контролирует операционная система, и даже если мы попытаемся хоть как-нибудь продвинуться в этом направлении самостоятельно, то наш миленький процесс СУБД повесится, оставив предсмертную записку Segmentation fault (core dumped).

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

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

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

Таким образом, поиск в таком индексе будет организован через простой алгоритм: прыгаем на элемент с индексом, равному маркеру транзакции, считываем влево, пока не найдём либо номер нужной нам страницы, либо начало массива — что значит, что в журнале нужной нам страницы нет.

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

Пылесос? Ещё и автоматический??? Дайте два!

Со всеми этими дополнительными файлами, журналами и индексами жить интересней и приятней, да вот возникает один вопрос — а что с ними делать-то в конце концов? Вот они у нас хранятся, собирают данные. Но СУБД данные не только сохраняет — но и удаляет. А вот о том, как от этих файлов избавиться — точнее сказать, как эти файлы очистить — мы не очень подумали.

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

Сначала узнаем, как удаляются записи: для того, чтобы особо не нагружать ввод-вывод, мы просто будем указывать в начале записи, жива она или нет. Но и здесь встаёт та же проблема — пометили запись как удалённую, а кто за нами чистить будет?

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

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

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

Ну что ж, наконец перейдём к самому интересному — тому, как эти страницы организованы между собой, как устроены записи, — к оператору таблиц!

Глава 3. Деревья. Сбалансированные. Страшно

Слово дерево и слово смерть для вас означает одно и то же!

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

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

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

В чём заключается сущность индекса? Мы в неструктурированную информацию вносим дополнительный смысл, который позволяет уменьшить время поиска по индексированному ключу.

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

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

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

Хрестоматийный пример — бинарные деревья поиска. Допустим, мы имеем массив чисел [1, 2, 3, 4, 5, 6, 7]. Если для поиска мы будем перебирать каждый элемент массива, то наш алгоритм поиска номера элемента в массиве будет иметь сложность.Но что если мы организуем индекс с помощью бинарного дерева поиска?

Допустим, нам нужно узнать местоположение числа 5 в массиве. Число 5 больше или меньше, чем число 4? Больше, значит идём по правой ветви. Число больше или меньше 6? Меньше, значит идём по левой ветви. Число равно 5? Равно — и его индекс в массиве равняется 4 (удивительно!).

Поиск, организованный с помощью бинарного дерева оказался быстрее — но постоянна ли его алгоритмическая сложность? Вдруг кто-то поиграется с нашей структурой, и вместо нормального дерева мы получим следующее:

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

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

Дубы, ели, доколе?!

Заглянув в Википедию, вы увидите только много-много терминов, которые вроде бы описывают свойства и алгоритмы cбалансированных деревьев. Ох, совсем забыл, постапокалипсис… Так что надеваем противогазы и вперёд на поверхность, бороться со сложностью!

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

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

Сущностьдеревьев в нашем случае заключается в следующих вещах:

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

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

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

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

Что ж…

Какой-то ужас. Пиктограммы лучше текста, говорите? Ну тогда смотрим визуализацию свойств:

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

Переворачивать не придётся. Придётся дробить

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

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

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

Но вот ещё один пограничный случай — а что если делегировать ключи и указатель некому, так как мы находимся в корне дерева, который является в том числе ещё и внутренним узлом?

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

Кстати об алгоритмической сложности — какова она в нашем случае? Так как для того, чтобы выйти на нужную запись, мы должны совершить следующее:

1. Зайти в корень, сравнить искомый ключ с первым хранящемся: если он меньше или равен ему, то идём по указателю с таким же номером, что и у ключа; если он больше, то смотрим: остались ли ещё ключи в узле? Если да, то проверяем со следующим ключом. Если нет, то идём по последнему указателю.

2. Зайти во внутренний узел, проделываем ту же самую операцию со сравнениями.

3. Как зашли в лист, начинаем прогонять искомый ключ со всеми ключами в узле.

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

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

Как в итоге сделать просто

В итоге оператор таблиц предоставляет следующие возможности для СУБД: создать таблицу, удалить таблицу, найти значение по ключу, вставить пару ключ-значение, пометить пару к удалению (настоящее удаление пары и поддержку VACUUM мы реализуем в следующий раз), выдать все записи таблицы в порядке возрастания.

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

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

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

Глава 4. Профессиональный переводчик на совиный — как довериться пользователю и не сломать базу

Словодробилка

На вход мы получаем строку и только. Значит мы должны пройтись по всей строке, символ за символом, и на выходе отдать массив лексем, или токенов.

У нас есть определённые зарезервированные слова, по типу SELECT или UPDATE, или зарезервированные символы (например, оператор неравенства !=), которые нельзя будет использовать в качестве идентификаторов, то есть названий колонок и таблиц. Поэтому, если мы встретим такие слова, то сможем без раздумий скушать их и превратить в токены ключевых слов.

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

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

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

Посылаем слова на три буквы

Какие три буквы, спросите вы? Как в том анекдоте — НБ… Ой, не то — БНФ! Форма Бэкуса — Наура. Мы уже встречались с ней в самом начале статьи, когда обсуждали гипотетический язык Language™:

вычисление
	::= выражения '?'
	  ;

выражения
	::= выражение
	  | '(' выражения ')' операция '(' выражения ')'
	  ;

выражение
	::= цифра операция цифра
	  ;

цифра
	::= '1' | '2' | '3'
	  | '4' | '5' | '6'
	  | '7' | '8' | '9'
	  | '0'
	  ;

операция 
	::= '+'
	  | '-'
	  ;

Только что-то схема заметно выросла. Мы записали синтаксис языка с помощью БНФ, и весь смысл этой схемы заключается в том, что существует определённое количество нетерминалов и терминалов. Терминалы — это то, что записано в кавычках — они сводятся к определённым символам. Нетерминалы — это, в общем, всё остальное: комбинации терминалов и нетерминалов (последовательность или выбор с помощью оператора |).

Такой формат описания синтаксиса языка является очень мощным инструментом — с его помощью автоматические генераторы парсеров даже способны выдать рабочий… парсер?

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

---

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

---

Начнём с самого верха: что представляет собой запрос? Это либо транзакция чтения/записи, с несколькими выражениями внутри, либо одно выражение. Так и пишем!

query  
    ::= 'BEGIN WRITE TRANSACTION;' 
        (statement ';')+ 
        'COMMIT' ';'?  
      | 'BEGIN READ TRANSACTION;' 
        (select ';')+ 
        'COMMIT' ';'?  
      | statement ';'  
      ;

Тут появились некоторые новые символы — и они являются ни терминалами, ни нетерминалами (что?). Элементы можно группировать в группы с помощью скобок, а затем указывать, что элемент может не появиться или появиться только один раз (символ ?), появиться один раз и больше (символ +), не появиться или появиться несколько раз (символ *). Такой формат записи не был задуман изначально в БНФ, но зато появился в расширенной версии БНФ (extended BNF, EBNF) — но она не позволяет выдумать что-то иное — просто запись выглядит почище.

Дальше нам нужно определить из чего может состоять само выражение:

statement  
    ::= select  
      | create  
      | drop  
      | insert  
      | update  
      | delete  
      ;

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

create  
    ::= 'CREATE' 'TABLE' table_existence? 
        '(' column_definition (',' column_definition)* ')'  
      ;

Вот уже что-то поинтереснее. Идут терминалыCREATEиTABLE— это понятно. Затем нетерминалtable_existence, который хранит в себе терминалыIF NOT EXISTSи которого вообще может в запросе не быть. Затем скобки — здесь будут указываться декларации колонок: название колонки и её тип.

column_definition  
    ::= column_name type 
      ;

column_name  
    ::= identifier  
      ;

type  
    ::= 'VARCHAR' '(' integer ')'  
      | 'FLOAT'  
      | 'INTEGER'  
      | 'BOOLEAN'  
      ;

identifier  
    ::= word  
      ;

А что это за нетерминалыintegerиword? Целое число и слово — но мы их определять в БНФ не будем; и так понятно.

Понятен теперь и возможный синтаксис нашего подмножества SQL. Но как же мы будем создавать из массива токенов ветвистое абстрактное синтаксическое дерево?

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

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

По такому же принципу действуют парсеры column_name и type. Пробуем всевозможные состояния, пока не получим... короткое замыкание!

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

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

Примечание

Парсер языка Language™, кстати, мог использовать в том числе и обратную польскую нотацию, Reverse Polish Notation (RPL), когда выражение (5 + 6) - 2 будет преобразовано не в абстрактное синтаксическое дерево, а в такое состояние: 56+2-. Довольно красиво, не так ли? Знак операции стоит после всех операндов, что позволяет избавиться от структуры дерева с предками и детьми. Но такой трюк можно провернуть только в тех языках, в которых количество операндов строго ограничено (хоть и не всегда), чего не скажешь о нашем выразительном SQL.

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

А в чём смысл?

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

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

Алгебра пригодилась! Правда не та…

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

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

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

Разберём несколько основных операций реляционной алгебры:

• Выборка отношения по определённому условию: такая операция выберет все кортежи, которые удовлетворяют условию.

• Проекция отношения на его атрибуты: название говорит само за себя — мы просто возьмём из кортежей данные только по определённым колонкам, атрибутам.

• Декартово произведение отношений: мы получим всевозможные сочетания кортежей в двух отношениях — декартово произведение отношений Буквы( (А), (Б) ) и Цифры( (0), (1) ) выдаст отношение из кортежей (А, 0), (А, 1), (Б, 0), (Б, 1).

• Объединение отношений с одинаковыми атрибутами: мы «приплюсуем» к кортежам первого отношения все те кортежи второго отношения, которых нет в первом.

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

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

Ну, это замечательно — но как преобразовать имеющееся абстрактное синтаксическое дерево в операции над отношениями?

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

SELECT * FROM bP — это проекция.

SELECT name FROM basedProgrammers WHERE age > 30 — 30}(bP))" alt="pi_{name}(sigma_{age > 30}(bP))" src="https://www.pvsm.ru/images/2023/01/06/kak-sozdat-svoyu-subd-s-nulya-i-ne-soiti-s-uma-prakticheskoe-posobie-nachinayushemu-nekromantu-chast-pervaya-55.svg" width="157" height="23" title="Как создать свою СУБД с нуля и не сойти с ума. Практическое пособие начинающему некроманту. Часть первая - 55"/>.

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

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

Котогенератор

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

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

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

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

Выразить условия выборки нам помогут циклы. Кто имел опыт с ассемблером, тот знает про инструкции «прыжков» — допустим, в человекочитаемом формате смысл такой: ПЕРЕЙТИ НА ИНСТРУКЦИЮ 5 ЕСЛИ 2 > 1. И если инструкции с первой по пятую не имеют других прыжков, то мы получим бесконечный цикл.

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

Операндами могут являться как какие-то конкретные значения, либо значения определённой колонки из открытого курсора.

Простые инструкции, но в итоге с помощью них мы можем выразить, например, декартово произведение:

ТРАНЗАКЦИЯ ЧТЕНИЯ
ОТКРЫТЬ КУРСОР 'БУКВЫ' ; Курсор 0 на таблице с буквами русского алфавита
ОТКРЫТЬ КУРСОР 'ЦИФРЫ' ; Курсор 1 на таблице со всеми цифрами
КОЛОНКА 0 1 ; Берём из курсора 0 колонку с буквой алфавита, записываем
КОЛОНКА 1 1 ; Уже колонка из курсора 1 с цифрой
ЗАПИСЬ В РЕЗУЛЬТАТ ; Складываем получившуюся запись в массив 
ВПЕРЁД 1 3  ; Если запись, следующая за курсором 1, существует, 
            ; то прыгаем на инструкцию с индексом 3 (считаем с 0)
            ; и двигаем курсор на одну запись,
            ; иначе выполняем инструкции дальше
СБРОС 1 ; Делаем так, чтобы курсор 1 снова указывал на первую запись в таблице
ВПЕРЁД 0 3
ВЫВОД   ; Останавливаем выполнение и отдаём массив с записями, которые мы получили
ЗАВЕРЬ  ; Заверяем транзакцию
СТОП    ; Останавливаем виртуальную машину

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

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

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

Глава 5. Заверитель транзакций. Виртуальный нотариус собственной персоной

Вошли и вышли, виртуальная машина за 20 минут

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

А мне вообще нужно указывать источник?

Вроде слово страшное, но на самом деле ничего страшного в виртуальных машинах нет — поэтому не сопротивляйтесь разберёмся с тем, из чего они состоят:

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

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

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

Вот и вся сложность — и всё благодаря тому, что мы чётко распределили обязанности по всем компонентам системы. Разделили сложность — и как вдруг она исчезла.

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

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

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

Восстанавливаемся от ошибок — почти как взрослые

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

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

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

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

После восстановления от ошибки мы «выключаем» виртуальную машину, выдаём пользователю сообщение о внутренней ошибке. Try again later, хе-хе.

Послесловие

Что дальше?

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

• Поддержки foreign keys, «синтаксического сахара» над JOIN’ами и ограничителями,

• Императивного подмножества SQL со своими функциями,

• Большего множества типов хранящихся значений, например, BLOB, TEXT, JSON, DATE…

• Индексов на основе B-деревьев, способных индексировать значения по нескольким полям, необходимых для обеспечения требований целостности данных,

• Поддержки операции VACUUM на уровне оператора таблиц,

• Сложной системы оптимизаций запросов,

• Сервера, способного отправлять запросы «по проводу»,

• Возможности выбора необходимой пользователю степени изоляции,

• Вложенных запросов.

И прочее, и прочее. В одну статью всё вышеперечисленное уж точно не поместится — так что либо задача остаётся на вас, либо… Ждите продолжения — с блэкджеком и живыми совами!

А зачем всё это?

Всё это, конечно, детский сад — реальные СУБД, настоящие production-ready инженерные решения, в которые вложены сотни человеко-лет, устроены сложнее, страшнее и далее по списку.

Но кто запрещает нам экспериментировать, создавать свои любительские проекты? Ведь и Linux, и Postgres, и Rust, как и многие другие важные вещи (не только в сфере IT), изначально создавались как простые, ни на что не рассчитывающие, студенческие поделки…

Как говорится — это редиска, но это наша редиска!

Поэтому творите, друзья, — вдруг именно ваше решение проложит путь в светлое будущее. И без всяких постапокалипсисов. Хотя почему вдруг — я в этом уверен.

Спасибо за составление компании на этом пути — не переключайтесь, впереди ещё вторая часть!

Полезные ссылки

• Исходный код SicQL

• Архитектура SQLite и документация к ней

• К. Дейт, Введение в системы баз данных

• Р. Нистрем, Crafting Interpreters

• Библия Компиляторы: принципы, технологии и инструменты

• К. Дейт, SQL и реляционная теория

• Системы базы данных: полное собрание

Постскриптум

Хочется выразить отдельные благодарности:

• Мише, автору канала МиКаст в Telegram, за его полезные советы на до сих пор продолжающемся пути становления программистом,

• коллективу историко-философского журнала «Русская Пустошь» за помощь во вычитке статьи.

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