Paikkatietoindeksointi puolustuksessa: H3, S2, R-Tree ja miljoonan jäljen kysely

Miljoonan jäljen kyselyongelma

Tavallinen operaattorin kysely puolustuksen fuusioalustalla kuuluu: "näytä kaikki 5 km:n säteellä tästä pisteestä viimeisen 60 sekunnin aikana." Se kuulostaa vähäpätöiseltä. Sadan miljoonan jälkipäivityksen taulussa, johon AIS-vastaanottimet, ADS-B-syötteet, tutkajäljet, ESM ja lennokkitelemetria kirjoittavat, naiivi toteutus romahtaa kolmessa viikossa tuotantoliikennettä.

Naiivi kysely on peräkkäisskannaus. SELECT * FROM tracks WHERE ST_DWithin(geom, $point, 5000) AND ts > now() - interval '60 seconds'. Sadan miljoonan rivin taulussa ilman paikkatietoindeksiä tämä kestää 12–40 sekuntia levystä riippuen. Tuhannen operaattorin päivittäessä jokainen 2 sekunnin välein tietokanta palaa. Korjaus ei ole nopeampi laitteisto. Korjaus on paikkatietoindeksi — ja indeksin valinta sanelee kaiken alavirrassa: sisäänajon läpäisykyvyn, kyselyn viiveen, tallennuksen jalanjäljen ja hajautetun shardauksen kustannuksen.

Tämä artikkeli käy läpi neljä indeksiperhettä, joilla on merkitystä puolustuksessa: H3, S2, R-Tree-suvun ja PostGIS GiST/SP-GiST/BRIN -kolmikon. Sen jälkeen se käsittelee hybridit aikasarjamallit, kaksikerroksisen karsinta-arkkitehtuurin yhteiselle operatiiviselle kuvalle sekä migraatiotarinan.

H3 (Uberin heksagonaalinen)

H3 on hierarkkinen heksagonaalinen ruudukkojärjestelmä. Planeetta jaetaan 122 perussoluun (10 viisikulmiota, 112 kuusikulmiota), ja jokainen perussolu jakautuu rekursiivisesti seitsemään lapseen aina resoluutioon 15 asti. Solu resoluutiolla 9 on noin 0,1 km² — kaupunginkorttelin kokoinen. Solu resoluutiolla 6 on noin 36 km² — käyttökelpoinen operatiivinen kohtaamiskupla.

Kuusikulmiot voittavat neliöt läheisyyskyselyissä, koska jokainen heksagonaalinen naapuri sijaitsee samalla keskipiste-etäisyydellä. Neliöruudukossa lävistäjänaapurit ovat 1,41× kauempana kuin reunanaapurit — jokaisen etäisyyslaskennan on käsiteltävä se erikoistapauksena. Kuusikulmioilla säteen 3 k-ring tuottaa täsmälleen 37 solua, kaikki ennustettavalla etäisyydellä. 5 km:n säteen haku muuttuu muotoon: muunna kyselypiste H3-soluksi, laajenna 5 km:n kattavaksi k-ringiksi, hae kaikki näillä solun ID-tunnuksilla merkityt jäljet ja tarkenna sitten täsmällisellä ST_Distancella.

Puolustusystävälliset ominaisuudet: H3-solujen ID-tunnukset ovat 64-bittisiä kokonaislukuja, vähäpätöisiä indeksoida missä tahansa KV-varastossa. Solun jäsenyys on hajautettavissa, joten H3-sarakkeella varustettu jälki voidaan shardata solun etuliitteen mukaan ilman räätälöityä logiikkaa. Solutason aggregaatit ("kuinka monta jälkeä per H3-7-solu viimeisen tunnin aikana") tiivistyvät suoraan muotoon GROUP BY h3_index. Olemme nähneet H3-indeksoitujen jälkitaulujen vastaavan 5 km:n läheisyyskyselyihin 8–14 ms:ssa 200 miljoonan rivin tauluissa.

Google S2

