FR2922335A1 - IMPROVED COMPUTER SYSTEM COMPRISING MULTIPLE NETWORK NODES. - Google Patents

Abstract

A data storage computer tool comprising a correspondence module (40) connected to storage units, said correspondence module (40) including a mapping function (404) for determining at least two storage addresses for receiving data associated with a virtual address received at the input (402), characterized in that, in the correspondence function: * at least a part of the storage units are logically distributed on the basis of a fault dependency criterion, and * at least one part of the virtual addresses are allocated in blocks to storage addresses according to a chosen rule, said rule comprising an arithmetic formula taking into account said dependency criterion.

Description

The invention relates to computer systems comprising a plurality of computer stations known as nodes interconnected in a network. Modern networks include user stations that are connected to one or more servers and can share applications and / or storage spaces locally or remotely.

In shared applications that use a large amount of data or share a large amount of data, specialized storage systems, such as the Storage Area Network, are often used. (or SAN).

The use of these advanced systems has certain disadvantages, such as the associated costs, the limitations of performance and extensibility, and the overall heaviness of the installation that corresponds to them.

Moreover, with modern networks, the use of these advanced systems represents an underutilization of the hardware already present in the network.

Finally, the systems that have been proposed that use the hardware already present in the network have unsatisfactory performance, especially in terms of fault management.

The invention improves the situation.

To this end, the invention proposes a computer data storage tool 30 comprising a correspondence module connected to storage units, said correspondence module comprising a correspondence function for determining at least two storage addresses to receive associated data. to a virtual address received as input.

According to a particular aspect, in the correspondence function: at least a part of the storage units are logically distributed on the basis of a fault dependence criterion, and

at least a portion of the virtual addresses are allocated in blocks to storage addresses according to a chosen rule, said rule comprising an arithmetic formula taking into account said dependency criterion.

The invention also relates to a computer data storage tool comprising a correspondence module connected to storage units, said correspondence module comprising a correspondence function for determining at least two storage addresses for receiving data associated with an address. received as input.

According to a particular aspect, in the correspondence function: at least a part of the physical addresses are logically distributed into a workgroup and into fault groups, on the basis of a fault tolerance criterion, at least one part of the virtual addresses are allocated in blocks to storage unit storage addresses according to a chosen rule, * said rule having a first arithmetic formula by assigning at least a portion of the virtual addresses to storage addresses belonging to groups and said rule comprising a second operative arithmetic formula in the presence of a failure to assign at least a portion of the virtual addresses concerned to storage addresses belonging to a fault group in accordance with that failure.

The invention also relates to a computer data storage tool comprising a correspondence module connected to storage units, said correspondence module being arranged to determine a correspondence between virtual addresses and physical addresses on the storage units, each address virtual address assigned to at least two storage addresses

According to a particular aspect, the correspondence module maintains a first table comprising storage unit failure identification data, as well as a second table comprising logical zone modification data each designating at least one virtual address.

According to another particular aspect, the computer tool further comprises a recovery unit arranged to update the data of a storage unit that has failed by calling the correspondence module with virtual addresses drawn from the second table, on the database of the first table.

Other advantages and features of the invention will appear better on reading the following description of examples, given by way of illustration and without limitation, from the drawings in which:

FIG. 1 shows a general functional view of a computer system according to the invention,

FIG. 2 shows an example of a logical implementation of the system of FIG. 1; FIG. 3 shows an exemplary composition of an element of FIG. 2; FIG. 4 shows a method of accessing a file. in the system of FIG. 1, FIG. 5 shows an exemplary implementation of an element of FIG. 3, FIG. 6 shows a correspondence between logical spaces and physical spaces managed by the element of FIG. 5, - Figure 7 shows an example of a function implemented by the element of Figure 5 to establish the correspondence of Figure 6, - Figure 8 shows an example of implementation of part of the FIG. 9, - FIGS. 9 and 10 show examples of functions executing in parallel with the function of FIG. 7; FIG. 11 shows an allocation of the logical spaces on the physical spaces as a variant of the correspondence represented in FIG. 6

FIG. 12 shows a variant of the function of FIG. 8 adapted to take account of the allocation of FIG. 11,

FIG. 13 shows an exemplary implementation of a part of FIG. 12,

FIG. 14 shows an example of a function running in parallel with the function of FIG. 7, and

FIG. 15 shows a variant of FIGS. 8 and 12 which implements both the allocation represented in FIG. 6 and that shown in FIG. 11.

The drawings and the description below contain, for the most part, elements of a certain character. They will thus be able not only to serve to better understand the present invention, but also to contribute to its definition, if necessary.

FIG. 1 represents a general diagram of a computer system according to the invention. In this system, an application environment 2 has access to a file system manager 4. A virtualization layer 6 establishes the correspondence between the file system manager 4 and storage servers 8.

FIG. 2 represents a logical implementation of the system of FIG. 1. In this implementation, a set of stations 10, also referred to herein as nodes, are interconnected in a network of which they constitute the physical and application resources.

In the example described here, the network consists of 5 stations, denoted Ni with i varying between 1 and 5. The application environment 2 is made of a distributed application layer 12 on the N1, N2 and N3, in one application layer 14 on the N4 and an application layer 16 on the N5.

