CN113590535B - An efficient data migration method and device for deduplication storage system - Google Patents

Abstract

The present application provides an efficient data migration method and device for a deduplication storage system. The method includes: by receiving a data migration request, determining a corresponding source server, and determining a file to be migrated in the source server; Set the number of independent hash functions to determine the bit vector corresponding to each available server, and determine each candidate server based on the bit vector; Spatial overlap data and data volume, determine the space-saving index corresponding to each candidate server; based on the space-saving index, determine the target migration file and determine the target server in each candidate server, so as to migrate the target migration file to the target server, and update the bit vector and space-efficient indexes. Thus, additional space costs are reduced during the data migration process for efficient and highly adaptable data migration.

Description

An efficient data migration method and device for deduplication storage system

technical field

The present application relates to the technical field of data migration, and in particular, to an efficient data migration method and apparatus for a deduplication storage system.

Background technique

With the introduction of deduplication technology, traditional migration methods face serious challenges. First, deduplication creates a data-sharing dependency in the storage file; breaking this dependency during migration adds additional space overhead. Second, eliminating redundancy increases the risk of data being unavailable in the event of a server crash. Existing data migration methods cannot solve the above problems at one time.

SUMMARY OF THE INVENTION

In view of this, the purpose of the present application is to propose an efficient data migration method and apparatus for a deduplication storage system to solve the above technical problems.

For the above purposes, this application provides:

An efficient data migration method for a deduplication storage system, comprising:

Receive the data migration request, determine the source server corresponding to the data migration request, and then determine the files to be migrated in the source server;

Determine each available server, and then determine the bit vector corresponding to each available server based on the to-be-migrated file and the independent hash function of the preset number, and determine each candidate server corresponding to the data migration request based on the bit vector ;

Based on the file to be migrated, determine the file space overlapping data and the data amount of the shared partition block with the candidate servers, and then determine the space saving corresponding to each candidate server based on the file space overlapping data and the data amount index;

Based on the space-saving index, determine the target migration file in the to-be-migrated files and determine the target server in each candidate server, so as to migrate the target migration file to the target server, and update the target server Bit vector and space saving index corresponding to the origin server.

Optionally, the determining of the target migration file in the to-be-migrated files includes:

determining the occupied space corresponding to each of the to-be-migrated files based on the space-saving index;

Determine the average data access frequency undertaken by each of the files to be migrated;

A target migration file is determined according to the average data access frequency and the occupied space.

Optionally, determining the target migration file according to the average data access frequency and the occupied space includes:

determining the ratio of the average data access frequency to the occupied space;

In response to determining that the ratio is greater than the preset unit heat value, determining that the file to be migrated corresponding to the ratio is the target migration file.

Optionally, the determining of the target server in the candidate servers includes:

determining the similarity between the target migration file and each candidate server;

A candidate server corresponding to a similarity greater than a preset similarity threshold is determined as a target server.

Optionally, the determining of the target server in the candidate servers includes:

determining the target occupied space of the target migration file;

determining the target data volume of the shared partition block of the target migration file and each candidate server;

determining the average data access frequency undertaken by each copy of the target migration file;

Determine the difference between the target occupied space and each of the target data volumes, and then determine the ratio of the average data access frequency to each of the differences;

In response to determining that the ratio is greater than a preset value, determining that the candidate server corresponding to the ratio is the target server.

An efficient data migration device for a deduplication storage system, comprising:

a receiving unit, configured to receive a data migration request, determine a source server corresponding to the data migration request, and then determine a file to be migrated in the source server;

The candidate server determination unit is configured to determine each available server, and then determine a bit vector corresponding to each available server based on the to-be-migrated file and a preset number of independent hash functions, and determine the bit vector based on the bit vector Each candidate server corresponding to the data migration request;

The index determination unit is configured to determine, based on the to-be-migrated file, the file space overlapping data and the data amount of the shared partition block with each candidate server, and then determine the file space overlapping data and the data amount based on the file space overlapping data and the data amount. The space-saving index corresponding to each candidate server;

a migration unit configured to, based on the space-saving index, determine a target migration file in the to-be-migrated files and determine a target server in the candidate servers, so as to migrate the target migration file to the target server, And update the bit vector and space saving index corresponding to the target server and the source server.

Optionally, the migration unit is further configured to:

determining the occupied space corresponding to each of the to-be-migrated files based on the space-saving index;

Determine the average data access frequency undertaken by each of the files to be migrated;

A target migration file is determined according to the average data access frequency and the occupied space.

Optionally, the migration unit is further configured to:

determining the ratio of the average data access frequency to the occupied space;

In response to determining that the ratio is greater than the preset unit heat value, determining that the file to be migrated corresponding to the ratio is the target migration file.

Optionally, the migration unit is further configured to:

determining the similarity between the target migration file and each candidate server;

A candidate server corresponding to a similarity greater than a preset similarity threshold is determined as a target server.

Optionally, the migration unit is further configured to:

determining the target occupied space of the target migration file;

determining the target data volume of the shared partition block of the target migration file and each candidate server;

determining the average data access frequency undertaken by each copy of the target migration file;

Determine the difference between the target occupied space and each of the target data volumes, and then determine the ratio of the average data access frequency to each of the differences;

In response to determining that the ratio is greater than a preset value, determining that the candidate server corresponding to the ratio is the target server.

An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, when the processor executes the program, the efficient data migration for a deduplication storage system as described above is realized method.

A non-transitory computer-readable storage medium storing computer instructions for causing the computer to perform efficient data migration for a deduplication storage system as described above method.

