Recently, a project I was working on required a cache that would ideally be capable of storing tens of millions of entries, reaching into the multiple-terabyte range. At this scale, using a single spinning disk is significantly cheaper than storing everything in memory, which Redis or Memcached would require. Another classic KV store, LevelDB, also ends up being impractical because it writes the value for each key to disk multiple times. If your values are small, LevelDB can be really really performant, but in my case the values are moderately sized (tens of kilobytes) and writing them to disk multiple times quickly becomes user-visible. And finally, I expected that storing this many entries on-disk as individual files in a folder would cause issues with inode exhaustion, and ultimately, the ACID guarantees that a filesystem provides have never been super clear to me.
This blog post describes how to build an on-disk cache with SQLite that’s capable of evicting entries when the cache gets too large. SQLite is a bit more machinery than I would’ve initially wanted but it scales to the size I want, provides ACID guarantees, and is surprisingly performant. The only difficulty is that it doesn’t have a good way to randomly select rows for eviction.
The underlying idea to get around this is to maintain a random shuffle of keys
in the database, so that ‘randomly evicting’ simply consists of deleting the
last N rows. The reason for random eviction (instead of LRU) is that I didn’t
Get operations to cause any writes to disk, which an LRU would need to
keep track of usage.
All operations are fairly fast, having a runtime that’s logarithmic in the number of rows.
The table schema:
CREATE TABLE cache (key TEXT NOT NULL PRIMARY KEY, val BYTEA);
PRIMARY KEY clause creates an index on the
key column, and this enables
efficient lookups by
When the process using the cache starts up, it needs to first get the max
rowid and store this in a variable called
n. This is used for maintaining
the random shuffle. The max rowid can be found with:
SELECT MAX(rowid) FROM cache;
Get operations simply consist of looking up the
val of the corresponding
SELECT val FROM cache WHERE key = ?;
Set operation is accomplished by performing an “inside-out” Fisher-Yates
shuffle. First, increment
n = n+1. Then choose a random number
i such that
1 <= i <= n. If
i != n, then move the row at rowid
i to rowid
UPDATE cache SET rowid = n WHERE rowid = i;
and insert the new row at rowid
INSERT OR REPLACE INTO cache (rowid, key, val) VALUES (i, ?, ?);
Note that the multiple queries should be performed in a transaction for consistency.
Delete the row with a given key, first lookup the rowid
i of the row
you wish to delete:
SELECT rowid FROM cache WHERE key = ?;
Then delete that row, and move the row with the highest rowid into that spot:
DELETE FROM cache WHERE rowid = i; UPDATE cache SET rowid = i WHERE rowid = n;
And finally decrement
n = n-1. Again, these queries should be performed in a
transaction for consistency.
If the cache is too large, a number of rows can be evicted by repeatedly deleting the row with the largest rowid:
DELETE FROM cache WHERE rowid = n;
n = n-1.
Note that eviction won’t actually reduce the amount of disk space used by SQLite
without running an expensive
VACCUM query, but it will allow previously
allocated space to be reused.