Divide et impera (разделяй и властвуй) – древний принцип для управления чем-то большим и сложным.

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

Что-нибудь разбить на кусочки – это круто! Переходите на сторону шардирования у нас есть печеньки!

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

Краткое содержание этой статьи:

1. Определение шардирования

2. А надо ли оно мне вообще?

3. Принципы шардирования

4. Шардирование по идентификатору
   

   1. Диапазоны

   2. Распределение по хеш-функции

   3. Карта распределения

   4. Перемешаем?

5. Решардинг (кратко)

Цикл:

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

2. Будет посвящена Шардировнию по гео-данным и детальному описанию решардинга.

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

Начнём с определения:

Шардирование, оно же сегментирование, оно же sharding – подход, при котором система разделяется на части (сегменты) для распределения между этими частями выполняемых задач (обычно хранения или кеширования). При этом сегменты одинаковы по форме, но различны по содержанию.

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

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

Шардирование не стоит путать ни с партиционированием, ни с репликацией.
Упрощённо Партиционирование – это разделение таблицы на несколько, но в рамках одного экземпляра субд.

Репликация – это копирование данных между экземплярами субд, которые в конечном счёте содержат один и тот же набор данных.

Из готовых решений, в которых из коробки уже реализовано шардирование, можно отметить:
MongoDB, Elasticsearch, ClickHouse, Greenplum, ScyllaDB, Cassandra
Так же есть надстройки над БД:
Citus для Postgresql и Vitess для MySQL

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

В этой серии статей мы не будем рассматривать описанные выше решения. Мы продумаем “как сделать своё” OLTP решение (решение ориентированное на оперативную обработку транзакций, а не на аналитическую обработку)! В общем, всё что уже готовое – “Not Invented Here”. А это значит, возможно, мы можем для себя придумать более интересное и эффективное решение ?

А надо ли оно мне вообще?

Отказ от зова

Прежде чем заниматься всякой ерундой типа шардинования нужно понять, а нужно ли оно мне. Архитектурное решение – всегда компромисс, поэтому часто нет однозначного ответа на вопрос “нужно ли шардирование?”.

Для себя я принял следующие правила для OLTP систем, при выполнении которых стоит задуматься о шардировании:

1. если системе не хватит для стабильной работы в ближайшие 5 лет машины 8CPU (2ГГц), 32Gb Ram и 200GB HDD.

2. Нужно сделать так, чтобы был мультимастер на запись.

3. Есть ли у нас ключевое разделение, например по странам.

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

Предположим, что мы решили, что на одной машине выполнять все задачи у нас не получится, или по ещё каким-либо причинам решили шардировать. Не торопимся, обратимся к DDD [книга с обезьяной], давайте в начале убедимся, что мы будем реализовывать один агрегат в терминологии DDD. Если мы реализовываем несколько агрегатов, то стоит в начале разделить систему на несколько систем, по одной на каждый агрегат, и потом снова оценить для каждой из получившихся систем “а нужно ли нам шардирование?”. Разгрузить систему можно “отправив в архив” часть данных, или сделав “охлаждение” каким-либо ещё способом, имеется ввиду, удалить старые и неактуальные данные из оперативных.

Мы всё же делаем один агрегат, разгрузили систему удалив ненужные данные, и мы точно не умещаемся на одну машину, и есть, возможно, ещё какие-то весомые аргументы, ну что, значит совершаем шаг в бездну и шардируем!

Принципы шардирования

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

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

Второе измерение: это выбор способа разбиения на сегменты.

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

1. по идентификатору

2. по географическому положению

3. для гарантированного сохранения

4. по времени

5. по особым признакам

Выбрать хороший принцип шардирования – целое испытание. Давайте рассмотрим, один из способов разбиения более подробно.

Шардирование по идентификатору

Предположим, у нас есть идентификатор у каждой записи, по которому мы хотим распределить записи между сегментами. Это может быть ИД записи, а может быть поле для группировки, например, ид пользователя для заказов.

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

Cупер-идентификатор – идентификатор для которого объём сильно отличается от медианы в большую сторону. Пример, пользователь с 1млн заказов, когда у обычного пользователя заказов 200-300. Что можно сделать с супер-идентификаторами разберёмся в разделе [Карта распределения по сегментам].

Распределение между сегментами обычно сводится к описанию правила, которое основано на:

1. диапазонах, и/или

2. распределению по остатку от деления или другой хеш-функции и/или

3. готовой карте распределения.

Диапазоны

Давайте рассмотрим случай, когда идентификаторы генерируются, равномерно и монотонно с увеличением, тогда мы можем сделать правило вида:

[1, 10^6] -> сегмент 0
[1+10^6, 2*10^6] -> сегмент 2
[1+210^6, 310^6] -> сегмент 3

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

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

Так же стоит следить за тем, чтобы всегда иметь в запасе следующий сегмент.

Вариант с диапазонами не подходит для случаев, когда генерация идентификаторов происходит случайно и не имеет диапазонов с равномерно и монотонно с увеличивающимся идентификатором. Например, если мы сделаем сегментированное хранение для UUID версии 4 (случайная генерация [habr uuid]) на основе диапазонов, то при добавлении сегментов, нам придётся переопределить диапазоны, а значит сделать решардинг, и мы теряем главный плюс подхода.

