В распределенных системах есть некоторые сценарии, требующие использования глобально уникальных идентификаторов.В этом случае можно использовать 36-битные UUID для предотвращения конфликтов идентификаторов.Однако у UUID есть некоторые недостатки.Во-первых, они относительно длинные, и UUID в общем беспорядок.
Иногда мы хотим использовать более простой идентификатор и надеемся, что идентификатор может быть сгенерирован в порядке времени.
Публичный аккаунт: технические заметки Longtai
Что такое алгоритм снежинки
Snowflake означает снежинка на китайском языке, поэтому его часто называют алгоритмом снежинки, который представляет собой алгоритм генерации распределенного идентификатора Twitter с открытым исходным кодом.
После того, как алгоритм снежинки Twitter сгенерирован, это 64-битное значение Компонент вводит метку времени, которая в основном поддерживает автоинкремент.
Преимущества алгоритма SnowFlake:
- Высокая производительность и высокая доступность: не зависит от базы данных во время генерации и полностью генерируется в памяти.
- Высокая пропускная способность: миллионы автоматически увеличивающихся идентификаторов могут генерироваться в секунду.
- Самоинкремент ID: хранится в базе данных, эффективность индексации высокая
Недостатки алгоритма SnowFlake:
Зависит от согласованности с системным временем. Если системное время вызывается или изменяется, это может вызвать конфликты идентификаторов или дублирование
Состав алгоритма снежинки
Структура снежинки показана на следующем рисунке:
Содержит четыре компонента
Не используй: 1 бит, старший бит является битом знака, 0 означает положительный, 1 означает отрицательный, фиксируется на 0
отметка времени: 41-битная отметка времени на уровне миллисекунд (41-битная длина может использоваться для 69 лет)
идентификационный бит: 5-битный идентификатор центра обработки данных, 5-битный идентификатор рабочей машины, комбинация двух идентификационных битов может поддерживать развертывание до 1024 узлов.
серийный номер: 12-битный добавочный порядковый номер, указывающий, что узел генерирует дубликаты в течение миллисекунд, а порядковый номер указывает на уникальность, 12-битный может генерировать 4096 идентификаторов за миллисекунду.
4096 уникальных идентификаторов могут быть сгенерированы серийным номером за 1 миллисекунду, тогда 4096 * 1000 = 409w идентификаторов могут быть сгенерированы за 1 секунду
Алгоритм снежинки по умолчанию составляет 64 бита, а конкретную длину можно настроить самостоятельно. Если хочешь бегать дольше,Увеличьте количество бит в отметке времени; Если вам нужно поддерживать больше развертываний узлов,Увеличить длину маркера; если параллелизм высокий,Увеличить количество цифр в серийном номере
Суммировать: Алгоритм снежинки не статичен, его можно настроить в соответствии с конкретной сценой в системе.
Алгоритм снежинки Применимые сценарии
Поскольку алгоритм снежинки является упорядоченным и самоинкрементным, он обеспечивает высокую производительность вставки структуры индекса дерева B+ в MySQL.
Поэтому при повседневном использовании алгоритм Snowflake в основном применяется к идентификатору первичного ключа базы данных и первичному ключу, связанному с бизнесом.
Алгоритм Snowflake генерирует проблему дублирования идентификатора
Предположение: микросервис заказов, который генерирует идентификаторы с помощью алгоритма снежинки, развертывает всего три узла и имеет одинаковые идентификаторы.
В настоящее время существует 200 одновременных, равномерно распределенных трех узлов, три узла генерируют идентификаторы под одним и тем же порядковым номером в одну и ту же миллисекунду, затем будут генерироваться повторяющиеся идентификаторы.
Из приведенных выше гипотетических сценариев можно узнать, что существуют определенные предпосылки для конфликта идентификаторов, генерируемого алгоритмом Snowflake.
- Служба развернута в кластере, и некоторые идентификаторы компьютеров совпадают.
- В бизнесе существует определенный уровень параллелизма, и ни одна проблема дублирования не может быть вызвана без такого количества параллелизма.
- Время генерации идентификатора: согласованные порядковые номера в одну и ту же миллисекунду
Как определяется идентификационный бит?
Если вы можете гарантировать, что биты идентификации не повторяются, то идентификатор снежинки не будет повторяться.
Благодаря приведенному выше случаю мы знаем необходимые условия для повторения идентификатора. Если вы хотите избежать дублирования идентификаторов в сервисе, вам необходимо переместить статью из идентификатора
Давайте сначала посмотрим, как алгоритм снежинки используется в среде с открытым исходным кодом для определения идентификационного бита.
Mybatis-Plus v3.4.2 Snowflake Algorithm реализует класс Sequence, который предоставляет два метода построения: построение без параметров, которое автоматически генерирует dataCenterId и workerId, построение на основе параметров, которое четко указывает идентификатор при создании Sequence.
Hutool v5.7.9 относится к схеме генерации dataCenterId и workerId Mybatis-Plus и обеспечивает реализацию по умолчанию.
Давайте посмотрим на построение Sequence без параметров по умолчанию, как сгенерировать dataCenterId и workerId.
public static long getDataCenterId(long maxDatacenterId) {
long id = 1L;
final byte[] mac = NetUtil.getLocalHardwareAddress();
if (null != mac) {
id = ((0x000000FF & (long) mac[mac.length - 2])
| (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
id = id % (maxDatacenterId + 1);
}
return id;
}
ВходmaxDatacenterId— фиксированное значение, представляющее максимальный идентификатор центра обработки данных, значение по умолчанию — 31.
Почему максимальное значение 31? Поскольку максимальное двоичное значение 5 бит равно 11111, что соответствует десятичному значению 31.
При получении dataCenterId возможны две ситуации: во-первых, сетевой интерфейс пуст, и значение по умолчанию равно 1L, во-вторых, не пуст, и dataCenterId получен через Mac-адрес.
Известно, что значение dataCenterId связано с адресом Mac.
Далее посмотрите на workerId
public static long getWorkerId(long datacenterId, long maxWorkerId) {
final StringBuilder mpid = new StringBuilder();
mpid.append(datacenterId);
try {
mpid.append(RuntimeUtil.getPid());
} catch (UtilException igonre) {
//ignore
}
return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}
Входной параметр maxWorkderId также является фиксированным значением, представляющим максимальный идентификатор рабочей машины, значение по умолчанию — 31; datacenterId берется из приведенного выше метода getDatacenterId.
Значение переменной имениPID@IP, поэтому имя должно быть основано на@Разделите и получите индекс 0, чтобы получить PID
Получите 16 младших бит через хэш-код MAC + PID, выполните операцию и, наконец, получите workerId.
распределение флагов
Получение идентификационного бита Mybatis-Plus зависит от адреса Mac и PID процесса.Хотя этого можно избежать, насколько это возможно, все же есть небольшой шанс
Как определить идентификационный бит, чтобы он не повторялся? Есть два варианта:Предварительное и динамическое размещение
предварительное распределение
Прежде чем приложение выйдет в сеть, подсчитайте количество узлов, обслуживаемых в настоящее время, и вручную подайте заявку на идентификатор.
Это решение не требует разработки кода и может использоваться в фиксированных сервисных узлах или нескольких проектах, но оно не может решить проблему динамического расширения сервисных узлов.
динамическое размещение
Сохраняя бит идентификации в промежуточном программном обеспечении, таком как Redis, Zookeeper, MySQL и т. д., запрашивайте бит идентификации при запуске службы и обновляйте бит идентификации до следующего доступного после запроса.
При сохранении идентификационных битов проблема усложняется: идентификатор алгоритма снежинкиУникальный в пределах службы или глобально уникальный
Возьмем Redis в качестве примера: если вы хотите быть уникальным внутри службы, вы можете использовать узел Redis, который хранит идентификатор в вашем собственном проекте; если он глобально уникален, все приложения, использующие алгоритм снежинки, используют один и тот же узел Redis.
Разница между ними толькоСовместно ли используют Redis разные сервисы. Если нет требования быть глобально уникальным, лучше сделать идентификатор уникальным в пределах службы, так как это позволяет избежать единой точки проблемы.
Если количество сервисных узлов превышает 1024, требуется дополнительное расширение; можно расширить 10-битные идентификационные биты или можно выбрать структуру распределенной идентификации с открытым исходным кодом.
Схема реализации динамического размещения
Redis хранит ключ структуры хэша, который содержит две пары ключ-значение: dataCenterId и workerId.
Когда приложение запустится, перейдите в Redis, чтобы получить идентификационный бит через сценарий Lua. Получение и автоматическое увеличение dataCenterId и workerId выполняются в скрипте Lua, а доступные флаги доступны после возврата вызова.
Конкретная логика сценария Lua выглядит следующим образом:
- Когда получен первый сервисный узел, у Redis может не быть хэша snowflake_work_id_key.Сначала необходимо определить, существует ли хеш.Хеш инициализации отсутствует, а dataCenterId и workerId инициализируются 0.
- Если Hash уже существует, определите, равны ли dataCenterId и workerId максимальному значению 31, и инициализируйте dataCenterId и workerId до 0, если условия выполнены.
- Общее количество перестановок и комбинаций dataCenterId и workerId равно 1024. При назначении сначала назначьте workerId.
- Определите, равен ли workerId != 31, если условие истинно, увеличьте workerId и верните его; если workerId = 31, увеличьте dataCenterId и установите workerId на 0
DataCenterId и workerId продвигались вниз, образуя кольцо в целом. пройти черезАтомарность Lua-скриптов, чтобы генерация алгоритма снежинки под 1024 узлами не повторялась. Если флаг равен 1024, продолжить цикл с начала
Платформа распределенной идентификации с открытым исходным кодом
И Leaf, и Uid реализуют алгоритм снежинки, а Leaf дополнительно предоставляет идентификатор для генерации шаблона числового сегмента.
Лист Мейтуан:https://github.com/Meituan-Dianping/Leaf
Байду Уид:https://github.com/baidu/uid-generator
Алгоритм Snowflake может удовлетворить большинство сценариев, если в этом нет необходимости,Не рекомендуется внедрять решения с открытым исходным кодом для увеличения сложности системы.
Итоги обзора
Статья помогает читателям разобраться, что такое алгоритм снежинки и как решить проблему конфликта идентификаторов, порожденного алгоритмом снежинки, с помощью картинок и текстов.
Что касается проблемы конфликта идентификаторов, порожденного алгоритмом снежных колец, в статье дается решение:распределение флагов; Путем назначения битов идентификации компонента алгоритма снежинки достигается генерация уникального идентификатора в узле 1024 по умолчанию.
Вы можете увидеть конкретную реализацию алгоритма снежинки Hutool или Mybatis-Plus, чтобы лучше понять
Алгоритм снежинки не является панацеей и не может применяться ко всем сценариям.Если идентификатор должен быть уникальным в глобальном масштабе, а сервисный узел превышает 1024 узла, вы можете изменить состав самого алгоритма, то есть расширить идентификационный бит, или выбрать решение с открытым исходным кодом: LEAF, UID
Создать его непросто, а прочитать статью полезно.Нажмите, чтобы поддержать,удачи