/** Seconds to keep lock keys around */
const LOCK_TTL = 10;
+ /** Seconds to no-op key set() calls to avoid large blob I/O stampedes */
+ const COOLOFF_TTL = 1;
/** Default remaining TTL at which to consider pre-emptive regeneration */
const LOW_TTL = 30;
/** Tiny negative float to use when CTL comes up >= 0 due to clock skew */
const TINY_NEGATIVE = -0.000001;
+ /** Seconds of delay after get() where set() storms are a consideration with 'lockTSE' */
+ const SET_DELAY_HIGH_SEC = 0.1;
+
/** Cache format version number */
const VERSION = 1;
const FLD_VALUE = 1; // key to the cached value
const FLD_TTL = 2; // key to the original TTL
const FLD_TIME = 3; // key to the cache time
- const FLD_FLAGS = 4; // key to the flags bitfield
+ const FLD_FLAGS = 4; // key to the flags bitfield (reserved number)
const FLD_HOLDOFF = 5; // key to any hold-off TTL
- /** @var int Treat this value as expired-on-arrival */
- const FLG_STALE = 1;
-
const ERR_NONE = 0; // no error
const ERR_NO_RESPONSE = 1; // no response
const ERR_UNREACHABLE = 2; // can't connect
const INTERIM_KEY_PREFIX = 'WANCache:i:';
const TIME_KEY_PREFIX = 'WANCache:t:';
const MUTEX_KEY_PREFIX = 'WANCache:m:';
+ const COOLOFF_KEY_PREFIX = 'WANCache:c:';
const PURGE_VAL_PREFIX = 'PURGED:';
// Do not cache potentially uncommitted data as it might get rolled back
if ( !empty( $opts['pending'] ) ) {
- $this->logger->info( 'Rejected set() for {cachekey} due to pending writes.',
- [ 'cachekey' => $key ] );
+ $this->logger->info(
+ 'Rejected set() for {cachekey} due to pending writes.',
+ [ 'cachekey' => $key ]
+ );
return true; // no-op the write for being unsafe
}
- $wrapExtra = []; // additional wrapped value fields
+ $logicalTTL = null; // logical TTL override
// Check if there's a risk of writing stale data after the purge tombstone expired
if ( $lag === false || ( $lag + $age ) > self::MAX_READ_LAG ) {
- // Case A: read lag with "lockTSE"; save but record value as stale
- if ( $lockTSE >= 0 ) {
- $ttl = max( 1, (int)$lockTSE ); // set() expects seconds
- $wrapExtra[self::FLD_FLAGS] = self::FLG_STALE; // mark as stale
- // Case B: any long-running transaction; ignore this set()
- } elseif ( $age > self::MAX_READ_LAG ) {
- $this->logger->info( 'Rejected set() for {cachekey} due to snapshot lag.',
- [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ] );
-
- return true; // no-op the write for being unsafe
- // Case C: high replication lag; lower TTL instead of ignoring all set()s
+ // Case A: any long-running transaction
+ if ( $age > self::MAX_READ_LAG ) {
+ if ( $lockTSE >= 0 ) {
+ // Store value as *almost* stale to avoid cache and mutex stampedes
+ $logicalTTL = self::TTL_SECOND;
+ $this->logger->info(
+ 'Lowered set() TTL for {cachekey} due to snapshot lag.',
+ [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ]
+ );
+ } else {
+ $this->logger->info(
+ 'Rejected set() for {cachekey} due to snapshot lag.',
+ [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ]
+ );
+
+ return true; // no-op the write for being unsafe
+ }
+ // Case B: high replication lag; lower TTL instead of ignoring all set()s
} elseif ( $lag === false || $lag > self::MAX_READ_LAG ) {
- $ttl = $ttl ? min( $ttl, self::TTL_LAGGED ) : self::TTL_LAGGED;
- $this->logger->warning( 'Lowered set() TTL for {cachekey} due to replication lag.',
- [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ] );
- // Case D: medium length request with medium replication lag; ignore this set()
+ if ( $lockTSE >= 0 ) {
+ $logicalTTL = min( $ttl ?: INF, self::TTL_LAGGED );
+ } else {
+ $ttl = min( $ttl ?: INF, self::TTL_LAGGED );
+ }
+ $this->logger->warning(
+ 'Lowered set() TTL for {cachekey} due to replication lag.',
+ [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ]
+ );
+ // Case C: medium length request with medium replication lag
} else {
- $this->logger->info( 'Rejected set() for {cachekey} due to high read lag.',
- [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ] );
+ if ( $lockTSE >= 0 ) {
+ // Store value as *almost* stale to avoid cache and mutex stampedes
+ $logicalTTL = self::TTL_SECOND;
+ $this->logger->info(
+ 'Lowered set() TTL for {cachekey} due to high read lag.',
+ [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ]
+ );
+ } else {
+ $this->logger->info(
+ 'Rejected set() for {cachekey} due to high read lag.',
+ [ 'cachekey' => $key, 'lag' => $lag, 'age' => $age ]
+ );
- return true; // no-op the write for being unsafe
+ return true; // no-op the write for being unsafe
+ }
}
}
// Wrap that value with time/TTL/version metadata
- $wrapped = $this->wrap( $value, $ttl, $now ) + $wrapExtra;
+ $wrapped = $this->wrap( $value, $logicalTTL ?: $ttl, $now );
$func = function ( $cache, $key, $cWrapped ) use ( $wrapped ) {
return ( is_string( $cWrapped ) )
* is useful if thousands or millions of keys depend on the same entity. The entity can
* simply have its "check" key updated whenever the entity is modified.
* Default: [].
- * - graceTTL: If the key is invalidated (by "checkKeys") less than this many seconds ago,
- * consider reusing the stale value. The odds of a refresh becomes more likely over time,
- * becoming certain once the grace period is reached. This can reduce traffic spikes
- * when millions of keys are compared to the same "check" key and touchCheckKey() or
- * resetCheckKey() is called on that "check" key. This option is not useful for the
- * case of the key simply expiring on account of its TTL (use "lowTTL" instead).
+ * - graceTTL: If the key is invalidated (by "checkKeys"/"touchedCallback") less than this
+ * many seconds ago, consider reusing the stale value. The odds of a refresh becomes
+ * more likely over time, becoming certain once the grace period is reached. This can
+ * reduce traffic spikes when millions of keys are compared to the same "check" key and
+ * touchCheckKey() or resetCheckKey() is called on that "check" key. This option is not
+ * useful for avoiding traffic spikes in the case of the key simply expiring on account
+ * of its TTL (use "lowTTL" instead).
* Default: WANObjectCache::GRACE_TTL_NONE.
- * - lockTSE: If the key is tombstoned or invalidated (by "checkKeys") less than this many
- * seconds ago, try to have a single thread handle cache regeneration at any given time.
- * Other threads will try to use stale values if possible. If, on miss, the time since
- * expiration is low, the assumption is that the key is hot and that a stampede is worth
- * avoiding. Setting this above WANObjectCache::HOLDOFF_TTL makes no difference. The
- * higher this is set, the higher the worst-case staleness can be. This option does not
- * by itself handle the case of the key simply expiring on account of its TTL, so make
- * sure that "lowTTL" is not disabled when using this option.
+ * - lockTSE: If the key is tombstoned or invalidated (by "checkKeys"/"touchedCallback")
+ * less than this many seconds ago, try to have a single thread handle cache regeneration
+ * at any given time. Other threads will use stale values if possible. If, on miss,
+ * the time since expiration is low, the assumption is that the key is hot and that a
+ * stampede is worth avoiding. Note that if the key falls out of cache then concurrent
+ * threads will all run the callback on cache miss until the value is saved in cache.
+ * The only stampede protection in that case is from duplicate cache sets when the
+ * callback takes longer than WANObjectCache::SET_DELAY_HIGH_SEC seconds; consider
+ * using "busyValue" if such stampedes are a problem. Note that the higher "lockTSE" is
+ * set, the higher the worst-case staleness of returned values can be. Also note that
+ * this option does not by itself handle the case of the key simply expiring on account
+ * of its TTL, so make sure that "lowTTL" is not disabled when using this option. Avoid
+ * combining this option with delete() as it can always cause a stampede due to their
+ * being no stale value available until after a thread completes the callback.
* Use WANObjectCache::TSE_NONE to disable this logic.
* Default: WANObjectCache::TSE_NONE.
* - busyValue: If no value exists and another thread is currently regenerating it, use this
$minTime = $opts['minAsOf'] ?? self::MIN_TIMESTAMP_NONE;
$versioned = isset( $opts['version'] );
$touchedCallback = $opts['touchedCallback'] ?? null;
+ $initialTime = $this->getCurrentTime();
// Get a collection name to describe this class of key
$kClass = $this->determineKeyClass( $key );
- // Get the current key value
+ // Get the current key value and populate $curTTL and $asOf accordingly
$curTTL = null;
$cValue = $this->get( $key, $curTTL, $checkKeys, $asOf ); // current value
$value = $cValue; // return value
-
// Apply additional dynamic expiration logic if supplied
$curTTL = $this->applyTouchedCallback( $value, $asOf, $curTTL, $touchedCallback );
- $preCallbackTime = $this->getCurrentTime();
// Determine if a cached value regeneration is needed or desired
if (
$this->isValid( $value, $versioned, $asOf, $minTime ) &&
) {
$preemptiveRefresh = (
$this->worthRefreshExpiring( $curTTL, $lowTTL ) ||
- $this->worthRefreshPopular( $asOf, $ageNew, $popWindow, $preCallbackTime )
+ $this->worthRefreshPopular( $asOf, $ageNew, $popWindow, $initialTime )
);
if ( !$preemptiveRefresh ) {
$this->stats->increment( "wanobjectcache.$kClass.hit.good" );
return $value;
- } elseif ( $this->asyncHandler ) {
- // Update the cache value later, such during post-send of an HTTP request
- $func = $this->asyncHandler;
- $func( function () use ( $key, $ttl, $callback, $opts, $asOf ) {
- $opts['minAsOf'] = INF; // force a refresh
- $this->doGetWithSetCallback( $key, $ttl, $callback, $opts, $asOf );
- } );
+ } elseif ( $this->scheduleAsyncRefresh( $key, $ttl, $callback, $opts ) ) {
$this->stats->increment( "wanobjectcache.$kClass.hit.refresh" );
return $value;
// Decide if only one thread should handle regeneration at a time
$useMutex =
// Note that since tombstones no-op set(), $lockTSE and $curTTL cannot be used to
- // deduce the key hotness because $curTTL will always keep increasing until the
+ // deduce the key hotness because |$curTTL| will always keep increasing until the
// tombstone expires or is overwritten by a new tombstone. Also, even if $lockTSE
// is not set, constant regeneration of a key for the tombstone lifetime might be
// very expensive. Assume tombstoned keys are possibly hot in order to reduce
// This avoids stampedes on eviction or preemptive regeneration taking too long.
( $busyValue !== null && $value === false );
- $lockAcquired = false;
+ $hasLock = false;
if ( $useMutex ) {
// Acquire a datacenter-local non-blocking lock
if ( $this->cache->add( self::MUTEX_KEY_PREFIX . $key, 1, self::LOCK_TTL ) ) {
// Lock acquired; this thread will recompute the value and update cache
- $lockAcquired = true;
+ $hasLock = true;
} elseif ( $this->isValid( $value, $versioned, $asOf, $minTime ) ) {
// Lock not acquired and a stale value exists; use the stale value
$this->stats->increment( "wanobjectcache.$kClass.hit.stale" );
throw new InvalidArgumentException( "Invalid cache miss callback provided." );
}
+ $preCallbackTime = $this->getCurrentTime();
// Generate the new value from the callback...
$setOpts = [];
++$this->callbackDepth;
$valueIsCacheable = ( $value !== false && $ttl >= 0 );
if ( $valueIsCacheable ) {
+ $ago = max( $this->getCurrentTime() - $initialTime, 0.0 );
+ $this->stats->timing( "wanobjectcache.$kClass.regen_set_delay", 1000 * $ago );
+
if ( $isKeyTombstoned ) {
- // When delete() is called, writes are write-holed by the tombstone,
- // so use a special INTERIM key to pass the new value among threads.
- $tempTTL = max( self::INTERIM_KEY_TTL, (int)$lockTSE ); // set() expects seconds
- $newAsOf = $this->getCurrentTime();
- $wrapped = $this->wrap( $value, $tempTTL, $newAsOf );
- // Avoid using set() to avoid pointless mcrouter broadcasting
- $this->setInterimValue( $key, $wrapped, $tempTTL );
- } elseif ( !$useMutex || $lockAcquired ) {
- // Save the value unless a lock-winning thread is already expected to do that
- $setOpts['lockTSE'] = $lockTSE;
- $setOpts['staleTTL'] = $staleTTL;
- // Use best known "since" timestamp if not provided
- $setOpts += [ 'since' => $preCallbackTime ];
- // Update the cache; this will fail if the key is tombstoned
- $this->set( $key, $value, $ttl, $setOpts );
+ if ( $this->checkAndSetCooloff( $key, $kClass, $ago, $lockTSE, $hasLock ) ) {
+ // When delete() is called, writes are write-holed by the tombstone,
+ // so use a special INTERIM key to pass the new value among threads.
+ $tempTTL = max( self::INTERIM_KEY_TTL, (int)$lockTSE ); // set() expects seconds
+ $newAsOf = $this->getCurrentTime();
+ $wrapped = $this->wrap( $value, $tempTTL, $newAsOf );
+ // Avoid using set() to avoid pointless mcrouter broadcasting
+ $this->setInterimValue( $key, $wrapped, $tempTTL );
+ }
+ } elseif ( !$useMutex || $hasLock ) {
+ if ( $this->checkAndSetCooloff( $key, $kClass, $ago, $lockTSE, $hasLock ) ) {
+ // Save the value unless a lock-winning thread is already expected to do that
+ $setOpts['lockTSE'] = $lockTSE;
+ $setOpts['staleTTL'] = $staleTTL;
+ // Use best known "since" timestamp if not provided
+ $setOpts += [ 'since' => $preCallbackTime ];
+ // Update the cache; this will fail if the key is tombstoned
+ $this->set( $key, $value, $ttl, $setOpts );
+ }
}
}
- if ( $lockAcquired ) {
+ if ( $hasLock ) {
// Avoid using delete() to avoid pointless mcrouter broadcasting
- $this->cache->changeTTL( self::MUTEX_KEY_PREFIX . $key, (int)$preCallbackTime - 60 );
+ $this->cache->changeTTL( self::MUTEX_KEY_PREFIX . $key, (int)$initialTime - 60 );
}
$miss = is_infinite( $minTime ) ? 'renew' : 'miss';
return $value;
}
+ /**
+ * @param string $key
+ * @param string $kClass
+ * @param float $elapsed Seconds spent regenerating the value
+ * @param float $lockTSE
+ * @param $hasLock bool
+ * @return bool Whether it is OK to proceed with a key set operation
+ */
+ private function checkAndSetCooloff( $key, $kClass, $elapsed, $lockTSE, $hasLock ) {
+ // If $lockTSE is set, the lock was bypassed because there was no stale/interim value,
+ // and $elapsed indicates that regeration is slow, then there is a risk of set()
+ // stampedes with large blobs. With a typical scale-out infrastructure, CPU and query
+ // load from $callback invocations is distributed among appservers and replica DBs,
+ // but cache operations for a given key route to a single cache server (e.g. striped
+ // consistent hashing).
+ if ( $lockTSE < 0 || $hasLock ) {
+ return true; // either not a priori hot or thread has the lock
+ } elseif ( $elapsed <= self::SET_DELAY_HIGH_SEC ) {
+ return true; // not enough time for threads to pile up
+ }
+
+ $this->cache->clearLastError();
+ if (
+ !$this->cache->add( self::COOLOFF_KEY_PREFIX . $key, 1, self::COOLOFF_TTL ) &&
+ // Don't treat failures due to I/O errors as the key being in cooloff
+ $this->cache->getLastError() === BagOStuff::ERR_NONE
+ ) {
+ $this->stats->increment( "wanobjectcache.$kClass.cooloff_bounce" );
+
+ return false;
+ }
+
+ return true;
+ }
+
/**
* @param mixed $value
* @param float $asOf
return $ok;
}
+ /**
+ * @param string $key
+ * @param int $ttl
+ * @param callable $callback
+ * @param array $opts
+ * @return bool Success
+ */
+ private function scheduleAsyncRefresh( $key, $ttl, $callback, $opts ) {
+ if ( !$this->asyncHandler ) {
+ return false;
+ }
+ // Update the cache value later, such during post-send of an HTTP request
+ $func = $this->asyncHandler;
+ $func( function () use ( $key, $ttl, $callback, $opts ) {
+ $asOf = null; // unused
+ $opts['minAsOf'] = INF; // force a refresh
+ $this->doGetWithSetCallback( $key, $ttl, $callback, $opts, $asOf );
+ } );
+
+ return true;
+ }
+
/**
* Check if a key is fresh or in the grace window and thus due for randomized reuse
*
return [ false, null ];
}
- $flags = $wrapped[self::FLD_FLAGS] ?? 0;
- if ( ( $flags & self::FLG_STALE ) == self::FLG_STALE ) {
- // Treat as expired, with the cache time as the expiration
- $age = $now - $wrapped[self::FLD_TIME];
- $curTTL = min( -$age, self::TINY_NEGATIVE );
- } elseif ( $wrapped[self::FLD_TTL] > 0 ) {
+ if ( $wrapped[self::FLD_TTL] > 0 ) {
// Get the approximate time left on the key
$age = $now - $wrapped[self::FLD_TIME];
$curTTL = max( $wrapped[self::FLD_TTL] - $age, 0.0 );