· 4 dk okuma
Doğum Günü Paradoksu: Rastgele Kodlar Neden Sandığımdan Erken Çakışır
Rastgele üretilen kısa kodlar birçok uygulamada var: rezervasyon kodu (PNR), oyun odası kodu, indirim kodu, kısa link. 6 karakterlik bir kodun yüz milyonlarca olasılığı olduğunda iki kodun aynı çıkması imkânsız gibi görünür. Değil. Bu yazıda doğum günü paradoksunun iki projeme nasıl yansıdığını anlatıyorum: havayolu rezervasyon sistemimde örnek veriyi kuracak kod neredeyse kesin çakışacaktı, Casus oyunumda ise bir test her yetmiş çalıştırmada bir sebepsiz yere düşüyordu.
Paradoks
Bir odada kaç kişi olursa ikisinin doğum gününün aynı olma ihtimali %50'yi geçer? Sezgi 183 der, yılın yarısı. Doğru cevap 23.
Sezginin yanıldığı yer şu: soru "biri benimle aynı gün mü doğdu?" değil, "herhangi iki kişi aynı gün mü doğdu?". 23 kişide 253 farklı ikili var ve her ikili çakışma için ayrı bir şans.
Aynı hesap kodlar için de geçerli. N olasılıklı bir uzaydan n tane rastgele kod üretildiğinde:
- Beklenen çakışan ikili sayısı: λ ≈ n² / 2N
- En az bir çakışma ihtimali: 1 − e^(−λ)
- İhtimal yaklaşık 1,18 × √N kodda %50'ye ulaşır.
Kritik nokta son satır: çakışma N'de değil, N'nin karekökünde başlar.
Kodlar
İki projede de aynı biçimi kullandım: 6 karakter, 31 harflik bir alfabe.
/** Karışabilecek karakterler (0/O, 1/I/L) yok; kod telefonda okunurken yanlış anlaşılmasın. */
public static final String PNR_ALPHABET = "ABCDEFGHJKMNPQRSTUVWXYZ23456789";
public static final int PNR_LENGTH = 6;
31⁶ = 887.503.681, yani yaklaşık 887 milyon olasılık. Karekökü ise yaklaşık 29.800. Yani yaklaşık 35 bin kodda iki kodun aynı çıkma ihtimali %50.
Havayolu: örnek veri neredeyse kesin çakışacaktı
Havayolu rezervasyon sistemim, ilk açılışta uygulamayı gerçek gibi göstermek için örnek veri üretiyor: geçmiş ve gelecek uçuşlar, dolu koltuklar, iptaller. Bu, yaklaşık 75 bin rezervasyon demek. Her birine rastgele bir PNR veriliyor.
Hesap:
| Kod sayısı | Beklenen çakışan ikili | En az bir çakışma |
|---|---|---|
| 5.000 | 0,014 | %1,4 |
| 35.000 | 0,69 | %50 |
| 75.000 | 3,17 | %95,8 |
Veritabanında pnr sütununda UNIQUE kısıtı var. Yani kodlar körü körüne üretilseydi kurulum büyük ihtimalle yarıda kesilecek ve uygulama ilk açılışta hata verecekti. 887 milyon olasılığa bakıp "çakışmaz" demek kolaydı; hesabı yapınca durum tersine döndü.
Çözüm iki yerde. Örnek veri üretilirken kullanılan kodlar bellekte tutuluyor ve tekrar eden kod yeniden üretiliyor:
private static String unique(Set<String> used, Supplier<String> generator) {
String code;
do {
code = generator.get();
} while (!used.add(code));
return code;
}
Uygulama çalışırken yeni rezervasyonda ise kod veritabanında aranıyor, varsa yenisi üretiliyor:
for (int attempt = 0; attempt < 20; attempt++) {
final String code = pnr ? Codes.pnr(airline.random()) : Codes.ticketNumber(airline.random());
try (PreparedStatement ps = c.prepareStatement(existsSql)) {
ps.setString(1, code);
if (!ps.executeQuery().next())
return code;
}
}
throw new IllegalStateException("Benzersiz kod üretilemedi");
UNIQUE kısıtı yine yerinde: kontrol ile kayıt arasında bir şey ters giderse son söz veritabanının.
Casus: her yetmiş çalıştırmada bir düşen test
Casus'ta oda kurulunca 6 karakterlik bir oda kodu üretiliyor; arkadaşlar bu kodla odaya katılıyor. Kod üreticisini test etmek için şunu yazmıştım: 5.000 kod üret, hepsi farklı olsun.
Test çoğu zaman geçiyordu, ara sıra düşüyordu. Kodda hata yoktu; testin beklentisi yanlıştı. Yukarıdaki tablonun ilk satırı tam bu durum: 5.000 kodda en az bir çakışma ihtimali %1,4, yani yaklaşık her 70 çalıştırmada bir. Rastgele düşen bir test, hiç düşmeyen testten daha zararlı: bir süre sonra kimse kırmızıya inanmaz.
Testi istatistiğe göre yeniden yazdım:
// Birthday paradox: among 5,000 codes from 887 million, a single repeat happens about 1.4%
// of the time (creating a room then just draws again). A broken generator repeats far more.
var codes = Enumerable.Range(0, 5000).Select(_ => RoomCode.Generate(random)).ToHashSet();
Assert.True(codes.Count >= 4997, $"{5000 - codes.Count} repeats");
En fazla 3 tekrara izin var. Beklenen tekrar sayısı 0,014 olduğu için 4 ya da daha fazla tekrarın ihtimali yaklaşık milyarda 1,6; test artık sebepsiz düşmüyor. Ama üretici bozulursa, örneğin alfabenin yarısını hiç kullanmazsa ya da her seferinde aynı tohumla başlarsa, tekrarlar yüzlerle ölçülür ve test hemen kırmızı olur.
Çalışan sistemde çakışma bir hata değil, sıradan bir durum. Oda Redis'e "anahtar yoksa yaz" kuralıyla kaydediliyor; kod doluysa yenisi deneniyor:
public Task<bool> CreateAsync(Room room) =>
Db.StringSetAsync(StoreKeys.Room(room.Code), GameJson.Write(room), StoreKeys.RoomLifetime, When.NotExists);
for (var attempt = 0; attempt < MaxCodeAttempts; attempt++)
{
var room = RoomEngine.Create(RoomCode.Generate(random), /* ... */);
if (await rooms.CreateAsync(room)) return (null, room.Code);
}
return ("try_again", null); // ten taken codes in a row: practically never
"Önce bak, sonra yaz" yerine tek bir atomik işlem kullanmamın sebebi aynı anda kurulan iki odanın aynı kodu alamaması. Kontrol ile kayıt ayrı olsaydı ikisi de "boş" görüp ikisi de yazabilirdi.
Neden kodu uzatmadım?
Daha uzun bir kod çakışmayı azaltır, ama bu kodları insanlar telefonda okuyor, birbirine söylüyor, elle yazıyor. 6 karakter rahat; 10 karakter değil. Çakışmayı kod uzunluğuyla değil, tekrar deneme ve benzersizlik kuralıyla çözmek daha ucuz.
Çakışma ile tahmin edilebilirlik de ayrı konular. Çakışma "iki kodun aynı çıkması", tahmin ise "birinin başkasının kodunu bulması". Tahmine karşı koruma kodların güvenli bir rastgele kaynaktan gelmesi (Java'da SecureRandom, C#'ta kriptografik üreteç), sıralı olmaması ve deneme sayısının sınırlanması. Havayolunda PNR tek başına yetmiyor, yolcunun soyadıyla birlikte soruluyor ve hatalı denemeler bekletiliyor.
Öğrendiklerim
- Rastgele kodlarda çakışma √N civarında başlar. 887 milyon olasılıkta bu 30 bin civarı. Kod sayısı bu büyüklüğe yaklaşacaksa çakışma bir ihtimal değil, beklenen bir olay.
- Benzersizlik rastgeleliğe değil, bir kurala bağlanmalı: veritabanında
UNIQUE, Redis'te "yoksa yaz", kod doluysa yeniden deneme. - Rastgelelik içeren testler istatistikle yazılır. "Hiç tekrar olmasın" demek yerine beklenen değeri hesaplayıp bozuk bir üreticiyi yakalayacak, sağlamını ise yanlışlıkla düşürmeyecek bir sınır koymak gerekiyor.