Te hogy tárolnád?

Adatbázis: SQL, XML DB

Üdv,

Van egy egyszerű adatmodellem:

Jó sok ilyen kapcsolat van és minél gyorsabban kell őket elérném, egymás után, tetszőleges sorrendben. Az adatokat felépítem, feldolgozom és aztán mehetnek a levesbe, nincs szükség perzisztenciára. Az adatok feltöltését és feldolgozását mindenképp szeretném elkülöníteni, ezek más-más nyelveken lesznek implementálva. A tárolást megoldhatnám egy újabb processzel, de annyi féle adatbázis létezik, minek gyártanék mégegyet - gondoltam.

A betöltést és a feldolgozást is több processz végzi párhuzamosan. Betöltésnél a forrásanyagban a way-ek és node-ok rendezetlenül vannak és szeretném elkerülni, hogy a betöltő processzben rendezni kelljen őket, erre nem optimális a nyelv amiben implementáltam (ruby). A feldolgozás fázisában a "state" flag jelzi, hogy feldolgozott-e már a way (feldolgozás után nem dobhatom azonnal, mert az exportálást egy újabb processz végzi).

A feldolgozás egy processze egy időben egy way-en dolgozik, az összes node-ját elemezve. A feladat, hogy a processz hatékonyan hozzáférjen az adathoz.

Néhány adat:
- ways: kb 4M objektum
- nodes: kb 80M objektum
- feldolgozás elvárt sebessége: 10.000 ways/s/processz

Te hogy oldanád meg..? Mindenféle ötlet érdekel, csak az nyelv ami kötött: ruby. Java-ban lehet, hogy a loader hatékonyabban tudná rendezni az adatokat és nem lenne szükség arra, hogy a DB kezeljen kapcsolatokat, de ez első körben nem opció.

(Egyébként OpenStreetMap adatok feldolgozásáról van szó.)

UPDATE: Nincs szükség arra, hogy a DB kezelje a relációkat: első lépésben a Way-eket töltöm be adatbázisba és közben építek egy hash-t: 

$node_ways[node_id]->[way1_id,way2_id,...]

- majd jönnek a node-ok és találat esetén hozzácsapja a meglévő rekordhoz a node-ot (sql: UPDATE, redis: RPUSH/APPEND). Bár ez jelentősen megdobta a memóriaigényt a ruby loaderben, de tegyük fel, hogy ezt megoldom valahogy. Viszont a feladat még ettől adott: hogy/hol tároljam ezeket a sorokat?

  • 4086 megtekintés

( joco01 v | 2015. 05. 31., v – 14:19 )

A nyelv megkötés honnan jön? Egyébként nem hiszek abban, hogy egyik nyelv optimálisabb lenne másiknál. Ha nagyon sok az adat, akkor az algoritmikus komplexitás többet nyom a latban, és nem hinném, hogy rubyban vagy bármiben ne lehetne ugyanolyan komplexitású algoritmusokat megvalósítani.

Jól értem, hogy X helyről jön az adat, a feltöltés ezt valahova elteszi, utána valaki onnan kiveszi, hogy feldolgozza? Miért kell egyáltalán letárolni középen? Mehetne IPC-vel simán, memóriában végtelenszer gyorsabb az elérés. Vagy ha nagyon diszkre akarod írni, találj ki egy saját formátumot, amibe gyorsan tudsz írni és egy adott lekérdezés is gyorsan tud olvasni (pl. írj N darab fájlba, valami közös jellemző alapján az együtt feldolgozandó adatok menjenek közös fájlba).

A másik trükk, ami eszembe jut, az a sharding/batching. Pl. kulcs szerint hashelve egyszerre kérj le 1000 rekordot, így nagyságrendekkel kevesebb lesz a kommunikációs overhead. Vagy lehetne egy harmadik processz, ami az egészet vezérli, így lehet, hogy kicsit rosszabb a teljesítmény, de könnyebb koordinálni a feldolgozást egy helyről.

Eszembe jut még a MapReduce is, mint lehetőség, de nem tudom, ez mennyire fér bele az architektúrádba.

--

Ok, ez is jó, végülis tényleg nem fektettem túl sok energiát abba, hogy megnézzem, mennyire lenne hatékony ruby VM-ben tárolni és sorbarendezni az adatokat. Jobban ránézek.

Középen azért szeretném letárolni, mert a feldolgozó optimalizálásához nagyon sokszor kell majd felépítenem az adatbázist ami aránylag sok idő, ha olyan adatmennyiséget akarok, amivel lehet méréseket végezni. Nem akarom diszkre írni, elég memóriában.

Redis-sel épp az a gond, hogy egyszerre csak egy kulcsot lehet lekérni. Postgresql-lel 100-as batcheket kérek, de O(N) algoritmussal dolgozik, 1000 kikérése épp 10x annyi idő a fenti select-tel. Postgres-nél egyébként már 100-as batch-eknél sem az RTT gond, hanem az, hogy a postgresql túl lassan bogarássza ki az eredményt.

MapReduce-t fehér folt egyelőre.

