Apparatus and Method for Fast and Stable Data Storage

The present invention relates to processing data or information, and more particularly to storage thereof, when said storage has to be performed with a high degree of security.

In numerous applications, and in particular those related to distributed computing, it is desirable to have stable memories available.

A stable memory is a data storage device which possesses the following properties: firstly, the physical storage of information is stable, i.e. information does not tend to disappear with passage of time; and, secondly, the operation of writing is capable of being made "atomic", i.e. once information has been presented for writing, onc can be certain that the information is correctly written or else it is not written at all.

At present, stable memories are made from disks. Although disks do not directly provide stable data storage, they enable such stable storage to be obtained, in particular by conjoint use of two disk units. However, this method of proceeding has drawbacks. The first drawback is that the access time to a disk memory is not short enough for a stable storage unit based on disks to be considered as being a fast memory. The other drawback is that the stable character of the memory is obtained by copying the same information into both disk units. The controlling processor uses its own read/write memory to perform this double copying operation. As a result, if an error occurs in said processor between writing to one of the disks and writing to the other disk, the stable character of information storage is compromised.

The present invention solves these drawbacks, by providing firstly a memory (or data storage) device having fast access and capable of offering stable storage, and secondly by avoiding as much as possible any use of the processor's read/write memory for copying information into two different sections of memory.

The proposed data storage apparatus comprises, in combination:

a series of n banks of non-volatile memory which are externally addressable and which are provided with selective write or read controls; and

key access means suitable for defining keys designating each of the memory banks and for subsequently responding to the insertion of one of the keys accompanied by a write or a read request by selectively authorizing writing or reading in a manner which is applicable to the single memory bank defined by the said key, said authorization being destroyed after any memory bank has been addressed or after any new key has been inserted, thereby enabling each of the n memory banks to be used independently and successively by different processes without any risk of uncontrolled access.

In an advantageous embodiment, the key access means comprise:

an access table having P n-bit cells, each cell being capable, as a function of its index k, of receiving or of delivering at the output from the table a byte having not more than one bit which is different from the others; and

a series of n access entitlement registers respectively connected to the n outlets from the access table, said registers enabling one additional register designated by the different bit of the byte defined by the current index, each register possessing at least three states, including a rest or no access entitlement state, together with two access entitlement states for writing and reading respectively, which states can only be taken when the register is enabled.

With each memory bank being associated with a respective one of the registers in such a manner as to respond to external addressing only if a write or a read access entitlement has been noted in the associated register.

Preferably, the outlets from the access entitlement registers are applied to two multiplexers respectively for writing and for reading addresses in accordance with the number of the memory bank being addressed, write or read authorization being given to the memory banks by the outlet from the write multiplexer or from the read multiplexer, as the case may be.

The invention also provides a method of transferring data between a processor and a data storage device as defined above. The processor is deemed to be required to run a plurality of independent processes. The method comprises the following operations:

(a) on each request for new memory from a process, allocating to said process a free bank of memory of rank noted i, and seeking a key k associated with the rank 1 of the bank, then communicating to said process only the key k and the physical address of the bank; and

(b) only performing a write or a read operation for said process when said operation is preceded by an access opening instruction including the key k attributed to the process and the nature (writing or reading) of the operation, which has the effect of authorizing physical access to a single designated bank for writing or reading, as the case may be.

It may happen that several processes have to share the same memory bank. In this case, in addition to the said key giving access to the information storage apparatus, the processor attributes respective encrypting keys to each of the sharing processes in their work spaces, each of which encrypting keys is associated with the address of the zone reserved for the process as encrypted by said key.

Very advantageously, each process is associated at the same time with a pair of zones belonging to two distinct memory banks: each write operation comprises writing into one of the zones whose register is in write access, while the register of the second zone is not in access, and then copying the first zone into the second zone with the first zone register being in read access and the second zone register being in write access, whereafter both registers return to the no access state: reading is performed in both zones, and it is essential that they both give the same result.

In order to obtain atomic writing, when an anomaly occurs while writing to the first zone, writing is stopped, and on being restarted the second zone is copied back into the first, such that the write operation does not take place; whereas if an anomaly occurs while the first zone is being copied into the second, writing is stopped, and on restarting the first zone is copied again into the second, such that the write operation is performed.

In some applications it is desirable for the processor to be associated in this manner to a memory unit having two stable type disks. In which case only data taken from the fast data storage apparatus is transferred into the disk memory unit.

