Projection-based updates

Patent metadata

Field	Value
Publication number	US-10437809-B1
Application number	US-201514868086-A
Country	US
Kind code	B1
Filing date	Sep 28, 2015
Priority date	Sep 28, 2015
Publication date	Oct 8, 2019
Grant date	Oct 8, 2019

Abstract

A repository of key-value data may store a first object value having an internal structure of a hierarchy of sub-objects. The repository may receive a request to modify the first object, expressed as a projection of locations in the object to be updated and a function that, upon evaluation, returns values to be used to update the projected locations of the object. The repository may determine that the locations specified by the projections correspond to non-overlapping regions of the object and, based on the determination, update the object using the results of evaluating the function.

First claim

What is claimed is:

1. A system for updating objects maintained in a repository of key-value data, the system comprising:
one or more computing nodes configured as the repository of key-value data, the one or more computing nodes comprising instructions that, when executed by a processor of the one or more computing nodes, cause the system at least to:
receive a request to update an object stored in the repository of key-value data, the object comprising a hierarchy of sub-objects;
identify, in the request, one or more expressions indicative of forming versions of a first portion of the hierarchy of sub-objects and a second portion of the hierarchy of sub-objects;
identify, in the request, a first projection indicative of the first portion of the hierarchy of sub-objects to update based on the one or more expressions;
identify, in the request, a second projection indicative of the second portion of the hierarchy of sub-objects to update based on the one or more expressions;
determine that the first portion of the hierarchy of sub-objects indicated by the first projection does not overlap with the second portion of the hierarchy of sub-objects indicated by the second projection; and
update the first portion and second portion of the hierarchy of sub-objects, based at least in part on the one or more expressions, in response to the determination.

2. The system of claim 1 , wherein the first projection comprises an identifier indicative of a path from a root of the hierarchy of sub-objects to a location in the first portion of the hierarchy of sub-objects.

3. The system of claim 1 , wherein the one or more computing nodes comprise further instructions that, when executed by the processor, cause the system at least to:
receive an additional request to update the object;
identify, in the additional request, a first additional projection indicative of a first additional portion of the hierarchy of sub-objects;
identify, in the additional request, a second additional projection indicative of a second additional portion of the hierarchy of sub-objects; and
transmit information indicative of not updating the object in response to the additional request, based at least in part on determining that the first additional portion of the hierarchy of sub-objects overlaps with the second additional portion of the hierarchy of sub-objects.

4. The system of claim 1 , wherein the one or more expressions comprise an association between a projection and a specification of an immutable function.

5. The system of claim 1 ; wherein the updating the first portion of the hierarchy of sub-objects comprises forming a copy of the object in which the first portion of the hierarchy of sub-objects is replaced with a result of evaluating the one or more expressions.

6. A method comprising:
receiving a request to form a new version of an object stored on a storage device, the object comprising a hierarchy of sub-objects;
identifying, based at least in part on information included in the request, a first portion of the hierarchy of sub-objects to modify with a first result of evaluating one or more expressions included in the request to update the object;
identifying, based at least in part on information included in the request, a second portion of the hierarchy of sub-objects to modify with a second result of evaluating one or more expressions included in the request to update the object; and
forming the new version of the object by modifying the first portion and the second portion of the hierarchy of sub-objects partly in response to determining that the first portion of the hierarchy of sub-objects does not overlap with the second portion of the hierarchy of sub-objects.

7. The method of claim 6 , wherein identifying the first portion of the hierarchy of sub-objects comprises evaluating a first projection of the hierarchy of sub-objects specified by the request.

8. The method of claim 7 , wherein the first projection is indicative of a path from a root of the hierarchy of sub-objects to a location in the first portion of the hierarchy of sub-objects.

9. The method of claim 6 , further comprising:
receiving an additional request to update the object; and
determining to not update the object in response to the additional request, based at least in part on identifying a first additional portion of the hierarchy of sub-objects to update, identifying a second additional portion of the hierarchy of sub-objects to update, and determining that the first additional portion overlaps with the second additional portion.

10. The method of claim 6 , further comprising:
determining a first data type associated with the first result of evaluating the one or more expressions; and
determining to modify the first portion of the hierarchy based at least in part on the data type associated with the first result being compatible with a second data type associated with the second portion of the hierarchy.

11. The method of claim 6 , wherein the updating the first portion of the hierarchy of sub-objects comprises forming a copy of the object in which the first portion of the hierarchy of sub-objects is replaced with the first result of evaluating the one or more expressions.

12. The method of claim 6 , further comprising:
determining that all portions of the hierarchy of sub-objects to be updated with results of evaluating the one or more expressions are non-overlapping.

13. The method of claim 6 , further comprising:
mapping results of evaluating the one or more expressions to projections specified by the request, the projections identifying portions of the hierarchy of sub-objects to update.

14. A non-transitory computer-readable storage medium having stored thereon instructions that; upon execution by one or more computing devices, cause the one or more computing devices at least to:
receive a request to update an object stored in a data repository, the object comprising a hierarchy of sub-objects;
identify, based on a first expression included in the request, a first portion of the hierarchy of sub-objects to update with a first result of evaluating one or more expressions of the request to update the object;
identify, based on a second expression included in the request, a second portion of the hierarchy of sub-objects to update with a second result of evaluating the one or more expressions of the request to update the object; and
update the first portion and the second portion of the hierarchy of sub-objects partly in response to determining that the first portion of the hierarchy of sub-objects does not overlap with the second portion of the hierarchy of sub-objects, the first portion updated based at least in part on the first result, the second portion updated based at least in part on the second result.

15. The non-transitory computer-readable storage medium of claim 14 , comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:
identify the first portion of the hierarchy of sub-objects by at least evaluating first projection of the hierarchy of sub-objects specified by the request.

16. The non-transitory computer-readable storage medium of claim 14 , comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:
receive an additional request to update the object; and
determine to not update the object n response to the additional request; based at least in part on identifying a first additional portion of the hierarchy of sub-objects to update

Assignees

• Amazon Tech Inc

Inventors

• Xiao Wei
• Nieh Jeffrey Hocheng
• Ahmed Fahad
• Yanacek David Craig
• Budiman Andrew Desmond
• Shami Usman Ahmed

Classifications

• G06F16/83

  Querying · CPC title

• G06F16/23 Primary

  Updating · CPC title

• G06F16/2272

  Management thereof · CPC title