CN104408111B - A kind of method and device of deleting duplicated data - Google Patents

Abstract

This application discloses a method and device for deleting duplicate data based on the Openstack Object Storage system. The proxy node includes a deduplication middleware module, and the storage node includes a deduplication service process module. The deduplication middleware module is constructed with a deduplication hash ring. The deduplication Each node of the hash ring is the root node of a red-black tree, and the deduplication service process module sends the fingerprint file to the deduplication middleware module; after the deduplication middleware module finds the root node of the red-black tree, it determines whether there are duplicate files; Keep a duplicate file in the storage node, delete other duplicate files, and save a redirection file pointing to the reserved duplicate file in the location where other duplicate files were originally stored; if there is no duplicate file, each fingerprint The value of the virtual node partition contained in the file and the MD5 value of the file content are inserted into the red-black tree child node. This application makes full use of the advantages of linear growth and horizontal expansion of the performance of the Openstack Object Storage system, and can easily expand nodes.

Description

A method and device for deleting duplicate data

technical field

The present application relates to Openstack Object Storage cloud storage technology, in particular to a method and device for deleting duplicate data based on the Openstack Object Storage system.

Background technique

Openstack Object Storage (swift) is an object storage sub-solution of the Openstack open source cloud computing project, which provides powerful scalability, redundancy and persistence. Its architecture is as follows: Figure 1 Openstack Object Storage framework.

As shown in Figure 1, Openstack Object Storage mainly consists of two types of nodes: proxy (proxy) nodes and storage (storage) nodes. The proxy node is responsible for receiving the client's request and communicating with the storage node. It locates and forwards the request to the storage node according to the object requested by the client. The storage node is mainly responsible for data storage, providing data security guarantees such as backup, fault tolerance, consistency, and automatic data migration to achieve data balance. All nodes in the cluster can be expanded horizontally, which includes two aspects, one is to expand data storage capacity through storage; the other is to linearly improve performance (such as QPS, throughput, etc.). The metadata of Swift data is completely evenly and randomly distributed, combined with the scalability of all its nodes, there is no single point of business in the architecture and design.

Based on Openstack Object Storage, it can easily provide cloud storage services and provide data access services. But for cloud storage, it is necessary to store a large amount of data. How to save storage costs while ensuring normal service is a problem that every cloud storage service provider is considering. Data deduplication is one of the solutions to this problem. way. For a large amount of data, there must be many situations where the names are different but the data content is the same. These data are either stored in different directories, or belong to different user accounts, etc. For this kind of data, cloud storage should only keep one copy, and the others only point to the reserved one, which greatly reduces the total amount of storage required for storage, improves the utilization rate of storage space, and saves storage costs.

For the data deduplication of Openstack Object Storage, there are currently related solutions, and you can refer to the detailed description in the paper "A Deduplication Campus-based Cloud Storage System Based on Swift".

In this paper, two components are mainly added to the original Openstack Object Storage system architecture to achieve data deduplication, one is the deduplication client and the other is the deduplication middleware. Since the existing technology adds a deduplication client, and all file access needs to access the deduplication client, the benefit of the horizontal expansion of Openstack Object Storage is lost: the linear increase in performance. Moreover, adding deduplication clients also forms a single point of the cluster. In addition, this solution hardly utilizes the existing mechanisms of Openstack Object Storage, does not combine its features, and only adds functions in the periphery, resulting in a complex structure of the deduplication system.

Contents of the invention

The present application provides a method and device for deleting duplicate data based on the Openstack Object Storage system, so as to solve the problem of deleting duplicate data in the prior art.

According to the first aspect of the embodiment of the present application, a method for deleting duplicate data based on the Openstack Object Storage system is provided, the Openstack Object Storage system includes a proxy node and a storage node; the proxy node includes a deduplication middleware module, and the storage The node includes a deduplication service process module, wherein the deduplication middleware module is constructed with a deduplication hash ring, and each node of the deduplication hash ring is a root node of a red-black tree, and the method includes steps:

The deduplication service process module scans the files stored under each file system partition, generates fingerprints corresponding to each file, and sends these fingerprints to the deduplication middleware module through the fingerprint file; the fingerprint file includes a The value of the virtual node partition and the MD5 value of each file content;

Described deduplication middleware module searches the corresponding red-black tree root node of each fingerprint according to each MD5 value to the result of n modulus, and wherein n is the node number that deduplication hash ring comprises;

