US5440727A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Asynchronous replica management in shared nothing architectures
Assignee: International Business Machines Corp
•
Filing: 1994-07-15
•
Granted: 1995-08-08
•
Expires: 2014-07-15
Abstract
Abstract In a partitioned database system of the Shared Nothing type, one or more secondary replicas of each partition are maintained by spooling (i.e., asynchronously sending) modified (usually called dirty) pages from the primary replica to the secondary replica(s) rather than by using a synchronous page update or by sending log entries instead of entire pages. A Write-Ahead Log protocol is used so that a dirty page is not forced to non-volatile storage until a log record of the modification is created and written to non-volatile storage. Replica updating does not delay the committing of transactions because replica updating is done asynchronously with respect to transaction processing. Since dirty pages are sent rather than only log entries, disk accesses and processing at the secondary replica(s) arising from the maintaining of the replicas are minimized as well. Only one centrally accessible log is maintained for all replicas of the same partition.
Inventors
- 👤 Anupam K. Bhide
- 👤 George P. Copeland
- 👤 Ambuj Goyal
- 👤 Hui-I Hsiao
- 👤 Anant D. Jhingran
- 👤 Chandrasekaran Mohan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 09:32
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/27; G06F16/273; G06F16/23; G06F16/2358; G06F16/2365; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
264 words
An improved transaction processing system of the type which includes: a plurality of transaction processors connected by a communication network, each of said processors having its own private storage; said transaction processing system having at least one partition of data which is subpartitioned into pages, said partition of data including a primary replica of said partition and a secondary replica of said partition, said primary replica being stored in said private storage of one of said processors and said secondary replica being stored in said private storage of another one of said processors; and a non-volatile log, said transaction processing system using a Write-Ahead Log protocol in which a modification to a page in said partition is not considered made until said modification is stored in said log; wherein the improvement comprises: means for generating a response indicating to a transaction requestor that a requested transaction on the primary replica has completed; means for updating said secondary replica from said primary replica by asynchronously sending modified pages from said primary replica to said secondary replica independently of the generation of the response by the means for generating and without imposing any page sending order or timing constraint; means for keeping track of the pages of said partition which have been modified in said primary replica and not yet modified in said secondary replica; and means for making said log accessible to both said processors which are storing a replica of said partition, whereby said secondary replica is maintained without imposing delay upon the processing of transactions on said primary replica by said one processor.
Claim 2
Dependent Claim
264 words
An improved transaction processing system of the type which includes: a plurality of transaction processors connected by a communication network, each of said processors having its own private storage; said transaction processing system having at least one partition of data which is subpartitioned into pages, said partition of data including a primary replica of said partition and a secondary replica of said partition, said primary replica being stored in said private storage of one of said processors and said secondary replica being stored in said private storage of another one of said processors; and a non-volatile log, said transaction processing system using a Write-Ahead Log protocol in which a modification to a page in said partition is not considered made until said modification is stored in said log; wherein the improvement comprises: means for generating a response indicating to a transaction requestor that a requested transaction on the primary replica has completed; means for updating said secondary replica from said primary replica by asynchronously sending modified pages from said primary replica to said secondary replica independently of the generation of the response by the means for generating and without imposing any page sending order or timing constraint; means for keeping track of the pages of said partition which have been modified in said primary replica and not yet modified in said secondary replica; and means for making said log accessible to both said processors which are storing a replica of said partition, whereby said secondary replica is maintained without imposing delay upon the processing of transactions on said primary replica by said one processor.
Claim 3
Dependent Claim
56 words
A transaction processing system as defined in claim 1 wherein said transaction processing system has a plurality of partitions of data, each of said plurality of partitions of data including a primary replica and at least one secondary replica, each of said replicas of a same partition being stored in different ones of said private storages.
Claim 4
Dependent Claim
23 words
A transaction processing system as defined in claim 2 wherein said partitions of data form a distributed database of the Shared Nothing type.
Claim 5
Dependent Claim
60 words
A transaction processing system as defined in claim 2 and further comprising a node manager for identifying the particular processor which is deemed to have said primary replica of any particular partition in its private storage and for identifying each particular processor which has one of said at least one secondary replica of said particular partition in its private storage.
Claim 6
Dependent Claim
48 words
A transaction processing system as defined in claim 4 wherein said node manager tracks the operational status of each of said replicas and in the event of failure of the primary replica of any partition identifies a non-failed secondary replica of said any partition as the primary replica.
Claim 7
Dependent Claim
32 words
A transaction processing system as defined in claim 2 wherein transactions are completed only against the particular replica of any partition which is identified by said node manager as the primary replica.
Claim 8
Dependent Claim
30 words
A transaction processing system as defined in claim 2 wherein any one replica of any one or more partitions can fail without thereby causing said transaction processing system to fail.
Claim 9
Dependent Claim
19 words
A transaction processing system as defined in claim 7 wherein a failed replica can be restored from said log.
Claim 10
Dependent Claim
25 words
A transaction processing system as defined in claim 7 wherein a failed replica of a partition can be restored from another replica of said partition.
Claim 11
Dependent Claim
90 words
A transaction processing system as defined in claim 1 wherein each of said private storages includes a non-volatile portion and a volatile portion, said replica of a partition stored in each of said private storages being permanently stored in said non-volatile portion thereof, individual pages of said primary replica being fetched to said volatile portion of said private storage of said one processor for use, at least some of said fetched pages becoming modified and being forced back to said non-volatile portion of said private storage of said one processor.
Claim 12
Dependent Claim
56 words
A transaction processing system as defined in claim 10 wherein said means for updating includes means for sending a modified page of said primary replica from said volatile private storage portion of said one processor to said volatile private storage portion of said another processor for transfer into said non-volatile storage portion of said another processor.
Claim 13
Dependent Claim
54 words
A transaction processing system as defined in claim 11 wherein said means for updating further comprises means for acknowledging to said one processor that a modified page of said primary replica sent from said volatile private storage portion of said one processor has been stored in said non-volatile storage portion of said another processor.
Claim 14
Dependent Claim
41 words
A transaction processing system as defined in claim 11 wherein said modified page is transferred into said non-volatile storage portion of said another processor before said modified page is forced back to said non-volatile private storage portion of said one processor.
Claim 15
Dependent Claim
40 words
A transaction processing system as defined in claim 11 wherein said modified page is sent to said private storage of said another processor when said modified page is forced back to said non-volatile private storage portion of said one processor.
Claim 16
Dependent Claim
42 words
A transaction processing system as defined in claim 11 wherein said means for keeping track includes table means for identifying pages of said partition that have been modified and not yet stored in said non-volatile private storage portion of said another processor.
Claim 17
Dependent Claim
71 words
A transaction processing system as defined in claim 15 wherein said table means includes a first dirty page table for identifying modified pages of said partition that have not yet been stored in said non-volatile private storage portion of said one processor and a second dirty page table for identifying modified pages of said partition that have not yet been stored in said non-volatile private storage portion of said another processor.
Claim 18
Dependent Claim
18 words
A transaction processing system as defined in claim 1 wherein said log is stored in a log server.
Claim 19
Dependent Claim
27 words
A transaction processing system as defined in claim 17 wherein said means for making said log accessible includes means connecting said log server to said transaction processors.
Claim 20
Dependent Claim
27 words
A transaction processing system as defined in claim 18 wherein said means for making said log accessible includes means connecting said log server to said communication system.
Claim 21
Dependent Claim
27 words
A transaction processing system as defined in claim 1 wherein said primary replica can be updated by multiple transactions asynchronously with the updating of the secondary replica.
Claim 22
Dependent Claim
71 words
A transaction processing system as defined in claim 1 wherein said private storage of said one processor includes volatile private storage and non-volatile private storage and said means for updating includes means for sending a modified page to said private storage of said another processor in response to said modified page being sent from said volatile private storage of said one processor to said non-volatile private storage of said one processor.
References Cited (Backward Citations)
US4432057A
Cited
US4507751A
Cited
US4819156A
Cited
US4819159A
Cited
US5084816A
Cited
US5043866A
Cited
US5193162A
Cited
US5155845A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-07 | 1999-02-06 | 1999-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-07 | 2003-02-06 | 2003-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-07 | 2007-02-06 | 2007-08-08 | $7700.00 | Window Closed / Lapsed |