Chaîne unique aléatoire contre une liste noire

Question

Je veux créer une chaîne aléatoire d'une longueur fixe (8 caractères dans mon cas d'utilisation) et la chaîne générée doit être sensible à la casse et unique par rapport à une liste noire. Je sais que cela ressemble à un UUID mais j'ai une exigence spécifique qui me empêche de les utiliser

1. certains caractères ne sont pas autorisés, à savoir I, l et 1 sont lookalikes et O et 0 ainsi

Ma mise en œuvre initiale est solide et résout la tâche mais fonctionne mal. Et par mal, je veux dire, il est condamné à être de plus en plus lent chaque jour.

Voici mon implémentation actuelle je veux optimiser:

private function uuid() 
{ 
    $chars = 'ABCDEFGHJKLMNPQRSTVUWXYZabcdefghijkmnopqrstvuwxyz23456789'; 

    $uuid = null; 
    while (true) { 
     $uuid = substr(str_shuffle($chars), 0, 8); 

     if (null === DB::table('codes')->select('id')->whereRaw('BINARY uuid = ?', [$uuid])->first())) { 
      break; 
     } 
    } 

    return $uuid; 
} 

S'il vous plaît épargnez-moi la critique, nous vivons dans un monde agile et cette mise en œuvre est fonctionnelle et est rapide au code.

Avec un petit ensemble de données, il fonctionne magnifiquement. Cependant, si j'ai 10 millions d'entrées dans la liste noire et que j'en essaie de créer 1000 autres, cela échoue car cela prend plus de 30 minutes. Un cas d'utilisation réel serait d'avoir plus de 10 millions d'entrées dans la base de données et de tenter de créer 20 000 nouveaux codes uniques.

Je pensais avant l'ensemencement toutes les valeurs admises, mais ce serait fou: (24 + 24 + 8)^8 = 9.6717312e + 13

Ce serait bien si la communauté peut me diriger dans la bonne direction.

Best, Nikola

Answer 1

Deux options:

1. Il suffit d'utiliser un hachage de quelque chose d'unique, et tronquer il convient dans la bande passante de votre identifiant. Les hachages se heurtent parfois, vous devrez donc toujours vérifier la base de données et réessayer si un code est déjà utilisé.

   s = "This is a string that uniquely identifies voucher #1. Blah blah." 
   h = hash(s) 
   guid = truncate(hash) 
   

2. Generate cinq des chiffres d'un compteur incrémenter et trois au hasard. Un voleur aura moins de 1 chance sur 140 000 de deviner un code, en fonction de votre jeu de caractères.

   u = Db.GetIncrementingCounter() 
   p = Random.GetCharacters(3) 
   guid = u + p 
   

Answer 2

Je fini par modifier l'approche: au lieu de vérifier l'existence UUID sur chaque boucle, par exemple 50K DB vérifie, je divise maintenant les codes générés en plusieurs morceaux de 1000 codes et émet une requête par lot INSERT IGNORE dans une transaction.

Si les lignes concernées sont aussi nombreuses que les éléments (1000 dans ce cas), je sais qu'il n'y a pas eu de collision et que je peux valider la transaction. Sinon, j'ai besoin de restaurer le bloc et générer 1000 autres codes.