Keeping an in-memory database alive; caching and memcached

Four ways to keep RAM from forgetting

Redis answers from memory, which is why it is fast (lesson 17). Memory has two weaknesses: it forgets everything when the process or the machine stops, and one machine has only so much of it. The lecture is frank about the price of fixing the first: "increased persistency will tend to increase latency and decrease throughput" (p. 349).

Page 359, "Scaling Redis", answers with four headings, and each one guards against a different accident (Fig. 1):

Persistence survives a restart, replication survives a lost machine, partitioning survives growth, failover keeps the writes going when the master dies.

Snapshot or log?

The slide only names the two; the mechanics are from the Redis documentation. An RDB snapshot is a photograph: every few minutes, or sooner when many keys change, Redis writes a point-in-time copy of the whole dataset into one compact file. An AOF is a ledger: every write command is appended to a log, which Redis replays at restart.

A crash therefore costs different amounts (Fig. 2). The snapshot loses everything written since it was taken — minutes. The log loses only what had not reached the disk: about a second with the default policy (one flush per second), nothing if the file is synced after every write. That last setting is the "increased persistency" of p. 349: every write waits for the disk. In exchange, a snapshot is smaller and faster to reload than a log of every command. With both switched on, Redis restarts from the log, the more complete of the two.

Four topologies on one two-by-two

Page 360 lists four arrangements, each with its promise in brackets (the rendering jumbles the words): "I. Standalone", "II. Sentinel (automatic failover)", "III. Twemproxy (distribute data)", "IV. Cluster (automatic failover and distribute data)". Two capabilities, four combinations.

I · Standalone: copies, and nobody to promote them

Page 361 draws three shapes: a master alone, a master with slaves, and slaves of slaves ("multi-level"). The slaves give "data redundancy, reads offloading and save-to-disk offloading": a copy if the master's machine dies, more machines for reads, and a machine that writes the snapshots and logs instead of the master. "Clients can connect to the Master for read/write operations or to the Slaves for read operations." Then the line that matters: "There is no automatic failover."

Why read-only slaves? One machine orders the writes, so the copies never disagree about them. The copying is asynchronous (from the Redis documentation): the master answers before the slaves have the write, so a slave promoted after a crash may lack the last writes.

II · Sentinel: a watchdog that promotes

"Redis Sentinel provides a reliable automatic failover in a master/slave topology, automatically promoting a slave to master if the existing master fails" (p. 362). The figure puts a Sentinel on each of three servers, watching the master and the slaves and talking to each other. Why several? So that one Sentinel with a broken cable cannot depose a healthy master: the Redis documentation asks for at least three, and a failover needs the vote of a majority of them. The second bullet: "Sentinel does not distribute data across nodes" — every slave still holds the whole dataset.

III · Twemproxy: a proxy that splits

"Twemproxy works as a proxy between the clients and many Redis instances" — the second picture runs three of them behind a load balancer — and "Is able to automatically distribute data among different standalone Redis instances" (p. 363). It "Supports consistent hashing": servers and keys are hashed onto the same circle, and a key belongs to the first server point after it, clockwise; when a server joins or leaves, only the keys next to its points move, about one in n for n servers, where "hash mod the number of servers" would move almost all. Twemproxy "is a project from Twitter and is not part of redis"; "Multi-key commands and transactions are not supported" — such a command may need several servers — and there is no failover: a dead instance takes its keys with it.

IV · Cluster: slots with owners

"Redis Cluster distributes data across different Redis instances and perform automatic failover if any problem happens to any master instance" (p. 364). "All nodes are directly connected with a service channel": they check on each other and agree on who is alive. "The keyspace is divided into hash slots. Different nodes will hold a subset of hash slots." The figure adds the numbers — "Slots 0-6000", "Slots 6001-12000", "Slots 12001-16383": 16384 hash slots in all, each owned by one master. Which slot a key falls into is fixed by a formula of the Redis Cluster specification:

Key foo lands in slot 12182, so in the slide's cluster it lives on master C. When a master fails, one of its slaves is promoted and takes over its range of slots; the formula never changes, so every key keeps its slot. The last bullet: "Multi-key commands are only allowed for keys in the same hash slot." A command that needs two keys must run on one machine, atomically. user:42:name and user:42:city land in slots 6755 and 8210 — both on master B, yet the command is refused, because slots, not machines, are the unit that moves between masters:

redis> MGET user:42:name user:42:city
(error) CROSSSLOT Keys in request don't hash to the same slot

The way out is a hash tag: when a key contains {…}, only the part inside the first pair of braces is hashed. {user:42}:name and {user:42}:city both hash user:42 and share slot 15880:

redis> MSET {user:42}:name "Ada" {user:42}:city "Milano"
OK

Now kill some masters yourself. The widget shows one insight: copies are not failover, and failover is not distribution — only Cluster has both.

When a cache pays

Back to the hook's second program. The slides define a cache with Wikipedia (p. 367): "A cache is a collection of data duplicating original values stored elsewhere or computed earlier, where the original data is expensive to fetch (owing to longer access time) or to compute, compared to the cost of reading the cache" — a term they credit to IBM, in the 1960s. Its anatomy (p. 368) is the key-value store of lesson 17 cut to the bone: "simple key/value storage" and three operations, save, get, delete.

