The problem seems to be related to a higher number of Points of Presence and fewer requests in North America compared to Europe.
It seems that we're facing a CDN challenge: a competition for cache space. Our files are are pretty big (they take up more cache space than images, for example). Probably, our content isn’t staying in cache because the rate of requests per Point of Presence isn’t high enough in North America to keep it in CloudFront's cache.
Two days ago we switched to a different provider with fewer Points Of Presence in North America. Accumulated statistics for these two days show that our miss-rate now is just 11%. Hence the problem is solved.
It seems that hit-rate/miss-rate proportion doesn't tell the whole story of CDN performance. I configured 4 CDN providers: CloudFront, Google CDN, Fastly, BunnyCDN + included Google Storage into the test. All CDNs were configured to use as many POP servers as possible. Google Storage was in Multi-region mode in US.
Then I configured Uptrends and Pingdom to download a test file every 5 minute. We serve software downloads and that configuration roughly resembles real world load we see - a download request every minute or so from all over the world. Such load make CDNs not so effective because files tend to expire on CDN edge nodes.
Uptrends allowed us to choose test locations and I chose all cities in: North America, Australia, NZ, Germany, France, Spain, Italy, Poland and Russia. Pingdom doesn't allow to change checkpoint locations and provides random locations from Europe and United States. Unfortunately, Pingdom didn't include Australia checkpoints.
Test file was 43 Mb in size. I left tests running on all providers for about 20 hours. Test results are as following:
Average download times - Uptrends (smaller is better):
Download performance - Pingdom (smaller is better):
It's interresting that plain Gloud Storage was faster than Google CDN on both test platform. It may be a misconfiguration on my side, or the fact that Google CDN doesn't keep large files on their nodes for long.
There were download timeouts on Uptrends. Timeout happens when the server cannot download the file for 45 seconds. CloudFront had 2 timeouts, Google Storage had 4, Google CDN had 8 timeouts, BunnyCDN had 6 timeouts, and Fastly had 6 timeouts during 20 hour period.