After finding the root node of the red-black tree, judge whether the md5 value contained in each fingerprint already exists in the corresponding red-black tree sub-node, and for the case that the md5 value of any fingerprint exists in the red-black tree sub-node, further Determine whether the virtual node partition value stored in the red-black tree child node is the same as the virtual node partition value included in the fingerprint file where the fingerprint is located. If not, confirm that there is a duplicate file; keep a duplicate file in the storage node , delete other duplicate files, and save a redirection file pointing to the retained duplicate file in the location where other duplicate files were originally stored;

If there is no duplicate file, insert the virtual node partition value contained in each fingerprint file and the MD5 value of the file content into the corresponding child node of the red-black tree with each MD5 value as the key.

The second aspect of the embodiment of the present application provides another method for deleting duplicate data based on the Openstack Object Storage system, the Openstack Object Storage system includes a proxy node and a storage node; the proxy node includes a deduplication middleware module, and the storage The node includes a deduplication service process module, wherein the deduplication middleware module has a deduplication hash ring, and each node of the deduplication hash ring is a root node of a red-black tree, and the child nodes of the red-black tree store The value of virtual node partition, the MD5 value of file content; Described method comprises steps:

Receive the file storage request from the client;

Obtain the MD5 value of the file to be stored, and search for the root node of the red-black tree according to the MD5 value to the result of n modulus, where n is the number of nodes included in the deduplication hash ring;

After finding the root node of the red-black tree, judge whether the MD5 value exists in the child node in the red-black tree, if it exists in the child node, then confirm that there is a duplicate file, and store the position of the file to be stored Save a redirect file pointing to the duplicate file; if it does not exist in the child node, then confirm that there is no duplicate file, store the file to be stored at the location where the file to be stored is stored, and use the MD5 of the file to be stored The value is key and inserts the virtual node partition value and MD5 value of the file to be stored into the corresponding child node of the red-black tree.

The third aspect of the embodiment of the present application provides a device for deleting duplicate data based on the Openstack Object Storage system, the Openstack Object Storage system includes a proxy node and a storage node; the device includes:

The deduplication service process module located at the storage node is used to scan the files stored under each file system partition in the storage node, generate the corresponding fingerprint of each file, and send these fingerprints to the deduplication through the fingerprint file middleware module; and when there is a duplicate file, notify the storage node to keep a duplicate file in the storage node, delete other duplicate files, and save a copy pointing to the reserved duplicate file in the original storage position of other duplicate files Redirection file; the fingerprint file includes the value of a virtual node partition and the MD5 value of each file content;

The deduplication middleware module located at the proxy node is used to construct the deduplication hash ring. Each node of the deduplication hash ring is the root node of a red-black tree. According to the result of taking the modulus of n by each MD5 value, search for each fingerprint Corresponding red-black tree root node, where n is the number of nodes included in the deduplication hash ring; after finding the red-black tree root node, judge whether the md5 value contained in each fingerprint already exists in the corresponding red-black tree child node , for the case that the md5 value of any fingerprint exists in the red-black tree sub-node, further judge whether the value of the virtual node partition stored in the red-black tree sub-node is the same as the virtual node partition value included in the fingerprint file where the fingerprint is located , if different, then confirm that there is a duplicate file and inform the deduplication service process module; if there is no duplicate file, then use each MD5 value as a key to convert the value of the virtual node partition contained in each fingerprint file, the MD5 of the file content The value is inserted into the corresponding child node of the red-black tree.

The fourth aspect of the embodiment of the present application provides a device for deleting duplicate data based on the Openstack Object Storage system, the Openstack Object Storage system includes a proxy node and a storage node; the device includes,

The deduplication middleware module is used to build a deduplication hash ring, each node of the deduplication hash ring is a root node of a red-black tree, and the child nodes of the red-black tree preserve the value of the virtual node partition, The MD5 value of the file content; when the file storage request from the client is received, the MD5 value of the file to be stored is obtained, and the root node of the red-black tree is searched according to the result of modulo n by the MD5 value, where n is deduplication hash The number of nodes that the ring includes; after finding the root node of the red-black tree, judge whether the MD5 value exists in the child node in the red-black tree, if it exists in the child node, then confirm that there is a duplicate file, and notify The deduplication service process; if it does not exist in the child node, insert the value of the virtual node partition and the MD5 value of the file to be stored into the corresponding child node of the red-black tree with the MD5 value of the file to be stored as the key ;

