After struggling with all available options, I ended up writing a JWT token based SessionStore provider (the session travels inside a cookie, and no backend storage is needed).
http://www.drupalonwindows.com/en/content/token-sessionstate
Advantages:
- Drop-in replacement, no changes to your code are needed
- Scale better
than any other centralized store, as no session storage backend is
needed.
- Faster than any other session storage, as no data needs to be
retrieved from any session storage
- Consumes no server resources for
session storage.
- Default non-blocking implementation: concurrent
request won't block each other and hold a lock on the session
- Horizontally scale your application: because the session data travels
with the request itself you can have multiple web heads without
worrying about session sharing.