Back to results
US 12,222,922 B2Granted
Versioning of items in a data structure
AssigneeMicrosoft Technology Licensing, LLC
InventorsAleksandar Dragojevic, Junyi Liu, Antonios Katsarakis
Life of this patent
Estimating the term…
Abstract
A system comprising: memory storing a data structure comprising a plurality of items, each item comprising a key-value pair; a writer arranged to perform a plurality of write operations each to write a respective item, either a new item being added to the data structure or an existing item being modified in the data structure; and a reader configured to perform a group-read operation to read from the data structure any items having keys in a specified range. The writer is configured to maintain a global write version and the reader is configured to maintain a global read version.
Claims15
A system comprising:
- memory storing a data structure comprising a plurality of items, each item comprising a key-value pair;
- a writer arranged to perform a plurality of write operations each to write a respective item, either a new item being added to the data structure or an existing item being modified in the data structure;
- and
- a reader configured to perform a group-read operation to read from the data structure any items having keys in a specified range;
- wherein the writer is configured to maintain a global write version and the reader is configured to maintain a global read version;
- the writer is configured to perform each of the write operations by:
- i) reading and then incrementing the global write version, ii) writing the respective item in the data structure, including versioning the respective item with a respective version number equal to the global write version as read by the respective write operation prior to the increment, and then iii) generating a release indicator indicating the respective version number;
- the writer is configured to send release signals corresponding to at least some of the release indicators to the reader, each release signal signalling the respective version number, but to refrain from sending release signals corresponding to any release indicator indicating a higher respective version number before the release indicators indicating all lower version numbers have been generated;
- the reader is configured so as, upon receiving each release signal sent by the writer, to update the global read version to be equal to the respective version number as signalled in the release signal;
- and
- the reader is configured to perform the group-read operation by:
- reading the global read version at the start of the group-read operation, and then selectively reading items from the specified range of keys in the data structure based on having version numbers equal to or less than the global read version as read at the start of the group-read operation, passing over items in the specified range that have a greater version number.
9 more elements
A method comprising:
- storing a data structure comprising a plurality of items, each item comprising a key-value pair;
- by a writer, performing a plurality of write operations each to write a respective item, either a new item being added to the data structure or an existing item being modified in the data structure;
- and
- by a reader, performing a group-read operation to read from the data structure any items having keys in a specified range;
- wherein the writer maintains a global write version and the reader maintains a global read version;
- wherein each of the write operations comprises:
- i) reading and then incrementing the global write version, ii) writing the respective item in the data structure, including versioning the respective item with a respective version number equal to the global write version as read by the respective write operation prior to the increment, and then iii) generating a release indicator indicating the respective version number;
- wherein the method comprises the writer sending release signals corresponding to at least some of the release indicators to the reader, each release signal signalling the respective version number, but refraining from sending release signals corresponding to any release indicator indicating a higher respective version number before the release indicators indicating all lower version numbers have been generated;
- wherein the reader, upon receiving each release signal sent by the writer, updates the global read version to be equal to the respective version number as signalled in the release signal;
- and
- wherein the group-read operation comprises:
- reading the global read version at the start of the group-read operation, and then selectively reading items from the specified range of keys in the data structure based on having version numbers equal to or less than the global read version as read at the start of the group-read operation, passing over items in the specified range that have a greater version number.
9 more elements
A computer program embodied on computer-readable storage, the program comprising code configured so as when run on one or more processors to perform the operations of:
- storing a data structure comprising a plurality of items, each item comprising a key-value pair;
- by a writer, performing a plurality of write operations each to write a respective item, either a new item being added to the data structure or an existing item being modified in the data structure;
- and
- by a reader, performing a group-read operation to read from the data structure any items having keys in a specified range;
- wherein the writer maintains a global write version and the reader maintains a global read version;
- wherein each of the write operations comprises:
- i) reading and then incrementing the global write version, ii) writing the respective item in the data structure, including versioning the respective item with a respective version number equal to the global write version as read by the respective write operation prior to the increment, and then iii) generating a release indicator indicating the respective version number;
- wherein the method comprises the writer sending release signals corresponding to at least some of the release indicators to the reader, each release signal signalling the respective version number, but refraining from sending release signals corresponding to any release indicator indicating a higher respective version number before the release indicators indicating all lower version numbers have been generated;
- wherein the reader, upon receiving each release signal sent by the writer, updates the global read version to be equal to the respective version number as signalled in the release signal;
- and
- wherein the group-read operation comprises:
- reading the global read version at the start of the group-read operation, and then selectively reading items from the specified range of keys in the data structure based on having version numbers equal to or less than the global read version as read at the start of the group-read operation, passing over items in the specified range that have a greater version number.
9 more elements
Dependencies are inferred from the claim text.