CN105511801A - Data storage method and apparatus - Google Patents

Abstract

The invention discloses a data storage method and apparatus. The method comprises the following steps of acquiring to-be-stored data, determining a rack corresponding to the data in storage space via Hash calculation, acquiring a data copy corresponding to the data and determining a storage area of a data node of the data copy on the rack via Hash calculation, and storing the data copy in the storage area, wherein the storage space is annular storage space; the data node is corresponding to a plurality of virtual data nodes; and the storage space charged by the plurality of virtual data nodes are evenly divided into a plurality of storage areas. By the use of the data storage method and apparatus, data can be evenly distributed and quickly stored; and system processing performance can be improved.

Description

Method and device for data storage

technical field

The present invention relates to the field of data storage, in particular to a data storage method and device.

Background technique

Distributed cluster storage is a key technology for big data storage management, among which HDFS (Hadoop Distributed File System, Hadoop Distributed File System) has become an effective method to solve high-efficiency storage applications of big data due to its high transmission rate and high fault tolerance.

An existing implementation method is to describe the optimal cache capacity design problem as an integer programming problem, but the existing HDFS data placement strategy does not take into account the data balance problem and system execution performance while selecting data reliability improvement, resulting in Data storage is slow and system processing performance is low.

For the above problems, no effective solution has been proposed yet.

Contents of the invention

The embodiments of the present invention provide a data storage method and device, which can quickly complete data storage while ensuring balanced distribution of data, and improve system processing performance.

According to an aspect of an embodiment of the present invention, a data storage method is provided, including: obtaining data to be stored; determining the rack corresponding to the data in the storage space through a hash operation; obtaining the data corresponding to the data Copy, and determine the storage area corresponding to the data node on the rack of the data copy through a hash operation; wherein, the storage space is a ring storage space, the data node corresponds to a plurality of virtual data nodes, and the The storage space responsible for multiple virtual data nodes is composed of multiple equally divided storage areas; the data copy is stored in the storage areas.

Optionally, before acquiring the data to be stored, the method further includes: performing an equal division operation on the storage space to obtain a plurality of equally divided storage areas.

Optionally, before acquiring the data copy corresponding to the data, the method further includes: determining whether the rack is abnormal; the acquiring the data copy corresponding to the data includes: determining that the rack is normal , obtain the data copy corresponding to the data; when it is determined that the rack is abnormal, search for the next rack in the storage space in a clockwise order.

Optionally, before storing the data copy in the storage area, the method further includes: determining the storage area corresponding to the data node of the data copy on the rack through a hash operation Afterwards, determine whether the data node on the rack is abnormal; when it is determined that the data node is abnormal, search the next rack in the storage space in a clockwise order; when it is determined that the data node is normal, determine the Whether the storage area corresponding to the data node is sufficient; the storing the data copy in the storage area includes: when determining that the storage area is sufficient, storing the data copy in the storage area; When the storage area is insufficient, search the next data node on the rack in the storage space in a clockwise order.

Optionally, after storing the data copies in the storage area, the method further includes: determining whether all data copies have been stored; Search for the next rack in the storage space.

According to another aspect of the embodiments of the present invention, there is also provided a data storage device, including: an acquisition unit, configured to acquire data to be stored; a processing unit, configured to determine the data in the storage space through a hash operation The corresponding rack, and obtain the data copy corresponding to the data, and determine the storage area corresponding to the data node on the rack of the data copy through a hash operation; wherein, the storage space is a ring storage space, The data node corresponds to a plurality of virtual data nodes, and the storage space responsible for the plurality of virtual data nodes is composed of a plurality of equally divided storage areas; a storage unit is configured to store the data copy in the storage area.

Optionally, the processing unit is further configured to perform an equal division operation on the storage space to obtain a plurality of equally divided storage areas before acquiring the data to be stored.

Optionally, the device further includes: a first judging unit, configured to determine whether the rack is abnormal before acquiring the data copy corresponding to the data: the processing unit, configured to When the judging unit determines that the rack is normal, obtain the data copy corresponding to the data; when the first judging unit determines that the rack is abnormal, search for the next rack in the storage space in a clockwise order.

