Redis at Trivago

Ideas you will meet

Caching

Cache-aside, write-through, eviction and invalidation strategies.

Redis

In-memory data structures for caching, queues and leaderboards.

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• System Design Foundations · 11 minCachingHow keeping popular data in fast memory makes systems quicker, and the invalidation problems that come with it.Read hereClose

  Why a cache helps

  Reading from memory is thousands of times faster than a database round trip (lesson 3). A cache keeps copies of frequently needed data in fast storage so most requests never reach the slower source. The results: lower latency, less load on the database, and lower cost.

  100%

  Figure SDA-FND-06-1 · Cache-aside read path · © forcsguy.com

  Before: every read hits the database

  100%

  After: a cache answers most reads

  100%

  What changed

  • Most reads never reach the database
  • Responses are faster because memory is quicker than disk
  • The cache can be stale, so you decide how long is acceptable

  Where caches live

  • In the browser: controlled with HTTP headers such as Cache-Control.
  • At the edge (CDN): copies of pages and files near the user (lesson 9).
  • In the application tier: a shared cache like Redis or Memcached.
  • Inside the database: buffer pools and query caches.

  You can use several at once, each answering whatever it can.

  Common strategies

  Strategy	How it works	Good for
  Cache-aside	App checks cache, on miss reads the database and fills the cache	the default for most read-heavy data
  Read-through	The cache itself loads from the database on a miss	simpler app code
  Write-through	Writes go to the cache and the database together	data you read right after writing
  Write-behind	Writes go to the cache first and reach the database later	very high write rates, if you can risk losing a little

  Write-behind is fast but dangerous: if the cache fails before it flushes, writes are lost.

  Writes can use the cache in three different ways. The sequence shows when the database learns about the change:

  100%

  Figure SDA-FND-06-2 · Write-through: update the cache and the database together · © forcsguy.com

  100%

  Figure SDA-FND-06-3 · Write-back: acknowledge first, save later · © forcsguy.com

  100%

  Figure SDA-FND-06-4 · Write-around: skip the cache on writes · © forcsguy.com

  Watch one read with and without a warm cache. Press Play both together, and use the Simulate tab to slow the network and see the gap grow.

  Before: no cache

  100%

  After: cache hit

  100%

  What changed

  • The database is not asked at all
  • Two network hops disappear from the request
  • The saving grows as the network gets slower

  The hard part: invalidation

  There are only two hard things in computer science: cache invalidation and naming things.

  A cache holds a copy, and copies go stale. Your options:

  1. Time to live (TTL): entries expire after a set time. Simple, but data can be stale until then.
  2. Explicit invalidation: delete or update the cache entry when the source changes. Fresher, but you must never forget a code path.
  3. Versioned keys: put a version in the key (product:42:v7) so a change simply starts using a new key.

  Most real systems combine a TTL (a safety net) with explicit invalidation on writes.

  100%

  Figure SDA-FND-06-5 · Defending the database from lookups of keys that do not exist · © forcsguy.com

  Eviction: what to drop when full

  Memory is limited, so a cache removes items when it fills. Common policies: LRU (least recently used), LFU (least frequently used) and FIFO. LRU is a good default.

  Failure modes to know

  • Cache stampede: a hot key expires and many requests rebuild it at once. Fix with a lock, request coalescing, or adding random jitter to expiry times.
  • Cache penetration: requests for keys that do not exist always miss and reach the database. Fix by caching "not found" briefly, or with a Bloom filter.
  • Cold start: after a restart the cache is empty and the database takes the full load. Warm the cache or ramp traffic up.
  • Inconsistency: two writers update the cache and database in different orders. Prefer deleting the cache entry on write over updating it.

  A worked example: what a cache is really worth

  Suppose a product page reads from a database in 20 ms and from a cache in 1 ms, and the site serves 10,000 reads per second.

  Cache hit rate	Average latency	Reads reaching the database
  0% (no cache)	20 ms	10,000 per second
  50%	10.5 ms	5,000 per second
  90%	2.9 ms	1,000 per second
  99%	1.2 ms	100 per second

  The average latency is hit x 1 + (1 - hit) x 20. Notice two things. First, going from 90% to 99% barely changes the average (2.9 to 1.2 ms) but cuts database load ten times. That is usually the real prize: a cache is a way to protect the database. Second, the first 50% is cheap and the last 9% is expensive: it needs a much bigger cache, because the remaining misses are the long tail of rarely requested items.

  How big should it be? Traffic is usually skewed: a small share of items gets most requests (often described as "80% of requests go to 20% of items", and for popular content it is more extreme). Estimate your working set: the items requested within your cache lifetime. If 2 million product pages exist but 100,000 get 90% of the traffic, a cache that holds 150,000 of them at about 5 KB each needs only 750 MB. Measure the hit rate while changing the size, and stop growing when the curve flattens.

  100%

  Figure SDA-FND-06-6 · Hit rate rises quickly, then flattens · © forcsguy.com

  Stampedes: when a popular key expires

  Take a homepage fragment read 5,000 times a second and cached for 60 seconds. At the moment it expires, thousands of requests miss at once, and every one of them rebuilds it from the database. The database, which was lightly loaded because of the cache, suddenly takes a spike. If the rebuild is slow, requests pile up, the spike lasts longer, and the system can fall over exactly when it is busiest.

  Ways to defend:

  • Request coalescing (single flight). Let one request rebuild the value while the others wait for its result.
  • A short lock on rebuild. The first request takes a lock and rebuilds; the rest either wait briefly or serve the old value.
  • Stale-while-revalidate. Keep serving the expired value for a few more seconds while one background request refreshes it. Users see slightly old data and never see a spike.
  • Jittered expiry. Add a random amount to each TTL (for example 60 seconds plus up to 10) so thousands of keys written together do not all expire together.
  • Refresh ahead. For a handful of known-hot keys, refresh them on a schedule before they expire.

  100%

  Figure SDA-FND-06-7 · One request rebuilds, the others wait or use the old value · © forcsguy.com

  Mistakes people make

  • Caching without a plan for invalidation. "Cache it for an hour" is a promise that users may see hour-old data. Decide what staleness each kind of data tolerates (a like count: minutes; a price or permission: seconds or never).
  • Caching per-user data under a shared key. If a personalised page is cached under a key that does not include the user, the next visitor sees someone else's data. Include everything that changes the response in the key, or do not cache it.
  • Treating the cache as the source of truth. Caches lose data on restart or eviction. The database must be able to rebuild everything.
  • Ignoring the hot key. One enormously popular key can overload a single cache node. Replicate that key across nodes or add a small in-process cache in front.
  • Not measuring. Track hit rate, evictions, memory use and the latency of misses. A cache you do not measure is a guess.

  Try it yourself

  In the System Builder, open "The database becomes the bottleneck". Run it without a cache and watch the database turn red, then add a cache and try different sizes. In the sandbox, raise the "popular-item skew" slider and notice how much a small cache helps when a few items dominate. You can also open the cached design on the free canvas and try wiring the cache in front of different parts.

  More on this site

  Related reading

  • Flannel: An Application-Level Edge Cache to Make Slack ScaleSlack Engineering · SlackCase Studies
  • Redis UniversityRedis · Redis Ltd.Courses
  • Redis BlogRedis engineers · Redis Ltd.Blogs
  • RedisRedis · Redis Ltd.GitHub

  Show 6 moreShow fewer

  • Redis DocumentationRedis · Redis Ltd.Documentation
  • TAO: Facebook's Distributed Data Store for the Social Graph (paper)Bronson et al. · Meta (Facebook)Papers
  • Build Your Own XCodeCrafters · GitHubGitHub
  • Memory Optimization in Redis at WattpadWattpad engineers · WattpadCase Studies
  • Redis Fleet at HerokuHeroku engineers · HerokuCase Studies
  • Redis at TrivagoTrivago engineers · TrivagoCase Studies

  Open this lesson with its quiz and exercise

