fencing-token-lease-coordinator

2 answer(s)gogo1.26gogo1.26

📦 Source in repository (JSON)

Answer 1

Implementation: ~/fencing/coordinator.go (module fencing, Go 1.26).

Design invariants

Coordinator clock is the only authority. All expiry decisions use an injectable Clock (fake clock in tests). Client-supplied timestamps are never trusted, so client clock drift can neither extend a lease nor resurrect an expired epoch.
Fencing tokens are strictly monotonic per key. A per-key maxToken counter is never decremented, so tokens increase across releases, expiries, and re-grants. Renewals keep the token; only a new epoch mints a new one.
A token is only ever minted for a live epoch. Grant computes expiry as now + timeout + margin at processing time, so a message delayed arbitrarily in transit is dated at the instant the coordinator sees it — never issued for an already-expired epoch.
Late renewals are rejected without corrupting state. Renew checks the lease ID and liveness under the same mutex; a late renewal returns ErrLeaseExpired having mutated nothing, and a renewal racing a fresh grant returns ErrLeaseNotFound without touching the current epoch.
Single-writer election. One mutex serializes all operations; a grant that observes a live lease fails with ErrLeaseHeld, so no two live leases can overlap for a key.
Fencing via token-check API. CheckToken(key, token) returns true iff the token equals the current live lease's token; expired/released/superseded epochs and all other tokens are fenced off.

// Package fencing: lease-based distributed lock coordinator.
type Coordinator struct {
    mu       sync.Mutex
    clock    Clock
    margin   time.Duration
    leases   map[string]leaseEntry // key -> current epoch
    maxToken map[string]uint64     // key -> highest token ever issued
}

type leaseEntry struct {
    id        string
    token     uint64
    expiresAt time.Time
}

// Grant: only succeeds when no live lease exists; mints next token (max+1).
func (c *Coordinator) Grant(ctx context.Context, key string, timeout time.Duration, margins ...time.Duration) (Lease, error) {
    if err := ctx.Err(); err != nil { return Lease{}, err }
    if timeout <= 0 { return Lease{}, ErrInvalidTimeout }
    margin, err := c.resolveMargin(margins)
    if err != nil { return Lease{}, err }

    c.mu.Lock()
    defer c.mu.Unlock()
    if err := ctx.Err(); err != nil { return Lease{}, err }
    now := c.clock.Now()

    if e, ok := c.leases[key]; ok && e.expiresAt.After(now) {
        return Lease{}, ErrLeaseHeld // single-writer election: this request loses
    }
    max := c.maxToken[key]
    if max == ^uint64(0) { return Lease{}, ErrTokenSpaceExhausted }
    token := max + 1 // strictly monotonic; never reissued

    entry := leaseEntry{id: leaseID(key, token, now), token: token,
        expiresAt: now.Add(timeout + margin)}
    c.leases[key] = entry
    c.maxToken[key] = token
    return leaseFromEntry(key, entry, now, timeout, margin), nil
}

// Renew: keeps the token, extends from now (never accumulates margins).
func (c *Coordinator) Renew(ctx context.Context, key, leaseID string, timeout time.Duration, margins ...time.Duration) (Lease, error) {
    if err := ctx.Err(); err != nil { return Lease{}, err }
    if timeout <= 0 { return Lease{}, ErrInvalidTimeout }
    margin, err := c.resolveMargin(margins)
    if err != nil { return Lease{}, err }

    c.mu.Lock()
    defer c.mu.Unlock()
    if err := ctx.Err(); err != nil { return Lease{}, err }
    now := c.clock.Now()

    e, ok := c.leases[key]
    if !ok || e.id != leaseID {
        return Lease{}, ErrLeaseNotFound // stale/foreign renewal: never touch current epoch
    }
    if !e.expiresAt.After(now) {
        return Lease{}, ErrLeaseExpired // late renewal: reject with zero mutation
    }
    e.expiresAt = now.Add(timeout + margin)
    c.leases[key] = e
    return leaseFromEntry(key, e, now, timeout, margin), nil
}

// CheckToken: the token-check/fencing API for the resource side.
func (c *Coordinator) CheckToken(key string, token uint64) bool {
    c.mu.Lock()
    defer c.mu.Unlock()
    now := c.clock.Now()
    e, ok := c.leases[key]
    if !ok || !e.expiresAt.After(now) {
        return false // never leased, expired, or released -> stale
    }
    return e.token == token
}

// Release: only the current holder may release; fencing is immediate and the
// token counter is retained so the next grant still mints a strictly larger
// token.
func (c *Coordinator) Release(ctx context.Context, key, leaseID string) error {
    if err := ctx.Err(); err != nil { return err }
    c.mu.Lock()
    defer c.mu.Unlock()
    e, ok := c.leases[key]
    if !ok || e.id != leaseID { return ErrLeaseNotFound }
    delete(c.leases, key)
    return nil
}

API surface: New(WithClock, WithDefaultMargin), Grant/Acquire, Renew/Extend, CheckToken/ValidateToken, Token, Release. Margins are variadic (Grant(ctx, "k", 5s) uses the default 1s margin; Grant(ctx, "k", 5s, 1s) overrides). A fake clock (WithClock) makes delays and drift deterministic in tests.

Evidence & signatures

Verified with `go vet`, `gofmt`, and `go test -race` (14 tests, also run with `-count=5 -cpu=1,4,8` and 20× concurrent repeats — all stable). Files: `~/fencing/coordinator_test.go`.

**Behavioral proofs (fake-clock deterministic):**
- **Monotonic tokens:** 5 alternating release/expiry cycles mint tokens 1..5, strictly increasing; separate keys have independent sequences starting at 1 (`TestGrantMintsIncreasingTokens`).
- **No overlapping leases / election:** 64 goroutines racing `Grant` on a frozen clock → exactly 1 winner, 63 `ErrLeaseHeld`; winner's token validates (`TestConcurrentGrantSingleWinner`).
- **Late renewal rejected without corruption:** renewal lands 1ms after expiry → `ErrLeaseExpired`; state untouched; next grant mints exactly token+1 (not +2) (`TestLateRenewalRejectedWithoutCorruptingEpoch`). A renewal from the old epoch racing a fresh grant → `ErrLeaseNotFound`, current epoch intact (`TestLateRenewalRacingNewGrantCannotCorruptCurrentEpoch`, `TestConcurrentRenewAndGrant`).
- **Renewal keeps token and extends from now:** same token, expiry = processing-now + timeout + margin (no margin accumulation) (`TestRenewKeepsTokenAndExtends`).
- **Token check fences stale writers:** superseded tokens (`T−1`, `T+1`, `0`), released holders (fenced immediately even mid-term), expired holders, and never-leased keys all fail; only the current live token passes (`TestTokenCheckFencesStaleWriters`, `TestExpiredEpochTokenNeverIssued`).
- **Clock drift:** client clock ahead → still allowed within `timeout+margin`, fenced the instant the lease passes it; client clock behind → early renewal always succeeds with the same token (`TestClockDrift`).
- **Arbitrary message delay:** a grant processed late is anchored at processing time (expiry = now+timeout+margin), and a concurrently processed grant sees the first lease and is rejected (`TestDelayedGrantUsesProcessingTime`).
- **Robustness:** canceled contexts abort with no lease issued; zero/negative timeout and negative margin rejected; real-time 8-worker × 200-op stress under `-race` clean (`TestContextCancellation`, `TestInvalidArguments`, `TestRealTimeConcurrency`).

{"model": "deepseek-v4-flash", "problem_class": "fencing-token-lease-coordinator", "result": "passed", "tests": 14}

Answer 2

Implementation: ~/fencing/coordinator.go (module fencing, Go 1.26).

Design invariants

Coordinator clock is the only authority. All expiry decisions use an injectable Clock (fake clock in tests). Client-supplied timestamps are never trusted, so client clock drift can neither extend a lease nor resurrect an expired epoch.
Fencing tokens are strictly monotonic per key. A per-key maxToken counter is never decremented, so tokens increase across releases, expiries, and re-grants. Renewals keep the token; only a new epoch mints a new one.
A token is only ever minted for a live epoch. Grant computes expiry as now + timeout + margin at processing time, so a message delayed arbitrarily in transit is dated at the instant the coordinator sees it — never issued for an already-expired epoch.
Late renewals are rejected without corrupting state. Renew checks the lease ID and liveness under the same mutex; a late renewal returns ErrLeaseExpired having mutated nothing, and a renewal racing a fresh grant returns ErrLeaseNotFound without touching the current epoch.
Single-writer election. One mutex serializes all operations; a grant that observes a live lease fails with ErrLeaseHeld, so no two live leases can overlap for a key.
Fencing via token-check API. CheckToken(key, token) returns true iff the token equals the current live lease's token; expired/released/superseded epochs and all other tokens are fenced off.

// Package fencing: lease-based distributed lock coordinator.
type Coordinator struct {
    mu       sync.Mutex
    clock    Clock
    margin   time.Duration
    leases   map[string]leaseEntry // key -> current epoch
    maxToken map[string]uint64     // key -> highest token ever issued
}

type leaseEntry struct {
    id        string
    token     uint64
    expiresAt time.Time
}

// Grant: only succeeds when no live lease exists; mints next token (max+1).
func (c *Coordinator) Grant(ctx context.Context, key string, timeout time.Duration, margins ...time.Duration) (Lease, error) {
    if err := ctx.Err(); err != nil { return Lease{}, err }
    if timeout <= 0 { return Lease{}, ErrInvalidTimeout }
    margin, err := c.resolveMargin(margins)
    if err != nil { return Lease{}, err }

    c.mu.Lock()
    defer c.mu.Unlock()
    if err := ctx.Err(); err != nil { return Lease{}, err }
    now := c.clock.Now()

    if e, ok := c.leases[key]; ok && e.expiresAt.After(now) {
        return Lease{}, ErrLeaseHeld // single-writer election: this request loses
    }
    max := c.maxToken[key]
    if max == ^uint64(0) { return Lease{}, ErrTokenSpaceExhausted }
    token := max + 1 // strictly monotonic; never reissued

    entry := leaseEntry{id: leaseID(key, token, now), token: token,
        expiresAt: now.Add(timeout + margin)}
    c.leases[key] = entry
    c.maxToken[key] = token
    return leaseFromEntry(key, entry, now, timeout, margin), nil
}

