У развоју софтвера, често се суочавамо са занимљивим изазовима, посебно када радимо под строгим ограничењима ресурса и настојимо да минимизирамо трошкове пре него што МВП докаже своју вредност.
Повратак геокодирања
Крајем 2019. године, заједно са пар пријатеља, радио сам на развоју мале иОС апликације под називомAWAYАпликација омогућава корисницима да одржавају листу земаља које су посетили и делите је са другима.
Ево како то функционише: ако ваш телефон садржи фотографије, апликација, када затражи и прима приступ медијској библиотеци, може прочитати ширину и дужину где је свака фотографија снимљена из ЕКСИФ метаподатака.
Овај процес добијања адресе (у овом случају, назив земље) из географских координата се називаreverse geocodingЗа референцу, обрнуто од овог процеса - добијање географских координата из текстуалне адресе - познато је као напредно геокодирање.
Rešenja treće strane
Приликом развијања нашег МВП-а, почели смо са најједноставнијом опцијом која је доступна и коришћенаApple-ovo default rešenjeАпликација је радила, земље су аутоматски додате на листу, и почели смо да привлачимо наше прве кориснике.
Међутим, убрзо смо наишли на значајна ограничења. Аппле-ово решење је било веома споро због строгих лимита на захтеве мреже за његов АПИ, и није било дизајнирано за серијску обраду координата. Пошто корисничке медијске библиотеке често садрже хиљаде фотографија, процес одређивања земаља је био изузетно дуготрајан, понекад траје више од 30 минута да се заврши.
Уместо да одмах примате листу посећених земаља и делите је на Инстаграму или Фацебооку, корисници би једноставно отишли без чекања да се процес заврши.
Нисмо могли наћи одговарајуће решење треће стране.Гугл,Мапбокс, и други слични АПИ-ји или су имали исте проблеме као и Аппле - који су лоше прилагођени за обраду партија и не нуде предност штедње времена - или би били изузетно скупи с обзиром на запремину координата које смо морали да управљамо.НоминацијаБило би превише скупо због трошкова изнајмљивања одговарајућег сервера.
Без приступачних опција на полици, ја, који сам био одговоран за бацкенд, почео да градимо сопствени АПИ.
Гејсон
Пре овог пројекта, нисам имао искуства у раду са геопросторним подацима, тако да сам морао да научим све док смо развили апликацију.
Прва ствар која ми је била потребна за имплементацију била је информација о границама земаља како би се подударале координате.GeoJSON.
ГеоЈСОН је стандардна ЈСОН датотека са специфичном структуром која вам омогућава да опишете тачке, линије и облике произвољне сложености.
На пример, рецимо да желимо да чувамо информације о територији Италије.FeatureГранице земље би биле описане унутарMultiPolygonобјекат, који садржи низ полигона. Сваки полигон се састоји од једног или више низова парова координата, где је први и последњи пар координата[lon, lat]Облик описан у првом низу ће се додати у укупну географску зону, у овом случају, сама Италија, заједно са острвом Сардинија (острво ће бити описано у посебном полигону).
Било касније низове унутар полигона су опционалне и представљају искључене области. Ово ће бити неопходно да се искључе територије као што су градске државе потпуно окружене Италијом, као што су Сан Марино и Ватикан. Координате у овим низовима морају бити набројане по сату. Што више тачака наведемо, прецизније ће бити границе земље.
Метаподаци, као што је име земље, могу се укључити уpropertiesObjekat 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",
}
}
]
}
Припрема географије
Да бисте креирали светску мапу, морао сам да извор најтачније GeoJSON датотеке са координатама свих националних граница, што се испоставило да је изненађујуће изазовно.
Ослањао сам се на различите отворене изворе, укључујући агрегиране податке изОкеанографски институти,Пакети од npmjs.org, и отворени географски подаци изНоминација, између осталог. заједнички проблем са свим подацима које сам добио био је његов квалитет. Понекад су се границе преклапале, нарочито у случајевима политичких спорова између региона. У другим случајевима, били су доступни само подаци који су укључивали територијалне воде, што није било погодно за наше потребе. Морао сам да искључим те воде одузимањем карте океана од територија земље (посебно захваљујућиФландријски поморски институтПонекад је резолуција (број координата) била прениска за поуздано геокодирање, захтевајући од мене да потражим алтернативе.
Захтеви апликације били су прилично захтевни: потребне су нам прецизне, не преклапајуће границе за свако географско подручје у високој резолуцији без територијалних вода (за приказ на мапи у апликацији), и границе ниже резолуције укључујући територијалне воде (за брже и ефикасније геокодирање, посебно за фотографије снимљене на бродовима у близини обала - проблем који смо открили приликом рада са решењима трећих страна).
Након недељу и по пажљивог рада, успео сам да креирам две ГеоЈСОН датотеке високе резолуције.countries_maritime.json, описао границе свих земаља, укључујући њихове територијалне воде, док је друга,countries_coastline.jsonСвака датотека је била неколико стотина мегабајта величине, и на крају, осећао сам се као да сам лично посетио сваки угао света.
Огње
Када је лансирана, ажурирана верзија апликације прикупила је све раније необрађене фото координате из корисничке медијске библиотеке у сетовима од 10.000 и послала их на мој бацкенд у више захтева.
Бацкенд, изграђен на Ноде.јс и хостован на АВС-у, учитао јеcountries_maritime.jsonдатотеку у меморију приликом иницијализације. Када је дошао захтев са сетом координата, користио јеПолигонски изгледбиблиотека да се подударају координате за одговарајуће територије из датотеке, која је садржала 250 земаља.
Списак координата је подвргнут строгој валидацији, јер су, како се испоставило, неке координате биле изван дозвољеног опсега. Такође смо одбацили координате са висинама изнад 8.850 метара (мало изнад врха Евереста) како би избегли рачунање типичних фотографија крила авиона у Инстаграму (авиони обично лете на висинама изнад 9.000 метара).
Када је пронађена утакмица, идентификатор земље изpropertyНакон обраде свих координата, листа записаних идентификатора је дедуплицирана, додана на корисничку листу посећених земаља и враћена клијенту да би се апликација синхронизовала са бацкенд базом података.
Након преласка на наше прилагођено решење, врхунацбрзина обраде достигла 10.000 координата у секунди(у синтетичким тестовима), медијално време за обраду корисничке медијске библиотеке смањено је на 20–25 секунди (од регистрације корисника до враћања листе посећених земаља), аProsečan broj dodatih zemalja porastao je za 225% po korisnikuзбог прецизнијег геокодирања.
Географска администрација
Како је апликација наставила да расте, корисници су почели да подносе захтеве за функције.Један од најчешћих захтева био је додавање аутоматског препознавања за регионе и велике градове унутар сваке земље.
Prikupljanje visokokvalitetnih podataka za granice 250 zemalja već je bilo teško.Izgledi za prikupljanje sličnih podataka za hiljade regiona i gradova bili su još strašniji.
Да би се то решило, пренео сам територије из ЈСОН датотеке у Постгрес табелу и развио административни интерфејс за управљање географским зонама.Поред тога, интегрисао сам админ панел са неколико спољних АПИ-ја како бих аутоматизовао креирање листи за регионе и градове на основу њихових матичних земаља.
Први проблем на који сам наишао био је инхерентна сложеност података о географским регионима. Не постоји универзално јасна разлика између региона и градова, а различите земље имају различите нивое административних подела.Препоруке.de, користећи услове и рекурзивне позиве за филтрирање по административним центрима, величини становништва и унутрашњим односима.То је такође укључивало проучавање како поделити и организовати географске чворове, њихове односе и уграђене структуре, и исправљање неких погрешних података.
Други изазов је настао када сам радио са изворима координата за регионалне границе. Након претраживања листе осмИд за регионе и градове, морао сам да извучем геометрију њихових граница.Опширније: openstreetmap.orgi skoro potpuno nedokumentovanЋирић.openstreetmap.frОви извори су били непотпуни, тако да сам морао да пошаљем више захтева и упоредим њихове резултате, бирајући најбоље одговара на основу квалитета враћених података.
Упркос недостатку документације, сложених односа података и недоследности у изворима, успео сам да креирам стабилно решење. Интерфејс админ панела сада омогућава аутоматско учитавање листа градова и региона за било коју земљу са само неколико кликова, укључујући њихове метаподатке и најбоље расположиве граничне геометрије.
Да би се решили чести проблеми са GeoJSON подацима, чак сам развио уграђени уредник који омогућава поделу, спајање, одузимање и цртање недостајућих граничних геометрија.
Сви ови алати омогућили су нам, са тимом од само два човека, да креирамо базу података о регионима и градовима које смо били поносни да представимо корисницима у року од месец и по дана.
Тренутно, апликација подржава 3.134 региона и 28.083 градова, свака са прецизним границама, и прати број корисника који су их посетили.
Минимализација географије
Управљање 31.467 територија помоћу Ноде.јс постало је немогуће због ограничења перформанси и ресурса већ у кораку иницијализације индекса.
Као што сам раније поменуо, подаци потребни за приказивање апликација и геокодирање имали су веома различите захтеве: док је припрема мапи плочица за рендерирање у апликацији могла да приушти да траје неколико минута, геокодирање је било веома осетљиво на запремине података, са брзином која је директно везана за број координата у територијалним границама.
Експериментисао сам са неколико алгоритма како бих поједноставио координате ланца полигона.
Први приступ је биоРамер Дуглас ПеукерЊегово приближавање је било нестабилно, што је довело до нескладности у заједничким границама између различитих GeoJSON датотека, а то је такође изазвало губитак мањих детаља, као што су острва.
На крају,Razvio sam sopstvenu implementaciju(објављено као npm пакет) на основуВаскрсењеАлгоритам прилагођен за рад са ГеоЈСОН-ом. Постојеће имплементације овог алгоритама могу се применити само на специфичне делове ГеоЈСОН структуре, што је решило проблем стабилности резултата, али је ипак изазвало значајну деградацију граница и губитак малих детаља.ХЕП(са углом између три суседне координате као елемент гомиле), и обрадио га као једну криву са додатном логиком за очување заједничких тачака.
Razvio sam sopstvenu implementacijuПоред смањења запремине података, ова реструктурирања GeoJSON датотека помогла је да се открију бројне грешке и сукоби у подацима:
- Незатворене координате арте.
- Конфликтне низове због неправилног увлачења координата.
- Празне координатне артерије.
- Прекомерно гнездо
- Непотребна прецизност у координатима.
Успешно сам аутоматизовао валидацију и исправљање ових грешака, делимично користећи постојеће алате као што су:Полигонски клизач,@mapbox / Гејсонхинт,@mapbox / geojson-rewind,и @mapbox/geojson-extentОво укључује спајање одвојених полигона у мултиполигоне и геометријске колекције, смањење резолуције координата на потребан ниво, исправљање смеру координата и уклањање празних масива.
Као резултат тога, постигао сам значајно побољшање у перформансама обраде географских података.Поред тога, стабилност мог алгоритма решила је проблем неусклађених поједностављених граница између суседних региона на мапи.
Преузмите Мицросервис
Упркос смањењу рачунарског оптерећења кроз поједностављење географских података, постало је јасно да Ноде.јс дефинитивно није идеално решење за наше потребе.ПоштанскиНакон обимних истраживања, укључујући мерење перформанси и потрошње ресурса, одлучио сам за другу - једноставну микро-услугу изграђену са Го.
Архитектура микро-услуга је дизајнирана да максимизира брзину обраде координата док минимизира непотребне операције.
На свом првом покретању, микро-услуга се повезује са ПостгреСкл-ом и преузима све релевантне GeoJSON податке у сетовима од 100 објеката. Ови подаци се анализирају у структуре, од којих свака садржи полигон и одговарајући идентификатор територије.
Након што је структура мареја створена, аДрвоОва врста дрвета се често користи за креирање индекса за претрагу мултидимензионалних података, као што су полигони. Дрво омогућава логаритамске временске претраге за најмањи гранични правоугао који укључује циљни полигон.
Након што је дрво изграђено, микро услуга улази у стање слушања, чекајући долазне захтеве.
Када је примљен захтев, који се састоји од парова координата[lat, lon]мултитреед обрада је покренута. Резултат је скуп јединствених територијалних идентификатора који садрже наведене координате.
Свака координата прво пролази кроз претрагу кроз Р-дрво. Ова претрага може да врати правоугао који садржи полигон, који би потенцијално могао да укључи координату.Рај-кастинг алгоритамкористи се. Овај алгоритам ради у линеарном времену, чинећи га најинтензивнијим делом процеса. Међутим, пре него што извршим проверу зрачења, проверавам да ли је идентификатор територије за полигон већ пронађен током обраде других координата у захтеву. Ако јесте, проверу зрачења прескочите, што значајно смањује време обраде услуге.
Након што све нити заврше свој посао, низ идентификатора се враћа на Node.js слој. Испод сам покушао да представим архитектуру у следећем дијаграму:
Цео процес претраге, осим специфичне оптимизације за прескакање поновљених провера зрачења, блиско одражава како ПостГИС бави сличним задатком када користиПоклониИндекс је
Користећи АПИ изграђен око Го микро-услуге,постигли смо способност обраде око 100.000 парова координата у секундиZa poređenje, prethodno Node.js rešenje je upravljalo oko 10.000 parova koordinata za 250 zona, uključujući nadglavlje mrežnih zahteva i backend operacija.
Ово значајно побољшање брзине обраде омогућило је много брже састављање корисничких листа посећених земаља.Поред тога, уз подршку за препознавање региона и градова,aplikacija je videla 160% povećanje aktivnih korisnika i 107% povećanje deljenja korisnikaЊихови резултати
Решење остаје у употреби данас и наставља да ефикасно управља све већим количинама захтева и географским зонама.
