Сводка по схемам распределенной идентификации

Java задняя часть

Идентификатор является уникальным идентификатором данных.Традиционный метод заключается в использовании UUID и самоувеличивающегося идентификатора базы данных.В интернет-компаниях большинство компаний используют Mysql, и, поскольку требуется поддержка транзакций, механизм хранения Innodb обычно UUID слишком длинный и неупорядоченный, поэтому не подходит для использования в качестве первичного ключа в Innodb.Более подходит самоинкрементный ID, но с развитием бизнеса компании объем данных будет становиться больше и больше, и данные должны быть разделены на таблицы. , данные в каждой таблице будут автоматически увеличиваться в своем собственном темпе, и, вероятно, возникнут конфликты идентификаторов. В настоящее время необходим отдельный механизм, отвечающий за создание уникальных идентификаторов.Сгенерированные идентификаторы также можно назвать распределенными идентификаторами или глобальными идентификаторами. Проанализируем механизмы генерации распределенных идентификаторов.

在这里插入图片描述

Я сам это понимаю, прокомментируйте и посоветуйте, если нет, будьте милосердны. В этой статье не будем особо подробно разбирать, в основном подведем некоторые итоги, а затем опубликуем некоторые статьи подробно по определенной схеме.

Кроме того, я собрал коллекцию вопросов для интервью за 20 лет, в том числе краткое изложение Spring, Concurrency, базы данных, Redis, Distributed, Dubbo, JVM и микросервисов.Документация Тенсент

1. Идентификатор автоинкремента базы данных

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

Структура таблицы следующая:

CREATE DATABASE `SEQID`;

CREATE TABLE SEQID.SEQUENCE_ID (
	id bigint(20) unsigned NOT NULL auto_increment, 
	stub char(10) NOT NULL default '',
	PRIMARY KEY (id),
	UNIQUE KEY stub (stub)
) ENGINE=MyISAM;

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

begin;
replace into SEQUENCE_ID (stub) VALUES ('anyword');
select last_insert_id();
commit;

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

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

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

2. Режим базы данных с несколькими мастерами

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

Первая конфигурация экземпляра Mysql:

set @@auto_increment_offset = 1;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

Конфигурация второго экземпляра Mysql:

set @@auto_increment_offset = 2;     -- 起始值
set @@auto_increment_increment = 2;  -- 步长

После приведенной выше конфигурации последовательности идентификаторов, сгенерированные двумя экземплярами Mysql, выглядят следующим образом: mysql1, начальное значение равно 1, размер шага равен 2, а последовательность, сгенерированная идентификатором: 1, 3, 5, 7, 9, ... mysql2, начальное значение равно 2, размер шага равен 2, а последовательность, сгенерированная идентификатором: 2, 4, 6, 8, 10, ...

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

После реализации этого решения, даже если один из экземпляров Mysql перейдет в автономный режим, это не повлияет на DistributIdService.DistributionIdService все еще может использовать другой Mysql для генерации идентификаторов.

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

Теперь, если вы хотите добавить экземпляр mysql3, как это сделать? Во-первых, размер шага mysql1 и mysql2 должен быть изменен на 3, и его можно изменить только вручную, что требует времени. Во-вторых, поскольку mysql1 и mysql2 постоянно увеличиваются, мы можем увеличить начальное значение mysql3, чтобы дать достаточно времени для изменения размера шага mysql1 и mysql2. В-третьих, очень вероятно, что при изменении размера шага появятся повторяющиеся идентификаторы, для решения этой проблемы может потребоваться остановка операции. Для решения вышеуказанных проблем и дальнейшего повышения производительности DistributIdService, если используется третий механизм генерации распределенных идентификаторов.

3. Режим сегмента номера

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

Например, каждый раз, когда DistributIdService получает идентификатор из базы данных, он получает числовой сегмент, например (1,1000), этот диапазон представляет 1000 идентификаторов. Когда бизнес-приложение запрашивает у DistributIdService предоставление идентификаторов, DistributIdService требуется только локально увеличить 1. И вернуться, не запрашивая каждый раз БД, до локального автоинкремента до 1000, то есть, когда текущий сегмент номера будет израсходован, снова обратиться в БД для получения следующего сегмента номера.

Поэтому нам необходимо внести изменения в таблицу базы данных следующим образом:

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  current_max_id bigint(20) NOT NULL COMMENT '当前最大id',
  increment_step int(10) NOT NULL COMMENT '号段的长度',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

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

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

Чтобы улучшить высокую доступность DistributIdService, необходимо построить кластер. Когда бизнес запрашивает кластер DistributIdService для получения идентификатора, он случайным образом выбирает узел DistributIdService для получения идентификатора. Для каждого узла DistributIdService подключается база данных. в одну и ту же базу данных, поэтому возможно создание нескольких узлов DistributIdService для одновременного запроса базы данных на получение сегмента идентификатора. В настоящее время для управления необходимо использовать оптимистическую блокировку. Например, добавляется поле версии в таблицу базы данных, а для получения сегмента идентификатора используется следующий SQL:

update id_generator set current_max_id=#{newMaxId}, version=version+1 where version = #{version}

Так как newMaxId вычисляется в соответствии с oldMaxId + размер шага в DistributIdService, при условии, что указанное выше обновление выполнено успешно, это означает, что числовой сегмент получен успешно.

