Patch: Dynamic hashtable sizing

[Brad Fitzpatrick]

Nice.

Regarding the 'gotcha', though:  How hard would an incremental copy be,
copying only 'n' buckets per event loop?  You'd have to have a
'currently_at' position kept, and any changes made before that point while
you're still copying would need to be mirrored in the still-growing-slowly
larger copy.  Then when you're all the way caught up, remove the old one,
and zero out the 'currently_at' position, indicating there's no copy in
progress.

Or, even simpler:  no auto-resizing and just make the initial hashtable
size a function of the max memory parameter.  A lot of data structures in
the Linux kernel work like that.

I'm just afraid this gotcha would result in unnecessary pain on the
mailing list.  And if people are doing aggressive monitoring, alerts
going off, and clients with small timeouts, rehashing unnecessarily.
Without knowing their CPU/memory speed, we can't even reliably say what
the delay would be.

So I'd like to go with either an incremental or dynamically-tuned-at-init
approach.  Preference?



On Mon, 7 Aug 2006, Steven Grimm wrote:

> Here's a patch that squeezes another few percent of CPU time improvement
> out of our large caches. It adds auto-resize capability to the memcached
> hash table code.
>
> For small caches, this is a memory win because the initial size is now
> substantially lower, so the constant-factor memory overhead of memcached
> will be less. For large caches, this is a CPU time win because the old
> size (1 million buckets) was pretty easy to exceed substantially if you
> cached a lot of small items. One of our sets of servers has over 40
> million cache entries per server, which means that on average, the old
> code was having to do 40 string compares for each key in a "get" request.
>
> The gotcha: the hashtable has to resize itself periodically. That is not
> really noticeable with cache sizes up to a few hundred thousand entries,
> but beyond that the server will pause while it re-buckets all the
> existing cache entries. The hashtable never shrinks, only grows, so once
> your cache has filled up and you've started expiring old entries (and
> thus the number of entries reaches its maximum) you won't see any more
> pauses. For a 40-million-entry hashtable, you will see a total of 9
> pauses on the way to equilibrium, and only the last couple of them will
> be noticeable on modern hardware.
>
> This patch doubles the size of the hashtable when there are enough
> entries to fill the double-sized table -- that is, when the number of
> entries exceeds 2x the current hashtable size. The performance
> difference between doing it that way and expanding at 1x the current
> size was not really measurable in my tests, and this way eats less
> memory (a 32-million-bucket hashtable on a 64-bit system is not exactly
> tiny.)
>
> -Steve
>