Vyhledávání pomocí příkazu locate a implementace v Unity

Jednou z informací, které jsem přinesl v předchozím zápisku o Unity je ta, že Dash pro vyhledávání souborů a složek používá, krom Zeitgeistu, konzolový příkaz locate. Pokud jste alespoň trochu v prostředí terminálu pobyli, jistě jste ho objevili. Také jste si určitě všimli, že je velmi rychlý a že prohledává celý lokální filesystém, takže vám najde jak soubory v /usr/bin, tak na vaší pracovní ploše. Řekl bych, že většina uživatelů příkaz používá v jeho základní formě - locate hledaný_výraz a dál to moc neřeší. locate má ale o trochu větší potenciál a ten bych si dovolil trochu poodhalit právě v souvislosti s Unity, kde je jeho využití na daleko nižší úrovni, než bych očekával. ...

Rychlost locate je dána tím, že vyhledává v předpřipraveném (inkrementálně komprimovaném) indexu, resp. databázi, kterou pro něj připravuje program updatedb. Možná jste si všimli také toho, že vám nenašel soubory, které jste vytvořili teprve před chvílí, což je dáno tím, že se index běžně aktualizuje pomocí anacronu jednou denně.

Implementace locate v Ubuntu vypadá následovně. Nejjednodušší je podívat se do dokumentace (man locate, man updatedb), ale to není taková legrace, pojmu to investigativněji:

$ which locate
/usr/bin/locate

$ ls -l /usr/bin/locate
lrwxrwxrwx 1 root root 24 Apr 17 2012 /usr/bin/locate -> /etc/alternatives/locate

$ ls -l /etc/alternatives/locate
lrwxrwxrwx 1 root root 16 Apr 17 2012 /etc/alternatives/locate -> /usr/bin/mlocate

$ which updatedb
/usr/bin/updatedb

$ ls -l /usr/bin/updatedb
lrwxrwxrwx 1 root root 26 Apr 17 2012 /usr/bin/updatedb -> /etc/alternatives/updatedb

$ ls -l /etc/alternatives/updatedb
lrwxrwxrwx 1 root root 25 Apr 17 2012 /etc/alternatives/updatedb -> /usr/bin/updatedb.mlocate

A kdepak se nachází databáze a konfigurační soubor?
V jednom terminálu si spustím fatrace s příslušným filtrem a následně ve druhém updatedb (oboje s právy roota). Pak si přečtu výstup fatrace:

$ sudo fatrace | egrep 'updatedb.*\.(conf$|db$)' | uniq -f2
updatedb(7722): O /etc/updatedb.conf
updatedb(7722): O /var/lib/mlocate/mlocate.db

K souborům se samozřejmě dostanete i přímo pomocí samotného locate, pokud víte co hledáte, o tom žádná.

Příkaz locate je v Ubuntu jen zástupcem programu mlocate, který ve skutečnosti výsledky dodává a zrovna tak updatedb jen odkazuje na updatedb.mlocate. Oboje je v systému odkazováno přes správce alternativ, kde mohou být aplikace nahrazeny jinými se zachováním původního příkazu.

V Unixu se program locate objevil kolem roku 1983, jeho GNU variantu v linuxových systémech postupně vytlačoval bezpečnější slocate a ten zas efektivnější mlocate. to "m" na začátku mlocate je od slova merge, při aktualizaci se zpracovávají pouze změny a ty se přidávají do původní databáze, nemusí se tak pokaždé indexovat všechno znovu. Založeno je to na tom, že mlocate si v databázi uchovává i čas posledních změn adresářů a tak při aktualizaci přeindexuje pouze obsah těch, ve kterých se od posledně něco změnilo. Pokud přepíšu jméno jednoho souboru v home adresáři, trvá aktualizace databáze příkazem updatedb téměř neměřitelný čas na C2D s U12.10 na SSD disku, přičemž databáze obsahuje 588 212 záznamů. locate následně soubor neomylně najde také během pár milisekund.

Při použití příkazu locate dostane uživatel na výstup jen soubory, které jsou pro něj viditelné, jsou vždy kontrolována práva nadřazeného adresáře. Nedostane tedy například soubory z home jiného uživatele. Toto ale závisí na nastavení databáze, při použití přepínače -l s parametrem 0, nebo no, je možné vytvořit databázi, která práva řešit nebude a uživatel se dostane ke všem souborům bez výjimky. Ochrana dat systémové databáze je zajištěna i tím, že soubor /var/lib/mlocate/mlocate.db umožňuje čtení pouze rootovi a členům skupiny mlocate a tak se k jejímu obsahu normální uživatel dostane pouze příkazem locate.

V konfiguračním souboru /etc/updatedb.conf můžete definovat rozsah indexace. Na Ubuntu 12.10 vypadá config následovně:

PRUNE_BIND_MOUNTS="yes"
# PRUNENAMES=".git .bzr .hg .svn"
PRUNEPATHS="/tmp /var/spool /media /home/.ecryptfs"
PRUNEFS="NFS nfs nfs4 rpc_pipefs afs binfmt_misc proc smbfs autofs iso9660 ncpfs coda devpts ftpfs devfs mfs shfs sysfs cifs lustre_lite tmpfs usbfs udf fuse.glusterfs fuse.sshfs curlftpfs ecryptfs fusesmb devtmpfs"

PRUNE* znaméná zakázané, tedy ty, které se indexovat nebudou a mohou to být jména (PRUNENAMES), cesty (PRUNEPATHS) i filesystémy (PRUNEFS). Jednotlivé položky seznamu se oddělují mezerou.

Další možnosti přizpůsobení indexu spočívají v použití přepínačů příkazu updatedb, kde můžete části configu přerazit jinou definicí, i ovlivnit další parametry indexace. Některé dále proberu.