• Search, Analytics and Geo · 10 minNearby search with Redis GEOHow Redis stores locations in a sorted set using geohash scores, how GEOSEARCH finds nearby members, how to expire stale entries, and when to move to a spatial database.Read hereClose

  The problem

  "Show the nearest available drivers", "stores within 3 km", "friends nearby". The data is a large set of points that change often, and the question is always about a small neighbourhood. You want a fast, in-memory structure.

  How Redis does it

  Redis stores locations in an ordinary sorted set. Each member (a driver id) has a score that is a 52-bit geohash of its longitude and latitude. Geohash interleaves the bits of the two coordinates so that nearby places have nearby scores. A search turns a radius into a few score ranges, reads those ranges, then filters by exact distance.

  100%

  Figure SDA-SAG-09-1 · A nearby query in Redis · © forcsguy.com

  Typical commands:

  GEOADD drivers:blr 77.5946 12.9716 driver:42
  GEOSEARCH drivers:blr FROMLONLAT 77.60 12.97 BYRADIUS 2 km ASC COUNT 20 WITHDIST
  

  Design details

  • Partition the key. One sorted set for the whole planet is a hot spot and slow to search. Use a key per city, region or grid cell so each set is small and local, and shard keys across nodes.
  • Updates are cheap. Moving a member is another GEOADD, about O(log n). 75,000 updates per second is manageable on a few nodes.
  • Freshness. Sorted set members have no individual expiry. Keep a second sorted set lastseen with the update time as score, and run a job that removes members older than, say, 30 seconds from both sets.
  • Availability filter. Store only drivers who are available, or look up status after the search; keep the hot set small.
  • Accuracy. Redis uses a spherical model of the Earth, so distances can be off by a fraction of a percent, and results near a cell boundary rely on the exact filter. That is fine for "within 2 km", not for surveying.
  • Durability. Treat Redis as a rebuildable copy. The system of record is a database, and clients re-send their location every few seconds anyway.

  100%

  Figure SDA-SAG-09-2 · Keeping the hot set fresh · © forcsguy.com

  When Redis GEO is not enough

  Move to a spatial database such as PostGIS, or a purpose-built index, when you need polygons and fences, joins with other tables, constraints (opening hours, vehicle type) together with distance, or durable queries over history. Many systems combine them: a database for rich queries and Redis for the live, hot position data.

  Other grid systems are covered in the geofencing lesson and in the real-world reading: H3 (hexagons, good for aggregation and neighbours) and S2 (cells on a sphere).

  Real-world reading

  Related reading

  • Redis geospatial data typeRedisDocumentation
  • Redis GEOSEARCH commandRedisDocumentation
  • PostGIS documentationPostGIS project · PostGISDocumentation
  • H3: Uber's Hexagonal Hierarchical Spatial IndexUber Engineering · UberCase Studies

  Show 1 moreShow fewer

  • S2 GeometryGoogle · S2 GeometryDocumentation

  Open this lesson with its quiz and exercise