Note that the term station or station used here should be interpreted broadly, and as designating network computing elements on which applications or server programs run, or both.

The file system manager 4 is made of a distributed file system 18, and two non-distributed file systems 20 and 22. The system 18 is distributed over the NI, N2 and N3 and defines all the files accessible from the distributed application layer 12. The file systems 20 and 22 respectively define the set of files accessible from the application layers 14 and 16.

The files designated by the file systems 18, 20 and 22 are stored in a virtual storage space 24 which is distributed over all the Ni

6 with i varying between 1 and 5. The virtual storage space 24 is here divided into a shared logical space 26, and two private logical spaces 28 and 30.

The shared logical space 26 corresponds to the space accessible from the distributed application layer 12 by means of the distributed file system 18, and the private logical spaces 28 and 30 to the space accessible from the application layers 14 and 16 by means of the file systems 20 and 22.

The logical space 26 is distributed over the N1, N2 and N3, the private logical space 28 on the N3 and N4, and the private logical space 30 on the N5.

Thus, an application of the layer 12 (respectively 14, 16) "sees" the data stored in the logical space 26 (respectively 28, 30) by means of the file system 18 (respectively 20, 22), although these They are not necessarily physically present on one of the storage disks of the station 10 which uses this application.

Furthermore, the spaces 26, 28 and 30 are purely logical, that is, they do not directly represent physical storage spaces. Logical spaces are mapped using virtual addresses that are referenced or contained in file systems 18, 20, and 22.

To access the data of these files, it is necessary to use a correspondence module. The correspondence module contains a table 25 of correspondence between the virtual addresses of the data in the logical spaces and physical addresses which designate the physical storage spaces in which these data are actually stored.

Several achievements are possible for the correspondence module. The distribution of the physical storage spaces described here is an example intended to show the very general scope of the invention.

As can be seen in the example presented, each station is used for both the application layer and the storage layer. This multifunctionality makes it possible to use the free space on all the stations of the network, rather than leaving this space unoccupied. In the context of the invention, it would however be possible to specialize some of the stations, and create a node dedicated to storage or a node dedicated to applications.

This means that, in the context of the invention, any station can play an application node role, a storage node role, or both of these roles at the same time.

All the application, storage and file system resources 15 can be integrated locally on each station, or else distributed on the stations of the network.

This is for example the case of NI, N2 and N3 stations, whose resources are fully distributed, both at the application level and at the level of the file system and storage.

FIG. 3 represents an exemplary architecture of a station 10 of FIG. 2. The station represented in this example can represent one of the stations NI, N2 or N3. Station Nx individually has a structure similar to that of the global structure shown in Figure 1. It thus comprises an application layer 32, a file system 34, a virtualization layer 36 and a storage space 38 in the form of a local memory with direct access. The virtualization layer 36 includes a motor 40 and a look-up table 42. Direct access to the storage space 38 is managed by a storage client 44 and a storage server 46. Roles and operations of these elements will be specified below.

The example described here represents an improved embodiment of the invention, in which all the resources, both application and storage, are distributed over the network.

This means, for example, that the file system 34 is not entirely present on this station, but distributed over several of them, and that access to it implies communication with other nodes of the network which contain the desired data.

It is the same for the virtualization layer 36, the storage client 44 and the storage server 46. The distribution of these elements is managed by means of a management module 48.

For the rest of the description, it does not matter whether the resources in question are distributed or not.

The administration module 48 is mainly used when creating and updating logical spaces. When creating or modifying a logical space, the administration module 48 calls the virtualization layer 36 to create the correspondence table between each virtual address of the logical space and a physical address on a storage node Given.

Next, the correspondences between a file accessible by this file system and the virtual addresses of the data that make up this file are made at the level of the file system that exploits this logical space, the "physical" data being stored at the physical addresses associated with it. the correspondence table to the virtual addresses, according to the mapping established during the creation of the logical space.

This means that, as soon as a logical space is created by the administration module, the correspondences between the virtual addresses and the physical addresses are established. The virtual addresses appear "empty" to the file system accessing the logical space, although the physical addresses that correspond to them are already "reserved" through the correspondence table.

It is when the link between the data of the files of this space and the virtual addresses of these data is established that the physical addresses are filled.

In the embodiment described here, the look-up table 42 is a table that contains information for retrieving matches. When an application uses a given memory space 15, the motor 40 interacts with the table 42 to establish the corresponding physical address.

As will become clearer later, the lookup table 42 does not contain all the matches, but only a much narrower set of information sufficient to quickly restore the match.

In order to better understand the invention, it is necessary to differentiate the application layer from the storage layer. Indeed, the management of access to the data stored in the storage layer is an approach that has many advantages over the existing one.

Figure 4 shows a method implemented by the system to access a file. 30

The access to a file by an application of the application layer of a given node is initialized by a file access request 50. The file access request 50 comprises: an identifier of the file concerned for the file system and an address in this file,

the size of the request, that is to say the number of bits to be accessed following the address of the targeted file, and the type of request, namely the reading or writing.

In a step 52, the file system determines one or more virtual addresses for the data of this file, and generates one or more virtual access requests based on the request 50 and these virtual addresses. The virtual access requests each include:

- the targeted virtual address,

The size of the request, that is to say the number of bits to be accessed following the targeted virtual address, and

- the type of request, which is identical to that of the request 50.

Referring to the system depicted in FIG. 2, step 52 is to determine the logical space and the virtual address (es) on this space designated by the request 50, and to produce one or more virtual requests. ".

There is a difference in level between the file access requests and the virtual access requests. Indeed, a file access request will target the content of a large quantity of virtual addresses, to enable the content of a file to be reconstructed, whereas a virtual request targets the contents of a data block. associated with this address.

The virtual access request (s) obtained is then transmitted to the virtualization layer 5, which determines the physical address (es) and the corresponding storage spaces in a step 54.

To determine the physical addresses, the virtualization layer operates using the engine 40 and the look-up table 42. In the context of a read access request, the searched file already exists in a storage space 38, and the Engine 40 calls the correspondence table 42 with the virtual address (es) to determine by correspondence the physical address (es) of the data of the file. In the context of a write access request, the file does not necessarily exist beforehand in a storage space 38. Nevertheless, as we have seen above, the correspondences between virtual addresses and physical addresses are fixed, and the motor 40 therefore operates in the same way as in the context of a read request to determine the physical address or addresses of the data.

In any case, once the engine 40 has determined the physical addresses, it generates in a step 56 physical access requests that it transmits to the storage client 44.

In step 56, the physical access requests are generated based on the request 50 and the physical address (es) determined in step 54.

These requests include: - the intended physical address; The size of the request, that is to say the number of bits to be accessed following the physical address targeted by the request; and - the type of action targeted, namely reading or writing. The physical address and the size of the request are obtained directly from step 54, and the type of the request is inherited from the type of the virtual access request concerned.

A loop is then initiated in which a stopping condition 58 is reached when a physical access request has been issued to the storage client 44 for all physical addresses obtained in step 52.

In fact, each physical access request is placed in a request queue of the storage client 44 for execution in a step 60. The storage client 44 may optionally include several queues, for example a queue. by storage server 46 with which it interacts.

In this loop, all physical access requests in step 56 are represented as successively performed for simplicity. However, the execution can also be performed in parallel, and not only in series.

In the example described, requests are transmitted from layer to layer, up to the physical access layer. However, it would be possible to determine and transmit only addresses (virtual and physical), and to recover, at the physical layer level, selected properties of the initial file request to form the physical access requests.

For the execution of a given physical access request, the storage client 44 interacts with the storage server 46 of the storage station that contains the storage space 38 on which the designated physical address is located. by the physical access request concerned.

FIG. 5 represents an exemplary embodiment of the virtualization layer 36 of FIG. 3.

The engine 40 includes a queue 402, an address determination unit 404 and a repair / overlay unit 406.

The queue 402 receives all the virtual access requests for the determination of the corresponding physical addresses. The determination of the physical addresses is carried out by the address determination unit 404, in collaboration with the correspondence table 42.

In the example described here, the look-up table 42 contains only an extremely limited set of data which will be described later. Indeed, the invention proposes several schemes for assigning virtual spaces to physical spaces. These assignments make it possible to quickly and inexpensively determine virtual address / physical address matches on the basis of lightweight algorithms while offering a high quality of service. This is much more efficient in terms of processor and memory occupation than the use of a direct look-up table such as a "look-up table" (in English).

The purpose of the repair / overlay unit 406 is to update certain physical addresses when a storage space of a given station has ceased to function, as will be described below.

Figure 6 illustrates a first scheme for assigning virtual spaces to the physical spaces so as to tolerate so-called correlated failures. Correlated failure means a failure that renders inoperative a set of spaces or

14 storage units (hereinafter disks) interconnected (hereinafter failure group).

In other embodiments, the disks can be grouped by failure group on the basis of a fault dependency criterion. Such a fault dependence criterion aims to bring together disks for which the probability of a simultaneous failure is important, so as to ensure that the data of these disks are not replicated on one of them. .

As an example of a fault dependence criterion, mention may be made of the fact that the same node-node, both from a hardware and software point of view, is connected to the same network node, from a material point of view that software, the proximity of geographical location, etc.

To prevent such failures, the allocation of virtual space to the physical spaces is carried out so that: - the data of a virtual address is stored on disks that belong to distinct fault groups; and - the consecutive virtual address data is gathered into hatches that extend over all the disks.

Thus, in the example shown, we start from four nodes N1 to N4. The node N1 here comprises three disks MU11, MU12 and MU13, the node N2 three disks MU21, MU22 and MU23, the node N3 a disk MU31, and the node N4 three disks MU41, MU42 and MU43.

In the example described here, each node forms a failure group, that is, in terms of failure, it is considered that the disks of a node depend on it, but that the disks of nodes distinct are independent of each other.

The failure group N1 thus consists of the disks MU11 to MU13, the failure group N2 is composed of the disks MU21 to MU23, the failure group N3 is composed of the disk MU31, and the failure group N4 is composed of the disks MU41. at MU43. In other embodiments, the groups of failures could be defined differently, for example by belonging to a network unit. It is therefore important to understand that disks are first grouped by failure group and not only by node. Initially, the assignment shown in Fig. 6 starts from failure groups to define replication groups that allow secure duplication of data.

