Efektivita

20.10.2007 17:05 | Přečteno: 1641× | poslední úprava: 20.10.2007 17:10

Aneb i málo dokáže potěšit

Jak asi víte, nemám nejméně emailů. Proč se nepřiznat, je jich v tuto chvíli 750 000. Protože evidentně nikdo na planetě se podobným cifrám ani neblíží v důsledku čehož neexistuje klient, který by to odstojně zvládal, rozhodl jsem se je uložit do DB kam patří a vytvořit nad ní vyhledávací aplikaci.

Teď malé počty:

• Původně využité místo na disku (maildir): cca 8GB
• Soubory ve skutečnosti obsahovaly: 2.6GB dat*
• Pouze hlavičky emailů mají: 1.5GB
• Tělo emailů (tedy to co vlastně chci): cca 950MB.

*) Zbytek je nevyužitelné místo díky pevné velikosti sektorů na FS (4kB).

Tohle má tak nízkou efektivitu, až mě to nad databází dojalo.

       

Komentáře

[Josef Kufner]

No, když té databázi uděláš i IMAP rozhraní, tak by to mohlo být i použitelné

[Heron]

Možná v daleké budoucnosti - dělám to jen o víkendech a moje efektivita taky není bůh ví jaká . Kámoš z toho chce kompletního klienta, ty server - dohodněte se pánové

[Josef Kufner]

Když k tomu uděláš jen lehkého démona, tak nebude problém používat libovolného klienta

[Luk]

Jenže implementovat IMAP není bohužel vůbec triviální. Kdysi dávno jsem o něčem takovém uvažoval, ale odradila mě právě složitost tohoto protokolu (a to už mám za sebou implementaci svých vlastních SMTP a POP3 serverů).

[Kyosuke]

Hm, člověk by řekl, že nejefektivnější bude append-only mbox s (velmi) občasným packováním, případně ještě lépe nějaký obdobný formát (nutno vymyslet) s nevelkými komprimovanými bloky (řekněme po 1 MB?), a k němu dodatečné indexy na cokoliv, podle čeho se má rychle hledat. Databáze nejsou zrovna úsporný prosředek k ukládání dat.

[Filip Jirsák]

To co popisujete je databáze Otázka je, jestli se vyplatí vymýšlet vlastní optimální formát (a pak už vám nejspíš nezbyde čas nastudovat a naprogramovat všechny ty možné optimalizace, které už mají databáze naprogramované), nebo je lepší použít už hotovou databázi, která bude sice o něco méně efektivní, ale zase dostanete „zadarmo“ spoustu promyšlených optimalizací. Cena diskového prostoru bude dnes pravděpodobně daleko menší, než cena programátora, který zvládne naprogramovat efektivní databázový stroj…

[Kyosuke]

Databáze to sice je, ale těžce specializovaná. To znamená, že člověk nepotřebuje blbosti typu QL parser a query optimizer a podobně, protože ví, co se s těmi daty bude dělat (přidej email, smaž email č. 13242, najdi emaily podle subjectu...). A těch věcí podle mě není hodně. Ostatně některé mailery to tak řeší, ne? Evolution s mboxem používá indexové soubory, jestli se nepletu.

[Heron]

přidej email, smaž email č. 13242, najdi emaily podle subjectu...

...Vyhledávej v nich fultextem, seřaď relevantní emaily do stromu podle odkazů, hledej podle autora, data, čehokoliv, vyhledej maily daného autora v rozmezí datumů a jen s daným topicem...

Nene, stále mám pocit, že na toto se víc hodí SQL než souborová hash DB.

[Kyosuke]

Muhehehe!!! Fulltext a stromečky že patří do klasických relačních databází. No to je dobrý vtip. A co jako mám použít na ten fulltext? MySQL, které je podstatně pomalejší než Ruby+Ferret?

[Heron]

