深度科技的anything快速檢索技術(shù)研究

張木梁 張 磊 秦 娣

1(武漢深之度科技有限公司技術(shù)部 北京 100080) 2(武漢深之度科技有限公司研發(fā)中心 北京 100080) 3(武漢深之度科技有限公司市場部 北京 100080) (zhangmuliang@deepin.com)

為了能夠向用戶提供一個(gè)高速的、基于文件名搜索的離線文件搜索功能，我們引入了“anything快速檢索”技術(shù).對(duì)于“anything”的定義是Something like everything, but nothing is really like anything….

而anything之所以叫anything，是受到了Windows下everything軟件的啟發(fā)[1].原來在Linux中有一個(gè)類似的rlocate程序[2]，但是那個(gè)程序有點(diǎn)太老了，效率低下，效率方面的設(shè)計(jì)與當(dāng)前時(shí)代不相稱.主要是出于與Linux傳統(tǒng)桌面結(jié)合得比較緊密，優(yōu)化起來對(duì)系統(tǒng)其他組件影響都很大，很多發(fā)行版就不會(huì)在這方面進(jìn)行優(yōu)化.

1 基礎(chǔ)索引設(shè)計(jì)

1.1 簡要分析

在Linux下，最常用的文件搜索軟件是find，它會(huì)遞歸遍歷每個(gè)目錄，針對(duì)每個(gè)目錄與文件按照用戶給出的參數(shù)過濾出符合條件的目錄與文件，并打印出來.

在命令行模式下，find使用很廣，功能強(qiáng)大，不僅可以根據(jù)文件名查找文件，還可以根據(jù)文件類型、權(quán)限、修改時(shí)間、大小，甚至與其他軟件配合對(duì)文件進(jìn)行過濾.但是在圖形界面下，用戶最常用的仍是根據(jù)文件名對(duì)文件進(jìn)行查找，這是anything面向的核心問題.

使用find搜索時(shí)，如果已經(jīng)搜索過，則對(duì)應(yīng)的文件與目錄信息將會(huì)被緩存在內(nèi)存中，可以大大加速搜索.當(dāng)然，root用戶可以運(yùn)行sysctl -w vm.drop_caches=3來清除這些緩存.但是，即使使用了緩存，在僅使用文件名搜索的前提下，find的搜索速度仍然是不理想的.

find搜索會(huì)通過系統(tǒng)調(diào)用遍歷每個(gè)目錄的內(nèi)容，讀取其中的文件列表，再根據(jù)文件列表中的inode號(hào)找到對(duì)應(yīng)的inode信息，接著讀取inode類型為目錄中的文件內(nèi)容……如此遞歸查找.可以看到這個(gè)查找過程經(jīng)過多重遞歸，會(huì)不斷打開目錄(需要系統(tǒng)調(diào)用與內(nèi)存復(fù)制)，而且文件名在其中與inode信息夾雜在一起，會(huì)嚴(yán)重減緩純粹基于文件名的查找[3].

anything設(shè)計(jì)是與find完全不同的，不同之處在其內(nèi)部僅保存了文件(目錄)名以及必要的歸屬關(guān)系，以便進(jìn)行雙向的查找.所有的數(shù)據(jù)都存放在用戶態(tài)空間，沒有額外的系統(tǒng)調(diào)用開銷與內(nèi)存復(fù)制開銷.此外，考慮到數(shù)據(jù)訪問的最大可能性，相鄰數(shù)據(jù)是最有可能被一起訪問的數(shù)據(jù)，因此anything可以最大限度利用處理器的高速緩存，使得軟件的運(yùn)行性能更好.

總的來說，anything的設(shè)計(jì)理論上快速的主要原因是：

1) 相比于find，它不依賴于額外的系統(tǒng)調(diào)用與函數(shù)調(diào)用，減少了大量的系統(tǒng)調(diào)用開銷與內(nèi)存復(fù)制開銷；

2) 它使用的文件系統(tǒng)存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)針對(duì)性極強(qiáng)，內(nèi)容非常緊湊，使用也很高效.

1.2 內(nèi)部存儲(chǔ)設(shè)計(jì)

在經(jīng)典設(shè)計(jì)中，文件系統(tǒng)應(yīng)該使用數(shù)據(jù)結(jié)構(gòu)中的樹來存儲(chǔ).樹中的每個(gè)節(jié)點(diǎn)有一個(gè)字符串作為名稱，有N個(gè)指針指向其N個(gè)子節(jié)點(diǎn)，還有一個(gè)指針指向其父節(jié)點(diǎn)，以支持從上至下以及從下至上的雙向樹遍歷.這種結(jié)構(gòu)的優(yōu)點(diǎn)是修改很方便，不管是刪除、添加還是重命名每個(gè)節(jié)點(diǎn)都很快.但是在遍歷讀取時(shí)卻因?yàn)樾枰煌５闹羔樚D(zhuǎn)，會(huì)導(dǎo)致處理器的高速緩存頻頻失效，從而使得訪問速度降低，而又因?yàn)楦鱾€(gè)節(jié)點(diǎn)都是分散的，無法體現(xiàn)出相鄰節(jié)點(diǎn)的訪問相關(guān)性，所以也難以進(jìn)行有效的內(nèi)存訪問優(yōu)化.

