SD #6: Url Shortening Service Tasarimi

Problem: bit.ly gibi bir url shortening servisi tasarlayiniz.

Requirements

Ilk etapta requirements konusu cok detayli olarka aciga kavusturmamiz gerekiyor ki tasarimi yapabilelim. Diyelim ki su minvalde bir cozum isteniyor:

Functional Requirements
- Verilen bir URL'i kisaltip, calisan, unique bir kisa url olustur.

- Bir kullanici bizim olusturdugumu kisa linki yizaret ettiginde, orjinal adrese yonlendir.

- [Opsiyonel] Kullanici sisteme custom bir kisaltma onerebilmelidir 

- Olusturulan link icin expiration zamani atanabilmeli

Non-functional Requirements:

- Sistem highly-available olmali

- Rest API ile url olusturulabilmeli

Back-of-the-envelope Hesabi

On kabullerle birlestirerek asagi yukari ne kadar kaynaga ihtiyacimiz olacak bir bakalim.

- Read-heavy bir sistem olacagi asikar. 100:1 (read/write orani kabul edecegiz)

- Ayda 500 milyon url shortening requesti gelecek (demek ki aylik 50 milyar okuma olacak)

- Ayda 500 milyon write (36 * 24 * 3600 saniye) => 200 Url / saniye yazma

- 100:1 okuma orani olduguna gore, 20K RPS (requests per second)

- Kisaltilmis url'leri maksimum 5 yil saklayacagimizi kabul edelim. Ayda 500 milyondan, 5 yilda, 30 milyar url yapar. (40 yapmadi). Bir URL, compatibility acisindan maksimum 2000 karakter olmalidir (kaynak). Ama herkes 2000 karakter kullanmayacagi icin ortalama 500 karakter diyebiliriz. Bu da 500 bytelik bir saklama alani gerektirir. Sonucata bes yil icin bize toplamda 30Milyar * 500 byte = 15 Terabyte'lik bir saklama alani gereklidir. (Cok da degilmis).

- 200 req/sec yazma bekledigimizi yukarida hesapladik. Her bir url 500 byte kabul etmistik. Dolayisi ile 200 x 500 = 100 Kb/sec gibi bir yazma bandwidth'ine ihtiyacimiz var.

- Okuma icin 20K req/sec uzerinden yine her biri 500 byte ise, 20K x 500 = 10 Mb/sec bir okuma bandwidth'ine ihtiyacimiz var demektir.

- Her bir requestte gidip database'den okuyup redirection yapamayacagimiza gore, URL'lerin enazindan bir kismini cache'te tutmamiz gerek. Bu gibi durumlarda 80/20 yaklasimi yardimci olabilir. Yani elimizdeki URL'lerin %20'si toplam trafigin %80'inin uretecektir. O zaman sadece en cok kullanilan %20'lik kismi cachelemek bize maksimum faydayi saglar. Saniyede 20K okuma requesti gelecek diye hesaplamistik. Gunde 1.7 Milyar request anlamina gelir. Bunun %20'si ise 0.2 x 1.7 milyar x 500 byte = 170 Gb, cache uzerinde veri saklamamiz gerekiyor demektir. 

API Tasarimi
Api tasarimi bize gerekli interface'leri ve de saklama secenekleri hakkinda fikir verecektir. Ilk olarak kisatlma olsutrurma ile baslayalim. Bize neler gerekir? Kullaniciyi tanimak icin bir Api-key'e ihtiyac olacak. Bunun yaninda orjinal url verilmeli. Opsiyonel olarak, custom bir kisaltma kullanici tarafindan iletilebilir. Bu kisaltmanin oluruna biz bakip, olmuyorsa ona gore bir uyari mesaji dondurecegiz. Ek olarak da opsiyonel bir expiration date kullanicidan beklenebilir.  

createUrl(apiKey, originalUrl, [opt]customAlias, [opt]expirationDate) 

Egere kisaltma basarili ise, kullaniciya kisaltilmis halini dondurecegiz. Burada kucuk bir problem var. Kotu niyetli bir kullanici api'yi kullanarak elimizdeki tum kisaltmalari tuketebilir. Bu noktada kullanicilara gunluk ya da saatlik limitler tanimlamak yararli olacaktir. 

Database
Neler gerekiyor?

- Milyarlarca kayit saklayabilmeli (kayit kisa_url -> orjinal_url iliskisi)

- Her bir kayit cok kucuk (1Kbyte'tan az) 

- Kayitlar arasinda bir iliski (relation) yok (yaaay!)

- Read-heavy

Buradaki en buyuk ipucu kayitlar arasinda bir relation olmamasi. Yani hicbir zaman bir join islemi gerekmeyecek. Bu durumda direk NoSQL bir database ile devam etmek cok mantikli olacaktir. 

Kisa kes aydin havasi olsun
Simdi tinyurl nasil calisiyor bir hatirlayalim. Verilen uzun bir url icin tinyurl.com/a2qweqwdq2 gib bir url uretiyor. Burada slash'ten sonra gelen kisim bizim kisaltilmis key'imiz oluyor. 

1) On demand

Kullanicidan gelen bir url ile unique key arasinda bir iliski kurabilirsek, url kisaltma servisi calisabilir. URL geldigi zaman, bunu bir hash fonksiyonu ile unique ve daha kisa bir key'e donusturebiliriz. Yani tamamen URL'in bir fonksiyonu olan deterministik bir sistem elde etmis oluruz. Ancak:

- Farkli kullanicilar ayni url'i kisaltmak isterse ayni key'i elde ederler ki biz bunu istemeyiz. Cunku farkli expiriy sureleri olabilecegi gibi, eger trafik bilgisini de track etmek istersek isler karisir.

