System for database integrity with multiple logs assigned to client subsets

Claims

We claim:

1. A method of distributing log entries of transactions initiated by a plurality of clients commonly accessing at least one database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients, each of said plurality of clients commonly accessing said at least one database, each of said plurality of clients initiating transactions with said at least one database, each of said subsets including at least one of said plurality of clients;

providing in a first memory means a different transaction log buffer associated with each one of said plurality of subsets of clients; and

for each transaction of one of said plurality of clients, storing a transaction log entry in said different transaction log buffer associated with the subset of clients that includes the client that initiated said transaction.

2. The method of claim 1 further including the steps of:

providing in a second memory means a transaction log for each transaction log buffer;

storing said transaction log entry in said transaction log.

3. The method of claim 2 further including the step of providing, in a third memory means, a cache buffer; said cache buffer for storing a copy of a data block from said database upon which a transaction is executed.

4. The method of claim 1 wherein said first memory means comprises a random access memory (RAM).

5. The method of claim 2 wherein said second memory means comprises a disk drive.

6. The method of claim 1 wherein each said transaction is associated with a data block, said data block being a subdivision of said database.

7. The method of claim 6 further including the steps of:

providing a sequence number for each said data block;

incrementing the sequence number associated with said data for each transaction changing said data block.

8. The method of claim 7 further including the steps of:

providing an incarnation number for each said data block:

increasing said incarnation number associated with said data block for each transaction changing said data block, said changing being an initializing of said data block:

setting said sequence number for said data block to an initial value when said incarnation number is increased.

9. A database system comprising:

first storage means for storing data blocks, said data blocks being subdivisions of a database;

a plurality of clients, each client of said plurality of clients commonly accessing said database, each client of said plurality of clients initiating transactions with said database:

first and second subsets of said plurality of clients each of said subsets of clients having at least one client of said plurality of clients, clients of said first subset not being clients of said second subset;

cache buffer means coupled to said first storage means and to said first and second subset of clients, said cache buffer means for storing copies of said areas of data from said first storage means;

first and second transaction log buffer means coupled to said first and second subsets of clients respectively, said first and second transaction log buffer means for temporarily storing a log entry for each transaction initiated by a client of said first and second subset of clients respectively.

10. The database system of claim 9 further including:

first and second log storage means coupled to said first and second log buffer means respectively for permanently storing a log entry for each transaction of said first and second subset of clients respectively.

11. The database system of claim 9 wherein said first storage means comprises a disk drive.

12. The database system of claim 9 wherein said cache buffer means comprise random access memory (RAM).

13. The database system of claim 9 wherein said first and second transaction log buffer means comprise random access memory (RAM).

14. The database system of claim 9 wherein each of said data blocks includes a sequence number.

15. The database system of claim 14 further including sequence number incrementing means for incrementing a sequence number associated with said data block for each transaction changing said data block.

16. The database system of claim 15 wherein each of said data blocks further has an associated incarnation number.

17. The database system of claim 16 further including incarnation number increasing means for increasing an incarnation number associated with a block of data for each transaction initializing said data block.

18. The database system of claim 17 wherein said sequence number incrementing means sets a sequence number of a data block to a first value when the incarnation number of said data block is increased.

19. A method of providing a log of transactions of a plurality of clients accessing a database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients all accessing a single data abase, each of said subsets including at least one of said plurality of clients, each of said subsets having an associated log;

initiating a transaction on an original data block of said database by a client of one of said subsets of clients;

providing a copy of said data block to a cache buffer;

executing said transaction on said copy of said block data;

storing a transaction log entry of said transaction in a temporary memory means.

20. The method of claim 19 further including the step of storing said transaction log entry of said transaction in a permanent memory means.

21. The method of claim 20 wherein said permanent memory means comprises a disk drive.

22. The method of claim 19 wherein said temporary memory means comprises a random access memory (RAM).

23. The method of claim 19 further including the step of writing said copy of said data block over said original data block in said database.

24. The method of claim 19 further including the steps of:

providing a sequence number of said data block;

incrementing the sequence number associated with said data block for each transaction changing said data block.

25. The method of claim 24 further including the steps of:

providing an incarnation number for said data block;

increasing said incarnation number associated with said data block for each transaction initializing said data block;