• Core Concepts: How Things Actually Work · 8 minWhy Redis is fast, and Redis versus MemcachedIn-memory storage, a single-threaded event loop and rich data structures, plus how persistence and replication work.Read hereClose

  Why it is fast

  1. Everything lives in memory. No disk seek on the read path.
  2. Simple, efficient data structures (hash tables, skip lists, compact encodings) with predictable costs.
  3. A single-threaded event loop for command execution: no locks between threads, no context switching, and each command runs atomically. I/O multiplexing lets one thread serve thousands of connections.
  4. A lean protocol and in-process memory management.

  (Newer versions use extra threads for network I/O, but command execution stays ordered.)

  Image: Mixabest · Public domain · Source · Wikimedia Commons: Dual-channel DDR memory use 6026

  How the pieces fit

  100%

  Figure SDA-CORE-09-1 · Redis: event loop, memory, persistence and replication · © forcsguy.com

  More than a cache

  Redis stores typed values:

  Type	Use
  String	cached values, counters, flags
  Hash	objects with fields (a user profile)
  List	queues, recent items
  Set	unique members, tags, set maths
  Sorted set	leaderboards, priority queues, time-ordered data
  Others	streams, bitmaps, HyperLogLog, geospatial

  Because operations run on the server, you can increment, push, pop or intersect without a read-modify-write race.

  100%

  Figure SDA-CORE-09-2 · Redis data types and what they are for · © forcsguy.com

  Durability options

  Memory is volatile, so Redis offers:

  • Snapshots (RDB): periodic point-in-time dumps. Compact, but recent writes can be lost.
  • Append-only file (AOF): logs every write; replays on restart. Safer, bigger and a little slower.
  • Or none at all when it is purely a cache.

  Scaling and availability

  • Replication: a primary copies to replicas (asynchronously), serving reads and enabling failover.
  • Sentinel / managed failover promotes a replica when the primary dies.
  • Cluster: splits keys across nodes by hash slot, for data larger than one machine.

  Redis versus Memcached

  	Redis	Memcached
  Data types	many	strings only
  Persistence	optional	none
  Replication	yes	not built in
  Threading	one for commands	multi-threaded
  Best for	cache plus data structures, queues, counters	a very simple, large, pure cache

  For most new projects Redis is the more flexible choice. Memcached remains fine for a straightforward cache that must use many CPU cores.

  Pitfalls

  • Memory is finite: set a maxmemory and an eviction policy (for example LRU).
  • Avoid slow commands on huge collections.
  • A very hot key still concentrates load on one node.

  More on this site

  Related reading

  • Redis DocumentationRedis · Redis Ltd.Documentation
  • Redis BlogRedis engineers · Redis Ltd.Blogs
  • Redis UniversityRedis · Redis Ltd.Courses
  • RedisRedis · Redis Ltd.GitHub

  Show 6 moreShow fewer

  • Redis persistenceRedis · Redis Ltd.Documentation
  • Memory Optimization in Redis at WattpadWattpad engineers · WattpadCase Studies
  • Scale with Redis ClusterRedis · Redis Ltd.Documentation
  • Scaling Job Queue with Redis at SlackSlack engineers · SlackCase Studies
  • Moving persistent data out of Redis at GithubGithub engineers · GithubCase Studies
  • PayPal Developer Community BlogPaypal engineers · PaypalBlogs

  Open this lesson with its quiz and exercise