diff options
Diffstat (limited to 'includes/cache/bloom/BloomCacheRedis.php')
| -rw-r--r-- | includes/cache/bloom/BloomCacheRedis.php | 370 |
1 files changed, 370 insertions, 0 deletions
diff --git a/includes/cache/bloom/BloomCacheRedis.php b/includes/cache/bloom/BloomCacheRedis.php new file mode 100644 index 00000000..212e5e8b --- /dev/null +++ b/includes/cache/bloom/BloomCacheRedis.php @@ -0,0 +1,370 @@ +<?php +/** + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * http://www.gnu.org/copyleft/gpl.html + * + * @file + * @author Aaron Schulz + */ + +/** + * Bloom filter implemented using Redis + * + * The Redis server must be >= 2.6 and should have volatile-lru or volatile-ttl + * if there is any eviction policy. It should not be allkeys-* in any case. Also, + * this can be used in a simple master/slave setup or with Redis Sentinel preferably. + * + * Some bits are based on https://github.com/ErikDubbelboer/redis-lua-scaling-bloom-filter + * but are simplified to use a single filter instead of up to 32 filters. + * + * @since 1.24 + */ +class BloomCacheRedis extends BloomCache { + /** @var RedisConnectionPool */ + protected $redisPool; + /** @var RedisLockManager */ + protected $lockMgr; + /** @var array */ + protected $servers; + /** @var integer Federate each filter into this many redis bitfield objects */ + protected $segments = 128; + + /** + * @params include: + * - redisServers : list of servers (address:<port>) (the first is the master) + * - redisConf : additional redis configuration + * + * @param array $config + */ + public function __construct( array $config ) { + parent::__construct( $config ); + + $redisConf = $config['redisConfig']; + $redisConf['serializer'] = 'none'; // manage that in this class + $this->redisPool = RedisConnectionPool::singleton( $redisConf ); + $this->servers = $config['redisServers']; + $this->lockMgr = new RedisLockManager( array( + 'lockServers' => array( 'srv1' => $this->servers[0] ), + 'srvsByBucket' => array( 0 => array( 'srv1' ) ), + 'redisConfig' => $config['redisConfig'] + ) ); + } + + protected function doInit( $key, $size, $precision ) { + $conn = $this->getConnection( 'master' ); + if ( !$conn ) { + return false; + } + + // 80000000 items at p = .001 take up 500MB and fit into one value. + // Do not hit the 512MB redis value limit by reducing the demands. + $size = min( $size, 80000000 * $this->segments ); + $precision = max( round( $precision, 3 ), .001 ); + $epoch = microtime( true ); + + static $script = +<<<LUA + local kMetadata, kData = unpack(KEYS) + local aEntries, aPrec, aEpoch = unpack(ARGV) + if redis.call('EXISTS',kMetadata) == 0 or redis.call('EXISTS',kData) == 0 then + redis.call('DEL',kMetadata) + redis.call('HSET',kMetadata,'entries',aEntries) + redis.call('HSET',kMetadata,'precision',aPrec) + redis.call('HSET',kMetadata,'epoch',aEpoch) + redis.call('SET',kData,'') + return 1 + end + return 0 +LUA; + + $res = false; + try { + $conn->script( 'load', $script ); + $conn->multi( Redis::MULTI ); + for ( $i = 0; $i < $this->segments; ++$i ) { + $res = $conn->luaEval( $script, + array( + "$key:$i:bloom-metadata", # KEYS[1] + "$key:$i:bloom-data", # KEYS[2] + ceil( $size / $this->segments ), # ARGV[1] + $precision, # ARGV[2] + $epoch # ARGV[3] + ), + 2 # number of first argument(s) that are keys + ); + } + $results = $conn->exec(); + $res = $results && !in_array( false, $results, true ); + } catch ( RedisException $e ) { + $this->handleException( $conn, $e ); + } + + return ( $res !== false ); + } + + protected function doAdd( $key, array $members ) { + $conn = $this->getConnection( 'master' ); + if ( !$conn ) { + return false; + } + + static $script = +<<<LUA + local kMetadata, kData = unpack(KEYS) + local aMember = unpack(ARGV) + + -- Check if the filter was initialized + if redis.call('EXISTS',kMetadata) == 0 or redis.call('EXISTS',kData) == 0 then + return false + end + + -- Initial expected entries and desired precision + local entries = 1*redis.call('HGET',kMetadata,'entries') + local precision = 1*redis.call('HGET',kMetadata,'precision') + local hash = redis.sha1hex(aMember) + + -- Based on the math from: http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives + -- 0.480453013 = ln(2)^2 + local bits = math.ceil((entries * math.log(precision)) / -0.480453013) + + -- 0.693147180 = ln(2) + local k = math.floor(0.693147180 * bits / entries) + + -- This uses a variation on: + -- 'Less Hashing, Same Performance: Building a Better Bloom Filter' + -- http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf + local h = { } + h[0] = tonumber(string.sub(hash, 1, 8 ), 16) + h[1] = tonumber(string.sub(hash, 9, 16), 16) + h[2] = tonumber(string.sub(hash, 17, 24), 16) + h[3] = tonumber(string.sub(hash, 25, 32), 16) + + for i=1, k do + local pos = (h[i % 2] + i * h[2 + (((i + (i % 2)) % 4) / 2)]) % bits + redis.call('SETBIT', kData, pos, 1) + end + + return 1 +LUA; + + $res = false; + try { + $conn->script( 'load', $script ); + $conn->multi( Redis::PIPELINE ); + foreach ( $members as $member ) { + $i = $this->getSegment( $member ); + $conn->luaEval( $script, + array( + "$key:$i:bloom-metadata", # KEYS[1], + "$key:$i:bloom-data", # KEYS[2] + $member # ARGV[1] + ), + 2 # number of first argument(s) that are keys + ); + } + $results = $conn->exec(); + $res = $results && !in_array( false, $results, true ); + } catch ( RedisException $e ) { + $this->handleException( $conn, $e ); + } + + if ( $res === false ) { + wfDebug( "Could not add to the '$key' bloom filter; it may be missing." ); + } + + return ( $res !== false ); + } + + protected function doSetStatus( $virtualKey, array $values ) { + $conn = $this->getConnection( 'master' ); + if ( !$conn ) { + return null; + } + + $res = false; + try { + $res = $conn->hMSet( "$virtualKey:filter-metadata", $values ); + } catch ( RedisException $e ) { + $this->handleException( $conn, $e ); + } + + return ( $res !== false ); + } + + protected function doGetStatus( $virtualKey ) { + $conn = $this->getConnection( 'slave' ); + if ( !$conn ) { + return false; + } + + $res = false; + try { + $res = $conn->hGetAll( "$virtualKey:filter-metadata" ); + } catch ( RedisException $e ) { + $this->handleException( $conn, $e ); + } + + if ( is_array( $res ) ) { + $res['lastID'] = isset( $res['lastID'] ) ? $res['lastID'] : null; + $res['asOfTime'] = isset( $res['asOfTime'] ) ? $res['asOfTime'] : null; + $res['epoch'] = isset( $res['epoch'] ) ? $res['epoch'] : null; + } + + return $res; + } + + protected function doIsHit( $key, $member ) { + $conn = $this->getConnection( 'slave' ); + if ( !$conn ) { + return null; + } + + static $script = +<<<LUA + local kMetadata, kData = unpack(KEYS) + local aMember = unpack(ARGV) + + -- Check if the filter was initialized + if redis.call('EXISTS',kMetadata) == 0 or redis.call('EXISTS',kData) == 0 then + return false + end + + -- Initial expected entries and desired precision. + -- This determines the size of the first and subsequent filters. + local entries = redis.call('HGET',kMetadata,'entries') + local precision = redis.call('HGET',kMetadata,'precision') + local hash = redis.sha1hex(aMember) + + -- This uses a variation on: + -- 'Less Hashing, Same Performance: Building a Better Bloom Filter' + -- http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf + local h = { } + h[0] = tonumber(string.sub(hash, 1, 8 ), 16) + h[1] = tonumber(string.sub(hash, 9, 16), 16) + h[2] = tonumber(string.sub(hash, 17, 24), 16) + h[3] = tonumber(string.sub(hash, 25, 32), 16) + + -- 0.480453013 = ln(2)^2 + local bits = math.ceil((entries * math.log(precision)) / -0.480453013) + + -- 0.693147180 = ln(2) + local k = math.floor(0.693147180 * bits / entries) + + local found = 1 + for i=1, k do + local pos = (h[i % 2] + i * h[2 + (((i + (i % 2)) % 4) / 2)]) % bits + if redis.call('GETBIT', kData, pos) == 0 then + found = 0 + break + end + end + + return found +LUA; + + $res = null; + try { + $i = $this->getSegment( $member ); + $res = $conn->luaEval( $script, + array( + "$key:$i:bloom-metadata", # KEYS[1], + "$key:$i:bloom-data", # KEYS[2] + $member # ARGV[1] + ), + 2 # number of first argument(s) that are keys + ); + } catch ( RedisException $e ) { + $this->handleException( $conn, $e ); + } + + return is_int( $res ) ? (bool)$res : null; + } + + protected function doDelete( $key ) { + $conn = $this->getConnection( 'master' ); + if ( !$conn ) { + return false; + } + + $res = false; + try { + $keys = array(); + for ( $i = 0; $i < $this->segments; ++$i ) { + $keys[] = "$key:$i:bloom-metadata"; + $keys[] = "$key:$i:bloom-data"; + } + $res = $conn->delete( $keys ); + } catch ( RedisException $e ) { + $this->handleException( $conn, $e ); + } + + return ( $res !== false ); + } + + public function getScopedLock( $virtualKey ) { + $status = Status::newGood(); + return ScopedLock::factory( $this->lockMgr, + array( $virtualKey ), LockManager::LOCK_EX, $status ); + } + + /** + * @param string $member + * @return integer + */ + protected function getSegment( $member ) { + return hexdec( substr( md5( $member ), 0, 2 ) ) % $this->segments; + } + + /** + * $param string $to (master/slave) + * @return RedisConnRef|bool Returns false on failure + */ + protected function getConnection( $to ) { + if ( $to === 'master' ) { + $conn = $this->redisPool->getConnection( $this->servers[0] ); + } else { + static $lastServer = null; + + $conn = false; + if ( $lastServer ) { + $conn = $this->redisPool->getConnection( $lastServer ); + if ( $conn ) { + return $conn; // reuse connection + } + } + $servers = $this->servers; + $attempts = min( 3, count( $servers ) ); + for ( $i = 1; $i <= $attempts; ++$i ) { + $index = mt_rand( 0, count( $servers ) - 1 ); + $conn = $this->redisPool->getConnection( $servers[$index] ); + if ( $conn ) { + $lastServer = $servers[$index]; + return $conn; + } + unset( $servers[$index] ); // skip next time + } + } + + return $conn; + } + + /** + * @param RedisConnRef $conn + * @param Exception $e + */ + protected function handleException( RedisConnRef $conn, $e ) { + $this->redisPool->handleError( $conn, $e ); + } +} |