Konspekt · Butun tizimlar
Qidiruv takliflari (autocomplete) dizayni
Muammo
Qidiruv maydonidagi har bosish o'nta taklif so'raydi va javob keyingi tugmadan oldin kelishi kerak. Tizimni qadamma-qadam quramiz: vaqt byudjeti, `LIKE 'pre%'` nega yiqiladi, har tugunda tayyor top-k saqlaydigan trie, prefiks bo'yicha shard'lar, debounce va CDN, atomik almashtiriladigan oflayn pipeline, trendlar uchun real vaqt qatlami, filtr va shaxsiylashtirish narxi.
Nimani o'rganasiz
- Tugma bosishlarini so'rov tezligi va kechikish byudjetiga qanday aylantirish
- Nega har tugunida top-k saqlangan prefiks daraxti baza so'rovidan yutadi
- Debounce, mijoz keshi va CDN so'rovlarning ko'pini backend'ga yetmasdan qanday olib qoladi
- Oflayn pipeline, atomik indeks almashtirish va kichik real vaqt qatlami takliflarni qanday yangi va toza saqlaydi
Diagramma kod sifatida
Darsdagi yakuniy sxemani matn ko'rinishida oling va Jira, GitLab, GitHub, Notion yoki hujjatga qo'ying: Mermaid u yerlarda o'zi chiziladi. D2 va PlantUML (Confluence, IntelliJ) uchun alohida variantlar bor.
Mermaid: sxema
flowchart LR
n_user(["Qidiruv maydoni"])
n_api["Suggest API"]
n_index{{"Indeks shard 1"}}
n_index2{{"Indeks shard 2"}}
n_cdn[/"CDN edge"\]
n_queue[["So'rovlar logi"]]
n_agg("Agregatsiya job")
n_storage[("Snapshot'lar")]
n_trend{{"Trend 5 daqiqa"}}
n_api --> n_index
n_api --> n_index2
n_user --> n_cdn
n_cdn -.-> n_user
n_cdn --> n_api
n_api -->|"asinxron"| n_queue
n_queue --> n_agg
n_agg --> n_storage
n_storage --> n_index
n_storage --> n_index2
n_queue --> n_trend
n_api --> n_trendMermaid: so'rovlar ketma-ketligi
sequenceDiagram
participant n_user as Qidiruv maydoni
participant n_api as Suggest API
participant n_db as So'rovlar bazasi
participant n_index as Indeks shard 1
participant n_cdn as CDN edge
participant n_agg as Agregatsiya job
participant n_storage as Snapshot'lar
participant n_trend as Trend 5 daqiqa
participant n_queue as So'rovlar logi
Note over n_user,n_api: Har bosishga o'nta taklif, keyingi tugmadan oldin
n_user->>n_api: GET /suggest?q=ip#38;lang=en HTTP/1.1
n_api-->>n_user: HTTP/1.1 200 OK
Note over n_api,n_db: LIKE 'ip%' o'nta qaytarish uchun millionlab qator o'qiydi
n_api->>n_db: EXPLAIN ANALYZE
n_db-->>n_api: Limit (actual time=611.4..611.5 rows=10)
Note over n_api,n_index: Har tugunda javobi tayyor turgan trie
n_api->>n_index: lookup prefix=#34;ip#34;
n_index-->>n_api: walk root -#62; i -#62; p (2 hops)
Note over n_api,n_index: Indeksni prefiks oralig'i bo'yicha shard qilish
n_api->>n_index: shard map v7 (split by traffic, not alphabet)
n_index-->>n_api: [a, iq) -#62; idx-1 heap 29 GB 49% of traffic
Note over n_user,n_api: Har bosish bitta so'rov
n_user->>n_api: 18:14:02.110 GET /suggest?q=i
Note over n_user,n_cdn: So'rovlarning ko'pi backend'ga yetib bormaydi
n_user->>n_cdn: GET /suggest?q=ip#38;lang=en HTTP/1.1
n_cdn-->>n_user: HTTP/1.1 200 OK
Note over n_agg,n_storage: So'rovlar logi keyingi indeksga aylanadi
n_agg->>n_storage: agg output window=2026-11-17T08:00Z/1h
Note over n_storage,n_index: Yangi trie ni eskisi yoniga yuklab, bitta ko'rsatkichni almashtirish
n_storage->>n_index: 10:05:12 idx-1 loaded snapshot trie-2026-11-17T09 (29.4 GB, 41 s)
Note over n_api,n_trend: Hozir issiq narsalar uchun kichik real vaqt qatlami
n_api->>n_trend: trend.match prefix=#34;st#34; window=5m
n_trend-->>n_api: storm warning 1 812 / 5m x46 vs usual
Note over n_queue,n_trend: Hech narsa ko'rsatilishidan oldin filtrlash
n_queue->>n_trend: filter drop #34;cheap pills now#34; from trend:en
n_trend-->>n_queue: rule blocklist match (spam)
Note over n_user,n_cdn: Shaxsiylashtirish keshga tushadi
n_user->>n_cdn: GET /suggest?q=iph#38;lang=en HTTP/1.1
n_cdn-->>n_user: HTTP/1.1 200 OKD2
direction: right
n_user: "Qidiruv maydoni" {
shape: rectangle
}
n_api: "Suggest API" {
shape: rectangle
}
n_index: "Indeks shard 1" {
shape: hexagon
}
n_index2: "Indeks shard 2" {
shape: hexagon
}
n_cdn: "CDN edge" {
shape: oval
}
n_queue: "So'rovlar logi" {
shape: queue
}
n_agg: "Agregatsiya job" {
shape: rectangle
style.multiple: true
}
n_storage: "Snapshot'lar" {
shape: stored_data
}
n_trend: "Trend 5 daqiqa" {
shape: hexagon
}
n_api -> n_index
n_api -> n_index2
n_user -> n_cdn
n_cdn -> n_user {
style.stroke-dash: 3
}
n_cdn -> n_api
n_api -> n_queue: "asinxron"
n_queue -> n_agg
n_agg -> n_storage
n_storage -> n_index
n_storage -> n_index2
n_queue -> n_trend
n_api -> n_trendPlantUML: so'rovlar ketma-ketligi
@startuml
participant "Qidiruv maydoni" as n_user
participant "Suggest API" as n_api
database "So'rovlar bazasi" as n_db
collections "Indeks shard 1" as n_index
participant "CDN edge" as n_cdn
participant "Agregatsiya job" as n_agg
database "Snapshot'lar" as n_storage
collections "Trend 5 daqiqa" as n_trend
queue "So'rovlar logi" as n_queue
note over n_user, n_api : Har bosishga o'nta taklif, keyingi tugmadan oldin
n_user -> n_api : GET /suggest?q=ip&lang=en HTTP/1.1
n_api --> n_user : HTTP/1.1 200 OK
note over n_api, n_db : LIKE 'ip%' o'nta qaytarish uchun millionlab qator o'qiydi
n_api -> n_db : EXPLAIN ANALYZE
n_db --> n_api : Limit (actual time=611.4..611.5 rows=10)
note over n_api, n_index : Har tugunda javobi tayyor turgan trie
n_api -> n_index : lookup prefix="ip"
n_index --> n_api : walk root -> i -> p (2 hops)
note over n_api, n_index : Indeksni prefiks oralig'i bo'yicha shard qilish
n_api -> n_index : shard map v7 (split by traffic, not alphabet)
n_index --> n_api : [a, iq) -> idx-1 heap 29 GB 49% of traffic
note over n_user, n_api : Har bosish bitta so'rov
n_user -> n_api : 18:14:02.110 GET /suggest?q=i
note over n_user, n_cdn : So'rovlarning ko'pi backend'ga yetib bormaydi
n_user -> n_cdn : GET /suggest?q=ip&lang=en HTTP/1.1
n_cdn --> n_user : HTTP/1.1 200 OK
note over n_agg, n_storage : So'rovlar logi keyingi indeksga aylanadi
n_agg -> n_storage : agg output window=2026-11-17T08:00Z/1h
note over n_storage, n_index : Yangi trie ni eskisi yoniga yuklab, bitta ko'rsatkichni almashtirish
n_storage -> n_index : 10:05:12 idx-1 loaded snapshot trie-2026-11-17T09 (29.4 GB, 41 s)
note over n_api, n_trend : Hozir issiq narsalar uchun kichik real vaqt qatlami
n_api -> n_trend : trend.match prefix="st" window=5m
n_trend --> n_api : storm warning 1 812 / 5m x46 vs usual
note over n_queue, n_trend : Hech narsa ko'rsatilishidan oldin filtrlash
n_queue -> n_trend : filter drop "cheap pills now" from trend:en
n_trend --> n_queue : rule blocklist match (spam)
note over n_user, n_cdn : Shaxsiylashtirish keshga tushadi
n_user -> n_cdn : GET /suggest?q=iph&lang=en HTTP/1.1
n_cdn --> n_user : HTTP/1.1 200 OK
@endumlPlantUML: komponentlar
@startuml
left to right direction
agent "Qidiruv maydoni" as n_user
component "Suggest API" as n_api
stack "Indeks shard 1" as n_index
stack "Indeks shard 2" as n_index2
frame "CDN edge" as n_cdn
queue "So'rovlar logi" as n_queue
collections "Agregatsiya job" as n_agg
storage "Snapshot'lar" as n_storage
stack "Trend 5 daqiqa" as n_trend
n_api --> n_index
n_api --> n_index2
n_user --> n_cdn
n_cdn ..> n_user
n_cdn --> n_api
n_api --> n_queue : asinxron
n_queue --> n_agg
n_agg --> n_storage
n_storage --> n_index
n_storage --> n_index2
n_queue --> n_trend
n_api --> n_trend
@endumlXulosa
Autocomplete keyingi bosish bilan poyga: boshidan oxirigacha 100 ms ga yaqin, serverda 20 ms.
1) Qidiruvlarni emas, bosishlarni sanang: o'rtacha 3 500/s, cho'qqida 14 000/s. 2) LIKE 'pre%' tartiblash uchun har mosni o'qiydi; har tugunida top-k saqlangan trie mikrosoniyalarda javob beradi. 3) Trafik bo'yicha kesilgan prefiks oraliqlari bilan shard qiling, replikalar bilan. 4) Debounce, mijoz keshi va qisqa prefikslar uchun CDN yukning ko'pini oladi. 5) Oflayn pipeline so'rovlar logini snapshot'larga aylantiradi, ular atomik almashtiriladi; kichik real vaqt qatlami trendlarni qo'shadi. 6) Blocklist va noyob foydalanuvchilar chegarasi bilan filtrlang; shaxsiylashtirishni faqat kesh baribir yordam bermaydigan joyda qiling.
Ko'rsatkichlar: boshida va oxirida
| Ko'rsatkich | Boshida | Oxirida |
|---|---|---|
| Taklif p95 | 60 ms | 35 ms |
| Backend'ga so'rov | 3 500/s | 3 600/s |
| Yangilik kechikishi | 86 400 s | 60 s |
| Yomon takliflar | 140/kun | 3/kun |
Qadamlar
- Holat Har bosishga o'nta taklif, keyingi tugmadan oldin
Kuniga 25 million qidiruv, har birida o'rtacha 12 ta bosish deylik: kuniga 300 million suggest chaqiruvi, o'rtacha 3 500/s, kechki cho'qqida to'rt baravar ko'p.
- Muammo
LIKE 'ip%'o'nta qaytarish uchun millionlab qator o'qiydiquerydagi B-tree indeksiporalig'i qayerdan boshlanishini topa oladi. - Yechim Har tugunda javobi tayyor turgan trie
Trie (prefiks daraxti) da har prefiksga bitta tugun bor:
i, keyinip, keyiniph. - Yechim Indeksni prefiks oralig'i bo'yicha shard qilish
To'liq trie ga 60 GB ga yaqin kerak, bu bitta jarayon va kechki cho'qqidagi bitta CPU uchun ko'p.
- Muammo Har bosish bitta so'rov
Kechki cho'qqida API 14 000 so'rov/s oladi.
- Yechim So'rovlarning ko'pi backend'ga yetib bormaydi
Uch qatlam, eng arzonidan boshlab.
- Yechim So'rovlar logi keyingi indeksga aylanadi
Foydalanuvchi haqiqatan yuborgan har qidiruv so'rovlar logi oqimiga ketadi, javob kutmasdan.
- Yechim Yangi trie ni eskisi yoniga yuklab, bitta ko'rsatkichni almashtirish
Har shard yangi snapshot'ni bo'sh xotiraga yuklaydi, eskisi bilan xizmat qilishda davom etadi.
- Yechim Hozir issiq narsalar uchun kichik real vaqt qatlami
Ikkinchi iste'molchi o'sha so'rovlar logini o'qiydi va oxirgi besh daqiqa hisobini xotirada saqlaydi.
- Yechim Hech narsa ko'rsatilishidan oldin filtrlash
Takliflar foydalanuvchi oldiga biz qo'yadigan so'zlar, shuning uchun ular har qanday kontent kabi e'tibor talab qiladi.
- Holat Shaxsiylashtirish keshga tushadi
Mahsulot jamoasi foydalanuvchining o'z oldingi qidiruvlarini tepada ko'rmoqchi.
- Xulosa Xulosa
Autocomplete keyingi bosish bilan poyga: boshidan oxirigacha 100 ms ga yaqin, serverda 20 ms.
Atamalar
- Trie (prefiks daraxti)
- Har prefiksga bitta tugun bo'lgan daraxt; qidiruv narxi yozilgan harflar soniga bog'liq, ma'lumot hajmiga emas.
- Top-k
- Eng yaxshi k ta natijaning oldindan hisoblab qo'yilgan ro'yxati, so'rov paytida saralashga hojat qolmaydi.
- Debounce
- Oxirgi hodisadan keyin qisqa pauzani kutib, faqat keyin so'rov yuborish; tez bosishlar bitta so'rovga aylanadi.