Understand that Google is continuously rewriting their infrastructure to handle increased scale. That's what they have 25k employees for.

Jeff Dean's rule of thumb is that you should build a growth factor of 10 into the design, but any more than that and you will probably have to re-architect anyway. So going from 10,000 to 1 million and 1 million to 100 million are probably roughly equivalent in difficulty.