It can be seen from the above that the efficient data migration method and device for a deduplication storage system provided by the present application determine the source server corresponding to the data migration request by receiving the data migration request, and then determine the source server in the source server. the files to be migrated; determine each available server, and then determine the bit vector corresponding to each available server based on the to-be-migrated file and a preset number of independent hash functions, and determine the data migration request based on the bit vector The corresponding candidate servers; determine the file space overlapped data and the data volume of the shared partition block with the candidate servers based on the files to be migrated, and then determine the data volume based on the file space overlap data and the data volume. The space-saving index corresponding to the candidate server; based on the space-saving index, determine the target migration file in the files to be migrated and determine the target server in each candidate server, so as to migrate the target migration file to the target server, and update the bit vector and space-saving index corresponding to the target server and the source server. In this way, additional space costs are reduced during the data migration process, and data migration is carried out with an efficient and adaptable data migration strategy.

Description of drawings

In order to more clearly illustrate the technical solutions in the present application or in the prior art, the following briefly introduces the accompanying drawings that are used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only the One or more embodiments are described, and for those of ordinary skill in the art, other drawings can also be obtained from these drawings without creative effort.

1 is a schematic flowchart of an efficient data migration method for a deduplication storage system according to an embodiment of this specification;

2 is a schematic flowchart of an efficient data migration method for a deduplication storage system according to another embodiment of the present specification;

3 is a schematic diagram of a bit vector of an efficient data migration method for a deduplication storage system according to another embodiment of the present specification;

4 is a structural block diagram of an efficient data migration apparatus for a deduplication storage system according to another embodiment of the present specification;

FIG. 5 is a schematic diagram of a hardware structure of an electronic device for an efficient data migration method for a deduplication storage system according to an embodiment of the present specification.

FIG. 6 is a schematic overview of Jingwei for an efficient data migration method for a deduplication storage system according to an embodiment of this specification.

到服务器

的数据迁移的示例。FIG. 7 is a slave server of the efficient data migration method for the deduplication storage system of this specification

to the server

example of data migration.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present application more clearly understood, the present application will be further described in detail below with reference to specific embodiments and accompanying drawings.

It should be noted that, unless otherwise defined, the technical or scientific terms used in one or more embodiments of the present specification should have the usual meanings understood by those with ordinary skill in the art to which this application belongs. The terms "first," "second," and similar terms used in one or more embodiments of this specification do not denote any order, quantity, or importance, but are merely used to distinguish the various components. "Comprises" or "comprising" and similar words mean that the elements or things appearing before the word encompass the elements or things recited after the word and their equivalents, but do not exclude other elements or things. Words like "connected" or "connected" are not limited to physical or mechanical connections, but may include electrical connections, whether direct or indirect. "Up", "Down", "Left", "Right", etc. are only used to represent the relative positional relationship, and when the absolute position of the described object changes, the relative positional relationship may also change accordingly.

FIG. 1 shows a flow 100 of an embodiment of an efficient data migration method for a deduplication storage system according to the present application. The efficient data migration method for a deduplication storage system in this embodiment includes the following steps:

Step S101: Receive a data migration request, determine a source server corresponding to the data migration request, and then determine a file to be migrated in the source server.

The execution body of the embodiment of the present application may be, for example, a server, and may receive a data migration request through a wired connection or a wireless connection.

Specifically, the data migration in this embodiment of the present application may include cutting data from one server to another or multiple servers, or may include copying data from one server to another or multiple servers. Data migration can be the cutting or copying of the entire file to another or more servers, or the cutting or copying of one or several data blocks in the file to another or more servers.

After receiving the data migration request, the execution subject can obtain the source server identifier carried in the data migration request, for example, the source server IP address, and then the execution subject can locate the source server corresponding to the data migration request according to the source server identifier. Then, the execution body may also obtain the identifier of the file to be migrated carried in the data migration request, which may be, for example, the file name of the file to be migrated or the storage address of the file to be migrated, etc. The specific content of the identifier of the file to be migrated is not specified in this embodiment of the present application. limited. Furthermore, the execution subject may locate the to-be-migrated file in the source server according to the to-be-migrated file identifier.

Step S102: Determine each available server, and then determine a bit vector corresponding to each available server based on the to-be-migrated file and a preset number of independent hash functions, and determine the corresponding data migration request based on the bit vector. each candidate server.

的时间复杂度来确定服务器是否包含这样的块，其中

是可用服务器中的块总数。采用Bloom Filter (BF)来表示每个可用服务器上的块。捕获了数据特征，并促进了从成对指纹检查到位向量（也称数据草图）上的成员关系查询的相似性检测。然后，判断一个服务器是否在一个文件中包含n块的时间复杂度可以降低为

，其中

表示使用的哈希函数的数量。示例的，如图3所示，假设可用服务器中的块集合

由三个分区块

、

和

组成，则BF代表

，其长度为d=19。该可用服务器对应的位向量中的所有d位最初设置为0。使用

，即使用两个独立哈希函数将每个可用服务器中的每个块映射到位向量中的

位置。这些命中的位置都会被设为1。从哈希函数派生的二进制字符串即为位向量，也即数据草图。每个可用服务器将维护一个位向量，具有相同的

函数和向量长度，以在块级别记录成员信息。根据位向量和

所使用的哈希函数，可以实现对任意文件中的任意块的成员查询。具体来说，当源服务器中的文件

试图从所有可用的候选服务器中选择它的最佳目标服务器时，它首先需要每个可用服务器的BF位向量，然后基于位向量确定所述数据迁移请求对应的各候选服务器。示例的，对于源服务器中的文件

中的任何块

，如果Bloom Filter中

哈希位置的任何位为0，则BF判断该块不属于可用服务器。否则，BF认为查询的块

属于可用服务器。In this embodiment, the execution body may determine multiple non-empty servers as available servers, and the available servers may receive migration files from overloaded servers (eg, source servers). In order to find a corresponding candidate server for each file to be migrated from the available servers, it is possible to compare the fingerprints of the blocks contained in the files to be migrated (for example, MD5 or SHA-1 can be used) and the fingerprints of the blocks stored by the available servers. For example, for a file containing n blocks, you can use

time complexity to determine whether the server contains such a block, where

