Power laws and skew
What it is
Assume Zipf: the item of rank i gets frequency proportional to i^(−α). The cumulative share of traffic carried by the top C of N items falls into three different regimes. The border between them is a genuine phase transition (a sharp change of behavior), not a matter of degree.
α = 1. The harmonic sum (1 + 1/2 + 1/3 + …) grows like a logarithm, so h ≈ ln C / ln N and C ≈ N^h. Each point of hit rate costs a constant multiplicative factor in cache size. For N = 10⁹, ten points cost about 8× the cache, at every point on the curve: 50%→60% and 85%→95% cost the same multiple.
α < 1 (flatter). This is typical of web objects (0.6–0.8) and of query shapes in analytics, even where table popularity is steeper. The sum grows like C^(1−α), so h ≈ (C/N)^(1−α).
At α = 0.8, h ≈ (C/N)^0.2.
- For h = 50%: C/N = 0.5^(1/0.2) = 0.5⁵ = 0.03125, about 3% of the corpus.
- For h = 90%: C/N = 0.9⁵ ≈ 59% of the corpus.
At that point you are no longer caching. You are replicating.
α > 1. The infinite sum of i^(−α) converges to a finite number. Therefore the number of items needed for a given hit rate depends only on h and α, not on N at all. The cache does not need to grow when your data grows.
From Caching › The popularity exponent
Every family hides a power-law distribution: Zipfian terms in text, power-law vertex degree in graphs, clustered spatial density in maps, hot series labels in metrics. So variance, not volume, sets each one's worst case.
From Specialized Processing Models › Earning its own system
Where it appears
In 8 mechanisms. Each says what the mechanism is about, then how this principle shows up there, in its own words.
- Data Movement
How do records cross between two systems that have independent rates, independent availability and independent lifetimes, and what are you willing to lose when the assumption underneath the crossing breaks?
Real keys are Zipfian (a few are extremely popular, and the top key alone can be several percent of the volume), so this is the normal case, not an edge case.
Read it inTwo kinds of skew: different problems, different fixes
- Indexing
When does a separate "where is it?" structure pay for itself, and what does it cost to keep it true?
Posting list lengths follow a Zipf distribution: a few terms appear in most documents, and most terms appear in very few.
Read it inSet membership: inverted indexes
- Transactions & Concurrency Control
What happens when many users change the same data at the same time, and how do we keep the result correct?
Real access patterns are skewed (statisticians say Zipfian: a few keys get most of the traffic).
- Query Processing
Why can one question be answered by plans whose costs differ by a factor of ten thousand, and what does each operator force the engine to do?
The same Zipf distribution (a very uneven distribution where a few keys are huge and most are tiny) that caps a distributed join's speedup at 14x makes a hash aggregation's working set small.
Read it inThe output does not grow with the inputSkew: the assumption of uniformity, pricedJoins, aggregates and windows: what each forces
- Execution Engine Runtime
Once a query plan is chosen, why does the machine still sit idle, and what does each mechanism of a query runtime pay to buy that idle time back?
How a join survives a hot key, and the Zipf arithmetic behind how big the hottest key gets, are query processing's; routing a key that outweighs a partition is data movement's.
Read it inWhere parallelism comes from and what bounds itSkew and elasticity
- Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
The problem and its solution are one Zipf fact seen from two ends.
Read it inThe first copy with no obligationA distributed cache is not a latency tierThe popularity exponent and the phase transition at α = 1Size a cacheConsistent hashing, and the hot key that hashing cannot fix
- Distributed Systems Coordination
Who is allowed to decide, and how does everyone else learn the decision without asking?
The same fact appears in several settings: a single grouping key larger than memory that recursive repartitioning cannot rescue; the head of a Zipf distribution that consistent hashing cannot split; and here, the hot partition that no increase in P fixes.
Read it inPartitioning and the partition count
- Specialized Processing Models
What do you build when a query predicate cannot be reduced to a range over an ordered key?
You cannot balance-partition a power-law graph without cutting most edges.
Read it inProperty graph versus RDF, and what graph forbidsTraversal and degree skewFinding is cheap, scoring is the cost; the inverted indexWhen does a workload earn its own system?
Related
Made on the same pages most often.