FR2940570A1 - Computing data storage tool for network of nodes in computer system, has constructor constructing ordered sequence of calls of elements, where call sequence comprises conveyor call and previous call of lock, for each next call of conveyor - Google Patents

Abstract

The tool has a storage address accessing manager (44) including an access actuator carrying out accessing of a storage address on a storage space (38) i.e. direct-access local memory, of a network of user stations. The accessing manager has a constructor that constructs an ordered sequence of calls of elements of the accessing manager from storage address accessing request data. The ordered sequence of calls comprises a conveyor call and a previous call of a lock of a conveyor accessing manager (40), for each next call of a conveyor.

Description

SEANODES4.FRD 1 Storage system with multiple network nodes with parity management

The invention relates to computer systems comprising several computer stations called 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 space 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 as well as in the amount of space allocated to data redundancy.

The invention improves the situation.

For this purpose, the invention proposes a computer tool for storing data in a network of stations, each station comprising one or more storage units, at least some of which have storage addresses suitable for receiving storage data and data. parity, the tool being implanted on each station and comprising on the one hand a virtualizer associating virtual addresses and storage addresses, and on the other hand an access manager to the storage addresses. In this tool, the virtualizer maps a group of virtual addresses and a group of given storage addresses to store the corresponding storage data as well as parity data, the storage addresses of each group being distributed over separate storage units.

In addition, the access manager comprises the following elements: a locker, arranged to lock or unlock access to a storage address on a storage unit of the station on which the tool is implanted; access, arranged to make an access to a storage unit storage address of the station on which the tool is implanted, - a parity controller, arranged to calculate parity data, - a connector, arranged to enable an exchange of data between the access manager and another access manager, - a relay, arranged to transmit data characteristic of an access request, from the access manager to another access manager, a constructor, arranged to construct, based on access request data for a storage address, an ordered sequence of calling at least some of the elements of the access managers of the shared stations; carrying the storage addresses of the address group designated by said access request, said ordered sequence comprising at least one call to the relayer, and comprising, for each subsequent call of a relay, a prior call to the locker of the manager of the this runner's access.

Other characteristics and advantages of the invention will appear better on reading the following description, taken from examples given for illustrative and non-limiting purposes, taken from the drawings in which: FIG. 1 shows a general functional view of 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. shows an example of composition of an element of FIG. 3, - FIG. 5 shows a method of accessing a file in the system of FIG. 1, - FIG. 6 shows an example of carrying out an operation. of FIG. 5, and FIGS. 7 to 11 represent sequences of operations of FIG. 6 for various accesses according to the method of FIG. 5.

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

This description is likely to involve elements likely to be protected by copyright and / or copyright. The rights holder has no objection to the identical reproduction by anyone of this patent document or its description, as it appears in the official records. For the rest, he reserves his rights in full.

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 Ni, 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 produced in a distributed file system 18, and two non-distributed file systems 20 and 22. The system 18 is distributed over the N1, 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 the set of Ni 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 that 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 of correspondence between the virtual addresses of the data in the logical spaces and physical addresses that 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, however, it would 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 roles at once.

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

This is for example the case of N1, 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 N1, N2 or N3.

The Nx station individually has a structure similar to that of the overall structure shown in FIG. 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 FIG. a local memory with direct access.

The virtualization layer 36 includes a motor 40 and a look-up table 42. The direct access to the storage space 38 is managed by an access manager 44.

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 and the access manager 44. The distribution of these elements is managed by means of a management module 46.

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

The administration module 46 is mainly used during the creation and updating of the logical spaces. When creating or modifying a logical space, the administration module 46 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.

Then, 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 associated physical addresses in the file. correspondence table to the virtual addresses, in accordance with 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 file data of this space and the virtual addresses of this data is established that the physical addresses are fulfilled.

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, the engine 40 interacts with the table 42 to establish the corresponding physical address.

It will be understood that here, the table 42 is not a conventional look-up table, but rather a table which stores a limited number of information but which allows the engine 40 to recover the physical addresses.

Indeed, as will be explained below, the addresses on the different storage units are associated by block, which allows to find an address quickly, without having to store all possible matches.

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

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 access following the address of the targeted file, - the type of request, namely the reading or the write, and - a buffer identifier for storing the read data or obtaining the data to be written.

In an operation 52, the file system determines one or more virtual addresses for the data in this file, and generates one or more virtual access requests based on the request 50 and these virtual addresses.

The virtual access requests each comprise: 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, the type of request. query, which is identical to that of the request 50, and - a buffer identifier for storing the read data or obtaining the data to be written.

With reference to the system described in FIG. 2, the operation 52 consists in determining the logical space and the virtual address or addresses on this space designated by the request 50, and producing one or more access requests. virtual.

The term virtual access means that access is made to addresses of the virtual layer. However, as is clear from the foregoing, this access is not virtual in itself and involves access to corresponding physical data.