is the total number of blocks in the available server. A Bloom Filter (BF) is used to represent the blocks on each available server. Data features are captured and facilitated similarity detection from pairwise fingerprint checks to membership queries on bit vectors (also known as data sketches). Then, the time complexity of judging whether a server contains n blocks in a file can be reduced to

,in

Indicates the number of hash functions used. Illustratively, as shown in Figure 3, assuming the set of blocks in the available server

consists of three partitions

,

and

composition, then BF stands for

, whose length is d=19. All d bits in the bit vector corresponding to this available server are initially set to 0. use

, i.e. using two independent hash functions to map each block from each available server into a bit vector

Location. The position of these hits will be set to 1. A binary string derived from a hash function is a bit vector, or data sketch. Each available server will maintain a bit vector with the same

Function and vector length to log member information at the block level. According to the bit vector and

The hash function used enables member queries to any block in any file. Specifically, when a file in the origin server

When trying to select its best target server from all available candidate servers, it first needs the BF bit vector of each available server, and then determines each candidate server corresponding to the data migration request based on the bit vector. Example, for files in origin server

any block in

, if Bloom Filter

If any bit in the hash position is 0, BF judges that the block does not belong to an available server. Otherwise, BF considers the queried block

is an available server.

Step S103: Determine the file space overlapping data and the data amount of the shared partition block with the candidate servers based on the file to be migrated, and then determine the corresponding candidate servers based on the file space overlapping data and the data amount. space efficient index.

Space-saving index, defined as the amount of storage resources saved when files are migrated to the target server. This is the deviation between the amount of data released from the source server and the space added on the migration target. Space-efficient data migration determines which files are migrated and which target servers they should be directed to, reducing additional space costs.

Specifically, Algorithm 1 to determine the space-saving index is as follows:

和所有目标候选

的基于BF的数据草图和文件集，其中

。为了导出迁移变量

和相应的迁移目标

，设计了一个空间效率高的索引（即节省空间索引）来激发迁移序列。该函数如算法1第9-13行所示。设

表示

和

之间共享块的数据量，可以从

的数据草图上

中块的基于bf的成员关系查询派生而来。然后，函数根据

与

的偏差，返回索引

，这反映了将文件

从

迁移到

所节省的空间资源。

的值是根据不包含

的草图计算的，反映了

中

和其他之间的空间重叠。Specifically, the above-mentioned Algorithm 1 is explained as follows: the input includes the origin server

and all target candidates

BF-based data sketches and filesets, where

. To export migration variables

and the corresponding migration target

, a space-efficient index (i.e., a space-saving index) is designed to motivate the migration sequence. The function is shown in Algorithm 1, lines 9-13. Assume

express

and

The amount of data shared between blocks, which can be changed from

on the data sketch

The middle block's bf-based membership query is derived. Then, the function according to

and

deviation, return index

, which reflects the

from

move to

space resources saved.

The value is based on not containing

The sketch of the calculated, reflects the

middle

and space overlap between others.

Step S104, based on the space-saving index, determine the target migration file in the to-be-migrated files and determine the target server in each candidate server, so as to migrate the target migration file to the target server, and update all the target migration files. bit vector and space-saving index corresponding to the target server and the source server.

来确定目标迁移文件（具体是通过最大

中的变量i来确定）及各候选服务器中的目标服务器（具体是通过最大

中的变量k确定），直到

中数据量的M百分比已经被迁移(如上述算法1的第3-5行所示)。每次迁移都会改变源服务器和目标服务器的存储状态。因此，在添加或释放文件的服务器上本地更新数据草图（即更新位向量）。此外，节省空间索引

也相应地在相关服务器上进行更新(如上述算法1的第6-8行所示)。In this embodiment, the space-saving index matched by each file server can be used to iteratively detect the maximum

to determine the target migration file (specifically by max.

the variable i in ) and the target server in each candidate server (specifically by the maximum

variable k in ), until

M percent of the amount of data in M has been migrated (as shown in lines 3-5 of Algorithm 1 above). Each migration changes the storage state of the source and target servers. Therefore, update the data sketch (i.e. update the bit vector) locally on the server where files are added or released. Also, space-efficient indexes

Updates are also made on the relevant servers accordingly (as shown in lines 6-8 of Algorithm 1 above).

As another implementation manner of the embodiment of the present application, the efficient data migration method for the deduplication storage system further includes migrating the files to be migrated to a single empty server.

中，有一组文件

有热度

。让

表示

中从文件划分的唯一块的集合。设

表示块

的大小，则服务器

的存储成本就是存储在其上的块的总大小，即

。注意，这个

函数为固定大小的块分块生成一个常量值，并为可变大小的块分块算法生成一个非常量值。设

表示包含关系，其中

表示块

包含在文件

中。不考虑一个文件在一个服务器上被多次复制的情况，因为它对访问分流没有影响，而只影响数据冗余。example, on an overloaded origin server

, there is a set of files

hot

. Let

express

A collection of unique blocks partitioned from the file. Assume

presentation block

size, the server

The storage cost of is the total size of the blocks stored on it, i.e.

. Note that this

The function generates a constant value for fixed-size chunking and a non-constant value for variable-size chunking algorithms. Assume

represents a containment relationship, where

presentation block

included in the file

middle. The case where a file is replicated multiple times on a server is not considered, because it has no effect on access distribution, but only on data redundancy.

可以定义为一个五元组

，其中

和

分别表示

的空间约束和服务约束，

表示源服务器中的存储文件集合。在这个初始状态下，在数据迁移之后，源服务器

中的每个候选迁移文件

将处于以下三种状态之一:The original state of the origin server before data migration

can be defined as a quintuple

,in

and

Respectively

space constraints and service constraints,

Represents a collection of storage files in the origin server. In this initial state, after data migration, the origin server

each candidate migration file in

will be in one of three states:

被迁移到目标服务器

，而源服务器占用的空间被释放。migration, i.e.

to be migrated to the target server

