1

I am looking for a complete pattern implementing cache-aside when used in a distributed system across multiple nodes read/writing from/to cache.

Specificly how to avoid making multiple requests to db and multiple writes to cache of the same data when all nodes concurrently encounter a cache miss

The problem described in the scenario below would potentially request the data 3 times (one for each node) and then insert it 3 times into the cache each node overwriting hes predecessor

I am looking for a common pattern to handle this scenario. on the table are 2 soloutions:

  • using a distributed lock on a key in the cache notifing other nodes when one of them has already began querying the data and inserting the data into the cache.
  • having a seperate writer service invalidating the cache and setting the new version in it (write-through is NOT an option since the external system can't interact with my cache)

any help would be appricated

scenario:

  1. an external system inserts data in an external db the data is classified by a version value, each time the system runs it creates a new version of the data.

    example document in "data" collection: 
    
    {
       version: 32.0,
       ......other fields 
    }
    

    the external system also updates a document in version collection:

    example document in version collection:
    
    {
       collection: 'data',
       version: 32.0
    }
    
  2. multiple web app instances are listening for requests for the current version of data.

  3. the web app handling the request checks current version from db

    3.1) if version exists in cache it retrives it and returns to client

    3.2) if version does NOT exist in cache it queries the new version

    3.3) inserts the new version, invalidates the cache of the old version. and returns it to the client

enter image description here

3
  • do you have a single shared cache, or one per webserver?
    – Ewan
    Oct 13, 2023 at 20:30
  • Shared redis cluster @Ewan
    – eran otzap
    Oct 13, 2023 at 20:32
  • put a single instance service in front of it which checks the cache and does the db lookup with a lock
    – Ewan
    Oct 13, 2023 at 20:36

3 Answers 3

2

The simple solution is to put the cache check and refresh logic in the cache.

This can be done by adding a second layer of api in front of the cache, calls get directed to this api rather than checking the cache/db directly.

This api implements a lock, so multiple requests can be blocked on a cache miss and wait for a single call to the db to update the cache before replying.

This means that you have to send all the calls to a single server. But you can still split these by cache key to support scaling and have failover for when boxes go down.

BUT!

You should remember that:

  • databases also have caching
  • you can add random numbers to cache expiry
  • reddis has keyspace notifications
  • nosql databases exist

I'm guessing that your overall problem is optimising your site for performance. Which means you need to try everything and compare the results.

1

I am going to assume you have 3 nodes/caches to make the answer simpler.

Let's consider the initial state of a set of completely empty caches and 3 concurrent requests for the same piece of data. We can consider the 3 cache nodes as a whole to be a datastore, as such we have to consider CAP theorem. If there is no network partition the three nodes can coordinate such that only one node makes the request to the database, once that result is retrieved the data can be distributed to the three nodes and then returned to the clients.

Now let's say the cache is partially partitioned - 2 nodes can talk to each other but one node is unable to talk to the other 2, all three caches are empty and all three receive client requests for the same data. The 2 connected nodes form a majority of the cache cluster, hence could be configured to act as before. Since the single node can't talk to the other two it can't retrieve their state with respect to if it is allowed to make a request to the DB - this is "meta" state as such we have a choice between consistency and availability:

  • Consistency - means this node is not allowed to make the DB request since it doesn't know the state of the other two - so cannot service the client (the data is unavailable).
  • Available - means that this node will try to request data from the database hence violating your rule that only one node should fetch from the DB - you have to make a choice, if you wish to violate this rule given this scenario.

So for an unpartitioned cluster (or the majority partition of a cluster) the logic is fairly simple, when a request is received:

  • Determine if a valid value is cached locally (on this node), a value is considered INVALID if:
    • It doesn't exist.
    • The TTL (time to live) has expired.
    • The client is requesting a newer version than is currently cached.
  • If the local data is valid, service the client and abort the rest of this flow.
  • Take a cluster wide lock on the key for that data, this prevents any node from servicing that key - all requests are held until the lock is released.
  • Check if the data is now valid (another node may have updated the data while you were waiting on the lock) - if so release the lock, service the client and abort the flow.
  • Fetch the data from the DB.
  • Distribute the data to all "connected" nodes.
  • Release the lock.
  • Service the client.

That said you still have a number of decisions as to what to do when partitioning occurs, specifically:

  • What do nodes in the minority partition do?
  • What happens when a partition is corrected - for example sync the complete cache to the other nodes.
  • What happens if the cluster partitions and some locks are held by nodes in the minority partition - for example you could transfer the locks to the nodes in the majority, however you then risk multiple requests to the database.
0

how to avoid making multiple requests to db and multiple writes to cache of the same data when all nodes concurrently encounter a cache miss

The "all nodes" aspect sounds like trouble.

The usual approach is have some load-balancing layer hash on a relevant identifier and direct all requests for identifier X to the same server Y, using modulo. So if N servers are up at the moment we peel off some prefix bits from SHA3(X) to compute Y = hash % N. As servers come and go the details will change and a request for X will end up going to another server, but hey, reboots are rare and after all that's what cache TTLs are for, right?

Suppose each server allocates 1 GiB of RAM for caching results. Then N servers offer an aggregate of N gigabytes, and critically we expect to find a given record X resident in exactly one server, according to hash mod N. This is a big win, and it works remarkably well.

There's little value add from distributed locks in such a scheme, assuming "last write wins" or similar conflict resolution approaches are applicable.

would potentially request the data 3 times (one for each node)

That simply doesn't happen if the load balancer is hashing on the data X, obtaining a result modulo N which is 3, and directing all requests about X to a single node. That node is certainly free to acquire / release a local lock for X if we're concerned that multiple X requests may arrive while a backend database query about X is pending.


We assume the DB is "large" and RAM-resident cache is "small".

Per unit time the update process is injecting a "small" number of updates, and is in a good position to issue cache invalidates. This might take the form of reducing default 3600-second TTLs to just a few seconds. In some caching systems the entry will soon expire. In other systems an entry, or at least a popular entry, which is about to expire may trigger scheduling a pre-emptive DB query to refresh it and extend its TTL. This offers a very natural way to discover that the version incremented. Such a background query allows the timely update of even a "hot" record with zero latency impact seen by front-end clients, at the cost of only serving stale data for a controlled and limited interval.

Let's assume the DB update process

  • cannot access the cache, and
  • always writes an updated timestamp when INSERTing a row.

That still gives us the flexibility to create a new cache update process responsible for timely cache invalidations.

while (True) do:

  • Perform an indexed query on "recent" updated timestamps, to retrieve rows updated since the previous loop iteration.
  • Issue cache invalidations for each row.
  • Optionally update the cache with the fresh row data, perhaps preserving the old TTL so unpopular items consume less cache space
  • Briefly sleep().
  • Lather, rinse, repeat the loop.
1
  • They sit behind a load balancer, that's not the issue, they all receive requests and they can all invalidate the cache at any given time
    – eran otzap
    Oct 14, 2023 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.