8000 [Cache] Add stampede protection via probabilistic early expiration · symfony/symfony@0b647d2 · GitHub
[go: up one dir, main page]
Skip to content
Sign in

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 0b647d2

Browse files
nicolas-grekasnicolas-grekas
committed
[Cache] Add stampede protection via probabilistic early expiration
1 parent 61530c8 commit 0b647d2

21 files changed

+234
-43
lines changed

‎UPGRADE-4.2.md

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
UPGRADE FROM 4.1 to 4.2
2+
=======================
3+
4+
Cache
5+
-----
6+
7+
* Deprecated `CacheItem::getPreviousTags()`, use `CacheItem::getStats()` instead.

‎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::getStats()` instead.
8+
49
Config
510
------
611

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

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -46,9 +46,12 @@ 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+
if (\is_array($v) && 1 === \count($v) && \is_array($v = $v[CacheItem::STATS_KEY] ?? null) && array(0, 1) === \array_keys($v)) {
53+
list($item->value, $item->stats) = $v;
54+
}
5255

5356
return $item;
5457
},
@@ -64,12 +67,14 @@ function ($deferred, $namespace, &$expiredIds) use ($getId) {
6467

6568
foreach ($deferred as $key => $item) {
6669
if (null === $item->expiry) {
67-
$byLifetime[0 < $item->defaultLifetime ? $item->defaultLifetime : 0][$getId($key)] = $item->value;
70+
$ttl = 0 < $item->defaultLifetime ? $item->defaultLifetime : 0;
6871
} elseif ($item->expiry > $now) {
69-
$byLifetime[$item->expiry - $now][$getId($key)] = $item->value;
72+
$ttl = $item->expiry - $now;
7073
} else {
7174
$expiredIds[] = $getId($key);
75+
continue;
7276
}
77+
$byLifetime[$ttl][$getId($key)] = $item->newStats ? array(CacheItem::STATS_KEY => array($item->value, $item->newStats)) : $item->value;
7378
}
7479

7580
return $byLifetime;

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

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -86,19 +86,20 @@ function ($sourceItem, $item) use ($defaultLifetime) {
8686
/**
8787
* {@inheritdoc}
8888
*/
89-
public function get(string $key, callable $callback)
89+
public function get(string $key, callable $callback, float $beta = null)
9090
{
9191
$lastItem = null;
9292
$i = 0;
93-
$wrap = function (CacheItem $item = null) use ($key, $callback, &$wrap, &$i, &$lastItem) {
93+
$wrap = function (CacheItem $item = null) use ($key, $callback, $beta, &$wrap, &$i, &$lastItem) {
9494
$adapter = $this->adapters[$i];
9595
if (isset($this->adapters[++$i])) {
9696
$callback = $wrap;
97+
$beta = INF === $beta ? INF : 0;
9798
}
9899
if ($adapter instanceof CacheInterface) {
99-
$value = $adapter->get($key, $callback);
100+
$value = $adapter->get($key, $callback, $beta);
100101
} else {
101-
$value = $this->doGet($adapter, $key, $callback);
102+
$value = $this->doGet($adapter, $key, $callback, $beta ?? 1.0);
102103
}
103104
if (null !== $item) {
104105
($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,7 +83,7 @@ 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 (!\is_string($key)) {
8989
throw new InvalidArgumentException(sprintf('Cache key must be string, "%s" given.', is_object($key) ? get_class($key) : gettype($key)));
@@ -93,10 +93,10 @@ public function get(string $key, callable $callback)
9393
}
9494
if (null === $value = $this->values[$key] ?? null) {
9595
if ($this->pool instanceof CacheInterface) {
96-
return $this->pool->get($key, $callback);
96+
return $this->pool->get($key, $callback, $beta);
9797
}
9898

99-
return $this->doGet($this->pool, $key, $callback);
99+
return $this->doGet($this->pool, $key, $callback, $beta ?? 1.0);
100100
}
101101
if ('N;' === $value) {
102102
return null;

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

Lines changed: 29 additions & 10 deletions
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,52 @@ 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+
if (\is_array($v) && 1 === \count($v) && \is_array($v = $v[CacheItem::STATS_KEY] ?? null) && array(0, 1) === \array_keys($v)) {
53+
list($item->value, $item->stats) = $v;
54+
} elseif ($innerItem instanceof CacheItem) {
55+
$item->stats = $innerItem->stats;
56+
}
5157
$innerItem->set(null);
5258

5359
return $item;
5460
},
5561
null,
5662
CacheItem::class
5763
);
64+
$this->setInnerItem = \Closure::bind(
65+
function (CacheItemInterface $innerItem, array $item) {
66+
if ($stats = $item["\0*\0newStats"]) {
67+
$item["\0*\0value"] = array(CacheItem::STATS_KEY => array($item["\0*\0value"], $stats));
68+
}
69+
$innerItem->set($item["\0*\0value"]);
70+
$innerItem->expiresAt(null !== $item["\0*\0expiry"] ? \DateTime::createFromFormat('U', $item["\0*\0expiry"]) : null);
71+
},
72+
null,
73+
CacheItem::class
74+
);
5875
}
5976

6077
/**
6178
* {@inheritdoc}
6279
*/
63-
public function get(string $key, callable $callback)
80+
public function get(string $key, callable $callback, float $beta = null)
6481
{
6582
if (!$this->pool instanceof CacheInterface) {
66-
return $this->doGet($this->pool, $key, $callback);
83+
return $this->doGet($this, $key, $callback, $beta ?? 1.0);
6784
}
6885

6986
return $this->pool->get($this->getId($key), function ($innerItem) use ($key, $callback) {
70-
return $callback(($this->createCacheItem)($key, $innerItem));
71-
});
87+
$item = ($this->createCacheItem)($key, $innerItem);
88+
$item->set($value = $callback($item));
89+
($this->setInnerItem)($innerItem, (array) $item);
90+
91+
return $value;
92+
}, $beta);
7293
}
7394

7495
/**
@@ -164,13 +185,11 @@ private function doSave(CacheItemInterface $item, $method)
164185
return false;
165186
}
166187
$item = (array) $item;
167-
$expiry = $item["\0*\0expiry"];
168-
if (null === $expiry && 0 < $item["\0*\0defaultLifetime"]) {
169-
$expiry = time() + $item["\0*\0defaultLifetime"];
188+
if (null === $item["\0*\0expiry"] && 0 < $item["\0*\0defaultLifetime"]) {
189+
$item["\0*\0expiry"] = time() + $item["\0*\0defaultLifetime"];
170190
}
171191
$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);
192+
($this->setInnerItem)($innerItem, $item);
174193

175194
return $this->pool->$method($innerItem);
176195
}

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,7 @@ function (CacheItem $item, $key, array &$itemTags) {
6464
}
6565
if (isset($itemTags[$key])) {
6666
foreach ($itemTags[$key] as $tag => $version) {
67-
$item->prevTags[$tag] = $tag;
67+
$item->stats[CacheItem::STATS_TAGS][$tag] = $tag;
6868
}
6969
unset($itemTags[$key]);
7070
} else {
@@ -81,7 +81,7 @@ function (CacheItem $item, $key, array &$itemTags) {
8181
function ($deferred) {
8282
$tagsByKey = array();
8383
foreach ($deferred as $key => $item) {
84-
$tagsByKey[$key] = $item->tags;
84+
$tagsByKey[$key] = $item->newStats[CacheItem::STATS_TAGS] ?? array();
8585
}
8686

8787
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` and `TaggableCacheInterface`
7+
* added `CacheInterface` and `TaggableCacheInterface`, providing stampede protection via probabilistic early expiration
88
* throw `LogicException` when `CacheItem::tag()` is called on an item coming from a non tag-aware pool
9+
* deprecated `CacheItem::getPreviousTags()`, use `CacheItem::getStats()` 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: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,8 +30,11 @@ interface CacheInterface
3030
{
3131
/**
3232
* @param callable(CacheItemInterface $item):mixed $callback Should return the computed value for the given key/item
33+
* @param float $beta A float that controls the likelyness of triggering early expiration.
34+
* 0 disables it, INF forces immediate expiration. The default is implementation dependend
35+
* but should typically be 1.0, which should provide optimal stampede protection.
3336
*
3437
* @return mixed The value corresponding to the provided key
3538
*/
36-
public function get(string $key, callable $callback);
39+
public function get(string $key, callable $callback, float $beta = null);
3740
}

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

