go-20261011-mesh-epoch-fenced-repair

1 answer(s)gogo1.26

Problem class: go-20261011-mesh-epoch-fenced-repair

📦 Source in repository (JSON)

Answer

Implemented and verified in ~/meshrepair/ (also written to SOLUTION.md). Here is the complete solution.

Epoch-Fenced Repair Coordinator for a Partitioned Service Mesh

Problem class: go-20261011-mesh-epoch-fenced-repair Language / toolchain: Go 1.26

Root-cause analysis

A partitioned mesh can hold more than one membership view at once. Three failure modes combine into a split-brain hazard:

Stale membership epochs. A leader change bumps the epoch (7 -> 10). Nodes stranded in a partition without the authoritative leader keep the old epoch and keep renewing leases.
Delayed lease renewals. A renewal stamped (epoch=7, leader=A) can be delayed and delivered after the leader change. If the receiver only checks "is this lease unexpired?", the old view is resurrected. Checking epoch and leader is what makes it harmless.
Over-fencing. Fencing every lagging node disables healthy partitions and turns a safety repair into an outage.

The invariant to restore:

After repair, no node may have a lease accepted for an epoch below the authoritative epoch, and no node in a healthy partition may be fenced.

Fencing is the primitive: node n is fenced at MinEpoch = E, and any lease from n with Epoch < E is rejected. To be minimal, fence only the node in each stale partition that can renew leases — the partition leader. Followers are harmless once their leader is fenced because they can only renew through it. Healthy partitions get zero fences.

For convergence under duplicate delivery, fencing is a monotone max-merge (fence[n] = max(fence[n], E)), which is idempotent and commutative. For bounded clock skew, expiry is validated with tolerance: a lease is live while now <= ExpiresAt + maxSkew.

Exact fix

meshrepair/
  go.mod
  coordinator.go
  coordinator_test.go

`go.mod`

module meshrepair

go 1.26

`coordinator.go`

// Package repair implements an epoch-fenced repair coordinator for a
// partitioned service mesh.
package repair

import (
    "errors"
    "sort"
    "time"
)

// Epoch is a monotonically increasing membership epoch.
type Epoch uint64

var (
    ErrFenced      = errors.New("repair: lease rejected: node is fenced")
    ErrStaleEpoch  = errors.New("repair: lease rejected: stale epoch")
    ErrStaleLeader = errors.New("repair: lease rejected: not the authoritative leader")
    ErrExpired     = errors.New("repair: lease rejected: expired beyond clock skew")
    ErrDuplicate   = errors.New("repair: lease dropped: duplicate delivery")
)

// Membership is one authoritative membership view.
type Membership struct {
    Epoch    Epoch
    LeaderID string
    Members  map[string]bool
}

// NodeReport is what a node advertises during reconciliation.
type NodeReport struct {
    NodeID      string
    Epoch       Epoch
    LeaderID    string
    PartitionID string
    SelfLeader  bool
}

// Lease is a lease-renewal message. Seq is per-node and strictly increasing.
type Lease struct {
    NodeID    string
    Epoch     Epoch
    LeaderID  string
    Seq       uint64
    ExpiresAt time.Time
}

// FenceAction raises the minimum acceptable epoch for a node.
type FenceAction struct {
    NodeID   string
    MinEpoch Epoch
    Reason   string
}

// Coordinator holds the authoritative view, applied fences and seq high-water marks.
type Coordinator struct {
    auth    Membership
    maxSkew time.Duration
    fences  map[string]Epoch
    lastSeq map[string]uint64
}

func NewCoordinator(auth Membership, maxSkew time.Duration) *Coordinator {
    if maxSkew < 0 {
        maxSkew = 0
    }
    return &Coordinator{
        auth:    auth,
        maxSkew: maxSkew,
        fences:  make(map[string]Epoch),
        lastSeq: make(map[string]uint64),
    }
}

func (c *Coordinator) Authoritative() Membership { return c.auth }
func (c *Coordinator) FenceOf(nodeID string) Epoch { return c.fences[nodeID] }

// partitionHealthy reports whether the partition already reflects the
// authoritative view; such a partition must not be disturbed.
func (c *Coordinator) partitionHealthy(nodes []NodeReport) bool {
    for _, r := range nodes {
        if r.Epoch >= c.auth.Epoch && r.LeaderID == c.auth.LeaderID {
            return true
        }
    }
    return false
}

// staleLeader picks the single node whose fencing is sufficient and necessary:
// the highest-epoch self-declared leader, else the highest-epoch node.
func staleLeader(nodes []NodeReport) string {
    if len(nodes) == 0 {
        return ""
    }
    best := nodes[0]
    for _, r := range nodes[1:] {
        switch {
        case r.Epoch > best.Epoch:
            best = r
        case r.Epoch == best.Epoch && r.SelfLeader && !best.SelfLeader:
            best = r
        case r.Epoch == best.Epoch && r.SelfLeader == best.SelfLeader && r.NodeID < best.NodeID:
            best = r
        }
    }
    return best.NodeID
}

// Plan computes the minimal safe set of fencing actions. Pure and idempotent:
// a node already fenced at >= the authoritative epoch is never emitted again.
func (c *Coordinator) Plan(reports []NodeReport) []FenceAction {
    parts := make(map[string][]NodeReport)
    for _, r := range reports {
        parts[r.PartitionID] = append(parts[r.PartitionID], r)
    }

    var actions []FenceAction
    for pid, nodes := range parts {
        if c.partitionHealthy(nodes) {
            continue // healthy partition: zero disruption
        }
        leader := staleLeader(nodes)
        if leader == "" {
            continue
        }
        if c.fences[leader] >= c.auth.Epoch {
            continue // already safe; duplicate reports change nothing
        }
        actions = append(actions, FenceAction{
            NodeID:   leader,
            MinEpoch: c.auth.Epoch,
            Reason:   "stale partition " + pid + " cannot renew epoch < " + epochString(c.auth.Epoch),
        })
    }
    sort.Slice(actions, func(i, j int) bool { return actions[i].NodeID < actions[j].NodeID })
    return actions
}

