並列実行できるlocateコマンドの実装

並列実行できる locate コマンドを実装しました。

github/u1and0/gocate

locate コマンドはファイル・ディレクトリを高速に検索します。
updatedbコマンドでデータベースファイルをあらかじめ作成しておく必要があります。

gocateはGo言語のgoroutineでlocateコマンドを並列に実行している...ただそれだけです。
locateコマンドは古くからあってか、未だにシングルスレッド実行なので、マルチスレッド実行できるようにGoでラップしました。

インストール

$ go install github.com/u1and0/gocate

必須

• mlocate
• updatedb

基本的な使い方

db作成

$ sudo gocate -init

# 下記コマンドを並列に実行する
# $ sudo updatedb -U /var --output /var/lib/mlocate/var.db
# $ sudo updatedb -U /root --output /var/lib/mlocate/root.db
# $ sudo updatedb -U /run --output /var/lib/mlocate/run.db
# $ sudo updatedb -U /srv --output /var/lib/mlocate/srv.db
# $ sudo updatedb -U /proc --output /var/lib/mlocate/proc.db
# $ sudo updatedb -U /sys --output /var/lib/mlocate/sys.db
# $ sudo updatedb -U /etc --output /var/lib/mlocate/etc.db
# $ sudo updatedb -U /home --output /var/lib/mlocate/home.db
# $ sudo updatedb -U /tmp --output /var/lib/mlocate/tmp.db
# $ sudo updatedb -U /boot --output /var/lib/mlocate/boot.db
# $ sudo updatedb -U /mnt --output /var/lib/mlocate/mnt.db
# $ sudo updatedb -U /usr --output /var/lib/mlocate/usr.db
# $ sudo updatedb -U /dev --output /var/lib/mlocate/dev.db
# $ sudo updatedb -U /opt --output /var/lib/mlocate/opt.db

updatedb をルートディレクトリの下の階層に対して並列に実行し、複数のdbファイルを作っています。

gocate -init については別途記載しましたので、先に知りたい方は後の項目 updatedbの並列化 を読んでください。

並列処理でlocate検索

$ gocate keyword

keyword が含まれるファイル・ディレクトリを検索し、標準出力に表示します。

内部的には並列に下記コマンドを実行していることと同じです。

/usr/sbin/locate -d /var/lib/mlocate/var.db keyword
/usr/sbin/locate -d /var/lib/mlocate/boot.db keyword
/usr/sbin/locate -d /var/lib/mlocate/dev.db keyword
/usr/sbin/locate -d /var/lib/mlocate/etc.db keyword
/usr/sbin/locate -d /var/lib/mlocate/run.db keyword
/usr/sbin/locate -d /var/lib/mlocate/mnt.db keyword
/usr/sbin/locate -d /var/lib/mlocate/srv.db keyword
/usr/sbin/locate -d /var/lib/mlocate/home.db keyword
/usr/sbin/locate -d /var/lib/mlocate/sys.db keyword
/usr/sbin/locate -d /var/lib/mlocate/tmp.db keyword
/usr/sbin/locate -d /var/lib/mlocate/usr.db keyword
/usr/sbin/locate -d /var/lib/mlocate/opt.db keyword
/usr/sbin/locate -d /var/lib/mlocate/proc.db keyword
/usr/sbin/locate -d /var/lib/mlocate/root.db keyword

gocateオプション

$ gocate -h
parallel find files by name

Usage of gocate
        gocate [OPTION]... PATTERN...

-v, -version
        Show version
-d, -database DIRECTORY
        Path of locate database directory (default: /var/lib/mlocate)
-init
        updatedb mode
-U, -database-root DIRECTORY
        Store only results of scanning the file system subtree rooted at PATH  to  the  generated  database.
-o, -output DIRECTORY
        Write the database to DIRECTORY instead of using the default database directory. (default: /var/lib/mlocate)
-dryrun
        Just print command, do NOT run updatedb command.
-- [OPTION]...
        locate or updatedb command option

実行されるコマンドの確認

-dryrunオプションを付けて実行すると、実行されるコマンドの表示のみで、locate自体は走りません。