Az ilyenek nagyon meg tudják ölni az egészet: "(SELECT id FROM ways WHERE done=0 LIMIT 100)". Esetleg lehet erre egy bitmap indexet csinálni, de attól sem várnék túl sokat. Ha nagyon kell az SQL, akkor egyrészt csak egy táblát használnék, hogy ne kelljen JOIN (ha mindig egyszerre kell a ways és az összes hozzá tartozó nodes, akkor fölösleges szétszedni két táblára), másrészt nem státusz alapján keresnék, hanem key-range-ekre. Tegyük fel, hogy egy processz 1-től 1000-ig generált ID-kkal letárolja a sorokat, ekkor én 1..100, 101..200, ..., 901..1000 ID-kra szűrnék, ez indexből baromi gyors lesz. Persze valahol külön tudni kell, hogy melyik halmazokkal vagy már kész, de az nagyságrendekkel kevesebb adat. Ha jól kihajtod a PostgreSQL-t, akkor elég hamar észre kell venned, hogy a kommunikációs overhead lesz a drágább, és a nagyobb batch-ek sokat fognak gyorsítani.

De nekem amúgy továbbra is az hiányzik, hogy hogyan akarod az adatokat olvasni. Adatokat írni könnyű bárhova, de azt kellene tudni, hogy milyen szisztéma szerint akarod majd kiolvasni őket a feldolgozás után. Vagy félreértem, és valójában csak a fentebbi problémára keresel megoldást, tehát hogy a még feldolgozandó sorokat kiolvasd valahonnan? A sorrend mindegy, egyszerűen csak végig kell menni a teljes halmazon? Hol jön be az a rendezés, amit említettél? Máshogy fogalmazva: OSM-ből olvas valaki, és beírja egy táblába, abból a táblából valaki kiolvassa, csinál vele valamit. Ennyi a probléma, vagy az is kérdés, hogy az utolsó lépés után még valaki ír is valahova?

--

A feldolgozás utáni exportálás ugyanaz a szisztéma lesz mint maga a feldolgozás. A feldolgozás kiegészíti a Way.tags -t vagy beállít egy újabb értéket ha az hatékonyabb, ez mindegy. Tehát van írás, de csak a rekordok 1/10-edénél, ez már nem lesz probléma szerintem. Ha a feldolgozás hatékonyan el tudja érni az adatokat, akkor az exportálás sem lesz gond. A feldolgozásnál, exportálásnál az elemek sorrendje mindegy.

Hogy 1 sorra (táblára) hozzam össze az adatot felvetette azt, hogy:
a. ilyen alakra kell hoznom őket a loaderben ami jelentős memória, mert kb tárolni kell mindent, hiszen a nyersanyagban a way-ek és node-ok random sorrendben vannak (és akkor COPY-val tolhatom be az adatokat gyorsan) vagy
b. először a way-eket töltöm be adatbázisba és közben építek egy ilyen hash-t: $node_ways[node_id]->[way1_id,way2_id,...] - majd jönnek a node-ok és találat esetén SQL UPDATE, hogy hozzácsapja a meglévő rekordhoz a node-ot. Ez jóval kevesebb memória a loaderben, cserébe sok UPDATE, ami nem biztos, hogy hatékony.

Ez hívtam hevenyészve rendezésnek, bár inkább összerendelés.

A b. megoldással próbálkozom most, sikerrel. Bár a Ruby VM zabálja a ramot: 4.5M kapcsolat a fenti formában tárolva és valamiért 800MB RAM - pedig minden scalar integer. Az a. pont megvalósítása jóval több ramot követelne. Postgresql helyett most visszatértem a Redis-hez, mert ezzel a legnagyobb problémája ki lett iktatva.

Redis-ben először list-ként tároltam a node-okat a way-hez (RPUSH), amivel 2700 ways/s -t értem el a feldolgozásnál, a kliens oldal koppant fel cpu-ban. Aztán megnéztem azt, hogy csak string-ként tárolom és a kliensben magam split-elek elválasztó karakterrel: ez 7500 ways/s lett (és még mindig a kliens oldal koppan). Ez már egész jó. Sőt, így, hogy csak string az érték, batch-ben is le tudom kérni a way-eket (MGET), de ma már nem nézem meg, hogy ez mennyit segít.

Szóval update: még egyszerűbb lett az adatstruktúra, nincs szükség relációk kezelésére a DB-ben (bár a loaderrel majd kezdenem kell valamit, mert ez túl sok memória, de tegyük fel, hogy lesz megoldás). Viszont a 7500 ways/s még mindig nem az igazi, pláne, hogy mindez kb 140%-ot eszik a CPU-ból (kliens és redis-server együtt).

Van-e kb. annyi RAM egy gépben, amiben elfér az összes adat?

Ha igen, akkor be kő cuppantani az egészet, és memóriában rendezni - majd ha szükséges, rendezve visszaírni valami gyorsan olvasható struktúrába (pl. txt fájl, vagy sima bináris stream), ha nem szükséges, akkor nem is kell visszaírni.

Ha nagyságrendileg több adatról beszélünk, mint ami befér, akkor tessék valami normálisabb SSD-t alája rakni, mert mezei diszk a random I/O-ba belegebed.

Könnyű azt mondani. :) Ruby objektumokként tárolva biztos nem lenne elég a RAM, mert pocsékol. Nyers adatként, optimalizált formában talán, de legalábbis úgy nem sokkal nyúlik túl a fizikai RAM-on.

