[Summary view] [Print] [Text view]

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