relacios adatbazis - gyors

olyan rdbms-t keresek, amelyik egyszeru (de nagy meretu, 10-20M rekord) tablak eseten

* (nagyon) gyors: sok (egy session-ben cca 500-1000 egyszeru) select, valamennyi update, ezekhez kepest keves insert

* (relative) egyszeru API C-nyelven

* tobb parhuzamos session tamogatasa (select, update, insert)

* lehetoleg open source es free

* az adat(bazis) ne valjon korruptta, vagy lehessen valahogy javitani

Hozzászólások

Nem vált be a MySQL a Clapf alá?

--
Sokan nincsenek tudatában annak, / hogy egyszer mindenki meghal. / Akik ráébrednek erre, / azonnal abbahagyják az ellenségeskedést.

Azt tervezem, hogy a kovetkezo stabil verzioban meg nem, de a 0.3.30-ban mar levaltom a CDB-t - nagyon szorit az, hogy read-only, es ehhez keresek egy stabil, gyors es konkurens elerhetosegu backend-et.

A sajat gepemen teljesen jo a MySQL, egy atlagos level 1-2-300 ms alatti kategorizalasa (attol fuggoen, hogy hany tokent talal benne) fel sem tunik havi par ezer levelnel. Es ha visszaallnek a Train On Error tanitasra, akkor a mysql cache is jobban ervenyesulne (de ebben a honapban a masik tanitasi modszert tesztelem. Es ahogyan bra ramutatott, amint tortenik egy write, egybol oda a cache).

A cel azonban az, hogy a clapf nagyobb kornyezetben is megallja a helyet. A clapf spamszurot (egyelore) nem egy isp szintu kornyezetbe (500-1000k user, n x 10^6 level/nap) pozicionalom :-), hanem mondjuk ennek a tizedere (es akkor tuti rohogve elvisz 1k felhasznalot napi n x 100k levellel egy kisebb magyar kornyezetben).

Ehhez 1. lepeskent azt szeretnem elerni, hogy ~50 ms korul legyen a statisztikai elemzes ideje (a level elolvasasatol kezdve a token adatbazissal valo konzultacion keresztul a spam valoszinuseg kiszamitasaig), es hogy egy ora alatt 100k levelet kepes legyen atereszteni postfix-szel - ahol parhuzamosan tobb level feldolgozasa tortenik. Ezert gondolkodom 1. korben egy kliens-szerver alapu rdbms-ben, hogy ne nekem kelljen pl. lock-kolassal, meg egyeb ilyen nyalanksagokkal izzadnom.

Jelenleg az sqlite3-at probalom, ami ~560k rekord eseten amig egy sok tokent tartalmazo levelet mysql-lel nem birtam ~650ms-nel gyorsabban elemezni, addig az sqlite3 kb. 50-60ms alatt elvegezte a 2365 select muveletet. Csak 1 baj van vele: a doksija szerint "SQLite is not intended to be an enterprise database engine", es a kozos adatbazis paralel iras/olvasasa gondot okozhat. Ezt pl. ugy tudom kikuszobolni, ha minden felhasznalonak sajat token adatbazisa van mondjuk a $HOME alatt, es azert ritka az a felhasznalo, aki (az sqlite3 doksi ovatos becslese szerint napi 100k hit belefer) 100k levelet/nap kap. Ez meg annyi plusz macerat jelenthet, hogy ebben az esetben maildrop-on keresztul kell futtatni, es nem postfix after-queue content filter-kent. Egy crash teszt majd segit eldonteni a dilemmat.

De addig hatha valaki eloall AZ adatbazissal, ami erre a celra a leginkabb megfelelo :-)

ASK Me No Questions, I'll Tell You No Lies

Most olvastam csak a szálat és sorban, így nekem is a BDB jutott eszembe (lentebb volt róla szó, ezért töröltem).
Egy komoly hátránya lehet: ha több gépet használsz és meg kell oldanod a szinkronizációt, vagy átjárhatóságot.

Lehet hogy most csúnyán fogsz nézni rám, de közvetlen BerkeleyDB nem lenne neked jó? Tény hogy nem SQL, de pont ez az erőssége ;)
--
- Miért jó a mazochistának?
- Mert ha rossz, akkor jó. Ha meg jó, akkor rossz, tehát jó.

