GCP's Firestore uses the same technology as Cloud Spanner to ensure consistency at scale. To learn more about Cloud Spanner and its CAP implications take a look at the introduction here:
In terms of CAP, Spanner claims to be both consistent and highly available despite operating over a wide area [...]. Does this mean that Spanner is a CA system as defined by CAP? [...] The purist answer is “no” because partitions can happen and in fact have happened at Google, and during some partitions, Spanner chooses C and forfeits A. It is technically a CP system. However, no system provides 100% availability, so the pragmatic question is whether or not Spanner delivers availability that is so high that most users don't worry about its outages.
Hence, while technically a CP system, Cloud Spanner (and thus also Firestore) is effectively CAP, as its "5 or more nines" availability guarantee is high enough for most users to ignore outages.
How do systems like Firestore provide high-availability while also providing consistency?
First, Google runs its own private global network for services like these, which means they're able to provide much stronger guarantees as opposed to relying on public networks.
Second, these systems utilize synchronized clocks to ensure consistency. In Google's case that boils down to TrueTime, a globally synchronized, GPS and atomic-clock based clock that provides strong time semantics (bounded uncertainty of 7ms) even for transactions happening on the opposite sides of the globe. Clocks make it possible to replace communication with local computation: instead of node N asking another node M whether some property holds, it can deduce the answer based on some information about M from the past together with the current time on N's clock (Liskov91).
Cloud Spanner depends on TrueTime to generate monotonically increasing timestamps. Cloud Spanner uses these timestamps in two ways. First, it uses them as proper timestamps for write transactions without the need for global communication. Second, it uses them as timestamps for strong reads, which enables strong reads to execute in one round of communication, even strong reads that span multiple servers. source
For further theory on how clocks help distributed system design, see Liskov's paper here. For more on Cloud Spanner, I highly recommend these summaries on the original Spanner paper as well as the follow-up paper.
Update: The good news is that you don't need atomic clocks, GPS and private global networks to ensure consistency and high availability. The open-source Spanner-inspired CockroachDB achieves much the same as its predecessor, although in lieu of TrueTime's strong time certainty it has to rely on more coarse-grained and less efficient synchronization as outlined in this fantastic comparison:
A simple statement of the contrast between Spanner and CockroachDB would be: Spanner always waits on writes for a short interval, whereas CockroachDB sometimes waits on reads for a longer interval.
