Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Filtered streams: the same policy at every tier is wrong

The filtered-stream result: the same policy at every tier is wrong

Lower tiers do not see the workload. They see the misses of the tier above: the original stream with every short-reuse-distance access removed.

The consequences are structural.

  • Every access reaching tier 2 has ≥ C₁ (the size of tier 1) by construction. The head of the locality distribution has already been consumed by tier 1.
  • The remaining stream carries (1 − h₁) of the volume but nearly all of the distinct items. Accesses per item collapse, and the stream flattens towards the independent reference model with its peak removed.
  • Recency, the strongest signal at tier 1, is a weak signal at tier 2. Frequency is the right signal low in a hierarchy; recency is the right signal high in it.

Illustration. Tier 1 serves 1,000,000 requests with h₁ = 80%. Tier 2 receives 200,000 requests, but those include almost every rarely used key that appeared at all. The keys that repeat quickly were all absorbed above. What repeats at tier 2 repeats because the key is popular, not because it was used a moment ago.

This explains a piece of history that otherwise looks like fashion in policies. LRU-K, 2Q and ARC were all designed for buffer pools that sit beneath an application, and often beneath an operating-system page . Those are filtered streams. Their common move is to add a frequency dimension that plain lacks. It also gives a testable prediction: a cache's correct policy is determined by its position in the hierarchy, not by its implementation. Copying an eviction setting from your Redis tier to your SSD tier is a category error, specifically an error towards over-weighting recency.

It also explains a measurement trap. The aggregate across tiers says nothing about which tier earned its place, because tier 2's achievable hit rate on a filtered stream is far below what an unfiltered stream of the same size would give. Measure per-tier hit rate against per-tier stream, or the numbers will justify the wrong tier.

In one sentence: tier n+1 sees tier n's misses, so locality is already spent; frequency wins low and recency wins high; position picks the policy, not the product.