Overall Engineering Clarity — Data, Distributed Systems and AI (Deep Dive)

Reading contract: this long-form companion retains the original mechanisms, diagrams and complete quiz bank. Spark examples target 3.5.7, Iceberg 1.9.2, PostgreSQL 16, and Java notes name their runtime versions; service APIs below are reference material, not a deployment recipe. Version-specific corrections are made in place; full worked self-check/final-exam answers and bounded local tests follow. Service procedures are explicitly unexecuted.

Overall Engineering Clarity — Data, Distributed Systems and AI

A slow query, a half-visible table update, and an AI answer drawn from the wrong tenant look like different incidents. Each exposes a boundary the system must make explicit: where work moves, when data becomes visible, and which evidence a request is allowed to use. This companion connects those boundaries through a governed data platform, from distributed computation to storage, indexes, and AI services.

Use the diagrams to follow one query or update, then use the decision tables and Q&A to challenge the design. The recurring shape is mental model → flow / diagram → internals → decision tables → code → Q&A with reasoning; the later quiz bank is a separate retrieval-practice pass, not another step in the platform’s runtime flow.

How to read each concept — the "Why → How → Trade-off" framework

Most engineers can recite what a thing is. The clarity gap shows up when you ask why it exists and what breaks. Use this template for every concept:

What it is        →  one sentence definition
Why it exists     →  the problem before this solution
How it works      →  internals / mechanism
When to use       →  correct fit
When NOT to use   →  anti-patterns
Trade-offs        →  latency, cost, consistency, complexity
Failure modes     →  what bites you in production
Concrete example  →  code or architecture you can point at

Intuition shortcut. Every technology in this post solves one of three pains:

1. One machine isn't enough → distribution, partitioning, replication.
2. Cheap object storage isn't transactional → lakehouse formats, commit protocols.
3. Models don't know your private/fresh data, and they hallucinate → embeddings, retrieval, agents, evals.

Default for every answer: problem first, mechanism second, trade-off third, failure mode fourth, example fifth.

Part I — Distributed Compute

This part follows query planning into physical work and then uses task evidence to choose a tuning experiment. Keep plan shape, partition data volume and process/container memory distinct: a shuffle change cannot repair every scan or native-memory bottleneck.

1. Apache Spark — Internals That Actually Matter

1.1 Mental model

Spark is a distributed query engine. The single sentence to remember:

Ask where data moves and where time is spent before buying more CPU.

Shuffle moves rows so matching keys meet, and is a frequent bottleneck. Scan I/O, skew, CPU-heavy expressions, Python conversion, scheduling and output can instead dominate; inspect the physical plan and task metrics before choosing a fix.

1.2 Execution flow — what really happens when you call an action

Imagine grouping a day’s playback events by user. The action triggers work, but rows for one user may be scattered across input partitions. Follow the diagram to the shuffle and then into the reducer tasks: that is where local scans become a cross-machine coordination problem. The scheduler and executor boxes explain who arranges the work; the shuffle boundary explains why more CPU alone may not shorten it.

Layers of work:

• Application → jobs triggered by actions → stages at shuffle dependencies → tasks for stage partitions. One action can generate multiple jobs, especially in SQL/AQE; this hierarchy is not a one-to-one action/job guarantee.
• DAG Scheduler decides stages; Task Scheduler dispatches tasks; BlockManager stores intermediate data on each executor.
• Narrow transformations (map, filter, select, mapPartitions, union) keep partitions local.
• Wide dependencies require cross-partition work. groupBy, distinct and repartitioning commonly shuffle; joins depend on the physical strategy and existing partitioning (a broadcast join need not shuffle the large input).
• Catalyst rewrites your logical plan; Tungsten-era execution improvements include binary representation and whole-stage code generation; AQE (Adaptive Query Execution) flips plans at runtime once it sees actual partition sizes.

1.3 Catalyst — the optimizer pipeline

The previous diagram describes execution; this one asks which work should be executed at all. If the playback query needs only yesterday’s rows and two columns, filtering and pruning before a shuffle can save more than tuning the shuffle itself. Follow the plan from named columns to physical operators, then use the rule table to identify which unnecessary work can disappear.

Key rules Catalyst applies (you should be able to name them):

1.4 Tungsten — what makes Spark fast on the CPU

• Whole-stage codegen fuses compatible physical operators into generated Java; unsupported operators create boundaries. JVM optimization can reduce dispatch overhead, but full-tree fusion or vectorization is not guaranteed.
• Binary row representation reduces per-object overhead; storage may be on-heap or explicitly configured off-heap. Tungsten does not mean all execution memory is off-heap.
• Columnar scans and batches can improve locality and reduce decoding work; generated row operators and columnar boundaries still coexist.

Opaque UDF semantics can limit optimization. Python execution adds serialization/process costs, while Scala/Java UDF and vectorized Python paths differ. Unrelated filters can still be pushed down; inspect the plan rather than claiming every UDF disables all codegen/pushdown.

1.5 AQE — Adaptive Query Execution

Three runtime optimizations that fire during query execution (default on since 3.2):

1. Coalesce shuffle partitions — small post-shuffle partitions are merged so reducers aren't underutilized.
2. Skew join handling — a heavily skewed partition is split into sub-partitions and the other side is replicated.
3. Switch join strategy — if a planned sort-merge join's input turns out small enough at runtime, AQE flips it to broadcast hash.

1.6 Why shuffle is expensive — the full picture

Costs that pile up:

• Encoding/serialization and copying; RDD serializers and SQL binary/shuffle paths differ.
• Disk spill if shuffle data exceeds memory.
• Network I/O between executors.
• Sorting (sort-based shuffle is the default).
• Reducer pressure — one slow reducer becomes a straggler.

Push-based shuffle in Spark 3.5.7: requires the supported external shuffle-service/YARN arrangement and shuffle mergers. Map output blocks can be merged to reduce small random fetches. It is not the Kubernetes shuffle-tracking feature, and this review claims no universal throughput win.

1.7 Memory model per executor

spark.executor.memory (heap)
  ├── reserved (300 MiB)
  ├── remaining heap (~40% of heap minus reserved at default fraction)
  └── unified region (~60% of heap minus reserved at default fraction)
        ├── execution (sort, join, agg, shuffle)
        └── storage   (cache, broadcast)
spark.executor.memoryOverhead   ← JVM/native overhead; Python if not separately limited
spark.memory.offHeap.size       ← separately configured execution off-heap
spark.executor.pyspark.memory   ← separate Python allowance when configured

OOM investigations include: too few partitions, skewed partitions, oversized cache, or memoryOverhead too small for PySpark workers / native libs.

1.8 The five things that make a Spark job slow

Treat the branches below as competing hypotheses, not a checklist of settings to apply together. If most tasks finish quickly and one runs much longer, investigate the straggler branch before increasing every executor’s memory. If all tasks scan large inputs, start with reads and pruning instead. The Spark UI sequence that follows supplies the evidence needed to choose a branch.

1.9 Spark UI — your diagnostic flow

Always inspect in this order:

1. SQL tab — physical plan + actual row counts. Spot accidental cartesians, wrong join strategy, missing pushdown.
2. Stages tab — input size, shuffle read/write, spill, task duration distribution. Median vs max ratio reveals skew.
3. Executors tab — GC time (a high fraction is a diagnostic signal, not a universal 10% threshold), failed tasks, memoryUsed.
4. Storage tab — persisted datasets, cached partitions and storage use; derive reuse/eviction behavior from the workload rather than assuming a universal cache-hit-ratio display.
5. Environment tab — confirm config actually loaded what you set.