Other characteristics and advantages of the invention appear from the following detailed description and the accompanying drawings, in which:

FIG. 1 diagrammatically illustrates a processor associated with a fast stable memory and with a disk unit;

FIG. 2 diagrammatically illustrates the general structure of the fast stable memory;

FIG. 3 illustrates a transaction system employing distributed computing with stable memories;

FIGS. 4 and 5 illustrate in more detail one embodiment of a stable fast memory; and

FIGS. 6 and 7 are two flowcharts applicable, in particular, to the transaction system of FIG. 3.

The drawings show objects of specific character. They are to be considered as being incorporated in the description to contribute to defining the invention.

In what follows, reference is made to various documents which are referenced as follows:

(BANA-82)--BANATRE M., LAPALME G. ENCHERE: A Distributed Auction Bidding System. 3rd Int. Conf. Distributed Computing System (Miami, October 82), pp. 833-837.

(GRAY-78)--GRAY J. N.

Notes on Database Operating Systems. LCNS 60, Springer-Verlag, (1978), pp. 393-481.

(GIFF-82)--GIFFORD D.K.

Information Storage in a Decentralized Computer System.

CSL-81-8, Xerox Palo Alto Research Center, March 1982.

(LAMP-76)--LAMPSON B. W., STURGIS H.

Crash Recovery in a Distributed Data Storage System.

Working Paper, Xerox PARC, November 1976.

The present invention is particularly applicable to a decentralized commercial transaction system using distributed computing means. Some of the aspects required by such a system have already been described (BANA-82).

In outline, the idea is to enable members of an organization which includes sellers and buyers to perform commercial exchanges, e.g. in the "Dutch clock" manner. In logic, the entity which models a commercial exchange is the transaction.

Generally speaking, transactions are deemed to possess three essential properties (GRAY-78):

(i) consistency or coherence: the transactions must obey legal protocols;

(ii) atomicity: a transaction either takes place or it does not take place; and

(iii) durability: once a transaction has been validated, it can no longer be cancelled.

The basic structure of a transaction system is shown in FIG. 3. It comprises a series of application processors AP which process transactions. The users, buyers or sellers, may communicate with the system defined by said application processors via work positions (WP), whose purpose is to enable buyers and sellers to participate in transactions. All the application processors AP are connected via intercommunication means or a communications machine MC. This enables users to join and leave the system and also to communicate information thereto.

The physical embodiment of the communication machine (MC) may take various different forms, such as a local network or a plurality of local networks interconnected by means of a national network (e.g. Transpac).

The system hereinafter referred to as ENCHERE is made up of two levels, namely the machine level and the application level.

The machine level comprises sites Si each of which is arranged about an application processor AP, work positions WP and the communications machine MC.

When considering a particular work position (e.g. WP.sub.i) belonging to a site S.sub.j, i.e. connected to application processor AP.sub.j, the workstation WP.sub.i sends orders to the site S.sub.j which interprets the orders. In said orders, a "new sale" causes a new transaction to be initiated. In order to perform this new transaction, several processes are created, one at the seller site, and the others at the buyer sites. One of the processes, the co-ordination process, represents the seller; the others, slave processes, represent the buyers who are going to participate in the sale. Such a group of processes co-operating for the purpose of performing a common task, in this case the sale of a product, is called an "activity". Naturally, several activities may take place at the same time.

Such a system constitutes an example of the case where two types of anomaly may occur:

anomalies due, for example, to software which may lead to undesirable actions, in particular actions having the result of uncontrolled access to memory; and

various types of hardware anomaly, of which the simplest is loss of electrical power, and which may also have the result of uncontrolled access to memory.

The invention solves the problems explained above by means of a particular stable memory, together with optional additional means.

A stable memory (LAMP-76) is an information medium which possesses two essential characteristics:

(i) a non-volatile physical medium; and

(ii) atomic read and write operations.

Generally, the physical medium used for constituting a stable memory is a disk. Although it does not intrinsically possess characteristic (ii), it may be programmed to possess said characteristic.

In the ENCHERE system, each application processor AP (FIG. 1) is equipped with a stable memory which contains:

the activity process stable variables which are modified by performing interleaved atomic activities and which are destroyed when the creating process is terminated, e.g. the variable representing EA(V) at a seller site process, where EA(V) designates the set of buyers associated with a given seller for a given transaction; and