Optionally, the device further includes: a second judging unit, configured to, before storing the data copy in the storage area, determine through a hash operation that the data copy is on the rack After the storage area corresponding to the data node of the data node, determine whether the data node on the rack is abnormal; the processing unit is configured to, when the second judging unit determines that the data node is abnormal, perform a clockwise sequence on the Search the next rack in the storage space; the second judging unit is also used to determine whether the storage area corresponding to the data node is sufficient when determining that the data node is normal; When the judging unit determines that the storage area is sufficient, store the copy of the data in the storage area; the processing unit is configured to, when the second judging unit determines that the storage area is not sufficient, in a clockwise order Searching for the next data node on the rack in the storage space.

Optionally, the device further includes: a third judging unit, after storing the data copy in the storage area, determines whether all data copies have been stored; the processing unit is configured to determine whether all data copies After the storage is completed, search for the next rack in the storage space in a clockwise order.

In the embodiment of the present invention, the data to be stored is obtained; the rack corresponding to the data is determined in the storage space through a hash operation; the data copy corresponding to the data is obtained, and the data on the rack of the internal data copy is determined through a hash operation The storage area corresponding to the node; among them, the storage space is a ring storage space, the data node corresponds to multiple virtual nodes, and the storage space responsible for multiple virtual nodes is composed of multiple equally divided storage areas; the data copy is stored in the storage area, In this way, the present invention completes data storage through a hash algorithm and introduces virtual data nodes and equally divided storage areas, so that data storage can be quickly completed while ensuring balanced distribution of data, and the technical problem of improving system processing performance is achieved.

Description of drawings

The accompanying drawings described here are used to provide a further understanding of the present invention and constitute a part of the application. The schematic embodiments of the present invention and their descriptions are used to explain the present invention and do not constitute improper limitations to the present invention. In the attached picture:

Fig. 1 is a schematic flow chart of an optional data storage method according to an embodiment of the present invention;

Fig. 2 is a schematic diagram of an optional rack migration according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of an optional rack backup distribution according to an embodiment of the present invention;

Fig. 4 is a comparison diagram of running time of an optional data connection query according to an embodiment of the present invention;

FIG. 5 is a comparison diagram of an optional actual backup distribution and running time according to an embodiment of the present invention;

FIG. 6 is an optional diagram of backup distribution of data nodes after adjustment according to an embodiment of the present invention;

FIG. 7 is a schematic flowchart of another optional data storage method according to an embodiment of the present invention;

FIG. 8 is a schematic flowchart of an optional data storage method according to an embodiment of the present invention;

FIG. 9 is a schematic structural diagram of an optional data storage device according to an embodiment of the present invention;

FIG. 10 is a schematic structural diagram of another optional data storage device according to an embodiment of the present invention;

Fig. 11 is a schematic structural diagram of a third optional data storage device according to an embodiment of the present invention.

detailed description

In order to enable those skilled in the art to better understand the solutions of the present invention, the following will clearly and completely describe the technical solutions in the embodiments of the present invention in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments are only It is an embodiment of a part of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts shall fall within the protection scope of the present invention.

It should be noted that the terms "first" and "second" in the description and claims of the present invention and the above drawings are used to distinguish similar objects, but not necessarily used to describe a specific sequence or sequence. It is to be understood that the data so used are interchangeable under appropriate circumstances such that the embodiments of the invention described herein can be practiced in sequences other than those illustrated or described herein. Furthermore, the terms "comprising" and "having", as well as any variations thereof, are intended to cover a non-exclusive inclusion, for example, a process, method, system, product or device comprising a sequence of steps or elements is not necessarily limited to the expressly listed instead, may include other steps or elements not explicitly listed or inherent to the process, method, product or apparatus.

Fig. 1 is a method for data storage according to an embodiment of the present invention. As shown in Fig. 1, the execution subject of the embodiment of the present invention is a data storage device, and the method includes the following steps:

Step S101, acquiring data to be stored.

Step S102, determine the rack corresponding to the data in the storage space through a hash operation.

Step S103. Obtain the data copy corresponding to the data, and determine the storage area corresponding to the data node on the rack for the data copy through a hash operation.

Wherein, the storage space is a ring-shaped storage space, and the data node corresponds to a plurality of virtual data nodes, and the storage space responsible for the plurality of virtual data nodes is composed of a plurality of evenly divided storage areas.

