[發(fā)明專利]安全網(wǎng)盤系統(tǒng)中一種基于目錄樹(shù)的數(shù)據(jù)同步方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210179530.8
• 申請(qǐng)日: 2012-05-31
• 公開(kāi)（公告）號(hào): CN102790760A
• 公開(kāi)（公告）日: 2012-11-21
• 發(fā)明（設(shè)計(jì)）人: 舒繼武;傅穎勛
• 申請(qǐng)（專利權(quán)）人: 清華大學(xué)
• 主分類號(hào): H04L29/06
• 分類號(hào): H04L29/06;G06F17/30
• 代理公司: 北京思海天達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 11203
• 代理人: 樓艮基

1.安全網(wǎng)盤系統(tǒng)中一種基于目錄樹(shù)的同步方法，其特征在于，它是在由客戶端計(jì)算機(jī)、服務(wù)器以及云存儲(chǔ)服務(wù)器三者共同構(gòu)成的基于個(gè)人用戶共享的安全網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)CorsBox中實(shí)現(xiàn)的，所述客戶端計(jì)算機(jī)和服務(wù)器之間通過(guò)Internet網(wǎng)連接，所述服務(wù)器和云存儲(chǔ)服務(wù)器之間通過(guò)以太網(wǎng)交換機(jī)連接，所述安全網(wǎng)盤系統(tǒng)中一種基于同步目錄樹(shù)的數(shù)據(jù)同步方法依次含有以下步驟：

步驟（1），客戶端計(jì)算機(jī)初始化所有目錄樹(shù)：

步驟（1.1），客戶端計(jì)算機(jī)向服務(wù)器發(fā)起同步請(qǐng)求，服務(wù)器計(jì)算機(jī)對(duì)客戶端的用戶身份進(jìn)行驗(yàn)證，然后將該用戶的服務(wù)器端目錄樹(shù)返回給客戶端；

步驟（1.2），客戶端計(jì)算機(jī)讀取保存在本地的客戶端目錄樹(shù)生成文件，在內(nèi)存中創(chuàng)造了該用戶的客戶端目錄樹(shù)和組成所述用戶的客戶端目錄樹(shù)的客戶端目錄樹(shù)結(jié)點(diǎn)：

客戶端目錄樹(shù)是一個(gè)二叉樹(shù)結(jié)構(gòu)，它的格式包括：root、nodes、nodesCount和maxnodesCount，其中，

nodes，以數(shù)組方式記錄了所述客戶端目錄樹(shù)的所有結(jié)點(diǎn)；

nodesCount，記錄了所述客戶端目錄樹(shù)中的總結(jié)點(diǎn)數(shù)；

maxNodesCount，表示所述客戶端目錄樹(shù)最多允許包含的結(jié)點(diǎn)數(shù)；

客戶端目錄樹(shù)結(jié)點(diǎn)的格式包括：nodeType、name、appendAttribute、lastModifyTime、lchild和rchild，其中：

nodeType，記錄所述客戶端目錄樹(shù)中的結(jié)點(diǎn)所對(duì)應(yīng)的是目錄還是文件；

name，記錄所述客戶端目錄樹(shù)中所述目錄或文件的名稱；

appendAttribute，對(duì)所述客戶端目錄樹(shù)中的目錄而言，記錄的是是否被共享，對(duì)所述客戶端目錄樹(shù)中的文件而言，記錄的是最新版本的版本號(hào)；

lchild，記錄了在所述客戶端目錄樹(shù)中該結(jié)點(diǎn)的左孩子的索引號(hào)；

rchild，記錄了在所述客戶端目錄樹(shù)中該結(jié)點(diǎn)的右孩子的索引號(hào)；

lastModifytime,記錄所述基于個(gè)人用戶共享安全網(wǎng)絡(luò)存儲(chǔ)系統(tǒng)CorsBox所維護(hù)的該結(jié)點(diǎn)的最新修改時(shí)間；

步驟（1.3），客戶端計(jì)算機(jī)根據(jù)步驟（1.1）的返回的服務(wù)器端目錄樹(shù)在內(nèi)存中創(chuàng)建該用戶的服務(wù)器端目錄樹(shù)，用于記錄所述云存儲(chǔ)服務(wù)器中的實(shí)時(shí)數(shù)據(jù)狀態(tài)；用戶的服務(wù)器端目錄樹(shù)的結(jié)構(gòu)與客戶端目錄樹(shù)完全相同，只是nodes數(shù)組中的結(jié)點(diǎn)類型是用戶服務(wù)器端目錄樹(shù)結(jié)點(diǎn)，用戶服務(wù)器端目錄樹(shù)結(jié)點(diǎn)包括：nodeType、name、appendAttribute、lchild和rchild，其中：

