Generowanie UUID v5. Co to jest nazwa i przestrzeń nazw?


125

Przeczytałem manstronę, ale nie rozumiem po co namei namespacedo czego.

W przypadku identyfikatorów UUID wersji 3 i 5 należy podać dodatkowe argumenty wiersza poleceń, przestrzeń nazw i nazwę. Przestrzeń nazw to UUID w postaci ciągu znaków lub identyfikator wewnętrznie wstępnie zdefiniowanych UUID przestrzeni nazw (obecnie znane to „ns: DNS”, „ns: URL”, „ns: OID” i „ns: X500”). Nazwa jest ciągiem o dowolnej długości.

Przestrzeń nazw:

Przestrzeń nazw jest UUID w reprezentacji ciągu lub

Czy to oznacza, że ​​muszę go gdzieś przechowywać (UUID v4) w związku z wygenerowanym UUID v5? W obu przypadkach, dlaczego nie dzieje się to automatycznie?

Nazwa jest ciągiem o dowolnej długości.

namecałkowicie losowy ciąg? Jaki jest zatem tego cel? Czy można go zdekodować z UUID v5?

Odpowiedzi:


106

Nazwy i przestrzeni nazw można użyć do stworzenia hierarchii (prawdopodobnie) unikalnych identyfikatorów UUID.

Z grubsza rzecz biorąc, identyfikator UUID typu 3 lub 5 jest generowany przez połączenie identyfikatora przestrzeni nazw z nazwą. Identyfikatory UUID typu 3 używają MD5, a identyfikatory UUID typu 5 używają SHA1. Dostępnych jest tylko 128 bitów, a 5 bitów jest używanych do określenia typu, więc wszystkie bity mieszania nie trafiają do UUID. (Również MD5 jest uważane za zepsute kryptograficznie, a SHA1 jest na ostatnich nogach, więc nie używaj tego do weryfikacji danych, które muszą być „bardzo bezpieczne”). To powiedziawszy, daje ci sposób na stworzenie powtarzalnej / weryfikowalnej funkcji "hash" mapującej możliwie hierarchiczną nazwę na probabilistycznie unikalną 128-bitową wartość, potencjalnie działającą jak hierarchiczny hash lub MAC.

Załóżmy, że masz magazyn (klucz, wartość), ale obsługuje on tylko jedną przestrzeń nazw. Można wygenerować dużą liczbę różnych logicznych przestrzeni nazw przy użyciu identyfikatorów UUID typu 3 lub 5. Najpierw utwórz główny UUID dla każdej przestrzeni nazw. Może to być identyfikator UUID typu 1 (host + znacznik czasu) lub 4 (losowy), pod warunkiem, że gdzieś go przechowujesz. Alternatywnie możesz utworzyć jeden losowy UUID dla swojego roota (lub użyć nullUUID: 00000000-0000-0000-0000-000000000000as root), a następnie utworzyć odtwarzalny UUID dla każdej przestrzeni nazw używając " uuid -v5 $ROOTUUID $NAMESPACENAME". Teraz możesz tworzyć unikalne identyfikatory UUID dla kluczy w przestrzeni nazw za pomocą „uuid -v5 $NAMESPACEUUID $KEYTe identyfikatory UUID można wrzucić do pojedynczego magazynu klucz-wartość z dużym prawdopodobieństwem uniknięcia kolizji. Proces ten można powtarzać rekurencyjnie, tak aby na przykład „wartość” skojarzona z kluczem UUID reprezentowała z kolei pewien rodzaj logicznej „przestrzeni nazw” „jak zasobnik, kontener lub katalog, wówczas jego UUID może być z kolei użyty do generowania bardziej hierarchicznych identyfikatorów UUID.

Wygenerowany identyfikator UUID typu 3 lub 5 zawiera (częściowy) skrót identyfikatora przestrzeni nazw i nazwy w przestrzeni nazw (klucz). Nie więcej przechowuje UUID przestrzeni nazw, niż wiadomość MAC przechowuje zawartość wiadomości, z której jest zakodowana. Z punktu widzenia algorytmu uuid nazwa jest „dowolnym” (oktetowym) ciągiem znaków. Jednak jego znaczenie zależy od aplikacji. Może to być nazwa pliku w katalogu logicznym, identyfikator obiektu w składnicy obiektów itp.