setting said sequence number for said data blocks to an initial value when said incarnation number is increased.

26. A database system comprising:

first storage means for storing data blocks, each of said data blocks having a sequence number

first and second subsets of clients accessing a single database, each of said subsets of clients having at least one client;

cache buffer means coupled to said first storage means and to said first and second subset of clients respectively, said first and second cache buffer means for storing copies of said data blocks from said first storage means;

first and second transaction log buffer means coupled to said first and second subsets of clients respectively, said first and second transaction log buffer means for temporarily storing a log entry for each transaction of said first and second subset of clients respectively;

first and second log storage means coupled to said first and second log buffer means respectively for permanently storing a log entry for each transaction of said first and second subset of clients respectively;

sequence number incrementing means coupled to said first storage means for incrementing a sequence number associated with a data block for each transaction changing said data block.

27. The database system of claim 26 wherein said first storage means comprises a disk drive.

28. The database system of claim 26 wherein said first and second cache buffer means comprise random access memory (RAM).

29. The database system of claim 26 wherein said first and second transaction log buffer means comprise random access memory (RAM).

30. The database system of claim 26 wherein each of said data blocks has an associated incarnation number.

31. The database system of claim 30 further including incarnation number increasing means coupled to said first storage means for increasing an incarnation number associated with said data block for each transaction initializing said data block.

32. The database system of claim 31 wherein said sequence number incrementing means sets a sequence number of said data block to a first value when the incarnation number of said data block is increased.

33. A method of distributing log entries of transactions of a plurality of clients accessing a database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients, each of said subsets including at least one of said plurality of clients;

providing in a first memory means a transaction log buffer for each subset of clients;

for each transaction of a client, storing a transaction log entry in a transaction log buffer associated with the subset of clients that includes the client;

providing in a second memory means a transaction log for each transaction log buffer;

storing said transaction log entry in said transaction log.

34. A method of distributing log entries of transactions of a plurality of clients accessing a database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients all accessing a single database, each of said subsets including at least one of said plurality of clients;

providing in a first memory means a transaction log buffer for each subset of clients;

for each transaction of a client, storing a transaction log entry in a transaction log buffer associated with the subset of clients that includes the client;

providing in a second memory means a transaction log for each transaction log buffer;

storing said transaction log entry in said transaction log;

providing, in a third memory means, a cache buffer; said cache buffer for storing a copy of a data block from said database upon which a transaction is executed.

35. A method of distributing log entries of transactions of a plurality of clients accessing a database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients all accessing a single database, each of said subsets including at least one of said plurality of clients;

providing in a first memory means a transaction log buffer for each subset of clients, said first memory means comprising a random access memory (RAM);

for each transaction of a client, storing a transaction log entry in a transaction log buffer associated with the subset of clients that includes the client;

providing in a second memory means a transaction log for each transaction log buffer;

storing said transaction log entry in said transaction log;

providing, in a third memory means, a cache buffer; said cache buffer for storing a copy of a data block from said database upon which a transaction is executed.

36. A method of distributing log entries of transactions of a plurality of clients accessing a database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients all accessing a single database, each of said subsets including at least one of said plurality of clients;

providing in a first memory means a transaction log buffer for each subset of clients, said first memory means comprising a random access memory (RAM);

for each transaction of a client, storing a transaction log entry in a transaction log buffer associated with the subset of clients that includes the client;

providing in a second memory means a transaction log for each transaction log buffer, said second memory means comprising a disk drive;

storing said transaction log entry in said transaction log;

providing, in a third memory means, a cache buffer; said cache buffer for storing a copy of a data block from said database upon which a transaction is executed.

37. A method of distributing log entries of transactions of a plurality of clients accessing a database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients all accessing a single database, each of said subsets including at least one of said plurality of clients;

providing in a first memory means a transaction log buffer for each subset of clients, said first memory means comprising a random access memory (RAM);

for each transaction of a client, storing a transaction log entry in a transaction log buffer associated with the subset of clients that includes the client;

providing in a second memory means a transaction log for each transaction log buffer, said second memory means comprising a disk drive;

storing said transaction log entry in said transaction log, each transaction associated with a data block;

providing, in a third memory means, a cache buffer; said cache buffer for storing a copy of a data block from said database upon which a transaction is executed.

