[发明专利]节点副本更新方法和装置

权利要求书

1.一种节点副本更新方法，其特征在于，包括：

检测Chord环上副本更新到最高版本的节点，其中，所述Chord环上的所有节点具有同一副本，并且每个节点的指针表中包括该节点的若干后继节点和若干后继节点的副本版本信息；

将副本更新到最高版本的节点作为更新树的根节点，按照Chord环上各个节点的副本版本由高到低的顺序，由上至下构建由各个节点组成的更新树，包括：

将副本更新到最高版本的节点作为更新树的根节点；

将Chord环上的所有节点组成的区域作为待划分区域；

重复以下过程，直到待划分区域为空：

将待划分区域中除副本版本最高的节点以外的节点组成的区域划分为若干子区域；

针对每个子区域，将子区域中副本版本最高的节点添加到更新树中，作为所述待划分区域中副本版本最高的节点的子节点；以及

将每个子区域分别作为待划分区域；

按照更新树从上至下的顺序，依次令更新树中的每个节点根据其父节点上的副本进行更新。

2.根据权利要求1所述的方法，其特征在于，所述将待划分区域中除副本版本最高的节点以外的节点组成的区域划分为若干子区域包括：

将待划分区域中除副本版本最高的节点以外的节点组成的区域平均划分为两个子区域。

3.根据权利要求1所述的方法，其特征在于，还包括用于确定子区域中副本版本最高的节点的方法：

根据子区域中首个节点的指针表中的各个节点，将子区域分割为若干区间；

按照从后至前的顺序，每个区间中除最后一个节点以外的每个节点从后继节点读取当前副本版本最高的节点信息，并根据本节点的副本版本信息更新所述区间中当前副本版本最高的节点信息，直至区间中的首个节点；

子区域中的首个节点从每个区间的首个节点获取每个区间的副本版本最高的节点信息；

子区域中的首个节点比较各个区间的最高的副本版本，确定子区域中副本版本最高的节点。

4.根据权利要求1所述的方法，其特征在于，

所述按照更新树从上至下的顺序，依次令更新树中的每个节点根据其父节点上的副本进行更新包括：按照更新树从上至下的顺序，依次令更新树中的每个节点根据其父节点上的副本进行增量更新，

和/或，

所述节点为内容分发网络中的边缘服务器。

5.一种节点副本更新装置，其特征在于，包括：

最高版本更新检测模块，用于检测Chord环上副本更新到最高版本的节点，其中，所述Chord环上的所有节点具有同一副本，并且每个节点的指针表中包括该节点的若干后继节点和若干后继节点的副本版本信息；

更新树构建模块，用于将副本更新到最高版本的节点作为更新树的根节点，按照Chord环上各个节点的副本版本由高到低的顺序，由上至下构建由各个节点组成的更新树，其中，所述更新树构建模块包括：

初始化单元，用于将副本更新到最高版本的节点作为更新树的根节点；将Chord环上的所有节点组成的区域作为待划分区域；以及

迭代构建单元，用于重复以下过程，直到待划分区域为空：将待划分区域中除副本版本最高的节点以外的节点组成的区域划分为若干子区域；针对每个子区域，将子区域中副本版本最高的节点添加到更新树中，作为所述待划分区域中副本版本最高的节点的子节点；将每个子区域分别作为待划分区域；

副本更新模块，用于按照更新树从上至下的顺序，依次令更新树中的每个节点根据其父节点上的副本进行更新。

6.根据权利要求5所述的装置，其特征在于，所述迭代构建单元进一步用于将待划分区域中除副本版本最高的节点以外的节点组成的区域平均划分为两个子区域。