using Microsoft.Extensions.Logging;
|
using Microsoft.Extensions.Options;
|
using WIDESEAWCS_RedisService.Connection;
|
using WIDESEAWCS_RedisService.Options;
|
using System.Text;
|
|
namespace WIDESEAWCS_RedisService.Bitmap
|
{
|
public class RedisBloomFilterService : IBloomFilterService
|
{
|
private readonly IRedisConnectionManager _connectionManager;
|
private readonly RedisOptions _options;
|
private readonly ILogger<RedisBloomFilterService> _logger;
|
private const int HashCount = 5;
|
private const long BitSize = 1_000_000;
|
|
public RedisBloomFilterService(
|
IRedisConnectionManager connectionManager,
|
IOptions<RedisOptions> options,
|
ILogger<RedisBloomFilterService> logger)
|
{
|
_connectionManager = connectionManager;
|
_options = options.Value;
|
_logger = logger;
|
}
|
|
private string BuildKey(string key) => $"{_options.KeyPrefix}bloom:{key}";
|
|
public void Add(string filterName, string value)
|
{
|
var db = _connectionManager.GetDatabase();
|
var fullKey = BuildKey(filterName);
|
var offsets = GetHashOffsets(value);
|
foreach (var offset in offsets)
|
db.StringSetBit(fullKey, offset, true);
|
}
|
|
public bool MayExist(string filterName, string value)
|
{
|
var db = _connectionManager.GetDatabase();
|
var fullKey = BuildKey(filterName);
|
var offsets = GetHashOffsets(value);
|
return offsets.All(offset => db.StringGetBit(fullKey, offset));
|
}
|
|
public void AddRange(string filterName, IEnumerable<string> values)
|
{
|
foreach (var value in values) Add(filterName, value);
|
}
|
|
private long[] GetHashOffsets(string value)
|
{
|
var offsets = new long[HashCount];
|
var bytes = Encoding.UTF8.GetBytes(value);
|
for (int i = 0; i < HashCount; i++)
|
{
|
uint hash = MurmurHash(bytes, (uint)i);
|
offsets[i] = hash % BitSize;
|
}
|
return offsets;
|
}
|
|
private static uint MurmurHash(byte[] data, uint seed)
|
{
|
const uint c1 = 0xcc9e2d51;
|
const uint c2 = 0x1b873593;
|
uint h1 = seed;
|
int len = data.Length;
|
int blocks = len / 4;
|
|
for (int i = 0; i < blocks; i++)
|
{
|
uint k1 = BitConverter.ToUInt32(data, i * 4);
|
k1 *= c1; k1 = RotateLeft(k1, 15); k1 *= c2;
|
h1 ^= k1; h1 = RotateLeft(h1, 13); h1 = h1 * 5 + 0xe6546b64;
|
}
|
|
uint tail = 0;
|
int tailIdx = blocks * 4;
|
switch (len & 3)
|
{
|
case 3: tail ^= (uint)data[tailIdx + 2] << 16; goto case 2;
|
case 2: tail ^= (uint)data[tailIdx + 1] << 8; goto case 1;
|
case 1: tail ^= data[tailIdx]; tail *= c1; tail = RotateLeft(tail, 15); tail *= c2; h1 ^= tail; break;
|
}
|
|
h1 ^= (uint)len;
|
h1 ^= h1 >> 16; h1 *= 0x85ebca6b;
|
h1 ^= h1 >> 13; h1 *= 0xc2b2ae35;
|
h1 ^= h1 >> 16;
|
return h1;
|
}
|
|
private static uint RotateLeft(uint x, byte r) => (x << r) | (x >> (32 - r));
|
}
|
}
|