38. A database system comprising:

first storage means for storing data blocks, said data blocks being subdivisions of a database, each of said data blocks having a sequence number contained therein;

at least one client coupled to said first storage means, said client for initiating transactions with said data blocks;

cache buffer means coupled to said first storage means and to said client, said cache buffer means for storing copies of said data blocks from said first storage means;

sequence number increasing means coupled to said first storage means for increasing a sequence number of a data block for each transaction changing said data block.

39. The database system of claim 38 wherein said first storage means comprises a disk drive.

40. The database system of claim 38 wherein said cache buffer means comprises random access memory (RAM).

41. The database system of claim 38 wherein each of said data blocks has an associated incarnation number.

42. The database system of claim 41 further including incarnation number increasing means coupled to said first storage means for increasing an incarnation number associated with said data block for each transaction initializing said data block.

43. The database system of claim 42 wherein said sequence number incrementing means sets a sequence number of said data lock to a first value when the incarnation number of said data block is increased.

44. A method of restoring a database comprising the steps of:

(a) providing a plurality of transaction logs, each of said transaction logs comprising a plurality of transactions, each of said transactions having a sequence number, each of said transaction logs associated with one of a plurality of subsets of clients of said database, each of said subsets of clients comprising at least one client;

(b) selecting one of said plurality of transaction logs;

(c) selecting a current transaction in said selected transaction log;

(d) reading said sequence number of said current transaction;

(e) comparing said sequence number of said current transaction with a current sequence number;

(f) performing said current transaction when said sequence number of said current transaction is one more than said current sequence number and applying current transaction to said database;

(g) setting said current sequence number equal to said sequence number of said current transaction;

(h) returning to step (c) when said sequence number of said current transaction is less than or equal to said current sequence number and when said sequence number of said current transaction is greater than one more than said current sequence number.

45. The method of claim 44 further including the steps of:

(i) returning to step (b) when all transactions in a selected transaction log have been selected;

performing steps (b) through (i) until all transactions of all transaction logs have been selected.

46. The method of claim 44 further including the steps of:

(i) providing an incarnation number for each transaction of said plurality of transaction logs;

(j) reading said incarnation number of said current transaction;

(k) comparing said incarnation number of said current transaction to a current incarnation number;

(l) returning to step (c) when said incarnation number of said current transaction is less than said current incarnation number;

(m) returning to step (d) when said incarnation number of said current transaction is greater than said current incarnation number.

47. The method of claim 46 further including the step of: performing steps (b) through (m) until all transactions of all transaction logs have been selected.

48. A method of distributing log entries of transactions initiated by a plurality of clients commonly accessing at least one database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients, each of said plurality of clients commonly accessing said at least one database, each of said plurality of clients initiating transactions with said at least one database, each of said subsets including at least one of said plurality of clients, each said transaction being associated with a data block, said data block being a subdivision of said at least one database;

providing in a first memory means a different transaction log buffer associated with each one of said plurality of subsets of clients;

for each transaction of one of said plurality of clients, storing a transaction log entry in said different transaction log buffer associated with the subset of clients that includes the client that initiated said transaction;

providing a sequence number for each said data block associated with each said transaction;

incrementing the sequence number associated with said data block for each transaction changing said data block;

providing an incarnation number for each said data block;

increasing said incarnation number associated with said data block for each transaction initializing said data block;

setting said sequence number for said data block to an initial value when said incarnation number is increased;

wherein said method maintains and distributes log entries of transactions initiated by said plurality of clients prior to a recovery process of said at least one database.

49. The method of claim 48 wherein a storage means comprising a disk drive stores said data block.

50. The method of claim 48 wherein said first memory means is a random access memory (RAM).

51. The database system of claim 50 further comprising:

first and second log storage means coupled to said first and second log buffer means respectively for permanently storing a log entry for each transaction of said first and second subset of clients respectively.

52. The database system of claim 50 wherein said first storage means comprises a disk drive.

53. The database system of claim 50 wherein said cache buffer means comprise random access memory (RAM).

54. The database system of claim 50 wherein said first and second transaction log buffer means comprise random access memory (RAM).

55. A database system for distributing log entries of transactions initiated by a plurality of clients accessing a single database, said database system comprising:

first storage means for storing data blocks, said data blocks being subdivisions of a database, each of said data blocks including a sequence number and an incarnation number;

a plurality of clients, each client of said plurality of clients commonly accessing said database, each client of said plurality of clients initiating transactions with said database;

first and second subsets of said plurality of clients accessing said at least one database, each of said subsets of clients having at least one client belonging to said plurality of clients, clients of said first subset not being clients of said second subset;

cache buffer means coupled to said first storage means and to said first and second subset of clients, said cache buffer means for storing copies of said data blocks from said first storage means;

first and second transaction log buffer means coupled to said first and second subsets of clients respectively, said first and second transaction log buffer means for temporarily storing a log entry for each transaction initiated by a client of said first and second subset of clients respectively;

sequence number incrementing means for incrementing, for each transaction changing one of said data blocks, said sequence number included in each of said data blocks;

incarnation number increasing means for increasing, for each transaction initializing said data block, said incarnation number included in each of said data blocks;

said sequence number incrementing means setting said sequence number of a respective one of said data blocks to a first value when said incarnation number of said respective one of said data blocks is increased;

wherein said database system maintains and distributes log entries of transactions initiated by said plurality of clients prior to a recovery process of said at least one database.

56. A method of distributing log entries of transactions initiated by a plurality of clients commonly accessing at least one database, said method comprising the steps of:

dividing said plurality of clients into a plurality of subsets of clients, each of said plurality of clients commonly accessing said at least one database, each of said plurality of clients initiating transactions with said at least one database, each of said subsets including at least one of the said plurality of clients;

providing in a first memory means a different transaction log buffer associated with each one of said plurality of subsets of clients;

for each transaction of one of said plurality of clients, storing a transaction log entry in said different transaction log buffer associated with the subset of clients that includes the client that initiated the transaction, each transaction being associated with a data block, said data block being a subdivision of said at least one database;

for each said transaction log entry, providing a length of log entry field, an operation code field, a page address field, and incarnation number field, a sequence number field, and a variable length change data field.

57. The method of claim 56 further comprises the steps of:

providing a sequence number for each said data block;

incrementing said sequence number associated with said data block for each transaction changing said data block.

58. The method of claim 57 further including the steps of:

providing an incarnation number for each said data block;

increasing said incarnation number associated with said data block for each transaction initializing said data block.

59. The method of claim 58 further including the step of:

setting said sequence number for said data block to an initial value when said incarnation number is increased.

60. The method of claim 59 wherein said variable length change data field contains data describing changes corresponding to a respective transaction log entry.

61. The method of claim 60 wherein said length of log entry field indicates the length of data contained in said variable length change data field.

62. The method of claim 61 wherein said operation code field indicates a type of a respective transaction log entry.

63. The method of claim 62 wherein said type of said respective transaction log entry is selected from the group consisting of delete type, change type, and write type.

64. The method of claim 63 wherein said page address field indicates the address of a data page corresponding to a respective transaction log entry.

65. The method of claim 64 wherein said incarnation number filed indicates a respective incarnation number of said data page.

66. The method of claim 65 wherein said sequence number field indicates a respective sequence number of said data page.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates generally to the field of databases, and in particular to a method for ensuring the integrity of a database.

2. Background Art

A database is an ordered collection of data. A database system allows one or more data users, referred to as "clients" to add to, change, read from, delete, and/or otherwise manipulate the data of the database. A database management system is utilized to control the storage, retention and retrieval of data by clients in a database.

In a computer system, the database is often stored on a permanent storage system, such as a magnetic, optical, or magneto-optical disk drive. The term "permanent storage system" refers to a storage system that is used to retain data over long periods of time, in spite of power interruptions and some other failures. A disk dive is an example of such a permanent storage system. If data is stored in a nonvolatile memory, such as on a Winchester disk drive, and the disk drive is turned off or otherwise powered down and then turned back on, the data is still available. This is in contrast to temporary storage systems, such as most dynamic random access memory (DRAM). If data is stored in a typical DRAM system (without battery power), and the DRAM is turned off and then turned back on, the data is no longer available.