A hibrid megoldás tűnik életképesnek, hogy magát az adatot alacsony szintű mmap()-elt memóriaterületen tárolom igen tömör bináris formában, az indexeket pedig a ruby objektumokra bízom. Az mmap-olt terület random access-szel lesz írva (amikor a Node értékeit csapom a Way mellé), de ezt javarészt elnyeli a writeback cache. A txt formátum már jelentősen túlnyúlna a fizikai RAM-on.

Valamit megint nem értek: ha a nyersanyagban a way-ek és node-ok random sorrendben vannak, honnan tudod, mi tartozik össze? Nem látok idegen kulcs mezőt a diagramodon.

Amúgy továbbra is azt mondom, dobd az SQL-t/Redist. Ha befér memóriába, jó, Ha nem fér be, akkor sharding. Végigmész a nyersanyagokon, és felosztod őket pl. 4 felé, pl. id%4 vagy id/1000000 alapján 0,1,2,3 vödörbe mennek a way-ek, node-ok is. Az a fontos, hogy összetartozó way-ek és node-ok azonos számú vödörbe kerüljenek, ezért fontos a fentebb írt mondatom, hogy tudni kell előre, mi tartozik össze. Ezután feldolgozod a 0-s way vödröt és 0-s node vödröt full memóriában, stb. Evvel azt érted el, hogy nincs többé adatbázis overhead, és a diszk IO-t is tömbösítetted a folyamat elejére egyben. Sőt, ha az egyik adathalmaz esetleg már megfelelő (vödör szám szerinti) sorrendben van (érdemes eleve ez alapján generálni a vödör számot), akkor a másik adathalmazt kell előre felrobbantani, és az előbbi rendezett adathalmazt on-the-fly tudod olvasni, nem kell diszkre kiírni.

--

A way.nodes az idegen kulcs, frissítettem a diagramot, hogy egyértelműbb legyen.

Ezt még nem egészem értem, de a lényege az, hogy a forrásfájlt több körben dolgozzam fel? Ez is jó ötlet, ezzel tetszőlegesen csökkenhető a ram igény, cserébe a forrásfájl kell többször végigolvasni szekvenciálisan, de ez ésszerű kompromisszum. Milyen triviális és mégse gondoltam rá, thx. :)

Ha a nodes-ban lenne ways-re mutató idegen kulcs, az könnyebb lenne. Mert akkor szét tudnád dobni a nyersadatokat vödrökbe, és ezeket csak egyszer kellene végigolvasni, meg a vödröket is csak egyszer. (Értsd, beolvasod a nyersadatot, és szétdobálod N-felé mindkettőt. Ez egy olvasás-írás ciklus. Utána meg a kis fájlokat is egyszer olvasod végig darabonként, de itt már megvan az előnyöd, hogy tudod, hogy a 0-adik ways fájl a 0-adik nodes fájllal van párban, stb.)

Így viszont azt tudod csinálni, hogy pl. beolvasol 1 millió ways-t, végigolvasod a nodes fájlt a párok után kutatva. Utána még 1 millió ways, még egyszer végigolvasod a teljes nodes fájlt. Stb.

--

( carlcolt | 2015. 05. 31., v – 14:33 )

Postgres-ben megneznem hogy biztos nem tudok-e egesz veletlenul a letezo osszes query-zett tablaban primary key-re is szurni (ha nem is az osszes query-ben, talan ha mar a 90%-uk csak a legujabb adatokal dolgozik, mar sokkal elorebb vagy), leven mindig az a szures a leghatekonyabb es az fut le eloszor (pl. done=0-nal nem lehet hogya z csak a felso 10%-a a primary_key ID-nak?)

Ugyanakkor szerintem szetszednem a ways.tags[]-et ways_tags tablara, a sajat primary key-evel, idegen kulccsal a ways id-jara es a tag-gel ami text. Es arra is megprobalnek primary key-re szurni amikor csak lehet. A ruby programban tarolod meg frissitgeted a primary key hatarokat, esetleg meg egy daemon is mehet benne.

Persze az is kerdes hogy a "Jó sok ilyen kapcsolat van" mit takar? Mert amit en irok az akkor segit latvanyosan ha 10^n es n>=6 sorosak a tablak.

Ja es most nezem csak: json. Postgres-ben oke, hogy van json tamogatas, de lassu. Nem tudnad inkabb azt is relaciosan tarolni?

( Batman | 2015. 05. 31., v – 14:32 )

Szeva,

Esetelg meg tudod osztani az általad használt tábla strukturáját és esetleges minta adadtokat is, végeznék pár tesztet. De a query amit írtál az nem egyezik a képen látható struktúrával ezért kérem ezt..

Postgresql-ből nem vagyok teljesen naprakész de talán hasonlóan működik ez a része mint Mysql-nek.
Szóval összejoinolod a ways-t a way_node_links-et és a nodes táblákat, majd ezekből kiveszed azt ahol a ways.done=0. Ez így szerintem elég felesleges.

Van 4M ways amint 80M nodes-al joinolsz össze majd nem tudom mennyi done=0 van de ha mondjuk félmillió akkor akkor felesleges a többi 3.5 millio join.(fáleg hogy limit 100-at használsz szóval lényegében 100 hasznos join kell neked a 4M helyett)