Chociaż działa to dobrze w przypadku umiarkowanie dużej liczby przestrzeni nazw i kluczy, w końcu wyczerpuje się, jeśli dążysz do bardzo dużej liczby unikalnych kluczy z bardzo dużym prawdopodobieństwem. Wpis Wikipedii dotyczący problemu urodzinowego (inaczej Paradoks urodzin) zawiera tabelę, która podaje prawdopodobieństwo co najmniej jednej kolizji dla różnych numerów kluczy i rozmiarów tabel. Dla 128-bitów, haszowanie 26 miliardów kluczy w ten sposób ma prawdopodobieństwo kolizji p=10^-18(pomijalne), ale 26 bilionów kluczy zwiększa prawdopodobieństwo co najmniej jednej kolizji do p=10^-12(jeden na bilion), a haszowanie 26*10^15kluczy zwiększa prawdopodobieństwo co najmniej jedno zderzenie zp=10^-6(jeden na milion). Dostosowując się do 5 bitów kodujących typ UUID, skończy się nieco szybciej, więc bilion kluczy ma mniej więcej 1 na bilion szans na pojedynczą kolizję.

Zobacz http://en.wikipedia.org/wiki/Birthday_problem#Probability_table, aby zapoznać się z tabelą prawdopodobieństwa.

Więcej informacji na temat kodowania UUID można znaleźć pod adresem http://www.ietf.org/rfc/rfc4122.txt .


2
Czy na pewnym poziomie w dół w hierarchii mogę użyć UUIDv5 jako przestrzeni nazw i UUIDv4 jako klucza losowego, aby upewnić się, że kolizje w samych danych (które są identyfikowane przez ten identyfikator GUID) nie zwiększają szans na kolizję UUID? Jakieś problemy z wydajnością, o których powinienem wiedzieć?
ermik

Jestem nowy w tej koncepcji i byłem zdziwiony, czym jest ta hierarchia , o której mówisz. Gdzie mogę to zobaczyć itp. Pewna jasność pojawiła się, gdy utknąłem przy wyjaśnieniu, że można to wykorzystać do utworzenia odtwarzalnego UUID dla przestrzeni nazw . Zastanawiam się, czy istnieje sposób na sprawdzenie, czy dany UUID (typu 3 lub 5) został wygenerowany przy użyciu określonej przestrzeni nazw (jego UUID)?
msciwoj

213

Identyfikatory UUID typu 3 i 5 to tylko technika umieszczania skrótu w identyfikatorze UUID.

Skrót SHA1 generuje 160 bitów (20 bajtów); wynik skrótu jest konwertowany na UUID.

Z 20-bajtowym hashem z SHA1:

SHA1 Digest:   74738ff5 5367 e958 9aee 98fffdcd1876 94028007
UUID (v5):     74738ff5-5367-5958-9aee-98fffdcd1876
                             ^_low nibble is set to 5, to indicate type 5
                                  ^_first two bits set to 1 and 0, respectively

(Zauważ, że pierwsze dwa bity „9” mają już odpowiednio 1 i 0, więc nie ma to żadnego wpływu).

Co mam haszować?

Pewnie się zastanawiasz, co mam haszować. Zasadniczo haszujesz konkatenację:

sha1([NamespaceUUID]+[AnyString]);

Przedrostek ciągu z tak zwaną przestrzenią nazw, aby zapobiec konfliktom nazw.

