Distributed database system providing data and space management methodology

• US 7,783,610 B2
• Filed: 02/22/2008
• Issued: 08/24/2010
• Est. Priority Date: 11/01/2004
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Sampath, Srikanth, Ramachandran, Satya N., Francis, Joe, Varakur, Gangavara Prasad, Lin, Mei-Lin Linda, Zhou, Fei
• Primary Examiner(s): Wong; Leslie
• Application Number:
  US12/035,930
• Publication Number:
  US 20080208938A1
• Time in Patent Office: 914 Days
• Field of Search: 707/689, 707/695, 709/203, 709/219
• US Class Current: 707/689
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A distributed database system providing data and space management methodology. In a distributed system consisting a plurality of servers sharing access to data pages, a method for setting a timestamp indicating when modifications to data pages are made in a non-regressing fashion includes steps of: maintaining a local sequence at each server and an allocation page timestamp on an allocation page; upon allocation of a data page, applying a timestamp to the data page which is greater than the allocation page timestamp; upon modification of a given data page at a particular server, setting the timestamp on the given data page to the greater of the local sequence at the particular server and an existing timestamp already on the given data page; and when data pages are deallocated, adjusting the allocation page timestamp to a value greater than the timestamp value on any deallocated data page.

Claims

1. In a distributed system comprising a plurality of servers sharing access to data maintained on data pages, a method for setting a timestamp indicating when modifications to data pages are made in a non-regressing fashion, the method comprising:

maintaining a local sequence at each server and an allocation page timestamp on an allocation page of the distributed system;

upon allocation of a data page, applying a timestamp to the data page which is greater than the allocation page timestamp;

upon modification of a given data page at a particular server, setting the timestamp on the given data page to the greater of the local sequence at the particular server and an existing timestamp already on the given data page; and

when at least one data page is deallocated, adjusting the allocation page timestamp to a value greater than the timestamp value on any deallocated data page.

2. The method of claim 1, wherein said step of setting the timestamp on the given data page includes setting the timestamp on the given data page without updating the allocation page.

3. The method of claim 1, wherein said step of adjusting the allocation page timestamp includes adjusting the allocation page timestamp to a value greater than the timestamp value on a particular data page when said particular data page is deallocated.

4. The method of claim 1, wherein said step of adjusting the allocation page timestamp includes adjusting the allocation page timestamp to a value greater than the local sequence value at any server of the distributed system when multiple data pages are deallocated.

5. The method of claim 1, wherein said maintaining step includes maintaining a local sequence at each server for applying a monotonically increasing timestamp to a data page modified at each server without updating the data page'"'"'s allocation page.

6. The method of claim 1, wherein the distributed system maintains a plurality of allocation pages and said allocation pages are updated only as a result of allocation and deallocation of data pages, and not for other data page modifications.

7. The method of claim 1, further comprising:

setting the local sequence at each server and the allocation page timestamp to a value based on highest local sequence value at any server at startup of the distributed system.

8. The method of claim 1, wherein said step of setting the timestamp includes increasing the local sequence at the particular server to a value greater than the existing timestamp already on the given data page if the existing timestamp is greater than the local sequence.

9. A computer-readable medium having processor-executable instructions for performing the method of claim 1.

10. In a distributed system comprising a plurality of servers sharing access to data maintained on data pages, a system for setting a timestamp indicating when modifications are made to data pages in a non-regressing fashion, the system comprising:

a local timestamp sequence maintained at each server of the distributed system;

a deallocation clock (object) provided on an allocation page of the distributed system;

a page allocation module which applies a timestamp to a data page which is greater than the deallocation clock value upon allocation of the data page and which adjusts the deallocation clock to a value greater than the timestamp value on any data page which is deallocated; and

a timestamp module at each server of the distributed system which sets the timestamp on a given data page to the greater of the local timestamp sequence and an existing timestamp already on the given data page when the given data page is modified at a particular server.

11. The system of claim 10, wherein timestamp module sets the timestamp on the given data page without updating the allocation page.

12. The system of claim 11, wherein the distributed system maintains a plurality of allocation pages and said allocation pages are updated only as a result of allocation and deallocation of data pages, and not as a result of modifications to data pages.

13. The system of claim 10, wherein said allocation module adjusts the deallocation clock to a value greater than the timestamp value on a particular data page when said particular data page is deallocated.

14. The system of claim 10, wherein said allocation module adjusts the deallocation clock to a value greater than local sequence value at any server of the distributed system when multiple data pages are deallocated.

15. The system of claim 10, wherein said timestamp module increases the local timestamp sequence at the particular server to a value greater than the existing timestamp already on the given data page if the existing timestamp is greater than the local timestamp sequence.

16. In a distributed database system comprising a plurality of nodes sharing access to data pages, each of the data pages having a timestamp for indicating when a given data page was last modified, a method for setting a data page'"'"'s timestamp in a non-regressing fashion, the method comprising:

providing a local sequence at each of the nodes and a watermark which is maintained logically by the system across all the nodes;

