Kiedy użyjesz długiego łańcucha ID zamiast prostej liczby całkowitej? [Zamknięte]

54

Chciałbym użyć Youtube jako przykładu: używają identyfikatorów w postaci PEckzwggd78.

Dlaczego nie używają prostych liczb całkowitych?

Lub imgur.com - używają również identyfikatorów, takich jak 9b6tMZSzdjęcia i galerie. Nie sekwencyjne liczby całkowite.

  • Dlaczego nie używają liczb całkowitych (szczególnie sekwencyjnych)?

  • W jakich przypadkach rozsądną decyzją jest stosowanie takich identyfikatorów ciągów zamiast liczb całkowitych?

Rakori
źródło
47
Co sprawia, że ​​uważasz, że identyfikatory nie są zwykłymi liczbami całkowitymi? Znam wiele usług internetowych, które używają liczb całkowitych w DB, ale wyświetlają je w pewnym kodowaniu base64, więc adresy URL wyglądają ładniej. Co ciekawe, identyfikatory YouTube prawie odwzorowują 64-bitowe liczby całkowite.
Josef
2
@rwong Ale OPs pyta, dlaczego nie używają identyfikatorów numerycznych, a odpowiedź może brzmieć: używają identyfikatorów numerycznych, po prostu wyświetlają je w base64 zamiast base10 lub base2. Nie wiem tego jednak na pewno, więc pytam OP, co konkretnie sprawia, że ​​sądzą, że identyfikatory nie są zwykłymi liczbami całkowitymi 64-bitowymi w base64.
Josef
3
Czy to nie to samo, co to .
the_lotus

Odpowiedzi:

101

YouTube nie może używać sekwencyjnych identyfikatorów z dwóch powodów:

  1. Jego bazy danych są prawie na pewno rozproszone, co komplikuje numerowanie sekwencyjne.

  2. Ma opcję prywatności „Filmy niepubliczne”: te, które nie pojawiają się w wynikach wyszukiwania, ale są dostępne, jeśli znasz identyfikator.

Dlatego identyfikatory wideo powinny być w miarę losowe i nieprzewidywalne. To, czy identyfikator jest reprezentowany tylko przez cyfry, czy przez kombinację liter i cyfr, nie ma znaczenia: istnieje trywialne mapowanie z jednej reprezentacji na drugą.

IMil
źródło
11
Identyfikatory numeryczne nie muszą być sekwencyjne
Sopel
28
@Sopel Myślę, że punktem IMil jest to, że Youtube musi generować rzadkie identyfikatory. Innymi słowy, jeśli szacuje się, że będziesz musiał tylko przechowywać 2^40przedmioty, w niektórych architekturach istnieją uzasadnione powody, aby wybrać przestrzeń 2^80lub 2^120bity. Przykłady przyczyn: ograniczenie kolizji bez technicznego sprawdzania kolizji; wykorzystanie rzadkości kluczy w ramach utrudniania odnalezienia tajemnic („wideo niepubliczne”) itp.
rwong
13
@Opel brzmiał: „Dlaczego nie używają liczb całkowitych (szczególnie sekwencyjnych)?” Wyjaśniam, że: 1) sekwencyjne identyfikatory są niepożądane; 2) liczby całkowite i ciągi są w zasadzie to samo
IMil
3
Klauzula „dlatego” nie jest logicznie zgodna, ale dwa ponumerowane punkty są poprawne. Jako przykład tego, dlaczego losowość nie jest koniecznym następstwem: numerowanie sekwencyjne z jednolitymi przerwami będzie działać w celu zapewnienia unikalnych identyfikatorów w wielu niezależnych bazach danych, tak aby wyniki można było łączyć w magazynie danych - jest to forma dzielenia na fragmenty. To znaczy, załóżmy, że nie spodziewasz się więcej niż 10000 regionalnych baz danych (być może masz teraz tylko 10, więc 10000 wystarczy). Wtedy każdy db może mieć kolumnę tożsamości zliczającą 10000 z unikalnymi 4 ostatnimi cyframi, nie będzie kolizji podczas scalania.
davidbak
2
@davidbak wymóg losowości wynika z (2). Niepowtarzalność można rzeczywiście uzyskać poprzez przypisanie nie nakładających się zakresów do różnych instancji bazy danych, ale pozostawiłoby to identyfikatory przewidywalne.
IMil
75
  • W postaci identyfikatorów: Oni używają Base64 (za pomocą znaków a- z, A- Z, 0- 9, -, i _). To pozwala im mieć 6 bitów informacji na znak. YouTube używa 11-znakowych identyfikatorów wideo, co oznacza, że ​​mogą wygenerować 2 6 * 11 lub więcej niż 7 * 10 19 identyfikatorów. Jak to ujął Tom Scott , „wystarczy, aby każdy człowiek na Ziemi mógł przesyłać filmy co minutę przez około 18 000 lat”. Base64 jest również łatwy w obsłudze, ponieważ 64 to potęga 2, co oznacza, że ​​każdy znak reprezentuje dokładną liczbę bitów. Używamy systemu szesnastkowego (podstawa 16) z tego samego powodu.

  • Ze względu na niesekwencyjny charakter identyfikatorów: oznacza to, że nie potrzebują zsynchronizowanego licznika między wszystkimi serwerami, które przypisują identyfikatory do filmów. Mogą po prostu wygenerować losową liczbę, sprawdzić, czy jest już w użyciu, i przejść od tego momentu. Mogą nawet przypisać każdemu serwerowi blok identyfikatorów do wyboru i wyeliminować sprawdzanie duplikacji. Nie wiem, czy oni to robią, ale mogli.

  • Innym powodem niesekwencyjnych identyfikatorów jest to, że właśnie dzięki temu działają filmy „niepubliczne”. Są to filmy, które nie pojawią się w wynikach wyszukiwania lub jako sugestie, ale są dostępne, jeśli masz link. Jeśli korzystasz z liczenia sekwencyjnego, możesz po prostu przejść do filmu, zwiększyć identyfikator o jeden, a pomysł niepublicznych filmów wideo jest teraz zepsuty.

  • Identyfikatory niesekwencyjne pomagają również ukryć informacje przed konkurentami, takie jak łączna liczba filmów lub liczba filmów przesłanych w określonym przedziale czasowym.