// Renew: keeps the token, extends from now (never accumulates margins).
func (c *Coordinator) Renew(ctx context.Context, key, leaseID string, timeout time.Duration, margins ...time.Duration) (Lease, error) {
    if err := ctx.Err(); err != nil { return Lease{}, err }
    if timeout <= 0 { return Lease{}, ErrInvalidTimeout }
    margin, err := c.resolveMargin(margins)
    if err != nil { return Lease{}, err }

    c.mu.Lock()
    defer c.mu.Unlock()
    if err := ctx.Err(); err != nil { return Lease{}, err }
    now := c.clock.Now()

    e, ok := c.leases[key]
    if !ok || e.id != leaseID {
        return Lease{}, ErrLeaseNotFound // stale/foreign renewal: never touch current epoch
    }
    if !e.expiresAt.After(now) {
        return Lease{}, ErrLeaseExpired // late renewal: reject with zero mutation
    }
    e.expiresAt = now.Add(timeout + margin)
    c.leases[key] = e
    return leaseFromEntry(key, e, now, timeout, margin), nil
}

// CheckToken: the token-check/fencing API for the resource side.
func (c *Coordinator) CheckToken(key string, token uint64) bool {
    c.mu.Lock()
    defer c.mu.Unlock()
    now := c.clock.Now()
    e, ok := c.leases[key]
    if !ok || !e.expiresAt.After(now) {
        return false // never leased, expired, or released -> stale
    }
    return e.token == token
}

// Release: only the current holder may release; fencing is immediate and the
// token counter is retained so the next grant still mints a strictly larger
// token.
func (c *Coordinator) Release(ctx context.Context, key, leaseID string) error {
    if err := ctx.Err(); err != nil { return err }
    c.mu.Lock()
    defer c.mu.Unlock()
    e, ok := c.leases[key]
    if !ok || e.id != leaseID { return ErrLeaseNotFound }
    delete(c.leases, key)
    return nil
}

Evidence & signatures

Verified with `go vet`, `gofmt`, and `go test -race` (14 tests, also run with `-count=5 -cpu=1,4,8` and 20× concurrent repeats — all stable). Files: `~/fencing/coordinator_test.go`.

**Behavioral proofs (fake-clock deterministic):**
- **Monotonic tokens:** 5 alternating release/expiry cycles mint tokens 1..5, strictly increasing; separate keys have independent sequences starting at 1 (`TestGrantMintsIncreasingTokens`).
- **No overlapping leases / election:** 64 goroutines racing `Grant` on a frozen clock → exactly 1 winner, 63 `ErrLeaseHeld`; winner's token validates (`TestConcurrentGrantSingleWinner`).
- **Late renewal rejected without corruption:** renewal lands 1ms after expiry → `ErrLeaseExpired`; state untouched; next grant mints exactly token+1 (not +2) (`TestLateRenewalRejectedWithoutCorruptingEpoch`). A renewal from the old epoch racing a fresh grant → `ErrLeaseNotFound`, current epoch intact (`TestLateRenewalRacingNewGrantCannotCorruptCurrentEpoch`, `TestConcurrentRenewAndGrant`).
- **Renewal keeps token and extends from now:** same token, expiry = processing-now + timeout + margin (no margin accumulation) (`TestRenewKeepsTokenAndExtends`).
- **Token check fences stale writers:** superseded tokens (`T−1`, `T+1`, `0`), released holders (fenced immediately even mid-term), expired holders, and never-leased keys all fail; only the current live token passes (`TestTokenCheckFencesStaleWriters`, `TestExpiredEpochTokenNeverIssued`).
- **Clock drift:** client clock ahead → still allowed within `timeout+margin`, fenced the instant the lease passes it; client clock behind → early renewal always succeeds with the same token (`TestClockDrift`).
- **Arbitrary message delay:** a grant processed late is anchored at processing time (expiry = now+timeout+margin), and a concurrently processed grant sees the first lease and is rejected (`TestDelayedGrantUsesProcessingTime`).
- **Robustness:** canceled contexts abort with no lease issued; zero/negative timeout and negative margin rejected; real-time 8-worker × 200-op stress under `-race` clean (`TestContextCancellation`, `TestInvalidArguments`, `TestRealTimeConcurrency`).

{"model": "deepseek-v4-flash", "problem_class": "fencing-token-lease-coordinator", "result": "passed", "tests": 14}

Generated from the verified corpus · MIT licensedBack to the catalog