Merge-update for efficient atomic memory modification in concurrent computer systems
Atomically updating an in-memory data structure that is directly accessible by a processor includes comparing old information associated with an old version of the in-memory data structure with current information associated with a current version of the in-memory data structure; in the event that the old information and the current information are the same, replacing the old version with a new version of the in-memory data structure; in the event that the old information and the current information are not the same, determining a difference between the current version of the in-memory data structure and the new version of the in-memory data structure, and determining whether the difference is logically consistent; and in the event that the difference is logically consistent, merging a change in the current version with the new version.
1. A method for atomically updating an in-memory data structure that is directly accessible by a processor, comprising:
comparing old information associated with an old version of the in-memory data structure with current information associated with a current version of the in-memory data structure;
in the event that the old information and the current information are the same, replacing the old version with a new version of the in-memory data structure;
in the event that the old information and the current information are not the same, determining a difference between the current version of the in-memory data structure relative to the old version of the in-memory data structure and the new version of the in-memory data structure relative to the old version of the in-memory data structure, and determining whether the difference is logically consistent, wherein a logically consistent difference pertains to concurrent modifications to the current version of the in-memory data structure and the new version of the in-memory data structure that are resolvable to arrive at a predictable memory state; and
in the event that the difference is logically consistent, merging a change in the current version with the new version.
2. The method of claim 1 , further comprising, in the event that the difference is logically consistent, replacing the current version with the new version that includes the merged change.
3. The method of claim 1 , wherein the old version of the in-memory data structure and the new version of the in-memory data structure are represented as directed acyclic graphs (DAGs).
4. The method of claim 3 , wherein determining the difference includes comparing portions of the DAGs.
5. The method of claim 3 , wherein determining the difference includes comparing portions of the DAGs and determining that at least some portions of the DAGs are identical.
6. The method of claim 1 , further comprising determining all differences between the current version of the in-memory data structure and the new version of the in-memory data structure and whether the differences are logically consistent.
7. The method of claim 1 , further comprising, in the event that the difference is not logically consistent, handling merge failure.
8. The method of claim 1 , wherein the in-memory data structure is stored in structured memory that is immutable.
9. The method of claim 1 , wherein the in-memory data structure is stored in structured memory that is deduplicated.
10. The method of claim 1 , wherein whether the difference is logically consistent is determined based at least in part on a logical consistency constraint selected from a plurality of potential logical consistency constraints.
11. The method of claim 1 , wherein the difference is logically consistent if at least a current version of a leaf node in the in-memory data structure or a new version of the leaf node is the same as an old version of the leaf node.
12. The method of claim 1 , wherein the difference is logically consistent if a leaf node in the in-memory data structure corresponds to a value that can be incremented or decremented.
13. The method of claim 12 , wherein merging the change in the current version with the new version includes evaluating a sum of a current version of the leaf node and a difference between a new version of the leaf node and an old version of the leaf node.
14. The method of claim 1 , wherein determining the difference between the current version of the in-memory data structure includes receiving a difference data structure that includes entries that indicate changes between the current version of the in-memory data structure and the new version of the in-memory data structure.
15. The method of claim 1 , wherein the new version of the in-memory data structure includes a difference data structure that includes changes to the old version of the in-memory data structure.
16. The method of claim 1 , wherein:
the in-memory data structure includes a value; and
merging the change in the current version with the new version includes performing an incremental merge-update of the value.
17. The method of claim 1 , wherein:
the in-memory data structure includes a value; and
merging the change in the current version with the new version includes performing an override merge-update of the value according to an override merge-update policy.
18. The method of claim 1 , wherein:
the in-memory data structure includes a nested data structure; and
merging the change in the current version with the new version includes performing merging recursively.
19. The method of claim 1 , wherein merging the change in the current version with the new version is performed in hardware.
20. A system for atomically updating an in-memory data structure that is directly accessible by a processor, comprising:
the processor configured to:
compare old information associated with an old version of the in-memory data structure with current information associated with a current version of the in-memory data structure;
in the event that the old information and the current information are the same, replace the old version with a new version of the in-memory data structure;
in the event that the old information and the current information are not the same, determine a difference between the current version of the in-memory data structure relative to the old version of the in-memory data structure and the new version of the in-memory data structure relative to the old version of the in-memory data structure, and determine whether the difference is logically consistent, wherein a logically consistent difference pertains to concurrent modifications to the current version of the in-memory data structure and the new version of the in-memory data structure that are resolvable to arrive at a predictable memory state; and
in the event that the difference is logically consistent, merge a change in the current version with the new version; and
a memory coupled to the processor and configured to provide the processor with instructions.