Support publish hedging in pubsub::client::Publisher

[suzmue]

Support publish request hedging in google-cloud-pubsub to reduce p99/p99.9 tail latency caused by transient network stalls or slow backend tasks.

Design

• Hedging Mechanism: When an in-flight batch publish exceeds a configured delay threshold, send a concurrent duplicate publish RPC and resolve the batch with whichever attempt finishes first.
• Rate Limiting: Rate-limit hedged RPCs using a token bucket that refills on successful publish RPCs.
• Telemetry: Attach the x-goog-pubsub-client-telemetry header to hedged attempts for backend tracking.
• Ordering Safety: Hedging does not apply for messages with ordering keys.

See java reference implementation: https://github.com/googleapis/google-cloud-java/pull/13735/changes

[suzmue]

During implementation, I evaluated an alternative design that integrated hedging directly into the existing batch worker rather than using a dedicated background queue (which is used in the Java and Go implementations).

While that alternative fits more cleanly into the existing publisher architecture, benchmark testing revealed noticeable differences in hedging performance and tail-latency mitigation. Not necessarily worse overall but worse for certain percentiles (though also better for others). Because of this difference, I plan to proceed with implementing the queue design.

[coryan]

While that alternative fits more cleanly into the existing publisher architecture, benchmark testing revealed noticeable differences in hedging performance and tail-latency mitigation. Not necessarily worse overall but worse for certain percentiles (though also better for others).

nit (optional): there math-y are ways to compare distributions: as I recall, "stochastic dominance" is the magic thing to search for. Basically you are trying to ask "By blind luck, how often would I get a better outcome on distribution A vs. distribution B".