Недавно на работе мы искали способ генерировать уникальные идентификаторы в распределенной системе, которые также можно было бы использовать в качестве первичных ключей в таблицах MySQL.
Мы знали, что в одной базе данных MySQL мы можем просто использовать идентификатор автоинкремента в качестве первичного ключа, но это не будет работать в разделенной базе данных MySQL.
Итак, я просмотрел различные существующие решения для этого и, наконец, узнал о Twitter Snowflake – простой 64-битный генератор уникальных идентификаторов.
UUID – это 128-битные шестнадцатеричные числа, которые являются глобально уникальными. Вероятность того, что один и тот же UUID будет сгенерирован дважды, ничтожно мала.
Проблема с UUID заключается в том, что они очень большие по размеру и плохо индексируются. Когда ваш набор данных увеличивается, размер индекса также увеличивается, а производительность запросов снижается.
Еще одна проблема с UUID связана с пользовательским интерфейсом. В конце концов, нашим пользователям понадобятся эти уникальные идентификаторы. Представьте, что клиент звонит в Службу поддержки клиентов, и его просят предоставить идентификатор. Необходимость вводить полный UUID по буквам – не самое приятное занятие.
Twitter snowflake – это специализированный сервис для генерации 64-разрядных уникальных идентификаторов, используемых в распределенных вычислениях для объектов в Twitter, таких как Твиты, прямые сообщения, Списки и т.д.
Эти идентификаторы представляют собой уникальные 64-разрядные целые числа без знака, которые основаны на времени. Полные идентификаторы состоят из следующих компонентов:
- Временная метка эпохи в миллисекундах – 41 бит (дает нам 69 лет по отношению к любой пользовательской эпохе)
- Сконфигурированный идентификатор машины/узла/сегмента – 10 бит (дает нам в общей сложности до 210, то есть 1024 идентификаторов)
- Порядковый номер – 12 бит (локальный счетчик на машину, который устанавливается на ноль после каждых 4096 значений)
- Дополнительный 1 зарезервированный бит в начале, который устанавливается равным 0, чтобы общее число было положительным.
Поскольку они используют временную метку в качестве первого компонента, следовательно, они также могут быть отсортированы по времени . Еще одним преимуществом является его Высокая доступность .
По умолчанию 64-разрядные целые числа без знака (long) генерируют идентификатор длиной 19, но иногда он может быть слишком длинным, в нашем случае требовался идентификатор, длина которого не должна превышать 10.
В этой статье будет представлена упрощенная версия генератора уникальных идентификаторов, которая будет работать для любого варианта использования генерации уникальных идентификаторов в распределенной среде на основе концепций, изложенных в сервисе Twitter snowflake.
В нашем случае полный идентификатор будет состоять из 20-разрядной метки времени, 5-разрядного рабочего номера и 6-разрядного порядкового номера.
Оставшийся 1 бит – это бит со знаком, и он всегда устанавливается равным 0, чтобы сделать конечное значение положительным.
Наши микросервисы могут использовать этот генератор случайных чисел для независимой генерации идентификаторов. Это эффективно и соответствует размеру int (4 байта или 32 бита).
Вот полный код на Java ( Вдохновленный Twitter snowflake , кредиты кода ) –
Шаг 1 – Мы инициализируем количество битов, которое потребуется каждому компоненту :
public class Snowflake {
// Sign bit, Unused (always set to 0)
private static final int UNUSED_BITS = 1;
private static final int EPOCH_BITS = 20;
private static final int NODE_ID_BITS = 5;
private static final int SEQUENCE_BITS = 6;
private static final int maxNodeId = (int)(Math.pow(2, NODE_ID_BITS) - 1);
private static final int maxSequence = (int)(Math.pow(2, SEQUENCE_BITS) - 1);
// Custom Epoch (Fri, 21 May 2021 03:00:20 GMT)
private static final int DEFAULT_CUSTOM_EPOCH = 1621566020;
private volatile int lastTimestamp = -1;
private volatile int sequence = 0;
// Class Constructor
public Snowflake() {
this.nodeId = createNodeId();
this.customEpoch = DEFAULT_CUSTOM_EPOCH;
}
Здесь мы берем пользовательскую эпоху по состоянию на пятницу, 21 мая 2021 года, 03:00:20 по Гринвичу.
EPOCH_BITS будет составлять 20 бит и заполняется текущей временной меткой в секундах (вы также можете использовать миллисекунду, если есть возможность многократного количества запросов в секунду).
NODE_ID_BITS будет состоять из 5 бит и заполняется с использованием Mac-адреса.
SEQUENCE_BITS будет иметь 6 бит и будет действовать как локальный счетчик, который будет начинаться с 0, идти до 63, а затем сбрасываться обратно на 0.
Шаг 2 – Создание синхронизированной функции для генерации идентификаторов :
public synchronized int nextId() {
int currentTimestamp = (int) (Instant.now().getEpochSecond() - customEpoch);
if(currentTimestamp < lastTimestamp) {
throw new IllegalStateException("Invalid System Clock!");
}
lastTimestamp = currentTimestamp;
return currentTimestamp << (NODE_ID_BITS + SEQUENCE_BITS) | (nodeId << SEQUENCE_BITS) | sequence;
}
Подождите, почему мы делаем эти сдвиги влево и логические операции ИЛИ?
Это связано с тем, что целое число представлено 32 битами, и изначально все они равны 0. Чтобы заполнить эти биты, мы должны взять каждый компонент отдельно, поэтому сначала мы взяли временную метку эпохи и сдвинули ее на 5 + 6, то есть на 11 бит влево. Выполнение этого заполнило первые 21 бит первым компонентом (помните, что первый бит всегда равен нулю, чтобы общее число было положительным). Оставшиеся 11 битов по-прежнему равны 0, и, следовательно, мы снова повторяем то же самое с логическим ИЛИ & двумя другими компонентами, тем самым заполняя все 32 бита и формируя полное число.
Шаг 3 – Служебная функция для генерации идентификатора узла с использованием MAC-адреса системы :
private int createNodeId() {
int nodeId;
try {
StringBuilder sb = new StringBuilder();
Enumeration networkInterfaces = NetworkInterface.getNetworkInterfaces();
while (networkInterfaces.hasMoreElements()) {
NetworkInterface networkInterface = networkInterfaces.nextElement();
byte[] mac = networkInterface.getHardwareAddress();
if (Objects.nonNull(mac))
for(byte macPort: mac)
sb.append(String.format("%02X", macPort));
}
nodeId = sb.toString().hashCode();
} catch (Exception ex) {
nodeId = (new SecureRandom().nextInt());
}
nodeId = nodeId & maxNodeId;
return nodeId;
}
}
Как это работает? 💡
Давайте теперь разберемся в его работе на примере –
Допустим, сейчас Солнце, 23 мая 2021 года, 00:00:00 по Гринвичу. Временная метка эпохи для этого конкретного времени равна 1621728000.
Прежде всего, мы корректируем нашу временную метку в соответствии с пользовательской эпохой-
Отметка текущего времени – (Настройка для пользовательской эпохи)
Итак, чтобы запустить наш идентификатор, первые 20 битов идентификатора (после подписанного бита) будут заполнены временной меткой эпохи. Давайте это значение со сдвигом влево:
i d << (NODE_ID_BITS + SEQUENCE_BITS )
Далее мы берем настроенный идентификатор узла/идентификатор сегмента и заполняем им следующие 10 битов
идентификатор | идентификатор узла << SEQUENCE_BITS
Наконец, мы берем следующее значение нашей последовательности автоматического увеличения и заполняем оставшиеся 6 битов –
идентификатор | последовательность//6149376
Это дает нам наше окончательное удостоверение личности 🎉
И это все! Первичные ключи, уникальные для всего нашего приложения!
Резюме 📊
В этой статье показано простое решение о том, как сгенерировать идентификатор снежинки, длина которого равна и.
Кстати, вы можете настроить количество битов для 3 компонентов, чтобы приспособиться к вашей работе.
записка: Мы должны сохранить генератор как одноэлементный, это означает, что мы должны создавать только один экземпляр SequenceGenerator для каждого узла. Если нет, то он может сгенерировать несколько повторяющихся идентификаторов.
Мало того, что твиттер использовал его, Discord также использует снежинки, их эпоха установлена на первую секунду 2015 года.
Instagram использует модифицированную версию формата, содержащую 41 бит для метки времени, 13 бит для идентификатора фрагмента и 10 бит для порядкового номера.
Я надеюсь, что это поможет вам! Спасибо за чтение:))
Хотите начать с веб-разработки? Оформить заказ ▶ HTML Реагировать: Окончательное Руководство
Эта электронная книга представляет собой всеобъемлющее руководство, которое научит вас всему, что вам нужно знать, чтобы стать веб-разработчиком, с помощью тонны простых для понимания примеров и проверенных дорожных карт
Он содержит 👇
✅ Сразу к делу, объяснения
✅ Простые примеры кода
✅ Более 50 интересных проектных идей
✅ 3 Контрольные списки секретных ресурсов
✅ Бонусная подготовка к собеседованию
Вы даже можете проверить бесплатный образец из этой книги
и вот ссылка на полную книгу, если вы хотите купить ее для себя
Первоначальная цена составляет 40 долларов, но цена по этой ссылке – 16 долларов (что на 60% меньше первоначальной цены) 😉
👇
Оригинал: “https://dev.to/apoorvtyagi/generating-unique-ids-in-a-large-scale-distributed-environment-257d”