Horizontal scaling of version caches in a distributed high-concurrency multi-user environment

Patent metadata

Field	Value
Publication number	US-12481589-B2
Application number	US-202318522430-A
Country	US
Kind code	B2
Filing date	Nov 29, 2023
Priority date	Jan 28, 2022
Publication date	Nov 25, 2025
Grant date	Nov 25, 2025

Abstract

Techniques for providing horizontally scaled caching of versioned data are provided. In some aspects, the techniques described herein relate to a method including initializing a first version cache (VC) object based on a version of data stored in a data storage device; replicating the first VC to generate a second VC; receiving a write operation at the first VC; generating a delta for the write operation, the delta representing a change in the version of data; writing the delta to a persistent replication log, the persistent replication log storing an ordered set of deltas including the delta; writing data in the write operation to the data storage device; and applying the ordered set of deltas at the second VC to update data stored by the second VC.

First claim

We claim:

1 . A method comprising:
replicating a first version cache to generate a replicated first version cache; receiving a write operation including data at the first version cache; generating a delta for the write operation representing a change in the data; writing the delta to a replication log storing an ordered set of deltas including the delta; and applying the ordered set of deltas at the replicated first version cache.

2 . The method of claim 1 , wherein applying the ordered set of deltas at the replicated first version cache comprises:
retrieving the ordered set of deltas from the replication log; obtaining a write lock, the write lock configured to block operations at the replicated first version cache; applying deltas in the ordered set of deltas, each delta in the ordered set of deltas modifying the data stored by the replicated first version cache; and releasing the write lock after applying the deltas in the ordered set of deltas.

3 . The method of claim 2 , further comprising:
determining that a lock grant timer has expired before the write lock is obtained; creating a new version cache; and replacing the replicated first version cache with the new version cache.

4 . The method of claim 2 , further comprising comparing the ordered set of deltas with a locally stored set of write operations to identify conflicts between the ordered set of deltas and the locally stored set of write operations.

5 . The method of claim 1 , further comprising:
receiving, at a router, an operation, the operation including a version; determining, by the router, if the version matches a version of the data associated with the first version cache by querying a routing table of version caches; transmitting, by the router, the operation to the first version cache if the version matches the version of the data associated with the first version cache; and instantiating, by the router, a new version cache if the version does not match the version of the data associated with the first version cache.

6 . The method of claim 5 , further comprising removing, by the router, a version cache from the routing table of version caches when a number of write operations is below a threshold.

7 . The method of claim 1 , wherein replicating the first version cache to generate the replicated first version cache comprises replicating the first version cache to generate the replicated first version cache after determining that a number of write operations exceeds a threshold.

8 . A non-transitory computer-readable storage medium for tangibly storing computer program instructions capable of being executed by a computer processor, the computer program instructions defining steps of:
replicating a first version cache to generate a replicated first version cache; receiving a write operation including data at the first version cache; generating a delta for the write operation representing a change in the data; writing the delta to a replication log storing an ordered set of deltas including the delta; and applying the ordered set of deltas at the replicated first version cache.

9 . The non-transitory computer-readable storage medium of claim 8 , wherein applying the ordered set of deltas at the replicated first version cache comprises:
retrieving the ordered set of deltas from the replication log; obtaining a write lock, the write lock configured to block operations at the replicated first version cache; applying deltas in the ordered set of deltas, each delta in the ordered set of deltas modifying the data stored by the replicated first version cache; and releasing the write lock after applying the deltas in the ordered set of deltas.

10 . The non-transitory computer-readable storage medium of claim 9 , further comprising:
determining that a lock grant timer has expired before the write lock is obtained; creating a new version cache; and replacing the replicated first version cache with the new version cache.

11 . The non-transitory computer-readable storage medium of claim 9 , further comprising comparing the ordered set of deltas with a locally stored set of write operations to identify conflicts between the ordered set of deltas and the locally stored set of write operations.

12 . The non-transitory computer-readable storage medium of claim 8 , further comprising:
receiving, at a router, an operation, the operation including a version; determining, by the router, if the version matches a version of the data associated with the first version cache by querying a routing table of version caches; transmitting, by the router, the operation to the first version cache if the version matches the version of the data associated with the first version cache; and instantiating, by the router, a new version cache if the version does not match the version of the data associated with the first version cache.

13 . The non-transitory computer-readable storage medium of claim 8 , wherein replicating the first version cache to generate the replicated first version cache comprises replicating the first version cache to generate the replicated first version cache after determining that a number of write operations exceeds a threshold.

14 . The non-transitory computer-readable storage medium of claim 13 , further comprising removing a version cache from a routing table of version caches when a number of write operations is below a threshold.

15 . A system comprising:
a processor configured to:
replicate a first version cache to generate a replicated first version cache;
receive a write operation including data at the first version cache;
generate a delta for the write operation representing a change in the data;
write the delta to a replication log storing an ordered set of deltas including the delta; and
apply the ordered set of deltas at the replicated first version cache.

16 . The system of claim 15 , wherein applying the ordered set of deltas at the replicated first version cache comprises:
retrieving the ordered set of deltas from the replication log; obtaining a write lock, the write lock configured to block operations at the replicated first version cache; applying deltas in the ordered set of deltas, each delta in the ordered set of deltas modifying the data stored by the replicated first version cache; and releasing the write lock after applying the deltas in the ordered set of deltas.

17 . The system of claim 16 , the processor further configured to:
determine that a lock grant timer has expired before the write lock is obtained; create a new version cache; and replace the replicated first version cache with the new version cache.

18 . The system of claim 15 , the processor further configured to:
receive an operation, the operation including a version; determine if the version matches a version of the data associated with the first version cache by querying a routing table of version caches; transmit the operation to the first version cache if the version matches the version of the data associated with the first version cache; and instantiate a new version cache if the version does not match the version of the data associated with the first version cache.

19 . The system of claim 15 , wherein replicating the first version cache to generate the replicated first version cache comprises replicating the first version cache to generate the replicated first version cache after determining that a number of write operations exceeds a threshold.

20

Assignees

• Workday Inc

Inventors

• Lee Darren
• Bornhoevd Christof

Classifications

• G06F2212/60

  Details of cache memory · CPC title

• G06F12/0815

  Cache consistency protocols · CPC title

• G06F2212/286

  Mirrored cache memory · CPC title

• G06F12/0802 Primary

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F12/0868 Primary

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title