下面是上述樹型設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)內(nèi)存消耗的分析.為簡單起見，先假設(shè)文件系統(tǒng)是一棵深度為D、分叉為N(N>1)的完全樹，這樣，在整棵樹中一共有葉節(jié)點(diǎn)ND-1個(gè)、非葉節(jié)點(diǎn)N0+N1+N2+…+ND-2=(ND-1-1)(N-1)個(gè).對(duì)于每個(gè)葉節(jié)點(diǎn)而言，忽略其文件名，其他部分的內(nèi)存僅包括一個(gè)指向其自身上一級(jí)的指針；對(duì)于每個(gè)非葉節(jié)點(diǎn)而言，忽略其文件名，其他部分的內(nèi)存也包含一個(gè)指向其自身上一級(jí)的指針(假設(shè)根節(jié)點(diǎn)也有一個(gè)父節(jié)點(diǎn)指針，但是其值為空)，以及N個(gè)指向子節(jié)點(diǎn)的指針，指針數(shù)一共是P=ND-1+(N+1)(ND-1-1)(N-1)=(2×ND-N-1)(N-1)個(gè)，對(duì)于64 b系統(tǒng)而言，需要的內(nèi)存是8×P個(gè)字節(jié).

在anything內(nèi)部存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的早期階段，使用樹來保存文件系統(tǒng)結(jié)構(gòu)也曾被考慮過，但是顧及高速緩存失效與指針過大的問題，顯然在此處使用線性存儲(chǔ)設(shè)計(jì)更好.所以就有了下面anything的數(shù)據(jù)結(jié)構(gòu)來保存文件系統(tǒng)數(shù)據(jù)的內(nèi)部存儲(chǔ)結(jié)構(gòu).

從表1可以看出，anything內(nèi)部文件系統(tǒng)存儲(chǔ)頭部為4 B的MAGIC和4 B的緩存區(qū)，之所以使用4 B，而不是64 b系統(tǒng)上的8 B是因?yàn)閷?duì)于1 000萬個(gè)文件與目錄的文件系統(tǒng)而言，使用上述結(jié)構(gòu)僅需約250 MB內(nèi)存，因此不需要8 B的長度與偏移量，從而可以節(jié)約一半的指針長度.在8 B之后是一個(gè)C語言風(fēng)格的字符串，對(duì)應(yīng)的是此文件系統(tǒng)樹的根目錄名，例如“”或者“homedeepin”，這個(gè)根目錄要求“”開頭，“”結(jié)尾，整個(gè)字符串以空字符結(jié)尾.

表1 anything的數(shù)據(jù)結(jié)構(gòu)

在上述頭部數(shù)據(jù)之后即為正式的文件樹結(jié)構(gòu)，每個(gè)文件或者目錄名均是一個(gè)C語言風(fēng)格的、以空字符結(jié)尾的字符串.表1中大寫的TAG標(biāo)簽代表一個(gè)目錄的結(jié)束，并且包含了自身父目錄節(jié)點(diǎn)的偏移量；小寫的tag標(biāo)簽代表一個(gè)文件信息的結(jié)束，并且以標(biāo)簽長度代表自身是文件還是目錄.在每個(gè)字符串之后是一個(gè)標(biāo)簽(tag)，對(duì)于文件來說，此標(biāo)簽占據(jù)1 B，標(biāo)識(shí)這是一個(gè)文件.對(duì)于目錄而言，此標(biāo)簽占據(jù)4 B，標(biāo)識(shí)這是一個(gè)目錄，而且記錄了這個(gè)目錄中第1個(gè)文件的偏移量，按照之前的分析，這個(gè)偏移量僅需要4 B就夠了，通過目錄的這個(gè)4 B標(biāo)簽就可以向下遍歷.如此反復(fù)，直到此目錄結(jié)束，將是一個(gè)單獨(dú)的值為0的字節(jié)，其后又是一個(gè)4 B的標(biāo)簽(TAG)，此標(biāo)簽除了標(biāo)識(shí)目錄結(jié)束之外，還記錄了本級(jí)目錄的父節(jié)點(diǎn)的偏移量，如此，就可以通過這個(gè)標(biāo)簽支持向上遍歷.此外，當(dāng)本級(jí)目錄結(jié)束之后將開始下級(jí)目錄的存儲(chǔ)，這樣即可以使得1棵目錄樹的數(shù)據(jù)是緊緊相鄰的，在讀取時(shí)非常高效，在刪除時(shí)也非常方便.

