¿Cómo creo un acortador de URL?

Quiero crear un servicio de acortador de URL donde pueda escribir una URL larga en un campo de entrada y el servicio acorta la URL a " http://www.example.org/abcdef".

En lugar de " abcdef" puede haber cualquier otra cadena que contenga seis caracteres a-z, A-Z and 0-9. Eso hace que 56 ~ 57 mil millones de cadenas posibles.

Mi acercamiento:

Tengo una tabla de base de datos con tres columnas:

1. id, entero, incremento automático
2. long, string, la URL larga que ingresó el usuario
3. short, string, la URL acortada (o solo los seis caracteres)

Luego insertaría la URL larga en la tabla. Luego seleccionaría el valor de incremento automático para " id" y crearía un hash de él. Este hash se debe insertar como " short". Pero, ¿qué tipo de hash debo construir? Algoritmos hash como MD5 crean cadenas demasiado largas. No uso estos algoritmos, creo. Un algoritmo de construcción propia también funcionará.

Mi idea:

Para " http://www.google.de/" obtengo la identificación de incremento automático 239472. Luego hago los siguientes pasos:

short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.

Eso podría repetirse hasta que el número ya no sea divisible. ¿Crees que este es un buen enfoque? Tienes una mejor idea?

_{Debido al continuo interés en este tema, he publicado una solución eficiente para GitHub , con implementaciones para JavaScript , PHP , Python y Java . Agregue sus soluciones si lo desea :)}

Continuaría con tu enfoque de "convertir número a cadena". Sin embargo, se dará cuenta de que su algoritmo propuesto falla si su ID es primo y mayor que 52 .

Antecedentes teóricos

Necesita una función biyectiva f . Esto es necesario para que pueda encontrar una función inversa g ('abc') = 123 para su función f (123) = 'abc' . Esto significa:

• No debe haber x1, x2 (con x1 ≠ x2) que hará que f (x1) = f (x2) ,
• y por cada y debes poder encontrar una x para que f (x) = y .

Cómo convertir la ID a una URL acortada

1. Piensa en un alfabeto que queremos usar. En tu caso, eso es [a-zA-Z0-9]. Contiene 62 letras .

2. Tome una clave numérica única y autogenerada (el autoincrementado idde una tabla MySQL, por ejemplo).

   Para este ejemplo, usaré 125 ₁₀ (125 con una base de 10).

3. Ahora tienes que convertir 125 ₁₀ a X ₆₂ (base 62).

   125 ₁₀ = 2 × 62 ¹ + 1 × 62 ⁰ =[2,1]

   Esto requiere el uso de división entera y módulo. Un ejemplo de pseudocódigo:

   digits = []
   
   while num > 0
     remainder = modulo(num, 62)
     digits.push(remainder)
     num = divide(num, 62)
   
   digits = digits.reverse
   

   Ahora asigna los índices 2 y 1 a tu alfabeto. Así es como podría verse su mapeo (con una matriz, por ejemplo):

   0  → a
   1  → b
   ...
   25 → z
   ...
   52 → 0
   61 → 9
   

   Con 2 → c y 1 → b, recibirá cb ₆₂ como la URL acortada.

   http://shor.ty/cb
   

Cómo resolver una URL acortada a la ID inicial

Lo contrario es aún más fácil. Simplemente haces una búsqueda inversa en tu alfabeto.

1. e9a ₆₂ se resolverá como "4ª, 61ª y 0ª letra del alfabeto".

   e9a ₆₂ = [4,61,0]= 4 × 62 ² + 61 × 62 ¹ + 0 × 62 ⁰ = 19158 ₁₀

2. Ahora encuentre su registro de base de datos WHERE id = 19158y realice la redirección.

Implementaciones de ejemplo (proporcionadas por comentaristas)

• C ++
• Pitón
• Rubí
• Haskell
• C#
• CoffeeScript
• Perl

¿Por qué querrías usar un hash?

Simplemente puede usar una traducción simple de su valor de incremento automático a un valor alfanumérico. Puede hacerlo fácilmente utilizando alguna conversión base. Digamos que el espacio de caracteres (AZ, az, 0-9, etc.) tiene 40 caracteres, convierta la identificación a un número base 40 y use los caracteres como dígitos.

public class UrlShortener {
    private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int    BASE     = ALPHABET.length();

