URL qisqartiruvchi qanday ishlaydi

Bu darsda nima o‘rganasiz

Do‘stingiz Telegram’da havola yubordi: dars.uz/K7xQm2. Siz bosasiz va bir lahzada uzun manzilli sahifa ochiladi. Bu bosishning ortida kichik, lekin qattiq talabli tizim ishlaydi. U olti belgini to‘g‘ri manzilga aylantirishi kerak: har safar, sekundiga o‘n minglab marta, dunyoning istalgan nuqtasidan, va havola bosmaxonada chop etilgan bo‘lsa — o‘n yil o‘tib ham.

URL qisqartiruvchi — intervyularda eng ko‘p so‘raladigan tizim dizayni savoli va eng ko‘p yuzaki javob beriladigani. “Xeshlaymiz, bazaga yozamiz, redirect qilamiz” — bu javob 30 soniyada tugaydi va hech narsani ko‘rsatmaydi.

Aslida bu masala aldamchi darajada chuqur. Unda kalit maydoni matematikasi, tug‘ilgan kun paradoksi, taqsimlangan ID generatsiya, kesh strategiyalari, hot key, CDN semantikasi, ochiq redirect zaifligi va analitika quvuri bor. Aynan shuning uchun u yaxshi birinchi mashq: kichik masala ichida katta tizimning deyarli barcha naqshlari mavjud.

Dars noldan hozirgi holatigacha boradi. Avval 2002-yilda bitta dasturchi velosiped forumi uchun yozgan oddiy xizmat ko‘riladi. Keyin u oyiga milliardlab bosishga xizmat qiladigan, chekka serverlarda yashaydigan tizimga aylanadi. Oxirida Google o‘z qisqartiruvchisini yopganda nima bo‘lgani — havolaning umri haqidagi eng muhim saboq.

1. Muammo: uzun havola va uning taqdiri

1.1 Qisqa havola oddiy tilda

Oddiy tilda: katta kutubxonada har kitobning to‘liq “manzili” bor — “uchinchi qavat, sharqiy zal, 14-javon, yuqoridan ikkinchi tokcha, chapdan 37-kitob”. Buni telefonda aytib berish noqulay. Shuning uchun kutubxona har kitobga qisqa katalog raqami beradi va kartochkada yozib qo‘yadi: “K7xQm2 — uchinchi qavat, sharqiy zal, ...”. Siz faqat raqamni aytasiz, kutubxonachi kartochkaga qarab kitobni topadi.

Qisqartiruvchi aynan shu kutubxonachi. Qisqa kalit — katalog raqami, uzun URL — to‘liq manzil, baza — kartochkalar qutisi, redirect esa “kitob anavi yerda” deb ko‘rsatish. Butun dars davomida uchta savol qayta-qayta keladi:

1. Raqamni qanday berish kerak, toki ikki kitob bir xil raqam olmasin va begona odam raqamlarni sanab chiqib, hamma kitobni topa olmasin? (3-bo‘lim)
2. Kartochkani qanday tez topish kerak, agar sekundiga o‘n minglab odam so‘rasa? (6–8-bo‘limlar)
3. Kutubxona yopilsa nima bo‘ladi? Qisqa havola bannerda, kitobda, vizitkada qoladi. Xizmat yopilsa, ularning hammasi bir kunda “o‘ladi”. (11.5)

1.2 Qisqa tarix: forumdan milliardlab bosishgacha

2002-yil yanvar. Amerikalik dasturchi Kevin Gilbertson TinyURL ni ishga tushiradi. Sabab oddiy edi: u bir g‘ildirakli velosiped (unicycle) ixlosmandlarining Usenet forumlarida yozardi. Uzun havolalar xatlarda bir necha qatorga bo‘linib, buzilib qolardi. TinyURL — birinchi mashhur qisqartiruvchi va hozir ham ishlab turgan eng eskilaridan biri.

Keyingi o‘n yilda qisqa havola Twitter bilan portladi: xabar 140 belgi bilan cheklangan, uzun havola esa uning yarmini yeb qo‘yardi. 2008-yilda bit.ly paydo bo‘ldi va qisqartirishni analitika biznesiga aylantirdi: “havolangizni kim, qayerdan, qachon bosdi”. 2009-yilda Google o‘zining goo.gl xizmatini ochdi. 2011-yilda Twitter o‘z t.co qisqartiruvchisini ishga tushirdi: o‘sha yilning 10-oktabridan boshlab xabarlardagi barcha havolalar avtomatik t.co orqali o‘tadigan bo‘ldi. Endi qisqartirish foydalanuvchining tanlovi emas, platformaning xavfsizlik va o‘lchash vositasi edi.

Bugungi yetakchi qisqartiruvchilar o‘zlari haqida oyiga yuzlab million yangi havola va o‘n milliardga yaqin bosish deb yozadi. Bu raqamlar kompaniyalarning o‘z da’vosi va yildan-yilga o‘zgaradi, lekin ular dars davomida ishlatadigan farazlarimizning tartibini beradi.

Oxirgi qator darsning birinchi muhim xulosasi: bu tizimda xom quvvat asosiy muammo emas. Muammo — har bosish foydalanuvchiga yaqin joyda, tez va xatosiz tugashi va havolalar o‘n yillar yashashi.

1.3 Funksional talablar

1. Uzun URL berilganda qisqa havola qaytarish
2. Qisqa havola ochilganda foydalanuvchini asl manzilga yo‘naltirish
3. Foydalanuvchi o‘z kalitini tanlashi (dars.uz/kafka)
4. Havolaning amal qilish muddati va o‘chirilishi
5. Bosishlar statistikasi: soni, geografiya, qurilma, manba

1.4 Nofunksional talablar

1.5 Konvert orqasidagi birinchi hisob

Bu son — 6 milliard havola — keyingi bo‘limdagi kalit uzunligini tanlashning asosi bo‘ladi. To‘rtinchi raqam — yarim yemirilish — esa 8-bo‘limda keshning nega bunchalik yaxshi ishlashini tushuntiradi.

2. Nol nuqta: redirect qanday ishlaydi

Butun mahsulot bitta HTTP mexanizmiga tayanadi. Uni aniq bilmasdan qolgan hamma narsani tushunib bo‘lmaydi.

