Jak tworzyć deterministyczne wytyczne


107

W naszej aplikacji tworzymy pliki Xml z atrybutem o wartości Guid. Ta wartość musiała być spójna między aktualizacjami plików. Więc nawet jeśli wszystko inne w pliku się zmieni, wartość guid dla atrybutu powinna pozostać taka sama.

Jednym z oczywistych rozwiązań było utworzenie słownika statycznego z nazwą pliku i identyfikatorami Guid, które miały być dla nich używane. Następnie za każdym razem, gdy generujemy plik, szukamy w słowniku nazwy pliku i używamy odpowiedniego guidu. Ale to nie jest wykonalne, ponieważ możemy skalować do setek plików i nie chcieliśmy utrzymywać dużej listy poradników.

Więc innym podejściem było uczynienie Guid tym samym na podstawie ścieżki do pliku. Ponieważ nasze ścieżki plików i struktura katalogów aplikacji są unikalne, identyfikator Guid powinien być unikalny dla tej ścieżki. Tak więc za każdym razem, gdy uruchamiamy aktualizację, plik otrzymuje ten sam identyfikator guid na podstawie swojej ścieżki. Znalazłem fajny sposób na generowanie takich „ deterministycznych przewodników ” (dzięki Elton Stoneman). Zasadniczo robi to:

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; 

} 

Więc mając ciąg, Guid zawsze będzie taki sam.

Czy są jakieś inne podejścia lub zalecane sposoby, aby to zrobić? Jakie są wady i zalety tej metody?

Odpowiedzi:


154

Jak wspomniał @bacar, RFC 4122 §4.3 definiuje sposób tworzenia identyfikatora UUID opartego na nazwie. Zaletą takiego rozwiązania (w porównaniu z samym użyciem skrótu MD5) jest to, że gwarantuje to, że nie kolidują one z identyfikatorami UUID opartymi na nazwach i mają bardzo (bardzo) małą możliwość kolizji z innymi identyfikatorami UUID opartymi na nazwach.

NET Framework nie ma natywnego wsparcia dla ich tworzenia, ale opublikowałem kod na GitHub, który implementuje algorytm. Można go używać w następujący sposób:

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

Aby jeszcze bardziej zmniejszyć ryzyko kolizji z innymi identyfikatorami GUID, można utworzyć prywatny identyfikator GUID, który będzie używany jako identyfikator przestrzeni nazw (zamiast używać identyfikatora przestrzeni nazw URL zdefiniowanego w specyfikacji RFC).


5
@Porges: RFC4122 jest niepoprawny i zawiera erratę, która naprawia kod C ( rfc-editor.org/errata_search.php?rfc=4122&eid=1352 ). Jeśli ta implementacja nie jest w pełni zgodna z RFC4122 i jego erratą, podaj dalsze szczegóły; Chciałbym, aby był zgodny ze standardem.
Bradley Grainger,

1
@BradleyGrainger: Nie zauważyłem tego, dzięki / przepraszam! Zawsze powinienem pamiętać o sprawdzaniu erraty podczas czytania RFC ... :)
porge

3
@Porges: Nie ma za co / nie ma problemu. To zdumiewa, że ​​nie aktualizują RFC na miejscu poprawkami z erraty. Nawet odsyłacz na końcu dokumentu byłby znacznie bardziej pomocny niż poleganie na czytelniku, aby pamiętał o wyszukiwaniu erraty (miejmy nadzieję, że przed napisaniem implementacji opartej na RFC ...).
Bradley Grainger,

1
@BradleyGrainger: jeśli korzystasz z wersji HTML, ma link do erraty z nagłówka, np . Tools.ietf.org/html/rfc4122 . Zastanawiam się, czy istnieje rozszerzenie przeglądarki, które zawsze przekierowuje do wersji HTML ...
porge

3
Powinieneś rozważyć dodanie
sapphiremirage

29

Spowoduje to przekonwertowanie dowolnego ciągu na Guid bez konieczności importowania zewnętrznego zestawu.

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

Istnieją znacznie lepsze sposoby generowania unikatowego Guid, ale jest to sposób na konsekwentną aktualizację klucza danych ciągu do klucza danych Guid.


Okazało się, że ten fragment kodu jest przydatny podczas używania unikatowego identyfikatora w bazie danych do dystrybucji stowarzyszonej.
Gleno,

6
Ostrzeżenie! Ten kod nie generuje prawidłowych identyfikatorów Guid / UUID (jak bacar również wspomniano poniżej). Ani wersja, ani pole typu nie są ustawione poprawnie.
MarkusSchaber

3
Czy nie byłoby równie efektywne użycie MD5CryptoServiceProvider zamiast SHA1, skoro MD5 ma już 16 bajtów długości?
Brain2000

21

Jak wspomina Rob, twoja metoda nie generuje UUID, generuje hash, który wygląda jak UUID.

RFC 4122 na UUID szczególności pozwala deterministycznych (nazwa oparte) UUID - wersje 3 i 5 Zastosowanie MD5 i SHA1 (odpowiednio). Większość ludzi prawdopodobnie zna wersję 4, która jest przypadkowa. Wikipedia daje dobry przegląd wersji. (Zauważ, że użycie słowa „wersja” wydaje się opisywać „typ” UUID - wersja 5 nie zastępuje wersji 4).

