Method for retrieving and modifying data elements on a shared medium

• US 7,324,995 B2
• Filed: 11/17/2003
• Issued: 01/29/2008
• Est. Priority Date: 11/17/2003
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Rackable Systems Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: McCauley, Steven R., Sastri, Gautham, Findleton, Iain B., Zhou, Xinliang
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/714,398
• Publication Number:
  US 20050108231A1
• Time in Patent Office: 1,534 Days
• Field of Search: 707/8, 707/203, 707/200, 707/201, 709/213, 709/214, 711/150
• US Class Current: 1/1
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for retrieving and modifying data elements on a shared medium following request from multiple client computers, such that data retrieval transactions on a data element, originating from one or more clients, are not compromised by data update transactions on the same data element originating from other clients. The shared medium controller receives from multiple clients transaction requests for reading or writing a data element stored on the shared medium. The transactions requests are added to an execution queue in order. All read transaction requests are then retrieved and executed in parallel, up to a write transaction request on the data element. The write transaction request is then executed while all incoming read transaction requests for the same data element are queued until the write transaction request is completed.

Claims

1. A method for retrieving and modifying data elements on a shared medium, comprising:

receiving at a shared medium controller, and from multiple clients, transaction requests, each of said transaction requests being for at least one of reading and writing a data element on said shared medium;

adding said transaction requests to an execution queue in order;

retrieving from said execution queue all read transaction requests for said data element;

executing all of said read transaction requests for said data element in parallel, until a write transaction request for said data element is retrieved from said execution queue, and according to said order;

executing said write transaction request for said data element and queuing all incoming read transaction requests for said data element until said write transaction request is completed;

determining and changing a state associated with said data element for each of said executing of said transaction requests, said state stored in said shared medium controller; and

whereby data retrieval transactions on said data element, originating from one or more clients, are not compromised by data update transactions on said data element originating from other clients.

2. The method as claimed in claim 1, further comprising:

checking whether a version state associated with said data element is locked;

if said version state is locked,

adding said transaction request for said data element to an execution queue;

if said version state is not locked,

executing said transaction request right away.

3. The method as claimed in claim 2, wherein said version state is locked following a transaction request originating from a client.

4. The method as claimed in claim 1, wherein said data elements are referred to as pointers defining an address range.

5. The method as claimed in claim 4, wherein a read transaction for multiple data elements is executed for all of said data elements which are not waiting for a pending write transaction, and following completion of said pending write transaction, remaining data elements are read.

6. The method as claimed in claim 4, wherein said shared medium controller maintains a list of version state information associated with said data elements on said shared medium and following modification of said data elements, said shared medium controller creates a new data structure in said list containing a new version state of said data elements and associating said new version state with a part of said data elements that has been modified.

7. The method as claimed in claim 6, wherein if said data elements being modified are associated with multiple separate data structures containing version states, creating a new single data structure in said list associated with all modified said data elements and removing said multiple separate data structures from said list.

8. The method as claimed in claim 6, wherein said version state is an initial version number and wherein said initial version number is incremented to obtain said new version state.

9. The method as claimed in claim 6, wherein said list of data structures is a double linked binary tree list.

10. The method as claimed in claim 1, wherein said read transaction request and execution comprises:

providing to said shared medium controller a client-stored version state information associated with said data element to be read;

comparing said client-stored version state information associated with said data element with a shared medium-stored state information;

sending back to originating client a confirmation that said client-stored version state information and the contents of said data element are accurate.

11. The method as claimed in claim 1, wherein said shared medium controller is physically located with the shared medium.

12. A method for executing a common task in a clustered computing environment comprising a plurality of computers interconnected to collaborate on said common task, said plurality of computers including at least a client computer and a shared storage medium storing data elements, comprising:

receiving at a shared medium controller, and from said plurality of client computers working on a same task, transaction requests, each of said transaction requests being for at least one of reading and writing a data element on said shared storage medium;

adding said transaction requests to an execution queue in order;

retrieving from said execution queue all read transaction requests for said data element;

executing all said read transaction requests for said data element in parallel, until a write transaction request for said data element is retrieved from said execution queue, and according to said order;

executing said write transaction request for said data element and queuing all incoming read transaction requests for said data element in said execution queue in order until said write transaction request is completed;

determining and changing a state associated with said data element for each of said executing of said transaction requests, said state stored in said shared medium controller; and

at least one of said plurality of computers modifying said data element stored on said shared storage medium;

said client computer retrieving said data element stored and using said data element stored to execute said common task;

whereby data retrieval transactions on said data element, originating from one or more client computers, are not compromised by data update transactions on said data element originating from other client computers.

13. The method as claimed in claim 12, further comprising:

checking whether a version state associated with said data element is locked;

if said version state is locked,

adding said transaction request for said data element to an execution queue;

if said version state is not locked,

executing said transaction request right away.

14. The method as claimed in claim 13, wherein said version state is locked following a transaction request originating from a client.

15. The method as claimed in claim 12, wherein said data elements are referred to as pointers defining an address range.

16. The method as claimed in claim 15, wherein a read transaction for multiple data elements is executed for all of said data elements which are not waiting for a pending write transaction, and following completion of said pending write transaction, remaining data elements are read.

17. The method as claimed in claim 15, wherein said shared medium controller maintains a list of version state information associated with said data elements on said shared medium and following modification of said data elements, said shared medium controller creates a new data structure in said list containing a new version state of said data elements and associating said new version state with a part of said data elements that has been modified.

18. The method as claimed in claim 17, wherein if said data elements being modified are associated with multiple separate data structures containing version states, creating a new single data structure in said list associated with all modified said data elements and removing said multiple separate data structures from said list.

19. The method as claimed in claim 17, wherein said version state is an initial version number and wherein said initial version number is incremented to obtain said new version state.

20. The method as claimed in claim 17, wherein said list of data structures is a double linked binary tree list.

21. The method as claimed in claim 12, wherein said read transaction request and execution comprises:

providing to said shared medium controller a client-stored version state information associated with said data element to be read;

comparing said client-stored version state information associated with said data element with a shared medium-stored state information;

sending back to originating client a confirmation that said client-stored version state information and the contents of said data element are accurate.

22. The method as claimed in claim 12, wherein said shared medium controller is physically located with the shared medium.