Probably does take a lot of compute to recreate the cache, but doing it in order of requests works pretty well as a heuristic for most important first, gradually backfilling when idle. Adding machines to the build infra seems like less of a loss than paying egress fees too.

Overall seems plausible that this data store isn't just a cache of things that can be recreated at will. The sibling comment about source being unavailable (or still available but at a different location) for the earlier builds is interesting in that respect.