, and the space occupied by the origin server is released.

来表示这种状态，这样:Introduce the following boolean state variables

to represent this state, like this:

。

.

副本。这种情况通常出现在热门文件中，在这些文件中，数据访问需求可能会超过源服务器的容量。Replication, that is, the source server sends the target server

copy. This situation typically occurs with popular files, where data access requirements may exceed the capacity of the origin server.

来表示这种状态，这样:Introduce binary boolean state variable

to represent this state, like this:

。

.

在源服务器上没有被迁移或复制，这意味着

和

。unchanged, that is

has not been migrated or replicated on the source server, which means

and

.

，其中：Based on the file state indicated by the above Boolean variable, the deep association state of its partitions can also be expressed mathematically. Likewise, blocks can also be migrated, copied, or unchanged. These states can also be represented by defining boolean variables. To represent the text transition state of the block, a boolean variable is defined

,in:

。

.

时，块

已经从源服务器

迁移到目标服务器

。这种状态可能是由于它的从属文件

的迁移造成的，其中

。when

time, block

already from the origin server

Migrate to target server

. This state may be due to its dependent files

caused by the migration of

.

，这样:Further define a boolean variable

,so:

。

.

时，块

将同时出现在源服务器和目标服务器上。如果在迁移过程中复制了它的任何附属文件(包含

的文件)，

的状态将被标记为复制。此外，破坏两个文件(一个已迁移，另一个未更改)的数据共享依赖关系还会在共享部分附加块复制。请注意，

还与文件移动引起的额外空间成本有关，可以表示为

。如果

和

，这意味着

保持不变。when

time, block

will appear on both the source and target servers. If any of its accompanying files (including

document),

will be marked as duplicated. Also, breaking a data sharing dependency of two files (one migrated, the other unchanged) also appends a block copy in the shared section. caution,

is also related to the extra space cost caused by file movement, which can be expressed as

. if

and

,this means

constant.

中文件及其分区块之间的状态关系，并将其表示为以下三种情况之一。采用易于理解的例子来说明这些特殊的例子。can be analyzed

The state relationship between the file and its partitioned blocks in , and express it as one of three cases. These special examples are illustrated with easy-to-understand examples.

和

，例如图7中的初始存储状态（Innitial storage state）的文件

。其中，

中的5表示文件

的热度，

为文件

中的块，其他文件的表示方式类似，不再赘述。在这种情况下，文件中包含的所有块要么是未更改的(如块

)，要么是已复制的(如块

)，依赖于未更改文件和已迁移/复制文件之间的块共享依赖关系。A file remains on the origin server, i.e.

and

, such as the file in the Initial storage state in Figure 7

. in,

The 5 in the file means the file

the heat,

for file

The blocks in other files are represented in a similar manner, and will not be repeated here. In this case, all blocks contained in the file are either unchanged (as blocks

), or copied (such as a block

), relying on block sharing dependencies between unchanged files and migrated/copied files.

，例如图7中的初始存储状态（Innitialstorage state）的文件

。在这种情况下，文件中包含的所有块要么被迁移(如块

)，要么被复制(如块

)。A file is migrated to the target server, i.e.

, such as the initial storage state (Initialstorage state) file in Figure 7

. In this case, all blocks contained in the file are either migrated (as blocks

), or is copied (as a block

).

。在这种情况下，文件

所涉及的所有块，即

将被复制。此外，文件的访问需求将通过在

中使用分布参数

进行复制来分散。该参数由网络中中广泛使用的负载均衡器调整，负责根据服务器的实际负载均衡存储系统中的负载。文件

为初始存储状态容器中的文件。Copy a file so that both the source server and the target server have a copy, such as the file in the Initial storage state in Figure 7

. In this case, the file

all the blocks involved, i.e.

will be copied. In addition, file access requirements will be

using distribution parameters in

Make copies to disperse. This parameter is adjusted by the load balancer widely used in the network, which is responsible for balancing the load in the storage system according to the actual load of the server. document

File in the container for initial storage state.

With the boolean variables mentioned earlier for files and blocks, the migration problem for an empty target server can be formulated as follows.

被迁移时，即

，那么包含该块的所有文件将被迁移到目标服务器:when block

when migrated, i.e.

, then all files containing that block will be migrated to the target server:

（1）

(1)

被迁移时，即

，那么它所包含的所有块将被迁移或复制:when file

when migrated, i.e.

, then all blocks it contains will be migrated or copied:

（2）

(2)

在服务器

和

都被复制时，即

，那么它所涉及的所有块也应该被复制:when file

on the server

and

are copied, i.e.

, then all blocks it involves should also be copied:

（3）

(3)

，

，块的状态，即

，是互斥的:the status of the file, i.e.

,

, the state of the block, i.e.

, which are mutually exclusive:

，

（4）

,

(4)

，The amount of migrated data should meet the predefined migration percentage M,

,

（5）

(5)

The final space/serving overhead of the source and target servers should not exceed the corresponding capacity

（6）

(6)

（7）

(7)

（8）

(8)

（9）

(9)

和

分别是初始状态

的空间约束和服务约束。

和

分别是目标服务器的空间约束和服务约束。状态变量都是布尔值:

。in,

and

are the initial state

space constraints and service constraints.

and

They are the space constraints and service constraints of the target server, respectively. The state variables are all boolean values:

.

Standardize the goals of the Jingwei solution (that is, the data migration strategies corresponding to the efficient data migration method for the deduplication storage system in the embodiment of the present application), that is, in terms of space efficiency (minimizing extra space cost) and service adaptability (maximum To achieve an elegant trade-off between the requirements of the shared data), the principle is as follows:

（10）

(10)

可以调整以适应两种基本原理的不同优化趋势，

为文件

的热度。Among them, the parameter

can be adjusted to accommodate the different optimization trends of the two rationale,

for file

the heat.