    public static String encode(int num) {
        StringBuilder sb = new StringBuilder();
        while ( num > 0 ) {
            sb.append( ALPHABET.charAt( num % BASE ) );
            num /= BASE;
        }
        return sb.reverse().toString();   
    }

    public static int decode(String str) {
        int num = 0;
        for ( int i = 0; i < str.length(); i++ )
            num = num * BASE + ALPHABET.indexOf(str.charAt(i));
        return num;
    }   
}

No es una respuesta a su pregunta, pero no usaría URL acortadas que distingan entre mayúsculas y minúsculas. Son difíciles de recordar, generalmente ilegibles (muchas fuentes representan 1 y 1, 0 y O y otros caracteres muy similares a los que son casi imposibles de diferenciar) y francamente propensos a errores. Intente usar minúsculas o mayúsculas solamente.

Además, intente tener un formato donde mezcle los números y caracteres en una forma predefinida. Hay estudios que muestran que las personas tienden a recordar un formulario mejor que otros (piense en los números de teléfono, donde los números se agrupan en un formulario específico). Pruebe algo como num-char-char-num-char-char. Sé que esto reducirá las combinaciones, especialmente si no tiene mayúsculas y minúsculas, pero sería más útil y, por lo tanto, útil.

Mi enfoque: tomar la identificación de la base de datos, luego codificarla en Base36 . NO usaría letras mayúsculas y minúsculas, porque eso hace que transmitir esas URL por teléfono sea una pesadilla, pero por supuesto, podría extender fácilmente la función para que sea un decodificador / base 62.

Aquí está mi clase PHP 5.

<?php
class Bijective
{
    public $dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public function __construct()
    {
        $this->dictionary = str_split($this->dictionary);
    }

    public function encode($i)
    {
        if ($i == 0)
        return $this->dictionary[0];

        $result = '';
        $base = count($this->dictionary);

        while ($i > 0)
        {
            $result[] = $this->dictionary[($i % $base)];
            $i = floor($i / $base);
        }

        $result = array_reverse($result);

        return join("", $result);
    }

    public function decode($input)
    {
        $i = 0;
        $base = count($this->dictionary);

        $input = str_split($input);

        foreach($input as $char)
        {
            $pos = array_search($char, $this->dictionary);

            $i = $i * $base + $pos;
        }

        return $i;
    }
}

Una solución Node.js y MongoDB

Dado que conocemos el formato que utiliza MongoDB para crear un nuevo ObjectId con 12 bytes.

• un valor de 4 bytes que representa los segundos desde la época de Unix,
• un identificador de máquina de 3 bytes,
• una identificación de proceso de 2 bytes
• un contador de 3 bytes (en su máquina), comenzando con un valor aleatorio.

Ejemplo (elijo una secuencia aleatoria) a1b2c3d4e5f6g7h8i9j1k2l3

• a1b2c3d4 representa los segundos desde la época de Unix,
• 4e5f6g7 representa el identificador de la máquina,
• h8i9 representa la identificación del proceso
• j1k2l3 representa el contador, comenzando con un valor aleatorio.

Dado que el contador será único si almacenamos los datos en la misma máquina, podemos obtenerlo sin dudas de que se duplicará.

Entonces, la URL corta será el contador y aquí hay un fragmento de código que supone que su servidor se está ejecutando correctamente.

const mongoose = require('mongoose');
const Schema = mongoose.Schema;

// Create a schema
const shortUrl = new Schema({
    long_url: { type: String, required: true },
    short_url: { type: String, required: true, unique: true },
  });
const ShortUrl = mongoose.model('ShortUrl', shortUrl);

// The user can request to get a short URL by providing a long URL using a form

app.post('/shorten', function(req ,res){
    // Create a new shortUrl */
    // The submit form has an input with longURL as its name attribute.
    const longUrl = req.body["longURL"];
    const newUrl = ShortUrl({
        long_url : longUrl,
        short_url : "",
    });
    const shortUrl = newUrl._id.toString().slice(-6);
    newUrl.short_url = shortUrl;
    console.log(newUrl);
    newUrl.save(function(err){
        console.log("the new URL is added");
    })
});

Versión C #:

public class UrlShortener 
{
    private static String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static int    BASE     = 62;

    public static String encode(int num)
    {
        StringBuilder sb = new StringBuilder();

        while ( num > 0 )
        {
            sb.Append( ALPHABET[( num % BASE )] );
            num /= BASE;
        }

        StringBuilder builder = new StringBuilder();
        for (int i = sb.Length - 1; i >= 0; i--)
        {
            builder.Append(sb[i]);
        }
        return builder.ToString(); 
    }