Further, before the data to be stored is acquired, the storage space is divided equally to obtain multiple equally divided storage areas.

Wherein, the ring-shaped storage space is divided equally. At this time, all virtual nodes in the storage space include multiple equally divided storage areas, that is, the storage space in charge of each virtual node is composed of multiple equally divided areas. After the data node is mapped to the storage space through the hash operation, address the first equally divided area where the data node is located. This is the mapping position of the node. If the position conflicts, use the method of linear detection and hashing to continue clockwise Find the next evenly divided area until the storage space that each data node is responsible for consists of multiple equally divided areas.

Optionally, before obtaining the data copy corresponding to the data, determine whether the rack is abnormal; when it is determined that the rack is normal, obtain the data copy corresponding to the data; when it is determined that the rack is abnormal, in a clockwise order Search for the next rack within the storage space.

Optionally, before storing the data copy in the storage area, after determining the storage area corresponding to the data node on the rack for the data copy through a hash operation, determine whether the data node on the rack Abnormal; when it is determined that the data node is abnormal, search the next rack in the storage space in a clockwise order; when it is determined that the data node is normal, determine whether the storage area corresponding to the data node is sufficient; when it is determined that the storage area is sufficient , store the data copy in the storage area; when it is determined that the storage area is not sufficient, search for the next data node on the rack in the storage space in a clockwise order.

Step S104, storing the data copy in the storage area.

In this step, the data can be grouped and stored according to the divided storage space. When machines are added or deleted in the cluster, the consistent hash algorithm rules of clockwise migration can reduce the data while maintaining monotonicity. The amount of migration and the pressure on the server.

Further, after the data copy is stored in the storage area, it is determined whether all the data copies have been stored; when it is determined that all the data copies have not been stored, the next rack is searched clockwise in the storage space.

It should be noted that, in the embodiment of the present invention, for multiple data copies, the hash operation function is used to map and store n racks, and the clockwise direction is set to sequentially select two different The data node stores two copies, and selects a suitable data node in each sequentially connected rack of n-k racks to store the remaining copies. The data nodes of the rack are searched in the annular storage space through two hash operation mapping methods, and the specific process is shown in Figure 1.

For the addition and deletion of data nodes, the embodiment of the present invention can use consistent hash operation mapping to obtain new data nodes on the ring storage space according to the clockwise migration rule. At this time, the data occurs in the equally divided areas in a single rack When the mapping changes, the stored data may maintain the original storage location or have a small-scale migration; the stored data backup is continuously stored on the adjacent racks in the ring space according to the consistent hash operation mapping. When the cluster adds a rack or encounters a failure When a rack exits, the data in the adjacent racks needs to be migrated. When the rack enters the ring storage space, the migration status of several racks related to backup data before and after the rack change is shown in Figure 2. It can be seen from Figure 2 that using this algorithm to deal with the distributed cluster data storage problem can Inheriting the consistent hash algorithm can avoid the advantages of increasing the pressure on the server due to massive data migration while maintaining monotonicity.

The following is a verification description for the above method;

Build an HDFS storage cluster in the local area network, use Ubuntu 14.04 as the operating system, install Hadoop cloud platform computing, Intel Xeon 4-core CPU, 8G memory, 1TB SATA hard disk, and Gigabit network card configuration for the connection of storage cluster data nodes, simulating 6 Racks (6, 8, 12, 9, 8, 10 data nodes per rack).

The obtained data is shown in Table 1. The performance of the data nodes is the same. The data nodes need to be configured according to the actual storage cluster conditions. The combination of the network card physical address and the LAN IP is used as the unique identification location, and the mapping function uses the Chord algorithm of consistent hashing. , the equal storage space size is set to 64MB, the uploaded data size is 50GB, and about 1200 storage areas are stored.

document Number of data copies File size take up space Number of records User Info 3 1MB 3MB 2130 make an announcement 3 16 GB 45GB 512k environmental data 3 640MB 1900MB 9680

Table 1

