Dr. Vermes Mátyás1
2001. december
A dokumentum az új, BTBTX formátumú táblaobjektumot ismerteti. Ha csupán alkalmazni akarjuk az új könyvtárat, akkor erre az írásra nincs szükség, mivel (természetesen) a korábbi táblaobjektumokkal megmaradt a kompatibilitás, ezek leírása pedig a Tábla objektum referencia dokumentumban található. Így a továbbiakat csak háttérinformációnak szánom.
Az új formátum legfontosabb tulajdonsága, hogy saját kulcskezelőn alapszik, így végre függetlenedni tudunk bármiféle idegen forrástól (Btrieve, Ctree), és feltétel nélkül szabaddá (GPL) tehetjük a kódunkat. Személyes véleményem, hogy hosszabb távon a saját kulcskezelő megbízhatóbb is lesz, mint az említett szoftverek.
Az alábbiakban áttekintem a BTBTX formátum fő jellegzetességeit a korábbi formátumokkal összeveteve.
Btrieve
A Btrieve-hez hasonlóan a BTBTX formátumban sincs külön index filé. Az adatok és az indexek táblánként egy darab bt kiterjesztésű filében vannak. A memófilék kezelését ugyanaz a szoftver végzi, mint a többi formátumban, kiterjesztésük btx. Az új formátum neve az adat- és memófilék kiterjesztésének összevonásából keletkezett. A Btrieve és BTBTX formátumú táblaobjektum egyaránt tartalmazza a mezők és indexek leírását. Mindkét formátum képes változó hosszúságú rekordok tárolására, de ezt a képességüket (a resource-októl eltekintve) nem használjuk. A Btrieve rekordkezelőt tipikusan kliens/szerver üzemmódban használják, szemben a BTBTX-re jellemző standalone programszervezéssel.
DATIDX
A BTBTX és DATIDX formátum hasonlít abban, hogy mindig rendelkezésre áll a tábla mezőinek és indexeinek leírása. A DATIDX formátumban az indexek frissítését a Ctree könyvtár automatikusan végzi.
DBFCTX
Különösen nagy hasonlóság van a BTBTX és a DBFCTX formátum kódja között. Az indexek módosítását nem a rekordkezelő könyvtárra bízzuk (ahogy a Ctree-re a DATIDX esetében), hanem magasabb szinten, a táblaobjektumban oldjuk meg. Kulcs módosításakor először töröljük az indexből a régi kulcsértéket, módosítjuk az adatrekordot, végül beírjuk az indexbe az új kulcsot. Talán meglepő, de mindez hatékonyan és megbízhatóan kódolható CCC-ben. Csakhogy, míg a DBFCTX esetében az elemi kulcskezelés függvényei a Ctree könyvtárból valók, a BTBTX saját kulcskezelőt használ.
A bt filé a mezők és indexek leírását egyaránt tartalmazza. Az indexek leírása a kötött dbf formátumba nem volt betehető, ezért DBFCTX-ben az index infót a ctx tárolja, ami azonban nem áll rendelkezésre, ha éppen letörölték. A BTBTX formátum mentes ettől a hibától.
Szükséges-e egyáltalán ISAM filékezeléssel bajlódni? A fiatalabb programozó generáció már azt sem tudja mi az az ISAM, SQL-en kívül mást el sem tudnak képzelni. Tekintsük azonban a következő SQL utasítást:
select szamlaszam,devnem,egyenleg from szamla where szamlaszam<'8830100440014832' order by szamlaszam desc
A fenti parancsot az Oracle, Postgres és MySQL úgy hajtja végre, hogy először kikeresi a where feltételnek megfelelő számlákat (a sorok száma akár többszázezer is lehet), majd az így kapott táblát rendezi, és negyedóra gondolkodás után megadja az első rekordot. Ettől a nyilvánvalóan rossz algoritmustól a fenti adatbáziskezelőket nem lehet eltántorítani. Hiába létezik index a szamlaszam oszlopra, hiába adunk bámilyen hint-et az optimalizálásra vonatkozóan, az Oracle kitartóan rendez. Ugyanez a lekérdezés egy ISAM filékezelővel, számlaszám szerinti indexszel, többszázezer eredménysorral fél percen belül elkészül úgy, hogy az első rekord egy ezredmásodpercen belül megvan.
Megmutattam ezt egy Oracle ,,szakértőnek", aki azt mondta, hogy a feladat rossz, mert az Oracle-nek olyan kérdéseket kell feltenni, aminek eredményeként kis táblákat kapunk. Irígylem azokat a programozókat, akiknek csak jó feladatokkal kell foglalkozniuk.
Általánosságban (finoman szólva) az mondható, hogy az SQL lekérdezésű, tranzakciós adatbázisszervereket nem olyan feladatok megoldására tervezték, amik egy nagy tábla sorainak többségét érintik. Ilyen feladatok azonban nyilvánvalóan léteznek. Tegyük fel például, hogy van egymillió számlánk, és ki akarjuk számolni mindegyiken a napi kamatot, vagy ki akarjuk gyűjteni azokat, amikre kivonatot kell nyomtatni, és éppen 900 ezer ilyen van.
Említek még egy dolgot, amit gyakran még a tapasztalt informatikusok is elfelejtenek, nevezetesen, hogy nincsenek csodák: A legvonzóbb hirdetésekkel rendelkező SQL adatbáziskezelő sem tud nagyobb adatbázisokban gyorsabban keresni, mint az egyszerű ISAM, minthogy erre jelenleg nem ismerünk jobb adatszerkezetet, mint a btree, ahogy azt az ISAM-ban néhány évtizede kitalálták.
No jó, legyen ISAM, akkor is mi értelme van új kulcskezelő szoftvert írni, amikor az ilyenekkel Dunát lehet rekeszteni? Meglepő, de nincs is ezekből olyan sok: Btrieve, Ctree, C-ISAM, DISAM, Berkeley-DB (SleepyCat). Ezeknek azonban egyike sem ingyenes, és a Ctree és a Berkeley DB kivételével a forrásuk is titkos. Emellett ezek legalább 10-15 éves szoftverek, amik az idők során egymásra rakódott API-k miatt szövevényessé váltak, rengeteg vitatható fontosságú szolgáltatást nyújtanak, viszont nehéz belőlük kibányászni a kisszámú tényleg szükséges funkciót. A programok fejlesztési irányával sem vagyok elégedett, pl. szerintem nincs szükség e termékekre épülő gyenge minőségű, SQL interfészű adatbázisszerverek fejlesztésére.
Nekem éppenséggel olyan kulcs/indexkezelőre van szükségem, ami az általam fontosnak tartott szolgáltatásokkal rendelkezik, áttekinthetősége és egyszerűsége miatt kézbentartható és megbízható. Úgy gondolom, hogy a mai PC-k teljesítménye lehetővé teszi, hogy az algoritmusok egyszerű és közvetlen alkalmazásával megoldjunk olyan feladatokat, amit korábban csak agyonoptimalizált programokkal lehetett. Méginkább így lesz ez a 64 bites rendszerek megjelenésével. A BTBTX egyszerű kulcskezelőjét egy szép délután portolni fogom 64 bites Linuxra, de mennyi ideig fog ez tartani a Ctree esetében?2
Ha megtekintjük a man 3 dbopen parancs után elénk táruló információt, rájövünk, hogy a Linuxon van ingyenes ISAM adatbáziskezelő. Installáltam az adatbáziskezelő forrását is, aminek tanulmányozásával a következők derültek ki:
A manban leírt adatbáziskezelőt eredetileg a BSD UNIX-on fejlesztették ki, amint az a Makefile-ben lévő megjegyzésben olvasható:
# Makefile for 4.4BSD db code in GNU C library. # This code is taken verbatim from the BSD db 1.85 package. Only this # Makefile and compat.h were written for GNU libc, and the header files # moved up to this directory.
Ugyanennek a szoftvernek van egy fejlettebb, a SleepyCat által fejlesztett változata, ami a SuSE Linuxokon szintén installálódik (és általában elfedi az előzőt). E csomag README-jében az alábbi licence információ bújik meg:
As a special exception, when Berkeley DB is distributed along with the GNU C Library, in any program which uses the GNU C Library in accord with that library's distribution terms, it is also permitted for Berkeley DB to be loaded dynamically by the GNU C Library to implement standard ISO/IEC 9945 and Unix interface functionality. Sleepycat Software, Inc.
E két adatbáziskezelő változat legfőbb jellegzetessége, hogy szigorúan egyfelhasználósak. Ez leginkáb azon múlik, hogy intenzíven cache-elnek, ezért nem is értesülhetnek más processzek által végzett adatmódosításokról (ritkán olvasnak).
Harmadszor, a Berkeley DB-nek létezik egy többfelhasználós, bonyolult tranzakciókezelésre képes változata, amit a SleepyCat forgalmaz, forrása letölthető a hálóról, ám üzleti alkalmazásra nem ingyenes.3
A saját kulcskezelő írásakor a legrégibb, legegyszerűbb változatból indultam ki. Az átalakítások folytán a szoftver egyrészt leegyszerűsödött, másrészt lehetővé vált a konkurrens használat. Az egyszerűsítés mértékére jellemző adatok:
Nézzük, milyen egyszerűsítések történtek a szoftverben:
A bővítések:
Terveim szerint a formátum részét fogja képezni a bytesorrend, ennek konverzióját azonban csak legvégül célszerű beépíteni a szoftverbe, hogy a fejlesztés alatt ne zavarja a tiszta képet.
Az alább ömlesztve felsorolt interfész részletes leírásának jelenleg nem volna sok értelme, így csak néhány észrevételt teszek.
BTREE *__bt_open (int fd, int psize); int __bt_close (BTREE*t); int __bt_fd (BTREE*t); int __bt_pagesize (BTREE*t); int __bt_lastrec (BTREE*t);
Az open paramétere nem filénév, hanem korábban megnyitott filé descriptor, így a nyitási mód kompatibilisnak tartható a CCC fopen-nel, és a UNIX/Windows különbségek sem gyűrűznek tovább. Üres (nulla hosszúságú) filé esetén meghatározható a pagesize, ha ezt 0-nak adjuk meg, azt a rendszer a default pagesize-zal helyettesíti, ez általában 4096 byte. A filébe írt adatrekordok számát adja meg lastrec.
int __bt_delete (BTREE*t, DBT*key); int __bt_put (BTREE*t, DBT*key, int cursor); int __bt_seq (BTREE*t, DBT*key, int flags);
Ezek a hagyományos dbopen függvények kis módosítással. A delete függvény csak konkrétan megadott kulcs törlését támogatja (kurzort nem töröl). A put harmadik paraméterével az szabályozható, hogy pozícionálódjon-e a kurzor. A seq függvény haramadik paraméterének (flags) egy bitjében előírható, hogy a filé 0-dik lapjára a keresés alatt readlockot tegyen (konkurrencia). Az indexet módosító processzek ennek megfelelően writelockot tesznek a 0-dik lapra, de ez nincs beépítve egyik (alacsonyszintű) függvénybe sem, mivel egyszerre több elemi műveletet kell lefedni lockkal, ezért a táblaobjektumba való.
int __bt_creord (BTREE*t, char*name); int __bt_setord (BTREE*t, char*name); int __bt_delord (BTREE*t, char*name); int __bt_renord (BTREE*t, char*namold, char*namnew);
E függvényekkel sorrendeket (btree struktúrákat) lehet a filében kreálni, aktuálisként kijelölni, törölni, átnevezni. Az interfészcsoport függvényei az indexet név alapján azonosítják. A delord által törölt egész btree egy mozdulattal a szabadlistába kerül.
RECPOS __bt_addresource (BTREE*t, DBT*buf, indx_t x); RECPOS __bt_append (BTREE*t, DBT*buf, int*recno); int __bt_rewrite (BTREE*t, DBT*buf, RECPOS*recpos); int __bt_read (BTREE*t, DBT*buf, RECPOS*recpos); int __bt_read1 (BTREE*t, DBT*buf, pgno_t p, indx_t x);
Az addresource függvény az 1-es lapon helyez el meg nem határozott célú metainfót. A táblaobjektum ezt a lapot a mezők és indexek struktúrájának leírására használja. Új adatrekordot ír a filébe az append, és visszaad egy RECPOS struktúrát, amivel hivatkozni lehet a rekordra. Az adatrekord hossza nem kötött, de rá kell férjen egy lapra. A rewrite függvény felülír egy létező adatrekordot. Az új rekord hosszának kötelezően egyeznie kell a régi hosszal. Az adatlapok módosítása automatikus lockolással védett. read és read1 kiolvasnak egy adatrekordot.
void __bt_pagelock (BTREE*t, pgno_t p, int mode); void __bt_pageunlock (BTREE*t, pgno_t p); int __bt_header_read (BTREE*t, int lock); int __bt_header_write (BTREE*t); int __bt_header_sync (BTREE*t); int __bt_header_release (BTREE*t);
A header író/olvasó függvények speciális gondossággal kezelik a konkurrenciát, többek között egy lock számlálót használnak az egymásba skatulyázott hívások nyilvántartására.
Az eddigiek ismertették a nyersanyagot, most következne, hogy hogyan lehet ebből megfőzni a vacsorát, azaz a táblaobjektumot. Idő híján csak néhány megjegyzés:
Az 1-es lap (adatlap) speciális célra, a mezők és indexek struktúrájának tárolására szolgál. Ez két rekordot jelent, mindkettő _arr2chr formátumban van kiírva. Más nincs az 1-es lapon.
Az adatrekordokat alapvetően a RECPOS struktúra segítségével lehet előkeresni. Ez CCC szinten egy 6 byte-os string, aminek első 4 byte-jában a lapszám, utolsó 2 byte-jában a lapon belüli index van.
A tabAppend művelet kiír egy (törölt) üres rekordot az utolsó adatlapra, vagy, ha ott nincs már elég hely, kezd egy új lapot. Visszaadja az új rekord RECPOS-át, amivel hivatkozni lehet a rekordra, és képezhetők a kulcsok. Az indexek csak az appendált rekord commitjában módosulnak, ha az elmarad (pl. tranRollback miatt), akkor a rekordra később egyáltalán nem lehet rápozícionálni, még goto-val sem, azaz a recno-k sora lyukas lesz.
Az 0-dik index neve mindig "recno". A recno indexben levő kulcsok szerkezete: 4 byte-on (big endian) rekordsorszám plusz RECPOS. A tabGoto művelet megkeresi az adott rekordsorszámhoz tartozó kulcsot, majd az ebben talált RECPOS alapján beolvassa a rekordot.
A többi kulcs szerkezete: szegmensek konkatenációja plusz az előbbi recno kulcs. Ez biztosítja, hogy az azonos kulcsok mégiscsak különbözzenek, és recno szerint legyenek rendezve. A tabSeek művelet nagyobbegyenlőt keres a megadott kulccsal, a visszakapott kulcsból meg lehet határozni az eredményrekord recno-ját, és a RECPOS alapján be lehet olvasni a rekordot.
A pack műveletben el akartam kerülni, hogy a pack sikere függjön a recno index épségétől, ezért a következőképpen megy: Sorban beolvassuk a filé összes lapját, miközben csak az adatlapokkal foglalkozunk. Ezekről az összes nem törölt rekordot átmásoljuk az új filébe (append, recbuf csere, commit). Az indexek menet közben újraépülnek. A szabadlista alkalmazása miatt a pack felcserélheti a rekordok eredeti sorrendjét.
A CCC szintű rekordlock minden mástól független. Egy rekord lockja 2GB-1MB-tól kezdve visszafele számolva egyetlen byte lockját jelenti.
A btree filé mindig fopen-nel nyílik, ezért az fopen-ben alkalmazott lock protokoll érvényesül. Egy bt filé pontosan egy descriptort használ.
Az indexeket olvasó processzek readlockot (lásd __bt_pagelock), a módosító processzek writelockot tesznek a 0-dik lapra. A lock protokoll biztosítja minden processz számára a megfelelő védelmet. Emellett teljesül, hogy egy írni akaró program rövid időn belül akkor is megkapja a kívánt writelockot, ha az olvasó programok readlockjai hosszú ideig átfednék egymást (live lock).
Az alábbi tesztek egy 172 ezer rekordot tartalmazó Kontó számla állománnyal készültek.
| Formátum | Méret | Skip | Pack | Upgrade | Goto+Seek | Suppindex |
| BTBTX | 95 MB | 9 s | 59 s | 143 s | 44 s | 23 s |
| DBFCTX | 80 MB | 5 s | 20 s | 113 s | 41 s | 25 s |
| DATIDX | 60 MB | 13 s | 23 s | 148 s | 43 s | 29 s |
A DATIDX takarékos mérete a számok lebegőpontos ábrázolásán (8 byte) múlik. A BTBTX ugyanolyan formátumban tárolja a mezőket, mint a DBFCTX. A méretnövekedés oka, hogy a rekordokat lapokra szétosztva tároljuk, ezért minden lapon lesz egy töredék kihasználatlan hely. Emellett a BTBTX formátum rugalmasabb: lehetővé teszi változó hosszúságú adat- és indexrekordok tárolását.
A ,,Skip" oszlop az egész adattábla számlaszám sorrendben történő végigolvasásának ideje. Meglepően jó időt produkál a DBFCTX formátum.
A ,,Pack" oszlop a tábla packolásának idejét mutatja. A BTBTX formátum packolása félig optimalizált: a rekordokat egészben másolja, de az indexeket menet közben építi. A DBFCTX packolása nagyon gondosan van megírva, a DATIDX ,,magától" jó.
A tabUpgrade művelet a táblát rekordonként és mezőnként másolja, eközben az indexek folyamatosan épülnek.
A ,,Goto+Seek" mérésnél minden rekordra rápozícionáltunk goto-val, majd az ott talált számlaszámra seek-eltünk.
A ,,Suppindex" oszlopban a számla állomány főkönyvi gyűjtéskor használt, meglehetősen összetett indexének előállítási ideje látszik.
1ComFirm BT.
2 Vagy a jelent illetően: egyszerűen bevezethető a ReiserFS 60 bites filé offseteket támogató API-ja, amivel már most megoldható a 2G-nál nagyobb filék kezelése.
3 A MySQL legújabb, tranzakciókezelést is tartalmazó változata erre az adatbázismotorra épül (így nyilván az sem lehet ingyenes).