Class: SafeMemoize::Stores::XFetch

Inherits:
Base
  • Object
show all
Defined in:
lib/safe_memoize/stores/xfetch.rb

Overview

Wraps any Base store adapter with probabilistic early expiry (the XFetch algorithm) to prevent cache stampedes — the thundering-herd problem where many processes simultaneously recompute a value the moment it expires under high load.

Instead of waiting until #read returns Base::MISS at the hard expiry deadline, the wrapper stochastically returns Base::MISS slightly before expiry, giving one process a head start on recomputation while everyone else still gets the cached value. The probability of early expiry rises as the entry approaches its deadline.

=== XFetch formula

early_expire = now − (delta × beta × log(rand)) ≥ expires_at

  • +delta+ — estimated computation time in seconds (default 0.1 s). Configure this to the typical duration of the underlying computation.
  • +beta+ — aggressiveness scalar (default 1.0); higher values trigger early recomputation more eagerly.

Values are stored internally as an envelope +expires_at:+ so the wrapper always knows the hard deadline regardless of what the inner store exposes on read. The envelope survives standard Ruby Marshal serialization (Redis via the +redis-store+ or +redis-client+ gems, Rails.cache, etc.). Values that cannot be serialized alongside a small hash are not supported.

Examples:

Wrap a Redis store

store = SafeMemoize::Stores::XFetch.new(
  MyRedisStore.new,
  delta: 0.2,   # typical computation time in seconds
  beta:  1.5    # slightly aggressive early expiry
)
memoize :fetch, store: store, ttl: 300

Compose with CircuitBreaker

store = SafeMemoize::Stores::XFetch.new(
  SafeMemoize::Stores::CircuitBreaker.new(MyRedisStore.new),
  delta: 0.1
)
memoize :fetch, store: store, ttl: 60

Constant Summary collapse

ENVELOPE_KEY = 
:__sm_xfetch_v1__
DEFAULT_BETA = 
1.0
DEFAULT_DELTA = 
0.1

Constants inherited from Base

Base::MISS

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods inherited from Base

#exist?

Constructor Details

#initialize(store, beta: DEFAULT_BETA, delta: DEFAULT_DELTA) ⇒ XFetch

Returns a new instance of XFetch.

Parameters:

  • store (Stores::Base) —

    the backing store to wrap

  • beta (Numeric) (defaults to: DEFAULT_BETA) —

    aggressiveness scalar (default 1.0)

  • delta (Numeric) (defaults to: DEFAULT_DELTA) —

    estimated computation time in seconds (default 0.1)

Raises:

  • (ArgumentError) —

    if +store+ is not a Base instance, or if +beta+/+delta+ are not positive numbers



64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 64

def initialize(store, beta: DEFAULT_BETA, delta: DEFAULT_DELTA)
  unless store.is_a?(Base)
    raise ArgumentError, "XFetch requires a Stores::Base instance (got #{store.class})"
  end

  @wrapped_store = store
  @beta = Float(beta)
  @delta = Float(delta)

  raise ArgumentError, "beta must be positive" unless @beta > 0
  raise ArgumentError, "delta must be positive" unless @delta > 0
end

Instance Attribute Details

#beta ⇒ Float (readonly)

Returns aggressiveness scalar.

Returns:

  • (Float) —

    aggressiveness scalar



55
56
57
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 55

def beta
  @beta
end

#delta ⇒ Float (readonly)

Returns estimated computation time in seconds.

Returns:

  • (Float) —

    estimated computation time in seconds



57
58
59
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 57

def delta
  @delta
end

#wrapped_store ⇒ Stores::Base (readonly)

Returns the wrapped inner store.

Returns:



53
54
55
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 53

def wrapped_store
  @wrapped_store
end

Instance Method Details

#clear ⇒ Object

Clear the wrapped store.



113
114
115
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 113

def clear
  @wrapped_store.clear
end

#delete(key) ⇒ Object

Delete from the wrapped store.



108
109
110
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 108

def delete(key)
  @wrapped_store.delete(key)
end

#keys ⇒ Object

Returns live keys from the wrapped store.



118
119
120
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 118

def keys
  @wrapped_store.keys
end

#read(key) ⇒ Object

Read from the wrapped store and apply the XFetch probabilistic check.

Returns Base::MISS when:

  • the inner store has no entry for +key+
  • the stored value is not an XFetch envelope (possibly written by an older version or a different store wrapper)
  • the XFetch formula triggers early expiry


84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 84

def read(key)
  raw = @wrapped_store.read(key)
  return MISS if raw.equal?(MISS)
  return MISS unless envelope?(raw)

  expires_at = raw[:expires_at]

  if expires_at
    now = Process.clock_gettime(Process::CLOCK_MONOTONIC)
    early = now - @delta * @beta * Math.log(rand) >= expires_at
    return MISS if early
  end

  raw[:value]
end

#write(key, value, expires_in: nil) ⇒ Object

Write the value to the wrapped store inside an XFetch envelope.



101
102
103
104
105
 
# File 'lib/safe_memoize/stores/xfetch.rb', line 101

def write(key, value, expires_in: nil)
  expires_at = expires_in ? Process.clock_gettime(Process::CLOCK_MONOTONIC) + expires_in.to_f : nil
  envelope = {ENVELOPE_KEY => true, :value => value, :expires_at => expires_at}
  @wrapped_store.write(key, envelope, expires_in: expires_in)
end