You can store "possible attacking" IP's in a counting Bloom filter and start blocking when it saturates. Random false positives are probably not an issue for an

You can store "possible attacking" IP's in a counting Bloom filter and start blocking when it saturates. Random false positives are probably not an issue for an analytics service that's inherently lossy anyways. By using Bloom filter you avoid storing IP's, and save tons of space. They're basically required for rate limiting in IPV6 where the address space is so large an attacker can just run you out of ram by using so many different IP's. It's also pretty common to have several thresholds of blocking based on individual IP vs subnets. So if more than 2 ips get blocked in a small subnet, you block the whole subnet.