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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура Randflake ID включает 30-битную метку времени unix с точностью до секунды, 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# Константы
 6RANDFLAKE_EPOCH_OFFSET = 1730000000  # Воскресенье, 27 октября 2024 г., 3:33:20 AM UTC
 7
 8# Распределение битов
 9RANDFLAKE_TIMESTAMP_BITS = 30  # 30 битов для метки времени (срок службы 34 года)
10RANDFLAKE_NODE_BITS = 17  # 17 битов для ID узла (макс. 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, включающая механизм аренды ID узла, доступна на GitHub.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однородность распределения ID

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

Заключение

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

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

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

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

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