Course · 11

Where do files live, and how do we find things fast?

This page covers three jobs. Keeping big files safe and cheap. Finding words inside millions of documents. Answering big "sum up everything" questions. Every number here was checked against official docs on 2026-10-25.

—Words you need

Each hard word once, in plain words glossary

01Block, file and object storage

Three ways to keep bytes, and when each one wins core

Block storage is a raw disk. It only knows numbered blocks. Your operating system puts a file system on top. It is fast and low-level. Databases love it.

File storage is a shared folder. Many servers mount it at once over the network and see the same files and folders.

Object storage stores whole files by name. You talk to it with web calls (PUT, GET, DELETE). There are no real folders and no "edit byte 500".

Database files → block. Files many servers must open by path → file. Everything users upload → object.

Sources: What is Amazon EBS · EBS Multi-Attach · What is Amazon EFS · checked 2026-10-25

02The object storage model

Bucket, key, metadata, whole-object writes, lifecycle tiers core

A bucket is the top container. Inside it, each object has a key, which is its full name, for example photos/puppy.jpg. The slash is just a character. "Folders" are only name prefixes.

An object is the bytes plus metadata: name-value pairs like Content-Type or your own x-amz-meta-* fields (user metadata is limited to 2 KB).

Objects are replaced, not edited. To change one byte you upload the whole object again. Turn on versioning to keep old copies.

Lifecycle tiers: pay less for cold data

A lifecycle rule moves objects to cheaper classes as they age, or deletes them. Cheaper classes have a catch: a minimum storage time you pay for even if you delete early, plus retrieval fees.

{ "Rules": [{
    "ID": "logs-tiering", "Status": "Enabled",
    "Filter": { "Prefix": "logs/" },
    "Transitions": [
      { "Days": 30,  "StorageClass": "STANDARD_IA" },
      { "Days": 90,  "StorageClass": "GLACIER" } ],
    "Expiration": { "Days": 365 } }] }

Object stores are simple on purpose: whole-object writes, one key at a time. Use lifecycle rules, but check minimum days before moving small or short-lived files.

Sources: What is Amazon S3 · S3 storage classes · S3 Lifecycle · Uploading objects (2 KB user metadata) · checked 2026-10-25

03Big uploads: multipart and pre-signed URLs

Let the client send bytes straight to storage interview favourite

Why not upload through your API? Every byte would pass through your servers. That costs bandwidth, memory and time, and it ties up a server for minutes.

A pre-signed URL fixes this. Your API signs a URL with its own AWS credentials. The URL says "PUT this one key, until this time". The browser uploads straight to S3. Then the client, or an S3 event, tells your API the upload is done, and the API saves the row (step 4).

Multipart upload splits one big file into parts. Parts go up in parallel and in any order. A failed part is retried alone. S3 joins the parts at the end.

url = s3.generate_presigned_url(
    "put_object",
    Params={"Bucket": "media", "Key": f"u/{user_id}/{uuid4()}.mp4",
            "ContentType": "video/mp4"},
    ExpiresIn=900)          # seconds; keep it short

Your API grants permission; storage moves bytes. Use multipart for anything above about 100 MB, and set a lifecycle rule to clean up unfinished multipart uploads.

Sources: S3 multipart limits · Uploading objects · Multipart upload overview · Pre-signed URLs · checked 2026-10-25

04Storing large files: chunks, dedup, and the metadata split

How Dropbox-style systems avoid sending the same bytes twice deep dive

Chunking means cutting a file into blocks. If you edit one page of a 1 GB file, only the changed blocks need to go up again.

Deduplication means storing each unique block once. The block's name is its content hash. The same bytes always give the same hash, so the server can say "I already have that one".

A file then becomes a list of block hashes. That list lives in a database. The bytes live in the blob store. This is the classic metadata + blob split.

Name blocks by their hash, keep a block list per file in SQL, and keep the bytes in object storage.

