Konspekt · Ma'lumot va saqlash
Geo qidiruv: kim yaqinda
Muammo
Taksi ilovasi yo'lovchi atrofidagi eng yaqin o'nta bo'sh haydovchini topishi kerak, 50 000 haydovchi esa har 4 soniyada joylashuvini yuboradi. Oddiy indeks nega yordam bermaydi va geohash, qo'shni katakchalar, quadtree hamda S2/H3 katakchalari "2 km ichida kim bor" savoliga millisoniyalarda qanday javob beradi.
Nimani o'rganasiz
- Kenglik va uzunlik bo'yicha B-tree nega baribir butun shahar bo'ylab tasmani o'qiydi
- Geohash: yaqin nuqtalarning prefiksi umumiy, shuning uchun katakcha bitta kalitga aylanadi
- Katakcha chetlari: doim qo'shnilarni ham o'qing, keyin aniq masofa bo'yicha saralang
- Zich markazdagi qizg'in katakchalar: quadtree bo'linishi, S2 va H3, katakcha bo'yicha sharding
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_rider(["Yo'lovchi ilovasi"])
n_drivers(["Haydovchi ilovalari"])
n_api["Moslash API"]
n_db[("Haydovchilar bazasi")]
n_geo{{"Geo indeks"}}
n_geo2{{"Geo indeks 2"}}
n_rider --> n_api
n_drivers --> n_api
n_api --> n_geo
n_api --> n_geo
n_api --> n_geo2Mermaid: so'rovlar ketma-ketligi
sequenceDiagram
participant n_api as Moslash API
participant n_db as Haydovchilar bazasi
participant n_geo as Geo indeks
participant n_drivers as Haydovchi ilovalari
participant n_geo2 as Geo indeks 2
Note over n_api,n_db: Masofa har bir haydovchi uchun hisoblanadi
n_api->>n_db: SELECT id, lat, lng FROM drivers
n_db-->>n_api: 10 rows, Seq Scan on drivers
Note over n_api,n_db: Kenglik bo'yicha indeks tasmani o'qiydi
n_api->>n_db: CREATE INDEX drivers_lat ON drivers (lat)#59;
n_db-->>n_api: Index Scan using drivers_lat
Note over n_api,n_geo: Geohash: ikki koordinata bitta kalitga
n_api->>n_geo: geohash(41.3110, 69.2797) = tz6x9q
Note over n_api,n_geo: Eng yaqin haydovchi chegaraning narigi tomonida
n_api->>n_geo: rider at tz6x9q, 40 m from its east border
Note over n_api,n_geo: Katakcha va uning 8 qo'shnisini o'qish
n_api->>n_geo: GEOSEARCH drivers FROMLONLAT 69.2797 41.3110 BYRADIUS 2 km ASC COUNT 10
n_geo-->>n_api: 1) d_7730 0.12 km
Note over n_drivers,n_api: Soniyasiga 12 500 joylashuv yangilanishi
n_drivers->>n_api: POST /v1/drivers/d_1842/location HTTP/1.1
n_api-->>n_drivers: GEOADD drivers 69.2810 41.3121 d_1842
Note over n_api,n_geo: Jim bo'lib qolgan haydovchilarni olib tashlash
n_api->>n_geo: ZADD drivers:seen 1795543324 d_1842
Note over n_api,n_geo: Juma kechqurun shahar markazida
n_api->>n_geo: 18:30 Friday, city centre
Note over n_api,n_geo: Quadtree: katakchalar zichlikka ergashadi
n_api->>n_geo: quadtree: split a square into 4 when it holds #62; 200 drivers
Note over n_api,n_geo2: S2 va H3 katakchalari va katakcha bo'yicha sharding
n_api->>n_geo2: cover circle(41.3110, 69.2797, 2 km) with H3 res 8D2
direction: right
n_rider: "Yo'lovchi ilovasi" {
shape: rectangle
}
n_drivers: "Haydovchi ilovalari" {
shape: rectangle
}
n_api: "Moslash API" {
shape: rectangle
}
n_db: "Haydovchilar bazasi" {
shape: cylinder
}
n_geo: "Geo indeks" {
shape: hexagon
}
n_geo2: "Geo indeks 2" {
shape: hexagon
}
n_rider -> n_api
n_drivers -> n_api
n_api -> n_geo
n_api -> n_geo
n_api -> n_geo2PlantUML: so'rovlar ketma-ketligi
@startuml
participant "Moslash API" as n_api
database "Haydovchilar bazasi" as n_db
collections "Geo indeks" as n_geo
participant "Haydovchi ilovalari" as n_drivers
collections "Geo indeks 2" as n_geo2
note over n_api, n_db : Masofa har bir haydovchi uchun hisoblanadi
n_api -> n_db : SELECT id, lat, lng FROM drivers
n_db --> n_api : 10 rows, Seq Scan on drivers
note over n_api, n_db : Kenglik bo'yicha indeks tasmani o'qiydi
n_api -> n_db : CREATE INDEX drivers_lat ON drivers (lat);
n_db --> n_api : Index Scan using drivers_lat
note over n_api, n_geo : Geohash: ikki koordinata bitta kalitga
n_api -> n_geo : geohash(41.3110, 69.2797) = tz6x9q
note over n_api, n_geo : Eng yaqin haydovchi chegaraning narigi tomonida
n_api -> n_geo : rider at tz6x9q, 40 m from its east border
note over n_api, n_geo : Katakcha va uning 8 qo'shnisini o'qish
n_api -> n_geo : GEOSEARCH drivers FROMLONLAT 69.2797 41.3110 BYRADIUS 2 km ASC COUNT 10
n_geo --> n_api : 1) d_7730 0.12 km
note over n_drivers, n_api : Soniyasiga 12 500 joylashuv yangilanishi
n_drivers -> n_api : POST /v1/drivers/d_1842/location HTTP/1.1
n_api --> n_drivers : GEOADD drivers 69.2810 41.3121 d_1842
note over n_api, n_geo : Jim bo'lib qolgan haydovchilarni olib tashlash
n_api -> n_geo : ZADD drivers:seen 1795543324 d_1842
note over n_api, n_geo : Juma kechqurun shahar markazida
n_api -> n_geo : 18:30 Friday, city centre
note over n_api, n_geo : Quadtree: katakchalar zichlikka ergashadi
n_api -> n_geo : quadtree: split a square into 4 when it holds > 200 drivers
note over n_api, n_geo2 : S2 va H3 katakchalari va katakcha bo'yicha sharding
n_api -> n_geo2 : cover circle(41.3110, 69.2797, 2 km) with H3 res 8
@endumlPlantUML: komponentlar
@startuml
left to right direction
agent "Yo'lovchi ilovasi" as n_rider
agent "Haydovchi ilovalari" as n_drivers
component "Moslash API" as n_api
database "Haydovchilar bazasi" as n_db
stack "Geo indeks" as n_geo
stack "Geo indeks 2" as n_geo2
n_rider --> n_api
n_drivers --> n_api
n_api --> n_geo
n_api --> n_geo
n_api --> n_geo2
@endumlXulosa
"Kim yaqinda" uchun beshta qoida.
1) lat yoki lng ustidagi oddiy indeks tasmani o'qiydi; joylashuvni katakcha kalitiga aylantiring (geohash, S2, H3). 2) Doim katakcha va qo'shnilarini o'qing, keyin aniq masofa bo'yicha saralang. 3) Tez o'zgaradigan joylashuvlarni xotirada saqlang va jim qolgan haydovchilarni muddati bilan o'chiring. 4) Katakchalar zichlikka ergashsin: quadtree yoki bir necha daraja. 5) Yirik katakcha bo'yicha sharding qiling va qizg'in hududlarga alohida shard bering.
Ko'rsatkichlar: boshida va oxirida
| Ko'rsatkich | Boshida | Oxirida |
|---|---|---|
| Qidiruv p95 | 900 ms | 35 ms |
| O'qilgan haydovchi | 50 000 | 1 200 |
| Eng yaqini o'tkazildi | 0% | 0% |
| Arvoh haydovchilar | 0 | 0 |
Qadamlar
- Muammo Masofa har bir haydovchi uchun hisoblanadi
Yo'lovchi ilovani ochib, mashina chaqiradi.
- Muammo Kenglik bo'yicha indeks tasmani o'qiydi
Keyingi fikr: chegaralovchi to'rtburchak, ya'ni kenglik va uzunlik ±2 km ichida,
latustida indeks bilan. - Yechim Geohash: ikki koordinata bitta kalitga
Geohash dunyoni qayta-qayta to'rga bo'ladi va yo'lni qisqa satr qilib yozadi.
- Muammo Eng yaqin haydovchi chegaraning narigi tomonida
Yo'lovchi o'z katakchasining sharqiy chegarasidan 40 m narida turibdi.
- Yechim Katakcha va uning 8 qo'shnisini o'qish
Geo indeks markaz va radiusni oladi.
- Holat Soniyasiga 12 500 joylashuv yangilanishi
Har haydovchi ilovasi har 4 soniyada joylashuvini yuboradi: soniyasiga 12 500 yozuv.
- Yechim Jim bo'lib qolgan haydovchilarni olib tashlash
Joylashuvlar yonida indeks har haydovchidan oxirgi marta qachon xabar kelganini saqlaydi.
- Muammo Juma kechqurun shahar markazida
Juma soat 18:30 da bitta markaziy katakchada 3 100 haydovchi kutadi, atrofida esa soniyasiga 900 yo'lovchi qidiradi.
- Yechim Quadtree: katakchalar zichlikka ergashadi
Quadtree butun shahar uchun bitta kvadratdan boshlanadi va kvadratda 200 dan ortiq haydovchi bo'lishi bilan uni to'rtga bo'ladi.
- Holat S2 va H3 katakchalari va katakcha bo'yicha sharding
Kutubxonalar xuddi shuni sfera ustida qiladi.
- Xulosa Xulosa
"Kim yaqinda" uchun beshta qoida.
Atamalar
- Geohash
- Kenglik va uzunlikni bitta qisqa satrga aylantirish: umumiy prefiksi uzun nuqtalar odatda yaqin turadi. Yaqin atrofni qidirishda kerakli katak va uning 8 qo'shnisi so'raladi, chunki yaqin nuqta chegaraning narigi tomonida bo'lishi mumkin.
- Quadtree
- Xaritani to'rtta kvadratga, to'lib qolgan kvadratni yana to'rttaga bo'ladigan daraxt. Shahar markazida kataklar mayda, cho'lda yirik bo'ladi, shuning uchun har katakda nuqtalar soni taxminan teng qoladi.