Glossary

Plain-English definitions of the terms used across the simulators — grows as new topics land.

Amdahl's law: Amdahl's law: the speedup from more cores is capped by the part of the work that can't be parallelized. If 10% is serial, even infinite cores cap you at 10× — and uneven splits leave cores idle well before that.
Availability: Whether the system can still respond to requests, even during failures. Often traded off against consistency when the network splits (partition).
Big-O notation: Big-O notation describes how an operation's cost grows as the input grows. It ignores constants and focuses on the shape: does doubling the data double the work, or barely change it?
Block index: A small in-memory map: 'the block starting at key X lives at byte offset Y'. It lets a read jump straight to the right block instead of scanning the file.
Blocking I/O: When a task waits on I/O (disk, network) and holds onto its core while doing nothing useful. Async/non-blocking I/O instead yields the core so other ready tasks can run — the core stays busy.
Bloom filter: A compact bit array that answers 'is this key DEFINITELY not here?' in memory. If it says no, we skip reading the file entirely. It can say 'maybe' wrongly (a false positive) but never misses a key that exists.
Byte offset: A byte offset is the distance (in bytes) from the start of the file. Offset 0 is the very first byte; a section at offset 48 starts 48 bytes in.
Compaction: Background merge of SSTables: combines overlapping tables, keeps only the newest value per key, and drops tombstoned data at the bottom level. This reclaims space and speeds up reads.
Concurrency: Dealing with many tasks over the same period by interleaving them — switching between them so they all make progress. On a single core only one runs at any instant; they take turns. Concurrency is a structure for managing work, not a guarantee that work runs simultaneously.
Consensus: Getting a group of machines to agree on a single value despite failures and message delays. Hard problem; Raft and Paxos are consensus algorithms.
Consistency: Whether all replicas show the same data at the same time. Strong consistency = every read sees the latest write; weaker models trade that for speed/availability.
Constant time — O(1): O(1), 'constant time': the operation takes the same time no matter how big the data is. A hash-table lookup is O(1) — finding 1 key among a billion costs the same as among ten.
Context switch: Saving one task's state and loading another's so a core can switch between them. It's what makes interleaving possible — and it isn't free; too many switches waste time on bookkeeping instead of work.
Core: An independent processor that can execute one stream of instructions at a time. N cores can run N tasks truly simultaneously; a single core can only interleave.
Data block: Records are grouped into fixed-size blocks (pages). The engine reads one whole block at a time from disk, not one record.
Disk total: Total bytes across ALL files on disk — the WAL plus every SSTable. This is larger than any single SSTable, and briefly includes the WAL before it's truncated after a flush.
Doubly-linked list: A linked list where each node points to both the next AND previous node. This lets you remove any node in O(1) once you have it — the trick behind an O(1) LRU cache.
Durability: A guarantee that once a write is acknowledged, it survives crashes — usually by writing to disk (a WAL) before confirming. The 'D' in ACID.
False-positive probability: False-positive probability: the chance the filter says 'maybe present' for a key that was never added. It rises as the filter fills up; you lower it by adding more bits per key. Formula: (1 − e^(−k·n/m))^k, for k hashes, n keys, m bits.
Fill ratio: Fraction of the bit array that is set to 1. Bloom filters only ever set bits (never clear them), so this climbs with every ADD. Around 50% full is the sweet spot for the optimal hash count.
Hash table: A structure that stores key→value pairs and finds any key in O(1) by hashing the key to a slot. The workhorse behind caches, indexes, and dictionaries.
Hostname: A human-readable name for a machine, like example.com. It must be translated to an IP address (via DNS) before a connection can be made.
IP address: IP address: the numeric address of a machine on a network, like 93.184.216.34. Computers route messages by IP, not by human-readable names.
Latency: How long one request takes to get a response — the delay. Measured in milliseconds. Lower is better. Distinct from throughput.
Leader: In a replicated cluster, the one node that accepts writes and tells the others what to do. If it dies, the cluster elects a new leader (see Raft).
Level (LSM): SSTables are organized into levels. L0 holds freshly-flushed tables (key ranges can overlap). Deeper levels (L1, L2…) are larger, sorted, and non-overlapping. Reads check newer levels first.
Linear time — O(n): O(n), 'linear time': the work grows in step with the data — twice the data, twice the work. Scanning every item in a list is O(n).
Linked list: A chain of nodes where each node points to the next. Inserting or removing a node is cheap (just repoint neighbors) but finding the Nth item means walking the chain.
Little's Law: Little's Law: L = λ·W. The average number of items in a system (L) equals the arrival rate (λ) times the average time each spends inside (W). It ties concurrency, throughput, and latency together with no assumptions about the workload.
Logarithmic time — O(log n): O(log n), 'logarithmic time': the work grows very slowly — doubling the data adds just one more step. Binary search and balanced trees are O(log n).
Memtable: An in-memory sorted table holding the newest writes. Fast to update. When it fills past its threshold, it's frozen and written to disk as an SSTable.
Network partition: A network split: some machines can't talk to others, though each side is still alive. Systems must choose how to behave — stay consistent or stay available.
Nines (availability): Availability expressed as a count of leading 9s: 'three nines' = 99.9% uptime. Each extra nine cuts allowed downtime ~10×: 99.9% ≈ 8.8 h/year, 99.99% ≈ 53 min/year, 99.999% ≈ 5 min/year.
No false negatives: A Bloom filter never has false negatives: if a key was added, every one of its k bits is 1, so a query for it always returns 'maybe present'. It can only be wrong in the other direction — a false positive.
Node: One element of a structure (list, tree, graph) — it holds a value plus links to other nodes. Also used to mean one machine in a distributed cluster.
Packet: A small chunk of data sent across a network. A big message is split into many packets, each routed independently and reassembled at the other end.
Parallelism: Actually running tasks at the same instant, which requires multiple cores (or machines). Parallelism needs concurrency to organize the work, but concurrency does not need parallelism — one core can be concurrent without ever being parallel.
Port: A number (0–65535) that identifies which program on a machine should receive a message. Web servers usually listen on port 80 (HTTP) or 443 (HTTPS).
Probe: One of the k hash functions maps the key to a bit position. ADD sets all k bits; QUERY checks them — a single 0 bit is enough to prove the key is absent.
Quorum: A majority agreement. With N replicas, requiring a quorum (more than half) to confirm a write or read guarantees any two quorums overlap — so they can't disagree.
Read amplification: Read amplification: how many data blocks a single GET had to read. A key in a deep level (or a missing key) may touch several SSTables — bloom filters keep this low.
Replica: A copy of the data kept on another machine. Replicas give you fault tolerance (one dies, others serve) and let reads spread across machines.
Round-trip: One full there-and-back trip: request out, response back. Each network round-trip adds latency, so cutting round-trips is a common optimization.
Scheduler: The component that decides which ready task runs on which core next. Round-robin gives each task a fixed turn (quantum) in rotation so no task is starved.
SLA: Service Level Agreement: a contractual promise about a metric (e.g. 99.9% availability) with penalties if missed. The externally-committed number.
SLO: Service Level Objective: an internal target you operate to (often stricter than the SLA) so you have headroom before breaching the contract.
SSTable: Sorted String Table: an immutable file of key→value records sorted by key. Once written it's never modified — only merged into a new one during compaction.
SSTable footer: A fixed-size 20-byte trailer at the very end of the file. It stores four numbers — the byte offset and length of the index section, and of the bloom section — plus a 4-byte magic number ('LSMT') to verify the file. A reader opens the file by reading these last 20 bytes first, which tell it where everything else lives.
Throughput: How many requests a system handles per unit of time (e.g. 10,000 requests/second). A system can have high throughput but still high latency per request.
Tombstone: A delete doesn't erase data — it writes a 'tombstone' marker that shadows older copies in lower levels. The data is actually removed later, during compaction.
Tree: A structure of nodes branching from a root, each node having children. Lookups follow one path from the root, so balanced trees search in O(log n).
Trie (prefix tree): Prefix tree: strings that share a prefix share the same path of nodes. A prefix lookup costs only as much as the prefix length — not the dictionary size — which is what makes it the structure behind autocomplete.
TTL (Time To Live): Time To Live: how long a cached answer stays valid before it must be looked up again. A DNS record with TTL 300 may be reused for 300 seconds.
Utilization: The fraction of available core-time actually spent doing useful work. Idle or blocked cores drag it down; low utilization is why adding cores often fails to speed things up proportionally.
Write amplification: Write amplification: total bytes written to disk ÷ bytes you actually wrote. Compaction re-writes data, so this is >1. The price LSM trees pay for fast writes.
Write-Ahead Log (WAL): Write-Ahead Log: every write is appended here on disk first. If the server crashes before the in-memory data is saved, it's replayed from this log so nothing is lost. It's cleared once the memtable it protects is safely flushed to an SSTable.