minúsculo geração ID aleatória de aparência

Question

Eu estou tentando gerar identificações exclusivas para uso em um aplicativo do Google App Engine e gostaria feedback sobre a viabilidade da abordagem que eu estou pensando em usar (perguntas no final). Eu li algumas perguntas sobre este tema, mas eu não me lembro de entrar em toda esta abordagem particular.

Eu gostaria IDs aleatórios-olhando, por exemplo, hashes MD5, mas eu também quero que eles sejam pequenas. Quatro a seis caracteres, ao longo das linhas de tinyurl, seria o ideal. Os IDs será para conteúdo gerado pelo usuário, no contexto da minha candidatura, coisas como perguntas do teste que as pessoas vão estar escrevendo. Não é necessário que os IDs ser aleatório-olhando (É bom se eles se parecem com IDs de série), mas a abordagem que eu estou pensando em usar se presta a isso, por isso não é realmente um problema.

Pessoas familiarizadas com o Google App Engine vai saber que escreve para o armazenamento de dados são particularmente caro e pode resultar em tempos de espera se houver muitos deles ao mesmo grupo de entidades. contadores Sharded são uma abordagem que é frequentemente usado para evitar gravação contenção em um único contador global e as transações falhas que vão com ele.

Junto com a obtenção de IDs curtas e evitando gravação contenção, eu estou tentando evitar o paradoxo de aniversário. Eu gostaria de se preparar para a possibilidade de haver milhões de IDs, mesmo se isso vai ao mar um pouco.

Eu estava pensando em usar um contador Sharded ao longo das seguintes linhas:

• O contador é Sharded em usuários, de modo que haja um caco para cada usuário. Cada objeto de contador tem a sua própria contagem que é específico para um determinado usuário, que é incrementado quando um novo item é criado por esse usuário. A contagem é incrementado independentemente de um item é criado com sucesso.
• A base de um ID é um hash MD5 do seguinte texto: " | "
• O hash MD5 resultante é então truncada, inicialmente para quatro caracteres.
• Um valor único global "comprimento" é mantida. Sempre que as etapas anteriores resultar em uma chave duplicada (se imagina isso vai acontecer muito rapidamente no início), o valor de comprimento será aumentado em um. hashes MD5 para novas IDs agora será truncada em caracteres "comprimento", ao invés de quatro caracteres.
• Eu não quero expor o endereço de e-mail do usuário, o que sugere que um hash de algum tipo seria um bom caminho a percorrer.

As minhas perguntas são: Estou certo em pensar que isso vai em grande parte evitar a gravação de contenção, como resultado de chaves duplicadas e que a tese escrita no campo de comprimento provavelmente não seria um problema, especialmente em comprimentos mais longos? Alguém pode descrever a matemática envolvida aqui? Será que o comprimento aumentar rapidamente para perto do comprimento de um hash MD5, pôr em causa o valor de toda a abordagem? Seria melhor apenas para ir com a cheia (mais) hash MD5, a fim de manter as coisas mais fáceis de manter? Existe alguma coisa que eu estou com vista?

Answer 1

Este algoritmo é inteligente e seria de fato minimizar operações de gravação. Assim, o valor de comprimento convergirá para um equilíbrio entre o comprimento mais curto e ausência de colisões.

Você pode relaxar o constrangimento de ausência de colisão usando estratégias utilizadas nas tabelas de hash. Tente algumas outras identificações exclusivas antes de cair de volta para incrementar o comprimento.

Eu, portanto, sugiro que você adicionar um contador de teste para o fim da cadeia de hash inicializado como 0. Se o ID gerado já é usado, incrementar o contador e repetição até um valor máximo do contador é alcançado depois que você aumentar o comprimento.

Você vai acabar com um uso mais eficiente do seu espaço de endereço ID e incrementos de comprimento muito menos frequentes.

Quanto à sua pergunta sobre o limite de comprimento de MD5 Eu acho que a escolha de MD5 é um exagero. Você realmente não precisa de um (pseudo) Secure Hash criptográfico. O que você precisa é um gerador de bits aleatórios para o qual você pode usar crc32 (ou Adler que é mais rápido). Especialmente se o código está a ser executado em um telefone celular. Para implementar um gerador de pouco aleatória com crc32, preceder um valor 32bits para a cadeia de haxixe e inicialize-o com um valor constante de sua escolha (a semente). Em seguida, calcular o crc32 neste string. Se você precisar de mais bytes, escreva o valor crc32 obtidas nos 32bits em frente à corda e recalcular o crc32. Iterate até que você tenha bits suficientes. Você pode substituir o crc32 com o algoritmo de sua escolha. Isto produz um meio barato e rápido o gerador de bits aleatória, onde a constante inicial é a semente.

Com este algoritmo que você minimizar o número de bits aleatórios gerados e também não têm limite superior de comprimento.

Em relação a codificação, você não especificar as restrições. você pode usar superior e letras minúsculas com os dígitos? Seu exemplo usa um alfabeto de 36 valores ASCII diferentes. Depois de ter o gerador de números pseudo-aleatório descrito acima que pode gerar o maior número de bytes conforme desejado, basta definir comprimento para ser o número de letras do seu ID e escolher a próxima letra com um modulo do próximo byte aleatória. Você saberá então exatamente quantos bytes para gerar de uma vez e gerar o ID é trivial.

Answer 2

Como sobre algo como isto:

1. Se você quiser 4 teclas de caracteres usando a-zA-Z0-9, então você teria: 62 ^ 4 => 14 milhões de valores possíveis.

