Bir milyard dollarlıq Tiny URL xidmətini necə yarada bilərəm?

Url Shortner Service-i necə yarada bilərəm?

Twitter-in dizayn məhdudiyyətlərindən biri hər mesajın 140 simvolla məhdudlaşmasıdır. Ancaq mənim kimi Twitter mesajlarınıza URL daxil etmək istəyirsinizsə, bu 140 simvol çox dəyərli olur. Çox güman ki, Twitter TinyUrl xidmətindən və ya başqa bir xidmətdən istifadə edərək 30 simvoldan uzun URL-ləri avtomatik olaraq qısa URL-lərə çevirir. Daha sonra, Bitly, Google Url Shortner, Rebrandly və s. Kimi bir çox URL qısaltma xidməti ortaya çıxdı. Bir çox şirkət marketinq kampaniyalarında, promosyon kampaniyalarında və s. Fərqli kanallarda istifadə etdi.

URL üçün bənzərsiz, təkrarlana bilən bir ID yaratmaq, düşünürəm ki, bir çox insanın ilk instinkti URL sətrini qarışdırmaq ola bilər - lakin bu, bir neçə səbəbdən yaxşı bir fikir deyil:

  • Uzunluq: Əksər normal qarışıq alqoritmləri (məsələn, md5), URL qısaldıcısının dövrünə zidd olan uzun simlər yaradır.
  • Özünəməxsusluq: Əlbəttə ki, bu bir URL kimliyi olmalıdırsa, unikal olmalıdır və xaşlar təbiətinə görə birmənalı deyil. Bu o deməkdir ki, bir URL-nin artıq istifadə olunan bir hash və alternativ yaratdığı ssenarini idarə etməlisiniz.
  • Yuxarıda baxın: Ən çox həşərat (asanlıqla) geri çevrilmir. URL-ni DB açarı kimi hash ilə axtarmaq lazımdır - bu, çox sayda URL ilə ideal olmaya bilər (milyardlarla təsəvvür edin).

Bu gün kiçik bir URL xidmətinin necə qurulacağını və inkişaf etdiriləcəyini müzakirə edəcəyik. Əvvəlcə onu 3 hissəyə ayıraq, alqoritm, dizayn və tərəzinin tərtibatı və incəlikləri.

Alqoritm:

62 alfasayısal simvolumuz var, yəni [az 0-9 AZ], tire (-) və alt xətt (_) URL-də icazə verilsə də, http: // abc kimi pis görünən bir URL olacağı üçün bunlardan qaçmaq istəyirik. com / c0 - rw_ və ya http://abc.com/______-. Aşağıdakı Base10-Base62 çeviricisinin sadə tətbiqi. Bir URL qısaltmaq üçün lazım olan yalnız budur.

62 simvol və 7,8,9,10,11 simvoldan ibarət bənzərsiz bir simli ilə qısalda bilərik:

62⁷ = 3.521.614.606.208 URL
62⁸ = 218,340,105,584,896 URL
62⁹ = 13.537.086.546.263.552 URL
62¹⁰ = 839,299,365,868,340,224 URL
6211 = 52,036,560,683,837,093,888 URL

Yuxarıdan bu 62⁶ = ~ 5 milyard mümkün sətir və 62⁸ = ~ 218 trilyon mümkün sətir və lazım olduqda çox şey yarada biləcəyimizi görə bilərsiniz.

Beləliklə, aşağıdakı link üçün qısaldılmış bir url yaratmaq istədiyimizi deyək

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

Beləliklə, baza 62 ilə bənzərsiz bir şəxsiyyət vəsiqəsi yaradacağıq və bunu ev sahibliyimizə əlavə edəcəyik. Yaradılan ID-nin qa12WS4 olduğunu və fərdi olaraq yerləşdirilən domenimizin http://short.io olduğunu düşünək

İndi sadəcə bu linkin unikal olduğuna və yenidən təyin edilmədiyinə əmin olmalıyıq. Bu blogun sonrakı hissəsində qənaət strategiyalarını müzakirə edəcəyik.

Aşağıdakılar misilsiz simlər yaratmaq üçün istifadə edilə bilən iki funksiyadır:

private static final char [] corpus = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" .toCharArray ();
/ * * Başlanğıc dəyəri unikaldırsa, yaradılan base62 nömrəsi yük balansı altında da unikaldır. Bu dəyərin eyni olmadığından əmin olun. * / public static final String getBase62From10 (son uzun başlanğıc dəyəri) {String number = seed + ""; char [] buf = yeni char [number.length ()]; int charPos = sayı.length () - 1; BigInteger bigIntegerNumber = yeni BigInteger (sayı); BigInteger radix = BigInteger.valueOf (62); while (bigIntegerNumber.compareTo (radix)> = 0) {buf [charPos--] = corpus [bigIntegerNumber.mod (radix) .intValue ()]; bigIntegerNumber = bigIntegerNumber.divide (radix); } buf [charPos] = corpus [bigIntegerNumber.intValue ()]; yeni String qayıt (buf, charPos, (number.length () - charPos)); } / ** * @param longNumber * bazada 62 * @ pozitiv ədədi 10 saylı bazada eyni ədədi qaytarır * / public static final String getBase10From62 (last long longNumber) {String number = longNumber + ""; BigInteger dəyəri = BigInteger.ZERO; üçün (char c: number.toCharArray ()) {value = value.multiply (BigInteger.valueOf (62)); əgər ('0' <= c && c <= '9') {dəyər = dəyər.add (BigInteger.valueOf (c - '0')); } əgər ('a' <= c && c <= 'z') {value = value.add (BigInteger.valueOf (c - 'a' + 10)); } əgər ('A' <= c && c <= 'Z') {dəyər = dəyər.add (BigInteger.valueOf (c - 'A' + 36)); }} return value.toString (); }

Dizayn:

İndi ərizənin qaralama hissəsinə gəldik. Sistemin iş yükündən və ya tətbiqin yük balanslaşdırıcısının arxasında olub-olmamasından asılı olaraq bir neçə yanaşma ola bilər. Birincisi, ən sadə, ikincisi, birinciyə nisbətən inkişaf.

Ən sadə halda, ehtimal ki, aşağıdakı sütunlarla əldə edə bildik:

  • id (verilənlər bazası tərəfindən yaradılan ardıcıllıq ID)
  • original_url - orijinal url dəyəri
  • URL qısaldın
  • Yaradılma tarixi
  • Tarixdən əvvəl ən yaxşısı

DB-dən identifikatorun yaradılması

  1. İndi bir simli URL dəyəri təyin edirsinizsə, kodun yalnız yaradılış tarixi ilə birlikdə masaya daxil edilməsi lazımdır. Bu sıra və unikal şəxsiyyət yaradacaqdır.
  2. Sonra, bu unikal ədədi identifikatoru əldə edin və baza-62-ə çevirin (bu ədədi dəyəri baza-62 nümayəndəliyinə çevirəcək). Normal baza10 yerinə 0, 9, az, AZ simvol olaraq, qa12WS4 şəklində bir identifikatora icazə verilir.
  3. İndi base62 simli qısa domeninizin əsas URL-sinə daxil edin http://short.io və voila http://short.io/qa12WS4 kimi qısaldılmış bir URL əldə edəcək və qısa URL sütununa yeniləyin. son istifadə tarixi ilə.
  4. İndi təkrar yönləndirmə məntiqini yazmalısınız, çünki db-dən təfərrüatlarını alacaqsınız və əgər bu qısa url-yə vursanız orijinal URL-yə yönləndirin.

Bu yanaşmanın iki mənfi cəhəti var:

  • Əvvəlcə iki DB əməliyyatı edirik: daxil edin və yeniləyin. Yüksək yük altında miqyas vermir.
  • İkincisi, verilənlər bazası köçürülməsi zamanı ardıcıllıq identifikatorları birləşdirilə bilməz, çünki eyni ardıcıllıq ID-si iki cədvəldə yaradıla bilər.

