[发明专利]分布式数据存储系统中多维有序数据的存储方法

摘要

本发明涉及一种分布式数据存储系统中多维有序数据的存储方法，属于计算机数据管理技术领域。该方法首先对待存储对象进行定义，得到由待存储对象组成的多维有序数据集合，并对基于该多维有序数据集合的操作进行定义；随后枚举所有的存储方案并计算相应的期望时间代价，最终选择期望时间代价最小的存储方案作为最终存储方案。本发明能够有效的找到一种高效的多维有序数据集合存储方案，方法直观有效、便于使用。

主权项

一种分布式数据存储系统中多维有序数据的存储方法，其特征在于，该方法包括以下步骤：1)对待存储的由多个对象组成的多维数据进行定义，并将维度划分为有序维度集合与无序维度集合；设O＝{o1,o2,...,os}为s个待存储对象组成的集合，Dim{D1,D2,...,Dk}为集合O中所有待存储对象维度集合，共有k个维度，s、k均为正整数；V为集合O中所有待存储对象数据值集合；设M为有序维度集合，N为无序维度集合,M、N均为非负整数，则待存储对象组成的集合O表达为多维有序数据集合的形式，如式(1)所示：SeqData(|o1,o2,...,os|,M,N,V)  (1)2)对基于步骤1)得到的多维有序数据集合的读取操作进行定义；2‑1)单元读取：对Di∈Dim，通过指定每一个维度的具体值Di＝di,i＝1,2,...k，进行数据读取的操作称为单元读取，定义单元读取操作为：Opread；2‑2)确定顺序近邻读取维度；对于有顺序近邻读取需求的维度Dtarget∈M，获取在该维度上的顺序近邻操作定义为：Opnext(Dtarget)；即对于维度Dtarget，取值为dtarget，通过指定Dtarget＝l‑1(l(dtarget)+1)实现顺序近邻操作，其中l为顺序函数，将维度取值映射为有序数据序号，l‑1则将数据序号反映射为维度取值；2‑3)确定逆序近邻操作维度；对于有逆序近邻读取需求的维度Dtarget∈M，获取在该维度上的逆序近邻操作定义为：Oppre(Dtarget)；即对于维度Dtarget，通过指定Dtarget＝l‑1(l(dtarget)‑1)实现逆序近邻操作；2‑4)确定序列读取操作；一次序列读取操作包含一次单元读取操作以及q次连续的顺序或逆序近邻操作；一次序列读取操作定义为：Opseq(Dtarget,q)；根据具体数据访问需求，确定最终的序列读取操作需求，即确定SeqArray＝[Opseq1,Opseq2,...,Opseqt]，其中Opseq是Opseq(Dtarget,q)的简写，表示一种序列读取操作；SeqArray为针对具体数据访问需求的访问序列数组，共包括t个序列读取操作；2‑5)统计步骤2‑4)中不同序列读取操作的使用频率，得到与会话数组对应的使用频率数组FreqArray＝[fre1,fre2,...,fret]，frei表示第i种序列读取操作的频率；3)枚举存储方案，计算每种该存储方案期望时间代价；多维有序数据集合的存储方案，即求解函数func使得对于所有Di，func(Di)＝DimArray[c],c＝1,2；其中，函数func表示存储方案，c代表数据下标，1,2是数组下标的可能取值；给定一种存储方案func，对系统读取时间代价进行评估，对于每一种操作，又分为两种情况，本地读取和异地读取；3‑1)测量当前系统的网络传输速度和磁盘读取速度；其中Ttrans为系统网络传输单个数据速度，Tread为磁盘读取速度；3‑2)计算单元读取时间代价；对于一次精确读取操作Opread，计算其本地读取时间代价如式(2)所示：TOpreadlocal=Ttrans+TrowLocate+ΠDi∈CKSet|Di|TcolLocate+Tread---(2)]]>式中，|Di|为维度Di的不同值的个数；TrowLocate为行键在节点中定位和读取的时间，TcolLocate为列寻址和定位时间；对应地,如果数据异地地读取，则增加协调者节点到数据拥有者节点的一次网络通信，定义异地读取时间代价如式(3)所示：TOpreadremote=Trans+TOpreadlocal---(3)]]>即增加一次数据网络通信消耗；3‑3)计算顺序近邻读取时间代价；本地读取时间代价如式(4)所示：TOpnextlocal=TOpreadlocal+sign(Dtarget∉CKSet)×Tindex---(4)]]>式中，Tindex为设置性能消耗，定义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)，遍历所有枚举的存储方案并计算其相应的期望时间代价,选择期望时间代价最小的存储方案作为最终存储方案。