There is a difference in level between file access requests and 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 resulting virtual access request (s) is then transmitted to the virtualization layer, which determines the physical address (es) and the corresponding storage spaces in an operation (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 file data already exists, and the engine 40 calls the table correspondence 42 with the virtual address (es) of this file to determine by correspondence the physical address (es) of the data of the file.

In the context of a write access request, the data of the file do not necessarily exist in a prior manner. 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 an operation 56 physical access requests that it transmits to the access manager 44.20. In the operation 56, the requests of Physical access is generated based on the request 50 and the physical address (es) determined in the operation 54.

These requests include: - the target physical address, - the size of the request, that is to say the number of bits to access following the physical address targeted by the request, - the type of action referred to, namely reading, writing, resynchronization or verification, - a buffer identifier for storing the read data or obtaining the data to be written, and - additional data necessary for the execution of the request.

The physical address and the size of the request are obtained directly from the operation 54, and the type of the request is inherited from the type of the virtual access request concerned.

In the context of the invention, the data are stored according to a parity diagram. This means that each virtual address has a unique physical address.

In addition, the virtual addresses and the corresponding physical addresses are grouped by address blocks, and an additional physical address is assigned to each block to store parity data.

The parity data is calculated by performing an operation or exclusive with all the data of the block. Thus, if a disk containing one of the physical addresses of the block fails, it remains possible to access the lost data, from the data of the other addresses of the block and the corresponding parity data.

It does mean, however, that managing concurrent access to data in a given block and maintaining consistency between data in a block and its parity data are crucial objectives.

The additional data of the physical access request is used to provide the access manager 44 with the information necessary to achieve these objectives.

Thus, this data may comprise: - all the physical addresses of the block to which the physical address in question belongs, - an identifier of a storage unit that has fallen down or desynchronized, and - a request model indicator to be put into operation. artwork. A loop is then started, in which a stopping condition 58 is reached when a physical access request has been sent to the access manager 44 for all the physical addresses obtained in the operation 52.

In fact, each physical access request is placed in a request queue of the access manager 44 for execution in an operation 60. The access manager 44 may optionally include several queues, for example a queue per node with which it interacts.

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

For the execution of a given physical access request, the access manager 44 will determine a sequence of conditioned calls to its own elements and / or to other elements of access managers. controlling other storage units.

Figure 4 shows different elements of the access manager 44 to execute the physical access requests (hereinafter access requests). In the example described here, the access manager comprises a lock 80, an access actuator 82, a parity controller 84, a connector 86, a relay 88, and a manufacturer 90.

Constructor 90 is an element that receives data that describes an access request, and that constructs the execution sequence of the request. The constructor 90 starts from parameters describing the general state of the system, as well as data specific to the access request, such as the target address and the nature of the request. By parameters describing the general state of the system is meant any data that allows the manufacturer to determine if one of the storage units to which access is to be made to carry out the request is down, and if so which.

By nature of the request, we mean the concept of reading or writing seen above. Indeed, a read operation does not require data modification and can generally be processed with a simpler sequence.

From this information, the constructor 90 will apply a generic sequence schema taken from the parameters mentioned above, and particularize it with the particular case of this request.

The different generic schemes will be described with figures 7 to 11.

In the sequence established by the manufacturer 90, calls to the elements of the access manager 44 are provided in a chosen order. Calls to elements of another access manager 44 are also provided when it is necessary to access data located on a storage unit that is not managed by the current access manager 44. For any access request, the constructor 90 will receive from the virtualizer the address group corresponding to the physical address concerned.

This group of addresses is transmitted in a fixed order which corresponds to a classification of the addresses in the corresponding address group, for example that of the corresponding virtual addresses.

Thus, for two separate sequences, the constructor 90 will call the addresses of the corresponding address group according to the set order. The lock 80 is a critical element whose function is to prevent or free access to data on a storage unit. This element is critical because it helps maintain data consistency. As we have seen above and as it will appear better later, it is crucial not to modify certain data during a sequence. The lock 80 can perform strict locks, i.e. which exclude access to the locked data. Alternatively, the lock 80 may perform selective locks depending on the intended access for the locked data. Thus, a so-called read lock will allow the realization of another read lock. The access actuator 82 is the physical manager of the access manager 44. It is this element that will concretely go to read and write on the storage units controlled by the access manager.

The parity controller 84 is an element of the access manager whose function is to compute a parity data element. As will become apparent later, the constructor is arranged to generate sequences which, when necessary, generate parity data over the water. This reduces the amount of data that is transmitted and increases the resilience to failures. Connector 86 is an access manager element that allows communication between two access managers managing separate storage units for sharing data.

The connector 86 may be implemented in different ways.

In a first implementation, the connector sends direct mail from a source to a destination. This means that the source expects a receive buffer to be free on the destination to receive this send. This implementation is direct and inexpensive in communication, but it has weaknesses in the sense that, if the destination does not have a free buffer to receive the shipment, it will be lost and an error will be generated.

In a second implementation, the connector 86 will store a pointer to the resource it is trying to share, and share that pointer. Thus, the destination can come to consult this pointer and thus remotely access the resource. This implementation is less risky and a little more expensive in communication, and quite simple to implement.

Finally, in a third implementation, the connector 86 will create a space for the resource, and manage this space on the basis of a logical identifier. The connector 86 will transmit this logical identifier to the destination, which may use it to interact with the connector 86 and access the resource.

This implementation is more reliable than the second implementation, but it is a little more complex to implement.

The relay 88 is an element of the access manager whose function is to transmit a request state to another access manager, in accordance with the schema established by the sequence.

As will be seen below, the relay 88 can be implemented in many ways. Thus, the relay 88 may transmit a sequence between two access managers, or an indicator of progression of the sequence with the elements that made it possible to generate this sequence.

As discussed above, the use of parity storage represents a number of challenges to master.

The first of these challenges is to maintain data consistency. Indeed, consistency is fairly simple to maintain in a replication system, since all data is always duplicated. In addition, the duplicate data is impacted only by a modification of the data to which it corresponds.

In contrast, in parity systems, the parity data do not directly represent data. In addition, these data are frequently modified, since any write on one of the data of an address block will impact the corresponding parity data.

Many problems arise then, like the management of the competition of access to data of the same group of addresses. Indeed, as we have just seen, a modification 15 due to a writing of a data item impacts the parity data of the corresponding address block.

So if we try to write on two data of the same group of addresses, and if the operations are not synchronized correctly, there is a significant risk that the parity data is false, because based on an old version of the data which have just been written.

This relatively simple case is further complicated when a failure of a disk occurs during a write.

Solutions have been proposed to manage this type of problem. They are generally based on the synchronization of the storage units between them by a conductor. However this is heavy and inefficient. The Applicant has developed a much more powerful and reliable tool. From the foregoing it follows that: - each station stores an access manager which manages all accesses to the storage units of this station, 20 - the access managers are independent of each other, and - an access request is implemented by means of a state machine part of which is executed by each access manager concerned.

Thus, since access managers are decoupled, they can operate more freely. The state machine which defines the operations necessary to execute the request can thus be made in the form of a call sequence to the access manager, the progress in the sequence being able to be conditioned by the reception of the request. data from another access manager.

To operate independently as described above, the access manager executes the requests as a sequence of calls to the elements described above, based on a sequence state.

Figure 6 shows a generic scheme of processing a request by the access manager.

In an operation 100, the access manager receives an execution order of an access request (operation 60 of FIG. 5). Upon receipt of this order with the corresponding parameters described above, it calls the constructor 90 to establish the execution sequence of the request.

In an operation 102, a call timer is created. This counter indicates what is the index of the next call to be executed.

A call index and call execution incrementation loop follows, in which the access manager determines in an operation 104 the state of execution of the call corresponding to the index. current.

The execution state can take several values: - wait: state which means that the access manager must wait for data from another access manager or an activation signal, - ready: state which means that the call can be executed without jeopardizing the proper execution of the request, - finite: state which means that the last call of the sequence has been executed successfully and that the access manager can consider that the access request has has been executed, and - error: state which means that an unexpected event has occurred which compromises the correct execution of the request.

When the access manager receives from another access manager the data necessary to execute the call corresponding to the current index, the execution state goes from standby to ready. In this case, it is a remote operation performed on a remote access manager that causes the state change. For example, the unlocking of a resource by an access manager locker requires the receipt of the access manager's run-time acknowledgment information that follows it in the sequence. state can also be local, for example when an operation by an access manager requires data resulting from an operation of another element of the same access manager.

For example, calculating a parity piece by the parity controller requires the access actuator to read the data necessary for this calculation. This will be best seen in Figures 7-11.

Then in an operation 106, the access manager tests whether the execution state is finished or error. If this is the case, then the execution of the sequence is completed in an operation 108.

In the case where the state was finished, the access manager proceeds with the following sequence.

In the case where the state was error, the access manager recalls the constructor with this execution state, as well as with the original parameters of the access request, in order to reconstruct a sequence that makes it possible to carry out the original query taking into account the error state.

In the case where the state is waiting or ready, the loop continues in an operation 110 which tests this state.

In the case where the execution state is pending, the loop resumes with the operation 104 to determine whether the execution state has changed. Otherwise, the loop continues with an operation 112 in which the call corresponding to the current index is executed.

The call timer is incremented in an operation 114, and the loop resumes with the operation 104 to determine the execution state of the next call.

The administration module 46 is capable of handling the detection of other types of errors, such as the total loss of access to a disk due to a hardware or network failure.25 The accesses 44 concerned by such a failure receive from the administration module 46 an imperative order to stop current requests, and a set of access requests adapted to this situation is issued.

Of course, an access manager 44 can process several requests in parallel as long as they do not target locked resources.

Figures 7 to 11 will now be used to describe various types of sequences implemented by the access manager. In FIGS. 7 to 11, the sequences are represented by sequences of operations arranged vertically and in several columns.

A series of vertically linked operations indicates that these operations are performed by elements of the same access manager. Each column therefore indicates the operations to be performed by each access manager concerned by a given request.

The sequences of FIGS. 7 to 11 correspond to the following contexts: in FIG. 7, the operation is a read operation in which no error is present, that is to say that all the resources necessary for this reading is accessible and functional, - in FIG. 8, the operation is a read operation in which the storage unit on which the data to be read is located is inaccessible. It is therefore necessary to recover this data from the data of all the other addresses of this address group, and the corresponding parity data, - in FIG. 9, the operation is a write operation in which no error is present, that is to say that all the resources necessary for this writing are accessible and functional. It is therefore necessary to write the data concerned and modify the parity data accordingly. In FIG. 10, the operation is a write operation in which the storage unit on which the data to be written must be stored is inaccessible. . It is therefore necessary to calculate the parity data taking into account this writing from the data of all the other addresses of this group of addresses, and to write these new parity data, and 10 - in FIG. 11, the operation is an operation in which the storage unit on which the parity data is located is inaccessible. So you just have to write the data.

In what follows, reference will be made to the addresses that are associated with the address targeted by the request as a corresponding address group.

In what follows, in a given figure, an access manager may be designated both by its name (that is to say, access manager of the storage unit that stores selected data) than by its column number (for example, the first access manager is the one that corresponds to the first column, etc.).

The access manager that receives the request will be named initial access manager, and the access manager that manages the parity data storage unit will be named parity access manager.

In all figures, the leftmost column of operations represents the operations of the initial access manager.

The operations implemented by the initial access manager are the same for all the sequences: - initiate the sequence (reference 720, 820, 920, 1020 and 1120), - transmit the sequence to a concerned access manager (reference 722, 822, 922, 1022, 1122), and - terminate the sequence (reference 724, 824, 924, 1024 and 1124) on receipt of a corresponding acknowledgment of the manager to which the sequence has been transmitted.

In addition, although the access manager of the client issuing the access request is represented in the first column as the initial access manager, this initial access manager could also be involved in another column.

Indeed, an access request sending client can also store storage or parity data. In this case, its access manager plays a double role in the sequence.

In all the figures, the rightmost operation column represents the operations of the parity access manager, with the exception of Figure 7 where it is unnecessary and Figure 11 where it is inaccessible.

The operations implemented by the parity access manager are the same for all the sequences: - to initiate the sequence (reference 826, 926, and 1026), - to lock the access to the parity data for the other sequences (reference 828, 928, and 1028), - read the local parity data, as well as the parity data made available by the access manager who initiated the sequence (reference 830, 930, and 1030), - calculate the data parity updated on the basis of the read data (reference 832, 932, and 1032), - write the updated parity data (reference 834, 934, and 1034) to the leftmost access manager in the case of a read operation, and locally in the case of a write operation, - unlock access to the parity data for the other sequences (reference 836, 936, and 1036), - send an acknowledgment execution manager to the access manager who initiated the sequence 828, 928, and 1028), and finish the sequence locally (reference 840, 940, and 1040).

