DATA BACKUP METHOD OF DISTRIBUTED FILE SYSTEM

• US 20150199243A1
• Filed: 01/09/2015
• Published: 07/16/2015
• Est. Priority Date: 01/11/2014
• Status: Abandoned Application

• Current Assignee: Research Institute of Tsinghua University in Shenzhen (Tsinghua University)
• Original Assignee: Research Institute of Tsinghua University in Shenzhen (Tsinghua University)
• Inventors: WU, Yongwei, CHEN, Kang, ZHENG, Weimin, LI, Zhenqiang
• Application Number:
  US14/593,358
• Publication Number:
  US 20150199243A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency

Abstract

A data backup method of a distributed file system is provided. The method is based on a comparison of a source file system and a target file system. Metadata of the target file system is compared with metadata of the source file system. The method includes: synchronizing target metadata of a target file according to source metadata of a source file, generating a file checksum list; determining whether a first target block is consistent with a first source block, obtaining and sending a first updated file checksum list to a first data node; determining whether a first chunk is consistent with a first target chunk, generating a first difference list, sending the first difference list and the first updated file checksum list to a first corresponding target data node; creating a temporary block, writing data in the temporary block, replacing the first corresponding target block with the temporary block.

Claims

1. A data backup method of a distributed file system, applied in a source file system and a target file system, comprising:

a metadata synchronization step of obtaining by a synchronization control node a copy list according to a source path in a data backup request input from a client, synchronizing target metadata of a target file in the target file system according to source metadata of a source file in the copy list, and generating a file checksum list corresponding to the source file;

a file difference analysis step of comparing by the synchronization control node a checksum of a first source block in the source file with a checksum of a first target block in the target file, determining whether the first source block is consistent with the first target block to obtain a first determining result, and updating information of the first source block and a first source data node corresponding to the first source block in the file checksum list according to the first determining result to obtain a first updated file checksum list, and sending the first updated file checksum list to a first data node, wherein the first data node is the first source data node or a first target data node corresponding to the first target block, and the first data node corresponds to a first block which is the first source block or the first target block;

a block difference analysis step of receiving by the first data node the first updated file checksum list, comparing a checksum of a first chunk in the first block with a checksum of a first target chunk in a first corresponding target block, determining whether the first chunk is consistent with the first target chunk to obtain a second determining result, generating a first difference list according to the second determining result, and sending the first difference list and the first updated file checksum list to a first corresponding target data node corresponding to the first corresponding target block; and

a data backup step of creating a temporary block by the first corresponding target data node, and writing data in the temporary block according to the first difference list and replacing the first corresponding target block with the temporary block.

2. The method according to claim 1, wherein the copy list comprises a plurality of rows of information of a plurality of source files inside the source path, and a row of information comprises a filename of the source file, a size of the source file and a file path of the source file;

and the source file comprises a plurality of first source blocks having a plurality of first source block checksums respectively and corresponding to a plurality of first source data nodes respectively; and

the target file comprises a plurality of target blocks having a plurality of first target block checksums respectively and corresponding to a plurality of first target data nodes respectively; and

the file checksum list comprises a plurality of records;

a record comprises an No. of a source block of the plurality of first source blocks, an ID of the source block, a checksum of the source block, an ID of a source data node corresponding to the source block, an ID of a corresponding target block corresponding to the source block, a checksum of the corresponding target block, an ID of a corresponding target data node corresponding to the corresponding target block and a mark bit indicating whether the corresponding target block is a new created target block; and

the first updated file checksum list comprises a plurality of first updated records;

an updated record corresponding to the record comprises the No. of the source block, an ID of a block, a checksum of the block, an ID of a data node corresponding to the block, the ID of a corresponding target block, the checksum of the corresponding target block, the ID of the corresponding target data node and the mark bit;

wherein the block is one of the plurality of first source blocks or one of the plurality of target blocks.

