> Obviously failing first requests isn't ideal but for popular requests it quickly becomes insignificant.

The first request can also be called asynchronously, and display a message to the user that it is 'processing....'.