I think this will be less of a problem than you might expect (though my
experience and evidence is at the tens of thousands of users level rather
than the millions of users level).
In the limit (no cache hits), the volume of DNS cache space used by DKIM
keys will scale with the volume of email processed by the site, however we
hope that DNS caches will provide some benefit so the cache space used
will be less than this. In practice this benefit is surprisingly small
because of the very heavy tail on the distribution of domains - I use the
present tense because this is true now for the DNS lookups performed by
current MTAs in response to incoming email, e.g. sender domain
verification. We're already close to at least one non-repeated lookup per
message. DKIM probably won't make it much worse even with per-user keys,
and the damage can be mitigated by low TTLs.
The following paper is very relevant to this. Its conclusion is that the
DNS is scalable because of the cacheing of NS records. Leaf record
cacheing (they talk about A records looked up by clients, but the same
would be true for email-driven lookups - MXs and DKKs) provides much less
benefit. The corollary is that increasing the load on the leafs is not an
attack on the foundations of DNS's scalability.
http://nms.csail.mit.edu/projects/dns/
Tony.
--
f.a.n.finch <dot(_at_)dotat(_dot_)at> http://dotat.at/
BISCAY: WEST 5 OR 6 BECOMING VARIABLE 3 OR 4. SHOWERS AT FIRST. MODERATE OR
GOOD.