hash - UUID de acortamiento/reajuste

url-shortener

Question

en primer lugar, quiero asegurarme de que soy consciente del hecho de que el reafilado es un tema sensato. Sin embargo, me gustaría escuchar algunas de sus opiniones, qué enfoque tomaría aquí.

Estoy construyendo una aplicación distribuida, donde los nodos crean remotamente entidades identificadas por un UUID. Eventualmente, todas las entidades deberían reunirse en un nodo de drenaje dedicado, que almacena todas las entidades mediante el uso de estos UUID.

Ahora quiero crear identificadores adicionales, que son más útiles para los usuarios humanos. La codificación de Base64 de los UUID aún crearía ID con 22 caracteres, lo cual no es apropiado para el uso humano. Entonces necesito algo como servicios de reducción de URL. La aplicación de funciones biyectivas no ayudará, ya que no reducirá el valor de la información. Por supuesto, soy consciente de que necesito perder información para acortar la identificación. Y también soy consciente de que cualquier reducción de información de un hash aumentará la probabilidad de colisión. Estoy atascado, ¿cuál es la forma más adecuada de reducir la información para crear identificaciones más cortas para los humanos?

Aquí hay algunos requisitos previos: proporcionaré la capacidad de mapear {UUID, ID abreviado} a través de mi almacenamiento de datos. Todavía preferiría una solución no centralizada. Probablemente nunca más necesite más de un millón de ID (~ 2 ^ 20) en total.

Aquí están los pensamientos que surgieron hasta ahora:

• Auto incrementó los ID: si usaría algún tipo de ID autoincrementado, podría transferir este ID a una cadena ofuscada y pasar esto. Este sería el enfoque más fácil, y mientras haya pocas teclas, las claves no serían muy largas. Sin embargo, tendría que presentar una entidad centralizada que realmente no quiero.
• Acorte el UUID: podría tomar algunos de los bits del uuid original de 128 bits. Entonces debería tener al menos en cuenta la versión del UUID. ¿O hay algo más malo con esto?
• Reposicionando el UUID: podría aplicar un segundo algoritmo hash en mi UUID inicial y almacenar el mapeo.

¿Hay algún otro enfoque? ¿Qué es favorable?

¡Gracias por adelantado!

Answer 1

¿Ha considerado utilizar un enfoque de alias externo, donde selecciona un diccionario de términos amigables para el ser humano y los usa para hacer (partes de) el UUID más legible:

de305d54-75b4-431b-adb2-eb6b9e546013

Usar un diccionario de 65536 palabras podría convertirse en:

de305d54-zebra-stackoverflow-extraneous-eb6b9e546013

Es poco probable que los usuarios vean una colisión mental hash (cebra que ocurre dos veces) con estos nombres legibles por humanos y su base de datos no crece de tamaño. La traducción es biyectiva y puramente UI.

Answer 2

1) Para acortar el UUID, puede simplemente XOR la ​​mitad superior con la parte inferior (y repita hasta que sea lo suficientemente corto para usted). Esto preservará las características de distribución. Al igual que cualquier solución que acorte la salida, aumentará la posibilidad de colisión debido a la paradoja del cumpleaños

2) XOR equivale a un hash trivial, pero como no se necesita una mezcla adicional, está bien. Puede usar un CRC o hash no criptográfico en su UUID, pero no creo que sea una mejora.

3) Si está dispuesto a aceptar una gestión central, no tiene por qué ser doloroso. Una autoridad central puede repartir bloques de espacio de direcciones de tamaño mediano a cada cliente, luego el cliente puede iterar a través de ese subrango al asignar identificadores. Esto garantiza que no haya colisiones, pero también evita un viaje de ida y vuelta para cada identificación. Una forma de hacerlo sería usar un entero de 32 bits para la ID, repartiendo un bloque de 16 bits a la vez. En otras palabras, el primer cliente se entrega 0001, que permite 00010000 a 0001FFFF.

4) Puede insertar en la base de datos con un UUID, pero también tiene un campo de identidad. Esto proporcionaría una ID única alternativa más compacta, que puede limitarse a una int de 32 bits.

Answer 3

Aquí hay un algoritmo de hash simple que escribí. Podrías usar esto ... puedes cambiar fácilmente las asignaciones de entrada y salida, y la longitud del hash para intercambiar la legibilidad frente a la probabilidad de colisión.

Este algoritmo no está diseñado para ser seguro o eficiente, pero debería ser el truco.

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];
  }
}

Answer 4

Solo un par de cosas que te vienen a la mente:

¿Cuál es tu caso de uso? Si le preocupa que genere identificadores de forma distribuida, una solución es asignar a cada máquina su propia identificación interna única y usarla como un prefijo o sufijo en sus identificadores.

Esto realmente no ayuda si al no tener una entidad central no significa nada que haga un seguimiento de los identificadores, incluso a nivel local. Puede tomar prestada una página del UUID y usar la hora del sistema junto con la identificación de la máquina asignada como se indicó anteriormente. Esto te reduciría a 64bits + cualquier tamaño que tu identificación de la máquina fuera. Básicamente, este es el esquema UUID V1, excepto que está utilizando algo más corto que la dirección MAC para la identificación de la máquina. Dado que sabe que puede comenzar en fechas> = 12 de febrero de 2010, es posible que pueda acortar aún más.

Echa un vistazo a la entrada UUID de wikipedia si aún no lo has hecho, puedes obtener una idea o dos de allí sobre cómo construir la tuya propia.