S2 jakaa pallon nelipuuprojektion kautta sisäänkirjoitetun kuution pinnalle. Jokainen tahko jaetaan rekursiivisesti neljään lapseen aina tasolle 30 asti, jossa solut ovat noin 1 cm². S2CellId on 64-bittinen kokonaisluku, joka koodaa solun tahkon, sijainnin Hilbert-käyrällä ja tason. Hilbert-koodaus on temppu: pallolla lähekkäin olevilla soluilla on lähekkäiset ID-tunnukset, joten kokonaislukusarakkeen BETWEEN-väli käyttäytyy kuin paikkatietoaluekysely.

Tämä kokonaislukuaritmetiikan etu on se, missä S2 voittaa. Jos käyttövarasto on shardattu RDBMS, litteä KV (DynamoDB, Cassandra) tai hakukone (Elasticsearchin geo_shape käyttää BKD-puita, mutta aluekyselyt S2CellId-tunnuksilla ovat yhtä nopeita), S2 pitää läheisyyslogiikan halpojen kokonaislukuvertailujen sisällä. GIS-laajennusta ei vaadita.

H3 vastaan S2 käytännössä: H3 on ystävällisempi yhtenäisetäisyyspäättelyyn, aggregaatioihin ja ihmisluettaviin soluihin. S2 on ystävällisempi, kun tallennuskerroksessa ei ole geometriatukea ja työskentelet miljardien pisteiden kanssa globaalin kattavuuden yli, jossa H3:n viisikulmiovääristymä (10 solua planeettaa kohden on vain 5 naapuria 6:n sijaan) aiheuttaa ongelmia. NATO:n merivalvontatiimit, jotka indeksoivat globaalia AIS-dataa, ovat siirtyneet S2:een juuri tästä syystä. Alueelliset ilmakuvat mannermaisella laajuudella pysyvät enimmäkseen H3:ssa.

R-Tree ja variantit

R-Tree, jonka Guttman esitteli vuonna 1984, indeksoi geometriat rajauslaatikoilla. Jokainen puun solmu tallentaa lastensa minimirajausristikon (MBR). Läheisyyskysely kulkee puuta pitkin karsien alipuut, joiden MBR ei leikkaa kyselyn vaippaa. Pahin tapaus on huono — MBR:ien välinen päällekkäisyys heikkenee lineaariskannaukseksi — mutta keskimääräinen tapaus reaalimaailman datalla on erinomainen.

R*-Tree (1990) vähentää MBR:ien päällekkäisyyttä älykkäämmillä solmujen jaoilla ja uudelleeninsertoinnilla ylivuodon yhteydessä. Se on variantti, jonka useimmat tuotantojärjestelmät toteuttavat nykyään, mukaan lukien libspatialindexin sisäinen muistinvarainen R-Tree, jota GeoPandas käyttää, sekä DuckDB:n paikkatietolaajennus.

Joukkolatauksen tarina on merkityksellinen. Miljoonan geometrian lataaminen yksitellen R-Treehen on hidasta ja tuottaa huonosti tasapainotetun puun. Sort-Tile-Recursive (STR) -joukkolataus rakentaa koko puun yhdellä läpiajolla, sen jälkeen kun geometriat on lajiteltu tilantäyttökäyrää pitkin, jolloin saadaan lähes optimaalinen MBR-asettelu. Tee aina joukkolataus, kun pystytät uuden indeksin täytetylle datajoukolle.

Milloin muistinvarainen R-Tree silti voittaa: asiakaspuolen geometriaindeksit yksittäisen operaattorin työasemalla (Qt-pohjaiset yhteisen operatiivisen kuvan asiakkaat, selaimen puolen Leaflet/Mapbox supercluster-tasot) ja tilattomat geofence-palvelut, joissa geofence-joukko mahtuu RAM-muistiin. 100k geofencen R-Tree libspatialindexissä palvelee point-in-polygon-hakuja 30–60 µs:ssa. PostGIS samalle työkuormalle, verkon edestakaisen viiveen kanssa, on lähempänä 1–2 ms.

PostGIS-indeksointi — GiST vs SP-GiST vs BRIN

PostGIS on oletusarvoinen paikkatietoselkäranka useimmille puolustuksen fuusiopinoille, joihin Corvus on koskenut, ja indeksin valinta sen sisällä ei ole vähäpätöinen. Katso syvällisempi PostGIS puolustukseen -läpikäyntimme täydellistä asennusta varten; tämä osio on indeksin valinnan yhteenveto.

