SYSTEM DESIGN: URL SHORTENER
GORSELDEKI QR Kodu kullanarak iletisim kanallarım üzerinden benimle iletisime gecebilirsiniz.
Bu yazı Alex XU’nun System Design Interview kitabının (mavi kapaklı olan) 8. böülümünü ihtiva eder.
Bu konuyla alakalı da çook güzel medium makaleleri var. Muhakkak göz gezdiriniz.
Bir url shortener tasarlamamız gerekiyor ve isterlerimiz de aşağıdaki gibi.
- Günde 100 milyon tane URL generate edilecek.
- Oluşturulan URL’lerin uzunluğu mümkün mertebe kısa olacak.
- Short URL’de kabul edilebilir değerler [0, 9] &[a, z] & [A, Z]
- Oluşturulan URL’lerin update edilmesine ya da silinmesine gerek yok.
Artık buradan sonra matematiğe başlamak gerekiyor. Çünkü estimationlar yapacağız.
- Günde 100 milyon URL üretecekse 100 milyon / 24 / 3600 = 1160. Yani saniyede 1160 tane URL üretiminden bahsediyoruz.
- Yazma oranı ile Okuma oranı arasındaki orana 1 ‘ e 10 dersek, dolayısıyla 11600 okuma gerçekleşir.
- Sistemi en az 10 yıl ayakta tutmak istersk: 100 milyon * 365 * 10 kadar record oluşması kuvvetle muhtemel. Yani 356 milyar gibi bir sayı.
- Bize parametre olarak gelecek URL’in ortalama length’ine 100 dersek 10 yılın sonunda totalde 365 TB yere ihtiyacımız var.
==============================================================
Burada tiny url server’ından status code’u 301 ile geriye döndük. 3XX nedir.? Ne işe yararlar.?
En basit haliyle 3XX status code’ları yönlendirme için kullanılan status code’larıdır.
Burada 301 dönülmüş. Tabi geriye 302'de dönülebilirdi.
Detaylıca 301 vs 302 bakacak olursak;
301;
Eğer client server’dan 301 status code’u alıyorsa, istenilen adres kalıcı olarak başka bir yere taşınmıştır. Bir kullanıcı ya da tarayıcı 301 aldığı zaman bu kaynağa her zaman yeni adresi üzerinden erişmesi gerektiğini anlar. Kalıcı olarak yönlendirildiği için, tarayıcı bu yanıtı cache’e alır ve aynı URL için yapılan sonraki istekler, bizim tasarımımıza göre, URL shortener servisine gönderilmez.
302;
İstenilen kaynak geçici olarak başka bir adreste bulunuyor. Ama kalıcı olarak asla yönlendirilmez. Bu da aynı URL için yapılan sonraki request’lerin bizim sistem tasarımımıza göre önce URL Shortener service’ine yönlendirileceği anlamına gelir.
Burada her iki durum için de farklı eksi yönler ve artı yönler vardır. Eğer amaç server’ın load olma süresini azaltmak ise 301 kullanılmaldıır. Ama amaç analitik yapmak ise, 302 daha iyi bir seçenek olabilir.
Bu davranışı görüntülemek için şöyle basit bir kod bloğu tanımlayabiliriz.
@GetMapping("/old-url")
public ResponseEntity<Void> redirectToNewUrl(HttpServletResponse response) {
response.setHeader("Location", "/new-url");
response.setStatus(HttpServletResponse.SC_MOVED_PERMANENTLY);
return ResponseEntity.status(HttpStatus.MOVED_PERMANENTLY).build();
}
@GetMapping("/new-url")
public ResponseEntity<String> newUrl() {
return ResponseEntity.ok("https://fskdev.com.tr");
}
Tarayıcıda isteği attığımızda, yukarıdaki gibi bir görüntü elde ediyoruz.
Networkü clear edip tekrar istek attığımızda ise aşağıdaki gibi direkt olarak cache’lediğini ve direkt olarak yeni url’e gittiğini görüyoruz.
==============================================================
URL Shortener için kullanılabilecek en basit mantık HashTable ya da HashMap olabilir. Bu iki yapıda temelde neredeyse aynıdır ama aralarında ince bir çizgide olan fakat, çok önemli farklar vardır.
- Her ikisi de key — value pari’lerini tutar.
- Her ikisinde de bir key değerinden sadece bir kere bulunabilir ama bir value değeri birden fazla bulunabilir.
- HashMap bir tane null key’e izin verir. Birden fazla null değer alabilir ama HashTable’da ne key değeri olarak ne de value değeri olarak null’e izin verilmez.
- HashTable thread safe’tir ama HashMap thread safe değildir.
- HashMap Enumeration interface’ini desteklemez. Ama HashTable enumeration interface’ini destekler. Buradaki enumeration normal enumlarla karıştırılmamalı. Enumeration, elementler üzerinde tek tek dolaşmak için kullanılan legacy bir interface’dir.
- Ama bu kötü bir durumdur. Çünkü enumeration fail-fast özelliğini sunmaz. Yani, Enumeration ile elementleri dolaşırken, ilgili collection’da bir değişiklik olursa Enumeration bu değişikliği hemen fark edip hata fırlatmaz. Ama aynı durum HashMap için geçerli değildir. Böyle bir durumda
ConcurrentModificationExceptionhatası fırlatılır.
==============================================================
HashMap ya da HashTable kullanmak için yapılması gereken şey, aslında bir hash fonksiyonun implementasyonunun yapılması. Hash fonksiyonu, girdiyi (örneğin bir metin, dosya ya da veri) belirli bir algoritma ile işleyerek, sabit uzunlukta ve genellikle benzersiz bir çıktıya (hash değeri) dönüştüren bir matematiksel fonksiyondur. Hash fonksiyonlarının temel amacı, veriyi özetlemek ve bu özeti hızlıca karşılaştırmaya uygun hale getirmektir.
Farklı iki input için aynı hash değeri oluşturulabilir. Bu durumlara collision denilir. Hash Fonkisonlarında bu durum hash table’lar üzerinden ele alınır. Hash Table’lar 16 birimlik bucket’lardan oluşur ve bu bucket’larda aynı hash değerine karşılık gelen bir değer oluşturulursa linked list gibi yana doğru açılan bir liste gibi dolmaya başlar.
Bazı hash fonksiyonları aşağıdaki gibidir.
CRC32
Basit bir hash algoritmasıdır. CRC32’nin asıl amacı, ağ iletişimi veya dosya iletimi sırasında meydana gelebilecek hataları tespit etmektir. Bu nedenle, daha okunabilir veya harfsel bir çıktı yerine hızlı işlenebilir ve kontrol edilebilir bir sayısal değer üretir.
import java.util.zip.CRC32;
public class Main {
public static void main(String[] args) {
String value = """
https://en.wikipedia.org/wiki/Systems_design
""";
CRC32 crc32 = new CRC32();
crc32.update(value.getBytes());
crc32.getValue();
System.out.println("CRC32 Hash Value ==> " + crc32.getValue());
}
}MD5
MD5 (Message Digest ), veriyi hashlemek için kullanılan popüler bir kriptografik hash fonksiyonudur. Bir girdi alır ve sabit uzunlukta (128 bit) bir hash değeri üretir.
public class Main2 {
public static void main(String[] args) throws NoSuchAlgorithmException {
String url = "https://fskddev.com.tr";
MessageDigest md = MessageDigest.getInstance("MD5");
byte[] digest = md.digest(url.getBytes());
StringBuilder sb = new StringBuilder();
for (byte b : digest) {
// Her bir byte'ı hexadecimal formatta yazıyoruz.
sb.append(String.format("%02x", b));
}
System.out.println(sb);
}
}SHA-1
SHA-1 (Secure Hash Algorithm), kriptografik bir hash fonksiyonudur ve girdiyi sabit uzunlukta bir hash değerine (160 bit ) dönüştürür.
public class Main3 {
public static void main(String[] args) throws NoSuchAlgorithmException {
String url = "https://fskddev.com.tr";
MessageDigest md = MessageDigest.getInstance("SHA-1");
byte[] digest = md.digest(url.getBytes());
StringBuilder sb = new StringBuilder();
for (byte b : digest) {
sb.append(String.format("%02x", b));
}
System.out.println(sb);
}
}Ya da getInstance methoduna parametre olarak SHA-256 falan da verilebilir.
Çıktılar üzerinden aşağıdaki gibi bir tablo oluşması kuvvetle muhtemel.
Burada şöyle bir durum var. İsterlerde oluşturukacak olan url’in minimum lenght’te olması bekleniyordu ve içermesi gereken karakterler belliydi. (a-z arası, A-Z arası ve 0–9 arası)
Buradan aşağıdaki gibi basit bir matematikle elde etmemiz gereken sonuç şu.
a-z => 26 karakter
A-Z => 26 karakter
0–9 => 10 karakter
Yani totalde 62 karakterimiz var.
Ve isterlerden biliyoruz ki, totalde 365 milyar’ı karşılayacak bir sistem kurmamız gerekiyor. Bunu yaparken de minimum length’i seçmemiz gerekiyor.
Aşağıdaki tabloyu inceleyecek olursak;
Bize lazım olan rakam 7, sebebi ise şu bize lazım olan request 365 milyon u karışılayabilecek request, bu yüzden 3.5 trilyon bize fazla fazla yetecek bir sayı. Tabi bir de collusion probleminin çözülmesi lazım. Aşağıdaki gibi bir algoritma ile bu collusion problemi de çözülebilir.
Çok basit bir algoritmik yaklaşım ile bu problem çözülebilir. Fakat, burada query’ler biraz pahalı olacaktır. Çünkü her seferinde DB’de var mı yok mu kontrolü yapılacaktır.
==============================================================
Bir başka yaklaşım, Base62 yaklaşımıdır.
Bu yaklaşım, bir sayıyı ya da metni 62 karakterden oluşan bir sistemde ifade etme işlemidir.
A ← → Z 26
a ← → z 26
0 ← → 9 10
Bunun için yardımcı bir method tanımı yapılarak devam edilebilir.
public class Base62 {
private static final String ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
private static final int BASE = ALPHABET.length();
public static String encode(long num) {
StringBuilder sb = new StringBuilder();
while (num > 0) {
sb.append(ALPHABET.charAt((int) (num % BASE)));
num /= BASE;
}
return sb.reverse().toString();
}
public static long decode(String str) {
long num = 0;
for (char c : str.toCharArray()) {
num = num * BASE + ALPHABET.indexOf(c);
}
return num;
}
}@Service
public class UrlMappingServices {
private final UrlMappingRepository urlMappingRepository;
private final UrlMapper urlMapper;
private static final AtomicLong counter = new AtomicLong();
public UrlResponseDTO shortenerUrl(UrlRequestDTO urlRequestDTO) {
// 1. Önce URL'in daha önce kısaltılıp kısaltılmadığını kontrol et
Optional<UrlMapping> existingUrl = urlMappingRepository.findByLongUrl(urlRequestDTO.longUrl());
if (existingUrl.isPresent()) {
return urlMapper.toDto(existingUrl.get());
}
// 2. Yeni bir kısa URL oluştur
long nextId = counter.incrementAndGet();
String shortUrl = Base62.encode(nextId);
// 3. Yeni mapping oluştur
UrlMapping urlMapping = urlMapper.toEntity(urlRequestDTO);
urlMapping.setShortUrl(shortUrl);
urlMapping.setCreatedAt(LocalDateTime.now());
urlMapping.setClickCount(0L);
return urlMapper.toDto(urlMappingRepository.save(urlMapping));
}
}Bu yaklaşımın diğer hash function yaklaşımından farkları aşağıdaki gibi olabilir.
- Unique bir id ile işlem yapılacağından daha sağlıklı bir yaklaşım olabilir. Çünkü collusion oluşumuna müsade edilmez.
- Hash function ile işlem yapıldığında bir sonraki tiny url’in bilinmesi imkansızdır.
==============================================================