UUID RFC wstępnie definiuje cztery obszary nazw dla Ciebie:

  • NameSpace_DNS: {6ba7b810-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_URL: {6ba7b811-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_OID: {6ba7b812-9dad-11d1-80b4-00c04fd430c8}
  • NameSpace_X500: {6ba7b814-9dad-11d1-80b4-00c04fd430c8}

Więc możesz razem mieszać:

StackOverflowDnsUUID = sha1(Namespace_DNS + "stackoverflow.com");
StackOverflowUrlUUID = sha1(Namespace_URL + "stackoverflow.com");

Następnie dokument RFC definiuje, jak:

  • weź 160 bitów z SHA1
  • i przekonwertuj go na 128 bitów UUID

Podstawowym celem jest pobranie tylko pierwszych 128 bitów, umieszczenie a 5w rekordzie typu , a następnie ustawienie pierwszych dwóch bitów clock_seq_hi_and_reservedsekcji odpowiednio na 1 i 0.

Więcej przykładów

Teraz, gdy masz funkcję, która generuje tak zwaną Nazwę , możesz mieć funkcję (w pseudokodzie):

UUID NameToUUID(UUID NamespaceUUID, String Name)
{
    byte[] hash = sha1(NamespaceUUID.ToBytes() + Name.ToBytes());
    UUID result;
    Copy(hash, result, 16);
    result[6] &= 0x0F; 
    result[6] |= 0x50;
    result[8] &= 0x3F; 
    result[8] |= 0x80;
    return result;
}

(Zauważ, że endian -ness twojego systemu może wpływać na indeksy powyższych bajtów)

Możesz mieć telefony:

uuid = NameToUUID(Namespace_DNS, 'www.stackoverflow.com');
uuid = NameToUUID(Namespace_DNS, 'www.google.com');
uuid = NameToUUID(Namespace_URL, 'http://www.stackoverflow.com');
uuid = NameToUUID(Namespace_URL, 'http://www.google.com/search&q=rfc+4112');
uuid = NameToUUID(Namespace_URL, 'http://stackoverflow.com/questions/5515880/test-vectors-for-uuid-version-5-converting-hash-into-guid-algorithm');

Wróćmy teraz do twojego pytania

W przypadku identyfikatorów UUID wersji 3 i 5 należy podać dodatkowe argumenty wiersza poleceń, przestrzeń nazw i nazwę. Przestrzeń nazw to UUID w postaci ciągu znaków lub identyfikator wewnętrznie wstępnie zdefiniowanych UUID przestrzeni nazw (obecnie znane to „ns: DNS”, „ns: URL”, „ns: OID” i „ns: X500”). Nazwa jest ciągiem o dowolnej długości.

Przestrzeń nazw ma dowolny UUID. Może to być jeden z predefiniowanych lub możesz stworzyć własny, np .:

UUID Namespace_RectalForeignExtractedObject = '8e884ace-bee4-11e4-8dfc-aa07a5b093db'

Nazwa jest ciągiem o dowolnej długości.

Nazwa to po prostu tekst, który chcesz dołączyć do przestrzeni nazw, a następnie zaszyfrować i wstawić do UUID:

uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'screwdriver');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'toothbrush');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'broomstick');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'orange');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'axe handle');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'impulse body spray');
uuid = NameToUUID('8e884ace-bee4-11e4-8dfc-aa07a5b093db', 'iPod Touch');

Uwaga : każdy kod udostępniony w domenie publicznej. Atrybucja nie jest wymagana.


45
Dzięki za dokładne wyjaśnienie. Gdybym mógł dać dodatkowe punkty Namespace_RectalForeignExtractedObject, zrobiłbym to.
boodle

Czy można zdekodować nazwę lub przestrzeń nazw zdekodowaną z UUID?
Sobota

3
@Sathesh Nie, nie można zdekodować skrótu; skróty to funkcje jednokierunkowe. Na przykład cała kolekcja Star Trek TNG Blu-Ray ma 81 GB i ma skrót C5740BBBF2429115276D4AB60A020ED3ADE01192 . Nie ma możliwości zdekodowania tego 20-bajtowego skrótu z powrotem do 81 GB. Jeśli naprawdę potrzebujesz, możesz spróbować zaszyfrować wszystkie możliwe identyfikatory GUID i możliwe ciągi, aż znajdziesz kombinację, która daje ten sam wynik. Za każdym razem znajdziesz to gdzieś pomiędzy wiecznością a wiecznością.
Ian Boyd

22

Nazwa to nic innego jak identyfikator, który jest unikalny w obrębie jakiejś przestrzeni nazw. Problem polega na tym, że przestrzenie nazw są często dość małe, a nazwy w jednej często kolidują z nazwami w innych. Na przykład numer rejestracyjny mojego samochodu (nazwa) jest unikalny w przestrzeni nazw DMV mojego stanu, ale prawdopodobnie nie jest unikalny na świecie; inne stanowe DMV mogły używać tej samej nazwy we własnych przestrzeniach nazw. Heck, ktoś inny może mieć numer telefonu (imię i nazwisko), który również pasuje, ponieważ jest to kolejna przestrzeń nazw itp.

Identyfikatory UUID można postrzegać jako zamieszkujące pojedynczą przestrzeń nazw tak rozległą, że może zapewnić unikalną nazwę dla wszystkiego ; to właśnie oznacza „uniwersalny”. Ale jak odwzorować istniejące nazwy w innych przestrzeniach nazw na identyfikator UUID?

