--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID: Geração Distribuída de Identificadores Únicos de 64 Bits com a Cifra de Bloco Sparx64' description: Gerador distribuído de IDs únicos de 64 bits que combina um timestamp de 30 bits, um ID de nó de 17 bits, um contador local de 17 bits e a cifra de bloco Sparx64 ARX para IDs não adivinháveis. language: pt date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Considere uma situação em que precisamos gerar números aleatórios únicos de 64 bits, e as partes externas não devem conseguir prever o próximo ou o número anterior. Aqui, podemos gerar um valor aleatório de 8 bytes, verificar se ele já existe no banco de dados e, em seguida, armazená-lo caso seja único. No entanto, este método apresenta várias desvantagens. Precisamos armazenar todo número gerado em um banco de dados para garantir a unicidade. A exigência de pelo menos uma ida e volta ao banco de dados cria problemas de latência, particularmente em um ambiente distribuído, onde a escalabilidade é crucial. Para resolver esses problemas, estamos apresentando o Randflake ID: um gerador de IDs aleatórios distribuído, uniforme, imprevisível e único. ## Como Funciona o Randflake ID? O Randflake ID é inspirado no Snowflake ID, o mecanismo de geração de identificadores k-ordenáveis amplamente utilizado, desenvolvido pela X (anteriormente Twitter). O Snowflake ID utiliza o timestamp atual, um ID de nó e um contador local para gerar um identificador. Expandimos ainda mais essa abordagem para a geração de IDs aleatórios únicos e acrescentamos um novo elemento: uma chave secreta. A ideia central é adicionar uma camada de cifra de bloco ao gerador de IDs únicos existente, para alcançar a inviabilidade de prever a relação entre os números. Uma cifra de bloco é uma função criptográfica fundamental que transforma um bloco de texto simples de tamanho fixo em um bloco de texto cifrado de mesmo tamanho. Essa transformação é governada por uma chave criptográfica. A característica distintiva de uma cifra de bloco é a sua reversibilidade: ela deve ser uma função biunívoca (bijetiva), garantindo que cada entrada única corresponda a uma saída única, e vice-versa. Essa propriedade é crucial para a decifragem, permitindo que o texto simples original seja recuperado a partir do texto cifrado quando a chave correta é aplicada. Ao empregar uma cifra de bloco como uma função biunívoca, podemos garantir que cada entrada única produza uma saída única correspondente dentro do intervalo definido. ## A estrutura e as considerações de projeto Com base nesses conceitos fundamentais, vamos examinar como o Randflake ID implementa essas ideias na prática. A estrutura do Randflake ID inclui um timestamp Unix de 30 bits com precisão de segundos, um identificador de nó de 17 bits, um contador local de 17 bits e uma cifra de bloco de 64 bits baseada no algoritmo sparx64. Seguem algumas decisões de projeto: - Algumas instâncias de VM no Google Cloud Platform conseguem sincronizar o relógio com precisão de 0,2 ms, mas esse nível de precisão não está disponível na internet pública ou em outros provedores de nuvem. - Escolhemos a precisão de segundos porque só conseguimos sincronizar o relógio entre os nós de forma eficaz com resoluções de alguns milissegundos. - O identificador de nó de 17 bits permite 131.072 geradores individuais no mesmo momento, que podem ser atribuídos por processo, por núcleo ou por thread. - Em sistemas de alta vazão, o contador local de 17 bits pode ser insuficiente. Para acompanhar a vazão, podemos atribuir múltiplos geradores, cada um com um ID de nó distinto, para operar em um único processo ou thread. - Adotamos o sparx64 como cifra de bloco de 64 bits, uma cifra de bloco moderna e leve baseada em operações ARX. - Os IDs do Randflake oferecem rastreabilidade interna, revelando seu ID de nó de origem e timestamp apenas para quem possui a chave secreta. - A vazão máxima teórica é de 17.179.869.184 IDs/s, o que é suficiente para a maioria das aplicações em escala global. ## Pseudocódigo da geração de Randflake ID Para ilustrar melhor o processo de geração do Randflake ID, o seguinte pseudocódigo em Python fornece uma implementação simplificada: ```python import time import struct from .sparx64 import Sparx64 # Constantes RANDFLAKE_EPOCH_OFFSET = 1730000000 # Domingo, 27 de outubro de 2024, 3:33:20 AM UTC # Alocação de bits RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bits para o timestamp (vida útil de 34 anos) RANDFLAKE_NODE_BITS = 17 # 17 bits para o ID do nó (máximo de 131072 nós) RANDFLAKE_SEQUENCE_BITS = 17 # 17 bits para a sequência (máximo de 131072 sequências) # Constantes derivadas RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1 RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1 RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1 class Randflake: def __init__(self, node_id: int, secret: bytes): self.node_id = int(node_id) self.sequence = int(0) self.rollover = int(time.time()) self.sbox = Sparx64(secret) def _new_raw(self) -> int: while True: now = int(time.time()) self.sequence += 1 sequence = self.sequence if sequence > RANDFLAKE_MAX_SEQUENCE: if now > self.rollover: self.sequence = 0 self.rollover = now sequence = 0 else: continue timestamp = now - RANDFLAKE_EPOCH_OFFSET return (timestamp << 34) | (self.node_id << 17) | sequence def generate(self) -> int: id_raw = self._new_raw() src = struct.pack("