The deduplication service process module is used to notify the storage node to save a redirection file pointing to the duplicate file at the location where the file to be stored is stored when there is a duplicate file; when there is no duplicate file, notify the storage to store The location of the file to be stored stores the file to be stored.

In this application, without introducing new nodes, combined with the mechanism provided by Openstack Object Storage itself, adding new functions inside the original nodes of the system can achieve the purpose of deduplicating data in the system, thereby solving the need in the prior art. The problem of complex system structure caused by additional components. At the same time, since the function of each proxy node in the system structure of this application is the same, and the node function of each storage node is also the same, so the horizontal expansion advantage of the linear growth of the performance of the OpenstackObject Storage system is fully utilized, and the nodes can be easily expanded, while in the cluster There is no single point either.

In the prior art, since the added deduplication client uses sqlite to store data, sqlite adopts a coarse-grained lock. When a connection wants to write to the database, all other connections are locked until the write connection ends its transaction. When the concurrency is high, the system performance is greatly reduced, and as the amount of data increases, the retrieval of a large amount of data by sqlite is also difficult. become a bottleneck. And the present invention realizes dynamic data maintenance by constructing a deduplication hash ring based on the hash ring and red-black tree in memory, in combination with the storage characteristics of Openstack Object Storage, without using sqlite to store static data, therefore, avoiding prior art In addition to the problems caused by storing static data in sqlite, it can also reduce the search time for duplicate data and improve system performance in the case of a large amount of data.

Description of drawings

Fig. 1 is the Openstack Object Storage system architecture diagram in the prior art;

Fig. 2 is the hardware structural diagram of Openstack Object Storage system in the embodiment of the present application

Fig. 3 is a schematic diagram of the Openstack Object Storage system architecture in the embodiment of the present application;

FIG. 4 is a schematic diagram of a deduplication hash ring in an embodiment of the present application;

Fig. 5 is the flowchart of constructing deduplication hash ring in the embodiment of the present application;

Fig. 6 is a schematic diagram of the signal direction of the system when constructing the hash ring in the embodiment of the present application;

Fig. 7 is the flow chart of client storage file in the embodiment of the present application;

Fig. 8 is a flow chart of deleting a file by the client in the embodiment of the present application;

FIG. 9 is a flow chart of a client reading a file in the embodiment of the present application.

detailed description

Reference will now be made in detail to the exemplary embodiments, examples of which are illustrated in the accompanying drawings. When the following description refers to the accompanying drawings, the same numerals in different drawings refer to the same or similar elements unless otherwise indicated. The implementations described in the following exemplary embodiments do not represent all implementations consistent with this application. Rather, they are merely examples of apparatuses and methods consistent with aspects of the present application as recited in the appended claims.

The terminology used in this application is for the purpose of describing particular embodiments only, and is not intended to limit the application. As used in this application and the appended claims, the singular forms "a", "the", and "the" are intended to include the plural forms as well, unless the context clearly dictates otherwise.

This application provides a set of solutions based on the Openstack Object Storage system to realize its deduplication function, so as to solve the problem of a large number of identical files in the cloud storage environment, reduce the total amount of system storage, improve storage utilization, and minimize the need for The impact of cluster read and write performance. In the following content of this application, the system architecture of the Openstack Object Storage system is first described, and then the construction process of the deduplication hash ring that plays a key role in identifying deduplication data in the system is described in detail, and then the use of the deduplication hash ring is described in detail. The process of data deduplication by the rehash ring is described in detail. Types of data deduplication include synchronous deduplication and asynchronous deduplication, and this application describes solutions for these two deduplication methods.

In order to facilitate the understanding of the technical solution described in this application, several basic concepts of the Openstack Object Storage system are first defined: there are three types of data stored in the Openstack Object Storage system, namely account, container, and object.

account: Indicates an account, and there are multiple containers under an account.

container: Indicates the container, and a container has multiple objects.

object: Indicates an object, which consists of file data, metadata, etc.

partition: The virtual node of the consistent hash algorithm in Openstack Object Storage. One actual node (storage) corresponds to several virtual nodes, and the virtual nodes are arranged by hash value in the hash space. For a file corresponding to an object, it can be mapped to the corresponding virtual node through the hash algorithm, and the virtual node can find the corresponding actual node through the mapping relationship. The value of the virtual node in this application is the serial number of the virtual node. After the virtual node is found through the serial number, the actual stoage node can be found through the mapping relationship between the virtual node and the actual node.

