一种基于访问频度变长逻辑分段的数据分发方法

摘要

本发明提供一种基于访问频度变长逻辑分段的数据分发方法。该方法通过将文件切分成细粒度的单元，基于用户在文件不同时间段上访问频度的差异，为文件生成变长逻辑分段，然后针对不同逻辑分段分别进行基于流行度的多副本放置，并为每个逻辑分段生成多级索引项，同时根据文件的副本等级调整更新文件的索引项，使数据在CDN网络中的副本分布更加符合用户的实际访问惯。同时，细粒度的文件切片，使得用户访问行为的统计更加精准，便于对用户访问频度特征基于时间变化的更新，并应用于内容分发的副本生成上，使系统中的数据分布自适应的随时间进行调整。另外，多级索引的应用，有效降低了数据副本等级调整时所带来的通信开销，提高了系统性能。

主权项

一种基于访问频度变长逻辑分段的数据分发方法，对于分发到网络中的文件f，分发过程如下：1)将文件f切分为大小相等的小数据块ub序列{ub1，ub2，...，ubn}；2)根据文件f的初始用户访问概率分布函数g(x)，计算得到每一个ubi的访问概率积分，整个序列的概率为{q1，q2，...，qn}；3)通过合并算法，将ub序列进行合并，生成数据片段序列{seg1，seg2，...，segk}，并为每个数据片段seg计算流行度和副本等级，其中，副本等级计算方法如下：假设D(l)是计算副本数目的函数，其只跟副本等级和总节点数相关，则目标方程为： F ′ ( L , Λ ) = arg min { Σ m = 1 M Σ k = 1 k m s u c m , k D ( l m , k ) + λ ( Σ m = 1 M Σ k = 1 k m c m , k q m , k l m , k - A ) } 其中，L为副本等级，km为第m个文件的数据片段数目；cm，k为第m个文件中第k个数据片段seg中所包含的小数据块ub数目；lm，k为第m个文件中第k个数据片段seg所对应的副本等级数，通过数值分析中的线性规划算法估计该lm，k的值；qm，k为第m个文件中第k个数据片段seg对应的用户访问概率，A为预设的平均延迟；4)根据所述步骤3)中的计算结果，得到所有数据片段seg的副本等级数，同时对应了所有小数据块ub的副本等级，然后对文件的所有小数据块ub根据其等级在CDN网络中进行放置，在放置时，假设ub的副本等级为L，首先计算小数据块ub的ID号，根据分布式哈希表DHT路由算法找到当前ub的主节点；然后将小数据块ub以及对应副本等级相关信息下载到主节点；再通过主节点的路由表找到与主节点的ID匹配L位的所有节点，将ub复制到这些节点上；5)为每个数据片段seg生成其一级索引项，其信息包括：每个小数据块ub的大小、数据片段seg中小数据块ub的起始和结尾序号、数据片段seg中所有小数据块ub的ID列表以及更新时间，并根据数据片段seg的副本等级将一级索引项分布在CDN网络中；6)通过整个文件的流行度信息，计算整个文件若不进行切分时对应的副本等级lall；7)对每个文件生成二级索引项列表，包括：数据片段seg的ID列表、数据片段seg的开始和结尾ub序号以及每个小数据块ub大小，以文件名的哈希值作为键值，并通过整个文件的副本等级lall对二级索引项进行放置，放置方法与所述步骤4)中的方法相同；8)文件放置完成后，以根据实际应用而选择的时间T为周期观测用户对文件不同小数据块ub上访问频度的变化，重新计算数据片段seg逻辑分块中的小数据块ub数目和首尾序号、访问流行度以及副本等级，并根据新的副本等级调整小数据块ub的副本数目，同时更新文件的一级和二级索引项。