Идентификаторы для распределённых систем

Каждый объект в информационной системе имеет некоторый признак по которому его можно однозначно идентифицировать — идентификатор. Если речь идёт о простых системах, то там вполне достаточно целочисленных идентификаторов, генерируемых средствами СУБД, или UUID. Они просты в использовании и понимании, но в то же время их возможностей недостаточно при построении распределённых систем, либо их поддержка создаёт определённые сложности.

Стандартные идентификаторы их достоинства и недостатки

Если вы имеете опыт работы с реляционными базами данных вроде MySQL, PostgreSQL и другими, то вы, наверняка, использовали механизмы генерирования целочисленных идентификаторов, которые выглядят как последовательность чисел 1, 2, 3 и т.д. У таких идентификаторов есть целый ряд достоинств:

• Генерируются средствами СУБД, вам не приходится реализовывать собственный механизм их генерирования
• Компактные (int32 занимает всего 4 байта, int64 или long — 8 байт), но позволяющие хранить значительное количество объектов — от 2147483647 (2^31-1) для int32 со знаком до 18446744073709551615 (2^64) для int64 без знака
• Поддерживают сортировку: строка с идентификатором 1 была создана раньше строки с идентификатором 10 в одной и той же таблице (если вы не вмешивались в процесс выбора идентификатора для новой строки)

В то же время у таких идентификаторов есть и существенный недостаток, проявляющийся в распределённых системах — зависимость от БД, в которой генерируются идентификаторы, потому что только использование одной БД позволит вам генерировать уникальные идентификаторы в рамках системы. Если вы полагаетесь на такие идентификаторы при разработке распределённой системы, то вы, скорее всего, будете использовать классическую репликацию «master — slave». И генерировать идентификаторы в такой схеме будет как раз master-база, которая может стать точкой отказа и обязательно станет ей с ростом нагрузки (а вы будете бросать значительные ресурсы на поддержание стабильности её работы).

В качестве частичного решения этой проблемы можно рассматривать партиционирование таблиц таким образом, чтобы на разных серверах генерировались разные идентификаторы. Например, если сервера два, то на первом будут только нечётные идентификаторы, а на втором — чётные. Но и этот подход имеет проблемы. Во-первых, нужно как-то определять, к какому серверу БД нужно обратиться при сохранении очередного объекта, а во-вторых будут сложности с дальнейшим масштабированием.

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

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

• Относительная компактность (128 бит или 16 байт)
• Большое количество возможных значений — потенциально 2^128, хотя реальное количество несколько меньше, но и этого будет достаточно

Но UUID имеет и свои недостатки, один из самых весомых — отсутствие возможности сортировки в СУБД по порядку создания. Кроме этого по UUID сложно определить к какому сервису или датацентру он относится, если вы не писали свой генератор UUID.

URN и подобные

Когда-то при разработке одного из проектов передо мной была поставлена задача создать генератор уникальных идентификаторов. Идентификаторы должны были позволять партиционировать данные по дате их создания, а так же определять сервис, в котором они были созданы. И первый вариант, пришедший мне в голову — генерировать что-то вроде URN, содержащий идентификатор сервис, дату создания идентификатора и случайно сгенерированный UUID. В общей сложности получалось что-то вроде: svc.20221206.c36c47c0-7568-11ed-9dc3-fbb57b9d0245.

Со своими задачами такой идентификатор справился успешно, но он занимает много места (49 байт в данном примере, если использовать UTF-8) и не поддерживает сортировку.

Twitter Snowflake ID

И вот я добрался до книги Алекса Сюйя «System Design. Подготовка к сложному интервью», где для решения задачи по написания генератора идентификаторов предлагается Twitter Snowflake ID. В описанном примере идентификатор представляет собой 64-разрядное целое число, где:

• 0 бит всегда равен 0
• биты 1-41 — метка времени от начала «эпохи Twitter» (4 ноября 2010 года) в миллисекундах
• биты 42-52 — идентификатор машины/сервиса, который создал идентификатор
• последние 12 бит — 53-64 — последовательность, используемая, если для одной метки времени создаётся несколько идентификаторов

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

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

Не обязательно, чтобы метка времени была именно в миллисекундах, вполне можно использовать и секунды, тут многое зависит от количества генерируемых идентификаторов в секунду, и будет ли достаточно метки времени и последовательности для покрытия количества генерируемых идентификаторов. Необязательно выделять 41 бит под метку времени, особенно, если она в секундах, в ряде случаев 31 бита будет достаточно. Ну и точку отсчёта вы можете взять какую-то свою, а не 4 ноября 2010 года или 1 января 1970 года. Строго говоря, метка времени вообще не обязательна, последовательности может хватить для ваших задач, но она будет полезна для случаев, когда у вас используется партиционирование данных по метке времени. Имейте в виду, что при использовании метки времени в идентификаторе у вас в обязательном порядке будут пропуски их диапазонов, если только у вас не очень высоконагруженная система, гарантированно генерирующая как минимум один идентификатор для каждой метки времени.

А вот последовательность, которую я бы поставил на второе место после метки времени, исключить не получится, так как в один момент времени может быть сгенерировано несколько идентификаторов. И, чтобы обеспечить их уникальность, как раз потребуется последовательность. Возможный диапазон значений зависит, опять же, от количества генерируемых идентификаторов. Если вы используете метку времени в секундах, и в секунду генерируется тысяча идентификаторов, то вполне хватит 10 бит (максимум 1024), хотя лучше взять с запасом 11 бит (2048 значений). А при полном отказе от метки времени в идентификаторе вы просто будете инкрементировать последовательность, минимизируя пропуски идентификаторов.

Под сервисы, машины и датацентры нужно выделять диапазоны бит с умом, пытаясь заранее вычислить потенциально максимальное их количество. Выделять под них 10 бит, как разработчики Twitter, вам, возможно, не потребуется, так как далеко не факт, что у вас будет по 32 (2^5) машины в 32 датацентрах.

Ну и напоследок я бы рекомендовал в самом конце зарезервировать 2-4 бита под версию идентификатора. Вполне вероятна ситуация, когда вы таки просчитаетесь с количеством сервисов или датацентров, и вам потребуется увеличить диапазоны бит под них, позаимствовав их у метки времени или последовательности. И чтобы отличать старые идентификаторы от новых, вам пригодится версия.