Шардирование

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

Но в конце концов вы достигаете потолка возможностей одной машины. Запросы замедляются, операции записи становятся узким местом, а объем хранилища приближается к пределу. Даже мощные облачные базы данных, такие как Amazon Aurora, достигают максимума примерно на 256 ТБ.

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

Разделить данные между несколькими машинами.

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

Сначала: что такое партиционирование?

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

Рассмотрим таблицу заказов с 500 миллионами строк и 2 ТБ данных. Запрос на извлечение заказов прошлого месяца должен сканировать всю таблицу. Индексы становятся огромными и медленными в поддержке, а фоновые операции, такие как вакуумирование, анализ или перестроение индексов, могут блокировать всю таблицу и влиять на производительность.

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

Существует два распространенных типа партиционирования:

Горизонтальное партиционирование: разделение строк по разделам. Например, по одному разделу на год заказов. Те же столбцы, меньше строк в каждом разделе.

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

Что такое шардирование?

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

Например, если мы шардируем наши данные заказов по id, мы можем получить что-то вроде этого:

Каждый шард - это автономная база данных со своим CPU, памятью, хранилищем и пулом соединений. Ни одна машина не хранит все данные и не обрабатывает весь трафик, что позволяет масштабировать как объем хранилища, так и пропускную способность операций чтения/записи по мере добавления новых шардов.

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

Как шардировать ваши данные

Когда вы решаете шардировать, вам нужно принять два связанных решения:

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

Как распределять: правило присвоения этих групп шардам. Оно определяет, как данные распределяются по машинам.

Выбор ключа шардирования

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

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

Вот что делает ключ шардирования хорошим:

Высокая кардинальность (cardinality, мощность множества): ключ должен иметь много уникальных значений. Шардирование по булевому полю (true/false) означает, что у вас может быть максимум два шарда, что сводит на нет его целесообразность. Шардирование по user_id при миллионах пользователей дает достаточно пространства для распределения данных.

Равномерное распределение: значения должны равномерно распределяться по шардам. Если вы шардируете по стране и 90% ваших пользователей в России, этот шард будет значительно больше остальных. user_id обычно распределяется хорошо. Временные метки (timestamps) создания могут подойти, если новые записи не все попадают на самый последний шард.

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

Например, хорошими ключами шардирования будут:

user_id для пользователь-центричного приложения: высокая кардинальность (миллионы пользователей), равномерное распределение, и большинство запросов ограничены одним пользователем ("покажи мне данные этого пользователя").

order_id для таблицы заказов в интернет-магазине: высокая кардинальность (миллионы заказов), запросы обычно ограничены конкретным заказом ("получить детали заказа", "обновить статус заказа"), и заказы равномерно распределяются во времени.

А плохими ключами шардирования могут быть:

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

created_at для растущей таблицы: все новые записи попадают на самый последний шард. Этот шард становится горячей точкой для записи, в то время как старые шарды не обрабатывают почти никакого трафика.

Стратегии шардирования

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

Шардирование по диапазонам

Шардирование по диапазонам (range-based sharding) - самое простое. Оно просто группирует записи по непрерывному диапазону значений. Вы выбираете ключ шардирования, например user_id или created_at, затем назначаете диапазоны значений шардам.

Например, если мы шардируем по user_id, мы можем назначить первые 1 миллион пользователей шарду 1, следующие 1 миллион - шарду 2 и так далее.

Шард 1 -> User IDs 1–1M
Шард 2 -> User IDs 1M–2M
Шард 3 -> User IDs 2M–3M

Главное преимущество шардирования по диапазонам - простота и поддержка эффективных сканирований по диапазонам. Если вам нужны все заказы между user_id 500K и 600K, вы обращаетесь только к одному шарду.

Шардирование по диапазонам лучше всего работает, когда разные пользователи естественным образом запрашивают разные диапазоны. Мультиарендные (multi-tenant) системы, например, хорошо подходят для этого. Это системы, где каждая компания получает диапазон IDs. Представьте SaaS-приложение, где у каждого клиента есть диапазон user_id. Пользователи компании A запрашивают только диапазон компании A, а пользователи компании B - только диапазон компании B. Это распределяет нагрузку по шардам.

Хеш-шардирование (по умолчанию)

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

Например, если у нас 4 шарда, мы можем маршрутизировать пользователей так:

shard = hash(user_id) % 4

Пользователь 42  -> hash(42) % 4 = Шард 2
Пользователь 99  -> hash(99) % 4 = Шард 3
Пользователь 123 -> hash(123) % 4 = Шард 1

Большое преимущество хеш-шардирования - равномерное распределение. Поскольку хеш-функция перемешивает входные значения, новые пользователи распределяются равномерно по всем шардам.

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

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

Шардирование на основе каталога

Шардирование на основе каталога (directory-based sharding) использует таблицу поиска, чтобы определить, где хранится каждая запись. Вместо использования формулы вы храните соответствия между записями и шардами в таблице или сервисе отображения.

Например:

user_to_shard
---------------
Пользователь 15   -> Шард 1
Пользователь 87   -> Шард 3
Пользователь 204  -> Шард 2

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

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

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

Сложности шардирования

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

Горячие точки и дисбаланс нагрузки

Даже с хорошим ключом шардирования некоторые шарды могут обрабатывать значительно больше трафика, чем другие. Эта проблема называется проблемой горячих точек (hot spots), и она сводит на нет главное преимущество шардирования, потому что один перегруженный шард становится вашим узким местом.

Самая распространенная причина - проблема знаменитостей. Если вы шардируете пользователей по user_id, шард Тейлор Свифт обрабатывает в 1000 раз больше трафика, чем шард обычного пользователя. Каждый раз, когда кто-то просматривает ее профиль, ставит лайк ее посту или отправляет ей сообщение, этот запрос попадает на один и тот же шард. Хеш-распределение здесь не помогает, потому что проблема не в стратегии распределения, а в том, что некоторые ключи по природе более активны, чем другие.

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

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

