Cześć!
W swojej aplikacji pisanej w Javie muszę wygenerować unikalny ciąg maksymalnie 8 liter i cyfr, który zostanie następnie przypisany do rekordu w bazie danych. Jakieś pomysły na eleganckie rozwiązanie, bez każdorazowego sprawdzania czy wygenerowany ciąg znajduje się już w bazie?
0
0
unikalny ciąg
maksymalnie 8 liter i cyfr
Kolego to sie nie dodaje. To sie nazywa perpetuum mobile :)
Musisz po prostu generowac losowy ciąg i jakoś handlować duplikaty.
6
W dużym skrócie - nie da się.
Masz dokładnie 8 znaków, każdy może być załóżmy dowolną literą lub cyfrą ASCII - jest ich łącznie 62 (26 dużych liter, 26 małych i 10 cyfr). Zaokrąglijmy do 64, żeby się wygodniej liczyło - np. zamiast tylko liter i cyfr weźmy zestaw znaków odpowiadających Base64.
64 możliwe wartości (znaki) możesz przedstawić na 6 bitach. 8 znaków po 64 możliwe wartości każdy daje nam całe 48 bitów... przypomnę, że funkcja skrótu MD5 ma 128 bitów i już od wielu lat jest uznawany za ani trochę bezpieczny, bo ryzyko złamania za duże (czyt. zbyt szybko dałoby się znaleźć kolizję) :) Z 48 bitami ryzyko kolizji i przypadkowego wygenerowania dwóch takich samych ciągów będzie jeszcze większe, szczególnie jeśli zakładasz brak możliwości sprawdzenia czy nie występuje kolizja to nie możesz temu przeciwdziałać.
Spójrz na ten kalkulator - 62-znakowy "alfabet", 8 znaków, 1000 IDków na sekundę i już po niecałej godzinie masz 1% szans na kolizję. Czy 1000 IDków na sekundę to dużo? Nawet jeśli, to przy 10 IDkach na sekundę masz 1% szans na kolizję już po 2 dniach.... Czy chciałbyś mieć 1% szans na to, że w ciągu najbliższych dwóch dni przepiszesz komuś konto bankowe na kogoś innego i Cię pozwie? :)
Chcesz czegoś w miarę pewnego (tzn. z nieporównywalnie mniejszym ryzykiem kolizji) -> użyj UUID lub GUID.
2
bierzesz kolejną wartość z sekwencji (czy co tam twoja baza ma), zamieniasz na hexa i uzupełniasz 0 z przodu do 8 znaków - proste, szybkie i pewne
3
Oczywiście, że się da -- pod warunkiem, że masz kontrolę nad bazą danych (to znaczy, że nikt Ci tam nie wpisuje swoich ciągów, tylko wszystko robi jeden algorytm) i ciągi są indeksowane. Robisz funkcję skrótu indeks -> ciąg, która się sensownie zachowuje i już. Trzeba trochę pogrzebać, ale się znajdzie.
Oczywiście, to się kiedyś kończy (masz skończoną liczbę możliwych ciągów) i masz tego świadomość? :)
superdurszlak napisał(a):
W dużym skrócie - nie da się.
[...]
Zgoda z wywodem @superdurszlaka, ale OP nie pisał nic o bezpieczeństwie... Pytanie było czysto matematyczne. :)
2
koszalek-opalek napisał(a):
Oczywiście, że się da -- pod warunkiem, że masz kontrolę nad bazą danych (to znaczy, że nikt Ci tam nie wpisuje swoich ciągów, tylko wszystko robi jeden algorytm) i ciągi są indeksowane. [...]
Sam sobie odpowiadam :), bo przyszło mi właśnie do głowy, że przecież można jeszcze inaczej (nieco oszukując). :) Skoro i tak chcesz to trzymać w bazie danych, to może wystarczy założyć unikalny indeks na pole z tym ciągiem (albo i zrobić z tego klucz główny!) i wtedy wkładasz do bazy po prostu ciąg losowy, a baza odrzuca Ci takie, które już są -- i lecisz z tym w pętelce...
4
maksymalnie 8 liter i cyfr
Zmieniamy to na UUID i problem sam się rozwiązuje.
0
@Paweł Grabowski: Poszukaj coś o generatorach w postaci rejestrów przesuwnych ze sprzężeniami zwrotnymi, one generują ciąg pseudolosowy o niepowtarzających się wartościach w okresie.
0
Pierwsze pytanie: po co? Select count aż tak dużo kosztuje?
Generowanie 8 znakowego napisu:
UUID.randomUUID().toString().substring(32+4-8)
Bez sprawdzania w bazie:
Sprawdzaj w pamięci RAM (zbiór jednorazowo inicjalizuj i dodawaj do zbioru po pomyślnym wstawieniu do bazy), o ile masz jakiś jeden punkt gdzie to możesz sobie trzymać (jeden serwer). Milion rekordów razy 6 bajtów to bardzo mało, nawet po opakowaniu w jakiś HashSet (bo czas wyszukiwania O(1) byłby bardzo wskazany). Dla przypadków miliardów+ rekordów można użyć OBDD, które zbiory nieporównywalnie większe niż 2^48 zjadają na śniadanie.
superdurszlak napisał(a):
64 możliwe wartości (znaki) możesz przedstawić na 6 bitach. 8 znaków po 64 możliwe wartości każdy daje nam całe 48 bitów
4
Pierwsze pytanie: po co? Select count aż tak dużo kosztuje?
Mam nadzieje ze to żart, ale nawet wtedy dość słaby. Wiesz co to race condition albo https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use ? :)
Generowanie 8 znakowego napisu:
Aaaa to już w ogóle jakieś szaleństwo i ABSOLUTNIE NIE WOLNO tak robić. Po pierwsze niektóre bity UUIDa nie są takie losowe jak może ci się wydawać (do poczytania np. https://devblogs.microsoft.com/oldnewthing/20080627-00/?p=21823 ) i jakiekolwiek substringowanie działa bardzo źle. Co więcej jak obcinasz do 8 znaków to nadal obniżasz entropię i to dość mocno więc możesz sobie nie sprawdzać w bazie tylko że kolizje będą non stop.
Sprawdzaj w pamięci RAM
To niekoniecznie da się zrobić bo co jak masz mikroserwisy i wiele nodów? Nawet jak będziesz rozsyłać do wszystkich eventy że dane id jest "zajęte" to nadal możesz mieć kolizje przy race condition.
0
Shalom napisał(a):
Sprawdzaj w pamięci RAM
To niekoniecznie da się zrobić bo co jak masz mikroserwisy i wiele nodów? Nawet jak będziesz rozsyłać do wszystkich eventy że dane id jest "zajęte" to nadal możesz mieć kolizje przy race condition.
Nie mówiąc o jeszcze prostszej sytuacji, gdy ten program generujący identyfikatory po prostu wyłączymy (albo się samy wywali/wyłączy), a potem włączymy ponownie. Pamięci RAM już nie masz po starym...
0
Shalom napisał(a):
Pierwsze pytanie: po co? Select count aż tak dużo kosztuje?
Mam nadzieje ze to żart, ale nawet wtedy dość słaby. Wiesz co to
race conditionalbo https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use ? :)
Nie żart, tylko skrót myślowy. Zagadnienia znam :)
Miałem na myśli model jednej (edit: jedna instancja na jednej JVM) aplikacji z sekcją krytyczną obejmującą i sprawdzenie i insert. Alternatywnie opakowanie sprawdzenia+inserta|rollbacka w izolowaną transakcję.
Bez tego kolizje oczywiście będą, i trzeba je będzie obsługiwać. Chodziło to, że wstępne sprawdzenie istnienia w bazie pozwoli bardzo mocno ograniczyć liczbę nieudanych insertów.
Shalom napisał(a):
UUIDa nie są takie losowe
OK, racja, poczytałem sobie, popatrzyłem na implementację tej metody, faktycznie jest obniżana entropia.
Czy to jest problem to tylko kwestia rzędu wielkości zapisywanych rekordów. Jeżeli OP przewiduje 10 rekordów na miesiąc to nic to nie zmieni.
Jeżeli jest potrzebna silna entropia to lepiej będzie np. wziąć
java.security.SecureRandom.nextBytes(byte[] bytes)
i zamienić je na napis.
W sumie to generowanie napisu to jest offtopic, OP o to nie pytał :)
Shalom napisał(a):
Sprawdzaj w pamięci RAM
To niekoniecznie da się zrobić bo co jak masz mikroserwisy i wiele nodów? Nawet jak będziesz rozsyłać do wszystkich eventy że dane id jest "zajęte" to nadal możesz mieć kolizje przy race condition.
pisałem:
o ile masz jakiś jeden punkt gdzie to możesz sobie trzymać (jeden serwer)
ale takie rozwiązanie by wówczas obniżało szansę kolizji, a nie eliminowało.
koszalek-opalek napisał(a):
Nie mówiąc o jeszcze prostszej sytuacji, gdy ten program generujący identyfikatory po prostu wyłączymy (albo się samy wywali/wyłączy), a potem włączymy ponownie. Pamięci RAM już nie masz po starym...
pisałem:
zbiór jednorazowo inicjalizuj
i chodziło mi oczywiście o wczytanie statyczne wszystkich identyfikatorów do RAMu w momencie startu (edit: z bazy danych)
0
Z ciekawości sprawdziłem jak w praktyce jest obniżona ta entropia, i mi wychodzi że niewiele, o ile nie popełniłem buga:
import java.security.SecureRandom;
import java.util.List;
import java.util.Map;
import java.util.UUID;
import java.util.function.LongFunction;
import java.util.stream.Collectors;
import java.util.stream.LongStream;
import org.apache.commons.codec.binary.Hex;
public class DebugLongStream {
public static void main(String[] args) {
test(x -> UUID.randomUUID().toString().substring(32 + 4 - 8));
SecureRandom rng = new SecureRandom();
test(x -> {
byte[] bytes = new byte[4];
rng.nextBytes(bytes);
return new String(Hex.encodeHex(bytes));
});
}
private static void test(LongFunction<String> mapper) {
Map<String, List<String>> s = LongStream.range(1, 10_000_000).mapToObj(mapper).collect(Collectors.groupingBy(Object::toString));
int[] count = new int[2];
count[0] = 0;
count[1] = 0;
s.forEach((l, list) -> {
if (list.size() > 1) {
// System.out.println(l + "==" + list.size());
count[0]++;
count[1] += list.size();
}
});
System.out.println("klas równoważności==" + count[0]);
System.out.println("elementów w klasach==" + count[1]);
}
}
klas równoważności==11721
elementów w klasach==23453
klas równoważności==11618
elementów w klasach==23245
1
Patrząc na ten kod powyżej zauważyłem ze to jeszcze większy hardkor niż myślałem wcześniej :D Bo to nie jest 8 znaków, tylko 8 hexów! Znaki są tylko 0-9a-h czyli masz tam raptem 4 (!) bajty entropii a nie 8. Czyli z birthday attack masz 50% na kolizje po raptem 2^16 ID czyli 65537.
I tak jak wspominałem wcześniej kawałki UUID nie są równie losowe. Prefix to jest timestamp, więc tutaj to obcięcie UUID sprawia ze bierzesz tylko i wyłącznie dolne bity timestampa. Więc jakby puścić trochę wątków w tym samym czasie to raz dwa skolidują pewnie.