Trond Norbye's Weblog

How well is your hash table working for you?

If you look in the internals of memcached you will find a large hash table where all of the items are stored in (we hash to a bucket before we do a linary search in a linked list to try to locate the item). Memcached is supposed to grow the hash table automatically to avoid having too long lists in each bucket (that would kill the performance), but wouldn't it be cool to know how well the hash table works for you?? Well that's really easy to find out with dtrace!

So let's look at the user-supplied-bugs in libmemcached as an example. I already have memcached running on my server, so I just open up a new terminal and start the following dtrace one-liner:

trond@opensolaris> pfexec dtrace -n ':::assoc-find { @a = quantize(arg2);}'
dtrace: description ':::assoc-find ' matched 1 probe

In another terminal I just type the following commands:

trond@opensolaris> export MEMCACHED_SERVERS=localhost:11211
trond@opensolaris> ./testapp user
servers localhost:11211
        localhost : 11211


user

Testing user_supplied_bug1                                       0.993 [ ok ]
Testing user_supplied_bug2                                       0.009 [ ok ]
Testing user_supplied_bug3                                       0.041 [ ok ]
Testing user_supplied_bug4                                       0.000 [ ok ]
Testing user_supplied_bug5                                       0.192 [ ok ]
Testing user_supplied_bug6                                       0.053 [ ok ]
Testing user_supplied_bug7                                       0.031 [ ok ]
Testing user_supplied_bug8                                       0.000 [ ok ]
Testing user_supplied_bug9                                       0.004 [ ok ]
Testing user_supplied_bug10                                      2.572 [ ok ]
Testing user_supplied_bug11                                      2.555 [ ok ]
Testing user_supplied_bug12                                      0.000 [ ok ]
Testing user_supplied_bug13                                      0.008 [ ok ]
Testing user_supplied_bug14                                      2.607 [ ok ]
Testing user_supplied_bug15                                      0.000 [ ok ]
Testing user_supplied_bug16                                      0.008 [ ok ]
Testing user_supplied_bug18                                      0.003 [ ok ]
Testing user_supplied_bug19                                      0.000 [ ok ]
Testing user_supplied_bug20                                      0.010 [ ok ]

All tests completed successfully

So let's terminate dtrace and look at the results:

^C


           value  ------------- Distribution ------------- count    
              -1 |                                         0        
               0 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 245648   
               1 |                                         589      
               2 |                                         35       
               4 |                                         0

So what does this tell us? In almost all of our requests the interesting item is the first item in the bucket :-)

Posted at 09:48AM Mar 28, 2009 by trond in Memcached  |  Comments[2]