Hlavní navigace

Jak se kreslí realtime volební mapy pro statisíce lidí

Autor: Lidovky.cz
Marcel Šulek

Datový novinář Marcel Šulek dává nahlédnout do své kuchyně. Jak vznikaly volební mapy pro server Lidovky.cz?

Doba čtení: 11 minut

Poslední dvoje volby jsem měl v Mafře na starosti vývoj okrskové volební mapy (parlamentní ’17 a prezidentské ’18 1. kolo, 2. kolo), která se měla aktualizovat už v průběhu hlasování (na rozdíl od předchozí produkce v Českém rozhlase, kde jsme ji generovali jednorázově po sečtení všech okrsků) a která měla odolat zátěži řádově desetitisíců konkurenčních zobrazení. Byla to celkem zajímavá výzva a zde shrnu, jak to nakonec celé fungovalo.

Při tvorbě webových map jsou možné v zásadě dva hlavní přístupy: buď lze poslat na klienta veškeré potřebné informace (geometrii a data) v surové podobě a nechat mapu vykreslit v prohlížeči (typicky do SVG nebo canvas), nebo vykreslení provést na serveru a klientovi posílat hotové bitmapy (nejčastěji ve WebMercator dlaždicích).

Výhodou posílání surových dat je, že to je nejmíň práce. Geometrii stačí převést do něčeho relativně standardního, třeba GeoJSON, následně spojit s volebními daty, na jejich základě zvolit způsob vykreslení (barva, průhlednost…) a pomocí nějaké knihovny (typicky D3) element nakreslit. Znamená to ale poslat vždy úplně všechna data, v úplně nejvyšším přiblížení. I když si tak návštěvník chce prohlídnout jen hrubou přehledovku České republiky, stáhne se mu geometrie posledního záhybu v Horní Dolní, kde starosta nechtěl dva sousedy v jedné volební místnosti, a tak tam rukou vyčlenil barák do vedlejšího okrsku. Pro účely České republiky takový okrskový GeoJSON váží asi 120 MB, ani při nejlepší vůli to tedy není prakticky proveditelné.

Druhá možnost je zmíněné posílání bitmapových dlaždic. Jednotlivá dlaždice je vždy menší (PNG o 256 × 256 px), ale zase součet velikosti všech dlaždic ve všech zobrazeních je mnohem vyšší než velikost GeoJSONu. Je to dáno jednak tím, že se musí generovat separátní sada dlaždic pro každé přiblížení (a každý stupeň přiblížení navíc znamená 4× více dlaždic), ale hlavně tím, že bitmapy na rozdíl od vektoru pevně svazují geometrii a data. Zatímco u vektoru lze volit způsob zobrazení až na klientovi (vybarvit plochu podle absolutního vítěze, nebo jen podle stupně podpory pro každého kandidáta, nebo místo plochy vybarvovat kolečko odpovídající počtu obyvatel apod.), bitmapu prostě klient zobrazí tak, jak ji dostane, a nic s tím neudělá.

Pak existuje ještě třetí cesta někde napůl: vektorové dlaždice, používají je třeba kolegové v Rozhlasu. Ty kombinují přístup vektorů (jsou plynule zoomovatelné a je tam oddělená geometrie a jejich vykreslení) a bitmap (v podstatě se na klienta posílají SVGčka ořezaná do jednotlivých dlaždic a zjednodušená na příslušný zoomlevel). Nemusí se tedy generovat všechny pohledy, a dokonce by šlo sdílet jedny dlaždice napříč různými volbami a jen měnit data a vykreslovací skript. Cenou za to však je prohibitivně pomalé vykreslování, kdy se taková mapa při interakci „seká“ i na moderním čtyřjádru, a co teprve na mobilech. Navíc jsme při jejich testování měli i problémy s kompatibilitou (byť ty už jsou možná vyřešené, je to už pár let, co jsem to zkoušel osobně).

Generujeme dlaždice

Z výše popsaných důvodů jsme tedy šli cestou on-the-fly generování bitmapových dlaždic. To v principu není přehnaný problém: stačí vzít už zmíněnou knihovnu D3, která umí vzít GeoJSON a zobrazit ho do canvasu a která funguje jak v prohlížeči, tak na serveru v podobě modulu pro Node.js. Jen místo browserového canvasu se jí předhodí jeho serverová implementace, ale jinak je kód identický.

