diff options
Diffstat (limited to 'www/wiki/includes/cache/BacklinkCache.php')
-rw-r--r-- | www/wiki/includes/cache/BacklinkCache.php | 578 |
1 files changed, 578 insertions, 0 deletions
diff --git a/www/wiki/includes/cache/BacklinkCache.php b/www/wiki/includes/cache/BacklinkCache.php new file mode 100644 index 00000000..48809d07 --- /dev/null +++ b/www/wiki/includes/cache/BacklinkCache.php @@ -0,0 +1,578 @@ +<?php +/** + * Class for fetching backlink lists, approximate backlink counts and + * partitions. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * http://www.gnu.org/copyleft/gpl.html + * + * @file + * @author Tim Starling + * @copyright © 2009, Tim Starling, Domas Mituzas + * @copyright © 2010, Max Sem + * @copyright © 2011, Antoine Musso + */ + +use Wikimedia\Rdbms\ResultWrapper; +use Wikimedia\Rdbms\FakeResultWrapper; +use Wikimedia\Rdbms\IDatabase; +use MediaWiki\MediaWikiServices; + +/** + * Class for fetching backlink lists, approximate backlink counts and + * partitions. This is a shared cache. + * + * Instances of this class should typically be fetched with the method + * $title->getBacklinkCache(). + * + * Ideally you should only get your backlinks from here when you think + * there is some advantage in caching them. Otherwise it's just a waste + * of memory. + * + * Introduced by r47317 + */ +class BacklinkCache { + /** @var BacklinkCache */ + protected static $instance; + + /** + * Multi dimensions array representing batches. Keys are: + * > (string) links table name + * > (int) batch size + * > 'numRows' : Number of rows for this link table + * > 'batches' : [ $start, $end ] + * + * @see BacklinkCache::partitionResult() + * + * Cleared with BacklinkCache::clear() + * @var array[] + */ + protected $partitionCache = []; + + /** + * Contains the whole links from a database result. + * This is raw data that will be partitioned in $partitionCache + * + * Initialized with BacklinkCache::getLinks() + * Cleared with BacklinkCache::clear() + * @var ResultWrapper[] + */ + protected $fullResultCache = []; + + /** + * @var WANObjectCache + */ + protected $wanCache; + + /** + * Local copy of a database object. + * + * Accessor: BacklinkCache::getDB() + * Mutator : BacklinkCache::setDB() + * Cleared with BacklinkCache::clear() + */ + protected $db; + + /** + * Local copy of a Title object + */ + protected $title; + + const CACHE_EXPIRY = 3600; + + /** + * Create a new BacklinkCache + * + * @param Title $title : Title object to create a backlink cache for + */ + public function __construct( Title $title ) { + $this->title = $title; + $this->wanCache = MediaWikiServices::getInstance()->getMainWANObjectCache(); + } + + /** + * Create a new BacklinkCache or reuse any existing one. + * Currently, only one cache instance can exist; callers that + * need multiple backlink cache objects should keep them in scope. + * + * @param Title $title Title object to get a backlink cache for + * @return BacklinkCache + */ + public static function get( Title $title ) { + if ( !self::$instance || !self::$instance->title->equals( $title ) ) { + self::$instance = new self( $title ); + } + return self::$instance; + } + + /** + * Serialization handler, diasallows to serialize the database to prevent + * failures after this class is deserialized from cache with dead DB + * connection. + * + * @return array + */ + function __sleep() { + return [ 'partitionCache', 'fullResultCache', 'title' ]; + } + + /** + * Clear locally stored data and database object. Invalidate data in memcache. + */ + public function clear() { + $this->partitionCache = []; + $this->fullResultCache = []; + $this->wanCache->touchCheckKey( $this->makeCheckKey() ); + unset( $this->db ); + } + + /** + * Set the Database object to use + * + * @param IDatabase $db + */ + public function setDB( $db ) { + $this->db = $db; + } + + /** + * Get the replica DB connection to the database + * When non existing, will initialize the connection. + * @return IDatabase + */ + protected function getDB() { + if ( !isset( $this->db ) ) { + $this->db = wfGetDB( DB_REPLICA ); + } + + return $this->db; + } + + /** + * Get the backlinks for a given table. Cached in process memory only. + * @param string $table + * @param int|bool $startId + * @param int|bool $endId + * @param int $max + * @return TitleArrayFromResult + */ + public function getLinks( $table, $startId = false, $endId = false, $max = INF ) { + return TitleArray::newFromResult( $this->queryLinks( $table, $startId, $endId, $max ) ); + } + + /** + * Get the backlinks for a given table. Cached in process memory only. + * @param string $table + * @param int|bool $startId + * @param int|bool $endId + * @param int $max + * @param string $select 'all' or 'ids' + * @return ResultWrapper + */ + protected function queryLinks( $table, $startId, $endId, $max, $select = 'all' ) { + $fromField = $this->getPrefix( $table ) . '_from'; + + if ( !$startId && !$endId && is_infinite( $max ) + && isset( $this->fullResultCache[$table] ) + ) { + wfDebug( __METHOD__ . ": got results from cache\n" ); + $res = $this->fullResultCache[$table]; + } else { + wfDebug( __METHOD__ . ": got results from DB\n" ); + $conds = $this->getConditions( $table ); + // Use the from field in the condition rather than the joined page_id, + // because databases are stupid and don't necessarily propagate indexes. + if ( $startId ) { + $conds[] = "$fromField >= " . intval( $startId ); + } + if ( $endId ) { + $conds[] = "$fromField <= " . intval( $endId ); + } + $options = [ 'ORDER BY' => $fromField ]; + if ( is_finite( $max ) && $max > 0 ) { + $options['LIMIT'] = $max; + } + + if ( $select === 'ids' ) { + // Just select from the backlink table and ignore the page JOIN + $res = $this->getDB()->select( + $table, + [ $this->getPrefix( $table ) . '_from AS page_id' ], + array_filter( $conds, function ( $clause ) { // kind of janky + return !preg_match( '/(\b|=)page_id(\b|=)/', $clause ); + } ), + __METHOD__, + $options + ); + } else { + // Select from the backlink table and JOIN with page title information + $res = $this->getDB()->select( + [ $table, 'page' ], + [ 'page_namespace', 'page_title', 'page_id' ], + $conds, + __METHOD__, + array_merge( [ 'STRAIGHT_JOIN' ], $options ) + ); + } + + if ( $select === 'all' && !$startId && !$endId && $res->numRows() < $max ) { + // The full results fit within the limit, so cache them + $this->fullResultCache[$table] = $res; + } else { + wfDebug( __METHOD__ . ": results from DB were uncacheable\n" ); + } + } + + return $res; + } + + /** + * Get the field name prefix for a given table + * @param string $table + * @throws MWException + * @return null|string + */ + protected function getPrefix( $table ) { + static $prefixes = [ + 'pagelinks' => 'pl', + 'imagelinks' => 'il', + 'categorylinks' => 'cl', + 'templatelinks' => 'tl', + 'redirect' => 'rd', + ]; + + if ( isset( $prefixes[$table] ) ) { + return $prefixes[$table]; + } else { + $prefix = null; + Hooks::run( 'BacklinkCacheGetPrefix', [ $table, &$prefix ] ); + if ( $prefix ) { + return $prefix; + } else { + throw new MWException( "Invalid table \"$table\" in " . __CLASS__ ); + } + } + } + + /** + * Get the SQL condition array for selecting backlinks, with a join + * on the page table. + * @param string $table + * @throws MWException + * @return array|null + */ + protected function getConditions( $table ) { + $prefix = $this->getPrefix( $table ); + + switch ( $table ) { + case 'pagelinks': + case 'templatelinks': + $conds = [ + "{$prefix}_namespace" => $this->title->getNamespace(), + "{$prefix}_title" => $this->title->getDBkey(), + "page_id={$prefix}_from" + ]; + break; + case 'redirect': + $conds = [ + "{$prefix}_namespace" => $this->title->getNamespace(), + "{$prefix}_title" => $this->title->getDBkey(), + $this->getDB()->makeList( [ + "{$prefix}_interwiki" => '', + "{$prefix}_interwiki IS NULL", + ], LIST_OR ), + "page_id={$prefix}_from" + ]; + break; + case 'imagelinks': + case 'categorylinks': + $conds = [ + "{$prefix}_to" => $this->title->getDBkey(), + "page_id={$prefix}_from" + ]; + break; + default: + $conds = null; + Hooks::run( 'BacklinkCacheGetConditions', [ $table, $this->title, &$conds ] ); + if ( !$conds ) { + throw new MWException( "Invalid table \"$table\" in " . __CLASS__ ); + } + } + + return $conds; + } + + /** + * Check if there are any backlinks + * @param string $table + * @return bool + */ + public function hasLinks( $table ) { + return ( $this->getNumLinks( $table, 1 ) > 0 ); + } + + /** + * Get the approximate number of backlinks + * @param string $table + * @param int $max Only count up to this many backlinks + * @return int + */ + public function getNumLinks( $table, $max = INF ) { + global $wgUpdateRowsPerJob; + + // 1) try partition cache ... + if ( isset( $this->partitionCache[$table] ) ) { + $entry = reset( $this->partitionCache[$table] ); + + return min( $max, $entry['numRows'] ); + } + + // 2) ... then try full result cache ... + if ( isset( $this->fullResultCache[$table] ) ) { + return min( $max, $this->fullResultCache[$table]->numRows() ); + } + + $memcKey = $this->wanCache->makeKey( + 'numbacklinks', + md5( $this->title->getPrefixedDBkey() ), + $table + ); + + // 3) ... fallback to memcached ... + $curTTL = INF; + $count = $this->wanCache->get( + $memcKey, + $curTTL, + [ + $this->makeCheckKey() + ] + ); + if ( $count && ( $curTTL > 0 ) ) { + return min( $max, $count ); + } + + // 4) fetch from the database ... + if ( is_infinite( $max ) ) { // no limit at all + // Use partition() since it will batch the query and skip the JOIN. + // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs. + $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache + return $this->partitionCache[$table][$wgUpdateRowsPerJob]['numRows']; + } else { // probably some sane limit + // Fetch the full title info, since the caller will likely need it next + $count = $this->getLinks( $table, false, false, $max )->count(); + if ( $count < $max ) { // full count + $this->wanCache->set( $memcKey, $count, self::CACHE_EXPIRY ); + } + } + + return min( $max, $count ); + } + + /** + * Partition the backlinks into batches. + * Returns an array giving the start and end of each range. The first + * batch has a start of false, and the last batch has an end of false. + * + * @param string $table The links table name + * @param int $batchSize + * @return array + */ + public function partition( $table, $batchSize ) { + // 1) try partition cache ... + if ( isset( $this->partitionCache[$table][$batchSize] ) ) { + wfDebug( __METHOD__ . ": got from partition cache\n" ); + + return $this->partitionCache[$table][$batchSize]['batches']; + } + + $this->partitionCache[$table][$batchSize] = false; + $cacheEntry =& $this->partitionCache[$table][$batchSize]; + + // 2) ... then try full result cache ... + if ( isset( $this->fullResultCache[$table] ) ) { + $cacheEntry = $this->partitionResult( $this->fullResultCache[$table], $batchSize ); + wfDebug( __METHOD__ . ": got from full result cache\n" ); + + return $cacheEntry['batches']; + } + + $memcKey = $this->wanCache->makeKey( + 'backlinks', + md5( $this->title->getPrefixedDBkey() ), + $table, + $batchSize + ); + + // 3) ... fallback to memcached ... + $curTTL = 0; + $memcValue = $this->wanCache->get( + $memcKey, + $curTTL, + [ + $this->makeCheckKey() + ] + ); + if ( is_array( $memcValue ) && ( $curTTL > 0 ) ) { + $cacheEntry = $memcValue; + wfDebug( __METHOD__ . ": got from memcached $memcKey\n" ); + + return $cacheEntry['batches']; + } + + // 4) ... finally fetch from the slow database :( + $cacheEntry = [ 'numRows' => 0, 'batches' => [] ]; // final result + // Do the selects in batches to avoid client-side OOMs (T45452). + // Use a LIMIT that plays well with $batchSize to keep equal sized partitions. + $selectSize = max( $batchSize, 200000 - ( 200000 % $batchSize ) ); + $start = false; + do { + $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' ); + $partitions = $this->partitionResult( $res, $batchSize, false ); + // Merge the link count and range partitions for this chunk + $cacheEntry['numRows'] += $partitions['numRows']; + $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] ); + if ( count( $partitions['batches'] ) ) { + list( , $lEnd ) = end( $partitions['batches'] ); + $start = $lEnd + 1; // pick up after this inclusive range + } + } while ( $partitions['numRows'] >= $selectSize ); + // Make sure the first range has start=false and the last one has end=false + if ( count( $cacheEntry['batches'] ) ) { + $cacheEntry['batches'][0][0] = false; + $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false; + } + + // Save partitions to memcached + $this->wanCache->set( $memcKey, $cacheEntry, self::CACHE_EXPIRY ); + + // Save backlink count to memcached + $memcKey = $this->wanCache->makeKey( + 'numbacklinks', + md5( $this->title->getPrefixedDBkey() ), + $table + ); + $this->wanCache->set( $memcKey, $cacheEntry['numRows'], self::CACHE_EXPIRY ); + + wfDebug( __METHOD__ . ": got from database\n" ); + + return $cacheEntry['batches']; + } + + /** + * Partition a DB result with backlinks in it into batches + * @param ResultWrapper $res Database result + * @param int $batchSize + * @param bool $isComplete Whether $res includes all the backlinks + * @throws MWException + * @return array + */ + protected function partitionResult( $res, $batchSize, $isComplete = true ) { + $batches = []; + $numRows = $res->numRows(); + $numBatches = ceil( $numRows / $batchSize ); + + for ( $i = 0; $i < $numBatches; $i++ ) { + if ( $i == 0 && $isComplete ) { + $start = false; + } else { + $rowNum = $i * $batchSize; + $res->seek( $rowNum ); + $row = $res->fetchObject(); + $start = (int)$row->page_id; + } + + if ( $i == ( $numBatches - 1 ) && $isComplete ) { + $end = false; + } else { + $rowNum = min( $numRows - 1, ( $i + 1 ) * $batchSize - 1 ); + $res->seek( $rowNum ); + $row = $res->fetchObject(); + $end = (int)$row->page_id; + } + + # Sanity check order + if ( $start && $end && $start > $end ) { + throw new MWException( __METHOD__ . ': Internal error: query result out of order' ); + } + + $batches[] = [ $start, $end ]; + } + + return [ 'numRows' => $numRows, 'batches' => $batches ]; + } + + /** + * Get a Title iterator for cascade-protected template/file use backlinks + * + * @return TitleArray + * @since 1.25 + */ + public function getCascadeProtectedLinks() { + $dbr = $this->getDB(); + + // @todo: use UNION without breaking tests that use temp tables + $resSets = []; + $resSets[] = $dbr->select( + [ 'templatelinks', 'page_restrictions', 'page' ], + [ 'page_namespace', 'page_title', 'page_id' ], + [ + 'tl_namespace' => $this->title->getNamespace(), + 'tl_title' => $this->title->getDBkey(), + 'tl_from = pr_page', + 'pr_cascade' => 1, + 'page_id = tl_from' + ], + __METHOD__, + [ 'DISTINCT' ] + ); + if ( $this->title->getNamespace() == NS_FILE ) { + $resSets[] = $dbr->select( + [ 'imagelinks', 'page_restrictions', 'page' ], + [ 'page_namespace', 'page_title', 'page_id' ], + [ + 'il_to' => $this->title->getDBkey(), + 'il_from = pr_page', + 'pr_cascade' => 1, + 'page_id = il_from' + ], + __METHOD__, + [ 'DISTINCT' ] + ); + } + + // Combine and de-duplicate the results + $mergedRes = []; + foreach ( $resSets as $res ) { + foreach ( $res as $row ) { + $mergedRes[$row->page_id] = $row; + } + } + + return TitleArray::newFromResult( + new FakeResultWrapper( array_values( $mergedRes ) ) ); + } + + /** + * Returns check key for the backlinks cache for a particular title + * + * @return String + */ + private function makeCheckKey() { + return $this->wanCache->makeKey( + 'backlinks', + md5( $this->title->getPrefixedDBkey() ) + ); + } +} |