上述結(jié)構(gòu)不斷重復(fù)，直到整個(gè)文件樹結(jié)束.

由上述結(jié)構(gòu)可以看出，相鄰的節(jié)點(diǎn)，即同級(jí)目錄下的文件都存儲(chǔ)在一起，這樣有利于內(nèi)存訪問優(yōu)化.而且將8 B指針優(yōu)化為4 B偏移量，也節(jié)省了存儲(chǔ)空間，減少了無效數(shù)據(jù)的存儲(chǔ)與無效內(nèi)存的訪問，此外，線性存儲(chǔ)也便于數(shù)據(jù)文件的存盤與讀盤.

對(duì)于每個(gè)葉節(jié)點(diǎn)，需要耗費(fèi)1 B存儲(chǔ)標(biāo)簽，對(duì)于每個(gè)非葉節(jié)點(diǎn)需要消耗4 B存儲(chǔ)子節(jié)點(diǎn)的偏移量，還有4 B用來存儲(chǔ)其所有子節(jié)點(diǎn)指向其本身的偏移量，則一共需要ND-1+8×(ND-1-1)(N-1)=(ND+7×ND-1-8)(N-1)個(gè)字節(jié)，對(duì)比之前樹需要耗費(fèi)的8×P=8×(2×ND-N-1)(N-1)個(gè)字節(jié)，易知在最好情況下是其內(nèi)存的116，在最差情況下是其內(nèi)存的13.

當(dāng)使用此結(jié)構(gòu)進(jìn)行搜索時(shí)不需要再通過樹狀搜索，而可以使用線性搜索，從前至后進(jìn)行字符串匹配，并跳過數(shù)據(jù)量較小的標(biāo)簽即可，這樣也方便進(jìn)行搜索分頁.

當(dāng)搜索到某個(gè)名稱符合要求時(shí)，即可使用目錄結(jié)尾的標(biāo)簽定位到父目錄的偏移量，繼而構(gòu)成完整的路徑，返回給調(diào)用者.

在這里也可以發(fā)現(xiàn)，其實(shí)對(duì)于搜索而言，程序并不需要保存子節(jié)點(diǎn)的偏移量，只需要父節(jié)點(diǎn)的偏移量即可，這樣還可以把額外的內(nèi)存再節(jié)省約一半，但是這會(huì)導(dǎo)致文件系統(tǒng)更改(文件與目錄刪除、添加、重命名)時(shí)變更速度較慢.若僅需使用離線搜索，即不考慮文件系統(tǒng)改動(dòng)的問題，則內(nèi)存消耗確實(shí)還可通過使用上述方法進(jìn)一步減少.

此外，由于需要至少1位來標(biāo)識(shí)文件或者目錄，因此最大的偏移量不可能是232，即最多能存儲(chǔ)231或2 GB內(nèi)存的數(shù)據(jù).為了可擴(kuò)展性考慮，在內(nèi)部其實(shí)保留了2位數(shù)據(jù)以進(jìn)行文件標(biāo)識(shí)，因此，最多可以使用1 GB內(nèi)存作為內(nèi)部存儲(chǔ).根據(jù)之前的測試估算，大約能保存4 000萬個(gè)文件或目錄，在目前看來是足夠的.

1.3 理論對(duì)比與實(shí)際測試

在進(jìn)行實(shí)際測試驗(yàn)證之前，首先作理論對(duì)比.

在預(yù)估為包含38.7萬個(gè)文件(目錄)、其中有大約4萬個(gè)目錄的情況下：

2) 若使用樹進(jìn)行數(shù)據(jù)存儲(chǔ)與搜索，在遍歷過程中需要持續(xù)生成節(jié)點(diǎn)，在搜索過程中需要遞歸遍歷(遞歸函數(shù)調(diào)用)各個(gè)節(jié)點(diǎn)，然后對(duì)每個(gè)節(jié)點(diǎn)調(diào)用strstr函數(shù)，即需要有4萬次遞歸函數(shù)調(diào)用以及38.7萬次strstr函數(shù)調(diào)用.當(dāng)然，在此期間高速緩存也會(huì)頻頻失效.在搜索過程中，由于不再需要系統(tǒng)調(diào)用，以及額外的從內(nèi)核態(tài)到用戶態(tài)的內(nèi)存復(fù)制(這個(gè)開銷相對(duì)較小)，這種搜索方法應(yīng)該會(huì)至少比find快一個(gè)數(shù)量級(jí).

