skip to content

Two inputs each arrive at 5,000 records a second under a 30-minute match bound. What is retained, and what does doubling the bound cost?

level: middleimportance: must knowfreq 58%

answer

  1. rate times time, once per side
  2. two sides summed, not one doubled
  3. bytes per held record vary by runtime
  4. memory linear in the bound
  5. recovered pairs follow the gap tail

basics

~20 s

Each side holds arrival rate times the bound: 5,000 a second over 1,800 seconds is 9 million records per side, 18 million across both. At a fixed rate and a symmetric bound, doubling the bound doubles the records held and the memory they occupy, while the extra pairs it recovers follow the tail of the gap distribution.

solid answer

~50 s

Do it as arithmetic, per side. Thirty minutes is 1,800 seconds, so each side holds about 5,000 × 1,800 = 9 million records, and both sides together about 18 million. Bytes follow from a **measured** per-record footprint including the bookkeeping the runtime adds — and that footprint varies several-fold between runtimes that keep a compact managed layout and those that hold ordinary language objects, so take it from a measurement rather than from another system's number. Spread across workers, the total divides by the number of workers only if the join key distributes evenly. At a fixed arrival rate and a symmetric bound, doubling the bound doubles held records and memory linearly — but it does not double the pairs recovered, because recovery depends on how many pairs actually sit between thirty and sixty minutes apart, which is usually a thin tail.

code

python · 19 lines
python
rate_left = 5_000          # records per second on the left input
rate_right = 5_000         # records per second on the right input
bound_seconds = 30 * 60    # limit on the difference between the two moments

# Each side is held for as long as a partner could still satisfy the predicate.
hold_left_seconds = bound_seconds
hold_right_seconds = bound_seconds   # would be ~0 if the bound were one-directional

held_left = rate_left * hold_left_seconds      # 9_000_000
held_right = rate_right * hold_right_seconds   # 9_000_000
held_total = held_left + held_right            # 18_000_000

bytes_per_held_record = 200   # MEASURE this; it differs several-fold between runtimes
retained_bytes = held_total * bytes_per_held_record   # ~3.6e9, about 3.6 GB

workers = 40
per_worker_bytes = retained_bytes / workers   # only even if the join key spreads evenly

print(held_total, retained_bytes, per_worker_bytes)

go deeper

for a junior

Recall the shape of the calculation before the details: records held equals how fast records arrive multiplied by how long they must be kept, and it applies to each of the two inputs separately.

for a middle

Do the arithmetic out loud and name every factor: rate, holding time per side, a measured footprint per held record, and the division across workers that only holds when the join key spreads evenly.

for a senior

Show what the number governs beyond memory — how much a saved picture of the job carries and how long a restart reloads — and name the levers that shrink it without touching the bound.

for a principal

Treat the bound as a budget line: memory grows with traffic while recovered pairs grow with a thin tail, so state what the extra retention is worth before agreeing to it.

## The arithmetic, done per side The retained size of a time-bounded match — a join whose predicate limits how far apart the two records' moments may be — is one multiplication done twice: 1. **Records held on a side** = that side's arrival rate × the time that side must be held. Here 5,000 records a second × 1,800 seconds = **9,000,000 records**. 2. **Records held in total** = the two sides added, not one side doubled by reflex. With equal rates and a symmetric bound they happen to coincide: **18,000,000 records**. 3. **Bytes** = records × a measured per-record footprint, which must include the key index entry and the moment stored alongside the record, not just the payload. The third line is where estimates go wrong. The footprint of one held record is not a property of the join; it is a property of how the runtime represents records. One lineage keeps a compact binary layout it manages itself; another holds ordinary objects of the host language, several times larger for the same fields. Quoting a figure learned on one runtime as though it were universal is the classic sizing error here. Measure, then multiply. ## What the number is and is not | Quantity | How to get it | The trap | |---|---|---| | Held records, one side | that side's rate × that side's holding time | assuming both sides are held for the same length when the bound is asymmetric | | Held records, total | the two sides summed | sizing one side and calling it the answer | | Bytes retained | records × measured footprint per held record | importing a per-record footprint from a different runtime | | Per worker | total ÷ workers | true only where the join key spreads evenly; one dominant key value is a neighbouring subject with its own remedy | | Restore cost | scales with the same retained size | forgetting that a saved picture of the job includes what the match is holding | The last row is the one people meet in production rather than on a whiteboard: the bound does not only set steady-state memory, it sets how much has to be written when the job saves a picture of itself and how long a restart takes to reload it. The mechanics of that saving belong to the recovery subject; the size of the thing being saved is set right here. ## What doubling the bound buys At a fixed arrival rate and a symmetric bound, going from thirty to sixty minutes: - **doubles** held records on both sides, and therefore the memory and the amount reloaded after a restart; - **does not double** the pairs recovered. The extra matches are exactly those whose two moments lie between thirty and sixty minutes apart. In most real pairings that gap distribution is heavily front-loaded, so the second thirty minutes buys a thin tail for the same price as the first thirty bought the bulk; - **does not materially change** the cost of handling one arrival. A probe goes to the held records under that arrival's own join key, so its cost tracks how many partners that key has, not how many records the job holds in total; - **does not change** when a matched pair is emitted. A match is emitted when the second record arrives, whatever the bound. What does stretch is any output that must wait for the bound to pass, such as a record emitted with a null counterpart once it is certain no partner is coming. ## What genuinely reduces the number - **Project before holding.** Keep the join key, the moment and the fields the output actually needs. Halving the bytes per held record halves the whole figure, and costs nothing but discipline. - **Use an asymmetric bound where the relationship is asymmetric.** If a payment can only follow its order and never precede it, the order side must be held for the full bound while the payment side needs holding only briefly. That is close to halving the retained set for no loss of matches. - **Drop on match where the cardinality allows it.** If each record can pair at most once, release it as soon as it pairs. In a many-to-many match this is wrong, because a later arrival may legitimately pair with the same record again. - **Shorten the bound deliberately** and count what is thereby missed, rather than discovering the miss later. What does **not** reduce it: adding workers. More workers divide the same 18 million records across more machines, which fixes a per-worker memory problem and changes the total not at all. Nor does an emission contract that publishes early results and corrects them later — when a value is handed downstream is a separate decision from how long a record must be retained in case its partner turns up. ## A worked sanity check At 200 bytes per held record — a figure to be measured, never assumed — 18 million records is about 3.6 GB before any bookkeeping, spread over however many workers the join runs on. That is a number a candidate can produce in an interview in thirty seconds, and it is the number that decides whether the requested bound is a configuration change or a redesign.

  • Does adding workers reduce the total retained size?
    No. It divides the same total across more machines, which is the right fix when one worker cannot hold its share and no help at all when the aggregate is the problem. The total is set by arrival rate and bound; only shrinking one of those, or shrinking the bytes per held record, moves it. Uneven key distribution means the division is not equal either, which is a separate subject with its own remedies.
  • When can a record be released as soon as it matches?
    When the join is genuinely one-to-one on that side, so a record that has paired can never pair again. Then the held set is the unmatched backlog rather than the full rate-times-bound figure, which can be far smaller. In a one-to-many or many-to-many match the record must stay until its bound passes, because another partner may still arrive.
  • What besides steady-state memory scales with the bound?
    The size of a saved picture of the job, and therefore how long a restart takes to reload it, since the held records are part of what is saved. Rescaling the job is affected for the same reason: the held records have to be redistributed before processing resumes. The mechanics belong to the recovery subject, but the volume involved is set by the bound chosen here.

saying these in an interview costs you the question

  • Sizes one side only and forgets both inputs are held
  • Assumes doubling the bound doubles the pairs recovered
  • Quotes a per-record footprint from one runtime as universal
  • Says more workers reduce the total records held
  • Calls a join bounded in time and therefore bounded in size, whatever the rate
  • Assumes a held record always leaves memory the moment it matches