From 1f2b2f3f8d451da49da4342b68658baf40f213b5 Mon Sep 17 00:00:00 2001 From: Aaron Schulz Date: Wed, 27 Jun 2018 10:40:19 +0100 Subject: [PATCH] Add key expiration and map resizing support to MapCacheLRU MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Also implement Serializable in to add stability to anything that uses naïve serialization (such as for persistent caching). Change-Id: I03ba654ffd80ba027d47d5d7583abfe48d52818d --- includes/libs/MapCacheLRU.php | 179 ++++++++++++++++-- .../phpunit/includes/libs/MapCacheLRUTest.php | 95 ++++++++++ 2 files changed, 261 insertions(+), 13 deletions(-) diff --git a/includes/libs/MapCacheLRU.php b/includes/libs/MapCacheLRU.php index 553315f23a..bca8c05a36 100644 --- a/includes/libs/MapCacheLRU.php +++ b/includes/libs/MapCacheLRU.php @@ -25,27 +25,47 @@ use Wikimedia\Assert\Assert; /** * Handles a simple LRU key/value map with a maximum number of entries * - * Use ProcessCacheLRU if hierarchical purging is needed or objects can become stale + * The last-modification timestamp of entries is internally tracked so that callers can + * specify the maximum acceptable age of entries in calls to the has() method. As a convenience, + * the hasField(), getField(), and setField() methods can be used for entries that are field/value + * maps themselves; such fields will have their own internally tracked last-modification timestamp. * * @see ProcessCacheLRU * @ingroup Cache * @since 1.23 */ -class MapCacheLRU { - /** @var array */ - protected $cache = []; // (key => value) +class MapCacheLRU implements IExpiringStore, Serializable { + /** @var array Map of (key => value) */ + private $cache = []; + /** @var array Map of (key => (UNIX timestamp, (field => UNIX timestamp))) */ + private $timestamps = []; + /** @var float Default entry timestamp if not specified */ + private $epoch; - protected $maxCacheKeys; // integer; max entries + /** @var int Max number of entries */ + private $maxCacheKeys; + + /** @var float|null */ + private $wallClockOverride; + + const RANK_TOP = 1.0; + + /** @var int Array key that holds the entry's main timestamp (flat key use) */ + const SIMPLE = 0; + /** @var int Array key that holds the entry's field timestamps (nested key use) */ + const FIELDS = 1; /** - * @param int $maxKeys Maximum number of entries allowed (min 1). - * @throws Exception When $maxCacheKeys is not an int or not above zero. + * @param int $maxKeys Maximum number of entries allowed (min 1) + * @throws Exception When $maxKeys is not an int or not above zero */ public function __construct( $maxKeys ) { Assert::parameterType( 'integer', $maxKeys, '$maxKeys' ); Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' ); $this->maxCacheKeys = $maxKeys; + // Use the current time as the default "as of" timesamp of entries + $this->epoch = $this->getCurrentTime(); } /** @@ -86,13 +106,14 @@ class MapCacheLRU { * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0] * @return void */ - public function set( $key, $value, $rank = 1.0 ) { + public function set( $key, $value, $rank = self::RANK_TOP ) { if ( $this->has( $key ) ) { $this->ping( $key ); } elseif ( count( $this->cache ) >= $this->maxCacheKeys ) { reset( $this->cache ); $evictKey = key( $this->cache ); unset( $this->cache[$evictKey] ); + unset( $this->timestamps[$evictKey] ); } if ( $rank < 1.0 && $rank > 0 ) { @@ -103,20 +124,31 @@ class MapCacheLRU { } else { $this->cache[$key] = $value; } + + $this->timestamps[$key] = [ + self::SIMPLE => $this->getCurrentTime(), + self::FIELDS => [] + ]; } /** * Check if a key exists * * @param string $key + * @param float $maxAge Ignore items older than this many seconds (since 1.32) * @return bool */ - public function has( $key ) { + public function has( $key, $maxAge = 0.0 ) { if ( !is_int( $key ) && !is_string( $key ) ) { throw new UnexpectedValueException( __METHOD__ . ' called with invalid key. Must be string or integer.' ); } - return array_key_exists( $key, $this->cache ); + + if ( !array_key_exists( $key, $this->cache ) ) { + return false; + } + + return ( $maxAge <= 0 || $this->getAge( $key ) <= $maxAge ); } /** @@ -137,6 +169,46 @@ class MapCacheLRU { return $this->cache[$key]; } + /** + * @param string|int $key + * @param string|int $field + * @param mixed $value + * @param float $initRank + */ + public function setField( $key, $field, $value, $initRank = self::RANK_TOP ) { + if ( $this->has( $key ) ) { + $this->ping( $key ); + } else { + $this->set( $key, [], $initRank ); + } + + if ( !is_array( $this->cache[$key] ) ) { + throw new UnexpectedValueException( "The value of '$key' is not an array." ); + } + + $this->cache[$key][$field] = $value; + $this->timestamps[$key][self::FIELDS][$field] = $this->getCurrentTime(); + } + + /** + * @param string|int $key + * @param string|int $field + * @param float $maxAge + * @return bool + */ + public function hasField( $key, $field, $maxAge = 0.0 ) { + $value = $this->get( $key ); + if ( !is_array( $value ) || !array_key_exists( $field, $value ) ) { + return false; + } + + return ( $maxAge <= 0 || $this->getAge( $key, $field ) <= $maxAge ); + } + + public function getField( $key, $field ) { + return $this->get( $key )[$field] ?? null; + } + /** * @return array * @since 1.25 @@ -154,10 +226,13 @@ class MapCacheLRU { * @param string $key * @param callable $callback Callback that will produce the value * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0] + * @param float $maxAge Ignore items older than this many seconds [Default: 0.0] (since 1.32) * @return mixed The cached value if found or the result of $callback otherwise */ - public function getWithSetCallback( $key, callable $callback, $rank = 1.0 ) { - if ( $this->has( $key ) ) { + public function getWithSetCallback( + $key, callable $callback, $rank = self::RANK_TOP, $maxAge = 0.0 + ) { + if ( $this->has( $key, $maxAge ) ) { $value = $this->get( $key ); } else { $value = call_user_func( $callback ); @@ -178,21 +253,99 @@ class MapCacheLRU { public function clear( $keys = null ) { if ( $keys === null ) { $this->cache = []; + $this->timestamps = []; } else { foreach ( (array)$keys as $key ) { unset( $this->cache[$key] ); + unset( $this->timestamps[$key] ); } } } + /** + * Get the maximum number of keys allowed + * + * @return int + * @since 1.32 + */ + public function getMaxSize() { + return $this->maxCacheKeys; + } + + /** + * Resize the maximum number of cache entries, removing older entries as needed + * + * @param int $maxKeys Maximum number of entries allowed (min 1) + * @return void + * @throws Exception When $maxKeys is not an int or not above zero + * @since 1.32 + */ + public function setMaxSize( $maxKeys ) { + Assert::parameterType( 'integer', $maxKeys, '$maxKeys' ); + Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' ); + + $this->maxCacheKeys = $maxKeys; + while ( count( $this->cache ) > $this->maxCacheKeys ) { + reset( $this->cache ); + $evictKey = key( $this->cache ); + unset( $this->cache[$evictKey] ); + unset( $this->timestamps[$evictKey] ); + } + } + /** * Push an entry to the top of the cache * * @param string $key */ - protected function ping( $key ) { + private function ping( $key ) { $item = $this->cache[$key]; unset( $this->cache[$key] ); $this->cache[$key] = $item; } + + /** + * @param string|int $key + * @param string|int|null $field [optional] + * @return float UNIX timestamp; the age of the given entry or entry field + */ + private function getAge( $key, $field = null ) { + if ( $field !== null ) { + $mtime = $this->timestamps[$key][self::FIELDS][$field] ?? $this->epoch; + } else { + $mtime = $this->timestamps[$key][self::SIMPLE] ?? $this->epoch; + } + + return ( $this->getCurrentTime() - $mtime ); + } + + public function serialize() { + return serialize( [ + 'entries' => $this->cache, + 'timestamps' => $this->timestamps + ] ); + } + + public function unserialize( $serialized ) { + $data = unserialize( $serialized ); + $this->cache = $data['entries'] ?? []; + $this->timestamps = $data['timestamps'] ?? []; + $this->epoch = $this->getCurrentTime(); + } + + /** + * @return float UNIX timestamp + * @codeCoverageIgnore + */ + protected function getCurrentTime() { + return $this->wallClockOverride ?: microtime( true ); + } + + /** + * @param float|null &$time Mock UNIX timestamp for testing + * @codeCoverageIgnore + */ + public function setMockTime( &$time ) { + $this->wallClockOverride =& $time; + } } diff --git a/tests/phpunit/includes/libs/MapCacheLRUTest.php b/tests/phpunit/includes/libs/MapCacheLRUTest.php index 2a962b796b..79f7b96f6e 100644 --- a/tests/phpunit/includes/libs/MapCacheLRUTest.php +++ b/tests/phpunit/includes/libs/MapCacheLRUTest.php @@ -11,11 +11,14 @@ class MapCacheLRUTest extends PHPUnit\Framework\TestCase { * @covers MapCacheLRU::toArray() * @covers MapCacheLRU::getAllKeys() * @covers MapCacheLRU::clear() + * @covers MapCacheLRU::getMaxSize() + * @covers MapCacheLRU::setMaxSize() */ function testArrayConversion() { $raw = [ 'd' => 4, 'c' => 3, 'b' => 2, 'a' => 1 ]; $cache = MapCacheLRU::newFromArray( $raw, 3 ); + $this->assertEquals( 3, $cache->getMaxSize() ); $this->assertSame( true, $cache->has( 'a' ) ); $this->assertSame( true, $cache->has( 'b' ) ); $this->assertSame( true, $cache->has( 'c' ) ); @@ -43,6 +46,27 @@ class MapCacheLRUTest extends PHPUnit\Framework\TestCase { [], $cache->toArray() ); + + $cache = MapCacheLRU::newFromArray( [ 'd' => 4, 'c' => 3, 'b' => 2, 'a' => 1 ], 4 ); + $cache->setMaxSize( 3 ); + $this->assertSame( + [ 'c' => 3, 'b' => 2, 'a' => 1 ], + $cache->toArray() + ); + } + + /** + * @covers MapCacheLRU::serialize() + * @covers MapCacheLRU::unserialize() + */ + function testSerialize() { + $cache = MapCacheLRU::newFromArray( [ 'd' => 4, 'c' => 3, 'b' => 2, 'a' => 1 ], 10 ); + $string = serialize( $cache ); + $ncache = unserialize( $string ); + $this->assertSame( + [ 'd' => 4, 'c' => 3, 'b' => 2, 'a' => 1 ], + $ncache->toArray() + ); } /** @@ -114,4 +138,75 @@ class MapCacheLRUTest extends PHPUnit\Framework\TestCase { $cache->toArray() ); } + + /** + * @covers MapCacheLRU::has() + * @covers MapCacheLRU::get() + * @covers MapCacheLRU::set() + */ + public function testExpiry() { + $raw = [ 'a' => 1, 'b' => 2, 'c' => 3 ]; + $cache = MapCacheLRU::newFromArray( $raw, 3 ); + + $now = microtime( true ); + $cache->setMockTime( $now ); + + $cache->set( 'd', 'xxx' ); + $this->assertTrue( $cache->has( 'd', 30 ) ); + $this->assertEquals( 'xxx', $cache->get( 'd' ) ); + + $now += 29; + $this->assertTrue( $cache->has( 'd', 30 ) ); + $this->assertEquals( 'xxx', $cache->get( 'd' ) ); + + $now += 1.5; + $this->assertFalse( $cache->has( 'd', 30 ) ); + $this->assertEquals( 'xxx', $cache->get( 'd' ) ); + } + + /** + * @covers MapCacheLRU::hasField() + * @covers MapCacheLRU::getField() + * @covers MapCacheLRU::setField() + */ + public function testFields() { + $raw = [ 'a' => 1, 'b' => 2, 'c' => 3 ]; + $cache = MapCacheLRU::newFromArray( $raw, 3 ); + + $now = microtime( true ); + $cache->setMockTime( $now ); + + $cache->setField( 'PMs', 'Tony Blair', 'Labour' ); + $cache->setField( 'PMs', 'Margaret Thatcher', 'Tory' ); + $this->assertTrue( $cache->hasField( 'PMs', 'Tony Blair', 30 ) ); + $this->assertEquals( 'Labour', $cache->getField( 'PMs', 'Tony Blair' ) ); + + $now += 29; + $this->assertTrue( $cache->hasField( 'PMs', 'Tony Blair', 30 ) ); + $this->assertEquals( 'Labour', $cache->getField( 'PMs', 'Tony Blair' ) ); + + $now += 1.5; + $this->assertFalse( $cache->hasField( 'PMs', 'Tony Blair', 30 ) ); + $this->assertEquals( 'Labour', $cache->getField( 'PMs', 'Tony Blair' ) ); + + $this->assertEquals( + [ 'Tony Blair' => 'Labour', 'Margaret Thatcher' => 'Tory' ], + $cache->get( 'PMs' ) + ); + + $cache->set( 'MPs', [ + 'Edwina Currie' => 1983, + 'Neil Kinnock' => 1970 + ] ); + $this->assertEquals( + [ + 'Edwina Currie' => 1983, + 'Neil Kinnock' => 1970 + ], + $cache->get( 'MPs' ) + ); + + $this->assertEquals( 1983, $cache->getField( 'MPs', 'Edwina Currie' ) ); + $this->assertEquals( 1970, $cache->getField( 'MPs', 'Neil Kinnock' ) ); + } } -- 2.20.1