8000 feature #27009 [Cache] Add stampede protection via probabilistic earl… · symfony/symfony@7e3b7b0 · GitHub
[go: up one dir, main page]
Skip to content

Commit 7e3b7b0

Browse files
fabpotfabpot
committed
feature #27009 [Cache] Add stampede protection via probabilistic early expiration (nicolas-grekas)
This PR was merged into the 4.2-dev branch. Discussion ---------- [Cache] Add stampede protection via probabilistic early expiration | Q | A | ------------- | --- | Branch? | master | Bug fix? | no | New feature? | yes | BC breaks? | no | Deprecations? | yes | Tests pass? | yes | Fixed tickets | - | License | MIT | Doc PR | This PR implements [probabilistic early expiration](https://en.wikipedia.org/wiki/Cache_stampede#Probabilistic_early_expiration) on top of `$cache->get($key, $callback);` It adds a 3rd arg to `CacheInterface::get`: > float $beta A float that controls the likelyness of triggering early expiration. 0 disables it, INF forces immediate expiration. The default is implementation dependend but should typically be 1.0, which should provide optimal stampede protection. Commits ------- 13523ad [Cache] Add stampede protection via probabilistic early expiration
2 parents 84ada0c + 13523ad commit 7e3b7b0

20 files changed

+254
-43
lines changed

‎UPGRADE-4.2.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
11
UPGRADE FROM 4.1 to 4.2
22
=======================
33

4+
Cache
5+
-----
6+
7+
* Deprecated `CacheItem::getPreviousTags()`, use `CacheItem::getMetadata()` instead.
8+
49
Security
510
--------
611

‎UPGRADE-5.0.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
11
UPGRADE FROM 4.x to 5.0
22
=======================
33

4+
Cache
5+
-----
6+
7+
* Removed `CacheItem::getPreviousTags()`, use `CacheItem::getMetadata()` instead.
8+
49
Config
510
------
611

‎src/Symfony/Component/Cache/Adapter/AbstractAdapter.php‎

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -46,9 +46,18 @@ protected function __construct(string $namespace = '', int $defaultLifetime = 0)
4646
function ($key, $value, $isHit) use ($defaultLifetime) {
4747
$item = new CacheItem();
4848
$item->key = $key;
49-
$item->value = $value;
49+
$item->value = $v = $value;
5050
$item->isHit = $isHit;
5151
$item->defaultLifetime = $defaultLifetime;
52+
// Detect wrapped values that encode for their expiry and creation duration
53+
// For compactness, these values are packed in the key of an array using
54+
// magic numbers in the form 9D-..-..-..-..-00-..-..-..-5F
55+
if (\is_array($v) && 1 === \count($v) && 10 === \strlen($k = \key($v)) && "\x9D" B429 === $k[0] && "\0" === $k[5] && "\x5F" === $k[9]) {
56+
$item->value = $v[$k];
57+
$v = \unpack('Ve/Nc', \substr($k, 1, -1));
58+
$item->metadata[CacheItem::METADATA_EXPIRY] = $v['e'] + CacheItem::METADATA_EXPIRY_OFFSET;
59+
$item->metadata[CacheItem::METADATA_CTIME] = $v['c'];
60+
}
5261

5362
return $item;
5463
},
@@ -64,12 +73,18 @@ function ($deferred, $namespace, &$expiredIds) use ($getId) {
6473

6574
foreach ($deferred as $key => $item) {
6675
if (null === $item->expiry) {
67-
$byLifetime[0 < $item->defaultLifetime ? $item->defaultLifetime : 0][$getId($key)] = $item->value;
76+
$ttl = 0 < $item->defaultLifetime ? $item->defaultLifetime : 0;
6877
} elseif ($item->expiry > $now) {
69-
$byLifetime[$item->expiry - $now][$getId($key)] = $item->value;
78+
$ttl = $item->expiry - $now;
7079
} else {
7180
$expiredIds[] = $getId($key);
81+
continue;
82+
}
83+
if (isset(($metadata = $item->newMetadata)[CacheItem::METADATA_TAGS])) {
84+
unset($metadata[CacheItem::METADATA_TAGS]);
7285
}
86+
// For compactness, expiry and creation duration are packed in the key of a array, using magic numbers as separators
87+
$byLifetime[$ttl][$getId($key)] = $metadata ? array("\x9D".pack('VN', (int) $metadata[CacheItem::METADATA_EXPIRY] - CacheItem::METADATA_EXPIRY_OFFSET, $metadata[CacheItem::METADATA_CTIME])."\x5F" => $item->value) : $item->value;
7388
}
7489

7590
return $byLifetime;

‎src/Symfony/Component/Cache/Adapter/ChainAdapter.php‎

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -64,8 +64,10 @@ function ($sourceItem, $item) use ($defaultLifetime) {
6464
$item->value = $sourceItem->value;
6565
$item->expiry = $sourceItem->expiry;
6666
$item->isHit = $sourceItem->isHit;
67+
$item->metadata = $sourceItem->metadata;
6768

6869
$sourceItem->isTaggable = false;
70+
unset($sourceItem->metadata[CacheItem::METADATA_TAGS]);
6971

7072
if (0 < $sourceItem->defaultLifetime && $sourceItem->defaultLifetime < $defaultLifetime) {
7173
$defaultLifetime = $sourceItem->defaultLifetime;
@@ -84,19 +86,20 @@ function ($sourceItem, $item) use ($defaultLifetime) {
8486
/**
8587
* {@inheritdoc}
8688
*/
87-
public function get(string $key, callable $callback)
89+
public function get(string $key, callable $callback, float $beta = null)
8890
{
8991
$lastItem = null;
9092
$i = 0;
91-
$wrap = function (CacheItem $item = null) use ($key, $callback, &$wrap, &$i, &$lastItem) {
93+
$wrap = function (CacheItem $item = null) use ($key, $callback, $beta, &$wrap, &$i, &$lastItem) {
9294
$adapter = $this->adapters[$i];
9395
if (isset($this->adapters[++$i])) {
9496
$callback = $wrap;
97+
$beta = INF === $beta ? INF : 0;
9598
}
9699
if ($adapter instanceof CacheInterface) {
97-
$value = $adapter->get($key, $callback);
100+
$value = $adapter->get($key, $callback, $beta);
98101
} else {
99-
$value = $this->doGet($adapter, $key, $callback);
102+
$value = $this->doGet($adapter, $key, $callback, $beta ?? 1.0);
100103
}
101104
if (null !== $item) {
102105
($this->syncItem)($lastItem = $lastItem ?? $item, $item);

‎src/Symfony/Component/Cache/Adapter/PhpArrayAdapter.php‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -83,17 +83,17 @@ public static function create($file, CacheItemPoolInterface $fallbackPool)
8383
/**
8484
* {@inheritdoc}
8585
*/
86-
public function get(string $key, callable $callback)
86+
public function get(string $key, callable $callback, float $beta = null)
8787
{
8888
if (null === $this->values) {
8989
$this->initialize();
9090
}
9191
if (null === $value = $this->values[$key] ?? null) {
9292
if ($this->pool instanceof CacheInterface) {
93-
return $this->pool->get($key, $callback);
93+
return $this->pool->get($key, $callback, $beta);
9494
}
9595

96-
return $this->doGet($this->pool, $key, $callback);
96+
return $this->doGet($this->pool, $key, $callback, $beta ?? 1.0);
9797
}
9898
if ('N;' === $value) {
9999
return null;

‎src/Symfony/Component/Cache/Adapter/ProxyAdapter.php‎

Lines changed: 43 additions & 10 deletions
< 5923 tr class="diff-line-row">
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@ class ProxyAdapter implements AdapterInterface, CacheInterface, PruneableInterfa
3131
private $namespace;
3232
private $namespaceLen;
3333
private $createCacheItem;
34+
private $setInnerItem;
3435
private $poolHash;
3536

3637
public function __construct(CacheItemPoolInterface $pool, string $namespace = '', int $defaultLifetime = 0)
@@ -43,32 +44,66 @@ public function __construct(CacheItemPoolInterface $pool, string $namespace = ''
4344
function ($key, $innerItem) use ($defaultLifetime, $poolHash) {
4445
$item = new CacheItem();
4546
$item->key = $key;
46-
$item->value = $innerItem->get();
47+
$item->value = $v = $innerItem->get();
4748
$item->isHit = $innerItem->isHit();
4849
$item->defaultLifetime = $defaultLifetime;
4950
$item->innerItem = $innerItem;
5051
$item->poolHash = $poolHash;
52+ // Detect wrapped values that encode for their expiry and creation duration
53+
// For compactness, these values are packed in the key of an array using
54+
// magic numbers in the form 9D-..-..-..-..-00-..-..-..-5F
55+
if (\is_array($v) && 1 === \count($v) && 10 === \strlen($k = \key($v)) && "\x9D" === $k[0] && "\0" === $k[5] && "\x5F" === $k[9]) {
56+
$item->value = $v[$k];
57+
$v = \unpack('Ve/Nc', \substr($k, 1, -1));
58+
$item->metadata[CacheItem::METADATA_EXPIRY] = $v['e'] + CacheItem::METADATA_EXPIRY_OFFSET;
59+
$item->metadata[CacheItem::METADATA_CTIME] = $v['c'];
60+
} elseif ($innerItem instanceof CacheItem) {
61+
$item->metadata = $innerItem->metadata;
62+
}
5163
$innerItem->set(null);
5264

5365
return $item;
5466
},
5567
null,
5668
CacheItem::class
5769
);
70+
$this->setInnerItem = \Closure::bind(
71+
/**
72+
* @param array $item A CacheItem cast to (array); accessing protected properties requires adding the \0*\0" PHP prefix
73+
*/
74+
function (CacheItemInterface $innerItem, array $item) {
75+
// Tags are stored separately, no need to account for them when considering this item's newly set metadata
76+
if (isset(($metadata = $item["\0*\0newMetadata"])[CacheItem::METADATA_TAGS])) {
77+
unset($metadata[CacheItem::METADATA_TAGS]);
78+
}
79+
if ($metadata) {
80+
// For compactness, expiry and creation duration are packed in the key of a array, using magic numbers as separators
81+
$item["\0*\0value"] = array("\x9D".pack('VN', (int) $metadata[CacheItem::METADATA_EXPIRY] - CacheItem::METADATA_EXPIRY_OFFSET, $metadata[CacheItem::METADATA_CTIME])."\x5F" => $item["\0*\0value"]);
82+
}
83+
$innerItem->set($item["\0*\0value"]);
84+
$innerItem->expiresAt(null !== $item["\0*\0expiry"] ? \DateTime::createFromFormat('U', $item["\0*\0expiry"]) : null);
85+
},
86+
null,
87+
CacheItem::class
88+
);
5889
}
5990

6091
/**
6192
* {@inheritdoc}
6293
*/
63-
public function get(string $key, callable $callback)
94+
public function get(string $key, callable $callback, float $beta = null)
6495
{
6596
if (!$this->pool instanceof CacheInterface) {
66-
return $this->doGet($this->pool, $key, $callback);
97+
return $this->doGet($this, $key, $callback, $beta ?? 1.0);
6798
}
6899

69100
return $this->pool->get($this->getId($key), function ($innerItem) use ($key, $callback) {
70-
return $callback(($this->createCacheItem)($key, $innerItem));
71-
});
101+
$item = ($this->createCacheItem)($key, $innerItem);
102+
$item->set($value = $callback($item));
103+
($this->setInnerItem)($innerItem, (array) $item);
104+
105+
return $value;
106+
}, $beta);
72107
}
73108

74109
/**
@@ -164,13 +199,11 @@ private function doSave(CacheItemInterface $item, $method)
164199
return false;
165200
}
166201
$item = (array) $item;
167-
$expiry = $item["\0*\0expiry"];
168-
if (null === $expiry && 0 < $item["\0*\0defaultLifetime"]) {
169-
$expiry = time() + $item["\0*\0defaultLifetime"];
202+
if (null === $item["\0*\0expiry"] && 0 < $item["\0*\0defaultLifetime"]) {
203+
$item["\0*\0expiry"] = time() + $item["\0*\0defaultLifetime"];
170204
}
171205
$innerItem = $item["\0*\0poolHash"] === $this->poolHash ? $item["\0*\0innerItem"] : $this->pool->getItem($this->namespace.$item["\0*\0key"]);
172-
$innerItem->set($item["\0*\0value"]);
173-
$innerItem->expiresAt(null !== $expiry ? \DateTime::createFromFormat('U', $expiry) : null);
206+
($this->setInnerItem)($innerItem, $item);
174207

175208
return $this->pool->$method($innerItem);
176209
}

‎src/Symfony/Component/Cache/Adapter/TagAwareAdapter.php‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -67,7 +67,7 @@ function (CacheItem $item, $key, array &$itemTags) {
6767
}
6868
if (isset($itemTags[$key])) {
6969
foreach ($itemTags[$key] as $tag => $version) {
70-
$item->prevTags[$tag] = $tag;
70+
B29D $item->metadata[CacheItem::METADATA_TAGS][$tag] = $tag;
7171
}
7272
unset($itemTags[$key]);
7373
} else {
@@ -84,7 +84,7 @@ function (CacheItem $item, $key, array &$itemTags) {
8484
function ($deferred) {
8585
$tagsByKey = array();
8686
foreach ($deferred as $key => $item) {
87-
$tagsByKey[$key] = $item->tags;
87+
$tagsByKey[$key] = $item->newMetadata[CacheItem::METADATA_TAGS] ?? array();
8888
}
8989

9090
return $tagsByKey;

‎src/Symfony/Component/Cache/Adapter/TraceableAdapter.php‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ public function __construct(AdapterInterface $pool)
3737
/**
3838
* {@inheritdoc}
3939
*/
40-
public function get(string $key, callable $callback)
40+
public function get(string $key, callable $callback, float $beta = null)
4141
{
4242
if (!$this->pool instanceof CacheInterface) {
4343
throw new \BadMethodCallException(sprintf('Cannot call "%s::get()": this class doesn\'t implement "%s".', get_class($this->pool), CacheInterface::class));
@@ -52,7 +52,7 @@ public function get(string $key, callable $callback)
5252

5353
$event = $this->start(__FUNCTION__);
5454
try {
55-
$value = $this->pool->get($key, $callback);
55+
$value = $this->pool->get($key, $callback, $beta);
5656
$event->result[$key] = \is_object($value) ? \get_class($value) : gettype($value);
5757
} finally {
5858
$event->end = microtime(true);

‎src/Symfony/Component/Cache/CHANGELOG.md‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,9 @@ CHANGELOG
44
4.2.0
55
-----
66

7-
* added `CacheInterface`, which should become the preferred way to use a cache
7+
* added `CacheInterface`, which provides stampede protection via probabilistic early expiration and should become the preferred way to use a cache
88
* throw `LogicException` when `CacheItem::tag()` is called on an item coming from a non tag-aware pool
9+
* deprecated `CacheItem::getPreviousTags()`, use `CacheItem::getMetadata()` instead
910

1011
3.4.0
1112
-----
@@ -19,7 +20,7 @@ CHANGELOG
1920
3.3.0
2021
-----
2122

22-
* [EXPERIMENTAL] added CacheItem::getPreviousTags() to get bound tags coming from the pool storage if any
23+
* added CacheItem::getPreviousTags() to get bound tags coming from the pool storage if any
2324
* added PSR-16 "Simple Cache" implementations for all existing PSR-6 adapters
2425
* added Psr6Cache and SimpleCacheAdapter for bidirectional interoperability between PSR-6 and PSR-16
2526
* added MemcachedAdapter (PSR-6) and MemcachedCache (PSR-16)

‎src/Symfony/Component/Cache/CacheInterface.php‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,8 +26,12 @@ interface CacheInterface
2626
{
2727
/**
2828
* @param callable(CacheItem):mixed $callback Should return the computed value for the given key/item
29+
* @param float|null $beta A float that controls the likeliness of triggering early expiration.
30+
* 0 disables it, INF forces immediate expiration.
31+
* The default (or providing null) is implementation dependent but should
32+
* typically be 1.0, which should provide optimal stampede protection.
2933
*
3034
* @return mixed The value corresponding to the provided key
3135
*/
32-
public function get(string $key, callable $callback);
36+
public function get(string $key, callable $callback, float $beta = null);
3337
}

0 commit comments

Comments
 (0)
0