İndi inkişafları müzakirə edək. İki şeyi yaxşılaşdıra bilərik: birincisi, DB quruluşu, ikincisi, əlavə etmək və yeniləmək əvəzinə yalnız bir əlavə edə bilərik. DB quruluşu belə:

  • id_hash (baza 62 əsas simvol kimi yaradılan simli sətir)
  • orijinal_url
  • URL qısaldın
  • Yaradılma tarixi
  • Tarixdən əvvəl ən yaxşısı

İndi id_hash-ı əsas açar kimi əldə etmək üçün mənə bənzərsiz toxum işarələri verən mərkəzləşdirilmiş bir xidmətə ehtiyacımız var. Məsələn, Redis’in avtomatik artırma xüsusiyyətindən istifadə ediriksə (təbiətdə atomik olduğu üçün), toxum nömrəsi ala bilərik və baza 62 simli də yarada bilərik ki, iki nümunə arasında yük balanslaşdırması da işləyəcəkdir. Tələbdən asılı olaraq, unikal toxum əldə etmək üçün bir sıra yanaşmalar hazırlamaq olar.

Bu sistemin miqyası və incəlikləri:

Trafik təxminləri: Ayda 500 milyon yeni URL qısaldılması üçün, eyni dövrdə (100 * 500 milyon => 50 milyard) yönləndirmə gözləyə bilərik. Saniyədə Sorgular (QPS) sistemimiz üçün nə ola bilər?

Saniyədə yeni URL qısaldılması:

a) 500 milyon / (30 gün * 24 saat * 3600 saniyə) = ~ 192 URL / s

b) 1000 milyon / (30 gün * 24 saat * 3600 saniyə) = ~ 386 URL / s

URL oxuma / yazma nisbəti 100: 1 nəzərə alınmaqla saniyədə yönləndirmələr:

a) 100 * 500 milyon = 50 milyard təxribat

50 milyard / (30 gün * 24 * 3600) = ~ 19 K / s

b) 100 * 1000 milyon = 100 milyard istiqamətləndirmə

100 milyard / (30 gün * 24 saat * 3600 saniyə) = ~ 38 K / s

Saxlama Tahminləri: Deyək ki, hər bir URL qısaldılması tələbini (və əlaqəli qısaldılmış linki) 2 il saxlayırıq. Ayda 1 milyard yeni URL-yə sahib olmağımız proqnozlaşdırıldığından, saxlayacağımız obyektlərin ümumi sayı 30 milyard olacaq:

1000 milyon * 2 il * 12 ay = 24 milyard

Hər bir saxlanan obyektin təxminən 500 bayt ölçüsündə olduğunu düşünək (yalnız top parkının təxmini - buna daha sonra çatacağıq). 15 TB ümumi yaddaşa ehtiyacımız var:

24 milyard * 500 bayt = 12 TB

Bant Genişliyi Tahminləri: Saniyədə yazma istəkləri üçün 386 yeni URL gözlənildiyindən, xidmətimiz üçün ümumi daxilolma məlumatları saniyədə 100 KB olacaqdır:

386 * 500 bayt = ~ 200 KB / s

Oxunma istəkləri üçün hər saniyədə təxminən 19,000 URL yönləndirməsinin gözlənildiyi üçün, xidmətimiz üçün ümumi çıxan məlumatların sayı saniyədə 9 MB təşkil edir.

38 KB * 500 bayt = ~ 18 MB / s

Yaddaş Təxminləri: Tez-tez daxil olan isti URL-lərin bir qismini önbelleğe almaq istəyiriksə, onları saxlamağımız üçün nə qədər yaddaş lazımdır? 80-20 qaydasına əməl etsək, yəni URL-lərin 20% -i trafikin 80% -ni yaradırsa, bu 20% isti URL'ləri önbelleğe almaq istəyirik.

Saniyədə 38.000 müraciətimiz olduğundan gündəlik 3,4 milyard müraciət alacağıq:

38 K * 3600 saniyə * 24 saat = ~ 3,4 milyard

Bu istəklərin 20% -ni önbelleğe almaq üçün 340 GB RAM-a ehtiyacımız var.

0.2 * 3.4 milyard * 500 bayt = ~ 340 GB

