Sub-containment concurrency for hierarchical data containers

• US 8,856,089 B1
• Filed: 08/27/2010
• Issued: 10/07/2014
• Est. Priority Date: 08/27/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Briggs, Gregory J., Rohr, Vincent M.
• Primary Examiner(s): GOFMAN, ALEX N
• Application Number:
  US12/870,405
• Time in Patent Office: 1,502 Days
• Field of Search: 707/695, 707/705
• US Class Current: 707/695
• CPC Class Codes: G06F 16/2315 Optimistic concurrency control

Abstract

A sub-container concurrency component of a tiered middleware framework ensures optimistic concurrency for transactions on hierarchical data containers. The component identifies an uppermost container level of a data read for performing a requested data modification to one or more data containers. The component further reads one or more of a parent version value or a child version value of the data container in the uppermost container level at a first time and a second time. Thus, the component writes data to the one or more data containers when each version value, such as the parent version value or the child version value, read at the first time matches its corresponding read version value read at the second time.

Claims

1. A computer-implemented method, comprising:

identifying, via one or more computing devices, an uppermost container level of a data read for performing a requested data modification to one or more data containers;

reading, via at least one of the one or more computing devices, at least one of a parent version value or a child version value of a data container in the uppermost container level for a first time;

determining, via at least one of the one or more computing devices, data to write to the one or more data containers based at least in part on the requested data modification;

reading, via at least one of the one or more computing devices, the at least one of the parent version value or the child version value of the data container in the uppermost container level for a second time; and

performing, via at least one of the one or more computing devices, a plurality of activities when individual version values from the first read match the version value from the second read, the plurality of activities including;

writing the data to the one or more data containers;

changing the parent version value and the child version value for individual ones of the one or more data containers, the parent version value being distinct from the child version value;

changing the parent version value of individual data containers that are an ancestor to individual ones of the one or more data containers following the writing of the data to the one or more data containers; and

changing the child version value of individual data containers that are a descendent to individual ones of the one or more data containers following the writing of the data to the one or more data containers;

wherein the reading for the first time and the reading for the second time individually include reading both the parent version value and the child version value in response to the data container in the uppermost container level being a sub-container, and wherein the changing the at least one of the parent version value or child version value includes updating both the parent version value and the child version value for the data container that is the sub-container.

2. The computer-implemented method of claim 1, further comprising aborting a data write to the one or more data containers when at least one version value read at the first time does not match the version value read at the second time.

3. The computer-implemented method of claim 1, wherein the reading for the first time and the reading for the second time individually include reading the parent version value when the data container in the uppermost container level is a root container, and wherein the changing the at least one of the parent and child version values includes updating the parent version value for the data container that is the root container.

4. The computer-implemented method of claim 1, wherein individual ones of the parent version values or individual ones of the child version values are globally unique identifiers, current real times, or current Lamport times.

5. A computer-implemented method, comprising:

identifying, via one or more computing devices, an uppermost container level of a data read for performing a requested data modification to one or more data containers;

reading, via at least one of the one or more computing devices, at least one of a parent version value or a child version value of a data container in the uppermost container level at a first time and a second time, wherein the reading for the first time and the reading for the second time individually include reading both the parent version value and the child version value in response to the data container in the uppermost container level being a sub-container; and

in response to determining that an individual version value of the data container read at the first time matches the individual version value read at the second time;

writing, via at least one of the one or more computing devices, data to the one or more data containers,

updating, via at least one of the one or more computing devices, the parent version value of at least one ancestor data container to the one or more data containers or updating the child version value of at least one descendent data container to the one or more data containers, and

changing, via at least one of the one or more computing devices, both the parent version value and the child version value of the data container in the uppermost container level when the data container in the uppermost container level is a sub-container.

6. The computer-implemented method of claim 5, further comprising aborting a data write to the one or more data containers when individual version values read at the first time do not match themselves as read at the second time.

7. The computer-implemented method of claim 5, wherein the reading for the first time and the reading for the second time individually include reading the parent version value when the data container in the uppermost container level is a root container.

8. The computer-implemented method of claim 5, further comprising updating the at least one of the parent and child version values for individual ones of the one or more data containers when individual version values read at the first time match themselves as read at the second time.

9. The computer-implemented method of claim 8, wherein the updating the at least one of the parent and child version values includes updating the parent version value for the data container that is the root container or updating both the parent version value and the child version value for the data container that is the sub-container.

10. The computer-implemented method of claim 5, wherein individual ones of the parent version values or individual ones of the child version values are globally unique identifiers, current real times, or current Lamport times.

