includes/cache/BacklinkCache.php

   1 <?php
   2 /**
   3  * Class for fetching backlink lists, approximate backlink counts and
   4  * partitions.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program; if not, write to the Free Software Foundation, Inc.,
  18  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19  * http://www.gnu.org/copyleft/gpl.html
  20  *
  21  * @file
  22  * @author Tim Starling
  23  * @author Aaron Schulz
  24  * @copyright © 2009, Tim Starling, Domas Mituzas
  25  * @copyright © 2010, Max Sem
  26  * @copyright © 2011, Antoine Musso
  27  */
  28
  29 /**
  30  * Class for fetching backlink lists, approximate backlink counts and
  31  * partitions. This is a shared cache.
  32  *
  33  * Instances of this class should typically be fetched with the method
  34  * $title->getBacklinkCache().
  35  *
  36  * Ideally you should only get your backlinks from here when you think
  37  * there is some advantage in caching them. Otherwise it's just a waste
  38  * of memory.
  39  *
  40  * Introduced by r47317
  41  *
  42  * @internal documentation reviewed on 18 Mar 2011 by hashar
  43  */
  44 class BacklinkCache {
  45         /** @var ProcessCacheLRU */
  46         protected static $cache;
  47
  48         /**
  49          * Multi dimensions array representing batches. Keys are:
  50          *  > (string) links table name
  51          *    > 'numRows' : Number of rows for this link table
  52          *    > 'batches' : array( $start, $end )
  53          *
  54          * @see BacklinkCache::partitionResult()
  55          *
  56          * Cleared with BacklinkCache::clear()
  57          */
  58         protected $partitionCache = array();
  59
  60         /**
  61          * Contains the whole links from a database result.
  62          * This is raw data that will be partitioned in $partitionCache
  63          *
  64          * Initialized with BacklinkCache::getLinks()
  65          * Cleared with BacklinkCache::clear()
  66          */
  67         protected $fullResultCache = array();
  68
  69         /**
  70          * Local copy of a database object.
  71          *
  72          * Accessor: BacklinkCache::getDB()
  73          * Mutator : BacklinkCache::setDB()
  74          * Cleared with BacklinkCache::clear()
  75          */
  76         protected $db;
  77
  78         /**
  79          * Local copy of a Title object
  80          */
  81         protected $title;
  82
  83         const CACHE_EXPIRY = 3600;
  84
  85         /**
  86          * Create a new BacklinkCache
  87          *
  88          * @param Title $title : Title object to create a backlink cache for
  89          */
  90         public function __construct( Title $title ) {
  91                 $this->title = $title;
  92         }
  93
  94         /**
  95          * Create a new BacklinkCache or reuse any existing one.
  96          * Currently, only one cache instance can exist; callers that
  97          * need multiple backlink cache objects should keep them in scope.
  98          *
  99          * @param Title $title : Title object to get a backlink cache for
 100          * @return BacklinkCache
 101          */
 102         public static function get( Title $title ) {
 103                 if ( !self::$cache ) { // init cache
 104                         self::$cache = new ProcessCacheLRU( 1 );
 105                 }
 106                 $dbKey = $title->getPrefixedDBkey();
 107                 if ( !self::$cache->has( $dbKey, 'obj', 3600 ) ) {
 108                         self::$cache->set( $dbKey, 'obj', new self( $title ) );
 109                 }
 110                 return self::$cache->get( $dbKey, 'obj' );
 111         }
 112
 113         /**
 114          * Serialization handler, diasallows to serialize the database to prevent
 115          * failures after this class is deserialized from cache with dead DB
 116          * connection.
 117          *
 118          * @return array
 119          */
 120         function __sleep() {
 121                 return array( 'partitionCache', 'fullResultCache', 'title' );
 122         }
 123
 124         /**
 125          * Clear locally stored data and database object.
 126          */
 127         public function clear() {
 128                 $this->partitionCache = array();
 129                 $this->fullResultCache = array();
 130                 unset( $this->db );
 131         }
 132
 133         /**
 134          * Set the Database object to use
 135          *
 136          * @param $db DatabaseBase
 137          */
 138         public function setDB( $db ) {
 139                 $this->db = $db;
 140         }
 141
 142         /**
 143          * Get the slave connection to the database
 144          * When non existing, will initialize the connection.
 145          * @return DatabaseBase object
 146          */
 147         protected function getDB() {
 148                 if ( !isset( $this->db ) ) {
 149                         $this->db = wfGetDB( DB_SLAVE );
 150                 }
 151                 return $this->db;
 152         }
 153
 154         /**
 155          * Get the backlinks for a given table. Cached in process memory only.
 156          * @param $table String
 157          * @param $startId Integer|false
 158          * @param $endId Integer|false
 159          * @param $max Integer|INF
 160          * @return TitleArrayFromResult
 161          */
 162         public function getLinks( $table, $startId = false, $endId = false, $max = INF ) {
 163                 return TitleArray::newFromResult( $this->queryLinks( $table, $startId, $endId, $max ) );
 164         }
 165
 166         /**
 167          * Get the backlinks for a given table. Cached in process memory only.
 168          * @param $table String
 169          * @param $startId Integer|false
 170          * @param $endId Integer|false
 171          * @param $max Integer|INF
 172          * @return ResultWrapper
 173          */
 174         protected function queryLinks( $table, $startId, $endId, $max ) {
 175                 wfProfileIn( __METHOD__ );
 176
 177                 $fromField = $this->getPrefix( $table ) . '_from';
 178
 179                 if ( !$startId && !$endId && is_infinite( $max )
 180                         && isset( $this->fullResultCache[$table] ) )
 181                 {
 182                         wfDebug( __METHOD__ . ": got results from cache\n" );
 183                         $res = $this->fullResultCache[$table];
 184                 } else {
 185                         wfDebug( __METHOD__ . ": got results from DB\n" );
 186                         $conds = $this->getConditions( $table );
 187                         // Use the from field in the condition rather than the joined page_id,
 188                         // because databases are stupid and don't necessarily propagate indexes.
 189                         if ( $startId ) {
 190                                 $conds[] = "$fromField >= " . intval( $startId );
 191                         }
 192                         if ( $endId ) {
 193                                 $conds[] = "$fromField <= " . intval( $endId );
 194                         }
 195                         $options = array( 'STRAIGHT_JOIN', 'ORDER BY' => $fromField );
 196                         if ( is_finite( $max ) && $max > 0 ) {
 197                                 $options['LIMIT'] = $max;
 198                         }
 199
 200                         $res = $this->getDB()->select(
 201                                 array( $table, 'page' ),
 202                                 array( 'page_namespace', 'page_title', 'page_id' ),
 203                                 $conds,
 204                                 __METHOD__,
 205                                 $options
 206                         );
 207
 208                         if ( !$startId && !$endId && $res->numRows() < $max ) {
 209                                 // The full results fit within the limit, so cache them
 210                                 $this->fullResultCache[$table] = $res;
 211                         } else {
 212                                 wfDebug( __METHOD__ . ": results from DB were uncacheable\n" );
 213                         }
 214                 }
 215
 216                 wfProfileOut( __METHOD__ );
 217                 return $res;
 218         }
 219
 220         /**
 221          * Get the field name prefix for a given table
 222          * @param $table String
 223          * @throws MWException
 224          * @return null|string
 225          */
 226         protected function getPrefix( $table ) {
 227                 static $prefixes = array(
 228                         'pagelinks' => 'pl',
 229                         'imagelinks' => 'il',
 230                         'categorylinks' => 'cl',
 231                         'templatelinks' => 'tl',
 232                         'redirect' => 'rd',
 233                 );
 234
 235                 if ( isset( $prefixes[$table] ) ) {
 236                         return $prefixes[$table];
 237                 } else {
 238                         $prefix = null;
 239                         wfRunHooks( 'BacklinkCacheGetPrefix', array( $table, &$prefix ) );
 240                         if ( $prefix ) {
 241                                 return $prefix;
 242                         } else {
 243                                 throw new MWException( "Invalid table \"$table\" in " . __CLASS__ );
 244                         }
 245                 }
 246         }
 247
 248         /**
 249          * Get the SQL condition array for selecting backlinks, with a join
 250          * on the page table.
 251          * @param $table String
 252          * @throws MWException
 253          * @return array|null
 254          */
 255         protected function getConditions( $table ) {
 256                 $prefix = $this->getPrefix( $table );
 257
 258                 // @todo FIXME: imagelinks and categorylinks do not rely on getNamespace,
 259                 // they could be moved up for nicer case statements
 260                 switch ( $table ) {
 261                         case 'pagelinks':
 262                         case 'templatelinks':
 263                                 $conds = array(
 264                                         "{$prefix}_namespace" => $this->title->getNamespace(),
 265                                         "{$prefix}_title" => $this->title->getDBkey(),
 266                                         "page_id={$prefix}_from"
 267                                 );
 268                                 break;
 269                         case 'redirect':
 270                                 $conds = array(
 271                                         "{$prefix}_namespace" => $this->title->getNamespace(),
 272                                         "{$prefix}_title" => $this->title->getDBkey(),
 273                                         $this->getDb()->makeList( array(
 274                                                 "{$prefix}_interwiki" => '',
 275                                                 "{$prefix}_interwiki IS NULL",
 276                                         ), LIST_OR ),
 277                                         "page_id={$prefix}_from"
 278                                 );
 279                                 break;
 280                         case 'imagelinks':
 281                                 $conds = array(
 282                                         'il_to' => $this->title->getDBkey(),
 283                                         'page_id=il_from'
 284                                 );
 285                                 break;
 286                         case 'categorylinks':
 287                                 $conds = array(
 288                                         'cl_to' => $this->title->getDBkey(),
 289                                         'page_id=cl_from',
 290                                 );
 291                                 break;
 292                         default:
 293                                 $conds = null;
 294                                 wfRunHooks( 'BacklinkCacheGetConditions', array( $table, $this->title, &$conds ) );
 295                                 if ( !$conds ) {
 296                                         throw new MWException( "Invalid table \"$table\" in " . __CLASS__ );
 297                                 }
 298                 }
 299
 300                 return $conds;
 301         }
 302
 303         /**
 304          * Check if there are any backlinks
 305          * @param $table String
 306          * @return bool
 307          */
 308         public function hasLinks( $table ) {
 309                 return ( $this->getNumLinks( $table, 1 ) > 0 );
 310         }
 311
 312         /**
 313          * Get the approximate number of backlinks
 314          * @param $table String
 315          * @param $max integer|INF Only count up to this many backlinks
 316          * @return integer
 317          */
 318         public function getNumLinks( $table, $max = INF ) {
 319                 global $wgMemc;
 320
 321                 // 1) try partition cache ...
 322                 if ( isset( $this->partitionCache[$table] ) ) {
 323                         $entry = reset( $this->partitionCache[$table] );
 324                         return min( $max, $entry['numRows'] );
 325                 }
 326
 327                 // 2) ... then try full result cache ...
 328                 if ( isset( $this->fullResultCache[$table] ) ) {
 329                         return min( $max, $this->fullResultCache[$table]->numRows() );
 330                 }
 331
 332                 $memcKey = wfMemcKey( 'numbacklinks', md5( $this->title->getPrefixedDBkey() ), $table );
 333
 334                 // 3) ... fallback to memcached ...
 335                 $count = $wgMemc->get( $memcKey );
 336                 if ( $count ) {
 337                         return min( $max, $count );
 338                 }
 339
 340                 // 4) fetch from the database ...
 341                 $count = $this->getLinks( $table, false, false, $max )->count();
 342                 if ( $count < $max ) { // full count
 343                         $wgMemc->set( $memcKey, $count, self::CACHE_EXPIRY );
 344                 }
 345
 346                 return min( $max, $count );
 347         }
 348
 349         /**
 350          * Partition the backlinks into batches.
 351          * Returns an array giving the start and end of each range. The first
 352          * batch has a start of false, and the last batch has an end of false.
 353          *
 354          * @param string $table the links table name
 355          * @param $batchSize Integer
 356          * @return Array
 357          */
 358         public function partition( $table, $batchSize ) {
 359                 global $wgMemc;
 360
 361                 // 1) try partition cache ...
 362                 if ( isset( $this->partitionCache[$table][$batchSize] ) ) {
 363                         wfDebug( __METHOD__ . ": got from partition cache\n" );
 364                         return $this->partitionCache[$table][$batchSize]['batches'];
 365                 }
 366
 367                 $this->partitionCache[$table][$batchSize] = false;
 368                 $cacheEntry =& $this->partitionCache[$table][$batchSize];
 369
 370                 // 2) ... then try full result cache ...
 371                 if ( isset( $this->fullResultCache[$table] ) ) {
 372                         $cacheEntry = $this->partitionResult( $this->fullResultCache[$table], $batchSize );
 373                         wfDebug( __METHOD__ . ": got from full result cache\n" );
 374                         return $cacheEntry['batches'];
 375                 }
 376
 377                 $memcKey = wfMemcKey(
 378                         'backlinks',
 379                         md5( $this->title->getPrefixedDBkey() ),
 380                         $table,
 381                         $batchSize
 382                 );
 383
 384                 // 3) ... fallback to memcached ...
 385                 $memcValue = $wgMemc->get( $memcKey );
 386                 if ( is_array( $memcValue ) ) {
 387                         $cacheEntry = $memcValue;
 388                         wfDebug( __METHOD__ . ": got from memcached $memcKey\n" );
 389                         return $cacheEntry['batches'];
 390                 }
 391
 392                 // 4) ... finally fetch from the slow database :(
 393                 $cacheEntry = array( 'numRows' => 0, 'batches' => array() ); // final result
 394                 // Do the selects in batches to avoid client-side OOMs (bug 43452).
 395                 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
 396                 $selectSize = max( $batchSize, 200000 - ( 200000 % $batchSize ) );
 397                 $start = false;
 398                 do {
 399                         $res = $this->queryLinks( $table, $start, false, $selectSize );
 400                         $partitions = $this->partitionResult( $res, $batchSize, false );
 401                         // Merge the link count and range partitions for this chunk
 402                         $cacheEntry['numRows'] += $partitions['numRows'];
 403                         $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
 404                         if ( count( $partitions['batches'] ) ) {
 405                                 list( $lStart, $lEnd ) = end( $partitions['batches'] );
 406                                 $start = $lEnd + 1; // pick up after this inclusive range
 407                         }
 408                 } while ( $partitions['numRows'] >= $selectSize );
 409                 // Make sure the first range has start=false and the last one has end=false
 410                 if ( count( $cacheEntry['batches'] ) ) {
 411                         $cacheEntry['batches'][0][0] = false;
 412                         $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
 413                 }
 414
 415                 // Save partitions to memcached
 416                 $wgMemc->set( $memcKey, $cacheEntry, self::CACHE_EXPIRY );
 417
 418                 // Save backlink count to memcached
 419                 $memcKey = wfMemcKey( 'numbacklinks', md5( $this->title->getPrefixedDBkey() ), $table );
 420                 $wgMemc->set( $memcKey, $cacheEntry['numRows'], self::CACHE_EXPIRY );
 421
 422                 wfDebug( __METHOD__ . ": got from database\n" );
 423                 return $cacheEntry['batches'];
 424         }
 425
 426         /**
 427          * Partition a DB result with backlinks in it into batches
 428          * @param $res ResultWrapper database result
 429          * @param $batchSize integer
 430          * @param $isComplete bool Whether $res includes all the backlinks
 431          * @throws MWException
 432          * @return array
 433          */
 434         protected function partitionResult( $res, $batchSize, $isComplete = true ) {
 435                 $batches = array();
 436                 $numRows = $res->numRows();
 437                 $numBatches = ceil( $numRows / $batchSize );
 438
 439                 for ( $i = 0; $i < $numBatches; $i++ ) {
 440                         if ( $i == 0 && $isComplete ) {
 441                                 $start = false;
 442                         } else {
 443                                 $rowNum = $i * $batchSize;
 444                                 $res->seek( $rowNum );
 445                                 $row = $res->fetchObject();
 446                                 $start = (int)$row->page_id;
 447                         }
 448
 449                         if ( $i == ( $numBatches - 1 ) && $isComplete ) {
 450                                 $end = false;
 451                         } else {
 452                                 $rowNum = min( $numRows - 1, ( $i + 1 ) * $batchSize - 1 );
 453                                 $res->seek( $rowNum );
 454                                 $row = $res->fetchObject();
 455                                 $end = (int)$row->page_id;
 456                         }
 457
 458                         # Sanity check order
 459                         if ( $start && $end && $start > $end ) {
 460                                 throw new MWException( __METHOD__ . ': Internal error: query result out of order' );
 461                         }
 462
 463                         $batches[] = array( $start, $end );
 464                 }
 465
 466                 return array( 'numRows' => $numRows, 'batches' => $batches );
 467         }
 468 }