As has been described above, the transition from one operation to another is conditional on a change of state.

The change of state can be of two types: - remote, when it is an operation on another access manager which induces the change. This is for example the case for initialization and unlocking operations (except for the access manager of the storage unit that receives the parity data), - local, when it is an operation on the same access manager that induces the change. This is for example the case for read operations, parity calculation, writing (local or remote), and request transmission.

In the figures, a distant state change is symbolized by an arrow from one column to another, and a local state change is symbolized by a vertical arrow within a column.

As shown in the figures, each time an operation of a given access manager changes the state of another access manager, the next operation in the given access manager sequence is conditioned by a remote state change controlled by the other access manager. This ensures the robustness of the sequences.

It should be noted that the operations of each sequence can be composed of several calls to elements of the access manager concerned. Thus, the operations are grouped here by type of action.

In the following, reference will be made to a conventional or degraded reading (or writing) sequence. These two terms are in opposition to each other and denote a system failure state associated with these operations.

Thus, by classical means that the system is fully functional, and all resources are accessible. It is therefore an ideal state, free from any breakdown. By degraded is meant on the contrary that the system has undergone an identified failure, and the sequences are adapted to take account of this failure.

Figure 7 is a typical read sequence, i.e. when there is no problem and the storage unit on which the resource to be read is stored is available. As a result, only the access manager issuing the request and the access manager of the storage unit that stores the data to be read are involved.