Lines changed: 36 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -21,13 +21,30 @@
2121
*/
2222
final class CacheItem implements CacheItemInterface
2323
{
24+
/**
25+
* References the unix timestamp stating when the item will expire, as integer.
26+
*/
27+
const STATS_EXPIRY = 'expiry';
28+
29+
/**
30+
* References the time the item took to be created, as float.
31+
*/
32+
const STATS_CTIME = 'ctime';
33+
34+
/**
35+
* References the list of tags that were assigned to the item, as string[].
36+
*/
37+
const STATS_TAGS = 'tags';
38+
39+
private const STATS_KEY = "\x005\xFC4ch3\x00";
40+
2441
protected $key;
2542
protected $value;
2643
protected $isHit = false;
2744
protected $expiry;
2845
protected $defaultLifetime;
29-
protected $tags = array();
30-
protected $prevTags = array();
46+
protected $stats = array();
47+
protected $newStats = array();
3148
protected $innerItem;
3249
protected $poolHash;
3350
protected $isTaggable = false;
@@ -121,7 +138,7 @@ public function tag($tags)
121138
if (!\is_string($tag)) {
122139
throw new InvalidArgumentException(sprintf('Cache tag must be string, "%s" given', is_object($tag) ? get_class($tag) : gettype($tag)));
123140
}
124-
if (isset($this->tags[$tag])) {
141+
if (isset($this->newStats[self::STATS_TAGS][$tag])) {
125142
continue;
126143
}
127144
if ('' === $tag) {
@@ -130,7 +147,7 @@ public function tag($tags)
130147
if (false !== strpbrk($tag, '{}()/\@:')) {
131148
throw new InvalidArgumentException(sprintf('Cache tag "%s" contains reserved characters {}()/\@:', $tag));
132149
}
133-
$this->tags[$tag] = $tag;
150+
$this->newStats[self::STATS_TAGS][$tag] = $tag;
134151
}
135152

136153
return $this;
@@ -140,10 +157,24 @@ public function tag($tags)
140157
* Returns the list of tags bound to the value coming from the pool storage if any.
141158
*
142159
* @return array
160+
*
161+
* @deprecated since Symfony 4.1. Use the "getStats()" method instead.
143162
*/
144163
public function getPreviousTags()
145164
{
146-
return $this->prevTags;
165+
@trigger_error(sprintf('The "%s" method is deprecated since Symfony 4.1. Use the "getStats()" method instead.', __METHOD__), E_USER_DEPRECATED);
166+
167+
return $this->stats[self::STATS_TAGS] ?? array();
168+
}
169+
170+
/**
171+
* Returns a list of stats info that were saved alongside with the cached value.
172+
*
173+
* See public CacheItem::STATS_* consts for keys potentially found in the returned array.
174+
*/
175+
public function getStats(): array
176+
{
177+
return $this->stats;
147178
}
148179

149180
/**

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

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -28,8 +28,11 @@ interface TaggableCacheInterface extends CacheInterface
2828
{
2929
/**
3030
* @param callable(CacheItem $item):mixed $callback Should return the computed value for the given key/item
31+
* @param float $beta A float that controls the likelyness of triggering early expiration.
32+
* 0 disables it, INF forces immediate expiration. The default is implementation dependend
33+
* but should typically be 1.0, which should provide optimal stampede protection.
3134
*
3235
* @return mixed The value corresponding to the provided key
3336
*/
34-
public function get(string $key, callable $callback);
37+
public function get(string $key, callable $callback, float $beta = null);
3538
}

‎src/Symfony/Component/Cache/Tests/Adapter/AdapterTestCase.php

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,6 +45,42 @@ public function testGet()
4545

4646
$item = $cache->getItem('foo');
4747
$this->assertSame($value, $item->get());
48+
49+
$isHit = true;
50+
$this->assertSame($value, $cache->get('foo', function (CacheItem $item) use (&$isHit) { $isHit = false; }, 0));
51+
$this->assertTrue($isHit);
52+
53+
$this->assertNull($cache->get('foo', function (CacheItem $item) use (&$isHit, $value) {
54+
$isHit = false;
55+
$this->assertTrue($item->isHit());
56+
$this->assertSame($value, $item->get());
57+
}, INF));
58+
$this->assertFalse($isHit);
59+
}
60+
61+
public function testGetStats()
62+
{
63+
if (isset($this->skippedTests[__FUNCTION__])) {
64+
$this->markTestSkipped($this->skippedTests[__FUNCTION__]);
65+
}
66+
67+
$cache = $this->createCachePool(0, __FUNCTION__);
68+
69+
$cache->deleteItem('foo');
70+
$cache->get('foo', function ($item) {
71+
$item->expiresAfter(10);
72+
sleep(1);
73+
74+
return 'bar';
75+
});
76+
77+
$item = $cache->getItem('foo');
78+
79+
$expected = array(
80+
'ctime' => 1.0,
81+
'expiry' => 9 + time(),
82+
);
83+
$this->assertSame($expected, $item->getStats());
4884
}
4985

5086
public function testDefaultLifeTime()

‎src/Symfony/Component/Cache/Tests/Adapter/ArrayAdapterTest.php

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
class ArrayAdapterTest extends AdapterTestCase
2020
{
2121
protected $skippedTests = array(
22+
'testGetStats' => 'ArrayAdapter does not keep stats.',
2223
'testDeferredSaveWithoutCommit' => 'Assumes a shared cache which ArrayAdapter is not.',
2324
'testSaveWithoutExpire' => 'Assumes a shared cache which ArrayAdapter is not.',
2425
);

0 commit comments

Comments
 (0)
0