Kako izgraditi Tiny URL uslugu koja se povećava na milijarde?

Kako izraditi Url Shorter uslugu?

Jedno od dizajnerskih ograničenja Twittera je to što je svaka poruka ograničena na 140 znakova, ali ako želite objavljivati ​​URL-ove u svojim porukama na Twitteru kao i ja, tih 140 znakova postaju vrlo dragi. To je razlog zašto Twitter automatski pretvara sve URL-ove dužine od oko 30 znakova u kratke URL-ove pomoću TinyUrl usluge ili bilo koje druge usluge. Kasnije su mnoge usluge za skraćivanje URL-ova prerasle na tržište, naime Bitly, Google Url Shortner, Rebrandly itd. Mnoga poduzeća su ih također počela koristiti u svojim marketinškim kampanjama, oglasnim kampanjama itd. Na raznim kanalima.

Stvaranje jedinstvenog, ponovljivog identifikatora za URL
Mislim da bi prvi instinkt mnogih ljudi mogao potražiti hashing URL-a - ovo ipak nije dobra ideja iz nekoliko razloga:

  • Duljina: Većina normalnih algoritama raspršivanja (recimo md5) proizvode duge nizove, što ide u usporedbi s točkom skraćivača URL-a.
  • Jedinstvenost: Očigledno je da će ovo biti URL identifikator, onda on treba biti jedinstven, a heševi po svojoj prirodi nisu jedinstveni - što znači da biste trebali rukovati scenarijem u kojem URL stvara već korišten hash i ima alternativu.
  • Potraga: Većina hashe-a nije (lako) reverzibilna, morat ćete potražiti URL koristeći hash kao db ključ - što možda nije idealno s obzirom na vrlo veliki skup URL-ova (zamislite milijarde)

Danas ćemo razgovarati o tome kako izraditi i razviti maleni url uslugu. Prvo se rastavimo na 3 dijela, algoritam, dizajn i način skaliranja i njegovih detalja.

Algoritam:

Imamo 62 alfa numeričke znakove, tj. [Az 0–9 AZ], iako su crtica (-) i podvlaka (_) dopušteni u URL-u i dalje ih želimo izbjeći jer bi to bio loš URL kao što je http: // abc .com / c0 - rw_ ili http://abc.com/______-.
Slijedi jednostavna implementacija pretvornika base10 u base62, to je sve što treba da skratimo URL.

Sa 62 znaka i jedinstvenom žicom dužinom od 7,8,9,10,11, možemo skratiti:

62⁷ = 3,521,614,606,208 url
62⁸ = 218.340.105.584.896 URL-ova
62⁹ = 13,537,086,546,263,552 url
62¹⁰ = 839,299,365,868,340,224 url
62¹¹ = 52.036.560.683.837.093.888 URL-ova

Dakle, možete vidjeti odozgo da možemo stvoriti ovih 62⁶ = ~ 5 milijardi mogućih nizova & 62⁸ = ~ 218 bilijuna mogućih nizova i puno više, ovisno o potrebi.

Pa, recimo da odlučujemo da želimo generirati skraćeni URL za donju vezu

https://medium.com/@vaibhav0109/cache-refreshing-techniques-446403de1ba2

tako da ćemo generirati jedinstveni id pomoću baze 62, dodati ga u našu host domenu, recimo da je generirani id qa12WS4, a naša hipotetička hostirana domena http://short.io, tako da moj maleni URL postaje http://short.io/qa12WS4

Sada se moramo samo uvjeriti da je ova veza jedinstvena i da nije dodijeljena ponovno, razgovarat ćemo o strategijama kako pohraniti u kasnijem dijelu ovog bloga.

Ispod su dvije funkcije koje se mogu koristiti za stvaranje jedinstvenih nizova:

private static final char [] corpus = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" .toCharArray ();
/ *
* Imajte na umu da je sjeme jedinstveno, tada će generirani osnovni broj 62 biti jedinstven i pod balansom opterećenja, pazite da ta vrijednost nije ista.
* /
javni statički konačni String getBase62From10 (konačno dugo sjeme)
{
  Broj niza = sjeme + "";
  char [] buf = novi char [broj.length ()];
  int charPos = broj.length () - 1;
  BigInteger bigIntegerNumber = novi BigInteger (broj);
  BigInteger radix = BigInteger.valueOf (62);
 
  dok je (bigIntegerNumber.compareTo (radix)> = 0)
  {
   buf [charPos--] = corpus [bigIntegerNumber.mod (radix) .intValue ()];
   bigIntegerNumber = bigIntegerNumber.divide (radix);
  }
  buf [charPos] = corpus [bigIntegerNumber.intValue ()];
  vrati novi niz (buf, charPos, (number.length () - charPos));
}
/ **
* @param longNumber
* pozitivan broj u bazi 62
* @ vrati isti broj, u bazi 10
* /
javni statički konačni String getBase10From62 (final long longNumber)
{
  Broj niza = longNumber + "";
  Vrijednost BigInteger = BigInteger.ZERO;
  za (char c: broj.toCharArray ())
  {
    vrijednost = vrijednost.multiply (BigInteger.valueOf (62));
    if ('0' <= c && c <= '9')
    {
      value = value.add (BigInteger.valueOf (c - '0'));
    }
    if ('a' <= c && c <= 'z')
    {
      value = value.add (BigInteger.valueOf (c - 'a' + 10));
    }
    if ('A' <= c && c <= 'Z')
    {
      value = value.add (BigInteger.valueOf (c - 'A' + 36));
    }
   }
   povratna vrijednost.toString ();
}