Assigning the disks of the failure groups to a replication group follows an allocation algorithm that implements the constraints described above.

To account for the first constraint, there must be at least as many replication groups as there are disks in the failure group that has the largest number of disks, according to the equation 10 of Annex A.

Then, in order to achieve the most flexible distribution in terms of load, the number of disks per replication group is fixed according to equation 11 of Appendix A. Finally, the disks are assigned individually in each group of replication according to [equation 12 of Annex A.

Thus, in the example of FIG. 6, the replication group GR1 comprises four disks which respectively correspond to the disks MU11, MU21, MU31 and MU43, and the other disks MU12 and MU13 of the failure group N1 are assigned respectively to the groups GR2 and GR3.5

Other disk assignment algorithms are possible, as those skilled in the art will recognize. It will be noted for example that, for the allocation of disks to the replication groups, it would also be possible to take into account the space available on the disks, so as to ensure replication groups of uniform size. Another possibility would be to take into account their performance to obtain homogeneous performance replication groups.

This could for example be done: * when assigning disks to replication groups, by complicating the algorithm, or * after the assignment described above, by performing disk exchanges between replication groups.

In a second step, to take into account the second constraint, the virtual addresses are assigned on the disks sorted by replication group. In each disk shown, each number that is represented means the association of virtual addresses to physical addresses.

Indeed, the virtual addresses are grouped in ascending order in units of hatching ("striping unit" in English) of defined sizes. The hatch units are themselves associated with physical addresses on the disks.

As can be seen in the upper part of Figure 6, the hatch units are assigned to all disks of all replication groups in ascending order, line by line.

Thus, the first hatch unit of the first disk of the first replication group receives the index 0, the first hatch unit of the second disk of the first replication group receives the index 1, and so on.

A line of hatch units will subsequently be called the actual hatch. Note also in the upper part of Figure 6 that for every other line, the hatch units are not ordered by increasing index.

This is because, to account for the first constraint, the data for each real hatch is replicated within the replication group to which the first version is assigned. As a result, corresponding real hatches are combined in pairs to form a main hatch each time.

To determine the allocation of hatch units for replication, we use an equation that ensures that: * two replicates of the same hatch unit are not stored on the same disk, and * the offset that is made to that effect is not constant, so that when a given disk fails, the load is spread over the other disks.

Thus, in the example shown in FIG. 6, the physical addresses of the MU11 disk of N1 receive the following hatch units: 0, 3, 10, 12, 20, 21, 30, 33, 40 and 42. in the example described here, the data is replicated to directly consecutive true hatches within the main hatch. In other embodiments, the replicated data could be in non-consecutive real hatches.

As can be seen from the above, it is therefore sufficient to know the total number of disks as well as the number of replication groups to determine a physical address from a virtual address. The correspondence table 42 is thus reduced to its simplest expression. Note also that, because of the data replication mentioned above, there are twice as many physical addresses as virtual addresses.

In the example shown in Figure 6, as well as in the remainder of this document, a simple replication of the data is performed, which results in doubling the amount of data stored. However, it would be possible to make more than two replicas of the data. Figure 7 shows the example of a function that allows to find a physical address from a virtual address.

In the example described here, this function is implemented in the address determination unit 404. It starts in an operation 2000 of a virtual address, for example taken from the queue 402.

In a 2020 operation, a test is performed to determine if the virtual address is related to a write request. If so, in an operation 2040, a test is performed to determine if the system is in a degraded state, i.e. if one of the disks has failed. If so, a Wrt Drt Z () function is called in 2060.

The operations 2040, 2060 and 2080 are connected to functions for the rapid recovery of a disk failure which will be described further with FIGS. 9 and 10.

In the case where the request associated with the virtual address is a read request, or when the state of the system is not degraded, or when the function Wrt _Drt_Z () ends, a function SU_Ind () is called in an operation 2070.

The function SU_Ind () starts from the virtual address whose correspondence is sought, and returns the index of the hatch unit SU Ind. which is associated with him. This is readily achievable as the size of each hatching unit is known. On the basis of this index, a Get function Phy_Ind () is called in an operation 2080 which determines corresponding physical address indices.

Finally, in an operation 2100, the physical address indices are converted into physical addresses by a function Phy_Ad (). This is easily achievable as the size of each hatching unit is known.

The function Get_Phy_lnd () will now be described with figure 8. The function Get_Phy_Ind (receives the two following arguments (operation 2082): * the index of the unit of hatching of which one seeks the correspondence, and * a table Ngr [ ] containing a row whose values indicate the number of disks for each replication group.

The table Ngr [] is useful because it allows to quickly find the total number of N disks and the number of Ngr replication group, and to access just as quickly the number of disks by replication group.

In another implementation, it is possible to directly pass N and Ngr 20 as arguments, but a computation is then necessary when one needs the number of disks within a given replication group.

The function of the function Get_Phy_Ind (is to find the index of the hatch unit in the sorting by failure group from its index in the sorting by replication group.In a first operation 2084, a strip function ( ) determines a main hatch index k, as well as the index ml in the replication groups of the first disk on which the virtual address is stored.This is done by applying Equations 20 and 21 of Appendix A.

In an operation 2086, a function Repl () determines the actual hatch indices k1 and k2 to account for the replication of the data. This is accomplished by applying Equations 22 and 23 of Appendix A.

In an operation 2088, a function Spl () determines the index p of the replication group that corresponds to the disk index ml, as well as the index q1 of the disk ml within this replication group. This is accomplished by applying Equations 24 and 25 of Appendix A. In an operation 2090, a function Shft () determines an index q2 within the index replication group p of the disk on which the replicated data is stored. This is accomplished by applying Equation 26 of Appendix A.

Other equations would obviously be usable, such as a simple shift unit index offset. In this simpler case, each disk within a replication group contains all replicated data from another disk in the same group.

In an operation 2097, a function Mrg () determines a disk index m2 which corresponds to the index q2 within the index replication group p. This is accomplished by applying Equation 27 of Appendix A. In an operation 2098, the indices ml and m2 of disks classified by replication group are converted to disk indices n1 and n2 of disks classified by failure group by a function Get_Dsk Ind (). This function performs the inverse operation of equation 12 and applies equations 28 and 29 of Appendix A.

Finally, the Get Phy_Ind () function returns the physical address indices determined in an operation 2099.

Now, the function WrtDrtZ () will be described with reference to FIGS. 9 and 10. As mentioned above, the invention relies in part on the replication of data in case of failure. The Wrt Drt ZO function and the function described in FIG. 9 allow a fast reintegration of a disk after a failure. This reinstatement is described with Figure 10.5

The principle of this reintegration is based on the marking of the virtual zones associated with a failed disk during a write.

Indeed, both during a read request and when there is no access, the stored data are not modified. Therefore, when a disk comes back from a failure, it is not necessary to update this data since they have not been modified.

On the other hand, if there has been write, the stored data is potentially distinct, and consistency must be restored with the version of the data that has been written.

For this, two tables are maintained during execution. The first table, called failures, contains two lines, one of which receives identifiers of 15 disks and the other receives a growing index. The second table, called zones, contains two lines, one of which receives zone identifiers, and the other receives a modification index.

In the example described here, the fault table is stored on each of the 20 disks in a space reserved by the administration module which is not usable for storing the data. This table is kept consistent on all the disks by the administration module. This table has a fixed size equal to the total number of disks. The fault table is filled by means of the function shown in FIG. 9. Thus, when a failure is detected, for example by the administration module 48 (operation 2200), this function receives the identifiers of all the disks. Out of order.

In an operation 2202, a function Is_Tgd_Dsk () searches for each failed disk identifier in the fault table.

For each missing identifier, the fault table creates a new entry that receives the disk identifier in the first line, and an index incremented in the second line (operation 2204). Otherwise the function processes the next identifier (operation 2206).

Alternatively, the fault table is implemented as a stack or linked list. Therefore, it comprises only one line which receives the indices of disks, and it is the index of position of each identifier in the table which serves as increasing index.

The Wrt Drt _Z () function relies on the clues from the fault table to maintain an up-to-date view of the areas associated with a failed drive that have been modified.

Thus, as discussed above, the function Wrt_Drt_Z () is called for each write request, and its function is to mark in the zone table the highest index of the failure table.

Thus, when a zone has an index greater than or equal to that of a disk of the fault table, this means that it has been modified after the failure of the disk considered.

On this basis, the repair and overlay unit 406 can perform the function of Fig. 10 to restore a disk after a failure. For this purpose, the unit 406 starts with an index i set to zero (operation 2300) and traverses the zone table.

Each time, a comparison between the index associated with the disk that is restored in the fault table and that of the index zone i in the zone table 30 indicates whether the zone was modified after the failure of the disk considered. (operation 2302). If so, then a function Upd_Z (i) updates the data of the area concerned by retrieving the replicated data corresponding thereto (operation 2304). Next, the zone table is updated to reflect this operation (2306).

Once the index field i is updated, an End_Drt Zone () function deletes the entry from the fault table associated with the restored disk, and goes through the fault table to increase the index of the zones by the maximum of the remaining indices. . This ensures slow index growth and avoids processing too much data.

If there are still areas to browse, the index i is incremented (operation 2310). Otherwise, the function ends in operation 2312.

It should be noted that the zone table can receive zones of configurable size. Indeed, an entry in the zone table is associated with a plurality of contiguous virtual addresses.

In the embodiment described here, this table is stored in the reserved data area of the logical volume to which the virtual addresses belong, i.e. it is equally distributed on all the disks.

Note that the reserved data area of the logical volume is not extensible indefinitely. It should also be noted that the call to the zone table constitutes a read request in the system.

It is therefore necessary to find a compromise between the granularity of the data of the zone table (which increases the performance of the recovery / recovery mechanism), and the cost which is associated with the multiplication of the requests (which increases with the granularity).

The functions described in FIGS. 9 and 10 can be seen as functions that loop in parallel with the main execution of the system. Indeed, to ensure maximum information security, these functions constitute "interrupts".

This means that if the condition of their launch (disk that fails or disk is restored) is encountered, the physical address determination requests that are running are canceled and replayed after these functions are executed.

These functions can therefore be performed directly in the virtualization layer or in the administration module, as separate functions as presented here, or as an integral part of the functions presented above.

Figure 11 shows an assignment of virtual spaces to physical spaces as an alternative to that of Figure 6. Here, fault tolerance is also increased, this time voluntarily leaving free spaces within replication groups called resiliency units.

For the sake of clarity, there is shown in this figure a single replication group that includes seven disks. Among these seven disks, we will define hatches comprising four hatch units for storing data, and three resilience units for fault tolerance.

As seen in Figure 11, the data is always replicated once, in the same manner as before, but there is also a lag with each hatch. This offset is used to ensure that all free spaces are distributed over all disks, which ensures a better balance of the load.

As for the hatch units, two physical addresses are associated on the disks with each resilience unit SpO, Spi and Sp2. In Fig. 11, the physical addresses associated with the same resiliency unit in a given principal hatch are referenced identically.

For the determination of physical address with the assignment described with FIG. 11, the function described with FIG. 7 remains usable, with some modifications to the function Get Phy_Ind ().

Such an alternative Get Phy Ind () function will now be described with FIG. 12. First of all, the difference of context between the allocation shown in FIG. 6 and that presented in FIG. 11 will be noted.

In the first case, the disks are divided into several groups to avoid correlated failures, that is to say affecting several disks at a time.

In the second case, some of the hatch units are used as free space to compensate for a failure of one or more of the disks, as will be shown below.

There is therefore no priori grouping of disks by replication group, although this is possible as will be seen with FIG.

The definition of the resilience units in addition to the hatch units amounts to distributing part of the physical addresses into a workgroup (those receiving the data of the hatch units) on the one hand, and into failure groups (those which receive the data of the resilience units) on the other hand, according to a fault tolerance criterion.

Such a fault-tolerance criterion relates, for example, to the number of successive failures that one wishes to support, and therefore the number of failure groups to be managed. In the present example, this number is three. Other criteria could nevertheless be used. In the example of FIG. 12, the function Get_Phy_Ind () can be seen as two successive blocks: * a processing block A to determine the disk and hatch indices as before, without taking into account the presence of the units of 5 resilience, and * a block B that treats the indices thus calculated to take into account the presence of the resilience units and obtain the real indices.

The function Get_Phy_Ind () receives the following three arguments (operation 2482): 10 * the index of the hatching unit whose match is sought, * the number of disks in the system, and * the number of units of resiliency .

In a first operation 2484, the StripO function determines a main hatch index k, as well as the mml index of the first disk on which the virtual address is stored.

The operation 2484 differs from the operation 2084 of Figure 8 in that the Strip () function is called with the number of hatch units, i.e. the number of disks minus the number of resilience units.

In an operation 2486, the Replu function determines the actual hatch indices k1 and k2 to account for the replication of the data as the operation 2086. In an operation 2490, the function Shft () determines a subscript mm2 of the receiving disk. the replicated data. Operation 2490 differs from operation 2090 of Figure 8 in that the function Shft () is called with the number of hatch units, i.e., the number of disks minus the number of units resilience.

In an operation 2492, a function Cp_Spr () determines an index ml which corresponds to the real index of the disk associated with the index mml. This function is used to modify the mml index to take into account the presence of the resilience units. As will be seen below, the index ml that returns the function Cp_Spr () can be an index of a unit of resilience.

In an operation 2494, a function Cp_Spr () determines an index m2 which corresponds to the real index of the disk associated with the index mm2. This function is used to modify the mm2 index to take into account the presence of the resilience units. As will be seen below, the index m2 that returns the function Cp_Spr () can be an index of a unit of resilience.

Once the indices ml and m2 are determined, the physical address indices are returned in 2499. The function Cp_Spr () will now be described with FIG. 13. This function receives as arguments a disk index mm, a unit index The function Cp_Spr () starts by executing a function Spr () in 2602. The function Spr () implements the equation 30 of the Appendix A. The Spr () function receives three input arguments: * the disk index mm, * the hatch unit index k; 25 * the total number of discs N.

As the index mm has been established on an N-S number of disks, the function Spr () thus makes it possible to establish an index m which takes into account the presence of the S units of resilience. Next, a test determines in an operation 2604 whether the disk associated with the real index m has failed and whether a resiliency unit has been assigned to it. An exemplary implementation of the function 2604 is the holding of a table here called resilience table. This table contains a single line, in which each column corresponds to a disk of index m corresponding to the number of the column. The value stored in each column indicates: * that the index disk m is not broken, or * that the index disk m is out of order, and the stored value is then a unit of resilience index which determines the index of the disk to which the resilience unit associated with the index disk m is assigned.

Such a resilience table is stored on each of the disks and is synchronized continuously, together with the fault table for example. If a resiliency unit is to be used then the index mm is updated in an operation 2606 by a function Spr_2 () which implements equation 31 of Annex A using as arguments the total number of disks N , the number of resilience units S, and the index m that has just been calculated. This function assumes that the data of index disk m is stored in each hatch on the resilience unit whose resilience index is indicated by the resilience table, and that therefore it is sufficient to know the hatch index k to determine the index of the disk on which the desired resilience unit is allocated.

For this, after updating the mm index, the Cp_Spr () function is restarted. Thus, in the case where two failures occur successively, if the resiliency unit associated with one of the failed disks is located on the second failed disk, the function Cp_Spr (is repeated again, so that the The returned index corresponds to a resiliency unit on a functional disk.

In this way, multiple failures can be tolerated, as the resiliency units can be used to replace other resiliency units. To maintain the resilience table, and to fill the physical addresses associated with the resiliency units during a failure, a function will now be described with FIG.

When the system detects that a disk fails (operation 2700), this function receives the IDs of all failed disks.

In an operation 2702, a function Spr_Dsk () modifies the index of the failed disk with which no resilience unit is associated. The value of its resilience index receives the first resilience index not already assigned.

Then, in an operation 2704, the replicated data of the hatch units that were located on the failed disk are copied to the associated resiliency units by means of a Wrt_Spr_Dsk () function.

To improve the performance, the copying is not immediately carried out: the function Wrt_Spr_Dsk () generates queries for writing the data available on the remaining hatchery unit to the resilience unit, and these queries are executed in competition with other access requests. This means that the resiliency unit can not be used until this write request has been made. Finally, the function ends in 2706.

Alternatively, the Wrt_Spr_Dsk () function generates the write requests on the resiliency units and executes these requests before any other access request.

Note that when the disk is restored, it is also necessary to copy the replicated data back to it again.

The function described in Figure 14 can be seen as a function that loops in parallel with the main execution of the system. Indeed, to ensure maximum information security, this function is an "interruption".

This means that if the condition of its launch (disk crashing) is encountered, the physical address determination requests that are running are canceled and replayed after this function has been executed.

This function can therefore be performed directly in the virtualization layer or in the administration module, as a separate function as presented here, or as an integral part of the functions presented above.

In an advantageous embodiment, the assignment described with FIG. 6 and that described with FIG. 11 are mixed, to provide an optimal breakdown support.

For the determination of physical address with such an assignment, the function described with FIG. 7 remains usable, with some modifications to the Get_Phy_IndO function.

Such a function Get Phy_Ind (alternatively will now be described with FIG.

The function shown in FIG. 15 is a mixture of the variants of the Get_Phy_Ind () function described with FIGS. 8 and 12. Thus, it has great similarities with them. This is why some operations have not been renumbered.

In an operation 2482, the function Get_Phy_lnd () receives the following arguments: * the index of the hatching unit whose match is sought, * an array Ngr [] containing a line whose values indicate the number of disks for each replication group, and * the number of resiliency units.

As for Figure 8, the table Ngr [] is useful because it allows to quickly find the total number of N disks and the number of Ngr replication group, and access just as quickly to the number of disks per replication group.

In another implementation, it is possible to directly pass N and Ngr as arguments, but a computation is then necessary when one needs the number of disks within a given replication group.

Operations 2484 and 2486 are then performed identically to those of FIG. 12, and operation 2488 is performed as step 2088 of FIG.

Next, operations 2490 to 2494 are performed as in the case of FIG. 12, taking into account that this operation is performed within a replication group.

The indices of the disks q1 and q2 within the replication group p are then transformed into disk indices ml and m2 in operations 2496 and 2497 in a similar manner to the operation 2097 of FIG. 8. Then the indices ml and m2 of the Disks classified by replication group are converted to disk indexes n1 and n2 of disks classified by failure group in a 2498 operation as operation 2098 of FIG.

Finally, operation 2499 is performed as step 2099 of FIG. 8 to return the physical address indices. 25

This embodiment is the embodiment is very advantageous because it offers a very high tolerance to various failures, both through the distribution of data on disks belonging to different failure groups that through the use of units resilience that can contain failures within replication groups.

In addition, the hatching distribution described in the modes described allows to obtain very improved performance, as the accesses are distributed on separate disks.

The hatching units are here described as having a fixed size. It would nevertheless be possible to implement the invention by assigning different sizes of hatch units according to the replication groups with some modifications to the described functions.

The engine and lookup table described herein form a correspondence module capable of assigning the virtual addresses to physical addresses based on a rule having an arithmetic formula defined by the above functions. Although in the embodiments described above these functions constitute the essence of the assignment rule, it would be possible to use a rule which fixedly affects a certain part of the virtual addresses, and which affects another part. virtual addresses with functions. Although the embodiments described above link the virtualization layer to an upstream application environment and to physical disks (or local memory unit) downstream, the skilled person will understand that the virtualization layer presented here could be isolated from these elements. It is therefore necessary to consider this layer independently, as a logical (virtualization) brick above and below which additional logical bricks can be stacked.

In this context, obtaining addresses that are called "physical address" means above all a disassembly of the virtualization layer. These addresses could indeed themselves be virtual addresses of a logical space of a storage server. In the same way, the virtual addresses received upstream could themselves correspond to a disabstraction of a higher virtualization layer.

The application that accesses the stored data may include a driver that manages the relationships between the various elements such as the application-file system interaction, the file system-correspondence module interaction, the correspondence module-client interaction. storage, implementing the storage server policy by getting each item a result and calling the next item with that result (or a modified form of that result).

Alternatively, the system is autonomous and does not depend on the application that calls the data, and the elements are able to communicate with each other, so that the information goes down and then back up the element layers into element.

Similarly, the communications between these elements can be provided in different ways, for example by means of the POSIX interface, IP, TCP, UDP protocols, shared memory, RDMA (Remote Direct Access Memory). It should be borne in mind that the object of the invention is to provide the advantages of specialized storage systems based on existing network resources. An exemplary embodiment of the system described above is based on a network in which the stations are made with computers comprising:

a specialized or generalist processor (for example of the CISC or RISC 5 type or other),

* one or more storage disks (eg Serial ATA, SCSI, or other hard drives) or any other type of storage, and

10 * a network interface (for example Gigabit, Ethernet, Infiniband, SCI ...)

* An operating system-based application environment (eg Linux) to support applications and offer a file system manager, * an application set to realize the correspondence module, for example the Clustered Logical Volume Manager module the Exanodes application (registered trademark) of the company Seanodes (registered trademark),

An application set for producing the storage client and the storage server of each NBD, for example the Exanodes Network Block Device module of the Exanodes (registered trademark) application of the company Seanodes (registered trademark),

An application set for managing the distributed elements, for example the Exanodes Clustered Service Manager module of the Exanodes (registered trademark) application of the company Seanodes (registered trademark).

This type of system can be realized in a network comprising: 30 * conventional user stations, adapted for application use on a network and acting as application nodes, and

A set of computing devices made in accordance with the above, and which act as network servers and storage nodes. Other materials and applications will be apparent to those skilled in the art for making alternative devices within the scope of the invention.

The invention encompasses the computer system comprising the application nodes and the nodes storing as a whole. It also encompasses the individual elements of this computer system, and in particular the application nodes and the storage nodes in their individuality, as well as the various means for carrying them out.

Similarly, the data management method is to be considered in its entirety, that is to say in the interaction of the application nodes and the storage nodes, but also in the individuality of the computer stations adapted to achieve the application nodes. and the storing nodes of this process.

The above description is intended to describe a particular embodiment of the invention. It can not be considered limiting or describing it in a limiting manner, and covers in particular all combinations of characteristics of the variants described.

The invention also covers, as products, the software elements described, made available under any "medium" (support) readable by computer. The term "computer-readable medium" includes data storage media, magnetic, optical and / or electronic, as well as a medium or transmission vehicle, such as an analog or digital signal.

ANNEX A SECTION 1 NGR = max (NN) (10) If i <N mod NGR, NGR [i] = NGR + 1 Otherwise, NGR [i] N = N GR n N m = + (n mod NGR) x + min (mod NGR, N mod NGR) (12) NGR NGR SECTION 2 k SUInd. N m1 = SUInd. mod N k1 = kx 2 (22) (20) (21) APPENDIX A (continued) SECTION 2 (continued) k2 = kx 2 + 1 (23) mi ù min (1 + N1 N mod NGR) NGR qi = ml where min ml N mod NGR) ù px N (25) 1 + NGR NGR q2 = (qi + 1 + (k mod (NGR [p] ù 1))) mod NGR [p] (26) m2 = q2 + px N + min (p, N mod NGR) (27) NGR ni = qi x NGR + p (28) n2 = q2 X NGR + p (29) SECTION 3 m = (mm + k) mod N (30) mm = ( m + N ù S) mod N (31) p = N NGR (24)

Claims (3)

claims A computer data storage tool comprising a correspondence module (40) connected to storage units (38), said correspondence module (40) comprising a correspondence function (404) for determining at least two storage addresses for receiving data associated with an incoming virtual address (402), characterized in that, in the correspondence function: * at least a portion of the storage units are logically distributed on the basis of a fault dependency criterion , and * at least a portion of the virtual addresses are allocated in blocks to storage addresses according to a chosen rule, said rule comprising an arithmetic formula taking into account said dependency criterion. 15 A data storage computer tool comprising a correspondence module (40) connected to storage units (38), said correspondence module (40) comprising a correspondence function (404) for determining at least two storage addresses for receiving data associated with an incoming virtual address (402), characterized in that, in the correspondence function: * at least a portion of the physical addresses are logically distributed into a workgroup and into fault groups, on the basis of a fault tolerance criterion, at least a portion of the virtual addresses are allocated in blocks to storage unit storage addresses according to a chosen rule, said rule having a first arithmetic formula by assigning least part of the virtual addresses to storage addresses belonging to workgroups, and * said rule comprising a second arithmetic formula in the presence of a failure to allocate at least a portion of the virtual addresses concerned to storage addresses belonging to a fault group according to this failure. 38 39 A data storage computer tool comprising a correspondence module connected to storage units, said correspondence module being arranged to determine a correspondence between virtual addresses and physical addresses on the storage units, each virtual address being assigned to at least at least two storage addresses, characterized in that the correspondence module maintains a first table comprising storage unit failure identification data, and a second table including logical area modification data designating each at least one virtual address, the computer tool further comprising a recovery unit arranged to update the data of a storage unit that has failed by calling the correspondence module with virtual addresses derived from the second table, based on the data from the first table.