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

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

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

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

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

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

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

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

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

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

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

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

Структура и соображения по проектированию

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

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

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

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

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

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

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

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

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

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

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

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

 1import time
 2import struct
 3from .sparx64 import Sparx64
 4
 5# Constants
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Sunday, October 27, 2024 3:33:20 AM UTC
 7
 8# Bits allocation
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 bits for timestamp (lifetime of 34 years)
10RANDFLAKE_NODE_BITS = 17  # 17 bits for node id (max 131072 nodes)
11RANDFLAKE_SEQUENCE_BITS = 17  # 17 bits for sequence (max 131072 sequences)
12
13# Derived constants
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, включающая механизм аренды ID узла, доступна на GitHub.

Другие соображения

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

Координация ID узлов

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

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

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

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

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

Арендатор является текущим держателем диапазона ID узлов.

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

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

Смягчение последствий сбоев часов

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

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

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

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

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

Заключение

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

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

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

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

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