Szóval elöbb kellene kiszelektálni azt amire tényleg szükséged van és ahoz joinolni. Valami ilyesmi:

SELECT ways.id, ways.tags, json_agg(nodes.lat) AS lats, json_agg(nodes.lon) AS lons, json_agg(nodes.ele) AS eles, json_agg(nodes.ref_cnt) AS ref_cnts
FROM (SELECT * FROM ways WHERE done=0 /*limit 100*/) as ways
LEFT JOIN way_node_links ON way_node_links.way_id=ways.id LEFT JOIN nodes ON nodes.id=way_node_links.node_id
GROUP BY ways.id

A queryt nem probáltam ki de talán nem syntax hibás :)

> Szóval összejoinolod a ways-t a way_node_links-et és a nodes táblákat, majd ezekből kiveszed azt ahol a ways.done=0

Azt hiszem ezzel fején találtál valamit. Azt gondoltam, hogy a postgresql magától kitálja, hogy előbb a done=0 -ra szűrjön limittel, majd joinoljon (indexek megvannak hozzá), de erre magától nem képes..?

Eredetileg ezzel próbálkoztam: 


SELECT ways.id, ways.tags, json_agg(nodes.lat) AS lats, json_agg(nodes.lon) AS lons, json_agg(nodes.ele) AS eles, json_agg(nodes.ref_cnt) AS ref_cnts
FROM ways LEFT JOIN way_node_links ON way_node_links.way_id=ways.id LEFT JOIN nodes ON nodes.id=way_node_links.node_id
WHERE done=0
GROUP BY ways.id LIMIT 100

Mindenesetre most változott a feladat ezen része azzal, hogy 1 táblára redukáltam a dolgokat.

"Azt gondoltam, hogy a postgresql magától kitálja, hogy előbb a done=0 -ra szűrjön limittel, majd joinoljon (indexek megvannak hozzá)"

Eledobsz egy EXPLAIN-t, es kiirja, hogy mit hogy mivel csinalna.

--
I'm not saying the new Apple Watch will only be worn by wankers but it's not vibration, shock and splash proof for nothing.

Esetleg ha nem az elvárt utat választaná, megnézni, hogy az előszűrtnek szánt adathalmaz view-ba generálása változtat-e az optimalizáló hozzáállásán.

(De mindenképpen kötelező elolvasni buckó kolléga gondolatait - lehet, hogy nem általános megoldást tartalmaznak, de akinek adottra kellhet valaha jól teljesítő, az jegyezze fel, bármit is nevezünk az adott 24 órában trendinek.)

( asch v | 2015. 05. 31., v – 15:43 )

Érdemes ezeket elméletileg végiggondolni először: milyen fajta keresés milyen adatszerkezetekkel mennyi ideig tart elméletileg? Beleférünk-e a CPU cache-be vagy a RAM-ba? (Abból kell kiindulni, hogy a RAM sokkal gyorsabb bármilyen háttértárnál, és ennél is sokkal gyorsabb a CPU cache.)

Ha belefér a RAM-ba, akkor mindenképpen jól jársz, ha betöltöd az egészet a lekérdezések előtt. Első megközelítésnek szerintem a legjobb az adott programozási nyelv objektum modelljét használni a betöltéshez, és a collection framework adta lehetőségekkel felvenni rá kereső adatszerkezeteket (indexeket). De ha épp határeset, hogy beférsz-e a memóriába, akkor még egy bare-metal adatszerkezet kialakítása is megérheti. Olyan, amiben tényleg semmi sallang nincs, pont annyi bitet tárolsz, amennyit muszáj.

Ha nem fér bele az egész a RAM-ba, akkor nagyságrendileg lassabb lesz minden lekérdezés. Ha ez nem elfogadható, akkor trükközni kell. Ebben az esetben én megpróbálnám földrajzi hely szerint szeparálni az adatokat. Magyarul kijelölnék téglalap alakú területeket, amiknek az adatai egyben tárolódnak. És minden algoritmust úgy kell megcsinálni, hogy ezeket tudja kezelni, úgy tudjon utat keresni, hogy csak a környékbeli darabokat tölti be. Lehet azzal is trükközni, hogy egy teljes úthálózatot redukálsz egy ponttá, amin belül már eleve megkerested a legrövidebb utakat az összes bejárata és kijárata között, és csak azt használod amikor útvonalat keresel. Pl, ha nemzetközi útvonalkeresést csinálsz Európán belül, akkor minden ország minden határátkelője egy csomópont, és a közöttük lévő szakaszok a legrövidebb utaknak felelnek meg. Azt, hogy hány ilyen szintet érdemes felvenni, azt néhány méréssel ki lehet találni. A lényeg az, hogy úgy tudjon működni az algoritmusod, hogy az adatoknak csak egy kis részét kelljen betölteni/végigtúrni.

Én sok éve szórakoztam az OSM adatbázissal. Az akkori gépemnek 500M memóriája volt, az akkori adatbázis letölthető dumpja 4G körüli. Én csak megjeleníteni akartam szeleteket belőle. Ezt úgy csináltam, hogy az adatokat végigolvastam, és földrajzi hely szerint szűrtem arra a környékre, amit meg akartam jeleníteni. Ami maradt, azt már be tudtam tölteni a memóriába, és egy naív algoritmussal meg lehetett jeleníteni.

