includes/libs/MapCacheLRU.php

   1 <?php
   2 /**
   3  * Per-process memory cache for storing items.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  * http://www.gnu.org/copyleft/gpl.html
  19  *
  20  * @file
  21  * @ingroup Cache
  22  */
  23 use Wikimedia\Assert\Assert;
  24
  25 /**
  26  * Handles a simple LRU key/value map with a maximum number of entries
  27  *
  28  * The last-modification timestamp of entries is internally tracked so that callers can
  29  * specify the maximum acceptable age of entries in calls to the has() method. As a convenience,
  30  * the hasField(), getField(), and setField() methods can be used for entries that are field/value
  31  * maps themselves; such fields will have their own internally tracked last-modification timestamp.
  32  *
  33  * @see ProcessCacheLRU
  34  * @ingroup Cache
  35  * @since 1.23
  36  */
  37 class MapCacheLRU implements IExpiringStore, Serializable {
  38         /** @var array Map of (key => value) */
  39         private $cache = [];
  40         /** @var array Map of (key => (UNIX timestamp, (field => UNIX timestamp))) */
  41         private $timestamps = [];
  42         /** @var float Default entry timestamp if not specified */
  43         private $epoch;
  44
  45         /** @var int Max number of entries */
  46         private $maxCacheKeys;
  47
  48         /** @var float|null */
  49         private $wallClockOverride;
  50
  51         const RANK_TOP = 1.0;
  52
  53         /** @var int Array key that holds the entry's main timestamp (flat key use) */
  54         const SIMPLE = 0;
  55         /** @var int Array key that holds the entry's field timestamps (nested key use) */
  56         const FIELDS = 1;
  57
  58         /**
  59          * @param int $maxKeys Maximum number of entries allowed (min 1)
  60          * @throws Exception When $maxKeys is not an int or not above zero
  61          */
  62         public function __construct( $maxKeys ) {
  63                 Assert::parameterType( 'integer', $maxKeys, '$maxKeys' );
  64                 Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
  65
  66                 $this->maxCacheKeys = $maxKeys;
  67                 // Use the current time as the default "as of" timesamp of entries
  68                 $this->epoch = $this->getCurrentTime();
  69         }
  70
  71         /**
  72          * @param array $values Key/value map in order of increasingly recent access
  73          * @param int $maxKeys
  74          * @return MapCacheLRU
  75          * @since 1.30
  76          */
  77         public static function newFromArray( array $values, $maxKeys ) {
  78                 $mapCache = new self( $maxKeys );
  79                 $mapCache->cache = ( count( $values ) > $maxKeys )
  80                         ? array_slice( $values, -$maxKeys, null, true )
  81                         : $values;
  82
  83                 return $mapCache;
  84         }
  85
  86         /**
  87          * @return array Key/value map in order of increasingly recent access
  88          * @since 1.30
  89          */
  90         public function toArray() {
  91                 return $this->cache;
  92         }
  93
  94         /**
  95          * Set a key/value pair.
  96          * This will prune the cache if it gets too large based on LRU.
  97          * If the item is already set, it will be pushed to the top of the cache.
  98          *
  99          * To reduce evictions due to one-off use of many new keys, $rank can be
 100          * set to have keys start at the top of a bottom fraction of the list. A value
 101          * of 3/8 means values start at the top of the bottom 3/8s of the list and are
 102          * moved to the top of the list when accessed a second time.
 103          *
 104          * @param string $key
 105          * @param mixed $value
 106          * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0]
 107          * @return void
 108          */
 109         public function set( $key, $value, $rank = self::RANK_TOP ) {
 110                 if ( $this->has( $key ) ) {
 111                         $this->ping( $key );
 112                 } elseif ( count( $this->cache ) >= $this->maxCacheKeys ) {
 113                         reset( $this->cache );
 114                         $evictKey = key( $this->cache );
 115                         unset( $this->cache[$evictKey] );
 116                         unset( $this->timestamps[$evictKey] );
 117                 }
 118
 119                 if ( $rank < 1.0 && $rank > 0 ) {
 120                         $offset = intval( $rank * count( $this->cache ) );
 121                         $this->cache = array_slice( $this->cache, 0, $offset, true )
 122                                 + [ $key => $value ]
 123                                 + array_slice( $this->cache, $offset, null, true );
 124                 } else {
 125                         $this->cache[$key] = $value;
 126                 }
 127
 128                 $this->timestamps[$key] = [
 129                         self::SIMPLE => $this->getCurrentTime(),
 130                         self::FIELDS => []
 131                 ];
 132         }
 133
 134         /**
 135          * Check if a key exists
 136          *
 137          * @param string $key
 138          * @param float $maxAge Ignore items older than this many seconds (since 1.32)
 139          * @return bool
 140          */
 141         public function has( $key, $maxAge = 0.0 ) {
 142                 if ( !is_int( $key ) && !is_string( $key ) ) {
 143                         throw new UnexpectedValueException(
 144                                 __METHOD__ . ' called with invalid key. Must be string or integer.' );
 145                 }
 146
 147                 if ( !array_key_exists( $key, $this->cache ) ) {
 148                         return false;
 149                 }
 150
 151                 return ( $maxAge <= 0 || $this->getAge( $key ) <= $maxAge );
 152         }
 153
 154         /**
 155          * Get the value for a key.
 156          * This returns null if the key is not set.
 157          * If the item is already set, it will be pushed to the top of the cache.
 158          *
 159          * @param string $key
 160          * @return mixed Returns null if the key was not found
 161          */
 162         public function get( $key ) {
 163                 if ( !$this->has( $key ) ) {
 164                         return null;
 165                 }
 166
 167                 $this->ping( $key );
 168
 169                 return $this->cache[$key];
 170         }
 171
 172         /**
 173          * @param string|int $key
 174          * @param string|int $field
 175          * @param mixed $value
 176          * @param float $initRank
 177          */
 178         public function setField( $key, $field, $value, $initRank = self::RANK_TOP ) {
 179                 if ( $this->has( $key ) ) {
 180                         $this->ping( $key );
 181                 } else {
 182                         $this->set( $key, [], $initRank );
 183                 }
 184
 185                 if ( !is_array( $this->cache[$key] ) ) {
 186                         throw new UnexpectedValueException( "The value of '$key' is not an array." );
 187                 }
 188
 189                 $this->cache[$key][$field] = $value;
 190                 $this->timestamps[$key][self::FIELDS][$field] = $this->getCurrentTime();
 191         }
 192
 193         /**
 194          * @param string|int $key
 195          * @param string|int $field
 196          * @param float $maxAge
 197          * @return bool
 198          */
 199         public function hasField( $key, $field, $maxAge = 0.0 ) {
 200                 $value = $this->get( $key );
 201                 if ( !is_array( $value ) || !array_key_exists( $field, $value ) ) {
 202                         return false;
 203                 }
 204
 205                 return ( $maxAge <= 0 || $this->getAge( $key, $field ) <= $maxAge );
 206         }
 207
 208         public function getField( $key, $field ) {
 209                 return $this->get( $key )[$field] ?? null;
 210         }
 211
 212         /**
 213          * @return array
 214          * @since 1.25
 215          */
 216         public function getAllKeys() {
 217                 return array_keys( $this->cache );
 218         }
 219
 220         /**
 221          * Get an item with the given key, producing and setting it if not found.
 222          *
 223          * If the callback returns false, then nothing is stored.
 224          *
 225          * @since 1.28
 226          * @param string $key
 227          * @param callable $callback Callback that will produce the value
 228          * @param float $rank Bottom fraction of the list where keys start off [Default: 1.0]
 229          * @param float $maxAge Ignore items older than this many seconds [Default: 0.0] (since 1.32)
 230          * @return mixed The cached value if found or the result of $callback otherwise
 231          */
 232         public function getWithSetCallback(
 233                 $key, callable $callback, $rank = self::RANK_TOP, $maxAge = 0.0
 234         ) {
 235                 if ( $this->has( $key, $maxAge ) ) {
 236                         $value = $this->get( $key );
 237                 } else {
 238                         $value = call_user_func( $callback );
 239                         if ( $value !== false ) {
 240                                 $this->set( $key, $value, $rank );
 241                         }
 242                 }
 243
 244                 return $value;
 245         }
 246
 247         /**
 248          * Clear one or several cache entries, or all cache entries
 249          *
 250          * @param string|array|null $keys
 251          * @return void
 252          */
 253         public function clear( $keys = null ) {
 254                 if ( func_num_args() == 0 ) {
 255                         $this->cache = [];
 256                         $this->timestamps = [];
 257                 } else {
 258                         foreach ( (array)$keys as $key ) {
 259                                 unset( $this->cache[$key] );
 260                                 unset( $this->timestamps[$key] );
 261                         }
 262                 }
 263         }
 264
 265         /**
 266          * Get the maximum number of keys allowed
 267          *
 268          * @return int
 269          * @since 1.32
 270          */
 271         public function getMaxSize() {
 272                 return $this->maxCacheKeys;
 273         }
 274
 275         /**
 276          * Resize the maximum number of cache entries, removing older entries as needed
 277          *
 278          * @param int $maxKeys Maximum number of entries allowed (min 1)
 279          * @return void
 280          * @throws Exception When $maxKeys is not an int or not above zero
 281          * @since 1.32
 282          */
 283         public function setMaxSize( $maxKeys ) {
 284                 Assert::parameterType( 'integer', $maxKeys, '$maxKeys' );
 285                 Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
 286
 287                 $this->maxCacheKeys = $maxKeys;
 288                 while ( count( $this->cache ) > $this->maxCacheKeys ) {
 289                         reset( $this->cache );
 290                         $evictKey = key( $this->cache );
 291                         unset( $this->cache[$evictKey] );
 292                         unset( $this->timestamps[$evictKey] );
 293                 }
 294         }
 295
 296         /**
 297          * Push an entry to the top of the cache
 298          *
 299          * @param string $key
 300          */
 301         private function ping( $key ) {
 302                 $item = $this->cache[$key];
 303                 unset( $this->cache[$key] );
 304                 $this->cache[$key] = $item;
 305         }
 306
 307         /**
 308          * @param string|int $key
 309          * @param string|int|null $field [optional]
 310          * @return float UNIX timestamp; the age of the given entry or entry field
 311          */
 312         private function getAge( $key, $field = null ) {
 313                 if ( $field !== null ) {
 314                         $mtime = $this->timestamps[$key][self::FIELDS][$field] ?? $this->epoch;
 315                 } else {
 316                         $mtime = $this->timestamps[$key][self::SIMPLE] ?? $this->epoch;
 317                 }
 318
 319                 return ( $this->getCurrentTime() - $mtime );
 320         }
 321
 322         public function serialize() {
 323                 return serialize( [
 324                         'entries' => $this->cache,
 325                         'timestamps' => $this->timestamps
 326                 ] );
 327         }
 328
 329         public function unserialize( $serialized ) {
 330                 $data = unserialize( $serialized );
 331                 $this->cache = $data['entries'] ?? [];
 332                 $this->timestamps = $data['timestamps'] ?? [];
 333                 $this->epoch = $this->getCurrentTime();
 334         }
 335
 336         /**
 337          * @return float UNIX timestamp
 338          * @codeCoverageIgnore
 339          */
 340         protected function getCurrentTime() {
 341                 return $this->wallClockOverride ?: microtime( true );
 342         }
 343
 344         /**
 345          * @param float|null &$time Mock UNIX timestamp for testing
 346          * @codeCoverageIgnore
 347          */
 348         public function setMockTime( &$time ) {
 349                 $this->wallClockOverride =& $time;
 350         }
 351 }