Миф о NoSQL (против СУБД) «присоединяется к масштабу»

Франк Пашот

.

Я сошлюсь на статью Алекса дебри «SQL, NoSQL и масштабирование: как DynamoDB масштабируется там, где реляционные базы данных не масштабируются», особенно на абзац о том, «почему реляционные базы данных не масштабируются». Но я хочу прояснить, что мой пост здесь не против этой статьи, а против очень распространенного мифа, который даже предшествует базам данных NoSQL. На самом деле я беру эту статью в качестве ссылки, потому что автор на своем веб-сайте и в книге имеет действительно хорошие моменты о моделировании данных в NoSQL. И потому, что AWS DynamoDB, вероятно, является самой сильной базой данных NoSQL на сегодняшний день. Я бросаю вызов некоторым широко распространенным утверждениям и лучше делаю это на основе хорошего качественного контента и продукта.

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

временная сложность соединений

Идея этой статьи, взятая из популярного выступления Рика Хулихана, заключается в том, что, соединяя таблицы, вы читаете больше данных. И что это очень интенсивная работа процессора. А временная сложность соединений «(O (M N)) или хуже», согласно статье Алекса дебри, или » O (log(N)) Nlog(M) » согласно слайду Рика Хоулихана. Это относится к» временной сложности «и нотации» Большого о». Вы можете прочитать об этом. Но это предполагает, что стоимость соединения зависит от размера задействованных таблиц (представленных N и M). Это было бы правильно при полном сканировании несекционированной таблицы. Но все реляционные базы данных поставляются с индексами дерева B*. И когда мы сравниваем с хранилищем ключ-значение, мы, очевидно, извлекаем несколько строк, и метод join будет представлять собой вложенный цикл со сканированием диапазона индексов. Этот метод доступа на самом деле вообще не зависит от размера таблиц. Вот почему реляционные базы данных являются королем приложений OTLP.

Давайте проверим это

В статье утверждается «что » есть одна большая проблема с реляционными базами данных: производительность подобна черному ящику. Существует масса факторов, влияющих на то, как быстро ваши запросы будут возвращаться.» с примером запроса типа: «SELECT * FROM orders JOIN users ON… Где user.id =… группа по… пределу 20″. Он говорит, что»по мере роста размера ваших таблиц эти операции будут становиться все медленнее и медленнее».

Я построю эти таблицы здесь, в PostgreSQL, потому что это моя предпочтительная СУБД с открытым исходным кодом, и покажу, что:

Создайте таблицы

Я создам здесь небольшие таблицы. Потому что при чтении плана выполнения мне не нужны большие таблицы для оценки стоимости и масштабируемости времени отклика. Вы можете выполнить то же самое с большими таблицами, если хотите увидеть, как они масштабируются. А затем, возможно, продолжить изучение возможностей больших таблиц (секционирование, параллельный запрос и т. д.). Но давайте начнем с очень простых таблиц без конкретной оптимизации.

Я создал две таблицы, к которым присоединюсь. Оба с автоматически сгенерированным первичным ключом для простоты.

Вставить тестовые данные

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

Это сгенерировало 10000 пользователей в таблице USERS со случайными именами.

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

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

Я нахожусь в PostgreSQL, версия 12, на коробке Linux только с 2 процессорами. Я запустил ручной вакуум, чтобы получить воспроизводимый тестовый корпус, а не полагаться на автовакуумное включение после загрузки этих столов.

Вот размеры моих таблиц: 1 миллион заказов занимает 104 МБ, а 10 тысяч пользователей — 1 МБ. Я увеличу его позже, но мне это не нужно, чтобы понять предсказуемость производительности.

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

Выполнить запрос

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

Объясните исполнение

Это так же просто, как выполнить запрос с помощью EXPLAIN:

Вот план выполнения со статистикой выполнения. Мы прочитали 3 страницы от пользователей, чтобы получить наш USER_ID (только индексное сканирование) и перешли с вложенным циклом к заказам и получили 100 заказов для этого пользователя. Это прочитало 3 страницы из индекса (сканирование растрового индекса) и 13 страниц из таблицы. Это в общей сложности 19 страниц. Эти страницы составляют 8 тысяч блоков.

4х первоначальных размеров при одинаковой производительности: 19 страницы читает

Давайте увеличим размер таблиц в 4 раза. Я меняю «generate_series(1100) «на» generate_series(1200) » в поколениях пользователей и запускаю то же самое. Это генерирует 40000 пользователей и 4 миллиона заказов.

Посмотрите, как мы здесь масштабируемся: я умножил размер таблиц в 4 раза, и у меня точно такая же стоимость: 3 страницы из каждого индекса и 13 из таблицы. В этом и заключается прелесть B * Tree: стоимость зависит только от высоты дерева, а не от размера стола. И вы можете увеличить таблицу экспоненциально, прежде чем высота индекса увеличится.

16X начальные размерные шкалы с коэффициентом затрат 21/19=1.1

Давайте пойдем дальше и снова увеличим размер таблиц x4. Я запускаю «generate_series(1400) » в поколениях пользователей и запускаю то же самое. Это генерирует 160 тысяч пользователей и 16 миллионов заказов.

Да, при значительном увеличении размера таблицы индексу, возможно, придется разделить корневой блок, чтобы добавить новый уровень ветви. Последствия минимальны: две дополнительные страницы для чтения здесь. Дополнительное время выполнения составляет десятки микросекунд при кэшировании в оперативной памяти и до миллисекунд при хранении на механическом диске. С таблицами 10x или 100x большего размера вы будете выполнять некоторый физический ввод-вывод, и только верхние ветви индекса будут находиться в памяти. Тогда вы можете ожидать около 20 вызовов ввода-вывода. С SSD на оптоволоконном канале (например, с AWS RDS PostgreSQL) это все равно будет происходить в однозначной миллисекунде. Самый дешевый AWS EBS Provisioned IOPS для RDS составляет 1000 IOPS, тогда вы можете оценить количество запросов в секунду, которые вы можете выполнить. Количество страниц здесь («буферов») — это правильная метрика для оценки стоимости запроса. Для сравнения с DynamoDB RCU.

Начальные размеры 64x с коэффициентом затрат 23/19=1.2

Последний тест для меня, но вы можете пойти дальше, я меняю на «generate_series(1800)» в поколениях пользователей и запускаю то же самое. Это генерирует 640 тысяч пользователей и 64 миллиона заказов.

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

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

Временная сложность дерева B * на самом деле очень легкая

Давайте вернемся к обозначению «Большое о». Мы определенно не » о (М Н)». Это было бы без какого-либо индекса, где все страницы из всех таблиц были бы полностью отсканированы. Любая база данных поддерживает хэшированные или сортированные структуры для улучшения запросов с высокой селективностью. Это не имеет ничего общего с SQL и СУБД и с СУБД и Иерархическая БД. В DynamoDB эта структура по первичному ключу является хэш-секционированием (и дополнительной сортировкой). В СУБД наиболее распространенной структурой является сортированный индекс (с возможностью дополнительного секционирования, зональных карт, кластеризации и т. д.). Мы не находимся в «O (log(N)) Nlog(M)», но больше похоже на» O(log(N)) log(M)», потому что размер управляющего стола (N) не имеет никакого отношения к стоимости внутреннего цикла. Первая фильтрация, та, что с «O (log(N))», отфильтровала эти N строк. Использование «N » и игнорирование внешней избирательности-ошибка. Во всяком случае, это O(log) для дерева B*действительно масштабируется, как мы уже видели, потому что база этой функции log() действительно мала (благодаря большим блокам ветвей – 8 КБ).

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

40 лет оптимизации СУБД

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

