includes/ConcurrencyCheck.php

   1 <?php
   2
   3 /**
   4  * Class for cooperative locking of web resources
   5  *
   6  * Each resource is identified by a combination of the "resource type" (the application, the type
   7  * of content, etc), and the resource's primary key or some other unique numeric ID.
   8  *
   9  * Currently, a resource can only be checked out by a single user.  Other attempts to check it out result
  10  * in the checkout failing.  In the future, an option for multiple simulataneous checkouts could be added
  11  * without much trouble.
  12  *
  13  * This could be done with named locks, except then it would be impossible to build a list of all the
  14  * resources currently checked out for a given application.  There's no good way to construct a query
  15  * that answers the question, "What locks do you have starting with [foo]"  This could be done really well
  16  * with a concurrent, reliable, distributed key/value store, but we don't have one of those right now.
  17  *
  18  * @author Ian Baker <ian@wikimedia.org>
  19  */
  20 class ConcurrencyCheck {
  21
  22         protected $expirationTime;
  23
  24         /**
  25          * @var User
  26          */
  27         protected $user;
  28
  29         /**
  30          * Constructor
  31          *
  32          * @var $resourceType String The calling application or type of resource, conceptually like a namespace
  33          * @var $user User object, the current user
  34          * @var $expirationTime Integer (optional) How long should a checkout last, in seconds
  35          */
  36         public function __construct( $resourceType, $user, $expirationTime = null ) {
  37
  38                 // All database calls are to the master, since the whole point of this class is maintaining
  39                 // concurrency. Most reads should come from cache anyway.
  40                 $this->dbw = wfGetDb( DB_MASTER );
  41
  42                 $this->user = $user;
  43                 // TODO: create a registry of all valid resourceTypes that client app can add to.
  44                 $this->resourceType = $resourceType;
  45                 $this->setExpirationTime( $expirationTime );
  46         }
  47
  48         /**
  49          * Check out a resource.  This establishes an atomically generated, cooperative lock
  50          * on a key.  The lock is tied to the current user.
  51          *
  52          * @var $record Integer containing the record id to check out
  53          * @var $override Boolean (optional) describing whether to override an existing checkout
  54          * @return boolean
  55          */
  56         public function checkout( $record, $override = null ) {
  57                 global $wgMemc;
  58                 $this->validateId( $record );
  59                 $dbw = $this->dbw;
  60                 $userId = $this->user->getId();
  61                 $cacheKey = wfMemcKey( 'concurrencycheck', $this->resourceType, $record );
  62
  63                 // when operating with a single memcached cluster, it's reasonable to check the cache here.
  64                 global $wgConcurrency;
  65                 if( $wgConcurrency['TrustMemc'] ) {
  66                 $cached = $wgMemc->get( $cacheKey );
  67                         if( $cached ) {
  68                                 if( ! $override && $cached['userId'] != $userId && $cached['expiration'] > time() ) {
  69                                         // this is already checked out.
  70                                         return false;
  71                                 }
  72                         }
  73                 }
  74
  75                 // attempt an insert, check success (this is atomic)
  76                 $insertError = null;
  77                 $res = $dbw->insert(
  78                         'concurrencycheck',
  79                         array(
  80                                 'cc_resource_type' => $this->resourceType,
  81                                 'cc_record' => $record,
  82                                 'cc_user' => $userId,
  83                                 'cc_expiration' => wfTimestamp( TS_MW, time() + $this->expirationTime ),
  84                         ),
  85                         __METHOD__,
  86                         array( 'IGNORE' )
  87                 );
  88
  89                 // if the insert succeeded, checkout is done.
  90                 if( $dbw->affectedRows() === 1 ) {
  91                         // delete any existing cache key.  can't create a new key here
  92                         // since the insert didn't happen inside a transaction.
  93                         $wgMemc->delete( $cacheKey );
  94                         return true;
  95                 }
  96
  97                 // if the insert failed, it's necessary to check the expiration.
  98                 // here, check by deleting, since that permits the use of write locks
  99                 // (SELECT..LOCK IN SHARE MODE), rather than read locks (SELECT..FOR UPDATE)
 100                 $dbw->begin();
 101                 $dbw->delete(
 102                         'concurrencycheck',
 103                         array(
 104                                 'cc_resource_type' => $this->resourceType,
 105                                 'cc_record' => $record,
 106                                 '(cc_user = ' . $userId . ' OR cc_expiration <= ' . $dbw->addQuotes(wfTimestamp( TS_MW )) . ')',  // only the owner can perform a checkin
 107                         ),
 108                         __METHOD__,
 109                         array()
 110                 );
 111
 112                 // delete failed: not checked out by current user, checkout is unexpired, override is unset
 113                 if( $dbw->affectedRows() !== 1 && ! $override) {
 114                         // fetch the existing data to cache it
 115                         $row = $dbw->selectRow(
 116                                 'concurrencycheck',
 117                                 array( '*' ),
 118                                 array(
 119                                         'cc_resource_type' => $this->resourceType,
 120                                         'cc_record' => $record,
 121                                 ),
 122                                 __METHOD__,
 123                                 array()
 124                         );
 125
 126                         // this was a cache miss.  populate the cache with data from the db.
 127                         // cache is set to expire at the same time as the checkout, since it'll become invalid then anyway.
 128                         // inside this transaction, a row-level lock is established which ensures cache concurrency
 129                         $wgMemc->set( $cacheKey, array( 'userId' => $row->cc_user, 'expiration' => wfTimestamp( TS_UNIX, $row->cc_expiration ) ), wfTimestamp( TS_UNIX, $row->cc_expiration ) - time() );
 130                         $dbw->rollback();
 131                         return false;
 132                 }
 133
 134                 $expiration = time() + $this->expirationTime;
 135
 136                 // delete succeeded, insert a new row.
 137                 // replace is used here to support the override parameter
 138                 $res = $dbw->replace(
 139                         'concurrencycheck',
 140                         array( 'cc_resource_type', 'cc_record' ),
 141                         array(
 142                                 'cc_resource_type' => $this->resourceType,
 143                                 'cc_record' => $record,
 144                                 'cc_user' => $userId,
 145                                 'cc_expiration' => wfTimestamp( TS_MW, $expiration ),
 146                         ),
 147                         __METHOD__
 148                 );
 149
 150                 // cache the result.
 151                 $wgMemc->set( $cacheKey, array( 'userId' => $userId, 'expiration' => $expiration ), $this->expirationTime );
 152
 153                 $dbw->commit();
 154                 return true;
 155         }
 156
 157         /**
 158          * Check in a resource. Only works if the resource is checked out by the current user.
 159          *
 160          * @var $record Integer containing the record id to checkin
 161          * @return Boolean
 162          */
 163         public function checkin( $record ) {
 164                 global $wgMemc;
 165                 $this->validateId( $record );
 166                 $dbw = $this->dbw;
 167                 $userId = $this->user->getId();
 168                 $cacheKey = wfMemcKey( 'concurrencycheck', $this->resourceType, $record );
 169
 170                 $dbw->delete(
 171                         'concurrencycheck',
 172                         array(
 173                                 'cc_resource_type' => $this->resourceType,
 174                                 'cc_record' => $record,
 175                                 'cc_user' => $userId,  // only the owner can perform a checkin
 176                         ),
 177                         __METHOD__,
 178                         array()
 179                 );
 180
 181                 // check row count (this is atomic, select would not be)
 182                 if( $dbw->affectedRows() === 1 ) {
 183                         $wgMemc->delete( $cacheKey );
 184                         return true;
 185                 }
 186
 187                 return false;
 188         }
 189
 190         /**
 191          * Remove all expired checkouts.
 192          *
 193          * @return Integer describing the number of records expired.
 194          */
 195         public function expire() {
 196                 // TODO: run this in a few other places that db access happens, to make sure the db stays non-crufty.
 197                 $dbw = $this->dbw;
 198                 $now = time();
 199
 200                 // remove the rows from the db.  trust memcached to expire the cache.
 201                 $dbw->delete(
 202                         'concurrencycheck',
 203                         array(
 204                                 'cc_expiration <= ' . $dbw->addQuotes( wfTimestamp( TS_MW, $now ) ),
 205                         ),
 206                         __METHOD__,
 207                         array()
 208                 );
 209
 210                 // return the number of rows removed.
 211                 return $dbw->affectedRows();
 212         }
 213
 214         public function status( $keys ) {
 215                 global $wgMemc, $wgDBtype;
 216                 $dbw = $this->dbw;
 217                 $now = time();
 218
 219                 $checkouts = array();
 220                 $toSelect = array();
 221
 222                 // validate keys, attempt to retrieve from cache.
 223                 foreach( $keys as $key ) {
 224                         $this->validateId( $key );
 225
 226                         $cached = $wgMemc->get( wfMemcKey( 'concurrencycheck', $this->resourceType, $key ) );
 227                         if( $cached && $cached['expiration'] > $now ) {
 228                                 $checkouts[$key] = array(
 229                                         'status' => 'valid',
 230                                         'cc_resource_type' => $this->resourceType,
 231                                         'cc_record' => $key,
 232                                         'cc_user' => $cached['userId'],
 233                                         'cc_expiration' => wfTimestamp( TS_MW, $cached['expiration'] ),
 234                                         'cache' => 'cached',
 235                                 );
 236                         } else {
 237                                 $toSelect[] = $key;
 238                         }
 239                 }
 240
 241                 // if there were cache misses...
 242                 if( $toSelect ) {
 243                         // If it's time to go to the database, go ahead and expire old rows.
 244                         $this->expire();
 245
 246
 247                         // Why LOCK IN SHARE MODE, you might ask?  To avoid a race condition: Otherwise, it's possible for
 248                         // a checkin and/or checkout to occur between this select and the value being stored in cache, which
 249                         // makes for an incorrect cache.  This, in turn, could make checkout() above (which uses the cache)
 250                         // function incorrectly.
 251                         //
 252                         // Another option would be to run the select, then check each row in-turn before setting the cache
 253                         // key using either SELECT (with LOCK IN SHARE MODE) or UPDATE that checks a timestamp (and which
 254                         // would establish the same lock). That method would mean smaller, quicker locks, but more overall
 255                         // database overhead.
 256                         //
 257                         // It appears all the DBMSes we use support LOCK IN SHARE MODE, but if that's not the case, the second
 258                         // solution above could be implemented instead.
 259                         $queryParams = array();
 260                         if( $wgDBtype === 'mysql' ) {
 261                                 $queryParamsp[] = 'LOCK IN SHARE MODE';
 262
 263                                 // the transaction seems incongruous, I know, but it's to keep the cache update atomic.
 264                                 $dbw->begin();
 265                         }
 266
 267                         $res = $dbw->select(
 268                                 'concurrencycheck',
 269                                 array( '*' ),
 270                                 array(
 271                                         'cc_resource_type' => $this->resourceType,
 272                                         'cc_record' => $toSelect,
 273                                         'cc_expiration > ' . $dbw->addQuotes( wfTimestamp( TS_MW ) ),
 274                                 ),
 275                                 __METHOD__,
 276                                 $queryParams
 277                         );
 278
 279                         while( $res && $record = $res->fetchRow() ) {
 280                                 $record['status'] = 'valid';
 281                                 $checkouts[ $record['cc_record'] ] = $record;
 282
 283                                 // TODO: implement strategy #2 above, determine which DBMSes need which method.
 284                                 // for now, disable adding to cache here for databases that don't support read locking
 285                                 if( $wgDBtype !== 'mysql' ) {
 286                                         // safe to store values since this is inside the transaction
 287                                         $wgMemc->set(
 288                                                 wfMemcKey( 'concurrencycheck', $this->resourceType, $record['cc_record'] ),
 289                                                 array( 'userId' => $record['cc_user'], 'expiration' => wfTimestamp( TS_UNIX, $record['cc_expiration'] ) ),
 290                                                 wfTimestamp( TS_UNIX, $record['cc_expiration'] ) - time()
 291                                         );
 292                                 }
 293                         }
 294
 295                         if( $wgDBtype === 'mysql' ) {
 296                                 // end the transaction.
 297                                 $dbw->rollback();
 298                         }
 299                 }
 300
 301                 // if a key was passed in but has no (unexpired) checkout, include it in the
 302                 // result set to make things easier and more consistent on the client-side.
 303                 foreach( $keys as $key ) {
 304                         if( ! array_key_exists( $key, $checkouts ) ) {
 305                                 $checkouts[$key]['status'] = 'invalid';
 306                         }
 307                 }
 308
 309                 return $checkouts;
 310         }
 311
 312         public function listCheckouts() {
 313                 // TODO: fill in the function that lets you get the complete set of checkouts for a given application.
 314         }
 315
 316         /**
 317          * @param $user user
 318          */
 319         public function setUser( $user ) {
 320                 $this->user = $user;
 321         }
 322
 323         public function setExpirationTime( $expirationTime = null ) {
 324                 global $wgConcurrency;
 325
 326                 // check to make sure the time is a number
 327                 // negative number are allowed, though mostly only used for testing
 328                 if( $expirationTime && (int) $expirationTime == $expirationTime ) {
 329                         if( $expirationTime > $wgConcurrency['ExpirationMax'] ) {
 330                                 $this->expirationTime = $wgConcurrency['ExpirationMax']; // if the number is too high, limit it to the max value.
 331                         } elseif ( $expirationTime < $wgConcurrency['ExpirationMin'] ) {
 332                                 $this->expirationTime = $wgConcurrency['ExpirationMin']; // low limit, default -1 min
 333                         } else {
 334                                 $this->expirationTime = $expirationTime; // the amount of time before a checkout expires.
 335                         }
 336                 } else {
 337                         $this->expirationTime = $wgConcurrency['ExpirationDefault']; // global default is 15 mins.
 338                 }
 339         }
 340
 341         /**
 342          * Check to make sure a record ID is numeric, throw an exception if not.
 343          *
 344          * @var $record Integer
 345          * @throws ConcurrencyCheckBadRecordIdException
 346          * @return boolean
 347          */
 348         private static function validateId ( $record ) {
 349                 if( (int) $record !== $record || $record <= 0 ) {
 350                         throw new ConcurrencyCheckBadRecordIdException( 'Record ID ' . $record . ' must be a positive integer' );
 351                 }
 352
 353                 // TODO: add a hook here for client-side validation.
 354                 return true;
 355         }
 356 }
 357
 358 class ConcurrencyCheckBadRecordIdException extends MWException {}