Memory efficient multi-versioned concurrency for a hypercube memory cache using anchor object pointers
AssigneeWorkday, Inc.
InventorsSrinivas Vemuri, Darren Lee
Life of this patent
Estimating the term…
Abstract
A system, method, and device for managing updates to a hypercube is provided. The method includes (i) obtaining a hypercube comprising a plurality of locations, wherein a particular location has an associated anchor object that stores version information for the particular location, (ii) receiving a request to store an updated value for the particular location, and (iii) storing the updated value for the particular location of hypercube, the updated value being stored with associated version information stored in the anchor object for the particular location.
Claims20
A system, comprising:
- one or more processors configured to:
- maintain a hypercube comprising a plurality of locations, wherein a location can store either a user-entered value or a formula;
- for each location, maintain an anchor object comprising separate input and computed snapshot chains;
- in response to a read request at a read timestamp for a location containing a formula:
- select a snapshot by performing the following in order:
- search the computed snapshot chain for a snapshot valid at the read timestamp, and if found, the found snapshot is deemed the selected snapshot;
- and
- in the absence of such a snapshot, obtain values valid at the read timestamp from the input chain, evaluate the formula, and append a new computed snapshot to the computed snapshot chain, wherein the newly appended snapshot is deemed the selected snapshot;
- and
- return the value from the selected snapshot;
- and
- a memory coupled to the processor and configured to provide the processor with instructions.
A method, comprising:
- maintaining a hypercube comprising a plurality of locations, wherein a location can store either a user-entered value or a formula;
- for each location, maintaining an anchor object comprising separate input and computed snapshot chains;
- in response to a read request at a read timestamp for a location containing a formula:
- selecting a snapshot by performing the following in order:
- searching the computed snapshot chain for a snapshot valid at the read timestamp, and if found, the found snapshot is deemed the selected snapshot;
- and
- in the absence of such a snapshot, obtaining values valid at the read timestamp from the input chain, evaluate the formula, and append a new computed snapshot to the computed snapshot chain, wherein the newly appended snapshot is deemed the selected snapshot;
- and
- returning the value from the selected snapshot.
A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:
- maintaining a hypercube comprising a plurality of locations, wherein a location can store either a user-entered value or a formula;
- for each location, maintaining an anchor object comprising separate input and computed snapshot chains;
- in response to a read request at a read timestamp for a location containing a formula:
- selecting a snapshot by performing the following in order:
- searching the computed snapshot chain for a snapshot valid at the read timestamp, and if found, the found snapshot is deemed the selected snapshot;
- and
- in the absence of such a snapshot, obtaining values valid at the read timestamp from the input chain, evaluate the formula, and append a new computed snapshot to the computed snapshot chain, wherein the newly appended snapshot is deemed the selected snapshot;
- and
- returning the value from the selected snapshot.
Dependencies are inferred from the claim text.