Как стать автором
Обновить

Комментарии 35

переходите на автошардинговые базы и не парьтесь

Что порекомендуете по сопоставимой цене и надёжности?

неужели для пг не изобрели аналог vitess?

Изобрели, называется CitusDB. Но нам это решение, увы, не подошло.

Почему?

Что касается гибридных решений для Postgres — большинство из них основаны на технологии PG FDW. FDW (foreign data wrapper) — это функциональность сервера Postgres, которая позволяет ему рассматривать данные на удаленном сервере как часть большего набора и интерпретировать этот разделенный на несколько серверов набор данных как единое целое. У этой технологии есть свои проблемы, но самая большая из них — доступ к данным через FDW чрезвычайно медленный.

Это выдержка из статьи.

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

А у вас список требований больше, чем у такого готового решения?

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

А в итоге решение выкладывали в опен-сорс? Если да, поделитесь ссылкой?

Пока не выкладывали, но если выложим - обязательно расскажем об этом.

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

Не "бесконечно" мала, а "неприемлемо" мала — в общем случае NOD(N,M)/M где N — сколько было шардов, M — сколько стало, и 0 если стало меньше шардов, а исходная строка на удаляемом шарде.


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

Кстати, раз вы написали, что используете range tree для поиска интервала, куда попадает номер бакета, ещё одной оптимизацией может быть назначение одному из серверов хэша 0xffff (раз у вас 65536 бакетов), чтобы избежать отдельной обработки перехода диапазона через 0.

Спасибо за уточнение и совет, отразим этот момент в статье.

Каждое решение имеет свои ограничения, и наше — не исключение.

  • Мы не поддерживаем автоматический решардинг (пока).

  • Мы не поддерживаем multi-shard операции JOIN.

  • Мы не поддерживаем распределенные транзакции.

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

Считаем offset = CalculateHash(shard_key) % BucketNumber. По этому номеру получаем ConnectionString из конфига (не нужно для этого держать отдельную мастер базу и иметь доп.риски отказа), по ConnectionString идём в нужную БД. BucketNumber определяется как константа один раз. А вот количество серверов может быть разным. Перенос отдельной базы на новый сервер это более простая задача, после которой всё что надо будет сделать это поменять соответствующий ConnectionString.

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

  1. Я правильно понимаю, что поиск товаров/заказов сломался из-за шардирования, запрос уходит не на тот шард?

  2. Можно вместе с ключом шардирования хранить вносить версию кольца с серверами? И при изменении конфигурации просто делать новую версию кольца?

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

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

Спасибо за статью!

А какого формата данные раскиданы по шардам? Одна табличка? Или разные? И знаете на уровне приложения что сейчас надо идти в такую-то табличку, которая на таких-то шардах?

Всегда пожалуйста! Рад, что понравилось и (или) было полезно!

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

То есть, само приложение понимает к каким данным обратились. И знает где эти данные лежат(на каком шарде)?

То есть, работает без прослойки/proxy/routing'а?

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

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

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

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

То есть клиентское приложение сделало запрос. Вычислился shard key. Обратились к БД конфигурации/master node. Она посмотрела в какой диапазон этот key попадает.

Суть такая что за каждый диапазон key отвечает какой-то один сервер, на котором данные под данный key.

И master node выдала connection string этого сервера.

Далее клиентское приложение создаёт подключение по такому connection string. И выполняет запрос.

Правильно?

Два нюанса.

Первый. Мы не ходим в master на каждый запрос конфигурации кластера, а храним ее в in-memory кэше.

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

В остальном вы все абсолютно верно поняли.

Спасибо за ответ!

Про коннекты. Мы сейчас находимся в нашем обсуждение на мобильном устройстве, в приложение ali. У него есть коннекты к различным шардам. Вы это имеете ввиду?

Что зашли в местный кэш(который, кстати, обновляется по push модели? К нему приходит push уведомление от сервера конфигурации?), получили connection string, посмотрели в некий местный хэш: "по данному connection string уже есть connection" и пользуемся им? Верно понял?

Нет, мы сейчас в обсуждении находимся на ноде k8s, в каком-нибудь поде с нашим back-end сервисом. Мобильное приложение оперирует back-end сервисами, выставляющими для него свои API.

Так вот, мы в back-end сервисе. К нему прилетает запрос. Мы понимаем, что этот запрос нужно обслужить, сходив в шардированную базу.

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

Далее мы идем в еще один in-memory cache и смотрим, есть ли у нас свободный коннект с такими же параметрами подключения. Если да - берем его. Если нет - создаем новое подключение, которое мы, по завершении работы с ним, положим в этот самый in-memory cache.

