[發明專利]分布式數據存儲系統中多維有序數據的存儲方法

有效

• 申請號: 201610459969.4
• 申請日: 2016-06-22
• 公開（公告）號: CN105975634B
• 公開（公告）日: 2017-10-31
• 發明（設計）人: 王建民;黃向東;張博;龍明盛
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F3/06
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙)11201
• 代理人: 廖元秋

1.一種分布式數據存儲系統中多維有序數據的存儲方法，其特征在于，該方法包括以下步驟：

1)對待存儲的由多個對象組成的多維數據進行定義，并將維度劃分為有序維度集合與無序維度集合；

設O＝{o₁,o₂,...,o_s}為s個待存儲對象組成的集合，Dim{D₁,D₂,...,D_k}為集合O中所有待存儲對象維度集合，共有k個維度，s、k均為正整數；V為集合O中所有待存儲對象數據值集合；

設M為有序維度集合，N為無序維度集合,M、N均為非負整數，則待存儲對象組成的集合O表達為多維有序數據集合的形式，如式(1)所示：

SeqData(|o₁,o₂,...,o_s|,M,N,V)(1)

2)對基于步驟1)得到的多維有序數據集合的讀取操作進行定義；

2-1)單元讀取：對D_i∈Dim，通過指定每一個維度的具體值D_i＝d_i,i＝1,2,...k，進行數據讀取的操作稱為單元讀取，定義單元讀取操作為：Op_read；

2-2)確定順序近鄰讀取維度；對于有順序近鄰讀取需求的維度D_target∈M，獲取在該維度上的順序近鄰操作定義為：Op_next(D_target)；

即對于維度D_target，取值為d_target，通過指定D_target＝l^-1(l(d_target)+1)實現順序近鄰操作，其中l為順序函數，將維度取值映射為有序數據序號，l^-1則將數據序號反映射為維度取值；

2-3)確定逆序近鄰操作維度；對于有逆序近鄰讀取需求的維度D_target∈M，獲取在該維度上的逆序近鄰操作定義為：Op_pre(D_target)；

即對于維度D_target，通過指定D_target＝l^-1(l(d_target)-1)實現逆序近鄰操作；

2-4)確定序列讀取操作；

一次序列讀取操作包含一次單元讀取操作以及q次連續的順序或逆序近鄰操作；一次序列讀取操作定義為：Op_seq(D_target,q)；

根據具體數據訪問需求，確定最終的序列讀取操作需求，即確定SeqArray＝[Op_seq1,Op_seq2,...,Op_seqt]，其中Op_seq是Op_seq(D_target,q)的簡寫，表示一種序列讀取操作；SeqArray為針對具體數據訪問需求的訪問序列數組，共包括t個序列讀取操作；

2-5)統計步驟2-4)中不同序列讀取操作的使用頻率，得到與會話數組對應的使用頻率數組FreqArray＝[fre₁,fre₂,...,fre_t]，fre_i表示第i種序列讀取操作的頻率；

3)枚舉存儲方案，計算每種該存儲方案期望時間代價；

多維有序數據集合的存儲方案，即求解函數func使得對于所有D_i，func(D_i)＝DimArray[c],c＝1,2；其中，函數func表示存儲方案，c代表數據下標，1,2是數組下標的可能取值；

給定一種存儲方案func，對系統讀取時間代價進行評估，對于每一種操作，又分為兩種情況，本地讀取和異地讀取；

3-1)測量當前系統的網絡傳輸速度和磁盤讀取速度；其中T_trans為系統網絡傳輸單個數據速度，T_read為磁盤讀取速度；

3-2)計算單元讀取時間代價；對于一次精確讀取操作Op_read，計算其本地讀取時間代價如式(2)所示：

TOpreadlocal=Ttrans+TrowLocate+ΠDi∈CKSet|Di|TcolLocate+Tread---(2)]]>

式中，|D_i|為維度D_i的不同值的個數；T_rowLocate為行鍵在節點中定位和讀取的時間，T_colLocate為列尋址和定位時間；

對應地,如果數據異地地讀取，則增加協調者節點到數據擁有者節點的一次網絡通信，定義異地讀取時間代價如式(3)所示：

TOpreadremote=Trans+TOpreadlocal---(3)]]>

即增加一次數據網絡通信消耗；

3-3)計算順序近鄰讀取時間代價；

本地讀取時間代價如式(4)所示：

TOpnextlocal=TOpreadlocal+sign(Dtarget∉CKSet)×Tindex---(4)]]>

式中，T_index為設置性能消耗，定義sign()為符號函數，sign(true)＝1；sign(false)＝0；

如果數據異地讀取，則其異地讀取時間代價如式(5)所示：

TOpnextremote=Ttrans+TOpnextlocal---(5)]]>

3-4)計算逆序近鄰讀取時間代價；

本地讀取時間代價如式(6)所示：

TOpprelocal=TOpreadlocal+sign(Dtarget∉CKSet)×Tindex---(6)]]>

如果數據異地讀取，則其異地讀取時間代價如式(7)所示：

TOppreremote=Trans+TOpnextlocal---(7)]]>

3-5)對于t個序列讀取操作，計算每一種序列讀取的時間代價；

TSeq=TOpreadlocal+sign(Dtarget∉RKSet)×q×TOpnextlocal+sign(Dtarget∈RKSet)×(qnTOpmaxlocal+q(n-1)nTOpnextRemote)---(8)]]>

其中，n是集群節點個數,q是該種序列讀取的連續次數；

3-6)計算給定存儲方案的期望時間代價E；

E=(Σi=1tTSeqi×frei)---(9)]]>

(4)重復步驟3)，遍歷所有枚舉的存儲方案并計算其相應的期望時間代價,選擇期望時間代價最小的存儲方案作為最終存儲方案。