Mogę bardzo polecić wideo Toma Scotta . Jego informacje są prawie zawsze zarówno interesujące, jak i dokładne.

rchard2scout
źródło
6
Zwróćmy też uwagę, że 11 znaków kodowania base64 przechowuje 66 bitów informacji, co oznacza, że ​​mogą łatwo zamapować 64-bitową liczbę całkowitą na taki ciąg. Czyli wewnętrznie mogliby użyć 64-bitowej int (ale nie muszą tego robić).
Bernhard Hiller
1
Dla porównania, konwencjonalna reprezentacja dziesiętna może wymagać aż 20 znaków, „marnując” do 9 znaków w porównaniu z Base64.
dan04
Film Toma Scotta wyjaśnia to doskonale.
AGB
13
  • Liczby całkowite nie skalują się tak dobrze, „normalna” 32-bitowa liczba całkowita bez znaku może przekroczyć nieco ponad 4 miliardy.

  • Mogą nie chcieć, abyś wiedział, ile przedmiotów ma w Internecie, lub śledził tempo wzrostu.

  • Litery mogą zawierać więcej informacji niż cyfry, potrzebujesz mniej liter, aby wyrazić ten sam „numer”. W przypadku dużej bazy danych indeksatora może to być suma.

Martin Maat
źródło
7
1) można użyć int 64
Rakori
4
2) dlaczego? ........... i tak wszystkie są publiczne. te, które nie są publiczne - nie są dostępne. to wszystko
Rakori,
3
3) Czy potrafisz opracować? wyrazić jakie informacje?
Rakori
2
Dla 1: to samo dotyczy int32 i int64. Chociaż int64 jest potencjalnie znacznie większy, może nie być wystarczająco duży.
Nepho
3
W bazie danych zapisałeś numer jako liczbę. Tak więc 32-bitowa int zajęłaby 32 bity. Tekst miałby mniejszą gęstość (o ile uboższy tekst
zależałby
8

1) Dlaczego niektóre strony internetowe używają liter w swoich identyfikatorach? Czy to są sznurki?

Nie wiemy, czy strony te przechowują identyfikatory w swojej bazie danych jako ciągi znaków. Liczby i ciągi znaków są w rzeczywistości takie same dla komputerów. Łańcuch to tylko liczba, pokazana na innej podstawie. 'A' = 0x41 = 65 = 0b1000001, dla komputera wszystko jest takie samo. Ale jeśli go wyświetlisz, im większa baza, tym krótsza reprezentacja i krótsze adresy URL są łatwiejsze do odczytania i udostępnienia dla ludzi. Strony takie jak YouTube i Imgur używają bazy 62 (litery, wielkie i małe litery oraz cyfry) lub większej (dodaj myślnik lub inne prawidłowe znaki adresu URL), co jest względnie krótkie dla dużych liczb. Z czego wolisz korzystać youtu.be/23489234892348234933lub youtu.be/B9k6KMrv8vh?