Description of the technical solution of the Openstack Object Storage system architecture in this application:

In this application, two components are added in the Openstack Object Storage system, namely the deduplication middleware module and the deduplication service process module shown in Figure 2, wherein the deduplication middleware module is installed on the proxy node, and the deduplication service process module Run on the storage node.

The Openstack Object Storage system of the present application is realized by means of multiple servers. The deduplication middleware can be implemented by means of a proxy server, and the deduplication service process can be implemented by means of a storage server. The deduplication middleware module and the deduplication service process module can be implemented by software, or by hardware or a combination of software and hardware. Taking software implementation as an example, as a device in a logical sense, it is formed by reading the corresponding computer program instructions in the non-volatile memory into the memory for operation by the processor of the device where it is located. From the hardware level, as shown in Figure 2, it is a hardware structure diagram of the deduplication service process and deduplication middleware in this application, except for the processor, network interface, memory and non-volatile memory shown in Figure 2 In addition to the memory, each server in the embodiment may further include other hardware, which is not shown in detail in FIG. 2 .

Fig. 3 is a logical architecture diagram of the Openstack Object Storage system in the embodiment. The deduplication middleware module builds and maintains deduplication hash rings (hash rings) and several red-black trees. Each node in the deduplication hash ring serves as the root node of each red-black tree. The child nodes of each red-black tree are used to store the key information of the stored object, through which each object stored in the entire system can be found. The key information of the stored object object here includes at least the sequence number of the virtual node where the object is located (that is, the partition value), the md5 value of the file content, and the fingerprint file name. FIG. 4 is a schematic diagram of a deduplication hash ring and a red-black tree.

The constructed deduplication hash ring is an array, and the number of elements in the array can be freely selected according to specific requirements, but as an embodiment, the number of virtual nodes is usually used as the number of array elements. In this application, position is used to indicate the array subscript, that is, the serial number of the array element. According to the position value, the array element, that is, the node of the deduplication hash ring, that is, the root node of the red-black tree can be located, so as to access the red-black tree. For how to calculate the value of position, please refer to the description below.

The following describes how to construct the deduplication hash ring and the red-black trees described in FIG. 4 with reference to FIG. 5 and FIG. 6 . In this embodiment, the deduplication hash ring and each red-black tree can be constructed when the system is initialized, and of course, it can also be constructed at other times according to requirements.

In this embodiment, the deduplication service configuration information can be written in object-server.conf, and the object-deduper field can be added. According to these configuration information, an array structure for deduplication hash ring can be constructed. Fig. 6 is a flow chart of constructing each node of the red-black tree.

The deduplication service process module scans each file stored under each file system partition (ie device), and generates a fingerprint file (step 701) that includes the fingerprint of each file (the fingerprint has the characteristic of being able to uniquely identify a file).

Combining with Figure 3, it can be known that this fingerprint file includes the file fingerprints corresponding to all objects under the device. Each fingerprint in the fingerprint file includes the MD5 value of the file content, accout, container, and object to which the file belongs. The MD5 value is a 128-bit feature code obtained by mathematically transforming the original information according to the public MD5 algorithm. The information contained in the fingerprint file includes the fingerprint of the file, the value of the partition, the IP address of the storage, and the path of the device. Through these information, you can find the file corresponding to the specific object: you can find the corresponding stoarge node according to the partition value, find the corresponding device according to the storage IP address and device path, and then locate the specific file according to the MD5 value in the fingerprint .

The deduplication service process module collects the fingerprint files of each device and sends them to the deduplication middleware module (step 702). In this embodiment, as shown in FIG. 5 , the fingerprint file is sent to the deduplication middleware module through HTTP.

The deduplication middleware module analyzes the fingerprint file, and obtains the fingerprint information of each file in the fingerprint file (step 703). Each red-black tree is constructed according to the md5 value in each fingerprint in the fingerprint file. The specific method of constructing the red-black tree is as follows: firstly, the MD5 value of each file content is moduloed by the number of array elements constituting the deduplication hash ring to obtain the position value, and the root node of the red-black tree is located according to each position value The position r of (step 704);

Then, each MD5 value is further used as a Key, and the key information of each object is respectively added to the child node corresponding to the root node of the corresponding red-black tree (step 705). Please refer to Figure 4, there are n+1 nodes in this figure, that is, the number of array elements is n+1; if the MD5 value corresponding to an object is m, then the root node position of the red-black tree corresponding to the object is r It is: r=m%(n+1). It is not difficult to see that the root node position of the red-black tree corresponding to any object is in the range of 0~n.

