Authentication Techniques

Our application is web service application with REST protocol. My question is about authentication of the caller to provide data requested by the REST API call.

Even for Oauth, we need to hit data store for every request.

Problem with sessions: the request may land on any server. We can't keep millions of sessions in a server.  In order to make the load balancer handle the load, we chose a light weight load balancer. It won't do Session based load balancing. Even if we replace it with a different one , it may not be a scalable solution.  Even in these days is using in-memory sessions still the only viable solution? Are there more scalable solutions available now?

Is replacing ldap server with a nosql datastore provide more scalable solution?  Is  some sort of external caching like memcache or ecache a common practice for handling identity information?

I understand checking permissions, but why every trasnaction... if they are only typing in their username and password, once, why check LDAP for each request? Why aren't you using session information, cookies? If' your trying to do RBAC you are hitting LDAP when you should be hitting database tables instead. Permissions and authentication can be done in a variety of ways, hitting ldap over and over would naturally become a bottleneck, so would any authentication service if you hit it that much.
Your load balancer's take care of the session data typically after the session is established with a server. The load balancers should be distributing, not your application.
http://docwiki.cisco.com/wiki/Session_Persistence_Using_Cookie_Learning_on_the_Cisco_Application_Control_Engine_Configuration_Example
https://devcentral.f5.com/articles/back-to-basics-the-many-faces-of-load-balancing-persistence
-rich

You have to budget for site responsiveness, if you can't create (or afford)the infrastructure, you may be a candidate for the "cloud" as the kids call it. It's still just hosting if you ask me, but it's hosting that is supposed to scale. If you can't afford to convert totally to some "cloud" service, maybe you can do it with the bottleneck portion of your site. But if your LB's aren't a priority, even a cheap one should be able to do session data handling. http://www.zenloadbalancer.com/
http://www.inlab.de/articles/free-and-open-source-load-balancing-software-and-projects.html
-rich

load balancer (LB) is "no more", you are looking at application delivery controller (ADC) - they started off as LB and still have that capability to handle session and persistence binding to server if need. the question is indeed to review the architecture from tier perspective and instance for the ...

web front processing - can more be done at the client end instead of the server end to eliminate strain at backend? the ADC to front most transaction and session handling with caching for repeated req? Consider web accelerator (content distribution n/w, or on-premise appliance)? authentication and authz can still be fronted by ADC too such as access policy managed for context and content aware, even with web portal and VPN access etc, it handle the AAA directing too..

You can move on to appl and DB tier as well but they are can be more restrictive if co-located and shared among other web apps, so most offloading at web front is preferred.

Eventually no matter what auth scheme you choose, the backend auth server will still be hit. Experience is that thses are central infra architecture handling and upgrade as scale up is needed if demand really go high. Hence ppl even talks about scale out (resource/reach) on top of scale up (perf/throughput). Hence the cloud broker and gateway comes in to engage worker cloud instance to handle and reduce hit...and also why identity federation are part and parcel as the auth is with the internal AD...

It's typically free to get in some calls to Load Balancer sales Rep's and even get POC's if they think you'll spend the money in the end. Call F5|BigIP/Cisco/Radware/RiverBed and look into other makers, even FOSS.
-rich

I thank every one for the responses.
@richrumble, we are already in cloud.  That simply doesn't solve the problem. We need to have architecture to distribute the load. We are looking for an architecture to distribute the authentication load and reduce the authentication load to avoid unnecessary cost

@btan
I agree with you.
the solutions you are mentioning are
1. session implementation
2. caching of repeated requests
3. Distributed Db dedicated for the authentication mechanism
4. Scale up
5. scale out.

we were also  thinking along these lines. I am trying to see if any other solutions are in practice.
#5 is the problem with the LDAP we have currently. so the alternatives are
either go with nosql or use something like this:
http://ldapcon.org/2011/downloads/hummel-slides.pdf

I don't know enough about your site/product/network, but the loadbalancers should do the session data after one is established, I can't think of a case where you'd want your app to distribute or figure out distribution, especially if all things are equal (multiple servers with the exact same data). If updating the DB is an issue, then transactions and replication are the issue, which may be why your looking to noSQL as a problem solver. I think you may want to hire someone to consult on the issue and how your product functions. LDAP is a one time hit per session, per user, after that the user should have a cookie, ID or something that keeps them alive for the next transaction, even if it's not on the same server. That session/cookie/id should correspond or reference to an ACL on the database, not LDAP DB, but your tables/rows/columns. Your permissions should be set there, not checked by ldap over and over... again I'm assuming, it's not been laid out how things are working, just that LDAP is bottleneck.
I've seen websites built on Hadoop, Sharepoint, Durpal, MySQL and some very large M$SQL, and ever since LB's came on the scene, I've seen very few if any these days not using one for the session/keepalive. It's entirely possible to have a use-case where you don't want that, I personally have no experience with that however.
-rich