3. The method according to claim 2, wherein the metadata synchronization step comprises:

A1;

obtaining the copy list, establishing a thread pool and allocating the source file to a first thread in the thread pool according to the copy list;

B1;

obtaining by the first thread the source metadata, obtaining the plurality of first source block checksums from the plurality of first source data nodes according to the source metadata;

C1;

obtaining by the first thread the target metadata from a target name node in the target file system, comparing a size of the source file with a size of the target file to obtain a first comparing result, requesting the target name node to create or delete the plurality of target blocks according to the first comparing result to ensure that the target file is equal to the source file in size, and updating the target metadata to obtain updated target metadata;

D1;

obtaining by the first thread the updated target metadata, and obtaining the plurality of first target block checksums from the plurality of first target data nodes according to the updated target metadata;

E1;

generating the file checksum list by the first thread according to the source metadata, the updated target metadata, the plurality of first source block checksums and the plurality of first target block checksums.

4. The method according to claim 2, wherein the file difference analysis step comprises:

A2;

comparing a second source block checksum of a second source block of the plurality of first source blocks with the plurality of first target block checksums and determining whether there is a second target block consistent with the second source block;

B2;

if there is the second target block consistent with the second source block, replacing an ID of the second source block in the file checksum list with an ID of the second target block, and replacing an ID of a second source data node in the file checksum list with an ID of a second target data node to obtain a second updated file checksum list, else going step A2, wherein the second source data node is corresponding to the second source block and the second target data node is corresponding to the second target block;

C2;

determining whether all of the plurality of first source block checksums are compared with the plurality of first target block checksums, if yes, going step D2, else going step A2;

D2;

traversing the second updated file checksum list, deleting a second updated record in which an ID of a block is the same as an ID of a corresponding target block and an ID of a data node is the same as an ID of a corresponding target data node to obtain the first updated file checksum list;

E2;

sending the plurality of first updated records respectively to the plurality of data nodes.

5. The method according to claim 2, wherein the block difference analysis step comprises:

A3;

receiving by the first data node a first updated record, and sending the first updated record and a first request for a target block checksum list to the first corresponding target data node;

B3;

dividing by the first data node the first block into a plurality of chunks with a same size, and calculating a plurality of chunk checksums of the plurality of chunks by using a digest algorithm;

C3;

receiving by the first corresponding target data node the first updated record and the first request, and dividing the first corresponding target block into a plurality of target chunks with a same size and calculating a plurality of first target chunk checksums of the plurality of target chunks to generate the target block checksum list, and sending the target block checksum list to the first data node, wherein the target block checksum list comprises;

Nos. of the plurality of target chunks, IDs of the plurality of target chunks and the plurality of first target chunk checksums;

D3;

receiving by the first data node the target block checksum list and creating a second difference list, wherein the second difference list comprises;

Nos. of the plurality of chunks, IDs of the plurality of chunks and a plurality of pieces of difference information;

E3;

comparing a second chunk checksum of a second chunk of the plurality of chunks with the plurality of first target chunk checksums and determining whether there is a second target chunk consistent with the second chunk;

F3;

if there is the second target chunk consistent with the second chunk, replacing an ID of the second chunk in the second difference list with an ID of the second target chunk to obtain the first difference list;

G3;

if there is no target chunk consistent with the second chunk, replacing the ID of the second chunk with NULL and writing a content of the second chunk into a second piece of difference information corresponding to the second chunk to obtain the first difference list;

H3;

determining whether all of the plurality of chunk checksums are compared with the plurality of first target chunk checksums, if yes, going step I3, else going step E3;

I3;

sending the first difference list to the first corresponding target data node.

6. The method according to claim 2, the data backup step comprises:

A4;

receiving by the first corresponding target data node the first difference list, and creating the temporary block whose size is the same as that of the first corresponding target block;

B4;

determining whether an ID of a third chunk in the first difference list is NULL;

