MediaWiki  master
QuorumLockManager.php
Go to the documentation of this file.
1 <?php
32 abstract class QuorumLockManager extends LockManager {
34  protected $srvsByBucket = []; // (bucket index => (lsrv1, lsrv2, ...))
35 
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 
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 
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 
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 
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 
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 
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 
255  abstract protected function isServerUp( $lockSrv );
256 
264  abstract protected function getLocksOnServer( $lockSrv, array $pathsByType );
265 
275  abstract protected function freeLocksOnServer( $lockSrv, array $pathsByType );
276 
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 }
LockManager
Class for handling resource locking.
Definition: LockManager.php:48
QuorumLockManager\doUnlockByType
doUnlockByType(array $pathsByType)
Stable to override.
Definition: QuorumLockManager.php:89
QuorumLockManager\getBucketFromPath
getBucketFromPath( $path)
Get the bucket for resource path.
Definition: QuorumLockManager.php:243
QuorumLockManager\$degradedBuckets
array $degradedBuckets
Map of degraded buckets.
Definition: QuorumLockManager.php:37
QuorumLockManager\doLockingRequestBucket
doLockingRequestBucket( $bucket, array $pathsByType)
Attempt to acquire locks with the peers for a bucket.
Definition: QuorumLockManager.php:133
QuorumLockManager
Version of LockManager that uses a quorum from peer servers for locks.
Definition: QuorumLockManager.php:32
QuorumLockManager\releaseAllLocks
releaseAllLocks()
Release all locks that this session is holding.
QuorumLockManager\isServerUp
isServerUp( $lockSrv)
Check if a lock server is up.
QuorumLockManager\doLockByType
doLockByType(array $pathsByType)
Definition: QuorumLockManager.php:39
QuorumLockManager\collectPledgeQuorum
collectPledgeQuorum( $bucket, callable $callback)
Attempt to acquire pledges with the peers for a bucket.
Definition: QuorumLockManager.php:166
QuorumLockManager\doUnlockingRequestBucket
doUnlockingRequestBucket( $bucket, array $pathsByType)
Attempt to release locks with the peers for a bucket.
Definition: QuorumLockManager.php:149
QuorumLockManager\doUnlock
doUnlock(array $paths, $type)
Unlock resources with the given keys and lock type.
Definition: QuorumLockManager.php:290
QuorumLockManager\releasePledges
releasePledges( $bucket, callable $callback)
Attempt to release pledges with the peers for a bucket.
Definition: QuorumLockManager.php:208
StatusValue\newGood
static newGood( $value=null)
Factory function for good results.
Definition: StatusValue.php:82
QuorumLockManager\$srvsByBucket
array $srvsByBucket
Map of bucket indexes to peer server lists.
Definition: QuorumLockManager.php:34
$path
$path
Definition: NoLocalSettings.php:25
QuorumLockManager\freeLocksOnServer
freeLocksOnServer( $lockSrv, array $pathsByType)
Get a connection to a lock server and release locks on $paths.
QuorumLockManager\doLock
doLock(array $paths, $type)
Lock resources with the given keys and lock type.
Definition: QuorumLockManager.php:286
QuorumLockManager\getLocksOnServer
getLocksOnServer( $lockSrv, array $pathsByType)
Get a connection to a lock server and acquire locks.
$type
$type
Definition: testCompression.php:52