SD3.3 · LESSON 3 OF 6

Key-value and access patterns

Choose representations and storage boundaries from access patterns, ownership and retention requirements.

THE IDEA

Key-value and access patterns

A key-value store is excellent when callers know the key: one lookup. A question like "which user has this email?" is a different access pattern: without help it scans every entry (100,000 of them). A secondary index answers it with one lookup, at the price of an extra write per record and extra memory (1.6 MB at 16 bytes per user). Design the store around the queries you must answer.

entries100,000secondary indexes0bytes per index entry16

get by key: 1 lookup find by email, no index: scan 100,000 entries find by email, with an index: 1 index lookup (no index yet: the scan applies) writes per new record: 1 + 0 index = 1 index memory: 100,000 × 16 B × 0 = 0 bytes

A key-value store is fast for the access pattern it was designed for: known keys. Other patterns need an index or a second representation, which costs extra writes and storage.

Add indexes and change the number of entries.

Predict first. Can an arbitrary key-value lookup efficiently answer every multi-field query?

Chapter context

A data model describes the facts a system owns and the relationships it must preserve. Storage choices should follow how those facts are queried, updated and retained, rather than a blanket preference for one database category.

TRY IT YOURSELF

Part 1. Do it hands-on

Cost the lookups by hand, then build a key-value store with a maintained secondary index.

entries100,000secondary indexes0bytes per index entry16

A key-value store is fast for the access pattern it was designed for: known keys. Other patterns need an index or a second representation, which costs extra writes and storage.

entries scanned without an index (100k users) index lookups with one index bytes at 16 B/user writes per new user with one index any query is efficient on a plain KV? (yes/no)

To do: A key-value store holds 100,000 users keyed by id. Finding the user with a given email (no secondary index) means scanning how many entries in the worst case?
To do: With a secondary index from email to id, how many index lookups find the user?
To do: The index stores 16 bytes per user. Bytes for 100,000 users?
To do: Each new user is written once to the store and once to the email index. Writes per new user?
To do: Can an arbitrary key-value lookup efficiently answer every multi-field query? Type yes or no

Part 2. Do it in code

class KV with self.data (dict key → record) and self.indexes (dict field → {value: [keys]}).
put(key, record): store the record, and update every index that exists (remove the old entry if the key already existed). Return the number of writes performed (1 + number of indexes).
get(key): the record or None (one lookup).
scan(pred): return (matching keys sorted, scanned) where scanned is the number of entries examined (all of them).
create_index(field): build an index over the existing data; subsequent puts keep it current.
find(field, value): if an index exists on the field return (sorted keys, 1) — one index lookup; otherwise fall back to scan and return (keys, scanned).
index_bytes(n_entries, bytes_per_entry): n_entries × bytes_per_entry.

class KV:
    def __init__(self):
        self.data = {}
        self.indexes = {}

    def put(self, key, record):
        pass

    def get(self, key):
        pass

    def scan(self, pred):
        pass

    def create_index(self, field):
        pass

    def find(self, field, value):
        pass

def index_bytes(n_entries, bytes_per_entry):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can an arbitrary key-value lookup efficiently answer every multi-field query?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

A simple retained-payload estimate is

M=w\,s\,d\,r,

where w is writes/day, s payload bytes/write, d retained days and r full-copy count. Add indexes, metadata, compaction headroom and backups separately; replication schemes may store more than exactly r payload copies.

Worked example

Two million records per day at 500 bytes each produce one decimal GB/day of raw payload. Thirty days retained across three full copies require 2,000,000×500×30×3=90,000,000,000 bytes, or 90 decimal GB before other storage. Compressibility and index size are separate measured factors.

Reference code

The following example uses the Python standard library and does not call a remote service.

daily,size,days,copies=2_000_000,500,30,3
assert daily*size == 1_000_000_000
retained=daily*size*days*copies
assert retained == 90_000_000_000
assert retained/1e9 == 90

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

NoSQL is not a single consistency or query model. Denormalization creates a maintenance responsibility. Payload estimates must not silently stand in for provisioned disk requirements.