Memory efficient multi-versioned concurrency for a hypercube memory cache using anchor object pointers

Patent metadata

Field	Value
Publication number	US-12561307-B2
Application number	US-202318522728-A
Country	US
Kind code	B2
Filing date	Nov 29, 2023
Priority date	Nov 29, 2023
Publication date	Feb 24, 2026
Grant date	Feb 24, 2026

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.

First claim

What is claimed is:

1 . A system, comprising:
one or more processors configured to:
obtain a hypercube comprising a plurality of locations, wherein each of the plurality of locations has a uniquely associated anchor object comprising a snapshot chain object that indexes a set of one or more snapshots for that location, wherein:
(i) each snapshot has an associated validity period defined by a start timestamp and an end timestamp;
(ii) each location in the hypercube corresponds to a coordinate tuple; and
(iii) each anchor object is a data structure record comprising (a) a location identifier that uniquely identifies the corresponding coordinate for the location in the hypercube, (b) a snapshot-chain reference comprising at least one pointer to the snapshot chain object, and (c) version metadata for the location;

receive a request to store an updated value for the particular location; and
store the updated value for the particular location of the hypercube, wherein storing the updated value comprises adding a snapshot corresponding to the updated value comprises adding a new snapshot corresponding to the updated value to the snapshot chain object in the anchor object for the location and setting the validity period for the new snapshot;
receive a request to obtain data from the hypercube with respect to a planning model;
determine a set of locations within the hypercube comprising data to be used in connection with providing a response to the request;
obtain the data for the set of locations based at least in part on a set of anchor objects for the set of locations by selecting, for each location, the snapshot from the corresponding anchor object's snapshot chain object having a validity period matching a timestamp associated with the request; and
provide a response to the request based at least in part on the data for the set of locations; and
a memory coupled to the processor and configured to provide the processor with instructions.

2 . The system of claim 1 , wherein the one or more snapshots for the particular location comprises a pointer to snapshot information for the particular location, and the snapshot information is associated with a corresponding validity period.

3 . The system of claim 2 , wherein the corresponding validity period comprises a start date and an end date.

4 . The system of claim 3 , wherein the start date for the snapshot information corresponding to the updated value stored for the particular location is a date at which the updated value is stored for the particular location.

5 . The system of claim 4 , wherein the end date for the snapshot information corresponding to the updated value stored for the particular location is set as a time at which a next update to a value for the particular location is modified or as an undefined period if the updated value is a most recent value for the particular location.

6 . The system of claim 2 , wherein the one or more processors are further configured to:
receive, from a reading process, a request to obtain a corresponding value for the particular location; determine a timestamp associated with the reading process; determine that a snapshot chain indexed in the anchor object for the particular location has as an associated snapshot having a validity period matching the timestamp; and in response to determining that the snapshot chain indexed in the anchor object for the particular location has the associated snapshot, obtain a value for the particular location based at least in part on the associated snapshot.

7 . The system of claim 2 , wherein the one or more processors are further configured to:
receive, from a reading process, a request to obtain a corresponding value for the particular location; and take a snapshot of a current value for the particular location and store the snapshot in the anchor object for the particular location.

8 . The system of claim 2 , wherein the one or more processors are further configured to:
receive, from a reading process, a request to obtain a corresponding value for the particular location; determine a timestamp associated with the reading process; determine that a snapshot chain indexed in the anchor object has as a snapshot having a validity period matching the timestamp; and in response to determining that the snapshot chain indexed in the anchor object has the snapshot matching the timestamp, provide a value for the particular location based at least in part on the snapshot matching the timestamp.

9 . The system of claim 2 , wherein the one or more processors are further configured to:
receive, from a reading process, a request to obtain a corresponding value for the particular location; determine a timestamp associated with the reading process; determine that a snapshot chain index in the anchor object for the particular location does not have a first snapshot having a validity period matching the timestamp; and capture a second snapshot of a value at the particular location in response to determining that the snapshot chain does not comprise the snapshot; and store the second snapshot for the particular location.

10 . The system of claim 9 , wherein the version information comprised in the anchor object is updated to include a validity period for the second snapshot.

11 . The system of claim 9 , wherein the validity period for the first snapshot is updated based at least in part on the second snapshot being captured.

12 . The system of claim 1 , wherein the version information comprises a snapshot chain object that indexes a set of snapshots for the particular location.

13 . The system of claim 1 , wherein the anchor object stores a set of pointers to a set of snapshots that form a history of changes of the value at the particular location over time.

14 . The system of claim 1 , wherein the anchor object is used for a location containing at least one of a defined alphanumeric value and a formula from which a derived value for the particular location is determined, and storing the value for a location comprising a formula entails the creation of a hybrid input-computed chain object which has separate inner chains for user entered values and for reader generated snapshots for derived values.

15 . The system of claim 1 , wherein the processor is further configured to search for a matching snapshot comprising (a) first searching a computed chain and in response to finding a matching snapshot, returning the matching snapshot, and (b) second, in the absence of a matching snapshot in the computed chain, searching an input chain, and in response to finding a matching snapshot in the input chain, evaluating a formula and adding a new snapshot in the computed chain.

16 . The system of claim 1 , wherein the anchor object for the particular location comprises a set of pointers for a set of snapshots stored in a snapshot database, and a cleanup operation is performed with respect to the set of snapshots.

17 . The system of claim 16 , wherein the cleanup operation includes removing a subset of the snapshots from snapshot database in response to a determination that a predefined criteria is satisfied.

18 . The system of claim 17 , wherein performing the cleanup operation comprises:
determining an earliest reading process among a set of current reading processes that read data stored in the hypercube; determining the subset snapshots having a respective validity period that terminates before a timestamp associated with the earliest reading process; and removing the subset snapshots from the

Assignees

• Workday Inc

Inventors

• Vemuri Srinivas
• Lee Darren

Classifications

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F16/11 Primary

  File system administration, e.g. details of archiving or snapshots (error detection or correction of the data by redundancy in operations G06F11/14) · CPC title

• G06F16/2264

  Multidimensional index structures · CPC title

• G06F16/2322

  using timestamps · CPC title

• G06F16/128

  Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16) · CPC title