一種基於彼得森圖的數據存儲和讀取方法
2023-09-16 15:37:45 2
專利名稱：：一種基於彼得森圖的數據存儲和讀取方法
技術領域：
：本發明涉及信息網絡
技術領域：
，特別涉及到由分布式存儲節點構成的網絡存儲
技術領域：
中的一種基於彼得森(Peterson)圖的數據存儲和讀取方法。
背景技術：
：隨著網際網路的發展和用戶寬帶接入的普及，許多公司和機構產生了海量數據的存儲需求。如果通過擴充存儲設備來解決該問題，一方面增加了公司對海量數據存儲維護的成本，另一方面，大量的訪問請求也給存儲伺服器來了巨大壓力。在這些條件下，分布式的存儲系統應運而生。分布式存儲通過網絡存儲設備，構建一個存儲專用網絡為用戶提供統一的信息存取和管理的服務，將數據合理分布在存儲網絡中，避免了伺服器單點瓶頸的問題。另外，隨著終端計算能力的增強，越來越多的個人用戶終端系統成為了寶貴的資源，而通過peer-to-peer(P2P)技術，可以將這些資源有效的整合，並具有自組織，抗動態性等特點，使得基於P2P的分布式存儲網絡受到了越來越多的青睞。Peterson圖是一個包含10個節點的正則圖，在該圖中，所有的節點度都相同，為3，任意兩個節點間的距離不超過2。由於Peterson圖結構的穩定性和對稱性，使其在並行計算等領域得到了應用，並取得了良好的效果。
發明內容本發明的目的在於提供一種基於Peterson圖的數據存儲和讀取方法，其將Peterson結構有效應用於網絡存儲中，可增強系統的存儲可靠性。該方法通過兩個層次的管理，將數據內容和索引信息進行分開存儲，保證該方法可以有效地對數據進行路由定位和存儲管理，同時，負載均衡的特性，也有利於Peterson結構在分布式存儲系統中的應用。為了實現上述目的，本發明的基於Peterson圖的數據存儲和讀取方法，其特徵在於，將數據內容和索引信息進行分開存儲，具體包括如下步驟1)確定待存儲數據所對應的數據ID,並存儲數據獲取表示數據的存儲節點所對應ID，並將數據存儲在提交該數據存儲請求的節點或者相近的節點上，當通過節點i寫入數據時，如果節點i中空間充足，則數據ID為i,並將數據寫入節點i中；如果節點i中空間不足，則數據ID為ID映射表中與節點i存在連結的其它節點ID,選擇具有可用空間且ID最小的節點並將數據寫入對應節點；2)確定數據的索引ID:將包括數據ID以及數據文件名的相關信息組成一個索引項，通過分布式哈希表方式，生成一個索引ID的值j，並將索引項存儲於該ID值的節點j上，具體步驟如下a)計算索引ID的值j，根據數據文件名或者標識進行哈希映射得到索引項的ID的值j:文件ID-Hash(》％10,使其取得之間的任意且唯一值；b)根據鄰接矩陣表，找到從節點i到目標存儲節點j的一條最短路徑，並將索引項存入其中；c)每個節點定期對鄰接表中的鄰接節點進行檢測，如果某個鄰接節點已失效，則修改鄰接矩陣中該節點ID和鄰接節點ID所對應行、列的值，將其設為無窮大或者一個很大的數，表示該路徑己經無效，這裡，檢測鄰接表中的節點狀態可以選擇下述方法中的任意一種0檢測節點間網絡拓撲距離；ii)檢測相關參數，包括節點間延遲以及帶寬。3)從任意節點讀取數據，讀取步驟如下-a)根據數據文件名或標識計算獲取索引ID的值j:/—ID=Hash(/)%10;b)通過一條最短路徑路由到索引節點j，取出索引表項；c)根據索引表項中的數據ID，即所存儲數據的節點ID值i，找到目標節點i,讀取數據。本發明的基於Peterson圖的數據存儲和讀取方法的有益效果在於通過將數據和節點映射到同一個ID空間，在統一的準則下有效地進行數據存儲管理，同時，數據和索引兩級存儲的方法，有利於存儲空間有限等情況下的數據定位，具有很強的實用價值。並且將Peterson結構有效應用於網絡存儲中，增強了系統的存儲可靠性。圖1是Peterson網絡中的結構和ID示意圖。圖2是本發明的基於Peterson圖的數據存儲和讀取方法中的存儲流程圖。圖3是本發明的基於Peterson圖的數據存儲和讀取方法中的讀取流程圖。圖4是利用本發明的基於Peterson圖的數據存儲和讀取方法的基於P2P網絡和Peterson網絡的雙層網絡示意圖。具體實施例方式下面結合附圖和具體實施例對本發明的基於Peterson圖的數據存儲和讀取方法進行詳細的說明。本發明提出的一種基於Peterson圖的數據存儲和讀取方法，通過兩個層次的管理，將數據內容和索引信息進行分開存儲；第一層是確定待存儲數據所對應的數據ID,即表示數據的存儲節點所對應ID，需要儘量保證將數據存儲在提交該數據存儲請求的節點或者相近的節點上，減少多個節點間傳遞數據帶來的通信代價；第二層是確定數據的索引ID，將數據ID等相關信息組成一個索引項，通過類似DHT的方式，生成一個索引ID,並將索引項存儲於該ID值的節點上。兩個層次的存儲保證了該方法可以有效地對數據進行路由定位和存儲管理，同時，負載均衡的特性，也有利於Peterson結構在分布式存儲系統中的應用。圖1是Peterson網絡中的結構和ID示意圖。如圖1所示，Peterson圖由10個節點組成，設其ID範圍為，當數據存儲其中時，要有一個一致的存儲和管理方法。圖2是本發明的基於Peterson圖的數據存儲和讀取方法中的存儲流程圖。圖3是本發明的基於Peterson圖的數據存儲和讀取方法中的讀取流程圖。如圖2所示，本發明的基於Peterson圖的數據存儲和讀取方法中的數據存儲方法，將數據內容和索引信息進行分開存儲，具體包括如下步驟1)確定待存儲數據所對應的數據ID，並存儲數據-獲取表示數據的存儲節點所對應ID，並將數據存儲在提交該數據存儲請求的節點或者相近的節點上，當通過節點i寫入數據時，如果節點i中空間充足，則數據ID為i，將數據寫入節點i中；如果節點i中空間不足，則數據ID只能為下述表1所示的ID映射表中，與節點i存在連結的其它節點ID，選擇具有可用空間且ID最小的節點，並將數據寫入該節點。2)確定數據的索引ID，將包括數據ID以及數據文件名等相關信息組成一個索引項，通過分布式哈希表方式，生成一個索引ID值j,並將索引項存儲於該ID值的節點j上，其步驟為a)計算索引ID;根據數據文件名(或者標識)進行哈希映射得到索引項的ID的值j,計算方法如下文件ID-Hash(文件名"％10，使其取得之間的任意且唯一值。b)根據表2所示的鄰接矩陣，找到從節點i到目標存儲點j的一條最短路徑，並將索引項存入其中；c)每個節點定期對鄰接表中的鄰接節點進行檢測，如果某個鄰接節點己失效，則修改鄰接矩陣中該節點ID和鄰接節點ID所對應行、列的值，將其設為無窮大或者一個很大的數，表示該路徑己經無效，這裡，檢測鄰接表中節點狀態的方法可以選擇下述方法中的任意一種i)檢測節點間網絡拓撲距離；ii)檢測節點間延遲、帶寬等相關參數。如圖3所示，本發明的基於Peterson圖的數據存儲和讀取方法中的數據讀取方法，從任意節點讀取數據時，具體包括如下步驟1)根據數據文件名(或標識)計算得到索引ID的值j:文件ID=Hash(文件名/)%10;2)通過一條最短路徑路由到索引節點j，取出索引表項；3)根據索引表項中的數據ID，即所存儲數據的節點ID值i，找到目標節點i,讀取數據。表1:Peterson網絡中的ID映射表tableseeoriginaldocumentpage7tableseeoriginaldocumentpage8層1採用糾刪碼的方法進行冗餘存儲，層2中每個節點都包含至少一個Peterson網絡中的節點信息。假設文件名為/的數據通過節點0寫入，則寫入步驟如下1)如果節點0中空間充足，則數據的ID為0，寫入節點0中；如果0中空間不足，則數據的ID只能為圖2ID映射表中存在連結的ID數(這裡可為l，4或者6)，寫入具有可用空間且ID最小的節點，這裡選擇節點l;2)計算文件ID，/—ID=Hash(/)%10，這裡假設/JD-5;3)將數據ID，數據文件名等相關信息建立索引項，如，放置在ID為5的Peterson節點中。根據表2所示的鄰接矩陣，找到從節點0到5的一條最短路徑，並將索引項存入其中。4)每隔2小時，每個節點需要對鄰接表中的鄰接節點進行檢測，如果某個鄰接節點已失效，則修改鄰接矩陣中這兩個節點ID所對應行、列的值(即該節點ID和己失效的鄰接節點ID在表2中的交叉值)，將其設為無窮大或者一個很大的數，表示該路徑已經無效。5)當從任意節點讀取數據時，假設從節點1讀取文件/，讀取過程如下a)計算文件哈希值/—ID=Hash(/)%10=5，即索引ID值；b)通過表2的矩陣路徑表，找到5跳內從節點1到達節點5的所有路徑，比如tableseeoriginaldocumentpage9然後，找到其中距離最短的路徑，艮卩l一一7—一5，路由到索引節點5，取出其中的索引表項，並返回給節點l;c)從索引表項中，讀取數據ID(這裡值為0)，則節點1向節點0發出査詢請求，讀取數據。上述說明文檔中的其他內容針對本專業領域內的普通技術人員，均可進行技術實現，這裡不再贅述。權利要求1、一種基於Peterson圖的數據存儲和讀取方法，其特徵在於，將數據內容和索引信息進行分開存儲，具體包括如下步驟1)確定待存儲數據所對應的數據ID，並存儲數據獲取表示數據的存儲節點所對應ID，並將數據存儲在提交該數據存儲請求的節點或者相近的節點上，當通過節點i寫入數據時，如果節點i中空間充足，則數據ID為i，並將數據寫入節點i中；如果節點i中空間不足，則數據ID為ID映射表中與節點i存在連結的其它節點ID，並將數據寫入對應節點；2)確定數據的索引ID將包括數據ID以及數據文件名的相關信息組成一個索引項，通過分布式哈希表方式，生成一個索引ID的值j，並將索引項存儲於該ID值的節點j上，具體步驟如下a)計算索引ID的值j，根據數據文件名或者標識進行哈希映射得到索引項的ID的值j文件ID＝Hash(f)％10，使其取得之間的任意且唯一值；b)根據鄰接矩陣表，找到從節點i到目標存儲節點j的一條最短路徑，並將索引項存入其中；c)每個節點定期對鄰接表中的鄰接節點進行檢測，如果某個鄰接節點已失效，則修改鄰接矩陣中該節點ID和鄰接節點ID所對應行、列的值，將其設為無窮大或者一個很大的數，表示該路徑已經無效；3)從任意節點讀取數據，讀取步驟如下a)根據數據文件名或標識計算獲取索引ID的值jf_ID＝Hash(f)％10；b)通過一條最短路徑路由到索引節點j，取出索引表項；c)根據索引表項中的數據ID，即所存儲數據的節點ID值i，找到目標節點i，讀取數據。2、如權利要求l所述的基於Peterson圖的數據存儲和讀取方法，其特徵在於，所述步驟l)中，當節點i中空間不足，數據ID選擇ID映射表中與節點i存在連結的其它節點ID時，選擇具有可用空間且ID最小的節點。3、如權利要求l所述的基於Peterson圖的數據存儲和讀取方法，其特徵在於，所述步驟2)的步驟c)中，採用如下所述方法中的任意一種來檢測鄰接表中的節點狀態i)檢測節點間網絡拓撲距離；ii)檢測相關參數，包括節點間延遲以及帶寬。全文摘要本發明提供一種基於Peterson圖的數據存儲和讀取方法，包括如下步驟1)獲取表示數據的存儲節點所對應ID，並將數據存儲在提交該數據存儲請求的節點或者相近的節點上，2)將包括數據ID以及數據文件名的相關信息組成一個索引項，通過分布式哈希表方式，生成一個索引ID的值j，並將索引項存儲於該ID值的節點j上；3)從任意節點讀取數據，讀取步驟如下a)根據數據文件名或標識計算獲取索引ID的值jf_ID＝Hash(f)％10；b)，路由到索引節點j，取出索引表項；c)根據索引表項中的數據ID，找到目標節點，讀取數據。該方法可以有效地對數據進行路由定位和存儲管理，同時，負載均衡的特性，也有利於Peterson結構在分布式存儲系統中的應用。文檔編號G06F12/00GK101645039SQ20091008512公開日2010年2月10日申請日期2009年6月2日優先權日2009年6月2日發明者尤佳莉,王勁林,王玲芳,鄧浩江申請人:中國科學院聲學研究所