Для обеспечения высокой доступности слоя БД необходимо развернуть БД в режиме multi-master.Для каждой БД необходимо следить за тем, чтобы сгенерированный сегмент номера не повторялся.Для этого требуется использование исходного идея, а затем добавляет в таблицу базы данных только сейчас.Начальное значение и размер шага, например, если есть два Mysql сейчас, то mysql1 сгенерирует числовой сегмент (1,1001), а последовательность будет 1, 3, 4, 5, 7.... mysql1 сгенерирует числовой сегмент (2,1002), а последовательность будет 2, 4, 6, 8, 10...

Для получения более подробной информации обратитесь к открытому исходному коду Didi TinyId:Ссылка на сайт

В TinyId добавлен шаг для повышения эффективности, в приведенной выше реализации логика самоувеличения ID реализована в DistributIdService, но по факту логика самоувеличения может быть перенесена в локальное бизнес-приложение, чтобы для бизнеса приложения Вам нужно только получить сегмент идентификатора, и вам больше не нужно запрашивать вызов DistributIdService при каждом увеличении.

4. Алгоритм снежинки

Вышеуказанные три метода в целом основаны на идее самоинкремента, а далее будет представлен более известный алгоритм снежинки — снежинка.

Мы можем думать о распределенных идентификаторах по-разному, если каждая машина, ответственная за создание распределенных идентификаторов, может генерировать разные идентификаторы каждую миллисекунду. Snowflake — это алгоритм генерации распределенного идентификатора с открытым исходным кодом в твиттере.Это алгоритм, поэтому он не совпадает с тремя вышеупомянутыми механизмами генерации распределенного идентификатора.Он не зависит от базы данных.

Основная идея такова: распределенный идентификатор фиксируется как длинное число, а тип long занимает 8 байт, то есть 64 бита Распределение битов в исходном алгоритме снежинки выглядит следующим образом:在这里插入图片描述

  • Первый бит является идентификационной частью.В java, поскольку старший бит long является битом знака, положительное число равно 0, а отрицательное число равно 1. Как правило, сгенерированный идентификатор является положительным числом, поэтому он фиксируется на 0.
  • Часть временной метки занимает бит 41. Это время в миллисекундах.Как правило, сохраняется не текущая временная метка, а разница между временными метками (текущее время - фиксированное время начала), которая может сделать сгенерированный идентификатор из меньшего значения, чтобы начать с ; 41-битная метка времени может использоваться для 69 лет, (1L
  • Идентификатор рабочей машины занимает 10 бит, что здесь более гибко, например, первые 5 цифр могут использоваться как идентификатор компьютерного зала центра обработки данных, а последние 5 цифр могут использоваться как идентификатор машины одного компьютера. комната, и можно развернуть 1024 узла.
  • Часть серийного номера занимает 12 бит, и один и тот же узел может сгенерировать 4096 идентификаторов за одну миллисекунду.

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

Алгоритм снежинки реализовать несложно, предоставьте реализацию Java на github:Ссылка на сайт

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

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

5. Baidu (генератор жидкости)

адрес гитхаба:uid-generatoruid-generator использует снежинку, но он отличается при создании идентификатора машины, также называемого workId.

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

Для workId в uid-generator он занимает 22 бита, time занимает 28 бит, а сериализация занимает бит 13. Следует отметить, что в отличие от оригинальной снежинки, единицей времени являются секунды, вместо миллисекунд, workId тоже разные, и одно и то же приложение использует workId при каждом перезапуске.

Для получения подробной информации см.GitHub.com/Baidu/UID-a…

6. Мэйтуан (Лист)

адрес гитхаба:Leaf

Meituan's Leaf также представляет собой распределенную среду генерации идентификаторов. Он очень всеобъемлющий, то есть поддерживает режим числового сегмента и режим снежинки. Режим числового сегмента здесь не представлен и аналогичен приведенному выше анализу.

Разница между режимом снежинки в Leaf и исходным алгоритмом снежинки в основном заключается в генерации workId.WorkId в Leaf генерируется на основе последовательного идентификатора ZooKeeper.Когда каждое приложение использует Leaf-snowflake, он будет в Zookeeper при запуске В системе генерируется последовательный идентификатор, который эквивалентен машине, соответствующей последовательному узлу, то есть workId.

Суммировать

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

Redis

Вот дополнительное введение в использование Redis для создания распределенных идентификаторов.На самом деле, аналогично использованию идентификаторов автоинкремента Mysql, команда incr в Redis может использоваться для достижения атомарного автоинкремента и возврата, например:

127.0.0.1:6379> set seq_id 1     // 初始化自增ID为1
OK
127.0.0.1:6379> incr seq_id      // 增加1，并返回
(integer) 2
127.0.0.1:6379> incr seq_id      // 增加1，并返回
(integer) 3

Эффективность использования Redis очень высока, но необходимо учитывать проблему сохраняемости. Redis поддерживает методы сохранения как RDB, так и AOF.

Персистентность RDB эквивалентна регулярному снятию снапшота для персистентности.Если снапшот инкрементируется несколько раз подряд, и нет времени сделать следующий персистентность снапшота, Redis в это время зависает, а ID будет повторяться после перезапуска Редис. .

Сохранение AOF эквивалентно сохранению каждой команды записи.Если Redis зависнет, дублирования идентификатора не будет, но перезапуск и восстановление данных займет слишком много времени из-за чрезмерной команды incr.

Категории