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

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


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


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

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

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

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


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

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


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



    UUID

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

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

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

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

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

    auto_increment_increment и auto_increment_offset

    Эти опции конфигурации 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. добавляем запись еще раз.

    Как побочный эффект, возможны лишние записи в предыдущем шарде, которые можно потом подчистить.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 34

      0
      Минус этого подхода – нет гибкости c алгоритмом распределения и с увеличением количества шардов, если не запастись заранее увеличенным auto_increment_increment.

      А что если заложить максимальное число шардов, а до их появления использовать ближайшие?
        0
        Если заложить на будущее, то вполне нормально можно избежать необходимости перераспределять данные. Я как раз написал, что можно запастись увеличенным auto_increment_increment, который отражает максимальное кол-во шардов, и будет больше чем кол-во действующих шардов с запасом на добавление новых.
        Кстати, забыл указать, что оба эти параметра могут принимать значения от 1 до 65535 — такого количества шардов хватит почти всем :)
        +1
        Интересно, но я иначе подхожу к вопросу шардинга.

        В зависимости от характера приложения, использовал два способа:

        1) поддерживать список диапазонов вида [ shard_pivot_id_min — shard_pivot_id_max ) -> shard_id. Разумеется, нужен быстрый и отказоустойчивый способ получить id по диапазону. Прекрасно работает решение «в лоб» — раскидывать этот список на каждый узел с приложением как элемент его конфигурации, прямо в процессе деплоя этой самой конфигурации. Недостаток в том, что список надо поддерживать руками, или иметь какой-то алгоритм, который из неких соображений будет эти диапазоны добавлять автоматически.

        2) «Динамический» шардинг. Условия: новые сущности, по которым делается шардинг, появляются относительно редко; сами шарды довольно большие, но неравнозначны по вычислительной мощности.
        Тут много, так что под спойлером.
        Поддерживается таблица вот такого вида:

        CREATE TABLE `DatabaseShards` (
          `database_shard_id` int(10) unsigned NOT NULL AUTO_INCREMENT, -- номер шарды, автоинкремент
          `database_server_id` int(10) unsigned NOT NULL, -- номер сервера
          `database_idx` tinyint(3) unsigned NOT NULL, -- номер базы в диапазоне 1 .. server.databases_count (см. ниже)
          `units_used` int(10) unsigned NOT NULL DEFAULT '0', -- число сущностей, размещенных на шарде
          `units_free` int(10) unsigned NOT NULL, -- сколько еще можно сущностей разместить на шарде
          `is_available` tinyint(1) NOT NULL DEFAULT '1', -- если 0, то на этой шарде нельзя больше ничего размешать
           -- .. опустим несущественное ..
          PRIMARY KEY (`database_shard_id`),
          KEY `idx_database_server_id` (`database_server_id`),
          KEY `idx_units_free_database_server_id` (`units_free`,`database_server_id`),
          CONSTRAINT `DatabaseShards_ibfk_1` FOREIGN KEY (`database_server_id`) REFERENCES `DatabaseServers` (`database_server_id`)
        )
        CREATE TABLE `DatabaseServers` (
          `database_server_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
           -- .. опустим несущественное ..
          `capacity` int(10) unsigned NOT NULL DEFAULT '100', -- "мощность" сервера. В попугаях.
          `units_per_shard` int(10) unsigned NOT NULL DEFAULT '1000', -- сколько сущностей размещается на одной шарде сервера
          `databases_count` tinyint(3) unsigned NOT NULL DEFAULT '10', -- сколько баз данных создается на сервере
          `is_available` tinyint(1) NOT NULL DEFAULT '1',
          PRIMARY KEY (`database_server_id`)
        )
        


        Под шардой тут понимается набор (server_id, database_id, shard_id), где server_id — ID севера, database_id — суффикс базы данных, shard_id — номер шарды, он же суффикс таблиц.

        Логика аллокации шарда для нового юнита:

        1. Пытаемся найти наименее занятую шарду:
        1.1. SELECT database_shard_id FROM DatabaseShards WHERE is_available = TRUE AND units_free > 0 ORDER BY units_free DESC LIMIT 1
        1.2. Если результат не нулевой, инкрементим units_allocated, декрементим units_free, используем эту шарду — закончили.
        1.3 Иначе, все занято
        2. Если все занято, нужна новая:
        2.1. находим наименее занятый доступный (WHERE is_available) сервер — ORDER BY COUNT(DatabaseShards.database_shard_id) / DatabaseServers.capacity LIMIT 1
        2.2. если таковых нет — exception (это произойдет, только если все сервера is_available = false)
        2.3. находим на этом сервере наименее занятый номер базы в диапазоне 1… server.databases_count. Тут ввиду отсутствия аналога generate_series в mysql немного жесть, не буду приводить этот адский запрос :) Если база с нужным именем еще не создана, создаем.
        2.4. добавляем в DatabaseShards запись с данными (server_id, database_idx), в units_free пишем server.units_per_shard, из LAST_INSERT_ID получаем номер шарды. Ее и используем.

        Информацию о карте шард можно хранить в специализированном key-value-сервисе. Мне на практике хватило handlersocket-а и стандартной mysql-репликации для отказоустойчивости.
          0
          Извините, не понял во втором примере как и кем генерируется ID сущности и как повторно по ID вычисляется с какого шарда его брать?
            0
            Упс, забыл про это сказать. Обычный автоинкремент, карта id сущности — id шарды хранится рядом, в еще одной табличке, запрашивается через handlersocket.
          0
          «Гибкость в балансировке нагрузки. Если один шард производительнее, ему можно дать больший диапазон.»
          «фактически разбить один диапазон на 2-3 новых диапазона, таким образом перераспределив нагрузку.»

          Это предполагается без перераспределения данных между шардами?
            0
            «Гибкость в балансировке нагрузки. Если один шард производительнее, ему можно дать больший диапазон.»
            Я имел ввиду, что до ввода в эксплуатацию шарду можно выделить подходящий по размеру диапазон исходя из каких-то замеров производительности (ну или «на глазок»). Т.е. данных на шарде пока нет, и переносить нечего.

            «фактически разбить один диапазон на 2-3 новых диапазона, таким образом перераспределив нагрузку.»
            А тут уже речь идет о перерасределении нагрузки, если на шард оказалось возложено слишком много или шарду не повезло, и на него попали очень популярные данные, количество обращений к которым гораздо больше среднего. В этом случае, конечно, данные выделенного диапазона нужно будет переносить.
            0
            Как показала лично моя практика, шардить проще по другому ключу, а не по ID. Банально SHARD_ID в какой-либо «главной сущности». И шардить только большие таблицы (маленькие подсасывать на все шарды круговой репликацией).
            В этом случае с автоинкрементами все решается auto_increment_increment и auto_increment_offset, при добавлении новых шардов инкремент увеличивается.

            Минус: auto_increment_increment и auto_increment_offset параметры сервера, так что если вы решили расшардить одну большую табличку на две в рамках одного сервера, то этот способ очевидно не подходит.

            Перераспределение данных тривиально: mysqldump -h localhost db <таблицa> --where «uc_account=123» > mysql -h SH2 db
            (на SH2 должен быть сессионной переменной отключен бинлог, аналогично при удалении с localhost)

              0
              Перераспределение данных тривиально: mysqldump -h localhost db <таблицa> --where «uc_account=123» > mysql -h SH2 db

              хм… с моими размерами неделю будешь дамп делать :)
              0
              Есть ещё специфический вариант с полной картой. Нужны два списка: список шардов и карта ID элемента -> ID шарда. При создании новой сущности, шард выбирается по любым удобным правилам (случайно, раунд-робином или по весам — it's up to you). В карту пишется какому шарду принадлежит сущность.

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

              Минусы очевидны:
              — размер карты равен количеству сущностей
              — на каждое чтение сущности нужно прочитать запись из карты

              Если хранилище карты быстрое, минусы нивелируются.
              0
              Самое главное забыл: отличная статься, можно ей маркер «Tutorial» поставить даже
                0
                Подскажите, а как на практике использовать шардинг? Например, есть приложение которое хранит большие объемы данных о пользователях. С высокой частотой появляются (регистрируются) новые пользователи. Приложение должно в цикле обращаться ко всем серверам по очереди, что бы определит диапазон и ID последнего зарегистрированного пользователя и на основании вернувшихся данных принимать решение на этот или другой сервер выполнять запрос insert?
                  0
                  хранение UID должно быть сквозное, либо в key/value либо в какой-то центральной БД
                  0
                  Вышеописанные случае хороши, с вышеописанными проблемами.

                  У меня архитектура шардинга следующая:
                  — каждый шард ( в моем случае это БД, которых может быть несколько на одном инстансе MySQL) имеет некий вес, пропорционально которому распределены uid
                  — генерим случайный номер шарды в соответствии с заданным распределением
                  — запоминаем в key/value хранилище, какому uid соответсвует какая шарда.

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

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

                  Далее хранение сообщений. Здесь работает принцип автоинкрементных таблиц, т.е. таблица должна быть не более 10M записей (у кого-то это 100K), messages_0… messages_M
                  Если uid записи в пределах 0-10М., то это таблица messages_0, 10М-20М — таблица 1. и т.д.
                  Как только подходим к порогу (M+1) * 10M — Lim — то генерим новую таблицу. Как правило — константа Lim = 20-30 cообщений, т.е. где-то за сек до инкрементации числа M (номер таблицы в данной шарде)

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

                    SELECT AUTO_INCREMENT FROM INFORMATION_SCHEMA.TABLES WHERE TABLE_NAME='message_%d' AND TABLE_SCHEMA='%s'"
                      0
                      Я слышал, что в таблице не желательно более 10-12 полей, а какое допустимое количество строк можно хранить в одной таблице?
                        0
                        Мы хранимм 10М строк и скорость доступа нас вполне устраивает. В старой системе у нас были триллионы записей и система так же работала.

                        например в Баду и Топфейсе считают цифру 100К
                          0
                          Откуда инфа? :)

                          Всё сильно зависит от строк, имхо. Если в строке два инта — можно сильно не ограничиваться.
                            0
                            инфа из первых уст разработчиков, или есть другие источники?
                            0
                            А над каки проектом работаете, если не секрет?
                          0
                          Еще такой вопрос, допустим, в приложение работает с личными сообщениями и профилями пользователей. В очередной раз отправленное сообщение нужно сохранить в таблице messages. Приложение видит, что на данном сервере в этой таблице уже 10 миллионов записей и по хорошему нужно выполнить запрос к серверу N. Допусти, у меня есть файл в котором массив ip серверов. Берем следующий сервер и выполняем необходимые операции. Правильно я рассуждаю? А как потом при просмотре истории сообщений приложение будет искать сообщения этого пользователя? Делать запросы ко всем серверам?
                            0
                            Немного не так… раз мы определили, что сообщения хранятся на шарде N, то все сообщения и лежат на этой вот шарде. Только мы в данной БД наращиваем кол-во таблиц приблизительно одинаковой размерности.

                            Тут наверно необходимо рассказать подробнее про структуру хранения. У нас введено понятие диалога и диалоги двух лиц лежат на одной шарде. А в случае, как описано выше, нужно сообщения хранить дважду, один экземпляр на шарде одного и второй на шарде второго пользователя
                              0
                              Т.е. у нас база данных одна и на всех серверах называется одинаково, так? И задача создавать новые таблицы по определенному шаблону и начинать инкримент с последнего в предыдущей таблице на предыдущем сервере?
                                0
                                нет… есть конфиг:
                                сервер 1, на нем расположены три базы…
                                BD_1 10
                                BD_2 10
                                BD_3 10

                                сервер 2
                                BD_4 15
                                BD_5 15

                                сервер 3
                                BD_6 10
                                BD_7 10
                                BD_8 10

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

                                Второе. на каждой шарде свой индивидуальный инкремент.
                                Как упоминалось в статье и я упоминал в комментариях возможно решение со сквозным UID по всем шардам. Но мы такое не практикуем.
                                0
                                А если хранить абсолютно все записи пользователей от 1 до 10000 на первом сервере, 10001 — 20000 на втором сервере и так далее. Т.е. Все сообщения, профили, ссылки на фотографии в профиле?
                                  0
                                  тоже так можно,
                                  почти так сделано в Топфейс
                                    0
                                    Тут есть разные подходы. Например, если в Мамба или Баду все данные одного пользователя хранятся на одной шарде, т.е. физически на одном сервере, то у нас исторически сложился немного иной подход, распределение по функциональному назначению: профиля хранятся на группе серверов Профиля, фотоальбомы в группе серверов Фотоальбомы, сообщения… и т.д. распределение между серверами, кроме системы сообщений, чисто классическое: остаток от деления UID на кол-во серверов.
                                    В системе сообщений, ранее была такая же система, пока мы не столкнулись с проблемой переполнения БД. Пришлось заняться перепроектированием.
                                  0
                                  номер шарды сообщения хранится в таблице контактов, и там же хранится номера таблиц…
                                  т.е мы имеем информацию в каких таблицах содержится диалог только в одной записи (можно сделать в нескольких, это же RDBM)
                                  0
                                  а вот таблица создается с проддолжением старого автоинкремента
                                  CREATE TABLE IF NOT EXISTS %s.`messages_%d` (
                                  		`id` int(20) unsigned NOT NULL AUTO_INCREMENT,
                                  		... 
                                  		`data` varchar(1024) DEFAULT NULL,
                                  		PRIMARY KEY (`id`) ) ENGINE=InnoDB AUTO_INCREMENT=%d
                                  
                                    0
                                    некоторым неудобством является отслеживанием в скрипте соединений, которые хранятся в массиве. По конфмгу выбираем по номеру шарды -> номер сервера, на котором находится данная шарда

                                    преимущество — мы можем очень оперативно двигать такие шардя с одного физического сервера на другой
                                      0
                                      Вопрос по поводу запроса, я обычно устанавливаю полям типа varchar длину 255, а int (11). Как лучше делать?
                                        0
                                        В книге П.Зайцева «Оптимизация производительности Мускуля» даны рекомендации:
                                        если в ваших данных иди (id > 0) заведомо в пределах
                                        256 то используйте TINYINT,
                                        в пределах 64K — SMALLINT
                                        в пределах 16М — MEDIUMINT
                                        в пределах 2G — INT
                                        иначе BIGINT
                                        это экономит место, память под индекс и соответственно время на поиск.
                                        естественно, по инту ищет быстрее.
                                        в общем очень рекомендую эту книгу.

                                    0
                                    Интересный пост в блоге инстаграма на эту тему для постгреса:
                                    instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram

                                    Only users with full accounts can post comments. Log in, please.