includes/cache/bloom/BloomCache.php

   1 <?php
   2 /**
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation; either version 2 of the License, or
   6  * (at your option) any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License along
  14  * with this program; if not, write to the Free Software Foundation, Inc.,
  15  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16  * http://www.gnu.org/copyleft/gpl.html
  17  *
  18  * @file
  19  * @author Aaron Schulz
  20  */
  21
  22 /**
  23  * Persistent bloom filter used to avoid expensive lookups
  24  *
  25  * @since 1.24
  26  */
  27 abstract class BloomCache {
  28         /** @var string Unique ID for key namespacing */
  29         protected $cacheID;
  30
  31         /** @var array Map of (id => BloomCache) */
  32         protected static $instances = array();
  33
  34         /**
  35          * @param string $id
  36          * @return BloomCache
  37          */
  38         final public static function get( $id ) {
  39                 global $wgBloomFilterStores;
  40
  41                 if ( !isset( self::$instances[$id] ) ) {
  42                         if ( isset( $wgBloomFilterStores[$id] ) ) {
  43                                 $class = $wgBloomFilterStores[$id]['class'];
  44                                 self::$instances[$id] = new $class( $wgBloomFilterStores[$id] );
  45                         } else {
  46                                 wfDebug( "No bloom filter store '$id'; using EmptyBloomCache." );
  47                                 return new EmptyBloomCache( array() );
  48                         }
  49                 }
  50
  51                 return self::$instances[$id];
  52         }
  53
  54         /**
  55          * Create a new bloom cache instance from configuration.
  56          * This should only be called from within BloomCache.
  57          *
  58          * @param array $config Parameters include:
  59          *   - cacheID : Prefix to all bloom filter names that is unique to this cache.
  60          *               It should only consist of alphanumberic, '-', and '_' characters.
  61          *               This ID is what avoids collisions if multiple logical caches
  62          *               use the same storage system, so this should be set carefully.
  63          * @throws MWException
  64          */
  65         public function __construct( array $config ) {
  66                 $this->cacheID = $config['cacheId'];
  67                 if ( !preg_match( '!^[a-zA-Z0-9-_]{1,32}$!', $this->cacheID ) ) {
  68                         throw new MWException( "Cache ID '{$this->cacheID}' is invalid." );
  69                 }
  70         }
  71
  72         /**
  73          * Check if a member is set in the bloom filter
  74          *
  75          * A member being set means that it *might* have been added.
  76          * A member not being set means it *could not* have been added.
  77          *
  78          * This abstracts over isHit() to deal with filter updates and readiness.
  79          * A class must exist with the name BloomFilter<type> and a static public
  80          * mergeAndCheck() method. The later takes the following arguments:
  81          *              (BloomCache $bcache, $domain, $virtualKey, array $status)
  82          * The method should return a bool indicating whether to use the filter.
  83          *
  84          * The 'shared' bloom key must be used for any updates and will be used
  85          * for the membership check if the method returns true. Since the key is shared,
  86          * the method should never use delete(). The filter cannot be used in cases where
  87          * membership in the filter needs to be taken away. In such cases, code *cannot*
  88          * use this method - instead, it can directly use the other BloomCache methods
  89          * to manage custom filters with their own keys (e.g. not 'shared').
  90          *
  91          * @param string $domain
  92          * @param string $type
  93          * @param string $member
  94          * @return bool True if set, false if not (also returns true on error)
  95          */
  96         final public function check( $domain, $type, $member ) {
  97                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
  98
  99                 if ( method_exists( "BloomFilter{$type}", 'mergeAndCheck' ) ) {
 100                         try {
 101                                 $virtualKey = "$domain:$type";
 102
 103                                 $status = $this->getStatus( $virtualKey );
 104                                 if ( $status == false ) {
 105                                         wfDebug( "Could not query virtual bloom filter '$virtualKey'." );
 106                                         return true;
 107                                 }
 108
 109                                 $useFilter = call_user_func_array(
 110                                         array( "BloomFilter{$type}", 'mergeAndCheck' ),
 111                                         array( $this, $domain, $virtualKey, $status )
 112                                 );
 113
 114                                 if ( $useFilter ) {
 115                                         return ( $this->isHit( 'shared', "$virtualKey:$member" ) !== false );
 116                                 }
 117                         } catch ( Exception $e ) {
 118                                 MWExceptionHandler::logException( $e );
 119                                 return true;
 120                         }
 121                 }
 122
 123                 return true;
 124         }
 125
 126         /**
 127          * Inform the bloom filter of a new member in order to keep it up to date
 128          *
 129          * @param string $domain
 130          * @param string $type
 131          * @param string|array $members
 132          * @return bool Success
 133          */
 134         final public function insert( $domain, $type, $members ) {
 135                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
 136
 137                 if ( method_exists( "BloomFilter{$type}", 'mergeAndCheck' ) ) {
 138                         try {
 139                                 $virtualKey = "$domain:$type";
 140                                 $prefixedMembers = array();
 141                                 foreach ( (array)$members as $member ) {
 142                                         $prefixedMembers[] = "$virtualKey:$member";
 143                                 }
 144
 145                                 return $this->add( 'shared', $prefixedMembers );
 146                         } catch ( Exception $e ) {
 147                                 MWExceptionHandler::logException( $e );
 148                                 return false;
 149                         }
 150                 }
 151
 152                 return true;
 153         }
 154
 155         /**
 156          * Create a new bloom filter at $key (if one does not exist yet)
 157          *
 158          * @param string $key
 159          * @param integer $size Bit length [default: 1000000]
 160          * @param float $precision [default: .001]
 161          * @return bool Success
 162          */
 163         final public function init( $key, $size = 1000000, $precision = .001 ) {
 164                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
 165
 166                 return $this->doInit( "{$this->cacheID}:$key", $size, min( .1, $precision ) );
 167         }
 168
 169         /**
 170          * Add a member to the bloom filter at $key
 171          *
 172          * @param string $key
 173          * @param string|array $members
 174          * @return bool Success
 175          */
 176         final public function add( $key, $members ) {
 177                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
 178
 179                 return $this->doAdd( "{$this->cacheID}:$key", (array)$members );
 180         }
 181
 182         /**
 183          * Check if a member is set in the bloom filter.
 184          *
 185          * A member being set means that it *might* have been added.
 186          * A member not being set means it *could not* have been added.
 187          *
 188          * If this returns true, then the caller usually should do the
 189          * expensive check (whatever that may be). It can be avoided otherwise.
 190          *
 191          * @param string $key
 192          * @param string $member
 193          * @return bool|null True if set, false if not, null on error
 194          */
 195         final public function isHit( $key, $member ) {
 196                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
 197
 198                 return $this->doIsHit( "{$this->cacheID}:$key", $member );
 199         }
 200
 201         /**
 202          * Destroy a bloom filter at $key
 203          *
 204          * @param string $key
 205          * @return bool Success
 206          */
 207         final public function delete( $key ) {
 208                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
 209
 210                 return $this->doDelete( "{$this->cacheID}:$key" );
 211         }
 212
 213         /**
 214          * Set the status map of the virtual bloom filter at $key
 215          *
 216          * @param string $virtualKey
 217          * @param array $values Map including some of (lastID, asOfTime, epoch)
 218          * @return bool Success
 219          */
 220         final public function setStatus( $virtualKey, array $values ) {
 221                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
 222
 223                 return $this->doSetStatus( "{$this->cacheID}:$virtualKey", $values );
 224         }
 225
 226         /**
 227          * Get the status map of the virtual bloom filter at $key
 228          *
 229          * The map includes:
 230          *   - lastID    : the highest ID of the items merged in
 231          *   - asOfTime  : UNIX timestamp that the filter is up-to-date as of
 232          *   - epoch     : UNIX timestamp that filter started being populated
 233          * Unset fields will have a null value.
 234          *
 235          * @param string $virtualKey
 236          * @return array|bool False on failure
 237          */
 238         final public function getStatus( $virtualKey ) {
 239                 $ps = Profiler::instance()->scopedProfileIn( get_class( $this ) . '::' . __FUNCTION__ );
 240
 241                 return $this->doGetStatus( "{$this->cacheID}:$virtualKey" );
 242         }
 243
 244         /**
 245          * Get an exclusive lock on a filter for updates
 246          *
 247          * @param string $virtualKey
 248          * @return ScopedCallback|ScopedLock|null Returns null if acquisition failed
 249          */
 250         public function getScopedLock( $virtualKey ) {
 251                 return null;
 252         }
 253
 254         /**
 255          * @param string $key
 256          * @param integer $size Bit length
 257          * @param float $precision
 258          * @return bool Success
 259          */
 260         abstract protected function doInit( $key, $size, $precision );
 261
 262         /**
 263          * @param string $key
 264          * @param array $members
 265          * @return bool Success
 266          */
 267         abstract protected function doAdd( $key, array $members );
 268
 269         /**
 270          * @param string $key
 271          * @param string $member
 272          * @return bool|null
 273          */
 274         abstract protected function doIsHit( $key, $member );
 275
 276         /**
 277          * @param string $key
 278          * @return bool Success
 279          */
 280         abstract protected function doDelete( $key );
 281
 282         /**
 283          * @param string $virtualKey
 284          * @param array $values
 285          * @return bool Success
 286          */
 287         abstract protected function doSetStatus( $virtualKey, array $values );
 288
 289         /**
 290          * @param string $key
 291          * @return array|bool
 292          */
 293         abstract protected function doGetStatus( $key );
 294 }
 295
 296 class EmptyBloomCache extends BloomCache {
 297         public function __construct( array $config ) {
 298                 parent::__construct( array( 'cacheId' => 'none' ) );
 299         }
 300
 301         protected function doInit( $key, $size, $precision ) {
 302                 return true;
 303         }
 304
 305         protected function doAdd( $key, array $members ) {
 306                 return true;
 307         }
 308
 309         protected function doIsHit( $key, $member ) {
 310                 return true;
 311         }
 312
 313         protected function doDelete( $key ) {
 314                 return true;
 315         }
 316
 317         protected function doSetStatus( $virtualKey, array $values ) {
 318                 return true;
 319         }
 320
 321         protected function doGetStatus( $virtualKey ) {
 322                 return array( 'lastID' => null, 'asOfTime' => null, 'epoch' => null );
 323         }
 324 }