I s kreslením do standardních mapových dlaždic nám pomůže D3. Jakmile známe souřadnice žádané dlaždice (určenou zoomem a souřadnicemi x a y), stačí vzít projekcid3.geo.geoMercator() a zadat jí správné měřítko a posunutí. Pokud se vám nechce počítat, stačí použít modulsphericalmercator a on to udělá za vás.

Pak vyberete z GeoJSONu ty features, které na dané dlaždici leží (třeba přes d3.geoBounds() ), pro každou z nich nastavíte způsob vykreslení (obvykle fillColor) a vykreslíte ji na canvas. Nakonec přes canvas.getImageData() dostanete blob s PNG daty a ten pošlete klientovi.

Škálujeme

Minimum viable produkt bychom měli, teď ke startupové otázce: does it scale? Bohužel moc ne. Node ani node-canvas na tohle úplně stavěné nebyly a dlaždice na nízkých zoomech, kde jeden obrázek obsahuje oblast přibližně od Ústí nad Labem po Brno s řádově tisíci okrsky (a tedy tisíci komplikovanými polygony), trvá i na moderním CPU vykreslit řádově vteřiny. U vyšších zoomů, kde se kreslí jen desítky okrsků, už se bavíme o milisekundách, ale hlavní zátěž půjde vždy na přehledovky, ne na detaily. Takže bylo třeba nižší stupně nějak jednoduše cachovat (a po načtení nové dávky výsledků zase invalidovat, mapa má přece být realtime).

A ještě jedna komplikace: zmíněných pár vteřin se bude kreslit dlaždice 7-69-44 ( z-x-y) od Ústí po Brno, ale jen na tomhle zoomu nám zbývají ještě nejmíň dvě komplikované dlaždice se západem a východem republiky, plus dalších asi pět s menšími kusy pohraničí. Pak by se hodil zoom 6 pro menší displeje a zoom 8 ještě pořád není o mnoho rychlejší… no prostě jedno jádro to neuhraje (resp. jeden proces, node.js je jednovláknový).

Buď můžeme spustit víc serverů a dát je za loadbalancer, nebo roztrhneme serverovou a vykreslovací logiku a mezi ně dáme nějaký „hub“, který bude spravovat požadavky na vykreslení od HTTP serveru, a naopak jim oznamovat, že žádaná dlaždice už je k dispozici. A samozřejmě, všechny vykreslovací jednotky by měly pracovat nad stejnými průběžnými výsledky – nechceme přeci mít okrsek, který je přes dvě dlaždice zobrazený dvěma barvami, protože druhý server ještě ze staťáku nestáhl poslední XMLko.

Pojďme si tedy udělat seznam dílčích služeb, které budeme potřebovat k vyřízení každého požadavku:

  • Cachovací služba (a to nějaká chytrá, který dva požadavky na stejnou dlaždici sloučí do jednoho a pak odpověď multicastuje)
  • Loadbalancer
  • HTTP endpoint
  • Manažer požadavků na dlaždice
  • Generátor dlaždic (minimálně 4 jádra, lépe tak 16)
  • DB s aktuálními výsledky a nějakou variantou PUB/SUB logiky na pushování změn na generátory

Jo, a celý tenhle tyjátr se použije tak jednou do roka na jedno odpoledne. Hodně štěstí s ospravedlňováním nákupu dedikovaného železa.

Skládáme řešení, hlavně levně

Naštěstí žijeme v době cloudu a všechno lze poskládat z ready-made komponent. Protože Mafra má historicky účet u Azure, většinou jsem pracoval s ním, ale paralelní nabídku za srovnatelné ceny najdete i na AWS.

Cachujeme a balancujeme

Cache zvládla nejsnáz obstarat Azure CDN. Stačí nastavit mapování na cílovou URL a o zbytek se postará její logika: pokud má request zacachovaný, tak rovnou odpoví, pokud ne, teprve jej přepošle na váš server (přičemž tenhle server klidně může být Azure loadbalancer, který jej teprve přepošle na konkrétní server). Pokud na CDN přijde víc dotazů na stejné nenacachované URL, interně si je sloučí a na server pošle jen jeden dotaz. Následnou odpověď pak zase vrátí na všechny požadavky (pravděpodobně to nefunguje napříč světovými regiony, ale pro regionální Lidovky a iDNES to nevadilo).

