The "always-fresh" cache: balance via event sourcing without blowing up memory

01 · CONTEXT

Balance as a sum of events

Em event sourcing the idea is, instead of storing the system's current state in a database, to store every step of the history so far. For an account balance, this means the balance on a given date is the sum of all deposits up to it minus the sum of all withdrawals up to it.

The predictable question about this approach was whether the service walks the whole list on every balance query. Over time, what proved to be the problem was the memory requirement.

Datomic, the database the service uses, separates the tasks of writing, storing, and querying data. All writes go through a single process, the transactor, which serializes and validates them. The query processes are the peers, and at Nubank the peers are the microservice instances themselves, which load data from DynamoDB into a large cache in memory. Nubank also lists Datomic and DynamoDB among the technologies where it stores data.

02 · THE PROBLEM

Instances that did not fit in memory

The machines started to freeze: they ran out of memory and stalled on garbage-collection pauses that lasted minutes. The first response was to increase the instances' memory, and at first it worked. On reaching 100GB instances hanging by a thread, the team concluded it could not go on like this.

The real problem rested on two facts about the system. The first: the event sourcing approach required loading a lot of data from storage into the peers' in-memory cache. The second: any instance of the service could be called to answer any request.

1. A customer who makes four balance requests while browsing the app can force four different instances to load the same data.

2. Each instance loads data from storage into a large in-memory cache, and any one of them can be called to answer any request.

3. No instance could hold the entire database in the in-memory cache, but every one of them had to hold data for all active customers at any given moment.

4. With 100GB instances hanging by a thread, the machines ran out of memory and stalled on garbage-collection pauses lasting minutes.

In practice, every instance spent time and memory redoing work that another machine had already done.

03 · THE IDEA

A cache that never needs to be invalidated

The author notes that the hard part of cache is not caching, but invalidating. The way out was to sidestep the hard part instead of solving it: a cache in which every reference points to nothing (a miss) or to something immutable, and therefore valid for one instant. When the world changes, you change the reference, not the value.

The inspiration came from Datomic itself, which stores data as a large tree of immutable nodes. If a node is already in the in-memory cache, it is valid because it is an immutable value.

The recipe has three pieces: an immutable store that maps references to values, a way to derive the current value from the database and push it to the store, and a way to obtain a valid reference to the most recent value. Any key-value store works as the immutable store, and the team chose DynamoDB.

The read strategy is read-through: look in the cache; if the data is missing, compute it from scratch, write it to the cache, and return it.

04 · THE KEY

From global version to per-account version

Datomic has a version number that the application can use, the basis-t, a reference to a point in the database's time. The team considered using it as the key reference, but every transaction increments this number. Losing an account's cache because of a deposit in another account is silly, says the author.

The solution was to add an attribute to the account entity in Datomic. It starts at zero and, on every action related to that account, is incremented by 1 in the same transaction. Because it counts each event of the account, it was named event-counter, and it provides a version number for the account data, usable as a cache key.

1. The app asks for an account's balance and the request can reach any instance of the service.

2. The instance asks Datomic for the account's current event-counter value, and that number serves as the version for the cache key.

3. If the key is not in the immutable store, it is a miss: the instance queries Datomic, computes the balance, and writes it to the store under the key.

4. On another request for the same account's balance, the event-counter is still the same and so is the cache key.

5. When the account receives a new deposit or withdrawal, the event-counter goes up and the next request is a miss.

05 · TRADE-OFFS AND RESULT

The database first, the cache after

In a CDN, you check the cache first and only then the real server. In the scheme described, the first thing is to query the database to get the event-counter. Only then do you look in the cache and, afterward, go back to the database to fetch the rest.

For the author, the choice makes sense because availability at any cost does not help the customer: what good is seeing a stale balance if they cannot act because the servers are down?

The main goal of the cache was to let the service run with fewer resources. Each instance needed 90GB of RAM and came to need 55GB. The service also began to scale horizontally, and latency dropped for most requests, all without giving up consistency.