Ha csak az utakat akarod használni, akkor az is segíthet, ha minden mást egyből kidobsz az adatbázisból.

Optimális adattípusokkal biztos befér a RAM-ba, ez nem probléma.

A részfeladatokat (betöltés/feldolgozás/exportálás) nem akarom egy processzben elvégezni, mert minden lépésnél sok időt elvisz majd az adott feladat optimalizálása és nem lenne praktikus ha az adatokat minden tesztnél újra és újra fel kellene építenem a korábbi lépések futtatásával. Az IPC elkerülhetetlennek tűnik.

Hm, bare-metal adatszerkezet: mmap-elt fájl? Most jutott eszembe! A Way betöltésénél már tudom, hogy pontosan mennyi memória kell majd neki, aztán ahogy megtalálom a Node-okat hozzá, csak szépen teszem be őket a helyükre és így rések nélkül fel tudom tölteni a memóriaterületet. Hogy tudjam melyk node-nak hol a helye, ahhoz építek egy indexet a memóriába, az kezelhető méret még ruby objektumokkal is. :)

Bár azt nem tudom előre, hogy mennyi kapcsolódó adatot akar rögzíteni a rekordhoz a feldolgozás, de a kettő végülis független probléma, nem muszáj egyben kezelni.

Ez most hirtelen nagyon megtetszett, közel nulla overhead, köszi az inspirációt. :)

( atomheart v | 2015. 05. 31., v – 15:45 )

Valamilyen graf adatbazis, pl. Neo4j?

----------------------
"ONE OF THESE DAYS I'M GOING TO CUT YOU INTO LITTLE PIECES!!!$E$%#$#%^*^"
--> YouTube csatornám

( uid_194 | 2015. 05. 31., v – 18:05 )

Mivel a nodes csak ket double es egy ID, biztos vagy benne, hogy kell neki kulon tabla? (Igen, igen, helypazarlas, de diszk olcso).

Tetszoleges document store jo lehet, talan MongoDB-t kiveve. Esetleg Riakot javasolnek, azzal relative jol meg lehet ezt. Talan Redis is jo lehetne, ha nem kulon tarolnad a nodeokat.

Persze komplikalni tudja a helyzetet, ha a kulonbozo wayekhez kesobb hozza akarsz fuzni, de nem veszesen.

Szoval en dobnam a kulon tablas elkepzelest, ebben az esetben az tobbet art, mint amennyi haszna van.

--
|8]

( Nyosigomboc v | 2015. 05. 31., v – 22:31 )

Pont a lenyeget nem fejtetted ki, hogy mi az a bizonyos feldolgozas. Az algoritmusodtol fugg, hogy milyen hozzaferesre erdemes optimalizalni, es egy csomo minden mas is. Ezen kivul az algoritmus optimalizalasa (pl. jobb, tobb hatterinfot kihasznalo) algoritmus hasznalata rengeteget tud segiteni. Mas az, ha teljesen altalanos grafban keresel minimalis osszsulyu utat, es mas, ha terkepen. Ld. A* helyett HNR.

Ami ennek ellenere mar latszik: Ha jol ertem, utcaid vannak. Ha a lat/lon double helyett 1-1 32 bites szam lenne (fixpontos), akkor worst case-ben 9mm pontossaggal le tudod tarolni. (40000000.0/(2**32)=0.009313225746154785 az egyenlitonel). Mivel ebbol van a legtobb (80M) node, ez foglalja a legtobb helyet, ezt lecserelve lazan beleferhet a memoriaba a teljes adathalmaz (ha 64 bites a geped, akkor enelkul is, a processenkenti cimter a kritikus, az tippre 2G alatt van). Ha foldrajzilag egy eleg zart helyrol szarmaznak az adataid, akkor ennel is jobban meguszhatod (ha pl. BP utjaira vagy kivancsi, akkor fogsz egy befoglalo teglalapot, es felosztod a koztes reszt a kritikus pontossagodnak megfelelo reszekre). Esetleg hasznalhatsz MGRS-t Grid Square ID nelkul, ha belefersz.
Ha a ruby nem pazarolja a memoriat tul trehany modon, akkor indulaskor betoltheted az egesz DB-t, feldolgozas utan meg kitorlod az egeszet.

--
I'm not saying the new Apple Watch will only be worn by wankers but it's not vibration, shock and splash proof for nothing.

( wachag | 2015. 06. 01., h – 09:34 )

ha nincs szükség perzisztenciára, esetleg VoltDB? (Most szemezek vele)

( freeoli v | 2015. 06. 01., h – 12:31 )

Saját tapasztalatból indulok ki. Mi egy nagyon más célból de a SOLR-t használjuk egyszerűen strukturált nagymennyiségű, összetett, xml adatok tartalmában azok közti tetszőleges keresések végrehajtására. Összesen kb 2M dokumentum 5Gb mennyiségben 1-2 ms válaszidővel. A fenti sebességet komplexebb keresések esetén is tudja tartani, képes a keresési feltételek értékei közt képes tartományokat, wildcardokat, stb is kezelni. Jól skálázható, nagyon gyors, stb.

A kérdező egy darab nagyon speciális lekérdezést akar csinálni, de azt nagyon gyorsan. Nagyon kicsi a valószínűsége, hogy egy teljes értékű, bármilyen lekérdezést támogató általános tároló rendszer hozza azt a sebességet, amit egy célra optimalizált egyedi megoldás. Persze utóbbit több munka beizzítani, de valamit valamiért.