Use the above settings to complete the multi-rack connection test parallel performance trend experiment, and verify the relationship between multi-rack parallel connection and backup allocation ratio. Here, it is considered that each data node is evenly distributed and there is little difference in individual performance. In theory, the data nodes in each rack have an equal chance of being allocated data backup according to the consistent hash algorithm. It can be seen from Figure 3 that according to the data load balancing theory, the data node backup of the rack in the actual situation should be similar to the theoretical situation, which can ensure the balanced storage of data between the racks. Figure 4 shows the comparison of running time. The data is connected and queried using the consistent hash optimization algorithm and the reduced-side connection query processing algorithm under the standard hadoop platform. The comparison shows that the mapping task is completed locally than from the mapping side. The time spent on data transfer to the reduction side is significantly shortened, and the startup overhead of data transfer is reduced.

Use the data upload experiment to upload the data set from the local file system to HDFS, verify the relationship between the optimized storage strategy and the data upload speed, and understand the data balance performance between data nodes by considering the distribution of backup numbers in the rack data nodes. Theoretically, it is considered that the data nodes are distributed in a uniform area, and the performance difference is not large, then the data nodes will have an equal chance to be allocated to the backup obtained by the rack. As shown in Figure 5, it can be seen that with the increase of data scale, the final communication time of data transmission can basically remain stable (about 51.5s and the fluctuation amplitude is not large), and the probability of each data node in the rack to obtain backup can be maintained. It fluctuates around the theoretical value (10%), indicating that the data nodes in the rack can ensure load balancing when they are assigned backups.

Verify the monotonicity and load balancing characteristics of the consistent hashing algorithm according to the change trend of the data migration and backup numbers. Add and delete data nodes to the cluster. Figure 6 shows the actual value of the rack after mapping and adjustment to obtain backups. , it can be seen that the newly added data nodes have a higher probability of obtaining backups. The reason for this is that the data needs to re-plan the probability of data nodes obtaining backups during the process of completing the mapping, but the oscillation amplitude is small within a reasonable range ( 1.8%), and did not affect the overall load balancing within the rack; this occurred because of the additional time required to select data nodes. Figure 6 shows the comparison of the running time of the data operation using the consistent hash algorithm and the random distribution Hadoop platform strategy. It can be seen that as the data scale increases, the running time increases slightly, and the data processing efficiency is high, indicating that this The design algorithm can meet the processing of large-scale data.

Fig. 7 is a data storage method provided by the embodiment of the present invention. As shown in Fig. 7, the execution subject of the embodiment of the present invention is a data storage device, and the method includes:

Step S701, acquiring data to be stored.

Step S702, determine the rack corresponding to the data in the storage space through a hash operation.

Wherein, the storage space is a ring-shaped storage space, and the data node corresponds to a plurality of virtual data nodes, and the storage space responsible for the plurality of virtual data nodes is composed of a plurality of evenly divided storage areas.

Step S703, determining whether the rack is abnormal;

When it is determined that the rack is normal, execute steps S704 to S706;

When it is determined that the rack is abnormal, step S710 is performed.

Step S704, acquiring a data copy corresponding to the data.

Step S705. Determine the storage area corresponding to the data node on the rack for the data copy through a hash operation.

Step S706, determining whether the data node on the rack is abnormal.

When it is determined that the data nodes on the rack are normal, perform step S707;

When it is determined that the data node on the rack is abnormal, step S710 is executed.

Step S707, determine whether the storage area corresponding to the data node is sufficient.

When it is determined that the storage area corresponding to the data node is sufficient, step S708 is executed.

When it is determined that the storage area corresponding to the data node is not sufficient, step S711 is executed.

Step S708, storing the data copy in the storage area.

Step S700. Determine whether all data copies have been stored.

When it is determined that the storage of all data copies is completed, the data storage ends.

When it is determined that all data copies have not been stored, step S710 is executed.

Step S710, search for the next rack in the storage space in a clockwise order and continue to execute step S703.

Step S711 , search the next data node on the rack in the storage space in a clockwise order and continue to execute step S707 .

In this way, the present invention completes data storage through a hash algorithm and introduces virtual data nodes and equally divided storage areas, so that data storage can be quickly completed while ensuring balanced distribution of data, and the technical problem of improving system processing performance is achieved.

It should be noted that, for the above method embodiments, for the sake of simple description, they are expressed as a series of action combinations, but those skilled in the art should know that the present invention is not limited by the described action sequence, because according to In the present invention, certain steps may be performed in other orders or simultaneously. Secondly, those skilled in the art should also know that the embodiments described in the specification belong to preferred embodiments, and the actions and modules involved are not necessarily required by the present invention.