Sources: Dropbox tech blog · Muthitacharoen et al., A Low-bandwidth Network File System, SOSP 2001 · Harnik, Pinkas, Shulman-Peleg, Side Channels in Cloud Services, IEEE S&P 2010

05From LIKE to the inverted index

Why the database scan fails, and what search engines do instead core

WHERE body LIKE '%cat%' has a wildcard at the front. A normal B-tree index is sorted from the first letter, so it cannot jump to "anything containing cat". The database reads every row. With 100 million rows, that is every query, every time.

It also gets the meaning wrong. It matches "concatenate". It misses "Cats". It cannot rank the best result first.

Search for cat: look up one entry, get docs 1 and 2. Search cat sat: take both lists and keep the docs in both (an intersection). Each list is sorted by doc id, so the merge is fast.

Analyzers: the same cleaning at write time and at query time

An analyzer has three parts, run in order: character filters (for example, strip HTML), exactly one tokenizer (split text into words), and token filters (lowercase, drop stop words like "the", add synonyms, cut words to their stem so "running" matches "run").

POST _analyze
{ "tokenizer": "standard", "filter": ["lowercase", "stop"],
  "text": "The Cat sat" }
→ tokens: "cat", "sat"   ("the" removed by the stop filter)

Use the database for exact lookups. Use an inverted index when users type words and expect ranked results.

Sources: Elastic: analyzer anatomy · Elastic: near real-time search · PostgreSQL: pg_trgm

06Ranking: TF-IDF and BM25

Which matching document comes first core

Finding matches is half the job. Ranking them is the other half. Two ideas drive it:

• Term frequency (TF): a word that appears often in a document makes it more relevant.
• Inverse document frequency (IDF): a rare word ("kubernetes") matters more than a common one ("the").

TF-IDF multiplies the two. BM25 fixes two of its flaws. First, TF saturates: the 50th "cat" adds almost nothing. Second, it normalises length: a long document is not rewarded just for having more words.

score(D, Q) = Σ over q in Q of  IDF(q) · f(q,D)·(k1 + 1)
                                 ─────────────────────────────────
                                 f(q,D) + k1·(1 − b + b·|D| / avgdl)
f = times q appears in D · |D| = length of D · avgdl = average length
k1 = how fast TF saturates (default 1.2) · b = how much length matters (default 0.75)

In an interview, say: "BM25 = TF-IDF with saturation and length normalisation; it is the default in Lucene-based engines."

Sources: Elastic similarity docs · Robertson & Zaragoza 2009

07Inside Elasticsearch / OpenSearch

Index, shards, replicas, and the 1-second refresh deep dive

An index is like a table. It is split into primary shards; each shard is a full Lucene index. Each primary has replica copies on other nodes. Replicas give safety and extra read capacity.

A search goes to every shard (scatter). Each shard returns its top hits. The coordinating node merges them (gather). More shards → more parallel work, but also more overhead per query.

Near-real-time: why a new document is not instantly searchable

A write goes to a memory buffer and the translog (a safety log on disk). It becomes searchable only after a refresh writes a new segment and opens it.

Search is "near real-time": about one second behind. Pick primary shard count early, by expected data size.

Sources: Elastic: index settings · Elastic: size your shards · OpenSearch index settings · checked 2026-10-25

08Keeping search in sync with the database

The dual-write trap, and change data capture interview favourite

Dual write means your app writes to the database and then to the search index. It looks simple. It breaks in quiet ways:

• The DB write succeeds, then the app crashes before the search write. Search is now missing data, forever.
• Two updates race. The DB ends with version B, but search ends with version A.
• Search is down. Do you fail the user's save? Retry? Where do you keep the retry?

Change data capture (CDC) avoids this. The app writes only to the database. A reader tails the database's own log of committed changes and turns each change into an event. A consumer applies the events to search, in commit order.

