Mint Caching Strategy

The Problem

#

Internet searches on caching strategies often yield a wealth of results, yet many have suggested solutions that aren’t robust enough for complex applications. We’ll examine a specific scenario where conventional caching methods fall short and provide a possible solution that may close the gap.

Defining The Scenario

#

Imagine a system that tracks VHS tape (📼) rentals for customers with the following rules:

• A customer is tracked by a unique ID.
• A customer has a first and last name.
• A VHS tape in inventory is tracked by a unique ID.
• A VHS tape can also be identified by a title. But many tapes can have the same title.
• A rental is defined by a customer renting one VHS tape.
• Customers can rent zero to many tapes at any time.
• A tape can be rented at most once at a time.
• Once a VHS tape rental is returned by a customer, the rental is removed from the system, i.e., no history.

Lets build a simple implementation of this system.

Data Model Layer

#

To start, we will use a relational-esque database. We can define the following ERD to represent the scenario:

In relational schema terms this could be represented as (note here that only the relevant fields are shown here):

customers(cid: integer, first: string, last: string, updated_at: timestamp);
tapes(tid: integer, title: string);
rentals(rid: integer, cid: integer, tid: integer, updated_at: timestamp);

• The customers relation holds customer records.
• The tapes relaton holds tape records.
• The rentals relation tracks rental records.
• customers.cid represents the primary key for a customer record.
• tapes.tid represents the primary key for a tape record.
• rentals.rid represents the primary key for a rental record.
• rentals.cid represents the foreign key of a customer in the customers relation.
• rentals.tid represents the foreight key of a tape in the tapes relation.
• tapes.updated_at and customers.updated_at hold the timestamps when the corresponding records gets any update.

API Endpoint Layer

#

Client software that interacts with customers connects to an API to execute operations:

This API includes the following endpoints:

# get customer records
GET /customers?<GET_CUSTOMERS_PAYLOAD>

# get a customer record
GET /customers/:cid?<GET_CUSTOMER_PAYLOAD>

# add a customer record
POST /customers

<POST_CUSTOMERS_PAYLOAD>

# update a customer record
PUT /customers/:cid

<PUT_CUSTOMERS_PAYLOAD>

# delete a customer
DELETE /customers/:cid

# get tape inventory
GET /tapes?<GET_TAPES_PAYLOAD>

# get a tape
GET /tapes/:tid?<GET_TAPE_PAYLOAD>

# add a tape
POST /tapes

<POST_TAPES_PAYLOAD>

# delete a tape
DELETE /tapes/t:id

# get rentals
GET /rentals?<GET_RENTALS_PAYLOAD>

# get a rental
GET /rentals/:rid?<GET_RENTAL_PAYLOAD>

# add a rental
POST /rentals

<POST_RENTALS_PAYLOAD>

# delete a rental 
DELETE /rentals/:rid

where:

• <GET_CUSTOMERS_PAYLOAD> is the set of GET parameters GET /customers consumes.
• <GET_CUSTOMER_PAYLOAD> is the set of GET parameters GET /customers/:cid consumes.
• <POST_CUSTOMERS_PAYLOAD> is the payload POST /customers consumes.
• <PUT_CUSTOMERS_PAYLOAD> is the payload PUT /customers consumes.
• <GET_TAPES_PAYLOAD> is the set of GET parameters GET /tapes consumes.
• <GET_TAPE_PAYLOAD> is the set of GET parameters GET /tapes/:tid consumes.
• <POST_TAPES_PAYLOAD> is the payload POST /tapes consumes.
• <GET_RENTALS_PAYLOAD> is the set of GET parameters GET /rentals consumes.
• <GET_RENTAL_PAYLOAD> is the set of GET parameters GET /rentals/:rid consumes.
• <POST_RENTALS_PAYLOAD> is the payload POST /rentals consumes.

Application Logic Layer

#

Lets further define simple endpoints for all the entities (note, code blocks in this post will be written in javascript-esque pseudo-code):

// customers.module
storage = storageFactory.create(customers);
get('/customers', (getCustomersPayload) => {
    validate(getCustomersPayload);
    return storage.get(getCustomersPayload);
});

get('/customers/:cid', (cid, getCustomerPayload) => {
    validate(getCustomerPayload)
    return storage.get(cid, getCustomerPayload);
})

post('/customers', (postCustomerPayload) => {
    validate(postCustomerPayload);
    return storage.create(postCustomerPayload);
});

put('/customers/:cid', (cid, putCustomerPayload) => {
    validate(putCustomerPayload);
    return storage.put(putCustomerPayload);
});


remove('/customers/:cid', (cid) => {
    storage.remove(cid);
    return;
})

// tapes.modules
storage = storageFactory.create(tapes);
get('/tapes', (getTapesPayload) => {
    validate(getTapesPayload);
    return storage.get(getTapesPayload);
});

