Re: Extensible hashing and RCU

[Evgeniy Polyakov <johnpol@2ka.mipt.ru>]

On Sun, Feb 18, 2007 at 07:46:22PM +0100, Eric Dumazet (dada1@cosmosbay.com) wrote:
> >Why anyone do not want to use trie - for socket-like loads it has
> >exactly constant search/insert/delete time and scales as hell.
> >
> 
> Because we want to be *very* fast. You cannot beat hash table.
> 
> Say you have 1.000.000 tcp connections, with 50.000 incoming packets per 
> second to *random* streams...

What is really good in trie, that you may have upto 2^32 connections
without _any_ difference in lookup performance of random streams.

> With a 2^20 hashtable, a lookup uses one cache line (the hash head pointer) 
> plus one cache line to get the socket (you need it to access its refcounter)
> 
> Several attempts were done in the past to add RCU to ehash table (last done 
> by Benjamin LaHaise last March). I believe this was delayed a bit, because 
> David would like to be able to resize the hash table...

This is a theory.
Practice includes cost for hashing, locking, and list traversal
(each pointer is in own cache line btw, which must be fetched) and plus
the same for time wait sockets (if we are unlucky).

No need to talk about price of cache miss when there might be more
serious problems - for example length of the linked list to traverse each 
time new packet is received.

For example lookup time in trie with 1.6 millions random 3-dimensional
32bit (saddr/daddr/ports) entries is about 1 microsecond on amd athlon64 
3500 cpu (test was ran in userspace emulator though).
Data obtained from netchannels research:
http://tservice.net.ru/~s0mbre/blog/2006/12/02#2006_12_02

I think I need to setup similar emulator for hash table of the above
size to check hash/list goodness.

> I am not really interested in hash resizing, because an admin can size it 
> at boot time. But RCU is definitly *wanted*

Trie in that regard is true winner - its RCU'fication is trivial.

> Note : It would be good to also use RCU for UDP, because the current rwlock 
> protecting udp_hash[] is a scalability problem.

-- 
	Evgeniy Polyakov