Статьи

4 проанализированных стратегии разделения данных для распределенного SQL

Август 17, 2017

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

Что такое YugabyteDB? Это высокопроизводительная распределенная база данных SQL с открытым исходным кодом, построенная на масштабируемой и отказоустойчивой конструкции, созданной по мотивам Google Spanner. SQL API (YSQL) Yugabyte совместим с PostgreSQL.

Уроки построения систем с разделенными данными

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


Вам также может быть интересно прочитать: 
Что такое распределенный SQL?

Memcached и Redis — алгоритмический шардинг

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

Часть изображения из источника:  Как работает Sharding

Pros

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

Cons

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

Анализ

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

Это делает этот тип шардинга плохим вариантом и не реализован в YugabyteDB.

Ссылки

Начальная реализация в Кассандре — Линейный хэш-шардинг

Различные члены команды Yugabyte принимали непосредственное участие в первые дни создания Cassandra в Facebook (около 2007 года), задолго до того, как он стал проектом с открытым исходным кодом. При проектировании шардинга данных в Cassandra мы обращали внимание на Bigtable от Google (который по умолчанию занимался шардированием) и Dynamo от Amazon (который по умолчанию использовал согласованное хэширование). В качестве попытки достичь лучшего из обоих миров мы выбрали линейное хэширование, также известное как  OrderPreservingPartitioner  в Кассандре.

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

Pros

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

Cons

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

Анализ

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

Это описано в документации  Apache Cassandra :

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

Следовательно, это плохая стратегия разделения и не реализована в YugabyteDB.

DynamoDB и Cassandra — последовательный хэш-шардинг

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

Pros

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

Cons

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

Анализ

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

Мы решили, что YugabyteDB должен поддерживать постоянное хэширование.

Google Spanner и HBase — Sharding диапазона

Apache HBase — это масштабируемая распределенная база данных NoSQL, созданная по образцу Google BigTable. Это еще одна база данных, с которой знакомы многие члены команды Yugabyte, учитывая, что они много лет назад создали и запускали HBase в масштабе в Facebook. Это была база данных, которая поддерживала несколько интернет-сервисов, таких как Facebook Messenger (платформа обмена сообщениями между пользователями) и Оперативное хранилище данных (которое обеспечивало метрики и оповещения во всей инфраструктуре Facebook). В HBase, как и в Google Spanner, есть поддержка разделения диапазонов.

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

Pros

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

Cons

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

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

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

Анализ

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

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

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

Собираем все вместе

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

Поддержка согласованного хеширования и разделения диапазонов

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

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


SQL