Dizajn:

Sada prelazimo na dizajnerski dio aplikacije. Ovdje može biti više pristupa, ovisno o opterećenju sustava ili ako aplikacija stoji iza balansirača opterećenja itd. Prvo najjednostavnije, a drugo poboljšanje u odnosu na prvo.

U najjednostavnijem slučaju vjerojatno bismo mogli zaobići sljedeće stupce:

  • id (ID generiranog DB-a u nizu)
  • original_url - orginalna URL vrijednost
  • shorten_url
  • Datum stvaranja
  • Datum isteka roka trajanja

Generiranje identifikatora iz DB-a

  1. Ako unesete vrijednost URL-a za string, vaš kôd treba samo da ga umetnete u tablicu, zajedno s datumom stvaranja, to će stvoriti red i jedinstveni ID.
  2. Zatim donesite jedinstveni numerički ID i pretvorite ga u base-62 (to će numeričku vrijednost pretvoriti u reprezentaciju base-62 (umjesto uobičajenog base10, omogućit će vam znakove od 0 do 9, az, AZ). To vam daje identifikator u obliku qa12WS4.
  3. Sada dodajte string base62 u svoj url osnovnog URL-a svoje kratke domene http://short.io i voila i dobit ćete skraćeni URL kao http://short.io/qa12WS4 i ažurirajte ga u stupcu s kratkim URL-om s datumom isteka.
  4. Sada morate jednostavno napisati logiku preusmjeravanja jer tko ikad pogodi ovaj skraćeni URL, dohvaćate detalje iz Db-a i preusmjeravate ga na izvorni URL.

Ovaj pristup ima 2 nedostatka:

  • Prvo radimo dvije DB operacije, umetamo ih i ažuriramo, pod velikim opterećenjem se neće skalirati.
  • Drugo, u slučaju migracije baze podataka, ID-ovi sekvence se ne mogu spojiti jer bismo mogli imati isti ID sekvence generiran u dvije tablice.

Razmotrimo sada poboljšanja, možemo poboljšati dvije stvari. Prvo DB struktura i drugo, umjesto umetaka i ažuriranja možemo raditi samo pojedinačne umetke. Struktura DB kako slijedi:

  • id_hash (osnovni 62 generirani niz kao primarni ključ)
  • ORIGINAL_URL
  • shorten_url
  • Datum stvaranja
  • Datum isteka roka trajanja

Da bismo imali id_hash kao primarni ključ, moramo imati centraliziranu uslugu koja mi daje jedinstvene oznake sjemena, na primjer, koristimo Redis autoincrement značajku (jer je atomske prirode), možemo dobiti broj sjemena i generirati niz 62, ovo također će raditi iza dva slučaja pod balansom opterećenja. Može se izraditi više pristupa kako bi se dobilo jedinstveno sjeme, ovisno o zahtjevu.

Ljestvica i preciznost ovog sustava:

Procjene prometa: Za 500M novih skraćenja URL-ova mjesečno, možemo očekivati ​​(100 * 500M => 50B) preusmjeravanja tijekom istog razdoblja. Što bi bili upiti u sekundi (QPS) za naš sustav?

Nova skraćenja URL-ova u sekundi:

a) 500 milijuna / (30 dana * 24 sata * 3600 sekundi) = ~ 192 URL-ova / s

b) 1000 milijuna / (30 dana * 24 sata * 3600 sekundi) = ~ 386 URL-ova / s

Preusmjeravanja URL-ova u sekundi uzimajući u obzir omjer čitanja / pisanja od 100: 1:

a) 100 * 500M = 50 milijardi preusmjeravanja

50 milijardi / (30 dana * 24 * 3600) = ~ 19K / s

b) 100 * 1000 milijuna = 100 milijardi preusmjeravanja

100 milijardi / (30 dana * 24 sata * 3600 sec) = ~ 38K / s

Procjene pohrane: Pretpostavimo da pohranimo svaki zahtjev za skraćivanje URL-a (i pridruženi skraćeni link) za dvije godine. Budući da očekujemo da ima svakog mjeseca milijardu novih URL-ova, ukupan broj objekata koje očekujemo pohraniti će biti 30 milijardi:

1000 milijuna * 2 godine * 12 mjeseci = 24 milijarde

