When does galloping to bracket a range beat one size query plus binary search on a remote sorted log?
answer
- which unit of cost actually matters here
- count round trips, not comparisons
- what a size query really costs on a follower
- where do the queries actually land
- roughly two log i against log n plus one
basics
~20 sGalloping wins when the size is unavailable, expensive or stale, or when targets cluster near the head, since its cost tracks the answer's position. A cheap, exact size wins for uniformly placed targets: one plain search halves the probes.
solid answer
~50 sCount round trips, not comparisons: on a remote log each probe is a paged read, so probe count is the cost model. A size query plus binary search costs `1 + log2(n)` round trips. Galloping costs about `2 log2(i)` and needs no size at all. So the decision turns on two facts about your workload. First, is the size cheap, exact and current? On a replicated log it is often none of those, and a search that never asks for it removes a coordination point from the read path. Second, where do targets land? A tailing feature that asks "first entry at-or-after timestamp T" with a recent T lands near the head, and `2 log2(i)` is a handful of probes; a query for an ancient timestamp lands near the end and pays roughly double a plain binary search. Measure the position distribution before choosing.
go deeper
Know that on remote data the number of reads matters far more than the number of comparisons, and that a search which avoids asking for the size has one fewer thing that can fail.
Be able to put numbers on both options — roughly one round trip plus log n probes against roughly two log i — and say which workload favours which.
Demonstrate the judgment: interrogate whether the size is exact and current, measure where queries land, exploit a caller's last-read offset, and name the worst case you are accepting.
Own the tradeoff at the system level: removing a metadata dependency from a hot read path, against the ongoing cost of maintaining a sparse index that would make the search question irrelevant.
## Fix the cost model first The textbook analysis of any search counts comparisons. On a remote, paged, replicated log that model is wrong by orders of magnitude: comparing two timestamps is free, and fetching the page that holds an entry is a network round trip plus possibly a disk read. The unit that matters is **probes**, and a senior answer starts by saying so. Everything below counts probes. ## The two candidate designs **A: size query plus binary search.** Ask the log how many entries it has, then binary search `[0, n)`. Cost: one metadata round trip plus about `log2(n)` probes. Requires the size to exist as an answerable question. **B: galloping (exponential search).** Probe 1, 2, 4, 8 ... until you pass the target or fall off the end, then binary search the last bracket. Cost: about `2 log2(i)` probes, where `i` is the answer's position. Requires nothing but ordered reads and a defined past-the-end answer. ## What actually decides it **Is the size cheap, exact and current?** On a single local sorted block, yes — take design A. On a replicated log the count may require asking a leader (a coordination point on what was a pure follower read), may be stale by the time you use it (an entry appended between the size query and the search is invisible to A but reachable by B), or may not be exposed at all. A search that never needs the size has one fewer dependency and one fewer failure mode, and that architectural simplification is often worth more than the probe arithmetic. **Where do targets land?** This is the measurement that settles the probe count. For a tailing feature — "stream me everything since timestamp T" issued repeatedly with a recent T — the answer sits close to the last position the caller read, so `i` measured from that offset is tiny and galloping resolves in single-digit probes. For an analytical backfill scanning from an old timestamp, `i` is close to `n` and B costs about `2 log2(n)` against A's `log2(n) + 1`. On a log with a billion entries that is roughly 60 probes versus 31 — at a few milliseconds each, a difference you will see in a p99. **Is the caller resuming from a known offset?** If so, gallop *relative to that offset*, not from index 1. That is the single highest-leverage adjustment: it makes `i` the distance travelled since the last read rather than the absolute position, which is exactly the quantity a tailing workload keeps small. ## The things that quietly change the arithmetic - **Page granularity.** If one fetch returns a page of many entries, the first probes of the doubling phase may all be served from a single page, and the effective probe count drops below the naive count. Aligning probes to page boundaries is worth more than shaving a doubling step. - **Caching and prefetch.** Repeated tailing queries touch overlapping regions; a warm cache makes early probes nearly free and shifts the balance further toward galloping. - **Concurrent appends.** The log grows during the search. Galloping tolerates this naturally — a probe that used to hit the sentinel may now return an entry — while a size captured once at the start of design A is immediately stale. - **A coarse index changes everything.** If the log can expose a sparse timestamp-to-offset map, both designs become a lookup plus a short local search, and this whole comparison shrinks to a footnote. Ask whether that index is cheap to build before optimising the search. ## How to justify the choice State the decision as a measurement, not a preference: instrument the position distribution of real queries and the true cost of the size call, then pick. Present galloping as the default when the size is a dependency you would rather not have, and be honest that its worst case is about twice a plain binary search. If you cannot measure, prefer the design with fewer dependencies — it is the one that keeps working when the metadata path degrades. ## The failure signal to watch If probe counts per query trend toward `2 log2(n)`, targets have stopped clustering near the head and galloping is now paying its penalty for a benefit you are no longer getting. That is the metric to alert on, and it is more informative than latency alone, because it tells you *why* the latency moved.
- The caller already knows the offset it last read. How does that change the design?Gallop relative to that offset instead of from index 1. The cost then tracks the distance travelled since the last read rather than the absolute position, which for a repeated tailing query is small and roughly constant. It is the highest-leverage change available and it costs nothing structurally.
- What metric tells you galloping has stopped being the right choice?Probes per query trending toward twice the logarithm of the log size. That means targets no longer cluster near the head, so you are paying the factor-of-two penalty without the position-based benefit. It is a better alarm than latency alone because it identifies the cause rather than the symptom.
- Does concurrent appending to the log break either approach?It weakens the size-query approach: the count is captured once and is stale immediately, so entries appended during the search are invisible. Galloping degrades gracefully — a probe that previously hit the past-the-end sentinel simply returns an entry on a later attempt, and the predicate stays monotone throughout.
- Why not just build a timestamp-to-offset index and stop arguing?Often the right answer, and worth raising. A sparse index turns both designs into a lookup plus a short local search. The counterweights are the write-path cost, the storage, and one more structure to keep consistent with a replicated log — so the question becomes whether query volume justifies that ongoing maintenance.
saying these in an interview costs you the question
- Counts comparisons when every probe is a network round trip
- Assumes a size query is free and always accurate
- Claims galloping is universally faster than binary search
- Ignores that targets may cluster near the head
- Never mentions measuring where queries actually land