Cache with guarantee of current data

Patent metadata

Field	Value
Publication number	US-12450169-B2
Application number	US-202318534355-A
Country	US
Kind code	B2
Filing date	Dec 8, 2023
Priority date	Dec 8, 2023
Publication date	Oct 21, 2025
Grant date	Oct 21, 2025

Abstract

The present technology is a cache that provides an implied guarantee that data returned in response to a query is current. The cache uses two techniques together to guarantee that data returned in response to a query from the cache is current. The first technique is a guaranteed clock value. The is a clock value for which all changes that have occurred before it have been written to the authoritative database. Any query having a clock value greater than the guaranteed clock value is invalid. The second technique is a data invalidation technique, where the cache repeatedly polls the authoritative database for information about changes and invalidates objects associated with changes. If no change has happened, the cache can confidently conclude it is up to date since the cache knows that it is aware of all changes as of the guaranteed clock value.

First claim

What is claimed is:

1. A method comprising:
receiving, by a cache, a request for metadata pertaining to an object ID, the request including a clock value, the clock value indicating an approximate time in which the metadata pertaining to the object ID was current;
determining, by the cache, that the clock value in the request is less than or equal to a guaranteed clock value in the cache, wherein a determination that the clock value in the request is less than or equal to the guaranteed clock value in the cache indicates that the cache is current since the clock value in the request;
determining, by the cache, that a root object ID for an object at a root file path containing the object ID identified in the request is not marked stale; and
returning, by the cache, the metadata pertaining to the object ID for the clock value in the request.

2. The method of claim 1 , further comprising:
polling an authoritative database, by the cache, for an update at the authoritative database to metadata for objects under the root file path;
receiving a response, by the cache, indicating that at least one object under the root file path has been updated, wherein the response includes an update clock value for a most recent update under the root file path; and
marking, by the cache, the root object ID as stale based on the response.

3. The method of claim 1 , further comprising:
requesting, by the cache, an update to at least one object under the root file path;
receiving, by the cache, the update to the at least one object under the root file path from an authoritative database; and
marking, by the cache, the root object ID as fresh based on the received update.

4. The method of claim 1 , further comprising:
incrementally receiving, by the cache, the guaranteed clock value from a clock value service at an authoritative database.

5. The method of claim 1 , wherein the metadata stored by the cache includes the object ID for the object, the clock value associated with a most recent change to the object, and object retrieval information.

6. The method of claim 1 , further comprising:
receiving a command to write a new object ID or a new revision to the object ID to an authoritative database; and
proactively storing the metadata pertaining to the object ID in the cache.

7. The method of claim 5 , wherein the metadata stored by the cache includes the root object ID for the object.

8. The method of claim 1 , further comprising:
determining that the object ID in the request is not present in the cache; and
retrieving the metadata pertaining to the object ID from an authoritative database.

9. A computing system comprising:
at least one processor; and
a memory storing instructions that, when executed by the at least one processor, configure the system to:
receive a request for metadata pertaining to an object ID, the request including a clock value;
determine that the clock value in the request is less than or equal to a guaranteed clock value, wherein a determination that the clock value in the request is less than or equal to the guaranteed clock value in a cache indicates that the cache is current through since the clock value in the request;
determine that a root object ID for an object at a root file path containing the object ID identified in the request is not marked stale; and
return the metadata pertaining to the object ID for the clock value in the request.

10. The computing system of claim 9 , wherein the instructions further configure the system to:
poll an authoritative database for an update at the authoritative database to metadata for objects under the root file path;
receive a response indicating that at least one object under the root file path has been updated, wherein the response includes an update clock value for a most recent update under the root file path; and
mark the root object ID as stale based on the response.

11. The computing system of claim 9 , wherein the instructions further configure the system to:
request an update to at least one object under the root file path;
receive the update to the at least one object under the root file path from an authoritative database; and
mark the root object ID as fresh based on the received update.

12. The computing system of claim 9 , wherein the instructions further configure the system to:
incrementally receive the guaranteed clock value from a clock value service at an authoritative database.

13. The computing system of claim 9 , wherein the metadata stored by the cache includes the object ID for the object, the clock value associated with a most recent change to the object, and object retrieval information.

14. The computing system of claim 9 , wherein the instructions further configure the system to:
receive a command to write a new object ID or a new revision to the object ID to an authoritative database; and
proactively store the metadata pertaining to the object ID in the cache.

15. A computer-readable storage medium that is non-transitory, the computer-readable storage medium comprising instructions that when executed by at least one processor, cause the at least one processor to:
receive a request for metadata pertaining to an object ID, the request including a clock value;
determine that the clock value in the request is less than or equal to a guaranteed clock value, wherein a determination that the clock value in the request is less than or equal to the guaranteed clock value in a cache indicates that the cache is current since the clock value in the request;
determine that a root object ID for an object at a root file path containing the object ID identified in the request is not marked stale; and
return, by the cache, the metadata pertaining to the object ID for the clock value in the request.

16. The computer-readable storage medium of claim 15 , wherein the instructions further configure the at least one processor to:
poll an authoritative database for an update at the authoritative database to metadata for objects under the root file path;
receive a response indicating that at least one object under the root file path has been updated, wherein the response includes an update clock value for a most recent update under the root file path; and
mark the root object ID as stale based on the response.

17. The computer-readable storage medium of claim 15 , wherein the instructions further configure the at least one processor to:
request an update to at least one object under the root file path;
receive the update to the at least one object under the root file path from an authoritative database; and
mark the root object ID as fresh based on the received update.

18. The computer-readable storage medium of claim 15 , wherein the instructions further configure the at least one processor to:
incrementally receive the guaranteed clock value from a clock value service at an authoritative database.

19. The computer-readable storage medium of claim 15 , wherein the metadata stored by the cache includes the object ID for the object, the clock value associated with a most recent change to the object, and object retrieval information.

20. The computer-readable storage medium of claim 15 , wherein the instructions further configure the at least one processor to:
receive a command to write a new object ID or a new revision to the object ID to an authoritative database; and
proactively store the metadata pertaining to the object ID in the cache.

Assignees

• Dropbox Inc

Inventors

• Ziegler-Millard Adrian
• Burke Neil
• Albert Akos
• Fundira Panashe
• Coopersmith Michael

Classifications

• G06F1/10 Primary

  Distribution of clock signals {, e.g. skew} · CPC title

• G06F12/12 Primary

  Replacement control · CPC title