Laird Breyer <laird(_at_)lbreyer(_dot_)com> wrote:
While your 40 million user database has constant activity, I presume
the vast majority of usernames have a long lifetime, a few days at
least. So if you build username snapshots at fixed intervals, then
users would have to wait a little for their new address to become
"live" etc.
If you're willing to suffer a _few_ false positives on the filtering,
and do a little more arithmetic, you can do better. Construct some
number of hash functions whose output is an address that holds 1 bit.
Hash each email address with each function, and turn the pointed-at
bit on. When email comes in, apply all the hash functions and check
the pointed-at bits. If they're all on, pass the message through.
A new user gets turned on immediately, by turning on the necessary
bits in the table. A deleted user doesn't go away until the next full
rebuild. There's a small chance (depends on hash table size, number
of hash functions, number of valid email addresses) of a random
address being accepted due to collisions, but this can be made
acceptably small. (Using a parameterized set of hash functions allows
them to be changed every rebuild, to avoid the chance that a commonly
attacked bad address passes.)
Seth
_______________________________________________
Asrg mailing list
Asrg(_at_)ietf(_dot_)org
https://www1.ietf.org/mailman/listinfo/asrg