Taking Equation 10 as the migration objective and Equations 1 to 9 as constraints, the problem can be expressed as an integer linear programming problem (ILP). It is known that the ILP problem is NP-hard, and there is no known efficient solution algorithm with polynomial time complexity. In particular, when variables are restricted to boolean assignments (0 or 1), then simply deciding whether the problem has an optimal solution is already NP-complete. However, commercial optimizers, such as CPLEX, lp_solve, and the Gurobi optimizer, can efficiently solve such problems for instances with hundreds of thousands of variables. Therefore, these highly optimized solvers are used to directly search for the optimal migration plan. However, this scenario may not be suitable for large storage systems, where it is not common for servers to connect to an empty state. Also, the limitation of migrating all files to one server may limit performance gains.

In this embodiment of the present application, by receiving a data migration request, the source server corresponding to the data migration request is determined, and then the files to be migrated in the source server are determined; each available server is determined, and then based on the to-be-migrated files and the preset number determine the bit vector corresponding to each available server, determine each candidate server corresponding to the data migration request based on the bit vector; determine the file space corresponding to each candidate server based on the to-be-migrated file The overlapping data and the data amount of the shared partition block, and then determine the space-saving index corresponding to each candidate server based on the file space overlapping data and the data amount; and determine the target server among the candidate servers, so as to migrate the target migration file to the target server, and update the bit vector and space-saving index corresponding to the target server and the source server. In this way, additional space costs are reduced during the data migration process, and data migration is carried out with an efficient and adaptable data migration strategy.

Continue to refer to FIG. 2 , which shows a flow 200 of another embodiment of an efficient data migration method for a deduplication storage system according to the present application. As shown in FIG. 2 , the efficient data migration method for the deduplication storage system in this embodiment may include the following steps:

Step S201: Receive a data migration request, determine a source server corresponding to the data migration request, and then determine a file to be migrated in the source server.

Step S202: Determine each available server, and then determine the bit vector corresponding to each available server based on the to-be-migrated file and a preset number of independent hash functions, and determine the corresponding data migration request based on the bit vector. each candidate server.

，其中

表示使用的哈希函数的数量，

表示任何候选服务器上的最大块数。需要注意的是，抽样技术将减少抽样比率的一个因子的时间复杂度。基于BF的数据草图的空间复杂度为

，其中

表示BF长度。A bit vector, that is, a data sketch in this embodiment of the present application. The time complexity of the BF-based data sketch is

,in

represents the number of hash functions used,

Indicates the maximum number of blocks on any candidate server. Note that the sampling technique will reduce the time complexity by a factor of the sampling rate. The space complexity of the BF-based data sketch is

,in

Indicates the BF length.

Step S203, determining the file space overlapping data and the data amount of the shared partition block with the candidate servers based on the files to be migrated, and then determining the corresponding candidate servers based on the file space overlapping data and the data amount. space efficient index.

，其中

表示任何文件中的最大块数。注意，在每次文件迁移之后，源服务器和目标服务器的存储状态都会部分更新。这不会增加算法的总体时间复杂度。另外，空间复杂度为

，其中

记录服务器概要，

记录节省空间的索引。The time complexity of space saving data migration is

,in

Represents the maximum number of blocks in any file. Note that the storage state of the source and target servers is partially updated after each file migration. This does not increase the overall time complexity of the algorithm. In addition, the space complexity is

,in

record server summary,

Record space-efficient indexes.

The principles of steps S201 to S203 are similar to the principles of steps S101 to S103, and are not repeated here.

。Step S204, determining the occupied space corresponding to each of the to-be-migrated files based on the space-saving index

.

的每个副本所承担的平均数据访问频率。Step S205: Determine the average data access frequency SDA(i) undertaken by each of the files to be migrated. SDA(i) is defined as a file

The average frequency of data access undertaken by each replica of .

，确定目标迁移文件。Step S206, according to the average data access frequency SDA(i) and the occupied space

, to determine the target migration file.

Specifically, the determining the target migration file according to the average data access frequency and the occupied space includes: determining a ratio of the average data access frequency to the occupied space; in response to determining that the ratio is greater than a preset unit The calorific value is determined, and the file to be migrated corresponding to the ratio is determined as the target migration file. The preset unit heat value reflects the quotient (quotient or ratio) between the amount of split data access (SDA) and the additional space required for copies of files to be migrated.

和共享分区块的数据量

来确定空间成本

。然后，执行主体可以根据平均数据访问频率SDA(i)和空间成本

的商（即比值）与预设值的大小，来确定该待迁移文件是否是目标迁移文件。如果，平均数据访问频率SDA(i)和空间成本

的商（即比值）大于预设值，则确定该待迁移文件为目标迁移文件。In addition, as another implementation manner of the embodiment of the present application, the execution body may also calculate the space cost according to the occupied space. Specifically, the execution body may determine the data amount of the partition block shared between the file to be migrated and each candidate server, and then may According to the space occupied

and the amount of data in the shared partition block

to determine the cost of space

. Then, the executive can access the data according to the average data access frequency SDA(i) and space cost

The quotient (that is, the ratio) and the preset value are used to determine whether the file to be migrated is the target migration file. If, average data access frequency SDA(i) and space cost

The quotient (that is, the ratio) is greater than the preset value, and the file to be migrated is determined as the target migration file.

The execution body can use the data replication algorithm based on heat perception to migrate the target migration file.

An example, the data replication algorithm based on heat perception is shown in Algorithm 2 below:

The interpretation of Algorithm 2 is as follows:

，

中得到

。

的值随后按降序排序，以构造服务器队列

(第3-4行)。排名在前面的服务器包含更多与

类似的内容。对于

中的每个服务器，计算SDA(i)和额外的空间成本-

。如果这两个参数之间的商大于

，那么文件

将被复制到

，即

中的第k个服务器(第5-9行)。在确定每个文件

的复制位置之后，进一步利用函数Heat Allocation

(第12-17行)来调整