objects (of the type "file") whose lifetime is greater than the atomic acitivity process which have access thereto and which modify them. A list of lots for sale constitutes an example of such an object.

Given that it is unrealistic to store stable variables on a disk, mainly because of the access time, the stable memory comprises two levels:

a stable fast access memory (MRS) constituted by means of a non-volatile read/write memory, for storing stable variables; and

a disk unit (UD) which contains the objects.

The fast stable memory is the first essential contribution of the invention.

The fast stable memory (FIG. 1) is a part of the address space of the application processor AP.

The contents of the stable variables of a process running on a processor AP is vulnerable to unforeseeable behaviour of the processor resulting from a hardware fault (loss of power, . . . ) or from a software fault (violation of memory protection, . . . ). To cope therewith, the invention proposes a memory MRS provided with hardware and software protection mechanisms described below. Preferably, the processor AP also uses a disk memory unit UD, as indicated above.

The stable fast memory MRS is constituted by 8 memory banks. Read or write access to each of these banks is protected by a key. This is illustrated in FIG. 2.

In this figure:

Bi, i.epsilon.[1,8] represents a memory bank, with the size of such a bank being fixed at 8 K 8-bit bytes, for example;

Ri, i.epsilon.[1,8] is a 2-bit register associated with bank Bi, it contains current access entitlements for the bank. (00: no access, 01: read access only, 10: write access only, 11: read and write access); and

AT is an access table with p=8-bit bytes. Bit j of byte k in this table is set to 1 if bank j of the memory is addressable. k constitutes the hardware key for access to bank j.

Elementary access to the stable fast memory MRS is described below:

a process P in processor AP which seeks to use a memory bank must initially acquire the bank by executing an "Allocation" primitive. The effect of this primitive in processor AP is as follows:

a free bank Bi, i.epsilon.[1,8] is allocated;

a free inlet k to the table AT is sought, and bit i of AT[k] is set to 1; and

the data pair (adr,k) is delivered to P, where ADR is the physical address of the bank and k is the access key to said bank.

P may only copy the content of a register reg to address y in MRS by executing the following pair of instructions: open (k,E); write (reg,x), where x represents the address y followed by the word to be copied.

Execution of the operation open has the effect of changing the register Ri associated with the bank Bi (pointed to by AT[k]) with a "write" access entitlement.

Execution of the operation write (reg,x) only copies the contents of reg to address y in the stable fast memory MRS if y is the address of a byte in Bi; otherwise the operation is refused. After the operation has been executed, the bank Bi is no longer accessible and the contents of Ri is "no access".

Read processing is similar to write processing, and requires the pair of instructions: open (k,l); read (reg,x).

The operations of reading or writing in a zone of stable fast memory are now described.

The operations of reading or writing in a zone of stable fast memory MRS are performed on the basis of elementary read or write accesses, each of which is preceded by an open operation.

In the following description it is supposed that the bank is open for writing (or reading) if a write (or read) operation in the zone is taking place.

Hardware access protection mechanisms described above ensure firstly that no direct access may be performed to a memory bank, and secondly that all access thereto is heavily verified by means of access keys.

These mechanisms which are satisfactory provided a bank is accessed by one process only, are no longer satisfactory if a plurality of processes share the bank. Additional means are therefore provided to prevent one process accessing a bank from damaging a zone belonging to another process in the same bank.

The protection mechanism associated with bank sharing is now described: two processes P1 and P2 share a common bank of the stable fast memory (hereinafter referenced MRS).

The invention provides a software mechanism which detects illegal access by P1 to the data zone belonging to P2, and vice versa. The solution proposed uses encryption (GIFF-82).

The processor system AP delivers to each process (which reserves a zone in the memory MRS) a pair of data items comprising an encrypting key and the zone address encrypted using said key.

Any subsequent access to said zone can only be performed by a process which possesses said pair of data items. Any attempt at decrypting that leads to failure causes a fault which is detected by the system.

All accesses defined so far have concerned only writing and reading in a zone of a bank in the MRS. There now follows a description of atomic read and write operations on the stable fast memory PRS.

The system allocates to each process P running on the application processor a pair of zones (Zi, Zj) belonging to two distinct banks Bi, Bj, such that a stable variable used by P is always represented by two copies in two independent banks.

A--Atomic writing of a stable variable V from P into MRS.

Let Vi and Vj be the addresses at which V is copied in banks Bi and Bj, then writing is described by the following algorithm:

1--Bi open for writing--no access to Bj;