2) Dlaczego używane są niesekwencyjne identyfikatory?

Odpowiedź IMil dobrze to wyjaśnia:

YouTube nie może używać sekwencyjnych identyfikatorów z dwóch powodów:

  • Jego bazy danych są prawie na pewno rozproszone, co komplikuje numerowanie sekwencyjne.

  • Ma opcję prywatności „Filmy niepubliczne”: te, które nie pojawiają się w wynikach wyszukiwania, ale są dostępne, jeśli znasz identyfikator.

Wyjaśniają one również, dlaczego identyfikatory są tak duże: (oczywiście YouTube nie obsługuje 23 489 234 892 348 234 933 różnych filmów)

  • Podczas generowania identyfikatorów problemem jest przypadkowe dwukrotne wygenerowanie tego samego identyfikatora, dlatego potrzebujesz dużej przestrzeni na identyfikatory, aby zapobiec problemowi z urodzinami

  • Ludzie mogą po prostu odgadnąć adres URL niepublicznych filmów, jeśli szansa na użycie dowolnego ważnego identyfikatora w filmie nie jest bardzo, bardzo mała.

Jasmijn
źródło
3
> „YouTube nie obsługuje 23 489 234,892,348,234,933 różnych filmów, oczywiście” Nie jestem pewien, czy to oczywiste, czy nie;)
unperson325680
People can just guess the URL of unlisted videos if the chance of any given valid ID being used for a video isn't very, very small.- skąd wiesz, że film niepubliczny nie jest dostępny dla wszystkich oprócz jego autora? nawet jeśli ktoś odgadł jego identyfikator
Rakori
1
@Rakori, bo tak działa YouTube.
Josef
2
@progo Chodzi mi o to, że każda osoba na świecie przesłała średnio 3,3 miliarda filmów na YouTube ...;)
Jasmijn
5

dlaczego nie tylko liczby całkowite, szczególnie sekwencyjne? A kiedy, w jakich przypadkach rozsądną decyzją jest taki ciąg znaków zamiast liczb całkowitych?

  • Lepsza spacja UTF-8 - kiedy zamieniasz liczbę w ciąg, otrzymujesz maksymalnie 10 kombinacji na znak (0-9), ale gdy dopuścisz dowolne znaki alfanumeryczne, otrzymasz 62 kombinacje na znak (az, AZ, 0-9 ), więc używając ciągów alfanumerycznych możesz utworzyć krótsze adresy URL niż w przypadku użycia ciągów numerycznych. Jest to ważne w przypadku witryn, w których użytkownicy udostępniają adresy URL - takich jak Youtube i Imgur.
  • Sekwencyjne liczby całkowite są trudniejsze do wytworzenia. Aby utworzyć sekwencyjną rosnącą liczbę całkowitą, musisz albo jeden wątek wygenerował liczby, albo skoordynować wiele hostów w systemie rozproszonym, a gdy uruchomisz aplikację o dużej objętości, taką jak Youtube lub Imgur, która nie skaluje się tak ładnie jak losowo generowany ciąg (żeby nie powiedzieć, że losowo generować)

Nawiasem mówiąc, niekoniecznie jest tak, że wewnętrzna reprezentacja jest łańcuchem. Prawdopodobnie mogą kodować identyfikator numeryczny jako ciąg alfanumeryczny dla krótszego adresu URL.

Samuel
źródło
1
2) w przypadku identyfikatora ciągu, ale przed wstawieniem nowego rekordu do bazy danych należy sprawdzić, czy identyfikator łańcucha został już wygenerowany. jaka jest zatem różnica z int ID?
Rakori
@ Rakorin Nawet przy użyciu czegoś tak prostego jak UUIDv4 szansa na kolizję jest znikoma. Użyj wystarczającej liczby losowości, a szansa praktycznie nie istnieje, więc duplikacja nie musi tak naprawdę być sprawdzana.
Andy
1
@davidpacker i czym to się różni od generowania dłuższej liczby całkowitej?
Sopel
@Sopel Jak zauważył Samuel, liczby całkowite zajęłyby więcej miejsca, tj. Byłyby dłuższe niż łańcuchy. W przeciwnym razie naprawdę nie ma żadnej różnicy.
Andy,
1
@davidpacker tylko po wydrukowaniu
Sopel
2

