Recentemente se me apresentou o problema de migrar um banco de dados de identificadores auto-incrementais para identificadores universais únicos (UUID).
A vantagem do UUID é bem conhecida e acabam sobrepujando as desvantagens. A proposta deste artigo é fornecer uma solução palatável para balancear as vantagens (unicidade principalmente) com as desvantagens (comprimento principalmente)
O que segue é uma pequena implementação de proposta de solução.
<?php
function calcEntropy($str)
{
// algoritmo de Shannon para cálculo da entropia
$chars = array();
$charcount = 0;
$i = strlen($str);
while ($i > 0) {
$i--;
$thischar = substr($str, $i, 1);
if (!isset($chars[ord($thischar)])) {
$chars[ord($thischar)] = 0;
}
$chars[ord($thischar)]++;
$charcount++;
}
$entropy = 0.0;
foreach ($chars as $val) {
$p = $val / $charcount;
$entropy = $entropy - ($p * log($p, 2));
}
return $entropy;
}
function genUuid()
{
/* ver https://www.php.net/manual/en/function.uniqid.php#94959 */
return sprintf('%04x%04x-%04x-%04x-%04x-%04x%04x%04x',
random_int(0, 0xffff), random_int(0, 0xffff),
random_int(0, 0xffff),
random_int(0, 0x0fff) | 0x4000,
random_int(0, 0x3fff) | 0x8000,
random_int(0, 0xffff), random_int(0, 0xffff), random_int(0, 0xffff)
);
}
function dec2hex($number)
{
$hv = array('0','1','2','3','4','5','6','7', '8','9','A','B','C','D','E','F');
$ret = '';
while($n != '0') {
$ret = $hv[bcmod($n,'16')].$ret;
$n = bcdiv($n,'16',0);
}
return $ret;
}
function genSUUID($prefix='', $maxLen=18) {
$charset = "qwertyuiopasdfghjklzxcvbnm" .
"QWERTYUIOPASDFGHJKLZXCVBNM" .
"0123456789_";
$max = strlen($charset);
$prefix = str_pad($prefix,2,'0',STR_PAD_LEFT);
$ts = dec2hex(date("y").str_pad(date("z"),3,'0', STR_PAD_LEFT).date("B"));
$ret = $prefix.$ts;
while(strlen($ret)<$maxLen) {
$ret .= substr($charset,random_int(0,$max),1);
}
return $ret;
}
// exemplo e cálculo de entropia
$largo = 20;
echo "\nGerando SUUID\n";
echo "# - " . str_pad("SUUID", $largo) . " - Entropia\n";
$e = 0;
for ($i = 0; $i < 10; $i++) {
$SUUID = genSUUID("xyz", $largo);
$entropy = calcEntropy($SUUID);
$e += $entropy;
echo "$i - " . $SUUID . " - " . calcEntropy($SUUID) . "\n";
}
echo "Entropia média = " . ($e / 10) . "\n";
$largo = 12;
echo "\nGerando md5(SUUID)\n";
echo "# - " . str_pad("SUUID", 32) . " - Entropia\n";
$e = 0;
for ($i = 0; $i < 10; $i++) {
$SUUID = md5(genSUUID("xyz", $largo));
$entropy = calcEntropy($SUUID);
$e += $entropy;
echo "$i - " . $SUUID . " - " . calcEntropy($SUUID) . "\n";
}
echo "Entropia média = " . ($e / 10) . "\n";
echo "\nGerando UUID canônico\n";
echo "# - " . str_pad("UUID", 36) . " - Entropia\n";
$e = 0;
for ($i = 0; $i < 10; $i++) {
$uuid = genUuid();
$entropy = calcEntropy($uuid);
$e += $entropy;
echo "$i - " . $uuid . " - " . calcEntropy($uuid) . "\n";
}
echo "Entropia média = " . ($e / 10) . "\n";
A função hex2ec() apenas serve para transformar um decimal em hexadecimal. Deixarei de lado as explicações.
Me concentrarei em genSUUID().
$prefix é um prefixo que usaremos para identificar o servidor. No caso ele aceita até 2 caracteres. Se o conjunto for [ a-z A-Z 0-9 ] cada caractere representa 62 unidades. 62^2=3844 servidores.
$charset é o conjunto de caracteres que iremos usar para representar o identificador.
$ts é a representação do tempo. Ela toma o ano com dois dígitos (acho que nos podemos permitir voltar ao esquema de dois dígitos até o próximo milênio) seguido de um identificador de três dígitos representando o dia no ano (isso é mais econômico que mm/dd) e finalizado pela representação swatch de hora, minuto do timestamp corrente. (Um dia tem 86400 segundos, ao passo que os beats do swatch divide o dia em 1000 partes. Como a ideia aqui não é precisão mas sim unicidade mantendo uma aproximação de quando foi gerado o id, essa resolução é aceitável).
Finalmente o prefixo, a representação do tempo são colados e adicionamos um conjunto de caracteres aleatório do conjunto indicado no $charset.
O que obtemos é um identificador com alta probabilidade de ser único que ao mesmo tempo nos informa em qual servidor e data foi criado com uma resolução de 1 minuto e 26,4 segundos.
Ele é o suficientemente menor que o UUID como para atrair o interesse (lembre que quanto menor seja seu índice no banco, menos RAM vai consumir sua consulta entregando resultados mais velozes)
Ao mesmo tempo, ele tem informação auto-contida que pode orientar na hora de depurar quem deu origem à informação.
Caso for utilizar em produção, lembre que a coluna que irá conter essa informação deve ser Case Sensitive (que aliás, também impacta positivamente na performance) e não precisa ser UTF8 sendo suficiente ASCII.
Atualização Por pura curiosidade implementei o algoritmo de Shannon para calcular a entropia de um string. Depois adicionei dois testes comparativos: o md5() do SUUID e o UUID. Para minha surpresa o SUUID apresenta valores de entropia equivalentes ao UUID mas com menos caracteres.
Generating SUUID (32 characters) Number of items represented: 3,850,278.001.389.542.008.853.330.205.498.027,278,336 - SUUID - Entropy 0 - xyz142EB295J5Vt1EzAtc3N6QLIZz2TZ - 4.3903195311148 1 - xyz142EB29 or DgyH2twFrNX9wWlRIAWz - 4.5389097655574 2 - xyz142EB295qSYM3Px7r1OnaUYGHwpro - 4.6875 3 - xyz142EB29Bal8PBFFERITHJKaCBIFCp - 4.2889097655574 4 - xyz142EB29z14aBz7faaRHYvXOQD39IQ - 4.3278195311148 5 - xyz142EB29xqj5boLEDMXI0DbZ4t0l45 - 4.4139097655574 6 - xyz142EB292eJPBvdPWzqk6EycZPCu5U - 4.4528195311148 7 - xyz142EB29i4RDeXRI4gwHc8EyrWWX7x - 4.4139097655574 8 - xyz142EB29q0l54u1KX6oyTiQtVgGrJB - 4.6875 9 - xyz142EB291LMUbRzveltEEdmA4bxurX - 4.4764097655574 Mean entropy = 4.4678007421131 Time consumed per iteration: 0.11599063873291ms Generating md5(SUUID) Number of items represented: 340,282,366,920,928,463,463,463,374,607,431,768,211,456 - SUUID - Entropy 0 - 7a9cff898936039c308bca38614e4896 - 3.4772170014625 1 - f2640bbe2e63af0d798d20919a67001f - 3.6678377974034 2 - e912722d4ff09cc23110e38d89ef52b3 - 3.6442475629608 3 - c33cfed4dfd09fbf212e24a6cbe52b7 - 3.6678377974034 4 - 5290ebc045fde2930b297ab905cda543 - 3.5778195311148 5 - 334efcce90828f75408a6503504731c6 - 3.6556390622296 6 - 53d0dc3aa33ba26da902412bcec89cd7 - 3.6639097655574 7 - 2c701ff81578676311a807d78c18f8f2 - 3.2897170014625 8 - 29ce9c482612a2820fae10a76ff686f8 - 3.4261085007312 9 - 97b0cb7e338eff600d4a6555db62e446 - 3.757048827787 Average entropy = 3.5827382848113 Time consumed per iteration: 0.1032829284668ms Generating Canonical UUID Number of items represented: 340,282,366,920,928,463,463,463,374,607,431,768,211,456 - UUID - Entropy 0 - be6c96fc-34d9-4fb5-b6f6-82e7b37e6be2 - 3.6150869889135 1 - 2f260cd1-7fff-4066-804a-5af2b113acf6 - 3.6552215288595 2 - 872b0d0d-5acd-4609-88ba-38b8d5e4a3b0 - 3.6597992243145 3 - 90ba1bdb-194e-4035-9b66-2946899b4a81 - 3.541336376912 4 - 7d09dd5c-72e1-4853-8965-54dbd8514823 - 3.6706425444691 5 - 9a54bbd0-aa98-4baf-b604-fceecd0bacb3 - 3.5759228351853 6 - b3d4ab1b-ae8b-4ca4-9675-398f29c6fc48 - 3.8082708345353 7 - be4039f8-997f-4cdb-8a67-2fe2bb42e35f - 3.8082708345353 8 - 37b3d945-6f13-4a0c-b518-7962f7fe8931 - 3.9193819456464 9 - 648b88ad-dbaa-4743-93ee-f5a8ce435232 - 3.7045114597155 Average entropy = 3.6958444573086 Time consumed per iteration: 0.046086311340332ms
Você precisa fazer login para comentar.