I know it all depends. 
I run a site which is averaging 150-200 request/minute or 200,000 pageviews per day on average. The load is handled over two webservers on Joyent. I am presently using the default CookieStore as my SessionStore.
I probably would of not questioned my SessionStore but I am running into two problems a couple dozen times a day. I am having problems sometimes with both CookieOverflow (when user is doing friend invites with the contacts gem) and InvalidAuthenticityToken (on session#create). I know the SessionStorage might have no impact what so ever on my InvalidAuthenticityToken but I am out of guesses for that one.
Which storage engine do you recommend? What should I use. Any other ideas for why I would be getting an InvalidAuthenticityToken problem on session#create.
I greatly appreciate your feedback!