Jak już wskazał, że byłoby to łatwe w użyciu powszechnie unikalny identyfikator tylko przy użyciu numerów, bo pod maską wszystko jest po prostu 0i 1i można zwiększyć liczbę do bardziej precyzyjnego podchodząc do 128 bitów lub więcej.

Myślę, że głównym powodem jest to, że zakładając dowolny ustalony zakres, taki jak uint32(na przykład), jeśli używasz również liter, możesz mieć w sumie krótszy identyfikator.

Wyobrażam sobie, że jest to uzasadnienie estetyczne adresu URL. Zamiast mieć 4,129,873,773litery, jest znacznie krótszy Fu837t(po prostu fikcyjny wymyślony przeze mnie). Użytkownik może nawet zapamiętać adres URL w celu przekazania go znajomemu. Platformy takie jak Youtube zwykle mają dłuższe UUID niż 32 bity, ponieważ szybko zabraknie im miejsca.

Ewald B.
źródło
3
Myślę, że to odpowiedź. Używanie ciągów nie jest ani bardziej wydajne, ani łatwiejsze do zachowania wyjątkowości. Powodem jest to, że łatwiej jest reprezentować jako adres URL
Sopel
jeśli użytkownik jest w stanie zapamiętać Fu837t, ale czy nie pamięta 2390?
Rakori
4
@Rakori: Fu837t byłby porównywalny z 2223955238, więc tak. 2390 byłby zakodowany jako „Vg”, więc: również tak.
Mooing Duck
@MooingDuck, no. Skąd wiesz, jaki jest algorytm generowania tego identyfikatora ciągu?
Rakori
3
@ Rakori to nie algorytm, to kodowanie. Istnieją algorytmy do przesyłania liczb między różnymi kodowaniami, ale który z nich jest używany, nie ma znaczenia, dopóki kodowanie jest dobrze zdefiniowane. Bezpieczne kodowanie base64 w adresach URL jest dobrze znane i znormalizowane .
Josef
2

Krótki URL jest pożądany, ponieważ upraszcza łączenie i udostępnianie (np. Możesz udostępnić link w SMS-ie, szybciej jest pisać i tak dalej). Usługi takie jak Youtube lub Imgurl chcą, aby adresy URL były udostępniane swobodnie, więc jest to ważna kwestia.

Używanie alfanumerycznych identyfikatorów zamiast liczb oznacza, że ​​potrzebujesz mniej znaków, aby wyrazić identyfikator o tym samym rozmiarze bitowym. Na przykład 6 cyfr daje milion unikalnych identyfikatorów, ale 6 znaków alfanumerycznych (przy użyciu zestawu base64) daje 68 miliardów unikalnych identyfikatorów.

Z tego co wiemy, alfanumerycznymi identyfikatorami mogą być kolejne numery, po prostu zakodowane w formacie alfanumerycznym, takim jak base64. Jednak często usługi komercyjne unikają kodów sekwencyjnych, aby ludzie nie zgadywali identyfikatorów i nie ujawniali informacji biznesowych, takich jak liczba klientów.

JacquesB
źródło
1

Istnieje kilka powodów, dla których warto używać identyfikatorów nienumerycznych, ale rozumiemy również, że nie wszystkie wartości ze znakami alfabetycznymi są tak naprawdę łańcuchami. YouTube ma reputację niewiarygodnej liczby filmów, rzędu 300 godzin filmów przesyłanych co minutę ( ref ). Unikalne liczby całkowite reprezentujące te filmy mogą być dość długie, więc użyj czegoś takiego jak liczby zakodowane w formacie Base64 URL ( ref ).

Rodzaje reprezentacji identyfikatorów:

  • Proste liczby całkowite: (12345, 981027489382493)
  • Podstawowa liczba całkowita 16: 123456789abcdef - znana również jako Hex
  • Podstawowa liczba całkowita 64: 9b6tMZS
  • Ciągi czytelne: 12032017-Read-my-awesome-article-01

Wszystkie mają swoje mocne i słabe strony. Im więcej unikatowych znaków możesz użyć do identyfikatorów, tym mniej znaków potrzebujesz do reprezentowania liczby. Podstawowe liczby 64 są dość dobrym kompromisem, ponieważ istnieje ustalony wariant, który działa dla adresów URL i kompresuje liczbę znaków potrzebnych do przedstawienia liczby od 6 do 8 (tj. 3/4 rozmiaru).

Czytelne ciągi działają w przypadku blogów, ponieważ mogą zwiększyć możliwości wyszukiwania, a znacznie łatwiej jest generować unikalne tytuły, gdy liczba rekordów jest niewielka.

