Tail at scale

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• 16 shards at 1% each → ≈ 15% of queries slowed
• scatter-gather over 40 shards → ≈ 33%
• waiting for all 5 → 4.9%
• 100 workers at a barrier → all fast only 36.6% of rounds
• 100 backends each at p99 → only ≈ 37% of requests see no slow one
• p = 0.01, N = 100 → 63%

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Physical Substrate & Performance Laws

  Why do trade-offs exist at all?

  $$P(\text{slow})=1-(1-p{)}^N$$

  Read it in place →

• Indexing

  When does a separate "where is it?" structure pay for itself, and what does it cost to keep it true?

  $$1-0.99^{16}\approx 15\%$$

  16 shards = $N$ · 0.01 = $p$

  Read it in place →

• Distributed Systems Coordination

  Who is allowed to decide, and how does everyone else learn the decision without asking?

  $$1-0.99^{40}\approx 33\%$$

  Read it in place →

• Specialized Processing Models

  What do you build when a query predicate cannot be reduced to a range over an ordered key?

  $$1-0.99^{100}\approx 63\%$$

  Read it in place →