十多年來，NAS中已經存在的目錄和檔案達到10億之多，在設計和開發備份系統的過程中碰到了很多挑戰，本文将分享大量檔案名記錄的樹形結構存儲實踐。
一、引言
既然是定期備份，肯定會有1次以上的備份。對于一個特定目錄，每次備份時都要與上次備份時進行比較，以期找出哪些檔案被删除了，又新增了哪些檔案，這就需要每次備份時把該目錄下的所有檔案名進行儲存。我們首先想到的是把所有檔案名用特定字元進行拼接後儲存。由于我們使用了MySQL儲存這些資訊，當目錄下檔案很多時，這種拼接的方式很可能超出MySQL的Blob長度限制。根據經驗，當一個目錄有大量檔案時，這些檔案的名稱往往是程式生成的，有一定規律的，而且開頭一般是重複的，于是我們想到了使用一種樹形結構來進行存儲。
例如，一個有abc、abc1、ad、cde 4個檔案的目錄對應的樹如圖1所示。
圖1 樹形結構示例
圖1中，R表示根節點，青色節點我們稱為結束節點，從R到每個結束節點的路徑都表示一個檔案名。可以在樹中查找是否含有某個檔案名、周遊樹中所有的檔案名、對樹序列化進行儲存、由序列化結果反序列化重新生成樹。
二、涉及的資料結構
注意：我們使用java編寫，文中涉及語言特性相關的知識點都是指java。
2.1 Node的結構
包括根節點在内的每個節點都使用Node類來表示。代碼如下：
class Node {
private char value;
private Node[]children = new Node[0];
private byte end = 0;
} 字段說明：
- value：該節點表示的字元，當Node表示根節點時，value無值。
- children：該節點的所有子節點，初始化為長度為0的數組。
- end：标記節點是否是結束節點。0不是；1是。葉子節點肯定是結束節點。預設非結束節點。
2.2 Node的操作
public Node(char v);
public Node findChild(char v);
public Node addChild(char v); 操作說明：
- Node：構造方法。将參數v指派給this.value。
- findChild：查找children中是否含有value為v的子節點。有則傳回子節點，沒有則傳回null。
- addChild：首先查找children中是否已經含有value為v的子節點，如果有則直接将查到的子節點傳回；否則建立value為v的節點，将children的長度延長1，将新建立的節點作為children的最後一個元素，并傳回新建立的節點。
2.3 Tree的結構
class Tree {
public Node root = new Node();
} 字段說明：Tree隻含有root Node。如前所述，root的value無值，end為0。初始時的children長度為0。
2.4 Tree的操作
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); - addName：向樹中增加一個新的檔案名，即參數name。以root為起點，name中的每個字元作參數調用addChild，傳回值又作為新的起點，直到name中的全部字元添加完畢，對最後一次調用addChild的傳回值标記為結束節點。
- contain：查詢樹中是否含有一個檔案名。
- next：對樹中包含的所有檔案名進行周遊，為了使周遊能夠順利進行，我們引入了新的類Found，細節會在後文詳述。
- writeTo：将樹寫入一個輸出流以進行持久化。
- readFrom：此方法是靜态方法。從一個輸入流來重新建構樹。
三、樹的建構
在建立的Tree上調用addName方法，将所有檔案名添加到樹中，樹建構完成。仍然以含有abc、abc1、ad、cde 四個檔案的目錄為例，對樹的建構進行圖示。
圖2 樹的建構過程
圖2中，橙色節點表示需要在該節點上調用addChild方法增加子節點，同時addChild的傳回值作為新的橙色節點。直到沒有子節點需要增加時，把最後的橙色節點标記為結束節點。
四、樹的查詢
查找樹中是否含有一個某個檔案名，對應Tree的contain方法。在圖2中的結果上分别查找ef、ab和abc三個檔案來示範查找的過程。如圖3所示。
圖3 樹的查詢示意圖
圖3中，橙色節點表示需要在該節點上調用findChild方法查找子節點。
五、樹的周遊
此處的周遊不同于一般樹的周遊。一般周遊是周遊樹中的節點，而此處的周遊是周遊根節點到所有結束節點的路徑。
我們采用從左到右、由淺及深的順序進行周遊。我們引入了Found類，并作為next方法的參數進行周遊。
5.1 Found的結構
class Found {
private String name;
private int[] idx ;
} 為了更加容易的說明問題，在圖1基礎上進行了小小的改造，每個節點的右下角增加了下标，如圖4。
圖4 帶下标的Tree
對于abc這個檔案名，Found中的name值為“abc”，idx為{0，0，0}。
對于abc1這個檔案名，Found中的name值為“abc1”，idx為{0，0，0，0}。
對于ad這個檔案名，Found中的name值為“ad”，idx為{0，1}。
對于cde這個檔案名，Found中的name值為“cde”，idx為{1，0，0}。
5.2 如何周遊
對于圖4而言，第一次調用next方法應傳入null，則傳回第一個結果，即abc代表的Found；繼續以這個Found作為參數進行第二次next的調用，則傳回第二個結果，即abc1代表的Found；再繼續以這個Found作為參數進行第三次next的調用，則傳回第三個結果，即ad所代表的Found；再繼續以這個Found作為參數進行第四次next的調用，則傳回第四個結果，即cde所代表的Found；再繼續以這個Found作為參數進行第五次調用，則傳回null，周遊結束。
六、序列化與反序列化
6.1 序列化
首先應該明确每個節點序列化後應該包含3個資訊：節點的value、節點的children數量和節點是否為結束節點。
6.1.1 節點的value
雖然之前所舉的例子中節點的value都是英文字元，但實際上檔案名中可能含有漢字或者其他語言的字元。為了友善處理，我們沒有使用變長編碼。而是直接使用unicode碼。位元組序采用大端編碼。
6.1.2 節點的children數量
由于節點的value使用了unicode碼，是以children的數量不會多于unicode能表示的字元的數量，即65536。children數量使用2個位元組。位元組序同樣采用大端編碼。
6.1.3 節點的end
0或1可以使用1位（1bit）來表示，但java中最小機關是位元組。如果采用1個位元組來表示end，有些浪費空間，其實任何一個節點children數量達到65536/2的可能性都是極小的，是以我們考慮借用children數量的最高位來表示end。
綜上所述，一個節點序列化後占用4個位元組，以圖4中的根節點、value為b的節點和value為e的節點為例：
表1 Node序列化示例
| value的unicode | children數量 | end | children數量/(end<<15) | 最終結果 |
|---|---|---|---|---|
| 根節點 | 0x0000 | 2 | 0x0002 | 0x00020000 |
| b節點 | 0x0062 | 1 | 0x0001 | 0x00010062 |
| e節點 | 0x0065 | 0x8000 | 0x80000065 |
6.1.4 樹的序列化過程
對樹進行廣度周遊，在周遊過程中需要借助隊列，以圖4的序列化為例進行說明：
圖5 對圖4的序列化過程
6.2 反序列化
反序列化是序列化的逆過程，由于篇幅原因不再進行闡述。值得一提的是，反序列化過程同樣需要隊列的協助。
七、讨論
7.1 關于節省空間
為友善讨論，假設目錄下的檔案名是10個阿拉伯數字的全排列，當位數為1時，目錄下含有10個檔案，即0、1、2……8、9，當位數為2時，目錄下含有100個檔案，即00、01、02……97、98、99，以此類推。
比較2種方法，一種使用“/”分隔，另一種是本文介紹的方法。
表2 2種方法的存儲空間比較（機關：位元組）
| 位數 方法 | 3 | 4 | 5 | 6 | ||
|---|---|---|---|---|---|---|
| “/”分隔 | 19 | 299 | 3999 | 49999 | 599999 | 6999999 |
| Tree | 44 | 444 | 4444 | 44444 | 444444 | 4444444 |
由表2可見，當位數為4時，使用Tree的方式開始節省空間，位數越多節省的比例越高，這正是我們所需要的。
表中，使用“/”分隔時，位元組數占用是按照utf8編碼計算的。如果直接使用unicode進行存儲，占用空間會加倍，那麼會在位數為2時就開始節省空間。同樣使用“/”分隔，看起來utf8比使用unicode會更省空間，但實際上，檔案名中有時候會含有漢字，漢字的utf8編碼占用3個位元組。
7.2 關于時間
在樹的建構、序列化反序列化過程中，引入了額外的運算，根據我們的實踐，user CPU并沒有明顯變化。
7.3 關于理想化假設
最初我們就是使用了“/”分隔的方法對檔案名進行存儲，并且資料庫的相應字段類型是Blob（Blob的最大值是65K）。在測試階段就發現，超出65K是一件很平常的事情。在不可能預先統計最大目錄裡所有檔案名拼接後的大小的情況下，我們采取了2種手段，一是使用LongBlob類型，另一種就是盡量減小拼接結果的大小，即本文介紹的方法。
即使使用樹形結構來存儲檔案名，也不能夠保證最終結果不超出4G(LongBlob類型的最大值)，至少在我們實踐的過程并未出現問題，如果真出現這種情況，隻能做特殊處理了。
7.4 關于其他壓縮方法
把檔案名使用“/”拼接後，使用gzip等壓縮算法對拼接結果進行壓縮後再存儲，在節省存儲空間方面會取得更好的效果。但是在壓縮之前，拼接結果存在于記憶體，這樣對JVM的堆記憶體有比較高的要求；另外，使用“/”拼接時，查找會比較麻煩。
作者：牛甯昌
來源：宜信技術學院