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 $pathsToLock = []; // (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 $pathsToLock[$bucket][$type][] = $path;
54 $lockedPaths = []; // files locked in this attempt (type => paths)
55 // Attempt to acquire these locks...
56 foreach ( $pathsToLock as $bucket => $pathsToLockByType ) {
57 // Try to acquire the locks for this bucket
58 $status->merge( $this->doLockingRequestBucket( $bucket, $pathsToLockByType ) );
59 if ( !$status->isOK() ) {
60 $status->merge( $this->doUnlockByType( $lockedPaths ) );
64 // Record these locks as active
65 foreach ( $pathsToLockByType as $type => $paths ) {
66 foreach ( $paths as $path ) {
67 $this->locksHeld
[$path][$type] = 1; // locked
68 // Keep track of what locks were made in this attempt
69 $lockedPaths[$type][] = $path;
77 protected function doUnlockByType( array $pathsByType ) {
78 $status = StatusValue
::newGood();
80 $pathsToUnlock = []; // (bucket => type => paths)
81 foreach ( $pathsByType as $type => $paths ) {
82 foreach ( $paths as $path ) {
83 if ( !isset( $this->locksHeld
[$path][$type] ) ) {
84 $status->warning( 'lockmanager-notlocked', $path );
86 --$this->locksHeld
[$path][$type];
87 // Reference count the locks held and release locks when zero
88 if ( $this->locksHeld
[$path][$type] <= 0 ) {
89 unset( $this->locksHeld
[$path][$type] );
90 $bucket = $this->getBucketFromPath( $path );
91 $pathsToUnlock[$bucket][$type][] = $path;
93 if ( $this->locksHeld
[$path] === [] ) {
94 unset( $this->locksHeld
[$path] ); // no SH or EX locks left for key
100 // Remove these specific locks if possible, or at least release
101 // all locks once this process is currently not holding any locks.
102 foreach ( $pathsToUnlock as $bucket => $pathsToUnlockByType ) {
103 $status->merge( $this->doUnlockingRequestBucket( $bucket, $pathsToUnlockByType ) );
105 if ( $this->locksHeld
=== [] ) {
106 $status->merge( $this->releaseAllLocks() );
107 $this->degradedBuckets
= []; // safe to retry the normal quorum
114 * Attempt to acquire locks with the peers for a bucket.
115 * This is all or nothing; if any key is locked then this totally fails.
118 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
119 * @return StatusValue
121 final protected function doLockingRequestBucket( $bucket, array $pathsByType ) {
122 return $this->collectPledgeQuorum(
124 function ( $lockSrv ) use ( $pathsByType ) {
125 return $this->getLocksOnServer( $lockSrv, $pathsByType );
131 * Attempt to release locks with the peers for a bucket
134 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
135 * @return StatusValue
137 final protected function doUnlockingRequestBucket( $bucket, array $pathsByType ) {
138 return $this->releasePledges(
140 function ( $lockSrv ) use ( $pathsByType ) {
141 return $this->freeLocksOnServer( $lockSrv, $pathsByType );
147 * Attempt to acquire pledges with the peers for a bucket.
148 * This is all or nothing; if any key is already pledged then this totally fails.
151 * @param callable $callback Pledge method taking a server name and yeilding a StatusValue
152 * @return StatusValue
154 final protected function collectPledgeQuorum( $bucket, callable
$callback ) {
155 $status = StatusValue
::newGood();
157 $yesVotes = 0; // locks made on trustable servers
158 $votesLeft = count( $this->srvsByBucket
[$bucket] ); // remaining peers
159 $quorum = floor( $votesLeft / 2 +
1 ); // simple majority
160 // Get votes for each peer, in order, until we have enough...
161 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
162 if ( !$this->isServerUp( $lockSrv ) ) {
164 $status->warning( 'lockmanager-fail-svr-acquire', $lockSrv );
165 $this->degradedBuckets
[$bucket] = time();
166 continue; // server down?
168 // Attempt to acquire the lock on this peer
169 $status->merge( $callback( $lockSrv ) );
170 if ( !$status->isOK() ) {
171 return $status; // vetoed; resource locked
173 ++
$yesVotes; // success for this peer
174 if ( $yesVotes >= $quorum ) {
175 return $status; // lock obtained
178 $votesNeeded = $quorum - $yesVotes;
179 if ( $votesNeeded > $votesLeft ) {
180 break; // short-circuit
183 // At this point, we must not have met the quorum
184 $status->setResult( false );
190 * Attempt to release pledges with the peers for a bucket
193 * @param callable $callback Pledge method taking a server name and yeilding a StatusValue
194 * @return StatusValue
196 final protected function releasePledges( $bucket, callable
$callback ) {
197 $status = StatusValue
::newGood();
199 $yesVotes = 0; // locks freed on trustable servers
200 $votesLeft = count( $this->srvsByBucket
[$bucket] ); // remaining peers
201 $quorum = floor( $votesLeft / 2 +
1 ); // simple majority
202 $isDegraded = isset( $this->degradedBuckets
[$bucket] ); // not the normal quorum?
203 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
204 if ( !$this->isServerUp( $lockSrv ) ) {
205 $status->warning( 'lockmanager-fail-svr-release', $lockSrv );
207 // Attempt to release the lock on this peer
208 $status->merge( $callback( $lockSrv ) );
209 ++
$yesVotes; // success for this peer
210 // Normally the first peers form the quorum, and the others are ignored.
211 // Ignore them in this case, but not when an alternative quorum was used.
212 if ( $yesVotes >= $quorum && !$isDegraded ) {
213 break; // lock released
217 // Set a bad StatusValue if the quorum was not met.
218 // Assumes the same "up" servers as during the acquire step.
219 $status->setResult( $yesVotes >= $quorum );
225 * Get the bucket for resource path.
226 * This should avoid throwing any exceptions.
228 * @param string $path
231 protected function getBucketFromPath( $path ) {
232 $prefix = substr( sha1( $path ), 0, 2 ); // first 2 hex chars (8 bits)
233 return (int)base_convert( $prefix, 16, 10 ) %
count( $this->srvsByBucket
);
237 * Check if a lock server is up.
238 * This should process cache results to reduce RTT.
240 * @param string $lockSrv
243 abstract protected function isServerUp( $lockSrv );
246 * Get a connection to a lock server and acquire locks
248 * @param string $lockSrv
249 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
250 * @return StatusValue
252 abstract protected function getLocksOnServer( $lockSrv, array $pathsByType );
255 * Get a connection to a lock server and release locks on $paths.
257 * Subclasses must effectively implement this or releaseAllLocks().
259 * @param string $lockSrv
260 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
261 * @return StatusValue
263 abstract protected function freeLocksOnServer( $lockSrv, array $pathsByType );
266 * Release all locks that this session is holding.
268 * Subclasses must effectively implement this or freeLocksOnServer().
270 * @return StatusValue
272 abstract protected function releaseAllLocks();
274 final protected function doLock( array $paths, $type ) {
275 throw new LogicException( __METHOD__
. ': proxy class does not need this method.' );
278 final protected function doUnlock( array $paths, $type ) {
279 throw new LogicException( __METHOD__
. ': proxy class does not need this method.' );