Генерация ID для шардинга в MySQL

Тема шардинга довольно обширная как с точки зрения программиста, так и с точки зрения администратора БД. Я сейчас хочу коснуться только вопросов генерации уникального ID сущности и алгоритмов выбора шарда.

Алгоритмы выбора шарда

Давайте сначала про алгоритмы, чтобы потом при описании способов генерации ID можно было ссылаться сюда.

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

Разбиение по диапазонам

Алгоритм состоит в том, чтоб разбить множество ID на непрерывные подмножества — диапазоны. Каждому из диапазонов соответствует один шард. Например, с 1 по 1000 — первый шард, с 1001 — 3000 на второй шард и т.д. Имея ID, достаточно не сложно понять в какой диапазон он входит и к какому шарду обращаться.
ID не обязательно должен быть целочисленным, но множество ID должно быть упорядоченным, то есть, если взять два ID, то можно сказать какой из них больше, какой меньше или что они равны. Но почти всегда это условие выполняется.
Плюсы этого алгоритма:

• Постепенное наращивание количества шардов. То есть вам не нужно иметь сразу много шардов, их можно подключать по необходимости, что удобно для начинающих проектов.
• Гибкость в балансировке нагрузки. Если один шард производительнее, ему можно дать больший диапазон.
• Решение проблем с перераспределением нагрузки. Например, если пользователь, хранящийся на одном из шардов, становится слишком активный, так что создает большую нагрузку, то можно выделить новый диапазон включая его ID, на отдельный шард. Т.е. фактически разбить один диапазон на три, таким образом перераспределив нагрузку.

Минусы:

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

Остаток от деления по модулю

Разумеется, обязательное условие — с ID должна быть возможна операция деления по модулю. Изначально определяется необходимое количество шардов, может с запасом. Номер шарда вычисляется по остатку от деления ID на количество шардов.
Интересно, что если ID является строкой, а шард выбирается по его подстроке, тем не менее это фактически является этим же алгоритмом. Например, ID — шестнадцатеричная запись хеша md5, а для выбора шарда используются первые 2 шестнадцатеричных цифры — это все равно деление по модулю. Можно считать, что используются другие цифры и/или порядок старшинства разрядов в числе.
Также стоит заметить, что для использования такой вариации алгоритма выбора шарда по подстроке надо быть уверенным в равномерном распределении символов подстрок, иначе нагрузка на шарды будет не равномерной. Например можно с уверенностью утверждать, что этому условию удовлетворяет шестнадцатеричная запись md5, а вот UUID совсем не гарантирует равномерности в подстроках.
Плюсы:

• Равномерное распределение новых пользователей по шардам. Нагрузка растет постепенно.
• Простое и быстрое вычисление номера шарда — одно арифметическое действие.

Минусы:

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

Способы генерации ID

UUID

Самое простое решение «в лоб» — генерировать уникальный ID, с вероятностью коллизии настолько малой, что вероятнее глюкнет автоинкремент у MySQL и выдаст уже использованное значение. Этим и занимается стандарт UUID ^[1].
MySQL сам умеет генерировать UUID() ^[2]. Для PHP есть библиотека ^[3].
Минус этого подхода – избыточная длина поля, особенно учитывая, что оно может использоваться для внешнего ключа. Хотя MySQL позволяет немного сократить с 36 до 16 байт, сделав его совсем не человекочитаемым:

SELECT UNHEX(REPLACE(UUID(), '-', '')); #Надо аккуратно выбирать charset для такого поля и аккуратно сравнивать

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

Мастер-таблица с автоинкрементом

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

auto_increment_increment и auto_increment_offset

Эти опции конфигурации ^[4] MySQL позволяют задать шаг приращения автоинкремента и первоначальное смещение.
Это можно использовать, чтобы каждый шард генерировал свой уникальный ID в сквозной нумерации. Достаточно установить аuto_increment_increment равным количеству шардов, а в auto_increment_offset записать номер шарда.
Алгоритм выбора шарда для добавления для не зависит от ID, а потому может быть любым, например, случайным или как пророчат духи балансировки. Обратное преобразование можно сделать делением ID по модулю auto_increment_increment.
Минус этого подхода – нет гибкости c алгоритмом распределения и с увеличением количества шардов, если не запастись заранее увеличенным auto_increment_increment. Зато в отличие от предыдущего способа, если один из шардов “упал”, он просто не будет выдавать ID из своей последовательности, нет зависимости от главной БД, что повышает отказоустойчивость.

Имитация Sequence

Этот метод позволяет избавиться от вертикального разбиения таблицы, как в методе с мастер-таблицей. У MySQL нет механизма генераций последовательностей, за исключением автоинкремента, который не совсем то, что надо.
Но Sequence можно имитировать примерно так:

CREATE TABLE IF NOT EXISTS `sequence` (
  `id` int(11) NOT NULL DEFAULT '0'
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO `sequence` SET `id` = 0;

Далее можно получать следующий ID из нужной последовательности:

UPDATE `sequence` SET `id` = last_insert_id(`id` + 1);
SELECT last_insert_id();

В таблице sequence можно держать несколько полей для нескольких последовательностей. А единицу в выражении last_insert_id(`id` + 1) можно заменить на другое число, реализуя auto_increment_increment.
Алгоритмы выбора шарда аналогичны используемым в методе с мастер-таблицей.

Динамический переход между шардами

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

1. вставляем запись,
2. получаем last_insert_id(),
3. если за границей диапазона, переключаемся на новый шард, который записываем в общую память как текущий,
4. на новом шарде создаем таблицу (и да поможет IF NOT EXISTS)
5. добавляем запись еще раз.

Как побочный эффект, возможны лишние записи в предыдущем шарде, которые можно потом подчистить.

Автор: maximw

Источник ^[5]