$ gocate -dryrun keyword
/usr/sbin/locate -d /var/lib/mlocate/var.db keyword
/usr/sbin/locate -d /var/lib/mlocate/boot.db keyword
/usr/sbin/locate -d /var/lib/mlocate/dev.db keyword
/usr/sbin/locate -d /var/lib/mlocate/etc.db keyword
/usr/sbin/locate -d /var/lib/mlocate/run.db keyword
/usr/sbin/locate -d /var/lib/mlocate/mnt.db keyword
/usr/sbin/locate -d /var/lib/mlocate/srv.db keyword
/usr/sbin/locate -d /var/lib/mlocate/home.db keyword
/usr/sbin/locate -d /var/lib/mlocate/sys.db keyword
/usr/sbin/locate -d /var/lib/mlocate/tmp.db keyword
/usr/sbin/locate -d /var/lib/mlocate/usr.db keyword
/usr/sbin/locate -d /var/lib/mlocate/opt.db keyword
/usr/sbin/locate -d /var/lib/mlocate/proc.db keyword
/usr/sbin/locate -d /var/lib/mlocate/root.db keyword

locate, updatedbオプションを全て使える

$ gocate -- -i --regex ".*ls.*cpp$"                       # locate mode
$ gocate -init -- --debug-pruning --add-prunenames NAMES  #updatedb mode

--の後に続く文字列は内部的にlocateまたはupdatedbへ渡されるので、すべてのコマンドオプションを使うことができます。
それぞれのオプションについて詳しくはman locate, man updatedb, 日本語版のmanは内容が薄いので、英語版LANG=en man locateのようにすることをおすすめします。
私も過去にlocateについて記事を書いています。
Qiita/u1and0/あなたの知らないlocateの世界

updatedbの並列化

gocateのマルチスレッドを活かすならば、dbファイルはなるべく同じくらいの大きさのファイルを複数作ったほうが良いです。
gocateはlocateコマンドをデータベースの数だけ複数走らせているだけなので、データベースが一つしかなければそもそも並列化の恩恵はありません。

dbをうまく分割して作ることでようやく並列化の恩恵にあやかれます。

dbファイルを複数作る方法は次のコマンドで一発です。

$ sudo gocate -init

このコマンドは次のコマンドをすべて実行していることと同じです。
デフォルトではルート直下にあるディレクトリすべてに対して、updatedbを実行します。

$ sudo updatedb -U /var --output /var/lib/mlocate/var.db
$ sudo updatedb -U /root --output /var/lib/mlocate/root.db
$ sudo updatedb -U /run --output /var/lib/mlocate/run.db
$ sudo updatedb -U /srv --output /var/lib/mlocate/srv.db
$ sudo updatedb -U /proc --output /var/lib/mlocate/proc.db
$ sudo updatedb -U /sys --output /var/lib/mlocate/sys.db
$ sudo updatedb -U /etc --output /var/lib/mlocate/etc.db
$ sudo updatedb -U /home --output /var/lib/mlocate/home.db
$ sudo updatedb -U /tmp --output /var/lib/mlocate/tmp.db
$ sudo updatedb -U /boot --output /var/lib/mlocate/boot.db
$ sudo updatedb -U /mnt --output /var/lib/mlocate/mnt.db
$ sudo updatedb -U /usr --output /var/lib/mlocate/usr.db
$ sudo updatedb -U /dev --output /var/lib/mlocate/dev.db
$ sudo updatedb -U /opt --output /var/lib/mlocate/opt.db

gocate -init ならこれらのコマンドを並列に実行してくれます。

updatedbのデータベース化するディレクトリの指定

データベース化のディレクトリを指定することもできます。
データベース化するディレクトリは-U または-database-root オプションで複数設定できます。 (updatedbのオプションと同じ)

$ sudo gocate -init -U /mnt -U /usr

これは/mntと/usr下のディレクトリそれぞれのディレクトリに対してデータベースを作るようにupdatedbを走らせます。

例えば、/mntと/usrの構造がこのとき
/usr
├── bin
├── include
├── lib
├── lib32
├── lib64 -> lib
├── local
├── sbin -> bin
├── share
└── src
/var
├── cache
├── db
├── empty
├── games
├── lib
├── local
├── lock -> ../run/lock
├── log
├── mail -> spool/mail
├── opt
├── run -> ../run
├── spool
└── tmp