Вот как с ними справляться:

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

Использовать составные ключи шардирования: вместо шардирования только по user_id объедините его с другим измерением, например hash(user_id + date). Это распределяет данные одного пользователя по нескольким шардам со временем, что помогает, если горячая точка имеет и большой объем, и охватывает временные периоды.

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

Операции между шардами

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

Проблема проявляется с запросами, которые не соответствуют вашему ключу шардирования. Если вы шардируете пользователей по user_id, запрос вроде "получить профиль пользователя 12345" обращается к одному шарду и выполняется быстро и просто. Но запрос вроде "получить топ-10 самых популярных постов в мире" должен проверить каждый шард, потому что посты разбросаны по всем пользовательским шардам. Вы отправляете запрос на все 3 шарда, ждете все 3 ответа, объединяете результаты и возвращаете топ-10.

Вы не можете полностью устранить межшардовые запросы, но можете минимизировать их:

Кэшировать результаты: если "топ-10 самых популярных постов" требует обращения ко всем шардам, кэшируйте результат на 5 минут. Первый запрос дорогой, но следующая тысяча запросов обращается к кэшу. Это особенно хорошо работает для запросов, которым не нужна точность в реальном времени (т.е. приемлема согласованность данных в конечном счете, eventual consistency). Таблицы лидеров, трендовый контент и агрегированная статистика - идеальные кандидаты.

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

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

Поддержание согласованности

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

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

Теоретическое решение, которое часто можно встретить в книгах - двухфазный коммит (2PC), где координатор просит все шарды подготовить транзакцию, ждет подтверждения от всех, что они готовы, затем отправляет команду всем выполнить коммит. Это гарантирует согласованность, но медленно и хрупко. Если любой шард или координатор откажет в середине транзакции, вся система окажется в застрявшем состоянии. Большинство реальных продакшен-систем избегают 2PC, потому что компромиссы производительности и надежности этого не стоят.

Так что же делать вместо этого?

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

• все это на одном шарде. Теперь все ваши транзакции одношардовые, быстрые и надежные.

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

Например, перевод денег между пользователями на разных шардах:

1. Списать деньги со счета пользователя A (шард 1)
2. Зачислить деньги на счет пользователя B (шард 2)
3. Если шаг 2 не удается, вернуть деньги пользователю A (компенсирующее действие)

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

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

Шардирование в современных базах данных

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

Распространенные NoSQL базы данных, такие как Cassandra, DynamoDB и MongoDB, позволяют указать ключ партиционирования и берут остальное на себя, но они не все используют один и тот же механизм распределения:

• Cassandra использует partitioner (например, Murmur3Partitioner) с виртуальными узлами, что является формой согласованного хеширования для отображения ключей партиционирования на диапазоны токенов на узлах.
• DynamoDB хеширует ключ партиционирования для маршрутизации элементов во внутренние разделы и разбивает/объединяет разделы по мере их роста; это не классическое кольцевое согласованное хеширование, доступное пользователям.
• MongoDB шардирует данные в сегменты на основе диапазонов по ключу шардирования. Если вы выбираете хешированный ключ шардирования, диапазоны - по хеш-пространству. Фоновый балансировщик автоматически разбивает и перемещает сегменты для поддержания баланса шардов. Это не классическое согласованное хеширование.

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

SQL базы данных также созрели и сделали шардирование проще, чем раньше. Vitess и Citus - популярные open-source слои шардирования, которые располагаются поверх PostgreSQL или MySQL. Они обрабатывают маршрутизацию запросов, межшардовые операции и решардирование без необходимости строить все самостоятельно. Облачные решения, такие как AWS Aurora и Google Cloud Spanner, предлагают распределенные SQL базы со встроенным шардированием.

Шардирование на собеседованиях по System Design

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

Когда упоминать шардирование

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

Поднимайте вопрос о шардировании, когда обсуждаете планирование масштаба и упираетесь в один из этих лимитов:

• Хранилище: "У нас 500 млн пользователей с 5 КБ данных на каждого, это 2.5 ТБ. Один экземпляр PostgreSQL справится с этим, но если мы вырастем в 10 раз, нам нужно задуматься о шардировании".
• Пропускная способность записи: "Мы ожидаем 50 тыс. записей в секунду при пиковой нагрузке. Одна база данных не справится с такой нагрузкой записи, поэтому нам следует шардировать".
• Пропускная способность чтения: "Даже с репликами чтения, если мы обслуживаем 100 млн ежедневно активных пользователей, делающих несколько запросов каждый день, нам нужно распределить нагрузку чтения по шардам".

Формула проста:

1. Определить узкое место
2. Объяснить, почему одна база данных не справится с нагрузкой
3. Предложить шардирование

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

Что говорить

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

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

2. Выбрать стратегию распределения "Я бы использовал хеш-шардирование с согласованным хешированием. Хешируем user_id для равномерного распределения пользователей по шардам".

3. Обозначить компромиссы "Компромисс в том, что глобальные запросы становятся дорогими. Если нам нужны "трендовые посты по всем пользователям", мы должны запросить все шарды и агрегировать результаты. Мы можем справиться с этим, кэшируя трендовый контент и предварительно вычисляя его в фоновой задаче, а не при каждом запросе".

4. Объяснить, как вы будете справляться с ростом "Мы начнем с 64 шардов, что даст нам пространство для роста. Согласованное хеширование упрощает добавление шардов позже без решардирования всех данных. Если нам потребуется больше емкости, мы можем добавить шарды, и переместим только часть данных".

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

Заключение

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

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

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

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