Glossary

Each entry starts with the plain words our pages use. The line under it gives the name experts use, if there is one, so you can search for it elsewhere. The links show the challenges where the word matters.

Add-wins

When one copy adds an item and another copy removes it at the same time, the add stays after a merge. The remove only cancels the adds it had already seen.

At least once

A promise that every message or job is done one time or more, never zero times. Your code must be fine when the same item comes back a second time.

Also called: at-least-once delivery

Backoff

Waiting a bit longer after each failed try before you try again. The wait often doubles each time, up to a limit.

Also called: exponential backoff

Backpressure

A busy part of a system makes new work wait, so it does not take on more than it can handle.

Bit mask

A number used to keep only some bits of another number. With a size that is a power of two, it can replace the slower % step.

Bloom filter

A row of bits that answers "could this item be here?". It may say yes by mistake, but it never says no for an item that was added.

Buffer

A piece of memory that holds bytes or values for a short time, until the code is ready to use them.

Burst

Many requests that arrive close together. A limiter may allow a short burst and still keep the long-term rate low.

Cache

A small, fast store that keeps values you may need again soon. When it is full, it must choose a value to remove.

Cap

The biggest value a number is allowed to reach. A wait that keeps doubling stops growing at its cap.

Check-then-act

Code that first looks at a value and then changes something based on what it saw. When many callers run it at once, another caller can change the value in between, so the change is made on old news.

Also called: check-then-act race, time of check to time of use

Circuit breaker

A guard in front of a service. After enough failures in a row, it stops calls for a while, then lets one test call through.

Collision

Two different keys that land on the same slot or the same number. The code must still keep both keys apart.

Committed

A change is committed when its writer says it is final. Before that, other readers must not see it.

Also called: commit

Connection pool

A small group of open network connections that callers borrow and give back, so the program does not open a new one for every request.

Credit

In this challenge, the side of a money record where money arrives in an account. This is a simplified convention. Real accounting uses the word in a more complex way. The side where money leaves is called a debit.

Data that merges

Data kept as copies on many machines, built so that merging any copies, in any order and any number of times, gives the same result.

Also called: CRDT, conflict-free replicated data type

Deadlock

Two parts of a program each wait for something the other one holds, so both wait forever.

Debit

In this challenge, the side of a money record where money leaves an account. This is a simplified convention. Real accounting uses the word in a more complex way. The side where money arrives is called a credit.

Deleted marker

A small note that says "something was removed here". It lets a search go past a removed key, or lets a copy remember what it removed.

Also called: tombstone

Dirty read

Reading a value that another transaction wrote but has not committed yet. That value may still be cancelled.

Doubly linked list

A chain of items where each item points to the one before it and the one after it. You can remove an item from the middle without searching for it.

Drift

A small delay that adds up over time, so each run of a schedule happens a little later than planned.

Eviction

Removing a stored item to make room for a new one. A cache does this when it is full.

False positive

A yes answer that is wrong. A Bloom filter can give one, because other items may have set the same bits.

Fixed window

A limit that counts requests and resets to zero at fixed times, such as each new second. A caller can send two bursts around one reset.

Hash function

A function that turns a key into a number that looks random. The same key always gives the same number.

Also called: hash

Hash map

A table that stores a value for each key and finds it quickly, by turning the key into a slot number.

How full the table is

The number of used slots compared to the total number of slots. A fuller table makes searches longer.

Also called: load factor

Idempotency key

A name the caller gives to one piece of work. Every repeat request with that name gets the same saved result, and the work runs only once.

Jitter

A small random change added to a wait or a time. It spreads out retries, and it also describes the small timing noise of a busy machine.

Least frequently used

A rule for a full cache: remove the key that was used the fewest times.

Also called: LFU

Least recently used

A rule for a full cache: remove the key that has gone longest without use.

Also called: LRU

Lock

A tool that lets only one part of a program use some data at a time. Others wait until it is free.

Also called: mutex

Leak

Something taken and never given back, like a connection opened and never closed, or a count raised and never lowered.

Lost update

Two callers read the same old value, each changes it, and each writes it back. The second write covers the first one, so one of the two changes is gone.

Message log

A list of messages where each new message goes at the end and old messages never change. Many readers can read it at their own pace.

Min heap

A tree kept in an array where each parent is no bigger than its children, so the smallest value is always at the top.

Also called: priority queue

Next slot search

When a slot is taken, check the next slot, then the one after it, until you find a free slot or the key you want.

Also called: linear probing

O(1)

A cost that stays about the same, however much data you have.

Also called: constant time

Old versions kept

A database keeps several versions of each value, so readers see a fixed view and never wait for writers.

Also called: MVCC, multi-version concurrency control

Overflow

A number grows past the biggest value its type can hold and wraps to a wrong value, often a negative one.

Peer

The program at the other end of a connection.

Position in the log

The number of a message in a log. A reader saves the position of the next message, so it can carry on after a restart.

Also called: offset

Power of two

A number you get by doubling 1 again and again: 1, 2, 4, 8, 16 and so on. Some fast tricks only work with these sizes.

Prefix

The start of a word. "ca" is a prefix of "car" and "cat".

Race condition

A bug where the result depends on which of two callers runs first. Both check, then both act on the same old value.

Also called: race

Ring buffer

An array with a fixed size where the slot after the last one is the first one again. It keeps values in arrival order without moving them.

Same view for the whole transaction

Each transaction sees the data as it was when it began, whatever other transactions do later.

Also called: snapshot isolation, snapshot

Sift-up and sift-down

The two moves that fix a heap. Sift-up moves a value toward the top, and sift-down moves it toward the bottom, until its parent is no bigger than it.

Also called: sift-up, sift-down

Sliding log

A way to limit requests that keeps the times of recent requests for each caller and counts how many fall inside the latest stretch of time.

Stampede

Many things move or happen at once, when only a few needed to. A server joining should not move almost every key.

State machine

A design with a short list of named states. Each event moves it from one state to the next and may trigger some actions.

Test call

One careful call let through to check if a broken service works again, before all traffic goes back to it.

Also called: probe

Thundering herd

Many clients that all retry at the same moment and hit a struggling service with a new wave of calls.

Time to live

How long a saved result stays fresh. After that time, it is treated as gone.

Also called: TTL, time-to-live

Token bucket

A rate limit design. Each caller has a bucket of allowance that refills slowly, and each request spends one unit.

Transaction

A group of reads and writes that a database treats as one piece of work. It either commits as a whole or is cancelled.

Tree of letters

A tree that stores words one letter per step, so words that start the same way share their first steps.

Also called: trie

Virtual nodes

Extra points on the circle for each server, so each server owns many small pieces instead of one big one.

Visibility timeout

How long a queue waits for a "done" message after it hands out a job. If no "done" arrives in time, the job goes back on the queue.

Wrap around

Going past the end of something and starting again at the beginning, like a clock going from 12 back to 1.