mufassall

Konspekt · Ma'lumot va saqlash

Geo qidiruv: kim yaqinda

14 daq · O'rta · mufassall.dtwin.uz/uz/l/geo-search/

← Darsni ochish

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
Yakuniy sahna
70%40%10%40%

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_geo2

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

D2

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_geo2

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

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

Xulosa

"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'rsatkichBoshidaOxirida
Qidiruv p95900 ms35 ms
O'qilgan haydovchi50 0001 200
Eng yaqini o'tkazildi0%0%
Arvoh haydovchilar00

Qadamlar

  1. Muammo Masofa har bir haydovchi uchun hisoblanadi

    Yo'lovchi ilovani ochib, mashina chaqiradi.

  2. Muammo Kenglik bo'yicha indeks tasmani o'qiydi

    Keyingi fikr: chegaralovchi to'rtburchak, ya'ni kenglik va uzunlik ±2 km ichida, lat ustida indeks bilan.

  3. Yechim Geohash: ikki koordinata bitta kalitga

    Geohash dunyoni qayta-qayta to'rga bo'ladi va yo'lni qisqa satr qilib yozadi.

  4. Muammo Eng yaqin haydovchi chegaraning narigi tomonida

    Yo'lovchi o'z katakchasining sharqiy chegarasidan 40 m narida turibdi.

  5. Yechim Katakcha va uning 8 qo'shnisini o'qish

    Geo indeks markaz va radiusni oladi.

  6. Holat Soniyasiga 12 500 joylashuv yangilanishi

    Har haydovchi ilovasi har 4 soniyada joylashuvini yuboradi: soniyasiga 12 500 yozuv.

  7. Yechim Jim bo'lib qolgan haydovchilarni olib tashlash

    Joylashuvlar yonida indeks har haydovchidan oxirgi marta qachon xabar kelganini saqlaydi.

  8. Muammo Juma kechqurun shahar markazida

    Juma soat 18:30 da bitta markaziy katakchada 3 100 haydovchi kutadi, atrofida esa soniyasiga 900 yo'lovchi qidiradi.

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

  10. Holat S2 va H3 katakchalari va katakcha bo'yicha sharding

    Kutubxonalar xuddi shuni sfera ustida qiladi.

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