Implementace v Dashi - unity-lens-files
Jak jsem zmínil, locate používá i výchozí Lens pro vyhledávání souborů a složek v Unity. Protože locate standardně vyhledává v téměř celém sytému, je následná filtrace za pomoci regulárních výrazů časově náročná. Proto v Unity použitá vyhledávací utilita limituje výstup locate přepínačem -l na 128 výsledků a pokud je tento počet dosažen, nedostane se do Dashe výsledek žádný, i když skutečně relevantní je třeba jen jeden soubor, nebo adresář.

Řešením by bylo vyrobit databázi externí jen pro home adresář uživatele a pomocí přepínače --prunepaths vyhodit adresáře, které se do výsledků nemají promítat a které Lens (resp Scope za tím stojící) stejně následně filtruje, tedy skryté adresáře a soubory. Stačí projet home uživatele, vytvořit seznam zakázaných adresářů alespoň na této základní úrovni a s tím teprve databázi zaindexovat. Tento seznam není problém aktualizovat před každou aktualizací databáze a výsledky by se mnohonásobně zlepšily. Například takto:

$ updatedb -l 0 -o $HOME/mlocate.db -U $HOME --prunepaths "$(find $HOME -maxdepth 1 -type d -regex ".*/\..*" | sed 's/ /\\ /g' | tr '\n' ' ')"

Výsledná databáze se po vyhození skrytých adresářů na mém systému smrskne ze 71155 souborů na 5871 jen pro home adresář. A to už je rozdíl dvou řádů oproti 588212 souborům v hlavní databázi. Vytvoření nové databáze pomocí předchozího pžíkazu trvalo v mém případě pár milisekund a to i na systému U13.04 s běžným pevným diskem, kde je sice v home souborů cca šestkrát méně, ale i po přepočtu je to zanedbatlná zátěž, která se navíc v tomto rozsahu provede pouze jednou.

Máte tedy novou databázi a pokud ji budete chtít použít, musíte na ni příkaz locate nasměrovat. K tomu slouží přepínač -d.

$ locate -d ~/mlocate.db hledaný_výraz

Nyní příklad z reálného života. Mám nainstalované prostředí Cinnamon, tudíž mám v systému docela dost souborů, které mají v cestě řetězec cinnamon, konkrétně:

$ locate -iec cinnamon
1566

Z toho je v běžném uživatelském prostoru pouze šest obrázků, které jsem udělal pro potřeby mé recenze a ty jsem chtěl hledat. Dash to vzdá kvůli nadměrnému množství výsledků, které není schopen efektivně filtrovat a tak mi neukáže nic. Teď neřeším Zeitgeist, který by soubory nelézt mohl, pokud již byly v prostředí otevírány, jeho historii jsem při testování locate vymazal.

Teď výsledek z databáze, kterou jsem před chvílí vytvořil:

$ locate -iecd ~/mlocate.db cinnamon
7

To je skutečný počet relevantních výsledků + 1, protože se na výstup dostane i adresář ~/.cinnamon, jehož obsah byl sice z indexace vyřazen, nikoliv však on sám. Vyfiltrovat i tento adresář je otázkou pikosekundy a na rychlost vyhledávání to nebude mít žádný vliv.

Kde je tedy problém? Proč to vývojáři Ubuntu již dávno neoptimalizovali? Když se kouknete do zdrojového kódu, najdete tam toto (je to v jazyce Vala):

// FIXME: we could limit the search to specific directories, but using regex
// matching slows down the search considerably
string[] argv = { "locate", "-i", "-e", "-l", "%u".printf (MAX_RESULTS),
"*%s*".printf (query.replace (" ", "*")) };

Možná mi něco uniká, ale nevidím žádný problém vést si databázi vlastní pro každého uživatele, přinejmenším ne výkonostní, natož prostorovou. Je fakt, že jsem troškař a většinu souborů mám na neindexovaných externích filesystémech, ale přesto. Na zkoušku jsem si do home adresáře přidal 2927 nových souborů v necelých dvou stovkách adresářů a pak to nechal přeindexovat. Trvalo to celé 22 ms. Když jsem je opět odebral, trvala aktualizace 16 ms. Filtrování základní databáze regexy, aby se dospělo ke stejnému výsledku, trvá o několik řádů déle a to po každém napsaném znaku. Nebyl by problém přepsat symlink locate na vlastní, ale to by mohlo mít dopad na další aplikace. Dal by se samozřejmě přepsat zdroják unity-lens-file, překompilovat a přeinstalovat, to by také nebylo tak komplikované. Nebo najít schpnější náhradu, bezpochyby jsou.


No nic, připomenu alespoň další přepínače příkazu locate, které mohou zefektivnit vaše hledání. Předem zmíním to, že locate můžete předhodit celý seznam řetězců oddělených mezerami, hledat se budou všechny (pokud nepoužijete přepínač -r, viz dále).

-i        nerozlišuje malá a velká písmena
-e        vypíše jen soubory, které skutečně existují
-b        vyhledávat se bude pouze v názvech souborů (jinak jsou prohledávány celé cesty). S tímto přepínačem se pojí ještě jedna finta - když řetězec uvedete zpětným lomítkem (\NAME), bude hledáno přesně zadané jméno, nikoliv jméno, které zadaný vzor obsahuje.
-c        vypíše místo výsledků jen jejich počet
-l        umožní definovat maximální počet výsledků, po kterém locate skončí
-r        umožňuje zadat regulární výraz, kterým bude výstup filtrován. Nedá se použít jen pro část hledaných řetězců, ale lze použít víckrát v jednom příkazu.
--regexp  všechny hledané vzory jsou interpretovány jako rozšířené regulární výrazy