Operation 722 then includes a call to connector 86, which will provide a location for receiving a remote write containing the read data.

Once the call to the connector 86 is made, the relay 88 transmits the read request to the access manager of the storage unit which stores the data to be read. The second access manager then performs the following operations: initialize the sequence locally (742), - call the locker 80 (744) to lock access to the data to be read for the other sequences, - call the access actuator 82 (746) to read the desired data, - call the connector 86 (748) with these data to carry out the remote write in the buffer opened by the operation 722, - call the lock 80 (750) to unlock the access to the data to be read for the other sequences, - call the relay 88 (752) to allow the initial access manager to proceed to operation 724, and - terminate the sequence locally (754). Figure 8 is a degraded read sequence, that is, the storage unit on which the data to be read is located is not accessible.

It is therefore necessary to read all the data of the other addresses of the corresponding address group, as well as the parity data to recover the data that one wishes to read.

In this figure, four columns appear: - the first column represents the operations of the initial access manager, - the second column represents the operations of the access manager of the storage unit which includes the first of the addresses of the group corresponding address, - the third column represents the operations of the access managers of the storage units that include the other addresses of the corresponding address group (the dotted lines are there to indicate that there are several), and - the fourth column represents the operations of the parity access manager.

As we will see, the sequences of the second and third columns are very similar.

