Encurtando/refazendo UUIDs

Question

em primeiro lugar, quero garantir que estou ciente do fato de que refazer é um assunto sensato.No entanto, gostaria de ouvir algumas de suas opiniões, qual abordagem você adotaria aqui.

Estou construindo um aplicativo distribuído, onde os nós criam remotamente entidades identificadas por um UUID.Eventualmente, todas as entidades deverão ser reunidas em um nó de drenagem dedicado, que armazena todas as entidades usando esses UUIDs.

Agora quero criar identificadores adicionais, que sejam mais úteis para usuários humanos.A codificação Base64 dos UUIDs ainda criaria IDs com 22 caracteres, o que não é apropriado para uso humano.Portanto, preciso de algo como serviços de encurtamento de URL.Aplicar funções bijetivas não ajudará, porque não reduzirá o valor da informação.Claro, estou ciente de que preciso perder informações para encurtar o id.E também estou ciente de que qualquer redução de informação de um hash aumentará a probabilidade de colisão.Não sei qual a forma mais adequada de reduzir informações para criar ids mais curtos para humanos.

Aqui estão alguns pré-requisitos:Fornecerei a capacidade de mapear {UUID, ID abreviado} por meio do meu armazenamento de dados.Eu ainda preferiria uma solução não centralizada.Provavelmente nunca precisarei de mais do que um milhão de IDs (~ 2 ^ 20) no total.

Aqui estão os pensamentos que tive até agora:

• IDs incrementados automaticamente: Se eu usasse algum tipo de ID incrementado automaticamente, poderia transferir esse ID para uma string ofuscada e distribuí-lo.Esta seria a abordagem mais fácil e, desde que haja poucas teclas disponíveis, as teclas não serão muito longas.No entanto, eu teria que introduzir uma entidade centralizada que realmente não quero.
• Encurte o UUID: Eu poderia pegar alguns dos bits do uuid original de 128 bits.Então devo levar pelo menos em consideração a versão do UUID.Ou há mais alguma coisa errada nisso?
• Refazendo o UUID: Eu poderia aplicar um segundo algoritmo de hash no meu UUID inicial e armazenar o mapeamento.

Existem outras abordagens?O que é favorável?

Desde já, obrigado!

Answer 1

1) Para encurtar o UUID, você pode simplesmente xorar a metade superior com a parte inferior (e repetir até que seja curta o suficiente para você). Isso preservará as características de distribuição. Como qualquer solução que reduz a saída, aumentará a possibilidade de colisão devido ao paradoxo de aniversário

2) XOR equivale a um hash trivial, mas como não é necessária uma mistura adicional, tudo bem. Você pode usar um CRC ou hash não -cropográfico no seu UUID, mas não acredito que seja alguma melhoria.

3) Se você está disposto a aceitar algum Gerenciamento central, não precisa ser doloroso. Uma autoridade central pode distribuir blocos de tamanho médio de espaço de endereço para cada cliente, e o cliente pode iterar através desse sub-range ao atribuir IDs. Isso garante que não há colisões, mas também evita uma viagem de ida e volta para cada ID. Uma maneira de fazer isso seria usar um número inteiro de 32 bits para o ID, distribuindo um bloco de 16 bits por vez. Em outras palavras, o primeiro cliente recebe 0001, o que permite 00010000 a 0001ffff.

4) Você pode inserir no banco de dados com um UUID, mas também possui um campo de identidade. Isso forneceria um ID exclusivo alternativo e mais compacto, que pode ser limitado a um Int de 32 bits.

Answer 2

Você já pensou em usar uma abordagem de alias externo, onde você escolhe um dicionário de termos amigáveis ​​e os usa para tornar (partes do) o UUID mais legível:

de305d54-75b4-431b-adb2-eb6b9e546013

Usar um dicionário de 65.536 palavras poderia se tornar:

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

É improvável que os usuários vejam uma colisão de hash mental (zebra ocorrendo duas vezes) com esses nomes legíveis por humanos e seu banco de dados não aumente de tamanho.A tradução é bijetiva e puramente UI.

Answer 3

Apenas algumas coisas que surgem na mente:

Qual é o seu caso de uso? Se sua preocupação é que você gera IDs de maneira distribuída, uma solução é atribuir a cada máquina It Id Id exclusiva e usá -lo como prefixo ou sufixo em seus IDs.

Isso realmente não ajuda se, ao não ter uma entidade central, você não quer dizer nada que acompanha o IDS, mesmo localmente. Você pode emprestar uma página da própria UUID e usar o tempo do sistema em conjunto com o ID da máquina atribuído como acima. Isso o levaria a 64 bits + qualquer que fosse o seu ID da sua máquina. Basicamente, este é o esquema V1 UUID, exceto que você está usando algo mais curto que o endereço MAC para o ID da máquina. Dado que você sabe que pode começar em datas> = 12 de fevereiro de 2010, você poderá diminuir ainda mais.

Confira a entrada da Wikipedia UUID, se você ainda não o fez, você pode ter uma ou duas idéias de lá sobre como construir a sua.

Answer 4

Aqui está um algoritmo simples de hash que escrevi. Você pode usar isso ... você pode alterar facilmente os mapeamentos de entrada e saída e o comprimento do hash para trocar a probabilidade de legibilidade versus colisão.

Esse algoritmo não foi projetado para ser seguro ou eficiente, mas deve fazer o truque.

public class HashTools {

  final static String inputMapping = "0123456789ABCDEF";

  final static String[] outputMapping = new String[] {
      "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H",
      "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"
  };

  /* Input: String - containing mostly letters / numbers
   * Output: <hashLength> String using 0-9,A-Z encoding
   */
  public static String simpleHash(String str, int hashLength) {
    StringBuilder hashStr = new StringBuilder(hashLength);
    String strUpper = str.toUpperCase();
    int[] hash = new int[hashLength];

    int i, j, num;
    for (i = 0; i < strUpper.length(); i++) {
      char strChar = strUpper.charAt(i);
      num = mapCharToInt(strChar);

      j = i % hashLength;
      hash[j] += num;
    }

    for (i = 0; i < hashLength; i++) {
      hashStr.append(mapIntToHashChar(hash[i]));
    }

    return hashStr.toString();
  }

  private static int mapCharToInt(char hexChar) {
    return inputMapping.indexOf(hexChar);
  }

  private static String mapIntToHashChar(int num) {
    return outputMapping[num % outputMapping.length];
  }
}