The vocabulary of p. 369, with what each name means:

A request that finds its key is a cache hit; one that does not is a miss, and goes to the original. Page 370 takes 45 hits and 10 misses:

The slide rounds them to "82% hit ratio" and "18% miss ratio".

More hits than misses?

Page 371, "When to cache?", gives a principle and a shortcut: "caches are only efficient when the benefits of faster access outweigh the overhead of checking and keeping your cache up to date" — "more cache hits then cache misses". The derivation below, not on the slides, turns the principle into a number. Call \(t_c\) the cost of one look into the cache and \(t_o\) the cost of the original, the database query:

1. A hit costs only the look: \(t_c\). A miss costs the look and then the trip to the original: \(t_c + t_o\).

2. A fraction \(h\) of the requests hit and \(1 - h\) miss, so the average request costs

   \[ T = h\,t_c + (1-h)(t_c + t_o) . \]

3. Collect \(t_c\), which every request pays:

   \[ T = t_c + (1-h)\,t_o . \]

4. Without the cache every request costs \(t_o\). The cache pays when \(T \lt t_o\):

   \[ t_c + (1-h)\,t_o \lt t_o \iff h \gt \frac{t_c}{t_o} . \]

5. So the break-even hit ratio is \(h^* = t_c / t_o\): the price of a look, measured in trips to the original. "More hits than misses", \(h \gt 0.5\), is the same rule only when a look costs half a trip. (Writing the copies and invalidating them adds to \(t_c\): the "keeping your cache up to date" of the slide.)

Where caches live

Caches sit wherever something slow stands behind something fast. Page 372 lists hardware ("cpu, hdd"), operating systems ("ram"), the "web stack", applications — even "your own short term vs long term memory". The web stack holds a ladder of them (p. 373): browser cache, DNS cache, Content Delivery Networks, proxy servers and, in the application, "full output caching" and the data caching of section 5. Along the ladder (p. 374), "the closer to the original request(er), the faster" — "but probably also the harder to get it right", since "the closer to the requester the more parameters the cache depends on": a copy in your browser depends on you, your cookies, your language; one next to the database serves every user.

Memcached: a cache that forgets on purpose

Memcached is the cache of the slides: a "Free & open source, high-performance, distributed memory object caching system", "Generic in nature, intended for use in speeding up dynamic web applications by alleviating database load", a "key/value dictionary" (p. 376). It was "Developed by Brad Fitzpatrick for LiveJournal in 2003" (p. 377).

"Technically" (p. 378): "It's a server", reached by "Client access over TCP or UDP". "Servers can run in pools": "eg. 3 servers with 64GB mem each give you a single pool of 192GB storage for caching". And the design decision: "Servers are independent, clients manage the pool". No server knows the others; the client library hashes the key and picks the server (Fig. 3) — the client layer of partitioning from p. 359. Each key has one home, so every server added adds its whole memory.

What deserves a place in it (pp. 379–380): data that is in "high demand (used often)", "expensive (hard to compute)" and "common", shared across users — "Best: All three". The typical tenants: "user sessions (often)", "user data (often, shared)", "homepage data (eg. often, shared, expensive)".

Its principles are its limits

Page 381 opens with one strength, "Fast network access (memcached servers close to other application servers)", then four refusals: "No persistency (if your server goes down, data in memcached is gone)", "No redundancy / fail-over", "No replication (single item in cache lives on one server only)", "No authentication (not in shared environments)". Page 382 adds limits and two more refusals: "1 key is maximum 1MB", "keys are strings of 250 characters (in application typically MD5 of user readable string)", "No enumeration of keys (thus no list of valid keys in cache at certain moment)", "No active clean-up (only clean up when more space needed, LRU: Least Recently Used )".

Read the list against p. 359: by design, memcached lacks three of the four kinds of machinery of section 1 — persistence, replication, failover — and keeps only the simplest form of the fourth, partitioning done by the client. It does not need the other three: every value in it duplicates something stored elsewhere, so a dead server costs time — its keys miss until reloaded from the database — not data. Its client API (p. 383) is the small vocabulary of any key-value store: add, set, get, getMulti, delete, increment, decrement, flush, plus addServer to grow the pool and getStats to watch it.

Memcached and Redis side by side

Page 365 lists Redis's advantages: "Performance", "Availability", "Fault-Tolerance", "Scalability (adaptability)", "Portability"; "Support for complex data types and structures", "Atomic operations and Transactions", "Pipelining (send multiple commands at once)", "LUA scripting support", "LRU eviction of keys", "Keys with limited time-to-live"; and an open-source server, simple to set up, with clients in many languages. Against memcached's principles:

The last row is the chart of Redis's advantages slide (p. 365), redrawn in Fig. 4. It prints no unit and no description of the benchmark, and comes from a vendor's blog (redislabs.com): read it for orders of magnitude.

Two facts to take from it. Redis and Memcached tie at 80,000: memcached's refusals buy simplicity, not speed. And "Redis pipelined" reaches 250,000, three times as much. Pipelining, "send multiple commands at once" (p. 365), removes waiting: instead of one network round trip per command, the client sends a batch and collects the replies together. Page 393 makes the same point for reads: even a hit costs a trip to the memcached server, so use multiget, "fetch multiple keys from memcached in one single call" — the "result is array of items". Redis's MGET does the same. In PHP it is the getMulti of p. 383 (the line is ours):

<?php
// multiget: three keys, one round trip; returns an array of the items found
$users = $cache->getMulti(array('user_1', 'user_2', 'user_3'));
?>

Cache-aside in code, and the two hard things

The slides show memcached at work in PHP. The first program caches a whole page, the "full output caching" of p. 373 (p. 384):

<?php
// p. 384: prints the page, built only on a miss
$html = $cache->get('mypage');
if (!$html)
{
  ob_start();
  echo "<html>";
  // all the fancy stuff goes here
  echo "</html>";
  $html = ob_get_contents();
  ob_end_clean();
  $cache->set('mypage', $html);
}
echo $html;
?>

Read it aloud: ask the cache for 'mypage'; if nothing comes back, build the page (PHP's output buffer, ob_start … ob_get_contents, captures everything echoed in between), store it under the key, print it. The next visitor gets the stored copy. This shape — look in the cache; on a miss compute or fetch, store, return — is called cache-aside (the name is not on the slides; Fig. 5).

Caching a whole page is fast but fragile: the page depends on everything shown on it. Page 385 moves the cache "on a lower level", to data caching: "easier to find all dependencies", the "ideal solution for offloading database queries", because "the database is almost always the biggest bottleneck in backend performance problems". The slide's code caches one user's row (p. 386; the key in set is restored, see the red pen):

<?php
// p. 386: the row of user $UID, from the cache if there
function getUserData($UID)
{
  $key = 'user_' . $UID;
  $userData = $cache->get($key);
  if (!$userData)
  {
    $queryResult = Database::query(
      "SELECT * FROM USERS WHERE uid = " . (int) $UID);
    $userData = $queryResult->getRow();
    $cache->set($key, $userData);
  }
  return $userData;
}
?>

The key is the user's business key, prefixed: 'user_' . $UID. On a miss one query by primary key runs — (int) lets only a number reach the SQL — and the row is stored.

The two hard things

Page 387 is one quote on a blackboard: "There are only two hard things in Computer Science: cache invalidation and naming things." — Phil Karlton. For the first, the slides give two strategies (Fig. 6).

Time-based (pp. 388–389): "Caching for a certain amount of time", "eg. 10 minutes"; "don't delete caches"; "thus: You can't trust that data coming from cache is correct". It is "Great for summaries", an "Overview", "Pages where it's not that big a problem if data is a little bit out of date (eg. search results)", and "Good for quick and dirty optimizations". In Redis this is the TTL of lesson 18: SET key value EX 600.

Event-based (pp. 390–392): "Store forever, and expire on certain events" — "store userdata for ever", and "when user changes any of his preferences, throw cache away". The read side keeps the query result with no expiry, and can be told to invalidate instead (p. 391):

<?php
// p. 391: the row of user $UID, or drop its cached copy
function getUserData($UID, $invalidateCache = false)
{
  $db = DB::getInstance();
  $db->prepare("SELECT * FROM USERS WHERE uid = {UID}");
  $db->assignInt('UID', $UID);
  $db->setCacheTTL(0); // cache forever
  if ($invalidateCache)
  {
    return $db->invalidateCache();
  }
  $db->execute(); return $db->getRow();
}
?>

and the write side throws the copy away after every update (p. 392):

<?php
// p. 392: update the row, then drop its cached copy
function updateUserData($UID, $data)
{
  $db = DB::getInstance();
  $db->prepare("UPDATE USERS SET ... WHERE uid = {UID}");
  ...
  getUserData($UID, true); // invalidate cache
  return $result;
}
?>

The cache lives inside a database wrapper (setCacheTTL(0), "cache forever"; invalidateCache()) that the slides do not show: read the pattern, not the API. After an update the next read misses and reloads the fresh row: the old copy is gone as soon as the write drops it, at the price of a delete per write and a miss after it. In the widget of section 3, a TTL traded stale reads for misses and never reached zero; deleting on write reached zero and kept nearly the whole hit ratio.

The deck closes with three tips (p. 394): be careful when security matters — remember "no authentication" (SASL authentication was then in the works); "Caching is not an excuse not to do database tuning. (Remember cold cache?)" — after a restart every request misses and the database takes the whole load; and write unit tests for your caching code, because "Debugging problems related to out-of-date cache data is hard and boring. Very boring."

Back to the hook. The word is duplicating: a cache holds "data duplicating original values stored elsewhere" (p. 367). When memcached loses a server, the originals are still in the database: the loss is time — a cold cache, a database under full load — never data. Redis, used as a database, may hold the only copy, so a crash would be a real loss: hence snapshots, logs, slaves, Sentinel and Cluster. Neither program is badly designed; they answer different questions. And whether a cache is worth having is one ratio: its hit ratio against the break-even \(t_c / t_o\).