    public static int decode(String str)
    {
        int num = 0;

        for ( int i = 0, len = str.Length; i < len; i++ )
        {
            num = num * BASE + ALPHABET.IndexOf( str[(i)] ); 
        }

        return num;
    }   
}

Puede hacer un hash de la URL completa, pero si solo quiere acortar la identificación, haga lo que sugirió Marcel. Escribí esta implementación de Python:

https://gist.github.com/778542

Sigo incrementando una secuencia de enteros por dominio en la base de datos y uso Hashids para codificar el entero en una ruta URL.

static hashids = Hashids(salt = "my app rocks", minSize = 6)

Ejecuté un script para ver cuánto tiempo lleva hasta que agota la longitud del personaje. Para seis caracteres puede hacer164,916,224 enlaces y luego sube a siete caracteres. Bitly usa siete caracteres. Menos de cinco personajes me parecen extraños.

Los hashids pueden decodificar la ruta de la URL de regreso a un entero, pero una solución más simple es usar el enlace corto completosho.rt/ka8ds3 como clave principal.

Aquí está el concepto completo:

function addDomain(domain) {
    table("domains").insert("domain", domain, "seq", 0)
}

function addURL(domain, longURL) {
    seq = table("domains").where("domain = ?", domain).increment("seq")
    shortURL = domain + "/" + hashids.encode(seq)
    table("links").insert("short", shortURL, "long", longURL)
    return shortURL
}

// GET /:hashcode
function handleRequest(req, res) {
    shortURL = req.host + "/" + req.param("hashcode")
    longURL = table("links").where("short = ?", shortURL).get("long")
    res.redirect(301, longURL)
}

Si no quieres reinventar la rueda ... http://lilurl.sourceforge.net/

// simple approach

$original_id = 56789;

$shortened_id = base_convert($original_id, 10, 36);

$un_shortened_id = base_convert($shortened_id, 36, 10);

alphabet = map(chr, range(97,123)+range(65,91)) + map(str,range(0,10))

def lookup(k, a=alphabet):
    if type(k) == int:
        return a[k]
    elif type(k) == str:
        return a.index(k)


def encode(i, a=alphabet):
    '''Takes an integer and returns it in the given base with mappings for upper/lower case letters and numbers 0-9.'''
    try:
        i = int(i)
    except Exception:
        raise TypeError("Input must be an integer.")

    def incode(i=i, p=1, a=a):
        # Here to protect p.                                                                                                                                                                                                                
        if i <= 61:
            return lookup(i)

        else:
            pval = pow(62,p)
            nval = i/pval
            remainder = i % pval
            if nval <= 61:
                return lookup(nval) + incode(i % pval)
            else:
                return incode(i, p+1)

    return incode()



def decode(s, a=alphabet):
    '''Takes a base 62 string in our alphabet and returns it in base10.'''
    try:
        s = str(s)
    except Exception:
        raise TypeError("Input must be a string.")

    return sum([lookup(i) * pow(62,p) for p,i in enumerate(list(reversed(s)))])a

Aquí está mi versión para quien la necesite.

Eche un vistazo a https://hashids.org/ es de código abierto y en muchos idiomas.

Su página describe algunas de las trampas de otros enfoques.

¿Por qué no solo traducir su identificación a una cadena? Solo necesita una función que asigne un dígito entre, digamos, 0 y 61 a una sola letra (mayúscula / minúscula) o dígito. Luego aplique esto para crear, digamos, códigos de 4 letras, y tendrá 14.7 millones de URL cubiertas.

Aquí hay una función de codificación de URL decente para PHP ...

// From http://snipplr.com/view/22246/base62-encode--decode/
private function base_encode($val, $base=62, $chars='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ') {
    $str = '';
    do {
        $i = fmod($val, $base);
        $str = $chars[$i] . $str;
        $val = ($val - $i) / $base;
    } while($val > 0);
    return $str;
}

No sé si alguien encontrará esto útil: es más un método de 'hack n slash', pero es simple y funciona bien si solo desea caracteres específicos.

$dictionary = "abcdfghjklmnpqrstvwxyz23456789";
$dictionary = str_split($dictionary);

// Encode
$str_id = '';
$base = count($dictionary);

while($id > 0) {
    $rem = $id % $base;
    $id = ($id - $rem) / $base;
    $str_id .= $dictionary[$rem];
}