Pretpostavimo da će svaki pohranjeni objekt biti otprilike 500 bajtova (samo procjena rezultata - u njega ćemo ukopati kasnije). Trebat će nam 15TB ukupnog prostora za pohranu:

24 milijardi * 500 bajtova = 12 TB

Procjena propusnosti: Za zahtjeve za pisanje, jer očekujemo 386 novih URL-ova svake sekunde, ukupni dolazni podaci za našu uslugu bit će 100KB u sekundi:

386 * 500 bajtova = ~ 200 KB / s

Za zahtjeve za čitanje, jer svake sekunde očekujemo ~ 19K preusmjeravanja URL-ova, ukupni odlazni podaci za našu uslugu bili bi 9MB u sekundi.

38K * 500 bajtova = ~ 18 MB / s

Procjene memorije: Ako želimo spremiti u predmemoriju nekih vrućih URL-ova kojima se često pristupa, koliko će nam memorije trebati da ih pohranimo? Ako slijedimo pravilo 80-20, što znači da 20% URL-ova generira 80% prometa, željeli bismo sačuvati predmemoriranje ovih 20% vrućih URL-ova.

Budući da imamo 38 K zahtjeva u sekundi, dobivat ćemo 3,4 milijarde zahtjeva dnevno:

38 K * 3600 sekundi * 24 sata = ~ 3,4 milijarde

Za predmemoriranje 20% ovih zahtjeva trebat će nam 340 GB memorije.

0,2 * 3,4 milijarde * 500 bajtova = ~ 340 GB

Budući da imamo kratku ideju razmjera, možemo stvoriti ograničenja za izgradnju sustava, recimo da možemo ograničiti korisnike na određeni broj stvaranja URL-ova i preusmjeravanja u određenom vremenskom razdoblju.

A trebamo podnijeti i opterećenje na DB-u (SQL ili NoSQL). Sada prelazimo na sitnice koje se odnose na razmjere. Za ljestvicu DB-a trebat ćemo:

a. Podjela na temelju raspona: URL-ove možemo pohraniti u zasebne particije na temelju prvog slova URL-a ili hash ključa ili na temelju datuma stvaranja ili datuma isteka. Taj se pristup naziva podjela na temelju raspona.

Glavni problem ovog pristupa je taj što može dovesti do neuravnoteženih particija.

b. Particioniranje na temelju hash: U ovoj shemi uzimamo hash objekta koji spremamo. Zatim izračunavamo koju particiju koristiti na temelju hash-a.

Naša funkcija hashta nasumično će rasporediti URL-ove u različite particije (npr., Naša hash funkcija može uvijek preslikati bilo koji ključ u broj između [1 ... 256]), a taj bi broj predstavljao particiju u koju pohranjujemo naš objekt.

Čišćenje podataka DB:

Treba li se unosi zauvijek zadržati ili ih treba obrisati? Ako je postignuto određeno vrijeme za korisnika određeno, što bi se trebalo dogoditi s vezom?

Da smo odlučili aktivno pretraživati ​​istekle veze kako bismo ih uklonili, to bi napravilo veliki pritisak na našu bazu podataka. Umjesto toga, polako možemo ukloniti istekle veze i napraviti lijeno čišćenje. Naša usluga pobrinut će se da se obrišu samo linkovi s istekom roka, iako neke istekle veze mogu trajati duže, ali se nikad neće vratiti korisnicima.

  • Kad god korisnik pokuša pristupiti vezi koja je istekla, možemo je izbrisati i vratiti grešku korisniku.
  • Za uklanjanje isteklih veza iz naše pohrane i predmemorije povremeno se može pokrenuti zasebna usluga čišćenja. Ova bi usluga trebala biti vrlo lagana i može se planirati prikazivati ​​samo kad se očekuje da će promet korisnika biti slab.
  • Možemo imati zadano vrijeme isteka za svaku vezu (npr. Dvije godine).
  • Trebamo ukloniti veze koje nisu bile posjećene u određenom vremenskom razdoblju, recimo šest mjeseci? Ovo bi moglo biti varljivo. Budući da je pohrana jeftina, možemo se odlučiti zauvijek zadržati veze.

Spremanje je još jedan zamršeni aspekt za česte pristupe URL-ova pristupa.

Koliko predmemorije moramo imati?

Možemo započeti s 20% dnevnog prometa i, na osnovu načina upotrebe klijenata, možemo prilagoditi koliko keš poslužitelja nam treba. Kao što je gore procijenjeno, potrebno nam je 340 GB memorije da bismo spremili 20% dnevnog prometa.

Koja bi politika izbacivanja iz predmemorije najbolje odgovarala našim potrebama?

volatile - ttl, LRU itd. su višestruke mogućnosti.

Reference :

https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904

Moglo bi biti mnogo više problema s skaliranjem, pokušao sam pokriti osnovne minimalne zahtjeve dok sam gradio uslugu skalabilnog skraćivanja URL-a.

Pitanja? Prijedlozi? Komentari?

Što je sljedeće? Slijedite me na Mediumu da biste prvi pročitali moje priče.