1.10 Join strategy cheat sheet

1.11 Skew — recognize and fix

Symptoms (Spark UI): one task at 30 min while peers finish in 30 s; one partition's shuffle read is 50× the median; max task time ≫ median.

Why it happens: Hash partitioning sends every row with the same key to the same reducer. One hot key = one overloaded reducer.

Fixes, in order of cheapness:

1. Turn on AQE skew join (spark.sql.adaptive.skewJoin.enabled=true).
2. Pre-aggregate before the join (combine map-side).
3. Salt the hot key.

Salting code (manual, when AQE isn't enough):

from pyspark.sql import functions as F
 
N = 32  # salt fan-out
big = df_big.withColumn("salt", (F.rand() * N).cast("int"))
small = (df_small
         .crossJoin(spark.range(N).withColumnRenamed("id", "salt")))
joined = (big.join(small, ["key", "salt"])
            .drop("salt"))

For this inner equijoin, each left row gets one salt and the right side is replicated N times, preserving the original join multiplicity. This scatters work statistically, not necessarily across exactly N distinct physical reducers. It also replicates all right rows here, not just hot keys; restrict salting to measured hot keys where possible. Outer/semi/anti joins need separate proofs.

1.12 Coding patterns you should know cold

Top-K per group with a window:

from pyspark.sql import functions as F, Window
 
w = Window.partitionBy("category").orderBy(F.col("score").desc(), F.col("id").asc())
top3 = (df.withColumn("rk", F.row_number().over(w))
          .where("rk <= 3")
          .drop("rk"))

Dedupe — keep the latest record per key:

w = Window.partitionBy("id").orderBy(F.col("event_ts").desc(), F.col("version").desc())
latest = (df.withColumn("rk", F.row_number().over(w))
            .where("rk = 1")
            .drop("rk"))

Sessionization with watermark (Spark 3.5.7 reference, not executed):

A 15-minute session gap joins adjacent events; the 30-minute watermark delays state cleanup and bounds some late-data handling. It is not a guarantee that every later event is always discarded, and output mode/operator support matters.

sessions = (events
    .withWatermark("ts", "30 minutes")
    .groupBy(F.session_window("ts", "15 minutes"), "user_id")
    .agg(F.count("*").alias("hits")))

Per-column profile in one pass (governance use case):

agg_exprs = []
for c in df.columns:
    agg_exprs += [
        F.sum(F.col(c).isNull().cast("int")).alias(f"{c}_nulls"),
        F.approx_count_distinct(c).alias(f"{c}_ndv"),
    ]
profile = df.agg(*agg_exprs)   # one aggregate plan; inspect exchanges and sketch memory

Version-aware upsert into Iceberg (Spark extensions required; unexecuted reference):

Deduplicate updates to one row per key before MERGE. The table retains a monotone source version and tombstone; otherwise an older replay can overwrite or resurrect a newer row. The generic UPDATE/INSERT-star scaffold below is valid only for aligned schemas and prefiltered replay-safe source rows; it does not make arbitrary CDC idempotent.

MERGE INTO catalog.db.dim_customer t
USING updates u
ON t.cust_id = u.cust_id
WHEN MATCHED AND u.version > t.version THEN UPDATE SET *
WHEN NOT MATCHED THEN INSERT *;

1.13 Spark on Kubernetes — what's different

• Each executor is a pod; the driver pod creates them.
• Dynamic allocation + shuffle tracking (available since Spark 3.0) means you don't need an external shuffle service — executors are kept around if they hold shuffle data still in use.
• Select executor node pools with node selectors/affinity plus compatible taints/tolerations; spot pools for cost; non-spot pool for the driver.

1.14 Q&A with reasoning

Q1. Why is reduceByKey better than groupByKey().mapValues(_.sum)? Because reduceByKey performs a map-side combine before the shuffle. The reducer receives one partial aggregate per partition per key instead of every raw value. Less network, less spill, less reducer memory.

Q2. A task takes 30 min while peers finish in 30 s. What's happening? Possible data skew — one key may have many more rows. Also check slow disks, retries, remote fetch and garbage collection before attributing the straggler. Spark UI shows max ≫ median task time and one task's shuffle read is huge. Fix with AQE skew join or manual salting; pre-aggregate where possible.

Q3. Why do Python UDFs hurt performance? Scalar Python UDFs cross the JVM/Python boundary and hide their internal semantics from Catalyst. Transfer may be batched; optimizer restrictions depend on which expressions reference the UDF. Use SQL functions or Pandas UDFs (Arrow batches; columnar, vectorized) instead.

Q4. cache() vs checkpoint() — when to use which? cache keeps lineage; if a partition is lost, Spark recomputes from the lineage chain. checkpoint writes to reliable storage and truncates lineage. Use checkpoint to break long iterative chains (graph algorithms, ML loops) where lineage recomputation would be catastrophic on failure.

Q5. repartition vs coalesce? repartition(N) shuffles to redistribute (approximately evenly for round-robin rows, not necessarily bytes or cost). coalesce(N) (where N < current partitions) merges existing partitions without shuffle, but may produce unbalanced output. repartitionByRange(N, col) partitions by range using sampling — useful before sorted writes.

Q6. PySpark task crashes with Container killed by YARN, exceeding memory limits. Heap is fine. Why? Python workers and native allocations consume process/container memory outside the JVM heap. Check separately configured PySpark/off-heap allowances and the remaining overhead budget against RSS; choose measured headroom, not a universal percentage. Avoid loading large local objects.

Q7. Why does broadcast join risk OOM? The small side is collected to the driver, then sent to every executor. if the serialized side is 500 MB and there are 200 executor copies, raw replication alone is about 100 GB; deserialized/hash-table overhead and driver work can be larger.

Q8. What does df.explain(True) show, and what would you look for? Parsed → Analyzed → Optimized logical plans + physical plan. You scan for: chosen join type, presence of BroadcastExchange, HashAggregate vs SortAggregate, predicate pushdown into FileScan, partition filters, and AQE rules applied.

2. Spark Tuning — Diagnostic Recipes

These are the recipes you should rehearse aloud.

2.1 Tuning checklist (memorize)

The sizes below are starting hypotheses, not acceptance thresholds. Validate them on the actual engine/storage version and representative data; no Spark service or benchmark is run here.

1. Right file format: Parquet/ORC with snappy/zstd; target file size 128–512 MB.
2. Partitioning on disk: low-cardinality cols (date, region). NOT high-cardinality (user_id).
3. Bucketing when you join the same large tables repeatedly on the same key.
4. spark.sql.shuffle.partitions: tune so each shuffle partition processes ~128–256 MB.
5. AQE on: spark.sql.adaptive.enabled=true, plus coalesce + skew-join.
6. Broadcast the small side; hint broadcast(df) if Catalyst doesn't pick it up.
7. Avoid UDFs when SQL functions exist; if needed, Pandas UDFs.
8. Predicate pushdown: filter before join; let Parquet stats prune.
9. Column pruning: select only what you need, early.
10. Cache reused DataFrames only after measuring benefit. PySpark 3.5.7 DataFrame persistence defaults to MEMORY_AND_DISK_DESER; do not copy a Scala RDD storage constant into a Python API.
11. Dynamic Partition Pruning for star-schema joins.
12. Speculation can duplicate unusually slow task attempts; it does not divide deterministic hot-key work and requires a safe output commit protocol.
13. spark.executor.memoryOverhead: measure native/Python RSS and separately configured PySpark/off-heap allowances; no fixed percentage guarantees safety.
14. Avoid collect() on big DFs; use toLocalIterator() only when the largest partition fits driver memory, or write out.
15. Z-order / sort within partitions for selective queries (Iceberg/Delta).

2.2 The "this job is slow" design review answer

1. I would not guess. I'd open Spark UI.
2. SQL tab → physical plan, join strategy, scan size, partition filters.
3. Stages tab → shuffle read/write, spill, GC time, max vs median task time.
4. Executors tab → GC %, OOM, memory used, failed tasks.
5. Map symptom to fix:
     huge scan      → pushdown / partitioning / column pruning
     huge shuffle   → broadcast / bucket / AQE / skew
     stragglers     → AQE skew, salting, speculation
     GC time high   → inspect heap allocation/cache and partition work
     native RSS high → measure Python/native usage and memoryOverhead
     small files    → repartition before write, compaction
6. I'd validate the fix by re-checking the same UI metrics.

2.3 Q&A with reasoning

Q. Why does Dynamic Partition Pruning help star schemas? A fact-dim equi-join with a filter on the dim can be optimized: Spark first runs the dim filter, collects the matching dim keys, and pushes them as a partition filter on the fact scan. The fact scan only reads partitions that survived. Saves enormous I/O on large facts.

Q. Why are small files harmful on object stores? Object request/open/planning overhead and metadata can dominate tiny files. S3 prefix request-rate guidance is provider-specific, not a law of all object stores. A 10 TB table in 1 KB files is unusable. Target 128–512 MB; compact regularly.

Q. How does AQE detect skew at runtime? After each shuffle stage, AQE looks at partition sizes. For supported skew joins, a partition must exceed both the configured median factor and absolute-byte threshold; it splits that partition into sub-partitions and replicates the matching rows from the other side of the join.

Part II — Storage and Lakehouse

Object APIs define individual object visibility, while table formats define which set of files constitutes a committed snapshot. Follow the format/catalog commit and retention rules before reasoning about compaction, concurrent writes or deletion.

3. Distributed Storage — Why Object Stores Need Lakehouses

A distributed job finishing its tasks does not yet mean readers can safely see its output. Suppose half the new files have arrived while the remaining tasks are retrying: a reader needs either the old table or the committed new table, not an accidental mixture. The diagram introduces the gap between individual object operations and a table-wide commit. Provider-specific capabilities differ, as the comparison below shows; the common requirement is a consistent published table state.

3.1 HDFS vs object stores at a glance

3.2 Why "no atomic rename" matters

Rename-based Hadoop committers stage task attempts before publication. HDFS rename is a namespace operation; general-purpose S3 uses copy/delete, with work proportional to copied bytes plus per-object operations. Attempt selection and job publication must tolerate retries/speculation. This does not imply every classic-committer configuration duplicates output, and S3 Express RenameObject is a different API.

That's why we have:

• S3A magic/staging committers use pending multipart uploads and job/task commit protocols to avoid rename-based publication. Completing each object is atomic; completing an entire multi-file job is not one all-object atomic operation.
• Lakehouse table formats (Iceberg/Delta/Hudi) — table commit visibility is controlled by the format and catalog/log protocol, not by assuming a multi-file directory rename. Iceberg uses atomic metadata replacement; Delta uses its transaction log; Hudi has a timeline protocol.

3.3 File format quick-take

3.4 Performance levers

• Avoid small files — compact to 128–512 MB Parquet.
• Partition layout: tenant=.../date=.../hour=... for time-aligned scans.
• Column projection + predicate pushdown with Parquet/ORC stats.
• Z-order / Hilbert for multi-column locality (Iceberg, Delta).
• Caching layer (Alluxio, EMRFS S3 cache) for repeated reads.

4. Lakehouse and Apache Iceberg — Tables on Top of Object Storage

4.1 The problem in one paragraph

Raw Parquet on S3/ADLS/GCS gives cheap storage. It does not give you atomic multi-file writes, safe schema evolution, row-level updates/deletes, time travel/audit, or fast pruning at petabyte scale. Iceberg, Delta, and Hudi all add a metadata layer that turns folders of files into transactional tables.

4.2 Iceberg layout — every level matters

Iceberg answers that visibility problem by making table membership explicit in metadata. Read this hierarchy from the catalog down: a reader selects a snapshot and follows its file references rather than guessing membership from whichever objects happen to be present. The same hierarchy also carries statistics, which is why it helps both correctness and query planning.

• Catalog/commit implementation resolves current table metadata and supplies atomic replacement/commit validation. REST, metastore and filesystem implementations differ; branches/tags can retain other snapshots.
• metadata.json records schema (with column IDs), partition spec, sort order, and snapshots.
• Manifest list holds per-manifest partition-summary stats so a planner can prune whole manifests.
• Manifests list data files plus per-file stats: row counts, null counts, min/max per column.
• Data files may be Parquet, ORC or Avro according to the format and engine support.

4.3 Read path — why Iceberg scales beyond Hive

Older Hive-style layouts relied on directory listings to discover files; historical S3 consistency limitations added difficulty to that approach. Iceberg reads a small set of metadata files that already enumerate data files plus stats — most pruning happens before any data file is opened. For a query limited to one day, follow partition pruning to the surviving manifests, then file statistics to the surviving files. Strong object-store consistency alone does not provide that snapshot membership or eliminate the cost of discovering and planning a large file set.

4.4 Write path and commit protocol

1. Each task writes Parquet to data/.
2. On task completion, manifest entries are assembled.
3. Driver builds a new metadata.json referencing a new snapshot.
4. Driver requests atomic replacement of the observed metadata with the new metadata. Conceptual CAS, not a literal universal commit(currentSnap, newMetadata) API; catalog implementations define the request and validation.
5. On conflict, validate whether the operation remains safe on the new state. Compatible appends may retry metadata assembly; conflicting row-level operations may fail and need recomputation. Blind retry is not correct for every write.

That's optimistic concurrency. The atomic replacement establishes visibility; operation-specific conflict checks establish whether concurrent changes are compatible.

4.5 Killer features and why they matter

4.6 Iceberg vs Delta vs Hudi

Hudi has two flavors:

• Copy-on-Write rewrites whole files on update — fast reads, expensive writes.
• Merge-on-Read appends log/delta records merged with base files at read — fast writes, slower reads until compaction.

4.7 Maintenance you cannot skip

Skip these and the table eventually slows to a crawl.

4.8 Governance hooks (why this matters for catalogs)

Iceberg metadata is itself queryable:

SELECT * FROM catalog.db.table.snapshots;
SELECT * FROM catalog.db.table.files;
SELECT * FROM catalog.db.table.partitions;
SELECT * FROM catalog.db.table.history;

That supports snapshot/file audits and retention operations; it is not complete business lineage or a legal-erasure proof. Deletion must also account for branches/tags, copies, backups, object versions, caches and retention/legal holds.

4.9 Q&A with reasoning

Q1. Parquet vs Iceberg — same thing? No. Parquet is a file format (columnar layout inside one file). Iceberg is a table format (which files belong to the table at which snapshot, with what schema). Iceberg tables contain Parquet files.

Q2. Why does Iceberg scale where Hive directory listing doesn't? Hive reads tables by listing directories. Iceberg reads metadata files that already enumerate files plus min/max stats, so most pruning happens before any data file is opened.

Q3. How does Iceberg handle two writers at once? Optimistic concurrency: each writer prepares new metadata referencing the snapshot it read, then performs a single catalog-level CAS. A conflicting writer validates against the new state; some operations can retry while incompatible updates fail and require recomputation.

Q4. Equality deletes vs position deletes? Position deletes identify a data-file path and row position. Equality deletes match values in a specified field-ID set, not arbitrary SQL predicates. Readers reconcile applicable deletes under spec/sequence rules; implementation, sort order and workload determine relative cost. Engine/spec support must be checked.

Q5. How would you do GDPR delete on a 10 PB table?

1. Authorize and record deletion scope. 2) Execute supported DELETE with the engine/table copy-on-write or merge-on-read mode. 3) Rewrite affected files where needed and verify current reads. 4) Expire eligible snapshots only after checking branch/tag references, legal retention and in-flight jobs. 5) Safely remove unreferenced/orphan files with an age margin. 6) Reconcile object versions, replicas, backups and derived indexes under policy. Snapshot expiry does not guarantee global unrecoverability or legal compliance.