The partition value and MD5 value in the object's fingerprint information can be used to determine whether there is duplicate data. The file name of the fingerprint file can find the corresponding fingerprint file, and the account stored in the duplicate file data can be judged according to the account information of the fingerprint stored in the fingerprint file. And as an embodiment, for the preservation of key information in the red-black tree child node in step 705, can adopt following mode: the IP address of storage and the path of file in this storage have been preserved in the file name of fingerprint file, and fingerprint file uses IP_device, the IP in this file name is the same as the IP of the storage where the mounted file system partition is located, and the device in the file name is the same as the path of the mounted file system partition. The fingerprint file can be saved in a specific storage location in the proxy, so in a preferred mode, only the file name, partition value and MD5 of the file content need to be saved in the red-black tree node.

As shown in Figure 5, in a preferred embodiment of the present application, using the characteristics of the horizontal scalability of the Openstack Object Storage system, the deduplication hash ring can be distributed on multiple proxies, and each of the proxy nodes maintains one of the Deduplication hash ring, thus forming a distributed deduplication hash ring. The specific method is as follows: According to the range option of the position value in the configuration file, the entire deduplication hash ring can be split into several parts, and each proxy node is only responsible for storing part of the deduplication hash ring, and each proxy node can pass HTTP Perform query operations. Figure 5 is a distributed deduplication hash ring divided into two parts: a hash ring with n nodes is divided into two deduplication hash rings and stored on different proxies, one of which stores a position ranging from 0 to (n/2 -1) an array; another array that stores positions ranging from n/2 to n.

In a preferred embodiment, the deduplication middleware module exists in the form of a WSGI plug-in, and the function of the plug-in can be turned on and off through a configuration file. Due to the attributes of WSGI itself, the plug-in can preprocess all received HTTP Request, that is to say, the data write request will first reach the removal middleware for preprocessing before storage, thus providing the possibility to prevent repeated data writing. In one embodiment, the following configuration content can be added to the deduplication middleware module through a configuration file (the configuration file is named by proxy-server.conf below):

1) The number of array elements, as an embodiment, can be the same as the number of partitions by default, which is more convenient for configuration;

2) The position range is between 0 and the total number of array elements -1.

In addition to this information, other information can be configured as needed. For example, when the distributed structure of the distributed hash ring described above is adopted, the configuration content can also include the IP addresses of other proxies configured with deduplication hash rings, and The position range configured on the proxy.

In one embodiment, under the distributed hash ring architecture, after reading a piece of data in the fingerprint file, and obtaining the position value by moduloing the node number of the deduplication hash ring according to MD5, it is also necessary to determine whether the position belongs to the proxy node. If it does not belong to the proxy node, the proxy node where the fingerprint file is located is obtained through the configuration file, and the fingerprint file is passed to the corresponding proxy node through the IP address information.

In this embodiment, a distributed architecture is used, and the process of constructing, maintaining and reconstructing the hash ring by each proxy can be processed in parallel. Through the following analysis of the time responsibility and space complexity of each proxy to construct the deduplication hash ring, it can be seen that the distributed architecture greatly reduces the pressure on a single server, and reduces the deduplication hash ring reconstruction when the server fails. time.

Time complexity of deduplication hash ring:

Time complexity = O(1)+O(logN), the average value of N: N=the total number of stored objects in the system/number of positions

Deduplication hash ring space complexity:

Assume that the file size stored in each red-black tree root node is about 65 bytes, of which MD5 is 16 bytes, ip is no more than 15 bytes, the path of the mounted file system partition is about 9 bytes, and the partition is 4 bytes. The red-black tree structure occupies 25 bytes, the three pointers parent, left, and right occupy 24 bytes, and the color occupies 1 byte.

Calculate the memory required for 100 million files in 65bytes: 65*100000000≈6.4G

The method of deduplicating data by using deduplication hash ring and red-black tree is described in detail below.

First, the process of synchronous deduplication (synchronous deduplication) is explained. Synchronous deduplication means that when a file is uploaded, if the file already exists in the system, the file will not be written, and the file upload will be returned directly, realizing the second-level upload function. Synchronous deduplication is triggered when the client sends a related file upload request.

