Timestamp-based approach to detecting stale values in a cache

Patent metadata

Field	Value
Publication number	US-2025355856-A1
Application number	US-202418667953-A
Country	US
Kind code	A1
Filing date	May 17, 2024
Priority date	May 17, 2024
Publication date	Nov 20, 2025
Grant date	—

Abstract

Systems and methods are disclosed herein for enabling consistent caching. The disclosed approach enables consistent caching by maintaining a timestamp that tracks an upper bound for the most recent observed write attempt to any key, regardless of whether the write attempt was successful or unsuccessful. When a server attempts to read a value of a key, it compares the upper bound timestamp of the key to a read timestamp of the key. The read timestamp is stored in the cache and represents a time at which the key was most recently read. If the upper bound timestamp is after the read timestamp, the cache is stale, so the server retrieves the value of the key from data storage rather than the cache. If the upper bound timestamp is before the read timestamp, the server retrieves the value of the key from the cache.

First claim

What is claimed is:

1 . A method of reading a value of a key, the method comprising:
receiving, from a client, a read request for the value of the key; obtaining, from a server, for every key in a key-value store, an upper bound write attempt timestamp associated with the key; determining, based on the upper bound write attempt timestamp associated with the key, whether a cache associated with the key-value store stores a stale value of the key; and responsive to determining that the cache stores a stale value of the key, retrieving the value of the key from the key-value store.

2 . The method of claim 1 , wherein determining whether the cache associated with the key-value store stores a stale value of the key comprises:
obtaining, from a cache associated with the key-value store, a read timestamp associated with the key; and determining that the upper bound write attempt timestamp is after the read timestamp.

3 . The method of claim 1 further comprising responsive to determining that the cache stores a stale value of the key:
retrieving a new read timestamp associated with the key from the key-value store; and
updating the cache with the key, the value, and the new read timestamp.

4 . The method of claim 1 , wherein determining whether the cache associated with the key-value store stores a stale value of the key is responsive to receiving a response from the cache, and wherein responsive to not receiving a response from the cache retrieving the value of the key from the key-value store.

5 . The method of claim 1 , further comprising:
receiving, from a client, a write request for a new value of the key and a write attempt timestamp associated with the write request; updating the server with the key and the write attempt timestamp; and updating the key-value store with the key and the new value.

6 . The method of claim 5 , wherein the upper bound write attempt timestamp is greater than or equal to the write attempt timestamp.

7 . The method of claim 1 , wherein the read timestamp associated with the key is greater than or equal to a commit timestamp associated with the key, wherein the commit timestamp represents a time at which the key-value store is updated with the key and the new value.

8 . The method of claim 1 , wherein the key-value store is a distributed key-value store storing data as key-value pairs in tables distributed across multiple nodes.

9 . A non-transitory computer-readable storage medium storing executable computer instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
receiving, from a client, a read request for the value of the key; obtaining, from a server, for every key in a key-value store, an upper bound write attempt timestamp associated with the key; determining, based on the upper bound write attempt timestamp, that a cache associated with the key-value store stores a stale value of the key; and retrieving the value of the key from the key-value store.

10 . The non-transitory computer-readable storage medium of claim 9 , wherein determining that the cache associated with the key-value store stores a stale value of the key comprises:
obtaining, from a cache associated with the key-value store, a read timestamp associated with the key; and determining that the upper bound write attempt timestamp is after the read timestamp.

11 . The non-transitory computer-readable storage medium of claim 9 , the operations further comprising, responsive to determining that the cache associated with the key-value store stores a stale value of the key:
retrieving a new read timestamp associated with the key from the key-value store, and updating the cache with the key, the value, and the new read timestamp.

12 . The non-transitory computer-readable storage medium of claim 9 , wherein determining that the cache associated with the key-value store stores a stale value of the key is performed responsive to receiving a response from the cache, and wherein the operations further comprise, responsive to not receiving a response from the cache, retrieving the value of the key from the key-value store.

13 . The non-transitory computer-readable storage medium of claim 9 , the operations further comprising:
receiving, from a client, a write request for a new value of the key and a write attempt timestamp associated with the write request; updating the server with the key and the write attempt timestamp; and updating the key-value store with the key and the new value.

14 . The non-transitory computer-readable storage medium of claim 13 , wherein the upper bound write attempt timestamp is greater than or equal to the write attempt timestamp.

15 . The non-transitory computer-readable storage medium of claim 9 , wherein the read timestamp associated with the key is greater than or equal to a commit timestamp associated with the key, wherein the commit timestamp represents a time at which the key-value store is updated with the key and the new value.

16 . The non-transitory computer-readable storage medium of claim 9 , wherein the key-value store is a distributed key-value store storing data as key-value pairs in tables distributed across multiple nodes.

17 . A method of writing a value to a key, the method comprising:
receiving, from a client, a write attempt to write the value to the key in a key-value store, the write attempt including an attempt timestamp; generating an upper bound write attempt timestamp, the upper bound write attempt timestamp associated with the key; storing the upper bound write attempt timestamp for the key in a server; determining, based on the upper bound write attempt timestamp and the attempt timestamp, whether the write attempt is allowable; and responsive to determining that the attempt is allowable, committing the value to the key in the key-value store.

18 . The method of claim 17 , wherein determining whether the write attempt is allowable comprises determining that the upper bound write attempt timestamp is after the attempt timestamp.

19 . The method of claim 17 , further comprising:
receiving, from a client, a read request for the value of the key; obtaining, from the server, the upper bound write attempt timestamp associated with the key; determining, based on the upper bound write attempt timestamp associated with the key, whether a cache associated with the key-value store stores a stale value of the key; and responsive to determining that the cache stores a stale value of the key, retrieving the value of the key from the key-value store.

20 . The method of claim 17 , wherein the key-value store is a distributed key-value store storing data as key-value pairs in tables distributed across multiple nodes.

Assignees

• Dropbox Inc

Inventors

• He Lihao
• Wang Yu-Wun
• Rapolu Ganesh Prasad
• Le Preslav

Classifications

• G06F16/24552

  Database cache management · CPC title

• G06F16/2322 Primary

  using timestamps · CPC title