Ber to tak, že si hraju. Prostě nevěřím tomu, že způsob jak to dělají mail klienti je nějak časově efektivní. Je mi jasné, že jejich vývojáři si často říkali něco ve smyslu, "hmm O(n^2), sakra, jak dlouho to bude trvat pro 100 položek? Jo je to hned, necháme to tak." Musí to jít rychleji, jen se to pro jejich počty nevyplatí implementovat. Fulltext nemusí být nutně ALTER TABLE `xxx` ADD FULLTEXT..., ale i tohle zkusím.

[Luk]

Je mi jasné, že jejich vývojáři si často říkali něco ve smyslu, "hmm O(n^2), sakra, jak dlouho to bude trvat pro 100 položek? Jo je to hned, necháme to tak.

Jestli to tak v konkrétním případě opravdu je, tak bych to autorovi otřískal o hlavu. Připomíná mi to obludně velké weby, kdy jen k zobrazení homepage je potřeba načíst 3 MB dat ("na mém připojení je to rychlé").

[Filip Jirsák]

A těch věcí podle mě není hodně. Ostatně některé mailery to tak řeší, ne? Evolution s mboxem používá indexové soubory, jestli se nepletu.

Třídění podle různých kritérií a hlaviček, fulltextové vyhledávání, statistiky… To že si to (téměř) každý klient řeší po svém a má vlastní index a keš uloženou někde lokálně je podle mne největší slabina dnešních e-mailových klientů.

[Kyosuke]

A co jiného by klient měl dělat? To už rovnou můžeme vymyslet IMAPv5 s podporou všech těchhle věcí, protože jinak nevidím moc možností, jak to opravdu udělat standardní. Jenomže většina poskytovatelů e-mailu tohle stejně nebude poskytovat - příliš náročné na výkon.

[Heron]

příliš náročné na výkon.

Tím si nejsem příliš jist, google dokazuje, že to jde. Bohužel pouze na web rozhranní.

[Filip Jirsák]

A co jiného by klient měl dělat? To už rovnou můžeme vymyslet IMAPv5 s podporou všech těchhle věcí, protože jinak nevidím moc možností, jak to opravdu udělat standardní.

Když ten IMAPv5 nebude mít vlastní TCP/IP protokol, ale bude fungovat přes HTTP, dostáváme se už pomalu k tomu, jak bych si to představoval.

Že jsou e-maily uložené na serveru a pak ještě jednou na každém klientovi, aby v nich klient mohl vyhledávat, to opravdu nepovažuji za šťastné řešení. Zvlášť když se uživatel přihlašuje pokaždé jinde (jako třeba ve škole) – pak si buď musí index při každém přihlášení okopírovat ze sítě a při odhlášení zpět (srdečné pozdravy cestovním profilům Windows), nebo musí mít index připojený jako síťový disk – takže na serveru jsou ty e-maily jednou ve formátu pro IMAP server, jednou pro poštovního klienta. Nějak se mi tu ztrácí význam té zaklínací formulky „použij IMAP a e-maily máš na serveru“.

Jenomže většina poskytovatelů e-mailu tohle stejně nebude poskytovat - příliš náročné na výkon.

Zatímco mít tohle a nad tím jako nadstavbu ještě webové rozhraní, to náročné na výkon není? Kdyby měl GMail zdokumentované rozhraní, přes které si to jejich AJAXové rozhraní povídá se serverem, je to už téměř ono (téměř proto, že je to zajisté proprietární věc, a pro standardizaci by bylo nutné mírně to zobecnit).

Ostatně většina poskytovatelů ať si poskytuje co uzná za vhodné, já si vyberu takového, který tohle poskytovat bude. Resp. si to budu poskytovat sám, když bude k dispozici příslušný software. Jenom mi současné řešení zatím nevadí tolik, abych se sám pouštěl do psaní příslušného serveru i klienta – server bych si třeba i napsal, ale použitelný klient, který si poradí s kdejakým v HTML zpraseným e-mailem, nepatří k věcem, které bych toužil psát…

