Method and apparatus for transferring data from the cache of one node to the cache of another node
First Claim
1. A method for transferring a resource from a first cache to a second cache, the method comprising the steps of:
- retaining a first copy of the resource in said first cache while transferring a second copy of the resource from the first cache to the second cache without first durably storing said resource from said first cache to a persistent storage; and
retaining at least one copy of the resource in said first cache until said first copy of the resource or a successor thereof is durably stored.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus are provided for transferring a resource from the cache of one database server to the cache of another database server without first writing the resource to disk. When a database server (Requestor) desires to modify a resource, the Requestor asks for the current version of the resource. The database server that has the current version (Holder) directly ships the current version to the Requestor. Upon shipping the version, the Holder loses permission to modify the resource, but continues to retain the resource in memory. When the retained version of the resource, or a later version thereof, is written to disk, the Holder can discard the retained version of the resource. Otherwise, the Holder does not discard the retained version. Using this technique, single-server failures are recovered without having to merge the recovery logs of the various database servers that had access to the resource.
100 Citations
51 Claims
-
1. A method for transferring a resource from a first cache to a second cache, the method comprising the steps of:
-
retaining a first copy of the resource in said first cache while transferring a second copy of the resource from the first cache to the second cache without first durably storing said resource from said first cache to a persistent storage; and
retaining at least one copy of the resource in said first cache until said first copy of the resource or a successor thereof is durably stored. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
allowing said first copy of said resource to be modified in said first cache prior to transferring said second copy to said second cache; and
preventing said first copy of said resource from being modified after transferring said second copy to said second cache.
-
-
4. The method of claim 3 further comprising the step of transferring a modify permission from a sending process associated with the first cache to a receiving process associated with the second cache along with said second copy of said resource.
-
5. The method of claim 4 wherein:
-
permissions for accessing said resource are governed by a master; and
the step of transferring said modify permission to the receiving process is performed prior to receiving acknowledgement from said master for transfer of said modify permission to said receiving process.
-
-
6. The method of claim 1 further comprising the steps of:
-
after transferring said second copy to said second cache, sending a request for permission to release said first copy;
in response to said request, causing said first copy or a successor thereof to be durably stored; and
in response to said successor being durably stored, sending a message that indicates that said first copy can be released.
-
-
7. The method of claim 6 wherein:
-
the step of sending a request for permission to release said first copy is performed by a sending process; and
the step of causing said first copy or a successor thereof to be durably stored includes the step of causing a process other than the sending process to store a successor to said first copy of said resource.
-
-
8. The method of claim 1 wherein the step of retaining at least one copy of the resource in said first cache includes the steps of:
-
prior to attempting to durably store said first copy, determining whether a durably stored copy of said resource is more recent than said first copy;
if said durably stored copy is more recent than said first copy, then releasing said first copy without durably storing said first copy; and
if said durably stored copy is not more recent than said first copy, then durably storing said first copy.
-
-
9. The method of claim 1 further comprising the steps of:
-
a receiving process associated with said second cache sending a request for said resource to a master of said resource;
in response to said request from said receiving process, said master of said resource sending a message to a sending process associated with said first cache; and
said sending process transferring said second copy to said receiving process in response to said message from said master.
-
-
10. The method of claim 1 further comprising performing the following steps after the step of transferring said second copy to said second cache:
-
a sending process associated with said first cache requesting a lock from a lock manager, wherein said lock grants permission to write said resource to disk but not permission to modify said resource;
said lock manager selecting a process that has a version of said resource that is at least as recent as said first copy;
said lock manager granting said lock to said selected process; and
said selected process writing said version of said resource to disk.
-
-
11. The method of claim 10 further comprising the step of, in response to said version of said resource being written to disk, said lock manager causes all versions of said resource that are older than said version to be released.
-
12. The method of claim 1 further comprising the steps of, after a failure of a cache that holds a dirty copy of said resource:
-
determining whether the failed cache held the latest version of the resource;
if the failed cache held the latest version of the resource, then writing a latest past image of the resource to disk;
releasing all previous past images of the resource; and
applying a recovery log of said failed cache to reconstruct the latest version of the resource.
-
-
13. The method of claim 12 further comprising the steps of:
-
if the failed cache did not hold the latest version of the resource, then writing the latest version of the resource to disk; and
releasing all past images of the resource.
-
-
14. The method of claim 1 further comprising the steps of, after a failure of a plurality of caches that hold dirty versions of said resource:
-
determining whether any of the failed caches held the latest version of the resource; and
if any of the failed caches held the latest version of the resource, then merging and applying the recovery logs of said failed caches to reconstruct the latest version of the resource.
-
-
15. A computer-readable medium carrying one or more sequences of instructions for transferring a resource from a first cache to a second cache, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:
-
retaining a first copy of the resource in said first cache while transferring a second copy of the resource from the first cache to the second cache without first durably storing said resource from said first cache to a persistent storage; and
retaining at least one copy of the resource in said first cache until said first copy of the resource or a successor thereof is durably stored. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
allowing said first copy of said resource to be modified in said first cache prior to transferring said second copy to said second cache; and
preventing said first copy of said resource from being modified after transferring said second copy to said second cache.
-
-
17. The computer-readable medium of claim 16 further comprising instructions for performing the step of transferring a modify permission from a sending process associated with the first cache to a receiving process associated with the second cache along with said second copy of said resource.
-
18. The computer-readable medium of claim 17 wherein:
-
permissions for accessing said resource are governed by a master; and
the step of transferring said modify permission to the receiving process is performed prior to receiving acknowledgement from said master for transfer of said modify permission to said receiving process.
-
-
19. The computer-readable medium of claim 15 further comprising sequences of instructions for performing the steps of:
-
after transferring said second copy to said second cache, sending a request for permission to release said first copy;
in response to said request, causing said first copy or a successor thereof to be durably stored; and
in response to said successor being durably stored, sending a message that indicates that said first copy can be replaced.
-
-
20. The computer-readable medium of claim 19 wherein:
-
the step of sending a request for permission to release said first copy is performed by a sending process; and
the step of causing said first copy or a successor thereof to be durably stored includes the step of causing a process other than said sending process to store a successor to said first copy of said resource.
-
-
21. The computer-readable medium of claim 15 wherein the step of retaining at least one copy of the resource in said first cache includes the steps of:
-
prior to attempting to durably store said first copy, determining whether a durably stored copy of said resource is more recent than said first copy, if said durably stored copy is more recent than said first copy, then releasing said first copy without durably storing said first copy; and
if said durably stored copy is not more recent than said first copy, then durably storing said first copy.
-
-
22. The computer-readable medium of claim 15 further comprising sequences of instructions for performing the steps of:
-
a receiving process associated with said second cache sending a request for said resource to a master of said resource;
in response to said request from said receiving process, said master of said resource sending a message to a sending process associated with said first cache; and
said sending process transferring said second copy to said receiving process in response to said message from said master.
-
-
23. The computer-readable medium of claim 15 further comprising instructions for performing the following steps after the step of transferring said second copy to said second cache:
-
a sending process associated with said first cache requesting a lock from a lock manager, wherein said lock grants permission to write said resource to disk but not permission to modify said resource;
said lock manager selecting a process that has a version of said resource that is at least as recent as said first copy;
said lock manager granting said lock to said selected process; and
said selected process writing said version of said resource to disk.
-
-
24. The computer-readable medium of claim 23 further comprising instructions for performing the step of, in response to said version of said resource being written to disk, said lock manager causes all versions of said resource that are older than said version to be released.
-
25. The computer-readable medium of claim 15 further comprising sequences of instructions for performing the steps of, after a failure of a cache that holds a dirty copy of said resource:
-
determining whether the failed cache held the latest version of the resource;
if the failed process held the latest version of the resource, then writing a latest past image of the resource to disk;
releasing all previous past images of the resource; and
applying a recovery log of said failed cache to reconstruct the latest version of the resource.
-
-
26. The computer-readable medium of claim 25 further comprising sequences of instructions for performing the steps of:
-
if the failed cache did not hold the latest version of the resource, then writing the latest version of the resource to disk; and
releasing all past images of the resource.
-
-
27. The computer-readable medium of claim 15 further comprising sequences of instructions for performing the steps of, after a failure of a plurality of caches that hold dirty versions of said resource:
-
determining whether any of the failed caches held the latest version of the resource; and
if any of the failed caches held the latest version of the resource, then merging and applying the recovery logs of said failed caches to reconstruct the latest version of the resource.
-
-
28. The computer-readable medium of claim 15,
wherein the instructions for retaining the first copy of the resource in said first cache include instructions for retaining the first copy of the resource in a first cache maintained by a first database server, wherein the instructions for transferring the second copy of the resource from the first cache to the second cache without first dumbly storing said resource from said first cache to a persistent storage include instructions for transferring the second copy of the resource from the first cache maintained by the first database server to a second cache maintained by a second database server without first durably storing said resource from said first cache maintained by said first database server to the persistent storage; - and
wherein the instructions for retaining at least one copy of the resource in said first cache until said first copy of the resource or a successor thereof is durably stored includes instructions for retaining at least one copy of the resource in the first cache maintained by the first data server until said first copy of the resource or a successor thereof is durably stored.
- and
-
29. A method of managing data in a system in which a plurality of caches hold dirty versions of resources from one or more shared disks, the method comprising the steps of:
-
when a cache of said plurality of caches requires a dirty version of a resource that is in another cache of said plurality of caches, transferring the dirty version of the resource from the cache in which the dirty version resides to the cache that requires the dirty version without first durably storing the dirty version;
maintaining separate recovery logs for each cache of said plurality of caches; and
when a cache of said plurality of caches fails, recovering the failed cache based on the recovery log associated with said failed cache without inspecting the separate recovery logs of the other caches of said plurality of caches. - View Dependent Claims (30, 31)
the cache in which the dirty version resides is a first cache;
the dirty version of the resource in the first cache is a first copy of the resource;
the cache that requires the dirty version is a second cache;
the step of transferring the dirty version is performed by transferring a second copy of the resource to the second cache; and
the method further comprising the steps of;
allowing said first copy of said resource to be modified in said first cache prior to transferring said second copy to said second cache; and
preventing said first copy of said resource from being modified after transferring said second copy to said second cache.
-
-
32. A computer-readable medium carrying instructions for managing data in a system in which a plurality of caches hold dirty versions of resources from one or more shared disks, the instructions including instructions for performing the steps of:
-
when a cache of said plurality of caches requires a dirty version of a resource that is in another cache of said plurality of caches, transferring the dirty version of the resource from the cache in which the dirty version resides to the cache that requires the dirty version without first durably storing the dirty version;
maintaining separate recovery logs for each cache of said plurality of caches; and
when a cache of said plurality of caches fails, recovering the failed cache based on the recovery log associated with said failed cache without inspecting the separate recovery logs of the other caches of said plurality of caches. - View Dependent Claims (33, 34)
the cache in which the dirty version resides is a first cache;
the dirty version of the resource in the first cache is a first copy of the resource;
the cache that requires the dirty version is a second cache;
the step of transferring the dirty version is performed by transferring a second copy of the resource to the second cache; and
the computer-readable medium further comprising instructions for performing the steps of;
allowing said first copy of said resource to be modified in said first cache prior to transferring said second copy to said second cache;
andpreventing said first copy of said resource from being modified after transferring said second copy to said second cache.
-
-
35. A system for transferring a resource, the system comprising:
-
a node that has a first cache that is communicatively coupled to a second cache from among one or more other caches that are included in one or more other nodes;
wherein said node is configured to retain a first copy of the resource in the first cache while transferring a second copy of the resource from the first cache to the second cache without first durably storing said resource from said first cache to a persistent storage; and
wherein said node is configured to retain at least one copy of the resource in said first cache until said first copy of the resource or a successor thereof is durably stored. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
said node is configured to allow said first copy of said resource to be modified in said first cache prior to transferring said second copy to said second cache; - and
said node is configured to prevent said first copy of said resource from being modified after transferring said second copy to said second cache.
-
-
38. The system of claim 37, wherein said node is configured to transfer a modify permission from a sending process associated with the first cache to a receiving process associated with the second cache along with said second copy of said resource.
-
39. The system of claim 38 wherein:
-
permissions for accessing said resource are governed by a master node; and
said node is configured to transfer said modify permission to the receiving process prior to said first node receiving acknowledgement from said master node for transfer of said modify permission to said receiving process.
-
-
40. The system of claim 35, wherein:
-
said node is configured to send a request to a master node for permission to release said first copy, after transferring said second copy to said second cache; and
said node is configured to receive a message from said master node that indicates that said first copy can be released after said master node causes, in response to said request, said first copy or a successor thereof to be durably stored.
-
-
41. The system of claim 40, wherein
said node comprises a sending process that is configured to send the request for permission to release said first copy; - and
a process other than the sending process stores a successor to said first copy of said resource.
- and
-
42. The system of claim 35 wherein said node is configured to retain at least one copy of the resource in said first cache by:
-
prior to attempting to durably store said first copy, determining whether a durably stored copy of said resource is more recent than said first copy;
if said durably stored copy is more recent than said first copy, then releasing said first copy without durably storing said first copy; and
if said durably stored copy is not more recent than said first copy, then durably storing said first copy.
-
-
43. The system of claim 35, wherein:
-
said node includes a sending process associated with said first cache, wherein said sending process is configured to receive a message from a master node that receives a request for said resource from a receiving process associated with said second cache; and
said sending process transfers said second copy to said receiving process in response to said message from said master node.
-
-
44. The system of claim 35, wherein:
-
said node includes a sending process that is configured to request a lock from a lock manager after said second copy is transferred to said second cache, wherein said lock grants permission to write said resource to disk but not permission to modify said resource; and
said lock manager selects a process that has a version of said resource that is at least as recent as said first copy and grants said lock to said selected process to cause said selected process to write said version of said resource to disk.
-
-
45. The system of claim 44 wherein said lock manager causes all versions of said resource that are older than said version to be released, in response to said version of said resource being written to disk.
-
46. The system of claim 35 further comprising:
-
a master node that is configured to determine, after a failure of a cache that holds a dirty copy of said resource, whether a failed cache held the latest version of the resource; and
wherein, if the failed cache held the latest version of the resource, the master node is configured to cause a latest past image of the resource to be written to disk, to cause all previous past images of the resource to be released, and to cause a recovery log of said failed cache to be applied to reconstruct the latest version of the resource.
-
-
47. The system of claim 46 wherein the master node is configured to, if the failed cache did not hold the latest version of the resource, cause the latest version of the resource to be written to disk, and to cause all past images of the resource to be released.
-
48. The system of claim 35 further comprising:
a master node that is configured to, after a failure of a plurality of caches that hold dirty versions of said resource, determine whether any of the failed caches held the latest version of the resource, and if any of the failed caches held the latest version of the resource, then merge and apply the recovery logs of said failed caches to reconstruct the latest version of the resource.
-
49. A system for managing data among a plurality of caches that hold dirty versions of resources from one or more shared disks, the system comprising:
-
a node that includes a cache from among said plurality of caches, wherein a separate recovery log is maintained for each cache of said plurality of caches, wherein another cache of said plurality of caches requires a dirty version of the resource that resides in said cache, and wherein the node is configured to transfer the dirty version to the other cache without durably storing the dirty version; and
a master node that is configured to recover a failed cache from among said plurality of caches based on the recovery log associated with said failed cache without inspecting the separate recovery logs of the other caches of said plurality of caches. - View Dependent Claims (50, 51)
the cache in which the dirty version resides is a first cache;
the dirty version of the resource in the first cache is a first copy of the resource;
the cache that requires the dirty version is a second cache;
the node is configured to transfer the dirty version of the resource by transferring a second copy of the resource to the second cache;
the first node is configured to allow said first copy of said resource to be modified in said first cache prior to transferring said second copy to said second cache; and
the first node is configured to prevent said first copy of said resource from being modified after transferring said second copy to said second cache.
-
Specification