CN100388237C - 基于轻量计算的数据重组方法 - Google Patents
基于轻量计算的数据重组方法 Download PDFInfo
- Publication number
- CN100388237C CN100388237C CNB2004100838706A CN200410083870A CN100388237C CN 100388237 C CN100388237 C CN 100388237C CN B2004100838706 A CNB2004100838706 A CN B2004100838706A CN 200410083870 A CN200410083870 A CN 200410083870A CN 100388237 C CN100388237 C CN 100388237C
- Authority
- CN
- China
- Prior art keywords
- disk
- storage
- data block
- data
- media file
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
本发明属于流媒体应用中存储管理技术领域，是一种基于轻量计算的数据重组方法。在流媒体应用的服务器中，当存储发生变化(存储增加或减少)时，媒体数据在存储中的分布便产生了不均衡性，本发明能够以极少的计算量和移动代价，将媒体数据在新的存储中进行分布调整，使得充分利用系统存储容量资源和带宽资源。当系统发生存储变化后，数据重组的方法为：将数据块的顺序号在媒体文件的有效位内进行循环右移，移动的位数由该媒体文件所经历的存储变化操作所决定，以移位所得的值作为函数值，以当前磁盘数为除数，运用除余哈希法选择新磁盘上存储的数据块(存储增加)或被删除磁盘上数据块的新存储位置(存储减少)。
Description
技术领域
本发明属于流媒体应用中存储管理技术领域，特别是一种基于轻量计算的数据重组方法。
背景技术
流媒体应用建立在IP网络的基础上，通过IP网络进行传输；系统分为服务器端和客户端，服务器端由具有一定计算能力和存储能力的服务器机群构成，负责存储的服务器内带有一组磁盘，客户端即可为普通的PC机，也可为电视与机顶盒的组合；媒体文件通过IP网从服务器端流向客户端，在客户端利用PC机或机顶盒中的播放器软件进行播放。与传统的文本、图片信息相比，流媒体应用中的视、音频文件需要很大的存储空间和播放速率，因此系统采用多个磁盘来存储媒体信息；此外，为了提高同一媒体文件的并发访问量，通常采用interleaving的技术，把一个媒体文件分成顺序的数据块，将这些数据块分散地存储在多个磁盘上。文献[1]
Halvorsen，Carsten Griwodz，Ketil Lund，Vera Goebel，ThomasPlagemann，Jonathan Walpole.Storage Systems Support for MultimediaApplications.IEEE DISTRIBUTED SYSTEMS ONLINE 1541-4922 Vol.5，No.2，February 2004。对于这些数据块在多个磁盘上的存储顺序来说，通常有两种：顺序存储和随机存储。顺序存储就是将同一媒体文件中的数据块以轮循的方式在多个磁盘上进行存储，系统可在多个磁盘上顺序读取；随机存储是将一个媒体文件中的数据块随机地存储在多个磁盘上，通过目录系统来读取数据块。对于这样的媒体文件存储方式，当存储发生变化时，系统将加入新的磁盘或删除一部分现有的磁盘，此时，为了充分利用存储空间及存储带宽，原有媒体数据块必须进行分布调整。现有的解决方案有三种，第一种为顺序存储及完全重组的方法，文献[2]S.Ghandeharizadeh and D.Kim.On-line reorganization of data in scalablecontinuous media servers.Proc.7th International Conference on Database andExpert Systems Applications，September 1996，这种方法的缺点在于存储变化操作后需要移动的数据块太多，使得调整代价十分大；第二种方法是基于随机存储的重组方法，文献[3]A.Goel，C.Shahabi，S.-Y.Yao，and R.Zimmerman.SCADDAR：An efficient randomized technique to reorganizecontinuous media blocks.Proc.International Conference on Data Engineering，2002，作者又在文献[3]Shu-Yuen Didi Yao，Cyrus Shahabi，Per-Ake Larson，Hash-Based Labeling Techniques for Storage Scaling，To appear in TheVLDB Journal中对该方法进行了改进，但是这种基于随机存储的方法仍然存在着一些问题，方法的结果与伪随机数生成器的选取有直接的关系，具有不确定性，致使磁盘的负载均衡性表现的不是很好，并且数据块调整的计算复杂度与存储变化次数相关，即使在文献[3]中作者已经解决了这个问题，但仍然存在着试探的问题，计算复杂度仍与试探次数相关；第三种方法是针对于增长式无服务器VOD系统提出的一种“行变换数据重组算法”，文献[4]T.K.Ho and Jack Y.B.Lee.A Row-Permutated DataReorganization Algorithm for Growing Server-less Video-on-DemandSystems.Proc.Intemational Symposium on Cluster Computing and the Grid(CCGrid)2003，Tokyo，Japan，May 12-15，2003，由于这种方法是针对无服务器流媒体系统设计的，因而无法适应一般的流媒体应用。
综上所述，对于存储变化后的数据分布问题，现有解决方法都存在着各种不足，主要表现在移动数据量大、调整计算复杂度高和负载均衡性不好三个方面。
发明内容
本发明的目的在于提供一种基于轻量计算的数据重组方法，它能够通过简单的计算，移动很少的数据，保证存储具有很好的负载均衡特性，使得充分利用系统存储资源和带宽资源。
在流媒体应用的服务器中，当存储发生变化(存储增加或减少)时，媒体数据在存储中的分布便产生了不均衡性，本发明能够以极少的计算量和移动代价，将媒体数据在新的存储中进行分布调整，使得充分利用系统存储容量资源和带宽资源。当系统发生存储变化后，数据重组的方法为：将数据块的顺序号在媒体文件的有效位内进行循环右移，移动的位数由该媒体文件所经历的存储变化操作所决定，以移位所得的值作为函数值，以当前磁盘数为除数，运用除余哈希法选择新磁盘上存储的数据块(存储增加)或被删除磁盘上数据块的新存储位置(存储减少)。
本发明的基于轻量计算的数据重组方法，当存储发生变化时，对于磁盘上的每个数据块，通过轻量的计算得到一个值作为函数值，并以当前磁盘数为除数，运用除余哈希法选择新磁盘上存储的数据块或被删除磁盘上数据块的新存储位置。
本发明是一种基于轻量计算的数据重组方法，其实现方法如下：
每个媒体文件以(F，B，RECORD)的三元组来表示，其中F为该媒体文件的标识号，B为该媒体文件的有效位，RECORD为该媒体文件的存储变化记录，记录在该媒体文件的生命周期内所经历的存储变化操作，每个媒体文件以一定的大小被分为多个数据块，每个数据块以(F，SID)的二元组来表示，其中F为数据块所属媒体文件的标识号，SID为数据块在媒体文件中的顺序号；
当存储发生变化时，以磁盘为单位进行数据重组操作，分为两种情况：存储增加和存储减少；
当有新的磁盘加入到磁盘组中时，新磁盘的磁盘号在原有磁盘号的基础上递增，更新所有文件的RECORD。对于一个磁盘上的一个数据块来说，首先根据该数据块所属媒体文件的RECORD得到媒体文件所经历的存储增加的次数N，然后根据媒体文件的有效位B对该数据块的SID进行有效位内的循环右移N位得到的值记为PID，再根据D＝(PID+F)modM来决定这块数据块是否要被转移到新的磁盘上，其中M为存储变化后的磁盘个数，当D不为新加入的磁盘的标识号时，该数据块并不移动，只有当D为新加入的磁盘序号，该数据块被转移到该序号为D的磁盘上；
当在现有的磁盘组中删除磁盘时，按照磁盘序号从大到小的方向进行磁盘的删除，更新所有文件的RECORD。对于被删除磁盘上的数据块来说，首先根据该数据块所属媒体文件的RECORD得到媒体文件所经历的存储增加的次数N，然后根据媒体文件的B对该数据块的SID进行有效位内的循环右移N位得到的值记为PID，通过D＝(PID+F)modM来计算数据块被转移的磁盘序号，其中M为磁盘删除后的磁盘组中磁盘个数，D为数据块将被转移到的目标磁盘号。
附图说明
图1是本发明的基于轻量计算的数据重组方法流程图。
具体实施方式
综上所述，本发明的基于轻量计算的数据重组方法具体步骤如下：参见图1。
步骤S1.1：读取存储变化类型S，存储增加或存储减少，更新所有媒体文件的存储变化记录；
步骤S1.2：如果S为增加，需要调整原有磁盘组上的数据块，找到需要移动的数据并将其移动到新的磁盘上，进入S1.3，如果S为减少，需要将被删除磁盘上的所有数据转移到其他未被删除的磁盘上，进入S1.12；
步骤S1.3：从现有磁盘中选择一个未调整过的磁盘作为调整对象；
步骤S1.4：在该磁盘中找到一个未调整过的数据块作为调整对象；
步骤S1.5：读取数据块所属媒体文件所经历的存储增加的变化次数N，读取文件标识号F和有效位B，读取该数据块顺序号I以及存储变化后的磁盘个数M；
步骤S1.6：将I在B位内循环右移N位，得到的值记为PID；
步骤S1.7：计算(PID+F)modM，如果所得到的值是新加入磁盘的标号，则需要移动该数据块，则进入S1.8，否则该数据块不需要移动，进入S1.9；
步骤S1.8：记录该数据块转移的目标磁盘号为(PID+F)modM；
步骤S1.9：如果磁盘中还有数据块没有进行调整，转入S1.4，否则进入S1.10；
步骤S1.10：移动所有需要移动的数据块到其新的存储位置；
步骤S1.11：如果还有其他没有进行调整的磁盘，转入S1.3，否则进入S1.19；
步骤S1.12：从被删除磁盘中选择一个未调整的磁盘作为调整对象；
步骤S1.13：从该磁盘中找到一个未调整过的数据块作为调整对象；
步骤S1.14：读取数据块所属媒体文件所经历的存储增加的变化次数N，读取文件标识号F及有效位B，读取该数据块顺序号I以及存储变化后的磁盘个数M；
步骤S1.15：将I在B位内循环右移N位，得到的值记为PID，记录该数据块转移的新位置是磁盘号为(PID+F)modM的磁盘；
步骤S1.16：，如果磁盘中还有数据块没有进行调整，转入S1.13，否则进入S1.17；
步骤S1.17：移动磁盘上的所有数据到新的存储位置上；
步骤S1.18：如果还有其他被删除的磁盘没有进行调整，转入S1.12，否则进入S1.19；
步骤S1.19：此次存储变化后的数据分布调整结束。
本发明的实现依赖于以下三个前提条件：
第一，在流媒体应用系统中，一个存储服务器中所采用的存储介质为相同的磁盘所组成的磁盘组，这样每个磁盘的存储空间和带宽都是相同的；
第二，系统中所有媒体文件都分成大小相同的数据块；
第三，初始状态，对于一个媒体文件的每个数据块来说，根据D0＝(SID+F)modM0来决定它在磁盘组中的存储位置，其中M0是初始时磁盘组中的磁盘个数，D0代表该数据块的初始存储磁盘号，F为该文件的标识号。
比较本发明与现有数据重组方法，我们显然可以看出本发明具有以下优点：
1.当存储发生变化后，数据调整过程中针对一个数据块的计算复杂度为1，不受该数据块所属文件所经历的存储变化次数影响。
2.当存储发生变化后，调整数据块分布所移动的数据块个数接近理论最低值，体现出很少的调整代价。
3.数据块在新的存储内调整之后，存储内所有磁盘具有很好的负载均衡性。
4.我们的数据重组方法对系统的存储要求很低，无需目录系统支持。
Claims (2)
1.基于轻量计算的数据重组方法，其特征在于，当存储发生变化时，对于磁盘上的每个数据块，通过轻量的计算得到一个值作为函数值，并以当前磁盘数为除数，运用除余哈希法选择新磁盘上存储的数据块或被删除磁盘上数据块的新存储位置；
其中，所述通过轻量的计算得到一个值作为函数值，具体步骤如下：
步骤S1.1：读取存储变化类型S，存储增加或存储减少，更新所有媒体文件的存储变化记录；
步骤S1.2：如果S为增加，需要调整原有磁盘组上的数据块，找到需要移动的数据并将其移动到新的磁盘上，进入S1.3，如果S为减少，需要将被删除磁盘上的所有数据转移到其他未被删除的磁盘上，进入S1.12；
步骤S1.3：从现有磁盘中选择一个未调整过的磁盘作为调整对象；
步骤S1.4：在该磁盘中找到一个未调整过的数据块作为调整对象；
步骤S1.5：读取数据块所属媒体文件所经历的存储增加的次数N，读取媒体文件的标识号F和媒体文件的有效位B，读取该数据块顺序号I以及存储变化后的磁盘个数M；
步骤S1.6：将I在B位内循环右移N位，得到的值记为PID；
步骤S1.7：计算(PID+F)modM，如果所得到的值是新加入磁盘的标号，则需要移动该数据块，则进入S1.8，否则该数据块不需要移动，进入S1.9；
步骤S1.8：记录该数据块转移的目标磁盘号为(PID+F)modM；
步骤S1.9：如果磁盘中还有数据块没有进行调整，转入S1.4，否则进入S1.10；
步骤S1.10：移动所有需要移动的数据块到其新的存储位置；
步骤S1.11：如果还有其他没有进行调整的磁盘，转入S1.3，否则进入S1.19；
步骤S1.12：从被删除磁盘中选择一个未调整的磁盘作为调整对象；
步骤S1.13：从该磁盘中找到一个未调整过的数据块作为调整对象；
步骤S1.14：读取数据块所属媒体文件所经历的存储增加的变化次数N，读取文件标识号F及有效位B，读取该数据块顺序号I以及存储变化后的磁盘个数M；
步骤S1.15：将I在B位内循环右移N位，得到的值记为PID，记录该数据块转移的新位置是磁盘号为(PID+F)modM的磁盘；
步骤S1.16：，如果磁盘中还有数据块没有进行调整，转入S1.13，否则进入S1.17；
步骤S1.17：移动磁盘上的所有数据到新的存储位置上；
步骤S1.18：如果还有其他被删除的磁盘没有进行调整，转入S1.12，否则进入S1.19；
步骤S1.19：此次存储变化后的数据分布调整结束；
该方法的实现依赖于以下三个前提条件：
第一，在流媒体应用系统中，一个存储服务器中所采用的存储介质为相同的磁盘所组成的磁盘组，这样每个磁盘的存储空间和带宽都是相同的；
第二，系统中所有媒体文件都分成大小相同的数据块；
第三，初始状态，对于一个媒体文件的每个数据块来说，根据D0＝(SID+F)modN0来决定它在磁盘组中的存储位置，其中N0是初始时磁盘组中的磁盘个数，D0代表该数据块的初始存储磁盘号，F为该文件的标识号。
2.根据权利要求1所述的基于轻量计算的数据重组方法，其特征在于，每个媒体文件以(F，B，RECORD)的三元组来表示，其中F为该媒体文件的标识号，B为该媒体文件的有效位，RECORD为该媒体文件的存储变化记录，记录在该媒体文件的生命周期内所经历的存储变化操作，每个媒体文件以一定的大小被分为多个数据块，每个数据块以(F，SID)的二元组来表示，其中F为数据块所属媒体文件的标识号，SID为数据块在媒体文件中的顺序号；
当存储发生变化时，以磁盘为单位进行数据重组操作，分为两种情况：存储增加和存储减少；
当有新的磁盘加入到磁盘组中时，新磁盘的磁盘号在原有磁盘号的基础上递增，更新所有文件的RECORD，对于一个磁盘上的一个数据块来说，首先根据该数据块所属媒体文件的RECORD得到媒体文件所经历的存储增加的次数N，然后根据媒体文件的有效位B对该数据块的SID进行有效位内的循环右移N位得到的值记为PID，再根据D＝(PID+F)modM来决定这块数据块是否要被转移到新的磁盘上，其中M为存储变化后的磁盘个数，当D不为新加入的磁盘的标识号时，该数据块并不移动，只有当D为新加入的磁盘序号，该数据块被转移到该序号为D的磁盘上；
当在现有的磁盘组中删除磁盘时，按照磁盘序号从大到小的方向进行磁盘的删除，更新所有文件的RECORD，对于被删除磁盘上的数据块来说，首先根据该数据块所属媒体文件的RECORD得到媒体文件所经历的存储增加的次数N，然后根据媒体文件的B对该数据块的SID进行有效位内的循环右移N位得到的值记为PID，通过D＝(PID+F)modM来计算数据块被转移的磁盘序号，其中M为磁盘删除后的磁盘组中磁盘个数，D为数据块将被转移到的目标磁盘号。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB2004100838706A CN100388237C (zh) | 2004-10-20 | 2004-10-20 | 基于轻量计算的数据重组方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB2004100838706A CN100388237C (zh) | 2004-10-20 | 2004-10-20 | 基于轻量计算的数据重组方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1763726A CN1763726A (zh) | 2006-04-26 |
| CN100388237C true CN100388237C (zh) | 2008-05-14 |
Family
ID=36747869
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB2004100838706A Expired - Fee Related CN100388237C (zh) | 2004-10-20 | 2004-10-20 | 基于轻量计算的数据重组方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN100388237C (zh) |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5513011A (en) * | 1993-01-25 | 1996-04-30 | Matsushita Electric Industrial Co., Ltd. | Method and apparatus for recording or reproducing video data on or from storage media |
| JPH1074156A (ja) * | 1996-08-29 | 1998-03-17 | Toyo Electric Mfg Co Ltd | データ処理装置 |
| CN1247608A (zh) * | 1997-02-27 | 2000-03-15 | 国际商业机器公司 | 用于分级存储管理系统的转换廉价磁盘冗余阵列 |
| US6442649B1 (en) * | 1999-08-18 | 2002-08-27 | Intel Corporation | Dynamic expansion of storage device array |
| WO2004001600A1 (en) * | 2002-06-24 | 2003-12-31 | Network Appliance, Inc. | Using file system information in raid data reconstruction and migration |
| CN1519726A (zh) * | 2003-01-24 | 2004-08-11 | 华为技术有限公司 | 一种磁盘在线重构方法 |
-
2004
- 2004-10-20 CN CNB2004100838706A patent/CN100388237C/zh not_active Expired - Fee Related
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5513011A (en) * | 1993-01-25 | 1996-04-30 | Matsushita Electric Industrial Co., Ltd. | Method and apparatus for recording or reproducing video data on or from storage media |
| JPH1074156A (ja) * | 1996-08-29 | 1998-03-17 | Toyo Electric Mfg Co Ltd | データ処理装置 |
| CN1247608A (zh) * | 1997-02-27 | 2000-03-15 | 国际商业机器公司 | 用于分级存储管理系统的转换廉价磁盘冗余阵列 |
| US6442649B1 (en) * | 1999-08-18 | 2002-08-27 | Intel Corporation | Dynamic expansion of storage device array |
| WO2004001600A1 (en) * | 2002-06-24 | 2003-12-31 | Network Appliance, Inc. | Using file system information in raid data reconstruction and migration |
| CN1519726A (zh) * | 2003-01-24 | 2004-08-11 | 华为技术有限公司 | 一种磁盘在线重构方法 |
Non-Patent Citations (2)
| Title |
|---|
| 基于RAID-5结构的校验位扩展算法研究. 王俊伟，刘志明，彭宇行，金士尧.计算机应用，第23卷第11期. 2003 |
| 基于RAID-5结构的校验位扩展算法研究. 王俊伟，刘志明，彭宇行，金士尧.计算机应用，第23卷第11期. 2003 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN1763726A (zh) | 2006-04-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102541990B (zh) | 利用虚拟分区的数据库重新分布方法和系统 | |
| Guo et al. | Design and evaluation of a scalable and reliable P2P assisted proxy for on-demand streaming media delivery | |
| CN101594292A (zh) | 内容发布方法、服务重定向方法及系统、节点设备 | |
| Ghandeharizadeh et al. | Placement of continuous media in wireless peer-to-peer networks | |
| CN101170371B (zh) | 一种p2p点播中客户端数据请求优化方法及系统 | |
| CN101800768A (zh) | 一种基于存储联盟子集划分的网格数据副本生成方法 | |
| CN111669629A (zh) | 视频cdn节点即时扩容方法、调度器及cnd存储系统 | |
| Sun et al. | Dynamic data replication based on access cost in distributed systems | |
| CN100388237C (zh) | 基于轻量计算的数据重组方法 | |
| Shi et al. | Bwcc: A fs-cache based cooperative caching system for network storage system | |
| CN113688115A (zh) | 一种基于Hadoop的档案大数据分布式存储系统 | |
| Xia et al. | Algorithms and performance of load-balancing with multiple hash functions in massive content distribution | |
| Rasool et al. | Replica placement in multi-tier data grid | |
| Jiang et al. | A replica placement algorithm for hybrid CDN-P2P architecture | |
| CN113472864B (zh) | 高性能的区块链分布式存储系统及方法、设备、存储介质 | |
| Dyaberi et al. | Storage optimization for a peer-to-peer video-on-demand network | |
| Rappos et al. | A cloud data center optimization approach using dynamic data interchanges | |
| KR102672013B1 (ko) | 서비스 제공을 위한 블록체인 데이터 저장 방법 및 저장 관리장치 | |
| Yao et al. | Hash-based labeling techniques for storage scaling | |
| Misra et al. | CLASH: a protocol for Internet-scale utility-oriented distributed computing | |
| Li et al. | GenRe: A general replication scheme over an abstraction of DHTs | |
| Séguin et al. | Towards elasticity in distributed file systems | |
| Chung et al. | Optimising upload bandwidth for quality of VCR operations in P2P VoD systems | |
| Lee et al. | A hierarchical overlay structure for video transmission in P2P cloud storage systems | |
| Sumari et al. | Data organization for broadcasting in mobile computing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| C17 | Cessation of patent right | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20080514 Termination date: 20091120 |