Comments 62
Есть такая СУБД, называется Oracle Database. Славится тем, что не следует (не следовала) стандартам. Например, пустая строка и NULL в понимании этой СУБД - это одно и то же.
Так вот, ее основное достоинство (имхо) - это версионность записей в БД. Рассмотрим пример: транзакция Т1 меняет запись, и дальше что-то делает. Транзакция Т2 пытается читать измененную запись. По стандарту SQL92 вторая транзакция должна встать в ожидание (на всех уровнях изоляции выше read uncommitted). Но с Oracle ситуация другая: на этой СУБД вы получите прошлую версию записи сразу, без блокировки.
Получается, что целостность (consistency) приобретает другой смысл. Оказывается важно, чтобы все чтения транзакции Т2 были сделаны из одного и того же среза (snapshot) данных. И этот срез фиксируется началом транзакции.
Собственно, на заре нулевых, когда NoSQL еще не было, а споры что лучше MSSQL или Oracle были, основным достоинством последней было именно наличие другой модели блокировок и работы с данными.
Вы здесь упоминаете SQL92, но Oracle как мне кажется, добивался большей параллельности (и следовательно большей производительности) не за счет выполнения стандарта, а за счет решения задач более высокого уровня. У MSSQL было лучше с реализацией, но у Oracle было лучше с концепцией.
Если вы реально интересуетесь темой, то я бы порекомендовал прочитать книгу Oracle Core (автор - Jonathan Lewis). Из книги вы узнаете, например, почему у блоков, хранящих данные таблицы, всего 1 слот для блокировок, а у блоков с данными индексов 2.
Благодарю за ответ!
Про строки и NULL — очень интересное наблюдение, обязательно надо ознакомиться с обоснованием для такого решения.
А про версионность записей — я с вами согласен, что СУБД, которые реализуют изоляцию транзакций на основе блокировок отдельных записей, добиваются большей параллельности.
На самом деле, первый прототип, который больше не увидит свет, SicQL пытался в блокировки строк — по крайней мере, в начале пути этого хотелось. Но, столкнувшись с неведомой сложностью сего дела, я быстро идею отбросил. Достаточно наивным было считать, что получится за два месяца теоретически охватить PostgreSQL/..., а затем воплотить в жизнь хоть малейший его клон. После такого провала, хе-хе, взгляд был обращён на SQLite, чья заслуга заключается в том, что изоляция транзакций и многоверсионность относительно других проектов реализованы относительно просто, да так, что для работы с базой данных достаточно одного процесса, который можно запускать непосредственно из приложения.
Но, в итоге, всё получилось как в этой цитате: «Всё не так просто, как кажется на первый взгляд, но и не так легко, как кажется на второй».
Рекомендую читателям ознакомиться ещё с тем, как изоляции транзакций поддерживаются в PostgreSQL.
Я надеюсь, что во второй части статьи получится затронуть теоретическую основу блокировок не просто страниц, а записей в ней.
SQLite является файловой СУБД. К файлу БД можно обращаться по сети. Если ваша цель реализация СУБД на основе файлов, то не забудьте обеспечить возможность такого обращения, желательно с хоть каким-то уровнем блокировок, то есть чтобы не блокировалась вся БД при обращении кого-то одного.
Полная блокировка (предоставление процессу соединения с БД блокировки записи основного файла посредством системного вызова) осуществляется только в момент очистки упреждающего журнала, то есть, когда нам такое поведение и нужно.
В момент чтения из файла БД и чтения/записи упреждающего журнала процессам СУБД предоставляется блокировка чтения/записи только определённой части файла, и зачастую эта часть файла равняется размеру страницы.
А я слышал, что в PostgreSQL тоже версионность записей до такой степени, что удалений в процессе обычной работы нет, есть только вставки и обновления (удаления — обновление отметки "удалено", физическое удаление делается вакуумом). Собственно, до прочтения тегов статьи с какого-то момента начало казаться, что автор вместо твердой научной фантастики теории начал пересказывать исходный код PostgreSQL (в этот же момент количество смехуечек, как тут уже заметили, превысило комфортный предел). И тоже слышал, что чтения в PostgreSQL всегда идут без блокировок, а это возможно только если читать (условно) устаревшие данные, которые в этот момент могут изменяться другой (пишущей) транзакцией. То есть получается, что подход Oracle не уникален (хотя тоже когда-то давно читал, что такая его стратегия чтения уникальна… но это было тогда, когда PostgreSQL на слуху не было)
И Вакуум запускается для диска. Потому как на диске используется страничная организация памяти.
А вот для RAM — там можно безнаказанно выделять и удалять память. Иначе можно вставить гигабайт данных, а потом удалить. И что этот гигабайт будет висеть мёртвым грузом в RAM?
Но я не знаю как точно работает postgres. Я написал как это должно работать по логике.
Я не настоящий сварщик, но меня все-таки смущает эта ваша концепция двух БД. Из практики, она обычно применяется в специализированных решениях, типа сервиса кэширования. А классические БД, такие как постгрес, заведомо ориентируются на объемы, превышающие возможный размер памяти. И требуют, чтобы в память влезали только индексы. В частности, в блокировках и транзакциях может участвовать не вся запись, а только её представитель — первичный индекс. А сколько там гигабайт — дело уже десятое.
Прочитав ваш комментарий я прекрасно удивил одну из проблем которую мы решали в процессе проектирования. И у меня возник вопрос.
Собственно как работает доступ к таблицам. Разные потоки делают запросы на read — при этом таблица лочится — но все могут получить доступ на чтение. Если в очереди запросов подходит запрос write — то ожидается пока все read не закончатся, потом лочится на write — и далее с таблицей работает 1 поток.
Все INSERT/UPDATE/DELETE — это write запросы и делаются внутри транзакции. И представим ситуацию — мы сделали UPDATE на гигабайт данных, или DELETE — а далее делаем SELECT в тойже транзакции — и мы должны получить уже изменённые данные. Самое простое — это когда мы залочили таблицу и делаем изменения прямо в ней. И Select тоже в ней. Если придётся откатывать транзакцию — то это тяжёлая операция. В нашем случае — идёт восстановление таблицы из журнала WAL. Также при откате Текущий WAL транзакции не записывается на диск.
Вы же описали ситуацию когда изменения INSERT/UPDATE/DELETE не делаются в существующие таблицы, а делаются кудато в другое место. Ну допустим в массив какой-то. Соответственно в это время с таблицей могут работать другие в режиме read.
Но как тогда делать SELECT? Путь это простая таблица без индексов. Это будет набор массивов в котором просто циклом перебираем строки. Но в вашем случае надо как то знать какие строки изменённые.
Конечно можно придумать геморройный механизм этого. Но это будет намного медленнее и жрать память. Простой перебор одномерного массива намного быстрее, чем перебор с проверкой — а не изменилась ли строка? А ещё надо учитывать DELETЕ — который может вообще пол таблицы в разных местах выкинуть.
Вобщем вопрос — а нужно ли такое поведение? Я вижу как минимум например засаду в следующем сценарии. Сделали платёж — запустился скрипт изменения баланса в БД — но подавис по времени. Если сделать сразу новый платёж — то мы получим неправильный баланс денег.
Ответ на ваш вопрос в последнем абзаце (отсылка к книге как устроен Oracle внутри).
У вас сейчас табличные блокировки. Любой изменяющий должен выставить блокировку на таблицу, и от момента блокирования таблицы до момента коммита транзакции таблица недоступна (для других). В стандарте SQL92 вопрос проработан дальше - блокировка ставится на запись, а не на таблицу, но ожидания все равно остаются.
В Oracle ключевым понятием является SCN. Это единый, сквозной номер изменения в БД. Любое изменяющее действие увеличивает этот номер (чтение может не увеличивать). Но каждая транзакция помнит "свой" стартовый SCN, от которого она должна отсчитывать все изменения.
То есть чтобы прочитать данные нужно не только знать что читать, но и то, на какой момент это читать.
Соответственно, изменения в любую запись БД вносятся с учетом этого SCN. Более подробно - вам лучше все же книгу почитать. Поверьте, это пока что поверхностный уровень. Внутри куда все сложнее, особенно с блокированием при изменении индексов.
Выигрыш записывать изменения в конце транзакции только в том что это время будет меньше чем время всей транзакции.
В нашей БД такой механизм применить легко даже не сильно меняя код. А именно. При каждом INSERT/UPDATE/DELETE — идёт запись в WAL. Так вот просто комментировать строку изменения таблицы, при этом изменения WAL останется. А в конце транзакции применить WAL к таблицам. Точно также как WAL применяется при старте БД. Также решается мега геморрой отката транзакции — его просто не будет, потому как таблицы RAM не изменились.
Но тогда внутри транзакции SELECT будет работать на устаревших данных.
И ещё непонятно. При старте транзакции указывается список таблиц которые должны быть неизменны на момент старта транзакции, транзакция же атомарна, что бы вся логика внутри транзакции отработала правильно. Но в случае если не блокировать таблицы — и изменения в них могут вносить другие транзакции, может получится каша.
Например делаем внутри транзакции SELECT сколько денег у клиента. Возвращается что 100$. Далее идём делать какую то логику. А в этот момент в другой транзакции снимаем эти 100$. Но при этом мы находимся в первой транзакции и она работает по логике что у клиента есть 100$.
Короче есть на чем подумать. Если внутри транзакции ненужны селект — то можно не блокировать таблицы на время транзакции. В сценариях описанных выше — такой подход неприемлем.
При дизайне СУБД с использованием SCN, каждое изменение имеет ссылку на прошлую версию той же записи. Таким образом, если вторая транзакция читает обновленные данные, но знает что ей нужны более старые (см. выше про необходимость знания транзакцией своего стартового SCN), то она по ссылкам в записи проходит дальше в историю, чтобы получить данные на тот момент, когда ей необходимо. Вопрос сколько истории хранить - регулируется размером UNDO TABLESPACE в Oracle. Возможны ошибки, что "транзакция слишком длинная, истории не хватило" - тогда есть 2 выхода: либо увеличить объем UNDO (область админа), либо изменить логику приложения (область разработчика).
СУБД общего назначения не может расчитывать ни на то, что вся таблица поместится в RAM, ни на то, что все изменения одной транзакции поместятся в RAM. Это слишком опрометчиво с точки зрения дизайна, и на практике рано или поздно случится так, что это ограничение будет нарушено.
Помимо механизмов изоляции транзакций, СУБД еще должна заботиться о резервном копировании (и репликации на другие инстансы, если смотреть еще дальше). Здесь тоже встают вопросы как минимизировать объем данных в резервной копии (или объем передаваемых данных на реплику).
Мораль здесь такая: для разработки своей СУБД лучше изучить существующие решения и выбрать работающие решения (отказавшись от ненужных фич), а не пытаться решить проблемы по мере их поступления. Последний путь - дороже в общем случае.
С другой стороны имеем тот же массив массивов + новые изменённые данные. Где их хранить? Ну допустим имеем новый массив. В котором например структуры (номер строки, новое значение). Тогда вместо простого for, мы должны на каждом цикле делать запрос к новому массиву, перебирать его и искать изменённую строку. Получаем дикий оверхед. Как избавится от этого оверхеда? Так на вскидку ничего нормального в голову не приходит. А если изменений на гигабайт — то вообще получим неработоспособную систему — такой SELECT просто зависнет навечно.
И тут получаем мой вопрос — а ради чего это нужно?
Пока напрашивается простой вариант — сделать 2 вида транзакций:
Fast — это в которых нету внутренних select, либо нас устраивают устаревшие данные. В таких транзакциях блокировать таблицу в конце транзакции.
И второй вариант — с полной блокировкой таблицы.
Что касается собственной разработки БД.
По поводу преимуществ собственной разработки уже были да и будут миллион дискуссий, более того всё существующее ПО это когда то собственная разработка. Но я согласен — без явной причины, на такой подвиг я бы не согласился ни за что. Нас вполне устраивал Postgres. Тут мне в личку писали, я там подробно ответил причину почему всё таки своя БД. Приведу ответ тут:
По поводу БД. Решение написать свой велосипед был непростым, но ему предшествовала 1 причина. Изначально БД была MSSQL, давно правда, потом перешли на Postgres. И он собственно устраивал на 100%. Но как то в 1 момент на 1 из проектов вылез непонятный косяк. Postgres периодически рандомно подвисал на транзакциях. Проблему искали 3 месяца. Что только не делали. Обложили всё что можно логами. Postgres заставили выводить все логи которые он может. Но блин из логов было только что мол этот запрос выполняется 40 секунд. Почему — хрен знает. Даже написали свой провайдер (до этого был Npgsql), думали проблема с коннектами.
А причина потом оказалась до банального проста. Кабель соединяющий один из RAID дисков — подгнил и периодически глючил. И postgres — просто периодически висел в ожидании записи на диск данных в WAL. И НИГДЕ ПРО ЭТО НЕ писал.
Собственно боязнь очередной нерешаемой подставы — привёл к решению собственной БД. Где можно посмотреть ВСЁ.
БД сейчас в стадии разработке. Используется C# и .net core. Для нас такое решение идеально потому как позволяет применить 1 интересную вещь. БД используется для web платформы, которая тоже написана на C# и .net core. БД — встраиваемая (вариант автономной работы тоже закладывается). И в режиме встраивания можно объединить обработку запроса в web сервере и БД в 1 поток с одним адресным пространством. Написал сумбурно — но смысл прост, уберется прослойка в виде TCP соединения с базой данных, и достигается максимальное быстродействие. И главное работа с БД у нас построена на процедурах. Писать процедуры на языке SQL — тот ещё геморрой, но мы привыкли уже. В нашей же БД процедуры пишутся на C#. NET вообще замечательная платформа. Лучшая по отладке. Например типичный кейс — приконектится из windows к серверу linux на другой стороне шарика к рабочему процессу в режиме отладки и у себя в студии просто по шагам отлаживать в исходном коде, с просмотром переменных и прочего. Иногда только так можно найти баг, который у тебя в локальной среде не воспроизводится.
Сейчас БД находится в стадии разработки. Например изначально был только управляемый код, что бы отладить основные механизмы. Сейчас переписываться под неуправляемый — что бы получить скорость. Разработки ещё на год…
Параллельно пишется менеджер для работы с БД. По типу SQL Manager for PostgreSQL. Тоже непростая вещь.
В дальнейшем планируется выложить БД в opensource. Но пока рано.
Хм, кажется, вместо написания своей БД на пару лет можно было бы просто добавить патч в PostgreSQL, чтобы он писал метрику времени ожидания записи WAL? Или хотя бы поднять такой вопрос в баг-трекере. Кажется, это точно было бы реализовано быстрее
Вся таблица в виде массива в RAM когда-нибудь порвёт RAM, но да ладно. Чтоб не делать вложенные проходы, можно докинуть изменяемое служебное поле для каждой ридонли-записи в основном массиве. В этом поле хранить индекс изменённой версии записи во втором массиве. При проходе проверка: нет индекса - не было изменений, есть - берём данные по индексу.
То что вы описали — это то что описал и я. В цикле для каждого столбца каждой строки придётся вызывать функцию которая будут проверять изменялось ли значение. Проверка это будет в общем случае как перебор другого массива в котором будут например структуры (номер строки, номер столбца, новое значение). И избавится от этого дикого оверхеда не получится.
Ещё раз попробую. Будет не перебор второго массива, а прямой доступ к элементу этого массива, сложность O(1). Например, основная таблица Persons (ID, Name, Age) представлена как массив arrPersons[rowIdx][colIdx], но с дополнительным 4-м полем ChangeIdx:
100, "Иванов", 23, null
200, "Петров", 54, 0
300, "Бобров", 37, null
Если сессия читающая, то поле ChangeIdx игнорируется.
Если сесси пишущая, а в вашей СУБД она всего одна для таблицы, то во время прохода смотрим:
У записей с айди 100 и 300 ChangeIdx = null, значит они не модифицировались, считываем данные как есть.
У записи 200 ChangeIdx = 0 значит в массиве изменений arrChangedPersons[ChangeIdx] по индексу 0 для него есть изменённая запись, например, с новым возрастом
arrChangedPersons[0] = 200, "Петров", 55
Петров повзрослел на год. Всё, просто забираем эту новую запись из arrChangedPersons без всяких проходов.
Дальше можно подумать, как не дублировать в arrChangedPersons данные которые не изменились, а писать туда только изменения. Допустим, у записи 200 поменялся и возраст, и фамилия - Петров стал 56-летним Петровским. Может тогда в arrChangedPersons[0] помещать односвязный список записей с полями:
arrPersons.rowIdx // индекс строки основного массива
arrPersons.colIdx // индекс столбца основного массива
newValue // новое значение, допустим, "Петровский"
nextPointer // указатель на следующее изменённое значение записи таблицы, относящеесе уже к возрасту 200-го
...
и т.д.
arrPersons.rowIdx даже не нужен, строка откуда пришли уже и так известна, а если запись удалена, то элемент arrChangedPersons будет содержать пустой список null. Ну и ещё м.б. отдельный массив для заинсерченных в пишушей сессии записей arrInsertedPersons, с проходом по нему после основного массива arrPersons. Если нужен частичный откат транзакции до точки останова, то надо сохранять всю историю изменений, будет чуть сложнее
И что получаем. На каждый цикл проверки делать дополнительную проверку 4 поля. И того если имеем миллион строк. Проверок делаем 2 миллиона при переборе (в случае когда условие например придётся на последнюю строку). А если учесть что это будут if с переходом — то скорее всего поломается оптимизация в проце для чистого перебора массива.
Далее мы должны в каждой таблице загруженной в RAM делать дополнительную колонку — например int. И того на 1M строк имеем лишние 4Mб данных.
Меня больше всего волнует потеря производительности для двойной проверки каждой строки.
Например как учитывать новые добавленные строки? В старой таблице не будет этих строк и собственно не будет 4-го поля для анализа.
Как учитывать удалённые строки? Это придётся ещё тогда служебный столбец добавлять типа deleted. И его тоже анализировать при каждом цикле?
Одновременно транзакция write может работать только 1. Потому как на каждый write придётся дублировать все эти поля.
Если у вас вся таблица в памяти, то держите 2 массива — данные таблицы на начало транзакции + массив вставленных значений в этой транзакции такой же структуры. В коде будет 2 одинаковых цикла по двум массивам, друг за другом
Плюс делать не одну простую проверку за цикл, а как минимум 3 — на предмет удаления строки, на предмет новой строки, на предмет изменения данных. И это только что всплыло в обсуждении. Что там ещё при разработке всплывёт?
Это я не упоминаю про индексы. Это те же самые массивы. Для них тоже придётся всякие служебные колонки вводить. И вообще непонятно что будет с раздвоенным индексом, в варианте вставки/удалении строк.
Я не говорю что идея плохая. Просто в представленном виде она имеет критичный оверхед. Но зерно в ней есть, надо подумать над ней, может получится усовершенствовать.
В MS SQL версионность включается на уровне базы настройкой READ COMMITTED SNAPSHOT ON/OFF
Показалось, что у вас каша в голове.
Для обеспечения изоляции транзакций применяют или блокировки, или версионность записей.
Почти все популярные субд (oracle, mssql, mysql, postgres) идут по пути версионирования (MVCC) – это не фишка только ораклы! А вот то, как устроен MVCC внутри, есть конечно отличия. Например, оракла / мускуль хранят в блоке данных только актуальные версии, а прошлые версии пишут в undo-лог, а постгрес хранит в блоке все версии, от чего таблицы "пухнут".
Целостность не приобретает никакой "другой смысл", целостность - это сохранение инвариантов. А то о чем вы говорите – на основе чего строить данные, какие данные видны – это про изоляцию. И для ее обеспечения, как я уже вначале упомянул, есть свои варианты.
Делал в свое время колоночную БД, правда без транзакций. Тоже байт-код использовал, но разбивал работу с таблицами на блоки из трех сегментов: чтение+фильтрация, все вычислительные операции, запись; так чтобы каждый блок мог выполняться в несколько потоков. Оптимизировал только вычислительные операции, а чтение и запись конвертировались в один в готовые узлы сканирования/записи таблиц.
PS: Вы случайно не вдохновлялись SQLite?
Случайности не случайны, не зря в тегах статьи стоит SQLite, а в источниках — её архитектура :)
Для меня она стала путеводной звездой, образом простоты и функциональности — и это позволило мне взглянуть на неё с другой стороны. Если бы многие вещи в SQLite были доступны без дополнительных танцев с бубном через pragma, то, я думаю, у этой СУБД было бы больше поклонников и меньше тех, кто рассматривает её только как СУБД для тестов (что на самом деле является не очень практичным подходом).
Помимо этого, я вдохновлялся давнишней статьей с СУБД на Python от студентов Иннополиса. Идея об изучении строения СУБД через её создание появилась именно после прочтения той статьи — и я хотел бы воспроизвести такие последствия и для других читателей, но уже для этой статьи.
Меня в SQLite впечталило "100-процентное покрытие по MCDC" и последующее практически полное отсутствие багов.
Интервью с создателем SQLite (часть 2): Android 2005, хвала Кнуту, 100% тестовое покрытие, собственная CVS / Хабр (habr.com)
зы. ClickHouse на минималках :) real-time-intelligence/fbase: Hybrid time-series column storage database engine written in Java (github.com)
Я нихчего не понял. Какие-то дикие скачки от архитектуры к языку запросов, потом к схеме хранения данных, потом снова к языку, потом опять схема, потом транзакции, и опять язык…
И все это приправлено густопсовым словоблудием.
С одной стороны, объем проделанной работы вызывает уважение. С другой — описание этой работы напоминает острую форму шизофазии.
Сам посыл верный, разобраться в том, как работают базы данных, однозначно полезно. Но при этом разбираться желательно без лирических отступлений и авторских ремарок (с претензией то ли на остроумие, то ли на фамильярность), занимающих чуть ли не половину текста.
И без ненужного функционала. Для того, чтобы описать сложную систему, надо даже часть важного функционала опускать, не говоря уже о добавлении в систему ненужного. Зачем здесь постраничная организация? Причем логика так и осталась неясной: если у нас и так бинарный формат, то зачем страницы-то? Если все делается ради чтения сегментами, то кто мешает читать теми же сегментами из одного файла? Вроде бы, где-то к середине автор пришел к концепции индексов. Но если у нас есть готовый указатель на смещение в файле, то зачем тут еще и страницы?
Попытка галопом по европам рассказать такие понятия как транзакции и блокировки удалась тоже так себе.
В общем, вам надо в первую очередь серьезно поработать над стилем и связностью изложения.
Благодарю за ответ, минус не мой.
И я согласен с тем, что это самое настоящее галопом по Европам. Но плохо ли это? Может, кому-то и требуется краткий (или не очень) экскурс в происходящее?
Цель статьи не обеспечить человека всей той теоретической базой, которая заложена в реляционных СУБД. Эту задачу и без меня выполняют вполне уважаемые люди, которые пишут интересно и пишут по делу. Но что бы взяться за увесистые тома ценной информации, нужно, что неудивительно, заинтересоваться. Не каждый программист имеет под боком достойного преподавателя, наставника, который за приличное время сможет рассказать об этом.
Цель статьи — заинтересовать читателя копнуть глубже, попробовать сделать что-то самим. Писал, в конце концов, я для себя — и если бы у меня под рукой пару месяцев назад была данная статья — я был бы нескончаемо рад.
По поводу стилистики текста — кому-то такой стиль очень понравился. Кому-то нет. Разве не так всё устроено в нашем мире? А диагнозы я бы, честно говоря, придержал при себе. Но развиваться есть куда — и я понимаю это как сейчас, так и тогда, в самом начале создания статьи.
По поводу постраничной организации — данный формат организации данных задаёт логику организации БД — какие-то страницы у нас рассказывают о таблицах, другие — о страницах в таблице, третьи же — о самих записях. Это позволяет нам строить индексы на основе деревьев, упрощает логику упреждающего журнала и так далее, и так далее...
Как такое сделать без страниц или любого другого формата упаковки строк, я не очень представляю. Поделитесь же тогда вы своим виденьем :)
P. S. Я бы больше задумался о необходимости «виртуальной машины» и кодогенератора. Так ли он нужен при наличии реляционной алгебры — возможно стоит несколько усложнить хранение операций и отсечь необходимость кодогенератора, позволив движку работать непосредственно с ней.
Это позволяет нам строить индексы на основе деревьев, упрощает логику упреждающего журнала и так далее, и так далее...
Возможно. Но из текста это совершенно неочевидно. О чем, собственно, и речь. Причина разбивки на страницы подана невнятно. Только что у нас был текстовый файл с одной таблицей — и уже один бинарный, разбитый на страницы, с кучей таблиц. У вас хорошо получается чесать языком на отвлеченные темы, но когда речь заходит о деле, начинаются провалы в логике. Хотелось бы обратного соотношения.
Вопрос, хранить ли все в одном файле — полностью вторичен. Это, скорее каприз, чем необходимость. Каприз, который усложняет реализацию и объяснения. И получается, что страницы с информацией таблицах становятся не нужны. Остается постраничная разбивка записей, про которую опять же, ничего не объяснено.
Разумеется, мой теоретический багаж меньше вашего. И ничего подобного, задуманной вами системе я никогда не делал. И, скорее всего, многие ваши решения технически оправданы. Но из текста это не видно.
"Кому-то нравится" — это, конечно, хорошее оправдание для себя, но оно не делает вашу фривольную манеру изложения лучше. Мемасики не могут заменить логические связки.
Немного подумав, как обычно хорошая мысля приходит опосля, я пришёл к тому, структуру статьи можно было выстроить иначе, более понятно. Но что получилось, то получилось :)
Статья вышла как набор заметок «по поводу», и, собственно, она таким образом и создавалась (см. Zettelkasten). Постараюсь не допустить такой оплошности в будущем — комментарии с критикой на Хабре это очень ценный ресурс для развития. Благодарю за неё!
P. S. Ниже в комментариях один из читателей уже вдохновился продолжить какой-то свой собственный проект. Статья свою задачу выполнила — а остальное лишь послужит почвой для будущих статей. Проба пера — она такая :)
Вот у мне тоже не получается нормально написать с первого раза. Сейчас бы я свой исходный комментарий написал совсем по-другому, без пассивной агрессии. По-хорошему, надо было просто ограничиться короткой рекомендацией, что хотя хорошая шутка и разбавляет текст, облегчая чтение, но когда их становится слишком много, то функция меняется на противоположную — становится сложнее воспринимать основной текст.
Ну и должен отметить что все это относится только к тексту, а не к проекту, который сам по себе вызывает безмерное уважение.
А мне наоборот очень зашёл ваш стиль изложения. Согласен с предыдущим оратором только в том, что местами получилось несколько сумбурно, но мне это ни сколько не помешало.
Но по поводу страниц хотел бы сказать зачем мы их применили у себя. Не буду описывать тернисты путь, как мы выбирали размер и прочее, напишу 2 главные причины.
Страницы на диске по 8Кб — основная причина, если мы изменили 1 байт в таблице, не хотелось бы переписывать 16Мб на диске, если страница например 16Мб. Изначально такой размер был выбран для получения преимуществ в скорости чтения с диска, и количества файлов в файловой системе, которое тоже ограничено, и прочего. Но последующая разработка показала оптимальным всё таки размер совпадающий с размером странице диска.
Страница в RAM — тоже равна 8Кб. Основная причина — экономия RAM. Загружать в RAM только те страницы которыми пользуешься.Опять же если страница RAM и DISK одинакового размера — то упрощает их синхронизацию.
Вы очень решительны, если сходу взяли очень широкий фронт работы по всем направлениям одновременно. Мне кажется на реализацию нужно несколько тысяч человеко-часов (1.5-2 года full time). Посмотрел ваши исходники sicql - почти всё ещё предстоит сделать. Несмотря на то, что в своем проекте Boson (NoSql) уже реализовывал отдельно виртуальную машину и компилятор, и B+ Tree индекс, и Storage, и CachedFileIO (аналог pager), но "подружить" эти наработки в целостный продукт довольно сложно. Хочу пожелать вам, как коллеге, терпения и удачи!
Да, с кодом, соответствующим текущим виденьем архитектуры, не очень густо :)
Прототип, который не знал ни о блокировках, ни о транзакциях, ни об индексах, меня настолько не удовлетворил, что я сознательно начал всё сначала. Это стало похоже на эксперимент — возможно ли по тексту статьи восстановить то, что имел в виду её автор :)
А о вашем проекте наслышан — то ли сезон своих СУБД начался, то ли ретроградный Меркурий. Благодарю, вам тоже желаю удачи!
Поскольку я рос вместе с mysql, то мне более логичным представляется скорее последовательный подход, чем "всё и сразу".
Из всего перечисленного самым важным элементом мне представляются индексы. Без которых БД действительно не взлетит. Собственно, MySQL была вполне себе юзабельной без транзакций и строчных блокировок, но имея индексы и табличные блокировки. На энтерпрайз не годилась, но весь веб на себе 3.23 тащила только в путь.
И в этом смысле я задаюсь вопросом — а так ли уж надо делать все сразу: и транзакции, и индексы, и блокировки, и парсер языка, и систему хранения? Может быть, выделить пару приоритетов и сосредоточиться на MVP? Особенно учитывая, что "с кодом пока не очень густо"?
Я смотрю на ситуацию несколько иначе. Я где-то вычитал одну мысль, что проект исследовательский и пэт-проект это вещи несколько разные. Первый вид домашних проектов создаётся с целью узнать что-то новое, второй же — пройти в тех же домашних условиях путь создания бизнес-продукта. Их цели не всегда пересекаются.
Предыдущий проект был как раз тем MVP — «давайте не будем запихивать все функции сразу, а сделаем хоть что-то в короткие сроки». Лично меня в конкретной ситуации разработки СУБД такой подход не удовлетворил — банально не хватило теоретической базы, чтобы предварительно учесть будущие требования к продукту.
Данная часть как раз и является подготовкой теоретической базы, хоть и в своём особенном формате, на основе которой можно будет строить проект. Такой подход не всегда клеится с бизнес-разработкой, где, обычно, теория ясна, требования накидываются постоянно, а первые деньги желательно было получить уже вчера.
Я всё-таки рассчитываю на то, что, получив опыт создания исследовательских проектов через «сначала в теории, затем всё на практике», получится более разумно подходить к бизнес-разработке. Собственно, что и получается — MySQL не очень-то и нужны были эти транзакции с самого начала, жить можно было и без них :)
У меня есть библия для тех, кто будет заниматься "главой 3". Издание 78 года, но по прежнему все актуально :)
Сам когда-то развлекался этим...
Журналируемую БД наверное проще реализовать на LSM-деревьях, однако в книге Кнута 1973/1978 года их быть ещё не должно.
Да, упоминания LSM там нет.
Почитал сейчас бегло про LSM. Сложилось впечатление, что они устроены заметно сложнее. И еще впечатление, что их трудно назвать "базовым" алгоритмом. Возможно, ошибаюсь.
По-видимому, lsm проще, чем b-деревья.
Читал о реализации наподобие следующего: 1 неотсортированный "журнал" в памяти или на диске, плюс n отсортированных сегментов на диске. При поиске просматривается "журнал", а затем все остальные сегменты. При вставке/обновлении в журнал добавляется запись, при удалении - отметка о удалении. Если журнал велик, он сортируется и сбрасывается на диск как новый сегмент. Сегменты при каких-то условиях объединяются (сортировка слиянием), при этом перезаписанные или удалённые записи теряются. Ещё элементарно делаются снэпшоты для изолированных транзакций - это всего лишь дополнительный журнал на транзакцию, который либо сливается с сегментами потом, либо отбрасывается.
Интересная вещь.
Ой, не все так просто...
Куча вопросов. Например - в каких структурах хранятся данные на диске? Допустим, таблица в миллион строк - как она лежит на диске? Как в ней осуществляется выборка записи по ключу?
В том, что находится в памяти - те же вопросы. Как осуществляется хранение и поиск? Даже если данные отсортированы, двоичный поиск не эффективен, даже в памяти на современных процессорах с кэшем - при каждом сравнении будут обращения к разным адресам в памяти, их не будет в кэше процессора. А у B-деревьев ключевые данные лежат компактно и будут в кэше с гораздо большей вероятностью.
А про диск все то же самое, только еще хуже. В общем, в описании LSM я не нашел самого главного - как делается поиск. Возможно, плохо смотрел. Но что-то мне кажется, что там используются какие-то более базовые кирпичики. Например, в памяти хэш-таблицы, а на диске - те же B-деревья.
А как строятся дополнительные индексы?
Я как бы не утверждаю, что LSM плохо, нет. Просто я не знаю деталей реализации. А B-деревья я делал, на C++, знаю все детали. Хотя, возможно, по этому они кажутся мне простыми))
В общем, в описании LSM я не нашел самого главного - как делается поиск.
Поиск посегментно, начиная с "журнала", а затем с последнего записанного сегмента к первому, пока данные по ключу не найдутся. Внутри сегмента данные упорядочены, так что подойдёт бинарный поиск. Журнал может быть небольшой и неупорядочен, так что линейный поиск. Но можно, конечно, загружать сортированный сегмент или журнал в память для кэширования, и уже в памяти любые структуры строить - хоть b-деревья, хоть хэш-таблицы. Наверно.
Я не очень знаком с этой структурой, прочитал описание несколько дней назад. Мне она показалась относительно простой, но если оптимизировать, конечно можно залезть в дебри.
Вот тут нашел что-то про LSM на хабре: https://habr.com/ru/company/vk/blog/358210/
А, ну вот, из той статьи
Например, Tarantool использует для хранения L0 B+*-tree, о которых я рассказывал в своём блоге.
На диске, как понимаю, примерно то же самое. Они скидываются и сливаются.
Получается, как я и предполагал, LSM-деревья работают на B-деревьях. То есть, от B-деревьев уйти никак не получится)))
Это частная реализация.
L0 B+*-tree
Похоже на надёжный пароль.
На текущий момент я не знаю более эффективных универсальных алгоритмов хранения информации с возможностью быстрого поиска, чем B-дерево. Именно универсальных. В каких-то частных случаях могут быть более эффективные решения, например, хэш-табицы.
А LSM, как я понял, это не алгоритм хранения и поиска, а скорее надстройка над ними. Там нет самого поиска. Он по прежнему использует старые вещи. Скорее всего варианты B-деревьев, просто других альтернатив нет.
В памяти для маленьких деревьев еще могут быть варианты. А вот для диска более эффективных структур я не знаю.
LSM по скорости поиска чуть менее эффективно, чем B дерево (всё-таки, сегменты перебираются линейно, да и в кэш процессора не влезают). У него другие плюсы, типа асинхронной балансировки без прерывания операций поиска и записи, и очень быстрой записи. Если интересно, можете посмотреть на реализацию f2fs - там lsm деревья используются, если верить вики.
Волшебные приключения в удивительном мире разработки СУБД. Самое то в сочельник. :) За Rust отдельный респект! Спасибо за увлекательную историю.
есть ещё одно важное требование у СУБД, в случаи проблем с диском или фс база не должна превратиться в тыкву, была статья на хабре что та же sqlite в этом плане хорошо отрабатывает и например лучше использовать её, чем пытаться писать в файлы какие-нибудь данные, если там конечно не тривиальный случай
Я мельком думал насчёт того, как поведёт данная система в случае, когда операционная система отдаст концы. В общем, должны сохраняться те транзакции, которые были заверены — а заверяются они тогда, когда происходит fsync() в упреждающий журнал. Тогда данные сохранятся в журнале даже при перебое питания (насколько я это понимаю). Если же сбой произошёл при переносе страниц из журнала в основной файл — то данные удаляются из журнала только в самом конце операции. В любом случае эту операцию начнёт сначала первое открытое соединение СУБД, когда оно заметит переполнение журнала, так что заверенные данные останутся в сохранности. По логике...
Очень круто и сильно впечатляет! Спасибо Вам за проделанную работу!
@sicikh, спасибо огромное за качественный и мотивирующий русскоязычный текст по декомпозиции в архитектуре ПО - я рассматриваю вашу статью именно в этом ключе. Это достаточно редкое чтиво.
Сейчас сяду за компьютер и попробую применить на практике предложенный вами подход "начать думать с двух сторон" - а то уже на несколько месяцев забросил разработку своего детища из-за неподдающихся решению проблем с послойной декомпозицией.
Спасибо!
Как же это прекрасно :)
Да, интересно, продолжайте. Неплохо бы, например, подробнее про формат страницы. Там же ещё где-то инфа о полях таблицы должна быть, их типах. Что если размер записи превышает размер страницы и занимает, скажем 2.5, а не одну. Или запись не имеет фиксированной длины, поскольку содержит текстовые поля неограниченного размера, причем так, что сам текст может занимать больше одной странцы. Есть ли вообще смысл размещать большой текст постранично? Кроме самих данных и ссылки на следующую странцу, какую метаинформацию страница ещё должна содержать? И т.д., и т.п.
Очень тяжело читать, при том, что материал не выглядит как что-то запредельной сложности. Мне кажется, то описанию не хватает некоторой редактуры.
Поскольку архитектура вашего курса скорее "теоретическая" (это не объём практических знаний - а порядок изложения материала: теоретические учат с начала до конца (или с конца в начало) а практические с середины - сделаем ничего не делающий, но законченный MVP), то выигрышнее смотрятся курсы каждая глава которых построена по такой схеме:
1. общее описание - чего хотим добиться и почему;
2. набросок технической реализации;
3. некоторые частные, но важные технические детали + куда копать \ что улучшать в части 2 (весь бойлерплейт части-2 оставляем читателю воспроизвести самостоятельно, как упражнение к главе);
Как создать свою СУБД с нуля и не сойти с ума. Практическое пособие начинающему некроманту. Часть первая