Were it be a small company, we would try sharding salts + increasing the number of rounds of scrypt or some mix with a bloom filter. However, this is facebook.

Were it be a small company, we would try sharding salts + increasing the number of rounds of scrypt or some mix with a bloom filter. However, this is facebook. It's not too expensive for them.