Part III — Indexes and Search

Graph and search indexes optimize different questions over authoritative data. Trace edge direction and bounded traversal for lineage, then analyzed terms, refresh and exact-value authorization filters for discovery; both indexes need rebuild and freshness contracts.

5. Graph Databases — Why Lineage Is Naturally a Graph

Some questions are fundamentally about relationships: "what depends on this column, 5 hops downstream?" Recursive SQL and graph traversal both pay for visited edges, filtering and result size. Neo4j-style native adjacency can make neighbor access efficient once an indexed start node is found; no database family is universally faster for every lineage graph.

5.1 Property graph model for lineage

5.2 Cypher essentials

These Neo4j 5 reference queries assume a single authorized tenant graph and indexed unique asset IDs. In a shared graph, bind tenant scope from authenticated context and constrain every traversed node/edge; filtering only the start node or trusting a caller-supplied tenant is insufficient. The final shortest-path example permits any relationship type deliberately; restrict types for lineage-only semantics.

// Anchor on an indexed node, bound depth
MATCH (start:Column {id:'sales.amount'})
MATCH (start)<-[:DERIVED_FROM*1..5]-(down:Column)
RETURN DISTINCT down.id;
 
// Temporal lineage — what was upstream on a date?
MATCH (a:Dataset {id:$id})-[r:DERIVED_FROM]->(b)
WHERE r.valid_from <= datetime($asOf)
  AND (r.valid_to IS NULL OR datetime($asOf) < r.valid_to)