2--write V into Vi;

3--Bi open for reading--Bj open for writing;

4--write Vi into Vj; and

5--no access to Bi--no access to Bj.

This algorithm ensures that at the end of step 5 both copies Bi and Bj of V in MRS are identical. This would not be the case if the write operation consisted in writing V into Vi and then writing V into Vj, since the copy of V in memory could be modified due to anomaly occurring between the two write operations (steps 2 and 4).

Supposing that an anomaly occurs during step 2, in this case V is not written into Vi. The recovery mechanism implemented by the system ensures that the bank Bj is copied back into the bank Bi on restarting. The atomic writing of V into MRS has not taken place.

Supposing that an anomaly takes place in step 4, the copy of Vi to Vj does not take place. On restarting, Vi is recopied into Vj and Vi is thus effectively written into Vj. Atomic writing of V into MRS has been performed.

It should be observed that: proper operation of the above algorithm supposes that the passage from the state (Bi write open--Bj read open) to the state (Bi read open--Bj write open) is indivisible. Otherwise, on restarting after an anomaly, the bank Bj (or Bi as the case may be) which is write open is considered as being inconsistent and cannot be used for reinitializing the other bank Bi (or Bj as the case may be).

B--Atomic reading of a variable V in MRS.

Reading is described by the following algorithm:

1--Bi open for reading--Bj open for reading;

2--if co the contents of Vi and Vj are equal co (where the symbols co delimit a comment which relates to a series of test operations that are easily performed).

Then:

co Vi is copied into V (into read/write memory) co else

co fatal error, an abnormal modification of Vi or of Vj has not been detected co endif.

3--Bi no access --Bj no access.

If an anomaly occurs during phase 2, the operation is restarted at phase 1.

Reference is now made to operating the disk unit (UD) which preferably accompanies the stable memory MRS (FIG. 1).

The only objects to be transferred from the address space of the processor AP to the disk unit UD belong to the memory MRS. The algorithms used for reading or writing an object in or to the UD are similar to those described in (LAMP-76).

The fact that only objects situated in MRS may be written to UD ensures that the two copies OD1 and ODA of an object O in UD are identical (providing writing takes place properly). This is because objects O in MRS are protected against uncontrolled access. This is not the case in (LAMP-76) where the object copied to disk is in read/write memory and is thus capable of being modified between two write operations to the disk.

In conclusion, it appears that the stable fast memory proposed herein has the following important advantages:

performance: access time to information stored in MRS is very fast, and is only twice as long as access time to information of the same size stored in read/write memory. This access time is much shorter than the access time generally obtained for stable memories based on a disk. By way of comparison, the time taken to write 256 8-bit bytes using an I 8086 processor into the MRS is 0.5 ms, as compared with 9 ms for a disk system DFS in conjunction with Altos processors;

security: the MRS is protected against any attempt at erroneous access while being updated; and

atomicity: both in writing and in reading, atomicity is provided by the means described above.

There follows a description of one particular embodiment of a fast stable memory given with reference to FIGS. 4 and 5.

Inlets constituting primitive "allocate" or "open" instructions, as the case may be, are applied in the form of eight wires to an inlet buffer 40. Five outlet wires from the inlet buffer 40 are used for addressing the access table 41.

The other three outlet wires from the buffer 40 are applied initially to a decoder 42. The decoder 42 is a 3 to 8 decoder and thus has eight outlets which serve as data inlets to the access table 41. Thus, the allocation instruction serves both to define the index k by the addresses to the access table 41, and to load a key via the decoder 42. In the key only one bit is set to 1 and the rank i of that bit corresponds to the free bank Bi attributed to the process in question.

The eight inlets/outlets of the access table 41 are also applied to respective gates 43 which, together with n pairs of bistables 44 constitute the above-mentioned registers Ri.

For an "open" instruction, the key K is communicated as an address to the access table 41 as before. Instead of being applied to the decoder 42, two of the three other wires from the buffer 40 are applied to the bistables 44, with each wire being connected to a respective one of the two bistables in each pair. In response to the address information applied thereto, the access table delivers a 1 bit on a single one of its eight outlets. The gates 43 then enable only one of the pairs of bistables 44, and only that pair can receive the write or read order as transmitted over the two lines going from the buffer 40 to the bistables 44. The primitive open instruction is thus recorded in the bistables 44.

