includes/libs/lockmanager/QuorumLockManager.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  */
  20
  21 /**
  22  * Base class for lock managers that use a quorum of peer servers for locks.
  23  *
  24  * The resource space can also be sharded into separate peer groups.
  25  *
  26  * See MemcLockManager and RedisLockManager.
  27  *
  28  * @stable to extend
  29  * @ingroup LockManager
  30  * @since 1.20
  31  */
  32 abstract class QuorumLockManager extends LockManager {
  33         /** @var array Map of bucket indexes to peer server lists */
  34         protected $srvsByBucket = []; // (bucket index => (lsrv1, lsrv2, ...))
  35
  36         /** @var array Map of degraded buckets */
  37         protected $degradedBuckets = []; // (bucket index => UNIX timestamp)
  38
  39         final protected function doLockByType( array $pathsByType ) {
  40                 $status = StatusValue::newGood();
  41
  42                 $pathsByTypeByBucket = []; // (bucket => type => paths)
  43                 // Get locks that need to be acquired (buckets => locks)...
  44                 foreach ( $pathsByType as $type => $paths ) {
  45                         foreach ( $paths as $path ) {
  46                                 if ( isset( $this->locksHeld[$path][$type] ) ) {
  47                                         ++$this->locksHeld[$path][$type];
  48                                 } else {
  49                                         $bucket = $this->getBucketFromPath( $path );
  50                                         $pathsByTypeByBucket[$bucket][$type][] = $path;
  51                                 }
  52                         }
  53                 }
  54
  55                 // Acquire locks in each bucket in bucket order to reduce contention. Any blocking
  56                 // mutexes during the acquisition step will not involve circular waiting on buckets.
  57                 ksort( $pathsByTypeByBucket );
  58
  59                 $lockedPaths = []; // files locked in this attempt (type => paths)
  60                 // Attempt to acquire these locks...
  61                 foreach ( $pathsByTypeByBucket as $bucket => $bucketPathsByType ) {
  62                         // Try to acquire the locks for this bucket
  63                         $status->merge( $this->doLockingRequestBucket( $bucket, $bucketPathsByType ) );
  64                         if ( !$status->isOK() ) {
  65                                 $status->merge( $this->doUnlockByType( $lockedPaths ) );
  66
  67                                 return $status;
  68                         }
  69                         // Record these locks as active
  70                         foreach ( $bucketPathsByType as $type => $paths ) {
  71                                 foreach ( $paths as $path ) {
  72                                         $this->locksHeld[$path][$type] = 1; // locked
  73                                         // Keep track of what locks were made in this attempt
  74                                         $lockedPaths[$type][] = $path;
  75                                 }
  76                         }
  77                 }
  78
  79                 return $status;
  80         }
  81
  82         /**
  83          * @stable to override
  84          *
  85          * @param array $pathsByType
  86          *
  87          * @return StatusValue
  88          */
  89         protected function doUnlockByType( array $pathsByType ) {
  90                 $status = StatusValue::newGood();
  91
  92                 $pathsByTypeByBucket = []; // (bucket => type => paths)
  93                 foreach ( $pathsByType as $type => $paths ) {
  94                         foreach ( $paths as $path ) {
  95                                 if ( !isset( $this->locksHeld[$path][$type] ) ) {
  96                                         $status->warning( 'lockmanager-notlocked', $path );
  97                                 } else {
  98                                         --$this->locksHeld[$path][$type];
  99                                         // Reference count the locks held and release locks when zero
 100                                         if ( $this->locksHeld[$path][$type] <= 0 ) {
 101                                                 unset( $this->locksHeld[$path][$type] );
 102                                                 $bucket = $this->getBucketFromPath( $path );
 103                                                 $pathsByTypeByBucket[$bucket][$type][] = $path;
 104                                         }
 105                                         if ( $this->locksHeld[$path] === [] ) {
 106                                                 unset( $this->locksHeld[$path] ); // no SH or EX locks left for key
 107                                         }
 108                                 }
 109                         }
 110                 }
 111
 112                 // Remove these specific locks if possible, or at least release
 113                 // all locks once this process is currently not holding any locks.
 114                 foreach ( $pathsByTypeByBucket as $bucket => $bucketPathsByType ) {
 115                         $status->merge( $this->doUnlockingRequestBucket( $bucket, $bucketPathsByType ) );
 116                 }
 117                 if ( $this->locksHeld === [] ) {
 118                         $status->merge( $this->releaseAllLocks() );
 119                         $this->degradedBuckets = []; // safe to retry the normal quorum
 120                 }
 121
 122                 return $status;
 123         }
 124
 125         /**
 126          * Attempt to acquire locks with the peers for a bucket.
 127          * This is all or nothing; if any key is locked then this totally fails.
 128          *
 129          * @param int $bucket
 130          * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
 131          * @return StatusValue
 132          */
 133         final protected function doLockingRequestBucket( $bucket, array $pathsByType ) {
 134                 return $this->collectPledgeQuorum(
 135                         $bucket,
 136                         function ( $lockSrv ) use ( $pathsByType ) {
 137                                 return $this->getLocksOnServer( $lockSrv, $pathsByType );
 138                         }
 139                 );
 140         }
 141
 142         /**
 143          * Attempt to release locks with the peers for a bucket
 144          *
 145          * @param int $bucket
 146          * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
 147          * @return StatusValue
 148          */
 149         final protected function doUnlockingRequestBucket( $bucket, array $pathsByType ) {
 150                 return $this->releasePledges(
 151                         $bucket,
 152                         function ( $lockSrv ) use ( $pathsByType ) {
 153                                 return $this->freeLocksOnServer( $lockSrv, $pathsByType );
 154                         }
 155                 );
 156         }
 157
 158         /**
 159          * Attempt to acquire pledges with the peers for a bucket.
 160          * This is all or nothing; if any key is already pledged then this totally fails.
 161          *
 162          * @param int $bucket
 163          * @param callable $callback Pledge method taking a server name and yielding a StatusValue
 164          * @return StatusValue
 165          */
 166         final protected function collectPledgeQuorum( $bucket, callable $callback ) {
 167                 $status = StatusValue::newGood();
 168
 169                 $yesVotes = 0; // locks made on trustable servers
 170                 $votesLeft = count( $this->srvsByBucket[$bucket] ); // remaining peers
 171                 $quorum = floor( $votesLeft / 2 + 1 ); // simple majority
 172                 // Get votes for each peer, in order, until we have enough...
 173                 foreach ( $this->srvsByBucket[$bucket] as $lockSrv ) {
 174                         if ( !$this->isServerUp( $lockSrv ) ) {
 175                                 --$votesLeft;
 176                                 $status->warning( 'lockmanager-fail-svr-acquire', $lockSrv );
 177                                 $this->degradedBuckets[$bucket] = time();
 178                                 continue; // server down?
 179                         }
 180                         // Attempt to acquire the lock on this peer
 181                         $status->merge( $callback( $lockSrv ) );
 182                         if ( !$status->isOK() ) {
 183                                 return $status; // vetoed; resource locked
 184                         }
 185                         ++$yesVotes; // success for this peer
 186                         if ( $yesVotes >= $quorum ) {
 187                                 return $status; // lock obtained
 188                         }
 189                         --$votesLeft;
 190                         $votesNeeded = $quorum - $yesVotes;
 191                         if ( $votesNeeded > $votesLeft ) {
 192                                 break; // short-circuit
 193                         }
 194                 }
 195                 // At this point, we must not have met the quorum
 196                 $status->setResult( false );
 197
 198                 return $status;
 199         }
 200
 201         /**
 202          * Attempt to release pledges with the peers for a bucket
 203          *
 204          * @param int $bucket
 205          * @param callable $callback Pledge method taking a server name and yielding a StatusValue
 206          * @return StatusValue
 207          */
 208         final protected function releasePledges( $bucket, callable $callback ) {
 209                 $status = StatusValue::newGood();
 210
 211                 $yesVotes = 0; // locks freed on trustable servers
 212                 $votesLeft = count( $this->srvsByBucket[$bucket] ); // remaining peers
 213                 $quorum = floor( $votesLeft / 2 + 1 ); // simple majority
 214                 $isDegraded = isset( $this->degradedBuckets[$bucket] ); // not the normal quorum?
 215                 foreach ( $this->srvsByBucket[$bucket] as $lockSrv ) {
 216                         if ( !$this->isServerUp( $lockSrv ) ) {
 217                                 $status->warning( 'lockmanager-fail-svr-release', $lockSrv );
 218                         } else {
 219                                 // Attempt to release the lock on this peer
 220                                 $status->merge( $callback( $lockSrv ) );
 221                                 ++$yesVotes; // success for this peer
 222                                 // Normally the first peers form the quorum, and the others are ignored.
 223                                 // Ignore them in this case, but not when an alternative quorum was used.
 224                                 if ( $yesVotes >= $quorum && !$isDegraded ) {
 225                                         break; // lock released
 226                                 }
 227                         }
 228                 }
 229                 // Set a bad StatusValue if the quorum was not met.
 230                 // Assumes the same "up" servers as during the acquire step.
 231                 $status->setResult( $yesVotes >= $quorum );
 232
 233                 return $status;
 234         }
 235
 236         /**
 237          * Get the bucket for resource path.
 238          * This should avoid throwing any exceptions.
 239          *
 240          * @param string $path
 241          * @return int
 242          */
 243         protected function getBucketFromPath( $path ) {
 244                 $prefix = substr( sha1( $path ), 0, 2 ); // first 2 hex chars (8 bits)
 245                 return (int)base_convert( $prefix, 16, 10 ) % count( $this->srvsByBucket );
 246         }
 247
 248         /**
 249          * Check if a lock server is up.
 250          * This should process cache results to reduce RTT.
 251          *
 252          * @param string $lockSrv
 253          * @return bool
 254          */
 255         abstract protected function isServerUp( $lockSrv );
 256
 257         /**
 258          * Get a connection to a lock server and acquire locks
 259          *
 260          * @param string $lockSrv
 261          * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
 262          * @return StatusValue
 263          */
 264         abstract protected function getLocksOnServer( $lockSrv, array $pathsByType );
 265
 266         /**
 267          * Get a connection to a lock server and release locks on $paths.
 268          *
 269          * Subclasses must effectively implement this or releaseAllLocks().
 270          *
 271          * @param string $lockSrv
 272          * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
 273          * @return StatusValue
 274          */
 275         abstract protected function freeLocksOnServer( $lockSrv, array $pathsByType );
 276
 277         /**
 278          * Release all locks that this session is holding.
 279          *
 280          * Subclasses must effectively implement this or freeLocksOnServer().
 281          *
 282          * @return StatusValue
 283          */
 284         abstract protected function releaseAllLocks();
 285
 286         final protected function doLock( array $paths, $type ) {
 287                 // @phan-suppress-previous-line PhanPluginNeverReturnMethod
 288                 throw new LogicException( __METHOD__ . ': proxy class does not need this method.' );
 289         }
 290
 291         final protected function doUnlock( array $paths, $type ) {
 292                 // @phan-suppress-previous-line PhanPluginNeverReturnMethod
 293                 throw new LogicException( __METHOD__ . ': proxy class does not need this method.' );
 294         }
 295 }