中为每个服务器分配的数据访问量。此功能接管了负载调度程序的角色，后者根据所涉及服务器的可用功能来平衡服务负载。For any file stored in the origin server, from the function

,

get in

.

The values of are then sorted in descending order to construct the server queue

(Lines 3-4). The top-ranked servers contain more

similar content. for

For each server in , compute SDA(i) and additional space cost -

. If the quotient between these two parameters is greater than

, then the file

will be copied to

,Right now

The kth server in (Lines 5-9). in each file

After copying the location of , further use the function Heat Allocation

(lines 12-17) to adjust

The amount of data access allocated for each server in . This feature takes over the role of the load scheduler, which balances the service load based on the available capabilities of the servers involved.

Step S207: Determine the target server among the candidate servers, so as to migrate the target migration file to the target server, and update the bit vector and space-saving index corresponding to the target server and the source server.

)来指示文件复制的必要性。单位热值(

)这个指标反映了分割数据访问(SDA)量与副本所需额外空间之间的商。SDA(i)定义为文件

的每个副本所承担的平均数据访问频率。如果其商大于这个单位热值，则执行任何复制。这确保了在有限的额外空间成本下增加热文件的副本。After determining the target migration file and target server, the next step is to adjust the migration plan by using the file's heat. Overheated files should have multiple copies in the system for fault tolerance and better user experience. The examples of this application provide a unit calorific value (

) to indicate the need for file copying. unit calorific value (

) This metric reflects the quotient between the amount of split data access (SDA) and the additional space required for replicas. SDA(i) is defined as a file

The average frequency of data access undertaken by each replica of . If its quotient is greater than this unit heat value, then perform any replication. This ensures increased copies of hot files with limited additional space cost.

。在这里，

是基于给定文件

的共享数据量对目标服务器排序的结果。

和

的复杂性是由

中每个文件的最大迁移时间和最大复制时间造成的。空间复杂度为

。The time complexity of the heat-aware data replication algorithm is

. it's here,

is based on the given file

The result of sorting the target server by the amount of shared data.

and

The complexity is given by

due to the maximum migration time and maximum copy time per file in . The space complexity is

.

Specifically, as another implementation manner, the determining of the target server among the candidate servers includes:

位置和该位置的值，进而与各候选服务器对应的位向量的相应

位置和该位置的值进行相似度计算，具体可以是将位向量中目标迁移文件中的各个块的

位置对应的值转化为向量，通过余弦相似度算法进行与候选服务器的相应位置的值的相似度的计算，进而得出目标迁移文件中的各个块与各个候选服务器的相似度。将大于预设相似度阈值的相似度对应的候选服务器确定为目标服务器。The similarity between the target migration file and each candidate server is determined. Specifically, the execution subject can determine the relative value of each block in the target migration file in the bit vector corresponding to the source server to which it belongs.

position and the value of this position, and then the corresponding bit vector corresponding to each candidate server

The similarity calculation is performed between the position and the value of the position, which can be calculated by calculating the similarity of each block in the target migration file in the bit vector.

The value corresponding to the position is converted into a vector, and the cosine similarity algorithm is used to calculate the similarity with the value of the corresponding position of the candidate server, and then the similarity between each block in the target migration file and each candidate server is obtained. A candidate server corresponding to a similarity greater than a preset similarity threshold is determined as a target server.

Specifically, as another implementation manner, the determining of the target server among the candidate servers includes:

determining the target occupied space of the target migration file; determining the target data volume of the shared partition between the target migration file and each candidate server; determining the average data access frequency undertaken by each copy of the target migration file; Determine the difference between the target occupied space and each of the target data volumes, and then determine the ratio of the average data access frequency to each of the differences; in response to determining that the ratio is greater than a preset value, determine that the ratio corresponds to The candidate server is the target server. The target server can be multiple servers, and by migrating the target migration file to multiple servers, a reasonable general migration strategy can be utilized to maximize the use of the shared partition blocks on each target server to reconstruct the target migration file, thereby potentially Reduce total space cost.

In this embodiment of the present application, a space-saving migration algorithm is used to preferentially determine the migration file and its migration target at a lower cost of additional space. On this basis, a heat-aware data replication algorithm is proposed, which replicates hot files with limited extra space overhead, and realizes service adaptability. With similarity-aware file allocation, the space savings increases gradually with the migration percentage. When 45% of the data is migrated, about 41% of the occupied space can be freed from the origin server. Space reduction is achieved by detecting the similarity between the target migration file and the candidate server.

的RS-ratio，与SARA方法相比节省了约3.5倍的存储空间。Jingwei (as shown in Figure 6) is an efficient and adaptable data migration strategy, that is, the efficient data migration method for the deduplication storage system described in the various embodiments of this application. on a suitable server. This helps improve the space efficiency and business adaptability of deduplication storage systems. First, under the condition that only one empty migration target is allowed, a migration strategy based on ILP technology is designed. Extending this question further to a more general scenario where multiple non-null servers can be used for migration. Use efficient heuristics based on Bloom filters to solve general migration problems. Tracking-driven experiments in different scenarios show that the embodiment of the present application can significantly reduce the extra space cost in the migration process while increasing the number of hot file copies. In summary, Jingwei implements an efficient and adaptable migration strategy to build a large amount of RH with limited additional storage space. Specifically, Jingwei generates copies for four hot files (66.7%), which only increases the space utilization by 5.7% compared to Goseed. In addition, Jingwei has achieved

, which saves about 3.5 times the storage space compared to the SARA method.

Continuing to refer to FIG. 4 , as an implementation of the methods shown in the above figures, the present application provides an embodiment of an efficient data migration apparatus for a deduplication storage system, which is implemented with the method shown in FIG. 1 . Correspondingly, the device can be specifically applied to various electronic devices.

As shown in FIG. 4 , an efficient data migration apparatus 400 for a deduplication storage system in this embodiment includes: a receiving unit 401 , a candidate server determination unit 402 , an index determination unit 403 and a migration unit 404 .