Распределение по хеш-функции

Давайте свернём наш идентификатор в небольшое число в каком-то диапазоне, назовём эти значения – виртуальные сегменты. И теперь из этого диапазона каждому числу (виртуальному сегменту) присвоим “реальный” сегмент. На самом простом уровне можно использовать остаток от деления идентификатора. Главный плюс подхода, равномерное использование ресурсов сегментов.

Виртуальный сегмент – значение которым описывается положение идентификатора в системе. Для виртуальных сегментов определена карта, которая для каждого виртуального сегмента определяет “реальный” сегмент. Реальным сегментом назовём сегменты шардирования определённые в начале статьи, но для простоты можно считать отдельное хранилище “реальным” сегментом

Немного о подводных камнях:

1. Плохо подобранная хеш-функция может привести к плохому распределению нагрузки между сегментами. Если идентификаторы генерируются с шагом, например, 10 и остаток от деления у нас 5, то все записи попадут в один сегмент.

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

Давайте попробуем подстелить немного соломки под обе проблемы, описанные выше.

Первая проблема решается тем, что мы берём хеш-функцию несколько более сложную чем остаток от деления. Выбираемая хеш-функция должна равномерно распределять идентификаторы на выбранный диапазон. Как хороший и рабочий в 99% случаев вариант можно использовать семейство функций xxHash [habr xxHash] и основываться на них свои производные хеш-функции.

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

Например, у нас было 3 сегмента, и мы хотим добавить ещё один. Тогда получается, что из каждого сегмента нам нужно выделить по четверти на новый сегмент. Если наша хеш-функция принимала значения от 0 до 11 и диапазоны были {0:[0-3];1:[4-7];2:[8-11]}, то решардинг по схеме {0:[0-2];1:[4-6];2:[8-10];3:[3,7,11]} приведёт к минимальному переносу данных. Из примера видно, что нужно будет где-то хранить карту отображения виртуальных сегментов на “реальные” сегменты.

“Фарш невозможно провернуть назад”, при радикальной смене хеш-функции глобальный решардинг неизбежен.

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

Другой вариант заключается в том, чтобы делать сегменты разными или смириться с неравномерной нагрузкой.

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

А ещё бывают исключения, например люди – которые заказывают в 100 раз больше, чем обычные или популярные новостные каналы, или очень крупные поставщики с x100 товаров.

Карта распределения по сегментам

“А давайте для вот этих наших крутых партнёров выделим отдельный сервер, чтобы у них всё летало, и они на остальных не влияли.” Эта мысль легко решается добавлением карты распределения идентификаторов. Можно каждому идентификатору определить сегмент. Если записей немного, например 10 миллионов, то такая карта прекрасно хранится в оперативной памяти и добавление в неё строк стоит очень обычно очень дёшево. Зато такой подход позволяет выделить исключения и распределить их “по-особому”.

Пример карты: {213:0,12321:0,456:1,67:7,99:2,374:super,987:2,…}, то есть каждому идентификатору ставим в соответствие сегмент.

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

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

Смешаем ежа с ужом

Достаточно часто можно смешать концепции что бы получить более гибкий и экономически выгодный результат.

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

Переусложнение как и переупрощение это крайности, которые приводят к проблемам в будущем. Для себя я решаю вопрос с переусложнением так:

1. опрашиваю других людей

2. откладываю спроектированное решение на пару дней, а затем перепроектирую не заглядывая в готовое решение

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

А с переупрощением, задавая вопросы “а что если?”.

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

Решардинг

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

Ниже приведу краткий обзор способов.

Попроще

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

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

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

Посложнее

Если не получается пойти по простому пути, то идём по одному из сложных.

Можно, тормознуть сервис, перенести данные и запустить. Будет простой в работе, но зато реализовать этот способ достаточно просто.

Более деликатным способом будет останавливать обслуживание по виртуальным сегментам. Фактически блокируется работа виртуального сегмента, данные виртуального сегмента переносятся и потом обслуживание виртуального сегмента возобновляется. Для этого способа требуется оркестрация переноса, и требуется разработать систему блокировок по “виртуальным сегментам”.

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

Если всё же требуется сделать решардинг, то система должна выглядеть так:

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

Более подробно и с примерами расскажу в следующей статье. Вместе с темой логики на маршрутизаторе.

Заключение

Спасибо за то, что прочитали до конца.

Следующая тема

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

Литература

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

1. (Книжка с обезьяной) Изучаем DDD – предметно-ориентированное программирование; Влад Хононов

2. (Подготовка к собесу) System Design. Подготовка к сложному интервью; Сюй Алекс

3. (Книжка с дятлом) Современный подход к программной архитектуре: сложные компромиссы; Нил Форд, Марк Ричардс, Прамод Садаладж, Жамак Дехгани

4. https://highscalability.com/consistent-hashing-algorithm/

5. (habr uuid) https://habr.com/ru/companies/vk/articles/522094/

6. (xxHash https://habr.com/ru/companies/globalsign/articles/444144/)

Благодарности

Денис К., Аня С., Юля Т., Сергей Р. и Филипп Б., спасибо, что прочитали и проревьюили мои прошлые версии этой статьи! Вы супер!