includes/cache/bloom/BloomCacheRedis.php

   1 <?php
   2 /**
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation; either version 2 of the License, or
   6  * (at your option) any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License along
  14  * with this program; if not, write to the Free Software Foundation, Inc.,
  15  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16  * http://www.gnu.org/copyleft/gpl.html
  17  *
  18  * @file
  19  * @author Aaron Schulz
  20  */
  21
  22 /**
  23  * Bloom filter implemented using Redis
  24  *
  25  * The Redis server must be >= 2.6 and should have volatile-lru or volatile-ttl
  26  * if there is any eviction policy. It should not be allkeys-* in any case. Also,
  27  * this can be used in a simple master/slave setup or with Redis Sentinel preferably.
  28  *
  29  * Some bits are based on https://github.com/ErikDubbelboer/redis-lua-scaling-bloom-filter
  30  * but are simplified to use a single filter instead of up to 32 filters.
  31  *
  32  * @since 1.24
  33  */
  34 class BloomCacheRedis extends BloomCache {
  35         /** @var RedisConnectionPool */
  36         protected $redisPool;
  37         /** @var RedisLockManager */
  38         protected $lockMgr;
  39         /** @var array */
  40         protected $servers;
  41         /** @var integer Federate each filter into this many redis bitfield objects */
  42         protected $segments = 128;
  43
  44         /**
  45          * @params include:
  46          *   - redisServers : list of servers (address:<port>) (the first is the master)
  47          *   - redisConf    : additional redis configuration
  48          *
  49          * @param array $config
  50          */
  51         public function __construct( array $config ) {
  52                 parent::__construct( $config );
  53
  54                 $redisConf = $config['redisConfig'];
  55                 $redisConf['serializer'] = 'none'; // manage that in this class
  56                 $this->redisPool = RedisConnectionPool::singleton( $redisConf );
  57                 $this->servers = $config['redisServers'];
  58                 $this->lockMgr = new RedisLockManager( array(
  59                         'lockServers'  => array( 'srv1' => $this->servers[0] ),
  60                         'srvsByBucket' => array( 0 => array( 'srv1' ) ),
  61                         'redisConfig'  => $config['redisConfig']
  62                 ) );
  63         }
  64
  65         protected function doInit( $key, $size, $precision ) {
  66                 $conn = $this->getConnection( 'master' );
  67                 if ( !$conn ) {
  68                         return false;
  69                 }
  70
  71                 // 80000000 items at p = .001 take up 500MB and fit into one value.
  72                 // Do not hit the 512MB redis value limit by reducing the demands.
  73                 $size = min( $size, 80000000 * $this->segments );
  74                 $precision = max( round( $precision, 3 ), .001 );
  75                 $epoch = microtime( true );
  76
  77                 static $script =
  78 <<<LUA
  79                 local kMetadata, kData = unpack(KEYS)
  80                 local aEntries, aPrec, aEpoch = unpack(ARGV)
  81                 if redis.call('EXISTS',kMetadata) == 0 or redis.call('EXISTS',kData) == 0 then
  82                         redis.call('DEL',kMetadata)
  83                         redis.call('HSET',kMetadata,'entries',aEntries)
  84                         redis.call('HSET',kMetadata,'precision',aPrec)
  85                         redis.call('HSET',kMetadata,'epoch',aEpoch)
  86                         redis.call('SET',kData,'')
  87                         return 1
  88                 end
  89                 return 0
  90 LUA;
  91
  92                 $res = false;
  93                 try {
  94                         $conn->script( 'load', $script );
  95                         $conn->multi( Redis::MULTI );
  96                         for ( $i = 0; $i < $this->segments; ++$i ) {
  97                                 $res = $conn->luaEval( $script,
  98                                         array(
  99                                                 "$key:$i:bloom-metadata", # KEYS[1]
 100                                                 "$key:$i:bloom-data", # KEYS[2]
 101                                                 ceil( $size / $this->segments ), # ARGV[1]
 102                                                 $precision, # ARGV[2]
 103                                                 $epoch # ARGV[3]
 104                                         ),
 105                                         2 # number of first argument(s) that are keys
 106                                 );
 107                         }
 108                         $results = $conn->exec();
 109                         $res = $results && !in_array( false, $results, true );
 110                 } catch ( RedisException $e ) {
 111                         $this->handleException( $conn, $e );
 112                 }
 113
 114                 return ( $res !== false );
 115         }
 116
 117         protected function doAdd( $key, array $members ) {
 118                 $conn = $this->getConnection( 'master' );
 119                 if ( !$conn ) {
 120                         return false;
 121                 }
 122
 123                 static $script =
 124 <<<LUA
 125                 local kMetadata, kData = unpack(KEYS)
 126                 local aMember = unpack(ARGV)
 127
 128                 -- Check if the filter was initialized
 129                 if redis.call('EXISTS',kMetadata) == 0 or redis.call('EXISTS',kData) == 0 then
 130                         return false
 131                 end
 132
 133                 -- Initial expected entries and desired precision
 134                 local entries = 1*redis.call('HGET',kMetadata,'entries')
 135                 local precision = 1*redis.call('HGET',kMetadata,'precision')
 136                 local hash = redis.sha1hex(aMember)
 137
 138                 -- Based on the math from: http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives
 139                 -- 0.480453013 = ln(2)^2
 140                 local bits = math.ceil((entries * math.log(precision)) / -0.480453013)
 141
 142                 -- 0.693147180 = ln(2)
 143                 local k = math.floor(0.693147180 * bits / entries)
 144
 145                 -- This uses a variation on:
 146                 -- 'Less Hashing, Same Performance: Building a Better Bloom Filter'
 147                 -- http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
 148                 local h = { }
 149                 h[0] = tonumber(string.sub(hash, 1, 8 ), 16)
 150                 h[1] = tonumber(string.sub(hash, 9, 16), 16)
 151                 h[2] = tonumber(string.sub(hash, 17, 24), 16)
 152                 h[3] = tonumber(string.sub(hash, 25, 32), 16)
 153
 154                 for i=1, k do
 155                         local pos = (h[i % 2] + i * h[2 + (((i + (i % 2)) % 4) / 2)]) % bits
 156                         redis.call('SETBIT', kData, pos, 1)
 157                 end
 158
 159                 return 1
 160 LUA;
 161
 162                 $res = false;
 163                 try {
 164                         $conn->script( 'load', $script );
 165                         $conn->multi( Redis::PIPELINE );
 166                         foreach ( $members as $member ) {
 167                                 $i = $this->getSegment( $member );
 168                                 $conn->luaEval( $script,
 169                                         array(
 170                                                 "$key:$i:bloom-metadata", # KEYS[1],
 171                                                 "$key:$i:bloom-data", # KEYS[2]
 172                                                 $member # ARGV[1]
 173                                         ),
 174                                         2 # number of first argument(s) that are keys
 175                                 );
 176                         }
 177                         $results = $conn->exec();
 178                         $res = $results && !in_array( false, $results, true );
 179                 } catch ( RedisException $e ) {
 180                         $this->handleException( $conn, $e );
 181                 }
 182
 183                 if ( $res === false ) {
 184                         wfDebug( "Could not add to the '$key' bloom filter; it may be missing." );
 185                 }
 186
 187                 return ( $res !== false );
 188         }
 189
 190         protected function doSetStatus( $virtualKey, array $values ) {
 191                 $conn = $this->getConnection( 'master' );
 192                 if ( !$conn ) {
 193                         return null;
 194                 }
 195
 196                 $res = false;
 197                 try {
 198                         $res = $conn->hMSet( "$virtualKey:filter-metadata", $values );
 199                 } catch ( RedisException $e ) {
 200                         $this->handleException( $conn, $e );
 201                 }
 202
 203                 return ( $res !== false );
 204         }
 205
 206         protected function doGetStatus( $virtualKey ) {
 207                 $conn = $this->getConnection( 'slave' );
 208                 if ( !$conn ) {
 209                         return false;
 210                 }
 211
 212                 $res = false;
 213                 try {
 214                         $res = $conn->hGetAll( "$virtualKey:filter-metadata" );
 215                 } catch ( RedisException $e ) {
 216                         $this->handleException( $conn, $e );
 217                 }
 218
 219                 if ( is_array( $res ) ) {
 220                         $res['lastID'] = isset( $res['lastID'] ) ? $res['lastID'] : null;
 221                         $res['asOfTime'] = isset( $res['asOfTime'] ) ? $res['asOfTime'] : null;
 222                         $res['epoch'] = isset( $res['epoch'] ) ? $res['epoch'] : null;
 223                 }
 224
 225                 return $res;
 226         }
 227
 228         protected function doIsHit( $key, $member ) {
 229                 $conn = $this->getConnection( 'slave' );
 230                 if ( !$conn ) {
 231                         return null;
 232                 }
 233
 234                 static $script =
 235 <<<LUA
 236                 local kMetadata, kData = unpack(KEYS)
 237                 local aMember = unpack(ARGV)
 238
 239                 -- Check if the filter was initialized
 240                 if redis.call('EXISTS',kMetadata) == 0 or redis.call('EXISTS',kData) == 0 then
 241                         return false
 242                 end
 243
 244                 -- Initial expected entries and desired precision.
 245                 -- This determines the size of the first and subsequent filters.
 246                 local entries = redis.call('HGET',kMetadata,'entries')
 247                 local precision = redis.call('HGET',kMetadata,'precision')
 248                 local hash = redis.sha1hex(aMember)
 249
 250                 -- This uses a variation on:
 251                 -- 'Less Hashing, Same Performance: Building a Better Bloom Filter'
 252                 -- http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf
 253                 local h = { }
 254                 h[0] = tonumber(string.sub(hash, 1, 8 ), 16)
 255                 h[1] = tonumber(string.sub(hash, 9, 16), 16)
 256                 h[2] = tonumber(string.sub(hash, 17, 24), 16)
 257                 h[3] = tonumber(string.sub(hash, 25, 32), 16)
 258
 259                 -- 0.480453013 = ln(2)^2
 260                 local bits = math.ceil((entries * math.log(precision)) / -0.480453013)
 261
 262                 -- 0.693147180 = ln(2)
 263                 local k = math.floor(0.693147180 * bits / entries)
 264
 265                 local found = 1
 266                 for i=1, k do
 267                         local pos = (h[i % 2] + i * h[2 + (((i + (i % 2)) % 4) / 2)]) % bits
 268                         if redis.call('GETBIT', kData, pos) == 0 then
 269                                 found = 0
 270                                 break
 271                         end
 272                 end
 273
 274                 return found
 275 LUA;
 276
 277                 $res = null;
 278                 try {
 279                         $i = $this->getSegment( $member );
 280                         $res = $conn->luaEval( $script,
 281                                 array(
 282                                         "$key:$i:bloom-metadata", # KEYS[1],
 283                                         "$key:$i:bloom-data", # KEYS[2]
 284                                         $member # ARGV[1]
 285                                 ),
 286                                 2 # number of first argument(s) that are keys
 287                         );
 288                 } catch ( RedisException $e ) {
 289                         $this->handleException( $conn, $e );
 290                 }
 291
 292                 return is_int( $res ) ? (bool)$res : null;
 293         }
 294
 295         protected function doDelete( $key ) {
 296                 $conn = $this->getConnection( 'master' );
 297                 if ( !$conn ) {
 298                         return false;
 299                 }
 300
 301                 $res = false;
 302                 try {
 303                         $keys = array();
 304                         for ( $i = 0; $i < $this->segments; ++$i ) {
 305                                 $keys[] = "$key:$i:bloom-metadata";
 306                                 $keys[] = "$key:$i:bloom-data";
 307                         }
 308                         $res = $conn->delete( $keys );
 309                 } catch ( RedisException $e ) {
 310                         $this->handleException( $conn, $e );
 311                 }
 312
 313                 return ( $res !== false );
 314         }
 315
 316         public function getScopedLock( $virtualKey ) {
 317                 $status = Status::newGood();
 318                 return ScopedLock::factory( $this->lockMgr,
 319                         array( $virtualKey ), LockManager::LOCK_EX, $status );
 320         }
 321
 322         /**
 323          * @param string $member
 324          * @return integer
 325          */
 326         protected function getSegment( $member ) {
 327                 return hexdec( substr( md5( $member ), 0, 2 ) ) % $this->segments;
 328         }
 329
 330         /**
 331          * @param string $to (master/slave)
 332          * @return RedisConnRef|bool Returns false on failure
 333          */
 334         protected function getConnection( $to ) {
 335                 if ( $to === 'master' ) {
 336                         $conn = $this->redisPool->getConnection( $this->servers[0] );
 337                 } else {
 338                         static $lastServer = null;
 339
 340                         $conn = false;
 341                         if ( $lastServer ) {
 342                                 $conn = $this->redisPool->getConnection( $lastServer );
 343                                 if ( $conn ) {
 344                                         return $conn; // reuse connection
 345                                 }
 346                         }
 347                         $servers = $this->servers;
 348                         $attempts = min( 3, count( $servers ) );
 349                         for ( $i = 1; $i <= $attempts; ++$i ) {
 350                                 $index = mt_rand( 0, count( $servers ) - 1 );
 351                                 $conn = $this->redisPool->getConnection( $servers[$index] );
 352                                 if ( $conn ) {
 353                                         $lastServer = $servers[$index];
 354                                         return $conn;
 355                                 }
 356                                 unset( $servers[$index] ); // skip next time
 357                                 $servers = array_values( $servers ); // reindex
 358                         }
 359                 }
 360
 361                 return $conn;
 362         }
 363
 364         /**
 365          * @param RedisConnRef $conn
 366          * @param Exception $e
 367          */
 368         protected function handleException( RedisConnRef $conn, $e ) {
 369                 $this->redisPool->handleError( $conn, $e );
 370         }
 371 }