As shown in Figure 7, when the deduplication middleware module receives a request from a client to upload a file, it starts to search for the root node position of the red-black tree according to the MD5 value of the file content. In a preferred example, the MD5 value is carried In the message of the file storage request, as an embodiment, it may be the etag in the header of the HTTP message.

Find the red-black tree root node position (step 801) according to the MD5 value of described file content, and by red-black tree root node and use MD5 value as key to find whether there is the identical child node of MD5 value in the described red-black tree (step 801) 802), if yes, confirm that there is a duplicate file, and store a redirection file pointing to the duplicate file at the location where the file to be stored is stored. If not, confirm that there is no duplicate file, store the file to be stored in the location where the file to be stored is stored, and use the MD5 value of the file to be stored as the key to insert the value of the virtual node partition and the MD5 value of the file to be stored into the red In the corresponding child node of the black tree. (storing the file to be stored in the position of storing the file to be stored can be writing the file to be uploaded into the corresponding account in the storage, and the corresponding account in the sotrage for writing the uploaded file into the corresponding account has been taught in the prior art, and will not be described here described in more detail).

It should be noted that this application uses the open interface provided by the Openstack Object Storage system for users to realize the related operations of redirecting files. This open interface allows adding your own file read and write interface file DiskFile, which can be added by adding this interface. file to generate and maintain redirection files. The deduplication function is added. When it is only necessary to read, if it is found that it is a redirected file, read the content of the redirected file. According to the partition, account, container, and object of the content of the redirected file, the actual file content is obtained and returned.

Steps 8031 to 8034 in the figure describe the process of generating a redirection file for steps 803 to 804 in an application example, and writing the redirection file to storage, specifically including:

dedupe_account is an account generated by the deduplication service process module when the Openstack Object Storage system is initialized (of course, the account can also be generated at other times as needed), which is used to store file content. The deduplication middleware module finds the child node of the red-black tree where the duplicate data is located according to the md5 value of the content of the file to be uploaded, uses the file name of the fingerprint file stored in the child node to find the corresponding fingerprint file, and then corresponds to the fingerprint, according to the account name stored in the fingerprint, it can be judged whether the aforementioned file content to be uploaded is stored in the account of dedupe_account (step 8031); if the aforementioned file to be uploaded has been stored in the account of dedupe_account, then generate the redirection file Afterwards, the redirection file is written into the account corresponding to the MD5 value in the storage, and the number of the current redirection files is recorded in dedupe_account (step 8034); that is, the counter refer in the figure adds 1.

If the file content to be stored is not in the dedupe_account, then the file content corresponding to the MD5 value is written into the dedupe_account (step 8032), and the redirection file is written into the storage by the MD5 value after generating the redirection file corresponding account, and record the current number of redirected files in dedupe_account (step 8033); that is, the counter refer in the figure is increased by 1, indicating that the reference is increased by 1. The fingerprint of the file in the updated dedupe_account can be sent to the deduplication middleware by the deduplication service process in real time, or can be sent to the deduplication middleware according to the period when the deduplication service process collects fingerprint files.

As shown in Figure 8, when receiving the client's delete file (DELETE) request, judge whether the deleted file is redirected file (step 1001), if not, then carry out normal delete operation (step 1007); If Yes, then read the redirection file (step 1002), delete the redirection file (step 1005), and update the current number of the redirection file (step 1003) (the counter representing the number of references of depute_account in the figure refer minus 1). If the updated current number of redirected files is zero (step 1004), delete the file content in the dedupe_account, and delete the red-black tree subnode corresponding to the dedupe_account (step 1006).

It can be seen that when the file is stored, only one real file content can be kept on the dedupe_account, and other accounts only need to store a redirected file when storing the file content, so that the purpose of synchronous deduplication can be achieved.

Fig. 9 is a flow chart of reading files from the Openstack Object Storage system. When receiving the file reading (GET operation) request, judge whether the read file is a redirection file (step 901), if yes, then read the redirection file, and obtain the content (account, container) of the redirection file , object information) (step 902), search the corresponding ring file according to these information, obtain the file content from dedupe_account (step 903), and return the file content to the proxy server (step 904). Ring is the most important component of Swift, which is used to record the mapping relationship between storage objects and physical locations. When it comes to querying information such as account and Object, it is necessary to query the information of the Ring file. How to search according to the ring file can be implemented according to the prior art.

The following is the process of asynchronous deduplication (asynchronous deduplication):