Ugy hallottam, hogy nagy rekordszamnal mar nem eleg gyors, ill. hogy idovel korruptta valhat az adatbazis, plusz a konkurens hozzaferest neked kell valahogy lekezelned. Az SQL-ben az a (nagy) konnyebbseg, hogy te csak kiadod az sql utasitasokat, a tobbit meg oldja meg backend.

ASK Me No Questions, I'll Tell You No Lies

Hát amikor utoljára programoztam C-ben (2002), akkor egész jól bírta a konkurrens thread-ek támadását(van benne tranzakciózás), ráadásul elég komolyan fejlesztik(ezért vette meg az Oracle és maradt openszósz). Nagy rekordszám alatt nem tudom mit értesz, de 1-2 millió rekorddal már próbáltam és az égvilágon semmi gondom nem volt vele. Nyilván optimalizálni kell a hozzáférést, de hát ez egy beágyazott adatbázis. Ha erre nem akarsz/tudsz időt fordítani akkor jöhet jól az SQLite. Nyilván az SQLite-ban ráfizetsz az SQL plan-re minden lekérdezéskor(kiv. prep stmt) és még azon túl is lesz overhead.
Korrupció? Nagyon sok sz*r BDB-s alkalmazást láttam. Ha nem szánod rá az időt, ne használd. Csalódni fogsz(Subversion BDB backend kódja. No comment). Valóban nem bolondbiztos, de ez a szép benne

Oracle Berkeley DB - The World's Most Popular High Performance, Embeddable Database

--
- Miért jó a mazochistának?
- Mert ha rossz, akkor jó. Ha meg jó, akkor rossz, tehát jó.

Mit szolsz az SQLite-hoz?

* (nagyon) gyors: sok (egy session-ben cca 500-1000 egyszeru) select, valamennyi update, ezekhez kepest keves insert ,

szerintem ez menne neki.

* (relative) egyszeru API C-nyelven

Tudtommal ez is adott

* tobb parhuzamos session tamogatasa (select, update, insert)

Ha jol emlexem tabla, es DB (fajl) szintu lockokkal operal, probald kerulni az olyan hosszu tranzakciokat, amiben iras van, es akkor nem lesz gond.

* lehetoleg open source es free

Open source es free, de van hozza penzes szupport, es egyeb nyalankgasok, pl encryptalt fajl formatum...

* az adat(bazis) ne valjon korruptta, vagy lehessen valahogy javitani

En nem talalkoztam meg korrupt sqlite dbvel.

PostgreSQL. Ha jól megtervezed az adatbázist, akkor piszok gyors. Kevés rekordnál lomhának tűnhet a mysql vagy az sqlite mellett, de az a jó benne, hogy ha _nagyon_ megnöveled az adatbázis méretét, akkor nem lassul, csak nagyon keveset.

A C apija nagyon egyszerű, még nekem is sikerült elsajátítanom.

Párhuzamosság: lehet, egyébként a transaction-jai nagyon jók.

free és open source: adott

az adatbázis nem válik korrupttá, viszont ha frissítesz (vagy backupolsz), akkor ökölszabány: pg_dump{,all} használata. Csak ezt. Max bzippeled, de soha és soha ne a nyers adatfájlokat piszkáld.

---------
WARNING: Linux requires you to type! After rebooted to Windows, you can safely unplug your keyboard.
szerény blogom -- új címen!

A sebesseg kritikus szempont. Egy egyszeru indexelt tablan mennyi ido alatt tudsz lefuttatni cca. 2000 select-et, ha van a tablaban vagy 500k-1M rekord? Hasznalhatsz cache-t, akarmit a minel gyorsabb mukodes erdekeben.

create table if not exists t_token (
token bigint unsigned not null,
uid smallint unsigned default 0,
nham int default 0,
nspam int default 0,
unique(token, uid)
);

create index t_token_idx on t_token(token, uid);

s elect nham, nspam from t_token where token=1 and (uid=0 or uid=1001)

ASK Me No Questions, I'll Tell You No Lies

Ha sebességre gyúrsz, akkor sima index helyett primary key alapján kellene keresned. Egyáltalán nem értek ahhoz a felhasználási területhez, ahol te mozogsz, de jobb RDBMS-ek esetén a keresési idő egyszerűen nem függ a rekordszámtól, feltéve ha index, főleg elsődleges kulcs alapján tud keresni. Nem tudnád így felépíteni az adattábláidat? Kifejezetten odafigyelve arra, hogy kizárólag elsődleges és külső kulcsok alapján keress?