Berin Loritsch
źródło
1

Mieszanie treści

Słowa „hash” nie ma w istniejących, fajnych odpowiedziach, więc zaczynamy:

Często dane można rozpoznać po wartości mieszania zamiast niezależnego, sztucznego identyfikatora. Jest to szczególnie widoczne w oprogramowaniu gitlub systemach plików, takich jak ZFS, w których ta szczególna właściwość używania skrótów zawartości nie tylko ułatwia rzeczy (na przykład usuwanie duplikatów), ale ma także inne miłe właściwości, takie jak trywialne buforowanie, bezpieczna historia, wykrywanie zgnilizny bitów itp.

Hashe zwykle występują jako liczby szesnastkowe (lub nawet większa przestrzeń na litery), dlatego nie widzisz liczb całkowitych. Po prostu to nie ma liczb całkowitych (w tych przypadkach).

Hashe są dobre, jeśli obiekty danych są niezmienne (jak w ZFS lub git); świetnie nadają się do przechowywania obrazów, na przykład na dużych sieciach CDN. Nie wiem, czy te konkretne identyfikatory faktycznie skrótami, ale z pewnością miałoby to sens (i jak skomentował Michael Kjörling, krótkie identyfikatory prawdopodobnie nie są skrótami z oczywistych powodów - dla porównania, git używa wartości SHA-1, które są 20 bajtami lub 40 cyfry szesnastkowe).

AnoE
źródło
1
Przynajmniej identyfikatory filmów na YouTube są za krótkie, by je haszować. Obowiązuje paradoks urodzinowy; krótko mówiąc, z przestrzenią haszową n bitów, zaczniesz widzieć kolizje po zobaczeniu 2 ^ (n / 2) obiektów blob wejściowych. Z około 60-70 bitów w identyfikatorze, to 30-35 bitów wyjątkowości lub kilka miliardów pozycji. Jestem prawie pewien, że do tej pory hostują więcej filmów. I oczywiście większość skrótów to liczby całkowite w porządku; że zwykle nie są drukowane w postaci dziesiętnej, nie ma wpływu na to, czy są liczbami całkowitymi. Trzeba przyznać, że te same dane można prawdopodobnie interpretować jako zmiennoprzecinkowe dane binarne ...
CVn
3
@ MichaelKjörling: Cóż, identyfikatory filmów na YouTube są zbyt krótkie, aby mogły być hashami kryptograficznymi , ale istnieje wiele funkcji mieszających, które mają 64 bity wyjściowe lub mniej - CRC-16/32/64, Java hashCode()itp. Oczywiście im krótszy hash, tym bardziej prawdopodobne są losowe kolizje.
dan04
Jeśli chcesz, aby ludzie pamiętali adres URL, nie rozróżniałbyś wielkości liter. A wymawianie „górnej” lub „dolnej” przed każdą literą jest znacznie mniej skuteczne niż zwykłe wypowiadanie liczb.
Lenne
0

Ok jednym z powodów jest to, że znaki są wysyłane jako znaki, a nie jako liczby całkowite. Wynika to z działania HTTP Get.

Kiedy mówisz: „dlaczego nie użyć liczby całkowitej?” Cóż, liczba całkowita jest następnie dzielona na części, a każda cyfra jest wysyłana jako znak, a ty i tak otrzymujesz ciąg znaków. Dlaczego więc nie wykorzystać wszystkich opcji dla postaci?

Istnieje również czynnik ludzki:

Weźmy na przykład imgur: https://imgur.com/ ***** / s6UqP

s6UqP,

Zakres każdego znaku wynosi: od a do z kapitału, od a do z pod kapitału i od 0 do 9 = 26+ 26+ 10 = 62 opcje dla każdej pozycji w ciągu. Z pięcioma pozycjami, czyli 916132832 możliwych kombinacji. Jeśli użyjesz tylko cyfr, potrzebujesz 9 cyfr.

Ludzie mogą przechowywać w pamięci około 7 obiektów, 9 cyfr to za dużo, wykonalnych jest 5 znaków.

Magiczna liczba 7

Pieter B.
źródło
Pamięta Gfycat: używają trzech słów, dwóch przymiotników i imienia zwierzęcia. Ponieważ istnieje wiele możliwości ( 1502 reklamy i 1751 zwierząt ), mają one ponad 3 miliardy kombinacji przy użyciu tylko trzech obiektów.
Gustavo Rodrigues