[Перевод] Как был создан потоковый SQL-движок
Возможно, вы как раз их тех, кто, просыпаясь каждое утро, задаёт себе три самых вечных жизненных вопроса: 1) как мне сделать потоковый SQL-движок? 2) Что это такое — потоковый SQL-движок? 3) Способен ли Господь наш сбрасывать те таблицы, коими владеет иной пользователь?
Я тоже ловил себя на том, что задаю себе эти вопросы, и порой они не оставляют меня даже во сне. Мне снятся различные SQL-операторы, которые тычут в меня пальцем, насмехаются над моей некомпетентностью, а я умоляю их, чтобы они ответили на эти вопросы.
Так вот, где-то год назад я (довольно смело, если «смелость» — это вообще про меня) снарядился как следует и пустился в долгий и тернистый путь, искать ответы на эти вопросы. Я шёл от монаха к пресвитеру, а от того — к жрецу макаронного монстра, и только в ужасе осознавал, сколь жалкие вопросы их занимают — например, каков смысл жизни, и как обрести мир с самим собой. Но, в конце концов, потерявшись в глубочайших расщелинах моего разума, я набрёл на часовенку, над входом которой значилось: «Epsio Labs». Тут я преисполнился откровения и вошёл в двери этого храма.
Друзья, сегодня я поделюсь с вами теми таинствами, которые познал там (за исключением тех, что подпадают под многочисленные NDA).
Что такое потоковый SQL-движок
Потоковый SQL-движок обеспечивает, чтобы результаты SQL-запросов всегда оставались актуальны, и их не приходилось пересчитывать. Даже в тех случаях, когда меняются данные, на которых основан запрос. Давайте разберём ситуацию на примере. Представьте себе простой запрос, например, SELECT count(*) FROM humans . Обычному SQL-движку (например, такому, как работает в Postgres, либо такому, как в MySQL) требовалось бы заново пересматривать все отдельные экземпляры humans при каждом выполнении такого запроса. Эта операция была бы весьма затратной и длительной, учитывая, что население на планете постоянно меняется. Но, работая с потоковым SQL-движком, можно было бы определить этот запрос всего один раз, и движок постоянно обеспечивал бы актуальность результата, учитывая как рождаемость, так и смертность. Не потребовалось бы никакого пересчёта, тем более не пришлось бы заново считать всех землян.
Как создать потоковый SQL-движок
Итак, простой пример, приведённый выше, вполне позволяет составить впечатление о том, как работает SQL-движок. Для начала требуется знать, как сработал бы любой обычный SQL-движок, если бы с его помощью потребовалось подсчитать количество людей. Далее, всякий раз при рождении нового человека вы бы увеличивали ваш результат на единицу, а всякий раз, когда кто-нибудь умирает, вы уменьшали бы результат на единицу. Всё просто, правда?
Давайте нарисуем схему, на которой изложим процедуру обработки такого запроса — например, как будет обрабатываться рождение нового человека. У нас есть ряд узлов, по одному на каждую операцию, а также «конечный» узел, в котором будет находиться таблица результатов. Поскольку мы имеем дело с потоковым движком, он работает именно с изменениями, и обмен сообщениями между нашими узлами будет представлен так:
где ключ — это та величина, которую мы хотим изменить, а модификация показывает, на какую величину мы хотим её изменить. Так, если бы мы хотели передать сообщение вида: «Эй, мистер Узел, тут добавилось 1,5 яблока», то оно выглядело бы так:
Каждый узел отвечал бы за приём изменений, выполнение операций того или иного типа, а затем за вывод результатов как таковых. Здесь есть и другая важная концепция: операции можно суммировать, при условии, что ключ у них один и тот же. Так, два изменения apple: 1.5 и apple: 2 эквиваленты apple: 3.5 . Бывает, что суммирование модификаций даёт 0, то есть, результат таков, как будто ничего не произошло. Например, у нас может быть два изменения, apple: 3 и apple: -3 . В таком случае ситуация эквивалентна той, в которой движку на вход не поступило никаких изменений. (Можете считать, что я дал вам три яблока, глубоко раскаялся в собственной щедрости и забрал у вас три яблока. С вашей точки зрения тогда бы ничего не изменилось — не считая того, что я испортил вам настроение). Чтобы этот пример выглядел более осмысленно, давайте нарисуем узлы, которые участвовали бы в нашем первом запросе (SELECT count(*) FROM humans), а затем добавим в систему первого человека, Адама.
Как видите, родился новый человек по имени «Adam». Узел «Counter» (Счётчик), названный так, вероятно, за способность считать, содержит внутреннее состояние, присущее сейчас процессу подсчёта людей в мире. Всякий раз, когда этот узел получает изменение (количество людей увеличивается млм уменьшается на единицу), движок обновляет свой внутренний счётчик, а затем выводит актуальные изменения. В данном случае требовалось учесть всего одно изменение: сообщить следующему узлу о необходимости один раз добавить единицу (в результате имеем текущее число людей, живущих на Земле). В таком случае следующим шёл бы узел «Final Results Table» (Итоговая таблица результатов). Это была бы полноценная реляционная таблица (хранимая, например, в Postgres). Можно представить себе, как любое такое действие транслируется в операцию DELETE или INSERT, в зависимости от ключа и модификации.
Далее давайте добавим Еву:
На этот раз узел счётчика должен вывести два изменения. Одно из них будет отменять предыдущее изменение, которое он вывел ранее, а второе — выдавать новое, обновлённое значение. В сущности, если бы мы попробовали просмотреть все изменения, которые узел Счётчик вывел в течение некоторого времени, то получили бы:
Поскольку разрешено комбинировать изменения с одинаковым ключом, вышеприведённое выражение эквивалентно следующему:
Если модификация равна нулю, это означает, что данное изменение можно просто удалить. Тогда в таблице с окончательными результатами у нас останется только 2: +1 — именно это нам и было нужно.
Что, к вам уже подбирается этот сладостный катарсис? Ага, ко мне тоже.
Другой пример, немного поинтереснее
Теперь представьте, что вы дьявол, и работаете с двумя таблицами:
1. «Таблица людей», в которой два столбца. В один столбец заносится уникальный идентификатор, а в другой — имя.
2. «Таблица зла», соотносящая id конкретных людей с (не)принадлежностью конкретного человека к числу злодеев.
Вполне очевидно, что нам было бы интересно подсчитать всех злодеев, и при этом учесть их поимённо:
SELECT humans.name, count(*) FROM humans
JOIN evil_humans ON humans.id = evil_humans.human_id
WHERE is_evil IS true
GROUP BY humans.nameЧтобы можно было создать план такого запроса (выстроить последовательность запросов), здесь нам потребуется ввести новые типы узлов.
Узел фильтрации
Такой узел позволяет фильтровать изменения по ключу, безотносительно их модификаций. Если изменение «проходит» фильтр, то он пропускает его как есть. Чтобы вам было проще составить впечатление о таком механизме, давайте изобразим такой узел, который будет пропускать лишь те изменения, ключ которых равен слову «cats» (кошки).
Как видите, мы подали на фильтр 3,4 кошки, и он, как ни удивительно, пропустил их без каких-либо изменений. Теперь давайте попробуем пропустить через этот фильтр «собак» (dogs):
Ого! На этот раз фильтр ничего не пропустил. Думаю, идею вы уловили. Идём дальше.
Узел объединения
Узел объединения (Join) отвечает за приём изменений от двух узлов и за вывод тех изменений, у которых «ключи объединения» совпадают. Для этого он поддерживает внутреннее состояние (хранилище данных) для всех проходящих через него изменений, отображая эти изменения на соответствующие им ключи объединения. Так, в нашем примере с
JOIN evil_humans ON humans.id = evil_humans.human_idмы бы создали один узел Join с двумя соответствиями:
Одно — слева, для отображения id на name
Второе — справа, для отображения human_id на is_evil
На практике эти отображения будут выглядеть примерно так:
Всякий раз, когда на узел Join будет поступать изменение с одной из сторон, он будет искать на другой стороне ключ, подходящий к этому изменению. Если найдёт, то выведет комбинацию значений. Давайте попробуем изобразить простой пример, где на узел Join подаётся новый человек по имени Томми с id 232, а затем вносим в базу данных изменение, согласно которому человек с id 232 — не злодей.
Сперва новый человек по имени Томми вступает в мир:
Ладно, наш поток подтянул изменение, сообщающее узлу Join, что в базу данных добавлен Томми с id 232. Узел Join подыскивает соответствие для указанного изменения по ключу 232 — и ничего не находит. Следовательно, он ничего не выводит, однако обновляет своё внутреннее отображение, чтобы отразить факт добавления Томми. Это поможет нам при следующей операции:
Здесь узел Join получил изменение, пришедшее справа и сообщающее, что человек с id 232 — не злодей. Затем узел Join поискал отображения слева, нашёл соответствующее изменение, о котором мы говорили выше (232: Tommy-) — и вывел скомбинированное изменение.
Но на этом история Томми не заканчивается. В любой момент могут поступить и другие изменения. Например, Томми упадёт с лестницы и погибнет. В результате узел Join получит Tommy, 232: -1, в результате чего этот узел выведет (232, Tommy, false): -1 — тем самым отменив предыдущее изменение Join. Либо у Томми может измениться показатель «злодейства» — этот пример мы прибережём на будущее.
Замечание — как вы могли заметить, здесь мы сказали, что «ключ объединения может измениться», но не ведём счёт модификаций при отображении объединений. В реальной практике, конечно, ведём, а затем перемножаем счёт модификаций с обеих сторон, чтобы получить итоговое количество модификаций.
Узел Group By
Узел «Group By» (Сгруппировать по) очень похож на узел-счётчик, уже рассмотренный выше. На самом деле, они просто близнецы-братья, но это уже история для другой статьи. Узел Group By выводит информацию, агрегированную по «корзинам». Так гарантируется, что все выведенные изменения непременно будут скомибинированы, и у вас останется не более чем по одному изменению на корзину. Вспомните, как мы брали в одну партию все изменения, с течением времени поступавшие на узел счётчика, и видели, что в итоге остаётся всего одно изменение, а остальные обнуляются. Это достигается путём поддержания внутреннего соответствия (в хранилище) между каждой корзиной и её агрегированным значением. Так, в нашем примере
SELECT humans.name, count(*) ... GROUP BY humans.nameузел Group By будет хранить соответствие примерно следующим образом:
Давайте попробуем изобразить простой пример и продемонстрировать, что произойдёт, если добавить на узел Group By новое имя, которое он никогда не видел:
Так что же здесь произошло? Изменение, поступившее на Group By — это приказ, по которому Group By должен увеличить Richard на единицу. Узел Group By просматривает свои внутренние соответствия и видит, что записи для Richard там нет. Он добавляет эту запись, а затем выводит Richard со значением, равным единице (это и есть ключ изменения (Richard, 1) ). Давайте продолжим и добавим ещё два экземпляра Richard:
Становится немного интереснее. Теперь узел Group By получает ещё одно изменение, согласно которому к Richard нужно добавить двойку. Узел Group By обновляет собственное внутреннее состояние, а затем выводит два изменения. Первое из них удаляет предыдущее, ранее выведенное изменение, а второе выводит новое, обновлённое значение количества для Richard.
Подытожим
Вернёмся к нашему исходному запросу:
SELECT humans.name, count(*) FROM humans
JOIN evil_humans ON humans.id = evil_humans.human_id
WHERE is_evil IS true
GROUP BY humans.nameЧтобы подготовить контекст для следующего примера, представьте молодого заправского программиста оп имени Томми, id 232 (возможно, вы помните его из давешнего примера, в котором объяснялись объединения). Томми — крутой чувак, который регулярно минусил негодяев на StackOverflow (злодейство=false).
Как-то раз Томми лягнула лошадь, и именно поэтому он неосторожно залил в master-ветку какую-то ерунду, одновременно с этим удалив всю непрерывную интеграцию. Этот случай мы представим в виде двух изменений. Одно из них отменяет предыдущее изменение, согласно которому Томми — не злодей (232, false): -1 , а второе добавляет новое изменение, согласно которому Томми — злодей (232, true): +1 :
Давайте кратко разберём вышеприведённый пример. Здесь мы вывели два изменения, о которых говорили выше: (232, false): -1 и (232, true): +1 . Узел Join получает эту информацию, проверяет соответствие с другой стороны (id → имена), находит имя (Tommy) и выводит внесённые изменения, сопроводив их именем «Tommy». Далее фильтрующий узел WHERE is_evil IS true отсеивает изменение (232, false): -1 , и, поскольку значение злодейства равно false, выводит только (232, true): +1 . Узел Group By принимает это изменение, смотрит свои соответствия, видит, что на Томми ранее уже была заведена запись. Следовательно, узел Group By отсылает одно изменение, отменяющее другое изменение, выданное ранее (Tommy, 7): +1 (это произошло, когда мы в прошлый раз добавляли злого Томми). Затем этот узел высылает ещё одно изменение, также изменяющее количество Томми.
Подождите, но зачем же нам все эти проблемы?
Итак, теперь в мире 8 Томми-злодеев, и, чтобы узнать этот результат, нам не приходится заново прогонять запрос. Вы, конечно, могли бы сказать: «Мистер Дьявол, да вам же не нужен потоковый SQL-движок для таких операций. Если у вас есть таблица со списком людей, в которой указано, кто из них злодеи, просто создайте индексные списки. Да, вам всё равно придётся перебирать все данные при каждом запросе, но эти операции поиска, как минимум, будут быстрыми. Узел Group By каждый раз всё равно должен будет начинать работу с нуля, но, всё-таки»…
Действительно, мы можем оптимизировать запросы так, чтобы они проверялись буквально на лету, но этот приём работает лишь до некоторого предела. По мере добавления новых операций объединения, группирования и (свят-свят!) WITH RECURSIVE, оптимизировать запросы становится всё сложнее. А по мере добавления в систему всяких Томми, Тимми, Эдвардов, Дженни (не говоря уже о Рикардо, Самуэлях, Джеффри и Бенни), даже этих оптимизаций может оказаться мало (причём, это я ещё далее не начал рассказывать о пороках, связанных с кэшированием данных на предприятии). Как сказал бы мудрец, потоковые SQL-движки, совершенно обалденны при решении таких проблем; собственно, именно для их решения они и созданы.
Заключение
Ну что, готовы создавать потоковый движок? Все необходимые для этого элементы мы уже разобрали, но пока не затронули некоторых важных концепций. Например, как обеспечивать постоянную согласованность (чтобы никогда не приходилось выводить фрагментарных результатов), как задействовать при этом всю пропускную способность системы (постоянно тягаясь с возникающими задержками), как нормально взаимодействовать с хранилищем данных (кто сказал async-io?). Может быть, напишу об этом другой пост, а может, и нет.
Кстати, о том, может ли Господь сбросить таблицу, которой владеет другой пользователь. Вопрос, очевидно, сводится к тому, использует ли Он RDS (если база данных у Него на собственном хостинге, то там он обладает правами суперпользователя, а в случае с RDS быть суперпользователем никому не дано. Да, даже Господу).
С тех пор, как я опубликовал эту статью, Старейшины из Epsio порешили, что более нет смысла утаивать свои тайны, поэтому выложили свой потоковый SQL во всеобщее пользование. Если хотите, можете посмотреть его здесь — поверьте, он просто летает.