--

( bucko | 2015. 06. 01., h – 16:58 )

Ha ezek a kiinduló adatok:
- ways: kb 4M objektum
- nodes: kb 80M objektum
- feldolgozás elvárt sebessége: 10.000 ways/s/processz

Következik:
- nodes/ways=20 (átlagosan), azaz 10.000 ways/s + 200.000 nodes/s
- legyen egy bika processzor - 64 thread -> 210.000*64 = 13.440.000 elem/s
- feldolgozási idő = 4M/(64*10.000)13M = 6,25s
- a minimális méret, ha minden elem 32bit INT
ways: 92 bájt
nodes: 12 bájt
egy struktúra: 332 bájt
- adatméret: 4M * 332 = 1,33GB
- minimális sávszélesség (feldolgozási sebesség): 1,33 / 6,25s = 0,2048GB/s
- egy elem olvasási ideje (átlagosan): 74,4ns
- egy bájt olvasása (64 bites buszra vetítve): 37,7ns

Mivel nem tudjuk min fog futni - vajon hol a szűk keresztmetszet?

A Way-nek van egy tags:text[] tulajdonsága is, ami átlagosan kb 160 bájt adat és nem említettem néhány mezőt a Node-on, hogy egyszerűsítések (ami int4-en és int2-n tárolható). Illetve egy Node több Way-hez is tartozhat, a kapcsolatok száma tehát nem 80M, hanem kb 120M. A Way.id és Node.id 64 bites, erre se tértem ki. Ez az aktuális állapot, a jövőben ezek a számok növekedni fognak valamenyit.

Egyébként 64db mag helyett 4db van és mellé max 6GB felhasználható RAM és SSD.

Megcsináltam sima fájlműveletekkel (az mmap-ot nem támogatja a ruby natívan): a feldolgozó az adathoz optimalizálás nélkül 70.000 ways/s/processz sebességgel jut hozzá, ez pedig már bőven elég neki.
A "sorter" (volt loader) párhuzamosan fut, processzenként 1 fájlt állít elő (így nem kell lockolni írásnál ahhoz, hogy tudjam, hogy a rekord milyen bájtpozícióra került). A feldolgozó szintén több processzel dolgozik a fájlokon.

A sorternek van egy említésre méltó memóriaigénye, mert 3 hashtáblát is épít: 


# ez alapjan tudjuk, melyk sorba kell irni
$node_ways = {}
# ez alapjan tudjuk, hogy hanyadik oszlopba kell irni
$way_nodes = {}
# ez alapjan tudjuk, hogy egy sor hanyadik byte-nal van az output-ban
$way_pos = {}

Ha túl nagyok lennének ezek a hash táblák, akkor a forrásfájlt több körben dolgozom fel. Ezzel vesztek valamennyi időt, de nyerhetek egy csomó memóriát - egy darabig megéri.

Szerintem ez a jó megoldás, köszi a tippeket, magamtól talán még mindig az adatbázisszervereket tesztelném.

Tehát akkor az adatméret:
ways: 92+21*4=176 bájt => pointerek 21*8=168, azaz 95%
nodes: 332+20*10=532 bájt => pointerek 20*8=160, azaz 30%
A százalékot még lehet súlyozni az egyes adatfajták függvényében.
Miarossebről írogatok?! Az Oracle azért vette meg a BerkeleyDb-t mert pont azt tudja, amit az sql nem!
Ez a feladatot tipikusan nem sql-ben kell megoldani. Egy-egy lekérdezésnek nem lista a végeredménye. A modern (leszaromaméretet) 64 bites pointerek auto id-k feleslegesek, hiszen nem egy karbantartó rendszert készítesz. A relációk száma is elég kevés, mint ahogy rajzoltad is. A pointerek legtöbb esetben egyáltalán nem kellenek!

Nem említettem a tags-et, mert azt úgy is tagonként (szavanként) kell indexelni. A változó hossz miatt érdemes külön táblába tenni, és tömöríteni. Ettől nem a mérete lesz kritikus, hanem a kb. 100M indexe.

Ennek a végeredménye egy egyenközű, rövid bájtsorozatoból álló rekordokat tartalmazó tartalmazó "tábla". Az "auto id", maga a pozíció/rekordhossz.
8X---
Számoltam egy kicsit, és az jött ki, hogy egy ilyen adatbázisban
(2magos, 1,5GHz POWER5 - 4 thread - az alap, ez ugye 2003-as technnológia)
- rekord keresési idő < 2us
- méret - úgy saccra - < 500MB
- adatbázis előállítása - úgy saccra - < 15perc
8X---
A rendelkezésre álló thread számot úgy érdemes felosztani, hogy
- meg kell becsülni a jelentős terhelést okozó processzeket
- meg kell becsülni az io és egyébb mellékes feladatok számát
A fent kettő összege <= rendelkezésre álló thread szám.
A felesleges thread switch jelentős lassulást eredményez, tehát ilyen feldolgozás futtatásakor törekedni kell az egy processz - egy adathalmaz elosztásra. De mintha ezt pont így csinálnád.
8X---
A "sorter" -> A fenti ésszerűsítések mellett az adatok könnyedén elférnek a memóriában. Innentől kezdve file írogatás helyett egy betöltés alatt el lehet végezni az összes feladatot. És kell az mmap!
A hátrányok:
- nem használhatsz ruby-t, sql-t
- nincs "kész öt perc alatt"
Előnyök:
- mindennek ellenére hordozható marad - már ha igény
- jól átgondolva a korlátokkal rendelkező adatstruktúrát optimális megoldás készülhet
- az "öt perc alatt kész" megoldással szemben nem kell évekig csiszolgatni
- nem kell fórumon mindenféle marhaságot megtudnod olyanoktól, akik még soha nem csináltak ilyet