Bunu asmak icin, kisaltma istegi geldigi zaman, olusturdugumuz key, veritabaninda var mi diye kontrol edebilir egere varsa sonuna bir counter ekleyebiliriz. Bu sekilde unique key saglanmis olur. 

2) Pre-compute
Baska bir yaklasimda ise, unique keyleri istedigimiz kadar onceden olusturur ve url kisaltma istegi geldigi zaman bosta olan bir tanesi bu url ile iliskilendirebiliriz. Bu durumda yukaridaki ayni url'in ayni key'i olusturmasi probleminin de onune gecilmis olur. Ayrica bu pre-computation islemi offline olarak yapilabilir. Hatta expire etmis olan url key'leri tekrardan sisteme durumu free seklinde kazandirilabilir, tekrar kullanilabilir.

Key'leri base64 ile encode edersek, her bir karakter 64 farkli deger alabilir. Bu durumda:

6 karakter = 6^64 = 68 milyar farkli string

olusturulabilir. Dolayisi ile 68 milyar farkli url ayni anda temsil edilebilir. Toplamda:

6 byte (1 karakter = 1 byte) x 68 milyar = 400 Gb 

Gibi bir saklama alanina ihtiyacimiz var demektir. O zaman bu secenek ile system design'a devam edelim. 

Key Generation Service

Key'leri onceden hesaplayip database'e insert edecek olan servisimizi su sekilde konumlandirabiliriz:

Henuz bir scalability ayarlamasi yapmadigimizi hatirlatayim. Sadece key generation service'i ayirdik. Burada web server'a bagli olan db uzerinde key ve url iliskisini tutuyoruz. Yani bir request geldigi zaman key ile bu db uzerinden arama yapip orjinal url'yi bulup, yonlendirme yapiyoruz. KGS'ye bagli olan db'de ise sadece bosta olan keyler tutuluyor. 

Partitioning

Servis cok tutuldu ve sistem requestleri karsilamkta zorlaniyor. Metriklere baktik ve key:url iliskisini tutan DB'de cok yuklenme oldugunu tespit ettik. Read-heavy bir sistemde bunun olmasi da cok normaldi zaten. Ilk adim olarak bu DB'yi rahatlatalim. Bunun icin DB'yi bir sekilde partitionlara ayirmamiz gerekiyor. 2 Sekilde yapilabilir:

1. Range bazli partitioning: Mesela, key'in ilk harfine bakarak DB'yi ikiye (veya daha fazla) bolebiliriz. Ornegin a-n ile baslayan key'leri bir DB#1'e; n-z ile baslayan keyleri de DB#2'ye kaydedebiliriz. Okuma istegi geldigi zaman da, keyin ilk harfine bakarak hangi DB'den okumamiz gerektigini bilebiliriz. Tek sorun, partitionlarin esit dagilmamasi olabilir. 

2. Hash bazli partitioning: Elimizdeki key'lerin bir de hash'ini alarak, bu keyleri ornegin 1 ile 256 arasinda uniform olarak dagitabiliriz. Surada guzel bir ornek bulabilirsiniz.

Cache

En cok ziyaret edilen %20lik kismi cache'te tutmaktan bahsetmistik. Hatta burada 170 Gb gi bir memory ihtiyaci hesaplamistik. Modern sistemler icin cok da buyuk bir mebla sayilmaz. Tek bir makinede tutulabilir. Hatta availability'i artirmak icin replika edilebilir. 

Cache'ten bahsedildigi zaman illa ki eviction policy'den de bahsetmek gerekir. Sonucta cache sinirli, yeni bir girdi gerektigi zaman hangi kaydi cache'ten silecegiz? Mevcut sistemde bize en cok ulasilan url'ler lazim oldugu icin LRU cache tam da bicilmis kaftan olarak karsimiza cikiyor. 

Senaryoyu bastan oynatalim. 

1. Bir kisa url requesti gelir

2. Load balancer'dan gecerek bir web server'a ulasir

3. Web server hemen gelen key'in cache'te olup olmadigina bakar

4. Cache'te var iste, expire olup olmadigina bakilir, tamamsa redirect saglanir. Expire olmus ise, kullaniciya hata dondurulur.

5. Cachte'te yok ise, database'e sorgu atilir.

6. Gelen key'e gore hangi DB partitionuna istek atilacagi belirlenir. Sorgu DB uzerinde calistirilir.

7. DB'den donen URL, tekrar expiration kontrolune tabi tutulur. Uygunsa redicrect saglanir. Ayni zamanda bu key:value cache'e eklenir. 

Purge'leme ve DB Temizligi 

Purging; databaseleri kontrol ederek, eski veya artik kullanimda olmayan kisimlarin silinmesi/temizlenmesi anlamina gelir. Bizim DB'lerde de expire olmus URL'ler olusacaktir zaman icerisinde. Bunlarin key:url DB'sinden silinerek, url'leri temizlenip, keyler tekrar key DB'sine yazilabilir. Bu sayede sinirli sayida olan key'leri donusumlu olarak kullanmis oluruz. 

Burada iki yaklasim var. Duzenli araliklarla DB uzerinde gezip expire olmus url'leri bulup silebiliriz. Ama bu DB uzerinde ekstra bir okuma yuku yaratacaktir. Bunun yerine, bir kullanici expire olmus bir linke ulastigi zaman, kullaniciya cevap dondukten sonra bu silme islemini yapabiliriz. 

Son olarak tasarim su sekilde gozukuyor:

Diger bir postta gorusmek uzere.

Stay hungry :)