U razvoju softvera često se susreću intrigantni izazovi, osobito kada se radi pod strogim ograničenjima resursa i nastoje smanjiti troškove prije nego što MVP dokaže svoju vrijednost.
Povratna geokodiranje
Krajem 2019. godine, zajedno s nekoliko prijatelja, radio sam na razvoju male iOS aplikacije pod nazivomAWAYAplikacija omogućuje korisnicima održavanje popisa zemalja koje su posjetili i dijeljenje s drugima.
Evo kako to funkcionira: ako vaš telefon sadrži fotografije, aplikacija, kada zatraži i prima pristup medijskoj knjižnici, može pročitati širinu i dužinu gdje je svaka fotografija snimljena iz EXIF metapodataka.
Ovaj proces dobivanja adrese (u ovom slučaju, ime zemlje) iz zemljopisnih koordinata zove sereverse geocodingZa upućivanje, obrnuto od ovog procesa - dobivanje zemljopisnih koordinata iz tekstualne adrese - poznat je kao napredna geokodiranje.
rješenja trećih strana
Kada smo razvili naš MVP, počeli smo s najjednostavnijom dostupnom i korištenom opcijom.Appleovo rješenjeAplikacija je djelovala, zemlje su automatski dodane na popis, a mi smo počeli privlačiti naše prve korisnike.
Međutim, ubrzo smo naišli na značajna ograničenja. Appleovo rješenje bilo je vrlo sporo zbog strogih ograničenja stope mrežnih zahtjeva za njegov API, a nije bio dizajniran za serijsku obradu koordinata. Budući da su korisničke medijske knjižnice često sadržavale tisuće fotografija, proces određivanja zemalja bio je izuzetno vremenski zahtjevan, ponekad traje više od 30 minuta.
Takvo dugo čekanje neizbježno je potkopalo viralnost naše aplikacije. Umjesto da odmah dobiju popis posjećene zemlje i dijele ga na Instagramu ili Facebooku, korisnici bi jednostavno otišli bez čekanja na završetak procesa.
Nismo mogli pronaći prikladnije rješenje treće strane.Google,Mapbox, i drugi slični API-ji ili su imali iste probleme kao i Apple - nisu prikladni za obradu partija i ne nude nikakvu prednost uštede vremena - ili bi bili prohibitivno skupi s obzirom na količinu koordinata koje smo trebali nositi.Nominacijabilo bi previše skupo zbog troškova iznajmljivanja odgovarajućeg poslužitelja.
S nedostatkom pristupačnih opcija na raspolaganju, ja sam, odgovoran za backend, počeo graditi vlastiti API.
GeoJSON
Prije ovog projekta, nisam imao iskustva s radom s geospatialnim podacima, pa sam morao naučiti sve dok smo razvili aplikaciju.
Prva stvar koja mi je bila potrebna za provedbu bila je informacija o državnim granicama kako bi se uskladile koordinate.GeoJSON.
GeoJSON je standardna JSON datoteka s specifičnom strukturom koja vam omogućuje opisivanje točaka, linija i oblika proizvoljne složenosti.
Na primjer, pretpostavimo da želimo pohraniti informacije o teritoriju Italije.FeatureGranične granice zemlje bit će opisane unutarMultiPolygonSvaki poligon sastoji se od jednog ili više niza koordinatnih para, gdje prvi i posljednji par koordinata[lon, lat]Oblik opisan u prvom nizu će se dodati na ukupnu zemljopisnu zonu, u ovom slučaju, sama Italija, zajedno s otokom Sardinije (otok će biti opisan u zasebnom poligonu).
Svaki naknadni raspon unutar poligona je neobvezan i predstavlja isključena područja. To će biti potrebno kako bi se isključile teritorije poput gradskih država koje su potpuno okružene Italijom, kao što su San Marino i Vatikan. Koordinacije u tim rasponima moraju biti navedene prema vremenu. Što više točaka navedemo, točnije će biti granice zemlje.
Metapodatci, kao što je ime zemlje, mogu se uključiti u ugrađenipropertiesObjekt je .
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"geometry": {
"type": "MultiPolygon",
"coordinates": [
[ // Polygon
// Exterior ring, Italy
[ [20, 35],[10, 30],[10, 10], ... ,[45, 20],[20, 35]],
// Interior "excluding" ring, San-Marino
[ [30, 20],[20, 15],[20, 25], ... ,[30, 20]]
],
[ // Polygon
// Exterior ring, Sardinia
[ [40, 40],[20, 45], [45, 30], ... ,[40, 40]]
]
]
},
"properties": {
"country": "Italy",
}
}
]
}
Priprema geodeta
Da bih stvorio svjetsku mapu, morao sam izvoriti najtočnije GeoJSON datoteke s koordinatama svih nacionalnih granica, što se pokazalo iznenađujuće izazovnim.
Oslanjao sam se na razne otvorene izvore, uključujući agregirane podatke izOceanografski instituti,Sljedeći članakNpmjs.org, i otvoreni geografski podaci izNominacija, između ostalog. Zajednički problem sa svim podacima koje sam dobio bio je njihov kvalitet. Ponekad su se granice preklapale, osobito u slučajevima političkih sporova između regija. U drugim slučajevima, dostupni su samo podaci koji su uključivali teritorijalne vode, što nije bilo prikladno za naše potrebe. morala sam isključiti te vode oduzimanjem oceanske karte od državnih teritorija (posebno zahvaljujućiFlandrijski pomorski institutPonekad je rezolucija (broj koordinata) bila previše niska za pouzdano geokodiranje, što me zahtijeva da potražim alternative.
Zahtjevi aplikacije bili su prilično zahtjevni: trebali smo precizne, ne preklapajuće granice za svako zemljopisno područje u visokoj rezoluciji bez teritorijalnih voda (za prikaz na karti u aplikaciji), i granice niže rezolucije, uključujući teritorijalne vode (za brže i učinkovitije geokodiranje, posebno za fotografije snimljene na brodovima u blizini obalnih linija - problem koji smo otkrili prilikom rada s rješenjima trećih strana).
Nakon tjedan i pol pažljivog rada, uspio sam stvoriti dvije GeoJSON datoteke visoke rezolucije.countries_maritime.json, opisao granice svih zemalja, uključujući njihove teritorijalne vode, dok je drugi,countries_coastline.jsonSvaka datoteka je bila nekoliko stotina megabajta u veličini, a na kraju sam se osjećao kao da sam osobno posjetio svaki kutak svijeta.
vatra
Kada je lansirana, ažurirana verzija aplikacije prikupila je sve prethodno neobrađene koordinate fotografija iz korisničke medijske knjižnice u serijama od 10.000 i poslala ih u moj backend u višestrukim zahtjevima.
Backend, koji je izgrađen na Node.js-u i smješten na AWS-u, naložio jecountries_maritime.jsonPrilikom inicijaliziranja datoteke u memoriju.Kada je došao zahtjev s skupom koordinata, koristio jePoligonalni pogledknjižnica za usklađivanje koordinata s odgovarajućim područjima iz datoteke, koja je sadržavala 250 zemalja.
Popis koordinata podvrgnut je strogoj validaciji jer su, kako se ispostavilo, neke koordinate bile izvan dopuštenog raspona. Također smo odbacili koordinate s visinama većim od 8.850 metara (malo iznad vrha Everesta) kako bismo izbjegli računanje tipičnih fotografija krila zrakoplova u stilu Instagrama (avioni obično lete na visinama iznad 9.000 metara).
Kada se pronađe utakmica, identifikatora zemlje izpropertyNakon obrade svih koordinata, popis zabilježenih identifikatora je dedupliciran, dodao se na korisnikov popis posjećenih zemalja i vratio klijentu kako bi se aplikacija sinhronizirala s backend bazom podataka.
Nakon prebacivanja na naše prilagođeno rješenje, vrhunacbrzina obrade dosegla 10.000 koordinata u sekundi(u sintetičkim testovima), mediano vrijeme za obradu korisničke medijske knjižnice smanjeno je na 20–25 sekundi (od registracije korisnika do vraćanja popisa posjećenih zemalja), aProsječan broj dodanih zemalja porastao je za 225% po korisnikuZbog preciznijeg geokodiranja.
Geodata administracija
Kako je aplikacija nastavila rasti, korisnici su počeli podnositi zahtjeve za značajke.Jedan od najčešćih zahtjeva bio je dodavanje automatskog prepoznavanja za regije i glavne gradove unutar svake zemlje.
Prikupljanje visokokvalitetnih podataka za granice 250 zemalja već je bilo teško.
Da bih to riješio, prenio sam teritorije iz JSON datoteke u tablicu Postgres i razvio administrativni sučelje za upravljanje geografskim zonama.Dodatno, integrirao sam admin panel s nekoliko vanjskih API-ja kako bih automatizirao stvaranje lista za regije i gradove na temelju njihovih matičnih zemalja.
Prvi problem s kojim sam se susreo bio je inherentna složenost podataka o zemljopisnim regijama.Ne postoji univerzalno jasna razlika između regija i gradova, a različite zemlje imaju različite razine administrativnih podjela.Sljedeći članakApi.de, koristeći uvjete i recursivne pozive za filtriranje po administrativnim centrima, veličini stanovništva i unutarnjim odnosima.To je također uključivalo proučavanje kako podijeliti i organizirati geografske čvorove, njihove odnose i nestane strukture, te ispravljanje nekih pogrešnih podataka.
Drugi izazov nastao je kada sam radio s koordinatnim izvorima za regionalne granice. Nakon preuzimanja lista osmId za regije i gradove, morao sam izvući geometrijske granice njihovih granica.Sljedeći članakOpenstreetmap.orgGotovo u potpunosti nedokumentiraniSljedeći članakOpenstreetmap.frTi su izvori bili nepotpuni, tako da sam morao poslati više zahtjeva i usporediti njihove rezultate, odabirom najboljeg odgovora na temelju kvalitete vraćenih podataka.
Unatoč nedostatku dokumentacije, složenim odnosima podataka i nedosljednostima u izvorima, uspio sam stvoriti stabilno rješenje.Admin panel sučelje sada omogućuje automatsko učitavanje lista gradova i regija za bilo koju zemlju s samo nekoliko klikova, uključujući njihove metapodatke i najbolje dostupne granične geometrije.
Kako bi se riješili česti problemi s podacima GeoJSON-a, razvio sam čak i ugrađeni uređač koji omogućuje razdvajanje, spajanje, oduzimanje i crtanje manjkajućih granica.
Svi ti alati omogućili su nam, s timom od samo dvije osobe, stvaranje baze podataka regija i gradova koje smo bili ponosni predstaviti korisnicima u roku od mjesec i pol.
Trenutno, aplikacija podržava 3.134 regije i 28.083 gradova, svaki s preciznim granicama, i prati broj korisnika koji su ih posjetili.
Minimiziranje geodeta
Rješavanje 31.467 teritorija s Node.js-om postalo je nemoguće zbog ograničenja performansi i resursa već u koraku inicijaliziranja indeksa.
Kao što sam ranije spomenuo, podaci potrebni za prikaz aplikacija i geokodiranje imali su vrlo različite zahtjeve: dok je priprema kartografskih pločica za renderiranje u aplikaciji mogla priuštiti da traje nekoliko minuta, geokodiranje je bilo vrlo osjetljivo na volumene podataka, s brzinom koja je izravno vezana za broj koordinata u teritorijalnim granicama.
Eksperimentirao sam s nekoliko algoritama kako bih pojednostavio koordinatne lance poligona.
Prvi pristup bio jeRamer Douglas PeuckerNjegova je približavanja bila nestabilna, što je dovelo do neusklađenosti u zajedničkim granicama između različitih GeoJSON datoteka, a također je uzrokovalo gubitak manjih detalja, poput otoka.
U konačnici,I developed my own implementation(izdana kao npm paket) na temeljuSljedeći članakWhyattPostojeće implementacije ovog algoritma mogle bi se primijeniti samo na određene dijelove strukture GeoJSON-a, što je riješilo problem stabilnosti rezultata, ali i dalje je uzrokovalo značajnu degradaciju granica i gubitak malih detalja.lijepo(s kutom između tri susjedne koordinate kao element gomile) i obrađivao ga kao jednu krivulju s dodatnom logikom za očuvanje zajedničkih točaka.
Razvijala sam vlastitu implementacijuOsim smanjenja volumena podataka, ova restrukturiranje GeoJSON datoteka pomoglo je otkriti brojne pogreške i sukobe unutar podataka:
- Nezavršene koordinatne arete.
- Konfliktne serije zbog nepravilnog uklanjanja koordinata.
- Prazne koordinatne arete.
- Prekomjerno gniježenje
- Nepotrebna preciznost u koordinatama.
Uspješno sam automatizirao validaciju i ispravljanje tih pogrešaka, djelomično koristeći postojeće alate kao što su:Poligonalno rezanje,@mapbox / geojsonhint,@mapbox / geojson-rewind,i @mapbox/geojson-extentTo je uključivalo spajanje zasebnih poligona u multipoligone i zbirke geometrije, smanjenje rezolucije koordinata na potrebnu razinu, ispravljanje smjera koordinata i uklanjanje praznih niza.
Kao rezultat toga, postigao sam značajno poboljšanje u učinkovitosti obrade zemljopisnih podataka.Osim toga, stabilnost mog algoritma riješila je problem neusklađenih pojednostavljenih granica između susjednih regija na karti.
Posjetite Microservice
Unatoč smanjenju računalnog opterećenja kroz pojednostavljenje geodata, postalo je jasno da Node.js definitivno nije idealno rješenje za naše potrebe.PoštarNakon opsežnih istraživanja, uključujući mjerenja performansi i potrošnje resursa, odlučio sam se za potonju – jednostavnu mikroslužbu izgrađenu s Go-om.
Arhitektura mikroslužbi osmišljena je kako bi se povećala brzina obrade koordinatnog para, a istodobno se smanjile nepotrebne operacije.
Nakon prvog pokretanja, mikroslužba se povezuje s PostgreSQL-om i preuzima sve relevantne GeoJSON podatke u serije od 100 objekata. Ti se podaci razvrstavaju u strukture, od kojih svaki sadrži poligon i odgovarajući teritorijalni identifikator.
Nakon što je uspostavljena struktura array, aR-drvoOva vrsta stabla često se koristi za stvaranje indeksa za pretraživanje multidimenzionalnih podataka, kao što su poligoni. stablo omogućuje logaritamsko pretraživanje za najmanji granični pravokut koji uključuje ciljni poligon.
Nakon što je stablo izgrađeno, mikroslužba ulazi u stanje slušanja, čekajući dolazne zahtjeve.
Kada je primljen zahtjev, koji se sastoji od parova koordinata[lat, lon]Multithreaded obrada je pokrenuta. Rezultat je niz jedinstvenih identifikatora teritorija koji sadrže navedene koordinate.
Svaka koordinata prvo podliježe pretraživanju kroz R-drvo. Ovo pretraživanje može vratiti pravokut koji sadrži poligon, koji bi potencijalno mogao uključivati koordinatu.Ray-casting algoritamOvaj algoritam djeluje u linearnom vremenu, čineći ga najintenzivnijim dijelom procesa. Međutim, prije nego što izvršim kontrolu radijacije, provjeravam je li identifikator teritorija za poligon već pronađen tijekom obrade drugih koordinata u zahtjevu.
Nakon što sve žice završe svoj rad, niz identifikatora vraća se u Node.js sloj. Ispod sam pokušao predstaviti arhitekturu u sljedećem diagramu:
Cijeli proces pretraživanja, osim specifične optimizacije za preskakanje ponavljanih provjera ray-castinga, detaljno odražava kako PostGIS rješava sličan zadatak kada koristipokloniIndeksi su.
Korištenje API-ja izgrađenog oko Go mikroslužbe,Postigli smo sposobnost obrade oko 100.000 parova koordinata u sekundiU usporedbi, prethodno rješenje Node.js upravljalo je oko 10.000 parova koordinata za 250 zona, uključujući nadglavlje mrežnih zahtjeva i operacija backend.
Ovo značajno poboljšanje brzine obrade omogućilo je mnogo brže sastavljanje popisa posjećenih zemalja korisnika.aplikacija je vidjela 160% povećanje aktivnih korisnika i 107% povećanje dijeljenja korisnikaNjihovi rezultati
Rješenje ostaje u upotrebi i danas i nastavlja učinkovito rješavati sve veći volumen zahtjeva i geografskih zona.Naravno, cijeli backend radi s manje od gigabajta RAM-a, pokazujući optimizirano korištenje resursa.
