Разъяснения требований
- Идентификаторы должны быть уникальными
- Идентификаторы должны сортироваться по времени
- Идентификаторы должны быть 64-битными.
- Система должна быть способна обрабатывать 10 000 идентификаторов в секунду.
Репликация с несколькими мастерами
Этот подход использует функцию auto_increment базы данных. Мы увеличиваем идентификатор в каждом сервере на размер шага k, где k — количество серверов баз данных.
Как показано на изображении, сгенерированные идентификаторы увеличились на 2.
Этот подход имеет несколько недостатков:
- На нескольких серверах идентификаторы не упорядочены по времени
- Плохо работает при добавлении или удалении серверов
Централизованное автоматическое увеличение
Если мы не можем заставить auto_increments работать с несколькими базами данных, что, если мы будем использовать одну базу данных? Таков подход Flickr.
Сервер билетов Flickr — это выделенный сервер базы данных с одной базой данных; в этой базе данных есть такие таблицы, как Tickets32 для 32-битных идентификаторов и Tickets64 для 64-битных идентификаторов.
Схема Tickets64 выглядит так:
CREATE TABLE `Tickets64` ( `id` bigint(20) unsigned NOT NULL auto_increment, `stub` char(1) NOT NULL default '', PRIMARY KEY (`id`), UNIQUE KEY `stub` (`stub`) ) ENGINE=InnoDB
SELECT * from Tickets64
возвращает одну строку, которая выглядит примерно так:
+-------------------+------+ | id | stub | +-------------------+------+ | 72157623227190423 | a | +-------------------+------+
Когда мне нужен новый глобально уникальный 64-битный идентификатор, я выдаю следующий SQL:
REPLACE INTO Tickets64 (stub) VALUES ('a'); SELECT LAST_INSERT_ID();
Этот подход имеет несколько недостатков:
- Единая точка отказа
UUID
String generateID() { return UUID.randomUUID().toString().replaceAll("-",""); }
UUID — это 128-битные шестнадцатеричные числа. Они просты в использовании и имеют очень низкую вероятность столкновения. Система может легко масштабироваться, поскольку каждый сервер отвечает за создание собственного идентификатора.
Этот подход имеет несколько недостатков:
- Не соответствует требованию 64-битного размера
- Идентификаторы не могут быть упорядочены по времени в зависимости от реализации
Твиттер Снежинка
Такой подход делит ID на разные разделы.
| 1 bit | 41 bits | 5 bits | 5 bits | 12 bits | |-------|-----------|----------------|------------|-----------------| | 0 | timestamp | data center id | machine id | sequence number |
Идентификаторы состоят из следующих компонентов:
- Временная метка эпохи — 41 бит, что дает нам 69 лет для любой пользовательской эпохи.
- Идентификатор центра обработки данных — 5 бит, что дает нам 32 центра обработки данных.
- Идентификатор машины — 5 бит, что дает нам 32 машины на центр обработки данных.
- Порядковый номер — порядковый номер увеличивается на 1 для каждого идентификатора, сгенерированного на машине. Сбрасывается в 0 каждую миллисекунду. Теоретически мы можем поддерживать 2¹² = 4096 новых идентификаторов каждую миллисекунду.
- Дополнительный зарезервированный бит должен сделать общее число положительным.
Такой подход соответствует нашим требованиям. Тем не менее, есть еще несколько соображений:
- Синхронизация часов. В распределенных системах серверы могут не использовать одни и те же часы для генерации метки времени. Популярным решением для синхронизации часов может быть использование Network Time Protocol.
Похожие подходы на основе Snowflake
Спасибо, что прочитали эту статью! Оставьте комментарий ниже, если у вас есть какие-либо вопросы. Эта статья также опубликована в The Woke Coder. Свяжитесь со мной в Linkedin и Twitter.