RETURN b;
 
// Shortest path between two assets
MATCH p = shortestPath(
  (a:Dataset {id:'src'})-[*1..5]->(b:Dataset {id:'dst'}))
RETURN p;

5.3 Things that explode at scale

• Unanchored traversals — start from indexed nodes, always.
• Supernodes — a Tag connected to millions of columns will blow up any traversal that touches it. Split by tenant/domain/time, or filter relationship types early.
• Unbounded depth — always cap with *1..N.

5.4 Q&A with reasoning

Q. Why is index-free adjacency fast? Once the start node is found via index, each hop follows stored relationship pointers. This can avoid repeated global lookup work; relational adjacency with suitable indexes can also be efficient. Output size and supernodes still dominate some queries.

Q. How do you model temporal lineage? Put valid_from and valid_to on relationships, or version snapshots. Then "what was upstream on 2026-04-30?" becomes a predicate filter.

Q. When is a graph DB the wrong choice? When the workload is mostly aggregations, transactional records, or wide tabular reporting. Use relational/Iceberg for source of truth and graph as a traversal index that can be rebuilt from the source of truth.

Q. What is a supernode and why is it bad? A node with extremely high degree (tag connected to millions of columns). Traversals through it explode. Mitigations: filter by relationship type at the supernode, partition the supernode by tenant/domain, or skip it in path expansions.

6. Elasticsearch — Inverted Index, Discovery, Hybrid Search

6.1 Why Elasticsearch exists

Full-text discovery needs ranking, tokenization, typo tolerance, filters, facets, and low latency across millions or billions of documents. An unindexed substring scan is costly and lacks full-text ranking semantics; PostgreSQL full-text/trigram indexes and other engines are alternatives, not inherently incapable.

6.2 Architecture

• A shard is a Lucene index. Segments are immutable inverted-index files; refresh creates new segments; merge consolidates.
• Primary shards scale indexing throughput; replicas scale read throughput and provide HA.

6.3 Inverted index + scoring

"customer" → [(d1, tf=3, pos=[1,5,10]), (d4, tf=1, pos=[2]), ...]

• BM25 scoring (default since 5.x).
• Analyzer = tokenizer + filters (lowercase, stemmers, synonyms).
• Mapping: text (analyzed for full-text) vs keyword (exact for filters/aggregations/sort).

6.4 Document lifecycle

1. Index → translog + in-memory buffer.
2. Refresh → newly indexed data becomes searchable. Elastic Stack commonly defaults to 1 s for recently searched indices; serverless defaults and activity rules differ. Refresh is not the durability/fsync boundary.
3. Flush creates a Lucene commit and starts a new translog generation; translog durability and fsync policies are separate from refresh.
4. Merge → fewer larger segments. force_merge on read-only indexes.

6.5 Query DSL — what to actually write

{
  "query": {
    "bool": {
      "must":   [{"match": {"name": "customer"}}],
      "should": [{"match": {"description": "PII"}}],
      "filter": [{"term": {"tenant": "acme"}}, {"term": {"sensitivity": "high"}}],
      "must_not": [{"term": {"deleted": true}}]
    }
  },
  "aggs": {"by_tag": {"terms": {"field": "tags.keyword"}}}
}

• filter doesn't score and is cacheable — put exact-match conditions there.
• match is analyzed; term is exact (use on appropriately mapped exact-value fields, including keyword/numeric/date/boolean as applicable).
• Multi-match for cross-field; phrase with slop; fuzzy for typo tolerance; k-NN for vector search (8.x+).

6.6 Capacity planning rules

• Shard size sweet spot 10–50 GB. Too small → overhead. Too large → slow recovery, slow merges.
• Heap sizing: follow version-specific defaults and keep below the actual compressed-oops threshold (Elastic documents 26 GB as generally safe, sometimes about 30 GB), with room for OS file cache/native memory. 32 GB is not a universal boundary.
• Index lifecycle (ILM) — hot/warm/cold/frozen tiers.

6.7 Operational pitfalls

• Mapping explosion — dynamic mapping on user JSON creating thousands of fields. Use dynamic: strict or dynamic: false.
• Deep pagination (from + size > 10k) — use search_after with PIT.
• Refresh interval of 1 s is wasteful for bulk loads — set to -1 then back.
• Hot shards — node-level imbalance; use shard allocation awareness.

6.8 Q&A with reasoning

Q. Why limit JVM heap to 32 GB? The compressed-oops threshold depends on JVM/platform; verify it in node logs. Elastic recommends leaving substantial memory for filesystem cache/native uses and warns that oversized heaps can hurt pauses.

Q. match vs term? match analyzes the query text (lowercases, stems) and searches the analyzed field; term is exact byte match against the indexed token. Use term on keyword fields, not on text.

Q. What is hybrid retrieval? BM25 (keyword) + dense vector (semantic), fused with Reciprocal Rank Fusion (RRF). BM25 catches exact terms; dense catches paraphrases. They can complement one another; measure retrieval recall, relevance and latency on the target queries.