Спасибо, понятно!

  1. Load balancer балансирует нагрузку между подами k8s?

  1. У каждого back-end сервиса свой пул(in-memory cache сервиса) уже созданных соединений к различным шардам?

  2. Выше писали "само приложение знает конфигурацию шардов". Зачем ему тогда знать, если этим знанием обладает back-end сервис? Который и роутит запрос в нужный шард. Тогда приложение умеет лишь слать запрос back-end сервису. Или я что-то не так понял?

  1. Да, стандарнтый k8s load balancer.

  2. Да.

  3. "Приложение" в этом контексте - это back-end сервис, а не мобильное приложение. Мобильное приложение вообще в базы напрямую не ходит, только в back-end сервисы.

Класс! Спасибо!
По поводу балансировки. Какой алгоритм используете?

К примеру, окажется так, что у вас 10 back-end сервисов("приложений" как Вы называете). Пришло 100 запросов. Каждый 10ый тяжелый. И у вас round-robin. Тогда все эти 10ый запросы на 10ом сервисе. Его грузит.

Данному решению неважно, какой load balancing алгоритм используется в кластере, куда задеплоен сервис, оно находится уровнем ниже - на data access level. Потому я про load balancing на уровне k8s в этой статье и не писал.

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

"Сначала мы вычисляем значение хэш-функции для переданного значения шард-ключа и вычисляем индекс бакета, разделив его по модулю на наше фиксированное количество виртуальных бакетов, равное 65536"
1. Пришли такие-то данные.
2. У них взяли поле, которое для этого типа данных является shardKey.
3. Вычислили hash(shardkey) % 65536.
4. Получили номер "виртуального бакета".
5. Теперь нужно понять, какой сервер отвечает за данный бакет.
6. Сходили в БД конфигуации == master node:
a) Дали этот номер == $Offset
(где bucket_index_start == 0, bucket_index_end == 65536 ?)
б) Получили адрес сервера

Верно?

  1. Пришел запрос, который нужно боработать, сходив в базу за данными. Например возьмем простой select из базы

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

  3. Вычислили hash(shardkey) % 65536, это значение и есть номер бакета, где лежат данные для данного shardKey - bucket_index.

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

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

    1. Если убрать интервальное дерево из рассмотрения, то на базе это будет (в псевдо-SQL) выглядеть как SELECT * FROM shards where bucket_index_start <= bucket_index <= bucket_index_end LIMIT 1

  6. Из узла взяли connection string к серверу

Классно, спасибо!

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

Почему сложен? Мне кажется, что вы как-раз его и реализовали.

Взяли круг из 65536 значений. Каждые данные попадают в какое-то значение. За интервал значений отвечает какой-нибудь сервер. Сервер отвечает даже за несколько интервалов. Чтобы распределить нагрузку более равномерно по серверам.

Это же и есть consistent hashing с виртуальными серверами?

У нас нет прохода по кольцу далее, если не найден сервер, отвечающий за диапазон.

А что у вас?

Как мне кажется, в consistent hashing теже интервалы, за которые отвечает сервер.

И у вас в таблице у master'а строка с сервером и интервал, за который он отвечает.

Пока всё тоже самое, на мой взгляд. Что я упускаю?

Как минимум, есть 1 сервер. В этом случае он отвечает за весь интервал:

min - 1

max - 65k

Понятно!

в зависимости от запроса может быть либо явным полем, либо вычисляемым

Можно пару живых примеров? Чтобы почувствовать лучше реальную реализацию.

Для иллюстрации разницы хватит вот такого тела запроса.

{
    "group_id" : 123,
    "group_name" : "foo",
    "sub_group_id" : 42
} 

В случае, когда shard key - явное поле, берем, group_id и его прогоняем через хэширование.

Когда shard key - вычисляемое поле, например, складываем group_id и sub_group_id и прогоняем через хэширование сумму.

Или, например, делаем запрос куда-то еще, чтобы получить по sub_group_id shard key для этого запроса.

Описанное решение совершенно никак не ограничивает, откуда берется shard key. Его может вообще в запросе не быть.

Спасибо!

То есть:

1) Сервис понимает тип запроса;

2) В зависимости от типа запроса реализует логику

if(request_type1) {
  Для получения shard_key взять из запроса значение определенного поля
} else if(request_type2) {
  Для получения shard_key взять из запроса значение определенные поля.
  Произвести над ними арифметическую операцию.
} else if(request_type3) {
  Для получения shard_key cходить в сторонний сервис
} else ... {
  Для получения shard_key реализовать комбинации перечисленных выше действий
}

?

Зарегистрируйтесь на Хабре, чтобы оставить комментарий