[Ignor]

Zvlášť když se uživatel přihlašuje pokaždé jinde (jako třeba ve škole) – pak si buď musí index při každém přihlášení okopírovat ze sítě a při odhlášení zpět

To "ze sítě" tuším již dnes může znamenat z IMAP serveru, ne? Index bude proti všem mailům trapně malý, takže to ani nevadí. Navíc nemusí být "fyzicky" vcelku, takže se zpátky nemusí nahrát celý, ale jen rozdíl (a jednou za čas to slít vše dohromady). Stejně je myšlenka serverového vyhledávání podle mě trochu mimo, páč přecejen ideálem pro mě je všechna pošta šifrovaná.

[Filip Jirsák]

To "ze sítě" tuším již dnes může znamenat z IMAP serveru, ne?

Možná pro PINE, o něm se většinou tvrdí, že umí s IMAPem všechno Ale pochybuji o tom, že by ten index byl přenositelný mezi různými klienty.

Index bude proti všem mailům trapně malý, takže to ani nevadí.

Pro gigové schránky už to nějakých pár desítek mega bude.

Stejně je myšlenka serverového vyhledávání podle mě trochu mimo, páč přecejen ideálem pro mě je všechna pošta šifrovaná.

To ale zároveň znamená přístup k poště jen z jednoho míst anebo několika málo míst. Pak vám samozřejmě lokální uložení pošty nemusí vadit. Někdo jiný ale zase chce mít poštu dostupnou odkudkoli se stejným komfortem, a nešifrovaná data na serveru mu nevadí. Dnes existuje jediná možnost, jak tohle zařídit – webové rozhraní. A to zrovna ten nejkomfortnější styl práce. Navíc i to fulltextové vyhledávání by šlo zařídit tak, že klient e-mail rozšifruje, vytvoří z něj seznam slov a ten pošle zpátky na server pro zařazení do indexu. Sice by pak na serveru bylo možné zjistit, jaká slova v e-mailu byla, ale už by nešlo získat přesnou podobu e-mailu.

[Ignor]

Abych dostával jen šifrované maily, tak mi je musí všichni taky šifrované posílat. No a svět, kde všichni šifrují bude taky vypadat jinak - lidi s sebou budou nosit smart karty nebo nějaká usb udělátka, takže s tím nebude problém. Nemyslím si sice, že e-maily budou tou motivací pro tato udělátka, spíš to bude celková digitalizace a elektronizace světa (jakože místo klasického podpisu po mně budou na každém kroku chtít podpis digitální, pravda podepisovat se takhle na ňadra či zadečky bude pro celebrity o něco těžší ).

Mít seznam slov z mailu díky nešifrovanému indexu je podle mě až moc. Navíc to předpokládá, že index nebo jeho části si budou klient a server nějak standardizovaně vyměňovat (což jsem teda požadoval i já, ale bylo mi to předloženo jako nevýhoda ).

Ono navíc ne všude, kde si chci přečíst mail nebo ho napsat, musím nutně chtít i vyhledávat, spíš bych řekl, že to se děje ve velké menšině případů, takže zdaleka ne vždy by se musel index mezi serverem a klientem přenášet.

[zde]

Co zkusit CDB? Je to DBware, takže malé, rychlé, čitelné...

[zde]

herdek, zapoměl jsem postnout ten link.. http://cr.yp.to/cdb.html

[Heron]

Není to špatný nápad, preferoval byl spíš TDB. Ale stále jsem přesvědčen, že uložení do SQL database bude mít větší výhody.

[freshmouse]

Těch 8 a 2,6 giga se mi ani nechce zdát (= jsem podiven)...

[freshmouse]

Ale stejně by mne zajímalo, kdy objevíš kouzlo archivů přístupných na webu.

[Heron]

Tehdy, až budou u mě doma v DB. O to se právě snažím.

[freshmouse]

Aha, to je ta EFEKTIVITA.

[Heron]

