Como Criar Guids Determinísticos

103

Em nosso aplicativo, estamos criando arquivos Xml com um atributo que possui um valor Guid. Esse valor precisava ser consistente entre as atualizações de arquivo. Portanto, mesmo que tudo o mais no arquivo seja alterado, o valor guid para o atributo deve permanecer o mesmo.

Uma solução óbvia era criar um dicionário estático com o nome do arquivo e os Guids a serem usados ​​para eles. Então, sempre que geramos o arquivo, procuramos o nome do arquivo no dicionário e usamos o guid correspondente. Mas isso não é viável porque podemos escalar para centenas de arquivos e não queremos manter uma grande lista de guias.

Portanto, outra abordagem era tornar o Guid o mesmo com base no caminho do arquivo. Visto que nossos caminhos de arquivo e estrutura de diretório de aplicativo são exclusivos, o Guid deve ser exclusivo para esse caminho. Portanto, cada vez que executamos uma atualização, o arquivo obtém o mesmo guid com base em seu caminho. Eu encontrei uma maneira legal de gerar esses ' Guias Determinísticos ' (Obrigado Elton Stoneman). Basicamente, ele faz isso:

private Guid GetDeterministicGuid(string input) 

{ 

//use MD5 hash to get a 16-byte hash of the string: 

MD5CryptoServiceProvider provider = new MD5CryptoServiceProvider(); 

byte[] inputBytes = Encoding.Default.GetBytes(input); 

byte[] hashBytes = provider.ComputeHash(inputBytes); 

//generate a guid from the hash: 

Guid hashGuid = new Guid(hashBytes); 

return hashGuid; 

} 

Assim, dada uma string, o Guid será sempre o mesmo.

Existem outras abordagens ou maneiras recomendadas de fazer isso? Quais são os prós ou contras desse método?

Punit Vora
fonte

Respostas:

151

Conforme mencionado por @bacar, a RFC 4122 §4.3 define uma maneira de criar um UUID baseado em nome. A vantagem de fazer isso (em vez de apenas usar um hash MD5) é que eles têm a garantia de não colidir com UUIDs não baseados em nome e têm uma possibilidade muito (muito) pequena de colisão com outros UUIDs baseados em nome.

Não há suporte nativo no .NET Framework para criá-los, mas postei um código no GitHub que implementa o algoritmo. Ele pode ser usado da seguinte maneira:

Guid guid = GuidUtility.Create(GuidUtility.UrlNamespace, filePath);

Para reduzir ainda mais o risco de colisões com outros GUIDs, você pode criar um GUID privado para usar como a ID do namespace (em vez de usar a ID do namespace da URL definida no RFC).

Bradley Grainger
fonte
5
@Porges: RFC4122 está incorreto e possui errata que corrige o código C ( rfc-editor.org/errata_search.php?rfc=4122&eid=1352 ). Se esta implementação não for totalmente compatível com RFC4122 e sua errata, forneça mais detalhes; Eu gostaria de fazê-lo seguir o padrão.
Bradley Grainger
1
@BradleyGrainger: Não percebi, obrigado / desculpe! Devo sempre lembrar de verificar a errata ao ler um RFC ... :)
porges
3
@Porges: De nada / sem problemas. Surpreende a mente que eles não atualizam o RFC no local com as correções da errata. Mesmo um link no final do documento seria muito mais útil do que contar com o leitor para se lembrar de pesquisar erratas (espero que antes de escrever uma implementação baseada na RFC ...).
Bradley Grainger
1
@BradleyGrainger: se você usar a versão HTML, há um link para a errata do cabeçalho, por exemplo, tools.ietf.org/html/rfc4122 . Gostaria de saber se existe uma extensão do navegador para sempre redirecionar para a versão HTML ...
porges
2
Você deve considerar contribuir com o repositório
sapphiremirage
29

Isso irá converter qualquer string em um Guid sem ter que importar um assembly externo.

public static Guid ToGuid(string src)
{
    byte[] stringbytes = Encoding.UTF8.GetBytes(src);
    byte[] hashedBytes = new System.Security.Cryptography
        .SHA1CryptoServiceProvider()
        .ComputeHash(stringbytes);
    Array.Resize(ref hashedBytes, 16);
    return new Guid(hashedBytes);
}

Existem maneiras muito melhores de gerar um Guid exclusivo, mas esta é uma maneira de atualizar consistentemente uma chave de dados de string para uma chave de dados Guid.

Ben Gripka
fonte
Considerou este fragmento útil ao usar identificador exclusivo em um banco de dados para distribuição federada.
Gleno
6
Aviso! Este código não gera Guids / UUIDs válidos (como bacar também mencionado abaixo). Nem a versão nem o campo de tipo estão definidos corretamente.
MarkusSchaber
3
Não seria tão eficaz usar o MD5CryptoServiceProvider em vez do SHA1, uma vez que o MD5 já tem 16 bytes de comprimento?
Brain2000,
20