FIG. 8 is a data storage device provided by an embodiment of the present invention. As shown in FIG. 8, the device includes;

The obtaining unit 801 is configured to obtain data to be stored.

The processing unit 802 is configured to determine the rack corresponding to the data in the storage space through a hash operation, obtain a data copy corresponding to the data, and determine the data copy corresponding to the data node on the rack through a hash operation. storage area.

Wherein, the storage space is a ring-shaped storage space, and the data node corresponds to a plurality of virtual data nodes, and the storage space responsible for the plurality of virtual data nodes is composed of a plurality of evenly divided storage areas.

The storage unit 803 is configured to store the data copy in the storage area.

Optionally, the processing unit 802 is further configured to, before acquiring the data to be stored, perform an equal division operation on the storage space to obtain multiple equally divided storage areas.

Optionally, as shown in Figure 9, the device also includes:

The first judging unit 804 is configured to determine whether the rack is abnormal before acquiring the data copy corresponding to the data;

The processing unit 801 is configured to obtain the data copy corresponding to the data when the first judging unit 804 determines that the rack is normal; Search for the next rack within the space.

Optionally, as shown in Figure 10, the device also includes:

The second judging unit 805 is configured to, before storing the data copy in the storage area, after determining the storage area corresponding to the data node on the rack for the data copy through a hash operation, determine the Whether the data node of is abnormal;

The processing unit 802 is configured to search the next rack in the storage space in a clockwise order when the second judging unit 805 determines that the data node is abnormal;

The second judging unit 805 is further configured to determine whether the storage area corresponding to the data node is sufficient when determining that the data node is normal;

The storage unit 803 is configured to store the data copy in the storage area when the second judging unit 805 determines that the storage area is sufficient;

The processing unit 802 is configured to, when the second judging unit 805 determines that the storage area is insufficient, search the storage space for a next data node on the rack in a clockwise order.

Optionally, as shown in Figure 11, the device also includes:

The third judging unit 806, after storing the data copy in the storage area, determines whether all the data copies have been stored;

The processing unit 802 is configured to search the next rack in the storage space in a clockwise order after determining that all data copies have not been stored.

Using the data storage device provided by the embodiment of the present invention, the data storage is completed through the hash algorithm and the introduction of virtual data nodes and equal storage areas, so that the data storage can be quickly completed while ensuring the balanced distribution of data, and the system processing performance can be improved. technical problem.

It should be noted that those skilled in the art can clearly understand that for the convenience and brevity of the description, the specific working process and description of the data storage device described above can refer to the corresponding process in the foregoing method embodiment. This will not be repeated here.

The serial numbers of the above embodiments of the present invention are for description only, and do not represent the advantages and disadvantages of the embodiments.

In the above-mentioned embodiments of the present invention, the descriptions of each embodiment have their own emphases, and for parts not described in detail in a certain embodiment, reference may be made to relevant descriptions of other embodiments.

In the several embodiments provided in this application, it should be understood that the disclosed technical content can be realized in other ways. Wherein, the device embodiments described above are only illustrative. For example, the division of the units can be a logical function division. In actual implementation, there can be another division method. For example, multiple units or components can be combined or can be Integrate into another system, or some features may be ignored, or not implemented. In another point, the mutual coupling or direct coupling or communication connection shown or discussed may be through some interfaces, and the indirect coupling or communication connection of units or modules may be in electrical or other forms.

The units described as separate components may or may not be physically separated, and the components shown as units may or may not be physical units, that is, they may be located in one place, or may be distributed to multiple units. Part or all of the units can be selected according to actual needs to achieve the purpose of the solution of this embodiment.

In addition, each functional unit in each embodiment of the present invention may be integrated into one processing unit, each unit may exist separately physically, or two or more units may be integrated into one unit. The above-mentioned integrated units can be implemented in the form of hardware or in the form of software functional units.

If the integrated unit is realized in the form of a software function unit and sold or used as an independent product, it can be stored in a computer-readable storage medium. Based on this understanding, the essence of the technical solution of the present invention or the part that contributes to the prior art or all or part of the technical solution can be embodied in the form of a software product, and the computer software product is stored in a storage medium , including several instructions to make a computer device (which may be a personal computer, a server, or a network device, etc.) execute all or part of the steps of the methods described in various embodiments of the present invention. The aforementioned storage medium includes: various media capable of storing program codes such as U disk, read-only memory (ROM, Read-OnlyMemory), random access memory (RAM, RandomAccessMemory), mobile hard disk, magnetic disk or optical disk.