Asynchronous deduplication occurs when deduplication hash rings and red-black trees are constructed. Asynchronous deduplication can also be started when adding or deleting devices, service restarts and other events.

During asynchronous deduplication, the deduplication middleware module determines whether there is duplicate data through the key information stored in each child node of the red-black tree. The determination method is: if the MD5 values are the same and the partition values are different, it means that the two objects Duplicate data is stored; if the MD5 value is the same and the partition value is the same, there may be duplicate data. It may be that the same user has deliberately stored two identical files, one of which is a copy. At this time, no special processing is required; If the MD5 values are different, it is determined that there is no duplicate data. The method of how to use the constructed deduplication hash ring to remove duplicate data in this application will be described below in conjunction with FIG. 7 .

When the deduplication service process module collects the fingerprint file, the data is transmitted to the deduplication middleware module through HTTP. For each fingerprint in the fingerprint file, the deduplication middleware module searches for the child nodes of the red-black tree according to the MD5 value contained in the fingerprint. If the corresponding child node is found, it judges whether it is consistent with the partition value recorded in the fingerprint file. The partition values recorded in the above child nodes are the same. If they are different, it is confirmed that there is currently duplicate data. Find the corresponding fingerprint according to the md5 value of the file content in the fingerprint file. According to the account name stored in the fingerprint, it can be judged whether the account storing the duplicate data is dedupe_account. If the duplicate data is not stored in dedupe_account, then the node with the same MD5 value The duplicate data stored in the account is moved into the dedupe_account, and the redirection file pointing to the duplicate data is stored in the account, and the number of the current redirection files is recorded. In one embodiment, after the file content is written into the dedupe_account, the fingerprint information corresponding to the updated file content can be sent to the deduplication middleware module through the fingerprint file to update the information stored in each child node of the red-black tree.

Other embodiments of the present application will be readily apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. This application is intended to cover any modification, use or adaptation of the application, these modifications, uses or adaptations follow the general principles of the application and include common knowledge or conventional technical means in the technical field not disclosed in the application . The specification and examples are to be considered exemplary only, with a true scope and spirit of the application indicated by the following claims.

It should be understood that the present application is not limited to the precise constructions which have been described above and shown in the accompanying drawings, and various modifications and changes may be made without departing from the scope thereof. The scope of the application is limited only by the appended claims.

Claims (10)