nodeType，記錄所述用戶服務(wù)器端目錄樹(shù)中的結(jié)點(diǎn)所對(duì)應(yīng)的是目錄或文件；

name，記錄所述的目錄或文件的名稱；

appendAttribute，對(duì)所述用戶服務(wù)器端目錄樹(shù)中的目錄而言，記錄的是是否被共享，對(duì)所述用戶服務(wù)器端目錄樹(shù)中的文件而言，記錄的是最新版本的版本號(hào)；

lchild，記錄了在所述用戶服務(wù)器端目錄樹(shù)中該結(jié)點(diǎn)的左孩子的索引號(hào)；

rchild，記錄了在所述用戶服務(wù)器端目錄樹(shù)中該結(jié)點(diǎn)的右孩子的索引號(hào)；

步驟（1.4），所述客戶端計(jì)算機(jī)在每次同步時(shí)掃描磁盤中的所述客戶端目錄樹(shù)的目錄及其子目錄，在內(nèi)存中創(chuàng)造用戶磁盤目錄樹(shù)記錄用戶的實(shí)時(shí)數(shù)據(jù)，用戶磁盤目錄樹(shù)的結(jié)構(gòu)與客戶端目錄樹(shù)完全相同，只是nodes數(shù)組中的結(jié)點(diǎn)類型是磁盤目錄樹(shù)結(jié)點(diǎn)，用戶磁盤目錄樹(shù)結(jié)點(diǎn)包括：nodeType、name、lastModifyTime、lchild和rchild，其中：

nodeType，記錄所述用戶磁盤目錄樹(shù)中的結(jié)點(diǎn)所對(duì)應(yīng)的是目錄還是文件；

name，記錄所述磁盤目錄樹(shù)中所述目錄或文件的名稱；

lastModifytime,記錄了在所述客戶端計(jì)算機(jī)中該結(jié)點(diǎn)的最后修改時(shí)間；

lchild，記錄了在所述磁盤目錄樹(shù)中該結(jié)點(diǎn)的左孩子的索引號(hào)；

rchild，記錄了在所述磁盤目錄樹(shù)中該結(jié)點(diǎn)的右孩子的索引號(hào)；

步驟（2），客戶端計(jì)算機(jī)依次按照如下步驟比對(duì)客戶端目錄樹(shù)與磁盤目錄樹(shù)；

步驟（2.1），客戶端計(jì)算機(jī)將客戶端目錄樹(shù)排序，排序方法如下：

步驟（2.1.1），創(chuàng)建一個(gè)當(dāng)前結(jié)點(diǎn)指針指向客戶端目錄樹(shù)的根節(jié)點(diǎn)，若當(dāng)前結(jié)點(diǎn)為空，則排序完成，否則使用步驟（2.1.2）中的方法進(jìn)行排序；

步驟（2.1.2），對(duì)待當(dāng)前結(jié)點(diǎn)的左孩子對(duì)應(yīng)的右結(jié)點(diǎn)鏈，某個(gè)結(jié)點(diǎn)的右節(jié)點(diǎn)鏈定義為一個(gè)集合，該集合包含該節(jié)點(diǎn)及其右孩子、右孩子的右孩子……，直到右孩子為空，按照字典序的方式順序排序，對(duì)字符串來(lái)說(shuō)，字典序是指：若A字符串的首字母在字典中順序排在字符串B的首字母之前，則稱在字典序中A>B，若想相等則比較第二個(gè)字母，以此類推；

步驟（2.1.3），將當(dāng)前結(jié)點(diǎn)指針依次指向其左孩子的右結(jié)點(diǎn)鏈中的每一個(gè)結(jié)點(diǎn)，若該結(jié)點(diǎn)的類型為目錄，則遞歸執(zhí)行步驟（2.1.1），若為文件則直接跳過(guò)；

步驟（2.2），客戶端計(jì)算機(jī)將磁盤目錄樹(shù)排序，排序方法與步驟（2.1）一樣；

步驟（2.3），客戶端計(jì)算機(jī)依次按照如下步驟比對(duì)客戶端目錄樹(shù)與磁盤目錄樹(shù)，生成比對(duì)結(jié)果：

步驟（2.3.1），分別設(shè)置客戶端目錄樹(shù)的當(dāng)前結(jié)點(diǎn)指針CDT和磁盤目錄樹(shù)的當(dāng)前結(jié)點(diǎn)指針DDT，然后將CDT指向客戶端目錄樹(shù)的根節(jié)點(diǎn)，DDT當(dāng)前指針指向磁盤目錄樹(shù)的根節(jié)點(diǎn)；