Oddiy tilda: siz eski manzilga xat yubordingiz, pochtachi esa konvertga “bu odam ko‘chib ketgan, yangi manzili — falon” degan yorliq yopishtirib, xatni qaytaradi. Siz yorliqdagi manzilga qaytadan yuborasiz. Redirect — aynan shu yorliq: server sahifani bermaydi, faqat “boshqa joyga bor” deydi va brauzer o‘zi qaytadan boradi. Yorliqda “doimiy ko‘chdi” yoki “vaqtincha boshqa joyda” deb yozilishi mumkin — bu farq 2.3 da butun mahsulotni o‘zgartiradi.

2.1 Bayt darajasida nima sodir bo‘ladi

Foydalanuvchi dars.uz/K7xQm2 ni bosdi:

GET /K7xQm2 HTTP/1.1
Host: dars.uz
User-Agent: Mozilla/5.0 ...

Server javobi:

HTTP/1.1 302 Found
Location: https://example.com/juda/uzun/manzil?utm_source=newsletter
Cache-Control: private, max-age=0, no-store
Content-Length: 0

Brauzer Location sarlavhasini ko‘radi va avtomatik yangi so‘rov yuboradi. Foydalanuvchi uchun bu bir soniyaning ulushi, tizim uchun esa — bitta to‘liq HTTP aylanmasi.

Diqqat qiling: javob tanasi bo‘sh. Ya’ni redirect juda arzon — 200–400 bayt. Butun mahsulotning asosiy operatsiyasi shu.

2.2 To‘liq kechikish byudjeti

Bu jadvaldan ikkita muhandislik xulosasi chiqadi:

1. Serverni 5 ms dan 2 ms ga tushirish deyarli hech narsa bermaydi. Tarmoq hukmron.
2. Foydalanuvchiga yaqin bo‘lish esa 50–100 ms tejaydi. Shuning uchun anycast, ko‘p mintaqa va chekka (edge) yechimlari kesh optimallashtirishdan muhimroq.

2.3 301 va 302: eng ko‘p munozara qilinadigan qaror

2.4 So‘rov serverni qanday topadi: DNS va anycast

dars.uz/K7xQm2 bosilganda brauzer avval qayerga so‘rov yuborishini bilishi kerak. Bu qadam 2.2-bo‘limdagi byudjetning eng katta o‘zgaruvchan qismi.