GiST on yleistetty hakupuu, jota PostGIS käyttää toteuttamaan R-Treeta vastaavan rakenteen geometrioiden yli. Se on oletus. Sopii hyvin, kun geometriat ovat kooltaan heterogeenisiä (sekoittaen pisteitä, viivoja, monikulmioita) ja kun työkuorma sekoittaa lukua ja kirjoitusta. Rakennusaika 100M pisteriville on noin 15–25 minuuttia nopealla SSD:llä, kun maintenance_work_mem on viritetty 2 GB:hen.

SP-GiST (tilaositettu GiST) toteuttaa nelipuita ja k-d-puita. Nopeampi pelkkien pisteiden työkuormissa, joissa data on tasaisesti jakautunut. Olemme mitanneet SP-GiSTin 1,4–1,8× nopeammaksi kuin GiST puhtaissa pisteläheisyyskyselyissä 50M rivin jälkitaulussa, 25 % pienemmällä indeksin jalanjäljellä.

BRIN (lohkoalueindeksi) on halpa vaihtoehto, kun data on jo fyysisesti klusteroitu sijainnin mukaan — esimerkiksi kun jälki-insertit on ositettu alueittain ja fyysisesti lisätty maantieteellisessä järjestyksessä. BRIN-indeksit ovat pieniä (kilotavuja tauluille, jotka tarvitsevat gigatavuja GiSTiä) ja hyödyllisiä toissijaisena suodattimena, ei ensisijaisena paikkatietoindeksinä. Ne loistavat kylmissä arkistoositteissa.

Paikka-aikayhdistelmäindeksimalli: "5 km:n säteellä viimeisen 60 sekunnin aikana" -työkuormissa älä yritä rakentaa yhtä monisarakeindeksiä. Rakenna sen sijaan GiST sarakkeelle geom ja B-tree sarakkeelle ts, ja ositta sitten taulu ajan mukaan. Kyselynsuunnittelija yhdistää molemmat, ja osituksen karsinta eliminoi 99 % datasta ennen kuin mitään paikkatietotyötä tapahtuu. Todelliset kyselysuunnitelmat miljoonan rivin osituksilla vastaavat 4–12 ms:ssa. Sama kysely ilman osituksen karsintaa, samassa indeksoidussa taulussa, on 200–400 ms.

Aikasarja + paikkatieto -hybridi

Puolustusjäljet ovat sydämeltään aikasarjoja. Jokainen jälkipäivitys on lisäys. Luvut ovat pääasiassa "uusin sijainti per lähetin" ja "viimeisen N minuutin jälki". Hybridipino on tärkeä.

TimescaleDB-hypertaulut PostGIS:n kanssa. Hypertaulu ositetaan automaattisesti aikalohkoittain (1 tunnin tai 6 tunnin lohkot suurivolyymisille syötteille). PostGIS GiST -indeksit rakennetaan per lohko. Yli 24 tuntia vanhojen lohkojen pakkaus tuottaa 8–14× tallennusvähennyksen. Jatkuvat aggregaatit esilaskevat per-H3-solu tuntittaiset yhteenvedot. Tämä on suositeltava aloituspino useimmille puolustuksen fuusiokäyttöönotoille.

kdb+/q korkeimman läpäisykyvyn tapauksiin. Kun alustan on imettävä useita satoja tuhansia jälkipäivityksiä sekunnissa — suuret tutkaverkot fuusioituna monilähteiseen ESM:ään — kdb+:n sarakepohjainen tallennus q-sql:n kanssa pysyy luokkansa parhaana. q-sql on niukka, lisensointi on kallista, mutta läpäisykyky on todellinen. Paikkatietotarina on käsin koottu (H3- tai S2-solujen ID-tunnukset tavallisina long-sarakkeina) eikä natiivi GIS-laajennus.