A navíc knowledge base potřebuju nejvíc ve chvíli, kdy nemám přístup na net. Hmm, tedy nějakých 10h do roka .

[Heron]

Vem si, že kdykoliv to má jen 5kB, tak už to zabere 8kB. Plus místo pro metadata. Ono se to napočítá.

[Luk]

Když se tak podívám do své pošty, tak mnoho zpráv se včetně hlaviček vejde do 2 KB. Tam už je u maildiru (při 4KB blocích) využití místa menší než 50 %.

[Jurek]

Priznam se, ze jsem to jeste netestil, ale nepokousite se nahodou o to same jako:

dbmail ?

[Heron]

Narazil jsem na tento projekt přibližně před dvěma měsíci. Není to vůbec špatná myšlenka, v podstatě to místo úložiště mbox, md, maildiru, používá DB. Bohužel, dnes se používá email stylem, že všechny programy jej vyžadují mít v přesné podobě na disku místo toho, aby se dotázali demona přesně stanoveným API. To by umožnilo daleko lepší škálování a výběr mail-storage. Nasazení tohoto projektu vyžaduje, aby ostatní programy, které s emailem chtějí pracoval, uměli pracovat s DB nebo se napojit na DBmail demona. Takže nastoupí patchování.

Já jdu ale dál. DBMail uloží celý email do DB a dál se o něj nestará. Prostě místo na disku je v DB. Já jej rozdělím na jednotlivé hlavičky (relevantní), nad nimi vytvořím vyhledávací index. Můj program má za cíl s těmi emaily pracovat ve smyslu vyhledávání informací. Nikoliv jen ukládání.

[Tom K]

dbmail rozparsuje mail na jednotlive hlavicky a ulozi do databaze. Potom poskytuje naprosto standardni IMAP a POP3 rozhrani, ktere snad dneska umi kazdy mail klient. mozna by bylo efektivnejsi misto vynalezani kola jen rozsirit funkcionalitu dbmailu prave o to zpracovani (pridat moznosti virtualnich slozek, fulltext vyhledavani a podobne jine uzitecne veci).

[Heron]

Jo. S tím DB schematem jsem nebyl spokojen, ale v podstatě máš pravdu. Toto je mail-storage. Já nechci dělat mail storage engine. Proč:

Někdo tu chtěl IMAP přístup. Ten jsem měl přes dovecot. Na klienta je to moc (stahuje si hlavičky které indexuje). Na FS je to moc (velké množství souborů k záloze) - východiskem pro storage je dbmail, možná. IMAP není řešení.

Pop3 je totéž, ale ještě horší, protože soubory se budou duplikovat. Jeden na serveru, druhý u klienta. POP3 není řešení.

Nepotřebuju s těmi "informacemi" (už tomu nebudu raději říkat emaily, evidentně to lidi mate ) zacházet jako s plnohodnotným emailem, potřebuji je jen někam uložit, hlavně smazat ty soubory z disku (už jsou týden pryč) a následně nad nimi vyhledávat. Takže ani email server, ani klient. Prohlížeč.

[Tom K]

V tom pripade, protoze maildir umi prakticky vsichni klienti bych zkusil nejaky virtual maildir filesystem pro fuse. Ano sice to neni specializovany nastroj pro spravu informaci/mailu, ale dalo by se tak snadno zbavit toho mnozstvi souboru a zase pomoci virtualnich slozek resit vyhledavani (fuse muze mit ta data ulozena v databazi nebo kdekoli jinde). Delat specializovany nastroj mi prijde, jako moc silne kafe. Radeji to udelat obecne pouzitelne. Jestli nechces klienta, ktery si indexuje hlavicky, tak zkus mozna radeji upravit existujiciho klienta tak, aby pro indexaci a ukladani hlavicek pouzival efektivnejsi engine (sqlite nebo neco podobneho).

[Josef Kufner]