The receiving unit 401 is configured to receive a data migration request, determine a source server corresponding to the data migration request, and then determine a file to be migrated in the source server;

The candidate server determination unit 402 is configured to determine each available server, and then determine the bit vector corresponding to each available server based on the to-be-migrated file and a preset number of independent hash functions, and determine all available servers based on the bit vector. each candidate server corresponding to the data migration request;

The index determination unit 403 is configured to determine, based on the to-be-migrated file, the file space overlapping data and the data amount of the shared partition block with each candidate server, and then determine the file space overlapping data and the data amount based on the file space overlapping data and the data amount. the space-saving index corresponding to each candidate server;

The migration unit 404 is configured to, based on the space-saving index, determine a target migration file in the files to be migrated and determine a target server in each candidate server, so as to migrate the target migration file to the target server , and update the bit vector and space-saving index corresponding to the target server and the source server.

In some embodiments, the migrating unit 404 is further configured to: determine the occupied space corresponding to each of the to-be-migrated files based on the space-saving index; determine the average data access frequency borne by each of the to-be-migrated files; The average data access frequency and the occupied space determine the target migration file.

In some embodiments, the migrating unit 404 is further configured to: determine a ratio of the average data access frequency to the occupied space; in response to determining that the ratio is greater than a preset unit heat value, determine the ratio corresponding to the ratio The file to be migrated is the target migration file.

In some embodiments, the migration unit 404 is further configured to: determine the similarity between the target migration file and each candidate server; and determine the candidate server corresponding to the similarity greater than a preset similarity threshold as the target server.

In some embodiments, the migration unit 404 is further configured to: determine the target occupied space of the target migration file; determine the target data volume of the shared partition between the target migration file and each candidate server; determine the target the average data access frequency undertaken by each copy of the migration file; determining the difference between the target occupied space and each of the target data volumes, and then determining the ratio of the average data access frequency to each of the differences; in response to It is determined that the ratio is greater than a preset value, and the candidate server corresponding to the ratio is determined to be the target server.

The technical carriers involved in the payment described in the embodiments of this specification may include, for example, Near Field Communication (NFC), WIFI, 3G/4G/5G, POS machine card swiping technology, two-dimensional code scanning technology, and barcode scanning technology , Bluetooth, infrared, short message (Short Message Service, SMS), multimedia message (MultimediaMessage Service, MMS) and so on.

It should be noted that the methods of one or more embodiments of this specification may be executed by a single device, such as a computer or a server. The method in this embodiment can also be applied in a distributed scenario, and is completed by the cooperation of multiple devices. In the case of such a distributed scenario, one device among the multiple devices may only execute one or more steps in the method of one or more embodiments of the present specification, and the multiple devices may perform operations on each other. interact to complete the described method.

The foregoing describes specific embodiments of the present specification. Other embodiments are within the scope of the appended claims. In some cases, the actions or steps recited in the claims can be performed in an order different from that in the embodiments and still achieve desirable results. Additionally, the processes depicted in the figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some embodiments, multitasking and parallel processing are also possible or may be advantageous.

For the convenience of description, when describing the above device, the functions are divided into various modules and described respectively. Of course, when implementing one or more embodiments of this specification, the functions of each module may be implemented in one or more software and/or hardware.

The apparatuses in the foregoing embodiments are used to implement the corresponding methods in the foregoing embodiments, and have the beneficial effects of the corresponding method embodiments, which will not be repeated here.

FIG. 5 shows a schematic diagram of a more specific hardware structure of an electronic device provided in this embodiment. The device may include: a processor 1010 , a memory 1020 , an input/output interface 1030 , a communication interface 1040 and a bus 1050 . The processor 1010 , the memory 1020 , the input/output interface 1030 and the communication interface 1040 realize the communication connection among each other within the device through the bus 1050 .

The processor 1010 may be implemented by a general-purpose CPU (Central Processing Unit, central processing unit), a microprocessor, an application specific integrated circuit (Application Specific Integrated Circuit, ASIC), or one or more integrated circuits, and is used to execute related program to implement the technical solutions provided by the embodiments of this specification.

The memory 1020 may be implemented in the form of a ROM (Read Only Memory, read only memory), a RAM (Random Access Memory, random access memory), a static storage device, a dynamic storage device, and the like. The memory 1020 may store an operating system and other application programs. When implementing the technical solutions provided by the embodiments of this specification through software or firmware, the relevant program codes are stored in the memory 1020 and invoked by the processor 1010 for execution.

The input/output interface 1030 is used to connect the input/output module to realize information input and output. The input/output/module can be configured in the device as a component (not shown in the figure), or can be externally connected to the device to provide corresponding functions. The input device may include a keyboard, a mouse, a touch screen, a microphone, various sensors, etc., and the output device may include a display, a speaker, a vibrator, an indicator light, and the like.

The communication interface 1040 is used to connect a communication module (not shown in the figure), so as to realize the communication interaction between the device and other devices. The communication module can implement communication through wired means (such as USB, network cable, etc.), or can implement communication through wireless means (such as mobile network, WIFI, Bluetooth, etc.).

The bus 1050 includes a path to transfer information between the various components of the device (eg, the processor 1010, the memory 1020, the input/output interface 1030, and the communication interface 1040).

It should be noted that although the above-mentioned device only shows the processor 1010, the memory 1020, the input/output interface 1030, the communication interface 1040 and the bus 1050, in the specific implementation process, the device may also include necessary components for normal operation. other components. In addition, those skilled in the art can understand that, the above-mentioned device may only include components necessary to implement the solutions of the embodiments of the present specification, rather than all the components shown in the figures.