ClickHouse geohash-sarakkeilla. ClickHouse käsittelee analyyttisen toiston kerroksen hyvin — toista viimeisen seitsemän päivän jäljet uutta korrelaatioalgoritmia vasten. Geohash-sarakkeet (vaihtelevanmittaiset base32-merkkijonot, etuliite-yhtäsuuruus = rajauslaatikon sisältyvyys) ovat pragmaattinen indeksi. ClickHouse 24.x lisäsi natiivit geoDistance- ja S2-funktiot; 5 miljardin rivin historiallisessa jälkitaulussa 10 km:n läheisyysskannaus ratkeaa 1–3 sekunnissa. Ei interaktiivinen, mutta hyväksyttävä analyytikkotyökuormille.

Indeksit operatiiviselle kuvalle

Yhteinen operatiivinen kuva (COP) on paikkatietoindeksien kanoninen kuluttaja. Satoja tai tuhansia operaattori-istuntoja, joista jokainen renderöi jälkiä näkymäalueen sisällä, päivittäen 1–4 kertaa sekunnissa. Ilman kaksikerroksista karsinta-arkkitehtuuria taustajärjestelmä kuolee ensin.

Palvelinpuolen karsinta. Palvelin soveltaa näkymäalueen rajauslaatikkoa paikkatietoindeksikyselynä, soveltaa sitten aikaikkunasuodatinta ja soveltaa sitten entiteettityyppi- ja luokitussuodattimia. Tulos on rajattu kuorma — tyypillisesti rajattu 5 000 jälkeen per vastaus pitämään johdon koko ennustettavana. Oikein indeksoidulla PostGIS-hypertaululla tämä on 6–20 ms per istunto.

Asiakaspuolen karsinta. Asiakas vastaanottaa hieman suuremman vaipan kuin näkyvä näkymäalue (jotta panorointi ei välittömästi laukaise uudelleenhakua), ylläpitää muistinvaraista jälkien R-Treeta ja renderöi vain sen, mikä on näkyvän kankaan sisällä. R-Tree hoitaa panoroinnin, zoomauksen ja kohdistustestauksen paikallisesti 60 FPS:llä ilman palvelimen edestakaisia kierroksia.

Kaksikerroksisuus on se, mikä skaalautuu tuhansiin samanaikaisiin istuntoihin. Palvelinpuolen karsinta rajaa taustajärjestelmän kustannuksen. Asiakaspuolen karsinta rajaa käyttöliittymän kustannuksen. Kumpikin kerros yksinään hajoaa. Tämä malli on välttämätön riippumatta siitä, onko COP paksu asiakas (Qt, .NET) vai selainkartta (Mapbox GL, MapLibre, deck.gl) — katso laajempi putkiviittaus puolustuksen fuusioputkisarjamme osasta 1.

Migraation realiteetit

Migraatio "kaikki yhdessä taulussa ilman paikkatietoindeksiä" -tilasta oikein indeksoituun, ositettuun, hypertaulupohjaiseen varastoon on se, missä useimmat puolustuksen dataohjelmat kompastuvat. Kolme sääntöä toimituskokemuksesta:

Kaksoiskirjoitus ennen siirtymää. Uusi indeksoitu varasto toimii rinnakkain vanhan taulun kanssa vähintään kaksi operatiivista sykliä (tyypillisesti kaksi viikkoa). Kirjoitukset menevät molempiin. Luvut siirtyvät asteittain. Peruutus on konfiguraatiolippu, ei tietokantamigraatio.

Skeeman evoluutiokuri. Sarakkeen lisääminen 500 GB:n hypertauluun, jossa on täysi GiST-indeksointi, ei ole 5 sekunnin ALTER TABLE. Suunnittele sarakkeiden lisäykset harkittuina julkaisuina. Käytä JSONB-kuormia kokeilun alla oleville kentille; nosta vakaat kentät tyypitetyiksi sarakkeiksi, kun skeema asettuu.

Täyttö aikajärjestyksessä lohkoina. Historiallisen jälkidatan palauttaminen uuteen hypertauluun käänteisessä kronologisessa järjestyksessä (uusin ensin) tarkoittaa, että operatiivisesti relevantti ikkuna on kyseltävissä ensin, kun vanhemmat lohkot ajetaan sisään taustalla. Älä odota täyttä täyttöä ennen kuin siirrät luvut yli.