Как сгенерировать уникальные идентификаторы в распределенной среде в большом масштабе

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

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

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

Универсальные уникальные идентификаторы - UUID

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

UUID - это синтетический идентификатор, состоящий из нескольких отдельных частей, таких как время, MAC-адрес узла или хешированное пространство имен MD5. Чтобы учесть все эти комбинации, на протяжении многих лет было несколько версий спецификации UUID, в частности версии 1 и 4. Однако другие версии могут быть вам интересны в зависимости от ваших данных и бизнес-области.

Работа со 128-битными числами - не самый удобный для разработчиков способ отображения информации, поэтому UUID обычно представлены в канонической текстовой форме, где 16 октетов (16 * 8 бит = 128 бит) преобразуются в 32 шестнадцатеричных символа, разделенных дефисами. , всего 36 символов:

Становится очевидным, что наиболее интересной особенностью UUID является то, что они могут генерироваться изолированно и при этом гарантировать уникальность в распределенной среде. Кроме того, лежащий в основе алгоритм генерации идентификатора не сложен и не требует какой-либо синхронизации (по крайней мере, до уровня 100 наносекунд), поэтому его можно выполнять параллельно:

Внутреннее свойство уникальности самогенерирования делает UUID одним из наиболее часто используемых методов генерации идентификаторов в распределенных средах. Однако имейте в виду, что UUID требуют дополнительного хранилища и могут отрицательно повлиять на производительность запросов.

Идентификаторы, созданные на уровне сохраняемости

Распространенный подход, когда вы не хотите создавать уникальные идентификаторы на уровне приложения, - позволить постоянному хранилищу позаботиться об этом. Все последние СУБД предоставляют своего рода тип данных столбца, позволяющий вам делегировать им создание уникального идентификатора. MongoDB предоставляет ObjectID, MySQL и MariaDB предоставляют AUTO_INCREMENT, MS SQL Server предоставляет IDENTITY и т. Д. Фактическое представление идентификатора отличается в разных реализациях базы данных, однако семантика уникальности остается той же.

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

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

Вышеупомянутый дополнительный путь к РСУБД может замедлить работу вашего приложения и излишне усложнить ваш код, однако современные инфраструктуры ORM могут помочь вам сделать это стандартизированным способом, независимо от базового продукта РСУБД, который вы используете.

ID серверов или идентификаторов Snowflake

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

Twitter не нуждается в особом представлении, и со средним показателем 9000 твитов в секунду и пиковыми значениями до 143199 твитов в секунду им требовалось решение, которое не только масштабируется по всей их обширной инфраструктуре серверов, но и генерирует эффективные идентификаторы для хранения. Вот так Twitter придумал проект Snowflake:

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

Twitter искал минимум 10 000 идентификаторов в секунду для каждого процесса со скоростью ответа ‹2 мс. Серверы идентификации не должны вообще требовать сетевой координации между ними, а генерируемые идентификаторы должны быть примерно упорядочены по времени. Наконец, чтобы свести к минимуму объем памяти, идентификаторы должны быть компактными.

Чтобы решить вышеуказанный проект, Twitter разработал проект Snowflake как Thrift Server, написанный на Scala. Сгенерированные идентификаторы состояли из:

  • Время - 41 бит (точность до миллисекунды)
  • Сконфигурированный идентификатор машины - 10 бит
  • Порядковый номер - 12 бит - переключается каждые 4096 на машину

Хотя Snowflake в настоящее время является устаревшим проектом Twitter, замененным более широким проектом TwitterServer, основные принципы работы распределенного генератора идентификаторов все еще применяются. Из-за независимого характера каждого генератора Twitter смог масштабировать свою инфраструктуру по мере необходимости, не внося дополнительных задержек, благодаря синхронизации и координации кластера.

Решение с сервером идентификаторов работает аналогично идентификаторам, сгенерированным кодом:

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

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

Заключение

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

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

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

Спасибо, что прочитали эту статью. Надеюсь увидеть вас в следующем.