A database with no queries: key-value stores and Redis

One key, one value, one step

The lecture opens on the map of p. 342, "Overview – NoSQL Family": "Data stored in 4 types: Document, Graph, Key-value, Wide-column", with Redis, Amazon DynamoDB, Aerospike and Riak in the key-value cell (the four families are in lesson 5). Key-value is the plainest of the four, and p. 343, "Why is performance important?", says why anyone wants it: speed. Besides Amazon's 1 % of sales and Google's "20% drop in traffic", it reports that for a "1-second delay in page-load time" an "Industrial Group" counted "11% fewer page views", "16% decrease in customer satisfaction" and "7% loss in conversions".

Take the slide's own example, the blog database of p. 346 (Fig. 1). To show the page of blog post 101 you need its text from the blog table, its author's name from users and its category from category: three tables, tied by foreign keys. A key-value store keeps the whole page — text, author, category — as one value under one key, post:101, and hands it back in one step.

The examples of p. 345 are keys that businesses already have: "(twitter.com) tweet id -> information about tweet", "(kayak.com) Flight number -> information about flight", an account number at a bank, an item number at Amazon. Most of what a site is asked starts from one of them, hence the slide's last line: "Search by ID is usually built on top of a key-value store". In Python terms the store is a dict: d[key] = value, d[key], del d[key] — and no loop over the values.

Page 346 asks the obvious question, "Isn't that just a database?", and lists what a relational database is: "Queried using SQL", "Key-based", "Foreign keys", "Indexes", "Joins". Read the list as two columns: a relational database has all five, a key-value store keeps only one — key-based. Keys exist in both, but they play different roles. In the relational blog the primary and foreign keys connect the tables, indexes let SQL search by any column — the slide's query, SELECT user_id from users WHERE username = "jbellis", finds a user by name, not by key — and joins put the page back together. The course notes say it in one line: in a key-value store "keys are just used to retrieve a specific value, unlike relational databases where primary and foreign keys are means to do searches and mapping between tables".

So the key-value store gives up a lot: no query on what is inside the values, no join, no secondary index, no schema to check. What it buys with that is cost. A lookup by key in a hash table takes one step whatever the number of keys, and nothing has to be parsed, planned or assembled. The race below puts numbers on it.

One step in memory is the whole point. A relational lookup, however well indexed, climbs a tree whose height grows with the data and, on disk, pays a seek at every level; a join pays it once per table.

A key-value store answers one question — what is under this key? — and gives up every other question to answer that one in a single step.

There is a second gift (background, not on these slides). Because every request names its key, the keys can be spread over many machines by hashing them, and any client can compute where a key lives. Dynamo placed keys and machines on a ring — consistent hashing, invented at MIT in 1997 for web caches. Redis's own ways of splitting its keys come in lesson 19; the ring itself returns with Cassandra in lesson 22.

Redis: a dictionary served over the network

The section slide of p. 347 spells the name: REmote DIctionary Server. A dictionary — a hash map from keys to values — living in a server and answering over the network. Page 348, "What is REDIS ?", gives the definition:

Three ideas to keep apart. It is a key-value store: access by key, nothing else. The value under a key can be a data structure the server understands — a string, a hash, a list, a set, a sorted set. And the operations on those structures are atomic. The middle idea is what "advanced" means. To a plain key-value store a list is a string of bytes like any other; to Redis it is a list, so you send the operation instead of the value (Fig. 2).

The exercise session says the same in plain words: "The stored values can be simple types (e.g., numbers) or complex structures (e.g., lists)" (p. 1581). Values — keep that word in mind when you reread the first sentence of p. 348.

The last line of p. 348: "Can be used as Database, a Caching layer or a Message broker", and each role has its reason in a box under it. A database, because "Redis can persist data to the disk": it can write snapshots and logs and reload them after a restart (lesson 19). A caching layer, because "Redis is fast": copies of data that is expensive to fetch or to compute are served from memory. A message broker, because "Redis is not only a key-value store": clients publish messages on channels that other clients subscribe to, or hand work through a list that a worker waits on.