The only difference between these sequences is that, for the second column, there is still no parity data portion. Therefore, the calculation of a new portion of parity data is not necessary, since it is the data of the corresponding address group that form the portion of parity data.

As for the normal read sequence, the operation 822 includes a call to the connector 86, which will provide a location for receiving a remote write containing the read data.

Once the call to the connector 86 is made, the relay 88 transmits the read request to the second access manager.

The sequence of the second access manager comprises the following operations: - initialize the sequence locally (842), - call the locker 80 (844) to lock access to the local data of the corresponding address group for the other sequences, - call the access actuator 82 (846) to read the local data of the corresponding address group, - transmit (850) the sequence to the third access manager, - call the locker 80 (852) to unlock the access to the data to be read for the other sequences, - call the relay 88 (854) to allow the initial access manager to proceed to operation 824, and to allow the third access manager to proceed to operation 872, and - terminate the sequence locally (856).

The operation 850 includes the call to the connector 86 to put the local address group data in a buffer available to the third access manager as a parity data portion. When this is done, the relay 88 is called to transmit the sequence to the third access manager.

The third access manager will then execute the following sequence: - initialize the sequence locally (858), - call the locker 80 (860) to lock access to the local data of the corresponding address group for the other sequences, 25 - calling the access actuator 82 (862) to read the local data of the corresponding address group, as well as the connector 86 to read the parity data portions of the access manager which initialized the local sequence, - call the parity controller 84 (864) to compute a new parity data portion, - transmit (866) the sequence to the next third access manager or, if they have all been called, to the parity access manager call the locker 80 (868) to unlock the access to the data to be read for the other sequences, - call the relay 88 (870) to allow the second access manager to proceed to the operation 852, o u the third previous access manager to proceed to operation 868, and to allow the next third access manager to proceed to operation 872, and - terminate the sequence locally (872).

The operation 866 is similar to the operation 850, and includes the call to the connector 86 to make the parity data portion available to the next access manager and then the call to the relay 88 to effectively transmit the sequence.

When all third access managers have initialized their sequence, the portion of parity data that has been calculated run-of-river contains data corresponding to the parity of all the data of the corresponding address group, at the same time. exception of access manager data of the non-accessible storage unit, and parity data.

The parity access manager (or fourth access manager) will then execute the sequence described above.

When the parity access manager has executed the operation 838, this changes the state of the last access manager initialized last, and allows the execution on it of the operation 868. Therefore, a wave the unlocking procedure goes up all the third access managers and the second access manager up to the initial access manager.30 Next, the operation 854 creates a counter-wave of the execution acknowledgment in the opposite direction, and allows terminating the sequence locally on the second access manager, the third access managers as well as on the parity access manager.

It can thus be seen that the sequence is executed by propagation from the left to the right of a portion of parity data which is computed over the water, with locking of the local data each time to preserve the coherence of the data.

When this calculation is done, we obtain the data that we want to read, and an unlocking wave followed by a counter-wave to locally complete the sequence on each of the access managers. This wave frees the buffers that have been opened for the execution of the sequences.

Thus, even if another failure occurred, it would be possible to resume the request on the basis of different buffers and locks made.

Although the impeachment wave and the impeachment counter-wave are represented in the sole operation 870, they represent two separate call-out operations 88, and this is the second call (the counter-wave) which triggers the termination of the sequence locally on the access managers.

Fig. 9 is a conventional write sequence, i.e. when there is no problem and the storage unit on which the resource to be written is stored is available. Therefore, only the initial access manager, the access manager of the storage unit that stores the data to be written and the parity access manager are involved.

In this figure, three columns appear: 30 - the first column represents the operations of the initial access manager, - the second column represents the operations of the access manager of the storage unit on which the resource to be written is stored, - the third column represents the operations of the parity access manager.25 As for the normal reading sequence, the operation 922 includes a call to the connector 86, which will make a slot available to the second access manager to access the data to write.

Once the call to the connector 86 is made, the relay 88 transmits the read request to the second access manager.

The sequence of the second access manager comprises the following operations: - initialize the sequence locally (942), - call the locker 80 (944) to lock the access to the local data of the corresponding address group for the other sequences, - call the access actuator 82 (946) to read the local data of the corresponding address group, as well as the connector 86 to read the write data of the initial access manager, - call the parity controller 84 (948 ) to calculate a parity data portion based on the local data of the corresponding address group and write data of the initial access manager, - transmit (950) the sequence to the parity access manager, - call the access actuator 82 (951) for writing to the storage unit concerned the write data of the initial access manager, - calling the locker 80 (952) to unlock the access to the data to li re for the other sequences, - call the relay 88 (954) to allow the initial access manager to move to the 924 operation, and the parity access manager to proceed to the 940 operation, and - complete the sequence locally (956).

Operation 950 includes the call to connector 86 to put the parity data portion in a buffer at the disposal of the parity access manager.

Then, in the operation 951, the access actuator 82 locally writes the initial access manager write data in place of the local data of the corresponding address group.

The order of operations 950 and 951 makes it possible to increase the parallelism of the execution of the sequence (as the parity manager can start working earlier). However, the order of these operations could be reversed.

When this is done, the relay 88 is called to transmit the sequence to the parity access manager. The parity access manager (or third access manager) will then execute the sequence described above. It should be noted that here, operation 934 consists in writing locally the new parity data that are drawn from the old parity data and the new written data.

Thus, even if a failure occurs, it would be possible to resume the request on the basis of the 15 different buffers and locks made.

When the parity access manager has performed the operation 938, this changes the state of the second access manager, and allows the execution on it of the operation 952.

This then causes the operation 954, which allows both the initial access manager and the parity access manager to terminate the sequence locally.

Fig. 10 shows a degraded write operation in which the storage unit on which the data is to be written is not accessible. It is therefore necessary to read all the data of the other addresses of the corresponding address group, as well as the parity data to store the data that one wishes to write in new parity data.

In this figure, four columns appear: - the first column represents the operations of the initial access manager, - the second column represents the operations of the access manager of the storage unit which comprises the first of the addresses of the corresponding address group, 25 - the third column represents the operations of the access managers of the storage units which comprise the other addresses of the corresponding address group (the dotted lines are there to indicate that there are several), and - the fourth column represents the operations of the parity access manager. As we will see, the sequences of the second and third columns are very similar.

The only difference between these sequences is that, for the second column, there is still no parity data portion. Therefore, the calculation of a new portion of parity data is performed by calculating the parity between the local data of the corresponding address group and the data to be written. As for the normal write sequence, the operation 1022 includes a call to the connector 86, which will make a slot available to the second access manager 15 to access the data to be written. Once the call to the connector 86 is made, the relay 88 transmits the write request to the second access manager. The sequence of the second access manager comprises the following operations: - initializing the sequence locally (1042), - calling the locker 80 (1044) to lock access to the local data of the corresponding address group for the other sequences, call the access actuator 82 (1046) to read the local data of the corresponding address group, - call the parity controller 84 (1048) to compute a parity data portion based on the local data of the corresponding address group and write data of the initial access manager, - transmit (1050) the sequence to the third access manager, 30 - call the locker 80 (1052) to unlock access to the local data of the group corresponding addresses for the other sequences, - call the relay 88 (1054) to allow the initial access manager to proceed to the operation 1024, and to allow the third access manager go to step 1072, and 5 - finish the sequence locally (1056).

The operation 1050 includes the call to the connector 86 to put the parity data portion of the operation 1048 in a buffer available to the third access manager. When this is done, the relay 88 is called to transmit the sequence to the third access manager.

The third access manager will then execute the following sequence: - initialize the sequence locally (1058), - call the locker 80 (1060) to lock access to the local data of the corresponding address group for the other sequences, call the access actuator 82 (1062) to read the local data of the corresponding address group, as well as the connector 86 to read the parity data portion of the access manager which initialized the local sequence, call the parity controller 84 (1064) to calculate a new portion of parity data, transmit the sequence to the next third access manager or, if all the third access managers have been initialized, to the manager parity access, 20 - call the lock 80 (1068) to unlock access to the local data of the corresponding address group for the other sequences, - call the relay 88 (1070) to allow the second access manager to proceed to operation 1052, or the third previous access manager to proceed to operation 1068, and to allow the next third access manager to proceed to operation 1072, and 25 - terminate the sequence locally (1072).

The operation 1066 is similar to the operation 1050, and includes the call to the connector 86 to make the parity data portion available to the next access manager and then the call to the relay 88 to effectively transmit the sequence. When all third access managers have initialized their sequence, the portion of parity data that has been calculated run-of-river contains data corresponding to the parity of all the data of the corresponding address group, at the same time. exception of access manager data of the non-accessible storage unit, and parity data. The parity access manager (or fourth access manager) will then execute the sequence described above.

It will be noted that here, the operation 1034 consists in writing locally the new parity data which are drawn from the old parity data and the new written data.

Since the storage unit that should store this written data is not accessible, it is the new parity data that represents this written data.

When the parity access manager has performed the operation 1038, this changes the state of the last access manager initialized last, and allows the execution on it of the operation 1068.

Therefore, an unlocking wave goes up all third access managers and the second access manager up to the initial access manager.

Then, the operation 1054 creates a counter-wave of the execution acknowledgment in the opposite direction, and allows the termination of the sequence locally on the second access manager, the third access managers as well as on the manager of the access manager. parity access. It can thus be seen that the sequence is executed by propagation from the left to the right of a portion of parity data which is computed over the water, with locking of the local data each time to preserve the coherence of the data.

When this calculation is made, the data that one wishes to write is obtained, and an unlocking wave followed by a counter-wave of locally terminating sequences makes it possible to release the buffers that have been opened for the execution of the data. sequences.

Fig. 11 shows a degraded write operation in which the parity data storage unit is not accessible.

Therefore, this operation is a simple write operation which only involves the initial access manager and the access manager of the storage unit on which the resource to be written is stored (hereinafter the second manager of the storage unit). This is very similar to Figure 9, except that all interactions with the parity access manager are removed.

As for the normal write sequence, the operation 1122 includes a call to the connector 86, which will make a slot available to the second access manager to access the data to be written.

Thus, the second access manager performs the following operations: - an initialization (1142) similar to the operation 942, - a lock (1144) similar to the operation 944, - a reading of the data to be written (1146) which comprises a reading of the data to write similar to that in the operation 946, but without the reading of the local data, - a writing of these data (1151) similar to that of the operation 951, - an unlocking (1152) similar to operation 952, a call to the relay (1154) similar to operation 954, and a local sequence termination (1156) similar to operation 956.

The sequences described with FIGS. 7 to 11 are easily adaptable to perform the parity synchronization and parity checking operations.

In fact, the parity synchronization involves the computation of new storage or parity data to update erroneous data, and the parity checking operation consists in calculating the parity portion for all the addresses of a group of parity. corresponding addresses, and to verify that it corresponds to the corresponding parity data.

The sequences described with FIGS. 7 to 11 represent an advantageous embodiment because they allow ordered locking and unlocking, distributed and propagated in chain.

More precisely, after the call to the first relayer, each subsequent call of a relayer implies a prior call to the locker of the access manager of this relayer. In addition, all locker calls for locking access to storage addresses including storage data are prior to a locker call to lock access to a storage address including the associated parity data. Finally, all locker calls to lock access to storage addresses are prerequisites for any call to a locker to unlock a storage address.

This ensures data consistency and avoids deadlock situations. More particularly, in the event of failure, data synchronization is guaranteed.

In addition, since the execution of the sequence is distributed over all the access managers, the client sending the request is no longer a point of which a failure is of consequence, and this failure can be better managed, as the sequences can end without the customer. This is particularly useful for fault management in the case where the client stores data from the corresponding address group of the sequence.

It also means that recovery of a client failure has a lower cost as it is sufficient for each sequence to resume where it left off without requiring resynchronization of the parity data.

In addition, this controlled propagation also allows a run-of-the-water calculation of the parity data portions. This makes it possible to distribute the computing load between the various servers, which is interesting for the management of complex parities. It also helps to spread the communication load associated with parity operations.

This is also favorable for exceptional situations such as degraded operating modes, or reconstruction and synchronization verification (coherence) phases, as these operations impact all access managers of a corresponding address group. given. In addition, the double acknowledgment mechanism and the termination of the request in the event of a breakdown increase the reliability and the robustness of the system.

Finally, these sequences could be adapted to parity-like error correction methods mentioned above as complex parities, such as Reed-Solomon codes or LDPC codes (eg Gallager).

These codes differ from the parity described above by the fact that they involve several parity data for each group of addresses, and only one as described above.

However, the principles described here, such as the locking order (data before parity) and unlocking (not locking after unlocking), as well as the propagation rules of the sequence on the access manager could be applied in a similar.

It would be possible to lighten some of the sequences, for example by removing the principle of double acknowledgment.

It would also be possible to reduce the latency by transmitting the sequence each time very soon after the lock, for example just after locking.

This would in fact make it faster to initialize the corresponding address group local data readings by each of the access managers.

Indeed, an advance transmission makes it possible to partially parallelize the execution of the sequence locally by the different access managers, while maintaining the coherence of the data.

It is also expected that the connector 86 provides data for remote reading, or on the contrary written remotely depending on the situation.

In the case of reading data, remote writing is interesting because it reduces latency. However, it would be possible to operate in remote reading from the initial access manager. This variant can be interesting because it then allows a client to manage the network load associated with these sequences.

Indeed, some sequences can induce significant communication flows, and it may be interesting to let the client choose the scheduling of requests involving network communications, rather than let a multitude of servers drown out the requests.

As regards the propagation of the portions of parity data, it is the remote reading which is interesting because it does not require the opening, in advance, of a space for storing these data.

However, in particular in the variant of forward request transmission, it would be possible to implement a remote write, providing that it is triggered after the provision of the corresponding memory space on the access manager side target.

On the other hand, although the use of remote write and read is here described to save buffers, it would be possible to replace them with sendings and receptions, with proper dynamic buffer management.

When the constructor of an access manager is called by a relay, the role of this constructor is limited to an instantiation on the access manager of the received sequence.

It also appears that a request is associated with a sequence, which is itself composed of essentially independent local sequences.

It follows from this that, in a variant, the constructor of each access manager could construct the local sequence on receipt of a message from a relayer. This construction can be almost total, that is to say that the constructor receives only a minimal number of information, such as an indicator of the access manager who called it, an indicator of the manager of next access, and a role indication (such as column number and type of operation). Several embodiments have been described above, with optional features. Whenever possible, the combination of these features with each of these embodiments has been described. However, it is the combination of the features of the described embodiments that is within the scope of the invention.