Part IV — AI / ML

Attention, vector retrieval and tool orchestration introduce different compute and trust boundaries. Derive the attention/cache costs, evaluate retrieval evidence, and keep model proposals separate from authorized actions and verified answers.

7. LLMs — What's Actually Inside the Box

7.1 The honest definition

An LLM is a neural network trained to predict the next token given previous tokens. Many chat LLMs use next-token pretraining plus post-training; architectures/objectives and tool/retrieval augmentation vary. This description is not a mechanistic explanation of every capability. It is not a database. It compresses patterns into weights — that's why it can hallucinate.

7.2 Transformer architecture

• Self-attention: $\text{softmax}(QK^T / \sqrt{d_k}) V$. Cost is $O(n^2 \cdot d)$ in sequence length.
• Multi-head: project into h heads, run attention in parallel, concatenate.
• Decoder-only (for example published Llama/Mistral architectures) — generation; do not infer undisclosed proprietary internals. Encoder-only (BERT) — embeddings/classification. Encoder-decoder (T5) — translation/summarization.
• Modern: RMSNorm, SwiGLU activation, RoPE position encoding, GQA (grouped-query attention) to shrink KV cache.

7.3 Why long context is expensive — and what saves it

• Attention is $O(n^2)$ in sequence length, so a 128k-token prompt costs ~16k× more than a 1k prompt for the attention matrix alone.
• KV cache stores prior keys/values so each new query attends to n cached positions without recomputing all prior projections/states. Dense attention for that decode step is O(n d); total generation across n new tokens still accumulates quadratic attention work. Cache memory grows with retained context.
• FlashAttention is an IO-aware kernel that tiles attention to keep working sets in SRAM and avoids materializing the full $n \times n$ matrix.
• RoPE scaling / NTK / YaRN alter position handling; usable length and retained quality require model-specific training/evaluation, not only a configuration change.
• Mixture-of-Experts (MoE): only a subset of expert FFNs activate per token (e.g., 2 of 8). Active FFN compute can fall relative to a dense model with the same total parameter count; routing, communication and memory determine actual throughput.

7.4 Embeddings and ANN search

An embedding maps text to a dense vector (typically 768–3072 dimensions). Similarity is cosine (after normalization, equivalent to dot product). Searching billions of vectors fast uses approximate indexes:

The trade-off triangle: recall ↔ latency ↔ memory. Tune efSearch/nprobe to move along that triangle.

7.5 Inference optimizations

• Quantization — INT8/INT4 reduce weight representation size relative to float formats; scale/metadata, kernels, KV cache and quality constraints determine real memory/latency savings.
• Speculative decoding — a small draft model proposes tokens; the big model verifies in parallel.
• Continuous batching admits new requests as others finish; PagedAttention manages KV storage. They are related serving mechanisms, not a universal 5–20× benchmark.
• Distillation — train a smaller student from a larger teacher.

7.6 Fine-tuning vs RAG

Choose the intervention from the failure: retrieval for missing authorized facts, prompting/schema/tool changes for workflow, and evaluated fine-tuning for learned behavior. LoRA is a parameter-efficient training method and can be used for SFT; these are not mutually exclusive product tiers.

7.7 Q&A with reasoning

Q. Why is attention $O(n^2)$? Every token computes a similarity score against every other token. n queries × n keys = $n^2$ pairs.

Q. Why does the KV cache help? In a causal decoder, cached prior K/V remain valid for a fixed prefix. The new query attends to n retained positions in O(n d), instead of recomputing full-prefix attention; growing-context generation still accumulates quadratic attention work.

Q. What does FlashAttention break? The memory wall — it avoids writing the full attention matrix to HBM, instead streaming tiles through fast SRAM. Same math, much less DRAM traffic.

Q. Why do tokenizers matter for cost? Token-based context limits and tariffs count the selected model tokenizer’s output. Count customer_account_id_v2 with that tokenizer; character length or rarity alone does not determine a fixed token count or price.

Q. Why does normalization matter for cosine vs dot product? Dot product equals the product of the two norms times cosine; magnitude and direction both matter. Increasing magnitude makes a negative dot product more negative, not a better high-score match. Normalize nonzero vectors to unit length and dot equals cosine.

Q. RLHF vs DPO? Both align the model to preferences over candidate pairs. A common RLHF pipeline fits a reward model and optimizes a policy, often with PPO; RLHF is broader than that one optimizer. DPO directly optimizes a preference objective without an explicit separately trained reward model in that recipe. Stability/quality are empirical, not guaranteed.

8. RAG and Agentic Systems — Models That Reach for Data and Tools

8.1 Vanilla RAG pipeline

The model’s weights are not the platform’s current catalogue. To answer “Which dataset contains customer contact details?”, the service must first find relevant, authorized records. Follow the lower indexing branch into the query-time retrieval path, then watch where retrieved material enters the prompt. That join is the crucial boundary: a fluent answer cannot compensate for missing evidence or a tenant filter applied too late.

8.2 Quality levers, in order of impact

The ordering is a diagnostic starting point, not a universal ranking; evaluate ablations for the actual corpus and task.

1. Chunking — semantic, with 10–20 % overlap, with metadata (source, owner, tenant, sensitivity, timestamp). For tabular metadata, chunk = a dataset card with name, description, key columns, owner, tags.
2. Hybrid retrieval — BM25 + dense, fused via Reciprocal Rank Fusion.
3. Query rewriting — HyDE (have the LLM imagine an answer, embed it, retrieve real docs by similarity), multi-query, decomposition.
4. Reranker — cross-encoder (bge-reranker, Cohere rerank) over top-50 → top-K.
5. Pre-retrieval metadata filters — tenant, time, sensitivity. Authorize the retrieval universe and enforce again before exposure. Some ANN engines apply filters after approximate scanning internally; use supported filtered/exact/iterative strategies and do not expose unauthorized intermediate results.
6. Prompt — citations format, structured output via JSON schema or function calling.
7. Caching answers by tenant, authorization/audience version, query/context, content and model/prompt version. Stale-while-revalidate is inappropriate where stale permissions could expose revoked content.

8.3 Why hybrid retrieval can complement either alone

• Dense embeddings nail semantic paraphrase ("client identifier" → customer_id).
• BM25 nails exact identifiers, code symbols, rare terms (PII_CUSTOMER_EMAIL_V2).
• RRF avoids directly comparing incompatible score scales, but has parameters (rank constant k, candidate windows and possibly weights):

score(d) = Σ over rankers   1 / (k + rank_r(d))         # k often 60

8.4 Evaluation (treat it as a test suite)

Tools: Ragas, TruLens, DeepEval, Langfuse. Use LLM-as-judge with a calibration set, plus periodic human review.

8.5 Agentic loop

Useful agent = LLM + a small set of typed tools + a loop with hard limits:

• max tool calls per task,
• token + dollar budget,
• wall-clock timeout,
• deterministic fallbacks for parts that should never depend on an LLM.

8.6 Worked example — autonomous PII classifier

A new column gives the agent loop a concrete task: decide whether the column needs a sensitive-data tag, with evidence a steward can inspect. Trace a clearly formatted email through the early rule branch, then contrast an ambiguous identifier that needs profiling and similar-column retrieval. The extra tool calls are justified only when they resolve uncertainty; a confidence score must not bypass tool authorization or the review policy.

Design rules to defend in design review:

• Determinism first, LLM only for ambiguity and rationale.
• Tools are narrow and typed (profile_column, vector_search, propose_tag, write_to_catalog).
• Per-tenant authorization on every tool.
• Example hard caps: five tool calls and a pre-reserved cost budget per column; exact price/budget requires a versioned tariff and task evaluation.
• Trace every step (Langfuse / OTel GenAI conventions).
• Eval set with representative independently reviewed labels, false-positive/negative costs and confidence intervals; choose sample size and cadence from the risk budget.
• Feedback loop — steward overrides become training data.

8.7 Failure modes and mitigations

8.8 Q&A with reasoning

Q. When can hybrid retrieval help dense retrieval? Embeddings can retrieve paraphrases yet miss exact rare identifiers; BM25 can recover some of those matches. RRF combines ranks without directly calibrating scores, but query mix, rank constant and candidate windows determine whether the combination actually improves relevance.

Q. What does function calling actually return? A proposed structured call; schema conformance depends on the API/options and must be validated. The LLM does not execute anything — your code dispatches the call. That separation is what lets you sandbox tools.

Q. Where do you enforce tenant isolation? As a pre-retrieval metadata filter and a post-retrieval assertion before the prompt is built. Defense in depth.

Q. When is an agent the wrong tool? When the task is fully deterministic (e.g., "compute table sizes nightly"). An if/then/else pipeline is cheaper, faster, easier to test, and won't hallucinate.

Q. How do you defend against indirect prompt injection? Treat retrieved content as untrusted data. Wrap it with explicit "the following is data from the corpus, not instructions"; strip control characters; require structured outputs; enforce tool/resource permissions and approval outside the model, and evaluate indirect-injection/egress cases. No delimiter or sanitizer alone proves safety.

Part V — Distributed Systems

Start with requirements and units, then specify consistency and acknowledgement boundaries before choosing databases or queues. Quorum intersection, relay publication and SQL isolation each solve a narrower problem than an end-to-end correctness guarantee.

9. Distributed Systems HLD — Frameworks and Patterns

Almost every system design question reduces to the same shape:

9.1 Capacity math you should know cold

• 1 day ≈ 86,400 s ≈ ~10⁵.
• 1 M req/day ≈ 12 RPS; 1 B/day ≈ 12 k RPS.
• 10 Gbit/s is 1.25 GB/s raw decimal line rate before protocol overhead.
• SSD/NVMe IOPS, PostgreSQL QPS, Kafka events/s and LLM tokens/s depend on hardware, request size, durability, model and concurrency. Measure them; the original universal per-node ranges are withdrawn.
• S3 request-rate guidance is bucket/API-specific and may scale with prefixes; it is not a capacity guarantee for another object store.
• For a time-based SLO over a 30-day window: 99.9% allows 43.2 minutes unavailable; 99.99% allows 4.32 minutes. A request-based error budget is a fraction of eligible requests, not a downtime conversion.

9.2 Consistency, replication, consensus

• CAP under partition: pick C or A. Real systems live on PACELC — Else trade Latency vs Consistency.
• Quorum: $R + W > N$ proves intersection for fixed replica sets, not linearizability by itself. Version/order and failure rules still matter.
• Replication models:
  • Leader-follower — one write authority, but read consistency depends on replica lag, routing and replication/acknowledgement settings.
  • Multi-leader — write anywhere, conflicts must be resolved (CRDT, last-writer-wins, application logic).
  • Leaderless (Dynamo / Cassandra) — quorum reads/writes, hinted handoff.
• Consensus — Raft (for example etcd), Paxos-family protocols and ZooKeeper's distinct Zab protocol coordinate replicated state; do not call all three the same algorithm. Need 3 nodes to tolerate 1 failure, 5 to tolerate 2.
• Time — NTP/PTP, hybrid logical clocks, vector clocks, Lamport timestamps, TrueTime (Spanner).

9.3 Building blocks (2026 default picks)

Interpret these as examples to evaluate, not a current market-ranking or default-vendor mandate.

9.4 Patterns you'll reach for

• Outbox pattern — atomically persist business row plus outbox row, then relay at least once. It closes a local lost-event gap; publication and external effects still need retries/deduplication.
• Saga — cross-service transactions with compensating actions when 2PC isn't viable.
• Idempotency keys — bind principal, operation and request payload to a durably recorded outcome; atomically dedup with the effect. A header alone cannot make retries safe.
• CQRS / event sourcing — separate write model from read model.
• Backpressure + bounded queues.
• Retry + exponential backoff + jitter + circuit breaker + bulkhead.
• Cache stampede mitigation: request coalescing, jittered TTL, stale-while-revalidate.
• Hot key — salt, secondary indexes, replicate.
• Schema migration without downtime — expand → migrate → contract.
• Backfills without overload — rate-limited, idempotent, resumable.

9.5 The outbox pattern in detail

An order saved without its notification event is a useful failure to reason about: the database says it happened, but downstream services never hear of it. The diagram puts both durable records inside one transaction and moves publication to a separate relay. Follow that relay carefully—it closes the lost-event gap, but retries still require the idempotent consumers shown on the right.

What it solves: the dual-write problem. If you write to the DB and then publish to Kafka as two separate calls, a crash between them leaves the system inconsistent. Outbox writes the event row in the same DB transaction as the business row. A separate relay reads outbox entries and publishes them; consumers must be idempotent (dedup by event id).

9.6 Worked example — multi-tenant lineage service

Apply that reliability question to lineage: a completed Spark job must eventually be visible in both the audit history and the dependency graph. These stores serve different readers, so the two arrows from ingestion are not an atomic transaction. Read the architecture with a failure in mind: if the graph update fails after durable capture, the service needs replay and a way to expose freshness rather than pretending the two views changed together.

Why two stores? Iceberg is the durable source of truth (cheap, replayable, auditable). The graph store is a traversal index that can be rebuilt from Iceberg if it corrupts. Writes go to both; the graph is eventually consistent with Iceberg.

9.7 Common HLD designs to be ready for

1. Distributed metadata catalog (Google-scale).
2. Lineage service spanning lakehouse + DW + dashboards.
3. PII discovery / classification platform.
4. Real-time data quality scoring on streams.
5. Multi-tenant search service.
6. Vector search at scale (multi-tenant RAG).
7. Idempotent ingestion service with exactly-once into Iceberg.
8. Job orchestrator for Spark DAGs with retries and SLA.
9. Distributed rate limiter / API gateway.
10. CDC pipeline Postgres → Kafka → Iceberg → DW.
11. Feature store for ML.
12. Observability platform.

9.8 Q&A with reasoning

Q. What does the outbox pattern solve? The dual-write problem. You want to update a DB row and publish an event. If you do them as two separate calls, a crash between them leaves the system inconsistent. Outbox writes the event row in the same DB transaction, then a relay reads the outbox table and publishes. Consumers must be idempotent.

Q. At-least-once vs exactly-once? At-least-once may deliver duplicates after retry. Exactly-once semantics have a specified scope: coordinate input progress with output or use a durable dedup/effect transaction. A MERGE statement alone does not prove exactly-once for arbitrary non-idempotent updates or stale CDC.

Q. Why use consistent hashing? When a node is added or removed, an expected roughly K/(N+1) keys move on adding a balanced node to N existing nodes (about K/N on removing one), instead of remapping nearly everything. Virtual nodes smooth load distribution.

Q. How do you avoid hot-key on a global counter? Bucket the key into many shards (counter:42#0..M-1), increment a random shard, sum periodically. Trade read cost for write scalability.

Q. What does R + W > N prove? Fixed read/write replica sets intersect. That alone is not linearizability: concurrent writes, failed/partial writes, version resolution and sloppy quorums require additional protocol rules. A timestamp tie-breaker is not a proof.

Q. Saga vs 2PC? Prepared 2PC participants can block awaiting a durable coordinator decision. A saga commits local steps and compensates on failure; orchestration may use synchronous or asynchronous calls. Compensation is a business action, not guaranteed rollback, and may itself need retries/manual repair. Choose from atomicity and failure requirements, not a microservice label.

10. SQL and RDBMS — Indexes, Plans, Isolation

10.1 Mental model

A database must answer three hard questions:

1. How do I store data safely? → transactions, WAL, durability.
2. How do I find data quickly? → indexes, statistics, optimizer.
3. How do I handle many users at once? → isolation, locks, MVCC.

Most SQL performance reduces to: how many rows must we touch, and can an index reduce that?

10.2 ACID + isolation levels

• MVCC (Postgres, Oracle, InnoDB) — ordinary snapshot reads and writes can coexist via tuple versions; row/table locks and DDL can still block. The visibility map supports vacuum/index-only scans, not the entire visibility mechanism.
• Long-running transactions prevent vacuum cleanup → table bloat.

10.3 Indexes — what they're for

There is no universal 5–10% cutoff. Correlation, covering/visibility, random I/O cost, table size and cache state affect index versus sequential scan cost.

10.4 Why WHERE date_trunc('day', ts) = '2026-04-30' is slow

Applying a function to the indexed column prevents direct B-tree lookup. Rewrite as a range:

WHERE ts >= '2026-04-30' AND ts < '2026-05-01'

This enables an ordinary B-tree range predicate; the optimizer may still choose a sequential scan. An expression index can support the matching date expression where its immutability/time-zone semantics are valid.

10.5 Reading EXPLAIN ANALYZE

Operators to recognize:

• Seq Scan — scans the relation; can be optimal even for large tables when many rows are needed.
• Index Scan / Index-Only Scan — compare selected rows, random I/O and visibility heap fetches, not just the operator name.
• Bitmap Heap Scan — combine multiple indexes, then fetch.
• Hash Join — build hash on smaller side.
• Merge Join — both sides sorted on join key.
• Nested Loop — fast when outer is small and inner is indexed.

Compare estimated versus actual rows, loops and buffers. Large errors suggest stale statistics, correlation, skew or parameter-sensitive plans; ANALYZE may help but is not a universal repair. EXPLAIN ANALYZE executes the statement, including writes, so use a safe fixture or an explicitly planned transaction.

10.6 Online schema migration — expand / contract

PostgreSQL 11+ can add a column with a constant nonvolatile default without rewriting every row, but ALTER TABLE still needs locks and validation may scan. Deploy dual writes before/during backfill, reconcile concurrent changes, validate parity, then switch reads and retire the old column under a rollback plan.

10.7 Q&A with reasoning

Q. How does a composite index (a, b, c) help queries? Usable for filters on a, (a, b), or (a, b, c) — a condition on b alone may still use the index but usually cannot narrow the scanned range effectively in PostgreSQL 16. Check the version and plan; this is not absolute unusability. Order columns by selectivity and common filter shape.

Q. Why is UUID a worse PK than BIGINT for clustered indexes? UUIDv4 values are random → inserts can hit scattered pages → page splits, fragmentation, poor cache locality. ULID/UUIDv7 improve temporal locality but do not guarantee strictly sequential order across generators. PostgreSQL heap storage is not an InnoDB-style permanently clustered primary index.

Q. Hash join vs merge join vs nested loop — when each?

• Nested loop — small outer + indexed inner; roughly O(outer × log inner + output) for that access path.
• Hash join — equi-joins; expected O(N+M+output) with adequate hash memory and ordinary hashing; skew/spill add cost.
• Merge join — ordered equijoin inputs; O(N+M+output), excluding input sorts. Duplicate-key runs still require buffering/revisiting matches.

Q. Why does VACUUM FULL block writers? It rewrites the table to reclaim space and takes an ACCESS EXCLUSIVE lock. An alternative such as pg_repack has its own locks, privileges, storage headroom and compatibility requirements; no live maintenance is performed here.

Part VI — Modeling and Governance

Define the fact grain and history semantics before choosing a star, vault or graph representation. Governance joins identity, ownership, quality, lineage and access policy; a tag proposal is not automatically an enforceable or legally sufficient decision.

11. Data Modeling — Choose by Query Shape

The right model depends on who asks what, not on which model is fashionable.

11.1 OLTP vs OLAP

11.2 Dimensional (Kimball) modeling

• Fact tables — measurements + FKs to dimensions; e.g. sales_fact (sale_id, date_key, product_key, store_key, qty, amount).
• Dimension tables — descriptive context (product, customer, date, store).
• Star = fact + flat dims. Snowflake = normalized dims (more joins, less duplication).
• Grain — the most atomic level a fact row represents. Define grain first.
• SCD types:
  • Type 1 — overwrite, no history.
  • Type 2 — new row + effective_from/to, is_current.
  • Type 3 — column for previous value.
  • Type 4 — terminology varies; Kimball uses a mini-dimension pattern, while some tutorials use a separate history-table label. State the chosen taxonomy.
  • Type 6 — Type 2 history plus current attributes overwritten across historical rows (the conventional 1+2+3 hybrid).

11.3 Other modeling approaches

• Data Vault 2.0 — Hubs (business keys), Links (relationships), Satellites (descriptive + history). Insert-only, auditable; great for raw enterprise lakes feeding star marts downstream.
• One Big Table (OBT) — wide tables on Iceberg/BigQuery for ML/feature engineering.
• Graph modeling — for lineage, entity resolution, knowledge graphs.

11.4 Modeling decision table

11.5 Q&A with reasoning

Q. What is grain and why does it matter? Grain is what one fact row represents. If grain is unclear, aggregations either double-count or lose meaning. Always define grain first.

Q. SCD Type 2 implementation in Spark + Iceberg? A matched MERGE source row does not automatically both update and insert. Stage change rows or use a transaction that closes the prior interval and inserts the new version atomically. Keep one current row per natural key, nonoverlapping effective intervals, stable version/surrogate identity and retry deduplication; handle late changes explicitly. The local worked program below demonstrates the transaction.

Q. When is Data Vault the right answer vs Kimball? Data Vault for raw, auditable, source-system-faithful layers in large enterprise lakes where multiple inconsistent sources land. Build Kimball star marts on top for analyst consumption.

12. Data Governance — Catalog, Quality, Lineage, Privacy

12.1 The six questions a governed platform must answer

1. What data do we have? — catalog
2. Who owns it? — stewardship
3. Can I trust it? — quality
4. Where did it come from? — lineage
5. Who can access it? — policy / RBAC / ABAC
6. Is it sensitive? — classification / PII detection

12.2 Architecture of a modern catalog

The lineage service answers dependency questions, but a catalogue also has to answer “what is this asset?” and “how do I find it?” Follow one new dataset through ingestion into the entity, search, and graph stores below. They are different views of the same asset, not three competing authorities; stable identity and visible update lag are what let the service combine their answers responsibly.

Why three indexes? Because three different access patterns:

• Entity store for canonical "what is this asset?"
• Search index for "find me anything about X."
• Graph for "what's upstream/downstream of X?"

12.3 Metadata types (memorize)

• Technical — schema, types, partitioning, formats, sizes.
• Business — glossary terms, domains, owners, descriptions.
• Operational — ingestion times, freshness, last-updated, run logs.
• Social — usage, ratings, certified status.
• Lineage — who reads / writes / derives.
• Quality — rule definitions, scores, incidents.

12.4 Data quality dimensions

12.5 Lineage granularity

• Table-level — jobs read/write tables (cheap, coarse).
• Column-level — which output column derives from which input columns. Built by parsing SQL or capturing Spark logical plans (OpenLineage's Spark integration).
• Row-level — full provenance per record. Expensive; rarely worth it.

12.6 OpenLineage — the standard

Three core entities: Job, Run, Dataset (inputs/outputs). RunEvents emit start/complete/fail. Spark / Airflow / Flink / dbt have integrations. Backends: Marquez, Datahub, OpenMetadata.

12.7 PII classification — layered, not "just call the LLM"

Deterministic layers can handle well-defined patterns, but their coverage must be measured; the LLM is only invoked for ambiguity, and a human approves low-confidence cases. This keeps cost, latency, and audit trails sane.

12.8 Policy enforcement

• Tag-based access — "if tagged PII and user not in privacy_role, mask."
• Row-level filters — tenant/region.
• Column masking — hash, redact, tokenize.
• Enforced in compute (Snowflake / Databricks / Trino) via integrations or proxies (Immuta, Privacera).

12.9 Q&A with reasoning

Q. RBAC vs ABAC — what's the practical difference? RBAC assigns permissions to roles; users inherit role permissions. ABAC evaluates attributes of subject, resource, and environment in a policy expression. ABAC can reduce role explosion when permissions depend on tenant, region, sensitivity, time, etc.

Q. What is a "data contract"? A versioned, testable agreement between producer and consumer covering schema, semantics, freshness, and SLAs. Enforced in CI: schema changes that break the contract fail the build.

Q. Why graph for lineage rather than recursive SQL? Multi-hop relationship traversal is what graph databases are built for. Both recursive SQL and graph traversal must visit relevant edges; benchmark representative depth/degree/filter/selectivity and cycle handling rather than assuming a universal winner.

Q. Where does OpenLineage capture column-level lineage? OpenLineage integrations can derive column dependencies from supported Spark plan expressions and facets. SQL parsing and runtime capture have different coverage; opaque UDFs, dynamic sources and unsupported operators can still leave unknown lineage. Record uncertainty rather than claiming complete fidelity.

Part VII — Algorithms, Languages, Platform

Use explicit invariants to select algorithms, runtime memory/concurrency behavior and deployment controls. The local algorithms have independent tests; JVM, Spark and Kubernetes procedures remain version-specific service references rather than reproduced operations.

13. Algorithms and Data Structures — The Patterns That Repeat

Don't memorize 200 problems. Learn the recognition table.

13.1 Pattern recognition

13.2 Big-data sketches

• HyperLogLog — approximate distinct count using registers; the relative standard error is approximately 1.04/sqrt(m), with memory depending on representation and corrections. Used by Spark's approx_count_distinct.
• Count-Min Sketch — approximate frequency. Heavy-hitter detection.
• Bloom filter — probabilistic set membership. False positives are possible; a correctly maintained insertion-only filter with consistent hashing has no false negatives for inserted keys. Deletion bugs, stale filters and inconsistent encodings invalidate that guarantee. Used inside Parquet row groups, RocksDB, ad-blocking.
• MinHash + LSH — near-duplicate detection at scale (entity resolution).

13.3 Patterns in code

Contracts: strings are iterated as Python Unicode code points; top-K values must be mutually orderable; DSU expects integer vertices in [0,n); topo expects finite reusable adjacency lists and includes neighbor-only vertices. LRU accepts hashable keys and uses -1 for misses (ambiguous if -1 is a stored value). Top-K costs O(n log k) plus its O(k log k) sorted output for k≥2; k=1 is a linear scan and k=0 returns immediately.

Sliding window — longest substring without repeating chars (O(n))

def length_of_longest(s):
    seen = {}
    left = best = 0
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1
        seen[c] = right
        best = max(best, right - left + 1)
    return best

Top-K with a min-heap of size K (O(n log k))

import heapq
 
def top_k(stream, k):
    if type(k) is not int or k < 0:
        raise ValueError("nonnegative integer k required")
    if k == 0:
        return []
    h = []
    for x in stream:
        if len(h) < k:
            heapq.heappush(h, x)
        elif x > h[0]:
            heapq.heapreplace(h, x)
    return sorted(h, reverse=True)

Why a min-heap of size k? The smallest of the top-K is on top; you only displace it if a new element is larger.

Union-Find with path compression + union by rank (~O(α(n)) per op)

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0] * n
 
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path compression
            x = self.p[x]
        return x
 
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.r[a] < self.r[b]:
            a, b = b, a
        self.p[b] = a
        if self.r[a] == self.r[b]:
            self.r[a] += 1
        return True

Used for connectivity (lineage clusters, account merging, friend graphs).

Topological sort — Kahn's algorithm (O(V+E))

from collections import deque
 
def topo(graph):                      # graph: {u: [v, ...]}
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] = indeg.get(v, 0) + 1
            indeg.setdefault(u, 0)
    q = deque([u for u, d in indeg.items() if d == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.get(u, []):
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    if len(order) != len(indeg):
        raise ValueError("cycle detected")
    return order

Used for job DAGs, compile dependencies, lineage recompute order.

LRU Cache (OrderedDict)

from collections import OrderedDict
 
class LRU:
    def __init__(self, cap):
        if type(cap) is not int or cap < 0:
            raise ValueError("nonnegative capacity required")
        self.cap = cap
        self.d = OrderedDict()
 
    def get(self, k):
        if k not in self.d:
            return -1
        self.d.move_to_end(k)
        return self.d[k]
 
    def put(self, k, v):
        if k in self.d:
            self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap:
            self.d.popitem(last=False)

13.4 Q&A with reasoning

Q. Why is heapifying a list O(n), not O(n log n)? Sift-down from the bottom up — leaves are already heaps, and most nodes are near the bottom (cheap sift). The geometric series sums to O(n).

Q. When does a Bloom filter return a false negative? Not for correctly maintained insertion-only filters with matching encodings/hash functions. It can if state is stale/corrupted or deletion clears shared bits. That's why it's used as a negative cache — a "no" is reliable, a "yes" requires confirmation.

Q. BFS vs DFS for shortest unweighted path? BFS — it expands by distance layer, so the first time you reach the target you've used the fewest hops.

Q. Why does Dijkstra fail on negative edges? It commits to the shortest known distance once a node is finalized; a later negative edge could discover a shorter path. Use Bellman-Ford for negatives (and detect negative cycles).

Q. How does HyperLogLog estimate distinct counts? It hashes each element, looks at the run of leading zeros in the hash, and tracks the maximum across many "registers" partitioned by hash prefix. The harmonic mean of 2^max_zeros across registers estimates cardinality. For m=16,384 registers the asymptotic relative standard error is about 0.8125%; storage depends on register encoding and estimator implementation, not a universal 16 KB allocation.

14. Java and the JVM — What Production Engineers Must Know

14.1 Memory model

The diagram describes a traditional generational HotSpot layout, not every collector. Region-based/concurrent collectors organize memory differently; pause/heap ranges below are workload hypotheses rather than service guarantees.