步驟（2.3.2），對(duì)客戶端目錄樹(shù)與服務(wù)器端目錄樹(shù)中當(dāng)前結(jié)點(diǎn)指針各自所指向的結(jié)點(diǎn)使用（2.3.2.1）中的方法進(jìn)行結(jié)點(diǎn)比對(duì)；

步驟（2.3.2.1），若CDT當(dāng)前所指向的結(jié)點(diǎn)和DDT當(dāng)前所指向的結(jié)點(diǎn)中，有且僅有一個(gè)為空，則在比對(duì)結(jié)果數(shù)組CDTvsDDT中增加一個(gè)元素記錄該路徑下為空的那顆目錄樹(shù)缺失結(jié)點(diǎn)，并返回；

若CDT當(dāng)前所指向的結(jié)點(diǎn)和DDT當(dāng)前所指向的結(jié)點(diǎn)均為空，則直接返回；

若CDT當(dāng)前所指向的結(jié)點(diǎn)和DDT當(dāng)前所指向的結(jié)點(diǎn)均不為空，則按字典序比對(duì)兩個(gè)當(dāng)前結(jié)點(diǎn)中name域的值：若CDT指向的結(jié)點(diǎn)中name域的值較大，則將DDT指向其右孩子，轉(zhuǎn)步驟（2.3.2）；反之則將CDT指向其右孩子，轉(zhuǎn)步驟（2.3.2）；

若CDT當(dāng)前所指向的結(jié)點(diǎn)和DDT當(dāng)前所指向的結(jié)點(diǎn)的name域值相同，即：依照字典序比較，結(jié)果為等于，則比對(duì)兩個(gè)結(jié)點(diǎn)中的lastModifyTime域的值：

若lastModifyTime域的值不相同，則在比對(duì)結(jié)果數(shù)組CDTvsDDT中增加一個(gè)元素記錄當(dāng)前結(jié)點(diǎn)所代表的文件的最后修改時(shí)間不同，并轉(zhuǎn)步驟（2.3.3）；

若lastModifyTime域的值相同，則直接轉(zhuǎn)步驟（2.3.3）；

步驟（2.3.3），將CDT和DDT分別指向各自的左孩子結(jié)點(diǎn)，然后再次從步驟（2.3.2）開(kāi)始執(zhí)行；

步驟（2.3.4），將CDT和DDT分別指向各自的右孩子結(jié)點(diǎn)，然后再次從步驟（2.3.2）開(kāi)始執(zhí)行；

步驟（2.3.5），當(dāng)執(zhí)行到這一步的時(shí)候，客戶端目錄樹(shù)與磁盤目錄樹(shù)已將整棵樹(shù)比對(duì)完畢，并將所有缺失的結(jié)點(diǎn)與最后修改時(shí)間不相同的結(jié)點(diǎn)信息都已記錄在比對(duì)結(jié)果數(shù)組CDTvsDDT中；

步驟（3），客戶端比對(duì)客戶端目錄樹(shù)與服務(wù)器端目錄樹(shù)：

步驟（3.1），客戶端將服務(wù)器端目錄樹(shù)排序，排序方法與步驟（2.1）一樣；

步驟（3.2），客戶端計(jì)算機(jī)依次按照如下步驟比對(duì)客戶端目錄樹(shù)與服務(wù)器端目錄樹(shù)，生成比對(duì)結(jié)果：

步驟（3.2.1），分別設(shè)置客戶端目錄樹(shù)的當(dāng)前結(jié)點(diǎn)指針CDT，和服務(wù)器目錄樹(shù)的當(dāng)前結(jié)點(diǎn)指針SDT，然后將CDT指向客戶端目錄樹(shù)的根節(jié)點(diǎn)，SDT指向服務(wù)器端目錄樹(shù)的根節(jié)點(diǎn)；

步驟（3.2.2），對(duì)客戶端目錄樹(shù)與服務(wù)器端目錄樹(shù)各自的當(dāng)前結(jié)點(diǎn)指針?biāo)赶虻慕Y(jié)點(diǎn)使用步驟（3.2.2.1）中的方法進(jìn)行結(jié)點(diǎn)比對(duì)；

步驟（3.2.2.1），若CDT當(dāng)前所指向的結(jié)點(diǎn)和SDT當(dāng)前所指向的結(jié)點(diǎn)中，有且僅有一個(gè)為空，則在比對(duì)結(jié)果數(shù)組CDTvsSDT中增加一個(gè)元素記錄該路徑下為空的那顆目錄樹(shù)缺失結(jié)點(diǎn)，并返回；

