sturdyc
A caching library with advanced concurrency features designed to make I/O heavy applications robust and highly performant
About sturdyc
This large README is shown as a plain-text preview. Read the full README at the source
> A sturdy gopher shielding data sources from rapidly incoming requests.
# `sturdyc`: a caching library for building sturdy systems
[](https://github.com/avelino/awesome-go)
[](https://pkg.go.dev/github.com/viccon/sturdyc)
[](https://github.com/viccon/sturdyc/blob/master/LICENSE)
[](https://goreportcard.com/report/github.com/viccon/sturdyc)
[](https://github.com/viccon/sturdyc/actions/workflows/main.yml)
[](https://codecov.io/gh/viccon/sturdyc)
`sturdyc` eliminates cache stampedes and can minimize data source load in
high-throughput systems through features such as request coalescing and
asynchronous refreshes. It combines the speed of in-memory caching with
granular control over data freshness. At its core, `sturdyc` provides
**non-blocking reads** and **sharded writes** for minimal lock contention. The
[xxhash](https://github.com/cespare/xxhash) algorithm is used for efficient key
distribution.
It has all the functionality you would expect from a caching library, but what
**sets it apart** are the flexible configurations that have been designed to
make I/O heavy applications both _robust_ and _highly performant_.
We have been using this package in production to enhance both the performance
and reliability of our services that retrieve data from distributed caches,
databases, and external APIs. While the API surface of sturdyc is tiny, it
offers extensive configuration options. I encourage you to read through this
README and experiment with the examples in order to understand its full
capabilities.
This screenshot shows the P95 latency improvements we observed after adding
this package in front of a distributed key-value store:
<img width="1554" alt="Screenshot 2024-05-10 at 10 15 18" src="https://github.com/viccon/sturdyc/assets/12787673/adad1d4c-e966-4db1-969a-eda4fd75653a">
And through a combination of inflight-tracking, asynchronous refreshes, and
refresh coalescing, we reduced load on underlying data sources by more than
90%. This reduction in outgoing requests has enabled us to operate with fewer
containers and significantly cheaper database clusters.
# Table of contents
Below is the table of contents for what this README is going to cover. However,
if this is your first time using this package, I encourage you to **read these
examples in the order they appear**. Most of them build on each other, and many
share configurations.
- [**installing**](https://github.com/viccon/sturdyc?tab=readme-ov-file#installing)
- [**creating a cache client**](https://github.com/viccon/sturdyc?tab=readme-ov-file#creating-a-cache-client)
- [**evictions**](https://github.com/viccon/sturdyc?tab=readme-ov-file#evictions)
- [**get or fetch**](https://github.com/viccon/sturdyc?tab=readme-ov-file#get-or-fetch)
- [**stampede protection**](https://github.com/viccon/sturdyc?tab=readme-ov-file#stampede-protection)
- [**early refreshes**](https://github.com/viccon/sturdyc?tab=readme-ov-file#early-refreshes)
- [**deletions**](https://github.com/viccon/sturdyc?tab=readme-ov-file#deletions)
- [**caching non-existent records**](https://github.com/viccon/sturdyc?tab=readme-ov-file#non-existent-records)
- [**caching batch endpoints per record**](https://github.com/viccon/sturdyc?tab=readme-ov-file#batch-endpoints)
- [**cache key permutations**](https://github.com/viccon/sturdyc?tab=readme-ov-file#cache-key-permutations)
- [**refresh coalescing**](https://github.com/viccon/sturdyc?tab=readme-ov-file#refresh-coalescing)
- [**request passthrough**](https://github.com/viccon/sturdyc?tab=readme-ov-file#passthrough)
- [**distributed storage**](https://github.com/viccon/sturdyc?tab=readme-ov-file#distributed-storage)
- [**custom metrics**](https://github.com/viccon/sturdyc?tab=readme-ov-file#custom-metrics)
- [**generics**](https://github.com/viccon/sturdyc?tab=readme-ov-file#generics)
# Installing
```sh
go get github.com/viccon/sturdyc
```
# Creating a cache client
The first thing you will have to do is to create a cache client to hold your
configuration:
```go
// Maximum number of entries in the cache. Exceeding this number will trigger
// an eviction (as long as the "evictionPercentage" is greater than 0).
capacity := 10000
// Number of shards to use. Increasing this number will reduce write lock collisions.
numShards := 10
// Time-to-live for cache entries.
ttl := 2 * time.Hour
// Percentage of entries to evict when the cache reaches its capacity. Setting this
// to 0 will make writes a no-op until an item has either expired or been deleted.
evictionPercentage := 10
// Create a cache client with the specified configuration.
cacheClient := sturdyc.New[int](capacity, numShards, ttl, evictionPercentage)
cacheClient.Set("key1", 99)
log.Println(cacheClient.Size())
log.Println(cacheClient.Get("key1"))
cacheClient.Delete("key1")
log.Println(cacheClient.Size())
log.Println(cacheClient.Get("key1"))
```
The `New` function is variadic, and as the final argument we're also able to
provide a wide range of configuration options, which we will explore in detail
in the sections to follow.
# Evictions
The cache has two eviction strategies. One is a background job which
continuously evicts expired records from each shard. However, there are options
to both tweak the interval at which the job runs:
```go
cacheClient := sturdyc.New[int](capacity, numShards, ttl, evictionPercentage,
sturdyc.WithEvictionInterval(time.Second),
)
```
as well as disabling the functionality altogether:
```go
cacheClient := sturdyc.New[int](capacity, numShards, ttl, evictionPercentage,
sturdyc.WithNoContinuousEvictions()
)
```
The latter can give you a slight performance boost in situations where you're
unlikely to ever exceed the capacity you've assigned to your cache.
However, if the capacity is reached, the second eviction strategy is triggered.
This process performs evictions on a per-shard basis, selecting records for
removal based on recency. The eviction algorithm uses
[quickselect](https://en.wikipedia.org/wiki/Quickselect), which has an O(N)
time complexity without the overhead of requiring write locks on reads to
update a recency list, as many LRU caches do.
Next, we'll start to look at some of the more _advanced features_.
# Get or fetch
I have tried to design the API in a way that should make the process of
integrating `sturdyc` with any data source as straightforward as possible.
While it provides the basic get/set methods you would expect from a cache, the
advanced functionality is accessed through just two core functions:
`GetOrFetch` and `GetOrFetchBatch`
As an example, let's say that we had the following code for fetching orders
from an API:
```go
func (c *Client) Order(ctx context.Context, id string) (Order, error) {
timeoutCtx, cancel := context.WithTimeout(ctx, c.timeout)
defer cancel()
var response Order
err := requests.URL(c.orderURL).
Pathf("/order/%s", id).
ToJSON(&response).
Fetch(timeoutCtx)
return response, err
}
```
All we would have to do is wrap the lines of code that retrieves the data in a
function, and then hand that over to our cache client:
```go
func (c *Client) Order(ctx context.Context, id string) (Order, error) {
fetchFunc := func(ctx context.Context) (Order, error) {
timeoutCtx, cancel := context.WithTimeout(ctx, c.timeout)
defer cancel()
var response Order
err := requests.URL(c.orderURL).
Pathf("/order/%s", id).
ToJSON(&response).
Fetch(timeoutCtx)
return response, err
}
return c.cache.GetOrFetch(ctx, id, fetchFunc)
}
```
The cache is going to return the value from memory if it's available, and
otherwise will call the `fetchFn` to retrieve the data from the underlying data
source.
Most of our examples are going to be retrieving data from HTTP APIs, but it's
just as easy to wrap a database query, a remote procedure call, a disk read, or
any other I/O operation.
The `fetchFn` that we pass to `GetOrFetch` has the following function
signature:
```go
type FetchFn[T any] func(ctx context.Context) (T, error)
```
For data sources capable of handling requests for multiple records at once,
we'll use `GetOrFetchBatch`:
```go
type KeyFn func(id string) string
type BatchFetchFn[T any] func(ctx context.Context, ids []string) (map[string]T, error)
func (c *Client[T]) GetOrFetchBatch(ctx context.Context, ids []string, keyFn KeyFn, fetchFn BatchFetchFn[T]) (map[string]T, error) {
// ...
}
```
There are a few things to unpack here, so let's start with the `KeyFn`. When
adding an in-memory cache to an API client capable of calling multiple
endpoints, it's highly unlikely that an ID alone is going to be enough to
uniquely identify a record.
To illustrate, let's say that we're building a Github client and want to use
this package to get around their rate limit. The username itself wouldn't make
for a good cache key because we could use it to fetch gists, commits,
repositories, etc. Therefore, `GetOrFetchBatch` takes a `KeyFn` that prefixes
each ID with something to identify the data source so that we don't end up with
cache key collisions:
```go
gistPrefixFn := cacheClient.BatchKeyFn("gists")
commitPrefixFn := cacheClient.BatchKeyFn("commits")
gists, err := cacheClient.GetOrFetchBatch(ctx, userIDs, gistPrefixFn, fetchGists)
commits, err := cacheClient.GetOrFetchBatch(ctx, userIDs, commitPrefixFn, fetchCommits)
```
We're now able to use the _same_ cache for _multiple_ data sources, and
internally we'd get cache keys of this format:
```
gists-ID-viccon
gists-ID-some-other-user
commits-ID-viccon
commits-ID-some-other-user
```
Now, let's use a bit of our imagination because Github doesn't actually allow
us to fetch gists from multiple users at once. However, if they did, our client
would probably look something like this:
```go
func (client *GithubClient) Gists(ctx context.Context, usernames []string) (map[string]Gist, error) {
cacheKeyFn := client.cache.BatchKeyFn("gists")
fetchFunc := func(ctx context.Context, cacheMisses []string) (map[string]Gist, error) {
timeoutCtx, cancel := context.WithTimeout(ctx, client.timeout)
defer cancel()
var response map[string]Gist
err := requests.URL(c.baseURL).
Path("/gists").
Param("usernames", strings.Join(cacheMisses, ",")).
ToJSON(&response).
Fetch(timeoutCtx)
return response, err
}
return sturdyc.GetOrFetchBatch(ctx, client.cache, usernames, cacheKeyFn, fetchFunc)
}
```
In the example above, the `fetchFunc` would get called for users where we don't
have their gists in our cache, and the cacheMisses slice would contain their
actual usernames (without the prefix from the keyFn).
The map that we return from our `fetchFunc` should have the IDs (in this case the
usernames) as keys, and the actual data that we want to cache (the gist) as the
value.
Later, we'll see how we can use closures to pass query parameters and options
to our fetch functions, as well as how to use the `PermutatedBatchKeyFn` to
create unique cache keys for each permutation of them.
# Stampede protection
`sturdyc` provides automatic protection against cache stampedes (also known as
thundering herd) - a situation that occurs when many requests for a particular
piece of data, which has just expired or been evicted from the cache, come in
at once.
Preventing this has been one of the key objectives. We do not want to cause a
significant load on an underlying data source every time one of our keys
expire. To address this, `sturdyc` performs _in-flight_ tracking for every key.
We can demonstrate this using the `GetOrFetch` function which, as I mentioned
earlier, takes a key, and a function for retrieving the data if it's not in the
cache. The cache is going to ensure that we never have more than a single
in-flight request per key:
```go
var count atomic.Int32
fetchFn := func(_ context.Context) (int, error) {
// Increment the count so that we can assert how many times this function was called.
count.Add(1)
time.Sleep(time.Second)
return 1337, nil
}
// Fetch the same key from 5 goroutines.
var wg sync.WaitGroup
for i := 0; i < 5; i++ {
wg.Add(1)
go func() {
// We'll ignore the error here for brevity.
val, _ := cacheClient.GetOrFetch(context.Background(), "key2", fetchFn)
log.Printf("got value: %d\n", val)
wg.Done()
}()
}
wg.Wait()
log.Printf("fetchFn was called %d time\n", count.Load())
log.Println(cacheClient.Get("key2"))
```
Running this program we can see that we were able to retrieve the value for all
5 goroutines, and that the fetchFn only got called once:
```sh
❯ go run .
2024/05/21 08:06:29 got value: 1337
2024/05/21 08:06:29 got value: 1337
2024/05/21 08:06:29 got value: 1337
2024/05/21 08:06:29 got value: 1337
2024/05/21 08:06:29 got value: 1337
2024/05/21 08:06:29 fetchFn was called 1 time
2024/05/21 08:06:29 1337 true
```
The in-flight tracking works for batch operations too where the cache is able
to deduplicate a batch of cache misses, and then assemble the response by
picking records from **multiple** in-flight requests.
To demonstrate this, we'll use the `GetOrFetchBatch` function, which as mentioned
earlier, can be used to retrieve data from a data source capable of handling
requests for multiple records at once.
We'll start by creating a mock function that sleeps for `5` seconds, and then
returns a map with a numerical value for every ID:
```go
var count atomic.Int32
fetchFn := func(_ context.Context, ids []string) (map[string]int, error) {
// Increment the counter so that we can assert how many times this function was called.
count.Add(1)
time.Sleep(time.Second * 5)
response := make(map[string]int, len(ids))
for _, id := range ids {
num, _ := strconv.Atoi(id)
response[id] = num
}
return response, nil
}
```
Next, we'll need some batches to test with, so here I've created three batches
with five IDs each:
```go
batches := [][]string{
{"1", "2", "3", "4", "5"},
{"6", "7", "8", "9", "10"},
{"11", "12", "13", "14", "15"},
}
```
and we can now request each batch in a separate goroutine:
```go
for _, batch := range batches {
go func() {
res, _ := cacheClient.GetOrFetchBatch(context.Background(), batch, keyPrefixFn, fetchFn)
log.Printf("got batch: %v\n", res)
}()
}
// Just to ensure that these batches are in fact in-flight, we'll sleep to give the goroutines a chance to run.
time.Sleep(time.Second * 2)
```
At this point, the cache should have 3 in-flight requests for IDs 1-15:
```sh
[1,2,3,4,5] => REQUEST 1 (IN-FLIGHT)
[6,7,8,9,10] => REQUEST 2 (IN-FLIGHT)
[11,12,13,14,15] => REQUEST 3 (IN-FLIGHT)
```
Knowing this, let's test the stampede protection by launching another five
goroutines. Each of these goroutines will request two random IDs from our
previous batches. For example, they could request one ID from the first
request, and another from the second or third.
```go
// Launch another 5 goroutines that are going to pick two random IDs from any of our in-flight batches.
// e.g:
// [1,8]
// [4,11]
// [14,2]
// [6,15]
func pickRandomValue(batches [][]string) string {
batch := batches[rand.IntN(len(batches))]
return batch[rand.IntN(len(batch))]
}
var wg sync.WaitGroup
for i := 0; i < 5; i++ {
wg.Add(1)
go func() {
ids := []string{pickRandomValue(batches), pickRandomValue(batches)}
res, _ := cacheClient.GetOrFetchBatch(context.Background(), ids, keyPrefixFn, fetchFn)
log.Printf("got batch: %v\n", res)
wg.Done()
}()
}
wg.Wait()
log.Printf("fetchFn was called %d times\n", count.Load())
```
Running this program, and looking at the logs, we'll see that the cache is able
to resolve all of the ids from these new goroutines without generating any
additional requests even though we're picking IDs from different in-flight
requests:
```sh
❯ go run .
2024/05/21 09:14:23 got batch: map[8:8 9:9]
2024/05/21 09:14:23 got batch: map[4:4 9:9] <---- NOTE: ID 4 and 9 are part of different batches
2024/05/21 09:14:23 got batch: map[11:11 12:12 13:13 14:14 15:15]
2024/05/21 09:14:23 got batch: map[1:1 7:7] <---- NOTE: ID 1 and 7 are part of different batches
2024/05/21 09:14:23 got batch: map[10:10 6:6 7:7 8:8 9:9]
2024/05/21 09:14:23 got batch: map[3:3 9:9] <---- NOTE: ID 3 and 9 are part of different batches
2024/05/21 09:14:23 got batch: map[1:1 2:2 3:3 4:4 5:5]
2024/05/21 09:14:23 got batch: map[4:4 9:9] <---- NOTE: ID 4 and 9 are part of different batches
2024/05/21 09:14:23 fetchFn was called 3 times <---- NOTE: We only generated 3 outgoing requests.
```
The entire example is available [here.](https://github.com/viccon/sturdyc/tree/main/examples/basic)
# Early refreshes
Serving data from memory is typically at least one to two orders of magnitude
faster than reading from disk, and if you have to retrieve the data across a
network the difference can grow even larger. Consequently, we're often able to
significantly improve our applications performance by adding an in-memory
cache.
However, one has to be aware of the usual trade-offs. Suppose we use a TTL of
10 seconds. That means the cached data can be up to 10 seconds old. In many
applications this may be acceptable, but in others it can introduce stale
reads. Additionally, once the cached value expires, the first request after
expiration must refresh the cache, resulting in a longer response time for that
user. This can make the average latency look very different from the P90–P99
tail latencies, since those percentiles capture the delays of having to go to
the actual data source in order to refresh the cache. This in turn can make it
difficult to configure appropriate alarms for your applications response times.
`sturdyc` aims to give you a lot of control over these choices when you enable
the **early refreshes** functionality. It will prevent your most frequently
used records from ever expiring by continuously refreshing them in the
background. This can have a significant impact on your applications latency.
We've seen the P99 of some of our applications go from 50ms down to 1.
One thing to note about these background refreshes is that they are scheduled
if a key is **requested again** after a configurable amount of time has passed.
This is an important distinction because it means that the cache doesn't just
naively refresh every key it's ever seen. Instead, it only refreshes the
records that are actually in active rotation, while allowing unused keys to be
deleted once their TTL expires. This also means that the request that gets
chosen to refresh the value won’t retrieve the updated data right away as the
refresh happens asynchronously.
However, asynchronous refreshes present challenges with infrequently requested
keys. While background refreshes keep latency low by serving cached values
during updates, this can lead to perpetually stale data. If a key isn't
requested again before its next scheduled refresh, we remain permanently one
update behind, as each read triggers a refresh that won't be seen until the
next request. This is similar to a burger restaurant that prepares a new burger
after each customer's order - if the next customer arrives too late, they'll
receive a cold burger, despite the restaurant's proactive cooking strategy.
To solve this, you also get to provide a synchronous refresh time. This
essentially tells the cache: "If the data is older than x, I want the refresh
to be blocking and have the user wait for the response." Or using the burger
analogy: if a burger has been sitting for more than X minutes, the restaurantFrequently Asked Questions
What is sturdyc?
sturdyc is a Database library for the Go programming language. A caching library with advanced concurrency features designed to make I/O heavy applications robust and highly performant
How many GitHub stars does sturdyc have?
sturdyc has 1,282 GitHub stars in the directory's latest synchronization.
How do I install sturdyc?
Install sturdyc with the Go module system using `go get viccon/sturdyc`. Check the repository for the current installation instructions.
What category does sturdyc belong to?
sturdyc is listed under Database, specifically Caches.