It should therefore be understood that all combinations of the embodiments between them and optional features are described in the present description, as well as their equivalents, even when this has not been explicitly described for the sake of simplicity.

Furthermore, the invention also relates to a data management method, applicable in a network comprising several data storage stations, comprising the following steps:

at. issuing a file request from a station, based on a representation in the form of virtual addresses, said virtual addresses being associated by group with given storage addresses to store the corresponding storage data as well as parity data ,

b. based on said address group association, determining the storage address corresponding to said virtual address, as well as the storage address group storing the storage data and the parity data, c. issuing an access request designating said storage address to an access manager of the station issuing the request, d. executing said access request by constructing an ordered sequence comprising, for each access manager concerned, one or more operations selected from the group which comprises: - locking or unlocking access to a storage address managed by the access manager, - access to a storage address managed by the access manager, - a calculation of parity data, - an exchange of data with another access manager, and - a data transmission. to another access manager, said sequence comprising at least one transmission of request data from the access manager of the sending station of the request to another access manager, and, for each subsequent transmission, a lock access to an address accessed by the access manager concerned.

This method further provides that: * all locks of access to storage addresses including storage data are prior to locking access to a storage address including the associated parity data, * all locks access to storage addresses is required prior to any unlocking of a storage address, and * after each transmission, locking of access to a storage address is performed by the called access manager.

Claims (8)

Revendications1. Computer tool for storing data in a network of stations, each station comprising one or more storage units (38), at least some of which have storage addresses adapted to receive storage data and parity data, the tool being implanted on each station and comprising on the one hand a virtualizer (36) associating virtual addresses and storage addresses, and on the other hand an access manager (44) to the storage addresses of this station, characterized in that The virtualizer (36) maps a group of virtual addresses and a group of storage addresses to store the corresponding storage data and parity data, the storage addresses of each group being distributed over separate storage units (38), * the access manager (44) comprises the following elements: - a lock (80), arranged to lock or unlock er access to a storage address on a storage unit (38) of the station on which the tool is implanted; - an access actuator (82), arranged to perform an access to a storage address on a unit storage device (38) of the station on which the tool is implanted; - a parity controller (84) arranged to compute parity data; - a connector (86) arranged to allow data exchange between the access manager and another access manager, - a relayer (88), arranged to transmit characteristic data of an access request, from the access manager to another access manager, - a manufacturer ( 90), arranged to construct, from access request data to a storage address, an ordered sequence of calls of at least some of the elements of the access managers of the stations comprising the storage addresses of the group d. addresses designated by said access request, said ordered sequence comprising at least one call to the relayer (88), and comprising, for each subsequent call of a relay (88), a prior call to the locker (80) of the access manager (40) of this relay ( 88). 2. Tool according to claim 1, characterized in that the constructor (90) is arranged to construct a sequence in which: all the calls to the locks (80) to lock access to storage addresses comprising data of storage prior to a call to the lock (80) to lock access to a storage address including the associated parity data, and - all locker calls (80) to lock access to storage addresses are preconditions any call to a lock (80) to unlock a storage address. 3. Tool according to claim 2, characterized in that the manufacturer (90) is arranged to construct a sequence in which, after said at least one call to the relayer (88), the target access manager (44) calls its locker (80) to lock access to a storage address. 4. Tool according to claim 3, characterized in that the constructor (90) is arranged to construct a sequence in which, when a relayer (88) calls the access manager (44) which manages the access to the data of parity, the sequence comprises a call to the following elements of this access manager (44): the lock (80) for locking the address of the parity data, the access actuator (82) for reading the data of parity, at the connector (86) for reading a parity data portion, at the parity controller (84) with the parity data and the parity data portion, at the access actuator (82) or at the connector ( 86) for writing data from the parity controller (84), the lock (80) to unlock access to the parity data, and the relay (88) to transmit an execution acknowledgment. 5. Tool according to claim 4, characterized in that the manufacturer is arranged to construct a sequence in which each call to the lock of a given access manager is followed by at least one call to the access actuator of the manager. given access to read storage data associated with the locked storage address, a call to at least one element of the given access manager, selected from the access actuator, the parity controller, and the connector , and a call to the locker of the given access manager to unlock the locked storage address. 6. Tool according to claim 5, characterized in that the constructor (90) is arranged to construct a sequence in which the call to the lock (80) of a given access manager (44) is followed by the call. the relay (88) of said given access manager (44) for transmitting an execution acknowledgment to the access manager (44) of the relay (88) who called the given access manager (44). 7. Tool according to claim 6, characterized in that the manufacturer (90) is arranged to build a sequence in which the call to the lock (80) of an access manager (44) other than the one that manages the access to the parity data is conditioned by the receipt of an execution acknowledgment from another access manager (44). 8. Tool according to claim 6 or 7, characterized in that the manufacturer (90) is arranged to construct a sequence in which the receipt of the execution acknowledgment by the access manager (44) of the relayer (88) who called the given access manager (44) is followed by the relayer call (88) to transmit a counter-acknowledgment to the given access manager (44).