Благодаря 40-летней оптимизации OLTP-приложений база данных Oracle обладает множеством функций, популярность которых зависит от ИТ-тенденций. Начиная с первых версий, в 80-х годах, поскольку иерархические базы данных все еще были в сознании людей, а страх перед «соединениями стоят дорого» уже существовал, Oracle внедрила структуру для хранения таблиц вместе, предварительно Соединенных. Это называется кластер. С самого начала он индексировался с помощью отсортированной структуры (индексный кластер) или хэшированной структуры (хеш-кластер). Параллельный запрос был быстро реализован для масштабирования и, с параллельным сервером, теперь известным как RAC, для масштабирования. Секционирование было введено для дальнейшего масштабирования, опять же с сортированными (секционирование по диапазону) или хэшированными (секционирование по хэшу) сегментами. Это может еще больше масштабировать доступ к индексу (локальный индекс с обрезкой разделов). И он также масштабирует соединения (PARTITION-WISE JOIN), чтобы уменьшить процессор и оперативную память для объединения больших наборов данных. Когда требовалась большая гибкость, победителем становились сортированные по дереву структуры B*, а в кластеризованные данные вводились индексные таблицы (чтобы избежать самой дорогостоящей операции, как мы видели в приведенных выше примерах). Но таблицы кучи и дерево B * по-прежнему являются победителями, учитывая их гибкость и потому, что операции объединения редко были узким местом. В настоящее время улучшилось секционирование (даже горизонтальное масштабирование за пределами кластеров с шардингом), а также кластеризация данных (кластеризация атрибутов, карты зон и индекс хранения). И всегда есть возможность доступа только к индексам, просто добавив больше столбцов в индекс, удалив основную стоимость доступа к таблицам. А материализованные представления также могут выступать в качестве предварительно построенного индекса объединения и также уменьшат объем процессора и оперативной памяти, необходимых для группирования путем агрегации.

Я перечислил множество функций Oracle, но Microsoft SQL Server также имеет много подобных функций. Кластеризованные таблицы, охватывающие индексы, индексированные представления и, конечно же, секционирование. Базы данных с открытым исходным кодом постоянно развиваются. PostgreSQL имеет секционирование, параллельный запрос, кластеризацию. Все еще с открытым исходным кодом, вы можете масштабировать его в распределенную базу данных с помощью YugabyteDB. MySQL в последнее время очень сильно развивается. Я не буду перечислять все базы данных и все функции. Вы можете легко перенести testcase в другие базы данных.

Да, и кстати, если вы хотите протестировать его на базе данных Oracle, вы быстро поймете, что запрос из статьи может даже не выполнять никакой операции соединения. Потому что при запросе с помощью USER_ID вам, вероятно, не нужно возвращаться к таблице USERS. А благодаря объявленному внешнему ключу оптимизатор знает, что соединение не нужно: https://dbfiddle.uk/?rdbms=oracle_18&fiddle=a5afeba2fdb27dec7533545ab0a6eb0e.

Базы данных NoSQL хороши для многих вариантов использования. Но помните, что это оптимизированное по ключу и значению хранилище данных. Когда вы начинаете разбивать документ на несколько сущностей с их собственными ключами, помните, что реляционные базы данных были изобретены для этого. Недавно я написал в блоге о другом мифе: миф о гибкости NoSQL (против СУБД): добавление атрибутов. Все отзывы приветствуются здесь или в Твиттере:

Новый пост в блоге о другом мифе в NoSQL против СУБД:

«присоединяется не масштабируется»https://t.co/u4aBE4HXb7

И у Твиттера тоже есть интересные мысли по этому поводу у Алекса дебри:

Франк Пачот (@FranckPachot) — эксперт по СУБД и написал очень хороший ответ на более ранний пост, который я написал о том, как DynamoDB масштабируется там, где реляционные базы данных этого не делают. Я очень рекомендую его прочитать.

https://blog.dbi-services.com/the-myth-of-nosql-vs-rdbms-joins-dont-scale/