One trick to problems like this is to solve it differently for celebrities, head queries, etc., than for less commonly accessed data. Essentially have two different systems and combine the data because designing a single system that meets both scale requirements is harder.