201081 - session id's are not hashed effectively

Status: RESOLVED FIXED

(NSS :: Libraries, enhancement, P2)

Description

[Ian McGreer]

Session id's are created by a monotonically increasing counter.  They are hashed
by a mod operation using the size of the session table as a base (between 1024
and 4096 buckets, IIRC).

This leads to sessions being created in clusters of buckets, often sharing the
same lock (over a group of buckets).  Pallab has found an uneven distribution of
lock contention for the session table locks, which he believes is due to this
clustering.

The proposed remedy is to use a multiplier when computing the hash of a session
id.  I grabbed one off a web search, patch forthcoming.  Kirk has tested this on
the 3.3 branch and it seems to have a positive effect.

Comment 1

[Ian McGreer]

Attachment: use multiplier when computing session id hash

Comment 2

[Ian McGreer]

Comment on attachment 119720 [details] [diff] [review]
use multiplier when computing session id hash


BTW, Kirk's test results are in bug 198159.

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

Could we get test results that DO use zone allocator?

Comment 4

[Kirk Erickson]

Attachment: selfserv stress of NSS_3_8_RTM

Nelson, I stressed 3.8 with the zone allocator engaged
(with and without session_id_hash.patch).

Hitting this machine from 14 client machines on the same subnet:
SunOS dsame2 5.8 Generic_108528-16 sun4u sparc SUNW,Ultra-4
System Configuration:  Sun Microsystems  sun4u Sun Enterprise 450
    (4 X UltraSPARC-II 480MHz)
System clock frequency: 96 MHz
Memory size: 4096 Megabytes

I saw a wash (no gain).

This is the same machine where we recorded the gain on
the 3.3 branch without the zone allocator.  So turned off
zone allocator and generated the "-nozones" runs.

See a small gain when the zone allocator is not engaged.

Comment 5

[Robert Relyea]

Comment on attachment 119720 [details] [diff] [review]
use multiplier when computing session id hash

Kirks tests show that even on the tip there is a marginal gain with the new
code. r= relyea

Comment 6

[Wan-Teh Chang]

Ian, could you cite the reference for your hash multipler?

Here is the Fibonacci hashing function used by PLHashTable.
(Brendan, do I get this right?)

size = 2^n, a power of 2.

value is a 32-bit unsigned integer.

hash(value, size) = (value * 0x9E3779B9U) >> (32 - n).

(0x9E3779B9U = 2654435769U is a number related to the
golden ratio.)

Comment 7

[Brendan Eich [:brendan]]

0x9E3779B9U is the golden mean represented as a fixed point 32 bit fraction. 
See Knuth 6.4 (do the exercises, too ;-) for why this number, related to the
Fibonacci numbers, is a good multiplier.  Any (fixed point approximation of an)
irrational number will be better than a rational number, but 2/(1+sqrt(5)) is best.

Probably unrelated reference:
http://lxr.mozilla.org/mozilla/source/js/src/jsdhash.h and the companion .c file
are worth a read if double hashing, using multiplicative hash, might be better
than chaining for handling collisions.

/be

Comment 8

[Ian McGreer]

Attachment: use suggested multipier based on golden mean

Same patch, using suggested multiplier.

Wan-Teh, should this go in 3.8.1?

Comment 9

[Wan-Teh Chang]

Comment on attachment 120072 [details] [diff] [review]
use suggested multipier based on golden mean

#define SHMULTIPLIER 0x9E3779B9U

#define pk11_hash(value,size) \
	((PRUint32)((value) * SHMULTIPLIER) & (size-1))

This is incorrect.  The hash should be:

#define pk11_hash(value,log2size) \
	((PRUint32)((value) * SHMULTIPLIER) >> (32-log2size))

where log2size is the log base 2 of size.

This means all the call sites of the pk11_hash macro would
also need to be changed.

Another option is simply to make size a prime number with
certain properties, for example, 1009, and say

#define pk11_hash(value,size) ((value) % (size))

This is the division method.  The current definition of
pk11_hash is the division method with size being a power
of 2.

Comment 10

[Ian McGreer]

Original patch checked in.  In this case, we are not hashing arbitrary keys, but
a counter.  Over time, all keys are equally likely, so the division method is
suitable.  The use of the multiplier is simply to spread keys over the table, so
that two successive session ids are not likely to be next to each other (and
hence within the same mutex).  The multiplier has been verified to maintain the
even distribution over all 2^32 keys.

The original patch was checked in because that change was already made on the
3.3 branch, so this is more consistent.