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 * @stable to extend 29 * @ingroup LockManager 30 * @since 1.20 31 */ 32abstract 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 throw new LogicException( __METHOD__ . ': proxy class does not need this method.' ); 288 } 289 290 final protected function doUnlock( array $paths, $type ) { 291 throw new LogicException( __METHOD__ . ': proxy class does not need this method.' ); 292 } 293} 294