1. a method for deleting duplicate data based on the Openstack Object Storage system, the OpenstackObject Storage system includes a proxy node and a storage node; it is characterized in that the proxy node includes a deduplication middleware module, and the storage node includes a deduplication service process module, wherein the deduplication middleware module is constructed with a deduplication hash ring, and each node of the deduplication hash ring is a root node of a red-black tree, and the method comprises steps: The deduplication service process module scans the files stored under each file system partition, generates fingerprints corresponding to each file, and sends these fingerprints to the deduplication middleware module through the fingerprint file; the fingerprint file includes a The value of the virtual node partition and the MD5 value of each file content; Described deduplication middleware module searches the corresponding red-black tree root node of each fingerprint according to each MD5 value to the result of n modulus, and wherein n is the node number that deduplication hash ring comprises; After finding the root node of the red-black tree, judge whether the md5 value contained in each fingerprint already exists in the corresponding red-black tree sub-node, and for the case that the md5 value of any fingerprint exists in the red-black tree sub-node, further Determine whether the virtual node partition value stored in the red-black tree child node is the same as the virtual node partition value included in the fingerprint file where the fingerprint is located. If not, confirm that there is a duplicate file; keep a duplicate file in the storage node , delete other duplicate files, and save a redirection file pointing to the retained duplicate file in the location where other duplicate files were originally stored; If there is no duplicate file, insert the virtual node partition value contained in each fingerprint file and the MD5 value of the file content into the corresponding child node of the red-black tree with each MD5 value as the key. 2. The method according to claim 1, characterized in that, keeping a duplicate file in the storage node is specifically: saving a duplicate file in depute_account; said dedupe_account is constructed for storing duplicate data account. 3. A method for deleting duplicate data based on the Openstack Object Storage system, the OpenstackObject Storage system includes a proxy node and a storage node; it is characterized in that the proxy node includes a deduplication middleware module, and the storage node includes a deduplication service process module, wherein the deduplication middleware module is constructed with a deduplication hash ring, each node of the deduplication hash ring is the root node of a red-black tree, and the child nodes of the red-black tree preserve the value of the virtual node partition, The MD5 value of file content; Described method comprises steps: Receive the file storage request from the client; Obtain the MD5 value of the file to be stored, and search for the root node of the red-black tree according to the MD5 value to the result of n modulus, where n is the number of nodes included in the deduplication hash ring; After finding the root node of the red-black tree, judge whether the MD5 value exists in the child node in the red-black tree, if it exists in the child node, then confirm that there is a duplicate file, and store the position of the file to be stored Save a redirect file pointing to the duplicate file; if it does not exist in the child node, then confirm that there is no duplicate file, store the file to be stored at the location where the file to be stored is stored, and use the MD5 of the file to be stored The value is key and inserts the virtual node partition value and MD5 value of the file to be stored into the corresponding child node of the red-black tree. 4. The method according to claim 3, further comprising: when receiving a request to delete a file, if the deleted file is a redirection file, then deleting the redirection file; if not If there is a redirection file, delete the file content in the storage node, and delete the red-black tree sub-node corresponding to the fingerprint of the file. 5. a device based on the Openstack Object Storage system to delete duplicate data, the OpenstackObject Storage system includes a proxy node and a storage node; it is characterized in that the device includes: The deduplication service process module located at the storage node is used to scan the files stored under each file system partition in the storage node, generate the corresponding fingerprint of each file, and send these fingerprints to the deduplication through the fingerprint file middleware module; and when there is a duplicate file, notify the storage node to keep a duplicate file in the storage node, delete other duplicate files, and save a copy pointing to the reserved duplicate file in the original storage position of other duplicate files Redirection file; the fingerprint file includes the value of a virtual node partition and the MD5 value of each file content; The deduplication middleware module located at the proxy node is used to construct the deduplication hash ring. Each node of the deduplication hash ring is the root node of a red-black tree. According to the result of taking the modulus of n by each MD5 value, search for each fingerprint Corresponding red-black tree root node, where n is the number of nodes included in the deduplication hash ring; after finding the red-black tree root node, judge whether the md5 value contained in each fingerprint already exists in the corresponding red-black tree child node , for the case that the md5 value of any fingerprint exists in the red-black tree sub-node, further judge whether the value of the virtual node partition stored in the red-black tree sub-node is the same as the virtual node partition value included in the fingerprint file where the fingerprint is located , if different, then confirm that there is a duplicate file and inform the deduplication service process module; if there is no duplicate file, then use each MD5 value as a key to convert the value of the virtual node partition contained in each fingerprint file, the MD5 of the file content The value is inserted into the corresponding child node of the red-black tree. 6. The device according to claim 5, wherein the deduplication service process module notifies the storage node to keep a duplicate file in the storage node, specifically: saving a duplicate file in depute_account; The dedupe_account is an account constructed for storing duplicate data. 7. A device for deleting duplicate data based on the Openstack Object Storage system, the OpenstackObject Storage system includes a proxy node and a storage node; it is characterized in that the device includes, Deduplication middleware module, used to construct deduplication hash ring, each node of this deduplication hash ring is the root node of a red-black tree, and the child node of described red-black tree preserves the value of virtual node partition, file content MD5 value; when receiving the file storage request from the client, obtain the MD5 value of the file to be stored, and search for the root node of the red-black tree according to the result of modulo n by the MD5 value, where n is the deduplication hash ring including After finding the root node of the red-black tree, judge whether the MD5 value exists in the child node in the red-black tree, if it exists in the child node, then confirm that there is a duplicate file, and notify the Deduplication service process; if it does not exist in the child node, insert the value of the virtual node partition and the MD5 value of the file to be stored into the corresponding child node of the red-black tree with the MD5 value of the file to be stored; The deduplication service process module is used to notify the storage node to save a redirection file pointing to the duplicate file at the location where the file to be stored is stored when there is a duplicate file; when there is no duplicate file, notify the storage to store the file to be stored The location of the file stores the file to be stored. 8. The device according to claim 7, wherein when receiving a request to delete a file, the deduplication service process module is also used to notify the storage node to delete the deleted file if the deleted file is a redirected file. If there is no redirection file, notify the storage node to delete the file content, and notify the deduplication middleware module to delete the red-black tree sub-node corresponding to the fingerprint of the file. 9. The device according to claim 7, wherein the deduplication hash ring is split into multiple rings according to predetermined rules and stored in multiple proxy nodes respectively. 10. The device according to claim 7, wherein the deduplication middleware module is installed on the proxy node in the form of WSGI.