3) 使用anything也首先需要進(jìn)行目錄樹遍歷，但是在搜索過程中需要從前向后，反復(fù)在線性存儲(chǔ)空間中調(diào)用strstr即可，即大約需要38.7萬次strstr調(diào)用.沒有系統(tǒng)調(diào)用開銷，沒有內(nèi)存復(fù)制開銷，而且由于內(nèi)存緊湊，又是單向內(nèi)存順序訪問，因此內(nèi)存訪問進(jìn)入高速緩存浪費(fèi)極少，非常自然，使用也很流暢，比目錄樹狀遞歸跳轉(zhuǎn)顯然要高效很多.

可以看出，從理論設(shè)計(jì)來看，anything的效率要明顯優(yōu)于前2種設(shè)計(jì)方案.

為了進(jìn)一步確定上述猜測是否正確，我們開發(fā)了3個(gè)程序來實(shí)際驗(yàn)證我們的理論設(shè)計(jì).

程序2：遍歷目錄時(shí)建立樹狀結(jié)構(gòu)后，再基于內(nèi)存樹存儲(chǔ)進(jìn)行搜索.

程序3：遍歷目錄時(shí)構(gòu)建基礎(chǔ)索引完成后，再基于基礎(chǔ)索引進(jìn)行搜索.

這3個(gè)程序的關(guān)鍵源碼分別參見程序1～3.

程序1. 遞歸遍歷直接搜索文件名.

void walkdir (const char* path, const char* query, int* count)

{

DIR* dir=opendir(path);

if (0==dir)

return;

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR &&

de->d_type!=DT_REG &&

de->d_type!=DT_LNK)

continue;

if (strstr(de->d_name, query)!=0) {

if (*count<10)

*count, path, de->d_name);

*count=*count+1;

}

if (de->d_type==DT_DIR) {

char fullpath[PATH_MAX];

de->d_name);

walkdir(fullpath, query, count);

}

}

closedir(dir);

}

程序2. 遞歸遍歷建立樹后再搜索.

typedef struct __fs_tree_item__ {

char* name;

int kids_count;

struct __fs_tree_item__* parent;

struct __fs_tree_item__** kids;

} fs_tree_item;

void walkdir(const char* path, fs_tree_item* fti)

{

DIR* dir=opendir(path);

if (0==dir)

return;

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR && de->

d_type!=DT_REG && de->d_type

!=DT_LNK)

continue;

fs_tree_item*kid=calloc(1, sizeof(

fs_tree_item));

if (kid==0) {

printf(″kid malloc error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

kid->name=strdup(de->d_name);

if (kid->name==0) {

free(kid);

printf(″kid strdup error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

kid->parent=fti;

fs_tree_item** kids=realloc(

fti->kids, (fti->kids_count+1)*

sizeof(void*));

if (kids==0) {

free(kid->name);

free(kid);

printf(″kids realloc error, path: %s,

name: %s, count: %d ″, path,

de->d_name, fti->kids_count);

continue;

}

fti->kids=kids;

fti->kids[fti->kids_count]=kid;

fti->kids_count++;

if (de->d_type==DT_DIR) {

char fullpath[PATH_MAX];

de->d_name);

walkdir(fullpath, kid);

}

}

closedir(dir);

}

void search_tree(const char* path, fs_tree_item* root, const char* query, int* count)

{

if (strstr(root->name, query)!=0) {

if (*count<10)

path, root->name);

*count=*count+1;

}

char fullpath[PATH_MAX];

root->name);

for (int i=0;ikids_count;i++)

search_tree(fullpath, root->kids[i],

query, count);

}

程序3. 遞歸遍歷構(gòu)建好基礎(chǔ)索引后再搜索 (需使用anything庫與頭文件).

static int walkdir(const char* name, fs_buf* fsbuf, uint32_t parent_off)

{

DIR* dir=opendir(name);

if (0==dir)

return EMPTY_DIR;

uint32_t start=get_tail(fsbuf);

struct dirent* de=0;

while ((de=readdir(dir))!=0) {

if (strcmp(de->d_name, ″.″)==0‖strcmp(de->d_name, ″..″)==0)

continue;

if (de->d_type!=DT_DIR &&

de->d_type!=DT_REG &&

de->d_type!=DT_LNK)

continue;

append_new_name(fsbuf, de->

d_name, de->d_type==

DT_DIR);

}

closedir(dir);

if (start==get_tail(fsbuf))

return EMPTY_DIR;

uint32_t end=get_tail(fsbuf);

append_parent(fsbuf, parent_off);

uint32_t off=start;

while (off

if (is_file(fsbuf, off)) {

off=next_name(fsbuf, off);

continue;

}

set_kids_off(fsbuf, off, get_tail(fsbuf));

char path[PATH_MAX];

get_name(fsbuf, off));

if (walkdir(path, fsbuf, off)==

EMPTY_DIR)

set_kids_off(fsbuf, off, 0);

off=next_name(fsbuf, off);

}