2. Break isso em partições N: 0000 ... 1000 1001 ... 2000 ..., ZZAA ... ZZZZ

   Cada partição é representada por uma entidade com: ID de início ID de final id atual

Agora, para gerar um ID:

1. escolher aleatoriamente um partição. Use a chave de ignição para cada partição como uma chave. Iniciar Transação:
2. get_or_create () que entidade partição.
3. Se o ID atual == id fim, vá para a etapa 1
4. save corrente id
5. id atual incremento por um Transaction End

Utilize o ID atual que foi salvo como o seu id.

Se você pegar N como 140 você cada partição teria 100.000 valores. Isso permitiria que algumas inserções concorrentes, limitando o número de tentativas devido a escolher uma partição "vazio".

Você pode precisar de pensar sobre isso mais. Especialmente, como vai lidar com o caso quando você precisar se deslocar para 5 ou 6 teclas numéricas?

-Dave

Answer 3

Apenas para adicionar alguns números concretos para a pergunta acima, eu tenho implementado um pequeno programa para gerar ids ao longo das linhas mencionadas na pergunta, e estes foram os resultados de uma das pistas de teste:

Length     Count      MD5             Base 62
4          400        3d0e            446
5          925        4fc04           1Myi
6          2434       0e9368          40V6
7          29155      e406d96         GBFiA
8          130615     7ba787c8        2GOiCm
9          403040     75525d163       YNKjL9
10         1302992    e1b3581f52      H47JAIs
Total:     1869561

Cada vez que o comprimento do hash aumentada, isto foi devido a uma colisão, de modo que havia seis colisões neste exemplo. A contagem é o número de chaves de um determinado comprimento que foram gerados antes de uma colisão. Os shows coluna MD5 a última chave truncada que foi adicionada com êxito antes de haver um erro de chave duplicada. A coluna nas mostras de extrema-direita a chave na base 62 (se eu tenho feito a conversão corretamente).

Parece que mais e mais chaves estão sendo geradas com cada personagem adicional, que é o que você pode imaginar. Estou esperançoso que esta abordagem irá escalar para conteúdo gerado pelo usuário.

Para quem está interessado, aqui está como eu tenho a representação base 62 para a última coluna:

def base_62_encode(input):
    "Inspired by code at http://en.wikipedia.org/wiki/Base_36."
    CLIST="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    rv = ""
    while input != 0:
        rv = CLIST[input % 62] + str(rv)
        input /= 62
    return rv

base62_id = base_62_encode(long(truncated_hash, 16))

---

(Adicionado mais tarde:)

Aqui está uma classe que cuida de várias coisas relacionadas com a geração desses IDs no contexto do Google App Engine. Por padrão, as chaves que são gerados por esta classe não são puramente base 62, uma vez que o primeiro caractere de um nome de chave GAE deve ser alfabético. Essa exigência foi abordada aqui usando base 52 para o primeiro caractere.

A base principal pode ser alterado para algo diferente de 62, alterando o valor "clist" que foi passado para (ou omitido de) o construtor. Um pode querer remover caracteres que são fáceis de se misturar, por exemplo, "1", "l", "i", etc.

Uso:

keygen = LengthBackoffIdGenerator(SomeClass, initial_length=5)
small_id, modified = keygen.small_id(seed_value_from_sharded_counter)

Aqui é a classe:

class LengthBackoffIdGenerator(object):
    """Class to generate ids along the lines of tinyurl.

    By default, ids begin with a alphabetic character.  Each id that is created is checked against previous ones
    to ensure uniqueness.  When a duplicate is generated, the length of the seed value used is increased by one
    character.

    Ids become gradually longer over time while remaining relatively short, and there are very few retries in 
    relation to the number of keys generated.
    """
    ids = set()

    def __init__(self, cls, clist='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', alpha_first=False,
            initial_length=5, check_db=False):
        self.clist = clist
        self.alpha_first = alpha_first
        if self.alpha_first:
            import re
            alpha_list = re.sub(r'\d', '', clist)
            if len(alpha_list) < 1:
                raise Exception, 'At least one non-numeric character is required.'
            self.alpha_list = alpha_list
        self.cls = cls
        self.length = initial_length
        self.check_db = check_db

    def divide_long_and_convert(self, radix, clist, input, rv):
        "Inspired by code at http://en.wikipedia.org/wiki/Base_36."
        rv += clist[input % radix]
        input /= radix
        return (input, rv)

    def convert_long(self, input):
        rv = ""
        if self.alpha_first:
            input, rv = self.divide_long_and_convert(len(self.alpha_list), self.alpha_list, input, rv)
        while input != 0:
            input, rv = self.divide_long_and_convert(len(self.clist),      self.clist,      input, rv)
        return rv

    def hash_truncate_and_binify(self, input, length):
        """Compute the MD5 hash of an input string, truncate it and convert it to a long.

        input  - A seed value.
        length - The length to truncate the MD5 hash to.
        """
        from assessment.core.functions import md5_hash
        input = md5_hash(input)[0:length]
        return long(input, 16)

    def _small_id(self, input):
        """Create an ID that looks similar to a tinyurl ID.

        The first letter of the ID will be non-numeric by default.
        """
        return self.convert_long(self.hash_truncate_and_binify(input, self.length))

    def small_id(self, seed):
        key_name = self._small_id(seed)
        increased_length = False
        if self.check_db and not self.cls.get_by_key_name(key_name) is None:
            self.ids.add(key_name)
        if key_name in self.ids:
            self.length += 1
            increased_length = True
            key_name = self._small_id(seed)
        self.ids.add(key_name)
        return (key_name, increased_length)