The above is only a preferred embodiment of the present invention, it should be pointed out that for those skilled in the art, without departing from the principle of the present invention, some improvements and modifications can also be made, and these improvements and modifications are also It should be regarded as the protection scope of the present invention.

Claims (10)

1. A method for data storage, comprising: Get the data to be stored; determining the rack corresponding to the data in the storage space through a hash operation; Obtain the data copy corresponding to the data, and determine the storage area corresponding to the data node on the rack of the data copy through a hash operation; wherein, the storage space is a ring storage space, and the data node corresponds to multiple a virtual data node, the storage space that the multiple virtual data nodes are responsible for consists of a plurality of evenly divided storage areas; storing the data copy in the storage area. 2. The method according to claim 1, characterized in that, before acquiring the data to be stored, the method further comprises: performing an equal division operation on the storage space to obtain a plurality of equally divided storage areas. 3. The method according to claim 1, wherein, before said obtaining the data copy corresponding to said data, said method further comprises: determining whether the rack is abnormal; The obtaining the data copy corresponding to the data includes: obtaining the data copy corresponding to the data when it is determined that the rack is normal; When it is determined that the rack is abnormal, the next rack is searched in the storage space in a clockwise order. 4. The method according to claim 1, wherein before storing the data copy in the storage area, the method further comprises: After determining the storage area corresponding to the data node on the rack of the data copy through a hash operation, determine whether the data node on the rack is abnormal; When it is determined that the data node is abnormal, search the next rack in the storage space in a clockwise order; When determining that the data node is normal, determine whether the storage area corresponding to the data node is sufficient; The storing the data copy in the storage area includes: storing the data copy in the storage area when it is determined that the storage area is sufficient; When it is determined that the storage area is insufficient, searching the next data node on the rack in the storage space in a clockwise order. 5. The method according to claim 1, wherein after storing the data copy in the storage area, the method further comprises: Determine whether all data copies are stored; When it is determined that all data copies have not been stored, the next rack is searched in the storage space in a clockwise order. 6. A device for data storage, comprising: an acquisition unit, configured to acquire data to be stored; A processing unit, configured to determine the rack corresponding to the data in the storage space through a hash operation, obtain a data copy corresponding to the data, and determine the data of the data copy on the rack through a hash operation A storage area corresponding to the node; wherein, the storage space is a ring-shaped storage space, the data node corresponds to a plurality of virtual data nodes, and the storage space responsible for the plurality of virtual data nodes is composed of a plurality of equally divided storage areas; a storage unit, configured to store the data copy in the storage area. 7 . The device according to claim 6 , wherein the processing unit is further configured to, before obtaining the data to be stored, perform an equal division operation on the storage space to obtain a plurality of equally divided storage areas. 8. The device according to claim 6, further comprising: A first judging unit, configured to determine whether the rack is abnormal before acquiring the data copy corresponding to the data; The processing unit is configured to obtain a data copy corresponding to the data when the first judging unit determines that the rack is normal; when the first judging unit determines that the rack is abnormal, in a clockwise order Search for the next rack within the storage space. 9. The device according to claim 6, further comprising: The second judging unit is configured to determine, before storing the data copy in the storage area, after determining the storage area of the data copy corresponding to the data node on the rack through a hash operation Whether the data nodes on the rack are abnormal; The processing unit is configured to search for the next rack in the storage space in a clockwise order when the second judging unit determines that the data node is abnormal; The second judging unit is further configured to determine whether the storage area corresponding to the data node is sufficient when determining that the data node is normal; The storage unit is configured to store the copy of the data in the storage area when the second judging unit determines that the storage area is sufficient; The processing unit is configured to, when the second judging unit determines that the storage area is insufficient, search the storage space for the next data node on the rack in a clockwise order. 10. The device according to claim 6, further comprising: A third judging unit, after storing the data copy in the storage area, determines whether all the data copies have been stored; The processing unit is configured to search the next rack in the storage space in a clockwise order after determining that all data copies have not been stored.