十多年來，NAS中已經(jīng)存在的目錄和文件達(dá)到10億之多，在設(shè)計(jì)和開發(fā)備份系統(tǒng)的過程中碰到了很多挑戰(zhàn)，本文將分享大量文件名記錄的樹形結(jié)構(gòu)存儲(chǔ)實(shí)踐。
創(chuàng)新互聯(lián)公司長期為近1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為合肥企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)，合肥網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
既然是定期備份，肯定會(huì)有1次以上的備份。對于一個(gè)特定目錄，每次備份時(shí)都要與上次備份時(shí)進(jìn)行比較，以期找出哪些文件被刪除了，又新增了哪些文件，這就需要每次備份時(shí)把該目錄下的所有文件名進(jìn)行保存。我們首先想到的是把所有文件名用特定字符進(jìn)行拼接后保存。由于我們使用了MySQL保存這些信息，當(dāng)目錄下文件很多時(shí)，這種拼接的方式很可能超出MySQL的Blob長度限制。根據(jù)經(jīng)驗(yàn)，當(dāng)一個(gè)目錄有大量文件時(shí)，這些文件的名稱往往是程序生成的，有一定規(guī)律的，而且開頭一般是重復(fù)的，于是我們想到了使用一種樹形結(jié)構(gòu)來進(jìn)行存儲(chǔ)。
例如，一個(gè)有abc、abc1、ad、cde 4個(gè)文件的目錄對應(yīng)的樹如圖1所示。
圖1 樹形結(jié)構(gòu)示例
圖1中，R表示根節(jié)點(diǎn)，青色節(jié)點(diǎn)我們稱為結(jié)束節(jié)點(diǎn)，從R到每個(gè)結(jié)束節(jié)點(diǎn)的路徑都表示一個(gè)文件名?？梢栽跇渲胁檎沂欠窈心硞€(gè)文件名、遍歷樹中所有的文件名、對樹序列化進(jìn)行保存、由序列化結(jié)果反序列化重新生成樹。
注意：我們使用java編寫，文中涉及語言特性相關(guān)的知識(shí)點(diǎn)都是指java。
包括根節(jié)點(diǎn)在內(nèi)的每個(gè)節(jié)點(diǎn)都使用Node類來表示。代碼如下：
重慶分公司
重慶分公司
class Node {
private char value;
private Node[]children = new Node[0];
private byte end = 0;
}字段說明：
public Node(char v);
public Node findChild(char v);
public Node addChild(char v);操作說明：
class Tree {
public Node root = new Node();
}字段說明：Tree只含有root Node。如前所述，root的value無值，end為0。初始時(shí)的children長度為0。
public void addName(String name) ;
public boolean contain(String name);
public Found next(Found found);
public void writeTo(OutputStream out);
public static Tree readFrom(InputStream in);操作說明：
在新建的Tree上調(diào)用addName方法，將所有文件名添加到樹中，樹構(gòu)建完成。仍然以含有abc、abc1、ad、cde 四個(gè)文件的目錄為例，對樹的構(gòu)建進(jìn)行圖示。
圖2 樹的構(gòu)建過程
圖2中，橙色節(jié)點(diǎn)表示需要在該節(jié)點(diǎn)上調(diào)用addChild方法增加子節(jié)點(diǎn)，同時(shí)addChild的返回值作為新的橙色節(jié)點(diǎn)。直到?jīng)]有子節(jié)點(diǎn)需要增加時(shí)，把最后的橙色節(jié)點(diǎn)標(biāo)記為結(jié)束節(jié)點(diǎn)。
查找樹中是否含有一個(gè)某個(gè)文件名，對應(yīng)Tree的contain方法。在圖2中的結(jié)果上分別查找ef、ab和abc三個(gè)文件來演示查找的過程。如圖3所示。
圖3 樹的查詢示意圖
圖3中，橙色節(jié)點(diǎn)表示需要在該節(jié)點(diǎn)上調(diào)用findChild方法查找子節(jié)點(diǎn)。
此處的遍歷不同于一般樹的遍歷。一般遍歷是遍歷樹中的節(jié)點(diǎn)，而此處的遍歷是遍歷根節(jié)點(diǎn)到所有結(jié)束節(jié)點(diǎn)的路徑。
我們采用從左到右、由淺及深的順序進(jìn)行遍歷。我們引入了Found類，并作為next方法的參數(shù)進(jìn)行遍歷。
class Found {
private String name;
private int[] idx ;
}為了更加容易的說明問題，在圖1基礎(chǔ)上進(jìn)行了小小的改造，每個(gè)節(jié)點(diǎn)的右下角增加了下標(biāo)，如圖4。
圖4 帶下標(biāo)的Tree
對于abc這個(gè)文件名，F(xiàn)ound中的name值為“abc”，idx為{0，0，0}。
對于abc1這個(gè)文件名，F(xiàn)ound中的name值為“abc1”，idx為{0，0，0，0}。
對于ad這個(gè)文件名，F(xiàn)ound中的name值為“ad”，idx為{0，1}。
對于cde這個(gè)文件名，F(xiàn)ound中的name值為“cde”，idx為{1，0，0}。
對于圖4而言，第一次調(diào)用next方法應(yīng)傳入null，則返回第一個(gè)結(jié)果，即abc代表的Found；繼續(xù)以這個(gè)Found作為參數(shù)進(jìn)行第二次next的調(diào)用，則返回第二個(gè)結(jié)果，即abc1代表的Found；再繼續(xù)以這個(gè)Found作為參數(shù)進(jìn)行第三次next的調(diào)用，則返回第三個(gè)結(jié)果，即ad所代表的Found；再繼續(xù)以這個(gè)Found作為參數(shù)進(jìn)行第四次next的調(diào)用，則返回第四個(gè)結(jié)果，即cde所代表的Found；再繼續(xù)以這個(gè)Found作為參數(shù)進(jìn)行第五次調(diào)用，則返回null，遍歷結(jié)束。
首先應(yīng)該明確每個(gè)節(jié)點(diǎn)序列化后應(yīng)該包含3個(gè)信息：節(jié)點(diǎn)的value、節(jié)點(diǎn)的children數(shù)量和節(jié)點(diǎn)是否為結(jié)束節(jié)點(diǎn)。
雖然之前所舉的例子中節(jié)點(diǎn)的value都是英文字符，但實(shí)際上文件名中可能含有漢字或者其他語言的字符。為了方便處理，我們沒有使用變長編碼。而是直接使用unicode碼。字節(jié)序采用大端編碼。
由于節(jié)點(diǎn)的value使用了unicode碼，所以children的數(shù)量不會(huì)多于unicode能表示的字符的數(shù)量，即65536。children數(shù)量使用2個(gè)字節(jié)。字節(jié)序同樣采用大端編碼。
0或1可以使用1位（1bit）來表示，但java中最小單位是字節(jié)。如果采用1個(gè)字節(jié)來表示end，有些浪費(fèi)空間，其實(shí)任何一個(gè)節(jié)點(diǎn)children數(shù)量達(dá)到65536/2的可能性都是極小的，因此我們考慮借用children數(shù)量的最高位來表示end。
綜上所述，一個(gè)節(jié)點(diǎn)序列化后占用4個(gè)字節(jié)，以圖4中的根節(jié)點(diǎn)、value為b的節(jié)點(diǎn)和value為e的節(jié)點(diǎn)為例：
表1 Node序列化示例
| value的unicode | children數(shù)量 | end | children數(shù)量/(end<<15) | 最終結(jié)果 | |
|---|---|---|---|---|---|
| 根節(jié)點(diǎn) | 0x0000 | 2 | 0 | 0x0002 | 0x00020000 |
| b節(jié)點(diǎn) | 0x0062 | 1 | 0 | 0x0001 | 0x00010062 |
| e節(jié)點(diǎn) | 0x0065 | 0 | 1 | 0x8000 | 0x80000065 |
對樹進(jìn)行廣度遍歷，在遍歷過程中需要借助隊(duì)列，以圖4的序列化為例進(jìn)行說明：
圖5 對圖4的序列化過程
反序列化是序列化的逆過程，由于篇幅原因不再進(jìn)行闡述。值得一提的是，反序列化過程同樣需要隊(duì)列的協(xié)助。
為方便討論，假設(shè)目錄下的文件名是10個(gè)阿拉伯?dāng)?shù)字的全排列，當(dāng)位數(shù)為1時(shí)，目錄下含有10個(gè)文件，即0、1、2……8、9，當(dāng)位數(shù)為2時(shí)，目錄下含有100個(gè)文件，即00、01、02……97、98、99，以此類推。
比較2種方法，一種使用“/”分隔，另一種是本文介紹的方法。
表2 2種方法的存儲(chǔ)空間比較（單位：字節(jié)）
| 位數(shù) 方法 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| “/”分隔 | 19 | 299 | 3999 | 49999 | 599999 | 6999999 |
| Tree | 44 | 444 | 4444 | 44444 | 444444 | 4444444 |
由表2可見，當(dāng)位數(shù)為4時(shí)，使用Tree的方式開始節(jié)省空間，位數(shù)越多節(jié)省的比例越高，這正是我們所需要的。
表中，使用“/”分隔時(shí)，字節(jié)數(shù)占用是按照utf8編碼計(jì)算的。如果直接使用unicode進(jìn)行存儲(chǔ)，占用空間會(huì)加倍，那么會(huì)在位數(shù)為2時(shí)就開始節(jié)省空間。同樣使用“/”分隔，看起來utf8比使用unicode會(huì)更省空間，但實(shí)際上，文件名中有時(shí)候會(huì)含有漢字，漢字的utf8編碼占用3個(gè)字節(jié)。
在樹的構(gòu)建、序列化反序列化過程中，引入了額外的運(yùn)算，根據(jù)我們的實(shí)踐，user CPU并沒有明顯變化。
最初我們就是使用了“/”分隔的方法對文件名進(jìn)行存儲(chǔ)，并且數(shù)據(jù)庫的相應(yīng)字段類型是Blob（Blob的最大值是65K）。在測試階段就發(fā)現(xiàn)，超出65K是一件很平常的事情。在不可能預(yù)先統(tǒng)計(jì)最大目錄里所有文件名拼接后的大小的情況下，我們采取了2種手段，一是使用LongBlob類型，另一種就是盡量減小拼接結(jié)果的大小，即本文介紹的方法。
即使使用樹形結(jié)構(gòu)來存儲(chǔ)文件名，也不能夠保證最終結(jié)果不超出4G(LongBlob類型的最大值)，至少在我們實(shí)踐的過程并未出現(xiàn)問題，如果真出現(xiàn)這種情況，只能做特殊處理了。
把文件名使用“/”拼接后，使用gzip等壓縮算法對拼接結(jié)果進(jìn)行壓縮后再存儲(chǔ)，在節(jié)省存儲(chǔ)空間方面會(huì)取得更好的效果。但是在壓縮之前，拼接結(jié)果存在于內(nèi)存，這樣對JVM的堆內(nèi)存有比較高的要求；另外，使用“/”拼接時(shí)，查找會(huì)比較麻煩。
作者：牛寧昌
來源：宜信技術(shù)學(xué)院