on startup of the database system, setting the watermark to a value greater than any local sequence value at any of the nodes;

when a data page is modified at a particular node, setting the data page'"'"'s timestamp to the greater of the particular node'"'"'s local sequence and an existing timestamp already on the data page without updating the data page'"'"'s allocation page;

when multiple data pages are deallocated, ensuring that the allocation page timestamp is above the watermark value;

when a single data page is deallocated, ensuring that the allocation page timestamp has a value greater than the value of the deallocated data page'"'"'s timestamp value; and

when a given data page is allocated, applying a timestamp to the given data page which is greater than the allocation page timestamp, so as to ensure that the given data page'"'"'s timestamp does not regress.

17. The method of claim 16, wherein said providing step includes providing a local sequence at each node for applying a monotonically increasing timestamp to a data page modified at a given node without updating the data page'"'"'s allocation page.

18. The method of claim 17, wherein allocation pages of the database system are updated only as a result of allocation and deallocation of data pages, and not for other data page modifications.

19. The method of claim 16, wherein said providing step includes setting the local sequence at each of the node a value based on highest local sequence value at any node at startup of the distributed database system.

20. The method of claim 16, wherein the watermark is maintained logically by the database system without storing the watermark at any node, and is manipulated and derived as needed through the local sequence values.

21. The method of claim 16, further comprising:

in response to database operations which affect multiple data pages without accessing said multiple data pages, increasing the local sequence at all nodes to a value greater than the watermark.

22. The method of claim 21, wherein said operations which affect multiple data pages include alter object and drop object operations, where said multiple data pages are not accessed and timestamps on said multiple data pages are not known.

23. The method of claim 16, wherein said step of setting the data page'"'"'s timestamp upon modification of the data page at a particular node includes incrementing the local sequence at the particular node before setting the data page'"'"'s timestamp.

24. The method of claim 16, wherein said step of setting the data page'"'"'s timestamp includes increasing the local sequence to a value greater than the existing timestamp already on the data page if the existing timestamp is greater than the local timestamp.

25. The method of claim 16, wherein said step of increasing the allocation page timestamp includes substeps of:

determining highest value of the allocation page timestamp, the local sequence, the data page'"'"'s timestamp, and for a multiple page deallocation the watermark; and

incrementing said highest value and applying it to the allocation page timestamp.

26. The method of claim 16, wherein a node comprises a database server in the distributed database system.

27. A computer-readable medium having processor-executable instructions for performing the method of claim 16.

28. In a distributed database system comprising a plurality of nodes sharing access to data pages, a system for setting a data page'"'"'s timestamp indicating when a given data page was last modified in a non-regressing fashion, the system comprising:

a local sequence maintained at each node of the distributed database system;

a watermark maintained logically across all nodes of the distributed database system and which is set to a value greater than any local sequence value at any of the nodes on startup of the distributed database system;

an allocation page timestamp maintained on each allocation page of the distributed database system;

a local timestamp module at each node of the distributed database system which maintains the local sequence and which, when a data page is modified at a particular node, sets the data page'"'"'s timestamp to the greater of the particular node'"'"'s local sequence and an existing timestamp already on the data page without updating the data page'"'"'s allocation page;

a deallocation module which, when a single data page is deallocated, ensures that the allocation page timestamp has a value greater than the value of the deallocated data page'"'"'s timestamp value and which, when multiple data pages are deallocated, ensures that the allocation page timestamp is above the watermark value; and

an allocation module which, when a given data page is allocated, applies a timestamp to the given data page which is greater than the allocation page timestamp, so as to ensure that the given data page'"'"'s timestamp does not regress.

29. The system of claim 28, wherein the local timestamp module applies a monotonically increasing timestamp to a data page modified at a given node without updating the data page'"'"'s allocation page.

30. The system of claim 29, wherein allocation pages of the database system are updated only as a result of allocation and deallocation of data pages.

31. The system of claim 28, wherein the watermark is maintained logically without storing the watermark at any node and is manipulated and derived as needed by the local timestamp module at each node through the local sequence values.

32. The system of claim 28, wherein the local timestamp module increases the local sequence to a value greater than the watermark in response to database operations which affect multiple data pages without accessing said multiple data pages.

33. The system of claim 32, wherein said operations which affect multiple data pages include alter object and drop object operations, where said multiple data pages are not accessed and timestamps on said multiple data pages are not known.

34. The system of claim 28, wherein the local timestamp module increments the local sequence at the particular node before setting the data page'"'"'s timestamp.

35. The system of claim 28, wherein the local timestamp module increases the local sequence to a value greater than an existing timestamp already on the data page if the existing timestamp is greater than the local timestamp.

36. The system of claim 28, wherein said allocation timestamp module sets the allocation page timestamp based on determining highest value of the allocation page timestamp, the local sequence, the data page'"'"'s timestamp, and, in event of a multiple page deallocation, the watermark.

37. The system of claim 36, wherein said allocation timestamp module incrementing said highest value before setting the allocation page timestamp.

38. The system of claim 28, wherein a node comprises a database server in the distributed database system.