3 * Version of LockManager that uses a quorum from peer servers for locks.
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.
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.
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
21 * @ingroup LockManager
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.
28 * @ingroup LockManager
31 abstract class QuorumLockManager
extends LockManager
{
32 /** @var array Map of bucket indexes to peer server lists */
33 protected $srvsByBucket = []; // (bucket index => (lsrv1, lsrv2, ...))
35 /** @var array Map of degraded buckets */
36 protected $degradedBuckets = []; // (bucket index => UNIX timestamp)
38 final protected function doLockByType( array $pathsByType ) {
39 $status = StatusValue
::newGood();
41 $pathsByTypeByBucket = []; // (bucket => type => paths)
42 // Get locks that need to be acquired (buckets => locks)...
43 foreach ( $pathsByType as $type => $paths ) {
44 foreach ( $paths as $path ) {
45 if ( isset( $this->locksHeld
[$path][$type] ) ) {
46 ++
$this->locksHeld
[$path][$type];
48 $bucket = $this->getBucketFromPath( $path );
49 $pathsByTypeByBucket[$bucket][$type][] = $path;
54 // Acquire locks in each bucket in bucket order to reduce contention. Any blocking
55 // mutexes during the acquisition step will not involve circular waiting on buckets.
56 ksort( $pathsByTypeByBucket );
58 $lockedPaths = []; // files locked in this attempt (type => paths)
59 // Attempt to acquire these locks...
60 foreach ( $pathsByTypeByBucket as $bucket => $bucketPathsByType ) {
61 // Try to acquire the locks for this bucket
62 $status->merge( $this->doLockingRequestBucket( $bucket, $bucketPathsByType ) );
63 if ( !$status->isOK() ) {
64 $status->merge( $this->doUnlockByType( $lockedPaths ) );
68 // Record these locks as active
69 foreach ( $bucketPathsByType as $type => $paths ) {
70 foreach ( $paths as $path ) {
71 $this->locksHeld
[$path][$type] = 1; // locked
72 // Keep track of what locks were made in this attempt
73 $lockedPaths[$type][] = $path;
81 protected function doUnlockByType( array $pathsByType ) {
82 $status = StatusValue
::newGood();
84 $pathsByTypeByBucket = []; // (bucket => type => paths)
85 foreach ( $pathsByType as $type => $paths ) {
86 foreach ( $paths as $path ) {
87 if ( !isset( $this->locksHeld
[$path][$type] ) ) {
88 $status->warning( 'lockmanager-notlocked', $path );
90 --$this->locksHeld
[$path][$type];
91 // Reference count the locks held and release locks when zero
92 if ( $this->locksHeld
[$path][$type] <= 0 ) {
93 unset( $this->locksHeld
[$path][$type] );
94 $bucket = $this->getBucketFromPath( $path );
95 $pathsByTypeByBucket[$bucket][$type][] = $path;
97 if ( $this->locksHeld
[$path] === [] ) {
98 unset( $this->locksHeld
[$path] ); // no SH or EX locks left for key
104 // Remove these specific locks if possible, or at least release
105 // all locks once this process is currently not holding any locks.
106 foreach ( $pathsByTypeByBucket as $bucket => $bucketPathsByType ) {
107 $status->merge( $this->doUnlockingRequestBucket( $bucket, $bucketPathsByType ) );
109 if ( $this->locksHeld
=== [] ) {
110 $status->merge( $this->releaseAllLocks() );
111 $this->degradedBuckets
= []; // safe to retry the normal quorum
118 * Attempt to acquire locks with the peers for a bucket.
119 * This is all or nothing; if any key is locked then this totally fails.
122 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
123 * @return StatusValue
125 final protected function doLockingRequestBucket( $bucket, array $pathsByType ) {
126 return $this->collectPledgeQuorum(
128 function ( $lockSrv ) use ( $pathsByType ) {
129 return $this->getLocksOnServer( $lockSrv, $pathsByType );
135 * Attempt to release locks with the peers for a bucket
138 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
139 * @return StatusValue
141 final protected function doUnlockingRequestBucket( $bucket, array $pathsByType ) {
142 return $this->releasePledges(
144 function ( $lockSrv ) use ( $pathsByType ) {
145 return $this->freeLocksOnServer( $lockSrv, $pathsByType );
151 * Attempt to acquire pledges with the peers for a bucket.
152 * This is all or nothing; if any key is already pledged then this totally fails.
155 * @param callable $callback Pledge method taking a server name and yeilding a StatusValue
156 * @return StatusValue
158 final protected function collectPledgeQuorum( $bucket, callable
$callback ) {
159 $status = StatusValue
::newGood();
161 $yesVotes = 0; // locks made on trustable servers
162 $votesLeft = count( $this->srvsByBucket
[$bucket] ); // remaining peers
163 $quorum = floor( $votesLeft / 2 +
1 ); // simple majority
164 // Get votes for each peer, in order, until we have enough...
165 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
166 if ( !$this->isServerUp( $lockSrv ) ) {
168 $status->warning( 'lockmanager-fail-svr-acquire', $lockSrv );
169 $this->degradedBuckets
[$bucket] = time();
170 continue; // server down?
172 // Attempt to acquire the lock on this peer
173 $status->merge( $callback( $lockSrv ) );
174 if ( !$status->isOK() ) {
175 return $status; // vetoed; resource locked
177 ++
$yesVotes; // success for this peer
178 if ( $yesVotes >= $quorum ) {
179 return $status; // lock obtained
182 $votesNeeded = $quorum - $yesVotes;
183 if ( $votesNeeded > $votesLeft ) {
184 break; // short-circuit
187 // At this point, we must not have met the quorum
188 $status->setResult( false );
194 * Attempt to release pledges with the peers for a bucket
197 * @param callable $callback Pledge method taking a server name and yeilding a StatusValue
198 * @return StatusValue
200 final protected function releasePledges( $bucket, callable
$callback ) {
201 $status = StatusValue
::newGood();
203 $yesVotes = 0; // locks freed on trustable servers
204 $votesLeft = count( $this->srvsByBucket
[$bucket] ); // remaining peers
205 $quorum = floor( $votesLeft / 2 +
1 ); // simple majority
206 $isDegraded = isset( $this->degradedBuckets
[$bucket] ); // not the normal quorum?
207 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
208 if ( !$this->isServerUp( $lockSrv ) ) {
209 $status->warning( 'lockmanager-fail-svr-release', $lockSrv );
211 // Attempt to release the lock on this peer
212 $status->merge( $callback( $lockSrv ) );
213 ++
$yesVotes; // success for this peer
214 // Normally the first peers form the quorum, and the others are ignored.
215 // Ignore them in this case, but not when an alternative quorum was used.
216 if ( $yesVotes >= $quorum && !$isDegraded ) {
217 break; // lock released
221 // Set a bad StatusValue if the quorum was not met.
222 // Assumes the same "up" servers as during the acquire step.
223 $status->setResult( $yesVotes >= $quorum );
229 * Get the bucket for resource path.
230 * This should avoid throwing any exceptions.
232 * @param string $path
235 protected function getBucketFromPath( $path ) {
236 $prefix = substr( sha1( $path ), 0, 2 ); // first 2 hex chars (8 bits)
237 return (int)base_convert( $prefix, 16, 10 ) %
count( $this->srvsByBucket
);
241 * Check if a lock server is up.
242 * This should process cache results to reduce RTT.
244 * @param string $lockSrv
247 abstract protected function isServerUp( $lockSrv );
250 * Get a connection to a lock server and acquire locks
252 * @param string $lockSrv
253 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
254 * @return StatusValue
256 abstract protected function getLocksOnServer( $lockSrv, array $pathsByType );
259 * Get a connection to a lock server and release locks on $paths.
261 * Subclasses must effectively implement this or releaseAllLocks().
263 * @param string $lockSrv
264 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
265 * @return StatusValue
267 abstract protected function freeLocksOnServer( $lockSrv, array $pathsByType );
270 * Release all locks that this session is holding.
272 * Subclasses must effectively implement this or freeLocksOnServer().
274 * @return StatusValue
276 abstract protected function releaseAllLocks();
278 final protected function doLock( array $paths, $type ) {
279 throw new LogicException( __METHOD__
. ': proxy class does not need this method.' );
282 final protected function doUnlock( array $paths, $type ) {
283 throw new LogicException( __METHOD__
. ': proxy class does not need this method.' );