1. Brauzer keshi        ->  0 ms   (agar oldin ochgan bo'lsa)
2. OS keshi             ->  0 ms
3. Rekursiv resolver    ->  5-20 ms  (provayder DNS'i)
4. Avtoritativ server   ->  20-100 ms (birinchi marta)

Ko‘p mintaqaga tarqalishning ikki usuli bor va ular tubdan farq qiladi:

2.5 Demak, biz nima quryapmiz?

Barcha bezaklarni olib tashlasak, mahsulot — bu juda katta va juda tez kalit-qiymat qidiruv:

kalit:   "K7xQm2"           (6-7 belgi)
qiymat:  "https://example.com/..."  (o'rtacha 100-500 bayt)

Operatsiyalar:
  GET(kalit) -> qiymat      19 000 / soniya, p99 < 50 ms
  PUT(kalit, qiymat)        200 / soniya

Butun qolgan dars — shu ikki operatsiyani ishonchli, arzon va tez qilish haqida.

3. Kalit maydoni: eng muhim dizayn qarori

Kalit uzunligi — bu bitta son, lekin u tizimning umrini, xavfsizligini va bazasining hajmini belgilaydi.

3.1 Base62 nima uchun

Oddiy tilda: avtomobil raqamlarini o‘ylang. Faqat raqamlardan foydalansangiz (123456), olti belgida bor-yo‘g‘i million mashina sig‘adi. Harflarni qo‘shsangiz (01 A 123 BC), xuddi shu uzunlikda yuz millionlab raqam paydo bo‘ladi. Qisqa kalit ham shunday: har belgi uchun qancha ko‘p variant bo‘lsa, kalit shuncha qisqa bo‘lishi mumkin. Lekin har belgi URL ichida xavfsiz bo‘lishi va odam uni chalkashtirmasligi kerak.

URL da xavfsiz ishlatiladigan belgilar: a-z, A-Z, 0-9 — jami 62 ta. Nega aynan shu:

3.2 Nega bandlik foizi muhim

Agar kalitlarni tasodifiy tanlasak, maydon qanchalik to‘lsa, to‘qnashuv shuncha tez-tez sodir bo‘ladi. Har bir to‘qnashuv — bazaga qo‘shimcha so‘rov va qayta urinish.

P(kamida bitta to'qnashuv) ≈ 1 - e^(-n² / 2N)

n² / 2N = 3.6e19 / 7.04e12 = 5 113 636
P ≈ 1 - e^(-5113636) ≈ 1.0  (100%)

3.3 Kalit generatsiyasining to‘rt strategiyasi

Yana ikkita variant:

Hash qilib kesish — base62(md5(url))[0:7]. Jozibali ko‘rinadi, lekin ikkita jiddiy kamchiligi bor: bir xil URL har doim bir xil kalit oladi (ya’ni ikki foydalanuvchi bir xil havolani qisqartirsa, ular bitta statistikani baham ko‘radi va biri ikkinchisining havolasini o‘chira oladi), hamda kesilgan hash to‘qnashuvi baribir tekshirishni talab qiladi. Foydali holati bitta: deduplikatsiya ataylab kerak bo‘lganda.

Oldindan generatsiya (Key Generation Service) — alohida xizmat bo‘sh kalitlarni oldindan yaratib qo‘yadi, ilova serverlari ulardan bloklab oladi (masalan bir marta 10 000 ta). Yozish yo‘lidan tekshirish ham, koordinatsiya ham butunlay yo‘qoladi.

3.4 Qaysi birini tanlash kerak

3.5 Inson omili: chalkash belgilar va nomaqbul so‘zlar

Matematik jihatdan mukammal kalit maydoni amalda ikkita insoniy muammoga uriladi.

Chalkash belgilar. Havolani odam qo‘lda ko‘chirsa yoki telefonda o‘qib aytsa, 0 va O, l, I va 1 farqlanmaydi. Chop etilgan materialda yoki telefon orqali aytilgan havolada bu — to‘g‘ridan-to‘g‘ri yo‘qotilgan tashrif.

Nomaqbul so‘zlar. Tasodifiy generatsiya ertami-kechmi haqoratli yoki nomaqbul ketma-ketlik chiqaradi. Havola brend materialida chop etilsa, bu jiddiy muammo.

Generatsiya -> qora ro'yxat bo'yicha tekshirish -> mos kelsa, yangisini olish

Qora ro‘yxat maydonning juda kichik qismini (odatda 0.001% dan kam) olib tashlaydi, ya’ni sig‘imga ta’siri yo‘q. Lekin tekshiruv kalitning qismlarini ham qamrashi kerak — 7 belgili kalit ichida 4 belgili nomaqbul so‘z bo‘lishi mumkin.

4. v0: eng sodda ishlaydigan yechim

Oddiy tilda: kutubxonachi bitta daftar tutadi. Yangi kitob kelsa — tasodifiy raqam o‘ylab topadi, daftarda band emasligini tekshiradi va yozib qo‘yadi. Kimdir raqam aytsa — daftarni varaqlab, manzilni aytadi. Kichik kutubxona uchun bu yetarli. Sekundiga o‘n ming kishi kelganda esa daftar atrofida navbat paydo bo‘ladi — 5-bo‘lim shu haqda.

4.1 Ma’lumotlar modeli

CREATE TABLE links (
    key         VARCHAR(10) PRIMARY KEY,   -- "K7xQm2"
    target_url  TEXT        NOT NULL,      -- asl manzil
    owner_id    BIGINT,                    -- kim yaratgan (NULL = anonim)
    created_at  TIMESTAMPTZ NOT NULL DEFAULT now(),
    expires_at  TIMESTAMPTZ,               -- NULL = cheksiz
    is_active   BOOLEAN     NOT NULL DEFAULT true
);

CREATE INDEX idx_links_owner ON links (owner_id, created_at DESC);
CREATE INDEX idx_links_expiry ON links (expires_at) WHERE expires_at IS NOT NULL;

Va butun ilova:

@app.post("/api/shorten")
def shorten(req):
    for _ in range(5):                              # to'qnashuvda qayta urinish
        key = random_base62(7)
        try:
            db.execute(
                "INSERT INTO links (key, target_url, owner_id) VALUES (%s, %s, %s)",
                (key, req.url, req.user_id))
            return {"short": f"https://dars.uz/{key}"}
        except UniqueViolation:
            continue                                # kalit band, yangisini olamiz
    raise ServiceUnavailable("kalit topilmadi")

@app.get("/<key>")
def redirect(key):
    row = db.query_one("SELECT target_url FROM links WHERE key = %s AND is_active", (key,))
    if not row:
        return render("404.html"), 404
    return Response(status=302, headers={"Location": row.target_url})

Bu kod ishlaydi va to‘g‘ri. Kichik loyihada u yillab xizmat qilishi mumkin. Endi uni raqamlar bilan buzamiz.

4.2 Saqlash hisobi

Sahifa hajmi                  8 KB
Bitta yozuv indeksda        ~20 bayt
Sahifadagi yozuvlar    8192 / 20 = ~400

B-tree chuqurligi = log_400(6e9)
  400^1 = 400
  400^2 = 160 000
  400^3 = 64 000 000
  400^4 = 25 600 000 000   <- 6 milliard shu yerda
  Chuqurlik = 4 daraja

4.3 API dizayni va idempotentlik

Yaratish API sining bitta nozik joyi bor: tarmoq uzilib qolsa, mijoz qayta yuboradi va ikkita havola paydo bo‘ladi.

POST /api/v1/links
Idempotency-Key: 7f3a9c1e-...        <- mijoz generatsiya qiladi
Content-Type: application/json

{"url": "https://example.com/...", "custom_alias": null, "expires_at": null}

Server kalitni saqlaydi va bir xil Idempotency-Key bilan kelgan takroriy so‘rovga avvalgi javobni qaytaradi — yangi havola yaratmaydi. Kalit muddati odatda 24 soat.

Xato kodlari ham mahsulot qismi:

Redirect tomonida ham kodlar ma’noli bo‘lishi kerak: 404 — bunday kalit yo‘q, 410 Gone — bor edi, o‘chirilgan (bu SEO va mijoz uchun farqli signal), 429 — skanerga qarshi.

SELECT * FROM links
WHERE owner_id = $1 AND (created_at, key) < ($2, $3)
ORDER BY created_at DESC, key DESC
LIMIT 50;

4.4 B-tree va LSM: qaysi biri bu yukka mos

Bazani “Postgres yoki Cassandra” deb tanlash aslida ikki xil saqlash strukturasi orasidagi tanlov. Farqni bilish kerak, chunki u kechikish va disk yukini belgilaydi.

4.5 Replikatsiya va “o‘zi yozganini o‘qish” muammosi

O‘qish yukini ko‘tarish uchun replikalar qo‘shamiz. Replikatsiya asinxron — kechikish odatda 10–100 ms, yuk paytida sekundlarga chiqishi mumkin. Va shu yerda haqiqiy hayotda juda ko‘p uchraydigan bug paydo bo‘ladi:

1. Foydalanuvchi havola yaratdi        -> asosiy bazaga yozildi
2. 200 ms dan keyin havolani bosdi     -> so'rov replikaga tushdi
3. Replikada hali yozuv yo'q           -> 404

Foydalanuvchi uchun bu “sizning xizmatingiz buzuq” degani. Uch yechim bor:

Bizning holatimizda birinchisi eng yaxshi: yaratish paytida yozuvni darhol keshga qo‘yamiz. Bu tabiiy, chunki yangi havola deyarli har doim darhol bosiladi — ya’ni u allaqachon “issiq” ma’lumot.

5. Nima sindi: v0 ning oltita zaif nuqtasi

Oddiy tilda: kutubxona mashhur bo‘ldi. Endi bitta daftar oldida minglab odam turibdi, ular orasida hammasi bir xil kitobni so‘rayotgan olomon bor, kimdir har kirganni sanab daftarga chiziq tortyapti, kimdir esa ataylab mavjud bo‘lmagan raqamlarni so‘rab kutubxonachini band qilyapti. Va kutubxona boshqa shaharda — odamlar yo‘lda soatlab yuradi. v0 ning har bir zaif nuqtasi shu manzaraning bir bo‘lagi.

5.1 O‘qish yuki bazani bo‘g‘adi

19 300 redirect/s — har biri bitta SELECT. Bitta Postgres instansiyasi yaxshi holatda 5 000–15 000 oddiy so‘rovni uddalaydi. Ya’ni cho‘qqida tizim yiqiladi, va yiqilish sekin emas: ulanishlar to‘lib, kutish vaqti oshib, timeout‘lar boshlanadi.

5.2 Bitta havola butun tizimni yiqitishi mumkin

Mashhur bloger bitta havolani ulashdi. U sekundiga 50 000 marta bosilyapti — bitta kalit, bitta baza qatori. Sharding yordam bermaydi (hammasi bitta shardda), replikatsiya qisman yordam beradi. Bu hot key muammosi.

5.3 Statistika yozish o‘qishdan qimmatroq

Har bosishda UPDATE links SET clicks = clicks + 1 yozsak, bitta qatorga sekundiga 50 000 marta yozish kerak bo‘ladi. Bu qulf raqobati (lock contention): tranzaksiyalar navbatga tizilib, redirect kechikishi sekundlarga chiqadi.

5.4 Yaratish yo‘li koordinatsiyaga bog‘lanib qoldi

Har bir yozuvda INSERT + to‘qnashuvda qayta urinish. Maydon to‘lib borgani sari qayta urinishlar ko‘payadi va yozish kechikishi o‘sadi.

5.5 Geografiya hisobga olinmagan

Server Frankfurtda, foydalanuvchi Toshkentda. Faqat tarmoq 150 ms qo‘shadi — server 5 ms ishlaganida. 2.2-bo‘limdagi byudjetga qarang: bu eng katta yo‘qotish.

5.6 Yo‘q havolalar bazani urib turadi

Bot va skanerlar mavjud bo‘lmagan kalitlarni so‘rab turadi (/aaa, /aab, …). Har biri keshda topilmaydi va to‘g‘ri bazaga tushadi. Bu — cache penetration hujumi va u oddiy skaner tomonidan tasodifan ham amalga oshiriladi.

6. Evolyutsiya: o‘n to‘rt qadam

Qadamlar mantiqiy tartibda: 1–4 — o‘qish yo‘li (saqlash, kesh, hot key, chekka); 5–7 — kalitlar, shardlar va yo‘q kalitlar; 8 — analitika; 9–11 — mahsulot va suiiste’mol; 12–14 — ko‘p mintaqa, metama’lumot va o‘n yillik umr. Har qadamda yutuq va narx yozilgan: bepul qadam yo‘q.

def resolve(key):
    url = cache.get(key)
    if url is not None:
        return None if url == NEGATIVE else url   # 404 ham keshlanadi
    row = db.query_one("SELECT target_url FROM links WHERE key=%s AND is_active", (key,))
    if row is None:
        cache.set(key, NEGATIVE, ttl=60)          # qisqa TTL: yo'q kalitlar uchun
        return None
    cache.set(key, row.target_url, ttl=86400)
    return row.target_url

Kesh: 20M yozuv, LRU
Skaner: 5000 yangi kalit / soniya

1 soatda: 18 million yangi (foydasiz) yozuv keshga kirdi
  -> issiq havolalarning katta qismi chiqarib yuborildi
  -> urish darajasi 95% dan 60% ga tushdi
  -> bazaga yuk 4-8 barobar oshdi

So'rov -> L1 (jarayon xotirasi, 10 000 ta eng issiq kalit, TTL 5 s)
       -> L2 (Redis, 20M kalit, TTL 24 soat)
       -> Baza

HTTP/1.1 302 Found
Location: https://example.com/...
Cache-Control: public, s-maxage=300, stale-if-error=86400

KGS bazasi:  [kalit, band_mi]  yoki oddiyroq — diapazon jadvali

Ilova serveri ishga tushganda:
  1. KGS dan 10 000 talik diapazon oladi        (bitta so'rov)
  2. Xotirasida saqlaydi
  3. Har yozuvda navbatdagisini oladi           (koordinatsiyasiz)
  4. Tugagach yangi diapazon so'raydi

shard = hash(kalit) mod N

PFADD link:K7xQm2:visitors <foydalanuvchi_id>
PFCOUNT link:K7xQm2:visitors   ->  1 043 219 (standart xato ~0.8%)

DELETE /api/links/K7xQm2
  1. Bazada is_active = false        (tombstone, qator o'chirilmaydi)
  2. Keshdan o'chirish yoki NEGATIVE qilib belgilash
  3. Chekka nuqtalarga purge signali
  4. Bloom filtridan chiqarilmaydi (o'chirib bo'lmaydi - 7-qadam)

Limit: daqiqasiga 100 ta

12:00:59 da 100 ta so'rov  (birinchi oyna)
12:01:00 da 100 ta so'rov  (ikkinchi oyna)
-> 2 soniyada 200 ta so'rov o'tdi, limit esa 100 edi

joriy oynaning 30% i o'tgan bo'lsa:
  taxminiy = oldingi_oyna x 0.7 + joriy_oyna

Mintaqa A: kalitning birinchi belgisi [a-h] dan
Mintaqa B: [i-p] dan
Mintaqa C: [q-z, A-Z, 0-9] dan

Sertifikat muddati: 90 kun
Yangilash 60-kunda boshlanadi
Kunlik yangilash: 100 000 / 60 = ~1670 sertifikat / kun

Yechish: kalit uzunligiga qarab emas, aynan kalit bo'yicha qidiriladi
  -> 5, 6, 7, 8 belgili kalitlar bir vaqtda yashaydi

Generatsiya: joriy uzunlik konfiguratsiyada
  -> maydon 20% to'lganda uzunlik bir belgiga oshiriladi

1-bosqich: IKKI TOMONLAMA YOZISH
   Yangi yozuvlar eski VA yangi bazaga yoziladi
   O'qish hali eskidan. Yangi bazaning to'g'riligi kuzatib boriladi

2-bosqich: TO'LDIRISH (backfill)
   6 milliard qator paketlab ko'chiriladi
   50 000 qator/s tezlikda: 6e9 / 5e4 = 120 000 s = ~33 soat
   Asosiy bazaga ta'sir qilmasligi uchun replikadan o'qiladi

3-bosqich: TEKSHIRISH
   Tasodifiy namuna solishtiriladi (masalan 1 million qator)
   Diapazonlar bo'yicha nazorat summalari
   Farq topilsa - sabab aniqlanmaguncha davom etilmaydi

4-bosqich: O'QISHNI BOSQICHMA-BOSQICH KO'CHIRISH
   1% -> 10% -> 50% -> 100%
   Har bosqichda 404 darajasi va kechikish kuzatiladi

5-bosqich: ESKI BAZANI O'CHIRISH
   Kamida bir necha hafta kutiladi - orqaga qaytish imkoni saqlanadi

7. Bitta bosishning hayoti

Evolyutsiyadan keyin tizim ko‘p qatlamli bo‘lib qoldi. Endi bitta bosishni boshidan oxirigacha kuzatamiz. Shunda har qatlam nega kerakligi va vaqt qayerga ketishi ko‘rinadi.

7.1 Qadam-baqadam

Oddiy tilda: siz mahalladagi filialga kirasiz. Ko‘p hollarda kerakli ma’lumot shu yerdagi ma’lumotnomada bor — javob darhol. Kamdan-kam hollarda filial markaziy kutubxonaga qo‘ng‘iroq qiladi. Siz esa farqni faqat kutish vaqtidan sezasiz.

1. DNS dars.uz uchun bitta IP qaytaradi, lekin bu IP yuzlab nuqtadan e’lon qilingan (anycast, 2.4). Tarmoq so‘rovni eng yaqin nuqtaga olib boradi.
2. TCP va TLS chekkada tugaydi — foydalanuvchidan 10–20 ms masofada. Ilgari ulanish bo‘lgan bo‘lsa, bu qadam qayta ishlatiladi.
3. Chekka KV da kalit bor bo‘lsa (odatda 90% va undan ko‘p), javob shu yerda yasaladi: 302 va Location.
4. Bosish hodisasi chekkadagi buferga tushadi va paketlab markazga ketadi (8-qadam). Foydalanuvchi buni kutmaydi.
5. Chekkada kalit yo‘q bo‘lsa — origin yo‘li: Bloom filtri → L1 → L2 → baza. Topilgan javob chekkada ham keshlanadi.

7.2 Vaqt qayerga ketadi

Bu hisobdan amaliy qoida chiqadi: chekkada topilish ulushini bitta asosiy metrika sifatida kuzating (14-bo‘lim). Serverdagi kod tezligini ikki barobar oshirish o‘rtachani 1–2 ms ga o‘zgartiradi. Chekkada topilish ulushini 50% dan 90% ga ko‘tarish esa o‘rtachani ~50 ms ga kamaytiradi.

7.3 Yangi havolaning birinchi daqiqasi

Eng nozik lahza — havola endigina yaratilgan payt. Ma’lumot hali hamma qatlamga yetib bormagan.

Agar birinchi bosish chekkaga havola yetib kelmasdan oldin kelsa, chekka uni topmaydi va origin’dan so‘raydi (miss-to-origin). Origin’da esa havola allaqachon bor: L2 keshda va Bloom filtrida. Ya’ni foydalanuvchi ozgina sekinroq javob oladi, lekin xato olmaydi.

8. Kesh matematikasi: nega oz sonli havola trafikning ko‘pini oladi

2-qadamda “eng faol 20 million havola trafikning 95% ini oladi” deb faraz qildik. Endi bu raqam qayerdan kelishini va qachon noto‘g‘ri bo‘lishini ko‘ramiz. Bu bo‘lim keshning hajmi, TTL va xarajatini hisoblash uchun asos bo‘ladi.

8.1 Oddiy tilda: vitrina

Oddiy tilda: kitob do‘konida yuz ming nom kitob bor, lekin kirish oldidagi vitrinada atigi ikki yuztasi turadi. Shunga qaramay, xaridorlarning katta qismi aynan vitrinadan oladi, chunki u yerda hozir hamma o‘qiyotgan kitoblar bor. Vitrina — kesh. Qanchalik kichik vitrina qanchalik ko‘p xaridorga xizmat qilishi ikki narsaga bog‘liq: kitoblar mashhurligi qanchalik notekis va mashhurlik qanchalik tez o‘zgaradi.

8.2 Notekislik: Zipf taqsimoti

Havolalar mashhurligi taxminan Zipf qonuniga bo‘ysunadi: eng mashhur havola ikkinchisidan taxminan ikki, uchinchisidan uch barobar ko‘p bosiladi. Umumiy holda i-o‘rindagi havolaning ulushi 1 / i^s ga proporsional. s qancha katta bo‘lsa, taqsimot shuncha notekis.

2-daraja amaliyotidagi simulyatsiya (60 000 havola, skaner, yangi va o‘chirilgan havolalar bilan) ham shuni ko‘rsatadi. Jadvalda — so‘rovlarning qancha qismi bazaga yetib borgani:

Ikkita saboq. Birinchisi: egrilik (s) kesh hajmidan kuchliroq. s ning 1.0 dan 1.2 ga o‘zgarishi bazaga yukni keshni to‘rt barobar oshirishdan ko‘proq kamaytiradi. Ikkinchisi: keshni ikki barobar oshirish bazaga yukni ikki barobar emas, atigi ~20–30% kamaytiradi.

8.3 Vaqt: havolaning yarim yemirilishi

Mashhurlik vaqt o‘tishi bilan so‘nadi. bit.ly 2011-yilda 1000 ta havolani tahlil qildi. Ular “yarim yemirilish”ni shunday aniqladi: havola eng ko‘p bosilgan paytdan boshlab, umrbod bosishlarining yarmini qancha vaqtda yig‘ishi. Natija: Twitter’da 2.8 soat, Facebook’da 3.2 soat, email va messenjerlarda 3.4 soat, YouTube’da 7.4 soat.

Bu — keshning “sirli” samaradorligining asosiy sababi. Har lahzada haqiqatan bosilayotgan havolalar — asosan so‘nggi bir-ikki kunda yaratilgan yoki ulashilganlar. Ular esa jami havolalarning juda kichik qismi.

LRU aynan shu vaqt omiliga mos keladi: u yaqinda so‘ralganlarni ushlaydi va eskirganlarni o‘zi chiqarib tashlaydi. Shuning uchun real trafikda LRU sodda Zipf modelidan ancha yaxshi natija beradi. Lekin bitta xavfi bor: skaner ham “yaqinda so‘ralgan” bo‘lib ko‘rinadi (2-qadam Deep). Shu sabab salbiy yozuvlar alohida saqlanadi.

8.4 TTL: yangilik va yuk orasidagi tanlov

Amaliy yechim ikki qismdan iborat: uzun TTL (soatlar yoki sutka) va o‘zgarish bo‘lganda majburiy invalidatsiya (10-qadam). TTL bu holda “xavfsizlik to‘ri” vazifasini bajaradi: invalidatsiya signali yo‘qolib qolsa, eskirish baribir TTL bilan cheklanadi.

9. Bugungi arxitektura

O‘qish yo‘li — so‘rov yuqoridan pastga tushadigan “elak”: har qatlam so‘rovlarning katta qismini o‘zi hal qiladi va pastga faqat qolganini yuboradi. Bazaga 19 300 so‘rovdan bir necha o‘ntasi yetib boradi.

9.1 Ikki yo‘lning qiyosi

Bu ajratish — darsning asosiy g‘oyasi. Ikki yo‘lning talablari butunlay boshqacha, shuning uchun ular boshqacha loyihalanadi. Ularni bitta “xizmat” deb qarash — birinchi arxitektura xatosi.

9.2 Mahsulot qatlami: havola faqat redirect emas

Ishlab chiqarishdagi qisqartiruvchi bir nechta qo‘shimcha talabni ko‘taradi va ularning har biri arxitekturaga tegadi:

UTM va marketing parametrlari. Havola yaratilganda maqsad URL ga utm_source, utm_campaign kabi parametrlar qo‘shiladi. Muhim tafsilot: bu parametrlarni saqlash paytida qo‘shish kerak, redirect paytida emas — aks holda har bir bosishda satr manipulyatsiyasi bajariladi va kesh kaliti murakkablashadi.

Mobil ilova havolalari. Foydalanuvchi telefonda havolani ochsa, brauzer emas, ilova ochilishi kerak. Bu Universal Links (iOS) va App Links (Android) orqali ishlaydi va domendan maxsus fayl talab qiladi (/.well-known/apple-app-site-association). Ya’ni sizning domeningiz endi faqat redirect emas, statik fayl ham xizmat qiladi — va u kalit qidiruvidan oldin tekshirilishi kerak.

QR kodlar. Qisqa havolaning QR kodi kichikroq va ishonchliroq skanerlanadi:

Qiziq tafsilot: QR’ning yana bir, ixchamroq “alfanumerik” rejimi bor, lekin u faqat katta harflar, raqamlar va bir nechta belgini qabul qiladi. Shuning uchun ba’zi xizmatlar QR uchun alohida, faqat katta harfli kalitlar beradi: DARS.UZ/K7XQM2 ixchamroq kodga sig‘adi.

Havola guruhlari va boshqaruv paneli. Kampaniya bo‘yicha guruhlash, birgalikda statistika, ommaviy import (CSV orqali 100 000 havola) — bularning har biri yozish yo‘liga yuk qo‘shadi. Ommaviy import alohida navbat orqali, tezligi cheklangan holda bajarilishi kerak; aks holda bitta mijoz KGS diapazonlarini tugatib, boshqalarning yaratishini to‘xtatib qo‘yadi.

10. Ishonchlilik: nima buziladi

10.1 Cache stampede (thundering herd)

Hot kalitning TTL i tugadi. Shu lahzada 50 000 ta so‘rov keshda topmaydi va bir vaqtda bazaga yuguradi.

Uchta himoya, birgalikda ishlatiladi:

1. Single-flight — bitta kalit uchun faqat bitta so‘rov bazaga boradi, qolganlari uning natijasini kutadi
2. Ehtimolli erta yangilash — TTL tugashiga yaqin har bir so‘rov kichik ehtimollik bilan keshni yangilaydi. Natijada yangilash bitta lahzada emas, vaqt bo‘ylab tarqaladi
3. Stale-while-revalidate — eskirgan qiymat qaytariladi, yangilash fonda ketadi. Redirect uchun bu mukammal: bir necha soniya eski manzil hech kimga zarar qilmaydi

def resolve_with_swr(key):
    entry = cache.get(key)
    if entry and not entry.expired:
        return entry.url
    if entry and entry.stale_ok:
        refresh_in_background(key)     # foydalanuvchi kutmaydi
        return entry.url
    with single_flight(key):           # faqat bitta so'rov bazaga boradi
        return load_from_db(key)

10.2 Nosozliklar taksonomiyasi

10.3 Degradatsiya tartibi

Bu tartibning mantig‘i bitta: chop etilgan havola ishlashi kerak. U bannerda, vizitkada, kitobda bo‘lishi mumkin. Yangi havola yaratilmasligi — noqulaylik; eski havola ishlamasligi — halokat.

10.4 Ulanish hovuzi: Little qonuni amalda

“Baza sekin” degan shikoyatning yarmi aslida noto‘g‘ri sozlangan ulanish hovuzi. Kerakli hajm intuitsiya bilan emas, formula bilan topiladi:

Ulanishlar soni = throughput x kechikish

10.5 Bu tizimni qanday sinash kerak

Testlar odatdagi CRUD ilovasidan farq qiladi, chunki eng qimmat xatolar poyga holatlari va yuk ostidagi xatti-harakatda.

11. Xavfsizlik

11.1 Ochiq redirect (open redirect)

Sizning domeningiz istalgan manzilga yo‘naltiradi. Bu mahsulotning maqsadi, lekin ayni paytda klassik zaiflik:

Fishing xati:
  "Bankingizdan xabar: hisobingizni tasdiqlang -> dars.uz/K7xQm2"

Foydalanuvchi ishonchli domenni ko'radi, lekin soxta saytga tushadi.

Bundan tashqari, ba’zi saytlar ishonch qarorlarini domen bo‘yicha qabul qiladi (masalan Referer tekshiruvi yoki OAuth redirect_uri oq ro‘yxati). Sizning domeningiz ularning himoyasini chetlab o‘tish vositasiga aylanishi mumkin.

Choralar: yaratishda skanerlash, shubhali havolalarga oraliq ogohlantirish sahifasi, shikoyat mexanizmi va tez o‘chirish, hamda rel="noopener noreferrer" va Referrer-Policy sarlavhalari.

11.2 Kalitlarni sanab chiqish (enumeration)

Ketma-ket yoki qisqa kalitlar bo‘lsa, hujumchi /aaa, /aab, /aac deb sanab chiqib, odamlarning shaxsiy havolalarini (hujjatlar, hisob-kitoblar, buyurtma sahifalari) to‘playdi. Bu nazariy emas — real hodisalarda milliondan ortiq shaxsiy hujjat shu yo‘l bilan topilgan.

Choralar: yetarli uzun va tasodifiy kalitlar (3.4-bo‘lim), IP bo‘yicha tezlik cheklovi, 404 javoblarga sun’iy kechikish, va eng muhimi — foydalanuvchilarga “qisqa havola maxfiy emas” ekanini aniq aytish.

11.3 Maxfiylik

11.4 SSRF va metama’lumot

13-qadamdagi ogohlantirish shu yerga ham tegishli: foydalanuvchi bergan URL ni server o‘qiganda ichki tarmoqqa kirish yo‘li ochiladi. Tekshiruv DNS yechimidan keyin, IP darajasida bo‘lishi kerak — domen nomi bo‘yicha tekshirish yetarli emas, chunki hujumchi o‘z domenini ichki IP ga yo‘naltirishi mumkin (DNS rebinding).

11.5 Havolaning o‘limi: goo.gl saboqi

Oddiy tilda: siz kitobingizda “batafsil: kutubxona katalogining K7xQm2 raqami” deb yozdingiz. Kitob o‘n yil sotiladi. Besh yildan keyin kutubxona yopilsa, kitobdagi har bir havola bir kunda o‘ladi — va siz uni hech qanday yo‘l bilan tuzata olmaysiz, chunki kitob allaqachon bosilgan.

Bu nazariy xavf emas. Google 2018-yil martida goo.gl ni yopishni e’lon qildi, 2019-yil 30-martdan yangi havola yaratish to‘xtadi. Eski havolalar yana besh yil ishladi. 2024-yil iyulda Google ularni ham o‘chirishini aytdi: havolalarning 99% dan ortig‘i o‘tgan oyda birorta ham bosish olmagan. 2024-yil avgustidan havolalarda ogohlantirish chiqa boshladi. 2025-yil 25-avgustdan esa nofaol havolalar 404 qaytara boshladi. Keyinroq Google ogohlantirish ko‘rsatilmagan, ya’ni 2024-yil oxirida faol bo‘lgan havolalar ishlashda davom etishini aniqlashtirdi.

Muhandis uchun uchta saboq:

1. Havola — va’da. Qisqa havola chop etilgan materialda xizmatdan uzoq yashaydi. Shuning uchun “o‘chirish siyosati” birinchi kundan yozilishi kerak: qachon, qanday ogohlantirish bilan, qaysi havolalar saqlanadi.
2. Chiqish yo‘li bo‘lsin. Foydalanuvchiga havolalar ro‘yxatini eksport qilish imkonini bering (17.5 dagi savol). Shunda xizmat yopilsa ham, ular o‘z domenida redirect’larni tiklay oladi.
3. O‘z domeningiz — eng yaxshi sug‘urta. Maxsus domen (go.brand.uz, 13-qadam Deep) ishlatgan mijoz xizmatni almashtirganda havolalarini yo‘qotmaydi: DNS yozuvini yangi provayderga yo‘naltirish va ro‘yxatni ko‘chirish yetarli.

12. Iqtisod

Ikkita xulosa:

1. Eng katta xarajat — chekka so‘rovlari va trafik, saqlash emas. Ya’ni optimallashtirish javob hajmini kamaytirishdan (bo‘sh tana, minimal sarlavhalar) va brauzer keshidan (301 masalasi) boshlanadi
2. Bitta havola juda arzon, lekin bepul emas. Bepul tarifda cheksiz havola berish — suiiste’molchilar uchun taklifnoma. Shuning uchun deyarli barcha qisqartiruvchilar yaratishni cheklaydi, o‘qishni esa cheklamaydi

12.1 Bitta havolaning umrbod narxi

Oddiy tilda: kutubxonaga kartochka qo‘shish deyarli bepul — qog‘oz arzon. Qimmat narsa boshqa joyda: har yangi kitobni “ichida zararli narsa yo‘qmi” deb tekshirish, va kim qachon o‘qiganini yozib borish.

Bu jadval 11.5 dagi saboqni raqam bilan tasdiqlaydi: havolani “abadiy” saqlash arzon. Qimmat narsa — suiiste’molga qarshi kurash va xizmatni yuritish. Biznes modeli ham shunga mos: bepul tarifda yaratish cheklangan, pullik tarifda esa mijoz analitika, maxsus domen va ko‘proq yaratish uchun to‘laydi.

13. Sig‘im rejalashtirish

13.1 Ko‘p ijarachilik: shovqinli qo‘shni muammosi

Bitta mijoz 100 000 havolani CSV orqali import qilyapti, ikkinchisining kampaniyasi viral bo‘ldi. Ikkalasi ham bir xil shardlarda, bir xil keshda, bir xil KGS diapazonlarida.

Umumiy tamoyil: har bir umumiy resurs uchun kvota bo‘lishi kerak, va kvota buzilganda tizim butunlay to‘xtamasligi, faqat o‘sha mijozni sekinlashtirishi kerak. Bu — adolatli rejalashtirish (fair scheduling) masalasi va u ChatGPT darsidagi navbat prioritetlari bilan bir xil sinfdan.

14. Kuzatuv va sifat

Har bir redirect uchun yozilishi kerak:

kalit, javob_kodi (302 | 404 | 410 | 429)
manba (chekka | L1 | L2 | baza)
kechikish_ms, mintaqa, chekka_nuqtasi
bot_mi (User-Agent tahlili)

Panellarda:

14.1 SLO va xato byudjeti

“99.99% mavjudlik” degan gap byudjetga aylantirilmasa, ma’nosiz shior bo‘lib qoladi.

Xato byudjeti amaliy vosita: u sarflanadi. Byudjet qolgan bo‘lsa — yangi xususiyatlarni chiqarish mumkin; tugagan bo‘lsa — jamoa barqarorlikka o‘tadi. Bu muhandislik va mahsulot o‘rtasidagi bahsni raqamga aylantiradi.

Sarflash tezligi bo‘yicha ogohlantirish (burn rate) oddiy chegaradan yaxshiroq ishlaydi:

Agar oxirgi 1 soatda byudjetning 2% i sarflansa   -> tez ogohlantirish (sahifa)
Agar oxirgi 6 soatda byudjetning 5% i sarflansa   -> sekin ogohlantirish (tiket)

Birinchisi jiddiy uzilishni darhol ushlaydi, ikkinchisi sekin oqib turgan muammoni — va ikkalasi ham “xato darajasi 0.1% dan oshdi” degan shovqinli alertdan foydaliroq.

14.2 Bot trafigi: statistikaning eng katta yolg‘oni

Havola ijtimoiy tarmoqqa qo‘yilganda uni odamlardan oldin robotlar ochadi: xabar oldindan ko‘rish (unfurl) botlari, xavfsizlik skanerlari, arxivlovchilar, raqobatchilarning kuzatuv vositalari.

Botlarni ajratishning uch usuli, ishonchliligi bo‘yicha:

1. User-Agent ro‘yxati — oson, lekin eskiradi va soxtalashtirilishi mumkin
2. Xulq-atvor — bot havolani qo‘yilgan lahzada, bir necha millisoniya ichida ochadi va keyin hech qachon qaytmaydi; odam esa tasodifiy vaqtda keladi
3. IP obro‘si — ma’lum bulut provayderlari diapazonlari va bot tarmoqlari

15. Antinaqshlar

16. Trade-off‘lar

Butun dars o‘nta gapda

1. Qisqartiruvchi — juda katta va juda tez kalit-qiymat qidiruv: bitta GET va bitta PUT; qolgan hamma narsa ularni tez, arzon va ishonchli qilish uchun (2.5).
2. O‘qish yozishdan 100–1000 barobar ko‘p: ikki yo‘l alohida loyihalanadi — o‘qish chekkada va keshda, yozish bitta mintaqada, tranzaksion (1.4, 9.1).
3. 302, 301 emas: brauzer keshi analitikani va havolani o‘zgartirish imkonini o‘ldiradi (2.3).
4. Kalit uzunligi raqamdan chiqadi: 6 milliard havola → 7 belgili base62; to‘qnashuvni yo‘q qilish emas, arzon qilish kerak (3-bo‘lim).
5. Hisoblagich + Feistel + blok: takrorsiz, taxmin qilinmaydigan kalitlar markazga deyarli murojaatsiz (3.3, 5-qadam).
6. Kechikishni tarmoq belgilaydi: server 5 ms, tarmoq 150 ms — chekka va anycast kesh optimallashtirishdan muhimroq (2.2, 7.2).
7. Kesh vaqt bo‘yicha so‘nishga tayanadi: yarim yemirilish ~3 soat, shuning uchun 20 mln yozuv 6 mlrd havolaning ~95% trafigini oladi; urish darajasini emas, topilmaslikni hisoblang (8-bo‘lim).
8. Keshning nosozliklari keshsizlikdan xavfliroq: stampede, hot key, skaner — single-flight, SWR, L1 va Bloom filtri bilan (6, 10-bo‘limlar).
9. Analitika asinxron va yo‘qotishga ruxsat etilgan: statistika buzilsa ham havola ishlashi kerak (8-qadam, 10.3).
10. Havola — va’da: u chop etiladi va xizmatdan uzoq yashaydi; kalitni qayta ishlatmang, eksport bering, yopishni bosqichma-bosqich rejalashtiring (10-qadam, 11.5).

17. Intervyu savollari

17.1 Asoslar

17.2 Kesh va masshtab

17.3 Ma’lumot va analitika

17.4 Xavfsizlik

17.5 Amaliy stsenariylar

18. Amaliyot

To‘rt daraja. Ikkinchi daraja uchun kod va avtomatik tekshiruvlar docs/amaliyot/url-shortener/ da: keys.py, bloom.py, cache.py — TODO; model.py — tayyor alifbo, barqaror xesh, markaziy hisoblagich, “baza” va Zipf trafigi; check.py — 17 ta tekshiruv.

19. Lug‘at

20. Raqamlar manbasi

Oyiga 100 mln havola, o‘qish/yozish nisbati, cho‘qqi koeffitsienti, URL o‘rtacha uzunligi, kesh urish darajasi, chekkada topilish ulushi, server va saqlash narxlari, kechikishlar va 11.5, 12.1 dagi xarajatlar — illyustratsiya uchun taxminiy raqamlar. Ular bozor yetakchilarining ochiq raqamlari tartibida tanlangan. Asosiy xulosalar — o‘qish yo‘lini chekka va keshga berish, kalit uzunligini hisob bilan tanlash, 302 ni tanlash, analitikani asinxron qilish va havolani va’da sifatida ko‘rish — bu raqamlarning bir necha barobarlik xatosiga ham chidamli.

21. Manbalar

• RFC 9110, “HTTP Semantics” (2022) — 301/302/307/308 va keshlanish
• David Karger va boshq. (1997), “Consistent Hashing and Random Trees”, STOC
• Burton H. Bloom (1970), “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM
• Adam Kirsch, Michael Mitzenmacher (2006), “Less Hashing, Same Performance: Building a Better Bloom Filter”, ESA
• Philippe Flajolet va boshq. (2007), “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”, AofA
• Andrea Vattani va boshq. (2015), “Optimal Probabilistic Cache Stampede Prevention”, VLDB
• Gil Einziger, Roy Friedman, Ben Manes (2017), “TinyLFU: A Highly Efficient Cache Admission Policy”, ACM Transactions on Storage
• Lee Breslau va boshq. (1999), “Web Caching and Zipf-like Distributions: Evidence and Implications”, INFOCOM
• Michael Luby, Charles Rackoff (1988), “How to Construct Pseudorandom Permutations from Pseudorandom Functions”, SIAM Journal on Computing (Feistel tarmog‘i)
• John Black, Phillip Rogaway (2002), “Ciphers with Arbitrary Finite Domains”, CT-RSA (cycle walking)
• bit.ly (2011), “You just shared a link. How long will people pay attention?” — havola yarim yemirilishi tadqiqoti
• Google Developers Blog (2018, 2024) — goo.gl ni yopish e’lonlari
• Instagram Engineering, “Sharding & IDs at Instagram” — mantiqiy shardlar
• Twitter Engineering, “Announcing Snowflake” (2010) — taqsimlangan ID
• OWASP: Unvalidated Redirects and Forwards; Server-Side Request Forgery Prevention Cheat Sheet