若CDT當(dāng)前所指向的結(jié)點(diǎn)和SDT當(dāng)前所指向的結(jié)點(diǎn)均為空，則直接返回；

若CDT當(dāng)前所指向的結(jié)點(diǎn)和SDT當(dāng)前所指向的結(jié)點(diǎn)均不為空，則按字典序比對(duì)兩個(gè)當(dāng)前結(jié)點(diǎn)中name域的值：若CDT指向的結(jié)點(diǎn)中name域的值較大，則將SDT指向其右孩子，轉(zhuǎn)步驟（3.2.2）；反之則將CDT指向其右孩子，轉(zhuǎn)步驟（3.2.2）；

若CDT當(dāng)前所指向的結(jié)點(diǎn)和SDT當(dāng)前所指向的結(jié)點(diǎn)的name域值相同，即：依照字典序比較，結(jié)果為等于，則比對(duì)兩個(gè)結(jié)點(diǎn)中的appendAttribute域的值；

若appendAttribute域的值不相同，則在比對(duì)結(jié)果數(shù)組CDTvsSDT中增加一個(gè)元素記錄當(dāng)前結(jié)點(diǎn)所代表的文件的版本號(hào)不同，并轉(zhuǎn)步驟（3.2.3）；

若appendAttribute域的值相同，則直接轉(zhuǎn)步驟（3.2.3）；

步驟（3.2.3），將CDT和SDT分別指向各自的左孩子結(jié)點(diǎn)，然后再次從步驟（3.2.2）開(kāi)始執(zhí)行，

步驟（3.2.4），將CDT和SDT分別指向各自的右孩子結(jié)點(diǎn)，然后再次從步驟（3.2.2）開(kāi)始執(zhí)行，

步驟（3.2.5），當(dāng)執(zhí)行到這一步的時(shí)候，客戶端目錄樹(shù)與服務(wù)器端目錄樹(shù)已將整棵樹(shù)比對(duì)完畢，并將所有存在結(jié)點(diǎn)缺失的路徑或文件版本號(hào)不同的結(jié)點(diǎn)信息都記錄在比對(duì)結(jié)果CDTvsSDT數(shù)組當(dāng)中；

步驟（4），客戶端比對(duì)步驟（2）和步驟（3）的比對(duì)結(jié)果，并根據(jù)此結(jié)果執(zhí)行相應(yīng)的同步操作，完成同步過(guò)程：

步驟（4.1），將步驟（2）中的比對(duì)結(jié)果CDTvsDDT數(shù)組中的元素按照路徑的字典序進(jìn)行排序；

步驟（4.2），將步驟（3）中的比對(duì)結(jié)果CDTvsSDT數(shù)組中的元素按照路徑的字典序進(jìn)行排序；

步驟（4.3），按照如下步驟依次比對(duì)數(shù)組CDTvsDDT、CDTvsSDT中的元素，生成需要執(zhí)行的同步操作；

步驟（4.3.1），數(shù)組CDTvsDDT、CDTvsSDT各自的第一個(gè)元素作為兩個(gè)比對(duì)結(jié)果傳入的結(jié)點(diǎn)，稱為傳入結(jié)點(diǎn)，進(jìn)入步驟（4.3.2）；

步驟（4.3.2），比對(duì)兩個(gè)傳入結(jié)點(diǎn)的路徑，將比對(duì)結(jié)果分為以下幾種情況考慮：

若步驟（2）中的比對(duì)結(jié)果傳入的結(jié)點(diǎn)記錄的路徑的字典序較小，則根據(jù)該結(jié)點(diǎn)記錄的信息分以下情況考慮，并將步驟（2）中傳入結(jié)點(diǎn)的下一結(jié)點(diǎn)與步驟（3）中的傳入結(jié)點(diǎn)作為新的傳入結(jié)點(diǎn)再次從步驟（4.3.2）開(kāi)始執(zhí)行；

1.若該結(jié)點(diǎn)記錄的信息為客戶端目錄樹(shù)中存在此結(jié)點(diǎn)，而磁盤目錄樹(shù)中不存在此結(jié)點(diǎn)，則表示該結(jié)點(diǎn)對(duì)應(yīng)文件或目錄已被客戶端離線刪除，因此需要對(duì)此路徑執(zhí)行下載操作；

2.若該結(jié)點(diǎn)記錄的信息為磁盤目錄樹(shù)中存在此結(jié)點(diǎn)，而客戶端目錄樹(shù)中不存在此結(jié)點(diǎn)，則表示該文件或目錄是用戶在未開(kāi)啟云存儲(chǔ)服務(wù)客戶端的時(shí)候增加的，因此需要對(duì)此路徑執(zhí)行上傳操作；

