Czy Oracle przestawia bajty, czyli wszystko co powinieneś wiedzieć o GUID

Po pierwsze – dlaczego taki tytuł? Żeby było ciekawiej. Nie mam pojęcia, co POWINIENEŚ
wiedzieć o GUID-ach. Orientuję się za to, jaka jest moja obecna wiedza na ich temat i chciałbym się nią z Tobą podzielić.

Trochę historii

Jakiś czas temu implementowałem funkcjonalność związaną z, krótko mówiąc, wprowadzaniem i usuwaniem rekordów mających postać GUID z bazy danych Oracle 11g. Dla uproszczenia załóżmy, że tabela miała jedną kolumnę o nazwie ID i typie RAW(16). Taki rozmiar pozwalał akurat na umieszczeniu w niej obiektu klasy GUID. W celach testowych przygotowałem następujący kod obrazujący sytuację:

 Po jego uruchomieniu otrzymujemy wynik:

Kurczę – co tu się dzieje, myślałem. Pamiętajmy, że wierszy w tabeli było mnóstwo, a różnice występują tylko w bajtach 0-7 – trochę czasu zajęło zanim w ogóle zorientowałem się,  że mam problem…

W takiej sytuacji zazwyczaj pomaga StackOverflow, więc czytam. Odpowiedzi było mnóstwo, bo i pytań na ten i podobne tematy dużo. Z tego, co na szybko się zorientowałem, wyklepałem kod w stylu:

Uff… pożar zażegnany. Wszystko działa. I działało by, gdyby nie to, że po czasie zawieruchy nadeszła cisza morska i miałem trochę czasu dla siebie. Pamiętając o tym problemie, postanowiłem dojść rzeczywistej przyczyny problemu. Zacząłem czytać – najpierw StackOverflow, potem Wikipedię, następnie trafiłem na specyfikację RFC4122. Dawno się tak fajnie nie czułem – niby klasa, z którą ma się mnóstwo do czynienia i człowiek zna ją jak zły szeląg, ale jak wszystko – pod powierzchnią okazuje się już nie taka prosta i myślę, że warto przy tak fajnej okazji przedstawić uzyskane informacje w zwięzłej, przystępnej formie. Czy się uda? Oceń sam.

Tekst poniżej zawiera pewne uproszczenia, ale mam nadzieję, że nie zawiera błędów. Jeżeli
jakiś zauważysz, daj znać.

I. Co to jest GUID?

GUID (Globally Unique Identifier) lub inaczej UUID (Universally Unique Identifier) to dwa określenia na tę samą wartość liczbową o długości 128 bitów i zapisywaną zazwyczaj w postaci 32 cyfr w układzie heksadecymalnym, czasami przedzielonych myślnikami i okolonymi nawiasami sześciennymi, np.:

Wartości mają tę właściwość, że do zarządzania nimi (ich tworzeniem) nie jest wymagana żadna instytucja centralna. Innymi słowy, każdy może utworzyć GUID offline i mieć przekonanie (graniczące z pewnością, co pokażę później), że jest on unikalny. Nie jest tak w przypadku, powiedzmy, wartości int32 – nie postawiłbym dużej kwoty na to, że jeżeli wylosuję wartość 354958221, to przy dużej ilości losowań nie wypadnie ona ponownie.

 II. Do czego służy?

Opisywany w dokumencie RFC4122 algorytm tworzenia GUID-ów umożliwia generowanie do 10 milionów wartości na sekundę, na maszynę. To, w połączeniu ze stałym, dość małym rozmiarem (w porównaniu do alternatyw) ułatwia ich sortowanie, porządkowanie, czy przechowywanie w bazach danych. Powyższe zaś sprawia, że GUID-y nadają się do:

•  Tworzenia kluczy podstawowych w bazach danych. Mamy wtedy pewność, że są one unikalne nie tylko w obrębie jednego serwera/aplikacji.
• Stosowania ich jako części adresów URL dla zapewnienia ich unikalności
• Ogólnie rzecz biorąc: identyfikowania wszelkiego rodzaju obiektów (kont, encji, wpisów w rejestrze i wielu innych)