// Decode
$id_ar = str_split($str_id);
$id = 0;

for($i = count($id_ar); $i > 0; $i--) {
    $id += array_search($id_ar[$i-1], $dictionary) * pow($base, $i - 1);
} 

¿Omitiste O, 0 e i a propósito?

Acabo de crear una clase PHP basada en la solución de Ryan.

<?php

    $shorty = new App_Shorty();

    echo 'ID: ' . 1000;
    echo '<br/> Short link: ' . $shorty->encode(1000);
    echo '<br/> Decoded Short Link: ' . $shorty->decode($shorty->encode(1000));


    /**
     * A nice shorting class based on Ryan Charmley's suggestion see the link on Stack Overflow below.
     * @author Svetoslav Marinov (Slavi) | http://WebWeb.ca
     * @see http://stackoverflow.com/questions/742013/how-to-code-a-url-shortener/10386945#10386945
     */
    class App_Shorty {
        /**
         * Explicitly omitted: i, o, 1, 0 because they are confusing. Also use only lowercase ... as
         * dictating this over the phone might be tough.
         * @var string
         */
        private $dictionary = "abcdfghjklmnpqrstvwxyz23456789";
        private $dictionary_array = array();

        public function __construct() {
            $this->dictionary_array = str_split($this->dictionary);
        }

        /**
         * Gets ID and converts it into a string.
         * @param int $id
         */
        public function encode($id) {
            $str_id = '';
            $base = count($this->dictionary_array);

            while ($id > 0) {
                $rem = $id % $base;
                $id = ($id - $rem) / $base;
                $str_id .= $this->dictionary_array[$rem];
            }

            return $str_id;
        }

        /**
         * Converts /abc into an integer ID
         * @param string
         * @return int $id
         */
        public function decode($str_id) {
            $id = 0;
            $id_ar = str_split($str_id);
            $base = count($this->dictionary_array);

            for ($i = count($id_ar); $i > 0; $i--) {
                $id += array_search($id_ar[$i - 1], $this->dictionary_array) * pow($base, $i - 1);
            }
            return $id;
        }
    }
?>

Esto es lo que uso:

# Generate a [0-9a-zA-Z] string
ALPHABET = map(str,range(0, 10)) + map(chr, range(97, 123) + range(65, 91))

def encode_id(id_number, alphabet=ALPHABET):
    """Convert an integer to a string."""
    if id_number == 0:
        return alphabet[0]

    alphabet_len = len(alphabet) # Cache

    result = ''
    while id_number > 0:
        id_number, mod = divmod(id_number, alphabet_len)
        result = alphabet[mod] + result

    return result

def decode_id(id_string, alphabet=ALPHABET):
    """Convert a string to an integer."""
    alphabet_len = len(alphabet) # Cache
    return sum([alphabet.index(char) * pow(alphabet_len, power) for power, char in enumerate(reversed(id_string))])

Es muy rápido y puede tomar enteros largos.

Para un proyecto similar, para obtener una nueva clave, hago una función de envoltura alrededor de un generador de cadenas al azar que llama al generador hasta que obtengo una cadena que aún no se ha utilizado en mi tabla hash. Este método se ralentizará una vez que su espacio de nombres comience a llenarse, pero como ha dicho, incluso con solo 6 caracteres, tiene mucho espacio de nombres para trabajar.

Tengo una variante del problema, ya que almaceno páginas web de muchos autores diferentes y necesito evitar el descubrimiento de páginas por conjeturas. Entonces, mis URL cortas agregan un par de dígitos adicionales a la cadena Base-62 para el número de página. Estos dígitos adicionales se generan a partir de la información en el registro de la página y aseguran que solo 1 de cada 3844 URL sean válidos (suponiendo Base-62 de 2 dígitos). Puede ver una descripción general en http://mgscan.com/MBWL .

Muy buena respuesta, he creado una implementación de Golang de bjf:

package bjf

import (
    "math"
    "strings"
    "strconv"
)

const alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

func Encode(num string) string {
    n, _ := strconv.ParseUint(num, 10, 64)
    t := make([]byte, 0)

    /* Special case */
    if n == 0 {
        return string(alphabet[0])
    }

    /* Map */
    for n > 0 {
        r := n % uint64(len(alphabet))
        t = append(t, alphabet[r])
        n = n / uint64(len(alphabet))
    }

    /* Reverse */
    for i, j := 0, len(t) - 1; i < j; i, j = i + 1, j - 1 {
        t[i], t[j] = t[j], t[i]
    }

    return string(t)
}

