includes/jobqueue/JobQueueFederated.php

   1 <?php
   2 /**
   3  * Job queue code for federated queues.
   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  * @author Aaron Schulz
  22  */
  23
  24 /**
  25  * Class to handle enqueueing and running of background jobs for federated queues
  26  *
  27  * This class allows for queues to be partitioned into smaller queues.
  28  * A partition is defined by the configuration for a JobQueue instance.
  29  * For example, one can set $wgJobTypeConf['refreshLinks'] to point to a
  30  * JobQueueFederated instance, which itself would consist of three JobQueueRedis
  31  * instances, each using their own redis server. This would allow for the jobs
  32  * to be split (evenly or based on weights) accross multiple servers if a single
  33  * server becomes impractical or expensive. Different JobQueue classes can be mixed.
  34  *
  35  * The basic queue configuration (e.g. "order", "claimTTL") of a federated queue
  36  * is inherited by the partition queues. Additional configuration defines what
  37  * section each wiki is in, what partition queues each section uses (and their weight),
  38  * and the JobQueue configuration for each partition. Some sections might only need a
  39  * single queue partition, like the sections for groups of small wikis.
  40  *
  41  * If used for performance, then $wgMainCacheType should be set to memcached/redis.
  42  * Note that "fifo" cannot be used for the ordering, since the data is distributed.
  43  * One can still use "timestamp" instead, as in "roughly timestamp ordered". Also,
  44  * queue classes used by this should ignore down servers (with TTL) to avoid slowness.
  45  *
  46  * @ingroup JobQueue
  47  * @since 1.22
  48  */
  49 class JobQueueFederated extends JobQueue {
  50         /** @var HashRing */
  51         protected $partitionRing;
  52         /** @var array (partition name => JobQueue) reverse sorted by weight */
  53         protected $partitionQueues = array();
  54
  55         /** @var int Maximum number of partitions to try */
  56         protected $maxPartitionsTry;
  57
  58         /**
  59          * @param array $params Possible keys:
  60          *  - sectionsByWiki      : A map of wiki IDs to section names.
  61          *                          Wikis will default to using the section "default".
  62          *  - partitionsBySection : Map of section names to maps of (partition name => weight).
  63          *                          A section called 'default' must be defined if not all wikis
  64          *                          have explicitly defined sections.
  65          *  - configByPartition   : Map of queue partition names to configuration arrays.
  66          *                          These configuration arrays are passed to JobQueue::factory().
  67          *                          The options set here are overridden by those passed to this
  68          *                          the federated queue itself (e.g. 'order' and 'claimTTL').
  69          *  - maxPartitionsTry    : Maximum number of times to attempt job insertion using
  70          *                          different partition queues. This improves availability
  71          *                          during failure, at the cost of added latency and somewhat
  72          *                          less reliable job de-duplication mechanisms.
  73          * @throws MWException
  74          */
  75         protected function __construct( array $params ) {
  76                 parent::__construct( $params );
  77                 $section = isset( $params['sectionsByWiki'][$this->wiki] )
  78                         ? $params['sectionsByWiki'][$this->wiki]
  79                         : 'default';
  80                 if ( !isset( $params['partitionsBySection'][$section] ) ) {
  81                         throw new MWException( "No configuration for section '$section'." );
  82                 }
  83                 $this->maxPartitionsTry = isset( $params['maxPartitionsTry'] )
  84                         ? $params['maxPartitionsTry']
  85                         : 2;
  86                 // Get the full partition map
  87                 $partitionMap = $params['partitionsBySection'][$section];
  88                 arsort( $partitionMap, SORT_NUMERIC );
  89                 // Get the config to pass to merge into each partition queue config
  90                 $baseConfig = $params;
  91                 foreach ( array( 'class', 'sectionsByWiki', 'maxPartitionsTry',
  92                         'partitionsBySection', 'configByPartition', ) as $o
  93                 ) {
  94                         unset( $baseConfig[$o] ); // partition queue doesn't care about this
  95                 }
  96                 // Get the partition queue objects
  97                 foreach ( $partitionMap as $partition => $w ) {
  98                         if ( !isset( $params['configByPartition'][$partition] ) ) {
  99                                 throw new MWException( "No configuration for partition '$partition'." );
 100                         }
 101                         $this->partitionQueues[$partition] = JobQueue::factory(
 102                                 $baseConfig + $params['configByPartition'][$partition] );
 103                 }
 104                 // Ring of all partitions
 105                 $this->partitionRing = new HashRing( $partitionMap );
 106         }
 107
 108         protected function supportedOrders() {
 109                 // No FIFO due to partitioning, though "rough timestamp order" is supported
 110                 return array( 'undefined', 'random', 'timestamp' );
 111         }
 112
 113         protected function optimalOrder() {
 114                 return 'undefined'; // defer to the partitions
 115         }
 116
 117         protected function supportsDelayedJobs() {
 118                 foreach ( $this->partitionQueues as $queue ) {
 119                         if ( !$queue->supportsDelayedJobs() ) {
 120                                 return false;
 121                         }
 122                 }
 123
 124                 return true;
 125         }
 126
 127         protected function doIsEmpty() {
 128                 $empty = true;
 129                 $failed = 0;
 130                 foreach ( $this->partitionQueues as $queue ) {
 131                         try {
 132                                 $empty = $empty && $queue->doIsEmpty();
 133                         } catch ( JobQueueError $e ) {
 134                                 ++$failed;
 135                                 $this->logException( $e );
 136                         }
 137                 }
 138                 $this->throwErrorIfAllPartitionsDown( $failed );
 139
 140                 return $empty;
 141         }
 142
 143         protected function doGetSize() {
 144                 return $this->getCrossPartitionSum( 'size', 'doGetSize' );
 145         }
 146
 147         protected function doGetAcquiredCount() {
 148                 return $this->getCrossPartitionSum( 'acquiredcount', 'doGetAcquiredCount' );
 149         }
 150
 151         protected function doGetDelayedCount() {
 152                 return $this->getCrossPartitionSum( 'delayedcount', 'doGetDelayedCount' );
 153         }
 154
 155         protected function doGetAbandonedCount() {
 156                 return $this->getCrossPartitionSum( 'abandonedcount', 'doGetAbandonedCount' );
 157         }
 158
 159         /**
 160          * @param string $type
 161          * @param string $method
 162          * @return int
 163          */
 164         protected function getCrossPartitionSum( $type, $method ) {
 165                 $count = 0;
 166                 $failed = 0;
 167                 foreach ( $this->partitionQueues as $queue ) {
 168                         try {
 169                                 $count += $queue->$method();
 170                         } catch ( JobQueueError $e ) {
 171                                 ++$failed;
 172                                 $this->logException( $e );
 173                         }
 174                 }
 175                 $this->throwErrorIfAllPartitionsDown( $failed );
 176
 177                 return $count;
 178         }
 179
 180         protected function doBatchPush( array $jobs, $flags ) {
 181                 // Local ring variable that may be changed to point to a new ring on failure
 182                 $partitionRing = $this->partitionRing;
 183                 // Try to insert the jobs and update $partitionsTry on any failures.
 184                 // Retry to insert any remaning jobs again, ignoring the bad partitions.
 185                 $jobsLeft = $jobs;
 186                 // @codingStandardsIgnoreStart Generic.CodeAnalysis.ForLoopWithTestFunctionCall.NotAllowed
 187                 for ( $i = $this->maxPartitionsTry; $i > 0 && count( $jobsLeft ); --$i ) {
 188                         // @codingStandardsIgnoreEnd
 189                         try {
 190                                 $partitionRing->getLiveRing();
 191                         } catch ( UnexpectedValueException $e ) {
 192                                 break; // all servers down; nothing to insert to
 193                         }
 194                         $jobsLeft = $this->tryJobInsertions( $jobsLeft, $partitionRing, $flags );
 195                 }
 196                 if ( count( $jobsLeft ) ) {
 197                         throw new JobQueueError(
 198                                 "Could not insert job(s), {$this->maxPartitionsTry} partitions tried." );
 199                 }
 200         }
 201
 202         /**
 203          * @param array $jobs
 204          * @param HashRing $partitionRing
 205          * @param int $flags
 206          * @throws JobQueueError
 207          * @return array List of Job object that could not be inserted
 208          */
 209         protected function tryJobInsertions( array $jobs, HashRing &$partitionRing, $flags ) {
 210                 $jobsLeft = array();
 211
 212                 // Because jobs are spread across partitions, per-job de-duplication needs
 213                 // to use a consistent hash to avoid allowing duplicate jobs per partition.
 214                 // When inserting a batch of de-duplicated jobs, QOS_ATOMIC is disregarded.
 215                 $uJobsByPartition = array(); // (partition name => job list)
 216                 /** @var Job $job */
 217                 foreach ( $jobs as $key => $job ) {
 218                         if ( $job->ignoreDuplicates() ) {
 219                                 $sha1 = sha1( serialize( $job->getDeduplicationInfo() ) );
 220                                 $uJobsByPartition[$partitionRing->getLiveLocation( $sha1 )][] = $job;
 221                                 unset( $jobs[$key] );
 222                         }
 223                 }
 224                 // Get the batches of jobs that are not de-duplicated
 225                 if ( $flags & self::QOS_ATOMIC ) {
 226                         $nuJobBatches = array( $jobs ); // all or nothing
 227                 } else {
 228                         // Split the jobs into batches and spread them out over servers if there
 229                         // are many jobs. This helps keep the partitions even. Otherwise, send all
 230                         // the jobs to a single partition queue to avoids the extra connections.
 231                         $nuJobBatches = array_chunk( $jobs, 300 );
 232                 }
 233
 234                 // Insert the de-duplicated jobs into the queues...
 235                 foreach ( $uJobsByPartition as $partition => $jobBatch ) {
 236                         /** @var JobQueue $queue */
 237                         $queue = $this->partitionQueues[$partition];
 238                         try {
 239                                 $ok = true;
 240                                 $queue->doBatchPush( $jobBatch, $flags | self::QOS_ATOMIC );
 241                         } catch ( JobQueueError $e ) {
 242                                 $ok = false;
 243                                 $this->logException( $e );
 244                         }
 245                         if ( !$ok ) {
 246                                 if ( !$partitionRing->ejectFromLiveRing( $partition, 5 ) ) { // blacklist
 247                                         throw new JobQueueError( "Could not insert job(s), no partitions available." );
 248                                 }
 249                                 $jobsLeft = array_merge( $jobsLeft, $jobBatch ); // not inserted
 250                         }
 251                 }
 252
 253                 // Insert the jobs that are not de-duplicated into the queues...
 254                 foreach ( $nuJobBatches as $jobBatch ) {
 255                         $partition = ArrayUtils::pickRandom( $partitionRing->getLiveLocationWeights() );
 256                         $queue = $this->partitionQueues[$partition];
 257                         try {
 258                                 $ok = true;
 259                                 $queue->doBatchPush( $jobBatch, $flags | self::QOS_ATOMIC );
 260                         } catch ( JobQueueError $e ) {
 261                                 $ok = false;
 262                                 $this->logException( $e );
 263                         }
 264                         if ( !$ok ) {
 265                                 if ( !$partitionRing->ejectFromLiveRing( $partition, 5 ) ) { // blacklist
 266                                         throw new JobQueueError( "Could not insert job(s), no partitions available." );
 267                                 }
 268                                 $jobsLeft = array_merge( $jobsLeft, $jobBatch ); // not inserted
 269                         }
 270                 }
 271
 272                 return $jobsLeft;
 273         }
 274
 275         protected function doPop() {
 276                 $partitionsTry = $this->partitionRing->getLiveLocationWeights(); // (partition => weight)
 277
 278                 $failed = 0;
 279                 while ( count( $partitionsTry ) ) {
 280                         $partition = ArrayUtils::pickRandom( $partitionsTry );
 281                         if ( $partition === false ) {
 282                                 break; // all partitions at 0 weight
 283                         }
 284
 285                         /** @var JobQueue $queue */
 286                         $queue = $this->partitionQueues[$partition];
 287                         try {
 288                                 $job = $queue->pop();
 289                         } catch ( JobQueueError $e ) {
 290                                 ++$failed;
 291                                 $this->logException( $e );
 292                                 $job = false;
 293                         }
 294                         if ( $job ) {
 295                                 $job->metadata['QueuePartition'] = $partition;
 296
 297                                 return $job;
 298                         } else {
 299                                 unset( $partitionsTry[$partition] ); // blacklist partition
 300                         }
 301                 }
 302                 $this->throwErrorIfAllPartitionsDown( $failed );
 303
 304                 return false;
 305         }
 306
 307         protected function doAck( Job $job ) {
 308                 if ( !isset( $job->metadata['QueuePartition'] ) ) {
 309                         throw new MWException( "The given job has no defined partition name." );
 310                 }
 311
 312                 return $this->partitionQueues[$job->metadata['QueuePartition']]->ack( $job );
 313         }
 314
 315         protected function doIsRootJobOldDuplicate( Job $job ) {
 316                 $params = $job->getRootJobParams();
 317                 $sigature = $params['rootJobSignature'];
 318                 $partition = $this->partitionRing->getLiveLocation( $sigature );
 319                 try {
 320                         return $this->partitionQueues[$partition]->doIsRootJobOldDuplicate( $job );
 321                 } catch ( JobQueueError $e ) {
 322                         if ( $this->partitionRing->ejectFromLiveRing( $partition, 5 ) ) {
 323                                 $partition = $this->partitionRing->getLiveLocation( $sigature );
 324                                 return $this->partitionQueues[$partition]->doIsRootJobOldDuplicate( $job );
 325                         }
 326                 }
 327
 328                 return false;
 329         }
 330
 331         protected function doDeduplicateRootJob( IJobSpecification $job ) {
 332                 $params = $job->getRootJobParams();
 333                 $sigature = $params['rootJobSignature'];
 334                 $partition = $this->partitionRing->getLiveLocation( $sigature );
 335                 try {
 336                         return $this->partitionQueues[$partition]->doDeduplicateRootJob( $job );
 337                 } catch ( JobQueueError $e ) {
 338                         if ( $this->partitionRing->ejectFromLiveRing( $partition, 5 ) ) {
 339                                 $partition = $this->partitionRing->getLiveLocation( $sigature );
 340                                 return $this->partitionQueues[$partition]->doDeduplicateRootJob( $job );
 341                         }
 342                 }
 343
 344                 return false;
 345         }
 346
 347         protected function doDelete() {
 348                 $failed = 0;
 349                 /** @var JobQueue $queue */
 350                 foreach ( $this->partitionQueues as $queue ) {
 351                         try {
 352                                 $queue->doDelete();
 353                         } catch ( JobQueueError $e ) {
 354                                 ++$failed;
 355                                 $this->logException( $e );
 356                         }
 357                 }
 358                 $this->throwErrorIfAllPartitionsDown( $failed );
 359                 return true;
 360         }
 361
 362         protected function doWaitForBackups() {
 363                 $failed = 0;
 364                 /** @var JobQueue $queue */
 365                 foreach ( $this->partitionQueues as $queue ) {
 366                         try {
 367                                 $queue->waitForBackups();
 368                         } catch ( JobQueueError $e ) {
 369                                 ++$failed;
 370                                 $this->logException( $e );
 371                         }
 372                 }
 373                 $this->throwErrorIfAllPartitionsDown( $failed );
 374         }
 375
 376         protected function doFlushCaches() {
 377                 /** @var JobQueue $queue */
 378                 foreach ( $this->partitionQueues as $queue ) {
 379                         $queue->doFlushCaches();
 380                 }
 381         }
 382
 383         public function getAllQueuedJobs() {
 384                 $iterator = new AppendIterator();
 385
 386                 /** @var JobQueue $queue */
 387                 foreach ( $this->partitionQueues as $queue ) {
 388                         $iterator->append( $queue->getAllQueuedJobs() );
 389                 }
 390
 391                 return $iterator;
 392         }
 393
 394         public function getAllDelayedJobs() {
 395                 $iterator = new AppendIterator();
 396
 397                 /** @var JobQueue $queue */
 398                 foreach ( $this->partitionQueues as $queue ) {
 399                         $iterator->append( $queue->getAllDelayedJobs() );
 400                 }
 401
 402                 return $iterator;
 403         }
 404
 405         public function getAllAcquiredJobs() {
 406                 $iterator = new AppendIterator();
 407
 408                 /** @var JobQueue $queue */
 409                 foreach ( $this->partitionQueues as $queue ) {
 410                         $iterator->append( $queue->getAllAcquiredJobs() );
 411                 }
 412
 413                 return $iterator;
 414         }
 415
 416         public function getAllAbandonedJobs() {
 417                 $iterator = new AppendIterator();
 418
 419                 /** @var JobQueue $queue */
 420                 foreach ( $this->partitionQueues as $queue ) {
 421                         $iterator->append( $queue->getAllAbandonedJobs() );
 422                 }
 423
 424                 return $iterator;
 425         }
 426
 427         public function getCoalesceLocationInternal() {
 428                 return "JobQueueFederated:wiki:{$this->wiki}" .
 429                         sha1( serialize( array_keys( $this->partitionQueues ) ) );
 430         }
 431
 432         protected function doGetSiblingQueuesWithJobs( array $types ) {
 433                 $result = array();
 434
 435                 $failed = 0;
 436                 /** @var JobQueue $queue */
 437                 foreach ( $this->partitionQueues as $queue ) {
 438                         try {
 439                                 $nonEmpty = $queue->doGetSiblingQueuesWithJobs( $types );
 440                                 if ( is_array( $nonEmpty ) ) {
 441                                         $result = array_unique( array_merge( $result, $nonEmpty ) );
 442                                 } else {
 443                                         return null; // not supported on all partitions; bail
 444                                 }
 445                                 if ( count( $result ) == count( $types ) ) {
 446                                         break; // short-circuit
 447                                 }
 448                         } catch ( JobQueueError $e ) {
 449                                 ++$failed;
 450                                 $this->logException( $e );
 451                         }
 452                 }
 453                 $this->throwErrorIfAllPartitionsDown( $failed );
 454
 455                 return array_values( $result );
 456         }
 457
 458         protected function doGetSiblingQueueSizes( array $types ) {
 459                 $result = array();
 460                 $failed = 0;
 461                 /** @var JobQueue $queue */
 462                 foreach ( $this->partitionQueues as $queue ) {
 463                         try {
 464                                 $sizes = $queue->doGetSiblingQueueSizes( $types );
 465                                 if ( is_array( $sizes ) ) {
 466                                         foreach ( $sizes as $type => $size ) {
 467                                                 $result[$type] = isset( $result[$type] ) ? $result[$type] + $size : $size;
 468                                         }
 469                                 } else {
 470                                         return null; // not supported on all partitions; bail
 471                                 }
 472                         } catch ( JobQueueError $e ) {
 473                                 ++$failed;
 474                                 $this->logException( $e );
 475                         }
 476                 }
 477                 $this->throwErrorIfAllPartitionsDown( $failed );
 478
 479                 return $result;
 480         }
 481
 482         protected function logException( Exception $e ) {
 483                 wfDebugLog( 'JobQueueFederated', $e->getMessage() . "\n" . $e->getTraceAsString() );
 484         }
 485
 486         /**
 487          * Throw an error if no partitions available
 488          *
 489          * @param int $down The number of up partitions down
 490          * @return void
 491          * @throws JobQueueError
 492          */
 493         protected function throwErrorIfAllPartitionsDown( $down ) {
 494                 if ( $down >= count( $this->partitionQueues ) ) {
 495                         throw new JobQueueError( 'No queue partitions available.' );
 496                 }
 497         }
 498
 499         public function setTestingPrefix( $key ) {
 500                 /** @var JobQueue $queue */
 501                 foreach ( $this->partitionQueues as $queue ) {
 502                         $queue->setTestingPrefix( $key );
 503                 }
 504         }
 505 }