GUID-y służą jako podstawowy identyfikator w wielu systemach operacyjnych (głównie Microsoft Windows) oraz aplikacjach (np. Firefox czy inne przeglądarki).

 III. A do czego nie powinniśmy go używać?

Jak wszystko, GUID także nie jest złotym młotkiem. Używając go (jak każdego narzędzia), powinniśmy mieć świadomość innych opcji i zawsze zastanawiać się, czy warto. Np. ten
artykuł opisuje różnice między GUID i INT w bazach danych. Można w nim wyczytać różne za i przeciw każdego rozwiązania. Zazwyczaj wymieniane wady GUID-ów:

• Są 4 razy większe niż standardowe, czterobajtowe typy. Może to spowodować problemy z wydajnością. Z drugiej strony przestrzeń dyskowa jest bardzo tania.
• Nie można posortować wierszy w tabeli po kolejności wpisywania (jak w przypadku kluczy sekwencyjnych)
• Utrudniają debugowanie aplikacji (np. XXXX where ID=’00112233445566778899AABBCCDDEEFF’,  spróbuj się nie pomylić:) )

Uwaga: wg specyfikacji, nie powinno się używać GUID-ów jako identyfikatorów służących do
uzyskania dostępu. Są one na tyle łatwe do odgadnięcia, że nie powinny być stosowane jako hasła.

 IV. Inne ciekawostki

• Całkowita pula GUID-ów wynosi 2^122 czyli około 5.3×10^36
•  Pula GUID-ów w wariancie 10x, wersji 1 (tworzonych na podstawie daty, o co chodzi wyjaśnię za chwilę), wyczerpie się około roku 3400.
• 50% szansa kolizji w przypadku typu 32-bitowego wystąpi już dla ok. 77 tysięcy wartości. Dla GUID-ów jest to liczba ok. 2×10^19. Oznacza to, że gdyby każdy człowiek na Ziemi miał przypisane 600 milionów równomiernie rozłożonych wartości, prawdopodobnie któreś dwie byłyby takie same 🙂
• Interfejs IUnknown związany z komponentami COM zawiera GUID o wartości {00000000-0000-0000-C000-000000000046}

V. Struktura GUID-ów

Jak wiemy, GUID-y mają postać 128 bitowej liczby przedstawianej zwyczajowo jako ciąg pogrupowanych lub nie cyfr w układzie heksadecymalnym. GUID-y występują w kilku wariantach i wersjach (z ang. variants oraz versions) – zależy w jaki sposób zostały utworzone. Jeżeli spojrzymy na GUID:

xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxxm

to cyfry M oraz N określają odpowiednio jego wersję i wariant. Jeżeli idzie o wariant, to w naszym przypadku na pozycji N zawsze będą znajdować się cyfry z przedziału 8-B. Z pięciu zaś istniejących wersji najważniejsze dla nas mają numery 1 i 4, które są zarazem cyframi na pozycji M:

GUID tworzony na podstawie znacznika czasu (timestamp) (ver.1)

Oto GUID stworzony na podstawie czasu: ee829e52-ee7c-11e5-9ce9-5e5517507c66. Wprowadzając go na stronie https://www.famkruithof.net/uuid/uuidgen można sprawdzić, kiedy został stworzony:

GUID tworzony na podstawie liczb pseudolosowych (ver.4)

Wersja czwarta to nasz stary dobry znajomy – GUID z .Neta :)Oto GUID na podstawie liczb pseudolosowych: dc6887dd-261a-43f9-9bd1-1c5ebcfd39a9.  Algorytm tworzenia GUID-ów w wersji 4 jest ściśle związany z systemem, a ponadto odtworzenie liczby pseudolosowej raczej nie jest zbyt przydatne 🙂

VI. Implementacja w .Net

Wreszcie, trochę kodu. Już prawie zapomniałem, od czego się to wszystko wzięło 🙂 Otóż, gdy natknąłem się na problem z przestawianiem części GUID-ów, użyłem R# do dekompilacji źródeł klasy GUID i zobaczyłem tam cuda i cudeńka 🙂