return NONEMPTY_DIR;

}

#define MAX_RESULTS 10

static uint32_t search_by_fsbuf(fs_buf*fsbuf, const char* query)

{

uint32_t name_offs[MAX_RESULTS], end_off=get_tail(fsbuf);

uint32_t count=MAX_RESULTS,

start_off=first_name(fsbuf);

search_files(fsbuf, &start_off, end_off,

query, name_offs, &count);

char path[PATH_MAX];

for (uint32_t i=0; i

char *p=get_path_by_name_off(fsbuf,

name_offs[i], path, sizeof(path));

printf(″%’u: %c %s ″, i+1, is_file(fsbuf, name_offs[i]) ? ′F′ : ′D′, p);

}

uint32_t total=count;

while(count==MAX_RESULTS) {

search_files(fsbuf,&start_off, end_off, query, name_offs,&count);

total+=count;

}

return total;

}

在程序里單獨(dú)在搜索前后調(diào)用gettimeofday獲取時(shí)間戳，進(jìn)行差分比較，在有緩存的情況下，3種方法搜索的耗時(shí)分別為：

1) 邊遞歸遍歷目錄邊匹配(類find)，10.1 s；

2) 遞歸遍歷目錄后用樹存儲(chǔ)目錄結(jié)構(gòu)再搜索，77 ms；

3) 遞歸遍歷目錄后用基礎(chǔ)索引存儲(chǔ)目錄結(jié)構(gòu)再搜索，8 ms.

如果使用perf,strace與google perftools進(jìn)行性能剖析，可以看出在第1個(gè)程序里主要的程序耗時(shí)(88%)都花在了opendir()的調(diào)用上.第2、第3個(gè)程序在搜索階段運(yùn)行沒有與內(nèi)核交互，而且時(shí)間過短，采樣過少，因此沒有有意義的數(shù)據(jù)產(chǎn)生，但是可以看出使用基礎(chǔ)索引技術(shù)比使用樹的方法快了接近10倍.

2 二級(jí)索引設(shè)計(jì)

上述基礎(chǔ)索引的設(shè)計(jì)已經(jīng)大大提高了基于文件名的搜索速度(相對(duì)于find而言)，但這種搜索方法仍然需要從前至后遍歷每個(gè)文件名進(jìn)行搜索[4].從表面上看，因?yàn)樾枰獙?duì)每個(gè)文件名進(jìn)行檢查，以得知其是否匹配搜索串，理論上不會(huì)有更快的方法了.但事實(shí)上，我們還可以做得更好，那就是使用倒排索引(inverted index)實(shí)現(xiàn)二級(jí)索引.

倒排索引的原理是對(duì)目標(biāo)字符串進(jìn)行切割，得到其所有的子字符串，然后將這些子字符串存放到對(duì)應(yīng)的索引數(shù)據(jù)結(jié)構(gòu)中，當(dāng)用戶輸入對(duì)應(yīng)的子字符串時(shí)能立刻找到相應(yīng)的原始字符串[5].

例如原始字符串為china，則可以得到c,h,i,n,a,ch,hi,in,na,chi,hin,ina,chin,hina與china，一共5+4+3+2+1=15個(gè)子字符串，假設(shè)china這個(gè)字符串的偏移量(或者指針)是100，則可以得到{“c”→100}, {“h”→100}, …, {“china”→100}等25個(gè)索引.當(dāng)用戶輸入hi時(shí)，即可以立刻得到{“hi”→100}這個(gè)索引，然后將100返回給調(diào)用者，由調(diào)用者通過這個(gè)偏移量或者指針得到“china”這個(gè)字符串.

在簡單的倒排索引設(shè)計(jì)中，一般使用Hash鏈表或者Trie樹作為索引數(shù)據(jù)結(jié)構(gòu)[6].anything使用的是Hash鏈表，其工作原理是，當(dāng)用戶輸入某個(gè)查詢字符串(如hi)時(shí)，anything將首先對(duì)字符串進(jìn)行一次Hash運(yùn)算，得到Hash數(shù)組中的下標(biāo)值，然后根據(jù)下標(biāo)值即可得到對(duì)應(yīng)的索引數(shù)組，在索引數(shù)組里順序查找即可得到對(duì)應(yīng)的索引(即hi)，從而可以獲取到所有的包含hi字符串的原始字符串的偏移量，將其返回給調(diào)用者.