Jednym z oczywistych rozwiązań jest wygenerowanie UUID (V1 lub V4) dla każdego elementu w celu zastąpienia starych nazw w ich rozłącznych przestrzeniach nazw. Wadą jest to, że są dużo większe, musisz przekazać wszystkie nowe nazwy każdemu, kto ma kopię twojego zbioru danych, zaktualizować wszystkie twoje API itp. Szanse są takie, że nie możesz całkowicie pozbyć się starych nazw w każdym razie, co oznacza, że ​​teraz każdy przedmiot ma dwie nazwy, więc czy poprawiłeś sytuację?

Tutaj właśnie wkraczają V3 / V5. Identyfikatory UUID wyglądają tak samo losowo jak V4, ale w rzeczywistości są deterministyczne; każdy, kto ma odpowiedni identyfikator UUID dla przestrzeni nazw, może następnie niezależnie wygenerować ten sam identyfikator UUID dla dowolnej nazwy w tej przestrzeni nazw. Nie musisz ich w ogóle publikować ani nawet wstępnie generować, ponieważ każdy może je tworzyć w locie w razie potrzeby!

Nazwy DNS i adresy URL są bardzo często używanymi przestrzeniami nazw, dlatego opublikowano dla nich standardowe identyfikatory UUID; Nazwy ASN.1 OID i X.500 nie są tak powszechne, ale organizacje normalizacyjne je uwielbiają, więc opublikowały również dla nich standardowe identyfikatory UUID przestrzeni nazw.

W przypadku wszystkich innych przestrzeni nazw musisz wygenerować własny identyfikator UUID przestrzeni nazw (V1 lub V4) i przekazać go każdemu, kto tego potrzebuje. Jeśli masz kilka przestrzeni nazw, publikowanie identyfikatora UUID dla każdego z nich nie jest idealne.

Tutaj pojawia się hierarchia: tworzysz jeden „podstawowy” UUID (dowolnego typu), a następnie używasz go jako przestrzeni nazw do nazywania innych przestrzeni nazw! W ten sposób wystarczy opublikować podstawowy UUID (lub użyć oczywistego), a każdy może obliczyć resztę.

Na przykład, zostańmy, chcieliśmy stworzyć kilka UUID dla StackOverflow; który ma oczywistą nazwę w przestrzeni nazw DNS, więc podstawa jest oczywista:

uuid ns_dns = '6ba7b810-9dad-11d1-80b4-00c04fd430c8';
uuid ns_base = uuidv5(ns_dns, 'stackoverflow.com');

Sam StackOverflow ma osobne przestrzenie nazw dla użytkowników, pytań, odpowiedzi, komentarzy itp., Ale są one również dość oczywiste:

uuid ns_user = uuidv5(ns_base, 'user');
uuid ns_question = uuidv5(ns_base, 'question');
uuid ns_answer = uuidv5(ns_base, 'answer');
uuid ns_comment = uuidv5(ns_base, 'comment');

To konkretne pytanie to # 10867405, więc jego UUID będzie wyglądał następująco:

uuid here = uuidv5(ns_question, '10867405');

Zauważ, że w tym procesie nie ma nic losowego, więc każdy, kto postępuje zgodnie z tą samą logiką, otrzyma tę samą odpowiedź, ale przestrzeń nazw UUID jest tak rozległa, że ​​(efektywnie, biorąc pod uwagę bezpieczeństwo 122-bitowego skrótu kryptograficznego) nigdy nie zderzy się z UUID wygenerowany z dowolnej innej pary przestrzeń nazw / nazwa.


Zastanawiam się, dlaczego stackoverflow musi mapować unikalnie wygenerowaną dużą liczbę całkowitą na identyfikator UUID, biorąc pod uwagę, że jej interfejsy API najwyraźniej zwracają tylko dużą liczbę całkowitą jako ciąg. Gdzie byłby używany identyfikator UUID, jeśli nie w interfejsie API. Wygląda na to, że powinniśmy wybrać UUID lub BIGINT? Po co ta strategia hybrydowa. Jednak +1 za jasne wyjaśnienie w Twojej odpowiedzi.
nishant

4
UUID V3 / V5 zostały zaprojektowane z myślą o konieczności deterministycznej konwersji istniejących (i prawdopodobnie kolidujących) przestrzeni nazw do jednej przestrzeni nazw UUID, co jest często przydatne podczas scalania zestawów danych. Jeśli to nie dotyczy tego, co robisz, wybierz V1 / V4.
StephenS
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.