func Decode(token string) int {
    r := int(0)
    p := float64(len(token)) - 1

    for i := 0; i < len(token); i++ {
        r += strings.Index(alphabet, string(token[i])) * int(math.Pow(float64(len(alphabet)), p))
        p--
    }

    return r
}

Alojado en github: https://github.com/xor-gate/go-bjf

/**
 * <p>
 *     Integer to character and vice-versa
 * </p>
 *  
 */
public class TinyUrl {

    private final String characterMap = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private final int charBase = characterMap.length();

    public String covertToCharacter(int num){
        StringBuilder sb = new StringBuilder();

        while (num > 0){
            sb.append(characterMap.charAt(num % charBase));
            num /= charBase;
        }

        return sb.reverse().toString();
    }

    public int covertToInteger(String str){
        int num = 0;
        for(int i = 0 ; i< str.length(); i++)
            num += characterMap.indexOf(str.charAt(i)) * Math.pow(charBase , (str.length() - (i + 1)));

        return num;
    }
}

class TinyUrlTest{

    public static void main(String[] args) {
        TinyUrl tinyUrl = new TinyUrl();
        int num = 122312215;
        String url = tinyUrl.covertToCharacter(num);
        System.out.println("Tiny url:  " + url);
        System.out.println("Id: " + tinyUrl.covertToInteger(url));
    }
}

Implementación en Scala:

class Encoder(alphabet: String) extends (Long => String) {

  val Base = alphabet.size

  override def apply(number: Long) = {
    def encode(current: Long): List[Int] = {
      if (current == 0) Nil
      else (current % Base).toInt :: encode(current / Base)
    }
    encode(number).reverse
      .map(current => alphabet.charAt(current)).mkString
  }
}

class Decoder(alphabet: String) extends (String => Long) {

  val Base = alphabet.size

  override def apply(string: String) = {
    def decode(current: Long, encodedPart: String): Long = {
      if (encodedPart.size == 0) current
      else decode(current * Base + alphabet.indexOf(encodedPart.head),encodedPart.tail)
    }
    decode(0,string)
  }
}

Ejemplo de prueba con la prueba Scala:

import org.scalatest.{FlatSpec, Matchers}

class DecoderAndEncoderTest extends FlatSpec with Matchers {

  val Alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

  "A number with base 10" should "be correctly encoded into base 62 string" in {
    val encoder = new Encoder(Alphabet)
    encoder(127) should be ("cd")
    encoder(543513414) should be ("KWGPy")
  }

  "A base 62 string" should "be correctly decoded into a number with base 10" in {
    val decoder = new Decoder(Alphabet)
    decoder("cd") should be (127)
    decoder("KWGPy") should be (543513414)
  }

}

Función basada en la clase Xeoncross

function shortly($input){
$dictionary = ['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','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','0','1','2','3','4','5','6','7','8','9'];
if($input===0)
    return $dictionary[0];
$base = count($dictionary);
if(is_numeric($input)){
    $result = [];
    while($input > 0){
        $result[] = $dictionary[($input % $base)];
        $input = floor($input / $base);
    }
    return join("", array_reverse($result));
}
$i = 0;
$input = str_split($input);
foreach($input as $char){
    $pos = array_search($char, $dictionary);
    $i = $i * $base + $pos;
}
return $i;
}

Aquí hay una implementación de Node.js que probablemente bit.ly. generar una cadena de siete caracteres altamente aleatoria.

Utiliza el cripto Node.js para generar un conjunto de 25 caracteres altamente aleatorio en lugar de seleccionar aleatoriamente siete caracteres.

var crypto = require("crypto");
exports.shortURL = new function () {
    this.getShortURL = function () {
        var sURL = '',
            _rand = crypto.randomBytes(25).toString('hex'),
            _base = _rand.length;
        for (var i = 0; i < 7; i++)
            sURL += _rand.charAt(Math.floor(Math.random() * _rand.length));
        return sURL;
    };
}

Mi versión de Python 3