A másik fontos dolog az RDBMS hangolása. Figyelj oda arra, hogy a PostgreSQL alap installja olyan konfigurációs fájlokkal érkezik, amelyek minimális memóriát engedélyeznek a postmasternek. Ez is nagyon fontos lehet a keresésnél. Nézd meg a postgresql.conf-ban a # - Memory - szekciót.

A harmadik dolog a hardver. RDBMS-ek alá soha nem tudsz túl sok memóriát tenni. És inkább költs plusz 60-100 kHUF-t memóriára, mintha lemondanál egy korszerű RDBMS-ről, és izomból próbálnál megoldani dolgokat - szorozd fel a rezsióradíjaddal.

Bocs, ha konkrétumokkkal nem tudtam szolgálni...

Legalabbis mysql alatt a "unique(token, uid)" resz alapjan ennek a 2 mezonek kulcsnak kellene lennie (es e 2 alapjan keresek). De ha javasolsz egy masik (es jobb) semat, azt megkoszonom. Egy adott token kulonfele uid-dal is szerepelhet, es egy uid-hoz sok token tartozhat, de a token+uid garantaltan unique. Jelenleg ugyan nem postgresql-t hasznalok (hanem mysql-t), de nezem meg a konfigjat.

ASK Me No Questions, I'll Tell You No Lies

Ok, tegyuk fel, van egy spamszurod, ami a tokeneket (legyen cca. 5-10 MB/per user) tarolja valahogyan file-ban.

1. Elolvasom a levelet, elkeszitem a token listat.

2. mmap()-al behuzom a memoriaba a felhasznalo token adatbazisat (5-10 MB RAM), valami strukturaba rendezem (legyen 10-15 MB RAM).

3. Gyorsan kiszedem az erdekes n x 100(0) tokent (a.k.a "select"), szamolok, megvan az eredmeny, felszabaditom a lefoglalt (5+10 vagy 10+15 MB memoriat)

3b) a token lista valahany elemet modositom, esetleg veszek fel uj tokeneket, es a modositast kiirom a file-ba.

A kerdesek:

1. Elfogadhato-e az, hogy csak a level elemzese felhasznalonkent 25 MB memoriaba kerul? 100 level parhuzamos feldolgozasa eseten ez cca. 2.5 GB. Nem tudom, ez mennyire sok egy mail szerveren. Azt sem, hogy ez a csomo mmap() mennyire I/O igenyes, es birja-e a mail szerver hw? Azt meg nem mondtam, de skalazhato megoldasban gondolkodom. Ez az?

2. Hogyan lehet ezt a kvazi "dirty cache"-t gyorsan es hatekonyan ki/vissza irni file-ba ugy, hogy gondolunk a konkurens hozzaferesre is?

ASK Me No Questions, I'll Tell You No Lies

Fenti rekord mérete alapján írtam, hogy ebből 500k-1M simán befér a RAM-ba, a perzisztens tár lehetne SQLite. Többszálú progiban lehet egy egységes API-d, ami megcsinálja, hogy a változtatásokat mentegeti az adatbázisba.
Azt nem feltételeztem, hogy ezt minden levélnél be kell töltened, mert nem egy démon a cucc, ami csak induláskor olvassa be az összes rekordot.
Bocs, ha hülyeséget írtam, de egy hasonló feladatot régebben egy ilyen démonnal oldottam meg, igaz az C++ volt és lehetett STL-es map-eket használni.

mondok csunyat: irj sajatot.

en csinaltam sajatot c++ban, rament egy kis idom, viszont
mysqlhez kepest hasit.

2M rekord, 120k select/s, 40-45k insert/s

random volt a select is, es indexelt volt, O(nlog n) idoben
valo kereses (AVL fak voltak mogotte)

hatrany: azt tudja, amit lekodolsz, ill bonyolult
selectekre nem jo. osszetett whereket, jointokat meg
meg lehet irni, nagyon bonyolultakat mar nincs sok ertelme ilyenben
megcsinalni..

nekem nagyon fontos volt a sebesseg, es a mysql alapjaraton
kozeleben sem ert (20k random select/s -et tudtam max kipreselni belole,
de persze ez lehet az en hibam is - nem ertek hozza.)