Verzování lze docílit dvěma způsoby: buď měnit URL, nebo posílat hlavičku max-age, případně expires. Pro moje účely bylo lepší měnit URL, protože jsem potřeboval s každou změnou výsledků invalidovat všechny dosavadní dlaždice bez ohledu na to, kdy je CDN poprvé „viděla“. Prakticky to vypadalo tak, že z klientské aplikace šel prvně dotaz na aktuální revizi (číslo 0 až asi 60, kolik bylo dávek výsledků) a následně se žádaly URL prefixované touto verzí (na což byl připraven HTTP server a tuhle část URL většinou zahazoval, protože vždy vracel nejnovější revizi, nedržel si historii).

V parlamentních volbách šel skrz CDN i dotaz na aktuální verzi, přičemž odpověď byla s hlavičkou max-age: 0, tedy že by si to CDN neměla vůbec pamatovat a vždy dotaz přeposlat na vnitřní adresu. To mělo zjednodušit aplikaci (a ušetřit jeden DNS dotaz), bohužel se ale nepravidelně párkrát stalo, že odpověď jaksi „zatuhla“ a CDN pořád vracela starou verzi. Na prezidentských volbách tedy šel úvodní dotaz přímo na loadbalancer a přes CDN šly až následné dotazy na dlaždice.

Další nevýhodou Azure CDN bylo, že sice umí HTTP i HTTPS odpovědi, ale neumí HTTPS terminovat, tedy že by HTTPS dotaz přeposlala na HTTP server. Přidalo to tak potřebu nasměrovat na server nějakou doménu a sehnat pro ni certifikát, naštěstí v době Let’s Encrypt to už není problém.

Na celé CDN platíte akorát za přenesená data (za náš protočený terabajt a půl dat to bylo asi 110 EUR), cachovaný storage je v ceně. Kromě vygenerovaných dlaždic jsme ji použili i jako prostředek „odstínění“ serverů OpenStreetMap a dalších poskytovatelů podkladových dlaždic, aby je nebombardovali všichni naši čtenáři, ale jen řádově menší traffic z CDNky.

Další zastávkou requestů byl loadbalancer. Ten je v Azure klikačka, zvenku se dozvíte jeho IP (na tu se hodí nasměrovat ten „no-CDN“ přístup) a naklikáte, na jaké virtuální mašiny (či další služby) má přesměrovávat. Umí i testovat, zda daný stroj žije (buď jen na TCP, kdy stačí, že přijme spojení, nebo na HTTP, kde musí vrátit kód 2×x), a posílá data jen na tu službu, která funguje. Já jsem se na tom spálil, protože generátory dlaždic vracely na request pouhého / kód nenalezeno (404) a já se divil, proč mi to napřímo funguje, ale loadbalancer hází timeout. Naštěstí jsem si to uvědomil dřív, než jsem totálně rozhodil firewallová pravidla (jsou separátní na loadbalanceru a vnitřních virtuálních mašinách). Balancer balancuje round-robinem, což bylo vcelku dostačující.

Servery, fronty a generátory

Teď přecházíme od různých cloudových služeb ke klasické IaaS. Na konkrétních virtuálech nám běžel HTTP(S) server, manažer fronty požadavků na dlaždice, databáze s aktuálními výsledky a generátory dlaždic.

HTTP server byla dvojka služeb na jednom stroji: nginx jako reverzní proxy + HTTPS terminátor a node.js jako celkem tenký skriptovací server. Ten jednak zadával požadavky na generování dlaždic, a jednak byl i sám připojen na výsledkovou databázi a posílal na klienta aktuální výsledky (pro použití při najetí myši nad okrsek, aby se mu vypsaly podrobné zisky jednotlivých stran/kandidátů).

Management požadavků řešil RabbitMQ. Je to nástroj přímo k tomuhle dělaný, se snadným API a dokumentací, že z nuly do produkce to trvá asi půl dne (jako v tomhle případě). Jako bonus má slušný webový interface, kde se dá celkem dobře odhadovat, zda je současný počet generátorů dostatečný, nebo jestli bych měl připlatit za nějaká další výpočetní jádra.

