Моя другая база данных - это компилятор

У нас открытый исходный код: github.com/chiselstrike/chiselstrike

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

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

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

В те дни, когда люди вставляли большие флоппи-дисководы в физические машины для их загрузки, вычислительные инновации означали новый набор инструкций для нового процессора. Но после пары десятилетий метаний между RISC, CISC, Cray, Sun, x86, Itanium и всем, что между ними, очень маловероятно, что в ближайшее время мы увидим новый соответствующий набор инструкций. Инновации происходят на уровне языка программирования в поиске новых способов взаимодействия с процессорами более быстрым и безопасным способом (подмигивая Rust) или в том, как вы соединяете эти вещи вместе (привет, M1!)

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

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

Рассмотрим следующий пример задачи: «Есть много людей с похожими именами. Учитывая конкретное имя и список пользователей, можем ли мы найти электронную почту тех, кто, вероятно, знает, почему значок сохранения выглядит так 💾”?

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

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

Но когда резина отправится в путь, данные не будут в памяти: они будут храниться в базе данных. Теперь вам нужно побеспокоиться о том, какая это будет база данных, какие у нее характеристики, каковы наиболее эффективные способы ее запроса и как удобно обернуть все это в ORM.

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

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

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

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

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

Мы уже видели эту проблему!

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

«Лучший способ что-то делать» сам по себе состоит из двух частей. Один факт, который поразил меня (много) лет назад, когда я впервые узнал, заключается в том, что заданная функция C/C++ возвращает 0:

Большинство оптимизирующих компиляторов не преобразуют это в очевидный (очевидный для тех, кто знает asm) x86 машинный код ниже:

Приведенный выше код сохранит регистры, которые потенциально могут быть уничтожены этой функцией, в стек, что является частью соглашения о вызовах функций x86, а затем установит регистр возврата в 0 с операндом mov (используется для загрузки значения в ячейку памяти или регистр). ), восстановить стек и вернуться.

Вместо этого оптимизирующие компиляторы x86 сделают что-то намного умнее:

Во-первых, компилятор замечает, что эта функция на самом деле не изменяет значение какого-либо регистра вне себя, поэтому сохранение и восстановление стека не требуется. Но умнее всего использовать оператор исключающее ИЛИ в регистре eax против самого себя, чтобы установить его в ноль.

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

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

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

Звучит знакомо?

Компиляторы и базы данных?

Так что же мешает нам сделать что-то подобное для баз данных? Давайте посмотрим, как это применимо к функции стрелки в нашем примере, user.age >= 40 && user.name == 'Glauber Costa'.

Первое, что должен сделать компилятор, — это разобрать ваш код на Абстрактное синтаксическое дерево. Мы используем swc для токенизации и анализа кода TypeScript, а затем можем преобразовать его в выражение фильтра, скажем, в SQL:

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

Встроенный компилятор ChiselStrike делает именно это: API запросов принимает стрелочные функции TypeScript, а встроенный компилятор преобразует выражения в выражения базы данных. Он также может узнать из этих выражений, какие индексы должны быть созданы, поэтому нет необходимости указывать их в модели.

Нам также не нужно разбивать ментальную модель TypeScript на SQL (или даже знать, поддерживается ли это вообще SQL). "Результат"?

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

Но как насчет времени выполнения?

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

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

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

Куда отсюда?

Есть еще много работы (и если вы заинтересованы делать это с нами, мы нанимаем!)

  • Скомпилируйте императивный код, такой как агрегации:недавние исследования показывают, что можно преобразовать циклы, подобные агрегации, в код базы данных, что мы планируем сделать после того, как улучшим наше внутреннее представление.
  • Автоматическое проецирование запроса. В настоящее время компилятор проверяет только лямбда-выражение, переданное функции фильтра. Однако, если мы проверяем целые конечные точки, мы можем — с помощью анализа побега — определить, какие свойства сущности используются на самом деле, и выполнить автоматическую проекцию. То есть среда выполнения может просто не SELECT использовать неиспользуемые столбцы в базовом SQL-запросе.
  • Используйте профилирование запросов для выбора индекса: хотя сейчас мы всегда создаем индекс при обнаружении кандидата, оптимальным образом будет учитываться информация во время выполнения. Это мало чем отличается от методов PGO в стандартных компиляторах.
  • Передача логики приложения в базу данных:компилятор ChiselStrike ограничен простыми выражениями, но мы можем сделать больше: в некоторых случаях мы можем передавать логику приложения в базу данных с помощью хранимых процедур. Точно так же мы можем избежать оценки некоторых предикатов во время выполнения, используя функции базы данных (например, запрашивая текущее время и преобразование строк).

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