Vpodstatě by se ty virtualni slozky daly pouzit i pres IMAP. Pokud by to neslo jinak, daly by se vytvaret tak, ze by se do nejake specializovane realne slozky ukladaly maily s pravidly pro vyhledavani (subject = nazev slozky, body = pravidla/dotaz).

[Heron]

Tohle mě taky napadlo.

[Heron]

bych zkusil nejaky virtual maildir filesystem pro fuse

Je to v plánu. Mám pocit, že už někdo nad fuse psal FS s daty v MySQL, ale tvrdil, že to bylo pomalé.

Jestli nechces klienta, ktery si indexuje hlavicky...

Jediná cesta je to napsat sám. Klientů jsem vyzkoušel hodně. Dal jsem na rady všech okolo, "tenhle je nejrychlejší, zkus ho". Možná byl. Pro prvních 30 000 mailů. Jediný kdo zvládal tehdy 400 000 emailů byl KMail, nad maildirem* a pop3. TB nad IMAPem je nepoužitelný. TB je vcelku nepoužitelný

*) jako on to není špatný způsob ukládání, přístup k jednotlivým emailům je rychlý, spousta metadat je ve jménu souboru a když se použije velikost bloku 512B, tak to nezabírá ani moc místa. Jenže zkuste si ty soubory pak zkopírovat. Nedočkáte se.

sqlite

Nevím proč, ale k podobným knihovnám mám averzi. Nechápu, proč nepoužít rovnou server. Výkonnostně si polepším.

[Kyosuke]

BTW, zkou3el jsi Mutt?

[Käyttäjä 11133]

Pochybuju

[Heron]

Používám ho běžně. Ovšem ne na tohleto.

[Ignor]

Šmarjá, to jsou problémy, které by nemusely být, kdybys těmi miliardami zpráv z maillinglistů nakrmil třeba nějaké lokálně provozované fórum či cosi takového.

[Heron]

To nejsou problémy. Prostě si píšu prográmek. To spíš vy ostatní s tím máte problém.

[Tom K]

Je to v plánu. Mám pocit, že už někdo nad fuse psal FS s daty v MySQL, ale tvrdil, že to bylo pomalé.

FS nad databazi samozrejme bude mit bezne operce velmi pomale, ale pro specialni pripad, kdy budou pozadovane specialni operace by to nemuselo byt tak spatne. obecne Je problem s rychlosti cteni/zapis. Tam je asi nejlepsi reseni pouzit FS, ktery umi zpracovat mnoho souboru a stejne je ukladat na nem, ale ne vsechny v jednom adresari, ale radeji nejaky squid styl.

Jediná cesta je to napsat sám. Klientů jsem vyzkoušel hodně. Dal jsem na rady všech okolo, "tenhle je nejrychlejší, zkus ho". Možná byl. Pro prvních 30 000 mailů. Jediný kdo zvládal tehdy 400 000 emailů byl KMail, nad maildirem a pop3. TB nad IMAPem je nepoužitelný. TB je vcelku nepoužitelný

To by mne hlavne zajimalo, jake nejcastejsi a casove kriticke operace se s temi 400k maily delaji a jestli jsou treba tridene a podobne. Protoze ja sice mam radove 100k mailu, ale vetsina jich je bokem, protoze mne zajimaji jednou za nekolik uherskych let.

Nevím proč, ale k podobným knihovnám mám averzi. Nechápu, proč nepoužít rovnou server. Výkonnostně si polepším.

Protoze sqlite databaze se dobre prenasi a pro jednoduche veci ala INSERT/SELECT bohate staci a napr driver v QT4 je univarzalni nezavisle na platforme. Pokud chci neco robustniho a sloziteho, tak to samozrejme radeji vrazim do postgresu (vcetne toho, ze je tam vestaveny velmi slusny fulltext)

[tomm]

No tohle me zajima. Ted jsem cca na 300K kouscich a rostu zhruba az o 100K rocne. Takze to brzo zacnuresit taky ... Drzim palce.