Generátory byly, jak jsem už výše psal, stroje s Node.js a node-canvasem (a přidruženou grafickou knihovnou Cairo). Původně mě trochu znervózňovalo, že se vždy drží celý ten okrskový GeoJSON v paměti, což znamenalo, že každý proces spotřeboval stabilně kousek pod 1 GB RAM. Protože ale také každý proces dovedl na 100 % vytížit jedno CPU a většina virtuálních strojů se poskytuje v poměru 1 CPU : 2 GB RAM, přičemž na těch strojích nic dalšího neběželo, tak jsem to dále neřešil. Softwarový inženýr by zaplakal, ale jak říká Martin Malý, za krásný kód ještě nikdo Pulitzera nedostal.

Konkrétní stroje, které generovaly mapy, byly dost… řekněme heterogenní sebranka. Až na několik málo špiček totiž všechny dlaždice nakreslil „cluster“ sestávající z kancelářského notebooku, plonkového kancelářského stroje bootovaného z USB flashky, mého domácího PC (připojený k internetu přes Wi-Fi) a mojí kancelářské pracovní stanice (4 jádra, kvůli omezení části firemní sítě byla routovaná přes VPNku k domácímu Mikrotiku a teprve přes něj do internetu).

Samozřejmě jsem měl pro případ, že by se tenhle domeček z karet začal hroutit, připravený deployskript, se kterým bych v Azure i AWS rychle nahodil další virtuální stroje, ale nebyl potřeba. Dohromady 16 jader jsme tak měli oba víkendy prakticky zdarma.

Generování statických dlaždic

Sčítání skončilo, volby nějak dopadly, dlaždice už se nikdy nezmění… co teď? Nechat server běžet a platit za něj každý měsíc ne zcela malé peníze, nebo jej vypnout a s ním zrušit i celou mapovou aplikaci? Naštěstí tu je třetí možnost: vygenerovat dlaždice do statických souborů. To se ale trochu snadněji řekne, než udělá.

Totiž tím, jak jsou dlaždice v zoomech a každý zoom navíc znamená 4× víc dat než ten předchozí, bylo potřeba zvolit nějaké přiblížení, do kterého dlaždice generovat. Ale jak? Ve velkých městech jsou okrsky malinké, takže tu je potřeba mít mapy opravdu podrobné. Na druhou stranu většina rozlohy ČR je tvořena řídce osídlenými vesnicemi, a hlavně přilehlými poli, lesy a loukami. Pokud vygenerujeme podrobné zobrazení, na drtivou většinu dlaždic se nikdo nikdy nepodívá, protože na nich bude akorát nějaký palouk. Pokud zvolíme jako konečný nižší zoomlevel, tak zase Brňáci nebudou mít šanci najít ten svůj okrsek.

Z toho důvodu jsme ještě trochu zkomplikovali klientskou aplikaci: od určitého přiblížení jsme místo dlaždic stahovali přímo GeoJSONy jednotlivých okrsků a geometrii kreslili (pomocí knihovny Leaflet.js ) až v prohlížeči. Tím se zkombinovaly výhody dlaždic v menším přiblížení (relativně konstantní velikost bez ohledu na složitost v nich obsažené geometrie, tedy že dlaždice s řídce osídleným pohraničím je stejně velká jako ta s tisíci pražskými okrsky) a surové geometrie ve vyšších zoomech (konstantní velikost bez ohledu na stupeň přiblížení, tedy že daný okrsek stačí stáhnout jednou a je použitelný i pro vyšší, až absurdní přiblížení).

A ani to nebylo moc programování navíc: díky tomu, že JavaScript a příslušné knihovny lze používat jak na klientovi, tak na serveru, šlo kód bez větších problémů sdílet.

Při tomto generování jsem naposledy ocenil model s RabbitMQ jako centrálním brokerem. Bylo totiž možné naplnit frontu požadavky na všechny dlaždice a pak podle potřeby připojit více výpočetního výkonu. To se hodilo zejména u 2. kola prezidentských voleb, kdy jsem generoval i mapu „co hlas, to tečka“, která byla výpočetně cca o dva řády náročnější než ostatní dlaždice. Normálně by to byla operace na celou noc, tady ale stačilo v AWS za Spot Pricing pořídit čtyři instance po 36 jádrech… a za půl hodiny bylo spočítáno. Faktura na tuhle 120jádrovou legraci čítala asi 40 Kč, opět se tak potvrdilo, že na jednorázové tasky se čím dál míň vyplatí optimalizovat. Většinou je levnější a jednodušší to přebít hrubou výpočetní silou.

Tento text původně vyšel na soukromém blogu Marcela Šulka.

Našli jste v článku chybu?