Разъяснения требований

  1. Идентификаторы должны быть уникальными
  2. Идентификаторы должны сортироваться по времени
  3. Идентификаторы должны быть 64-битными.
  4. Система должна быть способна обрабатывать 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.