Conditional updates for reducing frequency of data modification operations

• US 9,626,399 B2
• Filed: 07/21/2014
• Issued: 04/18/2017
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: O'Krafka, Brian W., Chiu, Patrick, Chander, Ramesh, Wang, Zhengheng
• Primary Examiner(s): Lewis, Cheryl
• Application Number:
  US14/336,949
• Publication Number:
  US 20150278283A1
• Time in Patent Office: 1,002 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

A computer system detects a request, from a requestor, to access a first data object stored in a tiered data structure that includes internal nodes and leaf nodes. In response to detecting the request to access the first data object, the computer system retrieves a leaf node that includes the first data object and locks the leaf node that includes the first data object. While the leaf node that includes the first data object is locked, the computer system transmits, to the requestor, a first conditional-update communication and detecting a first conditional-update response in response to the first conditional-update communication. In response to detecting the first conditional-update response corresponding to the first data object, the computer system performs one or more operations based on the first conditional-update response corresponding to the first data object before unlocking the leaf node that includes the first data object.

Claims

1. A method, performed by a computer system having one or more processors and memory, the method comprising:

detecting a request, received from a requestor, to access a first data object stored in a tiered data structure, the tiered data structure stored in one or more memory devices, wherein the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes, and wherein the request comprises a conditional request to modify the first data object;

in response to detecting the request to access the first data object;

retrieving a leaf node that includes the first data object, wherein the leaf node is a leaf node in the tiered data structure; and

locking the leaf node that includes the first data object;

while the leaf node that includes the first data object is locked;

transmitting, to the requestor, a first conditional-update communication that includes an indication of a current value of the first data object;

detecting a first conditional-update response to the first conditional-update communication, the detected first conditional-update response received from the requestor and corresponding to the first data object; and

in response to detecting the first conditional-update response, performing one or more operations based on the first conditional-update response; and

after performing the one or more operations based on the first conditional-update response, unlocking the leaf node that includes the first data object.

2. The method of claim 1, wherein two or more of the plurality of leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value.

3. The method of claim 1, wherein the leaf node that includes the first data object is write-locked while the first conditional-update communication is transmitted and the first conditional-update response is detected.

4. The method of claim 1, wherein:

retrieving the leaf node includes traversing the tiered data structure by navigating through one or more internal nodes to the leaf node that includes the first data object; and

the method further comprises;

after traversing through the one or more internal nodes, read-locking the one or more internal nodes that were traversed to reach the leaf node that includes the first data object.

5. The method of claim 1, wherein:

the first conditional-update communication provides information that enables the requestor to determine whether or not to update the value of the first data object based on the current value of the first data object; and

performing the one or more operations based on the first conditional-update response includes;

in accordance with a determination that the first conditional-update response includes a request to update the value of the first data object, updating the value of the first data object in accordance with the first conditional-update response; and

in accordance with a determination that the first conditional-update response does not include a request to update the value of the first data object, forgoing updating the value of the first data object.

6. The method of claim 1, wherein:

the request to access the first data object identifies a plurality of data objects including the first data object and a second data object, wherein the leaf node that includes the first data object also includes the second data object; and

the method further comprises;

while the leaf node that includes the first data object is locked, and after performing the one or more operations based on the first conditional-update response;

transmitting, to the requestor, a second conditional-update communication that includes an indication of a current value of the second data object;

detecting a second conditional-update response to the second conditional-update communication, the detected second conditional-update response received from the requestor and corresponding to the second data object; and

in response to detecting the second conditional-update response, performing one or more operations based on the second conditional-update response; and

wherein the leaf node that includes the first data object and second data object is unlocked after the one or more operations based on the second conditional-update response are performed.

7. The method of claim 1, wherein:

the first conditional-update communication includes an executable callback object; and

the first conditional-update response corresponds to a result generated based on execution of the callback object.

8. A computer system, comprising:

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

detecting a request, received from a requestor, to access a first data object stored in a tiered data structure, the tiered data structure stored in one or more memory devices, wherein the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes, and wherein the request comprises a conditional request to modify the first data object;

in response to detecting the request to access the first data object;

retrieving a leaf node that includes the first data object, wherein the leaf node is a leaf node in the tiered data structure; and

locking the leaf node that includes the first data object;

while the leaf node that includes the first data object is locked;

transmitting, to the requestor, a first conditional-update communication that includes an indication of a current value of the first data object;

detecting a first conditional-update response to the first conditional-update communication, the detected first conditional-update response received from the requestor and corresponding to the first data object; and

in response to detecting the first conditional-update response, performing one or more operations based on the first conditional-update response; and

after performing the one or more operations based on the first conditional-update response, unlocking the leaf node that includes the first data object.

9. The computer system of claim 8, wherein two or more of the plurality of leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value.