base_list = list("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
base = len(base_list)

def encode(num: int):
    result = []
    if num == 0:
        result.append(base_list[0])

    while num > 0:
        result.append(base_list[num % base])
        num //= base

    print("".join(reversed(result)))

def decode(code: str):
    num = 0
    code_list = list(code)
    for index, code in enumerate(reversed(code_list)):
        num += base_list.index(code) * base ** index
    print(num)

if __name__ == '__main__':
    encode(341413134141)
    decode("60FoItT")

Para obtener una solución Node.js / JavaScript de calidad, consulte el abreviador de id módulo , que se probó exhaustivamente y se ha utilizado en producción durante meses.

Proporciona un acortador eficiente de ID / URL respaldado por el almacenamiento enchufable predeterminado en Redis , e incluso puede personalizar su conjunto de caracteres de ID corto y si el acortamiento es idempotente . Esta es una distinción importante que no todos los acortadores de URL tienen en cuenta.

En relación con otras respuestas aquí, este módulo implementa la excelente respuesta aceptada de Marcel Jackwerth anterior.

El núcleo de la solución lo proporciona el siguiente fragmento de Redis Lua :

local sequence = redis.call('incr', KEYS[1])

local chars = '0123456789ABCDEFGHJKLMNPQRSTUVWXYZ_abcdefghijkmnopqrstuvwxyz'
local remaining = sequence
local slug = ''

while (remaining > 0) do
  local d = (remaining % 60)
  local character = string.sub(chars, d + 1, d + 1)

  slug = character .. slug
  remaining = (remaining - d) / 60
end

redis.call('hset', KEYS[2], slug, ARGV[1])

return slug

¿Por qué no solo generar una cadena aleatoria y agregarla a la URL base? Esta es una versión muy simplificada de hacer esto en C # .

static string chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
static string baseUrl = "https://google.com/";

private static string RandomString(int length)
{
    char[] s = new char[length];
    Random rnd = new Random();
    for (int x = 0; x < length; x++)
    {
        s[x] = chars[rnd.Next(chars.Length)];
    }
    Thread.Sleep(10);

    return new String(s);
}

Luego solo agregue el agregar la cadena aleatoria a la baseURL:

string tinyURL = baseUrl + RandomString(5);

Recuerde que esta es una versión muy simplificada de hacer esto y es posible que el método RandomString pueda crear cadenas duplicadas. En producción, debe tener en cuenta las cadenas duplicadas para asegurarse de que siempre tendrá una URL única. Tengo un código que tiene en cuenta las cadenas duplicadas al consultar una tabla de base de datos que podría compartir si alguien está interesado.

Este es mi pensamiento inicial, y se puede hacer más pensamiento, o se puede hacer una simulación para ver si funciona bien o si se necesita alguna mejora:

Mi respuesta es recordar la URL larga en la base de datos y usar la ID 0para 9999999999999999(o por grande que sea el número necesario).

Pero el ID 0 9999999999999999puede ser un problema, porque

1. puede ser más corto si usamos hexadecimal, o incluso base62 o base64. (base64 al igual que YouTube usando A- Z a- z 0- 9 _y- )
2. si aumenta de 0a 9999999999999999uniforme, los piratas informáticos pueden visitarlos en ese orden y saber qué URL se envían entre sí, por lo que puede ser un problema de privacidad

Podemos hacer esto:

1. tener un servidor asignado 0a999 un servidor, el Servidor A, por lo que ahora el Servidor A tiene 1000 de tales ID. Entonces, si hay 20 o 200 servidores que desean constantemente nuevas ID, no tiene que seguir pidiendo cada nueva ID, sino más bien pedir una sola vez por 1000 ID
2. para la ID 1, por ejemplo, invierta los bits. Así se 000...00000001convierte 10000...000, de modo que cuando se convierte a base64, aumentará de manera no uniforme las ID cada vez.
3. use XOR para voltear los bits para las ID finales. Por ejemplo, XOR con 0xD5AA96...2373(como una clave secreta), y algunos bits se voltearán. (siempre que la clave secreta tenga el bit 1 activado, cambiará el bit de la ID). Esto hará que las identificaciones sean aún más difíciles de adivinar y parezcan más aleatorias

Siguiendo este esquema, el único servidor que asigna las ID puede formar las ID, y también los 20 o 200 servidores que solicitan la asignación de ID. El servidor de asignación tiene que usar un bloqueo / semáforo para evitar que dos servidores solicitantes obtengan el mismo lote (o si está aceptando una conexión a la vez, esto ya resuelve el problema). Por lo tanto, no queremos que la línea (cola) sea demasiado larga para esperar a obtener una asignación. Por eso, asignar 1000 o 10000 a la vez puede resolver el problema.