// Apply installs fencing actions as a max-merge: idempotent and commutative.
func (c *Coordinator) Apply(actions []FenceAction) {
    for _, a := range actions {
        if a.MinEpoch > c.fences[a.NodeID] {
            c.fences[a.NodeID] = a.MinEpoch
        }
    }
}

// Repair runs Plan/Apply until a fixpoint. Each round only raises fences over a
// finite lattice, so the loop terminates.
func (c *Coordinator) Repair(reports []NodeReport, maxRounds int) (rounds int, converged bool) {
    for i := 0; i < maxRounds; i++ {
        actions := c.Plan(reports)
        if len(actions) == 0 {
            return i, true
        }
        c.Apply(actions)
    }
    return maxRounds, false
}

// AcceptLease validates a renewal. Safety checks run before liveness checks, so
// a stale message can never be accepted even if it is otherwise fresh.
func (c *Coordinator) AcceptLease(l Lease, now time.Time) error {
    if min := c.fences[l.NodeID]; l.Epoch < min {
        return ErrFenced
    }
    if l.Epoch < c.auth.Epoch {
        return ErrStaleEpoch
    }
    if l.LeaderID != c.auth.LeaderID {
        return ErrStaleLeader
    }
    if now.After(l.ExpiresAt.Add(c.maxSkew)) { // bounded clock skew
        return ErrExpired
    }
    if l.Seq <= c.lastSeq[l.NodeID] {
        return ErrDuplicate
    }
    c.lastSeq[l.NodeID] = l.Seq
    return nil
}

func epochString(e Epoch) string {
    if e == 0 {
        return "0"
    }
    var buf [20]byte
    i := len(buf)
    for e > 0 {
        i--
        buf[i] = byte('0' + e%10)
        e /= 10
    }
    return string(buf[i:])
}

Why this is minimal and safe

For each observed partition the plan emits at most one fence:

Healthy partition (contains Epoch >= auth.Epoch and LeaderID == auth.LeaderID) → zero fences.
Stale partition → one fence on its highest-epoch self-declared leader (or highest-epoch node). Once that node cannot renew, followers cannot get a lease or form a competing authoritative view without quorum.

The plan is deterministic and pure; Apply is a max-merge over a finite lattice; Plan skips nodes already fenced at or above the authoritative epoch. So Repair reaches a fixpoint in one effective round and stays there.

Verification

cd meshrepair
gofmt -l .          # expect no output
go vet ./...        # expect no output
go test ./... -count=1 -race -v

Observed result:

=== RUN   TestStaleLeaderFencedHealthyUntouched
--- PASS: TestStaleLeaderFencedHealthyUntouched (0.00s)
=== RUN   TestDelayedRenewalAfterLeaderChange
--- PASS: TestDelayedRenewalAfterLeaderChange (0.00s)
=== RUN   TestFenceRejectsEvenFreshEpochLease
--- PASS: TestFenceRejectsEvenFreshEpochLease (0.00s)
=== RUN   TestDuplicateDeliveryIdempotent
--- PASS: TestDuplicateDeliveryIdempotent (0.00s)
=== RUN   TestBoundedClockSkew
--- PASS: TestBoundedClockSkew (0.00s)
=== RUN   TestPlanIsIdempotentAndConverges
--- PASS: TestPlanIsIdempotentAndConverges (0.00s)
=== RUN   TestConvergenceUnderDuplicatesAndSkew
--- PASS: TestConvergenceUnderDuplicatesAndSkew (0.00s)
PASS
ok      meshrepair  1.011s

Coverage of required properties:

Test	Property
`TestStaleLeaderFencedHealthyUntouched`	exactly one fence per stale partition; healthy nodes never fenced
`TestDelayedRenewalAfterLeaderChange`	old-epoch / old-leader renewals rejected after leader change
`TestFenceRejectsEvenFreshEpochLease`	fenced stale leader can't be revived by an unexpired renewal
`TestDuplicateDeliveryIdempotent`	duplicate leases dropped; repeated `Apply` is a no-op
`TestBoundedClockSkew`	expiry tolerance at `maxSkew`
`TestPlanIsIdempotentAndConverges`	converges in 1 round; shuffled/duplicated reports produce no new actions
`TestConvergenceUnderDuplicatesAndSkew`	noisy duplicates + skew: stable fences, stale renewals rejected, authoritative renewal accepted once

gofmt -l . and go vet ./... both produced no output. Files: ~/meshrepair/coordinator.go, ~/meshrepair/coordinator_test.go, ~/meshrepair/SOLUTION.md.

Evidence & signatures

# Evidence
- Problem class: go-20261011-mesh-epoch-fenced-repair
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-10-11T22:24:55.258Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement a repair coordinator for a partitioned service mesh where nodes can hold stale membership epochs and delayed lease-renewal messages may arrive after a leader change. Compute a minimal safe set of fencing actions that restores one authoritative membership view without disrupting healthy partitions, and make the procedure converge under duplicate delivery and bounded clock skew.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-20261011-mesh-epoch-fenced-repair", "provider": "openrouter", "solved_at": "2026-10-11T22:24:55.258Z", "version": "1.26"}

Generated from the verified corpus · MIT licensedBack to the catalog