對(duì)于38.7萬個(gè)文件與目錄遍歷的實(shí)測表明，其索引內(nèi)存占用將超過2 GB，這完全是不可接受的.而對(duì)anything在對(duì)二級(jí)索引進(jìn)行優(yōu)化后，內(nèi)存消耗可以大幅度減少.在對(duì)上述含有38.7萬個(gè)文件與目錄的遍歷表明，其索引大約有600萬個(gè)，索引占用內(nèi)存約230 MB，程序占據(jù)內(nèi)存不超過500 MB(因?yàn)閯?dòng)態(tài)內(nèi)存分配需要大量的額外內(nèi)存空間)，基本可以接受.

在基礎(chǔ)索引中，如果是38.7萬文件與目錄，則一共需要進(jìn)行38.7萬次strstr的調(diào)用以完成一次完整的查找.在二級(jí)索引中，如果使用了Hash鏈表，每次查找時(shí)就可以大大減少strcmp的次數(shù).在這里，anything采用了質(zhì)數(shù)模的方法作為Hash函數(shù).對(duì)比基礎(chǔ)索引搜索需要的38.7萬個(gè)strstr調(diào)用，可以提高數(shù)10倍的性能.

測試環(huán)境中4個(gè)搜索方法的對(duì)比如下：

1) find——10.1 s，系統(tǒng)緩存增加260 MB;

2) 樹搜索——77 ms，存儲(chǔ)數(shù)據(jù)內(nèi)存需要30 MB;

3) 基礎(chǔ)索引搜索——8 ms，存儲(chǔ)數(shù)據(jù)程序內(nèi)存需要7 MB;

4) 二級(jí)索引搜索——0.4 ms，存儲(chǔ)數(shù)據(jù)程序內(nèi)存需要230 MB.

當(dāng)然，二級(jí)索引的問題仍然是其占用內(nèi)存實(shí)在太大，對(duì)于38.7萬個(gè)文件與目錄的文件數(shù)來說，基礎(chǔ)索引約占用7 MB內(nèi)存，而二級(jí)索引則需要占用約230 MB內(nèi)存.其次，當(dāng)發(fā)生文件系統(tǒng)變更時(shí)，基礎(chǔ)索引的變更比較容易實(shí)現(xiàn)，但是二級(jí)索引的更新就相當(dāng)繁復(fù)了，需要遍歷所有的索引，找到對(duì)應(yīng)的原始字符串偏移量進(jìn)行修改.此外，二級(jí)索引的文件保存與載入也較為麻煩，因?yàn)樾枰獙⒄麄€(gè)Hash鏈表序列化與反序列化，而且當(dāng)文件系統(tǒng)變更時(shí)，一旦變更了索引，則需要進(jìn)行數(shù)百兆甚至上吉數(shù)據(jù)的重新序列化，也會(huì)增大磁盤壓力.

因此，除非是在對(duì)文件名搜索速度非常關(guān)鍵的場所或者離線搜索的場景下，不然使用基礎(chǔ)索引進(jìn)行文件名搜索即可滿足要求.這將是anything應(yīng)用于其他場景的擴(kuò)展能力，不在本文介紹.

3 文件系統(tǒng)監(jiān)控

從以上可以看出，搜索提速最重要的原因是省去系統(tǒng)調(diào)用，但是文件系統(tǒng)是會(huì)不停變化的.因此anything需要對(duì)文件系統(tǒng)進(jìn)行監(jiān)控，在變化時(shí)及時(shí)對(duì)內(nèi)部的基礎(chǔ)索引進(jìn)行修改才能保證搜索的正確性與實(shí)時(shí)性.

everything對(duì)于文件系統(tǒng)變更的追蹤相對(duì)簡單一些，因?yàn)樗苯右蕾囉赪indows下NTFS文件系統(tǒng)的日志[7].但是在Linux下，首先文件系統(tǒng)繁多，例如RHEL 7CentOS 7采用的缺省文件系統(tǒng)是XFS，但是Debian與RHEL 6CentOS 6使用的缺省文件系統(tǒng)卻是ext4，而且這兩者的文件系統(tǒng)日志都沒有NTFS信息完全[8].除此之外還有btrfs等一系列的其他文件系統(tǒng).其次是在Linux下，管理員或者用戶對(duì)于文件系統(tǒng)的選擇較多，并且可以深入調(diào)整文件系統(tǒng)的參數(shù)，例如去掉日志，因此僅依賴于文件系統(tǒng)日志檢查文件系統(tǒng)的變更是不太可靠的.

另外，由于Linux本身沒有全局的文件創(chuàng)建、刪除與重命名的用戶態(tài)接口(比較接近的inotify無法遞歸監(jiān)控目錄)[9]，因此要解決此問題，只能使用獨(dú)立的模塊監(jiān)聽文件的創(chuàng)建、刪除與重命名，并通知相應(yīng)的用戶態(tài)程序更新文件系統(tǒng)數(shù)據(jù)與索引數(shù)據(jù).