$ sudo gocate -init -U /usr -U /var
warning: /usr/lib64 is not directory, it will be ignored for indexing.
warning: /usr/sbin is not directory, it will be ignored for indexing.
warning: /var/lock is not directory, it will be ignored for indexing.
warning: /var/mail is not directory, it will be ignored for indexing.
warning: /var/run is not directory, it will be ignored for indexing.
/usr/sbin/updatedb -U /usr/lib32 --output /var/lib/mlocate/usr_lib32.db
/usr/sbin/updatedb -U /usr/include --output /var/lib/mlocate/usr_include.db
/usr/sbin/updatedb -U /var/tmp --output /var/lib/mlocate/var_tmp.db
/usr/sbin/updatedb -U /var/empty --output /var/lib/mlocate/var_empty.db
/usr/sbin/updatedb -U /var/games --output /var/lib/mlocate/var_games.db
/usr/sbin/updatedb -U /usr/local --output /var/lib/mlocate/usr_local.db
/usr/sbin/updatedb -U /var/lib --output /var/lib/mlocate/var_lib.db
/usr/sbin/updatedb -U /usr/bin --output /var/lib/mlocate/usr_bin.db
/usr/sbin/updatedb -U /usr/share --output /var/lib/mlocate/usr_share.db
/usr/sbin/updatedb -U /var/local --output /var/lib/mlocate/var_local.db
/usr/sbin/updatedb -U /var/cache --output /var/lib/mlocate/var_cache.db
/usr/sbin/updatedb -U /var/db --output /var/lib/mlocate/var_db.db
/usr/sbin/updatedb -U /var/log --output /var/lib/mlocate/var_log.db
/usr/sbin/updatedb -U /usr/src --output /var/lib/mlocate/usr_src.db
/usr/sbin/updatedb -U /var/opt --output /var/lib/mlocate/var_opt.db
/usr/sbin/updatedb -U /var/spool --output /var/lib/mlocate/var_spool.db
/usr/sbin/updatedb -U /usr/lib --output /var/lib/mlocate/usr_lib.db

/usr/lib32 のディレクトリは /var/lib/mlocate/usr/lib32.db というファイル名のデータベースになります。
/usr, /var下にあるディレクトリ以外のファイルやシンボリックリンクはデータベース化に対して無視されます。
無視されるときはwarningとして標準出力に表示されます。
-Uを使ってwarningがあまりにも多いときには、ファイルが少ないディレクトリの階層まで登りましょう。

実行されるコマンドを確認したいときは-dryrunオプションを指定すると、updatedb自体は走りません。

$ sudo gocate -init -dryrun -U /usr -U /var

dbファイルの出力先

dbファイルの出力先は-o -outputオプションで決められます。(updatedbのオプションと同じ)
デフォルトは/var/lib/mlocateです。

$ sudo gocate -init -o /home/myhome/.locate

/home/myhome/.locate下に複数のdbファイルが作成されます。
-Uと-oは共用可能です。
-initが指定されていないと動作しません。

さいごに...並列化≠高速化

高速化を目指して並列化locateを製作したわけですが、
必ずしも元祖locateより速度が出るわけではありません。
データベース分割の仕方が鍵のようです。
当然お使いのPCのリソース(CPUやHDD,SSDの違い)にも左右されます。
goroutine(Goの並列化処理)を呼び出している間に元祖locateの検索が片付いてしまうほどのちょっとした検索だったら元祖に勝てません。

定量的なベンチマークとってないけど、定性的には限定的条件クリアしないとlocateには速度で勝てない。

条件
* データベースを2以上に分ける
* データベース検索の時間が1000ms以上掛かるようなdbの大きさ大きさ
* コア数2以上
* ドライブがSSDではなくHDDhttps://t.co/HXJpCT1qrC

— ＆Ｏｕ１ (@U1and0) September 2, 2021

1と3については当然ながら分けないと並列も糞もないので、速度で勝てない。
2についてはgoroutine起動している間にlocateの仕事が済むようなタイムフレームであれば、当然無駄にgoroutine起動しないlocateの方が速い。
4は2と関連して時間のかかる検索じゃないとlocateの方が早く仕事を終えてしまう

— ＆Ｏｕ１ (@U1and0) September 2, 2021

dbサイズが均一であることも大事。一個だけ巨大なdbだとそいつの検索に足を引っ張られて結局パフォーマンス良くない。

— ＆Ｏｕ１ (@U1and0) September 2, 2021

細かくdbを分ければ分けるほど窓口混雑の問題と一緒でdb均一にすることに近づく

— ＆Ｏｕ１ (@U1and0) September 2, 2021