The computer readable medium of this embodiment includes both permanent and non-permanent, removable and non-removable media and can be implemented by any method or technology for information storage. Information may be computer readable instructions, data structures, modules of programs, or other data. Examples of computer storage media include, but are not limited to, phase-change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read only memory (ROM), Electrically Erasable Programmable Read Only Memory (EEPROM), Flash Memory or other memory technology, Compact Disc Read Only Memory (CD-ROM), Digital Versatile Disc (DVD) or other optical storage, Magnetic tape cassettes, magnetic tape magnetic disk storage or other magnetic storage devices or any other non-transmission medium that can be used to store information that can be accessed by a computing device.

Those of ordinary skill in the art should understand that the discussion of any of the above embodiments is only exemplary, and is not intended to imply that the scope of the present application (including the claims) is limited to these examples; under the idea of the present application, the above embodiments or Technical features in different embodiments may also be combined, steps may be carried out in any order, and there are many other variations of the different aspects of one or more embodiments of this specification as described above, which are not in detail for the sake of brevity supply.

Additionally, in order to simplify illustration and discussion, and in order not to obscure the understanding of one or more embodiments of this specification, the figures provided may or may not be shown in connection with integrated circuit (IC) chips and other components. Well known power/ground connections. Furthermore, devices may be shown in block diagram form in order to avoid obscuring one or more embodiments of this description, and this also takes into account the fact that details regarding the implementation of such block diagram devices are highly dependent on the implementation of the invention (ie, these details should be well within the understanding of those skilled in the art) of the platform describing one or more embodiments. Where specific details (eg, circuits) are set forth to describe exemplary embodiments of the present application, it will be apparent to those skilled in the art that these specific details may be used without or with changes to the specific details One or more embodiments of this specification are implemented below. Accordingly, these descriptions are to be considered illustrative rather than restrictive.

Although the present application has been described in conjunction with specific embodiments thereof, many alternatives, modifications, and variations to these embodiments will be apparent to those of ordinary skill in the art from the foregoing description. For example, other memory architectures (eg, dynamic RAM (DRAM)) may use the discussed embodiments.

The embodiment or embodiments of this specification are intended to cover all such alternatives, modifications and variations that fall within the broad scope of the appended claims. Therefore, any omission, modification, equivalent replacement, improvement, etc. made within the spirit and principle of one or more embodiments of the present specification should be included within the protection scope of the present application.

Claims (10)

1. An efficient data migration method for a deduplication storage system, comprising:

receiving a data migration request, determining a source server corresponding to the data migration request, and further determining a file to be migrated in the source server;

determining each available server, further determining a bit vector corresponding to each available server based on the file to be migrated and a preset number of independent hash functions, and determining each candidate server corresponding to the data migration request based on the bit vector;

determining file space overlapping data and data volume of a shared partition block of each candidate server based on the file to be migrated, determining deviation of the file space overlapping data and the data volume, and further determining a space-saving index corresponding to each candidate server based on the deviation, wherein the space-saving index is the amount of storage resources saved when the file is migrated to a target server;

and determining a target migration file in the files to be migrated and a target server in each candidate server based on the space-saving index so as to migrate the target migration file to the target server and update the bit vectors and the space-saving index corresponding to the target server and the source server.

2. The method according to claim 1, wherein the determining a target migration file in the files to be migrated comprises:

determining the occupied space corresponding to each file to be migrated based on the space-saving index;

determining the average data access frequency borne by each file to be migrated;

and determining a target migration file according to the average data access frequency and the occupied space.

3. The method of claim 2, wherein determining a target migration file based on the average data access frequency and the footprint comprises:

determining a ratio of the average data access frequency to the footprint;

and in response to the fact that the ratio is larger than the preset unit heat value, determining that the file to be migrated corresponding to the ratio is the target migration file.

4. The method of claim 2, wherein determining the target server of the candidate servers comprises:

determining the similarity between the target migration file and each candidate server;

and determining the candidate server corresponding to the similarity greater than the preset similarity threshold as the target server.

5. The method of claim 2, wherein determining the target server of the candidate servers comprises:

determining a target occupation space of the target migration file;

determining the target data volume of the shared partition blocks of the target migration file and each candidate server;

determining an average data access frequency assumed by each copy of the target migration file;

determining a difference value between the target occupied space and each target data quantity, and further determining a ratio of the average data access frequency to each difference value;

and in response to determining that the ratio is greater than a preset value, determining that the candidate server corresponding to the ratio is the target server.

6. An efficient data migration apparatus for a deduplication storage system, comprising:

the receiving unit is configured to receive a data migration request, determine a source server corresponding to the data migration request, and further determine a file to be migrated in the source server;

a candidate server determining unit configured to determine each available server, determine a bit vector corresponding to each available server based on the file to be migrated and a preset number of independent hash functions, and determine each candidate server corresponding to the data migration request based on the bit vector;

the index determining unit is configured to determine file space overlapping data of each candidate server and data quantity of a shared partition block based on the file to be migrated, determine deviation of the file space overlapping data and the data quantity, and further determine a space-saving index corresponding to each candidate server based on the deviation, wherein the space-saving index is the amount of storage resources saved when the file is migrated to a target server;

and the migration unit is configured to determine a target migration file in the files to be migrated and a target server in each candidate server based on the space-saving index, so as to migrate the target migration file to the target server, and update the bit vectors and the space-saving index corresponding to the target server and the source server.

7. The apparatus of claim 6, wherein the migration unit is further configured to:

determining the occupied space corresponding to each file to be migrated based on the space-saving index;

determining the average data access frequency borne by each file to be migrated;

and determining a target migration file according to the average data access frequency and the occupied space.

8. The apparatus of claim 7, wherein the migration unit is further configured to:

determining a ratio of the average data access frequency to the footprint;

and in response to the fact that the ratio is larger than the preset unit heat value, determining that the file to be migrated corresponding to the ratio is the target migration file.

9. An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, characterized in that the processor implements the method according to any of claims 1 to 5 when executing the program.

10. A non-transitory computer-readable storage medium storing computer instructions for causing a computer to perform the method of any one of claims 1 to 5.

Images