在Linux下，監(jiān)控整個(gè)文件系統(tǒng)的變化可以采用下列方法：

1) 使用preload庫，監(jiān)控glibc對(duì)應(yīng)函數(shù)的參數(shù)與返回值，包括open,fopen,creat,mkdir,rmdir,rename等.這種方式的優(yōu)點(diǎn)是不依賴于內(nèi)核，但是它會(huì)對(duì)所有依賴于glibc庫的程序都造成影響，影響面大，工作量也不小(函數(shù)較多，參數(shù)處理較多)，而且具有較大的安全隱患，此外，對(duì)于靜態(tài)編譯libc庫的程序以及不依賴于libc庫的程序(雖然這種程序很少)無法監(jiān)控.

2) 使用審計(jì)系統(tǒng)，加入對(duì)相應(yīng)系統(tǒng)調(diào)用(open,creat,mkdir等)的審計(jì)，通過審計(jì)日志檢查系統(tǒng)調(diào)用的結(jié)果，根據(jù)結(jié)果更新文件系統(tǒng)數(shù)據(jù).其優(yōu)點(diǎn)是不依賴于內(nèi)核，系統(tǒng)調(diào)用數(shù)量較少，但是缺點(diǎn)是需要依賴于審計(jì)系統(tǒng)，而且事后處理日志的方式會(huì)缺少關(guān)鍵的場景信息，例如之前的文件或者目錄是否存在.

4) 編寫內(nèi)核模塊，使用內(nèi)核熱補(bǔ)丁技術(shù)(livepatch)替換內(nèi)核函數(shù).與上述技術(shù)路線類似，不需要自己考慮替換內(nèi)核函數(shù)指針的問題，缺點(diǎn)是需要重新實(shí)現(xiàn)或者調(diào)用原始函數(shù)，以保證功能的正確，而且熱補(bǔ)丁技術(shù)對(duì)內(nèi)核特性要求較高，龍芯申威內(nèi)核現(xiàn)在并沒有實(shí)現(xiàn)相應(yīng)的功能.此外，如果相應(yīng)的函數(shù)由于出現(xiàn)了問題需要使用熱補(bǔ)丁修復(fù)，將會(huì)帶來一些維護(hù)上的問題，雖然可能性較小.

5) 編寫內(nèi)核模塊，使用內(nèi)核tracepoint特性對(duì)系統(tǒng)調(diào)用入口與出口進(jìn)行事件跟蹤，并記錄處理結(jié)果，缺點(diǎn)是會(huì)對(duì)所有的系統(tǒng)調(diào)用進(jìn)行跟蹤，因此需要自己過濾，而且系統(tǒng)調(diào)用路徑較長，可能會(huì)導(dǎo)致較多的資源占用.

6) 編寫內(nèi)核模塊，通過kprobes對(duì)內(nèi)核函數(shù)進(jìn)行掛鉤，在函數(shù)入口和出口處進(jìn)行參數(shù)與返回值的檢查，當(dāng)發(fā)現(xiàn)滿足要求的文件事件時(shí)將事件信息記錄下來，其缺點(diǎn)是對(duì)比tracepoint來說，kprobes從理論上依賴的函數(shù)變化的可能性更大一些，當(dāng)內(nèi)核升級(jí)時(shí)可能會(huì)帶來維護(hù)的問題[10].

anything選擇了最后一種解決方法，雖然它要求內(nèi)核支持kprobes特性，但這是一個(gè)較容易實(shí)現(xiàn)的特性，而且anything要監(jiān)控的內(nèi)核函數(shù)也相對(duì)穩(wěn)定.

具體到需要跟蹤的內(nèi)核函數(shù)，主要就是VFS的文件系統(tǒng)變更函數(shù)，包括vfs_create等.為了確保只有當(dāng)函數(shù)成功返回時(shí)才進(jìn)行記錄，anything需要使用kretprobes進(jìn)行函數(shù)跟蹤.

需要注意的是，使用kretprobes有一個(gè)與架構(gòu)相關(guān)的問題，那就是要在函數(shù)入口處得到函數(shù)各參數(shù)的值，而在這里，kretprobes沒有給開發(fā)者提供很多便利，需要根據(jù)不同CPU架構(gòu)的內(nèi)核寄存器結(jié)構(gòu)體(pt_regs)制定的函數(shù)調(diào)用規(guī)約才能獲取相關(guān)的參數(shù)值.例如對(duì)于X86來說，其64 b系統(tǒng)的函數(shù)調(diào)用規(guī)約是從第1個(gè)參數(shù)開始，分別使用rdi,rsi,rdx,rcx,r8與r9寄存器保存參數(shù)，從第7個(gè)參數(shù)開始使用棧來保存剩余的參數(shù).這些代碼都被封裝到源碼的kernelmodarg_extractor.c中.因此，當(dāng)需要擴(kuò)展架構(gòu)支持時(shí)，主要在這里進(jìn)行修改即可.此外，在實(shí)際使用中，anything現(xiàn)在僅用到前4個(gè)參數(shù)，因此只要處理n等于1～4的情況即可.

