[Summary view] [Print] [Text view]

   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              }
 358          }
 359  
 360          return $conn;
 361      }
 362  
 363      /**
 364       * @param RedisConnRef $conn
 365       * @param Exception $e
 366       */
 367  	protected function handleException( RedisConnRef $conn, $e ) {
 368          $this->redisPool->handleError( $conn, $e );
 369      }
 370  }