The square-root rule

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.

• IVF: N = 10⁸, nprobe = 1 → nlist ≈ 10,000
• cost ≈ 20,000 comparisons instead of 10⁸
• nprobe = 16 → nlist ≈ 40,000
• partitions: P = 50 → 250
• partitions: P = 100 → 200
• partitions: P = 200 → 250
• C = 30 s, MTBF = 1 day → I* ≈ 2,277 s (38 min)
• overhead at I* ≈ 2.6%
• spot: τ = 30 min, M = 6 h → ≈ 4.2% lost work
• C = 1,800 s, r = 0.25 → T* = 120 hours
• four times the writes → only half the interval (60 h)
• fsync 1 ms, λ = 10,000 commits/s → W* ≈ 0.45 ms
• cost per commit at W* ≈ 0.22 ms + 0.22 ms ≈ 0.45 ms

Where it appears

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

• Persistence & Durability

  When a system says "yes, your data is safe", what exactly has it promised, and what did it have to do to keep that promise?

  $$\frac{\text{fsync}}{\lambda W}+\frac{W}{2},W^{\ast }=\sqrt{\frac{2\cdot \text{fsync}}{\lambda }}$$

  W (wait before the flush) = $x$ · fsync ÷ λ (fsync share) = $b$ · 1/2 (average wait) = $a$

  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?

  $$\text{cost}=\text{nlist}+\frac{N\cdot \text{nprobe}}{\text{nlist}},\text{nlist}\approx \sqrt{N\cdot \text{nprobe}}$$

  nlist (centroids) = $x$ · N · nprobe (vectors compared in probed cells) = $b$ · 1 (per centroid) = $a$

  Read it in place →

• Distributed Systems Coordination

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

  $$\text{cost}(P)=fP+\frac{c}{P},P^{\ast }=\sqrt{c/f}$$

  P (partitions) = $x$ · f (fixed cost per partition) = $a$ · c (imbalance) = $b$

  Read it in place →

• Fault Tolerance & Delivery Semantics

  What is the cheapest thing that can be safely done twice?

  $$\text{overhead}\approx \frac{C}{I}+\frac{I}{2\cdot \text{MTBF}},I^{\ast }=\sqrt{2\cdot C\cdot \text{MTBF}}$$

  I (checkpoint interval) = $x$ · C (cost of one checkpoint) = $b$ · 1 / (2·MTBF) (lost work per unit interval) = $a$

  Read it in place →

• Scheduling & Workload Management

  Which work runs now, which work waits, and who pays for the waiting?

  $$\text{overhead}\approx \frac{\tau }{2M}$$

  τ (checkpoint interval) = $x$ · 1/(2M) (lost work per unit interval) = $a$

  Read it in place →

• Table & Storage Maintenance

  Who pays for the gap between the order data arrives in and the order it is read in: the writer, every reader, or a background job, and what is the break-even?

  $$\frac{C}{T}+\frac{rT}{2},T^{\ast }=\sqrt{\frac{2C}{r}}$$

  T (interval) = $x$ · C (one rewrite) = $b$ · r/2 (degradation) = $a$

  Read it in place →