Page 349, "What is not REDIS", draws the limits:

• "Redis is not a replacement for Relational Databases nor Document Stores."
• "It might be used complementary to a SQL relational store, and/or NoSQL document store."
• "Even when Redis offers configurable mechanisms for persistency, increased persistency will tend to increase latency and decrease throughput."
• "Best used for rapidly changing data with a foreseeable database size (should fit mostly in memory)."

Each limit follows from where the data lives. In memory, the dataset must fit in the RAM you can afford, so its size must be foreseeable. Persistence is a dial: the more often Redis writes to disk before it answers, the longer each write waits for the disk — the price you saw in the race. So the system of record stays elsewhere, and Redis holds what is small, hot and changing fast (Fig. 3).

The use cases of p. 350 are the roles at work; the table pairs each with what does the work in Redis. (If you ever serve a trained neural network in an application, the features it reads at prediction time live in the same kind of store: the feature-store lecture says they are "typically stored in low-latency databases like Redis", p. 735, lesson 29.)

Page 351, "When to consider Redis", condenses all of this into four conditions — two reasons to choose Redis, then two limits it must respect:

• "Speed is critical" — the data is in memory and most commands take one step.
• "More than just key-value pairs" — you need the data structures and their atomic operations; for plain opaque values a simpler cache does the job (memcached, lesson 19).
• "Dataset can fit in memory" — the limit of p. 349.
• "Dataset is not critical" — you can afford to lose the latest changes if the server crashes, because making every write durable costs the speed you came for.

Redis is a key-value store whose values are data structures the server understands: you send the operation, not the whole value.

One thread, one command at a time

Page 352, "Redis Architecture", is a list of facts. The plain ones first: Redis is "Written in ANSI C by Salvatore Sanfilippo (@antirez)", "Works in most POSIX systems like Linux, BSD and OS X", "Linux is the recommended", and there is "No official support for Windows" (the slide adds a Win-64 port maintained by Microsoft). Two more lines carry the exam.

Start from a case. Two nurses' tablets record a visit to the same ward at the same instant: both send INCR visits, and visits holds 10. Inside a Redis server there is no "same instant": the two commands wait in line and run one after the other, 10 → 11 → 12 (Fig. 4).

The slide: "Redis is a single-threaded server, not designed to benefit from multiple CPU cores. Several Redis instances can be launched to scale out on several cores." And the consequence, one bullet later: "All operations are atomic (no two commands can run at the same time)."

Single-threaded, so atomic, with no lock anywhere: a lock exists to keep two threads off the same data, and here there is only one thread. Two clients that send INCR at once always count twice; an LPUSH never meets a half-built list.

One thread sounds slow. It is fast for four reasons:

• The data is in memory: no disk sits on the path of a request, unless you make every write wait for one (the dial of p. 349) — the race of section 1.
• The steps are short: "It executes most commands in O(1) complexity and with minimal lines of code" (p. 352).
• Nothing waits for anything else: no locks to take, no switching between threads.
• One thread serves thousands of connections: it watches all of them at once and serves whichever has a command ready (an event loop; background).

Kleppmann adds a subtler reason in Designing Data-Intensive Applications (background): "the performance advantage of in-memory databases is not due to the fact that they don't need to read from disk … Rather, they can be faster because they can avoid the overheads of encoding in-memory data structures in a form that can be written to disk." A Redis list is a list in memory, not a page format to translate back and forth.

The design has a price. While one command runs, every other client waits, so a command over a huge value — all the members of a set with a million entries — holds up everybody; "most commands in O(1)" is what keeps the queue moving. And one thread uses one core: to use eight cores you run eight instances, each with part of the keys — the seed of partitioning (lesson 19).