10. The computer system of claim 8, wherein the leaf node that includes the first data object is write-locked while the first conditional-update communication is transmitted and the first conditional-update response is detected.

11. The computer system of claim 8, wherein:

retrieving the leaf node includes traversing the tiered data structure by navigating through one or more internal nodes to the leaf node that includes the first data object; and

the one or more programs further include instructions for;

read-locking the one or more internal nodes that were traversed to reach the leaf node that includes the first data object after traversing through the one or more internal nodes.

12. The computer system of claim 8, wherein:

the first conditional-update communication provides information that enables the requestor to determine whether or not to update the value of the first data object based on the current value of the first data object; and

performing the one or more operations based on the first conditional-update response includes;

updating the value of the first data object in accordance with the first conditional-update response in accordance with a determination that the first conditional-update response includes a request to update the value of the first data object; and

forgoing updating the value of the first data object in accordance with a determination that the first conditional-update response does not include a request to update the value of the first data object.

13. The computer system of claim 8, wherein:

the request to access the first data object identifies a plurality of data objects including the first data object and a second data object, wherein the leaf node that includes the first data object also includes the second data object;

while the leaf node that includes the first data object is locked, and after performing the one or more operations based on the first conditional-update response, the one or more programs further include instructions for;

transmitting, to the requestor, a second conditional-update communication that includes an indication of a current value of the second data object;

detecting a second conditional-update response to the second conditional-update communication, the detected second response received from the requestor and corresponding to the second data object; and

performing one or more operations based on the second conditional-update response in response to detecting the second conditional-update response; and

wherein the leaf node that includes the first data object and second data object is unlocked after the one or more operations based on the second conditional-update response are performed.

14. The computer system of claim 8, wherein:

the first conditional-update communication includes an executable callback object; and

the first conditional-update response corresponds to a result generated based on execution of the callback object.

15. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer system with one or more processors, cause the computer system to:

detect a request, received from a requestor, to access a first data object stored in a tiered data structure, the tiered data structure stored in one or more memory devices, wherein the tiered data structure includes a plurality of internal nodes and a plurality of leaf nodes, and wherein the request comprises a conditional request to modify the first data object;

in response to detecting the request to access the first data object;

retrieve a leaf node that includes the first data object, wherein the leaf node is a leaf node in the tiered data structure; and

lock the leaf node that includes the first data object;

while the leaf node that includes the first data object is locked;

transmit, to the requestor, a first conditional-update communication that includes an indication of a current value of the first data object;

detect a first conditional-update response to the first conditional-update communication, the detected first conditional-update response received from the requestor and corresponding to the first data object; and

in response to detecting the first conditional-update response, perform one or more operations based on the first conditional-update response; and

after performing the one or more operations based on the first conditional-update response, unlock the leaf node that includes the first data object.

16. The non-transitory computer readable storage medium of claim 15, wherein two or more of the plurality of leaf nodes each include multiple data objects, each of the data objects including unique key information and a corresponding value.

17. The non-transitory computer readable storage medium of claim 15, wherein the leaf node that includes the first data object is write-locked while the first conditional-update communication is transmitted and the first conditional-update response is detected.

18. The non-transitory computer readable storage medium of claim 15, wherein:

retrieving the leaf node includes traversing the tiered data structure by navigating through one or more internal nodes to the leaf node that includes the first data object; and

the one or more programs further comprise instructions which cause the computer system to;

read-lock the one or more internal nodes that were traversed to reach the leaf node that includes the first data object after traversing through the one or more internal nodes.

19. The non-transitory computer readable storage medium of claim 15, wherein:

the first conditional-update communication provides information that enables the requestor to determine whether or not to update the value of the first data object based on the current value of the first data object; and

performing the one or more operations based on the first conditional-update response includes;

updating the value of the first data object in accordance with the first conditional-update response in accordance with a determination that the first conditional-update response includes a request to update the value of the first data object; and

forgoing updating the value of the first data object in accordance with a determination that the first conditional-update response does not include a request to update the value of the first data object.

20. The non-transitory computer readable storage medium of claim 15, wherein:

the request to access the first data object identifies a plurality of data objects including the first data object;

while the leaf node that includes the first data object is locked, and after performing the one or more operations based on the first conditional-update response corresponding to the first data object, the one or more programs further comprise instructions which cause the computer system to;

transmit, to the requestor, a second conditional-update communication that includes an indication of a current value of the second data object;

detect a second conditional-update response to the second conditional-update communication, the detected second response received from the requestor and corresponding to the second data object; and

perform one or more operations based on the second conditional-update response in response to detecting the second conditional-update response; and

wherein the leaf node that includes the first data object and second data object is unlocked after the one or more operations based on the second conditional-update response are performed.

21. The non-transitory computer readable storage medium of claim 15, wherein:

the first conditional-update communication includes an executable callback object; and

the first conditional-update response corresponds to a result generated based on execution of the callback object.