İndi miqyaslandırma haqqında qısa bir düşüncəmiz olduğu üçün sistemi qurmaq üçün məhdudiyyətlər dizayn edə bilərik. Bu o deməkdir ki, istifadəçiləri hər dövr üçün müəyyən sayda URL yaratma və yönləndirmə ilə məhdudlaşdıra bilərik.

Həm də DB (SQL və ya NoSQL) yükünü idarə etməliyik. İndi tərəzinin qırxıntısına enək. DB miqyası üçün bizə lazımdır:

bir. Kapsam əsaslı bölmə: URL-lərin URL və ya hash düyməsinin ilk hərfinə əsasən və ya yaradılış və ya son istifadə tarixinə əsasən ayrı bölmələrdə saxlaya bilərik. Bu yanaşma sahəyə bölünmə kimi tanınır.

Bu yanaşmanın əsas problemi balanssız arakəsmələrə səbəb ola bilər.

b. Hash əsaslı bölmə: bu sxemdə saxladığımız obyektin bir qarışığını götürürük. Sonra qarışıq əsasında istifadə ediləcək bölməni hesablayırıq.

Qarışıq funksiyamız URL'ləri təsadüfi olaraq fərqli bölmələrə paylayır (məsələn, hash funksiyamız hər zaman [1… 256] arasındakı bir saya hər hansı bir düyməni təyin edə bilər). Bu nömrə obyektimizi saxlayacağımız bölməni təmsil edəcəkdir.

DB məlumatlarının silinməsi:

Girişlər əbədi qalmalı və ya silinməlidir? Xüsusi bir sona çatma vaxtı gəldikdə əlaqədə nə baş verməlidir?

Bunları silmək üçün müddəti bitmiş bağlantıları aktiv şəkildə axtarsaq, bu, verilənlər bazamıza böyük bir yük verərdi. Bunun əvəzinə vaxtı bitmiş əlaqələri ləğv edə və təxirə salınmış bir təmizləmə apara bilərik. Xidmətimiz yalnız müddəti bitmiş linklərin silinməsini təmin edəcək, baxmayaraq ki, bəzi istifadə müddəti bitmiş bağlantılar daha uzun ömürlü ola bilər, lakin istifadəçilərə geri qaytarılmır.

  • Bir istifadəçi vaxtı keçmiş bir keçidə daxil olmağa çalışdıqda, linki silə və istifadəçiyə bir səhv qaytara bilərik.
  • Müddəti bitmiş bağlantıları yaddaşımızdan və önbelleğimizdən silmək üçün ayrı-ayrı bir təmizləmə xidməti vaxtaşırı işə salına bilər. Bu xidmət çox yığcam olmalıdır və yalnız istifadəçi trafikinin az olacağı gözlənildikdə işləyə bilər.
  • Hər bir keçid üçün standart bir sona çatma müddəti təyin edilə bilər (məsələn, iki il).
  • Bir müddət ziyarət edilməmiş əlaqələri silmək lazımdır, məsələn. B. altı ay? Bu çətin ola bilər. Yaddaş ucuzlaşdıqca əlaqələri əbədi saxlamağı seçə bilərik.

Caching, yüksək həcmli URL'lər üçün başqa bir kompleks problemdir.

Nə qədər yaddaşımız olmalıdır?

Gündəlik trafikin 20% -dən başlayaraq müştərilərin istifadə qaydalarına əsasən nə qədər önbellek serverinə ehtiyac duyduğumuzu tənzimləyə bilərik. Yuxarıda təxmin edildiyi kimi gündəlik trafikin 20% -ni önbelleğe almaq üçün 340 GB yaddaşa ehtiyacımız var.

Hansı önbellekdən azad etmə siyasəti ehtiyaclarımıza ən yaxşı uyğun gəlir?

uçucu - TTL, LRU və s. bir neçə seçimdir.

İstinadlar:

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

Daha çox miqyaslı problem ola bilər. Ölçeklenebilir bir url qısaldılması xidməti yaradaraq əsas minimum tələblərə cavab verməyə çalışdım.

Soruşun? Təkliflər? Qeydlər?

Nə var? Hekayələrimi ilk oxuyan olmaq üçün məni Mediumda izləyin.