Page 353 draws the whole server on one slide, and it doubles as the map of this lesson and the next two (Fig. 5).

Read it as a table of contents. Left, the data structures: the next section, then the commands of lesson 18. Right, persistence: the "journal (text)" is the log of every write, the AOF, and the "snapshot (binary)" a picture of the whole dataset, the RDB file — the two mechanisms of p. 359. Below, the machinery for more than one server: replication keeps slaves as "exact copies of the master" (p. 359), Sentinel promotes a slave when the master dies, Cluster also spreads the keys over several masters (lesson 19).

One thread runs one command at a time: every command is atomic without a lock, and fast because each is a short step in memory.

Seven shapes for a value

Page 354, "Redis data types", lists what the value under a key can be: seven types, each with a picture, what it "Contains" and its "Read/write ability". Look at the pictures first (Fig. 6); the slide's text for each type is in the tabs below it.

Read the pictures in pairs. A list and a set both hold strings, but the list keeps the order of insertion and the repeats — C appears twice — while the set keeps neither: each string once, in no order. The exercise session gives the reason to pick a set: "SETS are useful as it is very quick to test the existence of a value, which is not as easy when it comes to lists" (p. 1600). A sorted set is a set whose members carry a number, the score, and stay in score order; A and C tie at 250 and are ordered by name (Redis breaks ties alphabetically; background). A hash is a small dictionary inside the value: its inner keys are called fields (HSET user:1 name John), so the Redis key names the object and the fields name its attributes.

The last two are built on the others. A geospatial index is "Sorted set implementation using geospatial information as the score": the position is packed into one number, so points near each other mostly get scores near each other and a radius search becomes a few ranges of scores (background) — TYPE on such a key answers zset. A HyperLogLog answers one question only, how many different items have been added, approximately and in at most 12 KB; it never gives an item back.

# p. 355: bar held 223; returns (integer) 1223
INCRBY bar 1000

# p. 357: returns (integer) 1, the number of fields added to user:1
HSET user:1 name John

# p. 357: returns (integer) 1, the new length of the list jobs
RPUSH jobs "foo"

# p. 358: returns (integer) 2, the number of new members
SADD users "John" "Peter"

# p. 358: the score comes before the member; returns (integer) 3
ZADD scores 50 "Peter" 200 "Charles" 1000 "Mary"

# the point of p. 354, longitude first; returns (integer) 1
GEOADD places -103.55328 20.63373 "Value"

# returns (integer) 1: the structure changed
PFADD visitors "u17" "u03" "u17"

# returns (integer) 2: about two different visitors
PFCOUNT visitors

The slide's seven are the classic types. Newer versions add Streams (since Redis 5.0, 2018), a log of messages for queues, and modules such as JSON — background, not on the slides. Choosing a type is choosing which commands you get for free: ask what the question needs — order, uniqueness, a score, named fields, a position, a count of different things — and the type follows. Try it on eight cases.

Pick the type by the question you will ask: order and repeats, a list; uniqueness, a set; order by a number, a sorted set; named fields, a hash; one value or a counter, a string; a position, a geospatial index; how many different, a HyperLogLog.

The puzzle, answered

Back to the two choices of 2009 that sounded backwards. A database that answers only "what is under this key?" is the fix when a relational one is too slow, because that question costs one step in memory whatever the size of the data, with nothing to parse, plan or join — the flat line of the race. And Redis gives back much of what a plain key-value store loses: the value is a data structure, so a push, an increment or a membership test is still one command on one key.

One thread needs no lock because it cannot race with itself: commands run one after another, each atomic. It keeps up because every step is short and in memory, and when one core is not enough you start another instance. The price is printed on p. 349: the data must fit in memory, and the safer you make it on disk, the slower it gets.

The course introduction says that each category of systems "is covered along 5 dimensions": data model, "(declarative vs. imperative) query languages", data distribution, non-functional aspects and architectural solutions. A theory question on the features of Redis fits on that grid: