> Do they just coordinate the heartbeat intervals with the carriers, or do they bypass the Internet altogether and use some cell-network-specific push mechanism?
IIRC they use the xmpp protocol, so standard TCP over IP. In threads about this topic you often hear claims that Google has special deals with carriers. Whether this is true or not, no idea. I haven't seen any confirmation of this. It would be interesting to conduct measurements whether FCM sends less frequent heartbeat messages than the timeout is for "normal" long lived tcp connections.
In any case, deals or not, I guess Google has built a database as I've mentioned. But I'm only guessing here.