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