11. The computer-implemented method of claim 5, where the one or more data containers includes at least one data container that is nested inside another data container.

12. The computer-implemented method of claim 5, wherein the performing includes performing the requested data modification via an application process, and wherein the at least one of the parent version value or the child version value of the data container in the uppermost container level is updated when data in the data container in the uppermost container level is modified by another application process.

13. The computer-implemented method of claim 5, wherein the performing includes performing the requested data modification via an application process, and wherein the at least one of the parent version value or the child version value of the data container in the uppermost container level is updated when data in an ancestor data container, a sibling data container, or a descendant data container of the data container in the uppermost container level is modified by another application process.

14. One or more non-transitory computer readable media storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

identifying an uppermost container level of a data read for an application process to perform a requested data modification to data containers stored in at least one non-blob data store;

reading a parent version value and a child version value of a sibling data container in the uppermost container level at a first time and a second time, the parent version value of the sibling data container being distinct from the child version value of the sibling data container;

writing data to one or more data containers when the version value of the sibling data container read at the first time matches the version value read at the second time;

updating both the parent version value and the child version value of the sibling data container upon writing the data;

aborting a data write to the one or more data containers in response to at least one of the version values of the sibling data container read at the first time failing to match the corresponding version value read at the second time; and

updating at least one of the parent version value of individual ancestor data containers or the child version value of individual descendent data containers of individual sibling data containers in response to individual version values of the individual sibling data containers read at the first time matching the individual version values read at the second time.

15. The one or more non-transitory computer readable media of claim 14, wherein individual ones of the parent version values or individual ones of the child version values are globally unique identifiers, current real times, or current Lamport time.

16. The one or more non-transitory computer readable media of claim 14, wherein the data containers includes at least one data container that is nested inside another data container.

17. The one or more non-transitory computer readable media of claim 14, wherein the parent version value or the child version value of a sibling data container in the uppermost container level is updated when data in the sibling data container is modified by another application process.

18. The one or more non-transitory computer readable media of claim 14, wherein the parent version value or the child version value of a sibling data container in the uppermost container level is updated when data in an additional data container in the uppermost container is modified by another application process.

19. One or more non-transitory computer readable media storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

identifying an uppermost container level of a data read for performing a requested data modification to one or more data containers;

reading a blob version value of a data blob that includes a data container in the uppermost container level for a first time and a second time, the data container in the uppermost container level having a parent version value and a child version value,

changing the blob version value when at least one of the parent version value or the child version value of the data container in the uppermost container level is updated;

writing data to the one or more data containers when the blob version value read at the first time matches the blob version value read at the second; and

updating both the parent version value and the child version value of the data container in the uppermost container in response to writing data to the one or more data containers when the uppermost data container is a sub-container.

20. The one or more non-transitory computer readable media of claim 19, further comprising instructions that, when executed, cause the one or more processors to perform an act of aborting a data write to the one or more data containers when the blob version value read at the first time does not match the blob version value read at the second time.

21. The one or more non-transitory computer readable media of claim 19, further comprising instructions that, when executed, cause the one or more processors to perform an act of updating the at least one of the parent and child version values for individual ones of the one or more data containers when the blob version value read at the first time matches the blob version value read at the second time.

22. The one or more non-transitory computer readable media of claim 21, wherein the updating the at least one of the parent and child version values includes updating the parent version value for the data container when the data container in the uppermost level is a root container.

23. The one or more non-transitory computer readable media of claim 19, further comprising instructions that, when executed, cause the one or more processors to perform at least one of updating the parent version value of individual ancestor data containers to individual ones of the one or more data containers or updating the child version value of individual descendent data containers to individual ones of the one or more data containers when the blob version value read at the first time matches the blob version value read at the second time.

24. The one or more non-transitory computer readable media of claim 19, wherein the blob version value, individual parent version values or individual child version values are globally unique identifiers, current real times, or current Lamport times.

25. The one or more non-transitory computer readable media of claim 19, where the one or more data containers includes at least one data container that is nested inside another data container.

26. The one or more non-transitory computer readable media of claim 19, wherein the performing includes performing the requested data modification via an application process, and wherein the blob version value is changed when data in the data container in the uppermost container level is modified by another application process.

27. The one or more non-transitory computer readable media of claim 19, wherein the performing includes performing the requested data modification via an application process, and wherein blob version value is changed when data in an ancestor data container, a sibling data container, or a descendant data container of the data container in the uppermost container level is modified by another application process.

28. The one or more non-transitory computer readable media of claim 19, wherein the at least one of a parent version value or a child version value is stored as prefix data or suffix data in the data container.