You could also do a relatively simple solution like tack a two digit shard ID onto the front of your key then use this to direct your request to a specific cluster internally. Give the clusters a lot of RAM and rely on OS filesystem caching to keep frequently requested files in memory. Would be very easy and cheap to build.
-- awl