Konspekt · Ma'lumot va saqlash
Matn bo'yicha qidiruv (full-text search)
Muammo
Marketpleys katalogni `LIKE '%so'z%'` bilan qidiradi. 4 million mahsulotda har bir qidiruv jadvalning har bir qatorini o'qiydi, shunga qaramay boshqa apostrof bilan, kirillda yoki o'zbekcha qo'shimcha bilan yozilgan mahsulotlarni topa olmaydi. Haqiqiy matn qidiruvini bosqichma-bosqich quramiz: tahlil qilingan tokenlar ustidagi teskari indeks, BM25 reytingi, bazaning o'zgarishlar log'iga ergashadigan indeks, scatter-gather bilan shard'lar va xatoga chidamli qidiruv.
Nimani o'rganasiz
- Nega
LIKE '%x%'indeksdan foydalana olmaydi va butun jadvalni o'qiydi - Tahlil (analyzer): kichik harf, kirilldan lotinga, o'zbekcha apostroflar va qo'shimchalar, indekslashda ham, so'rovda ham bitta analyzer
- Postings ro'yxatli teskari indeks va BM25 reytingi aniq raqamlarda
- Indeksni o'zgarishlar log'i orqali yangi saqlash, hujjat bo'yicha sharding, scatter-gather va xatolarga chidamlilik
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(["Do'kon ilovasi"])
n_api["Qidiruv API"]
n_db[("Mahsulotlar bazasi")]
n_catalog["Katalog servisi"]
n_indexer("Indekser")
n_log[["O'zgarishlar log'i"]]
n_shard1[("Indeks shard 1")]
n_shard2[("Indeks shard 2")]
n_user -->|"chaqiruv"| n_api
n_catalog --> n_db
n_db -->|"asinxron"| n_log
n_indexer --> n_log
n_api --> n_shard1
n_api --> n_shard2
n_indexer --> n_shard1
n_indexer --> n_shard2Mermaid: so'rovlar ketma-ketligi
sequenceDiagram
participant n_api as Qidiruv API
participant n_db as Mahsulotlar bazasi
participant n_index as Qidiruv indeksi
participant n_user as Do'kon ilovasi
participant n_indexer as Indekser
participant n_log as O'zgarishlar log'i
participant n_shard2 as Indeks shard 2
Note over n_api,n_db: Katalog kichikligida LIKE bilan qidirish
n_api->>n_db: SELECT id, title, price_minor FROM products
Note over n_api,n_db: 4 million mahsulot: har qidiruv jadvalni o'qiydi
n_api->>n_db: EXPLAIN ANALYZE SELECT ... WHERE lower(title #124;#124; ' ' #124;#124; description) LIKE '%choynak%'#59;
n_db-->>n_api: Seq Scan on products (rows removed by filter: 3 998 160)
Note over n_api,n_index: Teskarisiga o'gir: so'zdan mahsulotlarga
n_api->>n_index: term df postings (doc id: positions)
Note over n_user,n_api: Bitta so'z, to'rt xil yozilgan
n_user->>n_api: sellers wrote #34;g'ilof#34; (phone case) in 4 ways, 2 170 products
Note over n_indexer,n_index: So'z nima ekanini bir marta, ikkala tomon uchun hal qil
n_indexer->>n_index: analyze(#34;Telefon GʻILOFLARI, qora#34;)
Note over n_api,n_index: Sotuv bo'yicha emas, mosligi bo'yicha sarala
n_api->>n_index: query #34;elektr choynak#34; N = 4 000 000 avgdl = 12
Note over n_indexer,n_db: Yangi mahsulot ertagacha ko'rinmaydi
n_indexer->>n_db: 10:12 seller adds #34;Elektr choynak 2 l#34; id 4120551 -#62; Products DB ok
Note over n_indexer,n_log: Indeksni bazaning o'zgarishlar log'idan ozuqlantir
n_indexer->>n_log: cdc products op=u id=4120551 lsn 0/7A3F10
Note over n_api,n_shard2: Hujjat bo'yicha bo'l, har bir shard'dan so'ra
n_api->>n_shard2: search q=#34;elektr choynak#34; size=10 -#62; both shards
Note over n_user,n_api: Xaridor #34;choyank#34; yozsa ham #34;choynak#34; ni top
n_user->>n_api: POST /v1/search HTTP/1.1
n_api-->>n_user: HTTP/1.1 200 OKD2
direction: right
n_user: "Do'kon ilovasi" {
shape: rectangle
}
n_api: "Qidiruv API" {
shape: rectangle
}
n_db: "Mahsulotlar bazasi" {
shape: cylinder
}
n_catalog: "Katalog servisi" {
shape: rectangle
}
n_indexer: "Indekser" {
shape: rectangle
style.multiple: true
}
n_log: "O'zgarishlar log'i" {
shape: queue
}
n_shard1: "Indeks shard 1" {
shape: cylinder
}
n_shard2: "Indeks shard 2" {
shape: cylinder
}
n_user -> n_api: "chaqiruv"
n_catalog -> n_db
n_db -> n_log: "asinxron"
n_indexer -> n_log
n_api -> n_shard1
n_api -> n_shard2
n_indexer -> n_shard1
n_indexer -> n_shard2PlantUML: so'rovlar ketma-ketligi
@startuml
participant "Qidiruv API" as n_api
database "Mahsulotlar bazasi" as n_db
database "Qidiruv indeksi" as n_index
participant "Do'kon ilovasi" as n_user
participant "Indekser" as n_indexer
queue "O'zgarishlar log'i" as n_log
database "Indeks shard 2" as n_shard2
note over n_api, n_db : Katalog kichikligida LIKE bilan qidirish
n_api -> n_db : SELECT id, title, price_minor FROM products
note over n_api, n_db : 4 million mahsulot: har qidiruv jadvalni o'qiydi
n_api -> n_db : EXPLAIN ANALYZE SELECT ... WHERE lower(title || ' ' || description) LIKE '%choynak%';
n_db --> n_api : Seq Scan on products (rows removed by filter: 3 998 160)
note over n_api, n_index : Teskarisiga o'gir: so'zdan mahsulotlarga
n_api -> n_index : term df postings (doc id: positions)
note over n_user, n_api : Bitta so'z, to'rt xil yozilgan
n_user -> n_api : sellers wrote "g'ilof" (phone case) in 4 ways, 2 170 products
note over n_indexer, n_index : So'z nima ekanini bir marta, ikkala tomon uchun hal qil
n_indexer -> n_index : analyze("Telefon GʻILOFLARI, qora")
note over n_api, n_index : Sotuv bo'yicha emas, mosligi bo'yicha sarala
n_api -> n_index : query "elektr choynak" N = 4 000 000 avgdl = 12
note over n_indexer, n_db : Yangi mahsulot ertagacha ko'rinmaydi
n_indexer -> n_db : 10:12 seller adds "Elektr choynak 2 l" id 4120551 -> Products DB ok
note over n_indexer, n_log : Indeksni bazaning o'zgarishlar log'idan ozuqlantir
n_indexer -> n_log : cdc products op=u id=4120551 lsn 0/7A3F10
note over n_api, n_shard2 : Hujjat bo'yicha bo'l, har bir shard'dan so'ra
n_api -> n_shard2 : search q="elektr choynak" size=10 -> both shards
note over n_user, n_api : Xaridor "choyank" yozsa ham "choynak" ni top
n_user -> n_api : POST /v1/search HTTP/1.1
n_api --> n_user : HTTP/1.1 200 OK
@endumlPlantUML: komponentlar
@startuml
left to right direction
agent "Do'kon ilovasi" as n_user
component "Qidiruv API" as n_api
database "Mahsulotlar bazasi" as n_db
component "Katalog servisi" as n_catalog
collections "Indekser" as n_indexer
queue "O'zgarishlar log'i" as n_log
database "Indeks shard 1" as n_shard1
database "Indeks shard 2" as n_shard2
n_user --> n_api : chaqiruv
n_catalog --> n_db
n_db --> n_log : asinxron
n_indexer --> n_log
n_api --> n_shard1
n_api --> n_shard2
n_indexer --> n_shard1
n_indexer --> n_shard2
@endumlXulosa
Matn qidiruvining oltita qoidasi.
1) LIKE '%x%' har bir qatorni o'qiydi; kichik jadvaldan kattasiga yaramaydi. 2) So'z nima ekanini mahsulot ham, so'rov ham uchun bitta analyzer bilan hal qil: kichik harf, bitta alifbo, apostrof variantlarisiz, ehtiyotkor stemmer. 3) Teskari indeks so'zlarni saralangan postings'ga bog'laydi; qidiruv faqat shu ro'yxatlarni o'qiydi. 4) BM25 bilan sarala: kamyoblik hisobga olinadi, takrorlar to'yinadi, uzun matnlar chegirma oladi. 5) Indeksni bazaning o'zgarishlar log'idan ozuqlantir va near-real-time'ni qabul qil; narx va qoldiq bazadan qayta o'qiladi. 6) Hujjat bo'yicha shard qil, scatter-gather ishlat va xatolarga qat'iy cheklovlar bilan chidamli bo'l.
Ko'rsatkichlar: boshida va oxirida
| Ko'rsatkich | Boshida | Oxirida |
|---|---|---|
| Qidiruv p95 | 45 ms | 24 ms |
| Har qidiruvda o'qilgan qatorlar | 50 000 | 21 000 |
| Topilmagan kerakli mahsulotlar | 37% | 6% |
| Natijasiz qidiruvlar | 3% | 2% |
| Yozuvdan qidiruvgacha | 0 s | 2 s |
Qadamlar
- Holat Katalog kichikligida LIKE bilan qidirish
Sotuvchilar mahsulotni katalog servisi orqali qo'shadi, xaridorlar qidiruv qatoriga so'z yozadi.
- Muammo 4 million mahsulot: har qidiruv jadvalni o'qiydi
Uch yildan keyin katalogda 4 million mahsulot va 1.2 GB matn bor.
- Yechim Teskarisiga o'gir: so'zdan mahsulotlarga
Teskari indeks (inverted index) har bir so'z uchun shu so'z uchraydigan mahsulotlar ro'yxatini saqlaydi: uning postings'ini.
- Muammo Bitta so'z, to'rt xil yozilgan
Tez, lekin kerakli mahsulotlarning uchdan biri hali ham topilmaydi.
- Yechim So'z nima ekanini bir marta, ikkala tomon uchun hal qil
So'z indeksga tushishidan oldin analyzer uni bir xil ko'rinishga keltiradi: kichik harf, kirilldan lotinga, apostrofning hamma variantlari olib tashlanadi, tokenlarga bo'linadi, qisqa ro'yxatdagi qo'shimchalar kesiladi.
- Yechim Sotuv bo'yicha emas, mosligi bo'yicha sarala
Endi "elektr choynak" ga 1 840 ta mahsulot mos keladi va tartib muhim.
- Muammo Yangi mahsulot ertagacha ko'rinmaydi
Indeks har kecha qaytadan quriladi.
- Yechim Indeksni bazaning o'zgarishlar log'idan ozuqlantir
Mahsulotlar jadvalidagi har bir commit bo'lgan o'zgarish CDC yoki outbox orqali o'zgarishlar log'iga tushadi.
- Yechim Hujjat bo'yicha bo'l, har bir shard'dan so'ra
Tavsiflar va pozitsiyalar bilan indeks 38 GB ga yetadi va bitta node xotirasiga sig'maydi: gavjum paytda p95 sekin-asta o'sadi.
- Yechim Xaridor "choyank" yozsa ham "choynak" ni top
Qidiruvlarning 2% i hali ham hech narsa topmaydi, asosan yozuv xatolari tufayli.
- Xulosa Xulosa
Matn qidiruvining oltita qoidasi.
Atamalar
- Teskari indeks (inverted index)
- Har bir so'z uchun shu so'z uchraydigan hujjatlarning saralangan ro'yxatini (postings) saqlaydigan indeks. Qidiruv hujjatlarni emas, faqat so'rovdagi so'zlarning ro'yxatlarini o'qiydi va kesishtiradi.
- Analyzer (matn tahlilchisi)
- Matnni indeks tokenlariga aylantiradigan qadamlar zanjiri: kichik harf, bitta alifbo, apostrof variantlarini olib tashlash, tokenlarga bo'lish, stemming. Aynan o'sha analyzer so'rovga ham qo'llanishi shart.
- BM25
- Matn qidiruvining standart reyting formulasi. Kam uchraydigan so'zlar og'irroq (idf), takrorlar foyda beradi, lekin to'yinadi (k1), uzun matnlar chegirma oladi (b).
- Near-real-time indeks
- Yangi yozuvlar darhol emas, keyingi refresh'da, odatda soniyada bir marta qidiruvga ochiladigan indeks. Refresh qanchalik tez-tez bo'lsa, birlashtirish kerak bo'lgan mayda segmentlar shunchalik ko'p.
- Scatter-gather
- So'rov hamma shard'larga yuboriladi, har biri o'zining top-k natijasini qaytaradi, koordinator esa ularni bitta ro'yxatga birlashtiradi. Javob eng sekin shard qancha ishlasa, shuncha vaqt oladi.