get('/tapes/:tid', (tid, getTapesPayload) => {
    validate(getTapesPayload)
    return storage.get(tid, getTapesPayload);
})

post('/tapes', (postTapePayload) => {
    validate(postTapePayload);
    return storage.create(postTapePayload);
});

remove('/tapes/:tid', (tid) => {
    storage.remove(tid);
    return;
})

// rentals.modules
storage = storageFactory.create(rentals);
get('/rentals', (getRentalsPayload) => {
    validate(getRentalsPayload);
    return storage.get(getRentalsPayload);
});

get('/rentals/:rid', (rid, getRentalsPayload) => {
    validate(getRentalsPayload)
    return storage.get(rid, getRentalsPayload);
})

post('/rentals', (postRentalsPayload) => {
    validate(postRentalsPayload);
    return storage.create(postRentalsPayload);
});

remove('/rentals/:rid', (rid) => {
    storage.remove(rid);
    return;
})

These endpoints will run as expected:

• A user invokes the client code to make a request to the API.
• The API delegates the request to the corresponding endpoint in the appropriate module.
• The endpoint will run the logic, referencing the storage layer for any data needed.

Assuming no data changes in storage have occurred, when client software makes many requests to GET endpoints with the same payloads, the API will execute the same logic; effectively producing redundant work.

Defining A Cache Layer

#

Ideally, we should prevent redundant work by placing a caching layer in these GET endpoints. Here is an example of the cache-aside strategy:

Caching technolgies typically have time-to-live (ttl) policies that define how long a cache entry should stay in the cache. For the sake of this discussion, we’ll assume ttl values for all cache entries are ∞.

The problem: Data Inconsistency

#

Lets refactor the GET /rentals/:id endpoint to use the cache-aside strategy.

function computeKey(id, getRentalsPayload) {
    return `rentals:${id}`
}

get('/rentals/:rid', (rid, getRentalsPayload) => {
    validate(getRentalsPayload)
    const key = computeKey(rid, getRentalsPayload);
    let result = cache.get(key);
    if(result) {
        return result;
    }
    result = storage.get(rid, getRentalsPayload);
    cache.set(key, result);
    return result;
})

Lets assume GET /rentals/:rid responses will have the following form:

type Rental = {
    id: number,
    tape: {
        id: number,
        title: string
    },
    customer: {
        id: number,
        first: string,
        last: string
    }
}

Also assume the following data in the relations

customers

tapes

rentals

When client software makes the first request to GET /rentals/1, the endpoint will need to reach the storage layer to grab the related data, cache it, then render out the payload:

{
    id: 1,
    tape: {
        id: 1,
        title: 'History of Computers',
        updated_at: 1757126811
    },
    customer: {
        id: 1,
        first: 'John',
        last: 'Doe'
        updated_at: 1757126811
    }
}

Any subsequent requests will be served using the cache. If customer with id 1 has a change in first and/or last name through the endpoint PUT /customers/:cid:

PUT /customers/1

{
    first: 'John II'
}

The cached data used in GET /rentals/1 will no longer reflect the latest state of the customer entity. How can the system know that the key produced by const key = computeKey(rid, getRentalsPayload); for the endpoint call GET /rentals/1 needs needs to be deleted? With the current setup, that answer is, it cannot. The problem is exacerbated as the system has more entities and the relationships between them

Adding A Mint Layer

#

We can add a “mint” layer that keeps track of the set of relevant entities’ updated_at timestamps. Leveraging the write-through caching stragety here, whenever we update a relevant entity, we also update this mint layer.

function computeMintKey(id) {
    return `mint:customers:${id}`;
}

post('/customers', (postCustomerPayload) => {
    validate(postCustomerPayload);
    const customer = storage.create(postCustomerPayload);
    const mintKey = computeMintKey(customer);
    cache.set(mintKey, customer.updatedAt)
    return customer;
});

put('/customers/:cid', (cid, putCustomerPayload) => {
    validate(putCustomerPayload);
    const customer = storage.put(putCustomerPayload);
    const mintKey = computeMintKey(customer);
    cache.set(mintKey, customer.updatedAt)
    return customer;
});

Once this layer exists, it can be used to compare updated_at values stored in the cache object with the ones stored in the mint.

get('/rentals/:rid', (rid, getRentalsPayload) => {
    validate(getRentalsPayload)
    const key = computeKey(rid, getRentalsPayload);
    let rental = cache.get(key);
    if(rental) {
        // we know the payload structure
        const customerMintKey = computeMintKey(rental.customer.id);
        const customerMint = cache.get(customerMintKey);

        if (customerMint && customerMint <= rental.customer.updatedAt) {
            return result;
        }
    }
    result = storage.get(rid, getRentalsPayload);
    cache.set(key, result);
    return result;
})

We can expand on this idea on any objects of arbitrary complexity as long as the mint layer is aware of the entity types it needs to check for.