(Ronda drogos banda! Jobbra-balra dzsóintok hevernek! ;)))

Egyetértek, de egy dolog kimaradt, a skálázódás. Az "ez még pont elfér a memóriában" elég hamar oda vezethet, hogy eléggé át kell írni. Tfh. bejön még egy nagyságrenddel több adat, vagy kicsit nagyobb lesz egy-egy rekord, és egyszer csak nem fog elférni. Ilyen nagy adathalmazoknál általában kell valamiféle shardingra is gondolni. Kivéve, ha hobby projekt, és tényleg sosem lesz több adat a mostaninál.

--

Jajjdehogyisnem! Csak nem olvastál elég alaposan!
Egyrészt topicnyitó barátunk említé, hogy jól megugrott a ruby memóriazabálása. Valamint a ruby nem támogat mmap-ot.
Én viszont azt írtam, hogy
- az optimalizált adatbázis befér a memóriába, és
- kell az mmap!
Komolyan bízok abban, hogy tudod mi az a mmap! Ha nem, vagy csak arra vagy kíváncsi, hogy én miként használtam, akkor szívesen leírom.

Ha ez a ways-route nem a Stargate univerzumon belüli adatokat ábrázolja, nos akkor igen jól megbecsülhető az adatok darabszáma. Így van ez a földrajzi adatokkal, meg a telefonszámokkal. Erre írtam egyszer, hogy elegendő - hacsak el nem foglaljuk a Szovjetúniót. :)

Ha a skálázódáson azt érted, hogy "gőzöm sincs mit csinálok" - akkor igazad van.
Üzemeltettem szakértők által tervezett rendszert, amelyik a tervezett méret 300%-val ugyanúgy dolgozott.
Aztán láttam ifjú sql titánok által megvalósított rendszert (figyeled: nem tervezettet írtam), ami az elvárt méret 30%-a esetén 15x lassabb volt, mint az előző elavult hardveren futó. Majd megszakadtam a röhögéstől, mert mindig éppen akkor, amikor bent jártam a cégnél, jelent meg egy emberke a főnöknél: írd már alá a memóriabővítést! No, látod, EZ egy skálázható rendszer volt! ;)

A hobby projekt és az adatmennyiség között nincs összefüggés.
Történetesen dolgoztam a topicnyitó adatainál kicsit kevesebb adattal, mégozzá az USA tudakozóját kezelni képes adatbázissal, illetve a környezetét programoztam. Ennél pl. szinte tetszőleges adatmennyiség és tetszőleges operátorszám mellett garantált idejű volt a lekérdezés. Sem sql, sem Descartes-szorzat nem járt a környékén, mert az rengeteg erőforrást igényelt volna.

Tudom, mi az az mmap, hasznos, de nem csodafegyver.

Elismerem, hogy a problémák nagy része jól megoldható memóriából. De ha megírtál egy szoftvert, ami tök jól elvan 7 GB adattal, és memóriában mindent jól megold, majd egyszer csak 70 GB adatot kell feldolgoznia (lehet túlzás, lehet valós), akkor elég sok új trükk fog kelleni, hogy működjön. Ha csak szekvenciálisan írsz-olvasol, akkor tök mindegy, mennyi az adat, arányosan tovább fog tartani, de működnie fog. Egyéb esetben még az is előfordulhat, hogy alapjaiban újra kell gondolni az egész algoritmust.

Ha SQL szerverben vagy hasonlóban oldottad meg, akkor jó esetben elég sok nagyságrendi növekedést kibír a rendszer, pont arra lett kitalálva, sokszor csak adni kell alá a diszket és megy tovább. De ez sokszor nem adja a legjobb performanciát.

Mennyiségileg fogalmam sincs a térképészetről, de abban biztos vagyok, hogy nem kell kimenni az univerzumból, a térképek mérete folyamatosan növekszik, csak nem tudom, mennyire. Új utakat építenek, régi utakat vesznek fel a térképre, az utakat pontosabban, 2x-5x-10x annyi köztes koordinátával egyre részletesebben ábrázolják, új helyek jönnek létre, stb.

--

Az adatmennyiség növekedése miatti agodalmadra már feljebb megérkezett a válasz.

Ekkora adatmennyiségnél, ha sql-ben megoldható - azaz a szerver képes működni az adott memóriában - minden bizonnyal legfeljebb tizedannyi memóriára van szükség. Talán sokkal kevesebbre.
Pl. a 2x double helyett 2x int4 helyett 1x int4, az id helyett semmi - ezzel pl. 24 helyett 4 bájt lesz a tárolás. (Le van írva, hogy hogyan. Nem én találtam ki!)
Persze ilyenkor az indexek és segédtáblázatok többen lesznek, mint az adatok.

