Architecture for fast globally distributed user authentication/authorization

We have build a free globally distributed mobility analytics REST API. Meaning we have servers all over the world which run different versions (USA, Europe, etc..) of the same application. The services are behind a load balancer so I can't guarantee that the same user always get's the same application/server if he/she does requests today or tomorrow. The API is public but users have to provide an API key in order for us to match them to their paid request quota.

Since we do heavy number crunching with every request, we want to minimize request times as far as possible, inparticular for authentication/authorization and quota monitoring. Since we currently only use one user database (which has to be located in a single data center) there are cases where users in the US make a request to an application/server in the US which authenticates the user in Europe. So we are looking for a solution where the user database interaction:

1. happens on the same application server
2. get's synchronized between all application servers
3. should be easily integrable into java application
4. should be fast (changes happen in every request)

Things we have done so far:

• a single database on each server > not synchronized, nightmare
• a single database for all servers > ok, when used with slave as fallback but American users have to authenticate over the Atlantic
• started installing bdr but failed on the way (no time, too complex, hard to make transition)
• looked at redis.io

Since this is my first globally distributed REST API I wonder how other companies do this. (yelp, Google, etc.)

Any feedback is very kindly appreciated,

Cheers,

Daniel