3.若結(jié)點(diǎn)記錄的信息為客戶端目錄樹(shù)與磁盤目錄樹(shù)中都存在此結(jié)點(diǎn)，但它們的最后修改時(shí)間不同，則表示用戶在未開(kāi)啟云存儲(chǔ)服務(wù)客戶端的時(shí)候修改了此文件，而在這段時(shí)間內(nèi)其他客戶端并沒(méi)有提交此文件的新版本至服務(wù)器，因此需要對(duì)此路徑執(zhí)行上傳操作；

若步驟（3）中的比對(duì)結(jié)果傳入的結(jié)點(diǎn)記錄的路徑的字典序較小，則根據(jù)該結(jié)點(diǎn)記錄的信息分以下情況考慮，并將步驟（3）中傳入結(jié)點(diǎn)的下一結(jié)點(diǎn)與步驟（2）中的傳入結(jié)點(diǎn)作為新的傳入結(jié)點(diǎn)再次從步驟（4.3.2）開(kāi)始執(zhí)行；

1.若該結(jié)點(diǎn)記錄的信息為客戶端目錄樹(shù)中存在此結(jié)點(diǎn)，而服務(wù)器端目錄樹(shù)中不存在此結(jié)點(diǎn)，則表示此文件或目錄已被其他客戶端刪除，應(yīng)在本地將它刪除；

2.若該結(jié)點(diǎn)記錄的信息為服務(wù)器端目錄樹(shù)中存在此結(jié)點(diǎn)，而客戶端目錄樹(shù)中不存在此結(jié)點(diǎn)，則表示此文件或目錄是其他客戶端上傳的，應(yīng)對(duì)此路徑執(zhí)行下載操作；

3.若結(jié)點(diǎn)記錄的信息為客戶端目錄樹(shù)與服務(wù)器端目錄樹(shù)中都存在此結(jié)點(diǎn)，但它們的版本號(hào)不同，則說(shuō)明其他用戶提交了新版本至服務(wù)器，而此用戶并沒(méi)有對(duì)此文件進(jìn)行修改，因此需要對(duì)此路徑執(zhí)行下載操作；

若步驟（2）中的路徑與步驟（3）中的路徑一致，則根據(jù)兩個(gè)結(jié)點(diǎn)分別記錄的信息分以下情況處理，并將兩個(gè)傳入結(jié)點(diǎn)的下一結(jié)點(diǎn)作為新結(jié)點(diǎn)再次從步驟（4.3.2）開(kāi)始執(zhí)行；

1.若步驟（2）中結(jié)點(diǎn)記錄的信息為磁盤目錄樹(shù)缺失結(jié)點(diǎn)，而步驟（3）中結(jié)點(diǎn)記錄的信息為服務(wù)器端端目錄樹(shù)缺失結(jié)點(diǎn)，則表示此文件或目錄已被其他用戶刪除，同時(shí)該用戶在為開(kāi)啟云存儲(chǔ)服務(wù)客戶端的情況下也刪除了此文件或目錄，因此只需將該路徑對(duì)于的結(jié)點(diǎn)從客戶端目錄樹(shù)中刪除即可；

2.若步驟（2）中結(jié)點(diǎn)記錄的信息為磁盤目錄樹(shù)缺失結(jié)點(diǎn)，而步驟（3）中結(jié)點(diǎn)記錄的信息為文件版本號(hào)不同，則表示其他用戶已上傳此文件的新版本，而此用戶在未開(kāi)啟云存儲(chǔ)服務(wù)客戶端的情況下刪除了此文件，因此需要對(duì)此路徑執(zhí)行下載操作；

3.若步驟（2）中結(jié)點(diǎn)記錄的信息為最后修改時(shí)間不同，而步驟（3）中結(jié)點(diǎn)記錄的信息為服務(wù)器端端目錄樹(shù)缺失結(jié)點(diǎn)，則表示其他用戶已將此文件刪除，而本地用戶在這段時(shí)間卻對(duì)此文件進(jìn)行了修改，因此需要對(duì)此路徑執(zhí)行上傳操作；

4.若步驟（2）中結(jié)點(diǎn)記錄的信息為最后修改時(shí)間不同，而步驟（3）中結(jié)點(diǎn)記錄的信息為版本號(hào)不同，則表示其他用戶上傳了此文件，而本地用戶也修改了此文件，因此需要進(jìn)行沖突處理，具體的方法是將本地文件重命名后上傳，并從服務(wù)器端下載該文件的最新版本；

步驟（5），依次執(zhí)行步驟（4）中生成的同步操作，完成同步過(guò)程。