Randflake ID: распределённая генерация 64-битных уникальных идентификаторов с помощью блочного шифра Sparx64

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

В этом случае можно сгенерировать 8-байтовое случайное значение, проверить, существует ли оно уже в базе данных, и затем сохранить его, если оно уникально.

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

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

Как работает Randflake ID?

Randflake ID вдохновлен Snowflake ID, широко используемым механизмом генерации k-упорядоченных идентификаторов, разработанным компанией X (ранее Twitter).

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

Мы расширили этот подход для генерации случайных уникальных идентификаторов и добавили новый элемент: секретный ключ.

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

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

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

Структура и проектные решения

Опираясь на эти фундаментальные концепции, рассмотрим, как Randflake ID реализует эти идеи на практике.

Структура Randflake ID включает 30-битную метку времени Unix с точностью до секунды, 17-битный идентификатор узла, 17-битный локальный счетчик и 64-битный блочный шифр на основе алгоритма sparx64.

Вот некоторые проектные решения:

• Некоторые виртуальные машины в Google Cloud Platform могут синхронизировать часы с точностью 0,2 мс, но такой уровень точности недоступен в публичном интернете или у других облачных провайдеров.

• Мы выбрали точность до секунды, поскольку можем эффективно синхронизировать часы между узлами только с точностью до нескольких миллисекунд.

• 17-битный идентификатор узла позволяет одновременно работать 131072 отдельным генераторам, которые могут назначаться для каждого процесса, ядра или потока.

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

• Мы выбрали sparx64 в качестве 64-битного блочного шифра, современного легковесного блочного шифра на основе операций ARX.

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

• Теоретическая максимальная пропускная способность составляет 17 179 869 184 ID/с, что достаточно для большинства глобальных приложений.

Псевдокод генерации Randflake ID

Для дальнейшей иллюстрации процесса генерации Randflake ID ниже приведен простой псевдокод на Python:

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Константы
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunday, October 27, 2024 3:33:20 AM UTC
 7
 8# Распределение битов
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 бит для временной метки (срок службы 34 года)
10RANDFLAKE_NODE_BITS = 17  # 17 бит для идентификатора узла (максимум 131072 узла)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 бит для последовательности (максимум 131072 последовательности)
12
13# Производные константы
14RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1
15RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1
16RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1
17
18class Randflake:
19    def __init__(self, node_id: int, secret: bytes):
20        self.node_id = int(node_id)
21        self.sequence = int(0)
22        self.rollover = int(time.time())
23        self.sbox = Sparx64(secret)
24
25    def _new_raw(self) -> int:
26        while True:
27            now = int(time.time())
28
29            self.sequence += 1
30            sequence = self.sequence
31
32            if sequence > RANDFLAKE_MAX_SEQUENCE:
33                if now > self.rollover:
34                    self.sequence = 0
35                    self.rollover = now
36                    sequence = 0
37                else:
38                    continue
39
40            timestamp = now - RANDFLAKE_EPOCH_OFFSET
41            return (timestamp << 34) | (self.node_id << 17) | sequence
42
43    def generate(self) -> int:
44        id_raw = self._new_raw()
45        src = struct.pack("<q", id_raw)
46        dst = bytearray(8)
47        self.sbox.encrypt(dst, src)
48        return struct.unpack("<q", dst)[0]

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

Прочие соображения

В этом разделе мы рассмотрим некоторые дополнительные соображения по реализации Randflake ID.

Координация идентификаторов узлов

Мы предлагаем координацию идентификаторов узлов на основе аренды.

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

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

Генератор, владеющий арендой, может запросить ее продление у службы координации, если выполнено условие продления.

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

Держатель аренды является текущим владельцем диапазона идентификаторов узлов.

Аренда считается активной и не истекшей, если она находится в пределах своего действительного периода.

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

Защита от неисправных часов

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

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

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

Равномерность распределения идентификаторов

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

Заключение

В этой статье мы представили Randflake, новый алгоритм генерации идентификаторов, который сочетает преимущества Snowflake и Sparx64.

Мы надеемся, что эта статья дала вам всестороннее понимание Randflake и его реализации.

Полный исходный код Randflake можно найти на GitHub.

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

Мы планируем выпустить производственно готовую службу координации для Randflake и Snowflake, которая будет открыта на GitHub. Следите за обновлениями!