The transactional outbox is the app-level cousin: write the event into an outbox table in the same transaction as the business change, then a relay publishes it.

Never make search the source of truth. Feed it from the database's log, and keep a "rebuild index from DB" job ready.

Sources: Debezium docs · microservices.io: Transactional outbox

09Typeahead and autocomplete

Tries, top-k at each node, and caching interview favourite

A trie (say "try") is a tree of letters. Walking down c → a takes as many steps as the prefix is long, no matter how many words exist.

The naive way then walks every word under "ca" and sorts by popularity. That is slow for short prefixes like "a". The fix: store the top-k completions inside each node. A lookup is then "walk the prefix, return the list".

• Build the trie offline (for example, hourly) from query logs. Swap in the new one. Writes never block reads.
• Cache hot prefixes at the edge or in Redis. Short prefixes are few and very hot.
• Shard by prefix when it outgrows one machine.
• On the client: wait about 100–300 ms after typing stops (debounce) before calling. This range is common practice, not from a spec.

Typeahead = trie (or FST) + top-k per node + offline rebuild + heavy caching.

Sources: Elastic blog · Elastic suggesters docs

10Warehouses, column storage and data lakes

Why "sum all sales by month" needs a different database core

OLTP (online transaction processing) is your app's database: many tiny reads and writes of whole rows. "Get order 42". "Insert one payment".

OLAP (online analytical processing) is reporting: few huge queries that read millions of rows but only a few columns. "Total revenue by country by month".

Data lake vs data warehouse

A data warehouse holds cleaned data in fixed tables. The shape is set before loading (schema-on-write). A data lake keeps raw files of any kind, often in S3, and applies a shape only when you read (schema-on-read). Many teams now use both: raw lake → cleaned warehouse tables.

Never run heavy reports on the OLTP primary. Copy data (often with CDC) into a column store.

Sources: Redshift columnar storage · AWS: What is a data lake

11Time-series databases

Metrics, sensor data, prices: append-only, by time briefly

Time-series data is a stream of (timestamp, value, labels) points. New points arrive all the time. Old points never change. Queries ask for ranges: "CPU of host-7, last 6 hours, per minute".

A time-series database (Prometheus, InfluxDB, TimescaleDB) is built for that shape:

• Compression: store the change between neighbour points, not the full value. Close numbers compress very well.
• Time blocks: data is cut into blocks by time, so "drop data older than 15 days" means deleting whole blocks.
• Downsampling: keep per-second data for days, per-hour data for years.

Metrics in a normal SQL table work at small scale. At millions of points per second, use a time-series store.

Sources: Prometheus storage docs · Pelkonen et al., Gorilla, VLDB 2015

12Bloom filters

"Definitely not here" in a few bits interview favourite

A Bloom filter is a row of bits, all 0 at the start. To add an item, hash it with k different hash functions and set those k bits to 1.

To check an item, look at its k bits. Any bit is 0 → the item is surely not in the set. All bits are 1 → it is probably in the set.

Why "probably"? Other items may have set those same bits by chance. That is a false positive. There are no false negatives. You also cannot delete from a plain Bloom filter, because a bit may be shared.

false-positive rate  p ≈ (1 − e^(−k·n/m))^k
best number of hashes k = (m/n)·ln 2
n = items added · m = bits · about 9.6 bits per item gives p ≈ 1%

Use a Bloom filter in front of a slow lookup when most answers are "no": disk files, caches, "is this username taken?" pre-checks.

Sources: Cassandra docs · Wikipedia: Bloom filter · Bloom 1970, Space/time trade-offs in hash coding

—When to use what

Situation → pick → why decision table

—Common mistakes

Traps that cost marks in interviews and money in production traps

—Interview questions

20 questions, easy to design-level. Try first, then open the answer practice

—Cheat sheet

Numbers and facts to remember memorise

—Sources

All checked on 2026-10-25 official docs

—Where next

Keep going through the course navigation