Executando verificação de segurança...
3

Como gerar identificadores aleatórios únicos de tamanho fixo?

1 - Problemática

Tenho um requerimento de gerar identificadores aleatórios únicos com tamanho fixo de 6 digitos compostos apenas por letras e números.

Devido a esse requerimento não vejo como utilizar ids padronizados como uuids pois possuem tamanho muito maior do que isso.

Partindo disso eu desenvolvi o seguinte algoritmo:

import secrets
import string

alphabet = string.ascii_lowercase
ids = [] # Na prática, claro, os ids estão sendo salvos em um banco de dados.

def generate_random_id():
    id = secrets.token_urlsafe(4)
    return id.replace("-", secrets.choice(alphabet)).replace("_",   secrets.choice(alphabet))
    
def attempt_to_generate_id(i, attempts=5):
    attempts_counter = 0

    while (id := generate_random_id()) in ids:
        if attempts_counter == attempts:
            raise ValueError("Too many attempts generating unique random id")
        
        attempts_counter += 1
        continue

    ids.append(id)
    return id

2 - Discussão

Os problemas que vejo nessa forma de gerar os identificadores únicos:

  • Necessidade de checar se o id já existe no banco.
  • Realizar um loop até encontrar um id que não exista ainda.
  • Usar a variável attempts pra evitar iteraçōes excessivas

Então a grande questão que eu gostaria de discutir seria confirmar se pra esse cenário realmente não há como fugir dessas tratativas ou se existem formas melhores de gerar os ids aleatórios com tamanho fixo.

Carregando publicação patrocinada...
6

Antes de pular direto para bibliotecas prontas, talvez seja interessante estudar e entender um pouco mais sobre os fundamentos.

A Abordagem Clássica: Feistel Cipher

O Feistel Cipher é uma técnica fundamental usada em muitas funções de hash populares, como AES e Blowfish. Ele é um método que permite criar uma função pseudoaleatória que é invertível, o que significa que cada entrada única produzirá uma saída única e vice-versa. Embora a implementação completa de algoritmos como DES seja complexa, uma versão simplificada do Feistel Cipher pode ser usada para gerar identificadores únicos de forma eficiente.

É importante entender que os bits que compõem um número podem ser "convertidos" ou "casted" para qualquer base ou formato. Para obter um identificador alfanumérico de 6 caracteres, podemos simplesmente realizar uma mudança de base. Por exemplo, podemos converter o número gerado pelo Feistel Cipher para Base62, que utiliza os caracteres 0-9, a-z, e A-Z. Em teoria, a Base62 é ideal para esse tipo de aplicação porque é uma representação de qualquer número como uma string alfanúmerica.

Aqui está uma implementação simples:

import math

# Constantes globais para o Feistel Cipher
MULTIPLIER = int(math.sqrt(2) * 1000)
INCREMENT = int(math.pi * 100000)
MODULUS = 2**20 + 3
SCALING_FACTOR = 2**24 - 1  # Fator de escala de 24 bits (16.777.215)

# Base62 charset
BASE62_CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def feistel_cipher(val, rounds=3):
    l1 = (val >> 16) & 0xffff
    r1 = val & 0xffff

    for i in range(rounds):
        l2 = r1
        r2 = l1 ^ int(math.floor(((MULTIPLIER * r1 + INCREMENT) % MODULUS) / MODULUS * SCALING_FACTOR))
        l1 = l2
        r1 = r2

    return (r1 << 16) + l1

def to_base62(num):
    if num == 0:
        return BASE62_CHARS[0]
    
    base62 = []
    while num > 0:
        remainder = num % 62
        base62.append(BASE62_CHARS[remainder])
        num = num // 62
    
    return ''.join(reversed(base62))

def generate_id(index):
    feistel_value = feistel_cipher(index)
    base62_id = to_base62(feistel_value)
    return base62_id.zfill(6)  # Garantir que o ID tenha exatamente 6 caracteres

# Exemplo de uso
print("Index | Feistel Value    | Base62 ID")
print("------+-----------------+----------")

for i in range(-10, 11):
    feistel_value = feistel_cipher(i)
    final_id = generate_id(i)
    print(f"{i:>5} | {feistel_value:>15} | {final_id}")

Aqui está a saída gerada:

Index | Feistel Value    | Base62 ID
------+-----------------+----------
   -10 |      -2028606875 | 02Awtc
    -9 |       -377150308 | 01tvDI
    -8 |      -1826568944 | 02Apzz
    -7 |        -39235198 | 00d7x0
    -6 |      -2325185930 | 031qFc
    -5 |       -800687972 | 01F0e4
    -4 |      -2247551437 | 02WGBa
    -3 |       -822742845 | 01E1Vc
    -2 |       -243871210 | 00xciQ
    -1 |      -1707877051 | 02DcXw
     0 |       2746720850 | 3jvTYx
     1 |        867012857 | 1G8o2V
     2 |        674985276 | 1AP7da
     3 |        889674871 | 1H2OpP
     4 |        745826968 | 1CytVA
     5 |       2939497522 | 3o7SRK
     6 |       1498284863 | 2cihU5
     7 |       2970999551 | 3oyt9r
     8 |       1134483750 | 2C5bNe
     9 |       2670139713 | 3jBcnT
    10 |       1222978124 | 2Ee2aY

A Realidade: Desempenho e Sugestões

Embora isso seja o que desejamos em teoria, essa implementação pode ser muito lenta para uso em produção. A finalidade dessa ilustração é mostrar como o processo funciona, mas em um ambiente real, você provavelmente não gostaria de fazer isso.

Sugestão Real:

Enquanto a solução que discutimos anteriormente serve como uma excelente ilustração de como conceitos como criptografia e conversão de base funcionam, para aplicações práticas, o uso de uma função de hash padrão e truncar o resultado é, na maioria dos casos, a melhor abordagem. Não há necessidade de reinventar a roda — aproveite as ferramentas robustas e otimizadas que já estão à sua disposição.

Além disso, evite adicionar bibliotecas desnecessárias ao seu projeto quando a solução já está disponível no seu ambiente. Mantenha seu código o mais simples possivel e você economizará tempo e recursos no longo prazo.

Realizar a geração de identificadores diretamente no banco de dados garante consistência, performance e reduz a complexidade na aplicação. No Postgres, por exemplo, você pode implementar essa lógica de forma simples usando um campo gerado, semelhante ao que o Git faz ao truncar hashes para gerar identificadores únicos e compactos.

CREATE TABLE my_table (
    id SERIAL PRIMARY KEY,
    unique_id VARCHAR(6) GENERATED ALWAYS AS (
        substring(encode(digest(CAST(id AS TEXT), 'sha256'), 'hex') FOR 6)
    ) STORED
);

Essa solução é simples e direta e mantém seu código fácil sem introduzir nenhuma dependência desnecessária. Ao entender os fundamentos, você pode fazer escolhas mais informadas e eficazes para suas necessidades práticas, utilizando de forma inteligente as ferramentas disponíveis.

1

Excelente explicação, obrigado pelas suas sugestōes. Achei muito interessante o algoritmo de Fesitel Cipher como modelo de estudo.

Eu tinha feito uma tentativa de truncar o valor de um hash a nível de aplicação, algo como:

hashed_token = hashlib.sha256()
short_hashed_token = hashed_token.hexdigest()[:6]

Porém acabei tendo problemas de colisōes, mas não tinha pensado em fazer isso a nivel de banco.

Vou testar fazer dessa forma!

2
1

Obrigado pela sugestão, estou tentando utilizar apenas libs built-ins do python, porém se eu não tiver sucesso dessa forma, com certeza essa lib parece encaixar bem no meu objetivo.

2
1

Estava lendo o github dessa lib e gostei muito que uma dos Use-cases que eles citam é justamente o que estou tentando fazer: url shortening.

No momento estou tentando utilizar apenas libs built-ins do Python, porém, vou dar uma estudada no código fonte do sqids para entender melhor como são feitos esses ids.

Obrigado pela sua sugestão.

2

Use a data/hora atual e um rand ao final. Quando converter para letras, ficará bem pequeno. É bom que é ordenável.

Outra possibilidade é você ter uma tabela de ids. Sempre que requisitar um, marque-o como utilizado. Nunca se repetirá e você poderá acompanhar o andamento pra saber quando estiver perto de acabar e você poderá gerar novos para a tabela.

1

Obrigado pelo seu comentário! Vou fazer um teste com essa ideia de utlizar data/hora com um rand no final, um grande ponto que preciso ver seria as chances de colisōes dos ids gerados dessa forma.

No algoritmo que coloquei na publicação a média tem sido de 3 a 5 colisōes a cada 100 mil ids gerados, então pode ser possível se diminuir ainda mais as chances.

Mas acho que essa técnica também acabaria levando para as mesmas trativas de checar se ja existe o id no banco, fazer um loop até encontrar um que não existe e limitar o número de tentativas pra evitar casos extremos.

Fora isso, eu não tinha pensado na sua segunda ideia em ter uma tabela de ids já populada com as opçōes, farei alguns testes com essa solução.

2

você pode resolver isso com conversão de base.
igual a gente faz de base binaria x decimal x hexadecimal, você pode trabalhar com um "número" de 36 algarismos (os numeros em sí e as letras do alfabeto).

no banco de dados, você continua utilizando os identificador decimal, até porque isso melhorar a indexação.

mas o que você apresenta para o usuario é a conversão desse número.

exemplo:
de 0 a 9, você vai ter 0 a 9 mesmo.
a partir daí que verá a diferença..

o 10 equivale a "a", o 11, "b" e assim por diante.

mas como no seu caso precisará de 6 digitos sempre, pode incluir na conversão uma adição para que id 1 seja equivalente a 100000.
(e quando converter do uid para decimal, não esqueça de subtrair).

assim, não tem risco de duplicar e elimina a necessidade de verificar a disponibilidade no banco de dados.