Como Rob menciona, seu método não gera um UUID, ele gera um hash que se parece com um UUID.

O RFC 4122 em UUIDs permite especificamente UUIDs determinísticos (baseados em nome) - as versões 3 e 5 usam md5 e SHA1 (respectivamente). A maioria das pessoas provavelmente está familiarizada com a versão 4, que é aleatória. A Wikipedia oferece uma boa visão geral das versões. (Observe que o uso da palavra 'versão' aqui parece descrever um 'tipo' de UUID - a versão 5 não substitui a versão 4).

Parece haver algumas bibliotecas por aí para gerar UUIDs de versão 3/5, incluindo o módulo uuid python , boost.uuid (C ++) e OSSP UUID . (Não procurei nenhum .net)

bacar
fonte
1
Isso é exatamente o que o pôster original está procurando. O UUID já possui um algoritmo para você começar com uma string e convertê-la em um GUID. O UUID versão 3 faz o hash da string com MD5, enquanto a versão 5 faz o hash com SHA1. O ponto importante na criação de um "guid" é torná-lo "exclusivo" em relação a outros GUIDs. O algoritmo define dois bits que devem ser configurados, assim como um nibble é configurado para 3 ou 5, dependendo se for a versão 3 ou 5.
Ian Boyd
2
Em relação ao uso da palavra "versão", o RFC 4122 §4.1.3 afirma: "A versão é mais precisamente um subtipo; novamente, mantemos o termo para compatibilidade."
Bradley Grainger
11
Publiquei
Bradley Grainger
@BradleyGrainger, recebo Aviso Bitwise-or operator usado em um operando de sinal estendido; considere lançar para um tipo menor não assinado primeiro
Sebastian
1
Isso está saindo do assunto! Sugira mover relatórios de bug individuais de lib para o GitHub.
bacar
3

Você precisa fazer uma distinção entre as instâncias da classe Guide os identificadores que são globalmente exclusivos. Um "guid determinístico" é na verdade um hash (conforme evidenciado por sua chamada para provider.ComputeHash). Hashes têm uma chance muito maior de colisões (duas strings diferentes produzindo o mesmo hash) do que o Guid criado via Guid.NewGuid.

Portanto, o problema com sua abordagem é que você terá que estar ok com a possibilidade de que dois caminhos diferentes produzirão o mesmo GUID. Se você precisar de um identificador exclusivo para qualquer string de caminho, a coisa mais fácil a fazer é apenas usar a string . Se você precisa que a string seja ocultada de seus usuários, criptografe-a - você pode usar ROT13 ou algo mais poderoso ...

A tentativa de encaixar algo que não é um GUID puro no tipo de dados GUID pode levar a problemas de manutenção no futuro ...

Rob Fonseca-Ensor
fonte
2
Você afirma que "Hashes têm uma chance muito maior de colisões ... do que o Guid criado por meio do Guid.NewGuid.". Você pode elaborar sobre isso? Do ponto de vista matemático, o número de bits que pode ser definido é o mesmo, e MD5 e SHA1 são hashes criptográficos, projetados especificamente para reduzir a probabilidade de colisões de hash (acidentais e intencionais).
MarkusSchaber
Eu diria que a principal diferença é o mapeamento de hashes criptográficos de um espaço infinito para outro espaço fixo usando uma função. Criação de imagens de um hash que mapeia strings de comprimento variável para 128 bits, enquanto Guid gera 128 bits pseudo-aleatórios. A geração pseudo-aleatória não depende de uma entrada inicial, mas ao invés disso, gera a saída uniformemente no espaço de saída usando a aleatoriedade propagada do hardware ou outros meios.
Thai Bui
2

MD5 é fraco, acredito que você pode fazer a mesma coisa com SHA-1 e obter melhores resultados.

BTW, apenas uma opinião pessoal, vestir um hash md5 como um GUID não o torna um bom GUID. Os GUIDs, por sua própria natureza, são não determinísticos. isso parece uma trapaça. Por que não chamar um spade de spade e apenas dizer que é uma string renderizada como hash da entrada. você pode fazer isso usando esta linha, em vez da nova linha de guid:

string stringHash = BitConverter.ToString(hashBytes)
Ryber
fonte
Obrigado por sua entrada, mas isso ainda me dá uma string, e estou procurando um GUID ...
Punit Vora
Ok, chame seu hash de "GUID", problema resolvido. Ou o problema real é que você precisa de um Guidobjeto?
user7116
gostaria que fosse assim tão simples .. :) mas sim, eu preciso de um objeto 'GUID'
Punit Vora
5
"Os GUIDs, por sua própria natureza, são não determinísticos" - isso só é verdadeiro para certos tipos ('versões') de GUIDs. No entanto, concordo que "vestir um hash md5 como um GUID não é um bom GUID" por outras razões, conforme explicitado por @Bradley Grainger e @Rob Fonseca-Ensor, e minha resposta a essa pergunta.
bacar