4 測試驗(yàn)證與結(jié)論

本文使用一個(gè)簡單但仍有典型意義的文件搜索來完成以下對(duì)比測試：

首先是測試環(huán)境.測試環(huán)境物理機(jī)為ThinkPad x230(8 GB內(nèi)存+機(jī)械硬盤).虛擬機(jī)為運(yùn)行在VirtualBox里完整安裝的Deepin 15.4(分配虛擬單核處理器2.9 GHz，虛擬內(nèi)存2 GB).

測試方法如下：

1) 使用sysctl -w vm.drop_caches=3清空緩存，然后運(yùn)行find-name ″*hellfire*，耗時(shí)約39.9 s.

3) 使用anything的基礎(chǔ)索引搜索hellfire，耗時(shí)約6 ms，基礎(chǔ)索引占用內(nèi)存約7 MB，測試程序占用內(nèi)存約14 MB.

4) 使用anything的二級(jí)索引搜索hellfire，耗時(shí)0 ms，二級(jí)索引占用內(nèi)存約230 MB，測試程序占用內(nèi)存約500 MB.

通過多次測試的結(jié)果表明，使用基礎(chǔ)索引比使用帶緩存的find搜索要快大約500倍甚至更多.若在忽略內(nèi)存等附加消耗的情況下，使用全內(nèi)存式的二級(jí)索引，anything的搜索速度會(huì)比使用基礎(chǔ)索引搜索速度再快20倍以上(但是占用內(nèi)存將增長35倍).是否引入二級(jí)索引需要根據(jù)實(shí)際的應(yīng)用場景來取舍，這是典型的時(shí)間空間復(fù)雜度互換的問題.

在處理器支持上，已經(jīng)驗(yàn)證anything能完全支持X86和自主可控CPU平臺(tái)，包括龍芯和ARM處理器，支持較新的申威(對(duì)部分?jǐn)U展指令集有要求).

anything是一個(gè)小巧的軟件，其功能很單一.但是它達(dá)到了為文件名搜索提供一個(gè)高效快速實(shí)現(xiàn)的目標(biāo)，而且對(duì)現(xiàn)有的系統(tǒng)侵入很小.同時(shí)，anything開源，希望有興趣的人能為它提交補(bǔ)丁，特別是對(duì)其他文件系統(tǒng)以及架構(gòu)的支持，當(dāng)然也包括對(duì)程序本身的修正和改進(jìn).

[1]萬立夫. 讓Everything支持網(wǎng)盤目錄搜索[J]. 電腦迷: 技巧與實(shí)踐Software, 2012 (2): 77

[2]Rasto L. About rlocate官方文檔[OL]. [2017-12-15]. http://rlocate.sourceforge.net/

[3]Wbruce C, Donald M, Trevor S. 計(jì)算機(jī)科學(xué)叢書：搜索引擎信息檢索實(shí)踐[M]. 劉挺, 秦冰, 張宇, 等譯. 1版. 北京: 機(jī)械工業(yè)出版社, 2010

[4]周磊. 十五個(gè)經(jīng)典算法研究與總結(jié)[OL]. [2017-12-15]. http://blog.csdn.net/v_JULY_v

[5]沈東良. Linux內(nèi)核中鏈表和散列表的實(shí)現(xiàn)原理揭秘[OL]. [2017-12-15]. http://blog.csdn.net/shendl

[6]嚴(yán)浪. 倒排文件技術(shù)設(shè)計(jì)[J]. 計(jì)算機(jī)與數(shù)字工程, 2011 (3): 168-170

[7]Zhao J. 探索Everything背后的技術(shù)[OL]. [2017-12-15]. https://wenku.baidu.com/view/76bb29da80eb6294dd886cb7.html

[8]Harley Q. Linux和Windows的遍歷目錄下所有文件的方法[OL]. [2017-12-15]. https://www.cnblogs.com/Harley-Quinn/p/6367425.html

[9]Zhang S. Linux文件系統(tǒng)變化通知機(jī)制—inotify[OL]. [2017-12-15]. http://blog.csdn.net/zhangskd/article/details/7572320

[10]潘風(fēng)云. Linux內(nèi)核kprobe機(jī)制[OL]. [2017-12-15]. http://blog.csdn.net/panfengyun12345/article/details/19480567