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 = array(); // (bucket index => (lsrv1, lsrv2, ...))
34 /** @var Array Map of degraded buckets */
35 protected $degradedBuckets = array(); // (buckey index => UNIX timestamp)
37 final protected function doLock( array $paths, $type ) {
38 return $this->doLockByType( array( $type => $paths ) );
41 final protected function doUnlock( array $paths, $type ) {
42 return $this->doUnlockByType( array( $type => $paths ) );
45 protected function doLockByType( array $pathsByType ) {
46 $status = Status
::newGood();
48 $pathsToLock = array(); // (bucket => type => paths)
49 // Get locks that need to be acquired (buckets => locks)...
50 foreach ( $pathsByType as $type => $paths ) {
51 foreach ( $paths as $path ) {
52 if ( isset( $this->locksHeld
[$path][$type] ) ) {
53 ++
$this->locksHeld
[$path][$type];
55 $bucket = $this->getBucketFromPath( $path );
56 $pathsToLock[$bucket][$type][] = $path;
61 $lockedPaths = array(); // files locked in this attempt (type => paths)
62 // Attempt to acquire these locks...
63 foreach ( $pathsToLock as $bucket => $pathsToLockByType ) {
64 // Try to acquire the locks for this bucket
65 $status->merge( $this->doLockingRequestBucket( $bucket, $pathsToLockByType ) );
66 if ( !$status->isOK() ) {
67 $status->merge( $this->doUnlockByType( $lockedPaths ) );
70 // Record these locks as active
71 foreach ( $pathsToLockByType as $type => $paths ) {
72 foreach ( $paths as $path ) {
73 $this->locksHeld
[$path][$type] = 1; // locked
74 // Keep track of what locks were made in this attempt
75 $lockedPaths[$type][] = $path;
83 protected function doUnlockByType( array $pathsByType ) {
84 $status = Status
::newGood();
86 $pathsToUnlock = array(); // (bucket => type => paths)
87 foreach ( $pathsByType as $type => $paths ) {
88 foreach ( $paths as $path ) {
89 if ( !isset( $this->locksHeld
[$path][$type] ) ) {
90 $status->warning( 'lockmanager-notlocked', $path );
92 --$this->locksHeld
[$path][$type];
93 // Reference count the locks held and release locks when zero
94 if ( $this->locksHeld
[$path][$type] <= 0 ) {
95 unset( $this->locksHeld
[$path][$type] );
96 $bucket = $this->getBucketFromPath( $path );
97 $pathsToUnlock[$bucket][$type][] = $path;
99 if ( !count( $this->locksHeld
[$path] ) ) {
100 unset( $this->locksHeld
[$path] ); // no SH or EX locks left for key
106 // Remove these specific locks if possible, or at least release
107 // all locks once this process is currently not holding any locks.
108 foreach ( $pathsToUnlock as $bucket => $pathsToUnlockByType ) {
109 $status->merge( $this->doUnlockingRequestBucket( $bucket, $pathsToUnlockByType ) );
111 if ( !count( $this->locksHeld
) ) {
112 $status->merge( $this->releaseAllLocks() );
113 $this->degradedBuckets
= array(); // safe to retry the normal quorum
120 * Attempt to acquire locks with the peers for a bucket.
121 * This is all or nothing; if any key is locked then this totally fails.
123 * @param $bucket integer
124 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
127 final protected function doLockingRequestBucket( $bucket, array $pathsByType ) {
128 $status = Status
::newGood();
130 $yesVotes = 0; // locks made on trustable servers
131 $votesLeft = count( $this->srvsByBucket
[$bucket] ); // remaining peers
132 $quorum = floor( $votesLeft / 2 +
1 ); // simple majority
133 // Get votes for each peer, in order, until we have enough...
134 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
135 if ( !$this->isServerUp( $lockSrv ) ) {
137 $status->warning( 'lockmanager-fail-svr-acquire', $lockSrv );
138 $this->degradedBuckets
[$bucket] = time();
139 continue; // server down?
141 // Attempt to acquire the lock on this peer
142 $status->merge( $this->getLocksOnServer( $lockSrv, $pathsByType ) );
143 if ( !$status->isOK() ) {
144 return $status; // vetoed; resource locked
146 ++
$yesVotes; // success for this peer
147 if ( $yesVotes >= $quorum ) {
148 return $status; // lock obtained
151 $votesNeeded = $quorum - $yesVotes;
152 if ( $votesNeeded > $votesLeft ) {
153 break; // short-circuit
156 // At this point, we must not have met the quorum
157 $status->setResult( false );
163 * Attempt to release locks with the peers for a bucket
165 * @param $bucket integer
166 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
169 final protected function doUnlockingRequestBucket( $bucket, array $pathsByType ) {
170 $status = Status
::newGood();
172 $yesVotes = 0; // locks freed on trustable servers
173 $votesLeft = count( $this->srvsByBucket
[$bucket] ); // remaining peers
174 $quorum = floor( $votesLeft / 2 +
1 ); // simple majority
175 $isDegraded = isset( $this->degradedBuckets
[$bucket] ); // not the normal quorum?
176 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
177 if ( !$this->isServerUp( $lockSrv ) ) {
178 $status->warning( 'lockmanager-fail-svr-release', $lockSrv );
179 // Attempt to release the lock on this peer
181 $status->merge( $this->freeLocksOnServer( $lockSrv, $pathsByType ) );
182 ++
$yesVotes; // success for this peer
183 // Normally the first peers form the quorum, and the others are ignored.
184 // Ignore them in this case, but not when an alternative quorum was used.
185 if ( $yesVotes >= $quorum && !$isDegraded ) {
186 break; // lock released
190 // Set a bad status if the quorum was not met.
191 // Assumes the same "up" servers as during the acquire step.
192 $status->setResult( $yesVotes >= $quorum );
198 * Get the bucket for resource path.
199 * This should avoid throwing any exceptions.
201 * @param $path string
204 protected function getBucketFromPath( $path ) {
205 $prefix = substr( sha1( $path ), 0, 2 ); // first 2 hex chars (8 bits)
206 return (int)base_convert( $prefix, 16, 10 ) %
count( $this->srvsByBucket
);
210 * Check if a lock server is up.
211 * This should process cache results to reduce RTT.
213 * @param $lockSrv string
216 abstract protected function isServerUp( $lockSrv );
219 * Get a connection to a lock server and acquire locks
221 * @param $lockSrv string
222 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
225 abstract protected function getLocksOnServer( $lockSrv, array $pathsByType );
228 * Get a connection to a lock server and release locks on $paths.
230 * Subclasses must effectively implement this or releaseAllLocks().
232 * @param $lockSrv string
233 * @param array $pathsByType Map of LockManager::LOCK_* constants to lists of paths
236 abstract protected function freeLocksOnServer( $lockSrv, array $pathsByType );
239 * Release all locks that this session is holding.
241 * Subclasses must effectively implement this or freeLocksOnServer().
245 abstract protected function releaseAllLocks();