Ez tenyleg csunya, mert gondoltam mar en is erre a szoszolesre, de nekem valami stabil es kiforrott, mar bizonyitott megoldasra van szuksegem, aminek mar kiderultek a gyerekbetegsegei (es fixaltak is), egyszoval valami production quality cuccban gondolkodom. Az sajnos nem opcio, ha allandoan a proprietary backend-emet kell debug-olni, hogy miert hasal el vagy csinal varatlan dolgokat (akarmilyen kornyezetben).

ASK Me No Questions, I'll Tell You No Lies

A legbonyolultabb query ez (a token es uid az index):

s elect nham, nspam from token_tabla where token=egy-64-bites-szam and (uid=0 or uid=egy-integer)

Azzal vagyok elegedetlen, hogy a mysql query cache nem (tul) okos, es ha a token_tabla-ba valaki ir, akkor az egeszt cache-t eldobja, ahelyett, hogy csak az esetlegesen erintett rekordot dobna el.

Ezert arra gondoltam, hogy a sajat backend az tkp. egy kvazi mysql query cache-t implementalna. A program ezt a cache-t kerdezne le, az pedig csak a select/update-ekkel foglalkozna, az insert-ek pedig kozvetlenul mennek a mysql tablaba. Ha egy rekord nincs meg, akkor lekerdezi a mysql adatbazisbol, es a tovabbiakban o szolgalja ki. Az update-eket o kezeli le, es ha egy rekordot kidob a cache-bol (es az dirty), akkor egy update-et kuld elotte a mysql adatbazisba.

Ez mukodhet?

ASK Me No Questions, I'll Tell You No Lies

mukodhet. lenyegeben en is ezt vazoltam fent. :)

az updateket o kezeli le azert nem szerencses, mert mi van ha
bekressel. szerintem minden, ami adatintegritassal kapcsolatos dolog,
kuldhetjuk vissza a mysqlnek, azt mondtad, hogy a selectek dominalnak.

a mysql query cache meg igen, sajnos buta..

amit meg hasznalhatnal, az a memcached mogotte mysqlel, bar
nekem a memcached is lassu volt [ugyanazon a vason,
amin az enyem szaguld. bar az enyem nem halozati, that's true.]

Na, egyre jobban tetszik az otlet. A cache egy rekordja kb. igy nezne ki (cca. 32 byte):

struct qcache {
unsigned long long token;
unsigned int uid;
unsigned int nham;
unsigned int nspam;
unsigned long timestamp;
unsigned char dirty;
}

Milyen adatstrukturat lenne erdemes hasznalni, ha a token+uid unique?

1 MB meretu cache-nel kb. 32k fer el. Gondoltam egy sima 32k elemu tombre, ami vagy rendezett (es akkor valami iteracioval keresem meg a kerdeses elemet) vagy nem rendezett, es akkor egy "full table scan"-nel keresek benne (de ez nagyon gagyinak tunik mar elsore is), vagy egy hash format hasznalok. De ha hash, akkor mi lesz a kulcs (hogyan all elo es hogyan tarolom)?

Megnezem meg a memcached-et is, nem akarom feleslegesen feltalalni a kereket, de ha egyszeruen megoldhato a dolog, akkor bele vagok.

ASK Me No Questions, I'll Tell You No Lies

elmondom hogy csinaltam en.

van egy sima lancolt listad, amiben tarolod az adatokat.

azt, hogy gyorsan elerd az elemeket, ugy valositod meg, hogy csinalsz
n darab mapet [nalad ez epp 6, azaz ahany elem van a structban],
es ezeken keresel.

ha valami uid alapjan kell, abban a mapben, ha valami nspam alapjan,
akkor abban.

ezek a mapek csak mutatokat tarolnak az eredeti strukturara, es mivel
a cpps map implementacio AVL fat hasznal, igy gyors is. van beepitett
find(), merge() akarmi, szoval tok konnyen kezelheto.

a hatrany: sok memoriat zabal.
az elony: kurvagyors :)

es lehetnek nyugodtan constok azok a pointerek, akkor meg jobb a dolog
[nalam 30-40%ot dobott rajta].

sajat benchmark, igy hirtelen:

[root@osiris zcache]# ./zcache
starting tree generation... sec: 1183844764, usec: 231820
generation finished, start random search... sec: 1183844798, usec: 802693
search ended: sec: 1183844813, usec: 190053
[root@osiris zcache]#