A client in a computer implemented database may be a human user, a processor, or a program executed on a processor. A client is any entity that can make a "transaction" with the database. A transaction is a sequence of operations that allow a client access to the database to read data, delete data, add new data, update or modify existing data. A transaction begins with an operation referred to as BEGIN operation and ends with either a COMMIT operation or a ROLLBACK operation. A COMMIT operation signifies the completion of a successful transaction. A ROLLBACK operation signifies the unsuccessful termination of a transaction.

In a typical computer-implemented database system, a transaction is not performed on the "original data" (i.e. the data stored on the permanent storage system), but is performed on a copy of the data. For example, when a client accesses a block of data from a database, a copy of the data is retrieved from the database and is stored in a temporary storage location, referred to as a "buffer". The client then may read, update, modify, replace or delete the block of data. The results of the transaction are effected on the original block of data at a later time. This is done because, typically, it is not possible to modify individual bytes in the permanent storage system; an entire block must be written at once. A typical database system utilizes a number of buffers to allow the transactions of multiple clients to be performed. As a result, there may be a number of transactions waiting to be executed on the original data at any one time. The delay in time between the execution of a transaction on data in a buffer and the execution of that transaction on the original data can affect the "integrity" of the database. The integrity of a database refers to its accuracy and reliability. A database has integrity if all outstanding client transactions have been executed in the correct order on the original data.

There are a number of factors that make it difficult to maintain the integrity of a database. First, when multiple clients access a database, a method to avoid harmful interaction among the clients must be provided. When multiple clients make changes to the database, the changes made by each client may be interrelated and must be applied to the database in the proper sequence across clients to preserve their relationship. Another factor that increases the difficulty of preserving the integrity of a database is that computer systems do not exhibit perfect reliability and components of a computer system occasionally fail, (e.g. the disk drive fails, the processor fails, there is a system failure, a power failure, etc.). Changes by clients to the database made before, during or after the failure must be applied to the database in the proper sequence to ensure database integrity.

When a database system failure occurs, a "recovery" operation is required. A recovery in a database system means recovering the database itself. That is, restoring the database to a state that is known to be consistent and reasonably recent. This is sometimes accomplished by restoring the database from a back-up copy of the contents of the database. The back-up copy is a duplicate copy of the original database that is made periodically.

A disadvantage of recovering a database from a backup copy is that the backup copy may not reflect transactions that occurred after the time the backup was made and before the failure of the database system. It is desired to be able to recreate those missing transactions to avoid the duplication of work that has already been performed on the database. This requires that the transactions be "persistent". Persistence refers to the retention of sufficient redundant information about a transaction to recreate the effects of the transaction at a later time, in the event that a failure causes loss of the primary copy of the data written by the transaction.

One prior art method used to ensure the persistence of changes involves sequentially writing short records containing information sufficient to redo the changes to a "log." The log provides a record of changes that can survive a database system failure. Thus, the persistence of the changes is provided.

A database system that uses a log to store redo records is illustrated in FIG. 1. The database system of FIG. 1 consists of a plurality of clients 101, 102 and 103 coupled to a database controller 104. The database controller includes a plurality of cache buffers 107-112, and a log buffer 113. The database controller is coupled to permanent storage devices 105 and 106. In the example of FIG. 1, storage device 105 stores log information and storage device 106 stores the original database data.

When a client reads information, a BEGIN operation is executed, the information is located in database 106 and transferred to one of cache buffers 107, 108, 109, 110, 111 or 112. The information is provided to the appropriate client from the proper cache buffer. When the client has read the information, a COMMIT operation is executed and the cache buffer is released for use by another client. No changes are recorded in database 106 since a read operation does not alter the original data. Correspondingly, a log entry is not required because there is no need to recreate a read transaction in the event of a failure.

When a client writes information, the information is first written to cache buffer 107, 108, 109, 110, 111 or 112. When all of the information to be added has been entered into the cache buffer, a log entry is produced and written to log buffer 113. When the client executes a COMMIT operation, the log entry is written to log 105. At some later time, an attempt is made to add the information to database 106. If this attempt fails, (or if some earlier failure prevents the attempt from taking place), the log entry in log 105 can be used as a redo record to "redo" the failed transaction.

When a client changes or deletes information in the database, the record containing the information to be changed is first located in database 106. The record is copied into a cache buffer 107, 108, 109, 110, 111 or 112. The client makes appropriate changes to the cache buffer containing the information. When all of the changes ha