laskoviymishka commented on code in PR #1640:
URL: https://github.com/apache/iceberg-go/pull/1640#discussion_r3739108070
##########
catalog/hive/lock_test.go:
##########
@@ -404,3 +404,195 @@ func TestLockConfigurationDefaults(t *testing.T) {
assert.Equal(t, DefaultLockCheckMaxWaitTime, opts.LockMaxWaitTime)
assert.Equal(t, DefaultLockCheckRetries, opts.LockRetries)
}
+
+func TestApplyJitterBelowCapNeverShorterThanInput(t *testing.T) {
+ minWait := time.Millisecond
+ maxWait := time.Minute
+
+ for _, d := range []time.Duration{
+ time.Millisecond,
+ 100 * time.Millisecond,
+ time.Second,
+ } {
+ for i := 0; i < 500; i++ {
+ got := applyJitter(d, minWait, maxWait)
+ assert.GreaterOrEqual(t, got, d,
+ "jitter must never wait less than the
configured interval")
+ assert.LessOrEqual(t, got, min(2*d, maxWait),
+ "jitter must not exceed one extra interval or
the configured maximum")
+ }
+ }
+}
+
+// Once calculateBackoff tops out there is no headroom to add into, so the wait
+// is spread downwards. It must still vary, or every retry after the sequence
+// saturates puts contending clients back in lockstep.
+func TestApplyJitterAtCapStaysWithinBoundsAndVaries(t *testing.T) {
+ minWait := 100 * time.Millisecond
+ maxWait := time.Second
+
+ seen := make(map[time.Duration]struct{})
+ for i := 0; i < 500; i++ {
+ got := applyJitter(maxWait, minWait, maxWait)
+ assert.GreaterOrEqual(t, got, maxWait/2,
+ "the spread at the cap must not exceed one half
interval")
+ assert.LessOrEqual(t, got, maxWait,
+ "the wait must never exceed the configured maximum")
+ seen[got] = struct{}{}
+ }
+
+ assert.Greater(t, len(seen), 1,
+ "waits at the cap must vary so contending clients do not poll
in lockstep")
+}
+
+// The spread at the cap must never poll sooner than a configured minimum wait,
+// which is reachable whenever minWait is more than half of maxWait.
+func TestApplyJitterAtCapNeverPollsSoonerThanMinWait(t *testing.T) {
+ minWait := 40 * time.Second
+ maxWait := time.Minute
+
+ for i := 0; i < 500; i++ {
+ assert.GreaterOrEqual(t, applyJitter(maxWait, minWait,
maxWait), minWait,
+ "a caller who configures a minimum wait must never poll
sooner than it")
+ }
+}
+
+// The guaranteed minimum must not fall as the sequence saturates. The attempt
+// before the cap waits for its own full interval, so flooring the spread at
half
+// the cap would let the first saturated attempt poll sooner than the one
before
+// it, which inverts the property that the wait between checks only ever grows.
+//
+// Reaching the cap takes a lowered lock-check-max-wait-time or a raised retry
+// count; the defaults (100ms, 1 minute, 4 retries) top out at 800ms and never
+// saturate. The values below are the smallest that put the boundary in range.
+func TestApplyJitterMinimumIsMonotonicAcrossTheCap(t *testing.T) {
+ minWait := 100 * time.Millisecond
+ maxWait := time.Second
+
+ // The sequence runs 100ms, 200ms, 400ms, 800ms, then saturates at 1s.
+ // Attempt 3 draws from [800ms, 1s]; attempt 4 is the first capped one.
+ //
+ // The bound compared against is exact, not sampled. Below the cap the
jitter is
+ // added on top, so the interval itself is the floor and no estimate is
needed.
+ // Sampling both sides instead would compare two noisy minima that sit
a hair
+ // above the same true floor, and which of them lands lower is chance.
+ var floor time.Duration
+ for attempt := 0; attempt < 8; attempt++ {
+ d := calculateBackoff(attempt, minWait, maxWait)
+
+ for i := 0; i < 2000; i++ {
+ assert.GreaterOrEqual(t, applyJitter(d, minWait,
maxWait), floor,
+ "attempt %d may not be allowed to wait less
than an earlier attempt", attempt)
+ }
+
+ if d < maxWait {
+ floor = d
+ }
+ }
+}
+
+// The specific boundary above, pinned so a future change to the floor cannot
+// quietly reintroduce the dip without failing on the exact numbers.
+func TestApplyJitterAtCapFloorsAtTheLastUncappedInterval(t *testing.T) {
+ minWait := 100 * time.Millisecond
+ maxWait := time.Second
+
+ assert.Equal(t, 800*time.Millisecond, calculateBackoff(3, minWait,
maxWait),
+ "the last interval before the cap")
+ assert.Equal(t, maxWait, calculateBackoff(4, minWait, maxWait),
+ "the first interval at the cap")
+
+ for i := 0; i < 2000; i++ {
+ assert.GreaterOrEqual(t, applyJitter(maxWait, minWait,
maxWait), 800*time.Millisecond,
Review Comment:
The pinned cases all use clean doubling ratios (100ms to 1s, floor 800ms).
The floor's hard case is a non-power-of-2 ratio where d/2 and the real
last-uncapped interval diverge, e.g. 300ms/1000ms, where the floor must be
600ms, not 500ms. I'd add one such case here; that's where the replay loop
earns its keep and the only spot the arithmetic could quietly go wrong.
##########
catalog/hive/lock_test.go:
##########
@@ -404,3 +404,195 @@ func TestLockConfigurationDefaults(t *testing.T) {
assert.Equal(t, DefaultLockCheckMaxWaitTime, opts.LockMaxWaitTime)
assert.Equal(t, DefaultLockCheckRetries, opts.LockRetries)
}
+
+func TestApplyJitterBelowCapNeverShorterThanInput(t *testing.T) {
+ minWait := time.Millisecond
+ maxWait := time.Minute
+
+ for _, d := range []time.Duration{
+ time.Millisecond,
+ 100 * time.Millisecond,
+ time.Second,
+ } {
+ for i := 0; i < 500; i++ {
+ got := applyJitter(d, minWait, maxWait)
+ assert.GreaterOrEqual(t, got, d,
+ "jitter must never wait less than the
configured interval")
+ assert.LessOrEqual(t, got, min(2*d, maxWait),
+ "jitter must not exceed one extra interval or
the configured maximum")
+ }
+ }
+}
+
+// Once calculateBackoff tops out there is no headroom to add into, so the wait
+// is spread downwards. It must still vary, or every retry after the sequence
+// saturates puts contending clients back in lockstep.
+func TestApplyJitterAtCapStaysWithinBoundsAndVaries(t *testing.T) {
+ minWait := 100 * time.Millisecond
+ maxWait := time.Second
+
+ seen := make(map[time.Duration]struct{})
+ for i := 0; i < 500; i++ {
+ got := applyJitter(maxWait, minWait, maxWait)
+ assert.GreaterOrEqual(t, got, maxWait/2,
Review Comment:
This lower bound is looser than the code actually guarantees. The floor at
the cap is 800ms (the last uncapped interval), but this only asserts >= 500ms,
so a regression letting the spread dip to 600-700ms would pass here.
TestApplyJitterAtCapFloorsAtTheLastUncappedInterval does pin the real 800ms, so
we're covered, but this assertion reads stronger than it is. I'd tighten it to
800ms so the two agree.
Separately, the message ("must not exceed one half interval") is upper-bound
wording on a GreaterOrEqual check. I'd flip it to something like "must be at
least half of maxWait" so a failure dump isn't confusing.
##########
catalog/hive/lock.go:
##########
@@ -160,6 +165,62 @@ func calculateBackoff(attempt int, minWait, maxWait
time.Duration) time.Duration
return minWait << attempt
}
+// applyJitter spreads a backoff interval so clients contending for the same
lock
+// stop re-polling in lockstep. calculateBackoff is a pure function of the
attempt
+// and the configured bounds, and contention is the precondition for retrying
at
+// all, so without this every waiter issues its CheckLock calls at the same
instants
+// and each round reaches the metastore as a burst.
+//
+// The invariants, in the order the code establishes them:
+// - below the cap the jitter is added rather than centred, so the wait is
never
+// shorter than the interval calculateBackoff produced;
+// - at the cap there is no headroom left to add into, so the wait is spread
+// downward instead, floored at the last interval the sequence produced
before
+// it saturated — a bound the schedule has already cleared, which stops a
later
+// attempt from being allowed to wait less than an earlier one;
+// - the result never exceeds maxWait and never falls below minWait.
Review Comment:
This last bullet isn't quite true when minWait > maxWait. calculateBackoff
resolves that config to maxWait, and applyJitter returns maxWait too, so the
result sits below minWait. TestApplyJitterHonoursMinWaitAboveMaxWait actually
pins exactly that (got == maxWait with minWait=90s, maxWait=60s).
I'd qualify it: never below minWait when minWait <= maxWait, otherwise
exactly maxWait.
##########
catalog/hive/lock.go:
##########
@@ -160,6 +165,62 @@ func calculateBackoff(attempt int, minWait, maxWait
time.Duration) time.Duration
return minWait << attempt
}
+// applyJitter spreads a backoff interval so clients contending for the same
lock
+// stop re-polling in lockstep. calculateBackoff is a pure function of the
attempt
+// and the configured bounds, and contention is the precondition for retrying
at
+// all, so without this every waiter issues its CheckLock calls at the same
instants
+// and each round reaches the metastore as a burst.
+//
+// The invariants, in the order the code establishes them:
+// - below the cap the jitter is added rather than centred, so the wait is
never
+// shorter than the interval calculateBackoff produced;
+// - at the cap there is no headroom left to add into, so the wait is spread
+// downward instead, floored at the last interval the sequence produced
before
+// it saturated — a bound the schedule has already cleared, which stops a
later
+// attempt from being allowed to wait less than an earlier one;
+// - the result never exceeds maxWait and never falls below minWait.
+func applyJitter(d, minWait, maxWait time.Duration) time.Duration {
+ if d <= 0 {
+ return d
+ }
+
+ // A caller that hands in an interval already past the cap is outside
the
+ // contract; leave it exactly as given rather than silently reshaping
it.
+ headroom := maxWait - d
+ if headroom < 0 {
+ return d
+ }
+
+ // Add up to another full interval, without exceeding the configured
maximum.
+ extra := d
+ if headroom < extra {
+ extra = headroom
+ }
+ if extra > 0 {
+ return d + time.Duration(rand.Int64N(int64(extra)+1))
+ }
+
+ // Replay the doubling sequence and keep the largest interval that
still fitted
+ // under the cap. The guard on scheduled keeps a non-positive or
overflowing
+ // minWait from spinning here.
+ //
+ // minWait is applied before the replay rather than relying on it. When
minWait
+ // is itself >= maxWait the loop cannot run at all, and options.go
accepts that
+ // configuration, so leaving the floor at d/2 there would allow a wait
of a third
+ // of the configured minimum.
+ floor := max(minWait, d/2)
+ for scheduled := minWait; scheduled > 0 && scheduled < maxWait;
scheduled <<= 1 {
+ if scheduled > floor {
+ floor = scheduled
+ }
Review Comment:
This downward-spread branch only runs once the sequence saturates at
maxWait, and under the defaults (100ms/60s/4 retries) we top out at 800ms and
never get there, so the replay loop is effectively dead code in a default
deployment. It's also the most intricate part of the helper, and I'm a little
uneasy about the most fragile code being the least exercised in practice.
Is the strict monotonicity across the cap worth it? A flat max(minWait, d/2)
floor drops the loop entirely, at the cost of letting the first capped attempt
dip slightly below the last uncapped one. If we do keep the loop, I'd at least
note plainly that it's only reachable under non-default config. Thoughts?
##########
catalog/hive/lock_test.go:
##########
@@ -404,3 +404,195 @@ func TestLockConfigurationDefaults(t *testing.T) {
assert.Equal(t, DefaultLockCheckMaxWaitTime, opts.LockMaxWaitTime)
assert.Equal(t, DefaultLockCheckRetries, opts.LockRetries)
}
+
+func TestApplyJitterBelowCapNeverShorterThanInput(t *testing.T) {
+ minWait := time.Millisecond
+ maxWait := time.Minute
+
+ for _, d := range []time.Duration{
+ time.Millisecond,
+ 100 * time.Millisecond,
+ time.Second,
+ } {
+ for i := 0; i < 500; i++ {
+ got := applyJitter(d, minWait, maxWait)
+ assert.GreaterOrEqual(t, got, d,
+ "jitter must never wait less than the
configured interval")
+ assert.LessOrEqual(t, got, min(2*d, maxWait),
+ "jitter must not exceed one extra interval or
the configured maximum")
+ }
+ }
+}
+
+// Once calculateBackoff tops out there is no headroom to add into, so the wait
+// is spread downwards. It must still vary, or every retry after the sequence
+// saturates puts contending clients back in lockstep.
+func TestApplyJitterAtCapStaysWithinBoundsAndVaries(t *testing.T) {
+ minWait := 100 * time.Millisecond
+ maxWait := time.Second
+
+ seen := make(map[time.Duration]struct{})
+ for i := 0; i < 500; i++ {
+ got := applyJitter(maxWait, minWait, maxWait)
+ assert.GreaterOrEqual(t, got, maxWait/2,
+ "the spread at the cap must not exceed one half
interval")
+ assert.LessOrEqual(t, got, maxWait,
+ "the wait must never exceed the configured maximum")
+ seen[got] = struct{}{}
+ }
+
+ assert.Greater(t, len(seen), 1,
+ "waits at the cap must vary so contending clients do not poll
in lockstep")
+}
+
+// The spread at the cap must never poll sooner than a configured minimum wait,
+// which is reachable whenever minWait is more than half of maxWait.
+func TestApplyJitterAtCapNeverPollsSoonerThanMinWait(t *testing.T) {
+ minWait := 40 * time.Second
+ maxWait := time.Minute
+
+ for i := 0; i < 500; i++ {
+ assert.GreaterOrEqual(t, applyJitter(maxWait, minWait,
maxWait), minWait,
+ "a caller who configures a minimum wait must never poll
sooner than it")
+ }
+}
+
+// The guaranteed minimum must not fall as the sequence saturates. The attempt
+// before the cap waits for its own full interval, so flooring the spread at
half
+// the cap would let the first saturated attempt poll sooner than the one
before
+// it, which inverts the property that the wait between checks only ever grows.
+//
+// Reaching the cap takes a lowered lock-check-max-wait-time or a raised retry
+// count; the defaults (100ms, 1 minute, 4 retries) top out at 800ms and never
+// saturate. The values below are the smallest that put the boundary in range.
+func TestApplyJitterMinimumIsMonotonicAcrossTheCap(t *testing.T) {
+ minWait := 100 * time.Millisecond
+ maxWait := time.Second
+
+ // The sequence runs 100ms, 200ms, 400ms, 800ms, then saturates at 1s.
+ // Attempt 3 draws from [800ms, 1s]; attempt 4 is the first capped one.
+ //
+ // The bound compared against is exact, not sampled. Below the cap the
jitter is
+ // added on top, so the interval itself is the floor and no estimate is
needed.
+ // Sampling both sides instead would compare two noisy minima that sit
a hair
+ // above the same true floor, and which of them lands lower is chance.
+ var floor time.Duration
+ for attempt := 0; attempt < 8; attempt++ {
+ d := calculateBackoff(attempt, minWait, maxWait)
+
+ for i := 0; i < 2000; i++ {
+ assert.GreaterOrEqual(t, applyJitter(d, minWait,
maxWait), floor,
+ "attempt %d may not be allowed to wait less
than an earlier attempt", attempt)
+ }
+
+ if d < maxWait {
+ floor = d
+ }
+ }
+}
+
+// The specific boundary above, pinned so a future change to the floor cannot
+// quietly reintroduce the dip without failing on the exact numbers.
+func TestApplyJitterAtCapFloorsAtTheLastUncappedInterval(t *testing.T) {
+ minWait := 100 * time.Millisecond
+ maxWait := time.Second
+
+ assert.Equal(t, 800*time.Millisecond, calculateBackoff(3, minWait,
maxWait),
+ "the last interval before the cap")
+ assert.Equal(t, maxWait, calculateBackoff(4, minWait, maxWait),
+ "the first interval at the cap")
+
+ for i := 0; i < 2000; i++ {
+ assert.GreaterOrEqual(t, applyJitter(maxWait, minWait,
maxWait), 800*time.Millisecond,
+ "the spread at the cap must not reach below the last
uncapped interval")
+ }
+}
+
+// A caller may configure minWait above maxWait; options.go accepts it, and
+// calculateBackoff resolves it by returning maxWait. The downward spread must
not
+// then draw below the configured minimum. Flooring at half the interval would
+// permit a third of it, because the replay loop cannot run when minWait is
already
+// past the cap.
+func TestApplyJitterHonoursMinWaitAboveMaxWait(t *testing.T) {
+ minWait := 90 * time.Second
+ maxWait := 60 * time.Second
+
+ d := calculateBackoff(0, minWait, maxWait)
+ require.Equal(t, maxWait, d, "calculateBackoff resolves this
configuration to the cap")
+
+ for i := 0; i < 2000; i++ {
+ got := applyJitter(d, minWait, maxWait)
+ assert.Equal(t, maxWait, got,
+ "with minWait past the cap the wait cannot be spread at
all without breaking it")
+ }
+}
+
+// Exercises the wiring at the acquireLocks call site rather than the helper
alone,
+// and pins the aggregate delay. The schedule is 10ms, 20ms, 40ms, 80ms, and
each
+// draw adds up to one further interval, so the total falls in [150ms, 300ms].
Only
+// the lower bound is asserted tightly; the ceiling is loose because a busy CI
box
+// can add arbitrary scheduling delay on top, and a flaky timing test is worse
than
+// no timing test.
+func TestAcquireLocksAggregateRetryDelayStaysWithinBound(t *testing.T) {
+ mockClient := new(mockHiveClient)
+ ctx := context.Background()
+ opts := NewHiveOptions()
+ opts.LockMinWaitTime = 10 * time.Millisecond
+ opts.LockMaxWaitTime = time.Second
+ opts.LockRetries = 4
+
+ mockClient.On("Lock", ctx,
mock.AnythingOfType("*hive_metastore.LockRequest")).
+ Return(&hive_metastore.LockResponse{
+ Lockid: 901,
+ State: hive_metastore.LockState_WAITING,
+ }, nil)
+ mockClient.On("CheckLock", ctx, int64(901)).
+ Return(&hive_metastore.LockResponse{
+ Lockid: 901,
+ State: hive_metastore.LockState_WAITING,
+ }, nil)
+ mockClient.On("Unlock", mock.Anything, int64(901)).Return(nil)
+
+ start := time.Now()
+ lock, err := acquireLocks(ctx, mockClient,
+ []tableLockIdentifier{{database: "testdb", table:
"testtable"}}, opts)
+ elapsed := time.Since(start)
+
+ require.Error(t, err)
+ require.Nil(t, lock)
+ assert.ErrorIs(t, err, ErrLockAcquisitionFailed)
+
+ assert.GreaterOrEqual(t, elapsed, 150*time.Millisecond,
Review Comment:
This asserts real elapsed wall-clock time, so on a busy CI box the >= 150ms
lower bound can flake, and the test sleeps for real every run. The additive
never-shorter property is already covered by
TestApplyJitterBelowCapNeverShorterThanInput without touching the clock.
I'd drop the timing assertions and keep this as a wiring check that's
count-based (assert CheckLock was called exactly 4 times) so we exercise the
call site without the clock dependency.
##########
catalog/hive/lock.go:
##########
@@ -160,6 +165,62 @@ func calculateBackoff(attempt int, minWait, maxWait
time.Duration) time.Duration
return minWait << attempt
}
+// applyJitter spreads a backoff interval so clients contending for the same
lock
+// stop re-polling in lockstep. calculateBackoff is a pure function of the
attempt
+// and the configured bounds, and contention is the precondition for retrying
at
+// all, so without this every waiter issues its CheckLock calls at the same
instants
+// and each round reaches the metastore as a burst.
+//
+// The invariants, in the order the code establishes them:
+// - below the cap the jitter is added rather than centred, so the wait is
never
+// shorter than the interval calculateBackoff produced;
+// - at the cap there is no headroom left to add into, so the wait is spread
+// downward instead, floored at the last interval the sequence produced
before
+// it saturated — a bound the schedule has already cleared, which stops a
later
+// attempt from being allowed to wait less than an earlier one;
+// - the result never exceeds maxWait and never falls below minWait.
+func applyJitter(d, minWait, maxWait time.Duration) time.Duration {
+ if d <= 0 {
+ return d
+ }
+
+ // A caller that hands in an interval already past the cap is outside
the
+ // contract; leave it exactly as given rather than silently reshaping
it.
+ headroom := maxWait - d
+ if headroom < 0 {
+ return d
+ }
+
+ // Add up to another full interval, without exceeding the configured
maximum.
+ extra := d
+ if headroom < extra {
+ extra = headroom
+ }
+ if extra > 0 {
+ return d + time.Duration(rand.Int64N(int64(extra)+1))
Review Comment:
Adding up to a full interval here gives us [d, 2d] below the cap. Java's
Tasks.exponentialBackoff only jitters by ~10% of the current delay, so a mixed
Java/Go fleet hitting the same HMS will spread quite differently, with Go
clients sitting in a window twice as wide.
I'm fine with the wider spread if it's deliberate, I'd just call the
divergence out in the doc comment so the next person doesn't assume we're
matching Java. wdyt?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