Wydaje się, że istnieje kilka bibliotek do generowania UUID wersji 3/5, w tym moduł uuid języka Python , boost.uuid (C ++) i UUID OSSP . (Nie szukałem żadnych .net)


1
Właśnie tego szukał oryginalny plakat. Identyfikator UUID ma już algorytm umożliwiający rozpoczęcie od ciągu znaków i przekonwertowanie go na identyfikator GUID. UUID w wersji 3 haszuje ciąg za pomocą MD5, podczas gdy wersja 5 haszuje go za pomocą SHA1. Ważnym punktem tworzenia „guid” jest uczynienie go „unikatowym” względem innych identyfikatorów GUID. Algorytm definiuje dwa bity, które należy ustawić, a także wartość półbajtu na 3 lub 5, w zależności od wersji 3 lub 5.
Ian Boyd

2
Jeśli chodzi o użycie słowa „wersja”, RFC 4122 §4.1.3 stwierdza: „Wersja jest dokładniej podtypem; ponownie zachowujemy termin dla zgodności”.
Bradley Grainger

11
Opublikowałem kod w języku C # do tworzenia identyfikatorów GUID w wersji 3 i 5 na GitHub: github.com/LogosBible/Logos.Utility/blob/master/src/ ...
Bradley Grainger

@BradleyGrainger, otrzymuję ostrzeżenie Bitwise - lub operator używany na operandzie ze znakiem; rozważ casting na mniejszy typ bez znaku
Sebastian

1
To staje się nie na temat! Zaproponuj przeniesienie pojedynczych raportów o błędach lib do GitHub.
Bacar

3

Musisz dokonać rozróżnienia między instancjami klasy Guida identyfikatorami, które są globalnie unikalne. „Deterministyczny przewodnik” jest w rzeczywistości hashem (czego dowodem jest twoje wywołanie provider.ComputeHash). Hashe mają znacznie większą szansę na kolizje (dwa różne ciągi tworzą ten sam hash) niż Guid utworzony za pomocą Guid.NewGuid.

Więc problem z twoim podejściem polega na tym, że będziesz musiał zaakceptować możliwość, że dwie różne ścieżki utworzą ten sam identyfikator GUID. Jeśli potrzebujesz identyfikatora, który jest unikalny dla dowolnego ciągu ścieżki, najłatwiej jest po prostu użyć tego ciągu . Jeśli chcesz, aby ciąg został ukryty przed użytkownikami, zaszyfruj go - możesz użyć ROT13 lub czegoś mocniejszego ...

Próba włożenia czegoś, co nie jest czystym identyfikatorem GUID do typu danych GUID, może w przyszłości doprowadzić do problemów z konserwacją ...


2
Twierdzisz, że „Hashe mają znacznie większe ryzyko kolizji ... niż Guid utworzony za pomocą Guid.NewGuid.”. Czy możesz to rozwinąć? Z matematycznego punktu widzenia liczba bitów, które można ustawić, jest taka sama, a zarówno MD5, jak i SHA1 to skróty kryptograficzne, zaprojektowane specjalnie w celu zmniejszenia prawdopodobieństwa (przypadkowych i celowych) kolizji skrótów.
MarkusSchaber

Powiedziałbym, że główną różnicą jest kryptograficzna mapa skrótów z jednej nieskończonej przestrzeni do innej ustalonej przestrzeni za pomocą funkcji. Obrazowanie skrótu, który odwzorowuje ciągi o zmiennej długości na 128 bitów, podczas gdy Guid generuje pseudolosowe 128 bitów. Generowanie pseudolosowe nie opiera się na początkowym wejściu, ale raczej na generowaniu wyjścia równomiernie w przestrzeni wyjściowej przy użyciu losowości zapoczątkowanej przez sprzęt lub w inny sposób.
Thai Bui

1

MD5 jest słaba, wierzę, że możesz zrobić to samo z SHA-1 i uzyskać lepsze wyniki.

BTW, to tylko osobista opinia, ubranie skrótu md5 jako identyfikatora GUID nie czyni go dobrym identyfikatorem GUID. Identyfikatory GUID ze swej natury nie są deterministyczne. to wygląda na oszustwo. Dlaczego po prostu nie nazwać pik po imieniu i po prostu powiedzieć, że jest to ciąg renderowany hash wejścia. możesz to zrobić, używając tej linii zamiast nowej linii guid:

string stringHash = BitConverter.ToString(hashBytes)

Dziękuję za wkład, ale nadal daje mi to ciąg znaków, a szukam GUID ...
Punit Vora

Ok, nazwij swój hash „GUID”, problem rozwiązany. Czy jest prawdziwy problem, że trzeba do Guidobiektu?
user7116

chciałbym, żeby to było takie proste ... :) ale tak, potrzebuję obiektu „GUID”
Punit Vora

6
„Identyfikatory GUID ze swej natury nie są deterministyczne” - dotyczy to tylko niektórych typów („wersji”) identyfikatorów GUID. Jednak zgadzam się, że „ubieranie skrótu md5 jako identyfikatora GUID nie tworzy dobrego identyfikatora GUID” z innych powodów, które opisali @Bradley Grainger i @Rob Fonseca-Ensor, oraz moja odpowiedź na to pytanie.
Bacar
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.