The outlets from the bistables 44 are grouped together with one of the groups concerning the write bistables and the other the read bistables. The group of lines relating to the write bistables is applied to a write multiplexer 45. The group of lines leaving the read bistables is applied to a read multiplexer 46. Both multiplexers receive the more significant bits of the memory bank addresses (i.e. the bits representative of the bank numbers), with said more significant bits being conveyed by lines referenced ADMSB. Finally, the write and read multiplexers 45 and 46 respectively supply the write and read authorization signals respectively referenced WSEL and RDSEL.

In FIG. 5, a buffer marked 50 receives the read signal RDSEL. The memory banks B1 to B8 are designated by numerical references 51 to 58. The address lines common to all of the banks marked ADBM are applied to the memory banks 51 to 58. The above-mentioned signal ADMSB is applied to a decoder 59 which activates only one of the banks B1 to B8. Each of these banks additionally receives a write authorization WSEL (if one exists). Finally, the data outlets from the banks 51 to 58 are applied in common to the buffer 50. The buffer 50 may deliver said data as a data outlet signal DD under the control of the read authorization signal RDSEL.

It can now be seen that a write or read order concerning one of the memory banks is only performed if the address contained in said order corresponds to the address as defined by the preceding open order, as stored in the bistables 44 and as applied to the various memory banks via the multiplexers 45 and 46.

There follows a description of an advantageous example of a "commit" protocol, which highlights the usefulness of stable memories. It is recalled that a single activity requires a co-ordinating process associated with a seller to act in conjunction with slave processes associated with buyers.

Generally speaking, the slaves send a "ready to commit" message to the co-ordinator. Once all of the slaves have sent this message, the co-ordinator can take a commit decision.

If one (or more) slave makes a request to abort the activity, the co-ordinator proceeds to abort said activity. The flowchart of the co-ordinating process is shown in FIG. 6.

A prelude, at step 60, is concerned with allocation of resources, and in particular with the allocation of channels. The "action" step 61 analyzes the orders coming from other processes. A specific sequence of instructions is performed as a function of these orders. Then, at step 62, the co-ordinator receives "ready to commit" messages from the slaves. When it has received all of these "ready to commit" messages, the co-ordinator may decide (step 63) to proceed with commiting (by sending "commit" messages) and then with commiting its own objects. If at least one of the slaves has had difficulties (was not able to send the "ready to commit" message), the co-ordinator sends an "abort" message to all of the slaves and erases its own temporary version (step 64). Otherwise, the temporary version becomes final at step 64.

The allocated resources are released during a "postlude" step 65.

Arrows C.sub.i designated checkpoints where the status of the process is saved. If an anomaly occurs between C.sub.i and C.sub.i+1, the process is restarted at point C.sub.i. Once The postlude has been started, it must be finished even if several attempts are necessary (the postlude is idempotent). FIG. 7 is a flowchart of a slave process. Steps 70 to 76A or 76B can be understood from the flowchart of the co-ordinating process. The existence of the same process-saving points C.sub.i (with I going from 0 to 5) and the existence of a switch depending on whether a process is committed or aborted should be observed.

Behaviour in the event of an anomaly is interesting.

The co-ordinating process has the role of:

detecting bad slave operation (as seen from a suitable distance); and

committing or aborting activities.

An anomaly may occur before or after an activity has been committed.

If an anomaly occurs before an activity is committed, the system starts from the image of the process as saved in stable memory and performs the following actions:

the prelude of the co-ordinating process is re-performed, thereby re-allocating the required resources (channels, etc.) to enable the processes to interact;

local variables are reinitialized from information stored in stable memory; and

the co-ordinating process is restarted from point C.sub.i, which is the last checkpoint performed by the co-ordinating process prior to the anomaly.

The co-ordinating process may suffer from an anomaly after taking the decision to commit activities. If the anomaly occurs while the co-ordinating process is sending activity-committing signals to the slaves, the system performs the following actions:

the co-ordinating process prelude is executed; and

the system restarts from checkpoint C.sub.5.

If an anomaly occurs prior to an activity being committed, the reaction of each slave process is similar to that of the co-ordinating process described above.

If an anomaly occurs after the pre-committing message has been sent, the slave process in question re-executes its own prelude and then waits for a committing signal from the co-ordinating process.

It may be observed that the slave processes may either receive "abort" messages from the co-ordinating process, or else they may commit "suicide".

This brief description of the ENCHERE system shows the advantage of stable memories, together with their role in the protocols required for committing activities.