I have spent quite a few days reading up on Oauth and token based security measures for REST API's and I am currently looking at implementing an Oauth based authentication approach almost exactly like the one described in this post (OAuth alternative for a 2 party system).

From what I understand, the token is to be verified upon each request to the resource server. This means the resource server would need to retrieve the token from a datastore to verify the clients token. Given this would have to happen upon every request I am concerned about the speed implications of hitting a datastore like MySQL or NoSQL upon every request just to verify the token.

Is this the standard way to verify tokens by having them stored in a RDBMS or NoSQL database and retrieved upon each request? Or is it a suitable solution to have them cached (baring in mind that we are talking millions of users)?