如果用户访问 n 次，则计算唯一用户数

Question

我想在广告网络中实施 FreqCapping。我想在一天中仅 n 次向唯一用户提供活动。如果n=1，我可以用redis中的BloomFilter来实现，但通常n大于1。有没有针对这个问题的数据结构（甚至是概率数据结构）？那是在redis中实现的吗？

Answer 1

如果 n 很小，只需在 '1x' + user、'2x' + user、...、n + 'x' + 'user' 上使用布隆过滤器。作为详细信息，请按随机顺序检查它们。这意味着当用户只在一小部分时间被看到时，您的查找次数就会减少。

如果n很大，考虑只进行固定数量的随机查找。当你接近你的极限时，这会交易表现，有时当你接近你的极限时选择不填充。例如，最多 4 次查找，在达到极限的 50% 时，您在 90% 的时间内做出了正确的选择，而在达到极限的 80% 时，您仍然在 60% 左右做出了正确的选择时间。如果 n=20，当您达到限制时，您将节省很多的时间。

我确信有某种特殊的布隆过滤器可以达到类似的限制，你每次 check/set 哈希函数的一个随机子集（检查比你设置的更多）。但是你不会在 Redis 中找到这种特殊结构 pre-built。

我建议的概率版本是这样的：

def is_available(user, k=4, n=20):
    tried = []
    for 1..k:
        i = rand(n)
        while i in tried:
            i = rand(n)
        id = user + ":" + str(i)
        if bloomfilter.lookup(id):
            tried.append(i)
        else:
            bloomfilter.add(id)
            return True
    return False

随机化的目的是减少您需要的查找次数。如果您每次都按照相同的顺序进行，那么在第 10 次访问时，您将进行 9 次查找，然后才发现它们没有超过配额。但是如果 n 是 20 并且您以随机顺序进行，则第一次查找的一半时间就足够了。这减少了往返次数，从而提高了性能，这在广告技术中非常重要。

Answer 2

听起来你在描述 Count-min sketch, and while Redis core doesn't have it, RedisBloom 的作用:)

如果用户访问 n 次，则计算唯一用户数

Count unique users if user visit n times

algorithm

bloom-filter

redis