Klasa ma jedno publiczną właściwość statyczną o nazwie Empty – jest to GUID złożony z samych zer. Poza tym ma pola prywatne o nazwach od _a do _k. Pierwsze z nich jest wartością int32, dwa następne short, a pozostałe to byte. Umieszczane są w nich poszczególne części GUID-a. Jak pamiętamy z podstaw informatyki, każdy bajt złożony jest z ośmiu bitów i wystarczy on akurat do zapisu dwóch cyfr heksadecymalnych, z których każda przyjmuje wartość 0x0-0xF (0-15 w zapisie dziesiątkowym). Stąd 128 bitów GUID-a podzielone na 4 bity na cyfrę, daje nam 16 cyfr heksadecymalnych. Pierwszych osiem – czyli 32 bity będzie zapisane w polu int _a, kolejne dwa pakiety po 4 będą w zmiennych _b i _c (short), a następnych 16, po dwa w ośmiu zmiennych _d-_k (byte). Tworzymy zatem GUID:

var testGuid = Guid.Parse(„00112233-4455-6677-8899-AABBCCDDEEFF”);

lub

var testGuid = new Guid(„00112233-4455-6677-8899-AABBCCDDEEFF”);

W okienku QuickWatch widzimy wnętrzności zmiennej:

Trzydziestodwubitowe pole _a o wartości dziesiątkowej 1122867 przechowuje pierwszy człon GUID-a, czyli „00112233”. Jeżeli zamienimy wartość int prostym kodem (Convert.ToString(_a, 2).PadLeft(32,’0′)) na bity, otrzymamy:
00000000-00010001-00100010-00110011 czyli właśnie 00-11-22-33. Magii nie ma – w przypadku pozostałych pól jest tak samo.

Jednak skądś ten mój pierwotny problem wynikł, a powstał on gdy użyłem konstruktora przyjmującego tablicę bajtów. Szybki podgląd źródeł i mamy winowajcę:

Rzeczywiście – bajty 8-15 będą przetworzone poprawnie, ale przy polach _a,_b_c dzieje się magia. Są one przesuwane tak, że bajt o indeksie 3 (czwarty w tablicy) staje się bajtem najstarszym (pierwszym, o indeksie zerowym) w wartości int _a. Kolejno po nim ustawiane są bajty drugi, pierwszy i zerowy!Tak samo w przypadku szortów – bajty mające w tablicy wyższy indeks stają się pierwsze. Oczywiście w przypadku pól _d-_k nie ma mowy o przesuwaniu, bo są to zmienne jednobajtowe. A więc co łączy pierwsze trzy pola? Długość większa, niż jeden bajt, powiesz pewnie. I to prawda. I pewnie od razu na myśl przychodzi Ci problem końcówki jajka, czyli „endianness” 🙂 Tak – strzał w dziesiątkę! Po chwili wyszperałem nawet świetny post Erica Lipperta (nawiasem mówiąc, jednego z najlepszych ekspertów od .Net)

Tak jak w przypadku bitów w bajcie, nie będę testował Twojej cierpliwości i powiem tylko, że tu jest pies pogrzebany – konstruktor GUID-a przyjmuje, że wartości kilkubajtowe są zapisane w formacie, gdzie najbardziej znaczący bajt jest ostatni – czyli w formacie Little Endian. Stąd przy tworzeniu GUID-a z tej tablicy, „prawidłowa” kolejność jest przywracana i stąd zjawisko, którego doświadczyłem 🙂  A ja chciałem zrzucić to wszystko na biedne Oracle 🙂

Podsumowując

Co nagle to po diable – być może, gdybym zastanowił się bardziej na początku, nie musiałbym sprawdzać wnętrzności GUID-ów, przez co na pewno byłoby szybciej, ale i nie miałbym szansy dowiedzieć się paru ciekawostek i przedstawić ich Tobie.Przepraszam za formatowanie tego posta – stanowczo nie jestem zawodowcem i nie zamierzam się bić z Bloggerem, który z uporem maniaka zmienia mi układ tekstu.Temat też na pewno nie jest wyczerpany i wydaje mi się – że jest nierówny – raz piszę jak dla początkującego, raz staram się wyciągać bardziej zaawansowane rzeczy. To dlatego, że sam nie wiem, do kogo kierować moje teksty.Być może następnym razem będzie lepiej – do następnego razu zatem.