>> I have clustered that table, its still unbelievably slow.
>
> Did you actually delete the old entries before clustering it?  if it's
> still got 4G of old sessions or whatever in it, clustering ain't gonna
> help.
Also, IMHO it is a lot better to store sessions in something like  
memcached, rather than imposing this rather large load on the main  
database...
PS : if your site has been down for 6 hours, you can TRUNCATE your  
sessions table...