mufassall

Konspekt · Butun tizimlar

Qidiruv takliflari (autocomplete) dizayni

13 daq · O'rta · mufassall.dtwin.uz/uz/l/design-search-autocomplete/

← Darsni ochish

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
Yakuniy sahna
35%40%50%20%30%50%50%

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_trend

Mermaid: 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 OK

D2

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_trend

PlantUML: 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
@enduml

PlantUML: 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
@enduml

Xulosa

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'rsatkichBoshidaOxirida
Taklif p9560 ms35 ms
Backend'ga so'rov3 500/s3 600/s
Yangilik kechikishi86 400 s60 s
Yomon takliflar140/kun3/kun

Qadamlar

  1. 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.

  2. Muammo LIKE 'ip%' o'nta qaytarish uchun millionlab qator o'qiydi

    query dagi B-tree indeks ip oralig'i qayerdan boshlanishini topa oladi.

  3. Yechim Har tugunda javobi tayyor turgan trie

    Trie (prefiks daraxti) da har prefiksga bitta tugun bor: i, keyin ip, keyin iph.

  4. 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.

  5. Muammo Har bosish bitta so'rov

    Kechki cho'qqida API 14 000 so'rov/s oladi.

  6. Yechim So'rovlarning ko'pi backend'ga yetib bormaydi

    Uch qatlam, eng arzonidan boshlab.

  7. Yechim So'rovlar logi keyingi indeksga aylanadi

    Foydalanuvchi haqiqatan yuborgan har qidiruv so'rovlar logi oqimiga ketadi, javob kutmasdan.

  8. 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.

  9. 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.

  10. 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.

  11. Holat Shaxsiylashtirish keshga tushadi

    Mahsulot jamoasi foydalanuvchining o'z oldingi qidiruvlarini tepada ko'rmoqchi.

  12. 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.