A sebesség nem arányos, mivel indexelük, ezért a növekmény az n*log2(n) függvénnyel becsülhető. Ha az adattömeget jól tudod darabolni, akkor ennél jobb az arány. Ami kérdéses a szöveg indexelése, de azt sosem olvasom be, így mindig befér. :)

Mondok kis példákat.
1) Számhordozási/jogosultság adatbázis - adattartalom:
- telefonszám - 201234567
- szolgáltató
- hordozás ideje - ha van
- előző szolgáltató
- előző hordozás ideje
- hozzáférés engedély A szolgáltatáshoz
- hozzáférés engedély B szolgáltatáshoz

Telefonszámok 14M, hordozások 0,5M.
Adatbázis méret: 10MB
Lekérdezési idő: 120-160ns (1,5GHz POWER5)
Előállítási idő: nem futott egymagában, így a <90s feldolgozási idő növekménye néhány s volt.
Memória igény: 40MB előállítás / 12MB lekérdezés - betöltöm

2) Cím adatbázis
- telefonszám
- helységnév - Budapest
- településrész - XX. kerület
- irányítószám
- cím - Ordas lakótelep 12. III. emelet 5.
- cím pontatlan - ez egy bool

Címek 3,5M
Adatbázis méret: 50MB
Lekérdezési idő: 160-220ns
Válaszidő http szerverként: 220-250us - a lekérdezés naplózásával együtt! (O_SYNC)
Előállítási idő: 35s kb. 1GB adatból.
Memória igény: 100MB előállítás / 2MB lekérdezés

A helymeghatározás a kétirányú indextől eltekintve nem sokkal bonyolultabb, mint a két példa. Azért gondold végig, hogy ezeket a 8-10 éves példákat sql-ben hogyan valósítanád meg és milyen erőforrásokkal!

( dap | 2015. 06. 03., sze – 02:43 )

Hát. Funkcionálisan hamar megvoltam, de most, hogy a végleges adatmennyiségen dolgoznék, a ruby komoly szopóroller lett. Csak a forrásfájl (.pbf) értelmezését segítő library közreműködése felzabbant 1.5 GB memóriát processzenként mire végigér a fájlon, akkor is, ha hozzá se nyúlok az adatokhoz. Sehogy nem tudom megkerülni. Áshatom elő a C tudásom..

Egyébként először HDD-re próbáltam kiírni a sorter kimenetét, elég hamar megmakkant tőle, random write, ugye. SSD-vel megoldva.

Hanyszor akarod ezt a konverziot eljatszani? Nem egyszerubb keriteni egy megfelelo gepet 1 napra (vagy felloni cloudba), mint szopni vele egy csomot? (persze ha sokszor kell, akkor celszeru gyorsra megirni, ha egyszer, akkor felesleges)
Egyebkent az meg mindig nem derult ki, hogy mit akarsz csinalni azokon az adatokon.

--
I'm not saying the new Apple Watch will only be worn by wankers but it's not vibration, shock and splash proof for nothing.

Most 4 processzel olvasok, darabjaval 1M utat, ez 1GB memoria/processz, azaz osszesen 4GB. Epp idealis. Ha szekvencialisan akarnam irni, azaz mindent ramban tartok az uccso pillanatig, akkor szerintem ennek a memorianak tobbszoroset enne meg a ruby. Igazabol a random write-tal semmi gond, ezert van az SSD. A szekvencialis iras osszessegeben lassabb feldolgozashoz vezetne, mivel meg tobb node scan kor kellene (es egy node miss csak 5x kevesebb ido mint a node hit, tehat nem olcso).

Mint kiderült, ez szivatott meg: https://bugs.ruby-lang.org/issues/11164

Fork()-olgattam, mert az optimalis az lenne ha 1 processzben epitenem fel a hash tablakat (ez viszonylag gyors), majd N processzel scanneltetnem vegig a node-okat, igy 100%-os hit ratio-t elerve (mert a node miss sem tul olcso).
Igen am, csak a ruby nem hasznalja ki a copy-on-write -ot, ezert a nagy (read-only) hash tablak megtobbszorozodtek a ramban. Eloszor nem ismertem fel hogy valojaban ez a gond, mert nem egyik pillanatrol a masikra lesz bloated a forkolt processz, hanem idovel, ahogy a GC dolgozgat. Azota viszont egyertelmu minden.

Most azt csinaltam, hogy kikommenteztem a forkolast, optimalizaltam a node miss feldolgozast, aztan ha ezt a bugot fixelik, majd visszateszem, elvileg nyerek vele valamennyit. Cserebe igy a ways beolvasasa is tobb processzel megy, ott meg nyerek is, csak kesobb elvesztem az elonyt a node miss-eken.

( dap | 2015. 06. 04., cs – 20:10 )

Update: kesz, mukodik es kb skalazhato a vegtelenbe. A teljes folyamatot tekintve lassabb lett mint amit akartam (3 kWays/s), de a ruby erre kepes, a 10 kWays/s irrealis lenne. Innen mar csak vas illetve nyelv kerdese.

A sorter lett a folyamat leglassabb pontja, 17 perc, a feldolgozas csak 7 perc.