Not at Google, but making reliable tests was one thing I really struggled with professionally. There are many, many possible causes of non-determinism. Even something as simple as using multiple threads means that you suddenly realize that you must decide how long you're willing to wait for the other thread to complete. (You always kind of did, but when all the logic was on one thread, the waiting was not as obvious and errors were less likely to cause hangups.)

Unfortunately, under high load, I found that threads can be starved of CPU for seconds at a time. The CI machine was flooring it trying to build the software and run the tests. Setting the timeout high enough that there were no random failures caused by CPU starvation meant that build failures would take a very long time, delaying feedback for errors. That was nearly as bad as the flakiness.

I mostly fixed the flakiness by making the number of threads configurable and only running one thread in the testing environment, but I think a better way would be to reduce the number of parallel jobs to keep the test machines' CPU utilization rate at something more reasonable. Then, you can set timeouts that reflect real performance expectations for your software.