elejen egymillio insert, aztan egymillio random select.
(ha leosztjuk, nagyjabol 28.5k insert/s, illetve 66k select/s,
ugy hogy most 4es loadja van a gepnek, es szejjel van hajtva
mind a 4 proci. ram kell neki, dehat ennyit meger.)

Nem RDBMS-t ajanlok, csak egy otlet:
Ha nem tanitod a szurodet nap vegeig, akkor egesz nap hasznalhatod ugyanazt a cache-t. Ez persze azt jelenti, hogy ha egy nap tobb ugyanolyan spam eltalalja ugyanazt a felhasznalot (szoval a token,UID paros megegyezik), akkor mindket esetben ugyanaz a dontes.
(Az idozites lehet rovidebb is.)
Ha ez nem megengedheto, akkor legyen egy plusz reteg az adatbazis es a szuro kozott, ami megismeri a modositott rekordokat, megjegyzi (hogy nap vegen tovabbadhassa, pl kiirja file-ba az update/insert utasitasokat), es addig a modositott erteket adja vissza valaszul. Gyakorlatilag egy cache a DB ele. Ebben az esetben eleg a modositast tarolni memoriaban (bar azt mind kell), legfeljebb ha tul sok, akkor ki kell irni DB-be, es uriteni.

Ha a masik szalon felmerult cache-t valasztod, akkor gyorsitasnak en a hash-elt valtozatot valasztanam, es ami utkozik, azt nyugodtan eldobhatod (mert ugyis csak cache).
---------------------
Q: Why do real Java programmers wear glasses?
A: Because they don't C#.

Ha gyors adatbazist (es nem feltetlenul relaciosat) szeretnel, akkor ajanlom figyelmedbe Konstantin Knizhnik FastDB illetve Gigabase nevu munkajat - a fastdb tud tranzakciot, adaptiv hash es t-tree adatstruktura a kereseshez (oracle timesten, mysql cluster is ilyet hasznal), illetve akar sajat indexelest is irhatsz s a GIST (Generalized Search Tree) interface segitsegevel. Sql szeru lekerdezo /manipulacios nyelv, es aktiv-(tobb)passziv replikacio is alaptartozek a hibatureshez ill. terheleselosztashoz.

A muveletek komplexitasa a doksi szerint kb igy alakul:

Type of search Average Maximal
Sequential search O(N) O(N)
Sequential search with sorting O(N*log(N)) O(N*log(N))
Search using hash table O(1) O(N)
Search using T-tree O(log(N)) O(log(N))
Access by reference O(1) O(1)

Tegnap olyan ejfel korul az alabbi jutott eszembe.

Keszitek egy fix meretu hash tombot (valami 32K koruli primszam meretben). A hash erteket a token alapjan kepzem (ami egyebkent egy 64 bites szam). Minden slot a hash-ben max. (mondjuk) 4 db elemet tartalmazhat, amelyek kozott szekvencialisan keresek. Collison eseten, ha az adott slot-on levo 4 elem egyike sem az amit keresek, akkor lekerdezem azt az sqlite3/mysql adatbazisbol, es a legregebbit felulirom az uj rekorddal.

Ezzel
- cache hit eseten barmely elem max. 1+3 lepesben megvan
- 128k elemet tud tarolni ~128*25 byte = ~3.2 MB memoria (+ egy kicsi) kell hozza
- automatikus kidobas a cache-bol nincs, csak ha az adott slot-ban nincs mar szabad hely

A szuro kesleltetett tanitasa jo ugyan a mysql query cache-nek, de eppen az azonnali tanitas elonyet veszitem el: lehet, hogy azert nem ismerem fel a 18:42-es spamet, mert pont azok a tokenek kellettek volna hozza, ami a 16:38-as es a 18:22-es spamben voltak. Raadasul ezeket a leveleket is valahol tarolni kell addig, egy queue-t kezelni. Nem vagyok biztos abban, hogy megeri a faradtsagot. Ebben a honapban az azonnali tanitas elonyet vizsgalom, mennyi pluszt ad a csak hiba eseten torteno tanitashoz kepest. Ha jelentos a ketto kozotti kulonbseg, akkor talan.

ASK Me No Questions, I'll Tell You No Lies