C4;

if the ID of the third chunk is not NULL, obtaining a content of the third chunk, and writing the content of the third chunk into the temporary block, else obtaining a third piece of difference information corresponding to the third chunk from the first difference list and writing the third piece of difference information into the temporary block;

D4;

determining whether all of chunks in the first difference list are determined, if yes, going step E4, else going step B4;

E4;

replacing the first corresponding target block with the temporary block.

7. The method according to claim 4, wherein step A2 comprises:

a1;

calculating a second source hash value of the second source block checksum and a plurality of target hash values of the plurality of first target block checksums by using a first hash function;

a2;

comparing the second source hash value and the plurality of target hash values;

a3;

if there is no target hash value the same as the second source hash value, there is no target block consistent with the second source block;

a4;

if there are a plurality of second target block checksums whose hash values are the same as the second source hash value, comparing the second source block checksum with the plurality of second target block checksums;

a5;

if there is the second target block whose checksum is the same as the second source block checksum, the second target block is consistent with the second source block.

8. The method according to claim 5, wherein the block difference analysis step further comprises:

determining whether the first corresponding target block is a new created target block according to the mark bit;

if yes, writing contents of the plurality of chunks into the plurality of pieces of difference information, replacing the IDs of the plurality of chunks in the second difference list with NULL to obtain the first difference list, and going step I3;

if no, going step E3.

9. The method according to claim 5, wherein step E3 comprises:

e1;

calculating a second chunk hash value of the second chunk checksum and a plurality of target chunk hash values of the plurality of first target chunk checksums by using a second hash function;

e2;

comparing the second chunk hash value and the plurality of target chunk hash values;

e3;

if there is no target chunk hash value the same as the second chunk hash value, there is no target chunk consistent with the second chunk;

e4;

if there are a plurality of second target chunk checksums whose hash values are the same as the second chunk hash value, comparing the second chunk checksum with the plurality of second target chunk checksums;

e5;

if there is the second target chunk whose checksum is the same as the second chunk checksum, the second target chunk is consistent with the second chunk.

10. The method according to claim 4, wherein if there is the second target block consistent with the second source block, the file difference analysis step further comprises:

storing the ID of the second source block, the ID of the second source data node and a No. of the second source block in a source backup table, wherein the source backup table comprises;

Nos. of a plurality of second source blocks, IDs of the plurality of second source blocks and IDs of a plurality of second source data nodes corresponding to the plurality of second source blocks.

11. The method according to claim 10, wherein step E2 comprises:

e11;

selecting a plurality of second updated records in which a plurality of data nodes are target data nodes from the first updated file checksum list according to the Nos. of the plurality of second source blocks;

e12;

establishing a plurality of directed edges to construct a directed acyclic graph according to the plurality of second updated records;

e13;

selecting a first directed edge corresponding to a vertex with zero out degree from the directed acyclic graph, sending a third updated record corresponding to the first directed edge and deleting the first directed edge from the directed acyclic graph, and repeating step el3 until there is no directed edge in the directed acyclic graph;

e14;

sending a plurality of fourth updated records in which Nos. of a plurality of blocks are not in the source backup table.

12. The method according to claim 11, wherein establishing a plurality of directed edges to construct a directed acyclic graph comprises:

defining IDs of a plurality of first data nodes and IDs of a plurality of first corresponding target data nodes in the plurality of second updated records as vertexes, defining edges from the IDs of the plurality of first data nodes to the IDs of the plurality of first corresponding target data nodes as directed edges;

replacing the IDs of the plurality of first data nodes respectively with the IDs of the plurality of second source data nodes and replacing IDs of a plurality of first blocks corresponding to the plurality of first data nodes respectively with the IDs of the plurality of second source blocks, and deleting from the source backup table a plurality of rows corresponding to the plurality of second source blocks, if the directed acyclic graph is formed to be a loop according to the plurality of directed edges.